Negative Sampling
( 참고 : word2vec Parameter Learning Explained ( Xin Rong, 2016 ))
이 방법은 hierarchical softmax보다 그 아이디어가 더 직관적이다. 한마디로 요약하자면, 한번의 iteration 마다 업데이트 해야 하는 output vector가 너무 많을 때, 그 중 일부만을 sample해서 업데이트 하는 방식이다. 예를 들어, 20000개의 단어가 있다고 하자. 기존의 방식대로 하자면, 이 20000개의 단어로 softmax를 사용하여 확률값을 내지만(too expensive computing cost), 이 방법 같은 경우에는 N개만을 샘플하여 N개의 binary classifier를 생성한다. 이는 보다 훨씬 더 빠른 연산을 가능하게 한다!
Negative?
Negative Sampling에서 말하는 Negative는 무엇일까? 간단한 예를 들어보자.
(철수,착하다)라는 word pair의 네트워크를 훈련할 때, 예측 대상의 label (actual output)은 ‘착하다’를 원 핫 인코딩한 벡터이다. 단어가 30000가지 있다고 하면, ‘착하다’ 위치에 해당하는 인덱스만 1이고 나머지 29999개는 0이 된다. 여기서 0이 negative (반대로 1이 positive)라고 할 수 있다.
그래서 Negative Sampling을 한다는 것은 이 29999개의 negative들 중 일부만을 샘플링한다는 것이다. ( 당연히 정답인 positive도 sampling한다 )
일반적으로, 작은 데이터셋에서는 5에서 20개, 큰 데이터 셋에서는 2에서 5개를 샘플링한다고 한다.
연산량이 얼마나 크게 줄어드는지 다음 예시를 통해 확인해볼 수 있다.
10000개의 단어에 대해 100dimension을 가진 weight matrix가 있다고 해보자. 기존의 방식대로 한다면, parameter수는 100만개(10000x100=1000000)가 된다.
하지만, 만약 negative sampling을 통해 5개의 negative을 샘플링(positive 1개 포함해서 total 6개 샘플링)했다면 , 그 parameter 수는 600개(6x100)이 된다. 파라미터 수를 0.06%로 크게 줄일 수 있다.
How to Sample
그렇다면 \(V-1\)개($V$ = vocabulary의 총 단어 수)의 negative들 중, 어떻게 샘플링할지도 다양한 방법이 있다. 대표적으로 word2vec에서는 unigram distribution으로 이러한 negative들을 샘플링한다. 즉, 더 자주 등장하는 (빈도 수가 높은) 단어가 샘플링 될 확률이 더 높다. 단어 \(w_i\)가 샘플로 뽑힐 확률(=\(P\left(w_{i}\right)\) ) corpus내에서 단어 \(w_i\)가 등장하는 횟수에서 전체 corpus의 단어 수를 나눈 것과 같다.
( Mikolov, T. et al, (2013)는, 단순한 unigram distribution 대신 frequency의 \(3/4\)제곱을 할 때 가장 좋은 성능을 보인다고 알려져있다. )
\(P\left(w_{i}\right)=\frac{f\left(w_{i}\right)^{3 / 4}}{\sum_{n}^{j=0}\left(f\left(w_{j}\right)^{3 / 4}\right)}\).
word2vec에서는 좋은 성능을 내는 것으로 알려진 다음과 같은 Error function을 사용하여 training을 한다.
\(E=-\log \sigma\left(\mathbf{v}_{w_{O}}^{\prime}{ }^{T} \mathbf{h}\right)-\sum_{w_{j} \in \mathcal{W}_{\mathrm{neg}}} \log \sigma\left(-\mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}\right)\).
- \(w_{O}\) : output word (i.e., the positive sample),
- \(\mathbf{v}_{w_{O}}^{\prime}\) : output vector of \(w_O\)
- \(\mathbf{h}\) : output value of the hidden layer
- CBOW) \(\mathbf{h}=\frac{1}{C} \sum_{c=1}^{C} \mathbf{v}_{w_{c}}\) in the CBOW
- Skip-gram) \(\mathbf{h}=\mathbf{v}_{w_{I}}\)
- \(\mathcal{W}_{\text {neg }}=\left\{w_{j} \mid j=1, \cdots, K\right\}\) : negative sample
Updating Equation
우선 \(E\)를 output unit \(w_j\)가 net input으로 들어갔을 때의 output값으로 미분을 하면, 다음과 같다.
\(\begin{aligned} \frac{\partial E}{\partial \mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}} &=\left\{\begin{array}{ll} \sigma\left(\mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}\right)-1 & \text { if } w_{j}=w_{O} \\ \sigma\left(\mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}\right) & \text { if } w_{j} \in \mathcal{W}_{\mathrm{neg}} \end{array}\right.\\ &=\sigma\left(\mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}\right)-t_{j} \end{aligned}\).
여기서 \(t_j\)는 단어 \(w_j\) 의 label로, positive sample일 경우 1, negative sample일 경우 0이다.
그 다음으로, \(E\)를 단어 \(w_j\) output vector로 미분하면 다음과 같다.
\(\frac{\partial E}{\partial \mathbf{v}_{w_{j}}^{\prime}}=\frac{\partial E}{\partial \mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}} \cdot \frac{\partial \mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}}{\partial \mathbf{v}_{w_{j}}^{\prime}}=\left(\sigma\left(\mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}\right)-t_{j}\right) \mathbf{h}\).
위를 통해 updating equation은 다음과 같이 나옴을 알 수 있다.
\(\mathbf{v}_{w_{j}}^{\prime}(\text { new })=\mathbf{v}_{w_{j}}^{\prime}(\text { old })-\eta\left(\sigma\left(\mathbf{v}_{w_{j}}^{\prime T} \mathbf{h}\right)-t_{j}\right) \mathbf{h}\).
이 update 식은 모든 단어가 아닌, 단지 샘플링된 단어들에만 적용되기 때문에 연산량이 크게 줄어들 수 있다.
따라서, \(E\)를 hidden layer의 output에 대해 미분하면, 다음과 같은 식이 완성된다.
\(\begin{aligned} \frac{\partial E}{\partial \mathbf{h}} &=\sum_{w_{j} \in\left\{w_{O}\right\} \cup \mathcal{W}_{\mathrm{neg}}} \frac{\partial E}{\partial \mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}} \cdot \frac{\partial \mathbf{v}_{w_{j}}^{\prime}{ }^{T} \mathbf{h}}{\partial \mathbf{h}} \\ &=\sum_{w_{j} \in\left\{w_{O}\right\} \cup \mathcal{W}_{\mathrm{neg}}}\left(\sigma\left(\mathbf{v}_{w_{j}}^{\prime} \mathbf{h}\right)-t_{j}\right) \mathbf{v}_{w_{j}}^{\prime}:=\mathrm{EH} \end{aligned}\).
CBOW의 경우 위 식의 \(EH\)를 그대로 updating equation에 집어 넣으면 되고, Skip-Gram같은 경우에는 모든 context word에 대해서 적용하여 \(EH\) value들을 합한 다음 집어넣으면 된다.