해당 게시물은 파이썬으로 만드는 OpenCV 프로젝트(이세우 저) 를 바탕으로 작성되었습니다.

영상 처리와 컴퓨터 비전

영상 처리

영상 처리(image processing)는 카메라로 찍은 사진 또는 영상에 여러 가지 연산을 가해서 원하는 결과를 새롭게 얻어내는 과정입니다. 대부분 영상 처리의 목적은 더 좋은 품질의 영상을 얻으려는 것입니다. 몇 가지 예를 들면 다음과 같습니다.

• 영상(화질) 개선: 사진이나 동영상이 너무 어둡거나 밝아서 화질을 개선하는 과정
• 영상 복원: 오래되어 빛바랜 옛날 사진이나 영상을 현대적인 품질로 복원하는 과정
• 영상 분할: 사진이나 영상에서 원하는 부분만 오려내는 과정

컴퓨터 비전

컴퓨터 비전은 영상 처리 개념을 포함하는 좀 더 큰 포괄적인 의미입니다. 영상 처리가 원본 영상을 사용자가 원하는 새로운 영상으로 바꿔 주는 기술이라면 컴퓨터 비전은 영상에서 의미 있는 정보를 추출해 주는 기술을 말합니다. 예를 들면 다음과 같습니다.

• 객체 검출(object detection): 영상 속에 원하는 대상이 어디에 있는지 검출
• 객체 추적(object tracking): 영상 속 관심 있는 피사체가 어디로 움직이는지 추적
• 객체 인식(object recognition): 영상 속 피사체가 무엇인지 인식.

일반적으로 컴퓨터 비전 작업은 입력받은 원본 영상을 영상 처리하여 원하는 품질의 결과 영상을 얻어낸 다음, 컴퓨터 비전으로 원하는 정보를 얻어내는 과정이 반복적으로 일어납니다.

OpenCV

OpenCV 개요

OpenCV는 오픈 소스 컴퓨터 비전 라이브러리(Open Source Computer Vision Library)를 줄여 쓴 말로, OpenCV는 영상 처리와 컴퓨터 비전 프로그래밍 분야의 가장 대표적인 라이브러리입니다.

OpenCV는 사진 혹은 영상을 처리해주는 포토샵 기능을 프로그래밍 언어로 구현할 수 있게 해주는 라이브러리라고 생각해도 크게 틀리지 않습니다.

OpenCV의 공식 웹사이트와 문서는 다음과 같습니다.

• https://opencv.org/
• https://docs.opencv.org/4.x/index.html

OpenCV의 소스 코드 저장소는 다음과 같이 2개로 나뉩니다.

• 메인 저장소 : https://github.com/opencv/opencv
• 엑스트라(extra) 저장소 : https://github.com/opencv/opencv_contrib

메인 저장소에서는 OpenCV 공식 배포에 사용하는 코드를 관리합니다. 엑스트라 저장소는 컨트리브(contrib) 저장소라고도 하는데, 아직 알고리즘이나 구현의 성숙도가 떨어지거나 대중화되지 않은 내용을 포함하고 있으며, 향후 완성도가 높아지면 메인 저장소로 옮겨집니다.

M1 Mac에서 OpenCV 설치

M1 Mac에서 OpenCV 설치를 진행해보겠습니다. OpenCV 학습을 위하여 다음과 같이 개발환경을 세팅했습니다.

Python 3.6
Numpy 1.14
OpenCV-Python 3.4.1, 엑스트라(contrib) 포함
Matplotlib 2.2.2

1. Anaconda 설치

효율적으로 가상환경을 관리하기위해 anaconda를 먼저 설치하겠습니다. 다음과 같이 anaconda 홈페이지에 들어가서 자신의 운영체제에 맞는 Installer를 다운받아 설치하는 방법이 있습니다.

• https://www.anaconda.com/products/distribution

하지만 여기에서는 homebrew로 conda를 설치하겠습니다.

brew install anaconda

터미널에서 아래의 명령어를 입력하여 제대로 설치되었는지 확인합니다.

conda

만약 zsh: command not found: conda 라는 에러가 발생할 경우, 설치경로를 찾아 conda init zsh를 입력 후 쉘을 재시작하면 됩니다.

/opt/homebrew/anaconda3/bin/conda init zsh

이후 다음과 같이 나오면 anaconda 설치완료입니다.

> conda -V
conda 22.9.0

또한 conda 설치시 기본 파이썬 버전이 3.9로 바뀌고, conda base 환경을 쓰게 됩니다. 이 점 주의해주세요.

> python --version
Python 3.9.13

2. 가상환경 만들기

우선, 파이썬 3.6 버전을 갖는 가상 환경을 만들어줍니다.

# Anaconda 환경에서 가상환경 만들기
conda create -n opencv python=3.6

파이썬 3.6 버전이 설치된 opencv라는 이름의 가상 환경이 만들어졌습니다. 이렇게 만든 가상 환경을 아래와 같이 실행해 줍니다.

# 가상환경 실행
conda activate opencv

가상 환경 안에 원하는 버전의 모듈을 설치합니다.

# numpy 1.14 버전 설치
pip3 install numpy==1.14.0

# 엑스트라(contrib)를 포함한 OpenCV-Python 모듈 3.4.1 설치
pip3 install opencv-contrib-python==3.4.1.15

# matplotlib 2.2.2 버전 설치
pip3 install matplotlib==2.2.2

이제, prompt 창에서 python을 실행시킨 뒤 아래와 같이 입력하면 각 모듈별 버전이 뜰 겁니다. 다른 버전이 뜨면 설치가 잘못되었거나 가상 환경 세팅이 잘못된 겁니다.

>>> import numpy
>>> numpy.__version__
'1.14.0'


>>> import cv2
>>> cv2.__version__
'3.4.1'

>>> import matplotlib
>>> matplotlib.__version__
'2.2.2'

이상으로 OpenCV의 개요와 설치 방법에 대해 알아봤습니다.

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Last Time: CNN Architectures

• 지난 강의에서는 CNN 아키텍쳐들을 배웠습니다.
• ImageNet Classification Challenge를 중심으로 연대순 우승자들을 알아봤습니다.
• 2012년에는 AlexNet이 있었으며, AlexNet이 Computer Vision의 진화를 촉발시켜 딥러닝 시대의 서막을 열었습니다.

• 2014년, 이전의 모델들보다 훨씬 더 깊어진 두 모델인 VGG와 GoogLeNet 입니다.
• Batch normalization이 발명되기 전 모델로, 레이어가 깊은 모델을 학습시키는 일은 상당히 어려웠지만, 이 두 모델은 깊은 모델을 수렴시키기 위해서 각종 테크닉(hackery)을 썼습니다.

• 2015년에는 ResNet이라는 아주 멋드러진 모델이 있었습니다.
• ResNet은 shortcut connection과 residual block이 도입된 모델입니다.
• ResNet에서 레이어의 출력은 (input + residual block의 output) 입니다. 이 구조는 큰 특징을 가지고 있습니다.
  1. residual block의 가중치가 0이면 이 block은 indentity mapping을 합니다.
     • 모델이 “필요없는 레이어” 를 사용하지 않도록 학습하는데 아주 유용합니다.
     • ResNet의 관점에서 L2 Regularization으로 해석할 수 있는데, 레이어에 L2 Regularization을 추가시키면 L2는 모든 파라미터가 0이 되도록 노력할 것이며, 파라미터들을 계속 0으로 보내면 residual block이 identity가 되기 때문에, ResNet의 관점에서는 파라미터를 0으로 만드려는 속성은 모델이 불필요한 레이어를 사용하지 않도록 해줄 수 있습니다.
  2. backward pass 에서의 gradient flow
     • “Addition gates”가 backward pass시 Upstream gradient가 두 갈래로 나눠지게 됩니다.
     • Upstream gradient가 오면 convolution block으로도 흘러들어가지만, residual connection 덕분에 현재 레이어를 생략하고 직접 이전 레이어로 흘러갈 수도 있습니다.
     • gradient를 원활하게 전달하기 위해, Residual connection은 gradient를 위한 일종의 고속도로 역할을 하여 학습을 더 쉽고 빠르게 할 수 있고, 모델이 엄청 깊더라도 잘 수렴할 수 있도록 도와줍니다.

• DensNet, FractalNet 과 같이 발전된 CNN 아키텍쳐도 살펴보았습니다.
• 이 모델들은 gradient flow의 관점에서 모델 내부에 additional shortcut (identity)를 추가합니다.
  • Loss와 각 Layer를 직접 연결하기 때문에 backward pass가 아주 수월합니다.

• 모델 별 연산량, 크기에 관한 그래프입니다.
• AlexNet와 VGGNet는 파라미터가 엄청 많습니다.
  • 파라미터가 많은 이유는 FC-layer 때문입니다.
• GoogLeNet 이나 ResNet 같은 아키텍쳐들은 FC-Layer를 Global Average Pooling(GAP)으로 대체시켜 파라미터 갯수를 상당히 감소시켰습니다.

Recurrent Neural Networks

• RNN의 기본 구조의 개요를 살펴보고, Vanilla RNN의수식 및 computational graph를 살펴본 후, vanilla RNN에서 생기는 문제를 해결하기 위해 나온 RNN 변형 구조들을 알아보겠습니다.
• 우선 RNN(언어에 관련된 task에 RNN을 많이 활용)이 CNN(이미지에 관련된 task에 RNN을 많이 활용)이나 Fully-Connected NN과 어떤 측면에서 다른지 살펴보겠습니다.

“Vanilla” Neural Network

one to one

• 지금까지 다루었던 아키텍쳐들은(Vanilla Neural Network), 예를들어 CNN이나 Fully-Connected NN은 input이 1개, output이 1개인, single-input single-output 형태로, 각 layer가 다음 layer로 feed하는 형태의 “Feed-forward” network 였습니다.
• 하나의 입력(image or vector)을 받아 category label을 output으로 출력을 하는 Image Classification이 전형적인 예시입니다.
  • 예를 들어, single image가 input되면, 어떠한 모델 아키텍쳐를 거쳐서 이미지에 대한 label(개 / 고양이 등)을 output으로 반환합니다.
• 이러한 기본적인 (vanilla) NN 를 one-to-one 구조라고 합니다.

Recurrent Neural Networks: Process Sequences

하지만 Machine Learning의 관점에서 생각해보면, 다양한 task 들을 해결하기 위해서는 neural network는 task에 따라 다양한 입력과 다양한 출력을 낼 수 있도록 유연한(flexible) 구조를 가져야합니다. sequence, 즉 순서가 있는 시계열 데이터를 다루며 입력과 출력의 크기가 자유로운 RNN은 네트워크가 다양한 입/출력을 다룰 수 있는 여지를 제공해줍니다.

one to many

• flexible한 형태로 one-to-many 형태가 있습니다.
• one-to-many는 single-input(image)를 입력으로 받아서 output을 더이상 lable형태가 아닌 sequence 형태로 내보내는 것입니다.
  • 예를 들어, single image를 input으로 읽으면, image 내용을 설명하는 sequence of words를 output으로 내보내는(어떠한 연산을 거쳐서 문장(연속적인 단어들)을 출력하는) Image Captioning이 있습니다.
    • input: dog image
    • output: words vector(‘A’, ‘dog’, ‘cute’, …)

many to one

• 또다른 형태로 many-to-one 형태가 있습니다.
• input이 더이상 single-input이 아니라, 여러 개의 variable-input을 받아 하나의 output을 생성하는 형태입니다.
  • 예를 들어, 여러개의 단어로 이루어진 문장을 입력으로 받아, 해당 문장의 감정(긍정인지 부정인지)을 구별하는 Sentiment classification이 있습니다.

many to many

• 또다른 형태로 many-to-many 형태가 있습니다.
• 여러 개의 variable input을 받아 여러개의 variable output을 생성하는 형태를 볼 수 있습니다.(입력과 출력의 길이가 다른 경우)
  • input이 sequence이고 output도 sequence인 many-to-many 형태에서는, input sequence와 output sequence의 길이가 다른 경우인 Machine Translation 형태를 볼 수 있으며, 이를 sequence-to-sequence problem 이라고 합니다.
• 여러 개의 variable input을 받아 하나의 input마다 하나의 output을 생성하는 형태를 볼 수 있습니다.(입력과 출력의 길이가 같은 경우)
  • 또다른 sequence-to-sequence problem에서는 many-to-one과 다르게 video frame별 classification label을 결정하는, sequence of images를 input으로 받아 sequence of labels을 출력으로 보내는 Per-frame video classification을 생각해 볼 수 있습니다.

neural network를 one-to-one 형태가 아닌 sequence-to-sequence 형태로 만들어 사용하여 훨씬 더 일반적이고 다양한 문제들을 다룰 수 있으며, sequence-to-sequence process의 일반적인 방법론중 하나인 Recurrent Neural Network(RNN)를 다루겠습니다.

Sequential Processing of Non-Sequence Data

• Recurrent Neural Network는 Non-Sequential data에도 유용하게 사용되기도 합니다.
  • 즉 RNN은 고정된 하나의 input과 ouput이 필요한 상황(one-to-one) 이더라도 sequential processing 이 필요한 경우 유용하게 사용될 수 있습니다.
• 위 슬라이드는 Non-Sequential data에 sequential processing을 적용한 한 예로, 이미지 분류 문제에 한번의 Feed-forward network를 통해 class를 분류하는 것이 아닌, image의 여러 부분을 순차적으로 살펴보는, 여러개의 glimpses(한 부분)들의 series를 보는 형태의 neural network를 통해 image의 class를 분류할 수도 있습니다.
  • 동작 방식은 step마다 이미지의 한 부분(glimpses)을 보고, 또 다른 부분을 보는 과정을 여러 번 반복하고 최종적으로 분류를 수행하는 것인데, 다음 단계에 이미지의 어디를 보아야 할지는 이전 단계에서 수행한 정보에 따라서 이루어집니다.

• Non-Sequential data를 가지고 sequential processing을 사용하는 또다른 예로 digits image를 순차적으로 전체 출력의 일부분씩 생성(generative)하는 neural network가 있습니다.
• 앞의 예와 반대로, 매 순간마다 신경망은 캔버스의 어느 지점에 그려야할지를 판단하고, 그리는 것을 반복하는 것입니다.
  • 마찬가지로 해당 모델에서도 이전에 그렸던 정보에 따라서 다음에는 어디에 그릴지를 판단합니다.

Recurrent Neural Network

• RNN의 동작 구조를 살펴보겠습니다.
• RNN은 내부에 시퀀스가 처리될 때 업데이트되는 “internal hidden state”를 가지며, RNN block에서 나온 화살표가 다시 RNN으로 들어가는 구조입니다.
  • 즉 Recurrent neural network는 매 time step마다 $x$ 를 input으로 받아 network 내부의 “internal hidden state”를 특정 update formula를 통해 update해가며, 이를 통해 계산한 output $y$ 를 출력하며 동작합니다.
• hidden state는 RNN이 새로운 입력을 받을 때마다 매번 업데이트 되며, hidden state는 모델에 feedback되어 매 단계마다 $y$ 값을 출력하고, 이후에 또 다시 새로운 입력 $x$ 가 들어옵니다.
  1. RNN이 입력을 받습니다.
  2. “hidden state”를 업데이트합니다.
  3. 출력 값을 내보냅니다.

• 위 그림은 RNN 모델을 펼쳤(unroll)을 때를 나타낸 것입니다.
• 각 timestep에서 RNN은 입력 프레임 $x_i$ 와 이전의 output(history) 두 개의 input을 가집니다.
• 모든 RNN block은 동일한 파라미터를 공유하지만, 각 timestamp에서 input과 history가 다른 동일한 block입니다.

RNN hidden state update and output generation

• 다음은 RNN을 수식으로 나타낸 것입니다.
  • $h_{t−1}$ : 이전 timestep(old state) $t−1$ 반복에서의 이전 상태, 즉 이전 상태의 hidden state
  • $x_t$ : 현재의 input vector
  • $f_W$ : 각 단일 timestep마다 적용되는 가중치 $W$ 를 가진 고정된 함수
    • 입력 또는 출력 시퀀스가 얼마나 길든, 매 단일 시간 단계에서 정확히 동일한 함수를 적용하기 때문에 시퀀스의 크기에 상관없이 시퀀스에서 순환 신경망을 사용할 수 있다.
  • $h_t$ : 현재 timestep(new state), 즉 다음 상태의 hidden state
  • $f_{W_{hy}}$ : output을 위한 함수
  • $y_t$ : output
• RNN에서의 hidden state는 가중치 행렬 $W$ 를 가지는 함수를 통해 위 슬라이드와 같이 계산합니다.
• 따라서, $t$ 에서의 hidden state는 ($t−1$ 에서의 state $h_{t−1}$)와 ($t$ 에서의 입력 벡터 $x_t$)를 입력으로 받아 가중치 행렬 $W$ 를 통해 계산하게 됩니다.
  • 이때 중요한 것은 함수는 모든 time step에서 $h_t$ 를 계산할 때 동일한 function과 $W$ 를 사용한다는 것입니다. 이는 어떠한 길이의 시퀀스라도 하나의 RNN으로 처리할 수 있다는 것을 의미합니다.
  • 즉 함수 $f$ 와 parameter $W$ 는 매 step마다 동일합니다.
• RNN에서 출력값 $y_t$ 를 가지려면 $h_t$​ 를 입력으로 하는 FC layer을 추가해야 합니다. FC layer은 매번 업데이트되는 $h_t$ 를 기반으로 출력 값을 결정합니다.

(Vanilla) Recurrent Neural Network

• 따라서, Vanilla RNN은 다음과 같이 계산합니다.
  • $t−1$ 에서의 이전의 hidden state($h_{t−1}$)와 $t$ 에서의 현재의 벡터($x_t$)를 입력으로 받습니다.
  • $h_{t−1}$ 와 $x_t$ 에 각각 가중치행렬 $W_{hh}$, $W_{xh}$ 를 곱하고 더해줍니다.
  • 앞에서 구한 값에 비선형함수(여기서는 tanh)를 취해 $t$ 에서의 현재의 hidden state인 $h_t$ 를 구합니다.
  • 마지막으로, 또 다른 가중치행렬 $W_{hy}$ 를 $h_t$ 에 곱한 결과를 $y_t$ 로, 즉 class score를 출력합니다.
