Word2Vec

1. Word2vec의 필요성

NLP (Natural Language Processing, 자연어처리) : 컴퓨터가 인간이 사용하는 언어를 이해하고 분석할 수 있게 하는 분야

ex) 'Naive Bayes'를 사용한 스팸 메일 분류기

• 성능 자체는 좋지만, 단어가 다른 단어와 어떤 차이점을 가지는지는 이해할 수 없다 -> 벡터화 고안

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

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

주어진 단어에 대해 앞뒤로 C/2개 씩, 총 C개의 단어를 Input으로 사용하여 주어진 단어를 맞추기 위한 네트워크를 만든다.

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를 계산한다.

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)확률로 제외된다.

---

reference :

• word2vec 관련 이론 정리