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

ABSTRACT

 

최근에 발표되었던 Skip-gram 모델은 단어의 문법적, 의미적인 유사도를 잘 표현하는 벡터를 학습하는 효과적인 모델이었다. 이번 논문에서는 벡터 표현력의 품질과 학습 속도를 향상할 수 있는 몇 가지 방법에 대해 소개한다. 그 예로, 자주 등장하는 단어들을 subsampling 하여 큰 속도 향상과 기존보다 균형 잡힌 단어 표현력을 학습시킬 수 있었다고 한다. 또한 기존에 사용하던 Hierarchical softmax를 대체하는 negative sampling에 대해 소개한다.

 

 

 

 

기존 모델로 얻어낸 벡터의 한계는 구(Phrase)를 잘 해석하지 못한다는 점이었다. 예를 들어, Canada와 Air를 더하였을 때, Air Canada의 정보를 잘 구해내지 못하였다. 따라서 저자는 이런 문제점을 다루기 위해 문장속에서 관용구를 찾는 간단한 방법과 수많은 관용구 데이터셋을 통해 더 정확한 벡터 표현력을 학습이 가능하다는 것을 보이고자 한다.

 

 

 

 

 

 

INTRODUCTION

 

과거에는 단어를 벡터로 표현하기 위해서 신경망구조를 사용했었다. 하지만, Skip-gram은 신경망의 빽빽한 행렬곱 연산을 하지 않는 모델이었기에 학습을 극도로 효율적으로 만들 수 있었다. 사실 기존에도 신경망을 사용하여 단어의 벡터 표현을 학습했을 때, 언어적 규칙성과 패턴을 명쾌하게 학습했었다. 그러나 이런 패턴은 단순한 선형변환 만으로도 학습할 수 있었고, Skip-gram은 이 점을 사용하였다. 예를 들어 $vec(Madrid) - vec(Spain) + vec(France)$의 결과는 다른 벡터들보다 $vec(Paris)$와 가깝도록 학습하면 되었다.

 

 

 

 

본 논문에서는 위의 Skip-gram에 적용할만한 몇 가지 방법에 대해서 소개한다. 그 방법에 대한 결과로 subsampling 기법을 사용했을 때는 학습 속도를 2~10배 향상할 수 있었으며 자주 등장하지 않는 단어에 대한 표현력도 크게 증가시킬 수 있었다고 한다. 또한 Noise Contrastive Estimation (NCE)의 단순화된 버전을 발표하였고, 이를 사용하면 기존의 Hierarchical softmax를 사용하는 것보다 학습 속도를 증가시킬 수 있을뿐더러, 벡터의 표현력도 증가시킬 수 있다고 하였다.

 

 

 

 

기존의 Skip-gram으로 학습한 단어의 벡터 표현은 관용구에 대해서는 잘 다루지 못한다는 한계가 있었다. 따라서 각 단어 따로따로가 아닌 관용구를 하나의 벡터로 표현하도록 하였을 때, 정확한 벡터를 만들 수 있다고 하였다. '단어'를 기반으로 했던 모델을 '구'를 기반으로 하는 모델로 변경하는 것은 비교적 쉬운 작업이라고 한다. '구'를 하나의 토큰으로 취급하여 학습을 하고 평가를 할 때는 따로 준비된 데이터셋으로 평가를 진행하기만 하면 되었다. 데이터셋의 예를 들자면 아래와 같다.

 

 

 

 

(지역-아이스 하키팀 관계)

Montreal : Montreal Canadiens :: Toronto : Toronto Maple Leafs

 

 

 

 

 

 

THE SKIP-GRAM MODEL

 

Skip-gram 모델의 학습 목표는 문서나 문장 속의 어떤 단어 $w$가 주어진다면, 그 주변 단어를 잘 예측하도록 하는 단어 $w$의 벡터를 찾는 것이다. 좀 더 정형화해서 수식으로 표현한다면 아래와 같다.

 

 

 

 

$$ \frac{1}{T} \sum_{t=1}^T \sum_{-c \leq j \leq c, j \neq 0} \log p(w_{t+j} \vert w_t) $$

 

• $T$ : 단어의 개수
• $w_i$ : $i$번째 단어
• $c$ : 주변 단어의 범위

 

 

 

 

여기서 기본 Skip-gram 모델은 $p(w_{t+j} \vert w_t)$를 softmax 함수를 사용하여 다음과 같이 정의한다.

 

 

 

 

$$ p(w_O \vert w_I) = \frac{\exp \left( {v'_{w_O}}^\top v_{w_I}\right)}{\sum_{w=1}^W \exp \left( {v'_w}^\top v_{w_I} \right)} $$

 

• $v_w$ : $w$의 입력 벡터
• $v'_w$ : $w$의 출력 벡터
• $W$ : 단어의 수

 

 

 

 

