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候補の数を揃えて、検索とかで使う評価指標（忘れた）で評価してもらいたい。

AlchemyAPIのSentiment精度をSentiment140のデータで評価する

AlchemyAPI
http://www.alchemyapi.com/

Techchrunchでも紹介されていた。
http://jp.techcrunch.com/2013/02/09/20130207alchemy-api-raises-2-million-for-neural-net-analysis-tech-on-par-with-ibm-watson-google/

AlchemyAPIは、固有名抽出（NER）とか極性抽出（Sentiment analysis）とか、自然言語処理技術をAPIを通じて提供するベンチャー。
自然言語処理系ベンチャーではかなり成功しているのではないだろうか。

今回は極性抽出について、彼らの精度を見てやろうって話。

AlchemyAPIはFreeのAPIを発行していて、メールアドレスだけしっかり登録しておけばあとは適当な情報を書いてもOK。1日1000回リクエストまでAPIを発行していいそうだ。ちょっとしたことをやるなら十分。少し腰を入れるとすると全然足りないという、まさにすばらしい調整。

各プログラミング言語でSDKが提供されている。
今回はJavaを選択した。SDKを見れば接続、評価は簡単にわかるだろうから省略。
とてもシンプル、かつ分かりやすいSDK。すばらしすぎる。

Sentiment140
http://www.sentiment140.com/

評価対象のデータは、Twitterで極性がついているもの。
Stanford大学の人がデータを作り、学術目的なら無料で利用できる。

今回はSentiment140のtestデータをAlchemyAPIに投げてみた。

結果は、
データ数: 498
　Pos: 182
Neg: 177
Neu: 139
Accuracy: 0.649

PosとNegだけで評価したら
データ数: 359
　Pos: 182
Neg: 177
Accuracy: 0.705

ちなみに、Sentiment140を提供しているStanford大学のGoらの論文はこちら。
"Twitter Sentiment Classification using Distant Supervision"

彼らの手法の説明は省略する。
論文は検索すればすぐに見つかるし、とても読みやすい＆手法がシンプルなので、すぐに理解できるはず。

論文の結果部分から、
素性はUnigram、識別器はSVMrightのlinear kernelで、Accuracy 0.822。
※ちなみに上記はPos/Negの評価で、Neuは外している・・・と論文に書いてあった気がする。

ここまでの結果をうけて・・・

AlchemyAPIはTwitterに特化しているわけではなく、一般文書やWebにも対応している。また、Sentiment analysisに特化しているわけでもない。

なので、一応、精度的にはGoらの手法に及んでいないが、だからといってAlchemyAPIのSentiment analysisが使えないということでもない。

参考までに、AlchemyAPIの出力は、
データ数: 498
　Pos: 215
Neg: 164
Neu: 119

となっており、少しPositiveを出しやすいのかなとも思ったけど、正解データとの分布みるとそこまでではないかなと思ったり。

何をどう間違えたかまでは見ていないので、それは次回。

Beyond Normalization: Pragmatics of Word Form in Text Messages

IJCNLP2011

Tyler Baldwin, Joyce Y. Chai
Michigan State University

OOVの正規化論文。
この論文では、OOVというのは単にIVの揺れというだけではなく、感情や強調などといった書き手の気持ちが含まれていると主張している。

例えば、
A: They won the game!
B: Yessssss
という文脈があると、"Yessssss"には単に"Yes"だけではなく、興奮などの感情が込められている。

コーパス作成
人手である程度整備した辞書（CMU pronouncing dictionary）に含まれていない単語をOOVとする。
Amazon Mechanical Turkを利用し、3人のアノテイターに以下のタグ付けをお願いした。
※3人とは少ないな・・・

1. 対応するIVを書く。
2. Fear, surprise, happiness, disgust, sadness, anger, other, noneから選ぶ
3. Friendliness/closeness, emphasis, other, noneから選ぶ
4. Extra information, to save time or space, unintentional mistake, otherから選ぶ

2については、ほぼNoneになった。次ぐのはHapiness。
3については、NoneとEmphasisが高い。
4については、約半数がExtra informationだった。

4の結果を踏まえ、OOVがExtra Informationを含むかどうかを判定する二値分類を行った。
素性は、
1. Character level features
同じ文字が二度以上使われているかどうか
一番多い文字は何か
IVから消された文字は何か
編集距離
IVより長い文字長か。
concatenated wordかどうか
数字を含むか
英数字（alphanumeric）を含むか
全部大文字かどうか
2. Punctuation features
続く文字がコンマ、ピリオド、クエスチョンマーク、ビックリマーク、もしくは顔文字かどうか
3. Positional features
文の最初か、最後か、途中か、単体か

SVMで学習識別したところ、72.4%のAccuracyが出た。

もう一歩踏み込むとおもしろいかな。

A Character-Level Machine Translation Approach for Normalization of SMS Abbreviations

IJCNLP2011

Deana L. Pennell, Yang Liu
The University of Texas at Dallas

