Deep Learning

AlphaGo : AlphaGo Pipeline 헤집기

Intro.

주위에서 온통 알파고(AlphaGo) 이야기만 들려온다. 글을 쓰기 시작한 3월 11일 현재 알파고는 이세돌 九단과의 경기를 두 경기 진행한 상태이다. 대결 시작 전 이세돌 구단이 5:0으로 무참히 이겨버릴 것이라는 여론과는 다르게 두 경기 모두 불계승으로 상대를 꺾은 알파고는 전 세계 모든 바둑인들을 경악시켰다. 앞으로 남은 경기들에 어떤 결과가 나올지는 모르지만, 현재까지 나온 결과만으로도 알파고는 인공지능 역사에 길이 새겨질 큰 족적을 남기고 있다.

알파고가 등장하기 전까지 바둑은 컴퓨터가 인간을 범접할 수 없는 유일한 아날로그 게임이라고 여겨졌다. 실제로 지금까지 개발되어온 바둑 AI들은 프로의 기력을 넘보기에는 실력의 차이가 너무나도 컸다. 그렇다면 알파고는 도대체 어떤 방법을 사용했기에 기존의 알고리즘과 엄청난 실력차를 보이고, 심지어 세계 정상급의 프로 기사까지 꺾을 정도의 실력을 갖출 수 있었을까?  알파고의 놀라운 실력을 파헤쳐보기 위해 이제부터 알파고라는 프로그램이 어떤 방식으로, 그리고 어떤 구조로 바둑이라는 게임에 접근했는지 – 그 과정을 세세하게 짚어보도록 할 것이다.

General AI Strategy

알파고 자체의 구조에 대해 말하기에 앞서, 1:1 대결 형식의 보드 게임 인공지능들이 대략적으로 어떤 방식을 통해 문제에 접근하는지부터 논의해보고자 한다.

우리가 만약 시간제한을 고려하지 않고, 무한대의 시간이 걸려도 좋으니 보드게임에 승리하는 인공지능을 만들어달라는 의뢰를 받았다고 해보자. 시간 제한이 없는 만큼 가장 이상적인 방법은 ‘현재 상태에서 가능한 행동들을 전부 고려하면서, 최대한 먼 수까지 바라보고 그 중 가장 이상적인 행동을 취하는 것’ 일 것이다. 문제는 바둑과 같은 1:1 대결 형식의 보드게임은 내가 어떤 행동을 취할 경우 상대방의 기회가 돌아가고, 상대방도 자신이 이득이 되는 행동을 한다는 것이다. 결국 내가 어떤 행동을 취했을 때 상대방이 어떤 행동을 할 것인지도 고려를 하면서 앞의 수를 바라보아야 한다.

 

Minimax.svg
Minimax Algorithm. 출처 : Wikipedia.

다음과 같은 행동트리를 살펴보자. 동그라미 친 부분이 내가 둘 차례이고, 네모를 친 부분이 상대가 둘 상태이다. 나와 상대가 할 수 있는 행동들을 전부 고려해보았을 때, 4수 뒤에 내가 얻을 수 있는 점수가 ‘4’ 층에 표시되어 있다. 이 점수중 내가 얻을 수 있는 가장 큰 점수는 +무한대 점수이고, 나는 이 점수를 얻을 수 있으면 정말 좋을 것이다. 그러나 당연히 합리적인 상대라면 내가 얻을 수 있는 점수를 최소화하는 방향으로 행동을 할 것이고, 따라서 +10, +무한대 중 더 작은 +10 점수를 얻게 만드는 행동을 할 것이다. 또한, 내 차례일 경우 나는 내 점수를 최대화하는 행동을 선택할 것이다. 이러한 생각을 가지고 4층부터 0층까지 올라가다 보면 결국 내가 취해야할 행동은 4층의 점수들중 가장 높은 점수인 +10이나 +무한대 등을 얻기 위한 왼쪽 길이 아니라, 상대의 행동까지 고려해보았을 때 가장 높은 점수인 ‘-7’ 을 얻기 위한 오른쪽 길을 선택해야한다는 것을 알 수 있다. 바둑과 같은 1:1 대전 게임에서 이러한 방식으로 행동을 하는 것은 가장 이상적인 행동 선택 방법으로 알려져 있으며, 상대방이 제공하는 최악의 수들 중 가장 최선의 수를 선택해야한다 는 의미에서 이를 minimax 알고리즘이라고 한다.

minimax 알고리즘이 가장 이상적인 행동 양식이라면, 우리의 의뢰를 해결하기 위해서는 최대한 많은 경우의 수를 고려하고, 그 중 minimax 알고리즘에 의해 가장 이상적인 행동을 취하는 프로그램을 만들면 된다! 우리의 의뢰는 해결되었다. 그러나 현실세계에서 이를 적용하기는 힘들다. 왜냐하면, 몇 수 앞을 내다보냐에 따라 고려해야할 상태의 가짓수가 기하급수적으로 늘어나기 때문이다. 예를 들어보자. 바둑의 경우 돌을 놓을 수 있는 칸의 갯수가 총 361개이다. 계산을 위해 수를 예쁘게 만들어서, 한 상태에서 행할 수 있는 행동이 대략 300개라고 해보자. 그렇게 할 경우, 상대방의 수까지 합해서 총 6수 앞까지 고려할 경우 고려해야할 총 가짓수는 300^6= 729000000000000 (729조 개) 이다. 애석하게도 컴퓨터의 연산 능력에는 한계가 있기 때문에, 이 정도로 많은 상태의 수를 다 고려하고 계산하기 위해서는 1초에 1억개의 상태를 계산한다고 해도 세 달 정도의 시간이 걸린다. 물론 이 가짓수는 몇 수 앞을 내다보냐에 따라 지수적으로 늘어나기 때문에, 체스나 바둑같은 거대한 보드게임에서 minimax 알고리즘만을 가지고 유의미한 능력의 인공지능을 만들기란 사실상 힘들다. 보통 프로 기사들은 50수 앞까지 내다보면서 대국을 한다고 하는데, minimax 알고리즘으로 50수 앞까지 내다본다면? 태양이 수명을 다해서 식을 때까지 계산해도 답을 못 낼 것이다.

결국 강력한 인공지능을 만들기 위해서는 이러한 탐색 공간을 효율적으로 탐색하면서 시간을 덜 사용함과 동시에 minimax 알고리즘에 가까운 성능을 내는 행동을 찾는 새로운 알고리즘이 필요하다. 이러한 방법을 찾기 위해 Alpha-beta Pruning, Principal variation search 등 다양한 방법들이 제시되었는데, 이제부터 소개할 방법은 그 중 보드게임 관련 인공지능에 가장 많이 사용된, 그리고 알파고가 기반으로 하고 있는 Monte Carlo Tree Search (MCTS) 라는 방법이다.

Monte Carlo Tree Search (MCTS)

몬테카를로 (Monte Carlo)라는 방식은 ‘확률적인 방식을 이용하여 문제를 해결하는 방법’ 들을 총칭하는 말이다. 이 방법에서는 실제로는 구하기 힘든 정교한 식이나, 실제로 다 보기 힘든 거대한 탐색 공간에 대해 직접적으로 접근하는 대신 ‘랜덤’ 을 이용해서 근사적으로 접근한다. 예를 들어 2 x 2 짜리 정사각형에 내접하는 반지름 1짜리 원을 그려넣고, 이 정사각형 안에 무작위로 점을 찍어서 원 안에 들어간 점의 수 / 전체 찍은 점의 수를 계산한다고 해보자. 점을 무진장 많이 찍다보면 그 값은 결국 π/4 의 값으로 수렴하게 될 것이다. 이것이 전형적인 몬테카를로 방법의 예시로, 몬테카를로를 이용하여 원주율의 값을 계산하는 방법이다.

Monte Carlo Tree Search (MCTS)는 앞서 말한 minimax에서의 행동 트리를 탐색하는 과정에서 몬테카를로 기법을 적용, 굳이 모든 상태에 대해 찾아보지 않고서도 좋은 행동을 선택할 수 있도록 설계된 알고리즘이다. MCTS가 어떤 방식으로 랜덤을 사용하여 트리를 구성해나가는지, 가장 기본적인 MCTS의 형태를 살펴보자.

Monte Carlo Tree Search Diagram. 출처 : Wikipedia.

MCTS의 기본적인 스텝은 총 4가지 단계로 이루어져 있다.

  1.  Selection : 루트로부터 시작하여 자식 중 가장 성공적인 자식을 택하는 방식으로 Leaf Node까지 이동한다. 일반적으로 한 쪽으로만 탐색이 몰리는 것을 방지하기 위해 여기에 랜덤하게 벗어날 여지를 주는 식으로 보정한다.
  2. Expansion : 리프 노드에 도달했는데 이 리프 노드가 게임을 끝내는 단계의 최종 노드가 아닐 경우, 다음 단계의 자식 노드를 생성하고 그 중 하나의 자식을 택하여 이동한다.
  3. Simulation : 현재 상태에서 랜덤하게 시뮬레이팅을 해서 게임을 진행해본다. 이를 playout이라고 하는데, 게임을 끝까지 진행해서 내가 이기는지, 지는지에 대한 결과값을 얻는다.
  4. Backpropagation : 현재 진행한 시뮬레이션의 결과를 바탕으로, 내가 온 경로들의 노드들에 결과값을 업데이트 해준다.

MCTS 에서는 이러한 step을 최대한 많이 반복하여 내가 택할 수 있는 행동들에 대해 각 행동이 어느 정도의 승률을 불러올까에 대한 정보를 시뮬레이팅 한다. 어느 정도 탐색을 하여 최종적으로 나의 행동을 선택해야 할 때는, 루트에서 할 수 있는 행동들 중 가장 많이 택하여 시뮬레이션을 해본 행동을 선택한다. 놀랍게도, 이러한 MCTS를 무한정 반복할 경우 결과값이 minimax의 결과로 수렴한다는 사실이 증명되어 있다. 그러나 일반적으로 기본적인 MCTS의 수렴 속도는 굉장히 느리기 때문에, 탐색 공간을 줄이고 효율적으로 결과를 찾아내기 위한 방법이 필요하다.

