Graham Neubig - ノンパラメトリックベイズ入門

ノンパラメトリックベイズ入門〜無限 HMM と教師なし単語分割〜

Graham Neubig
２０１０年１１月２９日

1Graham Neubig - ノンパラメトリックベイズ入門

発表の概要
●

●

前回はディリクレ過程、基底測度、ギブスサンプリングなどを紹介した
しかし、モデルはまだパラメトリック●●

パラメータの数は限られていた

今回は真のノンパラメトリックベイズ
無限 HMM （ HMM の状態数は無限）● 教師なし単語分割（可能な単語の数は無限）●

2

Graham Neubig - ノンパラメトリックベイズ入門

有限 HMM から無限 HMM へ

3

Graham Neubig - ノンパラメトリックベイズ入門

HMM のモデル（復習）●

品詞は隠れている状態● 状態の遷移確率は P T y i∣y i−1 = T , y , yi●i −1

各状態から単語を生成する●状態が与えられた場合の生成確率は P E  x i∣y i =E , y , xi

PT(1|0)0

PT(2|1)

PT(3|2)…

123134

5

行ごとに処理を行う

PE( 行 |1)i

PE( こと |2)PE( に |3)…

04Graham Neubig - ノンパラメトリックベイズ入門

ディリクレ過程●

前回の実装で利用した遷移確率を思い出してみよう
c  y i −1 y i ∗P base y i P  y i∣y i −1 =c  y i−1 ●ディリクレ過程を利用すると最尤推定で利用する頻度● 加算スムージングのような項●●

ここで鍵を握るのは基底測度 Pbase

5

Graham Neubig - ノンパラメトリックベイズ入門

基底測度の次元数
実装の課題で一様分布の基底測度を利用した品詞が 6 個の場合
確率0.2
0.10123456

品詞番号

品詞が 20 個の場合
0.060.04

確率

●

0.020

1 2 3 4 5 6 7 8 9 1011121314151617181920

品詞番号

6

Graham Neubig - ノンパラメトリックベイズ入門

さらに伸ばすと品詞が 100 万個の場合

0.02

1.50E-06

0.01

1.00E-06

0.010

確率

確率

品詞が 100 個の場合

5 13 21 29 37 45 53 61 69 77 85 93
1 9 17 25 33 41 49 57 65 73 81 89 97

品詞番号

●

5.00E-07
0.00E+00

130000 370000 610000 850000
10000 250000 490000 730000 970000

品詞番号

品詞の数を極大まで増やしていくと●それぞれの品詞の Pbase がゼロに近づく●

しかし、 Pbase 全体から品詞を生成する確率はそのまま

c  y i −1 y i ∗P base y i P  y i∣y i −1 =c  y i−1 

N=
品詞の数

Nlim ∑i =1N ∞

1=17NGraham Neubig - ノンパラメトリックベイズ入門

有限 HMM と無限 HMM●有限 HMM存在する品詞 yi を (yi-1 の後に ) 生成する確率c  y i −1 y i ∗P base y i P  y i∣y i −1 =c  y i−1 ●

無限 HMM
存在する品詞 yi を(yi-1 の後に ) 生成する確率
新しい品詞を(yi-1 の後に ) 生成する確率c  y i −1 y i P  y i∣y i −1 =c  y i −1 P  y i∣y i −1 =c  y i −1 8

Graham Neubig - ノンパラメトリックベイズ入門

例えば●c(yi-1=1 yi=1)=1 c(yi-1=1 yi=2)=1 としよう

可能な品詞が 2 個 (y1,y2) の場合
P  y i =1∣y i−1 =1=1∗1 /2
1∗1/2
P  y i =2∣y i −1 =1=22∗0P  y i =1,2 以外∣y i−1 =1=2可能な品詞が 20 個 (y1,y20) の場合
P  y i =1∣y i−1 =1=1∗1 /20
1∗1/20
P  y i =2∣y i −1 =1=2
2∗18/20P  y i =1,2 以外∣y i−1 =1=2

可能な品詞が∞個 (y1,y∞) の場合
P  y i =1∣y i−1 =1=1∗1 /∞1∗1/∞P  y i =2∣y i −1 =1=2
2∗1P  y i =1,2 以外∣y i−1 =1=2

