Abstract
이 논문은 이 전에 발표된 Efficient Estimation of Word Representations in Vector Space의 후속 논문으로 기존의 Skip-gram 모델보다 단어 벡터의 quality를 높이는 것과 동시에 훈련 시간을 줄이는 방법을 제시했습니다.
빈도수가 높은 단어를 subsampling 함으로써 훈련 시간을 줄이고, 좀 더 보편적인 단어 표현을 얻을 수 있었습니다. 또한, 계층적 소프트맥스를 대신할 수 있는 negative sampling에 대해서도 설명합니다.
단어 표현의 고질적인 문제는 관용어구를 표현할 수 없다는 것입니다. 예를 들어 'Canada'와 'Air'의미를 가지고 'Air Canada'로 합치는 것은 쉽지 않습니다.
이에 영감을 받아서, 텍스트에서 phrases를 찾는 간단한 방법을 소개하고, 수백만 개의 phrases에 대한 벡터 표현을 학습할 수 있다는 것을 보입니다.
Introduction
단어의 분산 표현은 유사한 단어를 묶음으로써 NLP task의 성능 향상에 큰 기여를 했습니다. 그리고 최근에 Mikolov와 연구진이 소개한 Skip-gram model은 아주 많은 양의 비정형 텍스트 데이터에서 높은 quality의 단어 벡터를 학습하는데 효율적인 방법입니다.
이 논문에서는 이처럼 좋은 성능을 보이는 Skip-gram을 조금 더 업그레이드합니다.
훈련과정에서 자주 등장하는 단어를 subsampling 하는 것이 시간을 약 2~10배까지 줄여주고, 보다 적게 등장하는 단어의 표현에 대한 정확도를 올려준다는 것을 확인했습니다.
또한, Noise Contrastive Estimation(NCE)를 간소화한 방법도 소개합니다. 이 방법은 이 전에 계층적 소프트맥스를 사용할 때보다 속도와 성능 면에서 효과가 좋습니다.
다음으로 Skip-gram을 단어 기반에서 phrase 기반의 모델로 확장하는 방법에 대해서 얘기합니다.
The Skip-gram Model
Skip-gram model훈련 목적은 한 단어에 대해서 그 주변 단어를 잘 표현할 수 있는 벡터를 찾는 것입니다. 수식적으로 표현하면 주어진 시퀀스 $w_1, w_2, \cdots, w_T$에 대해서 log probability의 평균을 최대화하는 것입니다.
$$ \frac{1}{T} \sum_{t=1}^T \sum_{-c \leq j \leq c, j\neq0}logp(w_{t+j} | w_t)$$
여기서 $c$는 context의 크기로 $c$가 크면 정확도가 높아지지만 동시에 훈련 시간도 늘어납니다.
기본 Skip-gram 공식에서는 $p(w_{t+j} | w_t)$를 소프트맥스 함수를 이용해서 정의합니다.
$$p(w_O | w_I) = \frac{exp({v_{w_O}^\prime}^T v_{w_I})}{\sum_{w=1}^W exp({v_w^\prime}^T v_{w_I})}$$
$v_w$와 $v_w^\prime$은 각각 입력과 출력 vector representationf of $w$입니다. $W$는 단어장에 있는 단어의 개수입니다.
Hierarchichal Softmax
계층적 소프트맥스(hierachical softmax)는 기존 소프트맥스를 대신하여 가능한 출력별 확률을 계산하는 모델입니다.
이 모델은 이진트리를 사용하여 모든 단어를 표현한 후 해당 단어에 도달할 확률을 구해나가는 방법을 사용합니다. 각 마디에서는 왼쪽과 오른쪽 중 어떤 자식(child)을 선택할 지에 대한 확률이 주어집니다.
$$p(w | w_I) = \prod_{j=1}^{L(w) - 1} \sigma([n(w, j+1) = ch(n(w, j))] \cdot {v_{n(w,j)}^\prime}^T v_{w_I})$$
- $n(w, j)$ = 뿌리부터 단어 $w$까지의 경로 중 $j$번째 마디
- $L(w)$ = 경로의 길이
- $ch(n)$ = 내부 마디 n마다 자식 노드 하나를 정한 것
- $[x]$ = 만약 $x$가 True면 값이 1이 되고, 아니면 값이 -1이 되는 함수
- $v_w$ = 단어 $w$에 대한 벡터 표현
- $v_n^\prime$ = 내부 마디 $n$의 벡터 표현
위의 식을 조금 더 자세히 살펴보겠습니다.
먼저 $ch(n)$을 왼쪽이라고 가정하겠습니다. 그러면 왼쪽 자식 노드로 진행할 확률 $p(n, left)$는 다음과 같이 정의할 수 있습니다.
$$p(n, left) = \sigma({v_n^\prime}^T v_{w_I})$$
이번에는 위에 제시된 식으로 한 번 보겠습니다.
먼저 왼쪽으로 진행할 확률을 구하는 것이기 때문에
$$[n(w, j+1) = ch(n(w, j))] = 1$$이 됩니다.
이렇게 되면 전체 $\sigma([n(w, j+1) = ch(n(w, j))] \cdot {v_{n(w,j)}^\prime}^T v_{w_I})$와 $p(n, left)$의 값이 같아지게 됩니다.
이번에는 오른쪽으로 진행할 확률을 보겠습니다.
$$p(n, right) = 1 - p(n, left)$$
여기서 시그모이드 함수의 특성상 $1-\sigma(x) = \sigma(-x)$입니다. 따라서 오른쪽으로 진행할 확률을 다시 써보면 아래와 같아집니다.
$$p(n, right) = \sigma(-{v_n^\prime}^T v_{w_I})$$
역시 제일 위의 식을 만족하는 것을 알 수 있습니다.
결론적으로 정의된 식 $p(w | w_I)$는 뿌리로부터 단어 $w$에 도달할 확률임을 알 수 있습니다. 그리고 뿌리에서 출발하게 되면 결국은 어떠한 단어에라도 도착하기 때문에 확률의 총합이 1이 됨을 알 수 있습니다.
$$\sum_{w=1}^Wp(w | w_I) = 1$$
Negative Sampling
네거티브 샘플링은 계층적 소프트맥스의 대안으로 사용할 수 있는 방법입니다.
먼저, 주어진 중심 단어 $c$와 임의의 단어 $w$에 대해 $w$가 $c$의 문맥에 등장할 확률을 $p(w|c)$라고 하겠습니다.
그리고 $c$의 문맥에 등장하는 단어 $o$와 $k$개의 네거티브 샘플 $w_1, w_2, \cdots, w_k$가 있다고 하겠습니다.
우리는 $p(o|c)$가 증가하고 $p(w_i | c)$는 감소하길 원합니다. 이는 다시 말하면 $p(o|c)$와 $1-p(w_i|c)$가 모두 증가하길 원하는 것과 같습니다.
$$maximize \big(log(p(o|c)) + \sum_i^k (1 - p(w_{i=1} | c))\big)$$
위 식을 이용하여 네거티브 샘플링(NEG)의 손실 함수를 정의하면 아래와 같습니다.
$$log \sigma({v_{w_O}^\prime}^T v_{w_I}) + \sum_{i=1}^k E_{{w_i} \sim P_n(w)} [log \sigma({-v_{w_i}^\prime}^T v_{w_I})]$$
여기서 $P_n(w)$은 unigram distribution $U(w)$로 부터 경험적으로 찾은 것이며 관계식은 아래와 같습니다.
$$P_n(w) = \frac{U(x)^{\frac{3}{4}}}{Z}$$
Subsampling of Frequent Words
아주 큰 말뭉치(corpora)에서 자주 등장하는 단어('in', 'the', 'a',...)는 드물게 등장하는 단어보다 보통은 적은 정보를 갖고 있습니다.
예를 들어 'France'와 'Paris'가 같이 등장한다면 모델 훈련에 도움이 되지만, 'France'와 'the'가 같이 등장하는 것은 별로 도움이 되지 않습니다. 거의 모든 단어가 'the'와 함께 등장하기 때문입니다.
이러한 희귀 단어와 자주 등장하는 단어 사이의 불균형을 해결하기 위해 간단한 subsampling 방법을 사용합니다.
$$P(w_i) = 1 - \sqrt{\frac{t}{f(w_i)}}$$
- $f(w_i)$ = $w_i$의 빈도
- $t$ = 기준치(정해주는 값) 보통 1e-5 정도로 사용
주어진 훈련 데이터에 있는 각각의 단어 $w_i$는 위와 같은 확률 계산을 통해 제거됩니다.
이러한 방법을 사용하면 발생 빈도가 $t$보다 큰 단어는 삭제하면서도, 발생 빈도의 순서는 보존합니다. 이는 학습을 빠르게 하고 정확도를 향상했습니다.
Empirical Results
위 표는 계층적 소프트맥스, NCE, NEG의 analogical reasoning task에 대한 결과를 비교한 것입니다.
task는 $vec('Berlin') - vec('Germany') + vec('France')$의 정답과 가장 가까운 벡터는?! 같은 문제를 푸는 것입니다.
이 task에는 2개의 카테고리가 있습니다. syntactic analogies와 semantic analogies입니다.
결과를 보면 네거티브 샘플링 모델이 계층적 소프트맥스, NCE에 비해 성능이 좋은 것을 알 수 있습니다.
또한 subsampling을 진행하면 적은 시간으로도 성능이 조금이나마 향상된 것을 볼 수 있습니다.
Learning Phrases
앞서 얘기한 것처럼, phrases는 단순히 각 단어의 의미를 합한 것을 뜻하지 않습니다. 'Air'와 'Canada'가 합쳐져 'Air Canada'라는 단어를 만드는 것처럼 말이죠.
논문에서는 phrases를 표현하는 벡터를 학습하기 위해 먼저 자주 함께 등장하면서 다른 context에는 자주 등장하지 않는 단어를 찾았습니다. 예를 들어 'New York Times'나 'Toronto Maple Leafs'같은 것들이 있습니다.
이것들을 훈련 데이터에서 unique token으로 바꿔줍니다. 단, 'this is'같은 애들은 그대로 남겨둡니다.
이렇게 되면, 단어장의 크기를 크게 증가시키지 않고도 적절한 phrases를 만들 수 있습니다. 이론적으로는 모든 n-gram모델을 이용해서 만들어야 하지만, 메모리 부족 때문에 unigram과 bigram만 이용했습니다. 또한 너무 빈도가 낮은 phrases를 포함하는 것을 막기 위해서 아래의 식을 이용해 점수를 매겨줬습니다.
$$score(w_i, w_j) = \frac{count(w_i w_j) - \delta}{count(w_i) \times count(w_j)}$$
여기서 $\delta$는 discounting coefficient로 너무 빈도가 낮은 애들을 포함하지 않게 제어하는 역할을 해줍니다.
이러한 과정을 $\delta$를 조금씩 줄이면서 2~4번 진행해주고, bigram보다 더 긴 몇몇 phrases를 만들어줬습니다.
이렇게 만들어진 phrases에 대한 벡터를 phrases를 포함한 새로운 analogical reasoning task를 이용해 평가해줬습니다. Table 2는 그 예를 보여줍니다.
Phrase Skip-Gram Results
결과를 보면 네거티브 샘플링이 $k=5$일 때도 좋은 결과를 보여줬음에도 불구하고 $k=15$일 때 더 좋은 성능을 보입니다. 놀라운 것은 계층적 소프트맥스가 subsampling을 하지 않았을 때는 성능이 제일 안 좋았다가 subsampling을 했을 때 성능이 제일 좋은 것입니다.
그 외에도 subsampling을 진행했을 때 모든 모델의 성능이 올라간 것으로 보아 subsampling이 정확도를 향상할 수 있다는 것을 알 수 있습니다.
여기서 성능을 극대화하기 위해서 훈련 데이터의 크기를 키우고 계층적 소프트맥스의 차원을 1000까지 늘렸더니 정확도가 72%까지 상승했습니다. 이는 많은 양의 데이터가 매우 중요하다는 것을 보여줍니다.
Additive Compositionality
단어 벡터가 그 주변 단어를 예측하기 위해 훈련되기 때문에, 그 벡터들은 단어가 나타나는 문맥의 분포를 표현하는 거라고 볼 수 있습니다.
이 값들은 출력층에서 계산되는 확률과 로그적으로 연관되어 있기 때문에, 두 단어 벡터의 합이 두 context의 분포의 곱과 연관되어 있습니다.
Comparison to Published Word Representations
Table 6을 통해서 Skip-gram모델이 다른 모델보다 학습한 표현의 quality가 더 좋다는 것을 알 수 있습니다.
이는 Skip-gram 모델이 이 전의 모델들에 비해 2~3배 많은 약 300억 개의 단어로 학습을 했기 때문인 것 같습니다. 물론, 훈련 데이터가 훨씬 크지만 이 전 모델들에 비해 시간 복잡도도 작습니다.
Conclusion
이 논문에서는 Skip-gram을 이용하여 단어와 phrases에 대한 분산 표현을 학습하는 방법에 대해 보였고, 이러한 분산 표현을 통해 정확한 analogical reasoning이 가능하다는 것을 증명했습니다.
또한, 계산에 효율적인 모델 아키텍처와 subsampling을 통해 아주 많은 양의 데이터를 비교적 적은 시간으로 학습할 수 있게 되었습니다. 이것으로 인해 단어와 phrases 벡터의 quality가 확연하게 증가했고, 자주 등장하지 않는 희귀 단어에 대한 표현도 전보다 좋아졌습니다.
뿐만 아니라 자주 등장하는 단어에 대한 정확한 표현을 아~주 쉽게 학습할 수 있는 Negative sampling algorithm을 소개하였습니다.
마지막으로 단어 벡터를 더함으로써 어떤 의미 있는 결합이 가능함과, phrases에 대한 표현을 학습하기 위해 phrases를 하나의 token으로 바꾸는 간단한 아이디어를 합쳐서 더 긴 텍스트 조각을 표현하는 강력하지만 간단한 방법을 소개했습니다.