위의 공식은 상당히 비효율적이라고 볼 수 있는데, 그 이유는 $\nabla \log p(w_O \vert w_I)$가 $W$에 비례하기 때문이다. 여기서 일반적으로 $W$의 크기는 $10^5 \sim 10^7$의 값을 갖기 때문에 비효율적이다.

 

 

 

 

 

 

Hierarchical Softmax

 

위에서 softmax를 사용하는 것이 비효율적이라고 발표했기 때문에, 이번에는 이 값을 효율적으로 근사할 수 있는 hierarchical softmax 방법을 소개한다. 최종적으로 각 단어가 등장할 확률을 얻기 위해 신경망을 통해 $W$개의 출력 노드를 계산하는 것 대신, 이 방법을 사용하게 되면 $\log_2W$개의 출력 노드만 계산하면 된다는 아주 큰 이점이 존재한다.

 

 

 

 

Hierarchical softmax는 이진 트리를 사용하며, $W$개의 단어들을 리프 노드로, 나머지 노드들은 자식들과의 연관

관계를 벡터로 표현한다. 이 중간 노드들을 통해 각 단어들이 어떤 확률로 등장할 것인지를 계산할 수 있다. 더 자세히 말하자면, 각 단어 $w$는 루트노드로 부터 시작해서 적절한 경로를 타고 들어가면 도달할 수 있으며, 이를 사용해 정의한 $p(w_O \vert w_I)$는 다음과 같다.

 

 

 

 

 

 

 

 

