[논문리뷰] Efficient Estimation of Word Representations in Vector Space(Mikoloiv, Word2Vec)

Efficient Estimation of Word Representations in Vector Space

0. 들어가는 말

word2vec으로 잘 알려진 두 편의 논문 중 한 편입니다. 기존에 Neural NET Language Model과 Recuurnct Neural Net Languege Model 기반의 Word Representations의 시간복잡도를 분석하고 보다 더 효과적인 Word Representation 방법인 CBoW와 Skip-Gram을 제안하고 있습니다.

가장 인상적인 부분은 본 논문에서 제시하는 단어 표현의 방법으로 king - man + woman = queen 이러한 연산이 가능하다는 것입니다. 

 

1. Introduction

현재(논문 발표 당시 2013년) NLP 시스템에서 사용되는 단어표현 방법들은 단어를 atomic unit으로 다루었고, 개별적인 단어를 표현 할 뿐 단어간의 유사성을 표현하지 못 하였습니다. 대표적으로 통계적인 언어 모델링을 이용한 N-gram을 생각해 볼 수 있을 것입니다. 이러한 표현 방법은 방대한 양의 데이터에 대하여 굉장히 간결하게(적은 계산으로) 언어를 표현할 수 있다는 장점이 있습니다.

 

하지만 이러한 단순한 기술은 많은 task에 한계를 가지고 있습니다. 가령 특정 도메인에 한정된 데이터의 경우 성능은 고품질의 데이터 셋의 크기에 달려있습니다. 하지만 기계번역 분야에서 여전히 많은 언어들은 충분하지 못 한 크기의 말뭉치를 가지고 있습니다. 또한 이러한 상황에서 단순한 scale up은 의미있는 개선을 가져오지 못 합니다. 따라서 우리는 보다 더 advecned techniques을 필요로 합니다.

 

최근 몇 년동안 머신러닝 분야가 발전하면서, 커다란 데이터 셋에 대하여 복잡한 모델을 훈련시키는 것이 가능해졌습니다. 또한 그들은 일반적으로 단순한 모델보다 좋은 성능을 보이고 있습니다. 대부분 성공한 개념들은 단어들의 분산적인 표현을 이용하고 있습니다. 대표적으로 neural network language model은 n-gram model보다 좋은 성능을 보이고 있습니다.

 

1.1 Goals of the paper

본 논문의 목표는 방대한 양의 데이터 셋으로부터 고품질의 word vector을 표현하는 기술을 제인하는 것입니다. 본 논문에서는 여러 차원에서 단어의 유사성을 표현하는 방법을 제안하고 있습니다. 놀라운 것은 이 방법을 이용하면 단순한 vector offset연산으로 단어의 유사성을 표현 할 수 있습니다. 예를들어 vector(king) - vector(man) + vector(woman) = vector(queen)와 같은 연산을 할 수 있습니다.

 

Word의 선형회귀를 보존하는 새로운 모델을 개발함으로 벡터 표현의 정확성을 최대화하였다. 또한 본 논문에서는 문법적인 요소와 의미적인 요소를 모두 평가할 수 있는  종합적인 test set을 설계합니다. 게대가 훈련에 필요한 시간복잡도까지 논의하고 있습니다.

 

1.2 Previous Work

연속된 vector로 단어를 표현하고자 하는 연구는 긴 역사를 가지고 있습니다. Neural Network Language Model(NNLM)을 평가하기 위한 가장 유명한 모델 구조는 「A neural probabilistic language model. Journal of Machine Learning Research」에서 제안되었습니다. 해당 모델 구조에서는 linear projection을 이용한 neural network 순전파와 non-neural hidden layer에서 벡터 표현과 통계적인 language model을 연결하여 학습에 사용합니다.

 

또 다른 흥미로운 NNLM의 구조는 「Language Modeling for Speech Recognition of Czech」, 「NEURAL NETWORK BASED LANGUAGE MODELS FOR HIGHLY INFLECTIVE LANGUAGES」에서 발표되었습니다. 해당 논문들에서는 word vector를 처음으로 single hidden layer을 이용하여 학습하는 방법을 제안하고 있습니다. 또한 word vector는 full NNLM없이 학습됩니다. 본 논문의 작업에서는 이와 유사하게 간단한 모델을 이용하여 word vector를 학습하는 방법을 제안합니다.

 

2. Model Architectures

모델들의 다양한 타입은 잘 알려진 LSA와 LDA를 포함하고 있는 연속적인 단어 표현을 평가하기 위하여 제안되었습니다. 본 논문에서는 신경망에서 학습되는 이산적인 단어 표현에 집중하고 있습니다. 이것은 단어의 선형회귀를 LSA보다 잘 보존하는 성능을 보여주고 있습니다. 게다가 LDA는 큰 데이터 셋에 있어서 연산비용이 많이 드는 한계를 가지고 있습니다.

 

