[NLP | 논문리뷰] Distributed Representations of Words and Phrases and their Compositionality

Word2Vec의 후속 논문이라고 할 수 있는 논문은 word embedding을 진행할 때에 어떻게 하면 더욱 효과적으로 그리고 빠르게 학습을 시킬 수 있을까에 대한 논문이었다.

논문 자체에 개념들이 자세히 설명이 되지는 않아 이번에는 논문을 번역식으로 리뷰하기 보다는 중요 요점만 취합하고 등장하는 주요 개념들을 위주로 기록하고자 한다.

어떤 방식이 더 학습에 도움이 될지 아직은 잘 모르겠으나 여러 시행착오를 거치면 논문 학습에 더 단단해지지 않을까 싶다.

💡 전체 내용에 대한 요약

Skip-gram 논문이 등장한 이후 word embedding에 대한 시도는 더욱 활발해졌다. Skip-gram은 이전보다 단어들간의 구조적 그리고 의미적 관계를 학습시킬 수 있었으며 학습시킨 벡터는 이들을 표현해낼 수 있었고 학습 속도 또한 매우 빨랐다.

이러한 skip-gram을 보다 발전시키고자 해당 논문은 두 가지 부분에 집중했다. 첫번째로, 기존의 Skip-gram은 구(phrase)에 대한 학습을 진행하지 못했다. 기존의 논문에도 나타나있듯이 단어들을 각각의 객체로 인식되어 학습되었으며 New York처럼 각 단어의 조합을 통해 나타나는 단어들을 학습하는 것에 어려움이 있었다. 논문은 이를 보완하고자 구에 대한 학습 방법을 제시했다. 각 Phrase들을 하나의 토큰으로 분리하고 그것이 phrase인지 또는 단순한 단어의 조합인지(an apple처럼 의미 없는)를 구별해내도록 만들었다.

두번째로 단어들을 보다 잘 학습시키기 위해 기존의 Hierarchical Softmax 방식 이외에도 Negative Samplin(NEG)를 소개했다. 이를 통해 빈번하게 등장하는 단어들을 보다 잘 학습시키고 학습 속도를 더 빠르게 하도록 했다. 그리고 이는 더욱 정확한 word representation을 학습할 수 있다.

🛠 Skip-gram Model

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

이때 C는 우리가 예측할 target의 범위를 나타낸다. C의 크기가 클 수록 training의 결과는 더욱 좋아지지만 훈련에 소요되는 cost가 더욱 커지게 된다. 기본적인 Skip-gram model은 softmax 함수를 이용하며 수식은 아래와 같다.

학습을 통해 도출되는 $∇ log p(w_O|w_I )$ 는 W의 부분으로써 동작해서 학습이 되는 구조.

💡 Hierarchical Softmax

Full softmax의 근접하면서 연산을 효율적으로 할 수 있는 방법은 Hierachical Softmax를 이용하는 것이다. 기존의 softmax는 모든 확률값을 구한 후에야 조건부 확률을 구할 수 있다. 그러나 희소벡터인 one-hot vector의 연산에 있어서 필요없는 연산을 너무 많이 하도록 만든다.

이를 해소하기 위해 나타난 구조가 Hierarchical Softmax이다. 이 방법의 주된 이점은 신경망의 output node를 W에 대한 확률분포를 대신하여 log(W)에 대한 확률분포를 얻을 수 있다는 것이다.

Hierarchical softmax는 이진트리를 이용해서 W의 output node를 표현한다. 이때 트리의 각 노드의 leaf는 child node의 확률과 관련되어 있다. 이것은 단어의 임의의 확률을 정의하게 해준다. 수식은 아래와 같으며 해당 내용에 대한 것은 이전 포스트를 참고하자.

모든 조건에 대한 조건부 확률의 합은 1. 따라서 이진 트리에 각각의 노드로 흘러 가는 것에 대한 확률도 합이 1이어야 한다. 이를 통해 각 노드의 단어들을 찾으러 갈 때의 확률들을 고려해 찾아가게 되는 것이다. 그리고 그렇게 찾아 갈 때의 확률들을 곱해주어 조건부 확률로 환산하게 된다.

