[논문리뷰] Distributed Representations of Words and Phrases and their Compositionality(Word2Vec, Mikolov)

Distributed Representations of Words and Phrases and their Compositionality

Abstract

최근 소개된 Skip-gram 모델은 단어의 Syntactic, Sementic 관계를 효율적으로 표현 할 수 있는 모델이다. 본 논문에서는 벡터의 퀄리티와 training의 속도를 향상시키는 방안에 대하여 논의한다.  자주 사용되는 word에 대한 subsampling을 통해 상당한 속도 향상과 더욱 규칙적인 단어 표현을 할 수 있게 되었다. 또한 계층적인 softmax의 대안을 제시한다.

기존의 단어 표현의 한계는 단어 순서에 대한 표현과 관용구의 표현이 불가능하다는 것이었다. 가령, 'Canada'와 'Air'의 의미는 쉽게 결합되지 못 하고, 'Air Canada'의 의미를 얻지 못 하게 된다. 이러한 문제를 해결하고자 본 논문에서는 간단한 구문을 찾아낼 수 있는 방법을 제안한다. 그리고 잘 훈련된 vector가 관용구의 의미를 표현 할 수 있음을 보여준다.

 

1. Introduction

벡터 공간에서 단어의 분산적인 표현은 유사한 단어를 grouping 함으로 NLP Task에 성능을 높이는데 도움을 준다. 이러한 단어 표현의 역사는 <Learning representations by backpropagating errors>을 시작으로 <A neural probabilistic language model>에서는 통계적인 Language Modeling의 idea를 제시하기에 이끌었다. 

 

최근(논문 발표당시 2013년) <Efficient estimation of word representations in vector space>에서는 많은 양의 text data로부터 양질의 단어 표현을 할 수 있는 Skip-gram model이 제안되었다. 이전에 사용하던 word vector를 훈련시키기 위한 neural network architecture와는 다르게 Skip-gram은 행렬곱 연산을 수행하지 않는다. 이것은 훈련을 매우 효율적이게 만들어 준다. 최적화된 단일 기기에서 10억개 이상의 단어를 하루만에 훈련시킬 수 있게 되었다.

 

신경망을 이용한 단어 표현은 단어를 언어학적으로 매우 명확하게 encoding한다는 점에서 흥미롭다. 더욱 놀라운 점은 선형변환으로 표현이 가능하단 것이다. 가령, vector(Madrid) - vector(Spain) + vector(France)의 결과에서 가장 가까운 vector를 찾으면 vector(Paris)가 되고 다른 많은 단어들에 대해서도 이러한 벡터 연산을 적용 할 수 있게 되었다.

본 논문에서는 original Skip-gram model을 개선시킬 것이다. 우리는 빈도수가 높은 단어를 sub-sampling함으로 훈련의 속도를 2~10배 향상시키면서 빈도수가 적은 단어들의 표현에 대한 정확도를 높일 수 있었다. 추가적으로 본 논문에서는 이전에 사용되었던 더욱 복잡하던 계층적인 softmax대신에  <Noise Contrastive Estimation(NCE)>를 단순화 시켜 Skip-gram 모델 훈련에 사용함으로 더 빠르고, 빈도수가 높은 단어에 대하여 더 나은 표현이 가능함을 입증하였다.

 

단어 표현은 개별적인 단어를 결합하여 표현하지 못함으로 관용구(idiomatic phrases)의 표현이 불가능 하다는 한계를 가지고 있었다. 가령, 'Boston Globe'는 신문의 이름인데, 자연스럽게 'boston'과 'globe'의 의미를 결합하여 해당 의미를 표현 할 수 는 없다. 그럼으로 모든 관용구에 대하여 벡터 표현을 사용함으로 skip-gram model의 표현력을 더욱 향상시킬 수 있었다. 결합된 단어로 구성된 문장의 의미를 표현하기 위한 또 다른 기술은 recursive autoneconders를 사용하는 것이다. recursive autoencoders를 이용하여 word vector를 대신하여 phrase vector로 사용 할 수 있게 된다.

 

word 기반에서 pharse 기반으로의 확장은 상대적으로 단순하다. 우선 data-driven approach를 이용하여 다수의 phrases를 확인한다. 그리고 그 다음 우리는 pharases를 훈련과정에서 개별적인 token처럼 다룬다. phrases vector의 quality를 평가하기 위해서 word와 pharese를 모두 포함하고 있는 analogical reasoning task를 개발하였다.

 

