Word2Vec : Distributed Representations of Words and Phrases and their Compositionality

본 논문은 Word2Vec 1 : Efficient Estimation of Word Representations in Vector Space와 같은 해에 발표된 후속 논문입니다!
Skip-gram 방법론의 representation quality와 computatoin efficiency 개선을 목표로 하고 있습니다.

0. Abstract

최근 소개되었던 conti Skip-gram model은 대량의 정확한 구문 및 의미적 단어 관계를 효율적으로 표현할 수 있는 방법입니다. 본 논문에서는 벡터의 퀄리티와 training 속도를 향상시킬 수 있는 방안들을 말합니다.
자주 사용되는 단어에 대한 subsmapling으로 속도 향상과 더욱 규칙적인 단어 표현을 진행하고, hierarchival(계층적) softmax를 제시하며 기존 softmax의 대안을 말합니다.

hierarchival softmax(HS)?
계층적 소프트 맥스란 기존의 softmax의 계산량을 현저히 줄인 softmax에 근사시키는 방법론 입니다. 본 논문에서 skip-gram 방법으로 모델을 훈련시킬 때 negative sampling 방법과 함께 쓰입니다.
그렇다면 이 계층적 소프트맥스를 쓰는 이유는 무엇일까요?
우선 기존 softmax를 Word2Vec에 적용할 때의 문제점을 살펴보겠습니다.
기존의 softmax는 MNIST와 같은 간단한 데이터셋에는 output이 10개면 충분했지에 수월하게 적용이 가능했습니다. 하지만 Word2Vec의 훈련 시에는 output의 개수가 Vocabulary에 있는 단어의 개수로 적어도 십만 개이기 때문에 십만 번 softmax 진행시 십만 번 이상의 exponetial 연산이 요구되며, 이는 엄청난 computational cost를 요구합니다. 그렇기에 개선된 방법으로 hierarchival softmax를 제시하게 됩니다.

기존의 word representation은 단어 순서나, 관용구의 표현이 불가능했습니다.
ex) Air, Canada : 이 두 단어의 의미는 쉽게 결합되지 않으며, Air Canada 의 의미를 얻지 못 합니다.
이러한 문제점에 따라 본 논문에서는 텍스트에서 구문을 찾는 방법을 제시하고, 이렇게 잘 훈련된 vector가 관용구의 의미를 잘 표현함을 증명합니다.

1. Introduction

단어를 컴퓨터가 이해할 수 있게 벡터화하는 것은 필수적이며, 이를 어떻게 벡터화하느냐에 따라 NLP task의 성능 향상에 도움이 됩니다. Word2Vec과 관련한 워드 임베딩은 "Word2Vec을 이해하기 위한 내용(1) - 워드 임베딩"를 참고하시면 좋습니다.

최근(2013년) 많은 양의 text data로 부터 양질의 단어 표현을 할 수 있는 Skip-gram 모델이 제안되었는데, 이는 기존과 달리 행렬곱 연산이 필요없고 이에 따라 매우 효율적입니다. (최적화된 단일 기기에서 10억개 이상의 단어를 하루만에 훈련 가능)

논문에서는 신경망을 이용하여 계산된 단어 표현은 많은 언어적 규칙 및 패턴을 매우 명확하게 encoding한다는 점에서 흥미롭다고 했습니다. 더욱 놀라운 점은 선형변환으로 가능하다는 점입니다. 예를 들어 vec(Madrid) - vec(Spain) + vec(France)의 결과는 vec(Paris)와 유사한 벡터가 되고, 다른 많은 단어들에 대해서도 이런 벡터 연산을 적용할 수 있다고 했습니다.

* 위 그림은 Skip-gram의 인공신경망 구조

논문에서는 이 original Skip-gram model을 개선시켰으며, 빈도수가 높은 단어를 subsampling함으로 훈련의 속도를 높이고 빈도수가 적은 단어들의 표현에 대한 정확도를 높인다고 했습니다.

기존의 skip-gram model은 
'단어의 형태학적 특성 반영 불가', 
'분포 가설을 기반으로 학습하기에 단어 빈도 수의 영향을 많이 받아 희소한 단어를 임베딩 하기에 어려움',
'OOV의 처리가 어려움'
의 단점이 존재

이에 더하여 이전에 사용되었던 계층적 softmax 대신 Noise Contrastive Estimation(NCE)를 단순화하여 Skip-gram model 훈련에 사용함으로 더욱 빠르고, 빈도수가 높은 단어에 대해 더 나은 표현이 가능하게 합니다.