• 그리고 푸는 문제에 따라서 Loss의 형태가 달라집니다.
  • Classification problem
    • $s = W_{hy} × h_t$
    • $Loss = Cross-entropy(s, y)$
  • Regression problem
    • $s = W_{hy} × h_t$

    • $Loss =

      s - y

      ^2_2$

• 즉, RNN 모델은 recurrence formula에 따라 세부적으로 다양한 종류의 모델들로 나뉘는데 그 중 가장 기본적인 모델인 Vanilla RNN의 $f_W$ 함수는 hidden state에 대해 선형변환을 하고, input vector에 대해서도 선형변환을 한 합에 nonlinear activation을 씌운 형태이며, 예측 단계에서는 해당 hidden state에 대해서 선형변환을 합니다.

정리하면, RNN 모델의 핵심은 시계열 데이터를 처리하기 위한 것입니다. 그래서 RNN 모델에서는 입력과 출력 말고도 순서 정보를 처리하기 위해 순서에 따라 업데이트되는 일종의 벡터인 internal state 혹은 hidden state를 가지고 있습니다. 그리고 RNN 모델에서는 데이터 상의 매 순서 혹은 시간마다 hidden state와 그 시간의 입력을 입력으로 받아 연산을 수행하는 recurrence formula를 통해서 새로운 순서 정보를 생성해냅니다.

RNN Computational Graph

• 이번에는 RNN의 formula를 Computational Graph로 살펴보겠습니다.
• 첫번째 input 데이터 $x_1$ 과 initial hidden state $h_0$ 이 필요합니다. $h_0$ 의 값은 보통 $0$ 으로 셋팅합니다.
• 이후에 $h_0$ 와 input $x_1$ 가 함수 $f_w$ 의 입력으로 들어가게 됩니다.

• 먼저, 초기 hidden state $h_0$ 와 input $x_1$ 을 함수 $f_w$ 의 입력으로 들어가서 새로운 hidden state $h_1$ 을 출력합니다.
• 그리고 다시 hidden state $h_1$ 과 다음 input $x_2$ 를 통해 $h_2$ 를 계산하고, $h_2$ 와 $x_3$ 를 통해 $h_3$ 를 계산하고, 이러한 과정을 반복합니다.
  • 즉 RNN이 hidden state를 가지며 이를 “재귀적으로” feed back 합니다.
• $h_t = f_W(h_{t-1}, x_t)$ : maximum length인 T까지 계속해서 같은 트렌드를 반복합니다.

• 이때, 모든 time-step에서 동일한 함수, 동일한 가중치 행렬 $W$ 가 사용되기 때문에, Computational Graph에서도 하나의 노드를 통해 $W$ 를 위와 같이 나타낼 수 있으며, input으로 들어오는 sequence의 길이만큼 반복합니다.
  • 중요한 점은, 함수 $f_W$ 의 가중치 $W$ 는 각 step 마다 모두 동일한 값을 사용한다는 점입니다.
  • 즉, hidden state $h$ 와 input $x$ 는 매 step 바뀌지만 $W$ 는 매번 동일합니다.
  • 앞에서도 한번 언급했듯, 모든 time step in sequence에서 동일한 weight matrix $W$ 를 사용하기 때문에, 하나의 recurrent neural network에서 어떠한 길이의 시퀀스도 입력으로 받고 처리할 수 있으며, 위의 graph를 얼마나 반복해서 수행하느냐만 달라지게 됩니다.
• 이때 back porpagation 과정에서 weight matrix $W$ 도 $f_W$ 노드에 input 되어야 합니다.
  • 즉 $W$ 파라미터는 계속 같은 것을 사용하기 때문에, RNN 구조를 backpropagation 할 떄, 경로가 여러개가 생깁니다. 즉, 모든 경로에 대해 backprop을 진행하는데 copy gate로 볼 수 있으며, 이때 copy node를 지나면서 모든 경로(여기선 $f_w$)의 gradient를 더해주는 gradient adder로 볼 수 있습니다.
    • Gradient : 각 step에서 Weight에 대한 Gradient의 총합
    • Loss : 각 step에 구한 yt에 대한 Loss를 모두 더한 값
• 정리하면, 모든 time-step에서 동일한 함수, 동일한 가중치 행렬 $W$ 가 사용되기 때문에 입력으로 주어지는 데이터의 시간대의 길이와 무관하게 데이터를 처리할 수 있으며, 가중치 행렬 $W$ 에 대한 최종 loss는 각 step 에서 계산된 loss 값들의 합을 사용합니다.
• 따라서 backpropagation 과정에서 가중치 행렬 $W$ 를 gradient descent를 이용한 업데이트를 하려고 할때, $\frac{dL}{dW}$ 는 각 step 에서 $W$ 에 대한 local gradient의 합이 됩니다.

RNN Sequential Task: Many to Many

• 앞에서 살펴본 RNN을 이용한 여러가지 sequential task 중에서, many to many의 경우를 살펴보겠습니다.
• 각각의 선을 따라서 next hidden state node를 만들고, $y_t$ 를 지나서 loss를 계산하는 형태입니다.
• Many to many에서 입력과 출력의 길이가 같은 경우, 각 시점에 대해 일대일로 출력을 생성하는 Per-frame Video classification에 대한 전체 computational graph를 생각할 수 있습니다.
  • 각 frame 시점마다 출력이 나오게 되고, 이는 네트워크에서 predict한 class score 정보 이며, 이들 각각에 대한 Ground-truth label 대해 $y_t$ 와 Cross entropy Loss를 계산하게 됩니다. 즉, Sequence의 각 요소(시간)당 Loss $L_t$ 를 얻게 되는 것입니다.
  • 그리고 최종 Loss function은 모든 시점에 있었던 loss를 합산합니다. 그리고 이 final loss에 대해 back propagation을 수행합니다.
• 정리하면 다음과 같습니다.
  • many-to-many 모델에서 각 timestep마다 $y$ 를 출력하고 $L_1$, $L_2$, …, $L_T$ 를 계산합니다.
  • 그리고 최종 loss $L$ 은 각 개별 loss의 합을 의미합니다.
  • 모델을 학습시키기 위해 역전파(backpropagation) 과정을 보면, loss는 각 timestep에서 이루어졌기 때문에 각 timestep마다 가중치 행렬 $w$ 에 대한 local gradient를 계산할 수 있습니다.
  • 따라서, 각각 계산된 local gradient를 최종 gradient에 더합니다.

RNN Sequential Task: Many to One

• 위 슬라이드는 시퀀스 입력을 받아서 하나의 출력을 내는 Many to one task에서의 Computational graph 입니다.
• many-to-one 경우에는 최종 hidden state $h_T$ 에 전체 시퀀스에 대한 정보를 가지고 있습니다.
• 이 경우는 전체 비디오 시퀀스에 대해 하나의 분류 레이블을 출력해야하는 Video Classificaiton으로 생각해볼 수 있으며, 여러 모델을 연결해서 최종의 hidden state에서 하나의 레이블을 출력하게 됩니다.
• 이때, 최종 hidden state는 전체 입력 시퀀스에 따라 영향을 받으므로, 네트워크가 마지막 classification을 수행하기 위해 순서대로 전체 시퀀스에서 알아야 하는 정보들을 encapsulate한 것이라고 볼 수 있습니다.

RNN Sequential Task: One to Many

• 위 슬라이드는 One to many의 경우로 입력 벡터는 고정이지만 출력 벡터는 각각 변하며, Image captioning으로 생각해 볼 수 있습니다.
• 이 경우는 하나의 입력 $x$ 에서 recurrent한 관계들을 사용해 전체 출력 시퀀스를 생성하게 됩니다.
  • input $x$ 는 이미지 한 장, output은 예측한 sequences of words가 됩니다.
• 대게 고정 입력은 모델의 초기 hidden state를 초기화 시키는 용도로 사용합니다. 그리고 RNN은 모든 스텝에서 출력값을 가집니다.

Sequence to Sequence: Many-to-one + one-to-many

• Seq2seq는 Input과 output이 분리된 구조로, many to one과 one to many가 합쳐진 형태입니다.
  • 임의의 여러 개의 단어로 된 문장을 input으로 받아 다른 언어로 이루어진 임의의 여러 개의 단어로 된 문장을 ouput으로 생성해내는 machine translation이 이러한 구조를 가지며, 입력과 출력의 시퀀스 길이는 다를 수 있습니다.
• Seq2seq는 Encoder에 해당하는 many to one RNN과 Decoder에 해당하는 one to many RNN을 통해 구성하며 다음과 같은 방식으로 동작합니다.(영어를 한국어로 번역한다고 가정)
  • Encoder가 입력 시퀀스(영어문장)를 받아서 출력으로 최종 $h_T$ 를 내보냅니다. 이는 입력된 input sequence들이 summarize되어 업데이트 된 final hidden state라고 할 수 있습니다. 즉 가변입력을 하나의 벡터로 요약합니다.
    • 이를 컨텍스트 벡터(context vector)라 합니다.
  • Decoder는 이 hidden vector를 입력으로 받아서 시퀀스(한국어)를 출력합니다.
• 그림처럼 전체 계산그래프를 풀어서 전체 학습과정을 해석해보면, output sentence의 각 losses를 합해서 역전파를 진행합니다.

Language Modeling

• RNN 구조는 자연어(natural language)를 만들어내는 language modeling 문제에서 유용하게 사용됩니다.
• characters level의 language modeling 이라면 매 step 마다 문자를, word level의 language modeling 이라면 매 step 마다 어떻게 단어를 생성해내어 완전한 문장을 만드는 것을 목표로 할 것입니다.
  • Language model의 기본 idea는 input data의 stream을 받아서 매 time point별 next character가 무엇인지 예측하는 것이며, 이를 통해 신경망이 문장의 글자 순서를 예측할 수 있기 때문에 Language Model이라고 부릅니다.
• language modeling의 간단한 예시를 위해 character(문자) level의 language model에 대해 살펴보겠습니다.
  • 간단한 예시로, ‘h’, ‘e’, ‘l’, ‘o’ 의 4가지 문자가 존재하고 이 문자들 (단어장) 을 이용해 ‘hell’ 다음의 문자로 ‘o’ 를 출력하려고 합니다.
  • 이를 위해서 RNN 에 모델에 ‘h’, ‘e’, ‘l’, ‘l’ 을 순서대로 모델에 넣고, 각각의 step 에서의 해당 스텝의 다음 문자를 target character 로 하여 학습을 시켜야합니다.
  • 즉, 첫번째 input $x_1$ ‘h’ 가 RNN을 통과하여 output $y_1$ 값 ‘e’ 가 나와야하고, 다음 input $x_2$ ‘e’ 가 RNN을 통과하여 output $y_2$ ‘l’ 이 나와야합니다.

Train time

• training 과정을 살펴보는데, 첫 번째 예시는 Character Prediction 문제 입니다. 이는 문장 채우기를 many to many로 풀어냅니다.
• ‘H’ 를 입력하면 ‘HELLO’ 가 자동완성 되도록 하는 상황을 생각해보겠습니다.
  • input sequence : ‘h’, ‘e’, ‘l’, ‘l’
  • output sequence : ‘e’, ‘l’, ‘l’, ‘o’
• 우선 위 그림처럼 input sequence를 ‘h’, ‘e’, ‘l’과 같이 미리 정해놓은 vocabulary를 one-hot encoding 시킨 vector로 변환시킵니다.
  • h = [1, 0, 0, 0]
  • e = [0, 1, 0, 0]
  • l = [0, 0, 1, 0]
  • o = [0, 0, 0, 1]

• $h_0 = 0$ 이라고 가정하고, $h_t$ 들을 구하는 식을 연산할 수 있습니다.

• 여기까지 한 번의 forward pass step 입니다.
• 이러한 sequence of input vector를 통해 time step별 hidden state를 구하고 각 단어에 대한 예측결과로 output을 출력해줍니다. 이렇게 network는 매 time point별 next element in the sequence (다음 올 단어)를 예측하게 됩니다.
• 타겟은 각각 ‘e’, ‘l’, ‘l’, ‘o’이지만, predicted score를 보면 각각 ‘o’, ‘o’, ‘l’, ‘o’ 입니다.
  • 즉, $s_1$, $s_2$ 는 틀렸고, $s_3$, $s_4$ 는 맞았습니다.
  • $s_1 = W_{hy} × h_1$
  • $s_2 = W_{hy} × h_2$
  • $s_3 = W_{hy} × h_3$
  • $s_4 = W_{hy} × h_4$
• True $y_1$, $y_2$, $y_3$, $y_4$ 와 비교해서 각각의 cross-entropy loss를 계산한 후, 전체 loss를 계산합니다. 그리고 이를 최소화하는 가중치 $W$ 를 찾는 train 과정이 필요합니다.
  • $L_1 = loss(s_1, y_1)$
  • $L_2 = loss(s_2, y_2)$
  • $L_3 = loss(s_3, y_3)$
  • $L_4 = loss(s_4, y_4)$
• 정리하면 “hello”를 학습한다고 할때, 이 모델을 구성하기 위해서는 다음과 같은 순서를 따릅니다.
  • 신경망의 입력으로 넣어주기 위해, 각 문자를 하나의 one-hot vector로 변환합니다.(위 슬라이드의 붉은색 박스)
  • 입력을 받아서 hidden state sequence를 생성합니다.(위 슬라이드의 초록색 박스)
  • 각 단어에 대한 예측 결과를 출력합니다.(위 슬라이드의 파란색 박스)

• 위 4개의 슬라이드는 어떠한 입력을 받아서 어떠한 출력을 하도록 학습하는지를 보여줍니다.
  • “h” 입력 —> “e”를 출력하도록 학습
  • “h”, “e”를 입력 —> “l”을 출력하도록 학습
  • “h”, “e”, “l”을 입력 —> “l”을 출력하도록 학습
  • “h”, “e”, “l”, “l”을 입력 —> “o”를 출력하도록 학습
• Forward pass관점에서는 RNN 구조 특성상 이전 input들이 모두 반영되어 예측에 활용됩니다.
• Backward pass관점에서는 반대로 여러 경로들(활용한 input 노드 수만큼)로 W의 그래디언트를 계산하게 됩니다.

Test time

• Test time때, 학습된 모델은 initial seed token이 되는 단어 하나를 입력받아서 위 슬라이드와 같은 방식으로 새로운 텍스트를 생성할 수 있습니다.
  • Predict한 결과를 다시 입력에 input 시킴으로써 한 글자만 입력해도 여러 글자를 예측 할 수 있습니다.
• 위의 예시에서 모델에 ‘h’ 가 입력되면 output으로 모든 문자 ‘h’, ‘e’, ‘l’, ‘o’ 애 대한 score 벡터를 얻을 수 있습니다.
  • 이 score 들을 softmax 함수를 이용해서 각각을 확률 값으로 나타내고, 확률 분포에 따라 하나의 문자를 샘플링하여 one-hot endcoding 후 다음 input으로 들어가게 됩니다.
  • 이렇게 학습시킨 모델을 활용할 수 있는 방법들 중 하나는 model로부터 sampling하는 것입니다.
• 이때, 가장 높은 score의 문자를 사용하는 것이 아니라 확률 분포에 따라 샘플링하는 이유는 모델의 다양성(diversity)을 얻기 위함입니다.
  • 즉 전체 문장을 만들어내기 위해 타임 스텝마다 확률 분포에서 문자를 하나씩 뽑아냅니다.
• 그렇다면 이전 step 에서 얻은 확률 분포 벡터를 다음 step의 input으로 그대로 사용하면 될 거 같다는 생각이 드는데, 굳이 하나의 문자만을 샘플링해 one-hot encoding을 하는 이유는 무엇일까?
  • 첫번째 이유는 train time 에서 모델이 모든 input이 one-hot encoding 된 상태로 학습이 되었기 때문에 다른 형태의 input이 들어갔을때 모델의 성능이 저하될 수 있습니다.
  • 두번째 이유는 위의 예시에서는 단 4개의 문자로 이루어진 vocabulary를 사용해 길이가 4인 벡터가 input, output 으로 사용됐지만, 사실 우리가 쓰는 언어에서 단어는 엄청나게 많기 때문에 그렇게 많은 차원을 가지는 softmax vector(dense vector)를 사용하려면 연산량이 엄청나게 많습니다. 따라서 one-hot endcoding을 이용한 sparse vector를 사용합니다.

• hidden state 계산에서 입력(여기서는 one-hot vector)이 가중치 행렬 W와 곱해지는 경우를 생각해보면, 이 곱셈 연산은 아주 sparse하다는 것을 알 수 있습니다.
• 위 슬라이드에서 알 수 있듯이, $W$ 에서 한개의 column만을 추출하면 되기 때문에 단순히 열을 추출하는 방식으로 구현하는 것이 더 효율적입니다.
  • 즉 $W$ 에 원-핫 인코딩으로 생성된 $x$ 를 곱하는 행위는 곧 $W$ matrix에서 특정 열을 선택해서 추출하는 것과 같습니다.
  • 이 때 특정 열은 input 벡터 $x$ 에서 1값을 갖는 행입니다.
    • $w_{11}$, $w_{21}$, $w_{31}$

• 이러한 이유로 인해, 일반적으로 위 슬라이드와 같이 입력과 RNN사이에 Embedding layer(노란색 박스)라는 것을 추가해줍니다.
• Embedding layer는 one-hot vector가 $W$ 의 어떤 column에 해당하는지를 학습하게 됩니다. 이는 단어를 sparse한 one-hot vector가 아닌 dense vector로 만들어주어 저차원에서 더 많은 단어를 표현할 수 있게 됩니다.

Truncated Backpropagation Through Time

• RNN 모델의 train 시에 loss를 구할때 각 step에서 나온 loss를 모두 합해서 최종 loss를 구했습니다.
  • 즉, 전체 seqence에 대해 forward pass를 진행하여 모든 step의 loss를 더해 최종 loss를 구하고 이것을 이용하여 backpropation을 진행합니다.
