Joint Inference of Named Entity Recognition and Normalization for Tweets

ACL2012

Xiaohua Liu, Ming Zhou, Furu Wei, Zhongyang Fu, Xiangyang Zhou
Harbin Institute of Technology, Microsoft Research Asia, and others

Named Entity Recognition (NER)とNamed Entity Normalization (NEN)に関する論文。
Twitterはリアルタイムの情報量が多いので、新しい情報源として注目されている。

この論文では、
PERSON,ORGANIZATION,PRODUCT,LOCATION
以上の４つのNEを抽出し、その代表表記に置換する手法を紹介している。
精度は、NERがF値80.2%〜83.6%、NENがF値79.4%〜82.6%と高い結果が出ている。

従来研究についても詳しく紹介されているが、省略。

本手法の特徴は、NERとNENを複数のTweetを使って相補的にモデルを作る点である。

例えば、あるTweetの"Alex"と別のTweetの"Alex Russo"がNERシステムによりPERSONと認識できれば、NENシステムが"Alex"を"Alex Russo"に正規化できる。

逆に、あるTweetの"burger king"が別のTweetの"Burger King"にNENシステムが正規化できなかったら、NERシステムはそれぞれに別々のNEを割り振れる。

提案手法は、BILOUスキーマとlinear chain CRFで実装している。
i番目のTweetのm番目の単語y^i_mと、j番目のTweetのn番目の単語y^j_nが同じEntityかどうかという変数z^ij_mnがある。
skip-chain CRFs (Galley, 2006)とは、正規化変数z^ij_mnがあるという点で異なる。

正規化変数z^ij_mnについて
同じEntityで、かつ同じLemmaだったら1となる。
例えば、あるTweetの"Gaga"がPERSONかつlemmaが"gaga"、別のTweetの"gaga"がPERSONかつlemmaが"gaga"なら、これらの正規化変数z=1。
ただし、stop wordに設定されているものは、対象外とする。
※stop wordは論文を参照のこと。

さて、正規化変数zが設定できたものについて、NEのまとめあげを行う。
上の例では、"Gaga"と"gaga"がともにPERSONでlemmaが"gaga"だった。
BILOUタグで上の例がそれぞれ"Lady Gaga"と"laaady gaga"だったとすると、"gaga"の一致から、これらは正規化しうるペアと見なせる。
同様に他の例でもペアを作っていき、「A=BかつB=CゆえにA=C」ということをやる。
そしてできた正規化候補集合の中で、もっとも出現回数が多い表現を標準表現とし、他の表現を標準表現に正規化する。
標準表現になりうる表現が複数ある場合は、Wikipediaのエントリーを採用。
※それでも複数ある場合はランダムに決める。

NER+NENの最適化については論文を参照のこと。
※たぶんME。

外部辞書を使う
WikipediaやFreebaseなどから35億語の辞書を構築。
その辞書内語と一致する語が現れた場合、可能な限りのEntityを付与する。
たとえば、"new york"という単語が現れた場合、辞書には"New York City"と"New York Times"が登録されいるため、この"new york"にはORGANIZATIONとLOCATIONのタグが付与される。

正規化変数zの条件を緩める
単語y^i_mと単語y^j_nのlemmaが完全に一致する場合のみ、z=1だった。
これに下記ルールを適用する。
1. 単語y^i_mと単語y^j_nが同じハッシュタグを持つときz=1。
2. Tweet^iとTweet^jの単語ベクトルの類似度が0.8より大きいときz=1。
3. Tweet^iとTweet^jの単語ベクトルの類似度が0.3より小さいときz=-1。

特徴ベクトル
1. Orthographic features
capitalizedなのか、upper caseなのか。
alphanumericなのか、slashを含むのか。
stop wordなのか。
prefixは？suffixは？

2. Lexical features
t^i_mとt^i-1_mとt^i+1_mのlemma。
t^i_mがOOVかどうか。
t^i_mとt^i-1_mとt^i+1_mのPOS。
t^i_mがハッシュタグかどうか。リンクかどうか。ユーザー名かどうか。

3. Gazetter-related features
※よくわからない。
外部辞書を参照して追加した語の有無。
外部辞書を参照して追加された最も多いタイプなのか。
外部辞書を参照して追加された最も多い単語なのか。

※もうひとつFeature Setがあるけど、めんどうなので省略。

評価では、テストデータを作成している。
2245Tweetに対してアノテーションを施し、２人のアノテーターでカッパー値0.72。

