一昨年くらいに，今はNAISTに言ったK君に紹介してもらった論文．

今から考えるとお恥ずかしい話なのですが，当時はGaussian Process をよくわかっておらず，

その時は意味をとることができませんでした．今なら，ワカル！！！！

ってことで NIPS ‘08 の論文です．

著者は

Erik B. Sudderth and Michael I. Jordan

でいつもながら，ジョーダン研ですね．

ホントにこのラボは凄いですね．

ちなみに，Erik B. Sudderth さんは， 僕がここ２，３年よく使っている．

E. Fox の sticky HDP-HMM の共著者というところでも，認識しています．

本論文は， Segmentation of Natural Scenes ということで，

自然画像の領域分割を扱っています．

複雑なように見えて，意外と素直なアプローチに思えたので，良いと思います．

まず，第一歩として，写真の領域を人手でくくって，名前をつけたデータに対して，

そのラベルと，生起頻度がべき乗則を満たしているということを指摘します．

このあたり，よく考えると，自然言語文の単語生起そのもので面白いですね．

ゆえに，その頻度をモデル化するのにDPよりも Pitman-Yor 過程がいいだろう．という主張になっています．

# ただ，本件については，どこまで本質的かは，私は判断つかない．

次に，画像の領域分割の生成モデルを与えます．

３章でシンプルなBags of image features モデルを導入します．

基本的には，super pixcel 毎にtexture color のカテゴリが対応して，そこから多項分布で

生成される．というモデル．

LDAのセンスそのまま．

しかしながら，このようなモデルだと，空間的な連続性を与えられない．という話が出てきます．

そこで，４章にて 裏に，GPを走らせて，空間分割をやろうという．

Spatially Dependent Pitman-Yor Process の考え方があらわれます．

どうもこのあたりのアイデアは， [24] J.A. Duan 2007 のアイデアっぽいのですが，非常にセンスが良いように感じました．

おもしろい．

まず，sticky breaking-process が[0,1] 区間の値による，棒の切れ端の切断の繰り返しだということを思い出します．

通常，その切断はBeta 分布でやるんですが，ここでは，Gauss分布を上手く使うことによって，実現します．

それは，Gauss分布の累積分布関数(CDF)を持ってきます．そこで，vという確率に達する変数をu=Φ^{-1}(v) として計算できるようにします．結局このCDFの逆関数を介せば，0 or 1 の値を出す，関数がGauss をバックに構成できるわけです．

（４）式は地味にけっこうキモ．

このアイデアと stick breaking-process をくっつけることができる．

GPは基本的には平均関数mに従うので，分散共分散関数由来の，空間的な相関性を持ちながら，

上記のようなガウス分布のかわりを成すことができる．

学習は変分法を導入しており，，これにより高速に計算できる．

わざわざ，うつさないが，パフォーマンスは極めてよいようで，

多手法を圧倒しているようにみえる．

個人的には Gaussian Process と PYPのくっつけ方が実に上手いと思った．

これは，もっと他にも応用の可能性があるのではないかとおもいます．

ちょっと，今日は眠すぎたので，説明がわからなくなってしまった・・・・．

また，気が向いたら，もう少し分かりやすく書きます．ではでは．

Understanding the metropolis-hastings algorithm

Chib, S. and Greenberg, E.

American Statistician, 1995 – JSTOR

pages={327--335}

を読んでみた．「なに！今更！」とかいうツッコミはやめて下さい．

僕のベイジアンっぷりは完全に付け焼刃なので，基礎が欠落してたりするんですよー．

メトロポリス-ヘイスティングス法は PRMLで読んで，ユーザとしては理解していたつもり

でしたが，何といいますか，ちゃんと腑に落ちてなかったのですね．

上のような論文を得まして，読ませて頂きました．

非常に分かりやすく，Acceptance-rejection samplingの話しなどを交えながら

書いていただいております．