마지막으로 우리는 단순한 vector의 덧셈으로 자주 의미있는 결과를 만들어 낼 수 있음을 알아냈다. 가령 vector(Russia) + vector(river)은 vector(Volga River)과 가까웠고, vector(Germany) + vector(capital)은 vector(Berlin)과 가까웠다. 이러한 결합은 명확하지 않은 언어에 대한 이해 정도를 수학적인 연산을 통해 표현 할 수 있음을 제안하고 있다.

 

2. The Skip-gram Model

Skip-gram의 training objective는 문장이나 문서에서 주변 단어들을 예측하는 단어 표현을 찾는 것이다. 더욱 명료하게 표현한다면, traning words w1, w2 ... wT에 대하여 Skip-gram의 objective는 log 확률의 평균을 최대화 하는 것이다.

이때 C는 training context의 크기를 나타낸다. C의 크기가 클 수록 training의 결과는 더욱 좋아지지만 훈련에 소요되는 시간이 더욱 커지게 된다. 기본적인 Skip-gram model은 softmax 함수를 이용하여 다음과 같이 수식화 할 수 있다.

2.1 Hierarchical Softmax

Full softmax의 근접하면서 연산을 효율적으로 할 수 있는 방법은 Hierachical Softmax를 이용하는 것이다. 신경망을 이용한 Language Modeling의 맥락에서 <Hierarchical probabilistic neural network language model>의 논문에서 해당 개념은 처음 소개 되었다. 이 방법의 주된 이점은 신경망의 output node를 W에 대한 확률분포를 대신하여 log(W)에 대한 확률분포를 얻을 수 있다는 것이다.

 

Hierarchical softmax는 이진트리를 이용해서 W의 output node를 표현한다. 이때 트리의 각 노드의 leaf는 child node의 확률과 관련되어 있다. 이것은 단어의 임의의 확률을 정의하게 해준다.

 

더 자세히는, 각 단어 w는 tree의 root로부터의 path를 얻어 닿을 수 있게 된다. n(w,j)를 root부터 w까지의 j번째 node라고 하고, L(w)를 path의 길이라고 하자. 즉, n(w,1) = root, n(w,L(w)) = w가 되게 된다. 이에 더하여 임의의 inner node n에 대하여, ch(n)은 임의로 고정된 n의 child이고 [[x]]는 x가 true이면 1 그렇지 않으면 -1의 값을 갖는다. 그렇다면 hierarchical sotfmax는 다음과 같은 수식에 의하여 정의될 수 있다.

이때 σ(x) = 1/(1 + exp(−x))이고, P(w|wI)의 총 합은 1로 확정할 수 있다. 이것은 logW보다 크지 않은 컴퓨팅 비용을 통해 실행 될 수 있다. 또한 skip-gram에서 각 단어 w에 대하여 두 개의 표현을 사용하기 위하여 Vw와 V'w를 이용한 표준적인 softmax 공식과는 다르게 Hierarchical softmax 공식은 각 단어에 대한 표현 Vw와 그의 모든 inner node n에 대하여 V'n을 표현 할 수 있게 된다.

 

Hierarchical Softmax에서 이용한 이러한 트리 구조는 성능 향상에 큰 기여를 하게 된다. <A scalable hierarchical distributed language model>에서는 트리 구조는 훈련 시간과 모델의 정확성에 큰 영향을 준다고 밝히고 있다. 본 논문에서는 Huffman tree를 이용하여 빈번하게 등장하는 단어에 대하여 짧은 코드로 빠르게 훈련 결과를 얻을 수 있었다. 

 

2.2  Negative Sampling

<Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics> Hierarchical softmax의 대안으로 Noise Constractive Estimation(NCE)가 소개되었고, <h. A fast and simple algorithm for training neural probabilistic language models>에서 language modeling에 적용되었다. NCE는 로지스틱 회귀의 평균을 통하여 데이터와 노이즈를 구분할 수 있는 좋은 모델이라는 것이 밝혀졌다. <A unified architecture for natural language processing: deep neural networks with multitask learning>에서는 NCE와 유사하게 hinge loss를 이용하여 데이터와 noise를 구분하는 훈련 모델을 제안하였다.

 

