(2010年07月07日 15:53), NIIBE Yutaka wrote:
> lattice.c では「いわゆるビタビアルゴリズムを使用して経路を選ぶ」とコメ
> ントにありますが、このコメントは削除すべきではないでしょうか。
>
> 現状の実装は Viterbi アルゴリズムとは関係ないと思います。似ていると勘違
> いしたか、あるいはこれから実装するつもりだったのか。
[...]
> 「Viterbi アルゴリズムを利用」する、というのであれば、文節 (Hidden
> State)、読み (Obserbation) と対応させて、文節の遷移確率に加えて、文節か
> らその読みが出てくる確率を使って、最尤の文節の並びを見つける、となると
> 思います。
Viterbi アルゴリズムは、動的計画法(Dynamic Programming)[1]で最尤の信号
源の状態遷移を見つける、ということだと思います。
Anthy の実装は「単に動的計画法で shortest path を見っけているだけじゃん、
(似てるといっても)Viterbi とは言えんだろう」と 7/7 の時点では考えていま
した。
それで、もう少しちゃんと読んだら、現状の実装はもっとひどい実装でした。
ここは及第点とは言えない、というレベルではなく、明らかに落第点しかあげ
られない、という感じです。プンプン。
現状の実装では「もっとも良いものを選択する」とならないことがあります。
ちょっと複雑な長い文章ならば、ぜんぜんダメでしょう。たぶん。
コメントにはラティス/トレリスと書いてありますが、実際はツリーで、全部の
場合を列挙しようと試みるものとなっています。例えば、下記のような[1] と
同じ例を考えます。
B E H
A C F I J
D G
build_graph で左から node を作っていきますが、一番最初だけはたしかにラ
ティス/トレリスっぽい、例えば、こんな感じになります。
[A-B]
[A] [A-C]
[A-D]
でも、次の段階で、
[A-B-E]
[A-B] [A-B-F]
[A-B-G]
[A-C-E]
[A] [A-C] [A-C-F]
[A-C-G]
[A-D-E]
[A-D] [A-D-F]
[A-D-G]
となって行きます。こう進めていくと node がたくさんになってしまうので、
NODE_MAX_SIZE を越えると remove_min_node で node が削られます。
うわぁ。削られるのは現状の段階のものだけなので、最後の方では足しては削り
足しては削りとなるでしょう。
うーん。弱ったなぁ。元になっている feature_set も疑問であるとともに、実
装も大きく間違ってる。どうしたものでしょう。
冷静に理性的に考えれば feature_set を使わないものにするとしても、遷移確
率で Viterbi アルゴリズムを使うにしても、いずれにしろ動的計画法による選
択の実装を書き直しましょう、ということでしょう。ここはグッと耐えて、ま
ずは lattice.c をマシなものに書き直し、かなぁ。
[1] http://mat.gsia.cmu.edu/classes/dynamic/node3.html
--
_______________________________________________
Anthy-dev mailing list
Anthy-dev@lists.sourceforge.jp
http://lists.sourceforge.jp/mailman/listinfo/anthy-dev
