CH8. 트리(Tree) 1-1 (트리의 개요)

• 비선형 자료구조를 다루는 첫 번째 자료구조
• 선형/비선형 자료구조는 자료구조에 대해 접근하는 방식이 다름!
  • 선형: Data를 저장하는 개념으로 접근!
  • 비선형: Data를 표현하는 개념으로 접근!
    • Data의 표현에 저장이라는 개념이 포함됨
• 즉, 비선형 자료구조는 data를 표현하는 방식을 제시함

8-1 트리의 개요

• 연결리스트와 트리의 비교
• 연결리스트를 정의하는 구조체?
• 노드의 추가, 삭제, 탐색을 위한 변수 만 정의되어있음
  • 연결리스트면 포인터 변수, 배열기반이면 배열의 index
• 주로 data의 삽입, 삭제, 탐색 을위한 함수만 정의됨
  • 그 과정에서 자동으로 노드의 추가, 삭제가 부수적으로, 자동으로 이루어짐
  • 노드 자체의 삽입/삭제에 대한 함수는 정의되지 않음
    • 노드를 직접적으로 control 하는 함수는 없는 꼴
• 즉, 연결리스트에서는 자료구조를 data의 저장이라는 개념 중심으로 접근
• 트리를 정의하는 구조체?
  • 구조체 정의 자체가 연결리스트와 동일하지 않음!
  • 직접적으로 노드를 control 하는 함수를 정의
  • 즉, 트리 자체를 갖다 만드는, 노드 자체를 추가, 조합, 컨트롤하는 함수를 만듦
  • Tree 자체를 만드는 도구를 정의하게 됨
    • Data의 저장은 부수적인것일 뿐 중요하지 않음!
• 트리 자체를 만드는 도구를 기반으로 다양한 data를 표현하기 위해 도구 자체를 만듦
  • 우선 트리를 구성하는 도구를 만들고
  • 그 도구를 이용해 무엇인가를 표현 함.
• 연결리스트의 함수는 data의 저장, 삭제, 탐색을 위한 함수로 자동으로 노드가 삽입, 삭제 됨
• 트리는 data의 저장이 아닌 직접 노드 자체를 연결/끊는 여러 도구들을 만듦
• 트리는 두 단이면 펼쳤을 때 연결리스트와 동일한 모양이지만, 형태 자체는 중요하지 않음
• 또한 트리의 구현에 사용되는 노드는 배열 기반이건 연결리스트 기반이건 노드라는 자체가 중요하지 안에 형식은 중요하지 않음!
  • 앞에서 배웠던 노드를 기반으로 구현

트리의 접근과 이해

• 트리는 계층적 관계를 표현하는 자료구조임
  • 트리: 하나의 중심점을 기점으러 뻗어나가는 구조라는 의미
• 트리를 만드는 도구를 먼저 정의하는 이유?
  • 트리로 표현 가능한 많은 형태의 data들을 모두 표현하도록 기반작업을 하는 것!
    • 도구를 이용하여 모든 형태의 트리들을 다 표현 가능하도록!

트리 관련 용어의 소개

• 트리 공부할때 자만하지 말라고 강사님이..
• 용어는 아래와 같이 사용하되, 노드 자체는 연결리스트의 노드와 기본적으로 동일하지만 완전히 같다고 생각하면 안됨!

트리의 노드간 관계

• 트리는 계층적으로 해석
• 트리 노드간의 관계는 상대적인 관계
  • 항상 부모노드일수도, 항상 자식노드일수 없음.
    • 상대적 관계에 의해 정의되므로 비교대상에 따라 달라짐
• 동일 부모를 둔 노드라면 형제 노드로 정의!

• 트리는 다양한 서브트리를 갖고 잇으며, 서브트리 또한 다른 서브트리로 이루어져 있음
  • 따라서 구조 자체가 재귀적이므로 ‘재귀’에 대한 제대로된 이해가 필요!

CH7. 덱 (Deque) 3

7-5 덱(Deque)의 이해와 구현

• ‘디큐’가 아닌 ‘덱’으로 읽는 이유? -> 발음상 ‘디큐’ 가 맞지만, dequeue와의 구별을 위해 보통 ‘덱’으로 읽음
• Deque는 Double-end queue의 줄임말
• Stack과 queue의 자료구조적 특성을 모두 가짐
  • 활용에 따라 stack 또는 queue처럼 사용 가능하므로, 기능상 특성만을 생각했을 때 두 자료구조적 특성을 갖는다고 표현 가능
• 덱을 큐(queue) 단원에서 설명하는 이유?
  • 덱에 대해서 다룰게 많지 않기 때문임