• 하지만 이러한 방법은 seqence 가 아주 긴 경우에는 문제가 발생할 수 있습니다.
  • 예를 들어, wikipedia 전체 문서를 학습시키려고 하면, 하나의 학습 step 마다 전체 wikipedia 문서를 거쳐 forward pass를 진행하고 gradient를 구할 수 있습니다. 이런 경우 연산량이 굉장히 많고 학습이 굉장히 느리게 진행될 것입니다.
  • 설령 Forward pass 계산시에도 연산 가능하다하더라도, Backward pass할 때 메모리의 문제가 큽니다.
    • $W$ 에 대한 그래디언트 계산을 위해서는 수많은 computational graph가 모두 살아있어야하며, 수많은 경로가 존재하기 떄문입니다.
• 즉 RNN에서의 역전파는 위 슬라이드와 같이 아주 긴 시퀀스를 학습하려고 할 때, 엄청난 양의 메모리가 필요하다는 문제가 있습니다.

• 따라서, 아주 긴 시퀀스를 RNN으로 처리하는 경우에는 대체 근사 알고리즘(alternative approxtimate algorithm)을 사용합니다.
  • “Truncated Backpropagation” 이라는 방법을 사용합니다.
  • RNN 버전의 mini-batch gradient descent 이라고 생각하면 됩니다.
• 메모리 로드를 막기 위한 practical한 방법인 Truncated backpropagation 방법은, train time에 한 스텝을, sequences를 일정 단위(batch)로 나누고 batch 만큼만 forward pass를 진행합니다. 그리고 batch seqence의 loss를 계산하여 gradient descent를 진행합니다.
  • 예를 들어 한 문단(chunks of the sequence)에서 자릅니다. Forward pass와 backward pass를 진행하여 $W$ 를 업데이트하고, $h_T$ hidden state를 만듭니다.

• 다음으로, 이전 batch 에서의 hidden state를 받아 다음 batch 에서도 동일한 과정을 진행합니다.
  • 앞에서 나온 $h_T$ 를 가지고 다음 input 벡터들과 함께 hidden state를 만들어고, forward pass, backward pass를 진행하여 $W$ 를 업데이트 합니다.

• 이는 전체 시퀀스를 나누어서 학습하는 방법으로, 동작 방법을 정리하겠습니다.
  • 1번째 chunk의 시퀀스에서 모든 hidden state를 계산해 loss를 구하고, 1번째 chunk의 시퀀스에 대해서만 backprop을 통해 $W$ 를 학습시킵니다.
  • 그리고 1번째 chunk의 마지막 hidden state 값을 기록해뒀다가 2번째 chunk로 전달합니다.
  • hidden state값을 전달받은 2번째 chunk는, 다시 2번째 chunk의 시퀀스에 대해서 모든 hidden state와 loss를 계산하고 2번째 chunk의 시퀀스에 대해서만 backprop을 수행합니다.
  • 그리고 2번째 chunk의 마지막 hidden state 값을 기록해뒀다가 3번째 chunk로 전달합니다.
  • 이러한 과정을 끝까지 반복해서 수행합니다.
• 정리하자면, 위 그림처럼 전체 seqeunce를 학습하지 않고 sequence의 subset(chunk)으로 나누어 학습시키는 방식으로 각 chunk별 마지막 hidden state만 기억하여 다음 chunk로 전달하는 방식입니다.
• 위와 같이, 각 chunk에 대해서만 backprop을 수행하면서 학습하기 때문에 이 방법을 “Truncated Backpropagation” 라고 부르며, 각 chunk에 대한 정보만 저장하면 되므로 한정된 자원의 GPU에서도 학습을 수행할 수 있게 됩니다.
  • 결국 각 chunk별 loss를 통해 해당 chunk의 weight matrix를 학습하는 형태가 되는 것입니다.

Example: Character generation

• RNN language model 을 활용하여 여러가지 데이터들을 학습시켜 재밌는 결과들을 얻을 수 있습니다.
• 셰익스피어의 작품들을 RNN으로 학습시켜 볼 수 있습니다.
• 셰익스피어의 소설을 input으로 통째로 집어넣습니다.

• 학습 초기에는 모델이 의미없는 문장들만 뱉어내지만, 학습을 시키면 시킬수록 의미있는 문장을 만들어냅니다.
• 훈련을 계속 진행하면서 어느정도 문장의 형태를 갖춘 문자로 나옵니다. 영어 문법을 잘 지키지않으면 말이 안되는 문장을 반환합니다.

• 마지막 결과를 보면, 그럴듯한 결과를 생성해 낸다는 것을 알 수 있습니다.
• 학습을 많이 시키면 훨씬 더 긴 문장들도 만들어낼 수 있으며, 모델이 HEAD에 발화자를 넣어야한다는 것을 알고, 셰익스피어풍의 문장들을 만들어냅니다. 다른 문장을 시작할 때 한 줄을 비워야 하는 것도 압니다.

• 이번에는 단순한 문장이 아니라 어려운 수식들이 포함된 수학책을 학습시켜봅니다.
• 수학책의 수식이 LaTex 문법으로 작성되어 있으며, 교과서의 LaTex 코드를 우리가 만든 RNN Language Model로 학습시킬 수 있습니다.

• 위와 같이 수학 교과서의 공식, 다이어그램과 같은 전체 구조를 학습하는 것을 확인할 수 있습니다.
• 수학적으로 봤을때 말도안되는 형태이지만 위 그림처럼 diagram도 표현하고 증명도 서술되며 그럴듯한 형태로 나타내고 있습니다.
• 재미있는 점 중 하나는 모델이 “증명 생략” 도 학습합니다.(ㅋㅋ?)

• 이번엔 리눅스 커널 소스코드를 학습시켜봅니다.

• 학습된 모델에서 샘플링을 해보면 C 소스코드 스러운 것들이 나옵니다.
• 모델이 if 문 작성법을 알고 있고, 들여쓰기와 중괄호를 쓰는법도 잘 알고있고, 주석다는 법도 알고있습니다.
• 물론 뜻은 아무 의미도 없습니다.

• 심지어 소스코드 제일 위에 GNU license 저작권까지 표기했습니다.
• 정리하면 모델은 데이터의 일반적인 구조를 아주 잘 학습했습니다.

여기서 중요한 점은 우리는 RNN 모델을 통해 다음의 단어가 올 것만을 학습시켰고, 모델에게 요청한 것은 그저 시퀀스의 다음 문자를 예측하라는 것이었는데, 구조에 대해서는 전혀 말해주지 않았음에도 불구하고 모델이 알아서 전체 구조에 대해 학습했다는 점입니다.

• 즉 모델은 학습과정 동안에 시퀀스 데이터의 숨겨진 구조(latent structure)를 알아서 학습합니다.

Searching for Interpretable Hidden Units

• RNN에 대한 이해를 위해, Language Model이 다양한 유형의 시퀀스 데이터에서 무엇을 학습하는지, 도대체 어떤 방식으로 동작하는지를 연구하게 되었습니다.
• 여기서 사용한 방법은 RNN을 학습시킨 후, 다음 문자를 예측하는 과정에서 생성하는 hidden state 시퀀스를 살펴보는 것이었다.
  • 구체적으로는, hidden state vector의 값이 tanh()를 통과해서 $−1 ∼ 1$ 값이 되었을 때 값에 따라 색깔을 칠한다면, 텍스트를 처리하는 과정에서 색깔이 켜지는 부분만이 hidden state가 학습한 문자라고 볼 수 있다는 아이디어를 사용했습니다.
• 여러 hidden state cell 에서 vector 를 추출해서 어떤 특성을 보는지 해석하는 실험을 했고 그 결과를 보여줍니다.

• 각 색깔은, 시퀀스를 읽는 동안에 앞서 뽑은 hidden vector의 값을 의미합니다.
• 빨간색으로 칠한 부분은 hidden unit의 값이 1에 가까운 것이고, 파란색으로 칠한 부분은 -1에 가까운 것이다.
• 대부분의 cell 에서는 아무 의미 없는 패턴으로, 해석이 불가한 결과를 보였습니다.

• 따옴표를 감지한 것이라고 이해할 수 있습니다.
• 즉, input에서 특정부분에 주목하는 hidden element가 존재합니다.
• 그저 모델이 다음 문자를 예측하도록 학습시켰을 뿐이지만 모델은 더 유용한 것들을 학습하는 것입니다.

• 또 다른 예로 문장의 끝에 개행이 들어간 데이터로 학습한 결과인데, 여기서는 문장에 개행이 있을 법한 길이를 감지한 것이라고 이해할 수 있습니다.
• 즉 Cell은 언제 모델이 new line characters을 필요로 할 지 지속적으로 추적하는 역할을 한다고 볼 수 있습니다.

• 각각 if문, comment, 주석, 들여쓰기 깊이를 감지한 것이라고 이해할 수 있습니다.
• 여기서 놀라운 점은, 단순히 다음 문자를 예측하도록 학습한 것 뿐인데, RNN은 이러한 내부 특징들(데이터의 구조와 형태)까지 모두 학습했다는 것입니다.
• 즉, 의도적으로 feature를 추출하지 않았음에도 불구하고, RNN의 특정 activation element들이 feature extractor의 역할을 하고있음을 알 수 있습니다.

RNN tradeoffs

• 이상 RNN의 장점과 단점을 정리한 슬라이드입니다.

Image Captioning

• RNN 구조가 computer vision 분야에서는 어떻게 사용되는지 알아보겠습니다.
• CNN과 RNN이 동시에 사용되는 대표적인 task로 Image Captioning이 있습니다.
• Image captioning 이란, 특정 이미지를 입력으로 받아서 해당 이미지를 설명하는 문장을 생성하는 task 입니다.
  • CNN에 이미지를 입력으로 넣어서 요약된 이미지정보가 들어있는 feature Vector를 추출합니다.
  • 추출한 feature를 RNN Language Model에 입력으로 넣어서 이미지를 설명하는 단어를 하나씩 생성하도록 합니다.
  • 즉, 하나의 입력(이미지)를 받아 여러개의 variable output을 생성하는 것입니다.

• Image captioning은 transfer learning을 사용하여 CNN의 마지막 두 layer를 제거한 형태로 사용합니다.
  • 이미지에서 CNN을 통과하여 4096 size의 feature vector를 추출하고, 이후 이 vector는 새로운 가중치행렬 $W_{ih}$ 와 연산되어 hidden state에 계산되어 집니다.
  • 즉 feature extractor로 사용하며, 이때 feature vector가 추출되고, 해당 feature는 hidden layer의 이전 hidden state 값으로 사용합니다.
• 이 전에봤던 language model이 stream of data에 대한 연산과 관련있었다면 Image captioning에서의 language model은 sequece의 START token과 End token에 집중하여 학습하기를 원합니다.

• 이때, RNN 에는 $$ 와 같은 문장의 시작을 알리는 단어(토큰)가 처음 input 으로 들어가게 됩니다.
• 그리고 CNN을 RNN과 연결하기 위해서, 기존 input $x$ 와 previous state를 linear transform시켜 더해주는 식인 recurrent formula(RNN에서 hidden state를 생성하는데 사용한 함수식)을 약간 수정하여 CNN에서 출력으로 나온 feature vector $v$ 에도 linear transform 하게 합니다.
  • CNN의 출력으로 나온 feature vector와 곱해지는 가중치 행렬 $W_{ih}$ 이 추가됨 (위 슬라이드의 now 식에 추가된 핑크색 $W$)
• 즉, 수정된 RNN은 다음의 3가지 input에서 가중치 합을 모두 더하고 tanh로 출력하게 됩니다.
  • $W_{xh}$ : 입력 $x$ 와 곱해지는 $W$
  • $W_{hh}$ : $t−1$ 에서의 hidden state와 곱해지는 $W$
  • $W_{ih}$ : CNN의 출력으로 나온 feature vector와 곱해지는 $W$

• 이제 vocabulary의 모든 스코어들에 대한 분포를 계산하여, 그 분포에서 샘플링을 하고 그 단어를 다음 스텝의 입력으로 다시 넣어줄 것입니다.
• 샘플링된 단어(y0)가 들어가면 다시 vacab에 대한 분포를 추정하고 다음 단어를 만들어냅니다.

• 모든 스텝이 종료되면 결국 한 문장이 만들어지며, 마지막으로는 와 같은 토큰이 output 으로 생성이 되면 문장을 끝냅니다.
• 이때, 와 토큰은 문장의 시작과 끝을 나타내는 것인데, 이러한 토큰이 있는 이유는 Image Captioning에서는 시작과 끝이 있는 문장으로 이미지를 설명하기 원하기 때문입니다.
  • 이렇게 토큰을 사용하게 되면, RNN이 언제 출력을 멈춰야 하는지에 대해서도 학습하게 됩니다.
  • 즉, 네트워크가 를 출력하면 여기서 문장이 마무리된다고 판단했다는 의미로 더이상 단어를 생성하지 않으며 이미지에 대한 caption이 완성됩니다.
• 이처럼, 위 이미지를 통째로 사용하여 얻어진 요점을 언어로 변경하는 Top-Down Approach라고 합니다.

Image Captioning: Example Results

• Image Captioning 모델이 제대로 출력한 결과입니다.
• 이 결과만 본다면 모델이 아주 똑똑한 것처럼 보입니다.
• 즉 모델은 상당히 파워풀하고 이미지를 묘사하기 위해 비교적 복잡한 captions도 만들어낼 수 있습니다.

• 하지만 위 슬라이드의 결과를 본다면, 모델이 아주 멍청하다는 것을 알 수 있습니다.
• 가운데 사진의 출력은 “여성이 해변에서 서핑보드를 들고 있다”라고 완전히 잘못된 결과를 출력했는데, 이는 학습된 데이터셋의 해변에 있는 대부분의 사람들은 서핑보드를 들고있었기 때문입니다.
  • 따라서, 해변에 누군가가 서있는 사진이라면 입력으로 들어온다면 무조건 서핑보드를 들고 있는 사람이라고 출력하게 됩니다.
• 오른쪽 아래 사진을 보면, “야구 유니폼을 입은 사람이 공을 던지고 있다”라고 출력했는데, 이는 모델이 인간과 같이 물리 법칙을 고려하지 못한다는 것을 의미합니다.
  • 우리는 저 자세에서 공을 던질 수 없다는 것을 알지만, 모델은 그냥 야구선수와 공이 있으면 공을 던진다고 출력할 것입니다.
• model이 잘못된 descript를 출력하기도 하는 것을 봤을 때 image captioning model은 computer vision task를 해결하기에는 아직 멀었다는 것을 알 수 있습니다.

Attention

• 여기서 RNN 보다 조금 더 업그레이드 된 모델인 Attention을 사용할 수도 있습니다.
• Attention을 사용하면 모델이 이미지를 보고 문장을 생성할때 이미지의 다양한 부분을 집중해서(attention) 볼 수 있습니다.
  • Top-Down Approach는 이미지의 디테일한 부분들에 집중하는 것이 상대적으로 어렵다는 단점을 가집니다.
  • Bottom-Up Approach인 Attention 기법을 이용하면 이미지의 모든 부분으로 부터 단어를 뽑아내어 디테일에 신경을 써줄 수 있습니다.

• 이 Attention 기법은 CNN의 출력으로 하나의 벡터를 만드는 것이 아니라, 각 벡터가 공간정보를 가지고 포함하는 $L×D$ size의 grid of vector를 추출합니다.

• CNN으로부터 벡터 하나를 만드는 것이 아니라 각 벡터가 공간 정보를 갖고 있는 grid of vector을 만들어냅니다.
• forward pass시에 매 step vocabulary에서 샘플링을 할 때 모델이 이미지에서 보고 싶은 위치에 대한 분포를 만들어 냅니다. 이미지의 각 위치에 대한 분포는 Train time에 모델이 어느 위치를 봐야하는지에 대한 attention이라고 할 수 있습니다.
  • 첫번째 hidden state $h_0$ 에서는 이미지의 위치에 대한 분포 $a_1$를 계산합니다.
  • 이 분포인 $a_1$ 를 다시 feature vector 와 연산하여 이미지에 대한 attention $z_1$ 을 생성합니다.
  • 이 attention $z_1$ 이 바로 “이미지에서 어느 부분을 집중적으로 볼지” 에 대한 정보 입니다.

• 이 요약된 벡터 $z_1$ 은 다음 step의 입력으로 들어갑니다.

• 그러면 이미지 위치에 대한 분포인 $a_2$ 와 vocabulary의 각 단어들의 분포인 $d_1$ 두개의 출력이 생성됩니다.

• 즉, 이전의 hidden state $h_0$ 에 attension $z_1$ 과 첫번째 단어 $y_1$ 와 연산되어 ouput으로 이미지 위치에 대한 분포 $a_2$ 와 단어에 대한 확률 (score 에 softmax를 취한 값) 분포 벡터가 output으로 생성이 됩니다.
• 이후 반복적인 과정이 이루어져, step마다 $a$, $d$ 가 만들어집니다.

• train을 마치면, 모델이 문장을 생성할때 각 단어마다 보는 이미지의 부분(attention) 이 이동하는 것을 확인할 수 있습니다.
  • caption을 만들 때 마다 이미지 내에 다양한 곳들에 attention을 주는 것을 볼 수 있습니다.
• Soft attention과 Hard attention의 차이를 보여줍니다.
  • Soft attention의 경우에는 “모든 특징”과 “모든 이미지 위치”간의 weighted combination을 취하는 경우입니다. 0~1부터 다양한 범위 값을 부드럽게 사용합니다.
  • Hard attention의 경우에는 모델이 각 타임 스텝마다 단 한곳만 보도록 강제한 경우입니다. 0또는 1의 값을 사용하여 정확하게 몇 부분을 집중해서 봅니다.

• 결과를 보면 실제로 모델이 caption을 만들 때 의미있는 부분에 attention을 하고 있는 것을 알 수 있습니다.

Visual Question Answering(VQA)

• CNN과 RNN + Attention을 동시에 사용하는 task의 예시로, Visual Question Answering이 있습니다.
• Visual Question Answering 이란, 이미지와 특정 퀴즈를 냈을때, 정답을 맞추는 task 입니다.
• 이미지와 질문을 입력하면 모델은 네개의 보기중 정답을 맞춥니다.

• VQA task 는 many-to-one 구조로 이루어진 모델을 사용합니다. 이때, CNN, RNN, Attention 구조가 사용될 수 있습니다.
  • 모델은 자연어 문장을 입력으로 받는데 이는 RNN을 통해 vector로 요약합니다.
  • 이미지 요약을 위해서는 CNN을 사용합니다. 이 둘 벡터를 concat하는 식으로 조합하면 질문에 대한 분포를 예측할 수 있습니다.
  • 모델이 정답을 결정하기 위해서 이미지에 대한 attention을 만들어냅니다.

