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 기법이 실제로 학습을 가속화하고, 이에 따라 학습의 성능을 향상시킬 수 있다는 것을 실험적으로 확인하였다.

 

Kaggle

Kaggle : Santa’s Stolen Sleigh

두 번째로 참여하게 된 Kaggle 대회는 Santa’s Stolen Sleigh 라는 대회이다. 이 대회는 다소 이벤트성 대회의 성격을 띠고 있는 것이, 크리스마스 기간에 맞추어 크리스마스 컨셉으로 나온 문제이기 때문이다. 제목만 봐도 그래보이지 않는가? 그러나 이 대회는 이벤트성 대회임에도 불구하고 실제 상금이 걸려있는 대회이다. 최종 1위 팀 / 리더보드 1위를 가장 길게 유지하고 있던 팀 / 제공된 Optimization Tool 을 이용한 팀 중 가장 점수가 높은 팀 에게 각각 1만불, 5천불, 5천불의 상금이 지급된다. 물론 나는 저 상금과는 상당히 거리가 멀었지만..

여하튼 이 대회는 다른 Kaggle 대회와는 다소 성격이 다른 대회이다. 다른 대회들이 정말 Data Science 스러운 문제들을 내놓고 있다면, 이 대회는 그보다는 조금더 PS적인 느낌이나 Optimization 느낌이 나는 문제를 제공했다고 할 수 있다. 과연 어떤 문제인지, 그리고 내가 어떤 방식으로 접근했는지 정리해보겠다.

Problem Description

크리스마스를 맞이하여 산타할아버지가 전 세계에 선물을 나누어주려고 한다. 세계 방방곡곡에 10만개의 선물을 배달해야하는데, 각각의 선물이 배달되어야 하는 위도-경도 좌표와 그 선물의 무게가 주어져있다. 산타할아버지는 루돌프가 끄는 썰매를 타고 North Pole에서부터 선물을 배달해야 한다. 그런데 한 번의 Trip에서 싣는 선물들의 무게의 합이 1000을 넘으면 안되고, Trip 한번이 끝나면 다시 North Pole로 돌아와서 남은 선물들을 담은 뒤 다음 Trip을 떠나야 한다. 썰매 자체의 무게는 10이다.

이 문제의 최종적인 목적은, 루돌프들이 너무 힘들지 않도록 배달하는 과정을 최대한 최적화시키는 것이다. 루돌프들이 힘든 정도는 ‘Weighted Raindeer Weariness – WRW’ 라고 해서, 다음과 같은 방식으로 계산한다.

WRW
w_kj = j번째 trip에서 k번째로 배달하는 gift의 무게, Loc_i = i번째로 배달하는 gift의 위치

즉, 어떤 지점에서 다른 지점으로 이동할 때의 그 거리와 그 거리를 이동할 때의 썰매+선물의 총 무게가 있을텐데, 이 값을 곱한 것을 모든 이동에 대해 다 더한 값을 WRW라고 하는 것이다. 이 때 거리는 haversine 이라는 방식을 이용하여, 위도와 경도를 이용하여 실제 지구상에서의 거리를 계산한 거리를 사용한다.

더 자세한 설명은 대회 페이지의 Description, Evaluation 항목에서 확인할 수 있다.

Approach

기본적으로 이 문제는 TSP 느낌이 나는 문제이다. 결국 주어진 지점들을 어떤 순서로 이동하느냐에 따라 점수가 달라지는 형태의 문제이기 때문이다. 물론 한 Trip에 대한  Weight limit이 있고, 점수 계산법도 크게 다르기 때문에 TSP와는 매우 다르면서도 훨씬 어려운 문제이기는 하지만 기본적으로 완전 그래프 위에서 경로를 최적화시켜나간다는 컨셉은 같기 때문에 전체적인 접근의 틀은 유사하게 가져갈 수 있을 것이다.

나는 기본적으로 이 문제에 대한 해결책을 크게 두 개의 단계로 나눠야 한다고 생각했다. 일단, 문제에서 각각의 Trip들에 대해 어떤 Gift들이 들어가야 하는지를 정해준다면, 각각의 Trip이 몇 번째로 진행되는가와는 상관 없이 Trip 하나하나에 대해 독립적으로 최적화를 시켜줄 수 있을 것이다. 즉, 문제를 크게 (1) Trip에 들어갈 Gift를 나누는 과정, (2) 각 Trip에서 선물을 배정하는 순서를 결정하는 과정 으로 나누어 진행할 수 있는 것이다.

