Word2vec

1. Word2vec의 필요성

Naive Bayes를 이용한 문서 분류 같이, NLP (Natural Language Processing, 자연어처리) Task를 처리해 왔습니다.

NLP (Natural Language Processing, 자연어처리) : 컴퓨터가 인간이 사용하는 언어를 이해하고 분석할 수 있게 하는 분야
ex) 'Naive Bayes'를 사용한 스팸 메일 분류기

• 성능 자체는 좋지만, 단어가 다른 단어와 어떤 차이점을 가지는지는 이해할 수 없다 -> 벡터화 고안
• SVD 같은 통계 기반으로도 단어의 벡터화는 가능하다.
• 그러나 SVD는 O(n^3)이나 되는 무거운 알고리즘이라서, 수십, 수백만 단위의 어휘에 적용하기 어렵다.
• 학습 속도를 높이기 위해 Word2Vec 사용

2. One-hot Encoding

• One-hot vector: 벡터의 요소 중 하나만 1이고 나머지는 전부 0인 벡터
• One-hot encoding
  • 단어를 고정 길이의 one-hot vector로 변환하여 사용.
  • 단어 한 개당 차원 하나씩 가짐. 단어 개수가 많아지면 벡터 차원 수도 비례해서 많아진다.
• 고정 길이의 vector는 신경망 학습에 사용할 수 있다.
• Word2Vec 학습 시에도 Input layer와 Output layer를 One-hot vector로 사용
• 단어 간의 연관성을 고려하지 않는 인코딩.
  • 각각의 단어 vector가 모두 orthogonal(직교).
  • 모든 단어의 코사인 유사도는 0. 단어 간의 관계를 벡터로 나타낼 수 없음.

example: "You say goodbye and I say hello."라는 문장이 있을 때 one-hot vector의 예제

• you = [1, 0, 0, 0, 0, 0, 0]
• goodbye = [0, 0, 1, 0, 0, 0, 0]

3. Word2vec 훈련하기

Distributional Hypothesis : 비슷한 분포를 가진 단어는 비슷한 의미를 가진다

Word2vec(2013)

• 기존 Neural net기반 학습 방법에서 크게 벗어난 것은 아니지만 연산량을 엄청 줄였다.

Word2vec을 학습시키기 위한 네트워크 모델 2가지

• CBOW (Continuous Bag-of-words)
• Skip-gram

이 두 가지 방법 모두 추론 기반의 학습 기법이다.

(1) CBOW

'집 앞에서 아이스크림을 사 먹었는데, 이빨이 ____ 너무 먹기가 힘들었다.'

• window size가 w일 때, ___ 앞의 w개 단어, ___ 뒤의 w개 단어를 보고 ___ 단어가 어떤 단어인지 예측하는 모델이다.
• 즉, 맥락(앞뒤의 단어)을 보고 타깃(중앙 단어)를 예측한다.
• 주어진 단어에 대해 앞뒤로 C/2개 씩, 총 C개의 단어를 Input으로 사용하여 주어진 단어를 맞추기 위한 네트워크를 만든다.
• window size가 w이면, 총 2*w개 단어(C개 단어)를 보고 주어진 단어를 맞추게 된다.
• 위 예시의 경우, window size가 1이면 "이빨이", "너무"라는 단어를 보고 "시려서"라는 단어를 예측하는 네트위크라고 볼 수 있다.

a. 구성

Input layer, projection layer(그림 상에선 hidden layer), output layer

1. Input layer에서 projection layer로 갈 때 VxN크기의 projection Matrix W를 만든다
   • N = projection layer의 길이 / 사용할 vector의 크기
2. projection layer에서 output layer로 갈 때 NxV크기의 weight Matrix W'를 만든다.
   • W, W'는 별개의 행렬
3. Input에서 단어를 one-hot encoding으로 넣어준다.
4. 여러개의 단어를 proejction해 그 벡터의 평균을 구해서 projection layer에 보낸다
5. W'를 곱해서 output layer로 보내 softmax계산을 한다.
6. 5.의 결과를 정답의 one-hot encoding과 비교하여 error를 계산한다.

