系列ラベリングなどで最適なパスを探索する方法はビタビアルゴリズムで効率的に求められる。 上位N個のパスを探索する方法はビタビアルゴリズムと、A*アルゴリズムで効率的に求められる。 日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus) の説明が分かりやすい。理解するために実装してみた。

ラティスの構造は以下のとおり。パスの重みは上記コードを参照。

#0       n1 --- n3
        /   \ /   \
       bos   x     eos
        \   / \   /
#1       n2 --- n4

ビタビアルゴリズムを適用後、バックトラックで最適なパスを選んだ場合の解と、 ビタビアルゴリズムを適用後、A*アルゴリズムで後ろ向きに最適なパスを順に選んだ場合の1-best解が一致している。 2-best以降もラティスの情報から、あっていることを確認。

下記の###以降はこのエントリ用に付け足した文字列。

$go test
Backtrack ### ビタビアルゴリズムで求めたパス
1 ### n2を通って、
0 ### n3を通る
1-best: 1 ### n2を通って、
1-best: 0 ### n3を通る

2-best: 1 ### n2を通って、
2-best: 1 ### n4を通る

3-best: 0 ### n1を通って、
3-best: 0 ### n3を通る

4-best: 0 ### n1を通って、
4-best: 1 ### n4を通る

goで優先度付きキューを実装するには、heap - The Go Programming LanguageのExample (PriorityQueue) が参考になる。

少し話はそれるが、機械翻訳において、n-best解は似通ったものが選ばれてしまう問題があるので、多様性を考慮するモデルを提案している話があって、これも気になるのでメモ。

Kevin Gimpel, Dhruv Batra, Chris Dyer, and Gregory Shakhnarovich. “A Systematic Exploration of Diversity in Machine Translation”, EMNLP, 2013. pdf

参考


関連記事






最近の記事