で，どういう理由で，メトロポリス-ヘイスティングス法の acceptance ratioが出てくるのか，

何を前提にしているのか，などが順を追って書いてあります．

メトロポリス-ヘイスティングス法だけについての文章ですし，

また，1995年(17年前！？？)　ということで，当時の「背景」も臭ってきて，

いろいろ腑に落ちました．

メトロポリス-ヘイスティングス法とか，Gibbs sampler とかは，

「アルゴリズム」

として，受け入れてしまってやるのは，簡単なんですが，

その奥のココロをわかっておいた方が，やっぱり良いなぁ，と思う次第です．

巨人の肩より下を理解してから，巨人の肩に乗っていきたいものです．

ありがとうございます．

ただ，まぁ，PRMLをちゃんと読んどきましょう．って話もあります．^_^;

How to Grow a Mind: Statistics, Structure and Abstraction
Josh Tenenbaum

NIPS2010で行われた講演．

MITのProfessor

D.Roy や Kemp, Griffiths,らの師匠なんですね．

若いのにスゲェ・・・．

心を機械学習でモデリングする，理解しようという人にとっては必聴の講演だとおもいます．

とても，よかったです．

Topic的にも多岐に渡っていますが，

基本的には Graphical model, Nonparametric Bayes などのモデルで

人間の心のプロセスを表現しよう という感じのアプローチ．

で，工学的にも効果的な事ができているので，

まったくもって，私としては共感できるお話でした．

http://web.mit.edu/cocosci/josh.html

ちなみに NIPS2010は現地に居たはずなんですが，，，，

多分時差ボケで死んでいた時かもしれません，，，，

Variational MCMC
Nando de Freitas, Pedro Hojen-Sorensen, Michael Jordan, Stuart Russell

http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=2&smnu=2&article_id=91&author_id=4

を読みましたので，そのメモです．

名前の通りで，とてもシンプルでかつ読みやすい論文でした．

もう１０年も前の論文ですが，分かりやすいポイントを突いているのではないでしょうか？

基本コンセプトは全くシンプルで，acceptable

Variationl Bayes （変分ベイズ）では，分布を変分近似して推定しますが，大域最適まで持って行け無い．

いっぽうで，MCMC（メトロポリス＝ヘイスティングス法を基本に考える）では，提案分布自体が，対象の確率分布と

随分違えば，良好な結果が得られない．

そこで，提案分布を近似でいいから，元の分布に近づけて上げようというはなし．

VBで近似した分布を提案分布に使って，サンプリングするんですね．

VBの説明から丁寧にしてあるので，読みやすいです．

しかし，ここまでなら，とても，ストレートなのですが，実は，

We show that naive algorithms exploiting this property can mix poorly,

というのがニクい ポイント．

つまり，ただ，VBで近似した分布で提案続けても，あまり良くないよー．

ということ．

なんで？？ の説明は３章冒頭に書いてあって

Both the importance
sampler and independent MH algorithm are well
known to perform poorly in high dimensions unless the
proposal distribution is very close to the target distribution
(Geweke 1989, Mengersen and Tweedie 1996).

ということ．VBで提案分布をつくっても，確かに，サンプリング対象の分布には近いかもしれないが

一回一回のサンプルを独立にとっていたのでは，なかなか，ずれた対象分布をサンプルできない．

MCMCとしては，サンプリング出でてきた点を上手く利用しながら次のサンプルを作っていったほうがいいのだ．

そこで

but address this problem by introducing more
sophisticated MCMC kernels based on block sampling
and mixtures of MCMC kernels

ということになる．

前者が 3.1 後者が 3.2に書かれている．

後者は，基本的には，遷移カーネルの混合や，積も同様に遷移カーネルになるよね．

という話で，それを上手く使っていこうということ．

一方で前者の block sampling はサンプリングしたデータをとっておいて，

Gibbs sampler みたいに，サンプル対象の変数以外を固定して，サンプリングするというもの．

