Peter Norvig / 青木靖 訳
先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。
このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleのものみたいな工業品質のスペル修正プログラムについて詳細に書 くのは、啓蒙するよりは混乱させるだけだと思う。それで、出張から帰る飛行機の中で 、1ページくらいのおもちゃのスペル修正プログラムで、80から90%の精度で毎秒10語程度処理できるものが書けないだろうかと考えてみた。
そうして書いたのが、以下に挙げる21行のPython 2.5コードで、これは完全なスペル修正プログラムになっている。
import re, collections
def words(text): return re.findall('[a-z]+', text.lower())
def train(features):
model = collections.defaultdict(lambda: 1)
for f in features:
model[f] += 1
return model
NWORDS = train(words(file('big.txt').read()))
alphabet = 'abcdefghijklmnopqrstuvwxyz'
def edits1(word):
n = len(word)
return set([word[0:i]+word[i+1:] for i in range(n)] + # deletion
[word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
[word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
[word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet]) # insertion
def known_edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
def known(words): return set(w for w in words if w in NWORDS)
def correct(word):
candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
return max(candidates, key=lambda w: NWORDS[w])
このコードは関数correctを定義しており、1つの語を入力として、もっとも適当と思われるスペル修正を結果として返す。
>>> correct('speling')
'spelling'
>>> correct('korrecter')
'corrector'
どういう仕組みになっているのか? 最初に、少し理論について話そう。与えられた語に対し、その語に対する最も可能性の高いスペル修正候補を選びたいとする。絶対確実な答えというのはなく (たとえば lates は late と修正すべきだろうか、それとも latest と修正すべきだろうか?)、 そのため確率がからむことになる。私たちは元の語 w に対し、可能な修正候補の集合の中から確率最大である修正語 c を見つけたい。
argmaxc P(c|w)ベイズの定理により、これは次に等しい
argmaxc P(w|c) P(c) / P(w)P(w) はどの c に対しても同じなので、ここでは無視することができる。
argmaxc P(w|c) P(c)この式は3つの部分からなる。右から順に:
ここでの当然の疑問は、どうして P(c|w) のような単純な式を2つのモデルがかかわる複雑な式に置き換えたのかということだろう。それは P(c|w) にはすでに2つの要素が融合しており、2者を分離して明示的に扱った方が簡単 になるからだ。スペルミスを含む語 w="thew" と、2つの修正候補 c="the" と c="thaw" を考えてみよう。P(c|w) が大きいのはどちらの語だろうか? a を e に変えるだけなので、"thaw" はいい修正候補と思える。一方、"the"は非常によく使われる語であり、タイプするときに指が e から w に滑ってしまったのかもしれないので、"the" というのも大いにありそうだ。要は、P(c|w) を推定しようと思うときには、語 c の確率と、c が w に変わる確率の両方を考慮する必要があるということだ。だから2つの要因を形の上で分離しておいた方が明確にすることができる。
これでプログラムの仕組みを説明する準備ができた。最初に P(c) の部分だが、100万語ほどからなる大きなテキストファイル big.txt を読み込むことにする。このファイルはProject Gutenbergで公開されている何冊かの本と、WiktionaryとBritish National Corpusから取った最も良く使われる語のリストをつなぎ合わせたものだ。(飛行機の中で手元にあったのは、たまたまノートPCに入っていたシャーロックホームズの小説だけだった。あとで他のソースからのテキストも追加していって、効果が変わらなくなったところで止めた。これについては評価の節で触れる。)
このテキストファイルからそれぞれの語を抽出する(関数 words を使う。このときすべて小文字に置き換えている。"the"も"The"も同じ語として扱い、語はアルファベットの並びとして定義される。そのため、"don't" は"don" と"t"の2語と見なされる)。それから確率モデルのトレーニングを行う。これはそれぞれの語が何回現われるか数えるというのを格好つけて言っただけだ。 これには関数 train を使う。ここまでのコードは以下のようになる。
def words(text): return re.findall('[a-z]+', text.lower())
def train(features):
model = collections.defaultdict(lambda: 1)
for f in features:
model[f] += 1
return model
NWORDS = train(words(file('big.txt').read()))
これで NWORDS[w] には語 w が何回現われたかが記録される。1つ厄介なことがある。未知の語だ。正しい英単語ではあるが、我々のトレーニングデータに は入ってないような語をどう 扱うかということだ。これまで見たことがないというだけで確率0だというのは不作法というものだ。この問題については標準的に用いられているアプローチがいくつかあるが、ここでは一番簡単なのを使おう。未知の語は、1度現われたものとして扱うのだ。この処理方法はスムージングと呼ばれていて、それは確率分布の0だった部分を最小のカウントに引き上げてなら すことになるからだ。コードでは collections.defaultdict クラス がこれを行っている。このクラスはPythonの普通のdict (他の言語ではハッシュテーブルと呼ばれているもの) のように振る舞うが、キーに対してデフォルトの値を設定することができ、ここではそれを1にしている。
次に与えられた語 w に対して可能な修正語 c を列挙する問題を考えよう。2つの語の間の編集距離という概念 がよく用いられる。すなわち、一方から他方を得るのに必要な修正の回数 ということだ。ここで編集は、削除(deletion、文字を取り除く)、転位(transposition、隣り合う文字を入れ替える)、置換(alteration、1つの文字を別な文字に変える)、挿入(insertion、文字の追加)のいずれかだ。次の関数は w から1回の編集で得られる語 c の集合を返す。
def edits1(word):
n = len(word)
return set([word[0:i]+word[i+1:] for i in range(n)] + # deletion
[word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
[word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
[word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet]) # insertion
この集合は大きなものになりうる。長さ n の語に対し、削除が n、転位が n-1、置換が 26n、挿入が 26(n+1) 通りあって、トータルでは54n+25 になる(この中には結果として同じになるものもある)。たとえばlen(edits1('something'))——edits1('something')の結果の要素数——は494になる。
スペル修正に関する文献によれば、スペルミスの80ないし95%は意図されたものからの編集距離が1であるということだ。すぐに見るように、私は開発用に270語からなるスペルミスのコーパスを用意したが、編集距離1であるものは76%だけだった。私が見つけた例は典型的な場合よりも難しいのかもしれない。なんにせよ、編集距離1だけというのは不十分と思 われるので、編集距離2も考慮に入れることにする。これは簡単で、edits1 の結果に対して edits1 を適用するだけ でいい。
def edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1))
コードとしては簡単だが、計算量はかなり大きくなる。len(edits2('something')) は 114,324 だ。しかしこれでかなりのスペルミスがカバーできるようになる。270のテストケースのうち、編集距離が2より大きいのは3つだけだ。つまり edits2 はテストケースの98.9%をカバーすることになり、これは私には十分に思える。編集距離が2より大きいものは扱わないので、ちょっとした最適化をすることができる。修正候補として、既知の語だけを取っておくのだ。依然可能性はすべて検討するが、大きな集合を保持せずに済む。この関数 known_edits2 は以下のようになる。
def known_edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
そうすると、たとえば known_edits2('something') は、edits2 が生成する114,324語の集合のかわりに、たった3語の集合になる: {'smoothing', 'something', 'soothing'}。こうすることで計算時間が10%ほど早くなる。
残る部分はエラーモデル P(w|c) だ。ここが難しかった部分 で、インターネット接続のない飛行機の座席で行き詰ってしまった。スペルミスのモデルを構築するためのトレーニングデータがなかったのだ。いくつか直感的にわかることはあった。母音を間違う確率は子音を間違う確率よりも高いとか、語の最初の文字を間違う可能性は低いとか、そういったことだ。しかしそれを裏付ける数字がなかった。それで近道をすることにした。 ｢編集距離1の既知の語が起きる可能性は、編集距離2の既知の語が起きる可能性よりはるかに高く、編集距離0の既知の語が起きる可能性よりはるかに低い｣という単純なモデルを定義することにしたのだ。ここで｢既知の語｣で意味しているのは、言語モデルのトレーニングデータに現われる語——辞書にある語——ということだ。この戦略は以下のように実装できる。
def known(words): return set(w for w in words if w in NWORDS)
def correct(word):
candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
return max(candidates, key=lambda w: NWORDS[w])
関数 correct は修正候補の集合として、元の語への編集距離が最短の語の集合を選ぶ(その集合が既知の語を含むという条件で)。 修正候補の集合を特定すると、NWORDS モデルで定義される P(c) の値が最大となる要素を選択する。
このプログラムがどれほど効果があるか評価してみることにしよう。飛行機の中で私はいくつかの例を試してみて、うまく行くように見えた。飛行機が着陸したあと、Oxford Text ArchiveからRoger MittonのBirkbeck spelling error corpusをダウンロードした。このデータから修正のテストセットを2つ抽出した。最初のものは開発用で、プログラムを開発している間に使うためのものだ。2番目のは最終テストセットで、中身を見たり、データに合わせてプログラムを修正しない。この2つのテストセットを使うというプラクティスは 健全なやり方だと思う。1つの特定のテストセットに合わせてプログラムをチューニングして、実際よりもうまくやっていると思いこむ罠を避けられる。以下に2つのテストセットの一部と、それを実行するための関数を示す。テストの全体(およびプログラムの残りの部分)を見るには、ファイルspell.py を見て欲しい。
tests1 = { 'access': 'acess', 'accessing': 'accesing', 'accommodation':
'accomodation acommodation acomodation', 'account': 'acount', ...}
tests2 = {'forbidden': 'forbiden', 'decisions': 'deciscions descisions',
'supposedly': 'supposidly', 'embellishing': 'embelishing', ...}
def spelltest(tests, bias=None, verbose=False):
import time
n, bad, unknown, start = 0, 0, 0, time.clock()
if bias:
for target in tests: NWORDS[target] += bias
for target,wrongs in tests.items():
for wrong in wrongs.split():
n += 1
w = correct(wrong)
if w!=target:
bad += 1
unknown += (target not in NWORDS)
if verbose:
print '%r => %r (%d); expected %r (%d)' % (
wrong, w, NWORDS[w], target, NWORDS[target])
return dict(bad=bad, n=n, bias=bias, pct=int(100. - 100.*bad/n),
unknown=unknown, secs=int(time.clock()-start) )
print spelltest(tests1)
print spelltest(tests2) ## only do this after everything is debugged
これの出力は以下のようになる。
{'bad': 68, 'bias': None, 'unknown': 15, 'secs': 16, 'pct': 74, 'n': 270}
{'bad': 130, 'bias': None, 'unknown': 43, 'secs': 26, 'pct': 67, 'n': 400}
開発セットの270のケースに対しては74%正しく修正して16秒かかり(17語/秒)、最終テストセットでは67%正しく修正した(15語/秒)。
更新: このエッセイの最初のバージョンでは、バグのために、それぞれのテストセットについて実際より高いスコアを報告していた。バグは小さなものだったが、気付くべきだった。以前のバージョンを読んだ読者 をミスリードする結果となったことを謝罪する。spelltest の最初のバージョンでは関数の4行目のif bias: をつけていなかった (そしてデフォルト値は bias=None ではなく bias=0 だった)。私は bias = 0 のときに は、NWORDS[target] += bias は効果がないと思っていた。実際 NWORDS[target] の値は変わらない のだが、効果はあった。(target in NWORDS) が true になるのだ。そのため、spelltest は未知の語を既知の語とみなすことになる。これはつまらない誤りで、defaultdict はプログラムを簡潔にしてくれたが、通常のdict を使っていれば起きなかったことだ。
結論として、プログラムの簡潔さ、開発時間、実行時間の点では目標に達することができたが、正確さの点では目標に至らなかった。
correct('economtric') => 'economic' (121); expected 'econometric' (1)
correct('embaras') => 'embargo' (8); expected 'embarrass' (1)
correct('colate') => 'coat' (173); expected 'collate' (1)
correct('orentated') => 'orentated' (1); expected 'orientated' (1)
correct('unequivocaly') => 'unequivocal' (2); expected 'unequivocally' (1)
correct('generataed') => 'generate' (2); expected 'generated' (1)
correct('guidlines') => 'guideline' (2); expected 'guidelines' (1)
この出力では、correct を呼んだ結果 (括弧の中は結果のNWORDS数) と、テストセットが期待している語 (同様に括弧の中はNWORDS数)を示している。これでわかるのは、'econometric' という語を知らなければ、'economtric' を正しく修正することはできないということだ。トレーニング用のコーパスにテキストを追加 することでこの問題は軽減できるが、間違った答えになる語も増えるかもしれない。最後の4行は、辞書に別な語形として書かれているものであることに注意して欲しい。だから動詞に'-ed' をつけたり名詞に'-s'をつけても構わないというモデルがあるといいかもしれない。
言語モデルの持つ2番目の潜在的な誤りの源は確率の不適切さで、辞書に2つの語が現われるが、間違った方が頻繁に現われるという場合だ。実際にこれが誤りの原因となっている例は見つけられなかったので、もう1つの問題の方が重要だと思われる。
テストを誤魔化すことで、
言語モデルの改良によってどれくらい結果が改善しうるのかシミュレートすることができる。テストデータの語に対し、正しいスペルで書かれた語を1回、10回、あるいはそれ以上見たことがある振りをするのだ。
これで言語モデルにもっと多くのテキスト(しかも正しいテキストだけ)がある場合をシミュレートできる。関数 spelltest
の引数 bias を使うとこれができる。正しいスペルの語にバイアスをかけたときに開発テストセットと最終テストセットに対する結果がどうなるか示した表を以下に挙げる。
| bias | 開発セット | 最終テスト |
|---|---|---|
| 0 | 74% | 67% |
| 1 | 74% | 70% |
| 10 | 76% | 73% |
| 100 | 82% | 77% |
| 1000 | 89% | 80% |
どちらのテストセットでも大きな改善が見られ、80-90%近くになっている。これは十分に良い言語モデルがあれば、正確さの目標に到達できることを示している。一方でこれはおそらく楽観的な値で 、大きな言語モデルを作ると、間違った答えを導くような語も持ち込むことになるからだ。
未知の語に対するもう1つの対処法は、既知でない語への修正も認めるというものだ。たとえば入力を"electroencephalographicallz"としたとき、適切な修正
がおそらく最後の"z"を"y"に変えることであるのは、"electroencephalographically"
が辞書になかったとしてもわかる。これは語の要素に基づいた言語モデルがあれば実現しうる。音節やサフィックス("-ally"のような)を使うこともできるが、2、3、ないしは4字のシーケンスに基づいて処理する方がずっと簡単だろう。
correct('reciet') => 'recite' (5); expected 'receipt' (14)
correct('adres') => 'acres' (37); expected 'address' (77)
correct('rember') => 'member' (51); expected 'remember' (162)
correct('juse') => 'just' (768); expected 'juice' (6)
correct('accesing') => 'acceding' (2); expected 'assessing' (1)
たとえば、'd' を'c'に置換して 'adres' を 'acres' にする変更は、'd' を 'dd' に、's' を 'ss' にする2つの変更を合わせたよりも大きいと見る必要がある。
また、いくつかのケースでは同じ編集距離の間違った語が選択されている。
correct('thay') => 'that' (12513); expected 'they' (4939)
correct('cleark') => 'clear' (234); expected 'clerk' (26)
correct('wer') => 'her' (5285); expected 'were' (4290)
correct('bonas') => 'bones' (263); expected 'bonus' (3)
correct('plesent') => 'present' (330); expected 'pleasant' (97)
これについても同様のことが言える。'thay' における 'a' から 'e'への変化は、'y' から 't' への変化より小さいと見る必要がある。どれくらい小さいか? 'they'に対する 'that' の出現頻度の大きさを乗り越えるためには、少なくとも2.5倍にする必要がある。
編集コストについてもっといいモデル
が使えるのは明らかだ。我々の直感に従い、同じ文字を連続させるとか、母音を別な母音に変えるといったことには(任意の文字間の変更と比べ)低いコストを割り当てることもできるだろう。しかしデータを集めた方が良さそうだ。スペルミスのコーパスを作り、周りの文字に応じて、それぞれの挿入、削除、置換がどの程度起こりやすいか測定するのだ。
これをうまくやるには多くのデータが必要になる。左右2文字ずつを枠として1つの文字が別な文字に変わるケースを考えると266通りあり、これは3億文字以上になる。それぞれの場合についていくつかの例がほしいだろうから、少なくとも10億文字の修正データが必要になる。たぶん100億くらいに考えておいた方が安全だろう。
言語モデルと誤りモデルの間には関連があることに注意する必要がある。今のプログラムはごく単純な誤りモデル(編集距離1の語はすべて編集距離2の語より優先する)を使っており、これは言語モデルへの制約になる。言語モデルに珍しい語を追加するのはためらわれ、それはたまたまそういう珍しい語の編集距離が1である場合には、編集距離2の非常に一般的な語があったとしても、珍しい語の方が選ばれてしまうからだ。もっといい誤りモデルを使っていれば、珍しい語を辞書に追加することにもっと積極的になれる。以下は珍しい語が辞書に入っていることで結果が損なわれている例だ。
correct('wonted') => 'wonted' (2); expected 'wanted' (214)
correct('planed') => 'planed' (2); expected 'planned' (16)
correct('forth') => 'forth' (83); expected 'fourth' (79)
correct('et') => 'et' (20); expected 'set' (325)
開発セット: purple perpul curtains courtens minutes muinets 最終テストセット: successful sucssuful hierarchy heiarky profession preffeson weighted wagted inefficient ineffiect availability avaiblity thermawear thermawhere nature natior dissension desention unnecessarily unessasarily disappointing dissapoiting acquaintances aquantences thoughts thorts criticism citisum immediately imidatly necessary necasery necessary nessasary necessary nessisary unnecessary unessessay night nite minutes muiuets assessing accesing necessitates nessisitates
特定の操作については編集距離3も含めるようにモデルを拡張することも可能だ。たとえば、母音の隣への母音の挿入、母音の他の母音への置換、"c"
と"s"のような近い子音間の置換について編集距離3を含めるなら、これらのケースのほとんどを正しく扱えるようになる。
correct('where') => 'where' (123); expected 'were' (452)
correct('latter') => 'latter' (11); expected 'later' (116)
correct('advice') => 'advice' (64); expected 'advise' (20)
correct('where')が、ある場合には 'were' と修正し、別な場合には 'where' のままとすべきであるというのはわかりようがない。しかし問い合わせが correct('They where going') であるなら、"where" は "were" と修正した方が良さそうだとわかる。
明らかな誤りに対し、いい修正候補が複数ある場合にも、周りにある語のコンテキストが助けになる。以下の場合を考えてみよう。
correct('hown') => 'how' (1316); expected 'shown' (114)
correct('ther') => 'the' (81031); expected 'their' (3956)
correct('quies') => 'quiet' (119); expected 'queries' (1)
correct('natior') => 'nation' (170); expected 'nature' (171)
correct('thear') => 'their' (3956); expected 'there' (4973)
correct('carrers') => 'carriers' (7); expected 'careers' (2)
どうして 'thear' を 'their' でなく 'there' と修正すべきなのだろう? 単独の単語だけで言うのは難しいが、質問がcorrect('There's no there thear')であるなら答えは明らかだ。
複数の語を同時に見るモデルを構築するにはずっと多くのデータが必要になる。Googleはdatabase of word countsをリリースしており、これは1兆語のコーパスから集められた5語までのシーケンスの出現数となっている。
90%の正確さを達成するスペル修正プログラムは選択に当たって周りの語のコンテキストを使う必要があると思える。しかしこれはまたの機会に
することにしよう･･･
correct('aranging') => 'arranging' (20); expected 'arrangeing' (1)
correct('sumarys') => 'summary' (17); expected 'summarys' (1)
correct('aurgument') => 'argument' (33); expected 'auguments' (1)
トレーニングする方言を決めるとい手もある。以下の3つの誤りは、アメリカ英語とイギリス英語のスペルの混乱によるものだ (トレーニングデータにはどちらも含まれている)。
correct('humor') => 'humor' (17); expected 'humour' (5)
correct('oranisation') => 'organisation' (8); expected 'organization' (43)
correct('oranised') => 'organised' (11); expected 'organized' (70)
Jurafsky とMartinのSpeech and Language Processingはスペル修正についてよく 書かれている。
Manning とSchutzeは教科書Foundations of Statistical Natural Language Processingで統計的言語モデルについて とても詳しく扱っている。しかしスペリングは扱っていないようだ(すくなくとも索引には載っていない)。
編集距離1の語は、私がはじめ書いていたように 55n+25 ではなく、54n+25であることを指摘してくれた Jay Liang に感謝する。
未知の語の問題を指摘してくれたDmitriy Ryaboy 感謝する。これによってNWORDS[target] += biasのバグを見つけることができた。
| home rss |