논문 리뷰 - Word2vec (2)

04 Jul 2023 in Studying ML/DL

Distributed Representations of words and phrases and their compositionality

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

해당 논문은 word2vec 의 후속 논문으로써 vector 품질과 학습 속도를 높인 방법에 대해 소개하고 있다. 소개는 간단히 여기서 마무리하고 논문을 리뷰해 보도록 하자.

• 🌟 Abstract
• 🎟️ Introduction
• 🕹️ Skip-gram Model
  • ✂️ Hierarchical Softmax
  • 🪚 Negative Sampling
  • 🏑 Subsampling of Frequent Words
• 🏎️ Learning Phrases
• ⚙️ Additive Compositionality
• 🚀 Conclusion

🌟 Abstract

해당 논문 이전에 발표한 논문에서는 continuous Skip-gram 모델을 통해 고품질의 distributed vector representations 을 학습하는 방법에 대해 설명했다. 이 논문에서는 벡터의 퀄리티와 학습 속도를 높일 수 있는 방법을 소개한다.

• Subsampling of the frequent words
• Instead of Hierarchical Softmax, use Negative Sampling

또한 관용어적으로 맞지 않는 단어들의 조합도 표현할 수 있는 phrase vector 를 소개한다. (Air Canada 처럼 서로 연관 없는 단어들이 만난 단어들)

🎟️ Introduction

이전 논문에서 소개한 Skip-gram 모델같은 경우 굉장히 많은 양의 데이터를 통해 고품질의 words’ representation vector 를 학습시킬 수 있었다고 한다. 이러한 학습이 가능했던 이유는 여타 다른 NNLM 모델들과 다르게 dense matrix multiplications 가 포함되지 않았기 때문이라고 밝히고 있다.

이 논문에서는 이 Skip-gram 의 아래와 같은 개선점을 통해 더 빠르고 정확해진 모델을 보여주고자 한다.

• Subsampling of frequent words
  • 이 방법을 통해 약 2~10배 속도 향상과 빈도 횟수가 낮은 단어에 대한 정확도 향상을 이룸
• Noise Contrastive Estimation(NCE) / Negative Sampling
  • 이 방법을 통해 속도 향상 및 자주 등장하는 단어에 대해 더 좋은 품질의 vector 생성 가능
• Phrase Vector 학습
  • 자연스럽지 못한 단어 조합들의 대한 vector 학습에 한계가 있음
  • 따라서 phrase 의 representation 을 담은 vector 를 활용해 Skip-gram 모델이 조금 더 풍부해질 수 있었음
  • ex) vec(“Montreal Canadiens”) - vec(“Montreal”) + vec(“Toronto”) = vec(“Torontor Maple Leafs”)

그렇게 이 방법을 통해 간단한 vector addition 에서 유의미한 결과를 볼 수 있다고 한다. 예를 들면, vec(“Russia”) + vec(“river”) 는 vector(“Volga River”) 와 같이 표현이 된다고 한다. 이러한 합성성은 당연하지 않은 언어의 이해가 word vector representation 의 간단한 계산으로 보일 수 있다는 것이다.

🕹️ Skip-gram Model

Objective Function : 중심 단어가 주어졌을 때 주변 단어를 예측할 확률의 log값 maximize

\[\frac{1}{T} \sum_{t=1}^{T} \sum_{-c \leq j \leq c, j \neq 0} \log p\left(w_{t+j} \mid w_{t}\right)\]

중심 단어를 기준으로 c 개의 단어를 살펴봄

그렇다면 해당 log 값은 어떻게 정의될까? \[p\left(w_{O} \mid w_{I}\right)=\frac{\exp \left(v_{w_{O}}^{\prime}{ }^{\top} v_{w_{I}}\right)}{\sum_{w=1}^{W} \exp \left(v_{w}^{\prime}{ }^{\top} v_{w_{I}}\right)}\]

Skip-gram model with softmax function

I 번째 단어에 대한 벡터와의 내적 연산값은 exp 값이 모든 단어에 해당하는 내적값의 exp 합으로 나눈 것으로 계산한다.

위 식에서 눈여겨 봐야할 점은 \(W\) 이다. \(W\) 는 vocab 의 개수인데 이 식이 실용적이지 못한 이유는 softmax 를 계산하는 것이 이 \(W\) 에 비례하기 때문이다. 보통 \(W\) 는 \(10^{5}-10^{7}\) 정도 된다고 한다.

✂️ Hierarchical Softmax

이전 논문에서는 연산량이 많은 softmax 를 해결하기 위해 단어를 Huffman Binary Tree 를 이용해 구성하고 그에 따라 Hierarchical Softmax 를 이용하였다. 그에 따라 기존 \(O(W)\) 만큼 걸리던 time complexity 를 \(O(log_2(W))\) 만큼 줄일 수 있었다.

