IBIS2010 に行ってきたよ(2日目) #ibis10

第13回情報論的学習理論ワークショップ (IBIS 2010) の2日目にも、のこのこ参加。
またまた簡単なまとめ。敬称略。

発表

今日は「情報理論屋さん」と「理論統計屋さん」のお話。
わかりやすくておもしろいか、さっぱりわからなくておもしろいか、の両極端。
とりあえず合い言葉は "Slepian & Wolf"。

多端子情報源符号化の現状と課題 (葛岡)

通常1対1で定式化される符号化問題を、複数の送受信者間で考えるのが「多端子情報源符号化」。
その中でもっともシンプルな2対1の Slepian & Wolf 符号化問題(1973)を軸に、補助情報を使って通信する情報量を減らしたり、情報理論屋さんの「解けた」は何がわかった状態なのか、という話などなど。


この前、条件付き自己情報にハマっていろいろ考えたりしてたのが、理解に役立った。よかった。

圧縮センシングの理論とその展開 (和田山)

線形射影で圧縮されたベクトルを、情報源が「スパースなベクトル」という制約を使って、完全復元するための十分条件や復元アルゴリズムを考えるのが「圧縮センシング」。

詳しくはこちらとかこちらとか。

圧縮センシングの数理
http://w2.gakkai-web.net/gakkai/ieice/vol4no1pdf/vol4no1_39.pdf
Compressive Sensing Resources
http://dsp.rice.edu/cs

L1 正則化で復元できる(ことがある)、「完全」に復元できるための十分条件の評価に確率的手法を使っているので、言えているのが「十分高い確率で完全に」復元できる、であるというのがなんかおもしろい。
そしてここでも "Slepian & Wolf"。


