단어 임베딩 -2: Iteration based methods (Word2Vec, FastText)

앞서의 원핫 인코딩 모델이나 윈도우 기반 co-occurence 모델은 모두 커다란 데이터셋에 대한 전체적인 정보를 살펴보고 단어를 벡터로 변환했습니다.

Iteration based 방법은 이와는 조금 다르게, 한 iteration마다 해당 컨텍스트에 단어가 등장할 확률을 점차 학습해나가는 모델입니다.

 

만들고자 하는 언어 모델은 "나는 친구와 과자를 먹었다"와 같은 유효한 문장에 높은 확률을 주고, "고양이 임베딩은  필통이다"와 같은 문장에는 낮은 확률을 주는 모델입니다.

 

$n$개의 단어로 이루어진 문장 $s$의 확률을 문장에 사용된 단어들, $w_1, \ldots, w_n$을 이용해 다음과 같이 정의할 수 있습니다.

 

$P(s) = P(w_1, w_2, \ldots, w_n)$

1. Unigram Model

먼저, 문장에 등장하는 모든 단어가 서로 독립적이라고 본다면, 다음과 같은 모델을 만들 수 있습니다.

 

$P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^n P(w_i)$

 

그러나, 사실 이 가정은 옳지 않다는 것을 즉시 알 수 있습니다.

왜냐하면 문장의 단어들은 독립적으로 등장하는 것이 아니라, 이전의 단어들에 크게 영향을 받기 때문입니다.

만약 unigram 모델을 사용한다면, "나는 과자와 친구를 먹었다"과 같은 유효하지 않은 문장 역시 높은 점수를 받게 될 것입니다.

 

2. Bigram Model

그렇다면 문장에 어떤 단어가 등장할 확률이 바로 직전 단어의 영향을 받는다고 가정한다면 어떨까요?

이런 방법을 쓴다면 "과자와 친구를 먹었다" 와 같은 문장에 높은 점수를 주는 경우는 조금 줄어들 것 같습니다.

이 방법을 Bigram model이라고 하고, 식으로 표현한다면 다음과 같습니다.

 

$P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^n P(w_i|w_{i-1})$

 

그러나, 이 방법은 전체 문장의 구조를 고려하기보다는 그저 연속하는 두 단어의 확률만을 고려하게 되기 때문에 여전히 너무 단순합니다.

 

3. n-gram Model

Bigram 모델을 확장해 n-gram model이라는 것을 구상할 수 있습니다.

단어가 등장할 확률이 바로 전 단어 뿐 아니라 n개 전 단어까지 영향을 받는다고 가정하는 것입니다.

이를 수식으로 나타내면 다음과 같습니다.

 

$P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^n P(w_i|w_{i-1}, w_{i-2}, \ldots, w_{i-n+1})$

 

n-gram 모델은 unigram, bigram 모델보다 조금 더 합리적이어 보입니다.

그러나 n-gram 모델에도 한계점이 존재합니다.

 

"고양이가 맛있게 먹은 밥은 불닭볶음면이다."

 

위와 같은 문장에 2-gram 을 적용해 봅시다. 우리는 고양이가 불닭볶음면을 먹을 수 없다는 것을 알지만 3-gram은 그렇지 않습니다.

 

"고양이가 맛있게 먹은 밥"

"맛있게 먹은 밥은 불닭볶음면이다"

 

위의 두 문장은 모두 3-gram에 의해서 높은 점수를 기록하게 될 것입니다.

"고양이가 맛있게 먹은" 으로부터 "밥"을 유추할 수 있고, "맛잇게 먹은 밥은" 으로부터 "불닭볶음면"을 유추할 수 있기 때문입니다.

이와 같이 n-gram은 긴 문장의 앞쪽과 뒤쪽의 문맥을 연결할 수 없다는 한계점을 가지고 있습니다.

그렇다고 n의 개수를 무한정 늘리게 되면 같은 문장으로부터 관찰할 수 있는 데이터의 양이 작아지는 희소 문제(sparse problem)이 발생하게 됩니다.

 

4. Continuous Bag of Words Model(CBOW)

문장 내에서 특정 단어의 등장은 앞에 등장한 단어들 뿐만이 아니라 해당 단어 이후에 나오는 단어들에도 영향을 받습니다.

CBOW에서는 앞서 등장한 단어들을 사용해서 이번에 등장할 단어를 유추하는 것이 아니라, 앞 뒤에 나온 단어들을 사용해서 중간 단어를 유추하려고 합니다.

