Word2vec

Word2vec

Word2vec (Mikolov et al. 2013)은 word vectors를 학습하기 위한 프레임워크 입니다.

[Paper] Efficient Estimation of Word Representations in Vector Space, https://arxiv.org/abs/1301.3781

Word2vec은 BoW나 TF-IDF에서 포착하기 어려웠던 단어 간 상관관계를 표현할 수 있고, Sparse하지 않은 Dense Representation이라는 점에서 큰 의의가 있습니다.

이러한 Word2vec의 동작방식(how to vectorize)는 크게 두가지 카테고리로 분류됩니다. 바로 Continous Bag of Words(CBOW)와 skip-gram(SG) 입니다. CBOW는 주변 단어들(context words)를 기반으로 중심어(center word)를 예측하는 계산을 수행하고, SG는 반대로 중심어(center word)를 기반으로 주변 단어(context words)를 예측하는 계산을 수행합니다.

본 포스트에서는 보다 성능이 좋다고 알려진 Skip-gram을 기준으로 알아볼 것이며, 구체적으로는 네거티브샘플링(Negative sampling)을 이용한 개선 버전인 SGNG을 설명할 예정입니다.

SGNS (Skip-gram with negative sampling)

알고리즘의 목적은 간단합니다.
1. 같은 문맥(context)에 위치한 word간 서로 존재할 확률을 Maximize
2. 다른 문맥(context)에 위치한 word간 서로 존재할 확률을 Minimize

하나하나 살펴봅시다.

Slidng Context Window

먼저 특정한 corpus에서 단어들을 순회하며 타겟 단어(t)를 기준으로 형성되는 context window를 상상해봅시다.

다음과 같은 문장이 있다고 가정해 보면,

I have passed for the Miami grand prix this weeked.

어느 특정 시점에 타겟어가 Miami이고 context window의 크기가 2라면 왼쪽으로 2단어(for, the), 오른쪽으로 2단어(grand, prix)가 윈도우에 속하게 됩니다.

이 상태에서 발생하는 단어들 간 pairs 중에서 positive samples은 다음과 같습니다. 첫번째 엘레멘트가 주변어이고 두번째 엘레멘트가 중심어라고 가정합시다.

(for, Miami)
(the, Miami)
(grand, Miami)
(prix, Miami)

반대로 negative samples는 이들을 제외하고 Miami와 매칭되는 corpus의 vocab에 있는 모든 단어들일 겁니다.

(???, Miami)

이러한 positive sample와 negative samples는 sliding context window가 모든 corpus를 돌며 수많은 positive samples 페어와 negative samples 페어가 만들어 질 것입니다.
이들이 SGNS의 트레이닝셋이고 이렇게 라벨없이 자체적으로 라벨을 형성하여 지도학습을 수행하는 것을 self-supervised learning이라 합니다.

How it works?

먼저 word가 context로 존재할 경우의 embedding vector와 중심어(center) 존재할 경우에 해당하는 embedding vector를 정의해봅시다.
이는 $|V| * d$ 의 크기를 가지 2개의 매트릭스로 정의됩니다.

corpus에 존재하는 모든 vocab에 대해 벡터값이 존재해야하므로 vocab의 크기인 $|V|$와 벡터 차원의 수 $d$를 가진 중심어 매트릭스 $W$와 주변어 매트릭스 $C$를 가정합시다.

각 매트릭스의 크기는 동일하게 $|V| * d$ 입니다.
예를 들어 corpus내 vocab의 수가 10000이고 300차원의 벡터를 가정한다면 10000*300 매트릭스가 됩니다.

벡터라이제이션 학습 전이므로 각 매트릭스 내 데이터 변수는 랜덤하게 초기화시킵니다.

이 상태에서 다음과 같은 positive samples 와 negative samples가 있다고 가정해봅시다.

# positive 
(for, Miami)
(the, Miami)
(grand, Miami)
(prix, Miami)
...

# negative 
(mountain, Miami)
(elephant, Miami)
(mountain, Miami)
(prix, Miami)
...

알고리즘은 positive pair를 기준으로 iteration을 돌며 계산을 시작할 겁니다. 특정 순간 (grand, Miami) 의 두 임베딩 벡터 페어가 선택되었다고 가정합시다.
해당 페어의 두 단어가 주어졌을 때, 두 단어가 같은 contex내 존재(positive sample)일 확률을 구해야하는데 이는 우선 $P(+, c_{pos-grand}, w)$라 표기해봅시다.

그 전에 구현 관점에서 매트릭스 $C$ 와 $W$에서 어떤 것이 grand이고 Miami의 임베딩 벡터 값을 알 수 없습니다. 이를 위해서는 모든 vocab을 one-hot encoding한 후에 해당하는 매트릭스와 매트릭스 곱을 수행하면 됩니다.
예를 들어 grand는 위 페어에서 context word이므로 해당 원핫인코딩 값($1 * |V|)$과 $C (|V| * d)$를 곱하게 되면 해당 단어의 임베딩 벡터 값($1 * d$)를 look-up하는 효과를 가지게 됩니다.
마찬가지로 Miami도 룩업하여 가져오면 됩니다. 차이는 여기서 Miami는 중심어(center word)이므로 매트릭스 $W$와 곱해줍니다.