まだキラーアプリがないらしい。紹介されていたのが「1ピクセルカメラ」。
なんかおもしろそうなので探してみた。たぶんこれ( http://dsp.rice.edu/cscamera )。まず映像を digital micromirror array で受ける。これは1つ1つがランダムに反射したりしなかったりする小さい鏡。反射する/しないのパターンがセンシング行列となる。反射した映像は1ピクセルのフォトダイオードで受けたものが圧縮系列。復号して合成すれば元の画像のできあがり。
そんな方法で実際に画像がどの程度復元できるのかはリンク先を。

補助情報を用いた情報源符号化 (松嶋)
  • 統計理論は少数の情報をなんとかしたい
  • 情報理論は漸近的な評価
  • 学習理論はおおらかw

というわけで(?)、ユニバーサル情報源符号化とかベイズ符号を補助情報付きで扱う話。
ここでも "Slepian & Wolf"。

情報理論的セキュリティと秘密増幅定理 (松本)

計算量的安全性(素因数分解など特定の問題の計算困難さによる安全保障)ではなく、情報理論的安全性(秘密 S と盗聴者が入手できる情報 Z がほぼ統計的に独立なら安全)の話。
つまり、Z と相関のある X から Z と統計的に独立な情報を作るにはどうするか、という問題。
そしてここでも "Slepian & Wolf"。


通信路の使用1回あたり秘密に送ることのできる情報量は条件付きエントロピーの差で表される。一見それ以上増やすことは出来なさそうだが、わざと「通信路を劣化させる」と、受信者への通信路容量の減少より盗聴者への通信路容量の減少の方が大きくなることがあるため、結果として秘密裏に送ることができる情報量が増える、という魔法のようなことが起こる。
あまりにも不思議な話なので、何か実際の例を作ってみたいところだけど、量子鍵配送とかなら作れても、古典的な範囲で無理矢理でも例を作ろうと思ったら、かなりファンタジー(苦笑)な状態を想定しないといけないっぽい……。

ロバスト推測の基礎とダイバージェンス型メソッドへの発展 (藤澤)

外れ値(outlier)に影響されにくいロバスト推定。ガウス分布とか最小二乗みたいな「綱渡り」ではなく「セーフティーネット+吊り橋+手すり付き」のロバスト推定でしょ、という話。
M推定とかβ相互エントロピーとかγ相互エントロピーとか。うーん、ここらへんは自分でも手を動かさないと理解が追いつかない……。

マルコフ基底と分割表解析への応用について (原)

これも全く知識のない分野。正確検定とか2元表とかMarkov基底とかトーリックイデアルとか。
中身はたぶんせいぜい 10% くらいしか理解できなかったと思うが、元・代数幾何屋さんなのでイデアルとか出てくると、なごむ。
計算代数は非常に次元の小さいところまでしかカバーできていないので、実際の機械学習などへの適用ではまだまだ課題が多いらしい。

無限次元マルチンゲール中心極限定理の使用法 (西山)

これも全く(ry
標準ブラウン橋とか漸近的分布不変とかリプシッツ連続とか。
マルチンゲールって勉強した方が……いい? 何回か挑戦してみたんだけど、ベースが足りてないのかちんぷんかんぷん。うん、確率過程をやろう(←昨日も言った)。

ポスターセッション

昨日よりはだいぶ空いてた。ありがたい。
おかげで昨日より長い時間参加できたが、激論交わしたりしてたので、結局昨日と同じ6つ。

混合正規分布におけるベイズ法と変分ベイズ法の相違について(山田)

変分ベイズ混合ガウスの1テーマだけで、このブログに一体いくつの記事を書いたんだろう、というくらいガッツリやったので、「ベイズ*1と変分ベイズの差がどの程度であるか明らかに」と言われて気にならないわけがないw。
その差とは「変分近似によって生じる誤差」の事だと思って聞いていたのだが、若干問題設定は違っていたらしい。まあそれはおいといて、厳密解と変分解の自由エネルギーの差はピッタリ log 2 だった、というところで、あれれ、それってコンポーネントの入れ替えの自由度が出ているだけだから、実は変分近似による誤差はゼロってこと? という話に。
で、もう少し細かく設定を聞くと、真の混合要素数は2、混合成分の共分散は単位行列固定で推論の対象外、真の混合比は 0.5, 0.5 で対称。うーんそれって変分近似する以前に隠れ変数と平均が独立になっちゃってて、つまりそこからの誤差が生じない設定になっちゃってないかなあなど、ちょうど居合わせた suzuvie さんも交えて議論。
是非、変分近似による誤差の影響が確実にある設定で調べてみて欲しいなあ。って、渡辺先生の本読んで自分でやれって?(苦笑)

Regularization Strategies and Empirical Bayesian Learning for MKL (Tomioka)

Multiple kernel learning (MKL) の既存の正則化手法を一つの枠組みで扱うとか、ベイズ化とか。1700(だったかな?)もの大量のカーネルを詰め込んでも、Elasticnet MKL なら有効なカーネルの自動抽出が働いてかつ精度も高い。L1 MKL やベイズなら重みが非零のカーネルはなんとたった5つ!
カーネル法は、全てカーネルの設計次第(職人芸、あるいは何でうまくいってるか本人にも説明できない)というところがいまいち気に入らなくて、少々敬遠気味だったのだけど、MKL やこの研究のような枠組みが使えるならいいかも。
などなどをご本人ではなく,居合わせた鈴木さんにいろいろ伺った。他のポスターが全部片付け終わっているような状態まで付き合っていただいてすいません(汗)。

ラベルノイズに頑健なトピックモデル(岩田)

「あとで読む」などの内容に関係なく付けられたラベルをノイズとして自動的に分類することで、頑健で精度の高いトピックモデルを構築。
すぐにでも実装できそう(手元の LDA with Gibbs sampling 実装にちょこちょこ足せば……)なほどシンプルなモデルなのに隙がない、という印象。なんかすごいなーと思ったら NIPS 2009 に出された結果を少し発展させたものだとか。さもあらん。

マスターマインドにおける最適解法とヒューリスティックを用いた解法に対する考察(藤居)

タイトルからマスターマインドの解法を研究したものかと思ったら、マスターマインドのような解空間が大きい問題を解く人間の意識はどのようにモデル化できるか、という話だった。
少し前に聞いた、迷路を解く人間の意識を数理モデル化するのに、確信度を潜在変数として入れたらいい感じだった、という話を思いだしました、と話したら多分同じ研究室の先輩だと思う、と。どこでどなたから聞いたんだったかなあ。

オンラインランク統合問題(安武)

検索結果などのランキング情報を複数あつめて、オンラインで統合する話。
方式1は上から抑える式が甘いけど、実験結果ではそんなに悪くない。方式2は既存の手法よりかなりよい上界だけど、一カ所アルゴリズムが確立できていないところがある。アプリケーションがまだない、ということだったので、オンラインでレスポンスが短い&逐次更新ができ、保持すべき情報が小さい(ランク数に対して線形)なら Web 系エンジニアならいろいろ使い道があるかもとか話す。
ただ、欠損値(こちらの検索結果には出てるけど、こっちには出てないページとか)の扱いとかがまだ課題。
ちょうどお話を聞いているときに、順位情報を使ってのクラスタリングなどを研究をされてる shima__shima 先生の臨時講義がその場で始まったりしてラッキー。


明日も行きたかったけど、家庭の事情で断念。残念無念。

*1:厳密解。指数時間かければ解ける