NCE는 softmax 로그확률의 근사적인 확률을 최대화하는 반면,  Skip-gram 모델은 오직 양질의 벡터 표현을 학습하는 것에 집중 할 수 있게 되었다. 그래서 본 논문에서는 Skip-gram의 퀄리티를 보존한 NCE를 자유롭게 단순화 할 수 있었다. 본 논문에서는 Negative Sampling(NCE)의 objective를 다음과 같이 정의하였다.

위 수식에서 logP(Wo|WI)는 Skip-gram의 objective를 대체하여 사용된다. 또한 Task는 noise분포 Pn(W)로부터 각 데이터의 K개의 negative sampling을 활용한 로지스틱 회귀를 이용하여 target data Wo를 구분하는 것이다. 본 논문의 실험에서는 작은 데이터 셋에 대해서는 K의 값이 5-20, 큰 데이터 셋에 대해서는 K의 값이 2-5가 가장 유용한 것을 밝혔다.

 

 

Negative sampling과 NCE의 주된 차이점은 NCE는 noise의 분포의 수치적인 확률과 sample이 모두 필요한 반면, Nagetive sampling은 오직 sample만 필요하다는 것이다. 그리고 NCE는 근사적으로 softmax의 log확률을 최대화하지만 이러한 특성은 본 논문에서 중요한 특성이 아니다.

 

NCE와 NEG 모두 parameter로부터 자유로운 noise에 대한 확률분포를 가지고 있다. 본 논문에서는 Pn(W)를 선택하기 위한 수를 조사하였고 unigram 본포 U(w)에서 3/4 지수승으로 늘어나는 것을 관찰하였다. 

 

2.3 Subsampling of Frequent Words

매우 큰 말중치 안에서, 수 억번씩 자주 등장하는 단어는 쉽게 과찰할 수 있다.(가령, 'a', 'the', 'in'). 이러한 단어들은 대게 드물게 등장하는 단어보다 적은 의미를 내포하고 있다. 예를들어 Skip-gram 모델에서는 'France'와 'Pairs'가 함께 등장 할때의 benefit을 'France'와 'the'가 함께 등장할 때의 benefit보다 더 크게 부여한다. 

 

드물게 등장하는 단어와 빈번하게 등장하는 단어의 가중치를 측정하기 위하여 본 논문에서는 간단한 subsampling방법을 이용하였다. 트레이닝 데이터 셋에 있는 각 단어 Wi에 대하여 다음 수식의 확률은 무시되게 된다.

위 수식에서 f(Wi)는 단어 Wi의 빈도수이고 t는 정해진 threshold이다.(일반적으로 10^-5) 본 논문에서 subsampling 공식을 선택한 이유는 t보다 빈도수가 큰 단어를 적극적으로 sampling할 수 있기 때문이다. 이러한 계층적인 subsampling에도 불구하고, 실제 실험에서 잘 동작함을 관측하였다. 가속화된 학습과 심지어는 드물게 등장하는 단어에 대한 정확도 향상까지 보여주었다.

 

3. Empirical Results

이번 섹션에서는 analogical reasoning task를 이용하여 Hierarchical Softmax(HS), Noise Contrastive Estimation, Negative Sampling, subsamping를 평가한다. task는 "Germany":"Berlin" :: "France" : ? 와 같이 구성되어 있고 해당 질문의 답은 vector(Germany) - vector(Berlin) + vector(France)의 결과와 가장 cosine 거리가 가까운 vector를 찾는 것으로 실행된다. 이것은 특별한 예로 정답은 Paris가 된다. 이 Task는 크게 Syntactic analogies(quick:quickly :: slow:slowly)와 Semantic analogies(나라와 수도)같이 두 개의 카테고리로 이루어져 있다.

 

Skip-gram을 training할 때는 큰 data set인 10억 개의 단어가 포함되어 있는 internal Google dataset을 이용하였다. 실험에서 5번 이하로 등장하는 어휘는 무시하여 약 672000개의 vocabulary를 얻을 수 있게 되었다. 다양한 Skip-gram의 성능은 Table1에 나타나있다. 

실험의 결과는 Negative Sampling은 Hierarchial Softmax보다 좋은 성능을 보이며, 심지어 Noise Cintrastive Estimation보다도 약간 더 나은 성능을 보였다. 빈번한 단어에 대한 subsamping은 training 속도를 향상시키면서 단어의 정확성 역시도 더욱 정확하게 만들었다.

 