하지만 그 방법에 대해 정확히 제시되지 않았는데 이번 논문을 통해 알아보도록 하자.

Hierachical Softmax Example

먼저 알고 가야하는 점들이 있다. 나는 논문을 읽을 때 이 부분에서 오랜 시간 걸렸었다.

• \(n(w, j)\) 는 w를 루트로 한 트리의 j 번째 노드
• \(L(w)\) 는 root 부터 w 까지의 길이
• \(ch(n)\) 는 n 의 child
• \([\![x]\!]\) 는 x 가 True 라면 1 아니면 -1
• 기본적으로 자식 노드는 왼쪽 자식 노드를 의미

이 부분을 상기하면서 아래 식을 보도록 하자. \[p\left(w \mid w_{I}\right)=\prod_{j=1}^{L(w)-1} \sigma\left([\![n(w, j+1)=\operatorname{ch}(n(w, j))]\!] \cdot v_{n(w, j)}^{\prime}{ }^{\top} v_{w_{I}}\right)\]

Hierarchical Softmax Equation

위 그림을 같이 보면서 설명하면 트리는 vocabulary 크기만큼 leaf 노드를 가진다. 저 식에서 중요한 건 안에 있는 일종의 if 문이다.

• j+1 번째 노드가 j번째 노드의 자식이라면 (왼쪽) : 중심 단어와 그 해당 주위 단어의 내적값
• j+1 번째 노드가 j번째 노드의 자식이 아니라면 (오른쪽) : -(중심 단어와 그 해당 주위 단어의 내적값)

해당 확률값을 maximize 한다는 것을 잊지 말자

이렇게 구성을 하게 되면 연산 횟수가 L(w)에 근사하게 되고 이는 트리의 높이이기에 \(log_2(V)\) 가 된다는 것이다. 한마디로 계산 효율성을 극대화 한 것이다. 또한 자주 등장하는 단어의 노드는 루트 노드로부터 거리를 가깝게 하여 더 빠른 계산이 가능하도록 하였다고 한다. 마지막 장점은 확률값 계산에 참여한 노드만 업데이트 되어 시간을 아낄 수 있다.

🪚 Negative Sampling

Hierarchical Softmax 의 대안으로 Noise Contrastive Estimation(NCE) 를 사용할 수 있다. 처음 보는 용어인데 이것이 무엇일까?

• CBoW, Skip-gram 모델에서 사용하는 비용 계산 알고리즘
• 전체 데이터셋에 Softmax 함수를 적용하는 것이 아닌, 샘플링으로 추출한 일부에 대해서만 적용
• NCE 를 사용할 경우 문제를 실제 context 에서 얻은 데이터 (\(X\)) 와 context 에 속하지 않는 단어들에서 뽑은 데이터 (\(Y\)) 를 구별하는 이진 분류 문제로 바꿀 수 있음
• k개의 대비되는(contrastive) 단어들을 noise distribution에서 구해서 (몬테카를로) 평균을 구하는 것이 기본 알고리즘

NCE 는 log 확률을 maximize 하는데 초점을 맞추고 있는 반면 Skip-gram 모델은 오직 고품질의 벡터를 학습하는데 초점을 맞추고 있다. 그렇기에 본 논문은 벡터의 품질은 유지하면서 NCE 를 간소화할 수 있었다고 한다. 이렇게 간소화된 형태를 Negative Sampling 이라 한다. \[\log \sigma\left(v_{w_{O}}^{\prime}{ }^{\top} v_{w_{I}}\right)+\sum_{i=1}^{k} \mathbb{E}_{w_{i} \sim P_{n}(w)}\left[\log \sigma\left(-v_{w_{i}}^{\prime}{ }^{\top} v_{w_{I}}\right)\right]\]

Negative Sampling

논문에서는 Skip-gram 의 objective 함수에 있는 \(\log P\left(w_{O} \mid w_{I}\right)\) 식을 모두 위 식으로 교체하였다고 한다.

• 좌측 term : 입력 단어 \(w_I\) 에 대하여 positive sample \(W_O\) 가 output 일 확률을 Maximize
• 우측 term : Negative Sample 에 대하여 \(W_I\) 가 output 이 될 확률을 최소화 → 내적 결과에 -1 을 곱함
  • Noise 단어들의 unigram 확률 분포인 \(P_n(w)\) 를 통해 sampling
  • Unigram Distribution은 단어가 등장하는 비율에 비례하게 확률을 설정하는 분포
  • 본 논문에서는 unigram dist. 에 3/4 승 한 분포(\(U(w)^{3 / 4} / Z\))가 실험적으로 가장 좋다고 함

그렇다면 NCE 와 NEG 의 차이점은 무엇일까?

• NCE : sample 과 noise distribution의 확률값 모두 필요
• NEG : sample 만 필요