非常に読みづらい。わかりづらい。
本文中に出てくる数字の意味がわからなかったり、図表が説明不足or本文と一致がとれなかったりで私には理解できなかった。
英語力の問題ならいつか理解できると信じ、一応めも。

Character-levelの機械翻訳（MT）で、Mosesを使っている。
提案手法は２ステップ。Character-levelのMT。デコード時には言語モデルを利用。
対象はAbbreviation。本論文ではOOVとIVは1:1対応という前提。

MTなので学習データを作る必要がある。
その学習データの作り方に、少し工夫がある。
対象はTweetなのだが、Tweetを適当にサンプリングしてアノテーションすると、OOVが含まれなかったり、同じOOVばかりをアノテーションすることになってしまう。
そこで、以下の5つの条件でTweetを絞り込んでいる。

1. Word Count Index
説明不足でよくわからんが、少なくとも５単語以下のTweetは対象外にしている。
2. Perplexity Scores
英語じゃないTweetを削除するため、（何を対象としたか不明だが）通常の英語文を元に構築した言語モデルでのPerplexityが1000以上、かつ
コーパス内で一般的なTweetを削除するため、（これまたどういうことか不明だが）筆者らの学習コーパスで構築した言語モデルでのPerplexityが1000以上のTweetを対象。
3. OOV Count
辞書にない単語をカウントし、一個もなければ対象外。
4. OOV Percentages
OOVのテキスト内での割合が5割以上、かつOOVの異なり数での割合が5割以下なら対象。
5. OOV Frequency Scores
コーパス内での出現が多いOOVを含むテキストを対象。

※例えば、コーパス内でのPerplexity Scoresという指標は、取り逃しが多くなりそうだから正直疑問。OOV Percentagesという指標は、OOVの割合が高すぎる上に異なり数でのフィルタリングとか意味が分からない。OOV Frequency Scoresというのは、それこそ網羅性が著しく減りそう。

上記のデータを対象に、5人の学生（と多分、第一著者）がアノテーションを実施。
（データを集めた時点でOOVはすでにアノテートされているのかもしれないが）OOVとその原型IVをアノテーションする。カッパ値は0.891とかなり高い。
※ただし、カッパ値の計算で怪しい記述があるため信じられない

ここから手法の肝となる部分なのだが・・・
一応、このあとも読んだけども、ここまでと同様に不明な点、理解できない点、信じられない点が多すぎるため、このへんで書くのはやめておこう。

つづきは今度。

Improving Text Normalization Using Character-blocks based Models and System Combination

COLING2012

Chen Li and Yang Liu
Department of Computer Science The University of Texas at Dallas

細かいことを色々やっているが、そのあたりは省略。
大きなポイントだけおさえる。

筆者らの言葉を使えば、character-levelの機械翻訳（MT）をcharacter-block-levelで行ったという論文。
先程もいったが、それだけだとイマイチ進歩性にかけるため、多くの細かい工夫を行なっている。・・・が、読み込んでいないので省略。

筆者らの手法は４つのサブシステムで構成される。

Character-Block Level MT
（たぶん人手で集めた）60個のcharacter-blockとその発音ペアを使う。
例えば、"yesterday"なら、"y e s t er d ay"というようなBlockになる。
このBlockでMTをかける。

Character-Block Level Sequence Labeling
CRFでラベリング。BILOUスキーマ。
基本的にはLiu et al. (2011)の論文と同じ。
違いはCharacterのかわりにCharacter-Blockを用いる点。
特徴量としては、Character-Blockを対象に
1. 表層
2. 音韻 (Phonetic)
3. 音節 (Syllable)
4. 単語単位
でBILOUスキーマを割り当てる。

Character-level Two-step MT
筆者らの以前の仕事を少し改善して利用。
OOVのある文字を直接IVのある文字に置き換えるのではない。
OOVのある文字を、まずphonetic sequenceに変換する。そしてそれを任意の文字（列）に変換する。
改善ポイントは、
1. いくつかの人手で定義した対象は、two-stepではなくone-stepで直接変換してしまう。
2. リランキングを行う（細かすぎるため省略）

Spell Checker
Jazzy Spell Checkerを利用

以上の４つを組み合わせ、N bestのNormalizationシステムを組み上げる。
組み合わせ方にはかなり細かい工夫があり、細かすぎるため省略。

実験の結果、Liu et al. (2012)やHan and Baldwin (2011)など、ACLに採用された論文がいい結果を出している。提案手法も実験セットによってはよい結果を出している。

細かすぎるので読み飛ばしてしまったが、そこに注目すべきかも。
後日リバイズ・・・するか、だれかのブログでも探すか。

A Broad-Coverage Normalization System for Social Media Language

ACL2012

Fei Liu, Fuliang Weng, Xiao Jiang
Research and Technology Center, Robert Bosch LLC

Twitterを対象にしたテキストNormalizationの論文。
人間の知覚に基づいた３つのアプローチにより正規化候補を算出する。
それぞれ、
Enhanced letter transformation
Visual priming
String and phonetic similarity