• 덱(deque)이란?
  • Stack은 선입 후출, queue는 선입 선출적 특성을 갖는다면 deque은 queue 구조에서 양쪽으로 삽입 및 출력이 모두 가능한 구조임
    • 양쪽 아무데로나 data를 넣고 꺼낼 수 있음
  • 방향의 상관 없이, data를 어디로 넣었건 꺼내는 방향은 상관 없음
    • F로 넣고 F로 꺼내건, F로 넣고 R로 꺼내건 상관 없음
  • 단, 넣은 순서나 위치(F또는 R)에 따라 꺼낼때의 data는 달라짐

덱의 이해

• 덱은 앞으로, 뒤로도 넣을 수 있고, 앞으로, 뒤로도 뺄 수 있는 자료구조
  • 앞으로 넣기, 앞에서 빼기, 뒤로 넣기, 뒤에서 빼기 4가지 연산 가능
  • 모든 연산은 짝을 이뤄 수행되지 않으며 개별적으로 연산 가능

덱의 ADT

• 각각 연산의 종류에 따라 앞/뒤 위치의 입력 및 출력에 대한 4개의 삽입/참조 연산 함수와 위치에 따른 peek 연산의 정의 필요

덱의 구현: 헤더파일 정의

• 덱의 구현에 가장 적절한 자료구조는 양방향 연결 리스트
  • 단순 연결리스트로 구현 할 경우?
    • 새로운 데이터의 삽입에는 F나 R의 위치에 상관없이 가능
    • 기존 데이터의 삭제 시, R 부분의 데이터를 삭제 할 때 문제 발생!
• 단순 연결리스트로 구현된 덱의 R부분에서 데이터를 삭제한다면?
  • 삭제 하는 해당 노드 이전 노드의 주소로 R의 값을 초기화해줘야 하지만 이전 노드의 주소를 알 수 없음
    • 실제로 알 수 없는건 아니지만 알기에 과정이 복잡함 (F 위치부터 다시 주소를 찾아 나가야 하므로..)
  • 따라서 양쪽 노드(해당 노드의 앞, 뒤)의 주소를 모두 아는 양방향 연결리스트 가 덱을 구현하기에 가장 적절한 자료구조형
• 덱 구조체에는 앞/뒤 모두 입/출력이 이루어지므로 head 뿐만 아니라 tail 도 정의되어야 함

덱의 구현: 함수의 정의

• 양방향 연결리스트에서 tail 포인터 변수만 추가된 꼴!

CH7. 큐 (Queue) 2

7-3 큐의 연결 리스트 기반 구현

• 배열기반과 다르게 설명할 내용이 매우 적음!
  • 단순연결리스트의 복습정도 난이도..
• 본 수업에서는 F가 연결리스트의 머리 부분을 가리키고, R이 연결리스트의 꼬리 부분을 가리키도록 설정
  • F에선 노드가 참조되며 삭제되고, R에서는 새 노드가 추가되는 형태
• 연결리스트의 노드 추가에서 중간에서 추가하는 부분 필요 없이 머리에서만 삭제하고 꼬리에서만 추가되는 형태이므로 상대적으로 쉬움!

연결 리스트 기반 큐의 헤더 파일

• 일반적인 연결리스트와 크게 다를 것 없음
• 게다가 머리/꼬리에서 각각 삭제와 참조의 역할이 정해져있음
• 큐 구조체의 멤버로는 머리와 꼬리를 가리킬 front와 rear 포인터 변수만 있으면 됨
• 연결 리스트는 앞에서 공부했던 연결 리스트의 구조체를 그대로 가져다 씀

연결 리스트 기반 큐의 구현: 초기화

• 새 큐가 선언 될 때 각각 F와 R 모두 NULL 포인터로 초기화 됨.
• 하지만 큐가 비었는지 판단하기에는 F포인터 변수가 NULL인지만을 갖고 비었는지 판단
  • 왜 R 포인터변수는 확인하지 않는가?
    • R 포인터 변수는 F 포인터 변수에 종속적이며 뒤에서 세세하게 다룸.

연결 리스트 기반 큐의 구현: enqueue

• Enqueue의 과정은 두 과정으로 나뉨.
  • 큐가 비었을 때와 비어있지 않은 경우.
• 큐가 비어있을 때
  • F와 R 모두 새 노드를 가리키도록 설정
• 큐가 비어있지 않을 때
  • F는 그대로, R만 새 노드를 가리키도록 설정
• 논리 흐름 자체가 F가 NULL을 가리키는지 아닌지를 기준으로(if문) R의 동작이 결정됨
  • R이 F에 종속적인 이유

연결 리스트 기반 큐의 구현: dequeue 논리

• Dequeue의 논리 흐름은 다음과 같음
  1. F가 가리키던 노드의 주소값을 backup 한 후
  2. F가 가리키던 노드의 next 값으로 F를 초기화
  3. Backup해 두었던 주소의 노드를 삭제
• 이 과정에서 별도로 R에 대한 초기화를 수행하지 않음
• 즉, enqueue와 다르게 노드가 하나가 남건 여러개가 남건 동일한 흐름으로 진행 가능(if문 필요 x)
• 삭제 후 어차피 R은 free된 주소를 가리키게 되므로 의미없는 값이 됨

