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 ベースの方だけでも，面白みは

あるかなとおもいます．

 

 

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

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