Information Retrieval and Web Search まとめ(10): スペル訂正

前回は、Permuterm インデックスや k-gram インデックスを使ったワイルドカード検索について解説した。今回は、クエリのスペル訂正を扱う。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の10日目の記事です。

adventar.org

スペル訂正

• スペル訂正の応用
  • 文書作成 (MS Word, Google Docs, ...)
  • 携帯電話での入力
  • Web 検索
• スペルミスの頻度
  • アプリケーションによるが、 ~1-20%
  • 26%: Webクエリ [Wang et al. 2003]
  • 13%: バックスペースなしでのリタイプ（英語とドイツ語） [Whiteelaw et al.]
  • 7%: 携帯電話サイズのハンドヘルドで、単語がリタイプで修正されたとき [Soukoreff & MacKenzie 2003]
  • 2%: 携帯電話サイズのハンドヘルドで、単語が修正されなかったとき [Soukoreff & MacKenzie 2003]
  • 1-2%: リタイプ [Kane and Wobbrock 2007, Gruden et al. 1983]

スペル訂正のタスク

• スペル誤りの検知
• スペル誤りの訂正
  • オートコレクト (hte --> the)
  • スペル候補のサジェスト
  • サジェストリスト

スペル誤りのタイプ

• Non-word（単語ではない）エラー
  • graffe --> giraffe
  • Non-word エラーは歴史的には文脈に依存しないものだった
  • （古典的には）文脈に依存しない
• Real-word（実単語の）エラー
  • タイポエラー
    • three --> there
  • 認識エラー（異形同音異義語 (homophone)）
    • piece --> peace
    • too --> two
    • your --> you're
  • Real-word エラーはほとんど文脈に合わせて訂正する必要がある

Non-word スペル誤り

• Non-word スペル誤りの検知
  • 辞書に入っていない単語はエラーとする
  • （ある一定までは）辞書を大きくすると改善される
  • Web 検索ではスペルミスが非常に多いので、大きい辞書の必要性は低い
• Non-word スペル誤りの訂正
  • 候補生成
    • 元の入力と似ている実単語を候補とする
  • もっとも良い候補を選択
    • 重み付き編集距離 (weighted edit distance) が最短のもの
    • 雑音のある通信路 (noisy channel) での確率が最も高いもの

Real-word スペル誤り

• 各単語 w について、候補集合を生成する
  • 発音が似ているもの
  • スペルが似ているもの
  • w も候補に含める
• 最もよい候補を選択
  • 雑音のある通信路でスペル誤りを評価
  • 文脈依存
  • "Flying form Heathrow to LAX" --> "Flying from Heathrow to LAX"

候補生成

• 以下の基準で候補となる単語を列挙する
  • 似ているスペルの単語
    • 編集距離が小さいもの
  • 似ている発音の単語
    • 発音の距離が小さいもの
• 80% の誤りは編集距離 1 まで
• 編集距離 2 まででほとんどの誤りがカバーできる
• 以下のような方法で候補生成ができる
  • 辞書をなめて各単語について編集距離をチェック
  • 編集距離が k (k = 1 or 2) 以下の単語をすべて生成し、辞書との共通集合をとる
  • 文字 k-gram インデックスを使い、 Jaccard 係数などでもっともらしい k-gram の単語を辞書から探す
    • IIR 3.3.4 節参照
  • Levenshtein 有限状態トランスデューサで高速に候補単語を計算
  • 事前計算したマッピングを使う

Damerau-Levenshtein 編集距離

• Damerau-Levenshtein 編集距離 (Damerau-Levenshtein edit distance) は、2つの文字列の編集距離を測る尺度の1つ
• 文字の編集
  • 挿入
  • 削除
  • 置換
  • 隣接文字交換
    • これ以外は Levenshtein 編集距離と同じ
• 編集距離については IIR 3.3.3 節を参照

Noisy channel モデルによる文脈非依存のスペル訂正

• Noisy channel （雑音のある通信路）モデル
  • 観測された単語（誤りを含む）が、元の単語に何らかの雑音が付与されたと考える
  • 雑音を取り除くデコーダを構成し、それで逆変換することで、元の単語を推定することができる
• 1990 年代に提案された
  • IBM
    • Mays, Eric, Fred J. Damerau and Robert L. Mercer. 1991. Context based spelling correction. Information Processing and Management, 23(5), 517–522
  • AT&T Bell Labs
    • Kernighan, Mark D., Kenneth W. Church, and William A. Gale. 1990. A spelling correction program based on a noisy channel model. Proceedings of COLING 1990, 205-210

Noisy channel モデルの概念図

• ベイズの定理を使う
  • 真の単語の確率変数 w$w$
  • 観測された単語の確率変数 x$x$
  • 予測された単語 w^$\hat{w}$
• P(x∣w)$P(x\mid w)$ が Noisy channel モデルを表す
• P(w)$P\left(w\right)$ は単語の事前分布
  • 入力ログから学習できる
• Non-word スペル誤りに対しては文脈（単語の周辺の情報）は不要