MCTS에서 수렴을 통해 얻고자 하는 최종적인 결과는 트리에 있는 각 노드 (게임의 상태) 에서 ‘내가 이길 확률이 얼마나 되는지’ 이다. 이에 대해, 현재 게임의 상태 s가 주어졌을 때 이 상태에서 내가 게임에서 이길 수 있는 확률의 정도를 계산하는 이론적인 함수 v*(s) 가 있다고 쳐보자. 물론 우리가 이러한 함수가 실제로 어떤 모양이고 어떻게 작동하는지는 알 수 없지만, 이런 함수의 존재를 가정해볼 수는 있다. MCTS를 무한정 진행할 경우, MCTS의 각 노드의 값들은 각 상태에서의 이론적인 승률 계산 함수값 v*(s) 의 값에 수렴하게 된다. 이를 역으로 접근해보면, v*(s)를 근사할 수 있는 함수 v(s)가 존재한다면 우리가 MCTS를 통해 얻고자 하는 결과를 먼저 근사적으로 얻을 수 있기 때문에 MCTS를 깊게 진행하지 않더라도 우리가 원하는 이상적인 행동을 계산할 수 있을 것이라는 생각을 할 수 있다. 또한, 이러한 함수를 조금 수정한다면 ‘현재 상태에서 어떤 행동을 하는 것이 더 좋을지’ 에 대한 값들도 얻어내어, MCTS 트리에서 가지치기를 할 때 더 효과적인 가지부터 칠 수 있게 하는 역할도 할 수 있을 것이다. 즉, 현재 게임의 상태 s로부터 내가 이길 수 있는 정도를 계산하는 함수 v(s)를 잘 만들어내는 것이 중요한 문제로 대두된다.

기존의 연구자들도 MCTS와 v(s)를 이용한 방법까지는 접근했고, 이를 이용하여 Pachi나 Fuego 등의 바둑 AI 들이 만들어졌다. 그러나 v(s)라는 함수 자체가 너무나도 만들기 어려운 함수이기 때문에, 기존의 연구들은 강력한 v(s) 함수를 만드는 데에 실패했고 결국 이러한 한계는 AI 성능의 약화로 이어질 수밖에 없었다. 그러나 이 시점에서 구글의 딥 마인드 팀은 v(s)를 만드는 데에 딥 러닝을 접목시켜 성능을 크게 향상시킨다.

Deep Learning : Introduction

딥 러닝은 ‘인공신경망’ 이라는 구조를 골자로 하고 있는 학습 알고리즘이다. 인공 신경망은 말 그대로 인간의 뇌에서 뉴런들이 연결되어 있는 신경들의 망을 수학적으로 간단히 모델링하여 모방한 구조를 말하는데, 대략적인 구조는 다음과 같다.

인공신경망. 출처 : Wikipedia.

그림에서 동그라미 쳐져있는 부분들은 각각 하나의 ‘노드’ (인간의 뉴런 하나를 모방한 것이다) 이며, 자신에게 들어오는 인풋값들을 바탕으로 값을 하나씩 계산해내고, 이 값을 다음 층의 노드들로 넘겨준다. 이것이 반복되며 마지막 층까지 값이 전달되고, 이 값이 내가 원하는 값이 되도록 인공 신경망을 학습시켜주어야 한다. 이 때 각각의 화살표에는 ‘weight’ 라고 해서, 시작 값에 얼마의 값을 곱해서 다음 노드에 넘겨줄 것인지에 대한 가중치가 있다. 인공 신경망을 학습한다는 것은 이러한 weight들을 조절하여, 신경망이 우리가 원하는 값들을 내놓도록 조정하는 것을 의미한다.

인공 신경망은 처음에는 아무런 정보도 가지고 있지 않기 때문에 처음 계산을 시키면 정말 의미없는 값들만 뱉어낼 것이다. 이를 학습시키기 위해서는 실제로 어떤 인풋이 주어졌을 때 어떤 아웃풋이 주어져야 한다, 라는 데이터들이 필요하다. 이 데이터의 인풋을 신경망에게 입력시켰을 때 뱉어내는 결과와 실제 결과를 비교하여 얼마나 차이나는지 계산을 하고, 이 차이에 대해 기울기(미분값)를 이용하여 각 weight들을 조금씩 움직이는 ‘gradient descent’ (기울기 강하) 방법을 이용하여 신경망을 학습시킨다. 수많은 데이터를 이용해 계속 weight를 움직여줄 경우 신경망은 결국 우리가 바라는 바를 학습할 수 있다.

이러한 인공 신경망 모델은 한 때 거대한 난항을 겪었는데, 그림에 나와있는 형태같은 3층의 신경망은 학습할 수 있지만 그보다 큰 신경망을 제대로 학습시킬 수가 없었던 것이다. 신경망은 노드의 수가 많고 층이 깊어질 수록 표현하고자 하는 함수를 보다 순조롭게 학습할 수가 있는데, 층을 깊게 늘릴 경우 weight를 조절하기 위한 기울기가 층을 거쳐오면서 사라졌고, 이에 따라 제대로 학습이 진행되지 않는 문제들 때문에 그 성능이 제한되었었다. 또한, 인공 신경망의 층 사이에서 값을 전달하기 위해서는 weight와 입력값을 곱해주기 위한 행렬연산이 필요하다. 그러나 노드의 수가 많아지면 이러한 행렬연산의 계산복잡도가 너무 높아져 빠르게 학습을 진행할 수가 없었다.
그러나 시간이 지나면서 이러한 학습 방법을 개선할 수 있는 방법들이 만들어지고, 병렬적인 계산을 통해 행렬 곱셉에 최적화된 GPU 분야의 개발이 가속화되면서 신경망의 크기와 깊이를 키울 수 있게 되었다. 이러한 거대한 신경망을 다루어서 문제를 해결하는 것이 결국 ‘딥 러닝’ 으로 불리는 분야로 떨어져 나온 것이다.

딥 러닝 분야가 발전하면서 기존의 단순한 계층 구조의 신경망 뿐만 아니라 여러 다양한 형태의 입력에 적용시킬 수 있는 새로운 신경망 구조들이 개발되었다. 그 중 하나가 알파고가 사용하고 있는 Convolutional Neural Network (CNN) 이다.

Convolutional Neural Network. 출처 : Wikipedia.

기존의 네트워크가 일차원의 벡터의 형태로 입력을 받던 것과 다르게, CNN에서는 보통 2차원의 형태로 입력이 주어진다. 예를 들어 30 x 30 크기의 이미지가 입력으로 주어진다고 해보자. 이러면 CNN의 ‘Convolution Layer’ 라는 층에서 이 이미지를 구석구석 살펴보면서 새로운 값을 만들어낸다. Convolution Layer에는 일정 크기의 ‘window’ 라는 것이 존재한다. 이 window가 3 x 3의 크기라고 해보면, convolution layer에서는 이미지에서 가능한 모든 3 x 3 크기의 작은 부분들을 살펴보면서 각각의 부분의 weight를 곱하여 새로운 값을 만들고, 이 값들이 모두 모여 새로운 28 x 28 크기의 아웃풋을 만들어낸다. 이러한 과정을 거쳐나가면서 CNN은 이미지에서 자신만의 기준으로 ‘특징’ 을 추출해 내는 방법을 학습하게 되고, 이러한 특징들을 가지고 마지막에 기존의 계층적 인공신경망과 유사한 층을 연결하여 원하는 결과를 내보내도록 학습을 하게 된다. CNN도 기존의 인공신경망과 마찬가지로, 입력값과 이에 따른 정답값이 있으면 유사한 방법으로 gradient descent를 적용하여 weight들을 학습해나갈 수 있다.

눈치가 빠른 독자라면 여기까지의 설명만으로도 CNN 구조가 알파고에 어떻게 적용되었는지 유추 할 수 있을 것이다. 바둑판의 경우 가로, 세로로 각각 19개의 줄이 있는 격자판 형태의 모습을 가지고 있다. 즉, ‘현재 바둑판의 상태를 19 x 19 크기의 이미지처럼 표시할 수 있는 것’ 이다. 알파고는 이 점을 이용하여, 바둑판의 상태를 이미지처럼 입력해주면 이 값을 CNN에 넣으면 원하는 값, 즉 현재 상태가 나에게 얼마나 유리한 상태인지, 그리고 현재 상태에서 돌을 어느 자리에 넣는지가 유리한 지 등을 계산하는 네트워크를 만들어서 학습하였다. 결국 알파고는 기존의 이론으로는 만들어내기 힘들었던 v(s)라는 함수를 딥 러닝 기법을 이용하여 매우 효과적으로 만들어낼 수 있었던 것이다. 이것이 기존의 바둑 AI와 알파고의 가장 큰 차이점이다.

AlphaGo Pipeline Structure

지금까지의 설명을 통해 알파고가 MCTS 기법, 그리고 딥 러닝을 이용해 학습한 상태 평가 함수 v(s)를 이용하여 효과적으로 상태-행동 트리를 탐색해나간다는 것을 알게 되었다. 그러나 실제 알파고 내부는 지금까지의 설명보다 훨씬 복잡한 방식으로 계산이 이루어지고 있으며, 신경망도 하나가 아니라 여러 개가 있어 각각을 보완하는 구조로 이루어져 있다. 실제 알파고 내부의 신경망들이 어떤 식으로 이루어져 있는지 먼저 대략적으로 살펴보자.

