対数線形モデルとエントロピー最大化の関係

昔の勉強ノートを引っ張りだしてくるシリーズ.

機械学習の対数線形モデルが最大エントロピー法とも呼ばれる,みたいな記述は頻繁に目にするし,統計力学のボルツマン分布の話とか考慮すれば,なんとなくそうなってそうな気はするけど,実際どうなの?というのを (たんに好奇心を満たすために) 調べてみた.実用上は何の意味ないと思う.

対数尤度関数に L1 正則化項を加えるタイプの目的関数を使った場合,もはやエントロピーは最大化されない,とかそういうわりとどうでもいいことがわかったりするかもしれない.

概要

「言語処理のための機械学習入門 (→ amazon) 」などに出てくるタイプの対数線形モデルの係数の最尤推定量が,エントロピーを「ある制約条件下」で最大化した場合のラグランジュ未定乗数に対応することを説明する (クロス表の対数線形モデルとはたぶん別物).

ただし,記号が煩雑になるのを避けるため,対数線形モデルとほぼ同一の構造を持ち,記号が煩雑でない条件付きロジットモデルがエントロピー最大化と等価であることを見る.

本文の最後に対数線形モデルと等価なエントロピー最大化問題を示す.多少ややこしくなるが,同じ方針で証明可能.
“対数線形モデルとエントロピー最大化の関係”の続きを読む

正定値行列と共分散とフィッシャー情報量(と機械学習との関連について少々)


確率統計ででてくる基本的な2つの行列(共分散行列、フィッシャー行列)の半正定値性はほとんど同じ方法で証明できる、ということについて。最後の方は機械学習と関連したすこしマニアックな話題。

関連1 → Cramer-Rao’s theorem
関連2 → 正定値行列と共分散(に関する駄文)

共分散行列の半正定値性

そもそも、共分散行列が半正定値になる理由は、任意のベクトル \(u\) に対して
\begin{align}
u^T\rm{Cov}[\boldsymbol X]u
&=\int u^T(\boldsymbol x-\bar{\boldsymbol x})
(\boldsymbol x-\bar{\boldsymbol x})^TudF(x)\\
&=\int |u\cdot(\boldsymbol x-\bar{\boldsymbol x})|^2dF(x)\ge0
\end{align}
となることから明らか。

フィッシャー情報量の半正定値性

同様に、フィッシャー情報量が半正定値行列になる理由は \(l(x|\theta)=\log f(x|\theta)\) として
\begin{align}
u^TI(\theta)u
&=u^TE[\nabla_\theta l(X|\theta)\cdot\nabla_\theta^Tl(X|\theta)]u\\
&=\int |u\cdot\nabla_\theta l(x|\theta)|^2dF(x|\theta)\ge0
\end{align}
より明らか。よって逆行列が存在すれば(つまりフィッシャー行列が退化していなければ) \(I(\theta)^{-1}\) も正定値。

さらに、任意の行列 \(A\) に対して \(A^TI(\theta)^{-1}A\) も半正定値(\(A\) が退化することもあるので「半」がくっついてくる)。これも上と全く同じ論法で終了。なのでクラメール・ラオのエントリーで出てきた次の式
\begin{align}
\mathrm{Cov}_{\boldsymbol{\theta}}
\left(\boldsymbol{W}(\boldsymbol X)\right)\geq \frac {\partial \boldsymbol{\tau}
\left(\boldsymbol{\theta}\right)} {\partial \boldsymbol{\theta}}
[I\left(\boldsymbol{\theta}\right)]^{-1}
\left( \frac {\partial
\boldsymbol{\tau}\left(\boldsymbol{\theta}\right)}
{\partial \boldsymbol{\theta}}\right)^T
\end{align}
の右辺も左辺も半正定値になることがわかる。

機械学習とフィッシャー情報量

このくらいまで書くとフィッシャー情報行列が退化する、というワクワクする状況についても書きたくなってくる。フィッシャー情報量 \(I(\theta)\) がモデルの真のパラメータのところで退化するケース。ゼロ固有値を持ち、その逆行列は存在しない(形式的には固有値ゼロで割るので逆行列が無限大に発散する)。こういう状況は機械学習でしばしば生じる。

