Distributed Representations of Words and Phrases and their Compositionality(2013) 논문 읽기①
0. Abstract
최근 도입된 Skip-gram Model은 정확한 구문 및 의미 단어 관계를 다수 포착하는 고품질 distributed vector representations(분산 벡터 표현)을 학습하는 효율적인 방법이다.
본 논문에서는 벡터의 품질과 훈련 속도를 모두 향상시키는 몇 가지 확장을 제시한다.
자주 등장하는 단어의 subsampling을 통해 우리는 속도를 높이고 더 규칙적인 단어 표현을 배운다.
또한 negative sampling이라고 불리는 계층적 softmax에 대한 간단한 대안을 설명한다.
단어 표현의 본질적인 한계는 단어 순서에 대한 무관심과 관용구를 표현할 수 없다는 것이다.
예를 들어, "Canada"와 "Air"의 의미는 "Air Canada"를 얻기 위해 결합될 수 없다.
본 논문은 이 예에서 영감을 받아 텍스트에서 구문을 찾는 간단한 방법을 제시하고 수백만 개의 구문에 대한 좋은 벡터 표현을 학습하는 것이 가능하다는 것을 보여준다.
1. Introduction
벡터 공간에서 단어의 분산적인 표현은 유사한 단어를 grouping 함으로 NLP Task에 성능을 높이는데 도움을 준다
최근 많은 양의 text data로부터 양질의 단어 표현을 할 수 있는 Skip-gram model이 제안되었다.
이전에 사용하던 word vector를 훈련시키기 위한 neural network architecture와는 다르게 Skip-gram은 행렬곱 연산을 수행하지 않는다.
이것은 훈련을 매우 효율적이게 만들어 최적화된 단일 기기에서 10억개 이상의 단어를 하루만에 훈련시킬 수 있게 되었다.
신경망을 이용한 단어 표현은 단어를 언어학적으로 매우 명확하게 encoding한다는 점에서 흥미롭다.
더욱 놀라운 점은 선형변환으로 표현이 가능하단 것이다.
가령, 의 결과에서 가장 가까운 vector를 찾으면 가 되고 다른 많은 단어들에 대해서도 이러한 벡터 연산을 적용 할 수 있게 되었다.
본 논문에서는 original Skip-gram model을 개선시킬 것이다.
우리는 빈도수가 높은 단어를 sub-sampling함으로 훈련의 속도를 2~10배 향상시키면서 빈도수가 적은 단어들의 표현에 대한 정확도를 높일 수 있었다.
추가적으로 본 논문에서는 이전에 사용되었던 더욱 복잡하던 계층적인 softmax대신에 Noise Contrastive Estimation(NCE)를 단순화 시켜 Skip-gram 모델 훈련에 사용함으로 더 빠르고, 빈도수가 높은 단어에 대하여 더 나은 표현이 가능함을 입증하였다.
단어 표현은 개별적인 단어를 결합하여 표현하지 못함으로 idiomatic phrases(관용구)의 표현이 불가능 하다는 한계를 가지고 있다.
예를들자면, 'Boston Globe'는 신문의 이름인데, 자연스럽게 'boston'과 'globe'의 의미를 결합하여 해당 의미를 표현 할 수 는 없다.
따라서 vector를 사용하여 전체 구문을 표현하면 Skip-gram 모델이 훨씬 더 표현력이 뛰어나게 된다.
recursive autoneconders(재귀적 오토인코더)와 같이 단어 벡터를 구성하여 문장의 의미를 표현하는 것을 목표로 하는 다른 기술도 word vector 대신 phrase vector를 사용함으로써 표현력을 향상 시킬 수 있다.
word 기반에서 pharse 기반으로의 확장은 상대적으로 단순하다.
첫 번째, data-driven approach(데이터 기반 접근방식)을 사용해 다수의 구문(phrase)을 식별한 다음, 구문(phrase)을 훈련과정에서 개별적인 token처럼 다룬다.
phrases vector의 quality를 평가하기 위해서 word와 pharese를 모두 포함하고 있는 analogical reasoning task를 개발하였다.
마지막으로 우리는 단순한 vector의 덧셈으로 자주 의미있는 결과를 만들어 낼 수 있음을 알아냈다.
가령 vector(Russia) + vector(river)은 vector(Volga River)과 가까웠고, vector(Germany) + vector(capital)은 vector(Berlin)과 가까웠다.
이러한 결합은 명확하지 않은 언어에 대한 이해 정도를 수학적인 연산을 통해 표현 할 수 있음을 제안하고 있다.
2. Skip-gram Model
Skip-gram의 training objective는 문장이나 문서에서 주변 단어들을 예측하는 단어 표현을 찾는 것이다.
traning words 에 대하여 Skip-gram의 objective는 log 확률의 평균을 최대화 하는 것이다.
이때 C는 training context의 크기를 나타낸다. C의 크기가 클 수록 training의 결과는 더욱 좋아지지만 훈련에 소요되는 시간이 더욱 커지게 된다.
기본적인 Skip-gram model은 softmax 함수를 이용하여 다음과 같이 수식화 할 수 있다.
= input vector
= ouput vector
= number of vacabulary
계산비용 때문에 이 공식은 비현실 적이다
2-1. Hierarchical Softmax
Full softmax의 근접하면서 연산을 효율적으로 할 수 있는 방법은 Hierachical Softmax를 이용하는 것이다.
이 방법의 주된 이점은 신경망의 output node를 에 대한 확률분포를 대신하여 에 대한 확률분포를 얻을 수 있다는 것이다.
Hierarchical softmax는 단어를 뜻하는 를 leaf 출력 계층의 binary tree representation을 사용하고, 각 노드에 대해 child nodes(하위 노드)의 상대적 확률을 명시적으로 나타낸다.
더 자세히는, 각 단어 는 tree의 root(뿌리)로부터 적절한 경로에 의해 도달할 수 있다.
을 뿌리에서 까지의 경로의 번째 노드
을 이 경로의 길이, = root, = 로 한다.
이에 더하여 임의의 inner node n에 대하여, 를 n의 임의로 고정된 child이고, x가 true이면 1 그렇지 않으면 -1의 값을 갖는다.
그런 다음 hierarchical sotfmax는 를 아래와 같이 정의 한다.
이때 이고, 의 총 합은 1이다.
이것의 계산 비용은 평균적으로 보다 작다.
각 단어 w에 대하여 두 개의 표현을 사용하기 위하여 와 를 이용한 표준적인 softmax 공식과는 다르게 Hierarchical softmax 공식은 각 단어에 대한 표현 와 그의 모든 inner node n에 대하여 을 표현 할 수 있게 된
다.
Hierarchical Softmax에서 이용한 이러한 트리 구조는 훈련 시간과 모델의 정확성 향상에 큰 기여를 하게 된며, 본 논문에서는 Huffman tree를 이용하여 빈번하게 등장하는 단어에 대하여 짧은 코드를 할당하기 떄문에 빠르게 훈련 결과를 얻을 수 있었다.
(출처: https://pongdangstory.tistory.com/433)Hierachical softmax방법에서는 마지막의 노드의 leaf값에 각 단어를 할당한다. 그리고 초기에 설정된 이 트리의 모양새는 모든 단어의 벡터값을 조정하는데 동일하게 사용된다.
이후에는 주어진 단어의 Word2vec의 임베딩 벡터값과 모든 노드들이 연결된다.
"he have"라는 단어가 주어졌을 때, "cat"이라는 단어를 예측하고자 한다면, "he"와 "have"가 word2vec의 임베딩 메트릭스에서 추출되어 합쳐진다.
이후에는 모든 노드들(아래의 경우 7개의 노드)와 연결된다. 각 노드와 연결되는 V라는 파라미터 값과의 관계의 출력값이 각 노드에서 왼쪽 혹은 오른쪽을 갈지를 결정한다.이를 식으로 표현하자면, 아래와 같다.
P(“cat” | context) = p(branch left at 1|context) p(branch right at|context) p(branch right at 5|context)
p(“cat” | context)= p(n(“cat”,1), left )⋅p(n(“cat”,2), right )⋅p(n(“cat”,3), right )
p(“cat” | context) = σ(v′n(p(“cat” | context),1)h)⋅σ(−v′n(p(“cat” | context),2)h)⋅σ(−v′n(p(“cat” | context),3)h)
why? p(n, left )=σ(v′Tn⋅h) p(n, right )=1−σ(v′Tn⋅h)=σ(−v′Tn⋅h) .정답 leaf의 단어가 있는 쪽으로 왼쪽 혹은 왼쪽으로 branch로 뻗어나갈 확률값을 최대화하도록 학습하게 된다.
2-2 Negative Sampling
Hierarchical softmax의 대안으로 Noise Constractive Estimation(NCE)가 소개되었고,language modeling에 적용되었다.
NCE는 로지스틱 회귀의 평균을 통하여 데이터와 노이즈를 구분할 수 있는 좋은 모델이라는 것이 밝혀졌다.
NCE는 softmax 로그확률의 근사적인 확률을 최대화하는 반면, Skip-gram 모델은 오직 양질의 벡터 표현을 학습하는 것에 집중 할 수 있게 되었다.
그래서 Skip-gram의 퀄리티를 보존한 NCE를 자유롭게 단순화 할 수 있었다.
본 논문에서는 Negative Sampling(NEG)의 objective를 다음과 같이 정의하였다.
위 수식에서 는 Skip-gram의 objective를 대체하여 사용된다.
또한 Task는 noise분포 로부터 각 데이터의 K개의 negative sampling을 활용한 로지스틱 회귀를 이용하여 target data 를 구분하는 것이다.
본 논문의 실험에서는 작은 데이터 셋에 대해서는 K의 값이 5-20, 큰 데이터 셋에 대해서는 K의 값이 2-5가 가장 유용한 것을 밝혔다.
Negative sampling과 NCE의 주된 차이점은 NCE는 noise의 분포의 수치적인 확률과 sample이 모두 필요한 반면, Nagetive sampling은 오직 sample만 필요하다는 것이다.
그리고 NCE는 softmax의 log확률을 최대화하지만 이러한 특성은 본 논문에서 중요한 특성이 아니다.
NCE와 NEG는 모두 매개변수로서 noise distribution 을 갖는다.
본 논문에서는 Pn(W)를 선택하기 위해 많은 수를 조사하였고, unigram 본포 U(w)에서 3/4 지수승으로 늘어나는 것을 관찰하였다.
2-3 Subsampling of Frequent Words
매우 큰 말중치 안에서, 수 억번씩 자주 등장하는 단어는 쉽게 발생할 수 있다.(가령, 'a', 'the', 'in').
이러한 단어들은 대게 드물게 등장하는 단어보다 적은 의미를 내포하고 있다.
예를들어 Skip-gram 모델에서는 'France'와 'Pairs'가 함께 등장 할때의 benefit을 'France'와 'the'가 함께 등장할 때의 benefit보다 더 크게 부여한다.
이 아이디어는 반대 방향으로도 적용될 수 있다.
빈번한 단어의 벡터 표현은 수백만 개의 예제에 대한 훈련 후 크게 변하지 않는다.
희귀한 단어와 빈번한 단어 사이의 불균형에 대응하기 위해 간단한 subsampling 접근법을 사용했다.
훈련 세트의 각 단어는 공식에 의해 계산된 확률로 폐기된다.
는 단어 wi의 빈도이고, 는 일반적으로 10-5 정도의 선택된 임계값이다.
subsampling 공식을 선택한 이유는 빈도의 순위를 유지하면서 빈도가 t보다 큰 단어를 적극적으로 subsampling하기 때문이다.
비록 이 subsampling하기 공식이 heuristically하게 선택되었지만, 실제로 잘 작동한다는 것을 발견했다.
그것은 학습을 가속화하고 희귀 단어의 학습된 벡터의 정확도를 크게 향상시킨다.
3. Empirical Results
이번 섹션에서는 analogical reasoning task를 이용하여 Hierarchical Softmax(HS), Noise Contrastive Estimation, Negative Sampling, subsamping를 평가한다.
task는 "Germany":"Berlin" :: "France" : ? 와 같이 구성되어 있고 해당 질문의 답은 의 결과와 가장 cosine 거리가 가까운 vector를 찾는 것으로 실행된다. 이것의 정답은 Paris가 된다.
이 Task는 크게 Syntactic analogies(quick:quickly :: slow:slowly)와 Semantic analogies(나라와 수도)같이 두 개의 카테고리로 이루어져 있다.
Skip-gram을 training할 때는 큰 data set인 10억 개의 단어가 포함되어 있는 internal Google dataset을 이용하였다.
실험에서 5번 이하로 등장하는 어휘는 무시하여 약 672000개의 vocabulary를 얻을 수 있게 되었다.
다양한 Skip-gram의 성능은 아래에 나타나있다.
실험의 결과는 Negative Sampling은 Hierarchial Softmax보다 좋은 성능을 보이며, 심지어 Noise Cintrastive Estimation보다도 약간 더 나은 성능을 보였다.
자주 등장하는 단어에 대한 subsamping은 training 속도를 향상시키면서 단어의 정확성 역시도 더욱 정확하게 만들었다.
standard sigmoidal recurrent neural networks(highly non-linear)에 의해 학습된 벡터가 훈련 데이터의 양이 증가함에 따라 이 작업에서 크게 향상된다는 것을 보여주며, 비선형 모델도 단어 표현의 선형 구조에 대한 선호도를 가지고 있음을 시사한다.
