機械学習コミュのstructured output prediction

structured output predictionで、重要そうな論文リストをあげます。

Michael Collins の Voted Perceptron
http://people.csail.mit.edu/mcollins/papers/tagperc.ps
http://people.csail.mit.edu/mcollins/publications.html

Max Margin Perceptron と、structured problemへの応用
http://jmlr.csail.mit.edu/papers/volume7/crammer06a/crammer06a.pdf
http://www.seas.upenn.edu/~ryantm/papers/nonprojectiveHLT-EMNLP2005.pdf

SVM struct 系
http://ttic.uchicago.edu/~altun/pubs/TsoJoaHofAlt-JMLR.pdf
http://ttic.uchicago.edu/~altun/

Ben Taskar の Max Margin Markov Networkと、それに必要な optimization algorithm 系
http://www.cs.berkeley.edu/~taskar/

ここまでの問題は、効果的なdecoding algorithmがすでにある、という前提があることです。　linear chain graphical modelに使えるViterbiや、parse treeを見つけるのに使うCKYなどです。　

さらに、あたらしく、decoder は greedy searchにして、search 自体を学習しよう、という手があります。

http://www.isi.edu/~hdaume/searn/

theoretical upper bound があるのがすごい。僕の理解が間違っていなければ学習結果のgreedy searchに近似保証をつけています。　考えとしては、structured output predictionの問題を reinforcement learningに落としたようです。　これはすごいのではないかと思います。　どうなのでしょうか？　

コメント(15)

最初
全て
最新の40件

[1] mixiユーザー 05月08日 09:16

> search + structured output
structured input （たとえば、文） -> structured output（たとえば、parse tree）
の間を、局所操作（たとえば、記号を２つ纏めて非終端記号に持ち上げる）の列によってつなぐとすると、「現在までに組みあがっているparse treeをみて、次にどの操作を適用するか」
（ただし、最終的に組みあがる木のlossを小さくするように）を決定するMDPのような問題として捉えることができますね。

個人的にはこれまで、この捉え方だと根性モノになりそうだなあと思っていたのですが、この論文ではなんだかちゃんと理論的な裏づけが与えられるのですね…。
すばらしい。

---
ところで、論文のリンクをたどっていったところのブログで、著者が愚痴っているのが面白いですね。

[3] mixiユーザー 05月08日 22:53

ある程度の期間同じトピックを追ってきててそれなりに前提を共有していると、大体みんな同じタイミングで大体同じようなことを思いつくものなんですねえ…。

要はその中で正しいものを選んで捕まえられるかどうかなんでしょうなあ、と。

[4] mixiユーザー 05月09日 15:54

kazawaさんは同じ事を考えていたんですか。。　でもそれなら、来年には kazawa著の、これよりもっと良いバージョンがでるかもしれないんですね。　

しかし、この論文は強化学習に強い人がいてこそですよね。　もっと幅広く勉強しないといけないと思いました。　

＞この捉え方だと根性モノになりそう

僕もIWPTの O(n) parser の論文を見た時、一応考えることは考えたんですが、性能をあげるのが難しいと思いました。　今でも左から右に一回 greedy searchしただけでは判断できないケースがあって、もう一回、右から左に戻りながら直さないといけないような気も。。　単に search の順番の話であって、論文の理論的に重要な点とは関係ないですが。

CKYみたいな特殊なdecodingがいらなくなると、tree kernelなどの重要性が更に増す気がします。　

[5] mixiユーザー 05月09日 15:58

> tree kernelなどの重要性が更に増す気がします。
決定の各段が(cost-sensitive)classificationに落ちるのなら、convolution kernel化も、し放題ですね！

[7] mixiユーザー 05月09日 20:37

＞適用するルールの順番はエラー率の減少が大きい順

それです！　NLPだと左右両方から影響があるので、左から順番だと違和感が…。簡単なところから先に解くのが良い。searnならまさにTBLと言う感じです。

[10] mixiユーザー 05月13日 19:55

よく読んでみたんですが、この論文はおかしいです。　このアルゴリズムを見ると、h^(0)よりは h^(1)の方がパフォーマンスが低くて、間違いを犯さなければならないですよね。　そうでないと、新しいpathが見付からない。　すると、h の性能はどんどん落ちているはず。　なのに、証明では h の性能は低くないと言っている（らしい）。　h の性能が低くならないなら、新しいpathが見付からないはずで、この学習アルゴリズムは意味がないですよね？　何かが強烈に間違っているか抜けている？　

[11] mixiユーザー 05月14日 20:21

> 8: kazawa
> 10: Nobuyuki

上の質問の答え（？）がプログのコメントに乗りました。　前よりかなりクリアになった気がします。

http://hunch.net/?p=188#comments

Policyは、多分、h^0 と h' はdeterministic だとおもうんですが、h^1 以降は、beta で決まった確率を使って、いままでに見つけた h^0 か h' のうちのひとつから random に引いてきて、そこで最適な action を使って次の path を見つけるようです。　

Eq (5)も、いわゆる greedy search 全体の近似保証ではなくて、Optimal Policyから離れすぎた State にいきなり行って、変な新しいpolicy h' が出来ないようにする工夫のようです。　

[13] mixiユーザー 06月11日 16:40

この考え方は、なかなか綺麗にまとめるのが難しそうですね。

そういえば、Inference に、制約を付ける話で、
Dan Roth, Wen-Tau Yih の、
http://www.machinelearning.org/proceedings/icml2005/papers/093_Integer_RothYih.pdf
は面白いと思いました。

CRF の Viterbiを Integer Linear Program に取り替えたら、いろいろできるようになったみたいです。　他のInference 問題も、Integer Linear Programとか、Quadratic Programとかに落ちてくるんでしょうか？　

[14] mixiユーザー 06月11日 22:20

> 他のInference 問題も、Integer Linear Programとか、Quadratic Programとかに落ちてくるんでしょうか？
翻訳での単語のアラインメントなど、「全候補の足し合わせを動的計画法で求めることはできないけど、ベストの候補を線形計画法で求めることができる」タイプの問題というのはいくつかあるみたいですよ。
こういうタイプの問題と、HM-perceptron、HMSVMなどのタイプの学習アルゴリズムを組み合わせると、これまでより多くの問題が多項式時間で解けるようになります。

[15] mixiユーザー 06月14日 14:14

新しいところだと、翻訳をまるごとやったりするようです。　
http://www.cs.berkeley.edu/~taskar/pubs/acl06.pdf

>「線形計画法で求めることができる」タイプの問題というのはいくつかあるみたいですよ。

そこのところが勉強不足なのを感じています。　Graph Algrithm はだいたいこんな感じなのではないかと。。　自然言語だと、CKYとViterbi以外は思いつかないんですが、他にもいろいろありそうな気がします。　

> これまでより多くの問題が多項式時間で解けるようになります。

そうですね。　このやり方には注目しています。　

ログインすると、みんなのコメントがもっと見れるよ