これまたTehさんの

Modern Bayesian Nonparametrics.

http://www.gatsby.ucl.ac.uk/~ywteh/teaching/npbayes.html

の影響で読んでみた．

The Infinite Partially Observable Markov Decision Process

F Doshi-Velez

NIPS2009 http://nips.cc/Conferences/2009/Program/event.php?ID=1643

ですね．

POMDPは 強化学習でよく仮定する MDPと違い，状態s_t が直接観測できないという仮定のもの．

歴史的にPOMDPと呼ばれるが，個人的にはHidden MDPとでも呼んでみたい気がしますが，

まぁ，そういうものです．

銅谷先生らのモジュール型強化学習などをイジっていた身としては，

Dirichlet Process mixture が出てきた段階から，まぁ，連続状態変数を隠れ状態からの出力分布でとらえて

その上で強化学習とかしたいよね．とか思っていたわけなんですが，

まぁ，そんな感じのモデルです．

まだ，Theoreticalな部分先行で実ロボットでどうこうという話ではない．

内容は基本的部分はシンプルで，

DPで隠れ状態 s_t が生成されると，

それらが，iHMMよろしくで， s,a の条件の下で DPから生成された多項分布（つまりは，遷移確率行列）で次の状態にトランジションする．

また，観測o ,報酬 r がそれぞれの s,a に対しての分布として生成されますよという生成過程

とってもagree な内容となっております．

で，このあたりはいいのですが，

やっぱり，ただでさえ，学習に時間がかかったりする強化学習さらにPOMDP．

Action Selectionの方が大変になっています．

実際には，belief を求めるのも， 複数のモデルをサンプルしてその上での信念分布を考えて

これの重ねあわせで考える． Q値も同様に考えるといった，近似を導入しています．

このあたりは，個人的には苦しそうな印象．

また，最適政策も求めにくいので，

Given a set of models, we apply a stochastic forward search in the model-space to choose an action.
The general idea behind forward search [14] is to use a forward-looking tree to compute the value
of each action.

ということで，フォワード探索で頑張って決めていきます．

実験では，ちゃんと動くぞ，というのを示していますが，

確かに状態数の推定はいいのですが，

そこからの強化学習としての方策生成まで，うまくつなげて綺麗な理論にするのは大変やなぁと思いました．

ただ，ノンパラベイズからの強化学習へのアプローチとしては，非常に素直だとおもうので，一読の価値はあるかと．

POMDPやんなきゃ感 カンジテル・・・・

※本 メモは大いに間違っている可能性もあるので，間違いに気づかれた方は，心優しくツッコんでください．

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

強化学習 Natural Actor-Critic が流行っていたあたり つまみ食いした以降は ちょっとサボっていました． 現状は どうなっているんでしょうね．

8:51 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

POMDPとSLAMの関係について．

8:49 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

しかしまあ，どんだけ tractable になっているかって話ですね． 不確実性のある実空間で行動意思決定するとなったら，教師なしのモデリングつかった 認識の話だけでなく やっぱ，強化学習は入れたくなるのが人情．ノンパラベイズ強化学習はやってる人はそんなにおおくないのかな．

8:41 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

Partially Observable Markov Decision Process ね POMDP ． 昔は確定的な ちょいヒューリスティックっぽい話がおおかった気がしたけど，こんだけベイズがしっかりしてきたら，綺麗な話になってきているのね．

8:40 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

POMDPとか，久しぶりに読んでいる．

8:36 PM - 18 Apr 12 via TweetDeck · Details

Tehさんの NIPS2011のチュートリアル

Modern Bayesian Nonparametrics.

http://www.gatsby.ucl.ac.uk/~ywteh/teaching/npbayes.html

で，Tree構造関係のノンパラベイズの方法で引用されていたので，

以前から読みたかったので読んでみた．

文章クラスタリングの手法であるLDAを階層化するという話．

http://books.nips.cc/papers/files/nips16/NIPS2003_AA03.pdf

最初，なんかよくわからなかったのですが，

僕が勝手にイメージしていた，階層のイメージと本論文の階層のイメージが 合わなかったで，

はじめ理解に苦労しました．

LDAはざくっといえば，文章はトピックの多項分布で，トピックは単語の多項分布ってことで

文章がbag-of-wordsとして出力されているという，さっぱりしたベイズの生成モデルのイイ例なのですが．

トピックの間に階層関係などはない．

hLDAはトピックにツリー構造を入れようとしている．

2003年だから，もう10年ほど前の話なんですね．

はい，不勉強ですみません・・・．

グラフィカルモデルはこんな感じ．