Word Embedding은, Input layer들과 projection layer 사이의 Projection Matrix W들의 평균을 내여 사용한다.

b. CBOW의 연산량

• C개의 단어를 Projection : CxN
• projection layer에서 output layer로 가는 것 : NxV

전체 연산량 : CxN + NxV
V -> ln(V)로 개선하면 전체 연산량 : CxN + Nxln(V)

c. CBOW가 빠른 이유

보통 C를 10내외의 크기로 잡는다.
전체 연산량 : (projection layer의 크기 N) * (ln(V)의 크기) 에 비례
C = 10, N=500, V=1,000,000로 해도 10,000 밖에 되지 않는다.

(2) Skip-gram

주어진 단어 하나를 가지고 주위에 등장하는 나머지 몇 가지의 단어들의 등장 여부를 유추

• 즉, 타깃 단어(중앙의 단어)를 보고 맥락 단어를 예측하는 모델
• 가까이 위치해 있는 단어일 수록 현재 단어와 관련이 더 많은 단어일 것
• 멀리 떨어져있는 단어일수록 낮은 확률로 택한다

CBOW와 방향만 반대일 뿐 동작하는 방식은 유사

a. Skip-gram의 연산량

C개의 단어를 샘플링할 때

• 현재 단어를 projection하는 데 N
• output을 계산하는 데 NxV (개선하면 Nxln(V))
• 총 C개의 단어에 대해 진행하므로 *C

연산량 : C(N + Nxln(V))

• 몇 개의 단어를 샘플링하냐에 따라 계산량이 비례하므로 CBOW보다는 학습이 느리다
• 실험에서는 Skip-gram이 더 좋은 결과를 보인다

(3) V to ln(V)

CBOW, Skip-gram을 그대로 돌리면 학습이 오래 걸린다 : V 때문.
네트워크의 output layer에서 softmax를 하기 위해선

• 각 단어에 대해 전부 계산을 해서 normalization을 해야 한다
• 추가적인 연산이 엄청나게 늘어난다

이를 방지하기 위해 이 부분의 연산량을 줄이려는 시도 등장

a. Hierarchical Softmax

a-1. 구성

softmax 대신 multinomial distribution function을 사용

• 단어 하나씩을 leave로 가지는 binary tree를 만든다
  • complete할 필요는 없지만, full이면 좋다
    • complete : 마지막 레벨 제외 모두 꽉채워있고, 왼쪽부터 채워진다
    • full : 모든 노드가 0개/2개의 자식 노드를 가짐
• 해당하는 단어 w1의 확률을 계산할 때, root에서부터 그 leaf까지 가는 path에 따라 확률을 곱한다

• w : 단어. leaf에 모든 단어가 하나씩 존재한다

• L(w) : w라는 leaf에 도달하기 까지의 path의 길이

• n(w,i) : root에서부터 w라는 leaf에 도달하는 path에서 i번째 만나는 노드

• n(w,1) : root

• n(w, L(w)) : w

• 이 노드 하나하나에 vector v_n(w,i)가 딸려있다.

• ch(node) : node의 고정된 임의의 한 child - 여기서는 왼쪽이 child

• [[x]] : if x: 1, else: -1

• h : hidden layer의 값 벡터

• sigma(x) : sigmoid function 1/(1+exp(-x))

hierarchial softmax를 사용할 경우 CBOW/Skip-gram에 있던 W' matrix를 사용하지 않는다.
대신 V-1개의 internal node가 각각 길이 N짜리 weight vector를 가지게 된다. : v'_i 라 하고 학습에서 update

• P(w|wi) : input word가 wi일 때 output word가 w일 조건부 확률

이를 구하면 P(w|wi)를 maximize하기 위해 -log를 취해서 objection function 완성

a-2. p(w) 의 연산량

• step마다 길이 N짜리 vector 2개의 내적이 일어난다 : N
• binary tree를 잘 만들었을 경우 평균적으로 root로부터 leaf까지의 평균 거리 : O(ln(V))