lemmaはOpenNLPを使用して取得。
POSはRitterらが作ったPOSタガーから取得。

結果は前述のとおり高い精度。
比較対象が筆者らの前の手法。それも結構高い。

エラーを解析したところ、
「スラングや短縮表現に弱い」
ということがわかった。
これは、lemmaを利用しているため、lemmaを計算出来ないような対象に弱いことを意味している。

例えば"California"と"Cali"。
後者は人名にもなりうる。

また、省略形が一般的に使われるようなもの。
例えば"Windows 7"と"Win7"。後者のほうが一般的に用いられているようだ。

※まだ読み込めていない。
※NERとNENを相互に最適化するというのは非常におもしろい。だが、複数のTweetを使うという点で、ものすごいコストの高い手法なのではないか。また、実験結果では示されていたが、相互に最適化したところで精度が本当にあがるのか疑問。

Automatically Constructing a Narmalisation Dictionary for Microblogs

ACL2012

Bo Han, Paul Cook, Timothy Baldwin
The University of Melbourne

タイトルからすると自動で崩れた表現と正規化表現の辞書を構築するという、とても興味深いもの。
英語の崩れた表現、例えば"2morrow"と"tomorrow"みたいなペアを作る。

従来研究には、
編集距離を使ったスペルチェック
Machine translationの枠組み
Distributional/string similarity
など。
提案手法は文脈情報を使う。

具体的に言うと、OOVの単語と似た文脈で使われる語をIVの候補とする。
OOV/IVの直近の単語やそのN-gramなどなどでベクトルを作る。
類似度の判定は、Kullback-LeiblerやJensen-Shannon、Euclidean distance、Cosine distanceなどメジャーなもの。

OOVの定義は、辞書になくて、対象コーパスで64回以上出現、かつ文字長が4以上。
上記手法でOOVとIVのペアを作った後、そのペアが正しいかどうか、Amazon Mechanical Turkで評価。OOVの63.3%は正しいペアがある（正解率ではない）ことがわかった。

ひとつのOOVにいくつかのIV候補があるわけだが、候補についてリランキングを行う。
方法は、
リランキングしない（文脈類似度のみ）
コーパスでの出現頻度が多いOOVを上位にする
Google Web 1T corpusでの出現数が多いIV

評価
ちょっとよくわからないが、比較に辞書を使っている、もしくは組み合わせている？
文脈類似度のペアの精度はP 0.47 R 0.22 F 0.30とイマイチ。
辞書の組み合わせで一番よいのが、P 0.85 R 0.63 F 0.72とかなりよい。

読んだ感想としては、
文脈を見ればOOVの正規化表現IVはある程度候補を集められる。しかし、網羅率はせいぜい6割。ここから文脈の類似度や編集距離を突き詰めても、そこまで精度よく答えを求められない。
正解率をあげるためには、既存の辞書を使うほうがよい。
既存の辞書は網羅率が低い、提案手法は正解率が低い、組み合わせてもそこまで精度がよくならない気がするが、そこはうまく工夫したのだろう。

あまり読み込んでいないのでなんとも言えないが、かなりいろいろ検討工夫している様子。ただし、手法自体に独自性があるとは感じなかったので、もっともらしい手法を丁寧にやったのだろう。丁寧にやるのは大事。

Robust kaomoji detection in Twitter

Steven Bedrick, Russell Berkley, Brian Roark, Richard Sproat
Oregon Health & Science University

辞書では対応しきれないような生成的な「顔文字」という対象を抽出する。
Twitterを対象としたコーパス作成。StreamingAPIで50日間観測。
9193のサンプルを収集、3700の顔文字は重複なし。重複は2500。

顔文字は文字通り顔に見立てた記号群、だけではなく、文字と一緒に用いられることもある。
e.g. ( ノﾟДﾟ)おはよう♥
ある文字を手に見立てていたりと、最近の顔文字はかなり複雑。
顔文字はSymmetryという特徴がある。

顔文字抽出にあたり、まずは候補領域を抽出する。
HMMを用いて、記号群を抜くような手法。Recallを重視し、Precisionは気にしない。
よくわからないがLinguisticとNon-linguisticでそれぞれ４つのパラメーターを使ったHMMモデルらしい。
あと独自のPCFGモデルを使ってNon-linguisticな候補を評価するらしい。
この生成モデルは、たとえばFACE→a EYES bなどといった形で、顔の構成を利用したモデルとなっている。
この評価値でランキングし、上位が顔文字？