alphago networks.PNG
AlphaGo Network Structures. 출처 : [1]. (알파고 논문)
 먼저 알파고에는 ‘현재 상태에서 다음에 놓여질 돌의 위치를 예측하는’ (즉, 현재 상태에서 상대가 돌을 놓을 위치를 예측할 뿐만 아니라 내가 어디에 놓아야할 지도 예측할 수 있는) 네트워크가 있다. 논문에서는 이를 ‘policy network’ (정책망) 이라고 한다. 물론, CNN의 형태를 가지고 있다.

Policy network를 학습하기 위해 알파고는 먼저 방대한 량의 데이터가 필요했다. 앞서 살펴보았다 시피 CNN을 학습시키기 위해서는 ‘인풋 데이터’ 와 이에 대응하는 ‘해답’ 이 굉장히 많이 필요했는데, 이를 KGS라고 하는 바둑 사이트에 남아있는 기보들을 사용하였다. 이 기보들을 사용해서 총 3천만개 정도의 ‘돌 상태가 주어졌을 때, 다음에는 어디에 놓을지’ 에 대한 데이터가 확보되었고, 이를 이용하여 policy network를 학습하였다. 또한, 차후 MCTS에서 이용하기 위해 policy network보다는 부정확하지만 훨씬 빠르게 같은 문제를 계산할 수 있는 ‘Rollout policy’ 라는 네트워크도 준비하여 학습시켰다.

알파고는 이에 그치지 않고, 이 네트워크를 더욱 더 발전시켰다. 일반 사용자들이 둔 대전을 이용하여 학습한 네트워크의 성능은 그 사용자들의 수준을 크게 상회하기는 어려울 것이다. 이를 방지하기 위해, 알파고는 ‘과거의 자신과의 대결’ 을 통해 더욱 학습을 진행했다. 과거의 자신과 대결하여 대결에서 이겼을 경우 현재 사용하는 네트워크의 weight를 강화시키는 방향으로 나아가고, 졌을 경우 그 반대 방향으로 나아가는 방법을 이용하여 네트워크의 성능을 향상시켰다. 그 결과, 기존의 KGS 데이터만을 이용한 네트워크보다 더 높은 정확도를 가진 네트워크를 완성시킬 수 있었다. 이 네트워크를 이용하면, 위 그림의 오른쪽 <policy network> 그림처럼 바둑판에 돌에 놓여진 상태가 주어졌을 때 어떤 위치에 돌을 놓을 것인지 확률분포와 같은 형태로 결과값이 주어진다.

Policy network도 대단한 네트워크이다. MCTS를 이용하지 않고 policy network만을 이용하여 단순히 돌을 놓았을 때에도 기존의 바둑 AI들을 높은 승률로 이길 수 있었다. 그러나 네트워크만으로는 진정한 알파고를 구동시킬 수 없다. 앞서 살펴보았듯이 MCTS 탐색을 위해서는 현재 돌이 놓여있는 상태에서 플레이어가 이길 정도를 계산하는 v(s)가 필요하고, 이를 계산하는 네트워크를 ‘value network’ (가치망) 이라고 한다.

Value network의 경우 policy network와 유사한 CNN 구조를 가지고 있다. 그러나 policy network가 마지막에 모든 돌을 놓을 수 있는 자리에 대해 확률 분포를 계산하는 것과 달리, value network는 마지막에 인풋으로 주어진 상태 s에 대한 단순한 값 하나만을 내놓는다. 이 네트워크를 학습시키기 위해 알파고는 ‘자신과의 대결’ 에서 나온 기보 데이터들을 저장해 놓은 뒤, 이기는 상태와 지는 상태들을 모아 value network의 학습 데이터로 넣어주었고 성공적으로 학습을 마칠 수 있었다.

alphago MCTS.PNG
AlphaGo MCTS. 출처 : [1].
 알파고는 앞서 만든 Policy Network와 Rollout Policy, 그리고 Value Network를 사용하여 MCTS를 진행한다. 각각의 네트워크는 다음과 같은 방식으로 이용된다.

  • Policy Network : 본래 Selection 단계에서 MCTS는 가장 성공적인 자식 노드를 선택하는 방법을 사용한다. 그러나 알파고의 MCTS는 여기에 Policy Network에서 계산한 ‘현재 state에서 이 돌을 놓을 확률’ 에 대한 항을 더하여, 더 높은 확률을 가진 행동 쪽으로 더 많이 움직이게 하는 방식을 차용한다. 이것은 기존의 컴퓨터 알고리즘이 구현하지 못했던 인간만의 ‘직관’ 을 알파고가 나름대로의 방법으로 구현했다고 해석할 수도 있다. 또한 탐색이 너무 한쪽으로 몰리는 것을 방지하기 위해 한 행동을 너무 많이 방문하면 어느 정도의 패널티를 주어 다른 방향의 행동에 대해서도 탐색을 해보도록 장려하기도 한다.
  • Rollout Policy : Rollout policy는 policy network보다는 성능이 훨씬 낮지만, 훨씬 빠른 계산을 할 수 있다는 장점을 가지고 있다. 따라서, MCTS의 Evaluation 단계에서 시뮬레이션을 돌릴 때 이 rollout policy 네트워크를 사용하여 시뮬레이션을 진행한다.
  • Value Network : Value network는 마찬가지로 Evaluation 단계에서 사용된다. Evaluation 단계에서는 rollout policy와 value network를 이용한 점수를 둘다 구하고, 둘을 일정 비율로 더하여 이 state의 최종적인 점수를 계산한다. 논문에 의하면 Rollout policy와 value network 를 하나씩만 사용하는 것보다는 (Single Machine에서 각각 ELO Rating 2450, 2200 정도) 둘을 복합적으로 사용하여 점수를 더해주는 것이 훨씬 좋은 결과를 내었다 (ELO Rating 2900 정도).

Step의 과정 중 selection, expansion, evaluation의 과정을 마치면 선택한 state에 대해 evaluate 한 점수 V(s) 가 나온다. 이 점수를 이용하여 backup 과정에서 방문한 경로의 점수와 방문한 횟수를 업데이트 해주고, 일정 시간동안 갱신을 한 후 갱신이 끝나면 최종적으로 현재 선택할 수 있는 돌의 위치 중 MCTS 트리에서 가장 많이 방문한 돌을 선택하여 놓게 된다.

앞서 설명한 MCTS 트리를 갱신해나가는 과정은 다행히도 연산을 분산시켜서 진행할 수 있는 과정이다. 따라서 알파고는 마지막 발전으로 하나의 컴퓨터에서 계산을 진행하는 대신 여러 개의 CPU와 GPU로 연산을 분산시켜서 MCTS를 수행하였고, 그 결과 프로들도 이해할 수 없는 ‘신의 한 수’를 찾아내는 정도의 탐색 능력을 가진 인공지능이 되었다!

Closing

지금까지 알파고가 대략적으로 어떤 방식으로 좋은 수를 탐색하는지를 알아보았고, 이를 알아보기 위해 기초적인 부분부터 차근차근 살펴보았다. 알파고 내부의 각각의 layer가 정확하게 어떤 구조로 설계되었고, 어떤 방식으로 학습되었는지에 대한 자세한 한글 설명은 이 블로그를 확인하면 좋을 것 같다. 각각의 레이어의 구조와 목적 함수, 성능 등에 대한 설명이 자세하게 되어있다. 이 보다 더욱 자세한 설명을 원하시는 분들은 Nature에 실린 알파고 논문, [1] 을 한번 읽어보시면 좋을 것 같다. 자세한 실험 과정 및 학습 방법이 상세하게 서술되어 있다.

일각에서는 이미 알파고를 ‘AI가 인간을 지배할 대 인공지능 시대의 서막’ 정도로 서술하고 있다. 많은 사람들이 알파고가 인류 최강 바둑기사를 박살내는 모습에 인공지능에 거부감을 가지거나 공포를 느끼고, 심지어는 삶의 무력함을 느끼는 분들도 실제로 계신다고 들었다. 그러나 머신러닝과 인공지능은 다른 방면에서 보면 ‘인간이 할수 없는 일을 해냄으로써 인간의 생활을 극도로 발전시킬 수 있는’  존재이다. 미국 퀴즈 프로그램 Jeopardy에서 다른 쟁쟁한 경쟁자들을 제치고 우승한 슈퍼컴퓨터 ‘Watson’ 은 현재 의료분야에서 사용되어, 의사보다 훨씬 높은 정확도로 암을 진단하는 데에 쓰이고 있다. 보다 일생생활에 밀접한 예시를 들어보자면, 머신러닝을 이용한 수많은 자동운전 차량들이 활발하게 연구되고 있다. 이러한 자동운전 차량들은 인간의 삶을 윤택하게 해줄 뿐만 아니라, 높은 교통사고율까지 효과적으로 줄여줄 수 있는 것이다.

지피지기면 백전백승이라는 말이 있다. 인공지능과 머신러닝의 능력이 급등하고 있는 이 시점에서 단순히 감탄하거나 놀라워하기보다는 ‘이들이 어떤 방식을 차용하기에 기존에는 불가능할것만 같았던 일을 해내는지’, ‘어떻게 하면 이들을 다룸으로서 내가 직면한 문제를 해결할 수 있는지’에 대해 공부한다면 지금 불어오고 있는 머신 러닝의 바람에 올라타 더 높은 곳을 바라볼 수 있을 것이라고 믿는다.

References

[1] D. Silver et al. “Mastering the game of Go with deep neural networks and tree search.” Nature 529.7587 (2016): 484-489.

Advertisements
Deep Learning

word2vec 관련 이론 정리

