自然言語処理と最適化

さて言語処理学会の年次大会で気になった発表などについて書いてみます。 といっても、個別の発表にというよりは全体感です。 今年気になったのは、最適化について少し考えなおしたほうがいいのかなということでした。

言語を扱う上で、一般的に解釈の曖昧性が残ることがふつうですから、いかにハードな制約を設けても何かしらのスコア関数を最大化する形に落ち着くのが普通です。 一方で自然言語処理の出力は、複数の変数の組合せ（例えば品詞列）を求めることが多いため、候補集合が入力データ長の指数サイズになります。 したがって全部チェックすることはできません。 古くからこの問題は、動的計画法で解くことが多かったわけですよね。 Viterbi法やCKY法などがこれにあたります。 動的計画法で解くということは、スコア関数が部分問題に分解できるという極めて強い制約がかかるわけですが、自然言語には極めて強いローカルな制約がありますから、この仮定はそこそこの良い近似ともみなせます。

動的計画法のこうした制約を取り払って大域的な制約・スコアを取り入れたいという流れが自然に出てきます。 こうした話は2000年代くらいから増えてきた印象があります。 例えば、ベイズな人たちは、これをMCMCでサンプリングしようと考えました。 より大域的な最適解を直接出すために、整数線形計画法を取り入れた人たちもいました。 整数線形計画法は、解きたい問題を制約式にエンコードするのが大変ですから、制約を述語論理で記述して確率的に制約を満たすようなマルコフロジックという考えも生まれました。 自由度を落とすかわりに、実用的に動く双対分解が2010年前後には流行っていました。 などなど。 手法的に見たときに、2000年代中頃から粛々と新しい大域的な最適化手法が試されてきたのだということを思い起こします。

前置きはこのくらいにして、今年の言語処理学会の年次大会を思い返すと、こうした最適化のアプローチの試行錯誤が気になりました。 NTTの西野さんが、文圧縮をする際に、与えられた構文木の全部分木集合をZDDで表現することによって、効率的にスコアの最大となる部分木を探索できる話をしていました（リンク）。 これは動的計画法の延長では有りますが、ZDDという外から輸入された技術を使ってより効率的に解けるという、きれいな話でした。

大域的な探索手法という点で見ると、2つ気になった発表がありました。 1つは時空間的な遷移の推定に、モンテカルロ木探索（MTS）を適用する話で、なんでNLPでMTS？？と一瞬戸惑いましたが、系列を探索するという点でこれは新しいアプローチだと思いました（リンク）。 もう1つは要約に遺伝的アルゴリズム（GA）を適用する話で、GAは局所的にうまく行っているものを確率的に組み合わせるような話になりますから、大雑把には局所的な構造の組み合わせで出来ている自然言語処理に実はよく適合するのではないかと思いました（リンク）。 いずれの発表でも、大域的に効いてくる「良い」スコア関数はなんぞやという点がまだ見えていない感じでしたが、構文解析を超えて、文をまたがった解析（照応解析や談話解析）がまた別のトレンドとしてありますから、今後注目を浴びそうな予感がします。

ところで、動的計画法は面白いですから（真理）、こないだのYANS合宿の時みたいに、昔からの知り合いに会うとすぐ動的計画法の話になってしまいました（完全に老害ですね・・・）。 動的計画法は麻薬のようなものだなぁ、としみじみ感じます。 一方でこうした麻薬のような魅力が「足枷」となって、大域的な制約をどのようにアルゴリズムに取り入れるかという視点を遅らせてきた原因でもあったようにおもいます。 ですので、動的計画法へのこだわりというものはどこかで捨て去らないといけないんじゃないのかというのが最近の気持ちです。 木やラティスという構造は気持ちのよいものです。 しかし、一方でそれにとらわれすぎて、アルゴリズム的に効率の良い方法が思いつきそうだからというバイアスがかかって、本当は木やラティスで表現することが適切ではないかもしれないという選択肢を無言で捨て去ってしまっているのではないかと考えるようになりました。 かねてより、自然言語処理の様々な出力を木として捉えるのは（例えば構文解析）本当に適切なのか？というようなことが気になっています。 自分の中で結論が出たわけでも、具体的な成果物があるわけでもないですが、この辺りはいずれ。