연결 리스트 기반 큐의 구현: dequeue 정의

연결 리스트 기반 큐의 실행

7-4 큐의 활용

• 실제시 시스템/하드웨어 개발이나 운영체제 등에서 사용됨

시뮬레이션의 주제

• 주어진 조건을 따름
• 대기실을 큐 라고 여기고, 제한시간 1시간동안 조건을 따르는 입력이 주어질 때 큐가 터지는지(메모리 에러) 터지지 않는지를 판단

시뮬레이션 예제의 작성

• 성공 및 실패 확률을 계산해보는 프로그램(아날로그로 계산해야하긴함..)
• 이런식으로 큐의 실제 예시 적용이 가능하다는것을 알면 됨.

인공신경망 학습 레시피

• 참고 글
  • https://karpathy.github.io/2019/04/25/recipe/
  • https://medium.com/@bntejn/%EC%9D%B8%EA%B3%B5%EC%8B%A0%EA%B2%BD%EB%A7%9D-%ED%95%99%EC%8A%B5-%EB%A0%88%EC%8B%9C%ED%94%BC-%EB%B2%88%EC%97%AD-70c5e58341ec
    • 원글의 번역본을 참고
• 네트워크의 학습시 시 발생할 수 있는 오류들을 줄이기 위한 프로세스를 정리
• 본문 시작전에 다음의 두 가지 중요 관찰사항에 대해 논함

1. 인공신경망의 학습과정은 딥러닝 라이브러리를 이용하여 완벽히 추상화하는것이 불가능함

• 보통의 딥러닝 라이브러리를 이용한 네트워크의 학습은 아래와 같은 흐름을 따름

dataset = my_dataset
model = my_model(my_transform, dataset, ResNet50, SGDOptimizer)

• 복잡한 실제 연산의 과정을 딥러닝 라이브러리는 위의 코드처럼 쉽게 표현되어있음
  • 하지만 실제로는 그렇지 않음
• 일반적인 딥러닝 모델의 학습에 역전파(back-propagation)와 SGD만 적용한다고 해서 인공신경망이 자동으로 동작하지 않음
  • Batch-norm을 적용한다고 해서 optimization이 마술처럼 이루어지는것도 아니고
  • RNN을 도입한다 해서 텍스트를 마술처럼 자동으로 이해하게 되는것도 아니며
  • 강화학습으로 문제를 정의할 수 있다 하여 꼭 그렇게 풀어야 하는것도 아님

2. 학습의 실패는 예고없이 등장함

• 코딩할 때 코드를 잘못 짜거나 설정을 잘못한다면 종종 예외처리문(error)을 만나게 됨
  • 문자열 자리에 정수를 넣거나, 매개변수 갯수가 다르다거나, import가 실패하거나, 혹은 입출력의 모양이 다르거나..
• 인공신경망 학습에 있어서 위와같은 쉬운 오류 외에 어디서 잘못되었는지도 모르는 오류가 발생할 확률이 매우 큼
  • 오류 자체가 구문적이며 단위적으로 테스트하며 디버깅하기가 매우 까다로움
  • 예를들어,
    • Data augmentation시 이미지의 좌우를 뒤집으면서 lable도 뒤집는것을 깜빡해서 인공신경망이 이러한 잘못된 정보까지 학습하는 바람에 오히려 모델의 정확도가 향상 될 가능성도 존재하게 됨.
    • 자기회기모델(auto-regressive model)을 학습시키며 off-by-one bug(배열이나 루프에서 바운더리 컨디션 체크와 관련한 논리적 에러)로 인해 예측하려는 값을 input으로 취하는 실수
    • Gradient를 잘라낸다는게 loss를 잘라내서 학습과정에서 outlier data들이 무시되게 될 수도 있음
    • 미리 학습해둔 checkpoint로부터 weight를 초기화했는데 해당 평균값을 쓰지 않는 실수
    • 정규화 세팅, 학습률, 학습률 감소율, 모델 크기 등에 대한 설정 잘못
  • 위의 경우 외에도 어떠한 잘못된 설정으로 네트워크를 학습시켰을 때 정확도가 좋아질 수 있고, 이는 순전히 운이 좋은경우에 해당
  • 대부분의 경우 학습은 문제없다는듯이 잘 진행되며 성능만 살짝 덜어지게 됨
• 이로인해 신경망을 학습하기 위한 방법으로 빠르고 강력한 방법은 전혀 효과적이지 않고 오히려 학습에 어려움을 줄 수 있음
  • 네트워크를 빠르게 학습시키는 여러 방법들이 실제로는 효용성이 떨어진다는 의미로 판단됨.