(誤差項に正規分布を仮定して確率モデルとして扱った場合の)多層パーセプトロンとかがこれに該当する。他にはHMMとか隠れノードのあるベイジアンネットとか。hidden state がある場合に退化することが多いっぽい。ちなみに SVM はそもそも確率モデルでないので対象外。

フィッシャー行列が退化すると何がまずいのか、というと、多層パーセプトロンはバックプロパゲーションするとローカルミニマムに落ちるからそもそも最尤推定は難しいのだけれども、直感的に言うと、たとえ最尤推定できたとしても、クラメール・ラオの下限が発散するので、最尤推定量のバラつきも無限大になる、ということを暗に意味している。

これは(悪い意味で)指数型分布族とは著しく異なる性質だ。指数型分布族的なものを正則モデル(regular model)というのに対して、特異モデル(singular model)というらしい。こいつらに対しては AIC などのモデル選択も理論的にはうまくいかない(実用的にはそれなりにうまくいくという話は周りの人たちからはよく聞く)。

そういうわけで、点推定はうまくいかないので、ベイズ推定をすることになる。ベイズ推定なら特異モデルに対しても漸近的な性質を導くことができる。くわしいことは特異モデルの機械学習のベイズ推定の理論の本 “Algebraic Geometry and Statistical Learning Theory” に書いてある(難易度:個人的な感想としては激高)。

共役事前分布について

定義など少し混乱気味になって、調べてみたので書いてみました。

定義

パラメトリックな確率分布の族 \(\{p(\theta); \theta\in\Theta\}\) を考える。確率変数 \(X\) の従う分布が \(p(x|\theta)\) のとき(もしくはそのように仮定するとき)、ベイズの定理より事後分布は

\begin{align*}
p(\theta|x)\propto p(x|\theta)p(\theta)
\end{align*}

となるが、このとき事前分布 \(p(\theta)\) と事後分布 \(p(\theta|x)\) が同じ分布族に属するときに \(p(\theta)\) は \(p(x|\theta)\) の共役事前分布であるという。同じ分布族に属するので、事前パラメータ \(\theta_0\) とデータ \(x\) が決定されると事後パラメータ \(\tilde\theta\) は \(\theta_0, x\) の関数として\(\tilde\theta(\theta_0, x)\) と書ける。
“共役事前分布について”の続きを読む

ディリクレ分布に関するメモ (6)

ディリクレ分布に関するメモ (3) ではガンマ乱数を正規化することでディリクレ分布に従う乱数を発生させました。

今回は別の方法を試してみます。

ポリアの壺

ポリアの壺(Polya’s urn)というのは以下のような手続きのことです。

  1. n種類の色のボールが入った壺を考える
  2. 壺から一つボールを取り出す
  3. 取り出したボールを壺に戻し、同じ色のボールを壺に追加する
  4. ステップ2に戻る

この手続きによって、壺の中のボールは増加し続けます。その色のシェアはランダムに変動しますが、やがて収束します。この収束した時のシェアを \(p^*\) とします。この極限のシェア \(p^*\) はボールを取り出した経路に依存し、これ自体が確率変数です。これは、例えば壺に赤と青のボールが一つずつ入っていたとして、最初の数回でたまたま赤が連続して出ると、その後も赤が出やすくなり、極限では赤のシェアが90%ということも起こりえるわけです。

さて、n色のポリアの壺を考えます。最初に \(\alpha=(\alpha_1,\cdots,\alpha_n)\) 個のボールが壺に入っていたとすると、このポリアの壺の極限分布が \(\text{Dirichlet}(\alpha)\) に従います(ちなみに、これは \(\alpha\) が自然数でなくても成立します)。
“ディリクレ分布に関するメモ (6)”の続きを読む

ディリクレ分布に関するメモ (5)

以前、ディリクレ分布の平均、分散、共分散を計算しました。

ところが今日、ディリクレ過程に従うランダム確率分布がなぜ離散的か?という問題に対する証明を与えている

Ferguson Distributions Via Polya Urn Schemes; David Blackwell and James B. MacQueen, Ann. Statist. Volume 1, Number 2 (1973), 353-355.

という論文を読んでいて任意の高次モーメントが必要になったので、計算してみました。
“ディリクレ分布に関するメモ (5)”の続きを読む

証明に使えそうな不等式の大全集

