スペル修正、翻字（Transliteration)周りのサーベイ
最近自分の分野と比較的近い、スペル修正、翻字（Transliteration）の分野の論文を読んでいます。カタカナーローマ字間の翻字はストーリーがあると思いましたので、テキトー紹介したく思います。かなりざっくりしていますのでご了承ください。主に検索クエリ周りの論文を収集しています。検索クエリ＝企業の独壇場！なイメージですね。
０．Knight and Graehl, Machine Transliteration, Computational Linguistics 1998
全ての始まりです。カタカナのローマ字表記と英語表記は似てるよねー、編集距離とればいいんじゃない？という話。
１．Brill et al. An Improved Error Model for Noisy Channel Spelling Correction, ACL 2000
この論文が編集距離における統計的手法の始まりです。編集距離の問題として、例えばスペル修正のタスクにそのまま適用しようとすると、閾値が全ての文字列間において一意に決めにくい問題があります（と今日考えました）。
例えばis->amの編集距離は2ですが、vaccumとvacuummの編集距離も2になります。文字列長でNormalizeする方法も考えられますが、この論文では単純に「2文字以上の編集を許す」ことにし、「どの編集が適用される確率が高いか」を学習データから学習しています。上の例から行きますと、is->amはスペルミスではないと考えられるので学習データには含まれていないはずです。一方vacuumm->vaccumに訂正する学習データがあれば、「is->amにするよりuu->cuにする方が起こりやすい」とモデルが解る訳です。
ちなみに補足としてこの論文で二文字以上の編集を許す場合は「編集が起きている場合」に限っています。vacuummとvaccumの例で行きますと、v/v, a/a, c/c, u/c, u/u, m/ε, m/m, にアラインされます（εは空列を意味します）。この場合「編集が起きている」＝「編集前後の文字が異なる（空列を含める）」とし、u/cとm/εの前後の編集をn文字許します。n=1の場合は、cu/cc, uu/cu, um/uε, mm/mεが編集として許されます。論文中ではεが暗黙の内にドロップされていた上、|α|やらnやらで編集を許すサイズが定義されていたので（ちなみに|α|=|β|とすると、|α|=n+1です。|α|≠|β|の場合のnの対応はまだ理解していません）、僕が論文を読んでいる時に理解するまでに時間がかかりました。（おまけに同じ著者の別の論文で例に間違いがあるので余計時間かかりました）
全てはこの論文を根として、木を描いているイメージです。一言でいいますと「編集距離を利用して文字列間のアライメントを取り、最も確からしいアライメントを取ろう！」という話。
ここからストーリーは３つ（以上）に分かれます。
A. カタカナー英語間の翻字
- Brill et al., Automatically harvesting katakana-english term pairs from search engine query logs, NLRS 2001
１．の手法をカタカナと英語間の翻字を認識するタスクに使用してやったぜ！という話です。論文中にある例でntex->ntekが抜けているので注意してください。
- Hagiwara and Suzuki, Japanese query alternation based on semantic similarity, ACL 2008
Distributionalな素性は使えそうだけどSparseになりやすいからKernelを使って文字列間の近似を取ったよ！という話です。
Distributionalな素性とは何か？ですが、検索エンジンにクエリを投げる時にスペースを空けて入れるもう一つのキーワードとそのパターンのPointwise Mutual Informationを取っています。例えば「JAL」が「日本航空」の書き換え候補となりうるか？という問いに答えるため、「JAL 航空券」というクエリと「日本航空 航空券」があったら文脈ベクトルとして{PMI(後ろに「航空券」が続く, 日本航空)}と、{PMI(後ろに「航空券」が続く, JAL)}の２つのCosine類似度を測ります。この手法は後述するLiらがadventuraがadventureのスペルミスでないことを示すために考えた手法からインスパイアされています。
気になった部分としてテストデータ構築の際に短い時間でユーザがタイプしたクエリは書き換え候補になりやすい、という仮定の元でコロケーション検出で用いられるLog-likliehood testの閾値以上の値を抽出している部分です。これである程度は高いAccuracyを出すのでは？と疑問でしたが、約10000ペア中約6500ペアしか書き換え候補ペアを抽出できていないので提案手法のAccuracy約80％を考えるとベースライン程度の役割しかなっていなかったことが伺えました。
この論文も１．の手法を素性の一つとして用いてますが、編集の確率を学習するデータとして英語と日本語の記事のタイトルペアを用いたみたいです。別の論文でもWikipediaを使って編集の確率を計算する手段を見ましたが、アカデミアでもよくある手法みたいですね。
Kernel部分は詳しく理解していません。キーワードのパターンを繋げる、程度しか理解していません。
- Cherry and Suzuki, Discriminative substring decoding for transliteration, EMNLP2009
機械翻訳の際に翻字が認識できると便利だよねー、という話。理解していません。
- Yang et al. Jointly optimizing a two-step conditional random field model for machine transliteration and its fast decoding algorithm, ACL 2010, short paper
Direct Orthogonal Mappingというアルファベット列とカタカナ（や中国語）の対応を取ってしまう手法。例えば「Goo=グー」「gle=グル」と対応を取ってしまう。
- Hagiwara and Sekine, Latent Class Transliteration based on Source Language Origin, ACL 2011, short paper
外来語は語源の言語があるからそれを隠れクラスとしてモデルを構築しよう！という話。理解していません。
- Yoh Okuno, Applying mpaligner to Machine Transliteration with Japanese-Specific Heuristics, Named entity workshop at ACL2012
詳しくは読んでいないのですが、少し表の数字が低いことが気になりますかね。（あくまで実用面での意味で。）
- Hagiwara and Sekine, Accurate Word Segmentation using Transliteration and Language Model Projection, ACL 2013, short paper
カタカナ文字列は長いと細切れになってしまうからこれを何とかしよう、という話。詳しく読んでないです。