• 따라서 네트워크의 학습에는 조심스럽고 방어적이고 시각화를 중요하게 여기는 방향으로 접근해야 학습에 좀 더 효과적임
  • 글쓴이의 경험에 따르면.. 참을성 있게 디테일에 집착하는 태도가 딥러닝 모델의 학습을 성공시키는데 가장 중요한 요소라고 함.

레시피

• 위에서 언급한 두 사실에 근거하여 저자가 제안하는 늘 참고하는 구체적인 학습의 프로세스를 소개함
  • 각 단계를 거치며 모델은 단순하게 시작해서 점차 복잡해지며, 매 단계마다 어떤 response가 발생할지에 대한 구체적 가설을 세우고, 각 단계가 적용된 후 혹시 발생했을지 모를 문제를 찾아내기 위해 실험과 검증을 반복
• 이렇게 보수적(조심스럽게)으로 접근하는 이유는 검증되지 않은 복잡성(새로운 것을 적용하는것)의 증가를 최대한 방지하고, 발견이 힘들거나 발견자체가 불가능할 수 있는 버그나 오류를 최대한 예방하기 위함임
• 네트워크의 학습시키는 코드를 짜는것을 인공지능망 학습과정에 비유하면 작은 학습률로 학습을 시작한 뒤 매 iteration마다 테스트 데이터셋 전체를 평가하듯이 각 단계를 진행해야 함.
  • 하나의 방법을 적용하고 effectiveness validation 후 다음 방법을 적용해야 함을 의미

1. 데이터와 하나가 되기

• 인공신경망 학습의 첫 단계는 코드는 건드리지 않고 학습용 데이터셋을 철저하게 살피는것!(매우 중요)
  • 수천개의 데이터를 훑어보며 분포를 이해하고 패턴을 찾는 과정
  • 중복된 데이터, 손상된 이미지, 손상된 레이블 등을 발견하고 제거
  • 데이터의 불균형, 편향을 발견하고 조절
• 데이터의 분석을 통해 궁극적으로 사용하게 될 아키텍쳐에 대한 힌트를 얻을 수 있음
  • 예를 들어 아주 지역적인 특성들 만으로 충분한지, 혹은 전역적인 맥락이 필요한지, 얼마나 많은 변화가 있고 어떤 형태들을 갖는지, 어떠한 비정상적인 변화가 감지되고, 전처리를 통해 제거가 가능한지, 공간적 위치가 중요한지, 어떤 pooling 방식이 좋을지, 세부사항이 얼마나 중요하고 얼마나 많은 이미지들을 샘플링을 통해 줄일 수 있을지, 레이블에 얼마나 노이즈가 많은지 등을 살펴볼 수 있음
• 또한 인공신경망이란 결국 데이터를 압축하고 일반화시켜주는 도구이기에 네트워크의 에러를 보고 어디가 잘못된 것인지도 알 수 있음
  • 만약 정확도가 원래의 것보다 떨어진다면 무언가 잘못되었다는걸 직관적으로 알 수 있게 됨
• 데이터의 품질에 대한 대략적인 감을 잡았다면 학습시킬 데이터를 찾고, 걸러내고, 정렬하기 위한 간단한 코드를 작성
  • 그 기준은 레이블의 타입, annotation,의 크기와 숫자 등 고려 가능한 어떠한 것이 될 수 있음
  • 각 기준에 따른 데이터의 분포를 시각화해보고 각 기준에 따라 시각화 했을 때 분포를 벗어나는 튀는 outlier들을 찾아봄
  • Outlier는 대부분 데이터 품질이나 전처리 과정의 오류로 인해 발생했을 가능성이 큼

2. 학습에서 평가까지 전 단계를 아우르는 골격을 먼저 짜고 기준 성능을 측정

• 이번 단계에선 확실하게 성능이 검증되는 작은 크기의 신경망이나 선형 분류기를 선택해서 테스트하는게 좋음
  • 위의 모델을 학습시키고 loss를 시각화하며 metric 측정 후 모델이 추론한 결과를 이용
• Random seed 이용. 랜덤한 seed를 이용하여 초기값을 설정하면 코드를 돌릴때마다 항상 동일한 결과가 나오게 할 수 있음.
  • 가변 변수를 하나 줄임으로써 안정성 확보
• 단순화. 학습에 필수적이지 않은 data augmentation등을 적용하지 않도록 해야 함.
  • 일반화 성능을 향상시켜주는 data augmentation은 debugging을 더 어렵게 만듦