Enhanced Letter Transformation
noisy channel modelでOOVの元となるIVを探す。
このとき、acronym (e.g. "bbl" for "be back later") は本論文では対象としない。
BackgroundコーパスでUnigramモデルを作って、そのデータを利用してnoisy channel modelを解く。
学習モデルにおけるOOVとIVのペアは、Google searchを使ったLiuらの論文（Liu 2011, "Insertion, deletion, or substitution? Normalizing text messages without pre-categorization nor supervision", ACL）で自動的に作る。
OOVの文字はそれぞれ
(a) 0-9の数字のどれかに対応
(b) アルファベット26文字のどれかに対応（自身を含む）
(c) nullにする
(d) いくつかのコンビネーションにする（ah, ai, aw, ay, ck, ea, ey, ie, ou, te, wh）
というように、IVの各文字と対応つける。
ここで作ったIVとOOVのペアは非常に雑多であるため、
1. phoneme boundary, syllable boundary, morpheme boundaryそしてword boundaryを考慮
2. globalな文脈を考慮
以上の2点により、質の向上を図っている。

Globalな文脈考慮
OOVがIVのLexical variantsならば、両者の前後に現れる単語も類似するはず。
そこで、前後に出現する単語をカウントし、上位100語をOOVまたはIVの文脈単語ベクトルとし、コサイン類似度で類似度を図る。
単語の重みはTFIDF。
※少し特殊なTFIDFで、なんか正規化が重複してかかっているような印象を受けた。
一定の類似度(Θ>0.0003)を持つペアだけに限定し、46288ペアから5000ペアに限定して実験に用いる。
※類似度を測った意味があったのか。結局トップ5000なのでは？

Phoneme-,syllable-, morpheme-, word-boundary考慮
Phoneme-, syllable-, morpheme-, word-levelで、BILOU tagging schemeとCRFでタグ付け。BILOUは、それぞれBegin, Inside, Last, OutsideおよびUnit-lengthの頭文字。
これにより、OOVとIVの対応付けが、1文字ごとの対応から数文字での対応を見るというような形になる。noisy channel modelで類似度を算出。

Visual Priming Approach
簡単に言ってしまえば、LCS (Longest Common Subsequence) を見ましょうということ。
log(TF(IV)) X [LCSの長さ] / [OOVの長さ]
※つまり、IVがよく使われやすい単語で、かつIVの先頭か末尾が少しだけ編集（追加、削除、置換）されているOOVはペアですよってことだね。

String/Phonetic similarity
Jazzy spell checkerを使った。

以上、3つの方法を紹介した。
3つの手法をどう混ぜるか
Oracle設定 各結果のtop nを集める（合計3n)。
Word-level設定 "Letter Tran"と"Spell Checker"からtop 3を収集（ただし、それぞれに閾値を設けるので、必ずしも3つずつではない）＋n個になるまで"Visual Priming"で埋める。
Message-level設定 Word-level設定に対し、local contextを使ったViterbi decoding processによりリランキング。

実験
結果については論文を参照。
Visual Primingがいい感じという結論。
文脈情報を利用したリランキングにより、精度は大幅に改善する。

※ところどころよく分からない部分があった。
※実験については、もう少しなんとかならなかったのか。
※Normalize手法については、新しくはないがもっともらしいことをやっているので、参考になった。

Named Entity Disambiguation in Streaming Data

ACL2012

Alexandre Davis, Adriano Veloso, Altigran S. da Silva, Wagner Meira Jr., Alberto H.F.Laender
Federal University of Minas Gerais, Federal University of Amazonas

こちらもNENの論文。
相変わらず読み込んでいないし読み込んでいない論文が多すぎるが、メモとして残す。

機械学習による分類タスク。
NEと代表表記の組みが、正解か否かを判定する。

仮説として、
アノテーションはコストがかかる。アノテーションはしきれない。
よって、正解ラベルがついたデータと大量のラベルがついていないデータがある。
それらをEMアルゴリズムで再帰的に学習させることで、大量のラベルなしデータを救うことができる
というもの。
正直、従来のアノテーションデータを利用して学習し、新規データに対して抽出を行うタスク、との違いがわからない。読み込みが足りないのかも。

EMアルゴリズムを使う部分は、ざっくり説明すると以下の感じ。
ラベルつきデータを使って学習
テストデータで評価
ラベルを反転させるようなルールを適用、閾値評価により反転
上記を繰り返し、最適な閾値を算出

ラベルを反転させる理由は、テストで間違った部分（FP、FN）の再学習が目的。

論文にはいろいろ提案手法について詳しくかかれているので、そこを読み解く必要がある。
現在の認識では、やっていることがわけわからん。

おもしろいと思ったのは、少量の学習データでも大量のラベル無しデータを、精度よく抽出できていたこと。
アルゴリズムによる特徴なのかは不明。従来手法でもけっこう高かったし。

AUCによる評価って、どうやってみればいいのか調べる必要がある。
AUCってなんだっけ。