그 다음은 negative pair를 봅시다.
여기서 한번에 몇개의 negative pairs를 계산할 건지를 결정하는 하이퍼파라미터 k가 정해져야 합니다. 3이라고 가정해봅시다.

다음과 같이 w에 매핑되는 수많은 negative samples 중 세 개의 pair를 뽑아옵시다. 각각 페어가 주어졌을때 이것이 동일 문맥에 존재하지 않을 확률(negative samples)는 다음과 같이 표기할 수 있을 겁니다.

자, 이제 문제는 특정한 두 단어(c, w)가 주어졌을 때 이들이 동일 문맥에 존재하는지(close to each other) 아닌지를 결정하는 binary classification과 동일해 졌습니다.

여기서 두 단어가 주어졌을 때를 결정하는 것은 벡터유사도(vector similarity) 입니다. 이를 통해 두 임베딩 간 내적으로 유사도를 표현할 수 있습니다.
그리고 binary classification은 뉴럴넷을 통해 수행할 것이므로 뉴럴넷 값에 확률을 계산하는 레이어 $\sigma$를 입혀 다음과 같이 확률 수식을 바꿔 표현할 수 있습니다.

Objection function

SGNS는 하나의 positive sample iteration마다 각각 stochastic-gradient descent를 수행합니다.
다음과 같이 하나의 iteration의 결과에서 모든 확률의 곱으로 최대우도법 형태로 표현해줍시다. 다음 식은 Maxmize하여야할 식이 됩니다.

경사하강법의 적용을 위해 최대가 아닌 최소를 구할 수 있도록 수식을 조금 수정하겠습니다. 목적함수를 negative log-likelihood 형태로 바꿔줍니다.

그리고 다음과 같이 벡터형태로 표현 됩니다.

이를 주변어 $c_{pos}$, $c_{neg}$ 및 중심어 $w$별로 각각 편미분하여 경사하강법을 수행하여 수렴시킵니다.
그리고 이러한 것을 모든 iteration에 대하여 반복해서 매트릭스 $C$와 $W$를 완성시킵니다.

그리하여 완성된 두 매트릭스에서 통상 타겟 매트릭스 $W$만 취하거나 두 매트릭스 벡터의 합을 취하면 벡터라이제이션 완료입니다.

Hyperparameter

nagative samples number k

negative sample을 얼마나 추출하는지 결정하는 k는 하이퍼파라미터로 개발자가 직접 지정해줘야합니다.
통상 큰 데이터 셋에는 2~5, 작은 데이터셋에는 5~20으로 지정합니다.

context window

narrow window는 단어간 유사도(similarity)를 더 잘 포착합니다.
반면 wider window는 먼 단어들간 관련성(relatedness)를 더 잘 포착합니다.

Without negative sampling?

negative sampling을 수행하는 이유는 computational efficiency 때문이었습니다. 네거티브 샘플링 없이 positive samples만 가지고 전체 vocab을 대상으로 목적함수에 대한 optimizing을 계산하는 경우를 살펴봅시다.

수식은 윈도우사이즈 내에서 모든 확률의 곱을 진행하고 윈도우가 슬라이딩하면서 전부 곱해주는 최대우도법 형태로 표현될 수 있을 겁니다.

여기서 $w$는 타겟 워드이고 타겟워드를 중심으로 분포한 주변어 중 윈도우 사이즈($-m \le j \le m$)내에 분포한 positive sample들을 곱해 줍니다.
그리고 여기 수식에서 \theta는 모든 타겟워드 $W$와 컨텍스트워드 $C$의 파라미터 값을 의미합니다.

그리고 이번엔 전체 데이터셋에 대하여 corpus의 끝까지 윈도우를 슬라이딩하며 전부 곱을 진행해줍니다.

경사하강법의 적용을 위해 최대가 아닌 최소를 구할 수 있도록 수식을 조금 수정하겠습니다. average log-likelihood를 적용하여 목적함수를 다음과 같이 변경합니다.

당연하게도 이와 같은 변경은 Maximizing Predictive Accuracy가 곧 Minimizing Objective Function가 된다는 사실에 기반한 전개입니다.

마찬가지로 다음 식을 $P(c_{pos(t+j)}|w_t;\theta)$을 벡터 내적의 곱 형태로 변형시킬 수 있습니다.

여기서 수식의 의미를 생각해보면 전체 vocab 중 해당 $c_{pos}$가 도출될 확률을 구하는 것이므로 $\sigma$는 다음과 같이 multiclass classification를 표현하는 softmax의 형태가 될 겁니다.

이에서 $\theta$를 모델의 모든 파라미터라고 했습니다. 이에는 다양한 word vector들이 존재할 겁니다. 그것도 $C$와 $W$에 각각 존재하겠죠. 여기서는 모든 word vector에 대해 각각 SGD를 수행합니다.

References

[1] Stanford CS224N: NLP with Deep Learning
[2] nlpdemystified, https://www.nlpdemystified.org/