이 문제를 진행하는 과정에서 가장 크게 유의해야할 점은 ‘계산량’ 이다. 먼저 선물의 갯수가 10만개나 되어, 안일하게 알고리즘을 세웠다가는 생각보다 계산량이 너무 많아져서 진행 속도가 너무 느려질 수 있다. 또한, 각 지점들 사이의 거리를 ‘haversine’ 으로 계산하는데, 이 계산에 sin, cos 뿐만 아니라 atan 등의 함수도 들어가기 때문에 거리 연산에 생각보다 많은 시간이 든다 (실험환경 기준으로 100000개의 haversine 연산을 하는 데에 0.31초 정도가 소요된다). 따라서, 최대한 계산량을 최적화하는 방향으로 문제를 해결해야 한다.

Stage #1 : Grouping Gifts (1)

문제를 Stage 1과 2로 나누어서 Grouping 과정과 Trip 순서 Optimization 과정으로 나누었지만, 실질적으로 대부분의 시간은 이 Stage 1 과정에서 소모하였다. 정말 엄청난 삽질과 멘붕, 그리고 시간소모를 하면서 결국 처음 예상했던 것과 너무 다른 방향으로 문제에 접근하게 되었고, 결국 정말 불만족스러운 결과를 얻게되었다. 여기에서는 처음부터 끝까지 내가 어떤 방식으로 문제에 매달렸는지에 대한 기록을 의식의 흐름대로 적어보려고 한다.

첫 번째 단계에서는 먼저 선물들을 묶어서 Trip에 들어갈 선물들을 선별해야한다. 이 때 대략적으로 초기해를 잡고 시작하려 했는데, 나는 처음 문제에 접근할 때 가장 좋은 방법이 ‘가까이 있는 선물들을 묶어서 한 Trip에서 같이 배달하는 것’ 이라고 생각하였다. 따라서 k-means를 구현하여 대충 가까이 있는 선물들을 묶어놓은 초기해를 만들었다. 이렇게 한 문장으로 적어놓으니 굉장히 간단하게 한 것 같지만, 이 k-means를 하는 데에도 나름 시행착오가 많이 들어갔다. haversine 연산의 시간이 오래 걸리기는 하지만 이를 기준으로도 충분히 계산할 수 있을 것이라고 생각하여, k-means를 할 때 위/경도 기반으로 계산을 진행했다. 그런데 이렇게 할 경우 클러스터의 중심점을 옮기는 과정에서 단순히 평균을 낼 수가 없어서, 단위구 위의 실제 좌표로 변환하여 평균을 낸 뒤 다시 위, 경도 기반 좌표로 바꾸는 식으로 계산을 진행했다. 또한, weight limit 조건을 만족하기 위해 가장 가까운 클러스터의 무게가 초과될 경우 다음으로 가까운 클러스터를 보는 방식으로 assign을 진행하였다.

대회 Forum을 보니 대부분의 사람들의 Trip의 수가 1200~1500 정도인 것 같아서, k를 1800으로 잡고 클러스터링을 진행하였다. 이 k-means의 경우 haversine 연산을 사용하기 때문에 numpy를 이용한 최적화를 하기가 힘들어서 실행 시간이 굉장히 오래 걸렸지만, 실행시켜놓고 일어나보니 얼추 클러스터링 된 결과를 얻을수가 있었다.

다음은 이 초기해를 바탕으로 Optimization을 진행하여, 더 좋은 Trip들을 얻는 과정이 필요하다. 이 과정이 문제 해결에 주가 되는 과정이므로 이 과정을 해결하는 알고리즘을 설정하는 것이 굉장히 중요하다. 결국 이러한 문제를 푸는 과정은 ‘방대한 해 공간을 탐색해가면서 가장 좋은 해를 찾는 것’ 이라고 요약할 수 있을 것이다. Machine Learning 분야에서는 이러한 ‘해공간의 탐색’ 이 Gradient Descent라는 이름으로, 기울기를 따라 조금씩 이동해가면서 해공간을 탐색하는 방식으로 사용되고 있다. 그러나 이번 대회와 같은 문제에서는 목적 함수가 Discrete하기 때문에, 함수에 기울기라는 것이 존재하지 않아서 다른 방법을 적용할 필요가 있다.