Introduction to LSTM

• LSTM은 RNN과 다르게 4개의 변수가 존재합니다.
• LSTM의 구조는 위 그림과 같으며, 왜 탄생되었는지에 대한 해답으로 RNN의 gradient 흐름부터 살펴보겠습니다.

Vanilla RNN Gradient Flow

• RNN을 학습시킬때 발생하는 대표적인 문제점이 있는데, RNN을 학습하는 과정의 forward pass 과정과 gradient를 계산하는 과정을 computational graph로 살펴보겠습니다.
• Vanilla RNN에서 hidden state $h_t$ 는 위와 같이 이전 hidden state $h_{t−1}$ 와 input $x_t$ 를 받아 가중치 $W$ 와 연산됩니다.
• Vanilla RNN에서 $h_{t−1}$ 에서의 gradient를 구하기 위해서는 $h_t$ 에 대한 loss의 미분을 계산해서 tanh gate를 지나서, mul gate 를 지나사 gradient를 back prop 해야합니다.
• 그런데, 이 back prop에는 다음과 같은 2가지 문제점이 있습니다.
  • 이 모델은 90년대에 나왔기 때문에 큰 문제가 아니지만, tanh 함수가 nice 하지 않습니다.
  • 행렬의 곱셈에서 back prop을 수행할 때, 동일한 matrix의 transpose를 계속해서 곱하게 됩니다.
    • Vanilla RNN의 구조에서 $W$ matrix가 모든 시점의 $f_w(h_{t−1}, x_t)$ 연산에서 활용되고 있음을 확인할 수 있습니다. 따라서 backward pass과정에서 $W_{hh}^T$ 가 계속해서 곱해집니다.
    • 이는 매번 vanilla RNN cells을 하나 통과할 때 마다 같은 가중치 행렬의 일부를 곱하게 된다는 것을 의미합니다.

• RNN의 특성 상, RNN이 여러 시퀀스의 Cell을 쌓아 올리는 사실을 고려하면, gradient가 RNN 모델의 Layers 시퀀스를 통해 어떤 방식으로 전달되는지 생각해 볼 수 있습니다. 이상한 느낌이 듭니다.
• $h_0$ 에 대한 gradient를 구하고자 한다면 결국에는 모든 RNN Cells을 거쳐야 합니다.

• 따라서 gradient는 여러 timestep에 걸치게 됩니다. 위 그림은 출력값을 순차적인 RNN 구조를 따라가 gradient를 계산하는 과정입니다.
• cell 하나를 통과할 때 마다 각 Cell의 행렬 $W$ transpose factors가 관여합니다.
  • $h_0$ 의 그레디언트를 계산할때 아주 많은 가중치 행렬들이 사용됩니다. 즉, nice 하지 않습니다.
• 이로 인해 seqence가 길어져 hidden cell이 많아지면(step이 늘어나면), 만약 곱해지는 값이 1보다 큰 경우라면 점점 값이 커질 것이고 1보다 작은 경우라면 점점 작아져서 0이 될 것입니다.

• 정리하면, 위 슬라이드와 같이 여러 개의 cell이 연결된 구조에서, upstream gradient는 cell을 넘어가는 매 순간마다 동일한 가중치 행렬 $W$ 와 곱해지게 됩니다.
• 이는 back prop중에 계속해서 동일한 가중치행렬 $W$ 의 transpose를 gradient에 곱하게 되는 결과로 이어지며, 이는 2가지 안좋은 결과를 초래합니다.
  • Exploding gradients problem (singular value > 1)
  • Vanishing gradients problem (singular value < 1)
• 따라서, W의 singular value = 1인 경우에서만 정상적으로 학습이 이루어지므로, 아예 제대로 이루어지지 않는다고 볼 수 있습니다.

• $W^T_{hh}$ 의 거듭제곱 largest singular value가 1보다 크면, 한 축의 방향으로 계속해서 증가하게 됩니다.이는 컴퓨터의 수치적인 문제를 야기합니다.
• exploding gradient를 해결하기 위해서 “gradient clipping” 이라는 방법을 사용할 수 있습니다.
  • gradient가 특정 threshold 보다 클때 적당한 크기로 scaling을 해주는 방법입니다.
• 하지만 실제 gradient가 아니기에 여전히 문제가 있습니다.

• $W^T_{hh}$ 의 거듭제곱 largest singular value가 1보다 작으면, 모든 축에 대해 축소됩니다. 즉, 크기 자체가 줄어들어서, 0에 거의 가까워지므로 그래디언트가 소멸되는 효과를 낳습니다.
• Vanishing gradient 문제에서는 clipping과 같이 heuristic한 방법이 따로 없기 때문에, vanishing gradient를 해결하기 위해서는 신경망 자체를 바꾸는 것이 일반적입니다.
• 정리하면 RNN은 오래전에 입력에 정보를 사용하지 못하는 장기 의존성(Long-Term Dependency)문제를 가지고 있습니다.
  • 그래서 나온 아키텍처가 LSTM 입니다.

Long Short Term Memory (LSTM)

• RNN 에서 발생하는 vanishing & exploding gradients 문제를 해결하기 위해 설계된 모델이 바로 LSTM (Long Short Term Memory)입니다.
  • LSTM은 gradient clipping과 같은 방법을 사용하지 않고도 gradient가 잘 전달되도록 설계한 모델입니다.
• LSTM에서, step $t$ 에는 hidden state $h_t$ 와 cell state $c_t$ 가 있습니다.
• LSTM은 바로 장기적으로 정보를 저장하는 cell state $c_t$ 를 가지고 있는 것이 Vanilla RNN과의 차이점 입니다.
• LSTM은 크게 다음과 같이 나뉘어집니다.
  1. 4개의 gate (input gate, forget gate, output gate, gate gate)
     • 현재 입력 $x_t$ 와 과거 hidden state $h_{t−1}$ 을 사용해 가중치 행렬 $W$ 와 곱해준 다음 비선형 함수(sigmoid, tanh)를 거쳐 4개의 gate value를 계산합니다.
  2. Cell state
     • 정보를 저장하고 갱신하는 역할로, 과거의 cell state값과 새로운 값 g와의 weighted combination 입니다.
     • cell state는 내부적으로 hidden variable간의 연산에만 활용되며 밖으로 노출되지 않는 값입니다.
     • LSTM이 cell을 바꾸는 방법으로 위 Gate gate(?), input gate, forget gate, output gate에 해당하는 i, f, o, g를 통해 이루어집니다.
  3. Hidden state
     • 정보를 출력하는 역할로, tanh로 cell state를 씌우고 o라는 벡터로 검수하고 내보냅니다.

• Vanilla RNN에서는 $x_t$ 와 $h_{t−1}$ 를 $W$ 와 곱한 결과가 tanh()를 거쳐서 바로 $h_t$가 되는 구조였습니다.
• 하지만, LSTM은 $x_t$ 와 $h_{t−1}$ 를 $W$ 와 곱한 결과를 총 4개의 gate i, f, o, g로 출력합니다. 이때, gate는 각각의 activation function을 통해 출력합니다.
  • i : Input gate
    • 이전의 hidden 상태 $h_{t−1}$ 과 입력 벡터 $x_t$ 에서 다음 cell 상태 $c_t$ 에 얼마나 많은 정보를 추가해야 하는지를 제어합니다.
    • 즉 cell에서의 입력 $x_t$​ 에 대한 가중치로, 현재 입력 값을 얼마나 반영할 것인지를 결정합니다.
    • activation function : sigmoid() —> 0 ∼ 1
  • f : Forget gate
    • 이전 step의 cell state 정보를 얼마나 망각할지에 대한 가중치입니다.
    • 즉 이전 상태 정보들을 얼마나 잊을 것인가 결정합니다.
    • 만약 f 값이 0 이라면, 이전 상태의 정보를 모두 사용하지 않는 것이고, f 값이 1 이라면, 이전 상태의 정보를 모두 사용하는 것입니다.
    • activation function : sigmoid() —> 0 ∼ 1
  • o : Output gate
    • 현재 hidden 상태 $h_t$ 에서 출력으로 표시해야 하는 정보의 양을 제어합니다.
    • 즉 cell state를 얼마나 나타낼 것인지 결정합니다.
    • activation function : sigmoid() —> 0 ∼ 1
  • g : Gate gate
    • input cell을 얼마나 cell state에 포함시킬지 결정하는 가중치입니다.
    • activation function : tanh() —> −1 ∼ 1
• Activation function 해석은 다음과 같습니다.
  • i, f, o
    • 잊기 위해서는 0에 가까운 값을, 기억하기 위해서는 1에 가까운 값을 사용하기 위해서 sigmoid를 사용하였습니다. 마치 스위치와 같은 역할을 합니다.
  • g
    • tanh의 -1 ~ 1은 강도를 나타내는 역할을 합니다.
• $c_t$ 의 식에 대한 직관적인 해석은 다음과 같습니다.
  • $f$ 와 $c_{t-1}$ 의 element-wise 곱셈
    • forget gate가 0∼1의 값을 가지므로, $f$ 가 0일 경우 $c_{t−1}$ 를 element-wise하게 0으로 만들어 전파하고 1일경우 온전한 값을 전파한다는 의미로, cell state를 다음 단계로 얼마나 전파할 것인지 말것인지를 의미합니다.
  • $i$ 와 $g$ 의 element-wise 곱셈
    • gate gate는 −1∼1의 값을 가지므로, 값을 빼고 싶은지, 아니면 더하고 싶은지 를 의미합니다.
    • input gate는 0∼1의 값을 가지므로, 빼거나 더하는 양을 얼마로 하고 싶은지 를 의미합니다.
    • 즉, i와 g의 element-wise 곱셈은 cell state에 어떤 값을 쓰고 싶은가(what we want to write), $W(h_{t−1}​, x_t)$ 값을 cell state에 얼마나 반영할지를 결정함을 의미합니다.
• $h_t$ 의 식에 대한 직관적인 해석은 다음과 같습니다.
  • $c_t$ 는 LSTM의 내부 작업을 수행하기 위한 숨겨진 어떠한 state라고 해석할 수 있습니다.
  • output gate는 0∼1의 값을 가지므로, 양을 조절하는 의미가 있습니다.
  • 즉, $o$ 와 tanh($c_t$)의 element-wise 곱셈은 시점 $t$ 에서 숨겨진 state($c_t$)를 얼마나 보여줄 것인가를 의미합니다.

LSTM Flow

• 동작과정을 따라가겠습니다.
• 이전 step의 cell state $c_{t−1}$ 은 forget gate와 element-wise multiplication을 합니다. f가 0이면 이 결과는 0이 되어 이전 cell state를 잊고 반면 f가 1이면 결과가 1이 되어 이전 cell state를 계속 기억합니다.
• $i$ 와 $g$ 의 element-wise mul에서, $g$ 는 -1 ~ 1의 값이므로 값을 뺄지 더할지를 결정합니다. $i$ 는 0 ~ 1의 값이므로 크기를 결정한다. 따라서 이 결과는 $W(h_{t−1}​, x_t​)$ 값을 cell state에 얼마나 반영할지 결정합니다.
• 마지막으로 $o$ 와 $tanh(c_t​)$ 를 element-wise mul하여 $h_t$​ 를 구합니다. 이는 $c_t$​ 에서의 0 ~ 1 사이의 값인 $W(h_{t−1}, x_t)$ 을 통해 원하는 element만 내보내는 필터링 된 결과를 만듭니다. 그리고 이 값도 다음 cell로 넘어갑니다. output gate는 다음 hidden state를 게산할 때 cell state를 얼마나 노출시킬지 결정합니다.

LSTM Gradient Flow

• LSTM의 다이어그램을 통해 gradient flow를 보면서 back prop 과정 $c_t —> c_{t−1}$ 을 살펴보겠습니다.
  • $c_t$ 가 가장 먼저 만나게 되는 sum node $+$ 는 gradient distributor 역할을 수행하기 때문에 upstream gradient가 두 갈래로 복사되므로 gradient가 잘 전달됩니다.
  • 다음으로 만나게 되는 forget gate와의 element-wise 곱셈은 gradient를 파괴할 수도 있지만, constant scaling 된다고 생각해 보았을때 f gate를 통한 값이 0에 가까우면 정보손실이 있기는 하지만 non-linearlity를 직접적으로 거치는 것이 아니기에 vanishing 문제라고 볼 수 없습니다.
  • 즉 0∼1 사이의 값으로 조절되는 것이기 때문에 기본적으로 파괴하는 것은 아닙니다.
    • 이때, forget gate의 0∼1 값은 sigmoid를 거친 후에 나온 값이기 때문에, sigmoid로 직접 back prop되는 것이 아닙니다. 따라서, sigmoid에서의 gradient 문제들도 일어나지 않습니다.
    • $L$ 에 대한 $c_{t−1}$ 그래디언트를 구하면, $c_t$ 에 대한 gradient flow는 $W^T_{hh}$ 거듭제곱에 영향을 받지 않는 것을 확인할 수 있습니다.
    • 이때, $f$ 값이 1에 가까울 수록, $t+1$ step에서의 그래디언트를 온전히 보관할 수 있게됩니다.
• 결과적으로 Cell state의 backprob은 그저 upstream gradient와 forget gate의 element-wise 곱 입니다.
  • back prop 경로에 행렬 $W$ 와의 곱셈도 없고 element-wise 곱셈만 존재하므로 문제가 없습니다.
• 이러한 구조는 기존의 RNN 구조보다 장점이 있습니다.
  1. 첫번째 장점은 기존의 RNN 의 backpropagation 과정에서 이루어지던 full matrix multiplication 보다 LSTM 에서 이루어지는 element-wise multiplication 이 낫다는 점입니다.
  2. 두번째 장점은 LSTM backpropagation 과정에서 매 step 마다 다른 값의 forget gate 가 곱해진다는 점 입니다.
     • 기존의 RNN 의 경우, 동일한 $W$ 행렬만을 계속 곱했지만, LSTM 에서는 forgate gate가 매 step 마다 계속 변하므로 exploding/vanishing gradient를 더 쉽게 해결할 수 있습니다.
     • 하지만 forget gate 에서 계속에서 0~1 사이의 값들이 곱해지다 보니 vanishing gradient 가 여전히 발생할 수도 있긴 합니다.
  3. 또한, 기존의 RNN의 backpropagation 과정에서는 매 step 마다 gradient가 tanh gate를 통과해야만 했습니다. 하지만, LSTM 에서 최종 hidden state h_t를 가장 첫 cell state(c_0)까지 backprob하는 것을 생각해보면 tanh gate를 한번만 통과하면 된다는 장점이 있습니다.

• LSTM을 정리하겠습니다.
  • RNN은 vanishing/exploding gradient 문제가 있습니다. 그래서 LSTM을 활용했습니다. LSTM에서는 cell state가 그 문제를 극복합니다.
  • vanishing/exploding gradient 문제가 생기는 이유는, RNN에서는 backprop을 할 때, $W^T_{hh}$ 거듭제곱이 들어가게 됩니다. Largest Singular value가 1보다 작으면, Vanishing문제가 생깁니다.
  • LSTM은 cell state에 대해서는 backprop 시에 $W$에 대한 거듭제곱 term이 없어서 그 문제를 극복했다고 볼 수 있습니다.
    • 즉 cell state를 두었기 때문에, $c_t$ 에서 $c_{t−1}$ 로 가는 backpropagation 과정에서 기존 RNN과는 달리 가중치 행렬 $W$ 를 곱하지 않고, 어떠한 non-linearlity도 거치지 않으며, 오직 $f$ 요소만 요소별 곱셈을 하면 됩니다.
• 또한, 여러개의 cell을 위 슬라이드와 같이 연결하더라도, Back prop되는 경로에 방해되는 것이 없습니다.(Uninterrupted gradient flow)
• 따라서, LSTM은 Vanilla RNN의 gradient vanishing 문제를 해결하고, forget gate의 적절한 파라미터 업데이트를 사용하여 gradient 값을 더 잘 제어하여 장기 의존성(Long-Term Dependency)문제를 해결한 모델이라고 볼 수 있습니다.
• LSTM의 gradient flow는 ResNet에서의 skip-connection과 유사한 방법으로 이해할 수 있습니다.
  • 그래디언트 flow가 방해되지않게 하는 구조는 ResNet 구조에서도 등장했습니다. (+)노드를 통해, 그래디언트 copy를 해서 소멸되지않고 그대로 활용할 수 있게 했습니다.
  • 즉 cell state는 backward pass 과정에서 gradient 를 쉽게 전달 할 수 있게하는 고속도로의 역할을 합니다.

Multi-layer RNNs

• 지금까지는 Single-layer의 RNN을 다루었는데, RNN도 CNN에서처럼 여러개의 layer로 구성할 수 있습니다.
• LSTM이외에 다양한 RNN의 변형된 구조들을 소개하겠습니다.

• RNN도 마찬가지로 여러겹을 쌓아서 Multi layer로 구성할 수 있으며, 실제로도 성능에 약간의 향상이 있습니다.
  • 하지만, RNN에서는 CNN처럼 매우 깊게 쌓는 구조는 흔하지 않으며, 주로 3~5개의 layer 정도로 구성됩니다.
• 이때, 각 layer끼리는 다른 가중치 행렬 $W$ 를 사용합니다.

Gated Recurrent Unit(GRU)

• RNN의 다른 변형된 아키텍쳐는 GRU(Gated Recurrent Unit) 입니다.
  • LSTM을 단순화한 버전이라고 생각할 수 있으며, LSTM과 마찬가지로 추가적인 연결을 통해 gradient flow를 개선시킨 모델입니다.
• 또한, brute force로 수만개의 조합을 직접 탐색하면서 좋은 성능을 내는 RNN 모델을 찾으려는 시도도 있었지만, LSTM보다 아주 우수한 성능을 내는 모델은 찾지 못하였습니다.

RNN Architectures : Neural Architecture Search

• CNN에서와 마찬가지로 RNN에서도 Neural Architecture Search를 통해 좋은 구조를 찾으려는 시도가 있었고, LSTM보다 조금 더 잘 동작하기는 했지만, 잘 사용되지 않습니다.
• 그 이유는 LSTM과 GRU가 특정 문제에서 최적화된 모델은 아니지만 실제로도 좋은 성능을 내며 다양한 문제에서 잘 수행되는 경향이 있기 때문입니다.

