唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

論文感想: "Social Text Normalization using Contextual Graph Random Walks" (ACL 2013)

Twitterとかのソーシャルメディアではくだけた表現が多いので、そういうテキストの正規化をする話
以下論文中の例の一部

  • wuz up bro (what is up brother)
  • 4get (forget), 2morrow (tomorrow), b4 (before)
  • fon (phone)
  • LMS (like my status), idk (i do not know), rofl (rolling on floor laughing)

この論文では1つの単語が別の1つの単語に対応している場合だけを扱う(つまり上の例の最後の行のようなものは扱わない

基本的なアイディアとしては前後の文脈(単語)が共通する単語は似た意味を持っているということを利用している。
word1 word2 word3 word4 word5と並んでいる時、word3の文脈はword1 word2 word4 word5になる
ただし文脈中の単語は一定回数以上出現した単語に限る
以下のようなグラフ(左側が文脈、右側が単語、遷移確率は共起頻度に基づく)上でのランダムウォークを考える
f:id:sucrose:20131013223308p:plain

hitting time (最初のノードからある特定のノードに到達するまでの平均遷移数)を正規化したものをコストとする
今回のタスクではノイジーな単語(くだけた表現)から通常の単語へのhitting timeを計算していて、hitting timeが小さいほど似た意味であると考えられる

このhitting timeに基づくコストと、最長部分文字列(LCS)を文字列全体の長さと編集距離で割った値に基づくコストの線形結合を全体のコストとする
ノイジーな単語ごとに正規化候補を求めて、このコストを使って足切りを行う

最終的なテキストの正規化は、候補の単語の組み合わせに対して5-gramの言語モデルで最大になるようなパスをViterbiアルゴリズムを使って求める

先行研究と比べてよい結果が得られた
f:id:sucrose:20131013230058p:plain
結果の例
f:id:sucrose:20131013225200p:plainf:id:sucrose:20131013225309p:plain

感想

先行研究のスコアと比べるとよすぎて(Recallが倍以上よい)、比較として正当なのかちょっと疑問がある……
先行研究の方も以下の記事で紹介しているけどこちらの方は単体では微妙だったけど既存の辞書と組み合わせたらF値がよくなった」的な主張をしているので、作った方の辞書単体で比較するのはどうなんだろう(いいような気もするけど