이것은 logW보다 크지 않은 컴퓨팅 비용을 통해 실행 될 수 있다. 본 논문에서는 Huffman tree를 이용했으며 빠르고 성능이 좋은 훈련 결과를 얻을 수 있었다.

💡 Negative Sampling

Hierarchical softmax의 대안으로 등장한 것은 Noise Constractive Estimation(NCE)이다. NCE는 로지스틱 회귀의 평균을 통하여 데이터와 노이즈를 구분할 수 있는 좋은 모델이라는 개념을 기반으로 나타났다. 또 다른 논문에서는 NCE와 유사하게 hinge loss를 이용하여 데이터와 noise를 구분하는 훈련 모델을 제안하였다.

NCE는 softmax 로그확률의 근사적인 확률을 최대화하하려 하지만 Skip-gram 모델은 오직 양질의 벡터 표현을 학습하는 것을 목표로 한다. 이에 따라 이들을 동시에 사용할 수 있으며 본 논문에서는 Skip-gram의 퀄리티를 보존하면서도 Noise를 분리하는 NCE를 효과적으로 사용할 수 있었다. 이러한 방법을 Negative Sampling(NCE)라고 칭하며 수식은 아래와 같다.

위 수식에서 좌측 $logP_n(Wo|WI)$는 Skip-gram의 objective를 대체하여 사용되며, 이는 입력 단어 $w_I$에 대해 positive sample $w_O$이 output일 확률을 최대화하려고 한다. 이때 조건부 확률이기에 곱으로 이용되어야 하지만 목적함수를 log로 고려해준다.

우측은 negative sample wi (i=1,...,k)에 대하여 negative sample $w_i$가 output이 될 확률을 최소화 하는 방향으로 학습한다. 이를 위해 내적의 결과에 -1을 곱하여 sigmoid 함수를 적용한다.

헷갈릴 수 있는 부분이기에 조심해야 한다.

Negative sampling과 NCE의 주된 차이점은 NCE는 noise의 분포의 수치적인 확률과 sample이 모두 필요한 반면, Nagetive sampling은 오직 sample만 필요하다는 것이다. 반대로 NCE와 NEG 모두 parameter와는 관련이 적은 noise에 대한 확률분포를 가지고 있다.

더 알고 싶다면 아래 링크 참조

https://www.kdnuggets.com/2019/07/introduction-noise-contrastive-estimation.html

💡 Subsampling of Frequent Words

사실 상 모든 문장과 문서에서 자주 등장하는 단어는 별로 의미가 없다. a, the, in 과 같은 것들은 단어간의 관계에도 큰 영향을 주지 못하기 때문이다. 즉, France와 Paris의 관계보다 France와 the의 관계는 관계성이 낮지만 그 빈도는 더 크다.

이를 보완하기 위해 Subsampling 기법은 더 많이 발생하는 조합에 대해서 상관관계를 만드는데 있어 더 낮은 가중치를 부여한다. 이를 통해 빈번하게 등장하는 단어는 train에 있어서 큰 변화를 주지 못하도록 만든다. 수식은 아래와 같다.

f(wi)는 단어 w의 frequency이며,  t는 threshold로 hyper parameter 이다. 따라서 각 단어 w_i가 subsampling 될 확률은 frequency에 비레하며, frequency가 매우 높은 단어들은 subsampling 과정을 통하여 샘플링 될 확률이 감소하게 된다. 이는 결과적으로 덜 발생하지만 중요한 단어의 representation quality를 개선하는 결과로 이어지게 된다.

💡 Learning Phrase