Summary

• RNN은 feed forward 네트워크에서 벗어나서, sequential data에 대해서 유연성있는 아키텍쳐 구조들을 허용합니다.
• Vanilla RNN은 심플하지만 잘 작동하지는 않습니다.
• 주로 LSTM과 GRU를 사용하는데, 이는 gradient flow를 방해받지않게 개선된 RNN 구조입니다.
• Sequence data를 처리하는 방법으로 RNN, 1D-CNN, Attention등이 있는데, 현재는 sequence

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

Last Time: Components of Convolutional Networks

• 앞 강의에서 CNN을 구성하기 위한 여러가지 components들을 살펴보았습니다.
• 그렇다면 components들을 어떻게 조합을 해야 성능이 좋을지, 역사적으로 어떻게 구성해왔는지에 대해 알아보겠습니다.

Today: CNN Architectures

• 여러 네트워크 중 ImageNet Classification Task 에서 좋은 성능을 보였던 대표적인 CNN Architectures들 (AlexNet, VGG, GoogLeNet, ResNet) 에 대해 살펴보겠습니다.
• 역사적인 관점에서 아주 흥미로운 모델들, 그리고 아주 최신의 모델들도 다룹니다.

LeNet-5(1998)

• 앞 강의에서 LeNet을 다룬 적이 있었지만, 조금 더 자세히 살펴보겠습니다.
• LeNet 은 Convolution layer가 성공적으로 적용된 최초의 ConvNet 입니다.
• 슬라이드에서 볼 수 있듯, 이미지를 입력으로 받아서 stride = 1 인 5 x 5 필터를 거치고, 몇 개의 Conv Layer와 pooling layer를 거쳐, 끝 단에 FC Layer가 붙습니다.
  1. Conv - ReLU - Pool(downsampling) 전체 N번 반복 합니다.
  2. Cout x H x W를 한 줄로 펴줍니다.
  3. FC - ReLU 전체 N번 반복 합니다., 마지막 output은 c차원 입니다.
• LeNet은 digit recognition task에서 우수한 성능을 보였습니다.

• LeNet-5의 구조를 살펴보는데, 구조는 동일하나 각 component의 구성이 바뀐버전을 살펴보겠습니다.
  • 원본 구조는 논문에 있습니다.
• 우선 Input 이미지는 grayscale 이므로 채널은 1입니다.

• Filter 사이즈는 1 x 5 x 5, filter 20개.
• P를 조정해서 output size가 같도록 만들어줍니다.
• ReLU로 nonlinear를 취해줍니다.

• K=2, s=2로 주고 크기를 반으로 다운샘플링 시킵니다.
• [Conv, ReLU, Pool] 1회

• Filter 사이즈는 20 x 5 x 5, filter 50개.
• P를 조정해서 output size가 같도록 만들어줍니다.
• ReLU로 nonlinear를 취해줍니다.

• K=2, s=2로 주고 크기를 반으로 다운샘플링 시킵니다.
• [Conv, ReLU, Pool] 2회

• 50 x 7 x 7 = 2,450를 flatten 시킵니다.

• FC-Layer를 적용해서, Input은 2450, Output은 500이 되도록 만들어주고, ReLU를 취해줍니다.

• FC를 적용하여, Input은 500, Output은 10이 되도록 만들어줍니다.
• $y ∈ {0, 1, …, 9}$ 라면, $f(x;W): ℝ^{1 x 28 x 28} → ℝ^{10}$ 입니다.
• 정리하면 네트워크를 통과할때 다음과 같이 진행됩니다.
  • pooling or stride를 사용하여 Spatial size가 감소합니다.
  • channel의 수가 증가됩니다.
• 현대의 architectures들은 점차 이러한 구조를 breaking 하고 있습니다. 이후의 architectures들을 살펴봄으로써 발전양상을 살펴보겠습니다.

AlexNet(2012)

• ILSVRC 를 remind해보면, ImageNet 데이터셋은 클래스 1000개, training set이 130만개, test set이 10만개로 구성되어있는 DataSet입니다.
• 2011년도 까지는 rule-based 방법으로, edge들을 직접 추출한 후, linear classifier를 얹어서 모델을 만들었습니다.
• 하지만 2012년, AlexNet 은 Conv layer를 깊게 쌓은 최초의 대규모 CNN 구조로, 2012년 ImageNet Classification task 에서 엄청난 격차를 보여주면서 Convolution Network는 컴퓨터 비전의 전면에 서게 되었습니다.
• AlexNet은 현재까지 약 50,000번 인용되었는데, CNN아키텍쳐 구성 방법에 영향을 많이 미쳤음을 알 수 있습니다.

• 위 슬라이드는 AlexNet의 전체 architectures구조 와, 각 Layer components, Details 입니다.
• AlexNet은 CNN을 깊게 쌓은 심층신경망 형태입니다.
• 모델 구조는 다음과 같습니다.
  • 227x227 크기의 입력 이미지
    • 논문의 그림에서는 input size가 224×224×3 으로 표시되어 있는데 오류입니다. 사실 input size 는 227×227×3 입니다.
  • 5개의 Convolutional layer + Max pooling layer
  • 3개의 Fully connected layer
    • 마지막 층은 softmax를 거쳐 최종적으로 1000개의 class로 분류합니다.
  • ReLU Activation function
• AlexNet의 몇가지 큰 특징 은 다음과 같습니다.
  • AlexNet이 ReLU nonlinear activation function을 사용한 첫번째 Neural Network입니다.
  • 채널간 Local response normalization이라는 정규화 방법을 사용하였습니다.
    • 현재는 Batch Normalization을 주로 사용합니다.
  • 당시에는 GPU의 메모리가 부족(3GB)해서 모델을 2개의 GPU에 병렬적으로 분리해서 학습을 수행하였습니다.
  • filpping, jittering, cropping, color normalization 등의 다양한 data augmentaion 을 적용했습니다.

• 강의에서의 질문에 대한 답을 찾겠습니다.
• $227 × 227 × 3$ size의 input 이미지가 네트워크에 들어갔을때 첫 conv layer (CONV1: 96 11x11 filters applied at stride 4) 를 통과한 output size 는 어떻게 될까?
  • 하나의 필터에서 나오는 output size는 $(227 − 11) / 44 + 1 = 55$ 임을 알 수 있습니다. 또한 필터의 갯수가 96 개이므로 총 output size는 $55 × 55 × 96$ 입니다.
• 이때, 첫번째 conv layer의 총 parameter 갯수는 어떻게 될까?
  • conv layer의 파라미터수는 filter size x filter depth x filter 개수로, $(11 × 11 × 3 + 1) × 96$ 개의 파라미터를 가집니다.

• 첫번째 conv layer를 거쳐 나온 $55 × 55 × 96$ size의 feature map을 Pooling layer (POOL1: 3x3 filters applied at stride 2) 에 넣어서 만들어진 output size 는 어떻게 될까?
  • 하나의 filter 에서 $(55 − 3) / 2 + 1 = 27$ size의 output이 생성되고 pooling layer는 input의 channel(depth)은 그대로 유지함으로써 총 output size는 $27 × 27 × 96$ 입니다.
• 이때, Pooling layer의 총 parameter 갯수는 어떻게 될까?
  • pooling layer는 단순히 pooling하는 과정(ex. max pooling) 이므로 학습시킬 파라미터가 없습니다.

params & memory & flop

앞에서 layer 및 parameter 계산법에 대해 알아보았는데, 조금 더 자세하게 memory와 flop의 관점까지 바라보는 과정을 진행해보겠습니다. 본 과정은 AlexNet의 구조를 따라가되, 일부 Layer의 수가 수정된 구조입니다.

• 이제 AlexNet의 layer들이 어떻게 쌓여있는지 살펴보겠습니다.(일부 변형됨.)
• Conv1 Layer의 Input size는 $227 × 227$ 이며, 3개의 Channel을 가집니다.
• $C_{out} = 64, K = 11, S = 4, P = 2$ 입니다.

• Output channels은 filters의 수와 같습니다.
• $C_{out} = 64$ 이므로, output size의 $C$도 64입니다.

• 위 수식대로 입력하면 $H$와 $W$ 는 56입니다.
  • $(Input\ width - Kernel\ size + 2 × Padding) / Stride + 1 = (227 - 11 + 2 × 2) / 4 + 1 = 56$
• 즉 Kernel size, stride, pad에 의해 output의 $H$와 $W$가 결정 됩니다.

• Conv1의 출력을 저장하기 위한, Output이 차지하는 Memory 공간 은 다음과 같이 계산할 수 있습니다.
  • output의 원소 개수 는 $Channel × Height × Width$ 이므로, $64 × 56 × 56 = 200,704$ 개 입니다.
  • 한 원소당 32-bit floating point 크기 를 가진다고 할때, 4 byte의 크기를 가집니다.
  • 따라서, Output이 차지하는 Memory 공간을 계산하기 위해서는 다음과 같이 계산합니다.
    • $(number\ of\ elements) × (bytes\ per\ element) / 1024 = 200,704 × 4 / 1024 = 784KB$
    • 즉 output을 저장하기 위해서는 784KB가 필요합니다.

• Conv1가 가지는 Parameter의 수 를 계산하기 위해서는 layer를 다시 살펴보아야 하는데, 다음과 같이 계산할 수 있습니다.(Filter가 학습되는 파라미터)
  • (number of filter x input channel x kernel size x kernel size) + bias 로 계산할 수 있습니다.
  • Weight 는 $Output\ Channel\ 수 × Input\ Channel\ 수 × Kernel\ size × Kernel\ size$ 이므로, $64 × 3 × 11 × 11$ 입니다.
  • Bias 는 Output Channel의 수와 같으므로, 64입니다.
  • 따라서, 총 파라미터 수는 $(64 × 3 × 11 × 11) + 64 = 23,296$ 개 입니다.

• Conv1의 계산에 필요한 floating point(부동소수점) 연산의 수 는 다음과 같이 계산할 수 있습니다.
  • Neural Network에서는 (multiply 한번 + add 한번) 을 한번의 floating point 연산 이라고 계산합니다.
    • 예를 들어, 크기가 3인 두 벡터의 내적은 element-wise 곱셈 3번 수행 후 3번의 덧셈을 수행해서 출력하게 되는데, 이때의 floating point 연산은 3번이라고 계산하는 것입니다.
  • 이는 Output의 총 원소 수 x 각 원소를 계산하기 위한 연산의 수 이므로, $(Output\ Channel × Output\ Height × Output\ Width) × (Input\ Channel × Kernel\ size × Kernel\ size)$ 로 구할 수 있습니다.
  • 따라서, $(64 × 56 × 56) × (3 × 11 × 11) = 72,855,552flops$ 입니다.

• Conv1 계산 후에 ReLU nonlinear activation function를 적용합니다.
• 이후 Pool1 layer를 적용합니다.
  • Channel은 그대로 유지하며, 가로 세로는 down sampling 됩니다.

• Pooling 레이어에서는 $C_{out} = C_{in}$ 이므로, 64입니다.
• Output Width(=Height)는 kernel, stride, input size에 의해 결정 됩니다.
  • $(Input\ width - Kernel\ size) / Stride + 1 = 53 / 2 + 1 = 27.5$
  • 위 결과에서, 소숫점 이하의 값을 내림 해주면 27이 됩니다.

• Pool1의 출력을 저장하기 위한, Output이 차지하는 Memory 공간 은 다음과 같이 계산할 수 있습니다.
  • output의 원소 개수는 $Channel × Height × Width$ 이므로, $64 × 27 × 27 = 46,656$ 개 입니다.
  • 한 원소당 32-bit floating point 크기를 가진다고 할때, 4 byte의 크기를 가집니다.
  • 따라서, Output이 차지하는 Memory 공간을 계산하기 위해서는 다음과 같이 계산합니다.
    • $(number\ of\ elements) × (bytes\ per\ element) / 1024 = 46,656 × 4 / 1024 = 182.25KB$
    • 즉 output을 저장하기 위해서는 182.25KB가 필요합니다.

• Pool1는 learnable parameter가 없습니다.

• Pool1의 계산에 필요한 floating point(부동소수점) 연산의 수 는 다음과 같이 계산할 수 있습니다.
  • Pooling Layer에서는 출력 후 채널별로 더해주는 연산이 없기 때문 에, 식은 $(Output\ Channel × Output\ Height × Output\ Width) × (Kernel\ size × Kernel\ size)$ 가 됩니다.
  • 따라서, $(Output\ Channel × Output\ Height × Output\ Width) × (Kernel\ size × Kernel\ size) = (64 × 27 × 27) × (3 × 3) = 419,904 flops$ 입니다.
    • Convolutional layer에 비해 현저히 적습니다.

• Conv Layer와 pooling Layer들을 여러번 통과 후에, Fully-Connected Layer와의 연결을 위해 Flatten시킵니다.
  • 즉, 입력을 모두 1차원 벡터로 펼쳐주는 연산을 수행하게 됩니다.
  • 이러한 연산을 수행하는 layer를 Flatten layer이라고 하며, 단순히 펼치는 작업 뿐이므로 학습되는 파라미터와 flop은 없습니다.
• 따라서, 출력은 $Input\ Channel × Height × Width = 256 × 6 × 6 = 9216$ 이 됩니다.

• Flatten layer를 통과한 1차원 벡터는 Fully Connected layer에 입력으로 들어가게 됩니다.
• FC6에 대한 파라미터 개수는 weight matrix의 크기와 같습니다.
  • 따라서 $input의\ 채널\ 수 × output의\ 채널\ 수 + bias term$ 입니다.
  • FC6에 대한 부동소수점 연산의 수는, 내적을 각 행마다 연산을 하는데(9216번), $W$ 의 행 개수가 4096이므로, $9216 × 4096 = 37,748,736$ 이 됩니다.

• 그리고 마지막 Fully connected layer는 1000개의 category에 대한 score를 출력하게 됩니다.
• 마지막 FC 레이어의 output은 ImageNet 데이터셋의 class가 1000개이기 때문에 1000개로 맞춰줍니다.

• AlexNet의 모델 구성(위 슬라이드의 빨간색 박스)은 단지 Trial and error를 통해 가장 성능이 좋았을 때의 모델 구성일 뿐입니다.

• 초록색 박스 부분을 보면, 네트워크를 통과하며 메모리, 파라미터, flop이 감소하게 되는 것을 볼 수 있는데, 이는 AlexNet뿐만 아니라, 여러 CNN에서도 따르고 있는 trend입니다.

• AlexNet에서의 메모리, 파라미터, flops에 대한 설명을 정리하면 다음과 같습니다.
  • Memory는 Conv layer가 더 많은 부분을 차지합니다.
    • 초기 Input은 픽셀 수가 높기(이미지 해상도가 높기) 때문입니다.
  • Parameter의 수는 FC layer가 더 많습니다.
    • 학습할 양이 많기 때문입니다.
  • Flops(부동소수점 연산량)은 대부분 Conv layer가 더 많은 연산을 수행합니다.
    • 즉 Conv레이어를 쌓을 때 연산 부담이 커집니다.

• 추가적으로 AlexNet은 대체로 다른 Conv Net의 다이어그램과 유사하긴 하지만, 분산처리(모델이 두개로 나눠진 구조) 를 했다는 차이점이 있습니다.
  • AlexNet을 학습할 당시에 GTX580으로 학습시켰는데, 메모리가 3GB 밖에 없어서 전체 레이어를 GPU에 다 넣을 수 없었기 때문에 네트워크를 GPU에 분산시켜서 학습하였습니다.
  • 따라서 모델을 2개로 나누어 두 개의 GPU가 각각 절반의 뉴런, feature map를 가지는 구조로 학습이 되었습니다.
• 따라서 위의 그림을 보면 첫번째 conv layer 를 나온 output size가 $55 × 55 × 96$ 이 아닌 $55 × 55 × 48$ 이 되어있는 모습을 확인할 수 있습니다.

• 따라서 위 그림과 같이 CONV1, CONV2, CONV4, CONV5에서는 오직 절반의 feature map으로만 연산을 합니다.
• CONV3, FC6, FC7, FC8에서는 나뉜 feature map들이 합쳐져 연산이 되어 최종적으로 전체 네트워크가 전체 feature map을 사용할 수 있게 됩니다.

• 정리하면, AlexNet은 ImageNet Classification Benchmark의 2012년도에 최초의 CNN기반 우승 모델입니다.
• 또한 AlexNet은 다양한 Task의 transfer learning에 많이 사용되었습니다.

ZFNet(2013)

• ZFNet 은 AlexNet 이후, ILSVRC 2013년에 우승한 아키텍쳐 입니다.
• AlexNet에서 많은 하이퍼파라미터에대해 시행착오를 거쳐, layer configuration을 수정하여 우승하였습니다.

• ZFNet은 AlexNet과 아이디어는 동일하지만, 더 큰 버전의 AlexNet입니다.
  • AlexNet과의 차이점은 1번째 Conv layer에서 Filter size와 Stride를 줄여서 더 세밀하게 탐색하도록 하였고, 이후의 Conv layer에서도 출력 필터의 수를 더 늘렸습니다.
  • Conv1에서 커널사이즈와 stride사이즈를 축소하여, 다음 layer가 더 고해상도로 인식 하게 됩니다.
  • Conv3, 4, 5에서 필터 개수를 증가 시킴으로써 연산 횟수, learnable parameter의 개수가 증가했습니다.
• 따라서, 단지 네트워크를 더 크게 하고 연산량을 늘려서 성능을 높인 More trial and less error라고 볼 수 있습니다.

VGGNet(2014)

• 2014년도에 넘어오면서 CNN 구조는 VGG, GoogleNet과 같이 더 복잡하고 깊게 만들어졌습니다.
  • 2012/2013년에는 8개의 레이어인 반면, 2014년에는 19레이어와 22 레이어로 늘어났습니다.
• ILSVRC 2014의 우승자는 Google의 GoogLenet이며, Oxford의 VGGNet이 2등을 차지했습니다.