9

Graham Neubig - ノンパラメトリックベイズ入門

無限とは？
●

●

ここではなぜ「無限の可能なタグ」にするか
理論：タグが多くても、まだまだ見たことがない珍しい言語現象はあるかもしれない「待ったをかける」● 「紫のかゞやく花と日の光思ひあはざることわりもなし」●●

実用：コーパスが大きくなればなるほどたくさんのクラスが欲しい10

Graham Neubig - ノンパラメトリックベイズ入門

サンプリングアルゴリズム
SampleTag(yi)c(yi-1 yi)--; c(yi yi+1)--; c(yi→xi)--

今のタグのカウントを削除する存在するタグの確率を計算（ディリクレ過程の式で ,p.8 ）for each tag in S ( 品詞の集合 )p[tag]=PE(tag|yi-1)*PE(yi+1|tag)*PT(xi|tag)
p[|S|+1]=PE(new|yi-1)*PE(yi+1|new)*PT(xi|new)yi = SampleOne(p)c(yi-1 yi)++; c(yi yi+1)++; c(yi→xi)++

新しいタグの確率を計算

yi の値を選ぶ
そのタグを追加する
11

Graham Neubig - ノンパラメトリックベイズ入門

実装のいろいろ●普通は 0 頻度のクラスは残る→クラス数が上がる一方●

新しいクラスを作る時に 0 頻度のクラス番号を使い回す

c(y1)=5 c(y2)=0 c(y3)=1●●

単純： c(y1)=5 c(y2)=0 c(y3)=1 c(y4)=1
賢い： c(y1)=5 c(y2)=1 c(y3)=1c(y1)=0 になると、 y1 が復活する確率が 0 になる

このモデルだと新しい品詞に弱い
新しい品詞は１つの品詞の後にしか来ない● 階層モデルで解決
●

遷移確率
品詞確率

P T y i∣y i−1 =DP  ,P T  y i P T y i =DP  , P base  y i 

12Graham Neubig - ノンパラメトリックベイズ入門

教師なし単語分割のモデル

13

Graham Neubig - ノンパラメトリックベイズ入門

言語モデルを使った教師あり単語分割●●

日本語や中国語などは明白な区切りがなくても単語という概念はある→単語分割は必要
言語モデルを使った単語分割はできる
分割したい文字列 x からなるすべての単語列 w は分割
候補● 候補の確率は言語モデル確率に比例● 確率の最も高い候補を正しい分割●x= ことば言語モデル GP(w= ことば )P(w= こ とば )P(w= こと ば )P(w= こ と ば )14

Graham Neubig - ノンパラメトリックベイズ入門

1-gram 言語モデル●

一番簡単な言語モデルは 1-gram●

文のそれぞれの単語は独立に生成P w =∏w ∈w P w i i●

1-gram 確率にディリクレ過程の事前確率をかけるP w i =●c w i  P base w i ∑i c w i 

2-gram や 3-gram を利用すると精度が上がる ( 上級編 )15

Graham Neubig - ノンパラメトリックベイズ入門

単語分割の基底測度●●

単語に対する基底測度は単語になり得る全ての文字列に確率を与えなければならない
よく使われているモデルは：●

まず単語の長さ J を確率的に選ぶ
P len J ●

それぞれの J 文字を文字の確率分布から独立に選ぶJ∏ j =1 P char x j ●組み合わせると、どの単語でも少しの確率が振られる

w i =x 1  x J

JP base w i =P len J  ∏ j =1 P char  x j 

16Graham Neubig - ノンパラメトリックベイズ入門

長さの確率
●

長さの確率分布として指数分布とポアソン分布
J

1 −
指数分布： P len J = e

●

−

J e
ポアソン分布： P len J =
J!

両方は「平均単語長 λ 」のパラメータがある17

Graham Neubig - ノンパラメトリックベイズ入門

文字 1-gram の分布●

文字 1-gram は予め最尤推定で計算しても良い
P char  x j =●●cx j∑ j c  x j 

未知の文字が扱えなくなるが、とりあえず学習コーパ
スを分割したいので、気にしない
文字 n-gram を利用したり、カタカナ / 漢字 / 数字の違いを利用するモデルもある（上級編、持橋 + ）18Graham Neubig - ノンパラメトリックベイズ入門