4. Learning Phrases

앞서 논의한 바와 같이, 많은 구(Phrase)들은 개별적인 단어들의 결합으로 얻어질 수 없는 의미를 가지고 있다. Phrase에 대한 vector표현을 학습하기 위해서 본 논문에서는 먼저 다른 맥락에서는 자주 등장하지 않고 특정 맥락에서만 자주 등장하는 단어쌍을 표현했다. 가령 'New York Times", "Toront Maple Leafs"는 training data에서 unique한 토큰으로 대체되는 반면 "this is"와 같은 구는 그대로 남겨 두었다. 

 

 이러한 방법은 어휘의 크기를 크게 키우지 않으면서도 많은 reasonable phrases를 얻을 수 있게 해주었다. 이론적으로 Skip-gram model은 모든 n-gram에 대하여 훈련 할 수 있겠지만, 과도한 메모리 부하를 가져올 것이다. phrases를 text에서 구분하기 위한 많은 기술들이 이전에 개발되었다. 하지만 그러한 기술들은 본 논문의 작업의 범위를 넘어서게 된다. 따라서 본 논문에서는 data-driven approach를 대신 이용하여 uni-gram과 bi-gram을 이용하여 다음과 같은 점수를 이용하였다.

δ는할인 계수로 사용되며 매우 빈번하지 않은 단어로 구성된 너무 많은 구를 방지한다. threshold를 넘어선 score를 가진 bi-gram이 선택되고 그것은 phrase로 사용되게 된다. 전형적으로 2-4 pass를 넘어서면 threshold를 감소시켜 더 긴 Phrase를 형성 할 수 있게 해주었다. 이렇게 만들어진 Phrase에 대한 실험 결과는 다음의 표와 같다. 또한 이 데이터 셋은 web을 통하여 공개하였다.

4.1 Phrase Skip-Gram Result

앞선 실험에서 사용했던 뉴스 데이터와 동일한 데이터로 실험을 시작하였다.  우선적으로 우리는 phrase기반의 training corpus를 구성하였고, hyper-parameter를 바꿔가며 Skip-gram 모델을 훈련하였다. 이때 vector의 차원은 300, context size는 5를 사용하였다. 이 setting은 이미 이전에 좋은 성능을 보여주었으며, 빈번한 단어에 대한 subsampling의 여부와 관계 없이 Negetive sampling과 Hierarchical softmax를 빠르게 비교하게 해주었다. 결과는 table3에 정리되어 있다.

Negative Sampling의 결과는 k=5에서도 상당한 정확도를 보이지만, k=15를 사용하였을 때 더욱 향상된 성능을 보여준다. 놀랍게도 Hierarchical Softmax는 subsampling을 사용하지 않았을 때 더욱 낮은 결과를 보여주었으며, 최상의 결과는 빈번하게 사용하는 단어에 대하여 downsampling을 하였을 때 나타났다. 이것은 subsampling이 더욱 빠르면서 정확한 결과를 보여줄 수 있음을 시사하고 있다.

 

Phrase analogy task의 가장 좋은 결과는 훈련 데이터의 총량을 약 330억개의 단어로 증가시켰을 때 나타났다. 이때 hierarchical sotfmax를 사용하였으며 차원의 수는 1000과 문장의 전체 맥락정보를 모두 이용하였다. 이 모델은 72%의 정확도를 보였다. 66%의 정확도를 보였던 모델은 훈련 데이터의 총량을 60억개의 단어로 사용하였으며 이는 큰 데이터 셋이 정확도를 높이는데 중요하다는 것을 보여주고 있다.

 

서로 다른 모델에 대하여 어떤 다른 학습의 결과를 얻는지에 대한 통찰을 얻기 위하여 자주 사용되지 않은 Phrases의 근접한 이웃에 대한 정보를 수동으로 탐색하였다. Table4에 해당 결과가 나와있다. 이전의 결과들과 일관적으로 가장 좋은 결과를 보이는 것은 subsamping을 수행한 Hierarchical Softmax였다.

 

5. Additive Compositionality