• VGGNet 은 아주 심플하면서도 nice한 아키텍쳐이며, ImageNet에서 7.3%의 Top 5 Error를 기록했습니다.
  • VGG는 AlexNet보다 더 작은 필터 를 이용하고, 더 많은 레이어 를 가지는 구조로 이루어져있습니다.
  • 또한 AlexNet에서는 8개의 레이어였지만 VGGNet은 16에서 19개의 레이어를 가집니다.
  • 그리고 VGG는 이웃픽셀을 포함할 수 있는 가장 작은 필터인 3×3 size의 filter를 사용 하며, stride 1, padding 1 만을 사용한 CONV layer 들을 구성하였습니다.
• 즉 VGG는 네트워크에 설계에 대한 어떠한 원칙을 갖도록 해준 모델 입니다.
  • AlexNet과 ZFNet은 단순히 trial and error였으며, VGGNet을 통해 네트워크의 확장과 축소를 더욱 쉽게 생각할 수 있게 되었습니다.

• 강조하면 VGGNet이 중요한 이유는 CNN아키텍쳐의 디자인 가이드를 제시했기 때문 입니다.
• VGG는 아주 심플하고 깔끔한 디자인 규칙 을 따릅니다.
  • NN은 기본적으로 5개의 stage로 이루어져 있으며, Stage 1, 2, 3에서는 conv두번에 pooling, 그리고 Stage 4,5에서는 conv를 4-5번하고 pooling 레이어를 쌓았습니다.
  • 모든 Conv layer는 3x3 크기이고, stride와 padding은 1입니다.
  • 모든 Max pool은 2x2 크기이고, stride는 2이며, Max pool 이후에는 channel을 2배로 늘립니다.

Design Rules of VGG

• 지금부터 이러한 구성으로 신경망을 구성한 motivation 을 알아보겠습니다.
• 모든 Conv Layer가 3x3 size 및 pad가 1인 디자인 규칙 에 대해서 살펴보겠습니다.
• 위 슬라이드의 Option 1과 Option 2는 큰 Kernel size를 가진 Conv layer와 작은 kernel size를 가진 Conv layer를 여러겹 쌓은 경우를 비교한 것인데, 그 결과는 다음과 같습니다.
  • 두 경우 모두에서 네트워크가 바라보는 입력의 양(receptive field)이 동일 합니다.
    • 5x5 Conv layer에서 영향을 받는 receptive field는 3x3 크기의 Conv layer 2개를 쌓았을 때와 동일합니다.
    • 마찬가지로, 7x7 크기의 Conv layer는 3x3 크기의 Conv layer 3개를 쌓았을 때와 영향을 받는 receptive field가 동일합니다.
  • 그러므로 작은 kernel size의 Conv layer를 여러겹 쌓은 경우에서 파라미터와 연산량이 더 적으며, 학습 속도를 개선할 수 있습니다.
    • Option 1
      • param = $Input\ Channel\ 수 × Output\ Channel\ 수 × Kernel\ size × Kernel\ size \ = C_{in} × C_{out} × 5 × 5 = 25C^2$
      • FLOPs = $(Output\ Channel × Output\ Height × Output\ Width) × (Input\ Channel × Kernel\ size × Kernel\ size) \ = (C_{out} × H × W) × (C_{in} × 5 × 5) = 25C^2HW$
    • Option 2
      • param = $9C^2 + 9C^2 = 18C^2$
      • FLOPs = $9C^2HW + 9C^2HW = 18C^2HW$
    • 즉 Params와 FLOPs 계산결과를 보면 3x3 Conv layer를 2개 쌓은 것이 5x5 Conv layer보다 더욱 적습니다.
    • 만약 $3×3$ size 필터를 가진 conv layer 세 개와, $7×7$ size 의 필터를 사용한 conv layer 한 개를 비교하면 다음과 같이 됩니다.
      • $3 × (3^2C^2) = 27C^2$ vs $7^2C^2 = 49C^2$
  • 또한 작은 kernel size의 Conv layer를 여러겹 쌓은 경우가 더 높은 표현력을 갖게 됩니다.
    • Conv layer를 여러번 쌓게되면, 더 많은 ReLU를 통과하며 비선형성(non-linearity)이 추가되므로 더 높은 표현력 을 가지게 됩니다.
• 따라서, 본 디자인 규칙은 작은걸 여러개 쌓는게 더 좋으니까 하이퍼파라미터로서 kernel size는 고려하지 않아도되고, 네트워크의 깊이만 고려하면 된다는 의미 를 담고 있습니다.

• 다음 디자인 규칙은, 모든 Max pool은 2x2 크기이고, stride는 2이며, Max pool 이후에는 channel을 2배로 늘리는 것 에 대해 살펴보겠습니다.
• 위 슬라이드의 Option 1과 Option 2는 Max pool 이후 channel을 2배 늘린 경우의 전과 후를 비교한 것인데, 그 결과는 다음과 같습니다.
  • Memory : 절반으로 줄어들었습니다.
  • Parameters : 4배 증가했습니다.
  • FLOPs : 그대로 유지됩니다.
• 여기서, 중요한 것은 연산량(FLOPs)가 유지된다는 점입니다.
  • 결국 channel을 2배 늘린 이유는 픽셀이 반으로 줄어도, 각각의 conv stage에서는 동일한 부동소수점 연산 수를 갖게 주기 위함 입니다.
• 따라서, 디자인 규칙 2는 각 stage에서의 Conv layer의 kernel size(each spatial resolution)가 변해도 Max pool 이후 channel을 2배로 해줌으로써 연산량을 동일하게 유지할 수 있다는 의미를 담고 있습니다.

• 다음은 VGGNet의 전체 네트워크를 한번 살펴보겠습니다.
• AlexNet의 총 파라미터 수는 60M인 반면, VGG는 총 파라미터 수는 약 138M 정도 임을 알 수 있습니다.
• VGG는 메모리 사용량이 많은 모델 입니다.
  • 초기 레이어에서 많은 메모리를 사용하는 것을 알 수 있습니다.
  • Sparial dimention이 큰 곳들이 메모리를 더 많이 사용합니다.
• 마지막 레이어는 많은 파라미터를 사용합니다.
  • FC-Layer는 dense connection이기 때문에 엄청난 양의 파라미터를 사용합니다.
  • 최근의 네트워크들은 너무 많은 파라미터를 줄이기 위해 FC Layer를 없애버리기도 합니다.

• 다음은 VGGNet의 Details 입니다.
  • VGGNet은 ImageNet 2014 Classification Challenge에서 2등, Localization에서는 우승을 했습니다.
  • AlexNet에서 사용한 Local response normalization은 사용하지 않습니다.
  • VGG16과 VGG19은 아주 유사하며, VGG19가 아주 조금 더 좋습니다. 보통 16을 더 많이 사용합니다.
  • 그리고 모델 성능을 위해서 앙상블 기법을 사용했습니다.
  • VGG의 마지막 FC-Layer인 FC7은 4096 사이즈의 레이어인데 아주 좋은, feature represetation을 가지고 있는 것으로 알려져있습니다.
    • 아주 좋은 feature representation으로, 다른 데이터에서도 특징(feature) 추출이 잘되며, 다른 Task에서도 일반화 능력이 뛰어난 것으로 알려져있습니다.

• 마지막으로 위 슬라이드는 VGGNet과 동일하게 5개의 Conv layer와 3개의 FC layer를 가지는 AlexNet을 비교한 것입니다.
• 이를 통해 VGGNet이 AlexNet에 비해 엄청나게 큰 모델 이라는 것을 알 수 있습니다.

GoogLeNet

• GoogLeNet은 ILSVRC 2014 Classification Challenge에서 우승한 모델입니다.
• VGGNet과 마찬가지로 depth가 깊어졌으며, 더 좋은 accuracy를 달성했습니다.
• GoogLeNet 은 계산 효율성을 고려하여 구성한 아키텍쳐 입니다.

• 즉 GoogLeNet은 성능을 높임과 동시에 네트워크 계산 효율성을 고려하는 것에 집중한 모델 입니다.
  • AlexNet에서 VGG까지의 모델들은 모두 네트워크의 크기가 커질수록 좋은 성능을 보이는 것에 집중한 모델이었지만, GoogLeNet은 효율적인 CNN을 설계하는 방법에 집중하였습니다.
  • 즉 GoogLeNet은 Parameter 개수, memory 사용, 연산 수를 줄이는 것에 중점 을 두었습니다.
  • Mobile에서는 training단계를 거치지는 않지만, Testing time에서 forward pass를 거쳐야 하므로 효율성이 중요합니다.

• GoogLeNet도 엄청 깊은 네트워크입니다.
• 반복하지만 GoogLeNet에서 가장 중요한 것은 효율적인 계산에 관한 특별한 관점이 있다는 것과 높은 계산량을 아주 효율적으로 수행하도록 네트워크를 디자인했다는 점입니다.
• GoogLeNet은 Inception module 을 사용합니다.
• GoogLeNet에는 파라미터를 줄이기 위해서 FC-Layer가 없습니다.
• 또한 전체 파라미터 수가 5M 정도입니다.
  • 60M인 AlexNet보다 적지만, 그럼에도 불구하고 훨씬 더 깊습니다.
• ILSVRC 2014에서 6.7%의 top-5 error로 우승했습니다.

GoogLeNet: Aggressive Stem

• 지금부터 GoogLeNet의 구조를 톺아보겠습니다.
• GoogLeNet의 첫번째 아이디어는 맨 처음에 Stem Network 를 사용한 것입니다.
  • 앞선 아키텍쳐들은 앞쪽 단계에서 고해상도의 이미지에 Conv layer 적용시 부동소수점 연산이 집중되어 있었습니다.
  • GoogLeNet은 해당 연산 수를 줄이기 위해서, 앞쪽 단계에서 빠르게 downsampling을 진행하는 선택을 했습니다.
  • 즉 Stem Network 는 입력 이미지를 아주 aggressively하게 다운샘플링 하는 역할을 수행하는 네트워크를 의미 하는데, 이를 사용한 이유는 초기의 expensive한 Conv 연산을 피하기 위함입니다.
• 슬라이드의 표에서, 3번의 Conv layer만으로 224x224 크기의 입력(resolution)이 28x28로 빠르게 줄어든 것을 볼 수 있습니다.
  • 앞쪽 단계에서 빠르게 downsampling을 진행함으로써, VGGNet에 비해 memory, parameter 수, 연산 수 모두 줄어들었음을 알 수 있습니다.

GoogLeNet: Inception module

• GoogLeNet의 두번째 아이디어는 연산 효율성을 올릴 수 있었던 핵심적인 부분인 Inception module 입니다.
• inception module은 좋은 local network typology를 디자인 하기위해 설계되었으며, 네트워크 안의 네트워크 (network within a network)의 개념으로 만들어졌습니다.
• GooleNet은 Inception module들을 쌓아올려 구성합니다.

• 즉 네트워크 안의 Local Network를 Inception module 이라고 합니다.
• 슬라이드의 Inception module은 Naive Inception module 입니다.
• Inception Module 내부에는 동일한 입력을 받는 서로 다른 다양한 필터들이 “병렬로” 존재합니다.
  • 1×1 CONV, 3×3 CONV, 5×5 CONV, 3×3 MAX POOL 연산이 병렬적으로 이루어집니다.
• 각 filter를 통해 연산되어 나온 output 들을 모두 depth 방향으로 합칩니다.(concatenate)
  • 합쳐진 하나의 출력을 다음 레이어로 전달합니다.
• 하지만 Naive Inception module은 계산 비용의 문제점이 존재 합니다.

• 예제를 살펴보겠습니다.
• 1×1 CONV 128개, 3×3 CONV 192개, 5×5 CONV 96개, 3×3 MAX POOL이 있으며, 각 연산은 병렬적으로 이루어지며, stride를 조절하여 입/출력 간의 spatial dimention을 유지시켜줍니다.
• Module input이 28×28×256일때 다음과 같습니다.
  • 1 x 1 x 128 conv의 출력: 28 x 28 x 128
  • 3 x 3 x 192 conv의 출력: 28 x 28 x 192
  • 5 x 5 x 96 conv의 출력: 28 x 28 x 96
  • 3 x 3 Pool의 출력: 28 x 28 x 256

• 모든 출력 값들을 depth-wise로 합친(concat) 사이즈를 계산해볼때 28 x 28 은 동일하고 depth가 점점 쌓이게 됩니다.
  • Inception module의 입력: 28 x 28 x 256
  • Inception module의 출력: 28 x 28 x (128 + 192 + 96 + 256) = 28 x 28 x 672 = 529K
  • spatial dimention은 변하지 않았지만 depth가 엄청나게 증가했습니다.
• 그리고 각 레이어들의 계산량을 한번 살펴보면 다음과 같습니다.
  • 1 x 1 x 128 conv의 연산량: 28 x 28 x 128 x 1 x 1 x 256
    • 1 x 1 conv는 각 픽셀마다 1 x 1 x 256 개의 내적연산을 수행되므로, 픽셀 당 256번의 곱셈 연산이 수행됩니다.
    • 그리고 각 픽셀이 총 28 x 28이며, 128개의 filter를 만들기 때문에 다음과 같이 연산됩니다.
  • 3 x 3 x 192 conv의 출력: 28 x 28 x 192 x 3 x 3 x 256
  • 5 x 5 x 96 conv의 출력: 28 x 28 x 96 x 5 x 5 x 256
  • 따라서 하나의 Inception Module에서의 전체 연산량은 854M가 되며, 이는 연산량이 아주 많습니다.
• Pooling layer 또한 입력의 Depth를 그대로 유지하기 때문에 문제를 악화시킵니다.
  • 즉 레이어를 거칠때마다 Depth가 점점 늘어만 갑니다.

Reminder: 1x1 convolutions

• Naive Inception module은 계산 비용의 문제점을 해결하기 전에 1x1 conv 를 다시 한번 살펴보겠습니다.
• 1x1 conv는 각 spatial location에서만 내적을 수행합니다.
  • 즉 spatial dimensions을 보존하면서, depth만 줄일 수 있기에, 입력의 depth를 더 낮은 차원으로 projection할 수 있습니다.
• Input feature map들 간의 선형결합(linear combination) 또는 각 input pixel에 동일한 FC layer를 적용하는 것으로 해석 할 수 있습니다.

Solution: “bottleneck layers”

• Naive Inception module은 계산 비용의 문제점을 해결하기위한 key insight는 “bottleneck layer” 를 이용하는 것입니다.
• “bottleneck layer”는 feature의 depth를 감소시키기 위해 1x1 convolutions을 사용하는 것을 의미 합니다.
• “bottleneck layer” 아이디어는 입력의 depth를 줄이는 것 입니다.
  • ouput의 채널수가 계속해서 많아져 연산량이 증가하는 문제를 해결하기 위해 Inception module 내부의 각 연산 과정에도 이러한 1x1 convolutions을 추가해 input의 차원(depth)을 축소합니다.
  • 3×3 conv, 5×5 conv 연산 이전에 1×1 conv 연산으로 함으로써 3×3 conv, 5×5 conv 연산에 들어갈 input 의 channel 수를 줄입니다.
  • pooling layer 에서는 3×3 pooling 연산 이후에 1×1 conv 연산을 적용하여 output 의 channel 수를 줄입니다.
• 즉 1x1 convolutions이 bottleneck layers의 역할로 추가되는 것입니다.
  • 픽셀별로 nonlinearity를 줄 수 있는 방법 으로서, 픽셀별로 fc layer에 한번 돌린 것보다 효과가 좋습니다.

• 즉 GoogLeNet은 Inception module with dimension reduction을 사용 하였습니다.
• Inception 모듈은 VGG와 같이 kernel size에 대해 하이퍼파라미터를 고려하지 않도록 설계 되었습니다.
  • Inception 모듈은 4개의 parallel한 branch가 있는데 각각 1x1 Conv, 3x3 Conv, 5x5 Conv, Max pool입니다.
  • 즉, Inception 모듈 안에서 다양한 크기의 kernel size를 고려하게 되므로, 하이퍼파라미터로 고려할 필요가 없게 되는 것입니다.
• 또한 Inception 모듈에서 또 한가지 주목할 것은 1x1 Conv 연산입니다.
  • 연산 비용이 비싼 spatial한 Conv 연산을 수행하기 전에 1x1 Conv 연산을 통해 input channel의 차원을 조절하여(줄여서) 연산량을 줄이는 방법을 사용 하였습니다.

• 결과적으로 1x1 convolutions를 추가함으로써 연산량을 많이 줄일 수 있습니다.
• 그리고 이를 통해 배울 수 있는 점은 1x1 convolutions를 이용하면 계산량을 조절할 수 있다는 사실입니다.
• 이때, 1x1 convolutions을 사용함으로써 input의 정보 손실이 일어나지 않을까라고 생각할 수도 있는데, 1x1 convolutions을 추가함으로써 네트워크가 더 깊어지는 효과도 있고 각 conv 연산 이후 ReLu와 같은 non-linear activation function을 사용함으로써 모델에 비선형성(non-linearity)를 부여할 수 있어 도움이 됩니다.

GoogLeNet: Global Average Pooling

• GoogLeNet의 세번째 아이디어는 네트워크의 맨 마지막에서 수행한 Global Average Pooling 입니다.
  • AlexNet에서 VGGNet까지의 네트워크에서 보았듯이, 모델 파라미터의 대부분은 마지막의 FC layer에서 나오게 됩니다.
  • GoogLeNet에서는 마지막 Conv layer의 출력을 1차원 벡터로 만드는 Flatten 연산 대신, 파라미터를 줄이기 위해 Global Average Pooling을 사용하여 이러한 파라미터의 수를 줄이며 efficiency를 높였습니다.
• Global Average Pooling은 마지막 Conv layer의 출력에서, 각 채널별로 1개씩의 평균을 구해 출력하는 방법입니다.
  • 슬라이드의 윗쪽 표를 보면, 7x7 크기의 1024개의 채널이 Global Average Pooling에 입력으로 들어가서, 1024 크기의 1차원 벡터가 출력되는 것을 확인할 수 있습니다.
• 슬라이드 아래의 표(VGGNet)와 비교해보면, Global Average Pooling이 VGGNet에 비해 엄청난 양의 파라미터 수를 줄여주었다는 것을 알 수 있습니다.

GoogLeNet: Auxiliary Classifiers