• Validation에서의 loss 확인. Test loss를 plot할 땐 전체 테스트셋에 대한 결과를 plot해야 함. 단순히 배치에 따른 test loss를 시각화하면서 loss을 매끄럽게 하는것보다 전체 testset에 대한 loss를 확인하는것이 중요. 또한 validation loss가 낮아야 학습이 잘 된 것으로 validation loss가 낮도록 모델을 학습
• 초기 손실값 확인. 초기 loss가 올바르게 잘 감소하고 있는지 확인. 예를들어 마지막 레이어를 잘 초기화했다면 softmax 결과에서 -log(1/clas갯수)가 측정되어야 함. L2 regression등에도 이와같이 기본값을 유도 가능
• 초기화 잘 하기. 마지막 레이어의 weight를 잘 초기화. 예를들어 평균이 50인 값에 근사시킨다면 최종 bias를 50으로 설정. 이러한값들을 잘 설정해서 학습 초기에 하키스틱 모양의 발산하는 loss 그래프를 피할 수 있음
• Human baseline. Loss 외에도 정확도같이 사람이 해석 가능한 metric을 모니터링. 또는 매 테스트마다 주석을 달아서 하나는 예측값, 하나는 GT로 간주해 사용
• Input-independent baseline. 입력과 독립적인 기준값을 학습. 예를 들어 모든 입력을 0으로 하게되면 real data가 들어가면 성능이 떨어지게 됨. 아무 정보가 없는 데이터로부터 모델이 아무런 정보도 얻지 못하는 것.
• Overfit one batch. 아주 작은 예제에 한해서 하나의 배치에만 과적합 시키기. 이를 위해 layer나 필터를 더해서 모델의 용량을 키우고 0에 근접한 loss를 얻을 수 있는지 확인해야 함. 레이블과 예측값을 하나의 그림에 시각화시켜 손실값이 최소일 때에도 둘이 잘 일치하는지를 확인. 그렇지 않다면 어디엔가 문제가 있는 상황
• 학습 loss가 감소하는지 확인. 조금 네트워크 용량을 키운 모델에 대해 학습 loss가 잘 감소하는지 확인
• 모델에 feed되기 전의 데이터를 시각화. 네트워크에 학습 데이터가 들어가기 바로 직전 단계에서 tensor에 저장되어있는 테이터와 레이블을 해석.
• 학습 중 예측값의 변화를 시각화. 미리 정해둔 임의의 test batch에 대해 예측값이 어떻게 변하는지를 시각화. 이를 통해 직관적 이해가 가능. 데이터가 특정한 방향이 아닌 오락가락하게 움직이면 모델이 instable함을 의미하게 됨. Learning rate가 너무 낮거나 높은 경우에도 이를통해 알아차릴 수 있음
• Dependency를 알기 위해 역전파 이용. 보통 대부분의 실수는 배치사이 차원간에 정보를 섞어버리는 실수. 이렇게되도 학습은 보통 계속됨.(다른 case로부터 섞인 필요없는 정보를 무시하도록 네트워크가 학습되므로) 특정 예제 i에 대한 loss를 1.0으로 설정하고 입력단까지 back propagation시켜서 해당 i번째 입력에 대해서만 0이 아닌 gradient가 계산되는지를 출력해보면 됨. 즉, 경사도를 이용해 신경망이 어떤 정보에 의존적인가에 대한 정보를 얻을 수 있음.
• Generalize a special case. 보통 코딩시 처음에는 매우 구체적인 함수부터 시작해서 잘 동작하는지 확인한다음 일반적으로 작동하는 함수를 다시 짜서 올바른 결과가 나오는지 확인하는 방법을 사용. 벡터 연산 코드에도 종종 쓰임.

3. Overfitting 시키기

• 이 단계에 다다르면 데이터셋에 대한 이해도도 충분하며 학습과 평가를 해주는 파이프라인도 잘 동작한다는 의미임.
• 좋은 모델을 찾기위해 택하는 방법은 두 단계로 나뉘어짐.
  • 첫째, 과적합에 용이한 큰 모델을 학습시키면서 학습 손실값을 최소화하는데만 집중
  • 둘째, 정규화를 적당히해서 validation에 대한 손실값을 줄임. 여기서 loss의 손실이 약간 발생함.
• 위의 일련의 과정을 통해 어떤 모델을 사용했건 오류값 자체가 줄어들지 않는다면 이를통해 버그나 잘못된 설정 등의 이슈를 잡아 낼 수 있기 때문
• 모델 선정. 학습에 적당한 모델을 선정하며, 다른 사람들이 일반적으로 사용했을 때 결과가 좋은 구조를 그대로 사용하는것을 추천함.
• Adam 사용 추천. 학습 초기단계에서 Adam을 learning rate 3e-4 정도로 하여 사용하는것을 추천함. 이유는 Adam이 lr을 포함한 다양한 하이퍼파라미터 설정에 영향을 가장 적게 받기 때문. CNN에선 튜닝 잘 된 SGD가 거의 모든 경우에 adam보다 더 나은 성능을 보여주나 최적의 learning rate 구간은 매우 좁고 task에 따라 가변적임. 즉, SGD가 적절히 동작하는 lr 구간을 찾기가 힘듦.
• 복잡도는 한번에 하나씩 더하기. 분류기 모델의 성능 향상을 위해 적용될 각종 알고리즘이 여러개일 경우 한번에 하나씩만 적용하고, 늘려갈 때마다 실제 기대한것처럼 정확도가 향상되는지를 확인해봐야함.
• Learning rate decay를 너무 믿진 말기. 다른 도메인에서 쓰이던 코드를 가져와서 재사용하는 경우 learning rate decay를 매우 조심해서 사용해야 함. 서로 다른 task에 대해 다른 learning rate decay function을 쓰는건 당연한 일. 게다가 lr decaying function은 보통 현재 epoch 숫자에 맞춰 계산되도록 구현되어 있는데, 적정 epoch은 dataset의 종류에 따라 크게 달라짐. 예를들어 ImageNet일때 30 epoch에서 1/10 decaying이지만, 다른 데이터셋은 다른 epoch에 적용되어야 함. 이로인해 lr이 너무 빨리 작아져서 적절하게 모델이 학습되지 않을 수 있음. 따라서 데이터셋에 따라 decaying을 일단 적용하지 말고, 마지막에 튜닝하는식으로 적용시켜야 함.

