mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
||||||||||||||||||||||||||||||||||||||||||||||
~/work/sdm/src% ./sdm -h sdm, hierarchically smoothed Dirichlet Mixtures. Copyright (C) 2006 Daichi Mochihashi, all rights reserved. $Id: sdm.c,v 1.2 2006/02/02 16:28:51 dmochiha Exp $ usage: sdm -M mixtures [-I emmax] [-R remmax] [-E epsilon] train model ~/work/sdm/src% ./sdm cran.dat cran.model number of documents = 1397 number of words = 5177 number of mixtures = 50 convergence criterion = 0.01 % iteration 3/50 [REM 2+16]... PPL = 258.464 ETA: 0:36:00 (45 sec/step) converged. [ 0:01:43] writing model.. done.外側のEMではハイパーパラメータだけを最適化しているので3回しか回って いませんが, 実際の最適化は内側の2+16=18回のReversing EMで行われて います。cranfield だとかなり速いですが, 大きなコーパスだともっと時間が かかります。
この /bin/sh のスクリプトは単に ~/.NeXT/.NextTrash/ にファイルを mv したり,
そこから mv したりしているだけなので, そこを書き替えれば Linux 等でも普通に
使えます。
環境変数 $TRASH が設定されていたらそれを使って,
なければ ~/.trash を必要なら作製して使う, というちょっとした変更をした
ものを下に置いておきました。OSXではごみ箱は ~/.Trash らしいので,
そう変更しておけばOSXでも使えると思います。
"rc" (recycle) がリサイクラに入れるコマンド, "rt" (retrieve) が
リサイクラから戻すコマンドです。rc も rt も少なくても有名なコマンドにはない
上, 短いので名前としても適切な気がします。
ちなみに, % rt file として $TRASH/file からカレントに戻す時,
そもそもリサイクラにどんなファイルがあるかわからないと難しいので,
~/.zshrc に 下のように書いておくと % rt [TAB] で補完が効きます。
下に置いたファイルでは, さらに % rt -l とするとリサイクラの中身が見れる
ようにしておきました。
_recycler () { local trdir="${TRASH:-$HOME/.trash}" reply=(`cd $trdir; echo *`) } compctl -K _recycler rt
% ls ~trash total 8 -rwxr-xr-x 1 dmochiha slt 517 02-10 21:54 testrc* % cp ~trash/testrc .のようなことができます。
Bayesian Sets は, アイテム集合 D に対して, クエリとしてそのサブセット Dc ⊂ D が与えられた時に, 残りのアイテム x ∈ D を Dc と同じクラスタに含まれると思われる順にソートして返すアルゴリズム。
ナイーブに考えるとこれは p(x|Dc) を評価すればいいような感じがするが, x の大域的な確率 p(x) が高ければ, Dc にかかわらずこれは高い値を持ってしまう (言語だと,「が」や「の」のような 機能語が検索されてしまうことに相当する)。 *1 よって, 上のスコアを p(x) で割って
p(x|Dc) / p(x) (1)を評価することにすれば, 頻度の影響を取り除くことができる。
I(x) = log p(x,Dc)/p(Dc)p(x) (2)が Dc が与えられた下でのx のスコアになって, これで検索するとうまくいくことがわかる。
さて, Bayesian Sets のポイントは, 上の確率
p(x,Dc), p(Dc), p(x) を計算する時に最尤推定で求めるのではなく, vague な事前分布を与えて,
パラメータθを積分消去してしまうという点。結局, 上の I(x) はハイパーパラメータ
だけに依存する, Γ関数を沢山含んだ関数になるが, 素性がバイナリの場合は
Γ(x+1)=xΓ(x) の関係を使うとどんどん綺麗な形になって, 最終的に
I(x) は列がアイテム, 行がアイテムの持つ素性を表す二値疎行列(データ) X と,
クエリに依存する重みベクトル w との内積を計算することに帰着する。
*2
これをMATLABで簡単に実装してみたのが下のページです。
>> help bsets s = bsets(X,q,alpha,beta) Bayesian Sets (Ghahramani and Heller, 2005) implementation. X : binary sparse matrix of (features * entries) q : row vector of query indexes s : row vector of scores for each entry in X alpha,beta : Beta hyperparameters of prior distribution (column vectors) $Id: bsets.m,v 1.2 2006/02/13 13:54:02 dmochiha Exp $ >> bsshow(bsets(M,[582],alpha,beta),'movie.txt'); loading movie.txt.. done. 582 225.244 Piano, The (1993) 191 57.4856 Amadeus (1984) 132 55.4172 Wizard of Oz, The (1939) 170 55.2144 Cinema Paradiso (1988) 462 55.0451 Like Water For Chocolate (Como agua para chocolate) (1992) 483 48.5138 Casablanca (1942) 509 48.2819 My Left Foot (1989) 70 46.7287 Four Weddings and a Funeral (1994) 86 45.5685 Remains of the Day, The (1993) 196 45.3046 Dead Poets Society (1989)
>> bsshow(bsets(M,[582 191 132 143],alpha,beta),'movie.txt'); % 「アマデウス」「ピアノ・レッスン」「オズの魔法使い」「サウンド・オブ・ミュージック」で検索 loading movie.txt.. done. 191 493.445 Amadeus (1984) 132 410.556 Wizard of Oz, The (1939) 174 366.719 Raiders of the Lost Ark (1981) *98 358.637 Silence of the Lambs, The (1991) *318 340.908 Schindler's List (1993) *172 321.592 Empire Strikes Back, The (1980) *69 320.884 Forrest Gump (1994) 143 319.785 Sound of Music, The (1965) 357 316.532 One Flew Over the Cuckoo's Nest (1975) 483 313.525 Casablanca (1942) *423 309.385 E.T. the Extra-Terrestrial (1982) *64 299.934 Shawshank Redemption, The (1994) *204 292.22 Back to the Future (1985) 173 285.095 Princess Bride, The (1987) *168 280.25 Monty Python and the Holy Grail (1974) 196 277.245 Dead Poets Society (1989) *28 276.291 Apollo 13 (1995) 496 270.269 It's a Wonderful Life (1946) 427 268.64 To Kill a Mockingbird (1962) *50 263.816 Star Wars (1977)'*' を付けた結果が, 明らかに間違っているエントリ。 クエリを増やすと一般にこういうことが起こって, 大域的に人気の高い映画が (p(x)で正規化しているにもかかわらず)出てきてしまう。
これはどうしてかというと, 重みベクトルの作り方に依存している。 最初の例の重みベクトル w_0 と, 後の例の重みベクトル w をプロットしたものが 以下。
「スターウォーズ」のような映画は多くの人が評価し, 素性として多くの1を 持っているので, この重みベクトルと内積を取った場合に, スコアがかなり高く なってしまう。
w0: query = [582] w: query = [582 191 132 143]
この理由は、二つ考えることができる。重みベクトル w は, 各素性の持つ(バイナリなので)ベータ分布のハイパーパラメータ α, β および, n 個の要素を持つクエリ(に対応するデータ行列の部分行列)中の素性の カウント c を使って以下のように書けるが (論文では q と書かれている)
w = log(α+c) - log(β+n-c) - logα + logβこれは, c = 0 の場合(素性はスパースなので, これがほとんど),
w = logβ - log(β+n)に等しくなる。ここで, 一つでもクエリが素性を持っていて c = 1 になると,
w = log(α+1) - logα + logβ - log(β+n-1)になる。
もう一つ, この理由は十分統計量の作り方にも関連している。
Bayesian Sets では, 素性がクエリに対応するサブ行列の中で何回現れたか
という総和 c だけを使っているので, 例えばクエリに対応するサブ行列が
[1 1 1 0 0 0], [0 0 0 1 1 1] だった場合, 十分統計量はこの和として
[1 1 1 1 1 1] になってしまい, 直感的には 1 を多く持つエントリとの内積が
大きくなってしまう。これは, 素性空間上に一つの分布を仮定していることに
恐らく対応すると思うので, その平均が例え確率密度が薄くても, データを表現
していると解釈されてしまうという問題。
これは
2005/11/11
のIBISでの話と似たところがあって, 複雑な分布をきちんと表現するためには,
例えばカーネルで高次元に飛ばす, という方法もあるような気がする。
(Kernel Bayesian Sets?) これは単にそう思っただけなので, rigid な根拠が
あるわけではないけれども。
ということで, だいたい書きたいことを書いたので, NL研の話の方をやろうと
思います。
注:以下の話はやたら細かいです。マニアック注意。
digamma関数 Ψ(x) = d/dxlogΓ(x)や, trigamma関数 Ψ'(x) = d^2/dx^2 logΓ(x)
などの polygamma 関数は, MATLAB では psi 関数が一般化されていて,
psi(n,x) で d^(n+1)/dx^(n+1) logΓ(x) を求めることができる。たとえば,
Ψ'(x) = psi(1,x).
C言語だと, digammaとtrigammaは
Lightspeed
の util.c に実装があるが, tetragamma関数 Ψ''(x) など,一般の polygamma 関数は
ないので, どうしようか, と思って探していたら,
石岡恒憲さんのページ
(一時期, 小論文の自動採点の話が有名になりましたが)に実装があるのを発見。
ガンマ関数の Newton 法に tetragamma 関数が必要になりそうで探していた
のですが, 結局僕の勘違い (trigammaまでしかいらなかった) だったので,
神! ということで紹介しておきます。
タイトル一覧 | |