ベイズ階層言語モデルによる教師なし形態素解析
NTTコミュニケーション科学基礎研究所
持橋大地

daichi@cslab.kecl.ntt.co.jp
IPSJ SIGNL 190
2009-3-25 (水)現在の形態素解析は完全か?
MeCabでの解析例• 前|スレ|1000|とりの|が|し|た|＼(^|o| ^)／• ち|ぃ|、|忠臣蔵|の|あら|すじ|おぼえ|た|！
• いづれ|の|御|時|に|か|、|女御|更衣|あ|また|さ|ぶら|ひ|た|ま|ひける|中|に|、|…
z 形態素解析の精度は「99%以上」と言われているが‥– 基本的に、新聞記事のみでの評価– 掲示板やブログの実際の文では、とても99%は無理– 音声認識、話し言葉の「正しい」教師データ？
– 未知の言語や古文には教師データが無い教師なし形態素解析
z 次々に現れる新語、新表現をいちいち、人手で辞書登録するのか？
z 教師あり学習では、「単語分割の基準」がヒューリ

スティックz 複雑な言語的知識はともかく、単語分割程度は教師なしで自動学習できるべきではないか？
– 情報理論的な「単語」の基準を与えたい

教師なし形態素解析.
• 教師データを使わない• 辞書を使わない • 自然言語一般の統計モデル

教師なし形態素解析: これまでの研究
z ヒューリスティックな基準– 連続する文字列の生起の検定が有意か– 前接/後続する文字分布のエントロピー (Jin, 田中2006)– MDLを用いた文字のチャンキング (松原 2007) etc..
‥ 統計的意味が曖昧/一部の情報しか使っていない
z 確率モデルに基づく統計的定式化– 文字列を単語分割した確率

ヒューリスティッ
クな基準も統計的に内包しているを最大化する、「言語として自然な」単語分割求める (永田 1996(教師あり); Goldwater+ 2006)

を

今回のアプローチ: 言語モデル確率z 直接、ベイズ単語nグラム-文字nグラム言語モデルの性能を最適化する単語分割

結果的に直感とも一致– 統計的意味が明確– 文字あたりパープレキシティ最小化

z NPYLM: Nested Pitman-Yor Language Model– 文字列から、隠れた単語分割を推定しつつ直接言語モデルを作成できる– Byproductとして、形態素解析が可能– 未知の言語を含む、あらゆる言語に適用可能– HPYLM(ベイズn-gram言語モデル)の拡張

準備: HPYLM n-gram
ユニグラム

“”

バイグラム

PY

Pitman-Yor過程 (PY)

PY

PY

“彼 が”

: 基底測度“が”PY: 確率分布から確率分布を生成

トライグラム“教会 が”

見る点在z 最高性能といわれるKneser-Neyスムージングは、HPYLMの近似 [Teh 2006]ÆHPYLM =「ベイズKneser-Ney nグラム」

HPYLM: 無限語彙モデル
PY

“”
PY

…

PY

: 基底測度z 基底測度は、単語の事前確率を表す– 語彙Vが有限なら、zは可算無限でもよい！Æ 無限語彙
– PYに従って、必要に応じて「単語」が生成される– 「単語」の確率は、文字n-gram=もう一つのHPYLM
z ME等で与えてもよい (が、再学習が面倒)

NPYLM: 文字-単語HPYLMの階層化
PY

“は”

“” PY
“会”

“”

“教”
“国”
“時”

PY

PY

PY

“が”

“彼 が” “教会 が”単語HPYLM“臨”
文字HPYLMz HPYLM-HPYLMの埋め込み言語モデル– つまり、階層Markovモデル
z 文字HPYLMのは, 文字数分の1 (日本語なら1/6879)

NPYLMの学習問題の定式化
z

データ:(文の集合)– 文:(文字列)– 隠れ変数:(のとき単語境界)z 隠れ変数の組み合わせは指数的に爆発

z 文がそれぞれ独立だと仮定すると、– 各文 の分割を、どうやって推定するか？
Æ ブロック化ギブスサンプリング、MCMC.