해공간을 탐색하는 기법들은 정말 다양하다. GA, SA 등 이미 수많은 메타휴리스틱 기법들이 발견되어 사용되고 있고, ACO 등의 집단지성 최적화 기법도 있다. 이러한 수많은 방법들 중, 나는 이 문제에 가장 적합해보이고 내가 일전의 프로젝트에 사용해보아 가장 익숙한 Tabu Search라는 방법을 이용하여 문제에 접근하기로 하였다(사실, 대부분의 상위권 팀들은 Simulated Annealing 을 사용한 듯 하다. 그래도 기본적으로는 비슷한 흐름을 가진 기법이니..).

Tabu Search는 기본적으로 특정 해에 대해 이웃한 ‘이웃해’를 정의하여 그 이웃해들 중 가장 좋은 해로 이동하는 Local Search 기법에다가 Local Minima에 빠지지 않도록 이동 금지 목록인 Tabu List를 관리하면서 탐색하는 기법이다. 즉, 기본적으로 특정 해 상황이 있을 때 그 해와 유사한 해인 이웃해를 정의해주어야 한다. 이 문제에서는 이웃을 (1) 특정 선물을 현재 Trip에서 다른 Trip으로 옮긴 해, (2) 가까이 위치한 특정 선물 2개의 Trip을 서로 맞바꾼 해 로 정하고, 구현하였다.

여기서 문제는, Tabu Search를 행하기 위해서는 현재 해가 얼마나 좋은 해인지 그 점수를 평가하는 기준이 있어야 한다는 것이다. 문제의 첫 번째 단계에서는 단순히 선물을 여러개의 Trip으로 나누는 일만을 하기 때문에 직접적으로 이 해가 좋은 해라는 기준을 세우기가 굉장히 어렵다. 그래서 간접적으로, ‘각 나눠진 Trip들에 대해 Greedy하게 (Weight이 큰 Gift를 먼저 배달하고, Weight이 같을 경우 위도 내림차순으로 배달) 배달했을 때의 총 WRW’ 를 평가 기준으로 삼아 Tabu Search를 진행하였다.

이웃해와 평가 함수가 정해졌으니 이를 바탕으로 Tabu Search를 진행하면 되지만, 정말 Naive하게 구현할 경우 계산량이 폭발해버리고 말 것이다. 기본적으로 이웃해를 본다는 것은 정의한 이웃해에 대해 가능한 해를 다 보아야 하는데, 이웃 (1)만 봤을 때도 모든 이웃해를 다 보기 위해서는

  •  Cluster 두개를 정하는 갯수 1800P2
  •  x 이동할 선물을 정하는 갯수 평균 50개
  •  x (이동한 후의 선물 위치 찾기 O(50) + 이동한 후의 WRW 변화량 계산 O(50 * haversine 연산) )

 으로,  한 단계에서 대충 O(81억 * haversine 연산) 이 필요한데, 최소 몇천에서 몇만 단계를 이동해야 하는 탐색에서 한 단계에서 저렇게 많은 연산이 필요하면 제대로 탐색을 진행할 수조차 없다. 따라서 여기에서 계산량을 줄이기 위해서 여러 가지 방법을 사용했는데,

(1) 이동한 후의 WRW 변화량을 직접 이동시켜서 계산하는 것이 아니라, 이웃이 된 후의 변화량을 예측하여 WRW 변화량 계산을 O(1)로 줄였다. 사실 이 과정에서 삽질을 많이 해서, 디버깅 하는데 애를 좀 먹었다.

(2) 한 단계에서 모든 클러스터 선택 가능성을 보는 것이 아니라, 첫 번째 클러스터를 정할 때에는 일정 갯수의 클러스터만 랜덤하게 선택해서 보았다. 또한, 두 번째 클러스터를 정할 때 현재 선택한 선물과 두 번째 클러스터의 첫번째 선물이 너무 멀리 떨어져있을 경우 탐색하지 않았다.

(3) 앞에서 소개한 Greedy한 방법의 중요한 점은, 선물들을 모두 Comparable 하게 만들 수 있다는 점이다. 따라서 각 Trip의 선물을 정렬해놓고 List의 형태로 가지고 있었고, 새로운 선물이 들어갈 위치를 찾을 때 이분 탐색을 이용하여 들어갈 위치를 찾았다. 이를 이용하면 새로운 선물이 들어갈 위치를 찾는데에 걸리는 시간이 O(50)에서 O(ln 50) 으로 줄어든다.