총 연산량 : Nxln(V)
error function을 categorical cross-entropy로 쓸 경우 최종 error를 계산하기 위해 해당하는 단어에 대해서만 확률을 계산하면 되므로, 다른 추가적인 연산 없이 O(Nxln(V))만으로 끝난다

a-3. 수식 계산

특정 hidden layer에 대해 모든 단어들의 확률을 더한 sigma{ p(wi|hidden layer) }
full binary tree라 가정하고, v_node와 h의 내적값을 x라 할 때,

• 특정 node에서 왼쪽 child로 갈 확률 : sigmoid(x)
• 특정 node에서 오른쪽 child로 갈 확률 : sigmoid(-x) = 1-sigmoid(x)
• 위 두개를 더하면 1

즉, sigma{ p(wi|hidden layer) } = 1
softmax 계산이 오래 걸리는 이유 : 확률 계산을 위해 모든 결과 합을 1로 만들기 위함

• output에 대해 일일이 계산을 해 전체 합으로 normalize했기 때문에 V만큼의 계산이 더 필요했던 것
• Hierarchical softmax를 사용하면 전체 확률에 대한 계산 없이 전체 합을 1로 만들 수 있다.

a-4. 마무리

• word2vec에서는 Binary Tree로 Binary Huffman Tree 사용
  • 자주 등장하는 단어를 짧은 path로 도달할 수 있기 때문
  • full binary tree다

b. Negative Sampling

Hierarchical softmax의 대체재로 사용
아이디어 : softmax는 너무 많은 단어들에 대해서 계산하므로, 몇 개만 샘플링해보자

• 전체 단어에 대해 계산하지 않고, 일부만 뽑아서 softmax 계산을 한 후 normalization
• 연산량 : NxV -> NxK (K=뽑은 sample의 수)
  • 이 때, target 단어는 반드시 계산을 해야하므로 : positive sample
  • 나머지 : negative sample
    • negative sample을 어떻게 결정하냐에 따라 성능이 달라진다.
    • 보통 성능적으로 결정

b-1. error function

새로운 error function
위와 같은 식을 maximize하도록 weight를 조정한다

• postivie sample
  • 
• negative sample
  • 

논문 참고

• 현재 보고있는 단어 w, 목표로 하고 있는 단어 c를 선정 -> (w,c)
• positive sample : (w,c)이 이 corpus에 있을 확률
• negative sample : (w,c)이 이 corpus에 없을 확률
• 각각을 더해 log를 취한다.

보통 negative sampling에서 sample을 뽑는 것은 noise distribution을 정의하고 그 분포를 이용하여 단어들을 일정 갯수 뽑아서 사용한다.

• 근데 논문에서는 여러 분포를 실험적으로 사용해본 결과 unigram distribution의 3/4승을 이용하면 unigram, uniform보다 좋은 결과를 보인다
  • unigram distribution : 단어가 등장하는 비율에 비례하게 확률을 설정하는 분포
  • 각 확률을 3/4승 하고 normalization factor로 나누어 단어가 등장할 확률로 사용

c. Subsampling frequent words

Hierachical softmax, negative sampling은 모델 자체의 계산복잡도를 줄이기 위함
추가적으로 'the', 'a', 'in'과 같이 자주 등장하는 단어들을 확률적으로 제외

• 학습 속도, 성능 향상

c-1. how to

• f(w) : 단어 w의 등장 빈도
• t : 빈도가 일정 값 이상일 때만 제외하겠다는 threshold
  • 논문에서는 t = 10^-5일 때 가장 결과 좋았다

학습할 때 각 단어는 P(wi)확률로 제외된다.

 

4. Word2Vec 속도 향상

(1) 단순한 Word2Vec 구현의 문제점

 

• 입력층의 One-hot 표현과 가중치 행렬의 곱 계산
• 은닉층과 가중치 행렬 간의 곱 계산

위 연산들을 수행하는데 컴퓨팅 자원이 많이 필요하다.

 

(2) Embedding 계층

• id가 주어지면 단순히 그 id에 해당하는 vector를 추출하는 계층이다
• forward: 입력층의 One-hot 표현과 가중치 행렬을 곱하는 대신, 그 id에 해당하는 행의 vector 값을 반환한다.
• backward: 주어진 id에 해당하는 행의 dW 값만 갱신한다. 나머지 부분의 dW 행렬 값은 전부 0이다.

 