Gibbs Samplingとは
文2の分割確率密度p(X,Z)の等高線

文1の分割z データXの確率を最大化する隠れ変数Zをp(X,Z)からサンプリングする方法– p(z_i|X)からのサンプリングを充分繰り返すと、正しい解に収束

Blocked Gibbs Sampler for NPYLM
z 各文の単語分割を確率的にサンプリング

Æ言語モデル更新
Æ別の文をサンプリング...を繰り返す.
z アルゴリズム:
0. For s=s_1…s_X doparse_trivial(s,Θ).
文字列全体が一つの「単語」
1. For j = 1..M do
Θ:言語モデルFor s=randperm(s_1…s_X) doのパラメータ
言語モデルからwords(s)を削除
words(s) 〜 p(w|s,Θ) をサンプリング
言語モデルにwords(s)を追加して更新
done.

Gibbs Samplingと単語分割
1 神戸では異人館 街の 二十棟 が破損した 。
2 神戸 では 異人館 街の 二十棟 が破損した 。
10 神戸 では 異人館 街の 二十棟 が破損した 。
50 神戸 で は異人 館 街 の 二 十 棟 が 破損 し た 。
100 神戸 で は 異 人館 街 の 二 十 棟 が 破損 し た 。
200 神戸 で は 異人館 街 の 二 十 棟 が 破損 し た 。
• ギブスサンプリングを繰り返すごとに、単語分割とそれに基づく言語モデルを交互に改善していく。

動的計画法による推論
z words(s)〜p(w|s,Θ) : 文sの単語分割のサンプリング
z 確率的Forward-Backward (Viterbiだとすぐ局所解)– Forwardテーブルを用いる–: 文字列が、時刻tからk文字前までを単語として生成された確率
z それ以前の分割について周辺化…動的計画法で再帰t-kY
YY：

jt-k+1tXk

動的計画法によるデコード
EOS:
zz：

=文字列の最後のk文字が単語となる
文字列確率なので、EOSに接続する確率に従って後ろからkをサンプルが最後の単語だとわかったので、を使ってもう一つ前の単語をサンプル

z 以下文頭まで繰り返す

動的計画法による推論 (トライグラムの場合)
t-k-1-j-1-i

t-k-1-j-1 t-k-1

tz トライグラムの場合は、Forward 変数としてを用いる: 時刻tまでの文字列のk文字前までが単語、さらにそのj文字前までが単語である確率– 動的計画法により、を使って再帰
z プログラミングが超絶ややこしい ;_;(文字列は有限なので前が存在しないことがある)–

実験: 英語音素列データ
z Goldwater+(ACL 2006)のHDP単語バイグラムモデルとの比較
z 上で使われているCHILDES英語音素列データ– “WAtsDIs”Æ“WAts DIs” (What’s this) のように復元するタスク
z 結果: Precision, Recall, F値とも非常に大きく改善– 9,790文、平均9.8文字/文と少量のデータセット

計算時間の比較
10時間55分
700
600
500
計算時間 400300(分)
200
1000z

17分

HDPNPYLM

HDP(Goldwater+ ACL 2006): 学習データのすべての文字について1文字ずつサンプリング– モデルは単語2グラムのみ (文字モデルなし)

zNPYLM: 文毎に動的計画法により効率的にサンプリング– 単語3グラム-文字∞グラムの階層ベイズモデル

実験: 日本語＆中国語コーパス
z 京大コーパス＆SIGHAN Bakeoff 2005 中国語単語分割公開データセットz 京大コーパスバージョン4– 学習: 37,400文、評価: 1000文(ランダムに選択)z 中国語– 簡体中国語: MSRセット, 繁体中国語: CITYUセット– 学習: ランダム50,000文、評価: 同梱テストセット
z 学習データをそれぞれ2倍にした場合も同時に実験