NCE 같은 경우 softmax 의 log 확률을 maximize 하는 것이 목표였다. 즉 잘 분류하고자 하는 것이 목표였으나 해당 논문의 주축인 word2vec 같은 경우 word representation 의 퀄리티를 높이는 것을 목표로 삼았기에 Negative Sampling 을 이용한 것이다.

🏑 Subsampling of Frequent Words

엄청난 양의 데이터를 활용하게 되면 적은 양의 정보를 주지만 자주 나오는 단어들이 있다. (ex. “the”, “a”, “is”, …). 하지만 풍부한 의미를 가지고 있는 단어들 중에서는 빈도수가 낮은 단어들도 있기 마련이다.

각 단어들의 등장 횟수의 imbalance 함을 해결하기 위해 본 논문은 간단한 subsampling 기법을 적용한다. 그것은 바로 discared probability

• 의미없는 다빈도 단어를 걸러내기 위함
• \(P\left(w_{i}\right)=1-\sqrt{\frac{t}{f\left(w_{i}\right)}}\) 를 이용하여 확률 설정
  • \(f(w_i)\) 는 단어 \(w_i\) 가 등장하는 빈도
  • \(P(w_i)\) 는 단어 \(w_i\) 가 sampling 되지 않을 확률
  • \(t\) 는 설정하는 threshold

즉, 자신들이 정한 threshold 를 넘기는 빈도수의 단어들을 sampling 하겠다는 것이다. 이를 통해 빈도수가 적지만 중요한 단어의 representation vector 의 퀄리티를 향상하는 결과를 가져올 수 있었다고 한다.

🏎️ Learning Phrases

대부분의 phrase 들은 단순히 개별 단어들을 합친 것이 아니다. 그렇기에 그 phrase 의 representation vector 를 학습하기 위해 특정 phrase 에서만 빈도 수가 높은 단어 쌍을 찾는 것을 시작으로 했다고 한다.

예를 들면, New York Times, Toronto Maple Leafs 와 같이 고유한 의미를 가진 것들은 하나의 토큰으로 치환하였다고 하고 this is, there are 같은 의미 없이 많이 나오는 것들은 그대로 사용하였다고 한다.

이러한 방식을 통해 vocabulary 사이즈를 늘리지 않고 phrase 를 직접 지정해주었고, data-driven 을 통해 자동으로 찾을 수 있도록 하였다고 한다. 그렇게 하기 위해 아래의 식을 적용해 정해놓은 기준보다 높으면 하나의 단어로 인식하도록 하였다고 한다. \[\operatorname{score}\left(w_{i}, w_{j}\right)=\frac{\operatorname{count}\left(w_{i} w_{j}\right)-\delta}{\operatorname{count}\left(w_{i}\right) \times \operatorname{count}\left(w_{j}\right)} .\]

Phrase Score

score = 단어가 동시에 등장하는 횟수 - \(\delta\) / 각 단어가 등장하는 횟수의 곱

여기서 \(\delta\) 는 너무 드물게 나오는 단어의 조합이 하나의 구로 만들어지지 않기 위한 hyper parameter

analogy test dataset

총 5개의 카테고리를 이용하여 analogy test 를 수행하였다고 한다. 각각 앞쪽 3개의 열을 이용해 마지막 열을 예측하는 문제이다.

⚙️ Additive Compositionality

마지막으로 볼 것은 앞서 언급했던 합성성이다. 본 논문에서는 Skip-gram 모델을 통해 학습된 word and phrase representations 들을 통해 간단한 연산을 통해 analogical reasoning 태스크를 정확하게 구현할 수 있다고 한다.

• Skip-gram 의 목적은 고품질의 word representation 들을 학습하는 것
  • 이는 중심부 단어의 context 를 이용해 주변 단어를 맞출 확률을 maximize 하는 것
• 두 단어의 vector 를 더한다는 것은 두 문맥을 AND 연산한다는 것
• 그렇기에 두 단어의 합을 통해 그 단어가 포함되있던 context 정보를 합칠 수 있다는 것

element-wise addition

🚀 Conclusion

논문을 끝마치면서 특이하게 representation vector 의 품질에 영향을 줬던 hyper parameter 들을 소개한다.

• Choice of Model Architecture
• Size of the vectors
• Subsampling rate
• Size of the training window.

하지만 여전히 OOV 문제는 해결하지 못하였고 (2013년이였기에…) Additive Compositionality 에서 단순 더하기만 할 수 있는건지 의문이 든다. 또한 subsmapling of frequent words 를 통해 어느 정도의 less frequent words 의 accuracy 를 얼마나 높였는지를 알 수 없어 아쉬움이 남는다. 이전 논문에서는 less frequent words 는 poor representation vector 가 학습되었고 개선 결과를 수치로 표현했으면 어떨까하는 생각이 든다.