많은 구(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를 형성 할 수 있게 해주었다.

Skip-gram model을 통해 학습된 word and phrase representaion은 간단한 벡터간의 연산을 통해 정교한 유추가 가능하게 해주는 linear structure를 보여준다. Skip-gram representation은 각각 vector들의 element-wise 합을 통해 의미적으로 단어를 결합하는 것을 가능하게 해주는 또 다른 linear structure를 보여줍니다.

벡터의 부가적인 특성은 training의 objective 함수를 관찰하면 설명될 수 있다. word vector은 비선형적인 softmax의 input를 포함하며 선형적인 관계를 가지고 있다. 문장 안의 주변 단어를 예측하는 word vector의 훈련과정에서 단어가 나타내는 맥락의 분포를 표현 할 수 있게 된다. 즉, word vector의 학습은 단어들간의 관계에 대한 학습으로 주변 맥락과의 분포 표현도 가능하게 한다는 것이다.

이렇게 나타난 vector은 output layer의 결과와 로그연산으로 관련되어 있음으로, 두 단어의 합은 두 단어가 표현하는 context의 곱과 관련되어 있다. 즉, 단어간의 단순한 합을 통해 의미간의 연산이 가능해진다는 것이다.

곱셈(Product)는 여기서 AND연산으로 동작하게 됩니다. 단어간의 조합이 나타날 때, 두 벡터가 학습 시에 학습 데이터로 사용된 word vector가 빈번하게 등장한다면 결과 역시 높은 그 word vector 조합이 등장할 확률이 높아지게 된다. 따라서 "Volga River"가 "Russian"과 "river"라는 단어와 함께 같은 문장에서 자주 나타난다면, 관계에 대한 학습으로 이 두 단어 벡터의 합은 "Volga River"의 벡터에 가까운 특징 벡터를 만들게 된다.

🔔 Result

단어들간의 관계 학습

학습에 대한 결과는 두 가지로 나눌 수 있다. 먼저, 단어들의 관계성에 대한 개선이 있는가이다. 본 논문에서 소개된 NEG 방법을 포함해 NCE, Hierarchical Softmax 그리고 Subsampling 여부를 통한 성능 증진 여부이다.

평가는 word 벡터의 선형대수적 연산의 결과와 가장 cosine 거리가 가까운 vector를 찾는 것으로 평가된다. 이 Task는 크게 Syntactic analogies와 Semantic analogies(나라와 수도)같이 두 개의 카테고리로 이루어져 있다.

표에서 나타나듯이 NEG가 다른 모델보다 훨씬 단어들간의 관계를 학습하는데 성능이 좋았음을 알 수 있었다. subsampling을 통해서는 학습시간이 1/2배보다 더 많이 감소했으나 성능이 동일하거나 동일했다.

skip-gram의 선형적 변환이 vector의 표현에 더 적합하다고 얘기할 수는 있으나 Negative Sampling과 같은 비선형적 연산은 word vector의 선형적 구조 형성에 도움이 될 수 있다. skip-gram은 오직 선형변환만 사용하지만 NGE같은 경우 확률값을 찾아나가기 위해 sigmoid 함수 사용한다. 이는 확률값에 대해서의 사용이기 때문에 word vector의 선형성을 해치지 않으면서 조건부 확률을 더 정확하게 찾을 수 있음을 알 수 있었다.

Phrase에 대한 학습 성능

두번째로는 phrase에 대한 학습 성능이다. 이와 마찬가지로 각 모델에 대한 성능을 비교했다.

이 경우에는 놀랍게도 Hierarchical Softmax를 이용한 Huffman code가 subsampling을 이용하자 비약적인 성능 상승에 더불어 1위를 차지했다. 또한, NEG는 phrase가 얼마나 등장해야 학습에 넣을 것이냐에 해당하는 K 값에 상당히 민감하다는 것을 알 수 있었다.

✏️ 느낀점

해당 논문을 읽으면서 NEG, NCE에 대해 더 학습했는데도 부족한 느낌이 많이 들었습니다. 이 부분에 대해 추가적인 학습이 필요한 것 같습니다.

또한, word vector에 대한 연산이 training objective log이었기에 word vector들의 단순한 합만으로 또다른 의미가 도출된다는 것이 신기했고 이를 통해 phrase를 학습시켰다는 것이 인상 깊었습니다. 이러한 Word embedding이 어떻게 더욱 발전되었는지에 대해 궁금증을 일으켰습니다

참고 : https://yunmap.tistory.com/entry/%EB%85%BC%EB%AC%B8-Distributed-Representations-of-Words-and-Phrases-and-their-Compositionality-Tomas-Mikolov
https://supkoon.tistory.com/13
https://coshin.tistory.com/44
https://velog.io/@mingqook/Distributed-Representations-of-Words-and-Phrasesand-their-Compositionality
논문 링크 : https://arxiv.org/pdf/1310.4546.pdf