そうすると，他の変数が引っ張ってくれるので，徐々に，対象分布をサンプリングしてくれるって

寸法ですね．

http://uai.sis.pitt.edu/papers/01/p120-de_freitas.pdf

まぁ，このくらい明確に差はでますよと．

感想としては，

コンセプトとして分かりやすく面白いかな と思いました．

わざわざ変分ベイズを使うかはおいておいて，

提案分布に近似分布を用いて，メトロポリス＝ヘイスティングスでblock samplingを使うというのは

とても有用そうだし，適用もしやすいように思いました．

ちょうどそういうアルゴリズムを考えていた際に， twitter で @issei_sato さんに教えていただいた論文でした．

感謝！！

まちがっていたら， @tanichu までつっこんでください．

ここ１年ちょっと MCMC と強化学習をくっつける類の妄想にとらわれていたのだが，あんまり，その手の話は耳に入っていなかった．

# ここ二年半は完全に頭がノンパラメトリックベイズに始まるベイズへの傾倒中．

前出の annotated hierarchy や mondrian process などの物色中に，関連しそうな文献を発見したので読んでみた．

Bayesian Policy Search with Policy Priors
David Wingate, Noah D. Goodman, Daniel M. Roy, Leslie P. Kaelbling and Joshua B. Tenenbaum

Proc. Int. Joint Conf. on Artificial Intelligience (IJCAI), 2011.

http://www.stanford.edu/~ngoodman/papers/WingateEtAl-PolicyPrios.pdf

である． D. Roy はここのトコロ 連打で読ませていただいているMITの若手．

Kaelbling はかなり昔から強化学習で名前が出ているMITの先生ですね．

博士課程時代も文献読んで いろいろ勉強させていただいた気がします・・・・

さてさて，主なウリとしては 強化学習の Policy の学習に Priorr を入れることで，Transfer learning みたいなことが出来る

的な話なのだが，ポイントは，

1. 強化学習のPlanning optimization（学習）を Inference 問題に置き換えるところ

2. MCMC で推定するところ

だ．

１．については，過去の研究では 最尤推定に持って行って，EMアルゴリズムとつなげることが多いようだが，

それを事前分布を持つことで MAP推定に置き換えている．そして その御蔭でPrior の入り込む余地が生まれる．

ということのようだ．

１．Inference に置き換えるプロセスだが， ざくっというと 評価関数を expに置き換えて，無理やり

確率分布にしてしまう類のやつだ．僕もチャンク抽出でやったことがある．

数式的には本文引用だが

これがreference していた論文など．

ここでcomplete

ちなみに， Policy の改善は 新しい 方策を提案分布から提案し，価値関数から確率を出して

採択するかを決めるという メトロポリス・ヘイスティングス法を使っている．

このために，価値関数は求められる（！）という，仮定を入れている．

# 結構凄いな・・・

様々なprior を準備して，有効性を検討している．

Prior 間の比較はあるのだが，他手法との比較がないので，本手法のパワフルさはよくわからなかった．

MCMC を使った強化学習ということで，ちょっと面白くはあったし，

報酬値->価値関数を何とか確率モデルの中に包み込んでしまいたい

というモチベーションは一緒なので，こういうのをもっと進めていければとおもいますね．

僕としては行動生成の a の選択の乱択を上手く含められたらいいように思うんですがねー．

以下，本論文の関連でざっとよんだ．

Hierarchical POMDP Controller Optimization by Likelihood Maximization

Marc Toussaint et al.  UAI ‘08

http://uai2008.cs.helsinki.fi/UAI_camera_ready/toussaint_revised.pdf

video lecture

http://videolectures.net/uai08_toussaint_hpco/

では Hierarchical finite state controller という方策器をEMアルゴリズムで最適化するという話．

トリックとしては，discount parameter を 徐々に長さを伸ばしていくDBNのmixtureを扱うというもの．

