Noise-contrastive estimation の雑なメモ

word2vec のモデルの説明で、以下の尤度関数の最大化を行いたいが、分母にある正規化項の計算が重すぎてこのままでは計算できないという話があった。

word2vec では、この尤度関数を直接最大化するのではなく、正例とノイズとを区別する２クラス分類問題の新たに考え、この問題の誤差関数を最小化することでパラメータを求めていた。しかし普通に考えると、位置tのコンテキストの条件付き確率分布の尤度最大化と、観測データとノイズの２クラス分類問題は全く別の問題のように見える。

Chainer本では前者の問題を解くのと後者の問題を解くのとは「本質的に同じ」と書いてあった。これらの本質的に同じとはどういうことなのか疑問に思ったので、negative sampling の元ネタらしい Noise-contrastive estimation の論文を読んでみた。

Noise-contrastive estimation: A new estimation principle for unnormalized statistical models

問題

ベクトル ${\bf x} \in \mathbb{R}^n$ が未知の確率分布 $p_d({\bf x})$ に従うとする。この分布を、パラメータ $\alpha$ を持つ確率分布 $p_m({\bf x}; \alpha)$ でモデル化し、尤度を最大化することでパラメータ $\alpha$ を決定することを考える。

確率分布は正規化されていなければならない。つまり、定義域全体に渡る積分が１にならなければならない。

正規化されていない分布 $p^0_m({\bf x}; \alpha)$ があるとき、正規化制約を満たすためには以下のように $p_m({\bf x}; \alpha)$ を定義すればよい。

しかし、 $Z(\alpha)$ が解析的に解けることはめったにないし、（word2vec の場合のように）数値的に計算するのもコストが高すぎて困難である場合が多い。したがって、 $Z(\alpha)$ を計算することなく、尤度を最大化する $\alpha$ を求めたい。

Noise-contrastive estimation

$Z(\alpha)$ を計算するのではなく、新たなモデルパラメータとしてモデルに組み込むことを考える。つまり $p_m$ を以下のように再定義する。

$Z$ をパラメータにしてしまったので、この分布は $Z$ の値をうまく決めないと正規化されない。このため、この分布の尤度を目的関数として最大化を行うことはできない。なぜなら、 $Z$ を小さくすれば尤度をいくらでも大きくできるからだ。

Noise-contrastive estimation では、観測されたデータである ${\bf x}$ と、人工的に作ったノイズ ${\bf y} \sim p_n$ をロジスティック回帰で識別する問題を代わりに考える。

$p_n$ は ノイズ分布 と呼ばれる分布であり、サンプリングすることができる分布であれば自由に選んでよいらしい。ただし、 $p_d$ が非ゼロである点では $p_n$ も非ゼロであることが望ましい。さらに言うと、 $p_d$ にできるだけ近い分布を選ぶのがよいらしい。

$X = ({\bf x}_1, \dots, {\bf x}_T)$ を観測データとし、 $Y = ({\bf y}_1, \dots, {\bf y}_T)$ をノイズ分布 $p_n$ からサンプルしたデータとする。このとき、NCE において最大化すべき目的関数(ロジスティック回帰の尤度関数)は以下のように与えられる。

ただし、 $h({\bf u}; \alpha, Z)$ は、 $\sigma(v)$ をシグモイド関数として、以下のように書ける関数。

つまり、 $p_m$ と $p_n$ の対数尤度比をシグモイドに突っ込んだのが $h$ 。

いろいろ条件を仮定すると、この目的関数を最大化するパラメータを $(\alpha^{*}, Z^{*})$ としたとき、 $\alpha^{*}$ は元々の問題の尤度関数を最大化する $\alpha$ と一致し、 $Z$ は $p^0_m$ を正しく正規化する値になることが示せるらしい。すごい。

まとめ

ということで、「本質的に同じ」というのは「どっちの問題を解いても同じモデルパラメータが得られる」という意味らしい。ただし、negative sampling は NCE をベースとしているけど異なる手法なので、negative sampling で本当に同じパラメータが得られるのかはよくわからない。後で調べたい。