• GoogLeNet의 마지막 아이디어는 Auxiliary Classifier 입니다.
  • Batch Normalization이 나오기 이전에는 deep Network 트레이닝이 어려워서, 10개 이상의 layer를 가지는 네트워크를 학습시키기 위한 여러가지 방법들(hack)을 사용하였는데, 그중 GoogLeNet에서 사용한 방법이 Auxiliary Classifier입니다.
  • Auxiliary classifier는 AvgPool - 1×1 Conv - FC - FC - Softmax로 이루어져 있습니다.
• 슬라이드에서 2개의 빨간색 박스가 Auxiliary Classifier인데, 이는 네트워크의 최종 출력과 같이 class score를 출력합니다.
  • 따라서, GoogLeNet은 총 3개의 다른 class score를 출력하였습니다.
    • 하나는 네트워크의 마지막, 나머지 두개는 네트워크의 중간
• 그리고 이 중간의 두 classifier의 score에 대해서도 trainset loss를 계산하여 gradient가 전파되도록 하였습니다.
  • 이는 네트워크에서 gradient가 더 잘 전파되도록 하는 효과 가 있었습니다.
  • 네트워크의 끝에만 gradient를 주입하는 것보다 네트워크의 중간에 gradient를 두번 더 주입하는 것이라고 생각하면 됩니다.
• 즉 이러한 Auxiliary classifier를 사용해서 네트워크 중간 중간에서 class를 분류하고, loss값을 이용함으로써 네트워크가 깊어져도 네트워크의 중간 중간에서 gradient를 잘 이용하여 학습할 수 있게 합니다.
• inference하는 과정에서는 중간에 2개의 auxiliary classifier를 모두 제거 후, 제일 마지막 layer의 softmax만을 사용 합니다.

GoogLeNet Architecture

• 전체 아키텍쳐의 모습입니다.
• 정리하면 GoogLeNet에는 가중치를 가진 레이어가 총 22개이며, 각 Inception Module은 1x1/3x3/5x5 conv layer를 병렬적으로 가지고 있습니다.
• AlexNet보다 12배 작은 파라미터를 가지고있고, ILSVRC 2014 clssification의 우승 모델입니다.
• GoogLeNet은 아주 신중하게 디자인된 모델이며, Google의 거대한 클러스터를 이용한 cross validation을 수행한 결과 나온 최적의 디자인 입니다.

ResNet(2015)

• ResNet 은 ILSVRC 2015 Classification Challenge에서 우승한 모델 입니다.
• ResNet은 layer개수를 크게 증가시키면서, accuracy는 반으로 줄이는 혁신을 선보였습니다.
  • ResNet 아키텍쳐는 152 레이어로 엄청나게 더 깊어졌습니다.

• ResNet 아키텍쳐는 이전의 다른 모델들에 비해 엄청나게 깊은 네트워크입니다.
• ImageNet데이터를 분류하기 위해 ResNet은 152개의 레이어를 가지고 있습니다.

motivation of ResNet

• Batch normalization이 등장하고 사람들은 10개 이상의 layers를 쌓는 deeper network가 가능해짐을 깨달았습니다.
• 기존 트렌드는 더 깊은 네트워크일수록 더 좋은 성능을 내 왔기 때문에 deeper network에서 더 좋은 성능을 낼 것으로 기대했지만, 문제는 너무 깊어지니 BN을 적용했음에도 불구하고 성능이 더 나빠졌습니다.
  • 위 그림에서, 56개 layer 모델이 20개 layer 모델보다 성능이 좋지 않은 것을 확인할 수 있습니다.
• 처음에는 이러한 현상이 딥러닝 모델이 Overfitting되었기 때문일 것이라고 추측 하였습니다.
  • 따라서 더 깊은 모델은 학습 시 Overfitting이 된 것이라고 가정을 하고 실험을 진행했습니다.

• 하지만 실험을 통해 알게된 사실은 매우 깊은 네트워크가 Overfitting이 아니라 오히려 Underfitting 되었다는 것입니다.
  • 위 슬라이드의 왼쪽과 오른쪽 그래프는 각각 Training data, Test data에 대한 결과인데, deeper model에서 둘 모두 안좋은 성능을 보이기 때문에 overfitting 문제가 아닙니다.
    • 그리고 overfit이 발생한다면 test error는 높더라도 training error는 아주 낮아야 정상일 것 입니다.
    • 그런데 56-layer의 traing error을 보면 20-layer보다 안좋습니다.
    • 그러므로 더 깊은 모델임에도 test 성능이 낮은 이유가 over-fitting 때문이 아니라는 것을 알 수 있습니다.
  • Training error을 살펴본 결과 deep model은 사실상 underfitting 되어있었습니다.
    • Training자체가 잘 되지않았습니다.
• 이러한 현상이 발생하는 이유는 네트워크가 깊어짐에 따라 모델을 최적화(optimize)하여 학습시키기 어렵다는 점 때문입니다.
  • 네트워크가 깊어지면 vanishing gradient/exploding gradient 문제 등이 발생하여 모델을 학습이 시키기 어려워져 오히려 안좋은 성능을 보이는 것입니다.

• deeper models은 shallower models보다 더 많은 representation power(more parameters)를 가집니다.
• 그렇다면 deeper models은 shallower models을 재현할 수 있어야 한다는 것 입니다. 적어도 비슷한 성능을 내기를 원한 것 입니다.
  • shallower models의 layer를 deeper models의 layer에 복사한 후, 나머지 layer를 identity function으로 생각한다면 얕은 모델을 emulate 한다고 생각할 수 있습니다.
    • ex. 첫 20개의 레이어는 20개의 레이어를 가진 모델을 통째로 복사하고 나머지 레이어는 identity function 역할만 하면되기에 이론적으로 56개의 레이어의 모델은 최소한 20개 레이어의 모델만큼의 성능은 보장됩니다.
  • 따라서 deeper models은 최소한 shallower models만큼 효과적이어야 합니다.
• 하지만, 여러 실험에서 깊은 모델이 underfitting 되었다는 것이 의미하는 것 은, 깊은 모델이 얕은 모델을 재현(emulate)하는 identity function를 optimization하는데 문제가 있다는 것을 의미합니다.

• 결론적으로, 다음과 같은 가설 을 세웁니다.
  • 해당 문제는 training 문제가 아니라, optimization problem 입니다.
  • deeper models은 optimization하기 더 어려우며, 때문에 특히 shallower models을 모방하기 위한 identity functions을 학습하지 않습니다.
• deeper models이 적어도 shallower models만큼 우수하려면, 네트워크를 수정해서 identity function을 잘 학습하도록 하는 것이 해결방안 입니다.
  1. 더 얕은 모델의 가중치를 깊은 모델의 일부 레이어에 복사합니다.
  2. 그리고 나머지 레이어는 input을 output으로 그냥 내보내서 identity mapping을 합니다.
• 이렇게 구성하면 Deeper Model의 학습이 제대로 안되더라도 적어도 Shallow Model 만큼의 성능은 보장됩니다.

• 이러한 문제를 해결하기 위해 ResNet에서는 identity function을 더 잘 학습하기위해서, skip connection을 이용한 Residual block 을 사용합니다.
• 즉, 수정된 네트워크 구조는 Residual Block 입니다.
  • Residual block은 일반적인 여러개의 conv layer들로 이루어져있고, 여기에 skip connection을 추가한 구조로 이루어져있습니다.
  • Skip connection 이란, 이전 레이어의 input(residual block의 처음 input)을 그대로 residual block의 output에 mapping하여 최종 output을 만들어내는 것 입니다.
  • 여기서 이전 레이어에 가져와 그대로 합쳐주는 x를 identity 라고 하고, 이것을 이후 output에 합치는 것을 identity mapping 이라고 표현합니다.
    • 이것을 수식으로 표현하면 H(x) = F(x) + x 라고 할 수 있습니다.
    • H(x)는 전체 conv layer들을 통과한 함수를 뜻합니다.
    • 원래는 전체 conv layer, 위 그림에서 H(x)를 학습해야했는데, 이렇게 skip connection을 이용함으로써 F(x)만 학습할 수 있게 됩니다. F(x) = H(x) − x 로 표현할 수 있으니, 이것은 즉 해당 block 에서 입력 x에 대한 잔차(residual) or 변화량(delta)만 학습 한다고 할 수 있습니다.
    • 따라서 residual block 이라고 부르는 것입니다.
• 네트워크는 Residual만 학습하면 그만이며, 레이어가 Full mapping을 학습하기 보다 이런 조금의 변화(X에 대한 변화량(delda))만 학습하는 것 입니다.
  • 만약 H(x)를 직접 학습시키는 대신에 F(x)인 Residual을 학습하는게 더 쉽다라는 가설이 참이라면, 어쩌면 대부분의 레이어가 잘 동작하려면 레이어의 출력이 Identity에 가까워야 할지 모른다는 것을 암시합니다.
  • 그러므로 Identity(Input)을 단순히 더해주고, 변화량(delta)만 학습시키면 됩니다.
• 정리하면 ResNet의 아이디어는 H(x) = F(x) + X 이니, F(x)를 학습시켜보면 어떨까? 하는 것이며, H(x)를 직접 배우는 대신에 X에 얼마의 값을 더하고 빼야할까?(Residual)를 배우는 것이 쉬울 것이라고 생각한 것이므로, 입력값을 어떻게 수정해야 하는지를 배운다고 보면 됩니다.

• 이 방식은 깊은 네트워크가 얕은 네트워크를 더 쉽게 emulate할 수 있게 해줍니다.
  • identity function에 대해 쉽게 학습이 되기를 기대하는 의미입니다.
  • 만약 슬라이드의 Residual Block안에 있는 2개 Conv layer의 weight를 0으로 설정한다면, 두 layer의 출력은 0이 되고 Residual Block의 최종 출력 결과는 identity를 계산하게 됩니다.
  • 또는 Input = output 이어야 하는 상황이라면 레이어의 출력인 F(x)가 0 이어야 하므로(residual = 0) 모든 가중치를 0으로 만들어주면 그만입니다.
• 또한, 깊은 네트워크에서 gradient의 흐름을 개선하는데에도 도움이 됩니다.
  • Back Propagation에서, Add gate는 입력 모두에 gradient를 전달해주는 gradient distributor 역할을 수행합니다.
  • 이러한 gradient의 전달이 Residual Block에서는 short cut으로 이루어지게 되므로, 깊은 네트워크에서 gradient의 흐름이 더 원활하게 이루어지게 됩니다.

Full ResNet architecture

• 전체 ResNet 구조에 대해 살펴보겠습니다.
• Residual Networks(ResNet)는 Residual Block을 쌓은 네트워크 구조입니다.
• 위 슬라이드를 보면, VGG에서 유사한 방식으로 residual block을 쌓은 형태라는 것을 알 수 있습니다.
  • Residual Block은 2개의 3 x 3 Conv 레이어로 구성되어있습니다.
  • 여러개의 stage로 나눠져있으며, stage가 시작할때 convolution시 stride=2를 적용하여 downsampling하고 그에따라 filter의 갯수를 2배로 늘립니다.

• 또한 GoogLeNet과의 유사한 점은 다음의 2가지가 있습니다.
  • 처음의 몇개 layer에서 aggressive down sampling을 수행하여, 네트워크 초반에 연산량을 줄입니다.(Stem Network)
  • 마지막 Conv layer의 출력인 네트워크의 끝에는 FC-Layer가 없고, Global Average Pooling을 수행하여 파라미터를 줄입니다.
    • 이후 FC-Layer, softmax를 이용해 class수 만큼의 output을 출력합니다.
      

• ResNet 모델의 Depth는 34, 50, 100까지 늘어나며, 논문에서는 ImageNet문제를 위해 152까지 늘렸습니다.
• ResNet-18의 구조는 다음과 같습니다.
  • Stem을 수행한 후, 총 4번의 stage를 반복하고 Linear layer(FC layer)로 결과를 출력합니다.
  • 각 stage에는 2번의 residual block과 4개의 Conv layer가 있습니다.
  • 18의 의미는 layer의 수를 의미합니다. (Stem에서 1개, 모든 stage에서 16개, 최종 출력에서 1개)
• ResNet-34의 구조는 다음과 같습니다.
  • Stem, 총 4번의 stage, FC layer의 형태는 동일합니다.
  • 각 stage에서 residual block(Conv layer)의 수가 더 증가했습니다.
  • 위 슬라이드 하단의 VGG-16과 비교해보면, ResNet이 더 적은 연산(FLOPS)을 수행하는 것을 알 수 있는데(4배 차이), 이는 Stem과 Global Average Pooling을 수행했기 때문입니다.

Residual Networks: Bottleneck Block

• ResNet은 모델의 Depth가 50 이상일때 연산 효율을 높이기 위해 Bottleneck Layers 를 도입합니다.
  • GoogLeNet에서 사용한 bottleneck layer와 유사한 개념입니다.
• Residual block의 conv layer에 들어가기 전에 1×1 conv layer를 이용해 차원(채널수)을 줄여서 3×3 conv layer의 연산량을 줄여주고, 이후에 1×1 conv layer를 이용해 다시 차원(채널수)을 늘리는 구조로 이루어져 있습니다.

• 즉 Residual Network를 더 깊게 쌓기 위해 Bottleneck Block이라는 구조가 새롭게 만들어졌습니다.
• 슬라이드는 “Basic Residual block”과 “Bottleneck Residual block”을 비교한 것입니다.
  • Basic block
    • Basic Residual block은 2개의 3 x 3 Conv레이어를 쌓음으로써, 각각 $9HWC^2$ 이므로 총 $18HWC^2$의 부동소수점 연산이 필요합니다.
    • 즉 3x3 Conv를 두번 수행합니다.
  • Bottleneck block
    • 먼저, 1x1 Conv layer를 사용해 입력의 채널을 1/4로 줄입니다. 그러므로 FLOPs는 $4HWC^2$ 입니다.
    • 3x3 Conv를 수행합니다. 그러므로 FLOPs는 $9HWC^2$ 입니다.
    • 마지막으로, 다시 1x1 Conv layer를 통해 입력의 채널을 4배로 키웁니다. 그러므로 FLOPs는 $4HWC^2$ 입니다.
    • 총 FLOPs는 $17HWC^2$ 입니다.
• 위의 각 과정에서의 FLOPs를 모두 계산해보면, Bottleneck block이 더 깊어졌지만 연산량은 오히려 더 줄어들었다는 것 을 알 수 있습니다.
• 따라서, Basic에서 Bottleneck으로의 전환은 아래와 같은 효과를 얻게됩니다.
  • 더 적은 연산량
  • 더 높은 표현력 (더 많은 layer을 통과하면서 더 많은 비선형성이 추가됨)

• ResNet-34에서 Basic block을 Bottleneck block으로 전환한 네트워크 형태가 ResNet-50입니다.
  • Network는 더 깊어졌고, 레이어수가 3배가 되며, error는 더 줄어들었지만, 연산량에는 큰 변화가 없습니다.
• ResNet-50보다 더 많은 Bottleneck block을 쌓은 구조들이 ResNet-101, ResNet-152이며 깊어질수록 네트워크가 더 잘 동작하므로 error는 조금씩 감소하였습니다.
  • 정확도가 더 높지만 연산 부담이 큰 모델입니다.

• ResNet을 훈련할때 여러가지 구체적인 방법들을 사용했습니다.
  • 모든 conv layer 이후에 batch normalization 을 사용했습니다.
  • He initialization 방법으로 가중치 초기화를 했습니다.
  • optimizer로 SGD+Momentum을 사용하고 초기 learning rate 는 0.1 로 설정하여 validation error 가 줄어들지 않는 시점에 learning를 10배씩 감소시키는 learning rate decay를 사용했습니다.
  • mini-batch size는 256입니다.
  • weight-decay는 1e-5를 사용하고 dropout은 사용하지 않았습니다.

• ResNet은 네트워크가 깊어질수록 error가 점점 줄어드는 경향을 보이며 엄청난 격차를 보이는 좋은 성능으로 대회에서 우승합니다.
  • degradation문제 없이 Very deep network를 아주 잘 학습시킬 수 있었습니다.
• ResNet은 ILSVRC와 COCO의 모든 대회종목을 2등과의 엄청난 격차로 휩쓸었습니다.
• Total top-5 Error는 3.6%로, ImageNet paper에서 제시한 “인간의 성능” 보다 뛰어났습니다.

Comparing complexity

• 왼쪽 그래프는 성능을 비교하는 그래프 이고, 오른쪽 그래프는 연산 수를 비교하는 그래프 입니다.
  • 오른쪽 그래프에서 x축은 모델의 연산량을 의미하고 y축은 모델의 성능(accuracy)을 의미합니다.
  • 오른쪽 그래프에서 오른쪽으로 갈 수록 헤비한 네트워크, 위로 갈수록 성능이 좋은 네트워크, 원 크기는 파라미터 개수(클수록 메모리가 부담)
• 모델 별로 성능과 복잡도(complexity)를 비교해서 살펴보겠습니다.
  • Inception-v4는 ResNet+inception모델이 합쳐진 개념으로 가장 좋은 성능을 보입니다.
  • AlexNet은 Accuracy가 낮으며 연산수는 적지만, 파라미터 개수가 많아 네트워크 입니다.
  • VGG를 보면 연산량과 메모리 사용량이 엄청 커서 효율성이 작습니다.
  • GoogLeNet은 연산량과 메모리사용량이 굉장히 작은 효율적인 모델입니다.
  • ResNet은 심플한 디자인, 양호한 효율성의 네트워크로 정확도가 아주 높아 성능이 좋습니다.

• 다음으로, 각 모델에서 forward pass 하는데에 필요한 시간과 전력사용량을 비교한 그래프 입니다.
• 왼쪽 그래프가 forward pass 하는데 걸리는 시간, 오른쪽 그래프가 전력사용량 입니다.
• VGG가 시간이 오래 걸리는 것을 확인할 수 있고, ResNet은 적당한 정도로 분포하는 것을 알 수 있습니다.

Model Ensembles(2016)

• 2016년에는 이전처럼 혁신적인 시도보다는 이전까지의 모델을 이용한 앙상블 방식 의 모델이 많이 쓰였습니다.
• Inception, Inception-Resnet, Resnet, Wide Resnet models의 Multi-scale ensemble을 사용하여 0.6%를 개선시켜 우승하였습니다.

SENet(2017)