즉, ["나는", "친구와", "먹었다"] 로부터 "과자를"을 유추하려고 하는 것입니다.

 

CBOW는 주변 단어들로 중심 단어를 유추하는 과제를 가진, hidden layer가 한 층인 인공 신경망입니다.

그림1. CBOW의 구조

CBOW의 작동 단계는 다음과 같습니다.

 

1. 유추하고자 하는 단어의 주변 단어들, 즉 $w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m}$을 원핫임베딩해 $x^{(c-m)}, \ldots, x^{(c-1)}, x^{(c+1)}, \ldots, x^{(c+m)}$을 얻습니다.
2. 각 벡터를 가중치 행렬에 곱해 $v_{c-m}, \ldots, v_{c-1}, v_{c+1}, \ldots, v_{c+m}$를 얻습니다. ($v_i = Wx^{(i)}$)
3. 얻은 임베딩 벡터들의 평균 벡터 $\hat{v}$를 구합니다. $\hat{v} = \frac{v_{c-m} + \ldots, v_{c+m}}{2m}$
4. $\hat{v}$를 두 번째 가중치 행렬에 곱해 $z = W' \hat{v}$를 얻습니다.
5. 결과값을 softmax 함수에 집어넣어 $\hat{y} = \textit{softmax}(z)$를 구합니다.

얻은 결과값인 $\hat{y}$가 예측하고자 하려던 단어의 원핫 임베딩값인 $y=x^{(c)}$와 같다면 정확도가 높은 모델이라고 할 수 있습니다.

 

가중치 행렬 $W, W'$의 값을 학습하기 위해서는 먼저 $\hat{y}$와 $y$ 사이의 차이를 측정할 필요가 있습니다.

이를 위해서 cross entropy 함수를 사용합니다. 이산적 분포에 대한 cross entropy 함수는 다음과 같습니다.

 

$H(\hat{y}, y) = - \sum_{j=1}^{|V|} y_j \log{\hat{y_j}}$

 

$y$ 가 원 핫 벡터이기 때문에 위 식은 다음과 같이 변환할 수 있습니다. ($y_c$=1, $y_i = 0$, if $i \neq c$ )

 

$H(\hat{y}, y) = - \log{\hat{y_c}}$

 

이 $H$ 는 $y_c=1$, $\hat{y_c}$가 비슷할수록 작아지고 서로 다를수록 커지는 값입니다.

예컨대, $\hat{y_c} = 1$이라면 $H$는 0이 되고, $\hat{y_c} = 0.01$이라면 4.5에 가깝게 커집니다.

따라서 최소화하고자 하는 목적 함수를 다음과 같이 정의할 수 있습니다.