예전에 포스팅한 Kaggle ‘What’s Cooking?’ 대회에서 word2vec 기술을 살짝 응용해서 사용해볼 기회가 있었다. 그 이후에도 word2vec이 쓰일만한 토픽들을 접하면서 이쪽에 대해 공부를 해보다가, 기존에 잘못 알고 있었던 부분들도 있고 더 알아가야 할 것들도 많아서 한번 내가 알고 있는 word2vec에 대한 내용들을 정리해서 포스팅해보려고 한다. 물론 나도 배워가는 입장이기에 아래에 쓰인 내용들이 많이 틀릴 수 있고, 글에 잘못된 내용들이 있다면 지적해서 알려주시면 감사하겠다.

# Word Embeddings as a Vector

NLP(Natural Language Processing, 자연어 처리)는 ‘컴퓨터가 인간이 사용하는 언어를 이해하고, 분석할 수 있게 하는 분야’ 를 총칭하는 말이다. 그러나 얼핏 생각했을 때 컴퓨터가 이를 이해할 수 있도록 변환하는 것은 참 어려운 일일 것이다. 컴퓨터에게 ‘사과’와 ‘초콜릿’ 이라는 두 단어를 보여준다고 컴퓨터가 두 단어의 개념적인 차이를 이해할 수 있을까? 컴퓨터는 단순히 두 단어를 유니코드의 집합으로만 생각할 것이다.

기본적으로 컴퓨터가 어떤 단어에 대해 인지할 수 있게 하기 위해서는 수치적인 방식으로 단어를 표현할 수 있어야 한다. 그러나 앞서 말했듯이, 수치화를 통해 단어의 개념적 차이를 나타내기가 근본적으로 힘들었다. 이 한계를 극복하기 전의 NLP는 ‘one-hot encoding’ 방식을 많이 사용했다. 예를 들어, 내가 어떤 단어들이 있는지에 대한 단어 n개짜리 ‘사전’ (Dictionary)이 있다고 해보자. 이 때, 어떤 단어를 표현하기 위해서 길이 n짜리 벡터를 하나 만들고, 그 단어가 해당되는 자리에 1을 넣고 나머지 자리들에는 0을 넣는 것이다.  사전이 [감자, 딸기, 사과, 수박] 이라면 사과를 표현하는 벡터는 [0, 0, 1, 0] 이 되는 식이다.
Naive Bayes를 이용한 스팸 분류기가 이 방법을 사용하는 전형적인 예시라고 생각할 수 있겠다. 단어 자체를 벡터화한 것은 아니지만, 이 경우 이메일 전체를 보면서 어떤 단어가 있으면 1, 없으면 0으로 나타내는 식으로 이메일 하나에 대한 벡터를 만든다. 이 방식은 당시에는 나름 좋은 성능을 내었고, 지금까지도 사용하는 사람들이 있지만 컴퓨터 자체가 ‘단어가 본질적으로 다른 단어와 어떤 차이점을 가지는 지 이해할 수가 없다’ 는 아주 큰 단점이 존재한다.

vector
Vector Representation을 통한 추론의 예시.

이러한 단점을 존재하기 위해 연구자들은 단어 자체가 가지는 의미 자체를 다차원 공간에서 ‘벡터화’ 하는 방식을 고안하게 되었다. 단어의 의미 자체를 벡터화할 수 있게 된다면, 기본적으로 이것을 사용해서 할 수 있는 일들이 굉장히 많아진다. 일단 단어들이 실수 공간에 흩어져있다고 생각할 수 있기 때문에 각 단어들 사이의 유사도를 측정할 수가 있고, 여러 개의 단어에 대해 다룰 때도 더해서 평균을 내는 등 수치적으로 쉽게 다룰 수가 있다. 또한 가장 좋은 점은 의미 자체가 벡터로 수치화되어 있기 때문에, 벡터 연산을 통해서 추론을 내릴 수가 있다는 점이다. 예를 들어, ‘한국’에 대한 벡터에서 ‘서울’에 대한 벡터를 빼고, ‘도쿄’ 에 대한 벡터를 넣는다면? 이 벡터 연산 결과를 통해 나온 새로운 벡터와 가장 가까운 단어를 찾으면, 놀랍게도 이 방식으로 ‘일본’ 이라는 결과를 얻을 수가 있다. 이것이 기존 방법과 가장 큰 차이점이자 장점이다.
이와 같은 추론에 대한 여러가지 실험들은 이 웹사이트 에서 해볼 수가 있다.  한국어 단어들에 대해 이러한 더하기, 빼기 연산을 해서 추론을 해볼 수 있다. 여기서는 나무위키와 한국어 위키백과를 이용해서 학습을 했다고 한다.

이제 방법은 알았다. 그렇다면, ‘어떻게 각 단어를 벡터화해야 하는가?’ 에 대한 문제가 관건이 될 것이다. 놀랍게도 이렇게 단어를 벡터화하는 방법 자체는 정말 예전부터 이루어져왔던 연구이다. 1980년대부터 관련 연구가 이루어져 왔는데, 2000년대에 와서 하나의 breakthrough라고 할 수 있는 ‘NNLM’ 방법이 만들어졌다. 이 NNLM 방법은 발전되어 ‘RNNLM’ 이라는 방법으로 발전되었고, 이것이 2013년 현재 ‘CBOW’와 ‘Skip-gram’ 이라는 아키텍쳐로 다시 한번 발전하여 현재 word2vec의 모양새로 이어지게 되었다. 이제, 이 방법들이 대충 어떤 방식으로 학습을 하는 것이고, 어떤 과정을 거쳐 현재 상태까지 도달하게 되었는지에 대해 서술할 것이다.
(앞서 언급한 방법들 외에도, ‘GloVe’ 라는 앞서 말한 방법들과는 다소 다른 방식으로 접근하는 새로운 연구가 있지만 이 글에서는 논하지 않겠다. 기본적으로 단어들 사이에 co-occurrence matrix X를 만든 후, 각 단어의 weight w_i, w_j의 내적이 log X_ij 와 최대한 유사해지게 만드는 weight 들을 구하는 방식이다. 더 자세히 알고 싶은 분은 이 페이지를 한번 읽어보시길 바란다.)

# How to Train Word Vectors?

일단 각각의 방법들에 대해 설명하기에 앞서, 단어의 벡터화를 학습하는 과정에서 가장 중요한 가정에 대해 언급하고 지나가야할 것 같다. 모든 Word Embedding 관련 학습들은 기본적으로 언어학의 ‘Distributional Hypothesis‘ 라는 가정에 입각하여 이루어진다.  이는, ‘비슷한 분포를 가진 단어들은 비슷한 의미를 가진다’ 라는 의미이다. 여기서 비슷한 분포를 가졌다는 것은 기본적으로 단어들이 같은 문맥에서 등장한다는 것을 의미한다. 예를 들어 앞서 작성한의 문단에서, 같은 문단에 ‘NNLM’과 ‘RNNLM’, ‘CBOW’, ‘Skip-gram’  이라는 단어가 함께 등장한다. 이 단어들이 같이 등장하는 일이 빈번하게 일어난다면, 이 단어들이 유사한 의미를 가진다는 것을 유추할 수 있지 않겠는가? 학습 데이터 수가 작으면 이러한 관계를 파악하기 힘들 수 있지만, 수많은 글들을 보면서 학습하다보면 이러한 단어들의 관계에 대해 파악할 수가 있을 것이다.
이러한 학습법들중 지금 설명하려는 방법들은 Neural Network를 이용한 학습방법들이다. 가장 먼저 등장한 아키텍쳐는 Feed-Forward Neural Net Language Model (NNLM) 이라는 모델이다.

– NNLM

NNLM
NNLM Structure

기본적으로 NNLM은 Input Layer, Projection Layer, Hidden Layer, Output Layer로 이루어진 Neural Network 이다. 일단, 현재 보고 있는 단어 이전의 단어들 N개를 one-hot encoding 으로 벡터화한다. 사전의 크기를 V라고 하고 Projection Layer의 크기를 P라고 했을 때, 각각의 벡터들은 VxP 크기의 Projection Matrix에 의해 다음 레이어로 넘어가게 된다. 그 다음부터는 우리가 알고 있는 기본적인 MLP 구조와 매우 유사하다. Projection Layer의 값을 인풋이라고 생각하고, 크기 H짜리 hidden layer를 거쳐서 output layer에서 ‘각 단어들이 나올 확률’을 계산한다. 이를 실제 단어의 one-hot encoding 벡터와 비교하서 에러를 계산하고, 이를 back-propagation 해서 네트워크의 weight들을 최적화해나가는 것이 기본적인 구조이다. 이 네트워크에서 최종적으로 사용하게 될 단어의 벡터들은 Projection Layer의 값들로서, 각 단어들은 크기 P의 벡터가 된다.

이 모델은 가장 초창기에 등장하여 단어의 벡터화라는 개념에 대한 새로운 지평을 열어주었다. 현재 존재하는 모든 Neural Network 기반 단어 학습 모델은 거의 모두 이 모델의 컨셉을 계승하여 발전시킨 모델이라고 할 수 있다. 그러나 초창기의 모델인 만큼 몇 가지 단점들이 존재한다. 일단,

  1. 몇 개의 단어를 볼 건지에 대한 파라미터 N이 고정되어 있고, 정해주어야 한다.
  2. 이전의 단어들에 대해서만 신경쓸 수 있고, 현재 보고 있는 단어 앞에 있는 단어들을 고려하지 못한다.
  3. 가장 치명적인 단점으로, 느리다.

이 모델이 하나의 단어를 처리하는 데에 얼마만큼의 계산복잡도를 요구하는지 생각해보자. 일단

  • 단어들을 Projection 시키는 데에 NxP
  • Projection Layer에서 Hidden Layer로 넘어가는 데에 NxPxH
  • Hidden Layer에서 Output Layer로 넘어가려면 모든 단어에 대한 확률을 계산해야 하므로 HxV

