![3/ 4 誤字を辞書と比較
? N -g r am で 修 正 候 補 の 絞 り 込 み
N - gr a mっ て ?
文字をN個ずつ切り出すという意味
自然言語処理にいろいろと使われてる。
と ろ と き = [と ろ ][ろ と ][と き ]
Nの個数で名前が変わる
1 文 字 ??? ユ ニ グ ラ ム ? [ と ] [ ろ ] [ と ] [ き ]
2 文 字 ??? バ イ グ ラ ム ? [ と ろ ] [ ろ と ] [ と き ]
3 文 字 ??? ト リ グ ラ ム ? [ と ろ と ] [ ろ と ろ ] [ と き ]
単 純 に N - gr a mと い え ば 基 本 的 に バ イ グ ラ ム （ 2文 字 ず つ ）
?例外にもれず今回はバイグラムを使用](https://image.slidesharecdn.com/pronama10slide-110904073813-phpapp01/85/pronama-16-320.jpg)
![3/ 4 誤字を辞書と比較
?編集距離が同じ場合の対処
go o lに 対 し て 編 集 距 離 が 1
go a l / go o / go o d / . . .
ス ペ ル ミ ス の 80 95%は 編 集 距 離 が 1ら し い [ 要 出 典 ]
?文章の出現頻度が高い語ほど正解に近いとする（DF）
go o dの 頻 度 が 高 い → go o dが 正 解 と 推 測
で も go a lが 正 解 で も お か し く な い じ ゃ ん ！](https://image.slidesharecdn.com/pronama10slide-110904073813-phpapp01/85/pronama-22-320.jpg)
![[DLHacks 実装] DeepPose: Human Pose Estimation via Deep Neural Networks](https://cdn.slidesharecdn.com/ss_thumbnails/20170821onodeepposepresentation-170928100207-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]data2vec: A General Framework for Self-supervised Learning in Speech,...](https://cdn.slidesharecdn.com/ss_thumbnails/220204nonakadl1-220204025334-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Viewers also liked (8)
Similar to スペル修正プログラムの作り方 #pronama (20)
スペル修正プログラムの作り方 #pronama
- 1. スペル修正プログラムの作り方 とろとき（@t o r o t o ki）
- 2. 自己绍介 ?名前は とろとき ? 言 語 は P ython/ P erl/ Ja v a （ @t o r o t ki） ? A nd roid と か 自 然 言 語 処 理 、 ?機械学習などを勉強中。 ?中学生
- 3. はじめに {自然言語処理?プロ生}初心者です 色々とおかしなところがあればご指摘ください スペルチェッカの実装はかなり簡単 - 今 回 作 成 し た コ ー ド は 約 180行 （ Pyt h o n ） - 内 、 50行 は デ ー タ ベ ー ス に 単 語 を 突 っ 込 む た め - 理論さえ分かればとっても簡単！
- 4. はじめに ?自然言語処理について ?コンピュータでテキストを 分析 させる試み ? Micr o so ft の 選 ぶ 、 10年 後 テ ク ノ ロ ジ ー 分 野 で ホ ッ ト な 職 業 ！ ? The Top Three hottest new majors for a career in technology D at a Mining/ Mac hine Lear ning/ AI / Nat ur al Language P r oc essing （ デ ー タ マ イ ニ ン グ ／ 機 械 学 習 ／ 人工 知 能 ／ 自 然 言 語 処 理 ） ← コ レ B usiness I nt elligenc e/ C ompet it ive I nt elligenc e （ビジネスインテリジェンス／競合調査） Analy t ic s/ S t at ist ic s （分析／統計） Mi cr osoft JobsBl og より引用 ht t p:/ / j obsbl og.com/ bl og/ t op- t hr e e - ne w- t e ch- m aj or s/
- 5. おおまかにやること ?単語の辞書を用意（数十万～数百万） ? 受 け 取 っ た 文 字 が 辞 書 に あ る か （ =誤 字 か ど う か ） ?無い場合、受け取った文字を辞書と比較 - ここが大変 ?もっとも適切な候補を出力
- 6. 1/ 4 単語の辞書を用意 辞書選び 何種類も無料で配布されてる 単 語 だ け が 必 要 な の で 、 基 本 的 に ど れ で も OK 主要なものはこの三つ IPA - dic N A IS T - dic U n iD ic 単 語 数 は N A IS T - dic < U n iD ic < IPA - dic ? 今 回 は IPA - dicを 使 用 （ Me Ca bに 付 属 し て い た せ い ）
- 7. 1/ 4 単語の辞書を用意 辞 書 の 中 身 （ IPA - dicの 場 合 ） きらびやか,1287,1287,8349,名詞,形容動詞語幹,*,*,*,*,きらびやか,キラビヤカ,キラビヤカ 史的,1287,1287,6608,名詞,形容動詞語幹,*,*,*,*,史的,シテキ,シテキ プラトニック,1287,1287,5077,名詞,形容動詞語幹,*,*,*,*,プラトニック,プラトニック,..(略) てらてら,1287,1287,8349,名詞,形容動詞語幹,*,*,*,*,てらてら,テラテラ,テラテラ 静謐,1287,1287,4845,名詞,形容動詞語幹,*,*,*,*,静謐,セイヒツ,セイヒツ 今回はここしか使わない
- 8. 2/ 4 受け取った文字が辞書にあるか ?さっきの単語辞書と受け取った文字を照合 ? 合 っ て い た ら （ =誤 字 じ ゃ な け れ ば ） そ の ま ま 出 力 ?合っていなければ、誤字扱いで次の段階へ
- 9. 3/ 4 誤字を辞書と比較 辞書に正解の文字があると仮定 正解を書こうとして誤字する確率の誤りモデルを計算 辞書 M icro s o ft G o o gle M y cro s o ft Ya h o o .....
- 10. 3/ 4 誤字を辞書と比較 誤りモデルを数値で出すために、編集距離を求める ?編集距離とは 入力文字列に最低何回の編集操作をすれば 正解が求まるかという数値。 1つ の 文 字 に 対 し て ?挿入 ?削除 ?置き換え ?転置??????を繰り返す
- 11. 3/ 4 誤字を辞書と比較 編集距離の例 誤字 単語 ?挿入: スペルミッス → スペルミス ?削除: スペミス?? → スペルミス ?置換: スプルミス? → スペルミス ?転置: スペミルス? → スペルミス
- 12. 3/ 4 誤字を辞書と比較 編集 距離 を 使え ば、簡 単 に誤 字を 探せ る！
- 13. 3/ 4 誤字を辞書と比較 はずもなく
- 14. 3/ 4 誤字を辞書と比較 ?問題点 漢字が多すぎて実用的じゃない（アルファベットだけなら大丈夫） 毎 回 20万 語 と 比 較 し な き ゃ い け な い 3文 字 の 比 較 量 は 1回 の 編 集 距 離 だ け で {(5, 000* 4)+3+(5, 000* 3)+3}* 200, 000 = 7, 001, 200, 000回
- 15. 3/ 4 誤字を辞書と比較 ?じゃあどうするの？ 前もって候補を絞る = N -g r am で 修 正 候 補 の 絞 り 込 み
- 16. 3/ 4 誤字を辞書と比較 ? N -g r am で 修 正 候 補 の 絞 り 込 み N - gr a mっ て ? 文字をN個ずつ切り出すという意味 自然言語処理にいろいろと使われてる。 と ろ と き = [と ろ ][ろ と ][と き ] Nの個数で名前が変わる 1 文 字 ??? ユ ニ グ ラ ム ? [ と ] [ ろ ] [ と ] [ き ] 2 文 字 ??? バ イ グ ラ ム ? [ と ろ ] [ ろ と ] [ と き ] 3 文 字 ??? ト リ グ ラ ム ? [ と ろ と ] [ ろ と ろ ] [ と き ] 単 純 に N - gr a mと い え ば 基 本 的 に バ イ グ ラ ム （ 2文 字 ず つ ） ?例外にもれず今回はバイグラムを使用
- 17. 3/ 4 誤字を辞書と比較 ? N -g r am で 修 正 候 補 の 絞 り 込 み どうやって絞り込むの？ 辞 書 か ら 全 単 語 の N - gr a mイ ン デ ッ ク ス を 作 る いう あ い う ち , あ っ と い う 間 , ね ら い う ち , .. ごり に ご り 酒 , お ご り , 名 ご り , ご り ご り , .. 次官 次官, 政治次官, 次官補, 事務次官
- 18. 3/ 4 誤字を辞書と比較 ? N -g r am で 修 正 候 補 の 絞 り 込 み どうやって絞り込むの？ 入力 データベaス → デー + ータ + タベ + ベa + aス N - gr a mイ ン デ ッ ク ス で 複 数 回 ヒ ッ ト す る も の デ ー : " デ ー タ テ レ ホ ン " , " デ ー タ セ ッ ト " , " デ ータ タ ブ レ ッ ト " , " デ ー タ ベ ー ス " ータ : "インバータ", "データベース","オータックス", "ポータブル", タベ : "ベタベタ", "データベース", "ヌタベット", "カンタベリー", ベa : ... aス : ... 参 考 : http: / / www.slideshare.net/naoya1977/spell-correction
- 19. 3/ 4 誤字を辞書と比較 ?編集距離にも工夫 N - gr a mを 使 っ て 候 補 を 減 ら す （ 4つ に 絞 っ た と 仮 定 ） こ と で 比較量を {(5, 000* 4)+3+(5, 000* 3)+3}* 200, 000 = 7, 001, 200, 000回 から {(5, 000* 4)+3+(5, 000* 3)+3}* 4 = 140, 024回 にまで減らすことができた。 ? た だ し こ れ は 編 集 距 離 が 1回 ま で の 話 （ smt h in g → so me t h in g） な ど が で き て い な い 編集距離を少しでも多く出すためには？
- 20. 3/ 4 誤字を辞書と比較 ?編集距離にも工夫 挿入 ? 削除? 置換 転置 {(5, 000* 4)+3+(5, 000* 3)+3}* 4 = 140, 024回 編集距離の計算で回数を多くしているのは 5, 000* 4（ 挿 入 ） と 5, 000* 3（ 置 き 換 え ） の 式 ?※ 5,000 は漢字及びひらがなとカタカナの数 2回 目 以 降 に 編 集 距 離 を 求 め る と き は 、 挿入 置き換え の作業を消せばよいのでは？
- 21. 3/ 4 誤字を辞書と比較 ?編集距離にも工夫 2回 目 以 降 は 挿 入 と 置 換 を 求 め な い こ と で ({(5, 000* 4)+3+(5, 000* 3)+3} * 4 * {(3+3)* 4} = 3, 360, 576回 と 編 集 距 離 2も ギ リ ギ リ 求 め ら れ る く ら い に で き る （ た だ し や っ て み た と こ ろ 4 6秒 の 時 間 が か か っ た ） 言語を変える、並列化する、などして高速化の必要あり？
- 22. 3/ 4 誤字を辞書と比較 ?編集距離が同じ場合の対処 go o lに 対 し て 編 集 距 離 が 1 go a l / go o / go o d / . . . ス ペ ル ミ ス の 80 95%は 編 集 距 離 が 1ら し い [ 要 出 典 ] ?文章の出現頻度が高い語ほど正解に近いとする（DF） go o dの 頻 度 が 高 い → go o dが 正 解 と 推 測 で も go a lが 正 解 で も お か し く な い じ ゃ ん ！
- 23. 3/ 4 誤字を辞書と比較 ?短い単語は求めにくい go o l は ス ペ ル ミ ス だ け ど 、 「 go o d」 が 正 解 と は い い に く い 実は結構難しい問題 ? そ も そ も 短 い 語 に 対 し て は Go o gle す ら で き て な い 「もしかして」が出てない図
- 24. 3/ 4 誤字を辞書と比較 ?短い単語は求めにくい ? 応 急 策 （ そ の 1） I mpro v ed E rro r M o del（ ち ょ っ と だ け 取 り 入 れ ） 単語の先頭は誤りにくいよね？ ? 先 頭 、 中 間 、 最 後 の 3値 で 計 算 ? た だ し 、 ま だ go o l→ go o d の 問 題 は 解 決 で き な い 。 むしろ悪化
- 25. 3/ 4 誤字を辞書と比較 ?応急策その2 置換操作の文字によって優先順位をつける - 「a」と「n」は間違えにくい - 「 p」 と 「 o 」 は 間 違 え や す い - こ れ だ と go o l→ go o d問 題 は 解 決 で き そ う だ け ど ???。 - 当然、漢字は不可
- 26. 3/ 4 誤字を辞書と比較 A sp e lling C orre ction p rog ram b ase d on a noisy channe l mod e l( M . Ke rnig han1 9 9 0 ) ?応急策その2
- 27. 3/ 4 誤字を辞書と比較 ?まとめ ?まず誤字かどうか判別 ? N - gr a mで 候 補 を 絞 る ?絞った候補と入力文字の編集距離を計算 - 候補が被ったら最も一般的な語を使う ?最も数値の高かった候補を出す
- 29. 豆 知識的 な 応用 事例 ? N -g r am N - gr a mに よ る 誤 字 候 補 の 絞 り - 類似文字の索引にも使える - コピペ論文を検出する論文まであった 剽窃レポート発見に利用する1文単位での検索クエリ作成手法 http: / / c i. nii. ac . jp/ naid/ 1 1 0 0 0 7 4 6 7 2 4 8
- 30. 豆 知識的 な 応用 事例 ? EM-b ased Er r or Mod el E M- ba se d E r r o r Mo de l ?検索エンジンからスペルミスを機械学習 ?あまり詳しくない ?引用すると ?（検索エンジンの）クエリログからクエリの訂正を行う ?誤りと正解のペアデータは必要ない ? ク エ リ ロ グ は 10 15%の ス ペ ル ミ ス を ?含むので、ここから学習 引 用 : ス ペ ル 訂 正 エ ン ジ ン に つ い て の サ ー ベ イ # T okyoN LP http : / / www. slid e share . ne t/ nokuno/ tokyonlp 0 5 -sp e ll-corre ction
- 31. ご清聴ありがとうございました。
- 32. 参考文献 ?「入門自然言語処理」 オ ラ イ リ ー ジ ャ パ ン 2010年 11月 発 行 , 592ペ ー ジ ?スペル修正プログラムはどう書くか h t t p: //bit . ly/c3B H f ?スペルミス修正プログラムを作ろう h t t p: //slide sh a . r e /qgh ImL ?スペル訂正エンジンのサーベイ h t t p: //slide sh a . r e /g7S ImR