(여기에서, $u_i$ 는 $W'$의 $i$번째 행벡터입니다.)

 

$\begin{align}J&=-\log P(w_c | w_{c-m}, \ldots, w_{c_m})\\&=-\log \frac{\exp(u_c^T \hat{v})}{\sum_{j=1}^{|V|}\exp(u_j^T \hat{v})}\end{align}$

 

이제 경사 하강법, back propagation을 사용해 $W, W'$을 학습할 수 있습니다.

 

5. Skip-Gram Model

CBOW가 주변 단어를 사용해 중심 단어를 예측하는 알고리즘이었다면, Skip-Gram은 반대로 중심 단어를 사용해 주변 단어를 예측합니다.

 

"과자를" 이라는 단어에서부터 "나는", "친구와", "먹었다"는 단어들을 예측하고자 하는 것입니다.

따라서 Skip-Gram에서는 "과자를"이 문맥이 됩니다. Skip-Gram의 구조는 CBOW와 유사하지만, 인풋과 아웃풋의 구성은 반대입니다.

그림2. Skip-Gram의 구조

Skip-Gram의 작동 단계는 다음과 같습니다.

 

1. 중심 단어 $w_c$를 원핫 임베딩해 인풋 벡터 $x$를 얻습니다.
2. 인풋 벡터에 첫 번째 가중치 행렬을 곱해 $\hat{v} = Wx$를 구합니다.
3. $\hat{v}$에 두 번째 가중치 행렬을 곱해 $u = (u_{c-m}, \ldots, u_{c-1}, u-{c+1}, \ldots, u_{c+m}$을 얻습니다.
4. $u$ 에 softmax 함수를 취해 $y = softmax(u)$를 계산합니다.
5. 각 $c-m, \ldots, c-1, c+1, \ldots, c+m$에 대해 $i$ 번째 원소는 $y_i$, 나머지 원소는 0을 갖는 원핫 벡터 $y^{(i)}$를 얻습니다.

CBOW와 마찬가지로 Skip-Gram에서도 비슷한 방법으로 목적 함수를 설정합니다.

다만 Skip-Gram에서는 결과 단어들이 서로 독립적이라고 가정함으로써(나이브 베이즈 가정) 식을 전개합니다.

 

$\begin{align}J &= -\log P(w_{c-m}, \ldots, w_{c_m} | w_c) \\&=-\log \prod_{j=0, j \neq m}^{2m}P(w_{c-m+j}|v_c) \\ &= - \log \prod_{j=0, j\neq m}^{2m} \frac{\exp (u_{c-m+j}^T\hat{v})}{\sum_{k=1}^{|V|}\exp (u_k^T\hat{v})}\end{align}$

 

 

6. Word2Vec

Word2Vec은 skip-gram에 negative sampling, subsampling을 적용해 보완한 워드 임베딩 모델입니다.

 

6-1. Negative Sampling

Skip-Gram 파트에서 정의한 $J$를 살펴보면 분모에서 $|V|$번의 계산을 하는 것을 발견할 수 있습니다.

단어 사전의 크키가 커질수록 해야 할 계산도 함께 늘어나게 되어 이 계산은 매우 비효율적입니다.

만약 전체 단어 사전에 대해 계산을 수행하는 대신 샘플링된 부분집합에 대해 계산할 수 있다면 어떨까요?

 

$P(D=1|w, c)$가  $(w, c)$가 $w$와 $c$가 서로 같은 문맥에 등장할 확률($(w, c) \in D$), $P(D=0|w, c)$는 $(w, c)$가 $w$와 $c$가 서로 같은 문맥에 등장하지 않을 확률($(w, c) \in \tilde{D}$)이라고 정의하겠습니다.

 

$P(D=1|w, c)$는 시그모이드 함수를 이용해 다음과 같이 정의됩니다.

여기서 $\theta$는 모델의 파라미터를 나타내는 기호로, 위의 $W, W'$이 될 것입니다.

 

$P(D=1|w, c, \theta) = \frac{1}{1 + \exp{(v_c^Tv_w)}}$

 

그렇다면 앞서의 Skip-Gram에 Negative Sampling을 적용한 모델의 목적함수는 다음과 같을 것입니다.

 

$\begin{align} J &= -\sum_{(w, c) \in D} \log P(D=1|w, c, \theta) - \sum_{(w, c) \in \tilde{D}} \log P(D=0|w, c, \theta) \\ &= - \sum_{(w, c) \in D} \log P(D=1|w, c, \theta) - \sum_{(w, c) \in \tilde{D}} \log (1-P(D=1|w, c, \theta)) \\ &= - \sum_{(w, c) \in D} \log \frac{1}{1+\exp{(-u_w^Tv_c)}} - \sum_{(w, c) \in \tilde{D}} \log (1 - \frac{1}{1 + \exp{(-u_w^Tv_c)}}) \\ &= -\sum_{(w, c) \in D} \log \frac{1}{1+\exp(-u_w^Tv_c)} - \sum_{(w, c) \in \tilde{D}} \log \frac{1}{1 + \exp{(u_w^Tv_c)}} \end{align}$

 

그렇다면 이제 $\tilde{D}$를 구성하는 방법을 살펴봅시다.

 

$D$에 속한 각 $(w, c)$에 대해서 $k$개의 negative sample을 끌어냅니다.

그 negative sample 쌍을 $(w, c_1), (w, c_2), \ldots, (w, c_k)$라고 합니다.

이 때 각각의 $c_1, c_2, \ldots, c_k$는 전체 단어 집합에서 선택하되, 각 단어가 선택될 확률은 해당 단어의 등장 빈도의 $\frac{3}{4}$승입니다.

즉, 등장 빈도가 0.9인 단어가 선택될 확률은 0.92, 등장 빈도가 0.01인 단어가 선택될 확률은 0.032에 비례합니다.

(정확히 0.92, 0.032가 아닌 이유는 기존에 합이 1이던 분포에 $\frac{3}{4}$승을 가할 경우 합이 1보다 커지기 때문입니다. 이 합을 1로 맞추기 위해 추가적인 정규화 상수가 필요합니다.)

$\frac{3}{4}$승을 가함으로서 드문 단어가 선택될 확률을 높일 수 있습니다.

 

6-2. Subsampling

지금까지 정의한 워드 임베딩 모델에서는, 같은 문맥에서 등장하는 각 단어쌍마다 계산을 하였습니다.

그런데 '은/는' 과 같은 단어를 생각해 봅시다.

'은/는'은 거의 모든 단어들과 같이 등장하면서, 모든 문서를 통틀어 굉장히 많이 등장합니다.

그러나 '사탕'과 '초콜릿', '사탕'과 '달다'와 같은 단어의 동시 등장은 우리에게 '사탕'이라는 단어에 대한 정보를 주는 반면, '사탕'과 '은'이 같이 등장한다는 사실은 '사탕'에 대해 그만큼의 정보를 주지 못합니다.

이러한 예시들로부터 매우 자주 등장하는 단어의 경우, 상당한 계산을 요구하지만 그에 비해 충분한 정보량을 주지 못한다고 가정할 수 있습니다.

 

단어들의 등장 빈도 사이의 이러한 불균형을 해소하기 위해 subsampling 방법이 사용됩니다.

문서의 각 단어 $w$를 다음과 같은 확률로 무시하는 것입니다. ($t$는 선택된 임계치, 보통 $10^{-5}$)

 

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

 

6-3. Dynamic window size

word2vec은 가변적인 윈도우 크기를 사용합니다.

최대 윈도우 크기 $k$가 주어지면, 각 단어에 대해서 $1, \ldots, k$사이에서 임의로 샘플링된 윈도우 사이즈 $k'$를 사용합니다.

 

6-4. Rare word pruning

최소 등장 횟수(min-count)이하로 등장한 단어의 경우 타겟 단어 혹은 문맥으로서 고려되지 않습니다.

 

7. FastText

7-1. Hiearchical Softmax

앞서 negative sampling을 통해 계산량을 줄이는 방법에 대해서 공부했습니다.

계산량을 줄이는 다른 방법 중 하나는 Hierarchical softmax입니다.

hierarchical softmax는 전체 단어에 대해 계산을 하는 대신 이진 트리를 타고 내려가는 방식을 택해, 계산 복잡도를 $O(|V|)$에서 $O(\log(|V|))$까지 줄입니다.

여기서 $O(\log(|V|))$은 이진 트리의 depth에 대응됩니다.

 

그림3. Hiearchical Softmax

 

Hierarchical softmax에서 사용하는 이진 트리의 리프 노드는 단어 사전의 각 단어를 가리키고, 중간 노드에는 모델이 학습하게 될 벡터가 할당됩니다.

Hierarchical softmax의 특징은 결과로서 각 단어에 대한 임베딩이 나오지 않는 것입니다.

Hierarchical softmax를 설명하기 위해 먼저 몇 가지 notation들을 먼저 소개하겠습니다.

• $L(w)$: 루트 노드부터 리프 노드  $w$까지 가기 위해 거쳐야 하는 노드의 수
• $n(w, i)$($n$): 루트 노드로부터 리프 노드까지 가기 위해 거치게 되는 $i$번째 노드
• $v_{n(w, i)}$: $n(w, i)$에 할당된 벡터
• $ch(n)$: 각 노드 $n$에 대해 임의로 선택된 자식 노드

위의 정의에 따르면, $n(w, 1)$은 루트 노드이며 $n(w, L(w))$는 리프 노드 $w$의 부모 노드입니다.

각 노드 $n$에 대해서 그 자식 노드 중의 하나를 임의로 설정하고 그를 $ch(n)$이라 하는데, 예컨대 모든 노드에 대해서 왼쪽 자식 노드를 선택하는 방법 등이 있습니다.

 

이 정의들을 가지고 이제 확률을 계산할 수 있습니다.

(여기에서, $[x]$는 $x$가 참일 경우 1, 거짓일 경우 -1의 값을 가집니다.)

 

$P(w | w_i) = \prod_{j=1}^{L(w)-1} \sigma([n(w, j+1) = ch(n(w, j))] \cdot v_{n(w, j)}^T v_{w_i})$

 

 

여기에서 주목할 것은 $[n(w, j+1) = ch(n(w, j))]$ 값이 정규화 기능을 제공한다는 것입니다.

모든 노드가 두 개의 자식 노드를 가지고, $\sigma (v_n^T v_{w_i}) + \sigma(-v_n^Tv_{w_i}) = 1$ 이기 때문에 각 노드에서 양쪽 자식 노드로 향할 확률을 더하면 1이 됩니다.

나아가, $\sum_{w=1}^{|V|}P(w|w_i)=1$이 되는 것 역시 확인할 수 있습니다.

 

Hierarchical softmax의 목적 함수는 다음과 같습니다.

(목적함수)

 

7-2. Position-dependent Weighting

이전까지 중심 단어의 양옆 윈도우에 포함된 문맥 단어들은 모두 같은 만큼 관련이 있다고 보았습니다.

position-dependent weighting에서는 단어의 위치에 따라 다른 만큼의 중요도를 부과했습니다.

즉, 기존의 문맥 벡터는 문맥 단어들이 임베딩된 벡터들의 단순 합이지만, position-dependent weighting을 사용하면 문맥 단어에 가중치를 곱해서 합한 것이 문맥 벡터가 됩니다.

 

$P = \left\{ -c, \ldots, -1, 1, \ldots, c \right\}$ 라고 할 때,  문맥 벡터는 다음과 같이 정의됩니다.

 

$v_C = \sum_{p \in P} d_p \odot u_{t+p}$

 

이 때, $\odot$은 pointwise 곱셉 기호입니다. (ex: $(1, 2, 3, 4) \odot (1, 3, 5, 7) = (1, 6, 15, 28)$)

Advances in Pre-Training Distributed Word Representations에 따르면 이러한 방식으로 정확도를 상당히 향상시킬 수 있으나(그림4) 이는 현재 FastText의 구현에는 적용되지 않았다고 합니다. (참고: https://github.com/RaRe-Technologies/gensim/issues/2840)

그림4. Accuracies on semantic and syntactic analogy datasets for models trained on Common Crawl (630B words). By performing sentence-level de-duplication, adding position-dependent weighting and phrases, the model quality improves significantly.

 7-3. Subword model

기존의 단어 임베딩 모델이 가진 한계점 중의 하나는 새로운 단어가 등장할 경우 임베딩이 되지 않는다는 것, 그리고 단어의 내부적 특성을 반영하기 어렵다는 것입니다.

 

예컨대 "액세서리", "악세사리", "악세서리"의 구성이 매우 유사한 것으로부터 비슷한 의미를 가지는 것을 유추할 수 있지만, 지금까지 공부한 단어 임베딩 기법을 사용해서 임베딩할 경우 결과적으로 거리가 가까운 벡터로 임베딩될수는 있겠지만 단어의 내적 구성을 참고한 결과는 아닐 것입니다.

특히, "앗세서리"와 같은 오타의 경우 의미적으로 "액세서리"와 동일하지만 전체 문서에서 나타나는 빈도가 적어 벡터화 자체가 되지 않을 수 있습니다.

또한 "액세서리샵" 같은 단어가 새로 등장할 경우 처음부터 학습을 다시 하지 않아도 이를 기존에 알고 있던 "액세서리"와 비슷한 벡터로 임베딩할 수 있으면 좋겠죠.

 

subword model 기법은 bag of chararcter n-gram으로 이런 고민을 일부 해소해 줍니다.

 

기존에 "where"라는 단어를 그 자체로 학습했다면, character 3-gram에서는 이를 <wh, whe, her, ere, re> 와 같이 조각냅니다.실제로는 $3\le n\le 6$ 사이의 $n$에 대해서 character n-gram을 구한 후 원래 단어 "where"을 더하므로, 결과물은 다음과 같을 것입니다.

 

<wh, whe, her, ere, re> +<whe, wher, here, ere> +<wher, where, here> + <where>

 

이렇게 문서에 들어 있는 모든 단어에 대해서 character n-gram을 가해 크기가 $G$인 사전을 만들었다고 합시다.임의의 단어 $w$에 대해서 $w$에서 나타나는 n-gram들을 $\mathcal{G} \in \left\{ 1, \ldots, G \right\}$ 라고 하겠습니다.각 n-gram들의 벡터 표현을 $z_g$라고 할 때, $w$의 벡터 표현은 $u = \sum_{g in \mathcal{G_w}} z_g^T$가 됩니다.

 

 

 

 

 

참고:
[1] Distributed Representation of Words and Phrases and their Compositionality, T. Mikolov et al. 
https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
[2] word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method, Y. Goldberg, O. Levy
https://arxiv.org/pdf/1402.3722.pdf
[3] Enriching Word Vectors with Subword Imformation, P. Bojanowski et al. https://arxiv.org/pdf/1607.04606.pdf
[4] Advances in Pre-Training Distributed Word Representations https://arxiv.org/pdf/1712.09405.pdf