左のc_n がツリーのノードに対応している．

ちなみに，左からの矢印が繋がっていたり，つながってなかったりで，うん？ と思うし，

c1 –> ｃLの path とかがよくわかんなくて，Bleiさんのこのグラフィカルモデル，これで間違いないのか

僕には自信がないです．（僕に自身がなくてもnips acceoptされてんだから，これでいいんだろうけど・・・）

でもって，c に対応する，トピックのノードが

Lレベルのツリー構造もっているんですね．

もちろん，ツリー構造も推定されます．

どういうモデルかというと，

まず，トピックにはtree構造があります．

で，文章は複数のトピックを持つのですが，

その複数の持ち方というのがトピックツリーのルートノードから，リーフへのpathとして表現されます．

つまり，

上の 2 なら beta1,beta2,beta5 をトピックのパラメータとしてもつ．

これらのmixtureから文章（単語の集合）が生成される と考える模様．

階層というか，

mixture っぽいんですよね．mixture component の選び方に，ツリー構造的な制約を入れた

という理解が正解な気がします．

Experimentでのsynthetic data での実験例が，それを端的に表しているように思う．

共通項～個別項という分け方での分解という感じなんでしょうね．

感覚的には，どれにでも出てくる， document frequency の高いワードがroot ノードに行くようで，

tf-idfみたいな文脈とかで使えたりするのかなぁ．と思ったりもしました．

前後してPitman-Yor diffusion tree とか読んだけど，木の生成モデルとしても大分違いますね．

はい．

ちなみに，上記は僕の勝手な解釈なので，絶賛間違い指摘募集中．

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

.@gavangavan @super_reader ルートノードのトピックは全文書上で共有されるので SN比を良くする用途にも使えそうな気がします．> nested CRP = hLDA

2:22 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

nested CRPのグラフィカルモデルは なんか，これでホントにいいのかなぁ？http://bit.ly/IM7s9U ちょっとよくわからないや．

1:14 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

「階層」という言葉にもいろいろあるものよのう． Dirichlet/Pitman-yor diffusion tree とか Kingman’s coalescent とかも，同じような意味での買いそうなのだろうか？それとも違うのだろうか？不勉強だから勉強しないとだめね．

1:11 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

nested とかいっておられるが，寧ろ親子関係が 並列になっていて，そやつらが，mixtureを構成する用な感じか．．． 確かに，木構造の制約をいれたら，root nodeは 全ドキュメントに共有されるトピックになるわけで， たしかに，hierarchical っぽくはなる．

1:09 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

nested CRP って木のノード毎にトピックがあって，その混合でドキュメントを表すってことか？？？？

1:06 PM - 18 Apr 12 via TweetDeck · Details

Tree 構造をつくるノンパラメトリックベイズということで，ちょっと読んでみた．

Pitman-Yor Diffusion Trees

http://arxiv.org/abs/1106.2494

http://mlg.eng.cam.ac.uk/dave/knowles2011uai.pdf

個人的には結構おもしろかった．

ツリーを単純につくるというよりは，ユークリッド空間上のガウス過程を考えてあげて

それが，分岐していく という過程の生成モデルになっている．

branching の部分がPitman-Yor っぽくて，

dt時間の間に別れるポイントが決定する確率があって，

分かれるときには，既存のルートにいくか，あらたなルートにいくかが

Pitman-Yor  つまり CRPの式で決定する．

その結果，各パスがサンプル点に到達する．

それが，hidden な tree structure になっているというお話．

inferenceは各パスをblocked gibbs sampler することで，求められるんだね．

LSI –> LDA の流れなど

文章分類などでもベイズといえば，直感的なユークリッド空間上での構成から離れていく

イメージがあったが，ツリーを作るのに，ワザワザ高次元空間上の確率過程を考えるというのが

おもしろかった．

Dirichlet Diffusion Tree (DDT)の拡張になっているというお話もあったが，

良い感じに拡張になっているらしい．

こういうtreeの生成モデルでは branching するときに 二分することが多いらしいんですが，

ちゃんと，二分以上 可変数個の分木を生成できるわけで，

僕は，好きだなぁ． と思いました．

どっかで，使えたら使いましょうかと．．．

でもTree structure 使いたいのって，むしろユークリッド空間じゃない事がおおいんだよなぁ．(´・ω・｀)

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

nested CRP と PY diffusion tree じゃ対象が大分ちがうわけですね．

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Pitman-Yor Diffusion Tree だいたい分かった．

4:42 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

なるほど．分岐の時にexisting な branch からCRPっぽく選択するのか・・・・．そこで分岐数が可変（潜在的に∞）とできるわけですね． > PYDT

