StrategyパターンでNGramモデルの文生成器を作った時のおもいで（NGramモデルのあらまし）

前回のブログ更新から随分と日があいてしまいました。ワタクシのブログ更新の頻度は多分年一回とかそんなレベルなのではないでしょうか。何と生産力のないことでしょう（嘆き）。

さて、前回の記事では「JavaScript界のあらましをさらに勉強している」とか書きました。嘘ではなくてJavascriptは触っていて、Javascriptソースを処理して動作するJavascript スクリプトを書いてみたけど、ソースを改行でsliceするfunctionを書いたらmerge-minify後にさっぱり動かない（注1）ことになって悲しみを知ったりとか色々あったのです。

しかし、今日はJavascriptではなくてJavaで書いたプログラムについて記事を書きたいと思います。JavascriptとJavaは全然違う言語だということはIT業界では常識云々ですが、そのへんの話は置いておいて以下の内容で記事を書いてみたいと思います。

「StrategyパターンでNGramモデルの文生成器を作った時のおもいで」

注１: merge-minify。javascript ソースコードから可読性のためのスペースや改行を除去してソースコードをまとめて軽量化すること。ページの応答速度が改善させる。改行を手がかりに処理していたので改行をとっぱらったらまるで動かなくなる。とほほ。

背景

ワタクシは自然言語処理という分野に興味を持ってお勉強をしてみたのです。自然言語処理は人間が書いたテキストをコンピュータで便利に処理するための技術です。例えば、キーボードの入力を漢字に変換するかな漢字変換とか、テキストを検索する検索システム（GoogleとかApache Solrとか）、商品レビューでお客さんが商品を褒めているのダメだししているのかの判定をしたりとか、医学論文などから人工知能が学習して医療診断する（IBMのシステムが有名です）などが自然言語処理の応用システムと言われています。

そのような応用システムを自然言語処理の基礎技術、例えば、テキストの「文」から「単語の区切りや品詞の判定」をする形態素解析ですとか、主語や述語といった文法的な構造の解析（文の構文解析といいます）といった技術が支えているのです。

ワタクシもこの自然言語処理に興味があったのです。例えば、小説執筆支援用「芥川龍之介パワー判定器」を作ってみたいのです。そこで、自然言語処理の教科書としてあちこちででおすすめされていた以下の２冊の本で勉強してみることにしました。

「Speech and Language Recognition 2nd editionand」（Daniel Jurafskey and James H. Martin 先生著、以下SLR本）

「確率的言語モデル（北研二先生著）」

今日は、SLR本のSection4 N-Gramsの演習問題（4.1から4.8まで）を解いて3-gramを生成するプログラムを書いたでその時の備忘ログを残しておきます。より具体的には、3-Gramの言語モデルをStrategyパターンによって実装し、太宰治先生の「走れメロス」で学習したメロス文自動生成器を作りました。

以下、

1. NGramモデルとスムージング手法（Back off smoothing）のざっくりした説明
2. プログラム作成の作成手順（設計、実装、テスト、文書化、リリース）

の順に記事を書いていきたいと思います。

1. NGramモデルのざっくりした説明

1.1 NGramモデル概説

NGramモデルは、人間が文章を書いたり話したりするその過程を、「文字や単語はその直前のN個の文字（や単語）で依存して生成されている」という仮定に基づいて確率モデル化したものです。NGramモデルは検索システムの検索、入力補完、誤字の補正など広く自然言語処理システムに応用されているそうです。

以下の例文を考えてみましょう。声に出して読んでみます。

Nana eats an X. (確率的言語モデルの3.1 NGramモデル入門より)

なんとなく、Xはappleやorangeな気がしてきます。eatsに続く言葉は食べ物でしょうし、an の次の単語は母音スタートなのです。この「気がする」をどう計算機でモデル化したらよいか、NGramモデルでは、これを単語列の条件付き確率として表現します。単語列 "eats an"の次に単語Xが生じる確率はP(X|eats, an)の値として表現します（とりあえずXの2つ前の単語列までを考えます）。

その確率値は、コーパスから単語列の頻度をカウントしてきて、P(apple|eats an) = C(eats an apple)/C(eats an)のように推定できます（Cはその単語列の頻度を表します）。テキストの"eats an apple"は、"eats an ant"よりもたくさん出現しそうですから、P(table | eat an) よりも P(apple|eats an)のほうが高くなりそうです。

$P(w_1,w_2,w_3,...,w_n) = P(w_1|\verb|<| S \verb|>| )P(w_2|\verb|<| S \verb|>|, w_1)P(w_3|w_1, w_2)...P(w_n|w_{n-1}, w_{n-2})$

