이 논문에서는 16개의 convolutional layer와 5개의 pooling layer가 있는 VGG-19 Network을 수정해 사용합니다.
Content Representation
2015년 Gatys의 논문에 따르면, content의 loss function은 아래의 식으로 표현됩니다. (아래 식들의 Notation은 원 논문의 것이 아니라 Luan의 논문을 따랐습니다.)
이 식에서 $I$는 input image, $O$는 output image, $F_{l}[I]$, $F_{l}[O]$는 각각 layer $l$의 filter 입력과 출력입니다.
Style Representation
한편, style 정보를 표현하기 위해 저자는 자신의 2015년 NIPS 논문 “Texture Synthesis Using Convolutional Neural Networks”을 인용해 Gram matrix라는 개념을 도입합니다. style (=texture) 정보를 얻는 Gram matrix $G_{l}$은 layer $l$에서 $i$번째 feature와 $j$번째 feature 간의 correlation을 계산한 것으로, 각 element는 단순한 vector inner product로 계산됩니다.
이에 따르면 style의 loss function은 아래의 식으로 표현됩니다. 아래 식에서 $S$는 style의 reference image입니다.
앞에서 설명한 알고리즘을 그림이 아니라 사진에 적용하면 다소 이상한 부분이 관찰됩니다. 아래 그림에서, 원래 사진에서 사각형이었을 건물의 창문들이 삐뚤빼뚤한 모양인 점과 하늘의 구름 부분인 좌측과 중앙 상단에 노랗게 창문 불빛이 투영된 점이 눈에 띕니다.
이 두 가지 문제를 해결하기 위해 이 논문에서는 두 가지 기법을 제안했습니다. 그 첫 번째는 Photorealism Regularization이라고 하고, 두 번째는 Augmented Style Loss with Semantic Segmentation이라고 합니다.
Photorealism Regularization
창문과 같은 부분의 찌그러짐을 줄이기 위해, Photorealism Regularization 기법에서는 image distortion에 penalty를 주는 loss function $\mathcal{L}_m$을 정의합니다.
이 부분에서는 Anat Levin의 “A Closed Form Solution to Natural Image Matting”이라는 논문의 image matting이라는 개념을 사용합니다. Image matting은 쉽게 말해, 아래 그림처럼 사진에서 foreground object를 뽑아내는 것을 의미합니다. 즉, foreground object를 정확히 뽑는다는 것은 입력 원본과 출력에서 해당 object의 경계 모양이 일치한다는 것과 같다는 뜻이므로, image matting에서 사용하는 cost function을 그대로 가져와서 image distortion을 줄이는데 이용하겠다는 것입니다.
이를 위해 Levin은 Matting Laplacian이라는 matrix $\mathcal{M}_I$를 정의했습니다. 다소 복잡하지만 Levin의 논문에서 소개한 식에 따라 input image $I$에서 $\mathcal{M}_I$를 계산하고, 이를 이용해 $\mathcal{L}_m$을 다음과 같이 정의합니다.
이 loss function $\mathcal{L}_m$을 위의 (4)식에 추가하는 것이 바로 Photorealism Regularization 기법입니다.
Augmented Style Loss with Semantic Segmentation
사진의 하늘 부분까지 창문 부분의 스타일이 적용되는 것을 ‘spillover’ 현상이라고 합니다. 이 문제를 없애려면 창문에는 창문, 하늘에는 하늘의 스타일을 적용하면 된다는 것이 이 논문의 접근법입니다.
이를 위해, 기존 “Champandard의 연구”, “Chen의 연구”에서처럼 semantic segmentation method를 적용해서 image를 ‘sky’, ‘building’, ‘water’ 등의 label 붙은 segment로 먼저 나눕니다. 그 다음, feature map에 각 segment에 해당하는 semantic segmentation mask를 씌워서 Gram matrix를 구합니다.
이에 따라 바뀐 style의 loss function 식 $\mathcal{L}_{s+}$는 아래와 같습니다.
이 식에서 $C$는 segment (channel)의 개수를 의미합니다.
Algorithm: Photorealism Regularization + Augmented Style Loss
이제 종합해 보겠습니다. 앞의 Gatys 논문의 loss function 식을 다시 쓰면 아래와 같습니다.
여기에 (5)식과 (6)식을 적용하면, 전체 loss function $\mathcal{L}_{total}$은 이제 아래 식과 같이 계산됩니다.
즉, 전체 loss function은 content loss + modified style loss + photorealism regularization이 됩니다.
이를 적용한 결과물은 아래 그림과 같습니다. 창문을 비롯해서 원본의 직선이 그대로 유지되고 있고, 하늘에 있던 노란 번짐도 없어졌습니다.
Neural Turing Machine을 한 마디로 정리하면, 외부의 메모리에 연결할 수 있는 neural network입니다. Neural network와 외부 메모리가 결합된 시스템은 Turing Machine과 일부 유사한 특징을 가집니다.
사실 컴퓨터공학을 전공해도 Turing Machine에 대해 깊게 알아볼 기회는 많지 않습니다. 네이버에서 튜링 머신 [Turing machine]을 찾아보면 다음과 같은 설명이 나옵니다.
1936년에 Turing이 고안한 추상적 계산 기계. 튜링 머신은 순서에 따라 계산이나 논리 조작을 행하는 장치로, 적절한 기억 장소와 알고리즘만 주어진다면 어떠한 계산이라도 가능함을 보여 주어 현대 컴퓨터의 원형을 제시하였다. – 튜링 머신 [Turing machine] (실험심리학용어사전, 2008., 시그마프레스㈜)
튜링 머신은 아래 그림과 같이 알고리즘(program)대로 현재 state와 tape에서 읽은 기호에 따라 다음 state를 결정하고, read/write head가 tape의 칸에 기호를 쓰고, read/write head를 좌우로 한 칸 움직이는 동작을 조합해서 실행합니다.
폰 노이만 아키텍처 (Von Neumann architecture)와 비교하자면, 튜링 머신은 기계를 사용해 수학적인 문제를 사람처럼 풀기 위한 이론적인 개념이고 폰 노이만 아키텍처는 튜링 머신의 개념을 바탕으로 실제 컴퓨터를 구현하기 위한 구조라고 할 수 있습니다.
Neural Turing Machine을 제안하는 이유가 뭘까요? 그것은 미분 가능한(differentiable) 컴퓨터를 만들 수 있기 때문입니다.
수학의 정석에도 나오듯이 미분 가능하려면 먼저 continuous해야 합니다. 그런데 Turing machine을 비롯해서 우리가 잘 알고 있는 디지털 컴퓨터는 기본 operation들이 discrete합니다. 즉, 0아니면 1, 여기 아니면 저기로 딱딱 끊어집니다.
예를 들어, 10이라는 값이 들어 있는 1000번지에서 읽으면 10이 그대로 읽힙니다. 999번지나 1001번지의 값에 영향을 받지 않습니다. 1000번지에 20이라는 값을 쓴다면 1000번지에만 20이 쓰여지지 999번지나 1001번지의 값이 그에 따라 달라지는 일은 없습니다. 뒤에서 다시 설명하겠지만 Neural Turing Machine은 이런 기본적인 operation들을 실수(real number) matrix 연산으로 바꿔 continuous하고 미분 가능하게 만듭니다.
미분 가능하면 뭐가 좋을까요? Gradient descent를 사용하는 다양한 최적화 알고리즘을 적용할 수 있습니다. 이 논문에서처럼 Neural network를 사용하면 back propagation으로 쉽게 training할 수 있다는 장점이 생깁니다. (아래 그림은 Daniel Shank의 슬라이드에서 일부 인용했습니다.)
Neural Turing Machine의 구조
먼저 가장 기초적인 Neural Network의 개념은, external input을 받아 external output을 만드는 아래 그림처럼 단순한 구조로 생각할 수 있습니다. 바로 다음에 설명할 RNN과 비교해 feedforward neural network이라고 부르기도 합니다. (아래 그림은 Kato Yuzuru의 슬라이드에서 일부 인용했습니다.)
여기서 발전된 RNN (Recurrent Neural Network)은 unit 자체의 출력을 다시 입력으로 받는 directed circle을 도입해서 일종의 internal memory 개념을 구현했습니다. 즉, RNN의 current state는 external input과 previous state로부터 결정이 됩니다.
반면, Neural Turing Machine은 external memory를 사용할 수 있는 구조입니다. 이 논문에서 controller라고 부르는 부분이 neural network입니다. Controller는 read head와 write head를 통해 memory에 읽고 쓸 수 있습니다. 여기서 ‘head’는 memory I/O operation을 추상화한 개념입니다. Turing machine에서 tape를 읽고 쓰는 부분의 용어를 그대로 사용해서 오히려 약간 혼란스럽게 느껴지기도 합니다.
Neural Turing Machine의 구현
아래 그림은 메모리에서 데이터를 읽고 쓰는 전체 구조를 한눈에 보입니다.
이 그림의 Read head라는 부분에서 실행하는 메모리 읽기 연산은 (1)식과 같습니다. 어느 번지 하나에서 바로 읽어오는 것이 아니라 $N$개의 번지에서 읽어 weight vector $w_t(i)$와 linear combination한 값을 읽어 옵니다. 즉 주변 값들의 영향을 받게 되는데 논문에서는 이를 ‘blurry’하다고 표현합니다. weight $w_t(i)$는 0과 1 사이의 값을 갖는 real number vector이며 계산 결과 읽는 값 $\mathbf{r}_t$도 real number vector가 됩니다.
Write head에서 실행되는 쓰기 연산은 (2), (3)식과 같이 삭제(erase) 후 덧셈(add)하는 2개의 식으로 구현됩니다. 마찬가지로 쓰기도 linear combination하면서 주변 값들의 영향을 받아 blurry한 특성을 가집니다. 중요한 것은 읽기, 쓰기가 모두 matrix 연산으로 구현되므로 미분 가능하다는 점입니다.
메모리의 주소를 계산하는 addressing mechanism을 아래 그림에 보입니다. 이 논문이 제안한 모델에서 메모리 주소를 계산하는 것은 weight vector $w_t(i)$를 결정하는 것과 같습니다.
이 논문에서 제시된 addressing 방법은 두 가지가 있습니다. 하나는 주어진 key vector 값과 유사한 정도를 계산해 찾는 content-based addressing이고, 다른 하나는 location에 따라 찾는 location-based addressing입니다.
전체 addressing mechanism은 4단계로 복잡하게 이뤄지는데 간략히 요점만 설명하면 다음과 같습니다.
Content Addressing: key vector $\mathbf{k}_t$ 와 비슷한 정도를 cosine similarity로 평가해서 content-based weight $\mathbf{w}_t^c$를 계산합니다.
Interpolation: 값과 이전 state $\mathbf{w}_{t-1}$의 값을 가중치 합산해서 $\mathbf{w}_t^g$를 구합니다.
Convolutional Shift: head 위치를 앞뒤로 shift하는 것을 convolution으로 계산해 $\tilde {\mathbf{w}}_t$를 얻습니다.
이 논문에서는 Copy, Repeat Copy, Associative recall, Dynamic N-Grams (N개의 이전 bit에서 다음 bit 예측), Priority Sort에 대해 실험했습니다. 비교 대상으로는 feedforward neural network controller의 NTM, RNN LSTM controller의 NTM, (NTM 아닌) RNN LSTM을 사용했습니다. 모든 실험의 학습에 RMSProp 알고리즘에 Momentum 0.9를 적용했고, 모든 LSTM은 3개의 hidden layer를 가지고 있습니다.
아래 그림은 Copy 실험의 결과입니다. 그래프에서 NTM을 적용한 2가지 경우가 LSTM만 단독 적용한 경우보다 훨씬 학습이 빠른 것을 볼 수 있습니다.
아래 그래프의 위쪽 2개의 row는 NTM에게 길이가 10, 20, 30, 50인 test 입력을 copy하도록 한 것입니다. 아래쪽 2개의 row는 길이가 120인 경우입니다. NTM에게 길이가 20인 copy를 train했음에도 오류가 매우 적은 것을 볼 수 있습니다.
반면, LSTM의 경우에는 길이 20까지는 오류가 거의 없지만 그 이상이 되면 급격히 오류가 많아지는 것을 관찰할 수 있습니다.
요약하면, NTM은 copy, sort와 같은 단순한 알고리즘을 매우 효율적으로 학습하고 training 범위를 벗어난 문제에 대해서도 높은 성능을 내는 것을 알 수 있습니다.
이 논문에서 풀려는 문제는 다차원 sensory input으로부터 직접 학습하는 reinforcement learning model을 만드는 것입니다. 쉽게 말해, 사람이 찾아낸 feature를 사용하는 것이 아니라 raw sensory data (이 논문에서는 video 데이터)에서 스스로 feature를 추출합니다.
기존의 reinforcement learning 이론에서, 어떤 policy $\pi$에 따라 현재 state $s$에서 action $a$를 취했을 때의 expected total reward를 action-value function $Q^\pi(s, a)$로 정의합니다.
이 식에서 $R_t$는 time $t$ 시점의 future discounted return으로 정의됩니다.
주어진 reinforcement learning 문제를 풀기 위해 이 Q 값을 최대화하는 optimal policy를 찾는 것이 Q-learning 알고리즘입니다. 즉, optimal action-value function $Q^*(s,a)$는 아래와 같습니다.
Optimal action-value function $Q^*(s,a)$는 Bellman equation에 의해 아래와 같이 recursive한 형태로 표현됩니다. Bellman equation은 제어 이론, 응용 수학, 경제학 이론에도 자주 등장하는 유명한 식입니다.
이 식의 의미는 다음과 같습니다. 현 시점에서 가능한 모든 action $a’$에 대해서, 그 action를 했을 때 미래에 예상되는 reward를 계산해 봅니다. 그러면 그 중에서 최대가 되는 경우의 $a’$을 찾을 수 있습니다. 그 때의 미래에 예상되는 reward 값인 에 future discount factor $\gamma$를 곱해서 현재의 reward $r$ 값과 더하면 optimal action-value function 값을 계산할 수 있다는 것입니다. 다르게 말하면, ${r + \gamma \max_{a’} Q^*(s’, a’)}$의 기대값을 최대화하는 action $a’$을 선택하는 것이 optimal policy라고 할 수 있습니다.
지금 이 연구에서 풀려는 Atari 2600 게임은 action에 대한 transition 확률과 reward가 명시적으로 주어지지 않는 model-free 문제입니다. 따라서 (3)식의 $Q^*(s,a)$를 table (Q-table)을 보고 산술적으로 계산할 수 없고, 대신 데이터에서 학습하여 prediction하는 접근 방법을 씁니다. 지금까지는 prediction에 supervised learning의 linear regression predictor 계열을 주로 사용해왔고, neural network을 사용했을 때에는 불안정해지거나 diverge하는 것으로 알려져 있었습니다.
이 논문의 가장 큰 contribution은 두 가지 아이디어로 Q-learning 알고리즘을 개선해서 neural network predictor 적용에 성공한 것입니다. 그 첫 번째는 experience replay이고, 두 번째는 target network의 사용입니다.
Experience replay는 인접한 학습 데이터 사이의 correlation으로 인한 비효율성을 극복하기 위한 기법입니다. 게임을 하는 agent의 경험 데이터 $(s,a,r,s’)$를 replay memory라는 이름의 buffer pool에 매 순간 저장해 뒀다가, update 할 때는 replay memory에서 random하게 minibatch 크기의 sample을 뽑아 계산하는 것입니다.
Target Network는 DQN과 똑같은 neural network을 하나 더 만들어, 그 weight 값이 가끔씩만 update 되도록 한 것입니다. $Q(s,a)$를 학습하는 순간, target 값도 따라 변하면서 학습 성능이 떨어지는 문제를 개선하기 위해서입니다. Target network의 weight 값들은 주기적으로 DQN의 값을 복사해 옵니다. Q-learning의 update에서 아래 식과 같은 loss function을 사용하는데, 먼저 나오는 $Q$는 target network에서 계산한 것이고 뒤의 $Q$는 원래의 DQN에서 계산한 것입니다.
이 연구에서 적용한 neural network은 3개의 convolutional layer와 2개의 fully-connected layer가 있는 구조입니다. Input state $s$는 이전의 $84 \times 84$ 크기의 프레임 4장이고, Output은 18개의 joystick/button 동작에 대한 $Q(s,a)$ 값, Reward는 score의 변경 값입니다.
지금까지 설명한 전체 DQN 알고리즘은 아래와 같습니다.
실험 결과
저자들은 이 논문에서 Atari 2600의 7가지 게임(Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest, Space Invaders)의 실험 결과를 보였습니다. 하지만 나중에 나온 2015년 Nature의 논문에서는 아래 그림과 같이 총 49개의 게임에 대한 결과를 보입니다. DQN은 다른 알고리즘보다 43개 게임에서 점수가 높았고, 29개 게임에서 human tester 점수의 75% 이상을 얻었다고 합니다.
하지만 논문을 읽지 않은 분들이라도 DeepMind에서 직접 올린 아래의 YouTube 영상은 다들 보신 적이 있을 겁니다. 600개의 에피소드를 학습한 다음, 벽 옆으로 터널을 만들어 공략하는 기술이 지금 봐도 놀랍습니다.
후속 연구
Q-learning 값을 update하는 식에서 max 연산자를 사용하기 때문에 DQN은 Q-value를 실제보다 높게 평가하고 그 결과 학습이 느려지는 경향이 있습니다. 이를 개선한 Double DQN이라는 알고리즘이 2015년에 역시 DeepMind에서 발표되었습니다.
또한, replay memory에서 uniform random sampling하는 DQN의 방식을 개선한 prioritized experience replay라는 기법이 제안되기도 했습니다. 이 방법은 더 중요한 experience를 더 자주 replay하도록 weight을 주어 효율적인 학습 효과를 보였습니다.
Jekyll 블로그에 올릴 포스트를 GitHub repository로 push하지 않고, 로컬에서 preview하며 작업할 수 있습니다. Jekyll 공식 페이지의 Basic Usage에 있는 내용 중에서 가장 필요한 부분만 여기서 정리해 보겠습니다.
먼저 jekyll serve 명령은 개발을 위한 웹 서버를 로컬에서 실행합니다. 기본으로 auto-regeneration 기능이 활성화 되어 있어, jekyll serve 실행 중에 data 파일(예를 들면 .md 또는 .html)에 변동이 있으면 실시간으로 _site 디렉토리의 파일들을 다시 생성합니다. 그 결과 http://localhost:4000/로 접속한 웹 브라우저에서 방금 수정한 내용을 바로 확인할 수 있습니다.
$ jekyll serve
# => A development server will run at http://localhost:4000/# Auto-regeneration: enabled. Use `--no-watch` to disable.
한 가지 알아둘 점은, _config.yml 파일은 수정해도 바로 반영되지 않습니다. 이 파일은 jekyll serve를 Ctrl-C를 입력해 종료하고 다시 실행해야 반영됩니다.
jekyll serve 명령은 실행하면 _site 디렉토리의 파일들을 전부 다시 생성합니다. 블로그의 규모가 작을 때는 문제가 되지 않지만, 커졌을 때는 생성에 걸리는 시간이 부담스러울 수 있습니다. 그럴 때는 --skip-initial-build라는 option을 사용하면 생성 과정을 생략하고 바로 웹 서버가 동작합니다.
$ jekyll serve --skip-initial-build
# => A development server will run at http://localhost:4000/# Skips the initial site build which occurs before the server is started.
이와 반대로, 로컬 웹 서버 기능이 필요없고 단순히 _site 디렉토리의 파일을 다시 생성하고 싶다면 jekyll build 명령을 실행하면 됩니다.
$ jekyll build
# => The current folder will be generated into ./_site
적용 방법은 위의 pull request에 잘 나와 있습니다. 간단히 정리하면 다음과 같습니다.
1. _data/tags.yml 추가 -- tag 저장소
2. tags.md 추가 -- tag 전체의 index page
3. _includes/tag_collector.html 추가 -- tag lists 생성
4. _includes/tag_link_formatter.html 추가 -- tag links 생성
5. _layouts/posts_by_tag.html 추가 -- 특정 tag가 있는 모든 포스트에 대한 page layout
6. _tools/createTag 추가 -- 새 tag 추가 명령어
7. index.html 및 _layouts/post.html 업데이트 -- 현재 post에 tag 표시
8. README.md 및 Introducing Lanyon 업데이트 (option)
이렇게 적용한 후에, 새로운 tag(예를 들어 GitHub Pages)를 등록하려면 command line에서 아래의 명령어를 입력합니다.
$ ./_tools/createTag "GitHub Pages"
그러면 아래와 같은 결과가 출력됩니다. 참고로 return되는 github-pages라는 string은 내가 등록한 “GitHub Pages”라는 tag의 slug이라고 부릅니다.
Begin using this tag by adding this line to your post's Front Matter:
---
tags: [github-pages]
---
새로운 tag를 등록하는 _tools/createTag 명령어를 사용하려면 먼저 시스템에 gawk (GNU awk)이 설치되어 있어야 합니다. Mac OSX 환경이라면 terminal에서 아래와 같이 2개의 명령어를 실행하면 gawk이 설치됩니다.
이후에 작성한 post에서 tag를 사용하려면 front matter 부분에 아래와 같은 형식으로 적으면 됩니다.
---
layout: post
title: Blogging Like a Hacker
tags: [github-pages]
---
<!--
your markdown or html starts here
-->
여러 개의 tag를 적용하려면 쉼표로 구분해서 적어줍니다.
---
layout: post
title: Blogging Like a Hacker
tags: [github-pages, jekyll]
---
<!--
your markdown or html starts here
-->
여기서 중요한 것은, front matter에 내가 쓰고 싶은 tag의 이름(“GitHub Pages”)을 적는 것이 아니라 그 tag의 slug (github-pages)을 적는다는 것입니다. 등록한 tag들의 이름과 slug 정보는 _data/tags.yml 라는 파일에 아래와 같이 간단한 형식으로 기록되어 있습니다.