京大コーパスの教師なし形態素解析結果
一方 、 村山富市 首相 の 周囲 に も 韓国 の 状況 や 立場 を 知 る 高官
は い ない 。
日産自動車 は 、 小型 乗用車 「 ブルーバード 」 の 新 モデル ・ Ｓ Ｖシリーズ ５ 車種 を １２ 日 から 発売 した 。
季刊 誌 で 、 今 月 三 十 日 発行 の 第一 号 は 「 車いすテニス 新世代チャンピオン 誕生 ― 斎田悟司 ジャパン カップ 松本 、 平和 カップ 広島連覇 」 「 フェスピック 北京大会 ― 日本 健闘 メダル 獲得 総数 ８ ８個 」 「 ジャパン パラリンピック ― 日本 の 頂点 を 目指 す 熱い 闘い 」など の 内容 。
整備新幹線 へ 投入 する 予算 が あ る の なら 、 在来 線 を 改良 するなどして、 高速 化 を 推進 し 輸送力増強 を 図 れ ば よい 。
国連 による 対 イラク 制裁解除 に 向け 、 関係 の深い 仏 に 一層 の 協力を 求め る の が 狙い とみられる 。
この 日 、 検査 され た の は ワシントン州 から 輸出 され た 「 レッドデリシャス 」 、 五 二 トン 。
ビタビアルゴリズムで効率的に計算可能(先行研究では不可能)

“正解”との一致率 (F値)z NPY(2),NPY(3)＝NPYLM 単語バイグラムorトライグラ

ム+文字∞グラム– NPY(＋)はNPY(3)でデータを2倍にしたもの
z 中国語: ZK08＝(Zhao&Kit 2008)での最高値と比べ、大きく改善– ZK08はヒューリスティックな手法をさらに混合したもの

“正解”データとの違い
一方 、 村山富市 首相 の 周囲 に も 韓国 の 状況 や 立場 を 知 る 高官
は い ない 。
季刊 誌 で 、 今 月 三 十 日 発行 の 第一 号 は 「 車いすテニス 新世代
チャンピオン 誕生 ― 斎田悟司 ジャパン カップ 松本 、 平和 カップ 広島連覇 」 「 フェスピック 北京大会 ― 日本 健闘 メダル 獲得 総数 ８ ８個 」 「 ジャパン パラリンピック ― 日本 の 頂点 を 目指 す 熱い 闘い 」
この 日 、 検査 され た の は ワシントン州 から 輸出 され た 「 レッドデリシャス 」 、 五 二 トン 。
「正解」データ

文法的判断

固有名詞を切りすぎない

一方 、 村山 富市 首相 の 周囲 に も 韓国 の 状況 や 立場 を 知る 高官は い ない 。
季刊 誌 で 、 今月 三十 日 発行 の 第 一 号 は 「 車 いす テニス 新 世代
チャンピオン 誕生 ― 斎田 悟司 ジャパンカップ 松本 、 平和 カップ 広島連覇 」 「 フェスピック 北京 大会 ― 日本 健闘 メダル 獲得 総数 ８８個 」 「 ジャパン パラリンピック ― 日本 の 頂点 を 目指す 熱い 闘い 」
この 日 、 検査 さ れた の は ワシントン 州 から 輸出 さ れた 「レッドデリシャス 」 、 五二 トン 。

「源氏物語」の教師なし形態素解析
しばしは夢かとのみたどられしを、やうやう思ひしづまるにしも、さむべき方なくたへがたきは、いかにすべきわざにかとも、問ひあはすべき
人だになきを、忍びては参りたまひなんや。若宮の、いとおぼつかなく、露けき中に過ぐしたまふも、心苦しう思さるるを、とく参りたまへ』な
ど、はかばかしうも、のたまはせやらず、むせかへらせたまひつつ、かつは人も心弱く見たてまつるらむと、思しつつまぬにしもあらぬ御気色の‥‥NPYLM