Nの数字は大きくなればなるほど、計算と確率値の保持が大変になります。Nが大きいと、学習用テキスト中に長い文があった場合、文中の単語列の並びのパターンを全ての記憶していなければなりません。そこで、NGramモデルでは、言葉の生成は単語をN-1個前までだけ見て決めればよいという近似を採用することで、文中の単語列の並び全ての保持を回避しています。

しかし、NGramモデルにはまだ弱点があります。N-1個前のみを見るという豪快な近似は、それよりも前方の文脈に影響をモデルに組み込むことはできません（これは別のモデルで解決が試みられているそうです。Long Short Term Memory を利用した Recurent Neural Networkなどです）を顧慮できない、または、ゼロ頻度問題なる問題があります。

ゼロ頻度問題とは、学習データにない単語列がテキストに１つでも単語があると、単語列の生成確率が０になってしまうというものです。例えば、「走れメロス」を学習データとしてNGramモデルの確率値を推定した時に、単語列の頻度のみを用いて確率値を計算すると、P("メロスは感激した。")のような、走れメロスの本文にない文の生成確率を計算しようとして、そのような文の並びは走れメロスの本文中にはないので（頻度をカウントできないので）、確率値は０になってしまうのです。

このゼロ頻度問題（加えて学習コーパス中の低頻度な単語列の扱い）に対して、未知語の確率値がゼロにならないための様々なスムージング手法が提案されてきました。その１つがSLR本の4.7「Backoff」で取り上げられている「Katz's の Back Off smoothing」です。

1.2 Katz's の Back Off smoothing

Backoff smoothing手法では以下のように確率値を補正します（以下は3gramの場合を示します）。

${ \begin{eqnarray} P(w_3|w_1,w_2) = \left\{ \begin{array}{ll} P^{*}(w_3|w_2, w_1) & (C(w_1,w_2,w_3) > 0 ) \\ \alpha(w_1,w_2) P(w_3|w_2) & (C(w_1,w_2) > 0) \\ P^{*}(w_3) & (Otherwise ) \ \end{array}\right. \end{eqnarray} }$

スターのついている確率値は以下による補正値です。

$P^{*}(w_3|w_1,w_2) = dC(w_1,w_2,w_3) C(w_1,w_2,w_3)/C(w_1,w_2)$
$dC(w_1,w_2,w_3) = C^{*}(w_1,w_2,w_3)/C(w_1,w_2,w_3)$

$C^{*}(w_1,w_2,w_3)$ は単語列頻度の補正値であるGood Turing 推定値を用います。 $w_1,w_2,w_3$ の出現数をr回とします。Good Turing 推定値は以下の数式で計算します。

$r^{*} = (r+1)N_{r+1}/N_r$

この $N_r$ はr回出現したn(この場合3)単語列の総数です。3単語の頻度が頻度0の時は、（おそらくより頻度の高いであろう）2単語列による確率値を用いて代替します。dCをかけた確率値の和は1になりません。そのディスカウントした確率値をゼロ頻度時の確率値として貯金しておくのがBack Off smoothing 法のミソになります。 $\alpha$ はディスカウント係数で貯金した確率値を分配する関数です。まず $\alpha$ を与えるために便宜的に $\beta$ という量を考えます。

$\beta(w_1, w_2) = 1 - \sum_{w_3:C(w_1,w_2,w_3) > 0} \frac { dC(w_1,w_2,w_3) C(w_1,w_2,w_3)} { C(w_1,w_2) }$

これは、 $w_1,w_2$ によって与えられる条件付き確率値の合計1から $w_1,w_2$ によるディスカウント係数分を引いたものです(ゼロ頻度用の貯金)。 $\alpha$ という関数で、 $w_1,w_2$ に対してこの貯金を $w_1,w_2,w_3$ がゼロ（または低頻度）の場合に割り振っています。

$\alpha(w_1,w_2) = \frac { \beta(w_1,w_2) } { \sum_{w3;C(w1,w2,w3)=0} P(w_3|w_1,w_2) }$

以上がBackoffスムージング法の概要です。スムージング手法には他にも以下のようなものが色々とあります。

・線形補間法
・ワンカウント法
・カーリーネイスムージング方法

NGramモデルのプログラムについても、これら多様なスムージング手法の追加を想定した作りにしたいものです。また、言葉を生成する方法はNGramモデルだけではなくRecurent Neural Networkなどの他の方法もあります。NGramモデルと他のモデルの切り替えができたほうがよさそうです。このNGramのスムージング法がたくさんあるという事実が以下で述べるプログラムの書き方に影響を与えるのです。(次回、「StrategyパターンでNGramモデルの文生成器を作った時のおもいで（プログラム作成の一般的方法論設計の段）」に続きます)

めいふの備忘ログ

やったことを忘れないように書きこのしておくのです。

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（NGramモデルのあらまし）

背景

1. NGramモデルのざっくりした説明

1.1 NGramモデル概説

1.2 Katz's の Back Off smoothing