可変次数 N-gram デコードのアルゴリズム
前に書いた N-gram 漢字-かな変換 - アスペ日記 のアルゴリズムについて。
かなり縦に長いエントリになると思う。途中までは一般的な日本語自然言語処理にかかわること。
例として、「かれがくるまでまつ」というひらがなの文をデコードして、対応する漢字かな混じり文にすることを考える。
こういう時に使われるのが「ラティス構造」。こういうやつ↓
（この図は一回しか出てきません。ちなみにこのために Keynote 買ったようなもの）
それぞれのノードで、そこに入ってくるエッジの中で一番確率が高いものとその確率を覚えていくことで、動的計画法によって最適なパスを導くことができる。
これをプログラム上でどう実現するか。
まず、共通接頭辞検索というものを使う。
これは、あるキーを渡すと、そのキーに前から一致するようなキーを持つ候補を列挙してくれるというもの。
例えば、「くるまで」をキーとして使うと、「く」「くる」「くるま」をキーとして持つ候補をすべて返してくれる。
文頭から一文字ずつずらしながらこの共通接頭辞検索を行うことで、ラティスの中に出現するノードを列挙できる。
例えば、「かれがくるまでまつ」では、まず「かれがくるまでまつ」全体を共通接頭辞検索に渡し、「か」と「かれ」に対応する候補があることを教えてもらい、その次は「れがくるまでまつ」→「れ」、「がくるまでまつ」→「が」「がく」、「くるまでまつ」→「く」「くる」「くるま」…という具合。
結果が返ってくるようなひらがな列を図にすると、例えば次のようになる。
か れ が く る ま で ま つ ｜か｜ ｜か れ｜ ｜れ｜ ｜が｜ ｜が く｜ ｜く｜ ｜く る｜ ｜く る ま｜ ｜る｜ ｜ま｜ ｜ま で｜ ｜で｜ ｜で ま｜ ｜ま｜ ｜ま つ｜ ｜つ｜
それらに対する値である漢字かな混じり表記を加えると次のようになる。
か れ が く る ま で ま つ ｜か｜ー（か、蚊） ｜か れ｜ー（彼、枯れ） ｜れ｜ー（レ） ｜が｜ー（が、蛾） ｜が く｜ー（学、額） ｜く｜ー（区） ｜く る｜ー（来る、繰る） ｜く る ま｜ー（車） ｜る｜ー（流） ｜ま｜ー（間） ｜ま で｜ー（まで） ｜で｜ー（で、出） ｜で ま｜ー（デマ） ｜ま｜ー（間） ｜ま つ｜ー（待つ、松） ｜つ｜ー（津）
で、値のほうだけを縦に並べると次のようになる。
か れ が く る ま で ま つ ｜か｜ ｜蚊｜ ｜彼 ｜ ｜枯れ ｜ ｜レ｜ ｜が｜ ｜蛾｜ ｜学 ｜ ｜額 ｜ ｜区｜ ｜来る ｜ ｜繰る ｜ ｜車 ｜ ｜流｜ ｜間｜ ｜まで ｜ ｜で｜ ｜出｜ ｜デマ ｜ ｜間｜ ｜待つ ｜ ｜松 ｜ ｜津｜
これは、本質的に一番上で描いたラティスと同じもの。
エッジは描いていないが、ある位置で始まるノードを作るときに、その位置で終わるノードとの連接を見るだけでいい。
わかりやすくするため、ノードに番号を付けてみる（文頭・文末はここでは考えない）。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ ｜レ｜５ ｜が｜６ ｜蛾｜７ ｜学 ｜８ ｜額 ｜９ ｜区｜１０ ｜来る ｜１１ ｜繰る ｜１２ ｜車 ｜１３ ｜流｜１４ ｜間｜１５ ｜まで ｜１６ ｜で｜１７ ｜出｜１８ ｜デマ ｜１９ ｜間｜２０ ｜待つ ｜２１ ｜松 ｜２２ ｜津｜２３
例えば、17番の「で」について考える。
前からこのノードにつながるのは、「で(17)」の開始位置で終わるノード、つまり 13番の「車」と 15番の「間」。
「車(13)」までの確率に「車-で」の bigram 確率をかけたものと、「間(15)」までの確率に「間-で」の bigram 確率をかけたものとで、より大きいものを選び（ここでは「車(13)」とする）、その確率を「で(17)」の確率とし、また選んだノード（「最適な左ノード」と呼ぶことにする）がどれだったかを覚えておく。（今回の例では、実際に確率を設定しているわけではないので、最適な左ノードは適当に選んである）
前から順番にこの処理を行うと、それぞれのノードについて最適な左ノードを決めることができる。図にすると、例えば次のようになる（ノードの右の数字はそのノードの ID で、左の数字は最適な左ノードの数字であることに注意）。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ １｜レ｜５ ３｜が｜６ ３｜蛾｜７ ３｜学 ｜８ ３｜額 ｜９ ６｜区｜１０ ６｜来る ｜１１ ６｜繰る ｜１２ ６｜車 ｜１３ １０｜流｜１４ １１｜間｜１５ １１｜まで ｜１６ １３｜で｜１７ １３｜出｜１８ １３｜デマ ｜１９ １７｜間｜２０ １７｜待つ ｜２１ １７｜松 ｜２２ ２０｜津｜２３
最後に、文末ノード（ここでは省略してある）から最適な左ノードをたどることで、最適なパスを知ることができる。
例えば、文末の最適な左ノードが「待つ(21)」であれば、「彼(3)-が(6)-車(13)-で(17)-待つ(21)」となり、漢字かな混じり文は「彼が車で待つ」となる。
さて、これを単純に trigram に拡張することを考える。
bigram を見るだけなら、前のノードと今のノードを見るだけでよかったが、trigram ではそうはいかない。
単純な解決法として、それぞれのノードで前の履歴を持っておくというものがある。
そうすると次のような図になる。長いので注意。
か れ が く る ま で ま つ ｜か｜ ｜蚊｜ ｜彼 ｜ ｜枯れ ｜ ｜か｜レ｜ ｜蚊｜レ｜ ｜彼 ｜が｜ ｜枯れ ｜が｜ ｜レ｜が｜ ｜彼 ｜蛾｜ ｜枯れ ｜蛾｜ ｜レ｜蛾｜ ｜彼 ｜学 ｜ ｜枯れ ｜学 ｜ ｜レ｜学 ｜ ｜彼 ｜額 ｜ ｜枯れ ｜額 ｜ ｜レ｜額 ｜ ｜が｜区｜ ｜蛾｜区｜ ｜が｜来る ｜ ｜蛾｜来る ｜ ｜が｜繰る ｜ ｜蛾｜繰る ｜ ｜が｜車 ｜ ｜蛾｜車 ｜ ｜学 ｜流｜ ｜額 ｜流｜ ｜区｜流｜ ｜来る ｜間｜ ｜繰る ｜間｜ ｜流｜間｜ ｜来る ｜まで ｜ ｜繰る ｜まで ｜ ｜流｜まで ｜ ｜車 ｜で｜ ｜間｜で｜ ｜車 ｜出｜ ｜間｜出｜ ｜車 ｜デマ ｜ ｜間｜デマ ｜ ｜デマ ｜ ｜まで ｜間｜ ｜で｜間｜ ｜出｜間｜ ｜まで ｜待つ ｜ ｜で｜待つ ｜ ｜出｜待つ ｜ ｜まで ｜松 ｜ ｜で｜松 ｜ ｜出｜松 ｜ ｜デマ ｜津｜ ｜間｜津｜
違う履歴を持つものは違うノードとみなすことになり、例えば「彼=が」（図中では「｜彼｜が｜」）と「枯れ=が」は別ノードになる。
これにノードの番号を付けると次のようになる。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ ｜か｜レ｜５ ｜蚊｜レ｜６ ｜彼 ｜が｜７ ｜枯れ ｜が｜８ ｜レ｜が｜９ ｜彼 ｜蛾｜１０ ｜枯れ ｜蛾｜１１ ｜レ｜蛾｜１２ ｜彼 ｜学 ｜１３ ｜枯れ ｜学 ｜１４ ｜レ｜学 ｜１５ ｜彼 ｜額 ｜１６ ｜枯れ ｜額 ｜１７ ｜レ｜額 ｜１８ ｜が｜区｜１９ ｜蛾｜区｜２０ ｜が｜来る ｜２１ ｜蛾｜来る ｜２２ ｜が｜繰る ｜２２ ｜蛾｜繰る ｜２３ ｜が｜車 ｜２４ ｜蛾｜車 ｜２５ ｜学 ｜流｜２６ ｜額 ｜流｜２７ ｜区｜流｜２８ ｜来る ｜間｜２９ ｜繰る ｜間｜３０ ｜流｜間｜３１ ｜来る ｜まで ｜３２ ｜繰る ｜まで ｜３３ ｜流｜まで ｜３４ ｜車 ｜で｜３５ ｜間｜で｜３６ ｜車 ｜出｜３７ ｜間｜出｜３８ ｜車 ｜デマ ｜３９ ｜間｜デマ ｜４０ ｜まで ｜間｜４１ ｜で｜間｜４２ ｜出｜間｜４３ ｜まで ｜待つ ｜４４ ｜で｜待つ ｜４５ ｜出｜待つ ｜４６ ｜まで ｜松 ｜４７ ｜で｜松 ｜４８ ｜出｜松 ｜４９ ｜デマ ｜津｜５０ ｜間｜津｜５１
ここで、例えば 「車=で(35)」ノードへの連接を考える。
bigram の場合と違い、位置だけで連接を見ることはできない。
「車=」の部分が履歴、「で」の部分がノードの本体なので、開始位置は「かれがくるま｜でまつ」の「｜」の位置。この位置で終わるノードは「が=車(24)」、「蛾=車(25)」、「来る=間(29)」、「繰る=間(30)」、「流=間(31)」だが、「車=で」に接続できるのは、「車」を最後に持つ「が=車(24)」、「蛾=車(24)」だけ。「が=車(24)」から「車=で(35)」への連接時には「が-車-で」という trigram の確率が使え、他の連接も同様。
そのような連接可能な左ノードの中で、最適な左ノードを決める。
それをすると、例えば次のようになる。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ １｜か｜レ｜５ ２｜蚊｜レ｜６ ３｜彼 ｜が｜７ ４｜枯れ ｜が｜８ ５｜レ｜が｜９ ３｜彼 ｜蛾｜１０ ４｜枯れ ｜蛾｜１１ ５｜レ｜蛾｜１２ ３｜彼 ｜学 ｜１３ ４｜枯れ ｜学 ｜１４ ５｜レ｜学 ｜１５ ３｜彼 ｜額 ｜１６ ４｜枯れ ｜額 ｜１７ ５｜レ｜額 ｜１８ ７｜が｜区｜１９ １０｜蛾｜区｜２０ ７｜が｜来る ｜２１ １０｜蛾｜来る ｜２２ ７｜が｜繰る ｜２２ １０｜蛾｜繰る ｜２３ ７｜が｜車 ｜２４ １０｜蛾｜車 ｜２５ １３｜学 ｜流｜２６ １６｜額 ｜流｜２７ １９｜区｜流｜２８ ２１｜来る ｜間｜２９ ２２｜繰る ｜間｜３０ ２６｜流｜間｜３１ ２１｜来る ｜まで ｜３２ ２２｜繰る ｜まで ｜３３ １３｜流｜まで ｜３４ ２４｜車 ｜で｜３５ ２９｜間｜で｜３６ ２４｜車 ｜出｜３７ ２９｜間｜出｜３８ ２４｜車 ｜デマ ｜３９ ２９｜間｜デマ ｜４０ ３２｜まで ｜間｜４１ ３５｜で｜間｜４２ ３７｜出｜間｜４３ ３２｜まで ｜待つ ｜４４ ３５｜で｜待つ ｜４５ ３７｜出｜待つ ｜４６ ３２｜まで ｜松 ｜４７ ３５｜で｜松 ｜４８ ３７｜出｜松 ｜４９ ３９｜デマ ｜津｜５０ ４２｜間｜津｜５１
後は、bigram の時と同じように最後から順番に最適な左ノードを見ていけば、最適なパスを決めることができる。この例でいうと、文末から見た最適な左ノードが「まで=待つ(44)」だとすると、最適パスは「彼(3)-彼=が(7)-が=来る(21)-来る=まで(32)-まで=待つ(44)」となり、漢字かな混じり文は「彼が来るまで待つ」となる。
で、この trigram のデコード法は「使える」のか。
使えない。
なぜか。
ここでのノード数を見ると、そこまで多くなっていないように見える（23->51）。
しかし、実際はとてもこんなものでは済まない。
ここでの例では省略しているが、例えば「ま」だけでも、実際には魔・真・馬…等多くの候補がある。他のかな列にしても同様。N-gram の次数を 1 増やすたびに、その候補数倍ぐらいにノード数が増え、計算量もそれに合わせて増大する。
じゃあ、どうすればいいか。
ここで、trigram デコード時のノードをよく見てみる。
…この「彼=蛾」ってノード、本当に要るの？
これだけじゃない。いかにも要らなそうなノードは他にもいっぱいある。「蛾=繰る」とか、「デマ=津」とか。
でも、「彼=蛾」ってノードを取っておかないと、例えば「彼-蛾-来る」という trigram 確率を後で計算するときに困るじゃん！ と言われるかもしれない。
なるほど、もっともだ。
でも、その「彼-蛾-来る」って、本当にちゃんと trigram として計算するの？
どうせ存在しないから「彼-蛾」の backoff score 求めようとして、それも存在しないから結局「蛾-来る」の bigram でお茶濁すんじゃないの？
もし、「彼=蛾」という bigram が存在しなければ、このことは事前にわかる。
だったら、最初から「彼=蛾」とか「枯れ=蛾」といった bigram の存在しないノードは作らず、「蛾」というノードにまとめてしまえばいい。
存在しない bigram （ここでは適当に決めた）ではノードを作らないとすると、図は次のようになる。
か れ が く る ま で ま つ ｜か｜ ｜蚊｜ ｜彼 ｜ ｜枯れ ｜ ｜レ｜ ｜彼 ｜が｜ ｜レ｜が｜ ｜が｜ ｜蛾｜ ｜学 ｜ ｜額 ｜ ｜が｜区｜ ｜区｜ ｜が｜来る ｜ ｜蛾｜来る ｜ ｜繰る ｜ ｜が｜車 ｜ ｜車 ｜ ｜流｜ ｜来る ｜間｜ ｜間｜ ｜来る ｜まで ｜ ｜繰る ｜まで ｜ ｜まで ｜ ｜車 ｜で｜ ｜で｜ ｜車 ｜出｜ ｜出｜ ｜デマ ｜ ｜まで ｜間｜ ｜で｜間｜ ｜間｜ ｜まで ｜待つ ｜ ｜で｜待つ ｜ ｜待つ ｜ ｜まで ｜松 ｜ ｜で｜松 ｜ ｜松 ｜ ｜津｜
具体的な作り方は、
- ある位置から始まる検索結果（3文字目だとすると「が」、「蛾」、「学」、「額」等）のそれぞれについて、その位置で終わる既存ノードとくっつけて N-gram による確率を求める
- 存在した N-gram を超える分の履歴を削る（「彼-蛾」で N-gram 検索して、「蛾」の unigram しか見つからなかったら「彼」は捨てる）。また、最高次まで見つかった場合は最初のひとつだけ捨てる（trigram モデルの場合、「彼-が-来る」という trigram が見つかっても、すべて記憶するのではなく「彼」は捨てる。次に使うのは「が-来る-まで」といった trigram になり、「彼」は使わない）。
- 削った結果を新しいノードとする。もしそのノードがすでに存在していたら、既存ノードの確率と今計算した確率とを比較して、今のものが高ければ上書きする。
上の図にノード番号を振ると、次のようになる。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ ｜レ｜５ ｜彼 ｜が｜６ ｜レ｜が｜７ ｜が｜８ ｜蛾｜９ ｜学 ｜１０ ｜額 ｜１１ ｜が｜区｜１２ ｜区｜１３ ｜が｜来る ｜１４ ｜蛾｜来る ｜１５ ｜繰る ｜１６ ｜が｜車 ｜１７ ｜車 ｜１８ ｜流｜１９ ｜来る ｜間｜２０ ｜間｜２１ ｜来る ｜まで ｜２２ ｜繰る ｜まで ｜２３ ｜まで ｜２４ ｜車 ｜で｜２５ ｜で｜２６ ｜車 ｜出｜２７ ｜出｜２８ ｜デマ ｜２９ ｜まで ｜間｜３０ ｜で｜間｜３１ ｜間｜３２ ｜まで ｜待つ ｜３３ ｜で｜待つ ｜３４ ｜待つ ｜３５ ｜まで ｜松 ｜３６ ｜で｜松 ｜３７ ｜松 ｜３８ ｜津｜３９
さらに、選ばれた最適な左ノードは次のようになる。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ １｜レ｜５ ３｜彼 ｜が｜６ １｜レ｜が｜７ ４｜が｜８ ３｜蛾｜９ ３｜学 ｜１０ ３｜額 ｜１１ ６｜が｜区｜１２ ９｜区｜１３ ６｜が｜来る ｜１４ ９｜蛾｜来る ｜１５ ６｜繰る ｜１６ ６｜が｜車 ｜１７ ９｜車 ｜１８ １０｜流｜１９ １４｜来る ｜間｜２０ １６｜間｜２１ １４｜来る ｜まで ｜２２ １６｜繰る ｜まで ｜２３ １９｜まで ｜２４ １７｜車 ｜で｜２５ ２０｜で｜２６ １７｜車 ｜出｜２７ ２０｜出｜２８ １７｜デマ ｜２９ ２２｜まで ｜間｜３０ ２５｜で｜間｜３１ ２７｜間｜３２ ２２｜まで ｜待つ ｜３３ ２５｜で｜待つ ｜３４ ２７｜待つ ｜３５ ２２｜まで ｜松 ｜３６ ２５｜で｜松 ｜３７ ２７｜松 ｜３８ ２９｜津｜３９
これで完成…なのだが、まだ無駄がある。
例えば、「まで=待つ(33)」の履歴、「まで=」は、実際には持つ必要がない。最適な左ノードが「来る=まで(22)」ということを覚えているので。
それでは省略してしまおう。その代わり、そのノードの N-gram 次数だけ覚えておくことにする。そうすると、次のようになる。
か れ が く る ま で ま つ ｜か｜１ ｜蚊｜２ ｜彼 ｜３ ｜枯れ ｜４ １／１｜レ｜５ ３／２｜が｜６ ５／２｜が｜７ ４／１｜が｜８ ３／１｜蛾｜９ ３／１｜学 ｜１０ ３／１｜額 ｜１１ ６／２｜区｜１２ ９／１｜区｜１３ ６／２｜来る ｜１４ ９／２｜来る ｜１５ ６／１｜繰る ｜１６ ６／２｜車 ｜１７ ９／１｜車 ｜１８ １０／１｜流｜１９ １４／２｜間｜２０ １６／１｜間｜２１ １４／２｜まで ｜２２ １６／２｜まで ｜２３ １９／１｜まで ｜２４ １７／２｜で｜２５ ２０／１｜で｜２６ １７／２｜出｜２７ ２０／１｜出｜２８ １７／１｜デマ ｜２９ ２２／２｜間｜３０ ２５／２｜間｜３１ ２７／１｜間｜３２ ２２／２｜待つ ｜３３ ２５／２｜待つ ｜３４ ２７／１｜待つ ｜３５ ２２／２｜松 ｜３６ ２５／２｜松 ｜３７ ２７／１｜松 ｜３８ ２９／１｜津｜３９
「／」の後ろが次数。これがあることで、33番の「待つ」は bigram ノードで、実際は 22番と合わせて「まで=待つ」というノードだということがわかる。それに対して、35番の「待つ」は unigram ノードで、bigram が存在しない場合のノードだということがわかる。
（厳密には、この次数は必要がない。例えば実際に unigram ノードの左ノードを見に行けば、bigram が存在しないということは後からでもわかる）
このようにすることで、例えば 4-gram モデルでデコードしても、そこまで遅くならないようになっている。4-gram デコードをナイーブにやったら、時間がかかってしょうがないはず。
（追記：一番上の図で「車」のノード忘れたけど本筋に関わらないからまあいいか）