(4) 이웃 (2) 에서 ‘서로 가까운 선물 두 쌍을 골라서 바꾼다’ 는 식으로 되어있는데, 여기서 선물을 선택할 때마다 가까운 선물이 뭐가 있는지를 계산한다면 어마어마하게 시간이 많이 투자될 것이다. 따라서 이는 미리 전처리를 해놓아서 특정 선물에서 가장 가까운 선물들의 목록이 담긴 배열을 만들어놓고, 필요할 때 이를 불러서 사용하였다.

Stage #1 : Grouping Gifts (2)

이렇게 Tabu Search를 구현하였으니 이제 돌리면서 점수가 줄어들기만을 기다리면 될 것이다. 그런데 문제가, 너무 수렴하는 속도가 느렸다. 처음 k-means만을 돌린 초기해의 WRW가 15.55B였는데, 반나절 넘게 돌리니 13.XXB 정도가 되었지만 수렴 속도가 너무 느려져서 더 낮아지길 기대하기 힘들었다. 당시 대회 1등의 점수가 12.38B였고, 100등 안에 들기 위해서는 12.45~6B 정도까진 점수를 내려야 했기 때문에 변화의 필요성을 느꼈다. 이 때 대회 Forum을 찾아봤는데, 이 링크에서 발견한 코드에서 단순히 k=4000으로 잡고, haversine도 아니고 위/경도를 가지고 단순히 k-means를 돌린 결과임에도 불구하고 돌린 결과가 13.7B 정도였다 (아무래도 내가 k를 작게 잡고, weight limit을 주어서 돌렸다는 점에서 점수가 많이 높여진듯 하다). 따라서, 초기해를 이 링크에서 주어진 submission으로 바꾸어준 후 새롭게 Tabu Search를 돌렸다. 확실히, 초기해가 낮아지니 더 많이 내려가는 양상을 확인할 수 있었다.

그런데 여기에서도 문제가 있었다. 일단 여기서 k=4000 이었기 때문에 Tabu Search를 진행하면서 점점 Trip들이 합쳐지고 Trip의 숫자가 줄어야 했는데, Trip이 서로 합쳐지는 일은 일어나지 않았다. 확실히 Tabu Search는 각 단계에서 이웃해들 중 가장 좋은 해로 이동하기 때문에, Trip이 줄어들기 위해서는 임시적으로 점수가 오르는 방향으로 진행되어야 할 것이므로 그 방향으로 진행하지 않을 수 있다는 생각이 들었다. 그래서 기존 점수에 더해서 Trip의 선물 갯수가 줄어드는 방향으로 이동할 경우 Bonus 점수를 주는 식으로 점수를 더해보았지만, 크게 상황이 나아지지는 않았다. 지금 와서 생각해보면, 강제로 하나의 Trip을 없애고 다른 Trip들로 분배하는 operation을 추가했으면 어땠을까 싶다.

또한, 어느정도 수렴이 된 결과를 가지고 Stage 2를 구현하여 돌려보았는데, 돌아가는 양상을 보니 Stage 2를 다 돌려도 결과가 잘해야 12.6~7B밖에 나오지 않을 것 같았다. 이렇게 되면, 좋은 점수를 얻지 못할 것 같다는 생각이 들었다.

이렇게 되어, 초기해를 clustering으로 정하는 방식을 폐기하고 이 링크에 있는 Submission으로 바꾸었다. 이 Submission의 경우 초기 점수가 12.52B 정도 되었는데, 이 방식은 선물들을 Longitude 기준으로 묶어서 North Pole 에서 시작하여 수직으로 내려오는 방식으로 진행하였다. 사실 모든 상위권 팀들은 이러한 방식으로 접근을 한 듯 하다. 이 방법을 가져와서 Gift 비교 기준 등을 수정하여 며칠 간 돌려본 결과, 12.52B에서 12.459B 정도까지 점수를 내릴 수 있었다.

Stage #2 : Trip Optimization

두 번째 단계에서는 분류한 선물들을 가지고 각각의 Trip 자체를 Optimize 하였다. Trip이 2천개 정도 있을 경우 각각의 선물은 평균적으로 50개 정도밖에 없기 때문에, 이 단계에서 빠르고 쉽게 점수를 내릴 수 있을 것이라고 기대했다.