3:47 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

へー．このgenerative process なかなか おもしろいなぁ． なんか，いろいろなトコロでありそう．あるある，なかんじ． PYDT

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Pitman-Yor Di usion Treesよむ

2:13 PM - 18 Apr 12 via TweetDeck · Details

NIPS1999らしいです．

SLAM読んでいると POMDPとの関係が気になるのが，人情．

ちゃんとThrun 氏がこのあたりの提案をされていたのですね．

基本的にはParticle filter でPOMDPにおける状態の信念分布を構成しましょう

というお話．

もう，１０年以上前の話なので，ごめんなさいという感じなのですが，

このあと，どのように展開しているのかちょっと調べないとな，と思いました．

@InProceedings{Thrun99h,
  author         = {S. Thrun},
  title          = {Monte Carlo {POMDP}s},
  booktitle      = {Advances in Neural Information Processing Systems 12},
  pages          = {1064--1070},
  year           = {2000},
  editor         = {S.A.~Solla and T.K.~Leen and K.-R.~M{\"u}ller},
  publisher      = {MIT Press}
}

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

.@po____ こんなんありましたわ． > Monte Carlo POMDP - ftp://ftp.irisa.fr/local/as/campillo/micr/bib/thrun1999b.pdf

9:07 PM - 18 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

POMDPとSLAMの関係について．

8:49 PM - 18 Apr 12 via TweetDeck · Details

Sequence Memoizer は Wood や Tehらによって提案された，∞gramモデル．

∞グラムモデルっていうのは，まぁ，Nグラムモデルなんですが，要はコンテクスト長がノンパラメトリックということ．

持橋さんの論文曰く，当時最高性能の Kneser-Neyスムージングがその近似となっている言語モデル

Hierarchical Pitman-Yor Language Model ですが．

そのN-gram長はgivenだった．

これを，コンテクスト長可変にしようというのが，∞グラムモデルといえるだろう．

“可変”という視点から，比較的自然につくられているのが，持橋さんの VPYLM もしくは IMMなわけですが，

Pitman-Yor 過程に基づく可変長n-gram言語モデル

http://chasen.org/~daiti-m/paper/nl178vpylm.pdf

これは，Beta分布からdrawした通過確率をつかって

Suffix tree を伸ばしていくという，まさに，可変長な視点からの∞グラムモデル．

これは，我々も，メロディ生成に利用させてもらったりしている．

Sequence Memoizer はコンセプト的には大分違って，

「全部覚えておいてやろう」というアプローチ

これは文章長をTとするとO(T^2) のメモリで，なんとかなるといえば，なんとかなるのだが，

実際にはでかすぎる．

彼らのcontributionは Pitman 1999, Ho 2006 の結果

を使えば，実は，結構カットできて，O(T)におさまるよ．という話．

ここで，HPYLMのCoagulationとFragmentationというプロセスが出てくる．

ここで，仮定しないといけないのは 集中度パラメータ c=0 ということ．

c=0 を満たせば，かんたんになる．

わかるのだが，実装が難しそうだなぁ，とは思う．

ただ，実装は

http://www.sequencememoizer.com/

がオープンにしているので，利用時は使わせていただこうかと．．．

ちなみに，持橋さんが，一昨年の日記にかかれていて，類似研究からの視点が伺えて面白い．

http://chasen.org/~daiti-m/diary/?200908#200908200

こんなところで

"A Stochastic Memoizer for Sequence Data"
http://www.gatsby.ucl.ac.uk/~ywteh/research/compling/WooArcGas2009a.pdf

"The Sequence Memoizer"
http://delivery.acm.org/10.1145/1900000/1897842/p91-wood.pdf?key1=1897842&key2=9039199921&coll=DL&dl=ACM&ip=133.19.33.3&CFID=12084269&CFTOKEN=64151334

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Coagulation と fragmentation 大体わかった． でも，Pitman 1999 と Ho 2006 の証明は追ってない． ここは深追いせずに，認めておこうか． 応用数学はどこまで基礎を深追いするかは，判断むずかしいね．

11:37 PM - 17 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Coagulation: GEMから生成されたパーティションがatomが別のGEMから生成されたパーティションとatomが共有されるよ，という理由で くっつくプロセスとか，そういうことか？

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

１年半前のもちはしさんのSequence Memoizer についてのコメント．一年半遅れで勉強中・・・．集中度パラメータ 0 は妥当っぽいのか・・．ふむふむ． > mots quotidiens. http://bit.ly/HOOQar

12:22 PM - 17 Apr 12 via chrome-share · Details