$$p(w \vert w_I) = \prod_{j=1}^{L(w)-1} \sigma \left( [\![ n(w, j+1)=\text{ch}(n(w, j)) ]\!]  \cdot {v'_{n(w, j)}}^\top v_{w_I} \right)$$

 

• $n(w, j)$ : 루트노드에서 시작해서 $w$로 가는 경로 중 등장하는 $j$번째 노드. 예로, $n(w, 1)$은 루트 노드를 말한다.
• $L(w)$ : 루트노드에서 시작해서 $w$로 가는 경로의 길이
• $\text{ch}(n)$ : 리프 노드가 아닌 노드 $n$의 한쪽 자식 (왼쪽 자식 or 오른쪽 자식 중 하나로 고정시켜서 해석)
• $[\![x]\!]$ : $x$가 참이면 1, 거짓이면 -1을 의미
• $\sigma(x)$ : $1/(1 + \exp(-x))$

 

 

 

 

예를 들어, 위의 그림과 같이 $w_I$가 lazy라는 단어였고, 이 단어가 입력일 때 $w_2$가 등장할 확률을 구하는 식은 아래와 같게 된다. 특히 아래에서 $\text{ch}(n)$은 $n$의 왼쪽 자식임을 가정하고 계산하였다.

 

 

 

 

$$ p(w_2 \vert w_I) = \sigma(1 \cdot {v'_{n(w_2, 1)}}^\top v_{w_I} ) \times \sigma(1 \cdot {v'_{n(w_2, 2)}}^\top v_{w_I}) \times \sigma(-1 \cdot {v'_{n(w_2, 3)}}^\top v_{w_I}) $$

 

 

 

 

어떤 단어 $w_I$가 입력되었을 때, 각 단어가 등장할 확률을 모두 더하면 1이 되는 것은 당연하다. $\sum_{w=1}^W p(w \vert w_I) = 1$. 또한 위에 언급한 Hierarchical Softmax는 $\log p(w_O \vert w_I)$와 $\nabla \log p(w_O \vert w_I)$의 계산량이 $L(w_O)$에 비례함을 나타낸다. 그 이유는 루트에서 부터 시작해 어떤 단어인 리프 노드에 도달하기까지는 최대 $\log W$만큼의 수만 곱해주면 되기 때문이다.

 

 

 

 

기존의 softmax에서는 확률을 구하기 위해서 각 단어 $w$에 대해 입력 단어벡터단어 벡터 $v_w$와 출력 단어 벡터 $v'_w$가 필요했던 반면에, hierarchical softmax에서는 각 단어별 하나의 벡터 $v_w$를 필요로 하며, 리프 노드가 아닌 노드 $n$에 대한 벡터 $v'_n$만 있으면 충분했다.

 

 

 

 

 

 

Negative Sampling

 

방금 소개했던 Hierarchical Softmax를 대체할 수 있는 것은 Noise Contrastive Estimation (NCE)이다. 사실 NCE는 softmax의 로그 가능도를 최대화하도록 근사할 수 있는데, Skip-gram은 그런것 보다 오로지 양질의 벡터 표현 학습에만 관심이 있다. 따라서 저자들은 벡터의 표현력을 저해하지 않는 한, NCE를 단순화시키도록 하였다. 그리고 그 결과로 Negative Sampling (NEG)를 발표하였으며 Skip-gram의 목적함수에서 등장하던 $\log p(w_O \vert w_I)$를 아래의 수식으로 대체하였다.

 

 

 

 

$$ \log \sigma({v'_{w_O}}^\top v_{w_I}) + \sum_{i=1}^k \mathbb{E}_{w_i \sim P_n(w)} \left [ \log \sigma (-{v'_{w_i}}^\top v_{w_I}) \right ] $$

 

 

 

 

이제 해야할 일은 logistric regression을 사용해서 노이즈 분포 $P_n(w)$에서 얻은 랜덤 단어들로부터 타깃 단어인 $w_O$를 구분해내야 하는 것이다. 노이즈분포에서 추출할 $k$개의 negative sample은 작은 데이터셋에서는 5~20으로 설정하고 대용량 데이터셋에서는 2~5 정도가 적당하다고 발표하였다.

 

 

 

 

저자들이 말하는 NCE와 NEG의 주된 차이점은 NCE는 노이즈분포로 부터 얻은 샘플들과 수치적 확률도 알아야 하는 반면, NEG는 오로지 샘플만 필요하다는 것이다. Negative sample의 개수 $k$와 함께 노이즈 분포 $P_n(W)$도 직접 설정해줘야 하는 파라미터 중 하나인데, 저자는 unigram의 $\frac{3}{4}$승이 가장 좋았다고 한다.

 

 

 

 

 

 

Subsampling of Frequent Words

 

아주 큰 말뭉치 데이터셋에서 자주 등장하는 a, the, in과 같은 단어는 정말 많이 등장한다. 이런 단어들이 등장하면 일반적으로 다른 단어들보다 적은 정보를 전달하게 되며, 벡터 표현에도 큰 영향을 주지 않는다. 이 불균형을 해소하기 위해서 저자들은 간단한 subsampling 방법을 사용하였다. 데이터셋에서 어떤 단어 $w_i$를 선택했다면, 아래의 확률로 그 단어를 학습에 사용하지 않는 것이다.

 

 

 

 

$$ P(w_i) = 1 - \sqrt{\frac{t}{f(w_i)}} $$

 

• $f(w_i)$ : $w_i$가 등장한 횟수
• $t$ : 직접 설정해야하는 임계값. 일반적으로 $10^{-5}$ 사용

 

 

 

 

위의 식은 단어 $w_i$가 자주 등장할 수록 학습에서 더 공격적으로 제외시켜 단어의 학습 비율을 비슷하게 가져가도록 하는 것이다. 비록 위의 공식이 휴리스틱 하게 생성되긴 했지만, 이번 실험과정에 있어서 학습 속도를 향상하고, 드물게 등장하는 단어에 대한 벡터 표현력을 크게 증가시키는 등 효과적이라고 하였다. 더 자세한 결과는 아래 실험 결과 파트에서 다룬다.

 

 

 

 

 

 

EMPIRICAL RESULTS

 

Skip-gram으로 학습된 1000차원의 단어벡터를 2차원 PCA projection으로 표현한 결과

 

 

 

 

이번 장에서는 위에서 언급했던 Hierarchical Softmax, NCE, NEG, subsampling에 대한 평가를 진행한다. 평가는 유사한 단어를 찾는 것으로 평가를 매기게 되며, 이는 벡터 간의 선형 변환으로 구하는 방법으로 계산된다. 예를 들어, 아래와 같은 문제가 있다고 하면, $vec(Berlin) - vec(Germany) + vec(France)$를 통해서 그 지점과 가장 가까운 정답을 찾는 것이다.

 

 

 

 

Germany : Berlin :: France : ?

 

 

 

 

이런 문제들에는 2가지 종류가 있으며, 하나는 문법적 유사도를 묻는 문제 quick : quickly :: slow : slowly, 다른 하나는 수도와 도시 문제를 묻는 것과 같은 의미적 유사도를 묻는 문제이다.

 

 

 

 

실험에 사용한 데이터셋은 여러 뉴스 기사들을 발췌한 글들이었으며, 전체 데이터에서 5번 미만으로 등장한 단어들은 학습에서 제외하도록 하였다. 그 결과 학습에 사용된 실질적인 단어의 수는 692K 개였다고 한다. 아래 표는 Skip-gram의 여러 변형들을 이 데이터로 평가한 결과를 보여준다.

 

 

 

 

Skip-gram의 종류에 따른 실험결과. 출처:Distributed Representations of Words and Phrases and their Compositionality

 

 

 

 

위의 표를 보게 되면 Negative Sampling이 Hierarchical Softmax보다 성능이 월등하게 좋았으며, Noise Contrastive Estimation보다는 살짝 더 좋다는 것을 볼 수 있다. 또한 subsampling 기법을 사용했을 경우, 학습시간이 크게 감소될 수 있고 단어 표현력에 대한 정확도도 살짝 증가한 것을 보여준다.

 

 

 

 

이런 결과에 "Skip-gram의 선형성 덕분에 이런 벡터의 선형 변환을 평가하는 것에 좋은 결과를 얻은 것이 아니냐?"라고 반박하는 주장이 있을 수 있지만, 저자는 시그모이드 함수를 사용한 일반 RNN모델도 데이터의 양을 늘리게 되면 좋은 성능을 보여준다고 밝히기 때문에 틀린 주장이라고 말한다.

 

 

 

 

 

 

LEARNING PHRASES

 

맨 앞에서 소개했던 문제점들 중 하나로, 여러 구들은 각각의 단어들의 의미 합으로 이루어져있지 않다는 것이 있었다. 이를 학습시키기 위해서 저자는 구 자체를 하나의 토큰으로 바라보고 학습하도록 하였다. 하지만 학습을 위해서는 데이터셋에서 구(Phrase)를 찾아내기 위한 방법을 찾아봐야 했다. 물론 이론적으로 가능한 모든 n-gram을 사용해서 데이터셋에 추가할 수 있지만, 이 방법은 메모리를 너무 많이 소비하기 때문에 비효율적이다. 논문에서는 어떤 문장 속에서 '구'를 의미하는 것인지 판단하기 위해서 unigram과 bigram의 개수를 사용하였다.

 

 

 

 

$$ \text{score}(w_i, w_j) = \frac{\text{count}(w_i w_j) - \delta}{\text{count}(w_i) \times \text{count}(w_j)} $$

 

• $\delta$ : discounting coefficient로서, 빈도가 낮은 단어들로 구(Phrase)를 구성하는 것을 방지

 

 

 

 

저자들은 학습 데이터를 2~4번 반복해서 돌면서 임계값인 $\delta$를 줄여나가며 더 긴 구(Phrase)가 형성될 수 있도록 만들었다. 이렇게 만들어진 관용구들은 마찬가지로 아래와 같은 5개 카테고리의 학습 데이터로 학습되었다.

 

 

 

 

Examples of the analogical reasoning task for phrases

 

 

 

 

 

 

Phrase Skip-Gram Results

 

이전의 실험과 비슷하게 여러 Skip-gram을 가지고 평가를 진행했으며, 사용한 학습 데이터는 별도의 '구'를 대상으로 하는 데이터셋을 가지고 진행하였다. 이전과 같이 벡터의 차원은 300, 주변의 범위는 5로 설정하여 학습을 진행하였다. 결과는 Negative Sampling이 $k=5$를 사용한 것보다, $k=15$를 사용했을 때 더 좋은 성적을 보여주었다고 한다.

 

 

 

 

구(Phrase)를 대상으로 학습한 Skip-gram의 결과

 

 

 

 

또 하나 신기한 점을 발견할 수 있는데, Hierarchical Softmax를 사용한 모델에서 subsampling을 하지 않았을 때, 가장 안 좋은 성능을 보여주다가 subsampling을 하게 되었을 때, 가장 좋은 성적을 보여주었다는 점이다. 저자들은 여기에 멈추지 않고 학습 데이터를 늘리고 벡터의 차원을 늘려 표현력을 더 높였다. 그 결과 정확도는 72%에 도달하게 되었다고 한다.

 

 

 

 

 

 

CONCLUSION

 

이번 논문에서는 몇 가지 주요 포인트들이 존재했다. 단어뿐만 아니라 구(Phrase)를 벡터 공간에 표현하도록 학습하는 방법에 대해 소개하였고, 관련된 여러 다른 기술들은 Skip-gram 뿐만 아니라 CBOW에도 적용할만하다고 하였다. subsampling 기법은 학습을 빠르게 할 뿐만 아니라 빈도가 낮은 단어에 대한 표현력을 높여줄 수 있는 중요한 기법이며 NEG라는 아주 간단한 기법으로도 정확도를 증가시킬 수 있기도 했다.

 

 

 

 

물론 여러 기법에 등장하던 하이퍼 파라미터는 각 작업마다 다른 값을 가질 수도 있으며, 성능에 가장 큰 영향을 미치는 것은 무엇보다 모델의 구조, 벡터 차원의 크기, subsampling의 비율이라고 밝혔다. 이번 작업물에 대한 가장 흥미로운 결과는 단어 벡터가 단순한 벡터의 덧셈으로 표현될 수 있다는 점이라고 한다. 최종적으로 이런 점들을 사용해 더 긴 문장에 대해 낮은 계산 복잡도로 강력하지만 단순한 학습이 가능하다고 정리하며 마무리한다.