두 번째 단계에서도 마찬가지로 Tabu Search를 이용하여 최적화를 진행했다. 이웃해는 (1) 두 선물의 배달 순서를 바꾼다 (2) 한 선물을 빼고, 다른 순서로 배달한다 로 정의하였다. 먼저 구현해놓은 Tabu Search가 있었기에, 이 단계에서는 상대적으로 쉽게 구현을 끝낼 수가 있었다.

문제는,  Stage #2가 생각보다 의미가 없는 단계였다는 것이다. 비슷한 위치 기준으로 클러스터링하여 생각한 해의 경우 확실히 처음 생각한 Greedy한 방법이 정말 ‘Greedy 할 뿐인’ 방법이었기 때문에 이 단계에서 최적화될만한 요소가 많았고, 다 돌려보지는 않았지만 대충 점수를 13.15B에서 0.4B정도는 내릴 수 있을거라는 생각이 들었다. 반면, Longitude 기준으로 진행했을 경우 위에서 생각한 Greedy한 방법이 최적해와 상당히 유사한 방법이었기 때문에 Stage #2에서 내려가는 점수가 정말 적어서 의미가 없는 수준이었다. 따라서 여기서 의욕을 잃은데다가 설상가상으로 계절학기 시험까지 겹쳐서 포기하고, 최종적으로 Stage #1에서 만든 12.459B 정도의 Submission을 제출하였다.

Result & Discussion

확실히 이 대회는 정말 재미있는 대회이기는 했지만, 개인적으로 너무 멘붕과 삽질을 한 대회여서 정신적으로 피해가 컸다. 나름 생각을 많이 하고 여러가지 시도를 해보았지만, 아직 다른 사람들과 비교해보았을 때 많이 모자란게 아닌가 싶다. 나의 최종적인 점수는 12.459B였고, 1위 팀의 점수는 12.384B였다. 나는 1127개의 팀중 최종적으로 175위를 하였다.

대회 최종적으로 1위2위를 한 팀의 결과를 링크에서 확인할 수 있다. 두 팀은 모두 SA를 기반으로 탐색을 진행한 듯 하며, 1위 팀은 SA 기반으로 가장 좋은 parameter를 찾는 데에 많은 시간을 소모한듯 하다.

아.. Kaggle 정말 너무 어려운거 같다. ㅋㅋㅋㅋ 앞으로 공부해야할 것도 너무 많고… 더 잘 하고 싶다. 공부에 대한 의욕만 불타오르게 만들어준 대회였다.

모든 실험은 python으로 구현하여 진행하였고, 구현 결과는 내 Github Repo에서 확인할 수 있다.

Kaggle

Kaggle : What’s Cooking?

Kaggle에 대해 알게 된건 올해 초 쯤이었던 것 같다. Kaggle은 일종의 데이터 사이언스 대회 사이트인데, 특정 문제가 주어지면 그 문제를 해결하기 위해 전 세계의 데이터 과학자들이 각자 가지각색의 알고리즘을 통해 문제를 해결하고, 그 성능을 경쟁한다. PS 분야에 Codeforces가 있다면, 데이터 사이언스 분야에서 이 사이트가 비슷한 역할을 하고 있다고 할 수 있겠다. 과제로 주어지는 문제의 종류는 굉장히 다양하며, 개중에는 데이터 분석이 필요한 기업들에서 상금을 걸고 대회를 주최하는 경우도 있다. 이 대회들에 참가하는 사람들은 처음 데이터 사이언스 공부를 시작하는 학생들뿐만 아니라, 관련 대학원생들이나 실제 현장에서 일하는 전문가들까지 굉장히 다양한 사람들이 대회에 참여하고 있다.

Kaggle에 대해 처음 알았을 때부터 굉장히 흥미가 생겼던 것이, 고등학교 때부터 내가 이 분야에 대해 공부하면서 최종적으로 하고싶었던 것들이 이렇게 ‘언뜻 보면 어떻게 해결해야할 지 모르겠는 고난도의 real-life 문제들’ 을  기계 학습 등의 방법을 통해 분석하고, 해결하는 것이었기 때문이다. Kaggle에서 주어지는 문제들은 이러한 나의 흥미에 딱 들어맞았다. 처음 Kaggle에 대해 알게 되었을 때는 관련 지식이 전혀 없었기 때문에, 문제를 풀 방법이 없었다. 그러나 1년간 기계 학습에 대해 공부하면서 이 분야에 대해 아직 미흡하지만 문제들에 도전은 해볼 정도의 지식은 생긴 만큼,  이제 갖가지 Kaggle 대회들에 실제로 참여해보면서 실제 문제들을 해결해보려고 한다.

