以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらコメントでご指摘いただけますと幸いです。
まとめ（ていない）
- 2章では正規表現、正規化、編集距離―「テキストデータをどこで区切るべきか」や「区切ったらどの単語とどの単語を同じと扱うべきか」を与える確立されたツールが紹介されている。
スピーチと言語の処理、ですか。28章もあるんですね…。1章のイントロダクションはまだ執筆されていませんね。2章は Regular Expressions, Text Normalization, Edit Distance ということですが…冒頭にユーザと ELIZA さんという方との会話が出てきますね。…この ELIZA さんあたりがきつくないですか？ 「助けがほしい」という人に「助けられたら何だというのか」といいますか？？
ええ…イライザさんは心理療法士ボットだったんですか…？ 心の治療に行ったのに逆にストレスを負いそうな…。
どうかな、「やせなければならない」という強迫観念をもっている人には「やせたらどうなりますか？」と訊いて治療していくんじゃないのかな。知らないけど。
裏を返せばそれだけデータの構造と意味を予め知っているからなんじゃないかな。もしテキストデータをそのまま数値（ASCIIコードか何か）の配列として扱って「入力されたテキストに対する心理療法士の応答」を学ぼうとするときっと途方もなく効率が悪いけど、実際の会話にかなり構造のパターンがあることがわかっていれば1960年代でも人間らしいボットが実現できるんだから。この頃の画像認識とかなんて人間っぽく何の画像か色々見分けたりはできなかったんじゃないの？ 知らないけど。
さっきから教科書への相槌が雑ですね…それに、テキストデータへの理解には分があるといってもそれ以上にタスクも曖昧で困難なものが求められがちじゃないんですか？ 質問に答えるとか翻訳するとか…。そういえば、アラビア語って活用形が多いんですか？ レンマ化のくだりに morphologically complex languages like Arabic とありますが。
いや、「10個しかないので大丈夫ですよ」みたいにいわれても…。導入部の最後に編集距離（Edit Distance）というのが出てきますが、スペルミス検出とかスピーチ認識において同一のものを指す単語の検出とかにつかうんですね。ある文字列を別の文字列にするのに何回の挿入、削除、置換を要したかというようなものなのでしょうか。…これって最短経路を求めるの大変なんじゃないですか？
ビタビアルゴリズム…放送大学教材の「自然言語処理」で名前は目にしたことがあります。39ページです。しかし、このときは編集距離という文脈ではなかったような…日本語の文章の形態素解析で複数の解釈がありえる場合がありますよね。教科書の例が以下です。以下のように列挙すると4パターンありますが（単純な例なので少ないですが実際にはとても多い）、途中の「元気」まで、「ね（根）‐たら（鱈）」を経由するのと「ねたら（寝たら）」を経由するのではコスト（ノードやエッジに対して適切に定義してください）が小さいのは後者なのでこの時点で「ね（根）‐たら（鱈）」の可能性は刈り取れるということです。
- 《文頭》‐ね（根）‐たら（鱈）‐元気‐に‐なった‐《文末》
- 《文頭》‐ねたら（寝たら）‐元気‐に‐なった‐《文末》 ※ 正解
- 《文頭》‐ね（根）‐たら（鱈）‐元気‐になった（担った）‐《文末》
- 《文頭》‐ねたら（寝たら）‐元気‐になった（担った）‐《文末》
うん、こちらの教科書で Viterbi Algorithm が出てくる8.4.5節でもむしろその放送大学の教科書の例に近い品詞タグ付けタスクの例で説明されている。編集距離に沿った説明については2.5.1節のつづきを読んだ方がよさそう…2.5.1節で最初に出てくる数式がその方法かな。この数式に具体的に X="inten" と Y="execu" をあてはめるとこうだね。
- 「inten を execu にする最小コスト」は、以下のうち最小のものである。
- 【１】「n を削除するコスト」＋「inte を execu にする最小コスト」
- 【２】「inten を exec にする最小コスト」＋「u を挿入するコスト」
- 【３】「inte を exec にする最小コスト」＋「n を u に置換するコスト」
え、うーん、わかるような気はしますが…場合分けってそれでMECEになっているんですか？
文字列を文字を参照しているポインタの配列と考えるとわかりやすいかも。つまり、「削除」「挿入」「置換」を、「削除」は配列からポインタを取り除くこと、「挿入」は新しいポインタを配列のどこかに挿入すること、「置換」はポインタの参照先の文字を書き換えることって考える。このとき、以下の場合分けはMECEだよね。
- n 文字の元文字列を m 文字の新文字列にするような操作は、以下の3パターンに場合分けできる。
- 元文字列の n 番目のポインタが取り除かれる。
- 元文字列の n 番目のポインタが新文字列において m-1 番目までにいる。
- 元文字列の n 番目のポインタが新文字列において m 番目にいる。
- 元文字列の n 番目のポインタが取り除かれるならば、そのポインタがいつ取り除かれるにせよ、そのポインタが取り除かれる操作を除いた残りの操作は「元文字列の n-1 文字目までを新文字列の m 文字目までにする」操作になっている。
- 新文字列において元文字列の n 番目のポインタが生き残っていて、かつ、それより後ろにポインタがあるならば、それらのポインタは全て挿入されたものである（「削除」「挿入」「置換」は元文字列のポインタの順序を変えない）。
その説明で伝わりますかね…？ とにかく、intention から execution へのレーベンシュタイン距離（編集距離であって、コストの定義は削除コストが1、挿入コストが1、異なる文字への置換コストが2）を求めてみましょう。面倒なので、intent から execut へのレーベンシュタイン距離を測ります。同じなので。先に図2.16から正解を確認しておくと、8ですね。delete が1回、substitute が3回、insert が1回ですから。では D("intent", "execut") を求めていきますが、レーベンシュタイン距離では異なる文字への置換は挿入＋削除としてもコストが同じなので、同じ文字への置換でない限り上の【３】を無視してかいています。
- D("inte", "e") = 3 ①②③
- D("inte", "ex") = min{ 1+D("int", "ex")=6, D("inte", "e")+1=4 } = 4 ④
- D("inte", "exe") = min{ 1+D("int", "exe")=7, D("inte", "ex")+1=5 } = 5 ⑤
- D("inte", "exec") = min{ 1+D("int", "exec")=8, D("inte", "exe")+1=6 } = 6 ⑥
- D("inte", "execu") = min{ 1+D("int", "execu")=9, D("inte", "exec")+1=7 } = 7⑦
- D("inte", "execut") = min{ 1+D("int", "execut")=8, D("inte", "execu")+1=8 } = 8
- D("inten", "ex") = min{ 1+D("inte", "ex")=5, D("inten", "e")+1=5 } = 5
- D("inten", "exe") = min{ 1+D("inte", "exe")=6, D("inten", "ex")+1=6 } = 6
- D("inten", "exec") = min{ 1+D("inte", "exec")=7, D("inten", "exe")+1=7 } = 7
- D("inten", "execu") = min{ 1+D("inte", "execu")=8, D("inten", "exec")+1=8 } = 8 ⑧
- D("inten", "execut") = min{ 1+D("inte", "execut")=9, D("inten", "execu")+1=9 } = 9
- D("intent", "ex") = min{ 1+D("inten", "ex")=6, D("intent", "e")+1=6 } = 6
- D("intent", "exe") = min{ 1+D("inten", "exe")=7, D("intent", "ex")+1=7 } = 7
- D("intent", "exec") = min{ 1+D("inten", "exec")=8, D("intent", "exe")+1=8 } = 8
- D("intent", "execu") = min{ 1+D("inten", "execu")=9, D("intent", "exec")+1=9 } = 9
- D("intent", "execut") = min{ 1+D("inten", "execut")=10, D("intent", "execu")+1=10, D("inten", "execu")=8 } = 8 ★ ここから出発
- intention
→（①②③ int を削除する）→ ention
→（④ x を挿入する）→ xention
→（⑤ e を挿入する）→ exention
→（⑥ c を挿入する）→ execntion
→（⑦ u を挿入する）→ execuntion
→（⑧ n を削除する）→ execution
