« April 2006 | Main | June 2006 »

2006.05.31

非健康

月曜。昼夜が完全に逆転し朝2時起床。GP本を読みすすめる。式をきちんと追ってみるが数学力が足りずいまいちよくわからない。眠かったのかもしれない。
夜に仕事飲み会で焼肉を食べる。帰り道におじさんと遭遇しさらに食事に。

火曜。学校のミーティング出た後に、デモをしに会社に。友人の就職祝いをするため学校に戻り、さくら水産で魚を食べる。ギャバンの「若さって何だ?」で盛り上がるが途中で寝てしまう。

ICMLの論文が手に入るようになったので、帰りに面白そうな論文をいくつか読んでみる。

Clustering Graphs by Weighted Substructure Mining がいいなぁ。グラフマイニングを応用しただけで面白いが、それをEMの枠組みできっちり定式化されているのがいい。

| | Comments (0) | TrackBack (0)

2006.05.29

山口にて

英語サークルで一緒に副部長をやっていた友人の結婚式が行われるということで山口に行ってきました。
今まで日本の最西到達記録は姫路だったので大幅に更新。

こういう式には、初出席ということで服装やらマナーやら良く分かりませんで、私はどたばたしましたが、式自体はとてもよく準備されて、とても良い結婚式でした。
披露宴は菜香亭という日本の著名人が愛用していた由緒ある場所で開かれ、笑い有り涙有りの内容でした。私は偉い人達の目を気にしながら新婦のモノマネをしたりしなかったり。

その後二次会で、違う学科の人と研究はどうなんだとか世の中の競争原理はなんだとか、日本の初等教育はどうたらこうだとかを話したりしました。みんな現場の人なので刺激的な話の内容。

前日寝てないこともあり、朝までがんばりたかったが寝てしまった。そして帰京。

| | Comments (0) | TrackBack (0)

2006.05.27

えいや

カメラレディを出しました。頭が働かず、もう何がなんだかわからない。
ちょうど一年前の今日、このネタになったプログラムが動きはじめたみたいで、感慨深い・・。

朝になったが、もうそろそろ家を出ないといけない。日本の西に行かないといけない。
この1週間もあまり眠ることができませんでした。時間の使い方が下手なのでしょうか・・。

| | Comments (1) | TrackBack (0)

2006.05.21

ESPer2006

今日はESPer2006で発表&デモしてきました。スタッフの皆様準備ごくろうさまでした。

この一週間はあまり寝ない状態でぶっとおしでプログラミングしてたので、結構ふらふらだったのですがプレゼン&デモの反響があってよかったです。疲れがふっとびました。まだまだいきますよー

| | Comments (0) | TrackBack (0)

2006.05.18

馬車馬

毎日プログラムをもくもく書いてます。いろいろ面白いことができる予定。昼夜が分からなくなってきた。
電車の中で"Gaussian Process"を読んでます。面白い本ですが、でかいので半閉じで怪しく読んでます。

| | Comments (0) | TrackBack (0)

2006.05.10

Canonical Huffman Code

昔書いた記事やコードを書き直して、CodeZineに投稿しました。[link]

長さ制限付きの場合もreverse package merge法[link]を使って最適な符号を求められるようになっています。ずっと以前に長さ制限付きの最適符号を求める方法はないのと聞かれ、いずれ用意しますと答えたままでした。3年目にして提供できました。しかし、長さ制限付きの場合の構築アルゴリズムはがちがちに最適化していなくて、必要な作業領域をもっと減らせるのですが、それはまたいつか・・

| | Comments (66) | TrackBack (0)

Searn

Searn (Search and Learn)はStructured Predictionを行うためのアルゴリズムです。

#発表の仕方がいろいろあったみたいですが、今回はそのことには触れません。論文の投稿数が増えていてレビュアーの負担が増えているのは確かですよね。

Structured Predictionは構造を持った出力を学習する問題です。例えば、品詞付けや、固有表現抽出などのシーケンスラベリングの問題やパーシングの構文木を求めたり、統計的機械学習でよくされる翻訳前と翻訳後の単語のアライメントをするためのマッチングを求めたりなどは全てこのStructured Predictionの範疇に入ります。今までこうした問題は小さい問題に分割して、それぞれ小問題の最善な結果を集めたものが全体の答えの一番よいものという形で解いていたのですが、全体の出力に制約がかかっている場合や全体の特徴を使いたい場合は直接構造を持った出力を予測することが必要となります。

これを解く方法は例えばConditional Random Fieldsやmax-margin Markov networks、multi-class SVMの延長線上にある最適化問題を解く形で問題を解方法などが提案されています。

