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/

Exponentiated Gradient による optimization
http://people.csail.mit.edu/mcollins/papers/NIPS2004_0621.pdf
http://people.csail.mit.edu/mcollins/papers/eg.ps

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

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

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

NIPS tutorial

NIPSのTutorial
この二つがすごいと思いました。

Spectral Methods for Dimensionality Reduction
http://www.cis.upenn.edu/~lsaul/nips05_tutorial/

PCAでデータ分布の構造を捜す話なんだけど、今はlinearどころか、いろんなmanifoldの構造が発見できるらしい。 これは自然言語に使えそう。

Nonparametric Bayesian Methods: Dirichlet Processes, Chinese Restaurant Processes and All That
http://www.cs.berkeley.edu/~jordan/nips-tutorial05.ps

これも上のと同じで自己発見の話。 Graphical Modelでクラスタリングするんだけれども、体系だった１つの分野になっているのがすごい。 似た様なクラスタリングするときに、parameterを共有できる。

忙しいのにネットショッピング

せっかく買った Shuttle ST20G5 が初期不良っぽいので返すことした。 AMD64 x2 dual core が使いたいので他のマザーボードを探すことに。

Asus A8N-VM マザーボード + Aspire X-Qpack のケースで小さくて完璧(Micro ATXサイズ) これなら片手で持ち運べるPCができる！と思ったのもつかのま、Linuxサポートは、VIAのchipsetに問題があって、12月か1月ぐらいに出来るようになるかも。。とか当てにならない話です。

待てないので諦めて他をあたっても、このサイズはどれも問題あるっぽい。 しょうがないのでこれなら動くだろう、と思われる一番安い GIGABYTE GA-K8U-939 に多分決定。 でもATXで大きい。

どうにも計算能力が欲しくて、二年か一年半毎に新しいPCを買うので、部屋には現在３つタワー型PCがあります。 とにかく小さいのがいい。

Micro ATXサイズのPCで、ノードは2つか3つで良いので、クラスターが作りたいです。

コンピューターにできること、できないこと

ボードゲームで、初手から最終手までルール上指せるすべての手を推計し、合計した数字:

チェス、１０の１２０乗。
将棋、１０の２２０乗。
囲碁、１０の３６０乗。

宇宙に存在する原子の数は１０の８０乗に満たないと言われています。 こういう数は、いかにコンピューターといえども不可能、つまり、初手から最終手までルール上指せるすべての手を読んで、必ず勝つコンピューターは『現在一般的な一つの命令を順番にこなす』コンピューターのモデルでは無理でしょう。 僕のパソコンでは無理です。

『量子物理学を用いた、実現していない』量子コンピューターなら理論上はありえるかもしれませんが、これはまだまだ先の話だとおもわれます。

１０の８０乗がどれぐらい簡単にでてくる数字か、少し考えてみます。 例えば、「1から100までの数から適当に一つ選んで？」って、学校のクラスの人、40人に頼むとします。 すると、全員が選ぶ数の組み合わせは、1の後に0を80個付けた数、１０の８０乗の分だけ、選びかたがあります。 たったこれだけでも、この数は宇宙に存在する原子の数と同じぐらい途方もない数です。

今年のパソコン、AMD Athlon 64でも2.8 GHzで、8400 MIPSだから、一秒に8400000000回、一つの命令、例えば足し算、が実行出来ます。 すると、一日に725760000000000まで順番に数を数えられます。 上の問題を、まともに全部の組み合わせをチェックするやりかたで解こうとすると、なんと 138の後に0が63個つく日数かかるのです。 そんなに待つのは到底不可能。 百年でも36500日しかないんですから。

総当たりして一日以内で終るのは、上の問題だと、7人分だけ。 コンピューターの能力の限界を超えるのなんて、すっごい簡単です。

さて、できないことをいかにやるか。

コンピュータ将棋世界一、「激指」開発者インタビューより抜粋

『「激指」では、羽生善治氏(現プロ四冠王)が実戦で指された棋譜を元に「この局面ではこういう手がよく指される」という可能性を数値化した上で、よく指されるタイプの手については手数を多く、あまり指されない手については確認程度に読む、という形で思考の効率化を図ってます。』

