« September 2005 | Main | November 2005 »

2005.10.27

カーネルの学習

OSの話でもないし、方程式の核の話でもないです。K(a,b) = φ(a)・φ(b)のカーネルです。(なんか、式が物を書いている人にみえてくる)

個人的に今は固有表現抽出タスクをやっているのですが、この話も面白そうだなぁと目をつけています。NLPにどのようにくっつけるかすぐにはわからないけど。

カーネルの学習は訓練データ(例えば、要素対とその間の距離)が与えられた時、カーネル(要素間の距離のようなもの)である対称正定値行列を求めるというもの。普通学習といったら各featureの重みを決めたりするのだが、カーネルの学習はもっとモデルの自由度が高い。一応、距離は正定値行列なので、要素間の距離が要素のfeatureで表現したときの内積であることは保障されている。しかし、featureが明示的に表せないような場合も含まれる(feature空間が無限次元とか)。ただ、新しく与えられたデータに対して、訓練データ中との距離(例えば、k-NNとかを使って分類する場合)を求める方法はよくわからないけど。

これができたらすごいよなぁと思っていたら、でてきていた。

K. Tsuda, G. Raetsch, and M.K. Warmuth. Matrix exponentiated gradient updates for online learning and Bregman projection. Journal of Machine Learning Research, 2005. in press. [link]

カーネルの学習の話だけではないが、それも一部分として含まれている(正確にはエラー最小化と、制約付きでの正定値行列の学習の話)。エラー最小化の方では、やっていることが、Ada-Boostingの拡張として説明されている。量子情報理論で出てくる von Neumann Divergenceとかの話も出てくる。勉強になります。

L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D. D. Lee (2005). Spectral methods for dimensionality reduction. To appear in B. Schoelkopf, O. Chapelle, and A. Zien (eds.), Semisupervised Learning. MIT Press: Cambridge, MA. [link]

カーネルの学習と直接関係しないけど、関係する話。

もし要素が高次元で表現されている場合は、そこで距離の概念を使うのは難しい(ほとんどの要素との距離が似てくるし、邪魔な次元もたくさんある)。そこで、Spectral Methodを使って次元圧縮しようという話。簡単に言えば、高次元中で近い要素と枝をつくり、そのグラフでの隣接行列を固有値分解、で大きい固有値とそれに付随する部分空間をとってくる。他にもいろいろあるが、最初に近い要素と枝をはったグラフを作る部分がポイント。次元削減した後も、高次元中で近い要素だったものは近いままで、遠い要素は遠いままとなる。しかもPCAとかと違って非線形の部分空間をとってこれる。

ざっと読んだだけなので、ぜんぜん検討違いなことを言っているかもしれない。内容は直接読んでください。

| | Comments (2) | TrackBack (0)

2005.10.24

いまさら、韓国まとめ

IJCNLPで何をしてきたかを1日3行ぐらいでまとめてみます。

IMG_1472

IMG_1482


初日。朝4時30出発。チェジュ島は飛行機で2時間半と近い。日本語英語伝わらず、かなり苦労する。昼飯は普通の店で食べたが特にトッポギが辛すぎ。よじれ、チョコを食べて中和。発表練習。夜は平壌冷麺を食う。

IMG_1500

IMG_1503


二日目。本会議初日。自分の発表。いろいろな人からデータの入手方法を突っ込まれる。夕飯前にビール3杯くらい飲んで出来上がったところで、豚を食う。皮付きなどがうまい。店の裏から何かを強く叩く音が聞こえてくる。

IMG_1518

IMG_1590


三日目。他の人を聞く余裕が出来たのでいろいろ聞く。午後はポスターとデモ。ずっと聞いていたがさすがに疲れてくる。夕食はディナー。現地の歌や踊りを聞く。踊り手がギクシャクしていてドキドキ。最後はみんなで輪になって踊る。


四日目。本会議最終日。終わりのMSの話が"言い換え"は"翻訳"と同じ方法でできるかもとかで面白かった。その後11時頃まで統計的機械翻訳チュートリアル。かなり具体的に教えてもらい、面白かった。

IMG_1538

IMG_1581


五日目。休日。タクシーを借り、ハルラ山のふもとに行った後、島の南の滝二つ、寺一つ回る。帰りにまわったくだり坂に見えるのに実は上り坂である「お化け道路」が面白かった。夜は高級な焼肉を食べるが、安い肉がうまかった。写真の坂は上りです。

六日目。ワークショップ。ONTLEXに出るが疲労もあり、あまりよく覚えていない。夕方は、新チェジュ市内を歩き回る。特に地下街の長さがすごかった。向こう側が見えない。夜は魚(映像)を食べる。ぴちぴち。

