たにちゅーの思惑|谷口忠大Home Page(たにちゅー・どっと・こむ)

2017 年 12 月
« 1 月    
 123
45678910
11121314151617
18192021222324
25262728293031

新着記事

最近のコメント

HOME > たにちゅーの思惑 >  研究 > Learning annotated hierarchies from relational data のメモ

Learning annotated hierarchies from relational data のメモ

2012-05-04 (fri)|カテゴリー:

筆頭著者の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 の1年後の 2007年にだされていますね.

 

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

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

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

 

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

image

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

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

 

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

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

 

generative model いってみましょう.

 

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

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

image

上のようなかんじ.

 

generative model としては,

 

1.木の生成 = binary tree の一様分布からランダムに 木が生成される.

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

3.重みを用いた通過確率でルートから木を伸ばしていく.(1.でサンプルした二分木が全部使われるわけではなく,確率的に枝刈りされるイメージか?)

4.すべてのカテゴリー(subtree)に対して,ベータ分布からfeature を生成するための確率 \theta を割り振る

5.\theta を使って,Bernoulli分布を使って feature のon /off のサイコロをふる.

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

あるかなとおもいます.

 

 

毎度,まちがってたらごめんなさい.

あくまで,僕の現状の理解です.

コメントの投稿




*


下記のタグが使用できます。
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <img localsrc="" alt=""> <pre lang="" line="" escaped="">

インフォメーション



tanichuの著作

copyright © Tadahiro Taniguchi All Right Reserved.