관용구를 표현하지 못 하는 문제에 대해서는 모든 관용구에 대해 벡터 표현을 사용함으로 skip-gram model의 표현력을 향상시켰습니다. 결합된 단어로 구성된 문장의 의미를 표현하기 위해서는 recursive autoencoders를 사용했고, 이를 이용하여 word vector를 대신하여 phrase vector로 사용할 수 있게 하였습니다.

word기반-> phrase기반 으로의 확장 :
①data-driven approach를 이용하여 다수의 phrases를 확인
②phrases를 훈련시키는 과정에서 개별적인 token처럼 다룸
=> phrases vector의 퀄리티를 평가하기 위해서 word와 phrase를 모두 포함하고 있는 analogical reasoning task를 개발하였음

마지막으로 단순한 vector의 덧셈으로 자주 의미있는 결과를 만들어 낼 수 있음을 알았다고 했는데, 예를 들어 vec(Russia)+vec(river)은 vec(Volga River)와 가까웠고 vec(Germany)+vec(capital)은 vec(Berlin)과 가까웠다고 합니다.

이러한 결합은 명확하지 않은 언어에 이해 정도를 수학적인 연산을 이용하여 표현할 수 있다는 점이 흥미로웠습니다..!

2. The Skip-gram Model

Skip-gram model의 training 목적은 문장 내 주변 단어들을 예측하는 단어 표현(벡터)을 찾는 것 입니다. 즉, 한 단어에 대해 주변 단어를 잘 표현할 수 있는 벡터를 찾는 것 입니다.
이를 수식적으로 말하자면 training words w1, w2, ..., wT에 대해 Skip-gram의 목적은 log(확률)의 평균을 maximize하는 것 입니다.
c는 training context의 size를 뜻하며, c가 커질수록 학습 결과는 좋아지지만 훈련 소요시간은 커지게 됩니다.

기본 Skip-gram model은 softmax를 이용하여 확률을 계산합니다.
vw와 v'w는 각각 입력과 출력 vector representation of w입니다. 분자는 input단어의 표현과 output단어의 표현의 내적의 exp이고, 분모는 모든 단어에 대한 input 단어 표현과의 내적의 exp sum 입니다.
W는 단어장에 있는 단어의 개수입니다.

Word2Vec을 이해하기 위한 내용(2) - Skip-gram model 에 더욱 상세히 적어 놓았습니다.

하지만 위에서 말한 softmax의 단점으로 인해 본 논문에서는 Hierarchical softmax를 사용합니다.

2.1 Hierarchical softmax

Full softmax에 근접하면서 연산을 효율적으로 진행하기 위해 Hierarchical softmax를 이용하게 됩니다. 기존의 softmax는 모든 확률값을 구한 후에야 조건부 확률을 구할 수 있습니다.

필요없는 연산을 너무 많이함을 막기 위해 이 방법이 나타났으며, 이 방법의 주된 이점은 신경망의 output node를 W에 대한 확률분포를 계산하여 log(W)에 대한 확률분포를 얻을 수 있다는 것 입니다.

Hierarchical softmax는 이진 트리를 이용하여 W의 output node를 표현합니다. 이때 트리의 각 노드의 leaf는 child node의 확률과 관련되어 있습니다. 이것은 단어의 임의의 확률을 정의하는데, 왼쪽과 오른쪽 중 어떤 자식(child)을 선택할지에 대한 확률입니다. 정답 leaf 단어가 있는 쪽으로 branch로 뻗어나갈 확률값을 최대화하도록 학습하게 됩니다.
Vw와 V'w를 이용한 표준적인 softmax와 달리 각 단어에 대한 표현 Vw와 그의 모든 inner node n에 대해 V'n을 표현할 수 있습니다.

Word2Vec을 이해하기 위한 내용(3) - Hierarchical softmax 에 예시와 함께 적어 놓았기에 읽으시면 도움이 될 것입니다!

2.2 Negative Sampling

Hierarchical softmax의 대안으로는 Noise Constractive Estimation(NCE)이 소개 되었습니다. NCE는 로지스틱 회귀의 평균을 통하여 데이터와 노이즈를 구분할 수 있는 좋은 모델이라는 것이 밝혀졌습니다. (또 다른 논문에서는 NCE와 유사하게 hinge loss를 이용하여 데이터와 noise를 구분하는 훈련 모델을 제안하였습니다)
(Word2Vec을 이해하기 위한 내용(4) - hinge loss : 힌지 손실)

NCE는 softmax 로그 확률의 근사적인 확률을 최대화하는 반면, Skip-gram model은 오직 양질의 벡터 표현을 학습하는 것에 집중합니다. 그렇기에 이들을 동시에 사용할 수 있으며, 본 논문에서는 Skip-gram의 퀄리티를 보존하며 Noise를 분리하는 NCE를 효과적으로 사용할 수 있었습니다. 논문에서는 이러한 방식을 Negative Sampling(NEG)이라고 하였으며, 수식은 아래와 같습니다.