유사하게, 다른 모델들과 비교하여, 본 논문에서 훈련에 필요한 parameter의 수에 따른 계산복잡도를 정의한다. 그 다음 계산복잡도를 최소화 하면서 정확도를 최대화하기 위한 방법을 모색한다. 모든 모델에서 훈련의 시간 복잡도는 다음과 같은 요소에 비례한다.

O = E x T x Q

 

위 수식에서 E는 훈련의 epoch수, T는 training set의 word수, Q는 각 모델의 특성에 따라 결정된다. 일반적으로 E은3~50으로 , T는 10억 이상으로 선택된다. 모든 모델은 stochastic gradient descent와 backbpropagation으로 훈련한다.

 

2.1 Feedforward Neural Net Language Model(NNLM)

확률적 순전파 NNLM은 「A neural probabilistic language model. Journal of Machine Learning Research」에서 제안되고 있다. 이것은 input, projection, hidden, output layer로 구성되어 있다. Input layer에서는 N개의 previous word가 1-of-V의 코드로 인코딩 되어 표현된다.(이때 V는 전체 단어의 수이다.) Input layer는 Projection layer(P)로 projection 된다. P는 N x D차원을 가지고 있다. 

 

NNLM 구조는 projection과 hidden layer 사이의 연산이 복잡해지게 된다. N=10인 일반적인 선택에 대하여, projection layer(P)의 크기는 500~2000이고, hidden layer의 크기 H는 일반적으로 500~1000이 되게 된다. 게다가 hidden layer은 V차원을 갖은 output layer에 연결되게 된다. 따라서 연산 복잡도는 다음과 같이 된다.

 

Q = (N x D) + (N x H x D) + (H x V)

 

하지만 몇몇 실전적인 해결책에서는 이러한 시간 복잡도를 회피하기 위해 계층적인 Softmax를 사용하거나 훈련중에는un-nomalized model을 이용하기도 한다. 또한, 1-of-V encoding의 단어 표현을 효과적으로 하기 위해 binary tree를 이용하여 log(V)의 크기로 scale down 할 수 있다. 본 논문의 모델에서는 Huffman binary Tree를 이용하여 계층적인 softmax를 사용한다. Huffman Tree는 는 짧은 이진 코드로 단어의 빈도수를 표현 할 수 있고, Output layer의 수를 줄 일 수 있게 된다. 그럼에도 불구하고 N x H x D의 복잡성은 해결되지 않는다. 따라서 우리는 Hidden layer를 갖지 않은 모델은 모델을 제안 할 것이다.

 

2.2 Recurrent Neural Net Language Model(RNNLM)

RNNLM은 RNN을 이용하여 더욱 얕은 신경망을 이용하여 복잡한 페턴을 표현함으로 feedforward NNLM의 한계를 극복하고자 제안되었다. RNN을 이용한 model은 Projection Layer를 갖지 않는다. 오직 input, hidden, output layer만을 갖는다. 이러한 특별한 모델은 시간 딜레이를 이용하여 hidden layer가 자기 자신에 연결된다. 이것은 짧은 기간에 대한 기억을 갖을 수 있게 되고 hidden state에 대하여 과거 정보에 대한 기억을 가지고 현재 input의 정보를 update할 수 있게 도와준다. 

RNN 모델의 Training Complexity는 다음 수식과 같이 표현된다. 단어 표현 D는 hidden layer의 크기 H와 같게 된다. 

 

Q = (H x H) + (H x V) 

 

그리고 또 다시 binary tree를 이용하면 (H x V)는 (H x log(V))로 표현 할 수 있게 된다. 따라서 해당 모델의 주된 복잡도는 (H x H)항이 되게 된다.

 

2.3 Parllel Training of Neural Networks

방대한 크기의 데이터 셋에 대하여 모델을 훈련시키기 위하여, 분산 연산 framework DistBelief를 가지고 있다. 이 framework는 같은 모델에 대하여 복제본을 만들어 병렬적으로 실행된다. 각각의 복제본은 중앙의 server를 통하여 기울기 update가 동기화 된다. 이런 병렬적인 훈련을 위해서는 mini-batch의 비동기적인 기울기 손실을 Adagrad를 이용하여 최적화한다. 이 framework에서는 일반적으로 100개 이상의 복제본을 이용하게 되고, multi-core 연산을 수행하게 된다.

3. New Log-linear Models

이번 섹션에서는, 연산량을 최소화하면서 단어의 분산 표현을 학습할 수 있는 새로운 두 모델의 구조를 제안한다. 이전 섹션에서 주요한 점은 연산의 복잡성이 non-linear hidden layer 때문이란 것이다. 이러한 사실은  단어 표현의 정확도를 줄이더라도 더욱 효율적인 훈련이 가능한 모델에 대하여 연구의 필요성을 가져왔다.