즉, NxP + NxPxH + HxV 만큼의 시간이 걸린다. 보통 사전은 가능한 모든 단어들을 가지고 있어야 하므로, 그 크기가 굉장히 크다 (최대 천만개 정도). 즉, 이 경우 Dominating Term은 HxV가 될 것이다. 보통 N=10, P=500, H=500 정도의 값을 사용한다고 생각하면, 하나의 단어를 계산하는 데에 O(HxV) = O(50억) 정도의 계산이 필요한 것이니 학습 시간이 정말 느릴것이다. 이를 개선하기 위해 이후 설명할 방법을 이용하면 HxV 항을 Hx ln(V) 정도로 줄일 수 있다. 이를 고려하면 Dominating Term은 NxPxH가 될 것이고, 그래도 계산량은 O(NxPxH) = O(250만) 정도로 많은 시간이 소요된다.

– RNNLM

RNNLM
RNNLM Structure

RNNLM은 기본적으로 NNLM을 Recurrent Neural Network의 형태로 변형한 것이다. 이 네트워크는 기본적으로 Projection Layer 없이 Input, Hidden, Output Layer로만 구성되는 대신, Hidden Layer에 Recurrent한 연결이 있어 이전 시간의 Hidden Layer의 입력이 다시 입력되는 형식으로 구성되어 있다. 이 네트워크의 경우 그림에서 U라고 나타나 있는 부분이 Word Embedding으로 사용이 되며, Hidden Layer의 크기를 H라고 할 때 각 단어는 길이 H의 벡터로 표현될 것이다.

RNNLM의 경우 NNLM과는 달리 몇 개의 단어인지에 대해 정해줄 필요가 없이, 단순하게 학습시켜줄 글의 단어를 순차적으로 입력해주는 방식으로 학습을 진행하면 된다. 학습을 진행하면서 Recurrent한 부분이 일종의 Short-Term 메모리 역할을 하면서 이전 단어들을 보는 효과를 낼 것이다. 또한, RNNLM은 NNLM보다 연산량이 적기도 하다. 이 모델이 한 단어를 처리하는 데에 필요로 하는 연산량을 생각해보면

  • Input Layer에서 Hidden Layer로 넘어가는 데에 H
  • hidden(t-1)에서 hidden(t)로 넘어가는 벡터를 계산하는 데에 HxH
  • Hidden Layer에서 Output 결과를 내기 위해 모든 단어에 대해 확률계산을 해야하므로 HxV

로, H를 무시하면 O(HxH + HxV) 이다. 일반적인 경우라면 HxV가 Dominating Term이 되겠지만, 앞서 말했듯이 이는 Hx lnV로 줄일 수 있는 테크닉이 존재한다. 따라서 이 모델은 한 단어를 진행하는 데에 O(HxH)의 계산량을 필요로 한다. H를 아까와 같이 500으로 잡는다면 O(25만)의 연산량이다. RNNLM에 비해 대략 1/N배로 줄어들어 계산이 빨라졌다.

NNLM과 RNNLM 모두 단어 벡터화 학습을 하기에 좋은 방법이다. 그러나 문제는 자연어 처리 분야의 특성상 굉장히 많은 데이타를 넣어서 학습시켜줘야 각 단어에 대한 정확한 표현법을 학습할 수 있을 것이라는 것이다. 따라서 성능도 성능이지만 학습을 빠르게 할 수 있는 방법이 필요하게 되었고, 이 문제를 해결하며 이 분야의 state-of-the-art로 떠오른 방법이 바로 word2vec이다.

# Word2Vec

word2vec은 2013년 구글에서 발표된 연구로, Tomas Mikolov라는 사람을 필두로 여러 연구자들이 모여서 만든 Continuous Word Embedding 학습 모형이다. 재밌는 점은, 이 논문을 집필한 사람 중 Jeffery Dean (구글의 전설적인 프로그래머로 MapReduce등을 만듬) 도 있다는 점이다. 이 모델이 기존 Neural Net 기반 학습방법에 비해 크게 달라진 것은 아니지만, 계산량을 엄청나게 줄여서 기존의 방법에 비해 몇 배 이상 빠른 학습을 가능케 하여 현재 가장 많은 이들이 사용하는 Word Embedding 모델이 되었다.

기존 연구들과 달리, 이 연구에서는 학습을 시키기 위한 네트워크 모델을 두 가지 제시하였다. 한 가지는 CBOW(Continuous Bag-of-Words) 모델이고, 다른 하나는 Skip-gram 모델이다.

CBOW
CBOW Architecture

CBOW 모델의 경우 다음과 같은 방식을 채용하고 있하고 생각할 수 있을 것 같다. “집 앞 편의점에서 아이스크림을 사 먹었는데, ___ 시려서 너무 먹기가 힘들었다.” 라는 문장에서, 사람들은 ___ 부분에 들어갈 단어가 정확하게 주어지지 않아도 앞 뒤의 단어들을 통해 ‘이가’ 라는 말이 들어갈 것을 추측할 수 있다. CBOW 모델도 마찬가지의 방법을 사용한다. 주어진 단어에 대해 앞 뒤로 C/2개 씩 총 C개의 단어를 Input으로 사용하여, 주어진 단어를 맞추기 위한 네트워크를 만든다.

CBOW 모델은 크게 Input Layer, Projection Layer, Output Layer로 이루어져 있다. 그림에는 중간 레이어가 Hidden Layer라고 표시되어 있기는 하지만, Input에서 중간 레이어로 가는 과정이 weight를 곱해주는 것이라기 보다는 단순히 Projection하는 과정에 가까우므로 Projection Layer라는 이름이 더 적절할 것 같다. Input Layer에서 Projection Layer로 갈 때는 모든 단어들이 공통적으로 사용하는 VxN 크기의 Projection Matrix W가 있고 (N은 Projection Layer의 길이 = 사용할 벡터의 길이), Projection Layer에서 Output Layer로 갈 때는 NxV 크기의 Weight Matrix W’ 가 있다.  (주의해야할 점은, 두 행렬은 별개의 행렬이라는 점이다. 예전 What’s Cooking 대회를 할 때는 이 W’ 가 W의 transpose라고 생각하고 구현했었다. 당시에 어떻게든 봐줄만한 결과가 나왔던 것이 신기하다..) Input에서는 NNLM 모델과 똑같이 단어를 one-hot encoding으로 넣어주고, 여러 개의 단어를 각각 projection 시킨 후 그 벡터들의 평균을 구해서 Projection Layer에 보낸다. 그 뒤는 여기에 Weight Matrix를 곱해서 Output Layer로 보내고 softmax 계산을 한 후, 이 결과를 진짜 단어의 one-hot encoding과 비교하여 에러를 계산한다.

CBOW 모델에서 하나의 단어를 처리하는 데에 드는 계산량은 다음과 같다.

  •  C개의 단어를 Projection 하는 데에 C x N
  • Projection Layer에서 Output Layer로 가는 데에 N x V

따라서 전체 계산량은 CxN + NxV가 되는데, 앞서 말한 V를 ln V로 줄이는 테크닉을 사용하면 전체 계산량이 CxN + N x lnV가 된다. 이 식을 잘 보면, 이 모델이 앞서 다른 모델들에 비해 왜 계산이 빠른지 알 수 있다. CBOW 모델에서 보통 C는 10 내외의 크기로 잡으므로, 전체 계산량은 결국 Projection Layer의 크기 N과 log-사전크기의 lnV의 크기의 곱에 비례하게 된다. 즉, C=10, N=500, V=1,000,000으로 잡아도 500 x (10+ln(1,000,000)) = 약 10000의 계산량밖에 들지 않는 것이다. 이는 앞서 확인한 NNLM이나 RNNLM에 비해 정말 엄청나게 줄어든 계산량이라는 것을 확인할 수 있다.

skip-gram
Skip-gram Architecture

다른 하나의 모델인 Skip-gram 모델은 CBOW와는 반대 방향의 모델이라고 생각할 수 있을 것 같다. 현재 주어진 단어 하나를 가지고 주위에 등장하는 나머지 몇 가지의 단어들의 등장 여부를 유추하는 것이다. 이 때 예측하는 단어들의 경우 현재 단어 주위에서 샘플링하는데, ‘가까이 위치해있는 단어일 수록 현재 단어와 관련이 더 많은 단어일 것이다’ 라는 생각을 적용하기 위해 멀리 떨어져있는 단어일수록 낮은 확률로 택하는 방법을 사용한다. 나머지 구조는 CBOW와 방향만 반대일 뿐 굉장히 유사하다.

Skip-gram 모델에서 하나의 단어를 처리하는 데에 드는 계산량은 다음과 같다. C개의 단어를 샘플링했다고 할 때,

  • 현재 단어를 Projection 하는 데에 N
  • Output을 계산하는 데에 N x V, 테크닉을 사용하면 N x ln V
  • 총 C개의 단어에 대해 진행해야 하므로 총 C배

로 총 C(N + N x lnV) 만큼의 연산이 필요하다. 즉 이 모델도 CBOW 모델같이 N x lnV에 비례하는 계산량을 가진 모델이기는 하지만, 몇 개의 단어를 샘플링하냐에 따라서 계산량이 그것에 비례하여 올라가게 되므로 CBOW 모델에 비해서는 학습이 느릴것이다.

CBOW 모델과 Skip-gram 모델을 비교하면 CBOW의 모델이 조금 더 논리적이라고 개인적으로 생각하지만, 실제 실험 결과에서는 Skip-gram이 CBOW에 비해 전체적으로 다소 좋은 결과를 내는 추세를 보인다. 현재는 대부분의 사람들이 Skip-gram 모델을 사용하는 것 같다.

# V to ln(V) : Complexity Reduction