수식에 대해 말하기 전에, Negative Sampling이 왜 사용되는지 이야기해 보겠습니다. 기존에는 W와 W' 모두 softmax를 취하고 전체 업데이트를 진행하였지만, Negative Sampling은 중심단어와 negative sample 몇 개에 해당하는 파라미터를 업데이트합니다.
예를 들자면 (김치,반찬) (김치,된장) (김치,식사) 의 조합을 업데이트 하기 위해서, 김치와 상관없는 폴란드 등과 같은 단어를 업데이트 해도 하지 않은 것과 별반 차이가 없을 것 입니다. 즉, 김치와 주변단어가 아닌 단어가 김치와 주변 단어인 단어보다 훨씬 많은데 이를 모두 업데이트 할 필요가 없다는 것 입니다.
따라서 김치와 연관된 단어는 positive sample로 두고, 연관되지 않는 단어 몇 개를 추출하고 이를 negetive sample로 두어 학습을 통해 파라미터를 업데이트합니다.

이제 다시 수식을 살펴보겠습니다.

좌측의 logPn(wo|wI)는 Skip-gram의 objective를 대체하여 사용되며, 이는 입력단어 wI에 대해 positive sample wo가 output일 확률을 최대화하려고 합니다.
이 때 조건부확률이기에 곱으로 이용되어야 하지만 목적함수를 log를 취해 고려해줍니다.

우측은 negative sample wi에 대해 wi가 output이 될 확률을 최소화하는 방향으로 학습을 진행합니다. 이를 위해 내적의 결과에 -1을 곱하여 sigmoid를 적용합니다.

Negative sampling과 NCE의 주된 차이점은 NCE는 noise의 분포의 수치적인 확률과 sample이 모두 필요한 반면, Negative sampling은 오직 sample만 필요하다는 것입니다.

Negative Sampling 단어는 전체 corpus 중 문장에 사용되는 비중이 높은 단어를 우선적으로 가중치를 주어 선별합니다. 특정 단어가 선별될 확률은 아래와 같습니다.

wi : i번째 단어 , f(wi) : 해당 단어의 빈도 , 3/4 : 성능 우수
P(wi) : wi가 나타날 확률 = 출현횟수 / 전체 corpus 수

Q) 그렇다면 Negative sample은 몇 개를 선별하는게 효과적일까?
정답은 데이터셋의 크기에 따라 다릅니다. 학습 데이터 셋이 작을 때는 5~20개 사이의 Negative sample을 추출하는 것이 효과적이고, 클 경우에는 2~5개 사이의 sample을 선정하는 것이 효과적이라고 합니다.

Word2Vec 성능은 아래와 같습니다.
CBOW < Skip-gram < Skip-gram with Negative Sampling(SGNS)
그렇기에 흔히 Word2Vec에서 Skip-Gram방법을 사용한다고 하면 Negative sampleing이 적용된 SGNS를 사용한다고 생각하시면 됩니다.

2.3 Subsampling of Frequent Words

매우 큰 말뭉치 안에서 굉장히 자주 등장하는 단어들이 있습니다.(a, the, in 등) 이런 단어들은 적은 의미를 내포하며 단어간의 관계에 큰 영향을 주지 못 합니다. 예를 들어 France와 Paris의 관계보다 France와 the의 관계의 관계성이 낮지만 빈도는 더 큽니다.

이를 보완하기 위해 말뭉치에서 자주 등장하는 단어는 학습량을 확률적인 방식으로 줄이는 Subsampling 기법을 이용합니다. Subsampling 기법은 더 많이 발생하는 조합에 대해서 상관관계를 만드는데 있어 더 낮은 가중치를 부여합니다.(등장 빈도가 많은 만큼 업데이트 될 기회도 많기 때문입니다)
이를 통해 i번째 단어 wi를 학습에서 제외시키기 위한 확률을 아래 수식과 같이 정의했습니다.

f(wi) : wi가 말뭉치에 등장한 비율 (단어 wi의 빈도수/전체 단어수)
t : threshold (일반적으로 10^-5)

예를 들어 '은','는'과 같은 빈도 높은 조사의 빈도 확률이 f(wi)=0.01로 매우 높다고 한다면, P(wi)가 0.9684 나 되어서 100번의 학습 기회 가운데 96번 정도는 학습에서 제외하게 됩니다.(96.84%로 제외시켜라) 반대로 등장 비율이 적어 P(wi) 가 0에 가깝다면 해당 단어가 나올 때 마다 빼놓지 않고 학습을 하게 됩니다.
이렇게 Subsampling은 학습량을 효과적으로 줄여 계산량을 감소시킵니다.