4. 일반화(Regularize)

• 지금까지 문제가 없었다면 최소한 학습용 데이터셋에는 확실하게 맞춰진 큰 모델을 갖고있게됨을 의미.
• 이제 regularization을 적용해서 학습정확도는 좀 잃더라도 테스트 정확도를 올릴 차례.
• 더 많은 학습용 데이터셋. 어떠한 경우에도 모델의 일반화에 최선의 방법은 더 많은 실제 데이터를 모으는것임. 더 많은 데이터를 모을 수 있는 상황에서 엔지니어링에 많은 노력을 소모하는것은 매우 흔한 실수. 더 많은 학습용 데이터를 통해 네트워크의 성능을 지속적으로 향상 시킬 수 있음. 차선책으로는 앙상블모델이 있지만 앙상블도 5개정도 모델 이후로는 성능이 증가하지 않음
• Data augmentation. 실제 데이터셋을 더 확보하는 방법 다음으로 좋은 방법은 가짜 데이터셋을 만들어 내는 것임. Resize, crop, flipping 등의 distortion을 이용하여 원래 학습 데이터셋보다 더 많은 학습용 데이터셋을 확보 가능
• Creative augmentation. Data augmentation 외에도 도메인 랜덤화, 시뮬레이션, 데이터와 배경을 합성시키는 하이브리드 기법, GAN등을 이용한 데이터의 증대 가능
  • http://vladlen.info/publications/playing-data-ground-truth-computer-games/?fbclid=IwAR3Bbb2-JTT46xou6-ueUpAXdqM3bL2i9UivKKRn05oRWCNnp7QRupTBZWA
  • https://arxiv.org/abs/1708.01642?fbclid=IwAR2pQV7k2oj8H6j2ndxTNCx5IC46VZMGgg2uFElT0CuzOAufePq-ea6JdU8
• Pre-training. 미리 학습시킨 네트워크를 사용하는 경우 웬만해선 성능이 더 좋음. 이미 충분한 데이터가 존재하더라도 pre-trained model을 불러와서 재학습시킬 때의 정확도가 훨신 높음.
• 지도학습 고수하기. 비지도학습에 현혹되지 말 것. 최신 결과물 중 쓸만한 방법이 없음. 반면 자연어처리 분야는 BERT 등의 비지도학습 기법들의 성능이 좋은 편.
• 입력 차원은 낮게. 이상한 정보를 포함하는 feature를 제거시켜야 함. 이상한 입력이 추가될수록 학습용 데이터셋이 충분하지 않은 경우 overfitting이 발생하게 됨. 이미지 내의 정보중 세세한 디테일한 내용이 중요하지 않다면 작은 이미지를 이용해 학습시키는것도 좋은 방법이 될 수 있음.
• 모델 크기는 작게. 대부분의 경우 도메인에 대한 knowledge를 이용해 신경망의 크기를 줄일 수 있음. 예를 들어 ImageNet의 backbone 가장 마지막에 fc layer를 사용하곤 했지만 훗날 average pooling으로 대체되며 파라미터 수를 많이 줄일 수 있게되었음.
• Batch size는 작게. Batch normalization 안의 정규화 때문에 작은 크기의 batch가 더 일반화 성능을 더 좋게 함. 이는 batch의 평균/분산 값들이 전체 데이터셋의 평균/분산 값의 추정치이기 때문인데, 작은 크기의 batch를 사용하면 scale과 offset 값이 batch에 따라 더 많이 wiggle되기 때문임.
  • 즉, 작은 크기의 batch를 사용함에 따라 학습과정에서의 불확실성(noise)이 증가하게 되어 일반화 성능이 향상될 수밖에 없음. 작은 크기의 batch는 그만큼 많은 parameter update가 수행되므로 noise성분을 더 많이 갖게 됨.