EMはlocal minimam にはまるよね．とは，言及している．

EMを使ったplanningを Marc Toussaintが示したのは，ICML 06

Probabilistic Inference for Solving Discrete and Continuous State Markov Decision Processes

Marc Toussaint and Amos Storkey

のようでした．

http://eprints.pascal-network.org/archive/00003921/01/ToussaintStorkey2006ProbabilisticInferenceSolvingMDPs.pdf

ここで， DBNのmixtureを扱うことを提案し MDPの場合に Planning を EMで解く方法を提案している．

コレはメモですので，

間違ってたらご指摘下さいませー．

Inference を使った強化学習では

Toussaint さんが activity高そうですね．

The Mondrian Process
Daniel Roy

2008年 Teh さんも共著の Mondrian Process の発表

視覚的にキャッチー（？）で興味を引く．

まだ，キラーアプリ（というかいいInference method ?）が無いようですが，

D. Roy 自身も，Teh さん自信も なんとなく端々から，けっこう「気に入っている」様子なのです．

僕も気になる存在ではあります．

簡潔にいうと  DP の多次元拡張．

より，感覚的に言うと Stick Breaking Process の 多次元拡張です．

棒を折っていくのではなくて，面を切っていくというプロセスになります．

モチベーションとしては，

Royさんらが提案してきた Annotated Hierarchy とかは， Relational Data に対しての

Tree clustreing を bi-clustering できるようにしているのですが，

Self-consistent ではないということ．

Goal: Self-consistent, multiresolution (ideally hierarchical)relational modeling

ということです．

Not satisfied by IRM, coalescent, annotated hierarchies

といっているだけに，このモチベーションは IRM ，Annotated Hierarchies あたりを押さえていないと

よくわからない気がします．

Mondrian Process の生成過程は木構造的なので再帰的にかけまして，

結局は縦方向と横方向に 予算 λが切れるまで分割し続けるというものです．

個人的には上の スライドの表記よりも 原著論文の 3.2 Generalizations tohigehr dimensions and trees の

方が簡単な例を示していて理解しやすいです．上の定義は 一般の測度まで自然に表現したもの．

↑3.2 に載っている簡単な例を 図解してみました． こちら．

本論文では，これを使ってrelational data の co-cluastering に持って行きたい気持ちは

十分に語っているのですが，よいinference 手法を提案するまでは行っていないようです．

実験では

We employed a number
of Metropolis-Hastings (MH) proposals that rotated, scaled, flipped, and resampled portions of the
Mondrian.

ということで，とにかく いろんな提案分布を使って混ぜながら， MH法で inference したとのこと．

個人的な感想としては，スキなんですが，

ここまで自由度をもたせたco-clustering での結果を「どう解釈するか？」というのも，

難しい問題だなぁと思いました．

自由度的には IRMよりも AH よりも上がっているわけで，，，，，，

とはいえ，数学的にはイケテル構造物のようなのでどこかでブレイクスルーすることを期待しております．

ちなみに，個人的には，面っていっているけど，これって，やっぱり値付きの木構造の生成じゃないの？

と思ったりもします．なんとなくなので，詳細はより踏み込まないといけませんが．

やっぱり，IRMの使い勝手の良さが，今は先にたってるかな，，，という気もします．

集合を積集合で捉えるのって，非常にGeneral なので・・・

では，最後に必見の， Mondrian Process 動画をどうぞ・・・・

現状，僕はあまりいい応用法を思いつきませんが，フォローしたいと思います．

そして，これが，現代美術家 Mondrian の絵です．

たにちゅー・谷口忠大・tanichu ‏ @tanichu

Mondrian Process の 動画 > http://youtu.be/JLotRY0fIug

筆頭著者のD. Roy さん 若いしカッコイイなー．@MIT

自分のホームページのアイコンがMondrian Processなのも好感が持てます．オイ．

本人のホームページはこちら http://danroy.org/

twitter は @roydanroy です．

