2012-12-10 Online VB inference for HDP (Wang+ 2011) を実装してみたけど
Online VB inference for HDP (Wang+ 2011) を実装してみたけど
- [Wang+ AISTATS 2011] Online Variational Inference for the Hierarchical Dirichlet. Process
HDP-LDA を Online な VB で解くという論文。
Teh さんらの VB 推論の論文も読んだんだけど、実にアクロバティックな分解が出てきて、いやこれはどうなんだろう……という気分になってしまい、実装してみる気にはならなかった。
一方、Wang さんらのこれはとても素直な式展開で、そんな簡単でいいんだーという感じ。自力で全部の式導出してみたけど、引っかかるところも特になし。
とはいえやっぱり VB なので、きつい独立の仮定がどれくらい精度に影響があるのか気になるところ。
アルゴリズムはとても簡単なので、これは試してみるっきゃあないでしょう、と実装してみた。
論文の pseudo code では u, v, λ を保持しておくように書かれていたが、それだけでは likelihood が計算出来ないので ζと も持ちまわっている*1。
HDP-LDA の CGS 推論はこの前2回目の実装してみた*2んだけど、中核部分だけで300行くらいあって、とにかく間違いやすくて、めんどくさくて、遅くて。
一方 Online HDP の方は中核部分は100行未満、 dish や table が増えたり減ったりしないので、なんと楽なことか。推論も速い。
と、ここまではいいことだらけだけど、一番肝心の結果が定量的にも定性的にも全然ダメ。
そうすると、どこか間違えちゃったんだろうな、と当然思うところ。
幸い、Wang さんら自身が公開されている Python 実装があるので、これを読んでみたのだが、論文とは似ても似つかない実装になっていて、どういうこと状態。
そんなわけで実装がまるで似ていないのだが、一応動かしてみたところ、結果の「定量的にも定性的にも全然ダメ」というところは同じだった。
パラメータを最適なものを選べば良くなったりするんだろうかとか、もうちょっと粘るつもりだけど、なにか有益なアドバイスがもらえたり、みたいなことをちょっぴり期待してとりあえず実装を晒しておく。
ああ、そうそう。[Wang+ 11] では likelihood を求めるための具体的な式が書かれていないので、自分で導出した。
ここで間違えているという可能性もあるわけなので、晒しておこう。
トピック-単語分布 :
文書-トピック分布 :
あと、Wang さんらの実装が出力する *.topics ファイルから、単語-トピック分布を出力するスクリプトも貼り付けておく。
*.topics ファイルは論文の中で λ にあたるパラメータ(実装の中の m_lambda は、論文の中のλ-ηに対応しているのでややこしい)をべたっと出力しているので、上の式が正しければかんたんにトピック単語分布が得られる。
import sys, codecs, numpy # topic-word distribution with open(sys.argv[1], 'rb') as f: b = numpy.array([[float(x) for x in s.strip().split()] for s in f]) phi = b / b.sum(axis=1)[:,None] K, W = phi.shape with codecs.open('ap/vocab.txt', 'rb', 'utf-8') as f: voca = [s.strip() for s in f] assert W == len(voca) for k in xrange(K): print "\n-- topic: %d" % k for w in numpy.argsort(-phi[k])[:20]: print "%s: %f" % (voca[w], phi[k,w])
2012-03-21 LDA のパープレキシティを使うとき
LDA のパープレキシティを使うとき
NLP2012 のポスター発表にて、LDA の文字を見かけるたびに思わずフラフラ〜と近寄り、あーだこーだ無責任なことを述べていたら、決まって「 shuyo さんですよね？」
なんでも、お茶の水大の小林先生の研究室の学生さんはみなさん揃って（かな？）トピックモデルをなにがしか絡めて研究されており、このブログの LDA ネタを参照していただけているという。なんとも有り難いというか照れくさいというか。
なにがしかのお役に立てているのはもちろん嬉しい反面、n_shuyo は言語処理も機械学習も専門家ではないので、ここに書いてあることを鵜呑みにはしないでいただくことはやっぱりお願いしておかなければ。
というわけで、不足や間違いの指摘は絶賛大歓迎＞読者各位
で、ここまで前振り。
そうしたポスターの発表を拝見させていただいていた中で、パープレキシティ周りの扱いがちょっと気になったので、少し思うところをまとめてみた。なお、専門家ではないので鵜呑み(ry
まずは論より証拠と言うことで、LDA を Collapsed Gibbs Sampling(以下 CGS) 200周で解くにあたって、初期値(つまり各単語のトピック)をランダムに変えて 100回行い、そのパープレキシティがどういった分布になるか見てみたい。
具体的には、以前公開したLDAの実装を使って、以下のようなコマンドを100 回実行、200回イテレーションした後のパープレキシティでヒストグラムを描く。
$ ./lda.py -c0:50 --df=2 -k 10 -i 200
こうなった。
見てわかるとおり、結構バラつきがある。ちなみに、今回のトイサンプル(約3200語)程度であれば 200回もイテレーションすればパープレキシティの変化はすっかり落ち着くので、大きい値はまだ下がっている途中というわけではない。
つまりこれは LDA の CGS は初期値依存性が高いことを示している。
理論的にはエルゴード性が満たされていれば(そしておそらく満たされている)、MCMC は任意の初期値から定常分布におおむね収束する。つまり十分な回数回せば初期値との相関は 0 になるはずだが、200回程度のイテレーションではまだまだ足りないという事だ。
では一体何回回せばいいのか？
(ダメだろうなと思いつつ)試しにある初期値で10万回ほど回してみたが、200回目からほとんど変化がなかった。*1
実は Gibbs Sampling は職人芸を駆使しなくても棄却率が 0 の提案分布が得られるという大きなメリットと引き替えに、とてつもなく足が遅い(初期値非相関なサンプルを得るために必要なイテレーション回数が非常に多くなる)という特性がある。特に自然言語処理で使われる離散な Gibbs Sampling では、独立なサンプルを得るのは絶望的といっていいだろう。
根拠はないが、LDA の場合、上で試したデータサイズですら仮に 10^100 回イテレーションしたとしても、まだ相関 0 にはならないんじゃあないだろうか。試してみようにも先に宇宙が滅亡するので無理だけど。10^(10^100)回くらいイテレーションすればさすがに足りるのかなあ？？(自信なし)
MCMC の最先端では、現実的な時間で独立なサンプルを得るための研究が(きっと)日夜行われているわけだけど、ここで使われている MCMC は「非相関？ なにそれおいしいの？」と言わんばかりの sampling の真似事に過ぎないわけで、同じ言葉の別のものくらいに思っておいたほうがむしろ変な勘違いがなくていいのかもしれない。
まあそんなことはさておき、だからといってパープレキシティを指標として使えない使わないなんてことはない。
ただ、特性をわかってないと間違った考察や結論を導いてしまうかもしれない点は注意しておいた方がいいと思う。特にほかのモデルやパラメータでの結果と比較したい場合。
とはいえ、どうやっても真の値を求めることはできない以上たいしてできることはなく、初期値を変えて5〜10回とか推論を行い、一番いいパープレキシティを取るというのが関の山かなあ。まあそれだけでもずいぶん信頼感は上がる(気持ち的にｗ)。
今回は LDA での CGS を槍玉に上げたが、大域最適解が保証されている凸最適化でもない限り、常に当てはまりうる話。例えば EMA とか VB とか勾配法全般とかも全部 local minimum を求める手法だし。
*1：データがもっと大きくて、初期値を都合良く選べば、ちょっとした local minimum から脱出するところくらいは数千回程度で観察できるかも
2011-09-02 ITM は結構使えそうでいい感じ。
Interactive Topic Modeling を読む (Hu, Boyd-Graber and Satinoff ACL2011)
9/3 の ACL 読み会で読む [Hu+ ACL11] Interactive Topic Modeling(ITM) の資料です(途中ですが力尽きましたすいません……)。
【追記】
ディリクレ木と Interactive Adding Constraints and Unassigning(←これがこの論文のキモ！) についての説明を追加しました。
【／追記】
Interactive Topic Modeling(ITM) とは
- 通常の LDA は教師無しであり、結果の制御は基本的にできない
- baseball と football が同じトピックに入って欲しいと思っても、うまく分類されない場合はパラメータを変えて試行錯誤するとか、分類後にトピックをクラスタリングするか
- ITM は LDA に「単語ＡとＢは同じトピックに入って欲しい」という制約を「後から」入れられるモデル
Notations
- Ω_j : 同じトピックに属するべき単語の集合(制約)
- Ω_i∩Ω_j=∅ (i≠j)
- C_j = |Ω_j|
- Ω=∪Ω_j
- K : トピック数
- V : 語彙数
- J : 制約数
- w_dn : 文書 d の n 番目の単語
- z_dn : w_dn の潜在トピック
- θ_d : 文書 d の トピック分布
- φ_k, π_kj : トピック-単語分布(Dirichlet Tree)
- T_{d,k} : 文書 d 内のトピック k を持つ単語数
- P_{k,w} : トピック k を持つ単語 w の個数
- P_{k,j} : 制約 j に属する、トピック k を持つ単語数
- 論文には W_{k,j,w} = 制約 j に属する、トピック k を持つ単語 w の個数が導入されているが、制約は単語に対して高々1つなので、制約 j を持つ w に対しては常に P_{k,w} = W_{k,j,w} ゆえ不要。
Dirichlet Tree
- ディリクレ木はディリクレ分布を階層化したもの
- 1階層目のディリクレ分布から「制約 or 制約無しの単語」を引く
- 制約を引いた場合は、さらに2階層目のディリクレ分布から「その制約に属する単語」を引く
- 2階層目のディリクレ分布のパラメータηがβと同じ値の場合、元のディリクレ分布と等価(後述)
- ηをβより大きくすることで下図の(c)のような分布を構成できる(階層化していないディリクレ分布では(d)のような分布しか作れない)
- (c) と (d) を間違っていたので、コメント欄でのご指摘により訂正(2011/9/7)
- ηをβより大きくすることで下図の(c)のような分布を構成できる(階層化していないディリクレ分布では(d)のような分布しか作れない)
- LDA-DF (Andrzejewski+ ICML09) は、複数のディリクレ木の混合分布を用いる
- 「木」がいっぱいあるから「森」(=DF:Dirichlet Forest)
モデル
ただし
Collapsed Gibbs Sampling で推論
この周辺分布から、次の full conditional を得る。
トピック-単語分布の推定
P(w|z,φ,π)=Multi(ξ_k) とおいて、事後分布の平均によってξを推定
- θ_k や perplexity は vanilla LDA と全く同様。
Interactive Unassignment
- 学習をある程度行ったところで、制約を追加することを考える
- 同じトピックに入って欲しい baseball と football が別のトピックに入ってしまった！
- 推論の更新式の項の中で、制約の影響を直接受けるのは P_kj のみ
- 追加・変更された制約について P_kj を数え直せば、それを初期値として新しいモデルの学習を行うことができる
- pros
- そこまで行った学習を活かすことができる
- cons
- すでに別々のトピックに割り振られた単語が多い場合、そこから Gibbs Sampling で抜け出すのは LDA の特性上難しい(イテレーションを数多く回さないといけない)
- そこで部分的に単語のトピックの割り振り(つまり z_dn)を解除することで、その問題を解決する
- 実装的には、z_dn に -1 にセットして、対応するカウンタも減ずる
- 解除する範囲について、4通りの方針を提案
- 1. All
- 全ての単語のトピック割り振りを解除する(つまり最初から学習をやり直す)
- 2. Doc
- 「追加・変更された制約に属する単語を含む文書」の全単語のトピック割り振りを解除する
- 3. Term
- 「追加・変更された制約に属する単語」のトピック割り振りを解除する
- 4. None
- トピック割り振りを解除しない(P_kj の数え直しのみ行う)
- 論文は Doc が一番効率がよいと主張
- 手元で実験した感じでも、その主張に一致する印象(定量的な評価ではありません)
- None はもちろん、Term でも制約を入れた単語が同じトピックに割り振られるとは限らない
- baseball と football に制約を入れて、しかもそれらのトピックをリセットしても、それぞれと共起度の高い別の単語(例えば baseball - pitcher, football - goal)が多く属するトピックに引っ張られる
- したがって共起しうる単語(つまり同じ文書の単語)をまとめてリセットする方が望む結果が得られやすい
モデルについて考察
- 制約がない場合、vanilla LDA と等価
- β=ηのとき、vanilla LDA と等価(制約があっても)
- CANNOT Link の無い LDA-DF にモデルとして等価
- というわけで Interactive Unassignment が ITM のキモ
「β=ηのとき、vanilla LDA と等価」の証明
簡単のため V=3, w_1 と w_2 に制約が入っている場合で説明すると、
P(w_1, w_2, w_3|z) = Multi(ξ_1, ξ_2, ξ_3) について
P(ξ) = P(ξ_1, ξ_2)・P(ξ_3|ξ_1, ξ_2) である
ただし P(ξ_1, ξ_2)=Dir(η, η), P(ξ_3|ξ_1, ξ_2) = Beta(β, 2β) ( Dir(β, 2β) と同等 )。
このときη=βなら、P(ξ) は Dir(β, β, β) を積に分解したものに一致する■
実装してみた
- https://github.com/shuyo/iir/blob/master/lda/itm.py
- https://github.com/shuyo/iir/blob/master/lda/vocabulary.py
- Python + numpy + nltk
Usage: itm.py [options]
Options:
-h, --help show this help message and exit
-m MODEL model filename
-f FILENAME corpus filename
-b CORPUS using range of Brown corpus' files(start:end)
--alpha=ALPHA parameter alpha
--beta=BETA parameter beta
--eta=ETA parameter eta
-k K number of topics
-i ITERATION iteration count
--seed=SEED random seed
--df=DF threshold of document freaquency to cut words
-c CONSTRAINT add constraint (wordlist which should belong to the
same topic)
-u UNASSIGN, --unassign=UNASSIGN
unassign method (all/doc/term/none)
まとめ
- 結構おもしろい＆使えるかも
- もっといろいろ実験してみたい
- 実装公開したので興味のある人は試してみて
- η(=100)が大きすぎる気がする(グラフの赤)
- apple や service(礼拝) など複数のトピックに分布する単語を全部同じ制約の単語に結びつけてしまう
- η=2 (グラフの黒)くらいでいいのでは？ 収束が遅い？
- ヒューリスティックだが、ηを最初は大きく、徐々に小さくしていくとか。
- 制約ごとにηを変えてもいいかもしれない
- 多義性を持つ単語を制約に加えた場合の振る舞いも確認しておきたいところ
References
- [Hu+ ACL11] Interactive Topic Modeling
- [Blei+ 2003] Latent Dirichlet Allocation
- [Andrzejewski+ ICML09] Incorporating Domain Knowledge into Topic Modeling via Dirichlet Forest Priors
- [小林+ 2011] 論理制約付きトピックモデルのためのディリクレ森事前分布構成法
2011-07-13 今回のポイントは R でコマンドライン処理？(笑)
ロジスティック回帰でいろんな特徴関数を試す
前回に続いて、ロジスティック回帰で遊ぶ。
まだ線形の特徴量しか試していなかったので、二次項や RBF (距離に基づく特徴)も追加し、イテレーションももっとたくさん行うようにし、また初期値や学習順によって結果が変わるから、テスト自体も複数回行えるようにした。
そうなると、さすがに対話式インターフェースでコピペ実行というわけにもいかないので、スクリプトにて記述。
分布図を吐かせるかどうか、テストを何回行うかはコマンドラインから指定できる。
R -q --vanilla --slave --args --chart -i 5 < lr.r
--args の後に --chart を書くと分布図を出力し、-i でテスト回数を指定する。
ここの実際の処理はこのように書いている。エラー処理？ なにそれおいしいの？
commandline <- commandArgs(TRUE) chart <- "--chart" %in% commandline i <- match("-i", commandline) if (is.na(i)) { I <- 1 } else { I <- as.numeric(commandline[i + 1]) }
このくらいのコマンドライン処理のモジュールは標準で付いていてもいいがするのだが、R は対話で使うもの、という確固たる信念でもあるんだろうか。
ちなみに -q や --vanilla などは R 本体のオプション。詳しくは説明しないが、付けておかないといろいろめんどくさい……
"R -q --vanilla --slave --args" までを小文字の r などに alias してしまって、普段はそちらを使う、などするのが便利かもしれない(苦笑)。
話をロジスティック回帰に戻す。
iris はもともと4次元のデータなので、それらを で表すと、今回実装してみた特徴は次の通り。括弧内は特徴空間の次元。
- 線形(5)
- 1, x_1, ..., x_4
- 二次(15)
- 1, x_1, ..., x_4, x_1^2, x_1x_2, ..., x_3x_4, x_4^2 (全ての2次以下の項)
- RBF(1297=6^4+1)
, ただし μ_j は 各 x_i ∈{-2.5, -1.5, -0.5, 0.5, 1.5, 2.5} である格子点、s=1, ..., 10
RBF にはいわゆるガウス基底を持ってきた。ただし尺度のパラメータは単純に整数値を選んでいる。
学習率は 0.1 から始めて、1周するごとに 0.95 倍しながら、0.0001 を下回るまで学習を繰り返す。
これらの特徴についてそれぞれ5回ずつ実行し、誤差(交差エントロピー)の平均を取ってみたのがこちら。
Linear Features: error=11.4314 Quadratic Features: error=6.888 RBF Features (s=1): error=8.6134 RBF Features (s=2): error=6.706 RBF Features (s=3): error=6.3842 RBF Features (s=4): error=6.1398 RBF Features (s=5): error=6.256 RBF Features (s=6): error=6.244 RBF Features (s=7): error=6.5798 RBF Features (s=8): error=7.6184 RBF Features (s=9): error=7.8868 RBF Features (s=10): error=8.5274
実は RBF で大量に素性を増やして、過学習的振る舞いを起こす => よし正則化しましょう！ という流れになる予定だったのだが、2次でほぼ精度が頭打ちになってしまっている(そもそも線形でもそんなに悪くない)というのが痛い(苦笑)。まあ、iris データセットはお行儀が良すぎるので、だいたい予想していたとおりではあるんだけど。
ガウス基底の尺度で精度にそれなりに差が出ることを見て取れることくらいが救いかな。
というわけで目論見を外してしまったのだけど、めげずに当初のストーリー通りに進める。
次回はこのロジスティック回帰＋確率的勾配降下法に対して、そもそも今回の主目的である FOBOS を使った L1/L2 正則化を適応してみる。データセットもちょっと他のを見繕ってみる。
お楽しみに。
2011-05-19 PRML 読んでやってみた（下巻編）
PRML 読んでやってみた（下巻編）
昨日の記事を書いて、そういえば「パターン認識と機械学習」(以下 PRML) 上巻については「やってみた」「試してみた」系の記事をまとめページを作っていたことを思い出した。
- PRML 読んでやってみた（上巻編）
そして、これの下巻編を作るの忘れてたので、ここにまとめておこう。
基本的には PRML を読む中で、本当にそうなのかなというあたりを手を動かしてみて確かめてみたという内容。実装は主に R で、たまに Python + numpy を使っている。
専門でない人間がやっているわけで、いろいろ間違っているかもしれない点はあらかじめ(実際、変分ベイズのときは盛大に間違えてた)。
6章 カーネル法
- PRML６章「ガウス過程による回帰」を R で試す
5章までとはまた全く異なるガウス過程＆カーネル法に苦心して、いいやとにかく実装してみよう！ というもの。
記事を読めばわかるが、実装してはみたものの、あまり理解できていない(苦笑)。まあそこらへんはご愛敬。
7章 疎な解を持つカーネルマシン
珍しく何も実装していない。SVM があんまり気に入ってないので(汗
まあでも、1回くらい実装してみてもいいかも。
8章 グラフィカルモデル
この章はもともと実装できるネタが少なく、せいぜいイジングモデルによるノイズ除去(8.3.3)と max-sum (8.4.5) くらいなのだが、本文抽出で使った条件付確率場でマルコフ確率場を、隠れマルコフ(13章)の実装で Viterbi を、それぞれ実装してしまったので、おなかいっぱい。
9章 混合モデルとEM
K-means と EM アルゴリズムを実装。
- 「パターン認識と機械学習」(PRML)読書会 #11 + R で K-means
そして9章の章末にほんのり登場している、オンライン EM も実装してみていたり。
収束に必要なイテレーションの回数が少なく済むこと、局所解にハマりにくそうな手応え、を感じた、気がする。
- 多次元混合ガウス分布での incremental EM 更新式
- オンラインEMアルゴリズムで混合ガウス分布推論
10章 近似推論法
- 変分ベイズ実装(PRML 10.2)
- 混合ガウス分布の変分下界の計算式
- PRML 10章の変分ベイズによる混合ガウス分布推論の検証（フォロー編)
変分ベイズによる混合ガウス分布の推論を実装してみたが、実装にしょうもない間違いがあって、「混合成分が多すぎても縮退しない」という誤った結論を出してしまって、各位に少々ご迷惑をかけてしまったり。
でもおかげで知見や知己を得られて、個人的には大変よかった。
11章 サンプリング法
取り上げられているサンプリング法を、ほぼひととおり試してみている。
- PRML 11章の重点サンプリングと SIR を試す
- 多変量正規分布をギブスサンプリングで
- スライスサンプリングで単語ごとの出題率に沿って抽出
- ハイブリッドモンテカルロ試してみた。
- ハイブリッドモンテカルロをもっと試してみた
サンプリング法は正直最初なんかしっくりきてなかった。いろいろ実装しているうちになんかわかってきた気がする、という雰囲気に。
しばらくしたら「あれーやっぱりなんかまだよくわからん……」とヘコむ程度の理解度なんだけどね。まあ、理解というのはそうやってちょっとずつ進んでいくもんです(うんうん)。
12章 連続潜在変数
主成分分析を、こちらも紹介されている手法をほぼ一通り。
- PRML 12章 主成分分析を試す(棒読み
- PRML 12章 確率的主成分分析を試す
- PRML 12章 主成分分析を EM アルゴリズムで解いてみる
- PRML 12章 ベイズ的主成分分析を R で
- PRML 12章 カーネル主成分分析を R で実装(棒読み)
ヒマなの？ いやいや、必ずしもそういうわけじゃあ。
13章 系列データ
- 隠れマルコフ実装してみた。
いやあやっぱり PRML ここまで読んだら実装してみたいよね。隠れマルコフ。
しかし、実装にはこれだけの内容をきちんと理解しなければならず、他の章の「試してみた」とはハードルの高さがだいぶ違う。
- 最尤推定(EM アルゴリズム) (13.2.1)
- Baum-Welch(フォワード・バックワード)アルゴリズム (13.2.2)
- スケーリング係数(13.2.4)
- Viterbi アルゴリズム(13.2.5)
- 複数系列を用いた学習 (演習 13.12)
- HMMからサンプリング(生成モデル) (13.2)
- left-to-right HMM (13.2)
ちょうどほぼ最後の章なので、「HMM の実装」をPRML を読むときの目標にしてみるといいかも。
14章 モデルの結合
特にお試し実装はしていない。
アンサンブルとかはもう実地で試し始めていたので、わざわざ「やってみた」しなくても、という感じ。
今、社内で PRML 読書会をしている。
そこでまた実装してみたくなったら、このまとめページにも記事追加されるかも。
