本記事は、京都大学人工知能研究会KaiRAのAdvent Calender 19日目の記事です。
今回は自然言語処理の手法について、動的計画法(Dynamic Programming)という切り口から簡単に解説してみたいと思います。
自然言語処理の手法である 構文解析 には動的計画法が用いられていますが、なぜ動的計画法であることが必要なのか、その性質に焦点を当てて動的計画法を用いる意義の理解の一助となれば幸いです。
目次
1. 動的計画法
1.1 動的計画法の概要
動的計画法については下記のようにわかりやすくまとめられています。
「ある大きな問題を、同じ形をしたより小さな部分問題に帰着させ、部分問題の計算結果を記録して使い回しながら解いていく」
出典: 中学受験の算数問題で入門する動的計画法
1.2 注目したい動的計画法の性質
この、 小さな部分問題の解を記録し、再利用することで時間計算量を効率化できる という点が自然言語処理に応用できます。
2. 自然言語処理への応用
2.1 自然言語の構文解析
動的計画法の応用に行く前に、自然言語処理における構文解析に触れておきます。
構文解析とは、自然言語の文を入力とし、その内部構造である構文構造を計算する自然言語処理技術のことです。
我々人間は、下記の2文のように同じ単語の組み合わせによって作られた文でも、その並びによって異なる意味を表すと認識できます。
さらに、見た目は全く同じ文であってもどこで区切るかによって考えられる文意を複数想定し、文脈に合うよう1つに絞ることもできます。
構文解析の目的は、このように複数ある選択肢の中から 人間の解釈と同じ文構造を正解として 出力することです。
2.2 CKY法
入力された文が短いものであれば考えうる構文を難なく列挙できますが、長い文になれば計算量は爆発的に増えるため、いかに効率よく計算するかがポイントになります。
そこでCKY法というアルゴリズムが用いられます。
CKY法とは、動的計画法を用いてすべての構文パターンから最も確率の高いものを計算するアルゴリズムです。
動的計画法の性質については1.1や1.2で触れましたが、つながりをもつデータを効率的に処理するために動的計画法は効果的です。
まとめ
動的計画法を応用したCKY法により、部分的な構文の解析結果を逐一保存しながら構文解析を進めることができます。