처음으로 참여한 Kaggle 대회는 ‘What’s Cooking?‘ 이라는 대회이다.  이 대회는 얼마 전인 12월 20일에 종료되었는데, 이 대회에 대해 알게 되고 실제로 참여한 것이 12월 17일이었다. 4일이라는 시간이 다소 짧아 많은 것을 시도해보거나 좋은 성과를 이루어내지는 못했지만, 그래도 이 동안 어떤 식으로 문제에 접근했는지 정리해보고자 한다.

Problem Description

이 문제에 대한 자세한 설명은 위에 첨부한 대회 페이지에서 자세하게 볼 수 있다.
문제의 전체적인 개요는 ‘어떤 음식을 만들기 위한 재료의 목록이 입력되었을 때, 이 음식이 어느 나라(지역)의 음식인지 분류하는’ 것이다. 재료는 양이나 넣는 순서 등은 주어지지 않고 단순히 재료의 이름만이 주어지며, 재료들의 이름이 깔끔하게 주어지지도 않는다(‘salt’, ‘sugar’, ‘eggs’ 등의 단순한 이름도 있지만, ‘eggland’s best® eggs’, ‘reduced-fat sour cream’ 등 브랜드나 부가적 설명이 붙은 재료들도 있고 typo가 있는 재료들도 있다). 이 재료들의 목록을 바탕으로 음식의 ‘cuisine(특정 지역, 나라의 음식)’ 을 분류해야 하는데, cuisine은 southern-us, spanish, french, korean, japanese, brazilian .. 등 20 종류가 있다. 문제를 해결하기 위해 약 4만 개의 음식에 대한 재료 정보를 담은 training data가 주어진다.

Methodology Part #1

이 문제를 보고 가장 기본적으로 떠오르는 접근법은 training data를 돌면서 ingredient의 dictionary를 만든 뒤, 재료 목록을 bag-of-ingredients 등으로 표현한 뒤 Naive Bayes나 Neural Network 등의 분류기를 사용하는 방법일 것이다. 그러나 나는 보다 재료들의 ‘본질적인 특성’ 에 대해 알 수 있는 방법이 있을 것이라고 생각했고, 재료들의 특성을 보다 수치적으로 표현할 수 있다면 이 정보를 이용하여 보다 정교한 분류가 가능할 것이라고 생각했다. 이에 분류에 앞서 각 ingredient의 정보를 수치화하는 방법이 필요하였고, 여기서 떠오른 것이 word2vec 이었다.

word2vec은 자연어처리(NLP)에서 사용되는 방법으로, 특정 단어의 직접적인 의미를 파악할 수 없었던 기존 자연어처리 기법을 비약적으로 발전시킨 방법이다. 이 방법에서는 각각의 단어들을 고차원의 숫자 벡터로 나타내어 단어 자체를 ‘특성화’ 시킨다. 이 방법을 이용하면 이 벡터들을 가지고 더하고 빼는 등 하면서 단어에 대한 추론이나 단어 사이의 관계도 쉽게 다룰 수가 있게 된다. word2vec에 대한 정보를 더 알고싶다면 이 블로그를 참조하면 될 것 같다.