본 논문에서는 Skip-gram을 이용한 단어나 구에 대한 표현이 단순한 벡터의 구조를 가지고도 analogical reasoning에서 정확한 성능을 보일 수 있는  선형적인 표현임을 입증하였다. 놀랍게도, Skip-gram의 표현은 의미있는 요소들의 결합을 벡터의 합으로 표현할 수 있음을 보여주고 있다. 이러한 현상은 Table5에 표현되어 있다.

벡터의 부가적인 특성은 training의 objective를 관찰하면 설명될 수 있다. word vector은 비선형적인 softmax의 input를 포함하며 선형적인 관계를 가지고 있다. 문장 안의 주변 단어를 예측하는 word vector의 훈련과정에서 단어가 나타내는 는 맥락의 분포를 표현 할 수 있게 된다. 이러한 값은 output layer의 결과와 로그연산으로 관련되어 있음으로, 두 단어의 합은 두 단어가 표현하는 context의 곱과 관련되어 있다. 곱셈(Product)는 여기서 AND연산으로 동작하게 됩니다. 높은 확률을 가지고 있는 두 벡터가 결합된다면 결과 역시 높은 확률을 가지고 되고, 다른 단어가 낮은 확률을 가지고 있다면 두 단어가 결합한 벡터 역시 낮은 확률을 가지게 됩니다. 따라서 "Volga River"가 "Russian"과 "river"라는 단어와 함께 같은 문장에서 자주 나타난다면, 이 두 단어 벡터의 합은 "Volga River"의 벡터에 가까운 특징 벡터를 만들게 됩니다.

 

6. Comparison to Published Word Representations

신경망 기반의 단어 표현은 많은 연구자들에 의하여 연구되었고 그 결과가 이미 공개되어 있다. <Efficient estimation of word representations in vector space>에서 이미 다른 연구들과 Skip-gram모델의 결과를 word analogy task와 비교하여 평가를 해놓았다.

 

학습된 vector의 quality의 다름에 대한 통찰을 얻기 위하여, Table6에서, 자주 사용되지 않은 word의 인접한 이웃들에 대한 실험적인 비굣를 보여주고 있다. 큰 말뭉치로 훈련된  Skip-gram 모델의 결과는 다른 단어 표현보다 더 나은 결과를 보여준다. 이 모델은 약 300억 개의 단어로 훈련을 시켰으며, 이는 일반적인 데이터보다 약 2~3배 많은 양이다. 놀랍게도 학습 데이터가 큼에도 불구하고 Skip-gram 모델의 훈련 시간은 이전의 모델들보다 더 빨랐다.

 

7. Conclusion

Skip-gram 모델에 대하여 단어와 구에 대한 분산적인 표현의 훈련의 방법을 보여주고, 이 방법은 선형적인 구조를 가지고서도 analogical reasoning에서 정확한 결과를 보여 줄 수 있는 가능성이 있음을 입증하였다. 이러한 방법은 CBoW모델의 훈련에도 사용될 수 있다.

 

본 논문에서는 계산적으로 효율적인 모델 아키텍처 덕분에 이전에 발표된 모델보다 더 많은 크기의 몇 가지 데이터에 대한 모델을 성공적으로 훈련시켰다. 이 모델은 word와 phrase의 표현의 quality를 크게 향상시킬 것이다. 또한 빈번하게 등장하는 단어에 대한 subsampling이 학습의 속도와 드물게 등장하는 단어에 대한 정확도를 높일 수 있음을 보여주었다. 본 논문의 또 다른 기여는 매우 간단한 Negative sampling을 이용하여 빈번하게 등장하는 단어들의 정확도를 높였다는 것이다. 

 

Task에 따라서 hyper-parameter와 model의 선택은 달라져야 하고, 본 논문의 연구진의 경험에 따르면 가장 중요한 요소들은 모델의 구조, vector의 크기, subsampling의 비율, window의 크기이다.

 

본 연구의 가장 흥미로운 결과는 단어의 벡터 표현은 단순하게 벡터를 더하여 할 수 있다는 것이다. Pharse의 표현을 학습하는데 있어서 또 다른 접근은 더욱 긴 text의 문장을 표현하면서 연산을 단순하게 하는 것이다. 본 논문의 작업에서는 재귀적인 벡터 연산을 이용한 근사적인 접근을 이용하여 이러한 결과가 가능함을 보여주었다.

 

본 논문의 실험에서 사용되었단 word, phrase 벡터는 web site에 공개되어 있다.