앞서 말한 기본적인 CBOW와 Skip-gram 모델을 그대로 구현해서 돌릴 경우 생각보다 학습이 오래 걸리는 것을 확인할 수 있을 것이다. 이는 앞서 말한 V에 관련된 항 때문이다. 영어 단어의 총 개수는 백만개가 넘는다고 한다. 그런데 네트워크의 Output Layer에서 Softmax 계산을 하기 위해서는 각 단어에 대해 전부 계산을 해서 normalization을 해주어야 하고, 이에 따라 추가적인 연산이 엄청나게 늘어나서 대부분의 연산을 이 부분에 쏟아야 한다. 이를 방지하기 위해서 이 부분의 계산량을 줄이는 방법들이 개발되었는데, Hierarchical Softmax와 Negative Sampling이 그 방법들이다.

– Hierarchical Softmax

Hierarchical Softmax는 계산량이 많은 Softmax function 대신 보다 빠르게 계산가능한 multinomial distribution function을 사용하는 테크닉이다. 이 방법에서는 각 단어들을 leaves로 가지는 binary tree를 하나 만들어놓은 다음(complete 할 필요는 없지만, full 할 필요는 있을 것 같다), 해당하는 단어의 확률을 계산할 때 root에서부터 해당 leaf로 가는 path에 따라서 확률을 곱해나가는 식으로 해당 단어가 나올 최종적인 확률을 계산한다.

HSexample
Example Binary Tree for Hierarchical Softmax
HSequation
Probability Equation for Hierarchical Softmax

설명하기 전 이 방법에서 사용하는 notation들을 살펴보자.

  • L(w)는 w라는 leaf에 도달하기 까지의 path의 길이를 의미한다.
  • n(w, i) 는 root에서부터 w라는 leaf에 도달하는 path에서 만나는 i번째 노드를 의미한다. n(w, 1)은 루트가 될 것이고, n(w, L(w)) 는 w가 될 것이다.
  • ch(node) 는 node의 고정된 임의의 한 자식을 의미하며, 여기서는 단순하게 node의 왼쪽 자식이라고 생각하겠다. 이렇게 생각해도 무방하다.
  • [[x]] 는 x가 true일 경우 1, false일 경우 -1을 반환하는 함수로 정의한다.
  • Hierarchial Softmax를 사용할 경우 기존 CBOW나 Skip-gram에 있던 W’ matrix를 사용하지 않게 된다. 대신, V-1개의 internal node가 각각 길이 N짜리 weight vector를 가지게 된다. 이를 v’_i 라고 하고 학습에서 update 해준다.
  • h는 hidden layer의 값 벡터이다.
  • sigma(x)는 sigmoid function 1/(1+exp(-x)) 이다.

이렇게 정의하고 위의 식과 같은 방법으로 p(w)를 계산한다고 해보자. 이 경우 각 스텝마다 길이 N짜리 벡터 두 개의 내적이 일어나므로 계산량 N이 필요하며, binary tree를 잘 만들었을 경우 평균적으로 루트로부터 leaf까지의 거리는 평균 O(lnV)일 것이므로 총 N x lnV의 계산량만으로 특정 단어가 나올 확률을 계산할 수 있다. 네트워크의 Error Function을 Categorical Cross-entropy 로 사용할 경우 최종 Error를 계산하기 위해서 해당하는 단어에 대해서만 확률을 계산하면 되므로, 다른 추가적인 연산 없이 O(N x lnV)의 계산량만으로 계산이 끝난다.

또한 특정 hidden layer 값에 대해 모든 단어들의 확률을 더한 sigma p(w_i | hidden layer) 를 생각해보자. Full binary tree를 산정하고 v_node와 h의 내적 값을 x라고 생각할 경우,

  • 특정 node에서 왼쪽 자식으로 갈 때의 확률 = sigmoid(x)
  • 특정 node에서 오른쪽 자식으로 갈 때의 확률 = sigmoid(-x) = 1-sigmoid(x)

따라서 특정 노드에서 왼쪽, 오른쪽 자식으로 갈 확률을 더하면 1이 된다. 이를 이용하면, sigma p(w_i | hidden layer) 값이 1이라는 것을 쉽게 보일 수 있을 것이다. Softmax function의 계산이 오래 걸렸던 것은 확률 계산을 위해 모든 결과에 대한 합을 1로 만들어주기 위함이었다. 이 과정에서 최종적으로 나온 output값에 대해 일일히 계산을 해주어서 전체 합으로 normalize를 해주었기 때문에 V 만큼의 계산이 더 필요했던 것인데, 이 Hierarchical Softmax를 사용하면 전체 확률에 대한 계산 없이 전체 합을 1로 만들어 줄 수 있어 좋은 multinomial distribution function으로 사용할 수 있게 되는 것이다.

word2vec 논문에서는 이러한 Binary Tree로 Binary Huffman Tree를 사용했다고 한다. Huffman Tree를 사용할 경우 자주 등장하는 단어들은 보다 짧은 path로 도달할 수 있기 때문에 전체적인 계산량이 더 낮아지는 효과를 볼 수 있을 것이다. 또한 Huffman Tree는 Full Binary Tree이기 때문에 Hierarchical Softmax의 조건에도 부합한다.

– Negative Sampling

Negative Sampling은 Hierarchial Softmax의 대체재로 사용할 수 있는 방법이다. 전체적인 아이디어는 ‘Softmax에서 너무 많은 단어들에 대해 계산을 해야하니, 여기서 몇 개만 샘플링해서 계산하면 안될까?’ 라는 생각에서 시작된다. 전체 단어들에 대해 계산을 하는 대신, 그 중에서 일부만 뽑아서 softmax 계산을 하고 normalization을 해주는 것이다. 즉, 계산량은 N x V에서 N x K (K = 뽑는 샘플의 갯수)로 줄어들 것이다. 이 때 실제 target으로 사용하는 단어의 경우 반드시 계산을 해야하므로 이를 ‘positive sample’ 이라고 부르고, 나머지 ‘negative sample’ 들을 어떻게 뽑느냐가 문제가 된다. 이 뽑는 방법을 어떻게 결정하느냐에 따라 Negative sampling의 성능도 달라지고, 이는 보통 실험적으로 결정한다.

그런데 word2vec의 경우 기존과는 다른 새로운 Error Function을 정의해서 사용한다. 그들은

NSequation.PNG

다음과 같은 목표를 maximize 하도록 weight을 조정한다. 이 때 좌측 항은 positive sample에 대한 항이고, 우측은 뽑은 negative sample들에 대한 항이다. 왜 이러한 objective function을 사용하게 되었는지는 논문 [5]에 자세하게 설명되어 있다. 기본적으로 보고있는 단어 w와 목표로 하는 단어 c를 뽑아서 (w,c)로 둔 후, positive sample의 경우 ‘이 (w,c) 조합이 이 corpus에 있을 확률’ 을 정의하고, negative sample의 경우 ‘이 (w,c) 조합이 이 corpus에 없을 확률’을 정의하여 각각을 더하고 log를 취해서 정리하면 위과 같은 형태의 식이 나온다. 자세한 수리적 전개 과정을 보고싶은 분들은 논문 [5]를 참조하시면 되겠다.

보통 Negative Sampling에서 샘플들을 뽑는 것은 ‘Noise Distribution’ 을 정의하고 그 분포를 이용하여 단어들을 일정 갯수 뽑아서 사용하는데, 논문에서는 여러 분포를 실험적으로 사용해본 결과 ‘Unigram Distribution의 3/4 승’ (여기서 Unigram Distribution은 단어가 등장하는 비율에 비례하게 확률을 설정하는 분포라고 할 수 있다. 이 경우 각 확률을 3/4승 해준 후, Normalization factor로 나누어서 단어가 등장할 확률로 사용한 것이다) 을 이용한 분포를 이용해서 실험한 결과 unigram, uniform 등 다른 분포들보다 훨씬 좋은 결과를 얻을 수 있었다고 한다.

– Further Method : Subsampling Frequent Words

Hierarchical Softmax와 Negative Sampling은 모델 자체의 계산복잡도를 줄이기 위한 테크닉이었다. 여기서 추가적인 방법으로, 논문에서는 ‘the’, ‘a’, ‘in’ 등 자주 등장하는 단어들을 확률적으로 제외하여 학습 속도를 향상시켰을 뿐만 아니라 성능까지 향상시켰다. 단어 w의 등장 빈도를 f(w)라고 할 때, 학습할 때 각 단어는

subsamplingequatoin.PNG

의 확률로 제외된다. 이 때 t는 빈도가 일정값 이상일 때만 제외하겠다는 느낌의 threshold 값인데, 논문에서는 10^-5 의 값을 사용했을 때 가장 좋은 결과를 얻을 수 있었다고 한다.

# Performance Comparison

이 파트는 여러 단어의 벡터화 학습법에 대한 실험적인 성능 비교를 다루는 부분이다. 이 때 성능을 측정하기 위해 사용한 실험은 ‘Analogy Reasoning Task’ 이다.

Analog.PNG
Example Word Pairs for Analogy Reasoning Task

Analogy Reasoning Task는 어떤 단어의 Pair, 예를 들어 (Athens, Greece) 라는 Pair가 주어졌을 때, 다른 단어 Oslo를 주면 이 관계에 상응하는 다른 단어를 제시하는 방식의 시험이다. 이러한 ‘관계’ 에는 수도, 화폐, 주와 도시 등 내용에 관련된 ‘semantic’ 한 관계가 5개 있으며, 문법에 관련된 ‘syntactic’ 한 관계가 9개 있다.
만약 지금까지 설명한 방법들로 각 단어의 벡터를 잘 학습했다고 할 경우 이 문제의 답을 추론하는 것은 간단할 것이다. 예를 들면, vector(Greece) – vector(Athens) + vector(Oslo)를 하고 이 벡터에 가장 가까운 벡터를 찾으면 Norway가 나올 것이라고 기대할 수 있을 것이다.

 