w^=argmaxw∈VP(w∣x)=argmaxw∈VP(x∣w)P(w)P(x)∝argmaxw∈VP(x∣w)P(w)$\begin{array}{r}\\ \hat{w}& ={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{w\in V}P(w\mid x)\\ & ={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{w\in V}{\displaystyle \frac{P(x\mid w)P\left(w\right)}{P\left(x\right)}}\\ & \propto {\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{w\in V}P(x\mid w)P\left(w\right)\end{array}$

言語モデル

• P(w)=C(w)T$P\left(w\right)={\displaystyle \frac{C\left(w\right)}{T}}$ は単語の言語モデルを表す
  • C(w)$C\left(w\right)$ は w が出現した回数
  • T はコレクション全体のトークン数
  • コーパスから学習できる

Noisy channel モデルの確率分布

• P(x∣w)$P(x\mid w)$ が Noisy channel モデルの確率分布
• 編集の確率分布を表す
  • 挿入、削除、置換、隣接文字交換
• 各種の誤り確率を計算するために、以下のような混合行列を計算する
  • del[x,y]: xy が x と入力された回数
  • ins[x,y]: x が xy と入力された回数
  • sub[x,y]: y が x と入力された回数
  • trans[x,y]: xy が yx と入力された回数
• 混合行列の生成
  • スペル誤りの一覧 by Peter Norvig
  • 1文字の編集誤りのカウントデータ by Peter Norvig
    • 全データのリスト
• Noisy channel モデルの確率分布を以下のようにする

P(x∣w)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪del[wi−1,wi]count[wi−1wi],if deletionins[wi−1,xi]count[wi−1],if insertionsub[xi,wi]count[wi],if substitutuiontrans[wi,wi+1]count[wiwi+1],if transpositin$P(x\mid w)=\{\begin{array}{l}{\displaystyle \frac{\mathrm{d}\mathrm{e}\mathrm{l}[{\mathrm{w}}_{\mathrm{i}-1},{\mathrm{w}}_{\mathrm{i}}]}{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[{\mathrm{w}}_{\mathrm{i}-1}{\mathrm{w}}_{\mathrm{i}}]}},\text{if deletion}\\ {\displaystyle \frac{\mathrm{i}\mathrm{n}\mathrm{s}[{\mathrm{w}}_{\mathrm{i}-1},{\mathrm{x}}_{\mathrm{i}}]}{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[{\mathrm{w}}_{\mathrm{i}-1}]}},\text{if insertion}\\ {\displaystyle \frac{\mathrm{s}\mathrm{u}\mathrm{b}[{\mathrm{x}}_{\mathrm{i}},{\mathrm{w}}_{\mathrm{i}}]}{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[{\mathrm{w}}_{\mathrm{i}}]}},\text{if substitutuion}\\ {\displaystyle \frac{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}[{\mathrm{w}}_{\mathrm{i}},{\mathrm{w}}_{\mathrm{i}+1}]}{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}[{\mathrm{w}}_{\mathrm{i}}{\mathrm{w}}_{\mathrm{i}+1}]}},\text{if transpositin}\end{array}$

• Add-1 スムージング
  • 混合行列のデータに出てこなかったスペル誤りは訂正できない
  • すべてのカウントに 1 を足すスムージングを入れて、これを回避する

評価データ

• 以下のようなスペル誤りのテストセットが公開されている
  • Wikipedia
  • aspell
    • Wikipedia のデータのフィルタされたバージョンがある
  • Birkbeck spelling error corpus
  • Peter Norvig

Noisy channel モデルによる文脈依存のスペル訂正

• Real-word スペル誤りに対しては文脈（単語の周辺の情報）が必要
• 文（クエリ）中の各単語について
  • 候補集合を生成する
    • 単語そのもの
    • 1文字までの編集で辞書に入っているもの
    • 異形同音異義語 (homophone)
• すべての候補からもっともよいものを選択する
  • Noisy channel モデルを使って計算

Real-word スペル訂正の流れ

• 候補生成
  • 文 x1, x2, x3, ..., xn があったとする
    • xi は単語
  • 各単語 xi に対して候補集合を生成
    • Candidate(x1) = {x1, w1, w1', w1''}
    • Candidate(x2) = {x2, w2, w2', w2''}
    • Candidate(x3) = {x3, w3, w3', w3''}
• 候補選択
  • P(W∣x1,...,xn)$P(W\mid x_1,...,x_n)$ を最大化する単語の並び W$W$ を選択する
  • P(w1...wn)$P(w_1...w_n)$ には言語モデルを使う
    • たとえばバイグラム (bigram) 言語モデル
    • P(w1...wn)=P(w1)P(w2∣w1)...P(wn∣wn−1)$P(w_1...w_n)=P\left(w_1\right)P(w_2\mid w_1)...P(w_n\mid w_{n-1})$

Noisy channel モデルの改良

• 重み付き Noisy channel モデル
  • w^=argmaxw∈VP(x∣w)P(w)λ$\hat{w}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{w\in V}P(x\mid w)P{\left(w\right)}^{\lambda }$
  • λ$\lambda$ は開発セット (development test set) から学習
• Richer edit [Brill and Moore 2000]
  • ent --> ant
  • ph --> f
  • le --> al
• 発音を通信路のモデルに組み込む [Toutanova and Moore 2002]
• デバイスを通信路のモデルに組み込む
  • 端末ごとの違いを取り入れる
  • デバイスごとにシステム的に分けてもよい

講義資料

• Wildcard queries and Spelling Correction (pdf)
  • Spelling correction

参考資料

• IIR chapter 3
• How to write a spelling corrector (Peter Norvig)
• Techniques for automatically correcting words in text (Kukich 1992)
• Finding approximate matches in large lexicons (Zobel and Dart 1995)
• Efficient Generation and Ranking of Spelling Error Corrections (Tillenius)