• 2017년 ResNext의 아이디어를 바탕으로한 여러 연구들을 통해서 Squeeze-and-Excitation(SE) 라는 방법을 사용한 SENet 이라는 모델이 나왔습니다.
• 그리고 이 모델이 2017년 좋은 성능을 보인 것을 마지막으로 ImageNet challenge는 끝납니다.

Other Networks

• 위에 모델들에 이어서 추가적으로 몇가지 중요한 모델 구조, ResNet에서 변형된 모델 구조들에 대해 살펴보겠습니다.

Network in Network(NiN)

• 2014년에 나온 논문으로 Network in Network 입니다.
• Network in Network의 기본 아이디어는 MLP Conv layer로, 각 Conv layer안에 FC-layer (multi-layer perceptron)를 넣는 것 입니다.
  • convolution시 filter 대신에 MLP를 사용해서 feature를 추출하는 방법을 고안했습니다.
  • 즉, Conv layer에서 filter를 거쳐나온 output을 여러개의 FC-layer에 통과시킴으로써 추상적인(abstract) feature 들을 추출해 더 복잡한(complex) activation map을 출력할 수 있도록 합니다.
• 이때, NiN 에서 말하는 FC-layer는 1×1 Conv layer라고 할 수도 있습니다.
• GoogLeNet과 ResNet에서 사용하는 bottleneck의 개념이 바로 이 NiN 에서 가져온 아이디어이기 때문에 NiN 은 큰 의미를 가집니다.

Identity Mappings in Deep Residual Networks

• 2014년에 나온 논문으로 Identity Mappings in Deep Residual Networks 입니다.
• 여기서는 ResNet block의 skip connection부분이 아닌 direct path 부분을 조절 하여 모델의 성능을 올렸습니다.

• “Pre-Activation”은 operation 순서를 바꿔 본 시도로, ReLU를 conv레이어보다 먼저 넣었습니다.
• Original ResNet block 에서는 윗단 레이어은 ReLU를 거친 positive값만 받기때문에, Identity function을 제대로 학습하지 못할 것 같다는 생각에서 출발한 시도입니다.

• 여러 실험들을 통해 논문에서 얻어낸 결론을 요약해보면 다음과 같습니다.
  • shortcut path (skip connection 부분)의 정보는 최대한 손상시키지 않는 것이 backpropagation, 정보 전달 측면에서 유리 합니다.
  • residual path에서는 shortcut과 합쳐주기 전에 activation function을 적용하는 것이 유리 하다는 것을 알아냈습니다.
• Accuracy는 1퍼센트정도 늘어나며, 크게 차이가 없으므로, 잘 사용되지는 않습니다.

Wide Residual Networks

• 또 다른 ResNet 에서 개선된 모델로 Wide ResNet 이 있습니다.
• 본 논문의 저자는 ResNet에서 네트워크의 깊이(depth)가 중요한게 아니라 residual 구조가 성능 향상에 큰 도움을 줬다고 주장 합니다.
• 따라서 네트워크가 extreamly 하게 깊어질 필요가 없다고 생각하여 residual block을 더 넓게 만들었습니다.
  • 본 논문에서 wide 하다는 의미는 channel의 개수가 많다는 것을 의미합니다.
  • 즉, WRN은 residual block을 구성하는 convolution layer의 filter 수를 증가시켜서 신경망의 넓이를 증가시켰습니다.
  • Widening factor k에 따라 channel 개수가 늘어나는 구조입니다.
  • 기존의 ResNet에는 Block 당 F개의 filter만 있었다면, F * K 개의 필터로 구성했습니다.
• 이렇게 각 레이어를 넓게(filter 의 갯수를 늘려) 구성하여 단 50개의 레이어만으로도 기존 152개의 레이어를 가지는 ResNet 보다 성능이 좋게 나오는 것을 증명 했습니다.

• 저자들은 기존 구조의 순서인 Conv-BN-ReLU가 아닌 BN-ReLU-Conv로 순서를 변경했습니다. 후자가 더 빨리 훈련하고 좋은 결과를 냈습니다. residual block의 power를 향상시킬수 있는 간단한 3가지 필수적인 방법은 다음과 같습니다.
  1. 합성곱층을 block마다 더 추가한다.
  2. feature planes를 더 추가하면서 합성곱층의 너비를 넓힌다.
  3. 합성곱층의 필터 size를 증가시킨다.

• 논문 저자들의 residual network의 일반적인 구조입니다.
• 논문에서 깊이 factor는 l, 너비 factor는 k로 나타냈습니다. figure1(a),(c)는 basic 모델과 basic-wide모델의 예를 보여줍니다.

• 위 표는 ImageNet과 COCO dataset의 성능을 비교합니다.
• Width가 증가할수록 성능이 올라가는 모습을 볼 수 있습니다.
• 정리하면 다음과 같습니다.
  1. widening은 여러 깊이의 residual network에서 성능을 일관되게 향상시킵니다.
  2. 깊이와 너비 둘다 증가시키는것은 파라미터의 수가 너무 많아지거나 강한 regularization이 필요해지기 전까지는 도움이 됩니다.
  3. 얇은 신경망과 동일한 수의 매개변수를 가진 넓은 신경망이 동일하거나 더 나은 성능을 낼 수 있기 때문에 residual network의 매우 깊은 깊이는 정규화 효과가 없는 것으로 보입니다. 더군다나, wide network는 얇은 네트워크보다 2배 이상의 많은 수의 매개변수를 사용하여 성공적으로 학습할 수 있습니다.

ResNeXt

• ResNet 논문의 저자들이 제안한 ResNet 을 발전시킨 형태인 *ResNext** 모델이 있습니다.
• 여기에서도 residual block 의 width를 늘리는 전략, 즉 conv layer의 filter의 갯수를 늘리는 방법 을 제안합니다.
• 독특한 점이 residual block 에서 여러 개의 병렬 pathway를 사용하는 구조 입니다.

• ResNext는 ResNet의 “Bottleneck” block을 병렬로 연결한 구조이며, 위 슬라이드의 오른쪽 구조와 같이 G개의 parallel pathway(block)으로 구성됩니다.
• 각 pathway에서 3x3 Conv layer의 연산을 위해 줄였다가 다시 증가시키는 채널의 수를 소문자 c라고 하면, 이러한 G개의 병렬 구조가 Bottleneck block과 같은 연산량을 갖게 하는 c의 값을 quadratic equation을 세우고 풀 수 있습니다.
  • 위 슬라이드의 아랫부분의 식이 quadratic equation이며, 아래의 Example은 다음과 같은 의미를 갖습니다.
    • Ex1) C=64, G=4라고 했을 때, c=24가 되어야 Bottleneck block과 같은 FLOPs를 갖습니다.
    • Ex2) C=64, G=32라고 했을 때, c=4가 되어야 Bottleneck block과 같은 FLOPs를 갖습니다.
  • 각 pathway에서 3x3 Conv layer의 연산을 위해 줄였다가 다시 증가시키는 채널의 수를 소문자 c라고 하고,
  • 각각의 pathway에서 FLOPs를 계산한 후, 모두 더하면 전체 FLOPs를 구할 수 있습니다.
• 이러한 방법은 네트워크 디자인을 수정하는 새로운 메커니즘을 제공합니다.
  • 연산량을 유지하는 채널의 수를 설정하는 것 대신에, 방정식을 풀어 pathway의 수 G를 설정할 수도 있습니다.

• ResNext에서는 단순히 병렬적으로 사용하는 것이 아니라 1 x 1 Conv에서 채널의 1/4로 축소하는 것이 아니라 ‘c’ 만큼 축소했는데 $9Gc^2 + 8GCc - 17C^2 = 0$ 이라는 Flops 수를 구하는 방정식으로 통해서 임의로 정한 C와 G를 이용했을 때, 기존의 bottleneck residual block과 동일한 연산이 수행되는 c를 구해 그 값으로 c를 정한다고 합니다.
• Grouped Convolution은 Group의 수만큼 GPU를 병렬적으로 사용하는데, 이때 채널을 GPU의 수만큼 분리해서 각 GPU별로 학습을 진행합니다.

• 위 사항들을 고려했을때 다음과 같이 표기할 수 있습니다.

• ResNext의 parallel pathway 구조를 이용하면, 연산량은 유지하면서 성능은 향상시킬 수 있습니다.
• 위 슬라이드는 (연산량은 유지하면서) Group의 수를 늘릴수록 성능이 좋아진다는 것을 보여줍니다.

Deep Networks with Stochastic Depth

• ResNet의 성능을 개선하고자 하는 방법은 계속되는데, Stochastic Depth 이라는 논문이 있습니다.
• 네트워크가 깊어지면 backpropagation 과정에서 gradient가 전달될 수록 점점 gradient가 작아지는 gradient vanishing 문제가 발생하곤했습니다.
• 이러한 문제를 해결하기 위해 train time 에 레이어의 일부를 dropout 하는 방법입니다.
  • 임의로 dropout 된 짧은 구조의 네트워크로 수월하게 학습을 하고 test time 에는 전체 네트워크를 이용해서 output을 내는 방법입니다.

FractalNet: Ultra-Deep Neural Networks without Residuals

• FractalNet 에서는 residual connection을 사용하지 않고 초기의 레이어(shallow)의 정보과 깊은 레이어(deep)의 정보를 모두 잘 전달하는 것이 중요하다는 관점에서 fractal 한 구조를 사용했습니다.
• 따라서 shallow layer의 정보와 deep layer의 정보를 모두 출력에 전달합니다.
• 또한 dropout 처럼 train time 에는 임의의 일부 경로의 정보를 사용해서 학습하고 test time 에 전체 경로를 이용하는 방법을 사용합니다.

DenseNet

• DenseNet 은 ResNet에서의 shortcut connection(skip connection)을 다른 방법으로 수행한 네트워크입니다.
  • ResNet에서는 Additive shortcut을 수행하였는데, DenseNet에서는 Concatenation shortcut을 사용 합니다.
  • 즉, 이전 layer의 feature를 Add하는 것 대신에 Concatenate하는 것입니다.
• 즉, 초기 input 이 모든 layer 에 동일하게 들어가고, 모든 레이어에서의 ouput 이 합쳐져(concat) 그 다음 conv layer의 input으로 들어가는 구조로 되어 있습니다.
• 논문의 저자들을 이러한 Dense block 이 gradient vanishing 문제를 완화할 수 있고 feature 들을 더 잘 전달하고 사용할 수 있게끔 한다고 주장합니다.

SqueezeNet

• SqueezeNet 은 효율성(efficient)를 중점적으로 하여 설계된 모델입니다.
• SqueezeNet에서 연산 효율을 올리기 위해 fire module 이라는 것을 사용했습니다.
• Fire module은 1×1 conv layer로 구성되어 있는 squeeze layer와 1×1 conv layer, 3×3 conv layer로 구성되어 있는 expand layer로 구성되어 있습니다.
• 이러한 fire module을 사용한 squeezeNet은 AlexNet 보다 50배 적은 파라미터를 가짐과 동시에 비슷한 성능을 보였습니다.
• squeezeNet을 더 압축하면 AlexNet 보다 500배 더 작아지게 된다고 합니다.

Main takeaways $ Summary

• 위 슬라이드는 이번 강의에서 배운 내용들을 요약한 것입니다.

해당 게시물은 Standford 2017 CS231n 강의와 2022년 슬라이드를 바탕으로 작성되었습니다.

해당 게시물은 이것이 코딩 테스트다 with 파이썬을 바탕으로 언제든지 블로그에 들어와서 보기위해 작성되었습니다.

구현(Implement)

코딩 테스트에서 구현(Implementation) 이란 “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정” 입니다.

• 흔히 알고리즘 대회에서 구현 유형의 문제란?
  • 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다.
• 구현 유형의 예시는 다음과 같습니다.
  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 실수 연산으 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는 문제)
  • 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 구현 파트의 대표적인 유형
  • 완전 탐색(Brute-Force) : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미
  • 시뮬레이션(Simulation) : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미

모든 알고리즘 문제에 적용되는 이야기지만, 특히 구현에서는 입력 변수의 표현 범위와 제한된 메모리, 제한된 채점시간을 주의 해야한다.

• 입력 변수의 표현 범위
  • 파이썬은 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다.
  • 하지만 다른 언어의 경우 int형을 벗어나는 경우 long long형 등 자료형을 고려해야 한다.
• 제한된 메모리
  • 보통의 문제의 경우 128MB를 제한으로 둡니다.
    • 데이터의 개수(리스트의 길이):1,000 = 메모리 사용량: 약 4KB
    • 데이터의 개수(리스트의 길이):1,000,000 = 메모리 사용량: 약 4MB
    • 데이터의 개수(리스트의 길이):10,000,000 = 메모리 사용량: 약 40KB
  • 즉, 128MB의 메모리 제한이 있는 곳에선 32,000,000개의 데이터까지 쓸 수 있다는 말이 됩니다.
• 제한된 채점시간
  • 보통의 문제의 경우 시간 제한은 1초로 지정됩니다.
  • 파이썬 3.7을 기준으로 1초에 2000만번(20,000,000)의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적입니다.
  • 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 합니다.
    • 실제로 N = 1,000,000일 때 NlogN은 약 20,000,000 입니다.

정리하면 알고리즘 문제를 풀 때, 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 합니다.

상하좌우

문제 정의

• 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1) 이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.
  • L: 왼쪽으로 한 칸 이동
  • R: 오른쪽으로 한 칸 이동
  • U : 위로 한 칸 이동
  • D: 아래로 한 칸 이동

이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서이다.

• 이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4) 라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1≤ N ≤ 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 < 이동 횟수 100)

출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

Test Case

[input]
5
R R R U D D

[output]
3 4

문제 해설

• 이 문제는 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 됩니다. 예를 들어 이동 횟수가 N번인 경우 시간복잡도는 O(N)입니다. 따라서 이 문제의 시간복잡도는 매우 넉넉한 편 입니다.
• 이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점 에서 시뮬레이션(Simulation) 유형으로 분류되며 구현이 중요한 대표적인 문제 유형입니다.

Solution

# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

시각

문제 정의

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
  • 00시 00분03초
  • 00시 13분 30초
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
  • 00시 02분 55초
  • 01시 27분 45초

입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 N ≤ 23)

출력 조건

• 0시 00분 00초부터 N시 59분 59초 까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

Test Case

[input]
5

[output]
11475

문제 해설

• 이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제입니다.
• 하루는 86,400초로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문입니다.
  • 즉 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있습니다.
• 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 됩니다.
• 이러한 유형은 완전 탐색(Brute-Force) 유형이라고 불립니다.
  • 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법 입니다.
  • 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간복잡도를 가지고 있으므로, 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절합니다.

Solution

# H를 입력받기
h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

왕실의 나이트

문제 정의

• 행복 왕국의 왕실 정원은 체스판과 같은 8 x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.
• 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
  1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
  2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

• 이처럼 8×8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 로 표현한다.

입력 조건

• 입력 조건 첫째 줄에 8×8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

Test Case

[input]
a1

[output]
2

My Solution

from sys import stdin

location = stdin.readline()
row = int(location[1])
col = int(ord(location[0])) - int(ord('a')) + 1

movable = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]

count = 0
for move in movable:
    move_row = row + move[0]
    move_col = col + move[1]
    
    if move_row < 1 or move_col < 1 or move_row > 8 or move_col > 8:
        continue
    
    count += 1

print(count)

Solution

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

• 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 됩니다. 다만, 8×8 좌표 평면을 벗어나지 않도록 꼼꼼하게 검사하는 과정이 필요합니다.
• 나이트의 이동 경로를 steps 변수에 넣는다면, 이 2가지 규칙에 따라 steps [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]로 값을 대입할 수 있습니다.
• 나이트의 현재 위치가 주어지면 현재 위치에서 이동 경로를 더한 다음, 8 × 8 좌표 평면에 있는지 확인하면 되는데, 이 과정은 반복문으로 처리할 수 있습니다.

게임 개발

문제 정의

• 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1×1크기의 정사각형으로 이뤄진 N×M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
• 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.
  1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터차례대로 갈 곳을 정한다.
  2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만수행하고 1단계로 돌아간다.
  3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로갈 수 없는 경우에는 움직임을 멈춘다.
• 현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다.매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력 조건

• 첫째 줄에 맵의 세로 크기 N과 가로크기 M을 공백으로 구분하여 입력한다. (3 ≤ N, M≤ 50)
• 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여주어진다. 방향 의 값으로는 다음과 같이 4가지가 존재한다.
  • 0: 북쪽
  • 1: 동쪽
  • 2: 남쪽
  • 3: 서쪽
• 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽순서대로 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
  • 0 : 육지
  • 1 : 바다
• 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력 조건

• 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

Test Case

[input]
4 4     # 4 by 4 맵 생성
1 1 0   # (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1 # 첫 출은 모두 바다
1 0 0 1 # 둘째 줄은 바다/육지/육지/바다
1 1 0 1 # 셋째 줄은 바다/바다/육지/바다
1 1 1 1 # 넷째 줄은 모두 바다

[output]
3

My Solution

from sys import stdin

n, m = map(int, stdin.readline().split())
x, y, d = map(int, stdin.readline().split())

map_init = [list(map(int, stdin.readline().split())) for _ in range(n)] # 초기화 지도 생성
visited = [[False] * m for _ in range(n)] # 방문한 곳 인식
visited[x][y] = True # 초기 위치는 1로 처리

movable_check = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 북, 동, 남, 서
move_count = 1 # 이동 횟수
turn_count = 0 # 회전 횟수

while True:
    # 왼쪽으로 회전
    d = 3 if d == 0 else d - 1

    mx = x + movable_check[d][0]
    my = y + movable_check[d][1]
    
    # 왼쪽회전 후 가보지도 않았고, 육지인 칸이 존재한다면
    if visited[mx][my] == False and map_init[mx][my] == 0:
        x, y = mx, my
        visited[mx][my] = True
        move_count += 1 # 이동 횟수
        turn_count = 0 # 회전 횟수
    else:
        turn_count += 1
    
    # 4개 방향으로 모두 갈 수 없다면 뒤로 이동(단, 바다면 안됨)
    if turn_count == 4:
        mx = x - movable_check[d][0]
        my = y - movable_check[d][1]
        
        if map_init[mx][my] == 0:
            x, y = mx, my
        else:
            break
        turn_count = 0
    
print(move_count)

Solution

# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보를 입력받기
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있다면 이동하기
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
            break
        turn_time = 0

# 정답 출력
print(count)