この、『効率化の方法を考えて実践する』のがコンピューターサイエンスです。 これだけです。 いかに余分な仕事をせずに、楽ができるか考えます。 このなかでも、やるべきことは、1、理論的に、そもそも解けそうな問題かどうか考え、できそうなら効率化の方法を考える、2、実践的に新しい問題に応用して経験を積む、というようにわけられます。

計算量が多すぎる場合、やれることはニつあります。一つは、上記のように『計算が少なくてすむ方法を考える』こと、もう一つは『並列化』です。

一つで無理でもプロセッサーの数を増やせばいいわけですが、この場合は問題が相互関係がない小さな問題に細かく分解できる性質のものであるかどうかで、できるかどうかが決まります。 現在のスーパーコンピューターはこれです。

ここでは、『第一位は米国のASCIプロジェクトにより開発されたASCI whiteであり、ピーク性能12.3TeraFlopsの計算性能を持って』います。(スーパーコンピュータの動向)

『10P（ペタ）FLOPSの水準になれば映画「2001年宇宙の旅」に登場するコンピュータ「HAL」のように人と同様の能力を持ったシステムを実現でき，100PFLOPSの水準になれば映画「マトリックス」に登場するコンピュータのように世界そのものを表現するシステムが実現できる可能性がある』といわれます。(CELLプロセッサーの記事より)

チェスだって、まともに解くのは不可能でも、効率化とハードの革新により、人間のチャンピオンと張り合うところまできました。 効率化と並列化の波は、何を可能にしてくれるでしょうか。

囲碁ができないコンピューター vs 映画「マトリックス」に登場するコンピューターの話でした。



参考、スーパーコンピュータの動向
http://www.nistep.go.jp/achiev/ftx/jpn/stfc/stt007j/feature1.html

参考、CELLプロセッサー
http://techon.nikkeibp.co.jp/article/NEWS/20051118/110883/

参考、「激指」開発者インタビュー
http://pcweb.mycom.co.jp/news/2002/05/17/26.html

参考、人工知能とゲーム
http://www.google.com/search?q=cache:NT-O5dM83poJ:www.yomiuri.co.jp/net/feature/004/20030818fe02.htm+yomiuri+%E5%9B%B2%E7%A2%81+%E4%BA%BA%E5%B7%A5%E7%9F%A5%E8%83%BD&hl=ja

http://www.google.com/search?q=cache:uWQSOrB36moJ:www.yomiuri.co.jp/net/feature/004/20030901fe01.htm+%E9%80%A3%E8%BC%89%E3%80%90%E4%BA%BA%E5%B7%A5%E7%9F%A5%E8%83%BD%E3%81%A8%E3%82%B2%E3%83%BC%E3%83%A0%E3%80%91%EF%BC%88%EF%BC%93%EF%BC%89%E5%B0%86%E6%A3%8B%EF%BC%88%E4%B8%8B%EF%BC%89&hl=ja

論文紹介 (自然言語)

http://www.seas.upenn.edu/~ryantm/papers/MS-CIS-05-11.pdf

Joint Conference on Human Language Technologies and Empirical Methods in Natural Language Processing, 2005 で、Best Student Paper Awardを取った論文の長いバージョンです。

思うことは。。 k-bestが O(n^6) ? そんなことはないとおもうんですが。

John saw a dog yesterday which was a Yorkshire Terrier.
みたいな、yesterdayのところがsawに行くはずなのに、なぜかdog とwhichの間にあるため、左右にくっつくだけの普通のparse treeではできない。 non-projective treeが必要だ。 その場合にはChu Liu Edmonds の maximum spanning tree for directed graphを使うと良い。 という話です。

これはよさそう。 というのも、まず、速い。 そして、実際アプリケーションを考えてみると、dependency treeの構造だけ分れば良いことが多い。 そして、やっぱりprojectiveだと、ちょっと不自然な構造？？ と思うことが多いからです。 通常のparse treeは語順の影響を受けすぎのような気がします。

■

http://chasen.org/~taku/publications/nl161-slide.ppt

を見て思ったこと。 CRFで形態素の分析をするときのpriorと、テキスト分類をするときに有効だと聞いていたpriorがちがうのに驚きました。 考えてみれば別に全然おかしくないですが。