Entroly as an Indicator of Context Boundaries -An Experiment Using a Web Search Engine-

Tanaka Kumiko
University of Tokyo

仮説は二つ。
連続する文字において連接確率の悪い文字が入った場合、そこが単語境界になりやすい。
連続する文字においてエントロピーが増加した場合、そこが単語境界になりやすい。

連接確率を学習させるので、Unsupervisedで出来る。

文字にすると説明が難しいが、要約すると、

1. 文字列がある
2. 単語区切りを適当に与える
3. 各Tokenと全体のエントロピーを図る
4. 単語区切りを適当に変える
5. 各Tokenと全体のエントロピーを図る
6. エントロピーが増加していればそっちのほうがよい

そんな感じなのだろうか。単語区切りの与え方はもっとなんかやっている気がするが、そこまで読み込めていない。
もっともな理論だが計算時間が問題になりそう。

実験結果を見る限りでは、なかなか精度がよさそう。

Solr3.6からSolr4.0に変更する際の注意点

注意点１：Velocityでプロパティファイルを指定している場合

v.propertiesでプロパティファイルを指定している場合、Solr3.6まではconf以下にファイルを設置する。Solr4.0からはvelocityディレクトリ内に設置する。
公式ではvelocityディレクトリはあくまでテンプレートを置くところだと説明があるが、4.0だとそれでは動かない。

注意点２：CommonsHttpSolrServerを使用している場合

Javaで開発している場合、Solrのライブラリを利用してプログラムから情報の登録と検索を行うケースがある。Solr3.6まででCommonsHttpSolrServerを使ってSolrに接続していた場合はSolr4.0からは変更する必要がある。色々なところで情報があるが、HttpSolrServerを使えばよい。
ハマリポイントとしては、必要なライブラリが増えること。solr-solrjライブラリとsolr-coreライブラリが必要だ。
以前はsolr-solrjのみで良かったし、実際にHttpSolrServerはこちらに入っているため、eclipse上ではエラーがでない。しかし、実行時にはsolr-coreライブラリも必要である。

2013/5/29 加筆
solr-solrj、slf4j-jdk14、jcl-over-slf4jの3つでよい。

Insertion, Deletion, or Substitution? Normalizing Text Messages without Pre-categorization nor Supervision

ACL2011
Fei Liu, Fuliang Weng, Bingqing Wang, Yang Liu

口語表現を文語表現に正規化する。
アノテーションデータを作らず、自動でwebから収集するらしい。

Edinburgh Twitter corpusには、400万語のout-of-vocabularyがあるらしい。
たとえば、"together"は"2gether","togetha","ththr"など。

従来手法
Noisy channel model
Noisy channel modelを使って、口語的表現から尤もらしい単語を見つける。
まず、口語的表現をカテゴライズする。
例えば、abbreviation、stylish variation?、prefix-clippingなど。
それから、カテゴリごとに学習する。

Hidden Markov Model
HMMでアノテーションデータを使って口語的表現を見つける。
※オーソドックスだと言える。

initial letter-to-ohine modelの拡張。

統計的機械翻訳

提案手法
acronyms（"bbl"->"be back later"）は扱わない。

口語的単語（OOV）と文語的単語の取得方法
OOVを含むツイートで、連続する語を"w1 w2 w3 OOV"か"OOV w1 w2 w3"でGoogle検索する。
OOVは一箇所でしか現れないってことはないので、本論文では６クエリ発行。
トップ32結果のスニペットを取得し、BOLD単語を収集。クエリで使った単語以外だけ、OOVの文語的単語候補として残す。
※Google依存！？！？
あとは、コーパス上で現れる部分文字列がけっこー一致する単語も候補とする。
あとは、OOVに簡単なルールを適用して、復元できないか試す。（例えば、"1"->"one", "won"; "2"->"to", "two"など）
あとは、InternetSlang.comから932語追加した。

その後、学習データの追加、削除処理を行う。
たとえば、(w1,w2)と(w2,w3)が学習データにあった場合、(w1,w3)を追加する。
あと、文語的表現として抽出した単語がCMU辞書になかった場合、学習データを削除する。
(headed, heading)みたいなペアを削除するため、いくつかヒューリスティックスを適用して削除する。

上記のプロセスを経て、最終的に62907ペアのトレーニングデータを作成した。