AWR1.PNG
Analogy Reasoning Task Results for Various Models. Word Dimension = 640

위는 단어 벡터 길이를 640으로 하고 다양한 모델을 이용하여 학습시켰을 때의 결과이다. 보다시피 RNNLM과 NNLM에 비해 CBOW와 Skip-gram이 Semantic, Syntactic 문제에 대해 훨씬 더 좋은 결과를 내는 것을 알 수 있다. 또한 두 모델을 비교해보면 Skip-gram이 Syntactic 문제의 정확도는 조금 떨어지기는 하지만, Semantic 문제에 대해서는 훨씬 높은 정확도를 보였다.

AWR2
Analogy Reasoning Task Results for Various Methods. Word Dimension = 300

위 표는 모델을 300차원 Skip-gram으로 고정한 후 실험한 결과이다. NEG-k는 k개 단어를 선택한 negative sampling이고, HS-Huffman은 Huffman Tree를 이용한 Hierarchical Softmax이다. (NCE-k는 negative sampling과 유사한 방법으로, Noise Contrastive Estimation이라고 하는 방법이다. 논문에서는 이 방법을 기초로 하여 목적 함수를 조금 바꾸어서 Negative Sampling을 만든 것이다.) 실험 결과 전체적으로 Hierarchical Softmax를 사용한 것 보다 Negative Sampling을 사용했을 때 더 결과가 좋은 것을 발견할 수 있다. 또한, 자주 등장하는 단어를 subsampling 했을 때 학습 시간이 눈에 띄게 줄어든 것 뿐만 아니라 성능까지 어느정도 향상되었다.
단, 이 표에서 Hierarchical Softmax의 성능이 낮았다고 실제 이 방법이 나쁜 방법인 것은 아니다. 이 실험 말고도 Phrase에 대해 비슷한 Task를 만들어서 실험을 진행하였는데, 이 경우 HS가 NS보다 훨씬 좋은 성능을 보였다. 즉 어떤 문제에 적용하는 지에 따라 성능이 달라지는 것으로 사료된다.

# Closing

word2vec 은 기존 단어 벡터 학습에 비해 훨씬 빠른 시간에 학습을 하면서도 더 좋은 성능을 낼 수 있게 하여 NLP 분야의 새로운 지평을 열었다. 이렇게 각 단어별 벡터를 잘 학습할 수 있다면 이러한 벡터들을 가지고 할 수 있는 일은 무궁무진하게 넓어진다. 단 단어별 벡터를 안다고 이를 단순하게 문장이나 문단의 의미로 확장시킬 수 있는 것은 아니다. 이를 위해서 각 문장이나 문단의 의미까지 파악하기 위해 문장이나 문단을 벡터로 변환하는 sentence2vec, paragraph2vec 등의 연구가 계속 이어지고 있다. 이 word2vec 코드는 이미 오픈소스화 되어 공개되어 있다. 학습 모델 및 이미 학습되어 있는 결과들, 그리고 여러 실험을 해볼 수 있는 도구이다. python에는 gensim이라는 라이브러리가 있는데, 이 라이브러리의 기능중 하나로 word2vec을 사용할 수도 있다. 이 라이브러리는 C로 최적화가 이루어져 있어 단순히 NumPy로 구현하는 것 보다 70배의 속도를 낸다고 한다. 실제로 word2vec을 다뤄보고싶으신 분들은 위의 툴들을 참고하시길 바란다.

# References

[1] T. Mikolov, et al., Efficient Estimation of Word Representations in Vector Space. [arXiv]
[2] T. Mikolov, et al., Distributed Representations of Words and Phrases. [Link]
[3] X. Rong, word2vec Parameter Learning Explained. [Link]
[4] J. Garten, et al., Combining Distributed Vector Representations for Words. [Link]
[5] Y. Goldberg, et al., word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method. [arXiv]

 

Deep Learning

Batch Normalization 설명 및 구현

NIPS (Neural Information Processing Systems) 는 머신러닝 관련 학회에서 가장 권위있는 학회들 중 하나이다. 이 학회에서는 매년 컨퍼런스를 개최하고, 작년 12월에도 NIPS 2015라는 이름으로 러시아에서 컨퍼런스가 개최되었다. 이 컨퍼런스에 참가한 Brad Neuberg라는 참가자가 있는데, 그가 이 컨퍼런스에서 느낀 10가지 딥러닝 트렌드(원문) 라는 글이 굉장히 화제가 되었었다. 이 트렌드들 중 가장 ‘실용적’ 이라고 느낀 두 가지 트렌드는 다음 두 가지이다.

  1. 거의 모든 state-of-the-art system은 LSTM을 어느 정도 채용하고 있다.
  2. 이제 뉴럴넷 학습에 Batch Normalization은 필수화 되어가고 있다.

이 중에서 이번 글에서 초점을 맞출 부분은 ‘Batch Normalization’ 기법이다. Batch Normalization은 2015년 arXiv에 발표된 후 ICML 2015 (마찬가지로 매우 권위 있는 머신러닝 학회이다) 에 publish 된 이 논문 (Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariance Shift) 에 설명되어 있는 기법으로, 이 글에서는 이 논문의 내용을 간단하게 요약하고 넘어간 후 Batch Normalization을 실제로 구현하고, 성능을 실험해보는 과정에 대해 서술한다.

Paper

Motivation

Batch Normalization은 기본적으로 Gradient Vanishing / Gradient Exploding 이 일어나지 않도록 하는 아이디어 중의 하나이다. 지금까지는 이 문제를 Activation 함수의 변화 (ReLU 등), Careful Initialization, small learning rate 등으로 해결하였지만, 이 논문에서는 이러한 간접적인 방법보다는 training 하는 과정 자체를 전체적으로 안정화하여 학습 속도를 가속시킬 수 있는 근본적인 방법을 찾고싶어 했다.

이들은 이러한 불안정화가 일어나는 이유가 ‘Internal Covariance Shift’ 라고 주장하고 있다. Internal Covariance Shift라는 현상은 Network의 각 층이나 Activation 마다 input의 distribution이 달라지는 현상을 의미한다. 이 현상을 막기 위해서 간단하게 각 층의 input의 distribution을 평균 0, 표준편차 1인 input으로 normalize 시키는 방법을 생각해볼 수 있고, 이는 whitening이라는 방법으로 해결할 수 있다. Whitening은 기본적으로 들어오는 input의 feature들을 uncorrelated 하게 만들어주고, 각각의 variance를 1로 만들어주는 작업이다.

문제는 whitening을 하기 위해서는 covariance matrix의 계산과 inverse의 계산이 필요하기 때문에 계산량이 많을 뿐더러, 설상가상으로 whitening을 하면 일부 parameter 들의 영향이 무시된다는 것이다. 예를 들어 input u를 받아 x=u+b라는 output을 내놓고 적절한 bias b를 학습하려는 네트워크에서 x에 E[x]를 빼주는 작업을 한다고 생각해보자. 그럴 경우 E[x]를 빼는 과정에서 b의 값이 같이 빠지고, 결국 output에서 b의 영향은 없어지고 만다. 단순히 E[x]를 빼는 것이 아니라 표준편차로 나눠주는 등의 scaling 과정까지 들어갈 경우 이러한 경향은 더욱 악화될 것이고, 논문에서는 이를 실험적으로 확인했다고 한다.

이와 같은 whitening의 단점을 보완하고, internal covariance shift는 줄이기 위해 논문에서는 다음과 같은 접근을 취했다.

  • 각각의 feature들이 이미 uncorrelated 되어있다고 가정하고, feature 각각에 대해서만 scalar 형태로 mean과 variance를 구하고 각각 normalize 한다.
  • 단순히 mean과 variance를 0, 1로 고정시키는 것은 오히려 Activation function의 nonlinearity를 없앨 수 있다. 예를 들어 sigmoid activation의 입력이 평균 0, 분산 1이라면 출력 부분은 곡선보다는 직선 형태에 가까울 것이다. 또한, feature가 uncorrelated 되어있다는 가정에 의해 네트워크가 표현할 수 있는 것이 제한될 수 있다. 이 점들을 보완하기 위해, normalize된 값들에 scale factor (gamma)와 shift factor (beta)를 더해주고 이 변수들을 back-prop 과정에서 같이 train 시켜준다.
  • training data 전체에 대해 mean과 variance를 구하는 것이 아니라, mini-batch 단위로 접근하여 계산한다. 현재 택한 mini-batch 안에서만 mean과 variance를 구해서, 이 값을 이용해서 normalize 한다.

Algorithm

알고리즘의 개요는 위에 서술한 바와 같다. 뉴럴넷을 학습시킬 때 보통 mini-batch 단위로 데이터를 가져와서 학습을 시키는데, 각 feature 별로 평균과 표준편차를 구해준 다음 normalize 해주고, scale factor와 shift factor를 이용하여 새로운 값을 만들어준다. 알고리즘의 개요는 다음과 같다.

BN1
Batch Normalization Transform

실제로 이 Batch Normalization을 네트워크에 적용시킬 때는, 특정 Hidden Layer에 들어가기 전에 Batch Normalization Layer를 더해주어 input을 modify해준 뒤 새로운 값을 activation function으로 넣어주는 방식으로 사용한다.

Network with Batch Normalization. 출처 : http://mohammadpz.github.io

Training Data로 학습을 시킬 때는 현재 보고있는 mini-batch에서 평균과 표준편차를 구하지만, Test Data를 사용하여 Inference를 할 때는 다소 다른 방법을 사용한다. mini-batch의 값들을 이용하는 대신 지금까지 본 전체 데이터를 다 사용한다는 느낌으로,  training 할 때 현재까지 본 input들의 이동평균 (moving average) 및 unbiased variance estimate의 이동평균을 계산하여 저장해놓은 뒤 이 값으로 normalize를 한다. 마지막에 gamma와 beta를 이용하여 scale/shift 해주는 것은 동일하다.