본 논문에서 제안하는 새로운 모델의 훈련은 두 단계로 이루어진다. 첫째, 연속적인 word vector는 단순한 모델을 이용하여 학습된다. 그리고 그 위에 N-gram NNLM은 분산 단어 표현이 훈련된다. 이후 단어 벡터 학습에 중점을 둔 상당한 양의 작업이 있었지만, 이전 연구에서 에서 제안된 접근 방식을 가장 간단한 것으로 간주한다.

 

3.1 Continuous Bag-of Words Models(CBoW)

첫 번째로 제안된 CBoW model은 hidden layer가 제거되고 모든 단어가 projection layer를 공유하고 있는 형태의 feedforward NNLM과 유사하다. 모든 단어는 같은 position으로 projection 된다. 우리는 이러한 구조를 Bag of Word(BoW)모델이라 하는데 이전에 projection된 단어들은 영향을 미치지 못 한다. 게다가 우리는 또한 미래의 단어를 사용한다. 우리는 log-linear classifier를 4개의 과거 단어와 4개의 미래 단어를 input으로 사용하여 가운데 있는 현재 단어를 훈련하여 가장 좋은 성능을 획득한다.

훈련 복잡도는 다음과 같은 수식으로 표현될 수 있다.

 

Q = (N x D) + (D x log(V))

 

우리는 이러한 구조를 기존의 표준적인 BoW와 구분되는 CBoW라고 한다. 이것은 연속적인 분산된 문맥을 표현할 수 있게 된다. 모든 단어들이 동일한 weight matrix를 사용하여 input layer에서 projection layer로 projection되는 것에 주목해야 한다!

 

3.2  Continuous Skip-gram Model

두 번째 모델 구조는 CBoW와 유사하다. 하지만 문맥을 기반으로 현재의 단어를 예측하는 대신에 같은 문장 안에서 다른 단어들을 기반으로 단어의 분류를 최대화한다. 각각의 단어를 input으로 사용하여 정해진 범위들의 단어를 예측한다. 우리는 범위를  증가시킬 수록 word vector의 결과가 향상됨을 찾아냈다. 하지만 이것은 계산 복잡성 역시 함께 증가시킨다. 단어 사이의 거리가 멀수록 가까운 단어보다 적게 관련되어 있기 때문에 우리는 작은 weight를 거리에 따라 조절하며 training 할 수 있다.

Skip-gram의 훈련 복잡도는 다음과 같은 수식에 비례한다.

 

Q = C x (D + D x log(V))

 

이때 C는 단어간 거리의 최대값이다. 또한 본 논문에서는 C를 5로 선택하였다. 각각의 training word에 대하여 1~C 사이의 임의의 수 R을 선택하였고 R개의 과거단어와 미래단어를 현재 단어의 정답 label로 설정하였다. 이것은 (R x 2)의 단어 분류를 필요로하고 한다.

 

 

4. Results

다른 버전의 단어 벡터의 품질을 비교하기 위해, 이전 논문은 일반적으로 표를 사용한다. 예제 단어와 가장 유사한 단어를 보여주고 직관적으로 이해합니다. 프랑스와 이탈리아가 유사하다는 것을 보여주는 것은 그다지 어렵지 않지만 다른 나라들과도 유사하다는 것을 보여주는 것은 새로운 도전이 될 것이다. 또한, 우리는 이전의 관측을 통해 단어 사이에는 더 많은 유사성을 가지고 있다는 것을 알고 있다. 가령, big과 bigger의 유사성은 small과 smaller이 같은 유사성과 같을 것이다. 더 나아가 어떻게 small에 대하여 big-biggest와 같은 유사성을 갖은 단어를 찾을 수 있을까?

 

놀랍게도, 이 질문은 아주 단순한 대수적인 연산을 통해서 해결 할 수 있다. small에 대하여 big-biggest와 같은 유사성을 갖은 단어를 찾기 위해서는 X = vector(biggest) -  vector(big) + vector(small)을 연산하고 벡터 공간에서 X와 cosine 거리가 가장 가까운 단어를 찾으면 vector(smallest)를 구할 수 있다.

 

마지막으로, 본 논문에서는 많은 데이터를 가지고 훈련한 고차원의 word vector의 결과는 단어 사이의 매우 미묘한 의미적인 표현에 사용 할 수 있음을 밝혔다. 이러한 의미를 표현 할 수 있는 word vector는 NLP application의 성능을 향상시킬 수 있을 것이다. 

 

4.1 Task Description

word vector의 quality를 측정하기 위하여, 5개의 type의 의미적인 질의로 구성된 comprehensive test를 정의하였다. 두개의 type에 대한 예시는 아래 테이블에서 확인 할 수 있다. 8869개의 의미적인 질의와 10675개의 문법적인 질의로 이루어져있다.