教師なし単語分割のサンプリング

19

Graham Neubig - ノンパラメトリックベイズ入門

単語分割の表現方法●

分割された文を表す方法として
x1 x2 x3 x4 x5 x6
●

文字列ｘ：

彼のことばで（観測変数）

y1 y2 y3 y4 y5●●

単語境界タグ列 y ： 1 1 0 0 1（非観測変数）yi が 1 であれば、 xi と xi+1 の間に単語境界がある
彼のことばで
1 1 0 0 1

彼のことばで20

Graham Neubig - ノンパラメトリックベイズ入門

サンプリングの対象●

サンプリングする変数は１個の単語境界タグ yi の値
彼 の ことば で
11 0 0 1

今回の対象 :y4●

1-gram モデルで影響されるのはその単語境界に隣接する単語だけ（「こと」と「ば」または「ことば」）
P( 彼 ) * P( の ) *P( ことば )* P( で )P( 彼 ) * P( の ) * P( こと ) * P( ば ) * P( で )21Graham Neubig - ノンパラメトリックベイズ入門

サンプリングの過程●

まず、単語境界に隣接する単語の頻度から 1 を引くc( ことば )--●orc( こと )--c( ば )--コーパスの総単語数を記録（保持）しておく
W =∑ i c w i 

22Graham Neubig - ノンパラメトリックベイズ入門

サンプリングの過程●

単語境界タグが 0 の場合の確率：１単語c  ことば P base  ことば P  y i =0∝P  ことば =W ●

単語境界タグが 1 の場合の確率： 2 単語
P  y i =1∝ P  こと P  ば c  こと P base  こと P  こと =W c  ば  P base  ば P  ば =W 1「こと」が追加されるため W+123

Graham Neubig - ノンパラメトリックベイズ入門

なぜ１を追加●ディリクレ過程で単語が生成されるたびに確率が変わる
これc  これ  P base  これ  0 P base これ P  これ ==W 0c( これ )++ W++はc  は  P base  は  0 P base は P  は ==W 1
c( は )++ W++

これP  これ =c  これ  P base  これ  1 P base  これ =W 2
c( これ )++ W++でc  で  P base  で  0 P base で P  で ==W 
3
c( で )++ W++

24

Graham Neubig - ノンパラメトリックベイズ入門

サンプリングの過程●

P(yi=0) と P(yi=1) に従って、 yi の新しい値をサンプリングする
P  y i =0=●P ことば P  ことば P こと  P  ば「こと」と「ば」、または「ことば」の頻度に１を足す
c( ことば )++orc( こと )++c( ば )++25

Graham Neubig - ノンパラメトリックベイズ入門

実装のいろいろ●初期化はどうする？
全部の文を１つの単語と初期化する● ランダムに初期化する●●●前向き後ろ向きアルゴリズムで１文ごとにサンプリングすることもできる ( 上級編：持橋 + ）タイプ（同じ単語になる境界）ごとにサンプリングもできる（上級編： Liang+ “Type based MCMC” ）26

Graham Neubig - ノンパラメトリックベイズ入門

課題

27

Graham Neubig - ノンパラメトリックベイズ入門

課題●

教師なし単語分割を実装すること●

前回の課題で利用したデータで●α の設定は実験的に決める●

単語分割精度で評価（スクリプトは送っておきます）●

単語列のマッチングをかけて、 F 値で評価

28

Graham Neubig - ノンパラメトリックベイズ入門

さらに詳しく知りたい人に●

ノンパラメトリックベイズの紹介
Jordan “Dirichlet Processes, Chinese Restaurant
Processes, and all that.” ( ビデオ )持橋 “最近のベイズ理論の進展と応用 (III) ノンパラメトリックベイズ”●

ノンパラメトリックベイズを使った言語モデル
Teh “A Bayesian Interpretation of Interpolated Kneser Ney”●

ノンパラメトリックベイズを使った単語分割
Goldwater+ “A Bayesian framework for word
segmentation: exploring the effects of context”
持橋 + “ ベイズ階層言語モデルによる教師なし形態素解析”
29