• Drop. 드롭아웃을 추가. ConvNet의 경우 Dropout2d (spatial dropout)을 적용. 단, Dropout은 batch norm과 잘 어울리지 못하므로 주의해서 적당히 써야 함.
  • https://arxiv.org/abs/1801.05134?fbclid=IwAR01IhZoe7yftt9oml_-DHSWqvHXqwjOzAXGtus1ZTCYvoEff8IuUQoNBi8
• Weight decaying. Weight decaying penalty를 증가시킴.
• Early stopping. 지금까지 측정된 validation loss를 이용하여 overfitting이 시작되려는 시점에 학습을 종료

• 더 큰 모델을 시도. 맨 마지막으로 큰 모델을 사용할 경우 overfitting될 수 있지만 그 전에 학습을 미리 멈추게 될 경우 작은 모델보다 훨씬 나은 성능을 보여 줄 수 있음

• 마지막으로, 학습시킨 분류기가 잘 동작한다는 추가적 확신을 얻기 위해 네트워크의 첫 번째 레이어의 weight값을 시각화해서 깔끔한 모서리가 나오는지를 확인. 만약 filter(weight 값)가 noise처럼 보인다면 제대로 학습된 것이 아니라고 의심 해 볼 수 있음. 비슷하게 네트워크의 중간 weight값을 시각화해서 이로인해 뭐가 잘못되었는지를 파악 할 수 있음.

5. Tunning

• 그리드 탐색보단 무작위 탐색. 여러 개의 하이퍼파라미터를 그리드 탐색방법으로 동시에 튜닝하게 될 경우 경우의 수가 너무 많음. 무작위 탐색방법을 적용하는게 가장 효율적임. 이유는 인공신경망의 성능이 특정한 소수의 파라미터에 훨씬 민감하게 반응하기 때문임. 예를 들어 파라미터 a를 변경했을 때 loss가 달라졌지만 b는 변경해도 아무런 영향이 없다면 a를 더 철저히 sampling해보는게 더 좋은 방법.
  • http://jmlr.csail.mit.edu/papers/volume13/bergstra12a/bergstra12a.pdf?fbclid=IwAR3DcdRfOMcrro_RyetpXE-CARWpn9fpYvLLIZjP2qXnyEGBDDYnvkTlNUk
• 하이퍼파라미터 최적화. 정말 다양하고 많은 베이지안 하이퍼파라미터 최적화 도구들이 존재. 최고의 방법은 노가다.

6. Squeeze out the juice

• 최적의 아키텍처와 하이퍼파라미터를 찾아낸 후에도 마지막 한방울의 성능까지 짜낼 수 있는 몇 가지 트릭이 존재.
• 앙상블 모델. 앙상블 모델은 어떠한 경우에서라도 2%정도의 정확도를 올려주는 확실한 방법임. 계산량 부담이 불가능한 경우 dark knowledge distillation을 통해 앙상블 모델의 정보를 작은 단일 모델로 증류(distillation)하는 기법을 시도.
  • https://arxiv.org/abs/1503.02531?fbclid=IwAR2HSli0-ilYp5SVP6avCmIyYV95KpSAm-nrJZ7w5wDn-MnDl6nRnHb9Edw
• 계속 학습 시키기. Validation loss가 줄어들지 않으면 대부분 학습을 중단시킴. 하지만 경험상 아무리 오랜시간 학습시켜도 학습은 계속되게 되어있음. 저자의 일례로 휴가기간 내내 실수로 돌려둔 학습모델의 성능이 엄청 좋아진 경험이 있다고 함.

결론

• 위의 일련의 과정을 통해 성공적인 학습을 위한 모든 요소들을 갖추게 됨. 기술, 데이터셋, 해결하고자 하는 문제에 대한 깊은 이해, 학습과 평가를 위한 총체적인 인프라를 갖추었으며 더 복잡해지는 모델들도 탐색하고, 각 단계에서 예측가능한 만큼의 성능 향상도 이루었을 것임. Good luck!

CH7. 큐 (Queue) 1

• 큐를 마지막으로 선형 자료구조가 끝나며, 8단원부터는 비선형 자료구조를 다룸
  • 따라서 챕터 7까지 학습 완료 후 선형자료구조에대한 전반적인 복습이 필요

• 선형자료구조와 다르게 비선형자료구조 파트는 조금 더 어려울 수 있기에 선형자료구조에대한 확실한 이해가 필요함

• 스택과 큐의 경우 이론은 어렵지 않으나 스택의 활용범위가 다양해서 계산기구현등의 까다로운 적용예시가 있었음
  • 큐는 그렇지 않음..

7-1 큐의 이해와 ADT 정의

• 큐는 FIFO(First-in, First-out) 구조의 자료구조로, 선입선출의 특성을 가짐
  • 일종의 줄서기와 동일
    • 스택은 프링글스처럼 하나의 입구로 넣고 빼는 방식
    • 큐는 종이컵분배기처럼 입구와 출구가 따로있어 먼저 넣은 데이터가 먼저 빠져나오게 됨