SearnはStructured Prediction問題を探索問題として扱い、各ステート上でのアクションを次々と選んでいくことによって問題を解きます。例えばシーケンスラベリングの場合は各ステートはそれぞれの位置(とそれまで付けたラベル)に対応して、各アクションはその位置にどのラベルをわりあてるかに対応しますし、木構造の問題は決められた順番に木構造を決めていく(例えばshift, reduceで)ことになります。このままだと、今までの小問題に分割していた方法と同じようですが、違うのがgreedyに各問題を解いていっても全体として最適な値となるように問題を調整/学習するという点です。例えばシーケンスラベリングである時点で、ラベルAを選んだ場合、その時点では全体の結果からそれがどれだけ良いアクションだったかはわかりませんが、それ以降いろいろ選んだ結果の期待値と、最適なラベルを選んだ場合の結果との差を求めて、それをそのアクションを選ぶ際のreward(報酬)とします。これは強化学習と同様のアイディアで、全体の損失関数が少なくなるように各ステップが良いアクションをとれるような報酬を決定していきます。これをブースティングのように収束するまで何回も繰り返します。

実際にはもうちょっと複雑なことになっていて、訓練時最初探索する範囲は、正解のシーケンスに対応するところですが、そこから、実際にテスト時に探索するようなところに少しずつ離れていく(正解のシーケンス情報を出力するoptimal policyが少しずつ薄まる)ことなります。

高速化のためにもいろいろやられているようで、例えば途中のラベルAを選んだ結果の全体の損失関数の期待値を真面目に求めるのは大変なので、モンテカルロサンプリングとして何回か最後まで探索問題をおこなって、その結果を期待値として使ったりするようです。他にも高速化のためにいろいろ工夫があるようですが、それは公開されるとしているソースコード読んでみないとわからない。

まだ、いろいろ分からないところがあります。例えば過学習してしまうよねぇとか、パーシングなど探索空間が広く、ステートが大きく間違えた方向にいってしまった場合でもこの手法有効に働くのかなどです。

それでも、Structured Predictionは複雑になりがちな中でこのような簡単な枠組みでできるというのはありがたい。

| | Comments (8) | TrackBack (0)

2006.05.08

GW

5/3 そうだお台場へ行こうということで、前日の夜にCCGで悩む青年を誘って未来科学館に行って来る。予想以上に面白かったのではしゃいでしまう。CGやらインターフェースやらいいなぁ。

5/4 寝る日と決めて一日中寝て過ごす。午後から親が家にやってきて食事。そしてまた寝る

5/5 そうだ京都へ行こうということで、京都へ向かうが、勢いで初日は姫路あたりに行く。姫路城やら、海やらを見てあははおほほと過ごす。すごい疲労で、ホテルについた直後にバタンQで寝る

5/6 京都へ移動して会社仲間と合流し、午前中ミーティング、午後観光する。時間がもったいないということで車によるワープを多用し、いろいろ寺まわる。夜に川床で食べようということになり、いろいろ探し、川沿いの人達を観察しながら食事。そのあと、いろいろ有名所をまわる

5/7 宇治に移動して、ラーメンたべて全自動スキャナシステムで興奮した後に、みんなでプログラミング。他の方々はICPCのプログラミング練習会をやっていたが、短時間のプログラミングは苦手な私はDFUDSを実装する。みんなプログラミング速い。その後京都に戻り食事、酒のみ、帰京。終電で家つきました。

思いつきで予定を決めていったにしては楽しめたGWでした

| | Comments (4) | TrackBack (0)

2006.05.02

A Latent Dirichlet Model

A Latent Dirichlet Model for Unsupervised Entity Resolution, Indrajit Bhattacharya and Lise Getoor, 6th SIAM Conference on Data Mining, Bethesda, MD, April 2006. [pdf]

Entity resolution問題に対して、従来のようにコンテキスト情報を用いたニ値分類等をせずに生成確率を直接latent dirichlet modelの枠組みで定義し、隠れグループの数も同時に推定できるモデル。decode時はgibbs samplingする。
実際解いた問題は、論文とそれを書いた著者集合のペアが大量に与えられた場合に、それぞれの著者が実際誰を指しているかを宛てる問題。隠れグループ(研究室や研究グループ? 仲間)がいくつかあって、そこから著者が生成されている感じの生成確率。

LDAは昔からbleiの論文とかを何回か読んでいるがあまり理解できていない(測度論・・)、とりあえずこれで試してみよう。

Latent Dirichlet Allocation(LDA)モデルはいろいろなところで使えそうだなぁと思って
これ、そのまま応用できる分野が多そうですね。個人的には、昔やりっぱなしの、単語(やチャンク)をクラスタリングするやつをこれを用いてやってみたいところです。

| | Comments (84) | TrackBack (0)

« April 2006 | Main | June 2006 »