7/28 に行われた nokuno さん主催の ICML 2012 の論文読み会にのこのこ参加。お疲れ様でした＆ありがとうございました＞各位
「えーまたトピックモデルなの？（ぶーぶー）」とブーイングを浴びつつ、[Kim+ ICML12] Dirichlet Process with Mixed Random Measures を紹介してみた。発表資料はこちら。
論文では Stick Breaking Process と Polya Urn の２つでモデルを表現していたが、そのあとどうせ Gibbs sampling するなら Chinese Restaurant Franchise の方がわかりやすかろうというわけで、がっつり絵を描いてみた(手描きだけど)。
DP-MRM は一言で言うと「教師ありノンパラトピックモデル」。
あるいは別の言い方では、Labeled LDA [Ramage+ EMNLP2009] のノンパラ版。
Labeled LDA は数ある教師ありトピックモデルの眷属の一つで、個人的にはこれまでに評価したことのあるものの中で一番使い勝手が良い印象。
実装は非常に容易で、普通の LDA の Collapsed Gibbs sampling ＋１０行程度で済む。Python で実際に L-LDA を実装してみたのがこちら。
ただし L-LDA ではラベル-トピック対応を明示的に指定する必要がある。またシングルラベルの場合は、全てのドキュメントに(共通の) second label (推論によっておそらく stopwords 類にひもづけられることが期待される)を与えるなどの工夫を行わないとかなり貧弱なモデルになることがわかっている。
L-LDA 論文では１ラベル１トピックで対応させているが、１対多の対応付けも例えばラベル web を web1, web2, web3 などに展開すると考えれば一応できる。が、各ラベルにいくつのトピックを対応させるか人手であらかじめ決める必要があるし、その対応も決定的なものになってしまう。
また Java と Python などのラベルは共通したトピックを持つだろうということも予測されるわけだが、そういうさじ加減もすべて手動でコントロールする必要がある。
一方本論文の提案する DP-MRM はそのラベル-トピック対応が階層化され、その対応が自動決定される(しかも確率分布として得られる)。
これは L-LDA の先ほどの難点を見事に解消するもので、かなり本気で嬉しい。
ただしノンパラベイズなので推論はやっぱりめんどくさい。ただでさえめんどくさい HDP-LDA の、さらに1.5〜２倍くらいのコード量になるかも？
ぶっちゃけ、個人的には喜びポイントはトピック数が無限個なところではなく、ラベル-トピック対応が階層化されているところなので、そこを DP ではなくディリクレ分布に置き換えることが出来れば、実装も少し楽＆推論も速くなってハッピーになるんじゃあないかなあ。ちょっとあとで考えてみる。
ところで、資料を slideshare にあげたら、twitter にて @torotoki さんからあれこれつっこみをいただいているうちに、ラベル-トピック対応を 1対多にする場合について L-LDA の論文に書いてあると勘違いしていることに気づかせてもらった……。お恥ずかしい。多謝。
ACL/EMNLP 読み会もスケジュールが合えば８月にでもやりましょう、という話あり。
あと TokyoNLP が @kisa12012 さん主催の TokyoML になる(断言しちゃった)。協力者を募集しているそうなので、われこそはという方ぜひ。勉強会は発表者を集めるのがやっぱり一番大変とのことなので、第１回の発表を予約しといた。TokyoNLP で機会があったらそのうち、と思っていた HDP-LDA の実装の話とかしようかな。たぶん。
ついでに発表分＆それ以外も含む ICML 2012 のミニ紹介。twitter でつぶやきそびれたやつもちらほら。
[Kleiner+] The Big Data Bootstrap
tsubosaka さんによる紹介資料。
Bootstrap を "Big Data" に適用する話。
bootstraping では n 個のデータから n 個復元抽出するが、そこには平均して 0.632n 個の異なり元が含まれてしまい[Efron+ 1993]、大規模データに対しては処理が全く軽くない。
そこで、b=n^0.6 個程度のかなり小さいサブセットをまず抽出し、それに対して n 個復元抽出(実際には多項分布の n 回試行でいい)をすることで、元の bootstrapping にかなり近い性能が出せますよ、というお話。
例えば n=10^6 なら、通常の bootstraping なら 6.32*10^5 くらいの異なり元になるところが 4000 程度で済むわけで、相当うれしい。実装も普通の bootstrapping に１行増えるか増えないかというレベルで、もう明日から使いますと言いたいくらい。
[Samdani+] Efficient Decomposed Learning for Structured Prediction
nokuno さんが紹介。資料公開はまだかな？
Structured Prediction と表題にあるが、内容的には Structured に特化した印象はなく。
loss function に gold output からの「距離」を加えて min-max 的アプローチをとることで、予想を外しにくい頑健なモデルが得られるが、探索時間が膨大になる。そこで探索範囲を gold output の「近傍」に限定すれば、探索時間を抑えつつ性能はあまり落ちないよ、という話。
その「近傍」を作るのに decomposition という考え方を導入してうまいことやるみたいなのだが、ちょっとまだそこらへん理解できてない。すんません。
[Biggio+ ICML12] Poisoning Attacks against Support Vector Machines
kisa12012 さんの発表資料＆エントリ
www.slideshare.net
SVM に対する Poisoning Attacks (訓練データへの悪意のあるデータ挿入)対策、かと思ったら、効果的に攻撃するには偽データをどう選択するのがいいか、だった。敵を知れば。
ブラックボックスではなく SVM への全入出力を把握できている設定なので、攻撃にしても余り現実的ではない気もするけど、少ない攻撃データで、どれだけ学習結果を歪められるかというのはおもしろい(MNIST での手書き数字モデルがかなり歪めることに成功している例が示されている)。
[Scherrer+] Scaling Up Coordinate Descent for Large L1 Regularization Problems
sleepy_yoshi さんの発表資料＆エントリ
最適化手法の一つ Coordinate Descent を並列化した Shotgun Algorithm[Bradley+ ICML2011] を含めた一般的なフレームワークを考察し、さらに新しい手法についても提案する、という話。
Shotgun はランダムに選んだ複数の座標それぞれで並列に coordinate descent して、その結果をすべて反映する、というまあ普通に考えても若干乱暴なアプローチ。適当にぶっ放して全部あたったらボロ儲け、Shotgun とは実にうまく名付けたもの。まあでも高次元の空間なら案外うまく行っちゃうんだろうかなあ。
本論文で提案する THREAD-GREEDY は(ちょっと論文の記述に齟齬があって正確なところはわからないものの)、Shotgun の結果のうち、一番いいのをひとつ採用するというアプローチ。足が遅くなる分、正確に……と思いきや、収束もかなり速いという結果が示されており、ちょっとまあ本当かなあ。確かめずに受け入れられるほど楽観的に離れない感じ。
Coordinate Descent はまだ使ったこと無いので正直ちょっと良くわかってなかったが、なんかハマるところがあれば使ってみようかな。
[Bischof+] Capturing topical content with frequency and exclusivity
Proceedings の目次ではこの表題だが、論文 pdf では "Summarizing 〜" となっている。なぞ。
Summarizing とあるから要約なのかと思って読んでいたらどうも話が合わない。最後の実験を読んで、ようやっと特徴語の抽出タスクを解いていることに気づいた。えー。もっと早く気付け？
モデルの複雑さ(Hierarchical Poisson Convolution)がタスクに対してオーバースペックな気がする(個人的な印象だけど)。
一応「階層化されたラベルが振られたドキュメントに対して exclusivity を考慮した特徴語の抽出が可能」であることがキモらしいんだけど、tf-idf に対して定性的にどれくらいいいのか気になるところ。
[Purushotham+] Collaborative Topic Regression with Social Matrix Factorization for Recommendation Systems
協調フィルタにソーシャル・ネットワークを組み込む話。
LDA を拡張した CTR(Collaborative Topic Regression) と SMF(Stochastic Matrix Factorization) を組み合わせたちょっとおもしろい感じのモデル。
SMF なしに比べ recall が 0.1〜0.2 程度上がるという結果なので、おそらく定性的に違いを感じられるほどのことはないんだろうなあ。
余談だが、notation がくちゃくちゃで読みにくかった……。
[Paisley+] Variational Bayesian Inference with Stochastic Search
変分ベイズの変分下界に必要な期待値計算に重点サンプリングを使う。その分散を十分小さくするにはサンプリング数が非常に多くなるわけだが、それを小さく抑えるために control variate という手法を組み合わせるよ、という話。ちょっとトリッキーでおもしろい。
そして実際に適用する手法の一つが HDP はもちろんいいんだけど、もう一つが Logistic Regression って個人的には うーん。しかもデータセットの一つが iris って、いやいやこらこら、みたいな。
[Minmo+] Sparse stochastic inference for latent Dirichlet allocation
Online LDA [Hoffman+ NIPS2010] の拡張になるのかな？
なにげに読みすすめてみたら、LDA を VB と Gibbs sampling のハイブリッドで解く！ とあって、なんか妙に高まる期待。
実際は topic z の推論にはサンプリングを、topic-word 分布の推論には VB っぽい手法を使うという、うーんちょっと期待はずれな感じ（何を期待したんだか）
実装は簡単そうなので、さくっと書いてみるのも楽しそう。そういえば Online LDA も実装しようかなといってほったらかしだったわー。
比較対象にあげられていたトピックモデルを sequencial Monte Carlo(つまりパーティクルフィルタ)で解く [Ahmed+ 2012] ってのも個人的に気になる。あとで読んでみよう。
[Mnih+] A fast and simple algorithm for training neural probabilistic language models
Neural 確率言語モデルの推論を簡素化した話。
Neural 確率言語モデルの一番簡単な log bilinear model を近似推論、長距離の素性を入れても現実的な時間で学習できるようになりましたよ、ということかなあ（自信なし)。
本論文によればもともと neural 確率言語モデルは n-gram より性能がよいそうな(余計な独立性の仮定が要らないから？)。予測や文生成には使いにくそうだけど。あまり知らないから一度他の関連論文も読んでみたいところ。
[Yang+] Clustering by Low-Rank Doubly Stochastic Matrix Decomposition
アイテム間の類似度を使ってクラスタリングを行う手法。タイトルには行列分解とあるが、あまり行列分解しているようには見えない。
pLSI によく似た式から出発して、最終的に item-topic distribution を得るという流れなのだが、一つ一つの手順の動機がつかめなくて、わかった気になれなかった。実験結果の数字は他の手法に比べてずいぶんいいのだが……。
類似度(確率)行列はアイテム数×アイテム数という巨大なものだが、提案されているアルゴリズムはそれに対してナイーブにループしているように見える。計算量大丈夫かなあ。
[Shivaswamy+] Online Structured Prediction via Coactive Learning
検索結果のクリックなどのフィードバックを通じてランキングを改善するという、ここまではよくある枠組みの話だが、そのフィードバックは best ではなくあくまでも better な解であるという自然な条件を想定して、その点をモデルに組み込んでいるのがポイント(表題の "coactive" はこのことを指している)。
"フィードバックはbestではなくbetter" をモデル化するために strictly α-informative という仮定を入れる。入出力の組を評価する utility 関数 U (大きいほどよい)に対し、予測解とフィードバックの差が、予測解と最適解の差のα倍で下から抑えられる(0<α≦1)、というもの(実際には slack 変数を入れてミスを許容)。柔らかく言うと、フィードバックは十分改善されていることを保証、みたいな？
αをいくつか変えて実験し、α=1 のとき regret 最小という結果。
あれれ？ α=1って「フィードバックが最適解」と同等だから、それが一番性能がいいってストーリー的におかしいよね？
実は、モデル設計時点では utility関数 U を "unknown to the learning algorithm" としているにもかかわらず、学習では U を特徴の線形結合とおき、そのパラメータを学習で決めている。
そうすると「得られたフィードバックが【最適解】となるように U を学習」することになり、そりゃそういう結果になるに決まっている。問題設定は非常に興味深かっただけに、とても残念。
[Wang+] Stability of matrix factorization for collaborative filtering
協調フィルタリングにおける行列分解の、敵対的ノイズに対する安定性（ロバスト性）がどれくらいあるかを理論的に評価したもの。
the ground truth との RMSE (二乗平均平方根誤差……日本語だとかえってわからないなｗ）に対する確率的な上界を導くのだが、the ground truth の定義（何をもって the ground truth とするのか）がよくわからなくてもやもやする。おそらく「ノイズがなかった場合の大域最適解」なのかなあ。
実用的というより、ちゃんと評価してくれている人がいるからと安心するお話。
[Defazio+] A Graphical Model Formulation of Collaborative Filtering Neighbourhood Methods with Fast Maximum Entropy Training
collaborative flitering には、隠れたトピックによって users と items が結び付けられていると考えるアプローチである latent-factor models (LSI の眷属)と、users と items の bipirate graph によって表現する neighbourhood models があり、この論文は後者を maximum entropy で解くにあたって、必要になる勾配をえいやと近似して解いてみた、というもの。
結果を見る限り、latent-factor models と大きな差があるように感じられなかった。metric をいろいろいじることができるのが、現実の問題に当てはめるときに嬉しかったりするのかなあ。
[Sato+] Rethinking Collapsed Variational Bayes Inference for LDA
LDA を VB で解くには、オリジナルの生 VB [Blei+ 2003]、Collapsed VB [Teh+ 2007]、CVB で事後分布の近似にテイラー展開の2次の項までとっていたのを、0次項(!)で済ませる CVB0 [Asuncion+ 2009] があるのだが、この中で直感に反してなぜか CVB0 が一番性能がいいことが経験的に知られている。これについて理論的な裏付けを与えることが出来ないか、という話。
CVB0 の推論は α-divergence (PRML にもちらっと出てたやつ）を最小化（ただしパラメータごとに α=1 だったりα=-1 だったりする）と同値であること、zero-forcing effect(パラメータを潰そうとする効果、かな？) が CVB0 の方が CVB より範囲が限定されていること、それらが効いているのではと考察。
こういう「ナイーブベイズがなぜ性能がいいか」的な話は、実際の応用に必ずしも役に立つわけではないが、おもしろい。
余談だが、この佐藤さんの論文はとても読みやすかった。
notation がデタラメだったり、かいつまんで読むと意味が取れなくなったりする論文も珍しくないのだが、Notation が整理されていて、各 section の論旨も明確。きちんと書いてあるとこんなに読みやすいんだなあ、と変なところで感動。
[Charlin+] Active Learning for Matching Problems
Matching Problem とはユーザに適したアイテムを割り当てる(あるいは逆)という、一見 Collaborative filtering と同じに見えるが、「ちょうど１つずつ、重複なく」割り当てるという設定になる。
Collaborative filtering より問題の難易度が相当上がるが、ぶっちゃけ使い道が思いつかない……。ので、具体的は提案手法のところまで読まなかった。ごめん。
[Weston+] Latent Collaborative Retrieval
Collaborative Filtering の手法は数あれど、それに query を加味したものはほとんどない、という abstract で始まり、えーそうかなあ、Personalized な IR とかでは近いことやってそうだけどなあ、といぶかしみつつも読みすすめていたのだが、"Q is the (finite) set of possible queries" というところでひっくり返ってしまい、断念。
いやあ有限のクエリーセットの研究はたしかに少ないかも。うんうん。