• 큐의 기본연산
  • 큐에서 데이터를 넣는 연산 -> enqueue
  • 큐에서 데이터를 빼는 연산 -> dnqueue
• 큐는 운영체제 관점에서 보면 프로세스나 쓰레드의 관리에 활용되는 자료구조
  • 이렇게 운영체제의 구현에도 자료구조가 사용이 되며, 운영체제의 학습 이전에 자료구조에 대한 이해가 선행되어야 함

큐의 ADT 정의

• 다음의 ADT를 이용하여 배열 기반의 큐 또는 연결 리스트 기반의 큐 를 구현 할 수 있음

7-2 큐의 배열 기반 구현

• 연결리스트/배열을 이용한 큐의 구현 중 배열기반의 큐 구현이 갖는 의미가 연결리스트보다 더 큼

큐의 구현 논리

• 입구가 있고 출구가 따로 존재하므로, 입구와 출구에 대한 코드 적용 시 별도의 방법을 고안해야 함
  • F, R 포인터 변수를 설정해서 F를 출구쪽, R을 입구쪽으로 설정

가장 기본적인 배열 기반 큐의 문제점

• 문제점
  • 배열의 길이가 정해진 경우, R포인터를 더 오른쪽으로 옮길 수 없는 상황에서 문제가 발생
  • 먼저 들어온 데이터가 참조되어 빈 공간인데도 활용하지 못하는 상황이 발생
• 이러한 문제를 해결하기 위해 맨 마지막 배열을 맨 앞의 배열과 연결(인덱스 조절하여 설정이 가능)하는 원형 큐 를 사용

원형 큐의 소개

• 전제조건: R과 F는 배열의 끝에 오면 맨 앞으로 다시 가게 된다.

원형 큐의 단순한 연산

• Enqueue: R 포인터가 이동 후 해당 자리에 새로 들어온 데이터를 저장
• Dequeue: F 포인터가 가리키던 자리의 데이터를 반환 후 이동

원형 큐의 단순한 연산의 문제점

• F, R이 같은 위치를 가리키면 데이터가 하나 저장된 상태
• R 포인터 바로 다음이 F 포인터인 경우 원형 큐는 다 찬 상태거나 텅 빈 상태이거나 둘중 하나임
  • 즉, 원형 큐가 빈 상태인지, 다 차 있는 상태인지 구분 할 수 없음
• 따라서 F와 R의 관계를 다시 정의하고 구분하여 원형 큐가 다 차있는 상태인지 빈 상태인지를 구별해야 함

원형 큐의 문제점 해결

• 텅 비어있는 상태를 초기화 상태로 정의하고, 초기화 상태에서 F와 R은 같은 배열 index를 갖도록 설텅
• 초기화 된 상태, 즉 F와 R이 같은 공간을 가리키는 상태를 Empty 상태로 정의
  • 해당 상태에 해당 index에는 정보를 넣지 못함
    • 메모리 손실!
    • 하지만 일반적으로 배열의 길이가 매우 길어지므로 한 칸의 메모리 손실은 매우 적으며, 이로인한 코드상의 이점이 훨씬 크므로 의미있음!

• R 바로 다음자리가 F가 되는 경우 Full 상태로 정의

• 즉, 다음과 같은 상대적인 F와 R의 관계를 통해 Empty와 Full을 구분
  • R == F: Empty
  • R+1 = F: Full
• 참고로 절대위치가 아닌 상대위치임!

원형 큐의 구현: 헤더파일

• 포인터 변수인 front(F)와 rear(R)은 배열의 index를 나타냄
• F와 R의 위치를 알고 배열의 끝에 도달했을 때 다시 0번 인덱스로 보내주는 helper function 정의 필요

원형 큐의 구현: Helper Function

• front, rear 값이 이동 시 가져야 할 올바른 index값을 반환하도록 정의
  • front나 rear의 값(배열의 index)이 맨 마지막일 경우 처음 값인 0을 반환하고
  • 아니면 다음 index를 반환하도록 정의

원형 큐의 구현: 함수의 정의1

• 각각 초기화 함수와 비어있는지를 구분하는 구분하는 함수
• 초기화 값이 0이 아닌 다른값이어도 동작에는 전혀 문제가 없음!
  • 원형 꼴이므로

원형 큐의 구현: 함수의 정의2

• Enqueue는 원형큐가 꽉 찬 경우를 제외하고 다음 인덱스값을 얻은다음 update된 인덱스 자리에 새로운 값을 저장함
• Dequeue는 원형큐가 텅 빈 경우를 제외하고 다음 인덱스값을 얻은다음 update된 인덱스 자리의 데이터를 반환
  • 둘 다 포인터 이동 후 en/de queue 연산 실행

원형 큐의 실행