word2vec이 단어 자체를 특성화하듯이, 나도 같은 방법으로 재료 자체를 특성화할 수 있다. 특히 이 문제에서 요리라는 것은 결국 재료의 선형적인 결합이라고 근사화할 수 있다고 생각하였기 때문에, 이렇게 재료를 수치화하여 분석한다면 좋은 결과를 얻을 수 있을 것이라고 생각하였다. 이를 ingredient를 vector로 바꾸는 과정이므로 ing2vec이라고 부르겠다. ing2vec의 학습에는 word2vec의 학습 방법 중 skip-gram을 이용하였는데, word2vec의 학습 자료인 ‘글’과는 달리 요리의 재료에는 딱히 정해진 순서가 없다. 따라서 특정 요리의 특정 재료에 대해 함께 등장하는 재료들을 랜덤하게 고른 다음, 이를 이용하여 학습을 진행하는 방법을 사용하였다. 또한 word2vec 학습에서의 ‘글’과 이 training data가 다른 점은, 글을 학습하는 과정에서는 실제 의미를 알 수 없는 반면 이 training data의 경우에는 cuisine이 무엇인지에 대한 답이 주어진다는 점이다. 이에 착안하여, skip-gram의 중간 hidden layer에 별개로 hidden layer #2 – output layer를 달아주어 cuisine classifying layer를 따로 달아주었다. 이를 이용하면, 각각의 ingredient의 unsupervised feature 말고도 각각의 재료의 ‘cuisine’ 의 특성을 반영하는 요소도 넣어줄 수 있을 것이라고 생각하였다. 결국 ing2vec에서 사용한 네트워크 구조와 학습법은 대충 다음과 같다.

Diagram
– Layer Structure and Cost Definition for ing2vec training.

 레이어 구조와 학습은 theano를 이용하여 구현했는데, 나는 네트워크 크기가 그렇게 크지 않고 학습 데이터도 word2vec의 데이터 사이즈에 비하면 굉장히 작기 때문에 학습이 빠르게 진행될 것이라고 생각하여 negative sampling 등의 방법을 사용하지 않고 굉장히 naive하게 구현하였다. 그런데 생각보다 학습 속도가 느려서, 밤새 학습을 진행했는데도 5 epoch밖에 진행하지 못했다 (물론 실험을 진행한 환경이 열악하기도 했지만).

 이렇게 naive하게 구현하게 ing2vec을 구현하였고, 학습이나 hyperparameter 선정도 제대로 진행되지 못하여 과연 vectorize가 제대로 되었을 지 의문이 들었지만 학습된 결과를 가지고 몇 가지 실험을 진행해보니 어느 정도는 학습이 제대로 진행된 것을 확인할 수 있었다.

coffee, gochujang
Top 10 Closest Ingredients to Target : (1) Coffee, (2) Gochujang Base

 위는 ‘coffee’ 와 ‘gochujang base’ 재료에 대해 가장 가까운 10개의 재료들을 나열한 결과이다. 가깝다는 기준으로는 cosine similarity를 사용하였다. 보다시피 두 결과 모두 유사한 느낌의 재료들이 모여있는 것을 확인할 수 있다. coffee의 경우 espresso, coffee liqueur 등이 있으며, gochujang base의 경우 gochugaru, kimchi, korean chile flakes 등이 있다. 특히 이 ing2vec training은 cuisine의 정보를 가지고도 training 된 만큼, 많은 나라의 음식에서 등장할 수 있는 coffee보다 거의 korean cuisine에만 등장할 gochujang base와 관련 재료들이 훨씬 높은 cosine similarity를 가지고 잘 모여있는 것을 확인할 수 있다.

icecream+coffee
Top 10 Closest Ingredients to ‘Ice cream + Brewed Coffee’

 위 결과는 ice cream과 brewed coffee의 벡터 두개를 합친 벡터에 대해 가장 가까운 10개의 ingredient를 확인한 결과이다. 원래의 두 재료가 1, 2위이며, 3위에는 ‘coffee ice cream’ 재료가 있다. 즉, 벡터를 수치화하여 더해서 새로운 벡터를 만들어도 새로운 재료의 특징을 잘 나타낼 수 있다는 결과를 확인한 것이다(물론 모든 경우에 대해 좋은 결과가 표현되는 것은 아니었다).

Methodology Part #2

ing2vec을 통해 ingredient 자체를 벡터화하는 데에 성공하였으니, 남은 과제는 이를 이용하여 요리를 분류하는 것이다. 문제는 각각의 재료의 특성을 반영하여 어떤 ‘재료의 목록’에 대한 일정한 길이의 벡터를 만들어야 하는데, 이를 정확하게 표현할 수 있는 방법에 대해 고민하고 이것저것 실험해보았지만 딱히 좋은 결과를 얻지는 못했다. 랜덤하게 특정 갯수의 재료를 뽑아서 긴 벡터를 만들고, 이를 이용하여 Simple Deep Layer Network를 만들고 실험해보았으나 이 모델은 학습 시간이 너무 길었고, 기대에 비해 좋은 결과를 얻지 못했다. 그렇다고 각 재료들에 대한 weight를 산정하여 선형적으로 더하기에는 각 재료들에 대한 weight를 얻을 적절한 방법이 떠오르지 않았으며, 각 음식마다 재료가 차지하는 비중이 크게 다를 수 있기 때문에 이 방법은 일단 배제하였다. 결국 최종적으로는 단순히 들어가는 재료들의 벡터들을 다 더하되, 너무 자주 나타나거나 sugar, salt 등의 단순한 조미료, 향신료 등은 weight를 작게 주었다. 또한, 특정 cuisine에서 자주 나타나는 일부 재료들은 weight를 크게 주어서 더해주었다. 이 vector를 같은 norm을 가지도록 normalize해준 벡터를 가지고 특정 ‘재료의 목록의 벡터’를 만들어서, 이를 이용하여 분류를 진행하였다.

