自然言語処理と最適化

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