Social Text Normalization using Contextual Graph Random Walks

論文メモ

ACL2013

Hany Hassan, Arul Menezes
Microsoft Research

OOVのNormalization
昨年、ちらほらRandom Walkが熱いと聞いていたので、さっそくチェック。


OOVを正規化する上で
1. 辞書に含まれていない多くの単語やNEは正規化するべきではない。
2. 同じOOVでも文脈やドメインによって適切な正規化があるはずである。
3. 正規化はHigh precisionでなければならない。
4. 当然、High recallが望ましい。

提案手法は、
1. IV候補と周囲の単語とでラティス構造を作り、言語モデルとViterbi decoderによって最適なIVを見つけ出す。
2. Unsupervisedで行う。

提案手法は、contextual similarity graphに対して、Random Walksを使う。

対象のOOVは、IVと1対1対応になっているもの。
btw <=> by the way
などは扱わない。



Baseline
Aspellに似た辞書ベースのspelling correction。
実験ではすべてのIV候補にViterbi decoderを適用し、最適なIVを特定する。

もうひとつはtrie approximate string matching with K errors。
(Chang etal., 2010) に類似した手法である。
K errorsは置換、追加、削除によって行われる。
我々は、さらにerrorsをカスタマイズした。
冗長化（lengthening）、文字置換、文字-数字置換、音的置換である。


Graph-based Random Walks

Bipartite Graph Representation
文脈的な類似度を評価したい。
WordのNgramを見て、たとえば{word1 word2 * word4 word5}の*に合う単語が、文脈的に類似度が高い。
この文脈的な類似度をbipartite graphで表現する。
First partiteは単語で、Second partiteは単語Ngramである。
First partiteはIVでもOOVでもよい。
適当なコーパスの中で、出現数がthreshold以下の単語をOOVとみなし、正規化対象とした。

Lexicon generation using Random Walks
Bipartite graphを作るのにMarkov Random Walksを使った。
Bipartite graphにおいて、OOVから始まりIVに終わるという問題を考える。
経路の重さは共起回数を元に計算している。
一定の試行回数以内に収束し（IVにたどりつか）ない場合は解なし。
収束までの回数がそのままコストとみなせる。
OOVのIV候補はいくつかあるので、コストとしては各IV候補の収束回数の和で全体を正規化して使用する。
後述のSimCostと合わせて最終的なコストが決定する。

Lexical Similarity Cost
LCRのRatioでコストを決める。
SimCost=LCS(n,m)/(ED(n,m)*MaxLength(n,m))
EDは編集距離で、Editex edit distanceを利用。
MaxLengthは文字長の大きい方の値。


Experiment
73,000,000ツイート（StreamingAPI March-April 2012）をnoisy dataとして利用。
English LDC Gigawordコーパスから50,000,000文をclean dataとして利用。
clean dataは学習時に使い、経路のコストを計算する。

test setは1000 sentenceで人手で作成。
機械翻訳（英語-スペイン語）の評価用に500 sentenceをバイリンガルによって作成。

clean dataでIVとOOVを決定する。
方法は先に述べた、コーパス内での出現回数による分類。閾値は10回。
noisy dataとclean dataの両方を使って、真ん中がOOVの5gramデータを作成する。
OOVのIV候補を使ってlaticeを作り、5gramにおけるbestなViterbe pathを計算する。

ベースラインは
・辞書引きスペルチェッカー
・trie approximate math with K errors (K=3)
コスト関数はSimCost

提案手法のRandom Walksは100 walks。
word nordの最終的な数は7M, context nodesは480M。
MapReduceを使って計算した。
最終的には、1つのOOVに対して5つまでのIV候補を出力する。

結果
人手で作った1000文の評価データで評価。従来手法よりも劇的によい。
Random Walksのstep2までの結果で作ったIV候補が一番よい結果を示した。
※PrecisionとRecallで評価しているが、どのように評価したか不明。というかP-Rで評価できるの？
※辞書ベースはトップ1、trieはトップ3、提案はトップ5だとしたら不平等ではないか？

(Han et al., 2012)と比較。
人手で作った1000文の評価データで評価。さらにHanらの作成した評価データでも評価。
どちらにおいても、提案手法が劇的によい。
※比較方法は不明。

Error Analysis
※よくわからない。
※いくつか例があるが、一文にたくさんOOVが含まれている。5gramの真ん中のスロットのみがOOVの対象に限定したのではないのか？
※比較に辞書ベースを用いているが、文脈によるViterbi decodingしてるならもう少しまともになりそうだが・・・。


MTの評価
※省略
※むしろなぜ載せた？


総評
実験のところが荒い気がするが、興味深い内容だった。
Random Walkをこうやって使うのはおもしろい。
アルゴリズムの流れが不明瞭なので、もう少し明らかにしてほしい。英語力の問題・・・？
最終的に1 bestを出力して精度が実験結果通りなら、なかなかよい気がする。
ただ、その1 bestはViterbiで求めているように思うので、Viterbi依存？
となると、従来手法との比較では、IV候補の数を揃えて、検索とかで使う評価指標（忘れた）で評価してもらいたい。