(3) Negative Sampling

• softmax를 이용한 다중 분류 문제를, sigmoid를 이용한 이진 분류 문제로 전환하는 것이 핵심 아이디어
• 예를 들면, input 단어가 "you", "goodbye"일때 target 단어가 "say"인가를 Yes/No로 답한다
• sigmoid 계층의 출력값을 확률값으로 본다. loss 함수는 cross-entropy를 이용한다.
• negative sampling: 하나의 input 단어에 대해 target 단어가 정답인 예 1개, 정답이 아닌 예 n개(예: 5개) 등 일부 case만 샘플링해서 학습에 사용한다.
  • 모든 경우의 수에 대해 학습하면 학습량이 너무 많기 때문에, 위와 같은 근사값을 구할 수 있는 방법을 이용한다.
  • 정답이 아닌 예(negative sample)은 단어의 확률분포에 따라 추출한다. 따라서 빈도가 높은 단어가 더 많이 샘플링된다.

 

5. 한국어 Word2Vec

word2vector는 bin 형식이나 tsv 형식으로 되어 있다. gensim 라이브러리를 이용해서 쉽게 로딩할 수 있다.

Pre-trained word vectors of 30+ languages는 wikipedia database backup dump를 기반으로 만들어진 word vector으로, 30여 개 언어의 word vector를 제공한다. 사실상 한국어로 된 유일한 word vector이다. 여기서 제공하는 code를 이용해 새롭게 word vector를 만들 수도 있다. 기본으로 제공하는 model은 최대 2만개 단어만 있으므로 이 개수를 늘릴 수 있다.

>>> import gensim 
>>> model = gensim.models.Word2Vec.load('ko.bin') # word vector 로딩 
>>> model['인공지능'] # 인공지능 word vector를 numpy array 형태로 출력 
array([-0.06324194, -0.6008734 , -0.26231512, 1.3287116 , -0.32701576, 0.5631857 , -0.7717267 , 0.31624222, -0.02853541, -0.39608407, (중략) -0.2817213 , 0.3327664 , 0.15192133, 0.14019588, -0.8833335 ], dtype=float32) 

>>> model.most_similar(['한국어', '미국'], ['한국']) # word vector를 "한국어 + 미국 - 한국"으로 계산했을 때 가장 가까운 것. 미국의 한국어, 즉 미국의 언어를 의도함. 
[('영어', 0.6886879801750183), ('일본어', 0.549891471862793), ('영문', 0.5408982038497925), ('언어', 0.5347272157669067), ('독일어', 0.5142326951026917), ('프랑스어', 0.5100058317184448), ('모국어', 0.47583508491516113), ('스페인어', 0.46559274196624756), ('중국어', 0.4549825191497803), ('영어권', 0.4537474513053894)] 

>>> model.n_similarity('한국', '한국어') # '한국' word vector와 '한국어' word vector 간의 코사인 유사도 
0.76380414 

>>> model.n_similarity('한국', '영어') # 한국-한국어 간의 similarity가 한국-영어 간의 similarity보다 큰 것에 주목. 
0.08317596 # 미국과 영어와의 similarity는 낮은데 영국과 영어의 similarity는 높음. 미국의 공용어도 영어인데 similarity가 낮게 나왔음. 이와 같이 word2vec이 잘 학습되지 않은 사례가 있을 수 있음. 

>>> model.n_similarity('미국', '영어') 
0.11053801 

>>> model.n_similarity('영국', '영어') 
0.42289335

이 외 더 자세한 사용 방법은 gensim model example을 참고하면 된다.

• 한국어 Word2Vec: 한국어 word2vec 모델을 만드는 방법을 설명한 글.
• 한국어 Word2Vec 데모: 단어 벡터 간의 연산(덧셈, 뺄셈)을 해서 가장 가까운 단어를 찾아 주는 데모. 꽤 쓸만한 품질을 보여준다.

---

reference :

• word2vec 관련 이론 정리