Automatic Letter-level Alignment
まず、文語的単語と口語的単語の最長一致部分文字列を求める。
それから文字のChunkを見つける処理を行う。

Step1. many-to-0 ("birthday" -> "bday")
Step2. 0-to-many ("sandwich" -> "sandwhich")
Step3. many-to-many ("someone" -> "some1")

まだまだNoisyな学習データがあるため、
・口語的表現には数字が入っていることとする
・ただし、文語的単語か口語的単語の3文字以上をchunkしたペアは除く

ここからletter-levelのalignmentを取る。
ただし、各alignmentのTop5だけルールとして採用する。
例えば、1-to-2だと、"ck","ey","ie","ou","wh"とそのalignmentペアだけ採用する。

上記の処理で、298160のletter-levelのalignmentルールができた。
"e"->"_" (have, hav)
"er"->"a" (another, anotha)

Sequence Labeling Model
コーパスはできたので、あとは文字列情報を基に、CRFで置換することを考える。
素性は、
文字列N-gram
音素N-gram
Syllable-level features (The English hyphenation dictionary使用)

実験
学習データは6150TweetにAmazon Mechanical Turkで3〜6人にアノテーションしてもらった結果を統合。選定して3802Tokenがテストデータ。
読み飛ばしたが、だいたい精度は60％くらい。
従来手法はJazzy Spell Checkerで47％くらい。
従来手法と提案手法を組み合わせると、68％くらい。

データの集め方は面白い。
ただ、どれほど学習データが正解なのかはわからなかった。
そこが大事だと思うので、そこを明確にしてほしい。

点予測による形態素解析

NL198 2010
中田陽介、NEUBIG Graham、森信介、河原達也

SVMベースの形態素解析
単語分割と品詞推定を別でやるところに特徴がある。

従来手法では、分を形態素列とみなし、形態素解析を単語分割と品詞推定を同時に行う系列ラベリングの問題として扱っている。
大きく、２つの系統に分けられ、ヒューリスティックスに基づく手法と、コーパスから規則などを学習する手法がある。

ヒューリスティックスに基づく手法はJUMANがある。
品詞間での連接コストや単語の生起コストを人手で与え、微妙なコスト調整が必要であるため、人的コストが高い。

コーパスに基づく手法は、連接コストや単語の生起コストをHMMのパラメータとみなす。
他にはCRFがある。
※最近調べた論文ではME (Maximum Entropy) なんかもそうだろう。

どちらにせよ、分野適用性が低く、標準文書（新聞）以外の文書については、解析精度が著しく低下することが知られている。

提案手法は点予測。

点予測による単語分割
単語分割の考え方は、
「現在注目している文字境界が分割ポイントになるか否か」
というものである。

素性は、

文字N-gram：窓幅"m"と長さ"n"を与えたとき、まず境界位置"i"の前後"i-m"から"i+m"までの部分文字列をとり、"n"以下の長さの全ての部分文字列をとる。

文字種N-gram：文字を文字種に変換した列であり、基本的な考え方は文字N-gramと一緒。文字種は、漢字（K）、カタカナ（k）、ひらがな（H）、ローマ字（R）、数字（N）、その他（O）の６つ。

単語辞書素性：位置iを始点とする単語、終点とする単語、内包する単語があるか否かのフラグと、その単語の長さ。

点予測による品詞推定
単語分割後に推定開始。
従来手法は、単語列を入力とする。
提案手法は、推定対象の単語と前後の文字列。
つまり、周囲の単語や品詞の推定結果を一切利用しない。

品詞の推定方法は4種類
1. 学習コーパスに品詞候補が複数出現する単語は、分類器で多値分類
2. 学習コーパスに品詞候補が1つの場合は、その品詞
3. 学習コーパスに品詞候補がないが辞書にはある場合、辞書の最初の品詞
4. 学習コーパスにも辞書にもない場合、名詞

素性は、
文字N-gram：単語境界のときとほぼ一緒
文字種N-gram：単語境界のときとほぼ一緒

単語ごとに多値分類
one v.s. rest

評価
線形SVM、"n=3"、"m=3"
精度はMecab-0.98とほぼ同程度

なかなか興味深い。
品詞推定方法に疑問はあるが、それでも精度はかなりよい。
学習コーパスがかなり充実しているのではないか？
分野適用性の柔軟さがあるという主張だが、そこまでではない印象。