七日目。旧チェジュ市でおみやげを買う。おばさんたちの勢いがすごい。街をうろうろ。メモリー売ってないかなぁと探す。早めに空港に着き、しばし待つ。プログラムのバグをとっていた。チェジュ→成田は1時間30分ぐらいでつく。帰宅。

| | Comments (0) | TrackBack (0)

2005.10.14

IJCNLP3日目

今日で本会議が終わりました。

初日にあった発表は無事終わりました。質問も想定していたものだったので聞き取れて答えられたと思います。

初韓国の感想としては英語、日本語がほとんど通じないのでかなり大変です。しかもハングル語だらけなのでそもそも読むことができずパターンマッチングの域で名前を照合しています。ごはんはおいしいです。マシッソヨ(おいしい)だけ覚えた。

聞いた中で面白かった話は・・
Discovering Relations from a Large Raw Corpus Using Tree Similarity-based Clustering
Min Zhang, Jian Su, Danmei Wang and Guodong Zhou

Relation Extractionを行うのに、関係の要素ペアをクラスタリングを行ってから、タグ付けしますよという話。そこまでは既にある話なのだが、そこのクラスタリングにParsing結果のTreeのsimilarityをtree kernelと同様に定義し、行うというもの。tree kernelと違うのはkernelの定義を満たしていないものの、うまく距離を測れるものを使っているところ(tree kernelのsumがmaxになっている)。クラスタリングだから満たしていなくてもかまわない。

An Empirical Study on Language Model Adaptation Using a Metric of Domain Similarity
Wei Yuan, Jianfeng Gao and Hisami Suzuki

Discriminativeな方法で言語モデルを学習しようというもののサーベイ。MLEではなく、設定したエラー(この場合はIMEの学習結果かな?)を最小化する方向で学習を行う。EMNLPで出ていた話も入っていた(Minimum Sample Risk Methods for Language Modeling, Jianfeng Gao, et al.)。学習が遅いんじゃないですかとGaoさんに直接聞いたら、MLEと同じくらいの速度ですよといっていた。試してみよう。

統計的機械翻訳のチュートリアルの予定が今日の本会議終了後にずれこみ、午後7時30分から午後11時までというハードスケジュールでやりました。最後はみんな変なテンション。実装の細かい内容まで触れていて(ソースコードを見せながらやった)これはやばいなぁと思った。Suffix Arraysが実装の中に使われていて一人で喜んでました。フレーズアライメントの場面で使うそうだ。言語モデルの精度がすごく重要だと話していて、charniakパーサで言語モデルを作る実装も進んでいるらしい。デコードをどう組み合わせるんでしょうかなと思ったのだが。。

| | Comments (0) | TrackBack (0)

2005.10.10

韓国

IJCNLP2005に出るため1週間ほど韓国に行ってきます。チェジュ島らしい。自分の発表は初日なので、最初から気合いを入れていきます。あとは・・

むこうでインターネットが使えるかはわからない。

旅の準備していたら、東京三菱が合併準備のためATMが使えないのでかなり困った。預金は分散して置くべきだなぁと思いました。

| | Comments (0) | TrackBack (0)

2005.10.07

CRF

Conditional Random Field (CRF)に関しての発表準備をしていて、ここ最近のCRF関連の話を集めて読んでみた。キーワードだけ集めてみてもDynamic CRF、Skip CRF、Piecewise CRF、Semi-Morkov CRF、モデルが複雑になった時の近似手法としてもvariational approach、MCMCなどなど研究はとても盛ん。自然言語処理、Computer Vision、Bio Informaticsとかでの応用も進んでいるみたい。

でも、そんなことはともかく私は最初のところ考え込んでいる。
CRFは従来の生成モデル(HMMとか)と比較し、オーバーラップしているFeatureを気にせず自由に入れられて学習出来る点が優れているといわれている。

この理由をp(X,Y)ではなくp(Y|X)でモデルを作っているから、明示的にp(X)を求めるプロセスが必要ないからできるのだと自分は思っていたのだが、いろいろ突っ込まれてみるとどうもはっきりしない。p(X,Y)を求めることもできるし。
そっちが理由ではなく、Log linearモデルだから実現できている話もあったが、それはMaximum Entropy法から導出されているものであり自由にFeatureを入れられる議論とあまり重なっていない気もする。(例えば、式だけ見ると、それぞれのFeatureが他の気にせずに独立に利いている形になっている) パラメータが重ね合わせを考慮して学習しているといえば、正確なのかなぁ。

そうなると、MEで学習した結果は、基底が独立っぽいやつを自動的に選ぶようになっているのか。いや、そこまではしていなくて、オーバーラップがあっても、学習器は基底がそれぞれ独立しているモデルを使った上で最善を尽くして学習できるという感じでいいのかな。

MEの論文をもう一回読み直してみよう。今ならきちんとわかるかもしれない

| | Comments (43) | TrackBack (0)

« September 2005 | Main | November 2005 »