結構な数の不等式が書いてあります。ほとんどに名前が付いているので有名なものばかりのはずなんだけど、四分の一くらいしか知らなかった。たくさん覚えておくと何かいいことがあるかもしれません :-)

いくつかのものはもっと一般的な形が存在したり、積分形にしてもOKだったりします。たとえば、コーシー・シュワルツ不等式なら、もっと一般的に内積空間に対して

\begin{align*}|\langle x,y\rangle|^2\le\langle x,x\rangle\langle y,y\rangle\end{align*}

が成り立ちます。Jensen 不等式なら

\begin{align*}\varphi\bigg(\int f(x)p(x)dx\bigg)\le\int \varphi(f(x))p(x)dx\end{align*}

だし、ほかにもヘルダー不等式、ミンコフスキー不等式も積分形にできます(もちろん関数空間はきちんと設定しないといけないけれども)。

binomial sum 不等式の積分形は成立するのでしょうか?

\begin{align*}???\qquad \int_0^d\frac{\Gamma(n+1)}{\Gamma(n-x+1)\Gamma(x+1)}dx\le n^d+1 \qquad???\end{align*}

いろいろ妄想してみると楽しいですね。

蛇足ですが、タイトルには「大全集」と書きましたが、個人的に知っている名前付き不等式でここに書いていないものありますね。たとえば、Gronwall 不等式、Sobolev 不等式とか。ほかにもたくさんあるかもしれません。

【追記】list of inequalities — wikipedia

NURVG : 無料で読むことができる乱数生成の本

ネット上に公開されている無料の乱数生成に関する800ページを超える大著。1986年にシュプリンガーから出版されたが、現在絶版。昔の本なので内容は少し古い。たとえば MCMC など、最近の重要な内容は(目次を見るかぎり)含まれていない。しかし、基本から丁寧に書いてあるようなので、手元においておいて損はないと思います。なぜ無料なのかは上述のウェブサイトを読むとわかります(シュプリンガーといろいろあったらしい)。ただ無料で利用出来るだけでなく、印刷、再配布、さらには販売してもいいらしく、売るときはこの本のセールスポイントを教えますよ、というジョーク?も。

Furthermore, I give anyone the permission, even without asking me, to take these PDF files to a printer, print as many copies as you like, and sell them for profit. If you would like me to advertise the sales points of the hard copies, please let me know.

機械学習屋さんもデータマイニング屋さんもシミュレーション屋さんも、確率統計に携わる人はダウンロードして iPad か kindle にでも突っ込んでおくことをオススメします(電子書籍リーダー買おうかなぁ)。

こちらのエントリーを書く際にこの本を参考にさせて頂きました。

自然対数の底 e (ネイピア数)のランダム性を調べてみた

自然対数の底 e(ネイピア数)を少数展開してみると

271828182845904523536028747135266249775724709369995957496696
762772407663035354759457138217852516642742746639193200305992
181741359662904357290033429526059563073813232862794349076323
382988075319525101901157383418793070215408914993488416750924
476146066808226480016847741185374234544243710753907774499206…

となります。ネイピア数500万桁についてランダム性を調べてみました。
“自然対数の底 e (ネイピア数)のランダム性を調べてみた”の続きを読む

分布の混合による負の二項分布の生成

ポアソン分布 (poisson distribution) は平均値 \(\lambda>0\) を唯一のパラメータとする離散確率分布ですが、これをガンマ分布 (gamma distribution) で混合してみることを考えます。つまりポアソン分布を \(p(x|\lambda)\)、ガンマ分布を \(q(\lambda|a,b)\) として、\begin{align*}r(x|a,b):=\int_0^\infty p(x|\lambda) q(\lambda|a,b)d\lambda\end{align*}を計算すると何が起こるのか、という話です。
“分布の混合による負の二項分布の生成”の続きを読む

Slice sampling

ベイズ統計などではよくマルコフ連鎖モンテカルロ(MCMC)を使います。MCMCというと Metropolis Hastings とか Gibbs Sampler を思い浮かべる人が多いと思います。しかし、MCMCというのはこの2つだけではないようです。ここでは最近、MCMCを実装する中で知った slice sampling という方法を実装してテストしてみた結果について書いてみます。 “Slice sampling”の続きを読む