전체적인 Batch Normalization layer의 pseudo-code 는 다음과 같다. 논문에는 다소 헷갈릴 수 있는 방식으로 설명이 되어있는데, 결국 중요한 것은 ‘Training 할 때는 mini-batch의 평균과 분산으로 normalize 하고, Test 할 때는 계산해놓은 이동 평균으로 normalize 한다. Normalize 한 이후에는 scale factor와 shift factor를 이용하여 새로운 값을 만들고, 이 값을 내놓는다. 이 Scale factor와 Shift factor는 다른 레이어에서 weight를 학습하듯이 back-prop에서 학습하면 된다.’ 라는 흐름이다.

BN2.PNG
Batch Normalization Pseudo-code.

단, 지금까지의 설명은 ‘일반적인 Network 일 때’ 에 한해서 통용된다. 만약 Batch Normalization을 CNN에 적용시키고 싶을 경우 지금까지 설명한 방법과는 다소 다른 방법을 이용해야만 한다. 먼저, convolution layer에서 보통 activation function에 값을 넣기 전 Wx+b 형태로 weight를 적용시키는데, Batch Normalization을 사용하고 싶을 경우 normalize 할 때 beta 값이 b의 역할을 대체할 수 있기 때문에 b를 없애준다. 또한, CNN의 경우 convolution의 성질을 유지시키고 싶기 때문에, 각 channel을 기준으로  각각의 Batch Normalization 변수들을 만든다. 예를 들어 m의 mini-batch-size, n의 channel size 를 가진 Convolution Layer에서 Batch Normalization을 적용시킨다고 해보자. convolution을 적용한 후의 feature map의 사이즈가 p x q 일 경우, 각 채널에 대해 m x p x q 개의 각각의 스칼라 값에 대해 mean과 variance를 구하는 것이다. 최종적으로 gamma와 beta는 각 채널에 대해 한개씩 해서 총 n개의 독립적인 Batch Normalization 변수들이 생기게 된다.

Benefit

논문에서 주장하는 Batch Normalization의 장점은 다음과 같다.

  1. 기존 Deep Network에서는 learning rate를 너무 높게 잡을 경우 gradient가 explode/vanish 하거나, 나쁜 local minima에 빠지는 문제가 있었다. 이는 parameter들의 scale 때문인데, Batch Normalization을 사용할 경우 propagation 할 때 parameter의 scale에 영향을 받지 않게 된다. 따라서, learning rate를 크게 잡을 수 있게 되고 이는 빠른 학습을 가능케 한다.
  2. Batch Normalization의 경우 자체적인 regularization 효과가 있다. 이는 기존에 사용하던 weight regularization term 등을 제외할 수 있게 하며, 나아가 Dropout을 제외할 수 있게 한다 (Dropout의 효과와 Batch Normalization의 효과가 같기 때문.) . Dropout의 경우 효과는 좋지만 학습 속도가 다소 느려진다는 단점이 있는데, 이를 제거함으로서 학습 속도도 향상된다.

Implementation

Batch Normalization의 경우 NIPS 2015 10대 트렌드에서 보았듯이 Deep Learning 계에서 필수적인 기법이 되어가고 있다. 나는 Deep Learning 구현에 python과 theano를 쓰는데, Batch Normalization Layer의 경우 Keras에는 이미 구현이 되어있지만 theano에는 아직 구현이 되어있지 않다(0.7.1 에서 추가될 예정이라는듯). 따라서 theano를 이용해서 한번 구현을 해보고 싶기도 하였고, 한번쯤은 실제로 구현을 해봐야 의미가 있을 것 같아 theano를 이용하여 Batch Normalization Layer를 구현해보았다.

구현한 코드는 Github에서 확인할 수 있다. Repo의 readme에 대략적으로 설명이 되어있기도 하지만, BatchNormalization.py 가 가장 핵심적인 Batch Normalization Layer이다. 일반적인 BN과 CNN에서 사용하는 BN을 모두 지원하며, train 시에는 run_mode를 0, test 시에는 run_mode를 1로 설정해주고 돌려야 한다. BNConvLayer.py와 BNMLP.py는 각각 activation 직전, hidden layer 직전에 Batch Normalization을 넣어준 convolution layer / MLP 이다.

논문과 조금 다르게 구현한 부분은 Test의 평균을 구하기 위해 moving average를 구하는 부분이다. 단순히 Moving Average를 구현할 경우, moving average를 구하기 위해서 최근 몇 개 input의 값들을 저장해놓아야 한다는 단점이 있다. 새로운 moving average를 계산할 때 가장 오래된  이를 방지하기 위해, 그냥 moving average 대신 exponential moving average 를 적용하여 값을 저장해놓지 않고도 moving average를 계산할 수 있도록 하였다.

Experiment

Batch Normalization Layer 를 구현해 보았으니, 실제로 뉴럴넷 학습에 Batch Normalization이 얼마나 강력한 효과를 가지는지 실험을 통해 확인해보았다. 실험은 간단하게 MNIST Dataset을 이용하여, Batch Normalization 을 적용한 네트워크와 그렇지 않은 네트워크의 성능 차이를 비교해보았다. MNIST Data의 전처리는 Global Contrast Normalization만 해주었다.

코드 상으로는 normalCNN.py 가 일반적인 네트워크, BNaddedCNN.py 가 Batch Normalization을 적용한 네트워크를 가지고 MNIST Classification을 진행하는 코드이다. 두 실험 모두 네트워크의 규모는 동일하다. 두 네트워크 모두 convolution layer 3개(channel은 각각 32개, 64개, 128개) 와 max-pool layer 2개, 그리고 마지막에 hidden layer 800개 – output layer 10개 짜리 MLP를 달아준 간단한 Convolutional Neural Network이다. 다만 차이점의 경우 normalCNN에서는 Convolution Layer들 사이에 Dropout Layer를 하나 달아주고 MLP에 Dropconnect를 적용하였으며, BNaddedCNN에서는 Drop 들을 다 제거하고 Convolution Layer와 MLP에 Batch Normalization을 적용하였다.

일단 같은 learning rate를 적용했을 때의 결과를 비교해보자. learning rate를 0.002로 잡았을 때, 단순한 CNN과 Batch Normalization을 적용한 CNN의 성능 비교 그래프이다.

BN3

결과 그래프를 보면 두 네트워크 사이에 확연히 성능의 차이가 존재하는 것을 알 수 있다. 같은 learning rate에서 학습을 진행했음에도 불구하고, Batch Normalization을 적용한 네트워크의 에러율이 일반 CNN의 에러율 그래프보다 훨씬 아래에 존재한다. 또한, epoch 1만 진행했을 때도 에러율이 3.19% / 1.65%로 반 정도로 차이가 난다. 적당히 성능을 비교하기 위해 약 25 epoch 정도만 학습을 진행했는데, 이 과정에서 가장 낮은 Validation Error Rate는 각각 0.92% / 0.78%로 Batch Normalization을 적용한 네트워크 쪽이 더 낮았다.

위에서 설명한 Batch Normalization의 장점중에는 높은 learning rate를 잡을 수 있다는 특징도 있었다. 이를 실험해보기 위해, 기존에 실험했던 learning rate의 10배인 0.02의 learning rate로도 비교실험을 진행해보았다. 이를 진행해보니 Batch Normalization에서는 특이한 점 없이 계속 에러율이 내려간 반면, 일반적 CNN에서는 gradient explode가 일어나 90%의 에러율을 보였다(에러율이 90%라는 것은 값이 폭발하여 NaN 등이 발생하고, 이에 따라 정상적인 값이 나오지 않았음을 의미한다).

마지막으로, Batch Normalization 을 적용한 Network에 0.01의 learning rate를 주고 빠른 learning rate decay를 적용하여 긴 시간동안 학습을 진행시켜 보았다. 총 300 epoch 동안 학습을 진행시켰으며, 최종적으로 학습을 마쳤을 때 MNIST Test Data의 Error rate는 0.6% 였다. 이 실험은 데이터의 preprocessing / augmentation, careful hyper-parameter selection 없이 진행되었으며 비교적 shallow한 CNN를 이용하여 진행하였으므로, 이것저것 처리를 해주고 네트워크 구조를 바꾸어 준다면 더 낮은 에러율을 얻을 수 있을거라고 확신한다.

BN4
최종적으로 돌려본 Batch Normalization Network의 Validation Error Rate 그래프. 300 epoch 후의 최종적 Test error rate는 0.6%였음.

Closing

Batch Normalization을 공부하고, 구현하고 실험해봄으로서 이 ‘각 layer 당 normalize를 해준다’ 라는 비교적 간단한 아이디어가 네트워크 학습의 성능을 얼마나 향상시킬 수 있는지에 대해 직접 체감할 수 있었다. Batch Normalization이 필수적인 트렌트가 되고 있다는 증언까지 있는 만큼, 딥 러닝에 관심이 있는 사람이라면 이 기법에 대해 알아놓으면 좋을 것 같다.

최종적으로 Batch Normalization과 이 글의 내용을 정리해보자면,

  • Batch Normalization에서는 각 layer에 들어가는 input을 normalize 시킴으로써 layer의 학습을 가속하는데, 이 때 whitening 등의 방법을 쓰는 대신 각 mini-batch의 mean과 variance를 구하여 normalize한다.
  • 각 feature들이 uncorrelated 되어있다는 가정의 효과를 없애주기 위해, scaling factor와 shifting factor를 layer에 추가로 도입하여 back-prop으로 학습시킨다.
  • Theano로 Batch Normalization을 구현하였다.
  • MNIST Dataset으로 실험한 결과 Batch Normalization 기법이 실제로 학습을 가속화하고, 이에 따라 학습의 성능을 향상시킬 수 있다는 것을 실험적으로 확인하였다.