각 카테고리의 질의는 두 단계로 이루어진다. (1) 유사 단어 쌍의 list를 수동으로 만든다. (2) 그 다음 질의의 커다란 list는 두 단어를 연결함으로 구성 할 수 있다. 예를들어 68개의 큰 미국 도시와 그 도시가 속한 주를 연결한다. 이러한 과정을 통해 약 2.5K개의 질의를 만들 수 있게 된다. 본 논문의 테스트 셋에서는 단일 언어로 구성된 단어만들 사용했고 New York과 같은 multi-word entity를 사용하지 않았다.

본 논문에서는 모든 타입의 질의를 통하여 정확도를 측정하였다. 질의는 closest word가 정확히 단어와 일치할 때만 정답이라고 가정하였다. 동의어 역시 오답으로 측정되었다. 이것은 100% 일치가 불가능하다는 것을 의미한다.

4.2 Maximization of Accuracy

우리는 word vector training에 Google News Corpus를 사용하였다. 이 Corpus는 약 60억개의 토큰으로 구성되어 있다. 

본 논문의 실험에서는 빈도수가 높은 10만개의 단어로 단어의 수를 제한하였다. 분명하게 우리는 최적화 문제에 대하여 시간적인 제약에 직면하게 된다. 즉, 더 많은 데이터와 더 많은 차원의 벡터로 훈련하는 것을 기대 할 수 있다는 것이다. 가장 좋은 모델을 선택하기 위하여 자주 쓰이는 3만개의 데이터에 대하여 sub set을 구성하여 훈련을 진행하였다. 다음 표는 CBOW 구조의 서로 다른 word vector 차원과 훈련 data set의 크기에 따른 결과를 보여준다.

이 결과는 벡터의 차원과 훈련 데이터를 키우면 점점 정확도가 향상됨을 보여주고 있다. 따라서 벡터의 차원과 훈련 데이터의 크기를 함께 키워야만한다. 

실제 실험에서는 3epoch과 0.025의 learning rate hyper-parameter로 하여 stochastic gradient descent과 역전파를 이용하여 훈련하였다.

 

4.3 Comparsion of Model Archtectures

우선적으로 서로 다른 모델을 비교하기 위하여 똑같은 데이터와 모든 모델을 640차원의 word vector로 맞춰서 실험하였다. 더 나아간 실험에서는 우리는 모든 Semantic-Syntactic Word Relationship test set을 사용하였다. 즉, 3만개의 단어 제한을 두지 않았다. 

다음의 표는 각 모델에 대하여 semantic/syntatic 정확도를 비교하고 있다.

다음으로, 본 논문에서는 오직 하나의 CPU를 사용하여 공적으로 사용 가능한 word vector들과 비교하여 평가하였다. 아래의 표는 결과를 비교하여 보여주고 있다.

CBoW 모델은 Google News data의 sub set으로 약 하루동안 training하였고 Skip-gram 모델은 약 3일동안 training하였다.

추가적으로 보고된 실험에서는 우리는 1epoch만을 이용하여 훈련하였다. 또한, learning rate를 선형적으로 줄여 나가며 트레이닝이 끝날시에는 learing rate가 0이 되게 하였다. 1epoch에 대하여 두 배 더 많은 데이터에 대하여 같거나 더 나은 성능을 보였다. 아래의 표는 그 결과를 비교하여 보여주고 있다.

4.4 Large Scale Parallel Training of Models 

앞에서 언급한 것과 같이, 본 논문의 실험에서는 분산 연산 framework인 DistBelief을 사용 하였다. Google News 60억개를 mini-batch 비동기화와 Adagrade를 이용하여 훈련하였다. 50~100개의 복제본을 이용하여 CPU의 갯수에 따른 훈련 결과는 아래의 표와 같다.

4.5 Microsoft Research Sententce Completion Challenge

Microsoft Sentence Completion Challenge는 최근에 소개된 advancing LM과 다른 NLP 기술에 대한 task 이다. 이 task는 1040개의 문장으로 구성되어 있으며 문장은 하나의 단어가 빠져있고 목표는 가장 일관성있는 단어를 선택하는 것이다. N-gram 모델, LSA-based 모델, log-bilinear 모델, combination of recurrent neural network의 결과는 이미 보고되어 있고 55.4%의 정확도를 보이고 있다. 본 논문에서는 Skip-gram 구조의 성능을 탐구하였다. 우선 640차원의 모델을 500만개 단어로 훈련하고 그 결과를 비교하였다. 

Skip-gram model은 LSA기반의 model보다 좋은 성능을 보이지 못하였다. 이전까지 가장 좋은 성능을 보인 RNNLMs의 결과와 weight 결합하였을 때 58.9%의 정확도를 보였다.

 

5. Examples of the Learned Relationships

아래의 표는 다양한 단어들의 관계를 보여준다.