hierarchical softmaxについて

hierarchical softmaxとは

word2vecのskip-gramモデルやGNNのrandom walkモデルでは,損失関数にsoftmaxを計算する場合があります.その時に,word2vecでは単語の数がたくさんあり,GNNではnodeの数がたくさんあり,softmaxの計算は非常に時間がかかります.

単純にsoftmaxを計算するのではなく近似法として,hierarchical softmaxと呼ばれるテクニックがあります.neagtive samplingなども同じ問題を解決するための方法の一つですが,今回はhierarchical softmaxを解説します.

softmaxを木の構造で捉える

より具体的に考えた方がわかりやすいので,word2vecのCBOWモデルを使って考えていきます.face, fix, dog, eat, in, parkの6つの単語があるとします.

そして,contextが,eat, in, parkでそれに対するpositive sampleがdogだとします.

まず通常のsoftmaxについて考えてみます.

全体の単語数が6個です.contextの単語のeat,in,parkのembeddingを求めて,何らかのaggregate functionを噛ませることで,一つのベクトルcを精製します.そしてそのベクトルcと中間層であるembedding層の行列との積を計算し,各単語のスコアが計算します.そこからsoftmaxを計算できます.

画像2

図 1. Contextのembeddingの計算方法

画像3

図 2. スコアの計算方法

この場合は6つの単語のスコアに対するsoftmaxを計算することになるので,単語の数が大きくなると非常に時間がかかります.expの計算が,O(1)と仮定すると,単語の数nとすれば,softmaxで確率を計算するには,O(n)かかります.

計算量を減らすテクニックとして,Hierarchical softmaxがあります.そのために,まずsoftmaxの計算を木の構造として見てみます.

画像3

図 3. softmaxの木の構造

以下のようにroot nodeから各単語のnodeに対してedgeがあり,そのedgeに確率が割り振ってあります.

実は,これ自体もHierarchical softmaxと呼べますが,中間nodeを足して,木を深くすると効用が分かります.以下のように木の深さが2の場合を見てみます(図4).同じようにedgeに確率が割り振られていて,あるnodeからその子nodeに移動する確率の合計は1になるようにします.例えば,図4では,P(1->2) = 0.3,P(1->3) = 0.4,P(1-> 4) = 0.3となります.

画像4

図4. Hierarchical softmaxの例

これによって,leafに到達する確率は合計で1になります.実際に,leafの確率を計算するには,nodeの移動の確率をかけていけば良いです.例えば,P(dog) = P(1->3) * P(3-> dog) = 0.4 * 0.9 = 0.36となります.

edgeの確率の計算方法

ただedgeの確率はどう計算すればいいのでしょうか.単純なsoftmaxの場合は,中間層とコンテキストから得られたベクトルcの掛け算をして,全ての単語のスコアを計算し,softmaxを計算していました.

Hierarchical softmaxの場合は,中間層を使わず,各edgeにembeddingを持ち,ベクトルcとそのembeddingの内積でスコアを計算します.そして,それを使ってsoftmaxをnodeごとに計算します.

そうすると,上の例であれば,通常のsoftmaxであれば,6回計算するところが,5回で終わります.

単語の数が小さい例だとあまりわからないですが,単語が10000個あるとして,木の深さが2で子nodeの数が100だとします.そうすると,10000回の計算が,100 * 2 = 200回の計算ですみます.

デメリット

計算量はO(log n)になるのですが,デメリットもあります.

より多くのEmbeddingが必要

通常のsoftmaxであれば,単語の数の分だけのembeddingを持っておけばよかったですが,Hierarchical softmaxの場合は,edgeの数だけembeddingを持つので,メモリをより多く使います.

木の構築

どのように木を作ればいいかも自明ではないです.そこにも新たな計算やアルゴリズムが必要になります.

補足

Hierarchical Softmaxは,上のデメリットもあり,negative samplingなどがよく使われているように思えます.

Reference

Hierarchical Softmax

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
2
ミクロ経済学,機械学習,統計学などに興味があります.数理的な話はこちらのブログで https://ludu-vorton.hatenablog.com/ 自分のサイト https://sites.google.com/view/gota-morishita