自然言語処理に関する最高峰の国際会議 ACL が先日開催されました． 発表された論文をいくつか眺めてみたのでメモ．
ほんとうはもっといっぱい紹介したい論文があるのだけれど，時間の都合上，5本だけ．気がむいたら続編あるかも．
すべての論文は，ACL Anthologyで入手することができる．
“Nonconvex Global Optimization for Latent-Variable Models” Matthew R. Gormley and Jason Eisner, ACL 2013
分枝限定法（評価関数の上限を推定しながら，探索木を刈りこむ）を用いて，隠れ変数モデルの大域解を求めよう，という話． 実験にはDMV(Dependency Model with Valence)というわりと有名な Unsupervised Dependency Parsingのモデルを用いている． グラフを見る限り，劇的に性能が良くなっているわけではなさそう，というか，線がつぶれてよく分からないｗ
正直さっぱり分かっていないんだけど，分枝限定法についてのぼくの限られた知識から推測すると， 隠れ変数が離散値をとる場合しか使えないような気がする． (正確にmarginalを計算しているのではなく，MAP解だけを数え上げているようにみえる)
実は，EMのような局所解に縛られる問題を，メタヒューリスティクスを使ってなんとかしよう，というのは，学部時代の恩氏が時々 言っていた話なのだけれど，当時は（いまも）能力が追いつかなくてぜんぜん歯が立ちませんでした．
すぐにどうこうする話ではなさそうだけれど，むかしから微妙に興味はあった話ではあるので， （小さな局所解がいっぱいあるような）モデルを扱うときのためにいちおう記憶にとどめておきたい．
“Scaling Semi-supervised Naive Bayes with Feature Marginals” Michael R. Lucas and Doug Downey, ACL 2013
Semi-supervised Naive Bayesというと，EMと組み合わせたNigamの有名な論文以来，きれいな構造とシンプルなアルゴリズムのため， よく使われるのだけれど，データ全体を何度もなめないといけないため，計算量が問題だった．あと，EMを使う以上，モデルが変な方向へ飛んでいってしまう(局所解につかまる)ため，性能が安定しないという問題があって，ちょっと扱いづらい．
そこで，featureの各クラスにおける出現確率だけをunlabeledデータから求める，というアイディアに基づいて高速化をはかったのがこの論文． ラベルつきデータが少数しか利用できない場合，featureの出現回数の”信頼性”が無くなってしまうので，大量に用意できるunlabeledデータを用いてパラメータを補正する，という感じ．
このとき，データが正例か負例かのどちらかに属する，という仮定を用いて，学習データにおける正例負例の割合をうまく取り込むことで精度を上げている．
Semi-supervised NBだと，わりと最近ではSemi-supervised Frequency Estimate(Su+ ICML’11)という，ワンパスで解いちゃう劇的に速い方法が提案されていて， アイディアもとても似ている．精度では今回提案された手法が優れているよう．計算時間の比較はなかったけど，同じくらい？
Naive Bayesは超有名なので，バリエーションも超大量にあるのだけれど，NBの良いところの一つはマルチクラス分類が自然に行えるところだと思っているので， データが2クラス限定になっちゃうこれはどうかなーと思ったりする部分もある． もちろん，one-versus-allのような仕組みでいくらでもマルチクラスに拡張できるのですが．
このへんは，2010年代っぽくない，とか言う人もいるけど，最近でも時々掘って成果を出している人がいるみたい．
“Unsupervised Transcription of Historical Documents” Taylor Berg-Kirkpatrick, Greg Durrett and Dan Klein, ACL 2013
このあいだ草津にいったときに，ちょっと趣きのある看板をみつけたので，
そういや白根山でみつけたこの看板、自然言語処理に対する挑戦っぽい pic.twitter.com/ps3qgUCGfO
— Koji Matsuda (@conditional) June 24, 2013
とか言ってたら，マジで論文が出てきた・・・．主に，むかしのタイプライターとか活版印刷で印刷された， 現在では読みにくくなってしまっている文書をいかにOCRするか，という題材．
モデルは， 言語モデル × typesettingモデル(文字のレイアウト：右にこれくらいズレてる，とか) × inkingモデル(インクのつけすぎで太くなっちゃってるとか) × ノイズモデル(経時変化による文字の欠けとか)を一つひとつ丁寧に組み上げて，Jointしている． 学習はEM．ちゃんと動くのか心配だけど，一つ一つの変数がちゃんと意味を持つよう工夫しているからか(むやみに変数が多くなりすぎないように工夫しているようにみえる)， ちゃんと学習できているらしい．
学習したモデルでは，人工的にインクをダバ〜っとこぼした原稿も解読できたりするようで，このへんもなかなか興味深い．モデル自体の解釈も面白そう．
“Scalable Decipherment for Machine Translation via Hash Sampling” Sujith Ravi, ACL 2013
暗号解読のノリで，言語モデル+サンプリングを使って対訳コーパスなしで翻訳をしちゃうお話の続編． 2011年の初出以来，年々進化を続けていて，今回は主に高速化がテーマになっている．
最初はword-to-wordの置換に基づく翻訳だけだったのが，これまでの研究で，さまざまなfeatureが使えるようになったのだけれど， ちょっと計算に時間がかかりすぎるようになってきたので，Hash Samplingという手法で高速化を行っている．
Hash Samplingというのは，あんまりよくわかっていないのだけれど，ベクトル同士の類似度をはかる (指数分布族からのサンプリングに用いる尤度項のテイラー近似は，パラメータベクトルと事例ベクトルの内積を用いて表せるらしい) ときに，feature vectorの空間で直接内積をとる代わりに，適当なハッシュ関数を通して，その間の差分(ハミング距離とか)を用いる方法のよう．
この手法によって，現在のパラメーターに近い語は高い確率でサンプルされ，そうでない語は低い確率，というサンプリングを高速に実現している． {0,1}ベクトルのハミング距離は最近のCPUだとかなり高速に計算できるようで，BLEU値をほとんど落とさずに，2桁くらいの高速化を実現したらしい．
Hash Samplingは，かなり汎用性が高い高速化手法っぽいので，そのうちじっくり読む機会があればいいなと思っている． テイラー展開による近似 + ハッシュによる近似，という2段階の近似を経ているあたりが少し気になったりはする．
“From Natural Language Specifications to Program Input Parsers” Tao Lei, Fan Long, Regina Barzilay, and Martin Rinard, ACL 2013
ICPCなどのプロコンの問題を，コンピュータに解かせよう！というモチベーションがありそうな研究． といっても，今回はまだ問題を解くところまでは行っていなくて，入力データの解析部分に対する挑戦． プロコンの問題では，たいてい，
入力は複数のデータセットからなる． 各データセットは2つの整数 a0 と L が1個のスペースで区切られた1行であり， a0 が最初の整数を， L が桁数を表す． ただし， 1 ≤ L ≤ 6 かつ 0 ≤ a0 < 10L である．
from AIZU ONLINE JUDGE
というような入力データのフォーマット指示がなされているので，これを構文解析して，パーサーを構成するC++プログラムを自動で生成しよう，というテーマ．
用いることの出来るデータは，上に挙げたようなフォーマット指示の問題文(英語)と，実際にプロコン主催者から与えられる入力データ． 直接プログラムそのものへの変換を考えるのではなく，フォーマット指示文から，データ構造を表す “specification tree”を生成し， それを通してparsingプログラム(より正確には，yaccやbisonに入力するような形式文法)の生成を行っている．
モデルは， テキスト中のそれぞれの要素が，他の要素とどのような関係を持っているかを当てるための dependency parsing と， それぞれのノードがプログラム内でどのような役割をもつか当てるための role labeling のふたつの要素で構成されている．
学習は，だいたい次のような流れ．
- 現在のモデルから specification tree をサンプリングする
- サンプリングされたtreeからプログラムを生成し，テスト用データをすべてパースできるか調べる(feedbackと呼ばれている)
- treeがどれくらい良いか，に応じて，Metropolis-Hasting ruleで次の状態を定める
このfeedbackと呼ばれる学習手法によって，F値が54から80程度に向上したらしい． 著者による発表スライドもあるので，興味をもって頂けましたら，ぜひそちらも．
つづく・・・かも？