MIT でPhD をとったばかりという若手の研究者ですね．

とはいえ，PhD Candidate 時代からバンバン 有名人と共著でNIPS始め出しまくっている感じです．

原著論文

http://danroy.org/papers/RoyKemManTen-NIPS-2007.pdf

さてさて，Nonparametric Bayes な Relational Data のクラスタリングに関わる論文なんですが，

# もはや，どこからどこまでがノンパラベイズか，僕のなかでわからなくなってきつつありますが・・・・．

本論文は Mondrian Process の2年前，Infinite Relational Model の１年後の 2007年にだされていますね．

abstract をざっと読んだ感じでは Infinite Relational Model のツリークラスタリングへの拡張かと思ったのですが，

単純に拡張というわけでもない．

もちろん，良く似ているものをシェアしています．

どういうことをやりたいかというと，

こういうことをやりたい．

複数の関係データがあったときに， それらを階層クラスタリングする，階層 Co-clustering ですね．

この階層，といか木構造がどういう意味での木構造を意味するかは，読んで洞察をえてもらうとして，

# 結局は generative model を理解しないと，どういう階層がえられるのかも見えてこない．

generative model いってみましょう．

本論文では，co-clustering で無い場合，普通のobjectに対して複数のfeatureが並んでいる場合の

階層クラスタリングの話しから入ります．

上のようなかんじ．

generative model としては，

１．木の生成 ＝ binary tree の一様分布からランダムに 木が生成される．

２．各subtree(結局はそのルートが生えてるエッジに対応)に対して 重み w_n を与える．（指数分布利用）

３．重みを用いた通過確率でルートから木を伸ばしていく．（１．でサンプルした二分木が全部使われるわけではなく，確率的に枝刈りされるイメージか？）

４．すべてのカテゴリー（subtree）に対して，ベータ分布からfeature を生成するための確率 \theta を割り振る

５．\theta を使って，Bernoulli分布を使って feature のon /off のサイコロをふる．

※４．５．はIRMと全く一緒ですね．

面白いのは，tree をツリー空間の一様分布からとってくるところと，そこから枝刈りをかけることで，

いろんな深さのクラスターを各データセットに与えているところでしょうか？

関係データでは，これを 縦・横 双方の軸にたいして 同時に行います．

ここで，ポイントは，実は，縦と横が 同じ集合であることを仮定している点．

ここは， IRM よりも問題として狭いです．

例えば， 学生名×学生名 で「AはBの友達」のようなデータセットを考えているわけです．

ゆえに，1. で生成する木も，縦横同じ木を生成します．

さて，こんなモデルですが，Inference はどうするのかというと，結局，Metropolis-Hastings (MH)アルゴリズムを

使わざるを得なくなります．

i. Subtree Pruning and Regrafting

ii. Edge Weight Adjustment

iii. Subtree Swapping

という提案をそれぞれ用いて，Metropolis-Hastings (MH)アルゴリズムを構成します．

あとは，実験などが載っています．

どういうものに応用するかは，考えないといけないところですが，

同じ集合間の関係性抽出が主なやりどころになるのではないでしょうか？

IRMよりかは，適用先は狭いのかな，と思います．

また，MH法を使っているために，IRMより収束は多分遅いのでしょう．

また，複数のデータセットを相手にしながらその奥に潜む共通のヒエラルキーを探すという視点で

ただのmixture でもないので， 関係データでない feature ベースの方だけでも，面白みは

あるかなとおもいます．

毎度，まちがってたらごめんなさい．

あくまで，僕の現状の理解です．

まぁ，とにかく 開いたら

が，目に飛び込んでくる Rose Treesの論文です．

1st author は Blundell さんですが， 2nd がノンパラベイズで大量に良い論文をかいておられる Yee Whye Tehさん

で 3rd が Heller さん．僕のなかでは IHHMM の論文が有名（無限階層の階層HMM ノンパラベイズ）．

