どうも.1ヶ月に1回はブログを書こうと思ったものの早くも7月で脱落してしまいましたが,マイペースで再びやろうと思います.

さてさて今回のテーマは、 Hierarchical Softmaxです.

Hierarchical Softmax とは,Softmaxの正規化項の計算のつらみを回避するために用いられている手法の一つですが,これを数式ベースで解説していこうと思います.ちなみにつらみ回避方法としては,Negative Samplingの方が主流な感じがなんとなくしますが,どうなんでしょうか.

Hierarchical Softmax に入る前に,普通のSoftmaxとその計算のつらみについてお話ししようと思います.

Softmax

Softmax関数は,ニューラルネットワークを用いた多クラス分類における,出力層の活性化関数として用いられます.

softmax

隠れ層のm次元ベクトルをh,出力層の重みをw_iとすると,Kクラス分類の場合に,出力としてクラスiに分類される確率をy_iとすると,

として表すことができます.ここでのポイントは,分類問題では出力が確率なので,y_iを正規化しているところがポイントになります.一方で、回帰問題では,

として恒等関数を用いる場合が多く,この場合は正規化は不要です.

さて,パラメーターw_iを求める時には,例えば負の対数尤度を損失関数として勾配法を用いますが,その勾配にy_iが含まれてしまいます.

勾配法では毎ループ,勾配の値を求めなければなりませんので,その度にy_iの中のK個の和を取らなければなりません.Kがとても大きくなった時,(例えばK=単語の数)勾配法をこのまま適用するのは辛いということがお分かりいただけたでしょうか.

これを回避する方法として,

  • Hierarchical Softmax
  • Negative Sampling

などの手法が提案されました.

Hierarchical Softmax

Hierarchical Softmaxとは,Kクラス分類に対して,二分木を作成し,2クラス分類の組み合わせで確率を計算するという手法です.2クラス分類の場合は,シグモイド関数を用いればよく,正規化項の辛い計算から解放されるというわけです.

図で表現すると以下のような形式になります.

Hierarchical-softmax

二分木のうち,葉には各クラスの確率の出力を割り当て,葉以外の節点には,隠れ層と同じm次元ベクトルbを保持します.
そして,接点から右の子へ行く確率を

で表現します.すると,シグモイド関数の性質から,左の子へ行く確率は,

で表現することができます.

これによって,例えばy_2の値を

で計算することができます.

このことから,y_iは,木の高さ(log K)程度の計算で済み,K回の計算をするよりも短縮できることがわかります.
もちろん,負の対数尤度に対する勾配も,

で計算され,軽い計算で済むことがわかります.

とはいえ,これを一般の添字で計算するには結構面倒なことになりますし,tensorflowやpytorchなどでも関数で一発でかけるというわけにはいかないようです.調べるとソースコード例はいくつかでますが…

実装する上では結局,Negative Samplingの方を採用したくなってしまいます.