[DL] Hierarchical Softmax

 

Introduction

Word2Vec에서 weight를 학습하기 위해서 마지막에 Softmax function을 사용한다. 이때 Skip-gram에서 사용하는 softmax function은 다음과 같이 정의된다 :

 

$$ p(w_O | w_I) = {{  \exp{\left( {v'_{w_O}}^T v_{w_I} \right)} } \over { \sum^W_{w=1} \exp{\left( {v'_{w}}^T v_{w_I} \right)}}  } $$

 

이때 분모는 corpus 안에 있는 모든 단어들을 대상으로 inner product를 하는 것이다. 보통 $W$는 $10^5-10^7$ 사이의 값이므로 대단히 computationally expensive하다. time complexity는 $O(W)$이다.

 

따라서 다른 방법이 필요한데, 이를 효율적으로 계산할 수 있는 방법이 Morin and Bengio(2005)에 의해 도입된 Hierarchical Softmax다. Hierarchical Softmax는 트리 구조를 이용하여 확률을 $O(\log{W})$에 계산할 수 있게 한다.

 

Hierarchical Softmax

Hierarchical softmax는 output layer의 값을 직접 softmax로 구하지 않고 binary tree 형태를 이용해 계산량을 줄여서 구하는 테크닉이다. 전체적인 구조는 다음과 같다. 

 

사진 출처 :https://paperswithcode.com/method/hierarchical-softmax

 

Distributed Representations of Words and Phrases and their Compositionality'를 보면, Hierarchical Softmax는 다음과 같은 식으로 나타난다 :

 

$$ p(w|w_I) = \prod^{L(w)-1}_{j=1} \sigma \left(  [[n(w,j+1) = \text{ch}(n(w,j))]]\cdot{v'_{n(w,j)}}^T v_{w_I} \right)$$

 

$\sigma$는 sigmoid function이고, $[[x]]$는 $x$가 true면 1이고 아니면 -1인 조건식이다. $\text{ch}(n)$는 $n$의 child를 의미한다. $L(w)$는 $w$에서 root까지 가는 path의 길이를 의미한다. $n(w,j)$는 root에서 $w$까지 $j$만큼 떨어진 node를 의미한다. 즉, $n(w,1)$는 root node다.

 

이때 위 그림과 같은 hierarchical softmax function에서 $p(I'm|C)$ 는 다음과 같이 계산된다 : 

 

$$p(I'm|C)=p(n(\text{I'm}, 1),\text{left}) \cdot p(n(\text{I'm}, 2),\text{left}) \cdot p(n(\text{I'm}, 3),\text{right})$$

 

이 값은 다시 이렇게 계산된다. 

 

$$= \sigma ({v_{n(w_2,1)}^T} v_{w_i}) \cdot \sigma ({v_{n(w_2,2)}^T} v_{w_i}) \cdot \sigma ({-v_{n(w_2,3)}^T} v_{w_i})$$

 

마지막 term에서 $v^T_n$ 앞에 $-$가 붙는 이유는 다음 식이 항상 성립하기 때문이다.

 

$\sigma ( v_n^T v_{w_i}) + \sigma ( -v_n^T v_{w_i}) =1$

 

따라서 softmax에서 모든 term들의 합이 1이 되는 것을 보일 수 있다. 

 

Tree의 구성

tree를 어떻게 구성할 것인가는 다양하게 나타날 수 있다. 위에서 언급한 논문에서는 binary Huffman tree를 사용한다.

 

---

References

Mao, L. (2019, August 17). Hierarchical softmax. Lei Mao's Log Book. Retrieved July 1, 2022, from https://leimao.github.io/article/Hierarchical-Softmax/

Papers with code - hierarchical softmax explained. Explained | Papers With Code. (n.d.). Retrieved July 1, 2022, from https://paperswithcode.com/method/hierarchical-softmax

Vidal, F. (2021, November 2). Negative sampling vs hierarchical softmax. Medium. Retrieved July 1, 2022, from https://flavien-vidal.medium.com/negative-sampling-vs-hierarchical-softmax-462d063dfca4

Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J. (2013). Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26.

Footnotes