しばし は 夢 か と のみ たど られ し を 、 やうやう 思ひ しづま る にしも 、 さむ べき 方 な く たへ がた き は 、 いかに す べき わざ に かと も 、 問ひ あは す べき 人 だに な き を 、 忍びて は 参り たまひ なん や 。若 宮 の 、 いと おぼつかな く 、 露け き 中に 過ぐし たまふ も、 心 苦し う 思さる る を 、 とく 参り たまへ 』 など 、 はかばかしうも 、 のたまはせ やら ず 、 むせ かへ ら せ たまひ つつ 、 かつ は 人も心 弱 く 見 たてまつ る ら む と 、 思しつつ ま ぬ に しも あら ぬ 御気色 の‥‥‫‪アラビア語教師なし形態素解析‬‬‫)‪z Arabic Gigawords から40,000文 (Arabic AFP news‬‬‫‪.‬اﻟﻔﻠﺴﻄﻴﻨﻴﺒﺴﺒﺒﺘﻈﺎهﺮةﻻﻧﺼﺎرﺣﺮآﺔاﻟﻤﻘﺎوﻣﺔاﻻﺳﻼﻣﻴﺔﺣﻤﺎس‬‫واذاﺗﺤﻘﻘﺬﻟﻜﻔﺎﻧﻜﻴﺴﻠﻮﻓﺴﻜﻴﻴﻜﻮﻧﻘﺪﺣﺎزﺛﻼﺛﺠﻮاﺋﺰآﺒﺮىﻔﻴﺎﺑﺮزﺛﻼﺛﺔ‬‫‪.‬اﻟﻤﺤﻠﻴﺔواﻟﺪوﻟﻴﺔﻟﻠﺤﺼﻮﻟﻌﻠىﻠﻮازﻣﻬﻤﺎﻟﺼﺤﻴﺔ‬‫‪Google translate:‬‬‫‪“Filstinebsbptazahrplansarhrkpalmquaompalaslam‬‬‫‪+‬ﺑﻠﻬﻮ‪+‬ﻗﺎﺋﺪ‬‫‪+".‬ﻣﺎﻳﺴﻤىﺐ‪+‬اﻟﺴﻠﻄﺔاﻟﻔﻠﺴﻄﻴﻨﻴﺔ‪+‬ﻻﻳﺘﻤﺘﻌﺒﻠﻘﺐ‪+‬رﺋﻴﺲ‬‫”‪iphamas.‬‬‫اﻋﻠﻨﺘﺸﺮﻃﺔﺟﻨﻮﺑﺎﻓﺮﻳﻘﻴﺎاﻟﻴﻮﻣﺎﻻﺛﻨﻴﻨﺎﻧﻤﺎﻻﻳﻘﻞ‬‫وﻗﺎﻟﺘﺪاﻧﻴﻴﻠﺘﻮﻣﺴﻮﻧﺎﻟﺘﻴﻜﺘﺒﺘﺎﻟﺴﻴﻨﺎرﻳﻮ‪.‬وﻗﺪاﺳﺘﻐﺮﻗﺎﻋﺪادهﺨﻤﺴﺔاﻋﻮام‪".‬ﺗﺎرﻳﺨﻲ‬‫‪NPYLM‬‬‫‪ .‬اﻟﻔﻠﺴﻄﻴﻨﻲ ﺑﺴﺒﺐ ﺗﻈﺎهﺮة ل اﻧﺼﺎر ﺣﺮآﺔ اﻟﻤﻘﺎوﻣﺔ اﻻﺳﻼﻣﻴﺔ ﺣﻤﺎس‬‫و اذا ﺗﺤﻘﻖ ذﻟﻚ ف ان آﻴﺴﻠﻮﻓﺴﻜﻲ ﻳﻜﻮن ﻗﺪ ﺣﺎز ﺛﻼث ﺟﻮاﺋﺰ آﺒﺮىﻔﻴﺎﺑﺮز ﺛﻼﺛﺔ‬‫‪Google‬هﻢ اﻟﺼﺤﻴﺔ‬‫ﻟﻠﺤﺼﻮﻟﻌﻠﻰ ﻟﻮازم‬‫‪ .‬اﻟﻤﺤﻠﻴﺔو اﻟﺪوﻟﻴﺔ‬‫‪translate:‬‬‫‪supporters‬‬‫‪because‬‬‫‪ “Palestinian‬اﻟﻔﻠﺴﻄﻴﻨﻴﺔ‬‫ﻣﺎﻳﺴﻤﻰ ب ‪ +‬اﻟﺴﻠﻄﺔ‬‫‪ +of‬ﻗﺎﺋﺪ ‪+‬‬‫‪the‬هﻮ‬‫‪event‬ب ل‬‫رﺋﻴﺲ ‪+‬‬‫‪ + " .‬ﻻﻳﺘﻤﺘﻊ‪of‬ب ﻟﻘﺐ ‪+‬‬‫‪the Islamic‬‬‫‪Resistance‬‬‫”‪Hamas.‬‬‫اﻻﺛﻨﻴﻦ اﻧﻤﺎﻻﻳﻘﻞ‬‫ﺟﻨﻮﺑﺎﻓﺮﻳﻘﻲ ا اﻟﻴﻮم‬‫‪Movement,‬ﺷﺮﻃﺔ‬‫اﻋﻠﻦ ت‬‫وﻗﺪ اﺳﺘﻐﺮق اﻋﺪاد ﻩ ﺧﻤﺴﺔاﻋﻮام ‪ .‬و ﻗﺎل ت دان ﻳﻴﻞ ﺗﻮﻣﺴﻮن اﻟﺘﻲ " ﺗﺎرﻳﺨﻲ‬“Alice in Wonderland”の解析
first,shedreamedoflittlealiceherself,andonceagainthetinyhandswereclaspedup
onherknee,andthebrighteagereyeswerelookingupintohersshecouldhearthevery
tonesofhervoice,andseethatqueerlittletossofherheadtokeepbackthewanderingh
airthatwouldalwaysgetintohereyesandstillasshelistened,orseemedtolisten,thew
holeplacearoundherbecamealivethestrangecreaturesofherlittlesister'sdream.thelonggrassrustledatherfeetasthewhiterabbithurriedbythefrightenedmousesplashedhiswaythroughtheneighbouringpoolshecouldheartherattleoftheteacupsasthemarchhareandhisfriendssharedtheirneverendingmeal,andtheshrillvoiceofthequeen…
first, she dream ed of little alice herself ,and once again the tiny hand s wereclasped upon her knee ,and the bright eager eyes were looking up into hers -shecould hearthe very tone s of her voice , and see that queer little toss ofherhead to keep back the wandering hair that would always get into hereyes -and still as she listened , or seemed to listen , thewhole place a round her
became alive the strange creatures of her little sister 'sdream. thelong grassrustled ather feet as thewhitera bbit hurried by -- the frightened mouse splashed
his way through the neighbour ing pool -- shecould hearthe rattle ofthe tea cups
as the marchhare and his friends shared their never -endingme a l ,and the …

“形態素”の再定義

z “自然言語処理 悪魔の辞典”: 高林哲氏

– 「形態素が何であるかは永遠の謎」

教師あり学習では、
確かに謎z 今や謎ではない！

– “形態素”とは、文字列の生成確率を最大にするような情報理論的な単位として導くことができる.

まとめz ベイズ単語nグラム-文字nグラムを階層的に統合した言語モデルによる、教師なし形態素解析– 動的計画法＋MCMCによる効率的な学習
z あらゆる自然言語に適用できる– データに自動的に適応、「未知語」問題がない– 識別学習と違い、学習データをいくらでも増やせる– 話し言葉、ブログ、未知の言語、古文、…
z あらゆる言語の文字列から直接、「単語」を推定しながらKneser-Ney nグラムを学習する方法ともみなせる

展望と課題z 教師あり学習と異なり、学習データをいくらでも増やせる

学習の高速化、並列化– HDP-LDAのGibbsの並列化 (Welling+, NIPS 20072008) が適用可能
z 識別学習との融合による半教師あり学習– Loglinearの枠組で統合するにも、生成モデルが必要
z これまで、生成モデルが存在しなかった
z 提案法は、CRFのForward-Backwardの教師なし版のようなものz POS Tagging: CRF+HMM (鈴木,藤野+ 2007)で提案

おわりご清聴ありがとうございました。