Word2Vec은 왜 작동하는가 — PMI의 다른 이름

Word2Vec은 “신경망 기반의 새로운 embedding”으로 불렸다. 그러나 Levy & Goldberg(2014)는 Skip-gram with Negative Sampling(SGNS)의 optimal solution이 정확히 shifted PMI matrix의 implicit factorization임을 증명했다. 이것이 의미하는 바는 무엇인가?

Skip-gram과 CBOW — 같은 아이디어, 다른 방향

Word2Vec의 두 architecture는 같은 직관을 반대 방향에서 구현한다.

Skip-gram은 center word로 context를 예측한다. center cat이 주어지면 the, sat을 예측하는 조건부 확률 $p(w_O \mid w_I)$를 학습한다. 각 (center, context) pair가 독립적인 training signal이 되므로, rare word도 자신의 context로부터 update를 받는다.

CBOW는 반대다. context the, sat의 평균 embedding으로 center cat을 예측한다.

$$\boldsymbol{v}_{\text{ctx}} = \frac{1}{2m} \sum_{j \neq 0} W_{\text{in}}[w_{t+j}, :]$$

평균 연산이 gradient를 $1/(2m)$으로 희석하므로, rare word의 update 신호가 약해진다. 대신 token당 softmax 계산이 1회로 줄어 학습이 ~3배 빠르다.

두 model 모두 hidden layer가 없다. Bengio 2003의 신경망 언어모델이 embedding lookup → hidden(tanh) → softmax였다면, Word2Vec은 hidden을 제거하고 embedding을 곧바로 softmax에 연결했다. 학습 속도가 약 10배 향상됐고, embedding quality는 동등하거나 더 나았다.

Full Softmax의 병목과 두 가지 우회

Skip-gram의 conditional probability는 다음과 같다.

$$p(w_O \mid w_I) = \frac{\exp(\boldsymbol{v}'^{\top}_{w_O} \boldsymbol{v}_{w_I})}{\sum_{w \in V} \exp(\boldsymbol{v}'^{\top}_w \boldsymbol{v}_{w_I})}$$

분모의 합산이 문제다. $|V| = 10^5$이면 token당 100k dot product, 1B token corpus에서는 $10^{14}$ 연산 — 단일 CPU로 수십 년이 걸린다.

Hierarchical Softmax는 vocabulary를 binary tree의 leaf로 배치하고, word prediction을 root → leaf의 binary decision 연쇄로 분해한다.

$$p(w \mid w_I) = \prod_{j=1}^{L(w)-1} \sigma\!\left([\![\cdot]\!] \cdot \boldsymbol{\theta}^{\top}_{n(w,j)} \boldsymbol{v}_{w_I}\right)$$

Huffman tree를 사용하면 frequent word의 path length가 짧아진다. 기대 path length는 분포의 entropy $H(W)$에 수렴하며, $|V| = 50{,}000$ 기준으로 full softmax 대비 약 3000배 빠르다.

Negative Sampling은 더 단순하다. 매 (center, context) pair마다 $k$개의 random “negative” word를 sampling해 binary classification으로 대체한다.

$$\ell_{\text{NS}} = -\log \sigma(\boldsymbol{v}'^{\top}_{w_O} \boldsymbol{v}_{w_I}) - \sum_{i=1}^{k} \mathbb{E}_{w_i \sim P_n}\!\left[\log \sigma(-\boldsymbol{v}'^{\top}_{w_i} \boldsymbol{v}_{w_I})\right]$$

per-pair cost가 $O((k+1) \cdot d)$로 줄어든다. $k = 5$이면 full softmax 대비 약 10,000배 빠르다.

noise distribution $P_n(w) \propto c(w)^{0.75}$의 지수 0.75는 Mikolov의 grid search 결과다. uniform($\alpha=0$)이면 rare word가 negative로 너무 자주 등장해 학습 신호가 약해지고, unigram($\alpha=1$)이면 the, a 같은 frequent word가 모든 pair의 negative로 수렴한다. 0.75는 mid-frequency를 강조하는 경험적 최적점이다.

SGNS의 optimal solution — PMI의 재발견

행렬 관점으로 보면, 학습된 $W \in \mathbb{R}^{V \times d}$와 $C \in \mathbb{R}^{V \times d}$는 다음의 rank-$d$ factorization을 수행한다.

$$WC^{\top} \approx M^{\text{SGNS}}, \quad M^{\text{SGNS}}_{wc} = \mathrm{PMI}(w,c) - \log k$$

2013년까지 NLP 커뮤니티는 count 기반(PPMI + SVD)과 prediction 기반(Word2Vec)을 본질적으로 다른 방법으로 인식했다. 이 정리는 둘이 같은 PMI matrix의 서로 다른 factorization 알고리즘임을 보였다.

트레이드오프

정리

• Skip-gram은 rare word에, CBOW는 frequent word에 강하다. 차이는 gradient의 분포에서 온다.
• Full softmax의 $O(|V|)$ 병목을 HS는 tree 구조로, NS는 binary classification으로 우회한다.
• SGNS의 optimal solution은 $\boldsymbol{v}_w^{\top}\boldsymbol{v}'_c = \mathrm{PMI}(w,c) - \log k$다. Word2Vec은 PMI matrix factorization의 다른 이름이다.
• hyperparameter $k$는 학습 속도뿐 아니라 PMI threshold를 결정하는 의미론적 선택이다.

Word2Vec 이후 GloVe, FastText, ELMo, BERT로 이어지는 진화는 이 distributional 통찰을 더 큰 context와 더 깊은 모델로 확장하는 과정이다.