Rose Tree とか僕はしらないので， 「なんやそれ」と興味をひかれていたが，放置していました．

Teh さんが HPでrecommend していたので，面白いのだろうと思っていた．

要は 階層クラスタリングでベイズ的にやりたいのですが，既存のものは Binary tree (二分木)が多いので

一気に複数にわかれる事のできる階層クラスタリングを作りましょう．という話です．

K. A. Heller and Z. Ghahramani. Bayesian Hierarchical
Clustering. In ICML, volume 21, 2005.

の拡張になっている模様．

Tehさんがスライドまでオープンにしてくれていて分かりやすかった．

http://www.gatsby.ucl.ac.uk/~ywteh/research/npbayes/brt.pdf

ありがたい！

階層的分類を考える場合には 階層的な分割Partition の生成であり，その再帰的な定義が必要になる．

このあたりが，そう．

スライドの方で，分かりやすく書いてくれているので，わかると思う．

で，その確率をどう与えるかというと，

ここが 僕的には面白いポイントだとおもうんですが，

各階層のPartitionの混合 mixture として，あたえるんですね．

数式的にはこれ．

We interpret a rose tree T as a mixture over partitions
in P(T) of the data points at its leaves D = leaves(T):

さらっと書いてあるけど，僕的にはこれがキモ．

次式もややこしそうだけど，ただの展開．

あとは，木の分かれ方で，混合率を与える．

で，推定はサンプリングで・・・・ といくのかとおもいきや，

それはcomplexity が高すぎて 無理とのことでGreedy 探索をします．

これが，Greedy 探索のための mergeの方法

ざくっというと

これらを適用してみて，尤度比が一番あがるやつを，適用していく

って感じみたい（だいたいの感じ）

Figure. 7 で GP mixture の話とかでてきてるけど，これはおまけ程度におもっておけばいい．

とにもかくにも，多分岐のツリーが作れるようになってバンザイ ということのようである．

ちなみに，先日書いた Pitman-Yor diffusion tree は，実数空間を前提にしたモデルだし，

それに比べると，空間や分布についての柔軟性はある．

# PYDT は面白いし好きなんですが．

Tree 関連 ノンパラ論文を nested CRP, PYDT, Rose Tree と読んでみたわけだが，

個人的には，Tree というものの 捉え方が まったくそれぞれ異なっていて，そのあたりが面白かった．

たにちゅー・谷口忠大・tanichu ‏ @tanichu

Bayesian Rose Trees だいたい分かった． Greedy search になってしまってるのが，Bayesian なわりに，悲しい感じもするが，パフォーマンスも良いようなのでいいのであろう．Tree を Partition のmixture と捉えるのおもしろい．

12:59 AM - 3 May 12 via TweetDeck · Details

たにちゅー・谷口忠大・tanichu ‏ @tanichu

"BRT and one version of BHC interpret trees as mixtures over partitions." これ，ポイントやな． > Bayesian Rose Trees

12:20 AM - 3 May 12 via TweetDeck · Details

たにちゅー・谷口忠大・tanichu ‏ @tanichu

なるほど， サーチは greedy サーチになっちゃうのか． hyperparameter は勾配でもとめるのか． 適宜そういう選択もするとっころはだいじやな．http://bit.ly/ITBWUK

12:17 AM - 3 May 12 via TweetDeck · Details

たにちゅー・谷口忠大・tanichu ‏ @tanichu

スライドを見て， A tree is treated as a mixture of partitions. の意味がちょっとわかった．．．． nested CRP に引き続き，tree を確率モデルとしてどう扱うか という事は なかなか 面白いところみたいな気がする．

12:00 AM - 3 May 12 via TweetDeck · Details

たにちゅー・谷口忠大・tanichu ‏ @tanichu

Bayesian Rose Trees の発表スライド http://bit.ly/ITBWUK

11:47 PM - 2 May 12 via TweetDeck · Details