3. Empirical Results

이 section은 Hierarchical Softmax(HS), Noise Contrastive Estimation(NCE), Negative Sampling, Subsampling을 평가합니다. task는 "Germany":"Berlin" :: "France" : ? 로 구성되어 있고, 이에 대한 정답은 vec(Berlin) - vec(Germany) + vec(France) 의 결과와 가장 cosine 거리가 가까운 vector를 찾는 것 입니다.

개인적인 생각으로는 vec(Berlin) - vec(Germany) = '수도라는 정보가 담긴 벡터' 인 것으로 유추되며, 이 정보를 France에 더하여 France 수도인 vec(Paris) 가 정답이 되는 것으로 생각됩니다.

이 task는 
1) Syntactic analogies(quick:quickly :: slow:slowly)
2) Semantic analogied(나라와 수도)
로 두 개의 카테고리로 이루어져 있습니다.

Skip-gram을 training할 때 10억 개의 단어가 포함되어 있는 internal Google dataset을 이용하였고, 실험에서 5번 이하로 등장하는 어휘는 무시하여 약 672,000개의 단어를 얻을 수 있었다고 합니다. Skip-gram의 성능은 아래와 같습니다.
실험의 결과로는 Negative sampling이 가장 좋았으며, Subsampling 진행시 개선된 성능을 보였습니다.

4. Learning Phrases

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

이 방법은 어휘의 크기를 크게 키우지 않으면서도 많은 reasonable phrases를 얻을 수 있게 해주었습니다. 구를 text에서 구분하는 많은 기술이 존재하지만, 본 논문에서는 아래와 같은 방법을 이용하였습니다. ( data-driven approach 대신 uni-gram과 bi-gram을 이용하여 socre를 구성)

매우 빈번하지 않은 단어로 구성된 구는 너무 많습니다. 그렇기에 이 스코어에서 델타(할인 계수)로 너무 많은 구를 방지합니다.
threshold를 넘어선 스코어를 가진 bi-gram이 선택되고 그것을 phrase로 사용합니다. (전형적으로 2~4pass를 넘어서면 threshold를 감소시켜 더 킨 Phrase를 형성할 수 있게 하였습니다.) 이런 방법으로 만들어진 Phrase에 대한 실험 결과는 아래와 같습니다.

5. Additive Compositionality

Skip-gram을 이용한 단어나 구에 대한 표현이 단순한 벡터 구조를 가지고도 analogical reasoning에서 정확한 성능을 보일 수 있는 선형적인 표현임을 입증하였습니다. Skip-gram의 표현은 의미있는 요소들의 결합을 벡터합으로 표현할 수 있음을 보이며, 이러한 현상은 아래 표와 같습니다.
이 벡터의 부가적인 특성은 training의 목적을 관찰하면 설명할 수 있습니다. word vector는 비선형적인 softmax의 input을 포함하여 선형적인 관계를 갖고 잇습니다. 문장 안의 주변 단어를 예측하는 word vector의 훈련과정에서 단어가 나타내는 맥락의 분포를 표현할 수 있게 되는 것 입니다. 이러한 값은 output layer의 결과와 "로그 연산"으로 관련되어 있으므로, 두 단어의 합은 두 단어가 표현하는 context의 곱과 관련되어 있습니다. 곱셈은 여기서 AND연산으로 동작하게 됩니다. 높은 확률을 가지고 있는 두 벡터가 결합된다면 결과 역시 높은 확률을 가지고 되고, 다른 단어가 낮은 확률을 가지고 있다면 두 단어가 결합된 벡터 역시 낮은 확률을 가지게 됩니다. 따라서 "Volda River"가 "Russian"과 "river"라는 단어와 함께 같은 문장에서 자주 나타난다면, 이 두 단어의 벡터 합은 "Volga River"의 벡터와 가까운 특징 벡터를 만들게 되는 것 입니다.

7. Conclusion

Skip-gram model은 단어와 구에 대해 부난적인 표현의 훈련 방법임을 보여줍니다. 또한 이 방법은 선형적인 구조를 가지고도 analogical reasoning에서 정확한 결과를 보여 줄 수 있는 가능성이 있음을 입증하였습니다.

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

본 논문의 연구진의 경험에 따르면 가장 중요한 요소들은 모델의 구조, vector의 크기, subsampling의 비율, window의 크기라고 했습니다.

본 연구의 가장 흥미로운 점은 word vector에 대한 연산이 training objective log이었기에 word vector들의 단순한 합만으로 또 다른 의미가 도출된다는 것이었습니다.

참고 : https://real-myeong.tistory.com/78
https://coshin.tistory.com/44