분류기로 처음에 사용한 방법은 Deep Layer Network로서, 3-hidden layer짜리 Deep Network를 만들어준 뒤 Leaky ReLU, DropConnect를 적용하여 학습을 시켜주었다. 반면, 40 epoch 정도 지났음에도 불구하고 성능이 72.3%정도밖에 나오지 않았다. 이에 접근법을 달리 생각해보았는데, 이 문제가 결국 확연히 특징이 나누어지는 그룹들을 분류하는 문제인 만큼 단순한 Deep Network보다는 localization 성향이 강한 모델이 성능이 잘 나올 수 있을것 같다고 생각되어 RBFN을 사용해보기로 하였다.

RBFN에서 커널로 Gaussian Kernel을 사용하고 실험해본 결과 커널의 수가 적었음에도 불구하고 Deep Network의 결과보다 좋은 성능을 얻을 수 있었다. 이에 커널의 수를 최대한으로 늘리고 실험하여, RBFN으로 얻을 수 있었던 최대의 결과를 마지막으로 제출하였다.

Result & Discussion

내가 얻을 수 있었던 최고의 성능은 78.8%로서, 총 1416개의 팀 중 560위를 하였다. 1위 팀의 성능은 83.2%로, 나의 성능과 4.4% 정도의 차이가 난다. 솔직히 생각했던 것에 비해 성능이 많이 나오지 않아 다소 실망하긴 했다. 80% 이상의 성능을 얻고 싶었는데, 열심히 이것저것 실험해보았지만 결국 실패했다. 시간이 더 있었고 더 여유롭게 실험할 수 있었다면 80% 정도 성능은 얻을 수 있지 않았을까라고 위로를 하고싶다.

내가 진행한 것 중에 가장 미흡한 부분이 Preprocessing 부분이었던 것 같다. 시간이 많이 없다는 촉박한 느낌에 일단 모델부터 생각해야한다는 마음가짐으로 임했었는데, 일부 상위 순위를 얻은 참가자들의 방법을 보니 재료 이름을 정리하고, 세공하는 데에 많은 공을 들이고 실질적인 분류는 이미 있는 패키지들로 진행하는 방식을 사용했다. 나는 실질적으로 거의 Preprocessing을 진행하지 않아서, 이 부분에서 공을 들였다면 보다 성능이 나아지지 않았을까 싶다.

또 다른 참가자들이 분류기로 xgboost를 많이 이용하던데, 어딘가에서 분류 문제에서 실질적으로 성능이 가장 잘 나오고 가장 많이 이용하는 방법이 random forest라는 말을 얼핏 들은 것 같다. 다음에 분류 문제를 사용하는 대회에 참여할 일이 있다면 xgboost를 한번 사용해볼 계획이다.

이번 대회 및 다른 대회들의 결과를 보면서 느낀 점은 결국 어느 한계까지 이르렀을 때부터는 ensemble 방법을 이용하는 참가자가 많았다는 것이다. 내 개인적으로는 ensemble 하는 것은 아이디어나 아름다움이 있다기 보다는 계산량이나 물량으로 성능을 억지로 올리는 느낌이 들어서 싫지만 현장에선 이러한 방식으로 많이들 사용하는 것 같다. 또 ensemble 하기에는 현재 노트북으로 실험하고 있는 내 실험 환경이 따라주지가 않는데.. 본격적으로 데이터 사이언스를 제대로 해보기 위해서는 좋은 스펙을 갖춘 데스크탑을 사야되는 것인지 고민이 되기도 한다.

구현 코드는 Github의 내 Repository에서 확인할 수 있다.