Introduction to Hierarchical Pitman-Yor Processes
Daichi Mochihashi
ATR SLCdaichi.mochihashi@atr.jp“Ultraconservative” SVM 2006
Aug 5, 2006
NAIST

Introduction to Hierarchical Pitman-Yor Processes – p.1/22

Overview• Pitman-Yor processes= Two-parameter Poisson-Dirichlet process PD(d, θ)(Pitman and Yor 1997)◦ ディリクレ過程 (有限次元の場合はディリクレ分布) の拡張• n-gram 分布の階層的な生成モデル

0-gramPrior: (n − 1) gramPD(dn , θn )1-gramPosterior: (n) gram

2-gram3-gramIntroduction to Hierarchical Pitman-Yor Processes – p.2/22

Background• 現状のトピックモデル (LDA,DM など) は unigram のみ◦ Trigram とのアドホックな混合が必要になる.
− 計算量も大きい◦ 「トピックに特有な bigram, trigram, ...」が存在− “mixture of” → { Gaussians, cultures, flour }− “everyone” → { shall (法律), ’s (口語) }− 適切にできれば, NE recognition の代わりになる• n-gram の, きちんとした確率モデルが必要◦ 他のモデルに部品として組み込める− 例. トピックモデル / 統計翻訳
◦ これまでの n-gram は, カウントの smoothing (= 確率モデル)◦ 無限語彙を自然に扱えるモデルが必要− 自然言語の語彙は本当は可算無限

Introduction to Hierarchical Pitman-Yor Processes – p.3/22

Pitman-Yor and DP• HPY (Hierarchical Pitman-Yor process, Teh 2006)· · · HDP (Hierarchical Dirichlet process, Teh & Jordan 2004)の拡張• Pitman-Yor process · · · Dirichlet Process (DP) の拡張• 以下, この順番で:

1. Dirichlet process とは?
2. Pitman-Yor process とは?
3. 階層 Pitman-Yor process とは?
4. Gibbs Sampling によるパラメータ推定

Introduction to Hierarchical Pitman-Yor Processes – p.4/22

Dirichlet process (DP) (Ferguson 1973) とは?
• 自然言語処理の文脈では (=1 次元の場合),無限次元の離散分布を生成する確率モデルのこと.
• G ∼ DP(α, G0 ) とすると, 基になる連続分布 (測度) G0 に対して
G_0G

G はそれと少し異なる, 無限次元の離散分布.
◦ concentration パラメータ α によって, G の G0 との違いを調整 (α = 0 とすると完全に一致)◦ 無数の G がサンプルできるが, その期待値は E[G] = G0 .
Introduction to Hierarchical Pitman-Yor Processes – p.5/22

Stick-breaking process• どうやって具体的に G ∼ DP(α, G0 ) をサンプルすればいい?

→ Stick-breaking process (Sethuraman 1994)• 長さ 1 (確率の総和) の棒を, 左から切っていく

1. まず, β1 ∼ Be(1, α) の点で棒を分割◦ 左の切れ端 π1 : 長さ β1
2. 残った方を, β2 ∼ Be(1, α) でまた分割◦ 左の切れ端 π2 : 長さ β2 (1 − β1 )3. 残った方を, β3 ∼ Be(1, α) でまた分割◦ 左の切れ端 π3 : 長さ β3 (1 − β2 )(1 − β1 )4. …

1 − β1π1

1 − β2π2π31 − β3···Introduction to Hierarchical Pitman-Yor Processes – p.6/22

Stick-breaking process (2)• 一般に, G ∼ DP(α, G0 ) は

πn = βnn−1(1 − βi )(n = 1, . . . , ∞)(1)i=1βi ∼ Be(1, α)のように棒を分割して,G=(2)∞πk δ(θk )

(3)

k=1

θk ∼ G0(4)のような δ 関数の無限和で表せる.
◦ 自然言語のような離散分布の場合は, G0 は自然数上の (一様)分布.

Introduction to Hierarchical Pitman-Yor Processes – p.7/22

Polya urn scheme of DP• G ∼ DP(α, G0 ) からのサンプル x = x1 , x2 , . . . , xn が得られている時, 次の x は何になるか?
p(x|x, DP(α, G0 )) = p(x|G)p(G|x, DP(α, G0 ))dGKαnk
δ(θk ) +G0 .
=n+αn+α(5)

(6)

k=1

◦ θk (k = 1, . . . , K ) : x1 , . . . , xn の中の異なり成分◦ nk (k = 1, . . . , K ) : その頻度
• ベイズ的なスムージングが得られる

α◦ 頻度 0 のカテゴリの確率は,
G0 .
n+α

Introduction to Hierarchical Pitman-Yor Processes – p.8/22

Polya urn scheme of DP (2)• これは, 次の MacKay の Dirichlet smoothing とも本質的に同じ(SVM 2004)

njαp̂(i|j) +ᾱip(wi |wj ) =nj + αnj + αni|j + αi=i (ni|j + αi )

(7)

(8)

• DM (山本 2003, Sjölander et al. 1996) とも同じ

n(v|h) + αmvp(v|h) =Cm v (n(v|h) + αmv )m

Γ(αm )  Γ(n(v|h) + αmv )C m ∝ λm
Γ(αm + h) v
Γ(αmv )

(9)

(10)

Introduction to Hierarchical Pitman-Yor Processes – p.9/22

Polya urn scheme of DP (3)• 何がいけないか?
◦ 頻度 0 のとき,p(wi |wj ) = αii (ni|j + αi )◦ 頻度 1 のとき,1 + αii (ni|j + αi )p(wi |wj ) = (11)(12)− 通常, α  1 (αi = 0.001 くらい)− 3 + αi , 2 + αi , 1 + αi ⇐⇒ αi … ものすごい差.
• 頻度 (1, 2, 3, . . .) 自体をそのまま信用せず, ダンピングする必要があるのでは?
→ ◦ Kneser-Ney smoothing (Kneser and Ney 1995)◦ Pitman-Yor processes (Teh 2006, Pitman and Yor 1997).

Introduction to Hierarchical Pitman-Yor Processes – p.10/22Pitman-Yor process PD(d, θ)• Stick-breaking process:◦ For k = 1, 2, . . . , ∞,βk ∼ Be(1 − d, θ + kd).

(13)

• k が増えるにつれ, 分割の平均位置が左に移動◦ より多くのコンポーネント (単語) に確率が割り振られる(heavy tail)• Polya urn representationp(x|x, PD(d, θ)) =tnk − dk=1n+θ

δ(θk ) +θ + dtG0n+θ

(14)◦ 前半で, カウントが常に d だけディスカウントされる◦ 後半のスムージングは DP と同じ

Introduction to Hierarchical Pitman-Yor Processes – p.11/22

Hierarchical Pitman-Yor Processes• Base measure G0 が, また階層的に PD(d , θ  ) に従う◦ 3-gram : G3 ∼ PD(d3 , θ3 |G2 )◦ 2-gram : G2 ∼ PD(d2 , θ2 |G1 )◦ 1-gram : G1 ∼ PD(d1 , θ1 |G0 )◦ 0-gram : G0 ∼ uniform. (p(v) = 1/V )0-gramPrior: (n − 1) gramPD(dn , θn )1-gramPosterior: (n) gram

2-gram3-gramIntroduction to Hierarchical Pitman-Yor Processes – p.12/22

Polya Urn scheme of HPY
p(x|x, HPY(d, θ)) =tnk − dk=1

θ + dtδ(θk ) +Gn−1c+θ
c+θ

(15)

• n-gram 分布を, (n−1)-gram 分布から生成する• Gn−1 は離散 · · · 新しい θk+1 は他の θ と同じになる可能性◦ 単語 w が Gn−1 から引かれた異なり数を t(w) とすると,

上式はn(w) − d·t(w) θ + dt+
Gn−1 (w)p(x = w|x, HPY(d, θ)) =c+θ
c+θ

(16)

• これは, 言語モデルで最高性能といわれる Kneser-Ney スムージ

ング (Kneser and Ney 1995)

n(w|h) − d(n(w|h))+ γ(h)p(w)p(w|h) =n(h)(17)

で, t(w) を常に 1 とした場合に相当する.
Introduction to Hierarchical Pitman-Yor Processes – p.13/22

Chinese Restaurant Process of HPY• 客が, 無限個のテーブルがあるレストランに入って食事をする◦ 同じテーブルに座った人は, 同じ料理を食べる• どのテーブルに座るか?
◦ 各テーブル k の客数 ck − d に比例した確率で選ぶ [人気順]◦ テーブルの総数 t に対して, θ + dt に比例した確率で新しいテーブルを選ぶ◦ 新しいテーブルでは新しい料理を頼む• レストラン = n-gram 文脈, 料理 = 単語, 客 = 頻度
◦ ある n-gram 文脈では, Pitman-Yor process に従って料理 (単語)の頻度が分布する◦ 新しいテーブルでの料理はどうやって選ぶ?

Introduction to Hierarchical Pitman-Yor Processes – p.14/22

Chinese Restaurant Process of HPY (2)• 新しいテーブルの料理は何にする?
◦ 親レストランに代理の客を行かせて, そこで同様に座って出た料理と同じにする◦ 親レストランでも新しいテーブルになったら, さらに親レストランに代理の客を行かせる• 親レストラン =(n-1)-gram 文脈◦ ある文脈で, 同じ単語が複数のテーブルでサーブされている可能性がある− 親レストランに行ったとき, 同じ料理を出される可能性が高い [人気順]− t(w) に相当する• これ以上親レストランがない =0-gram 文脈◦ 仕方がないので, 厨房が新しく考える (Base measure)◦ 新しく作った単語の確率は, 文字 HMM などで計算

Introduction to Hierarchical Pitman-Yor Processes – p.15/22

Inference of seating arrangementsp(s) =

G0 (w)c0w··

wu· )
tu·
 (θ|u| )d(t|u|u(θ|u|)(cu·· )(1 − d|u| )(cuwk −1)

(18)

w k=1

• cuwk : Frequency of word w at table k in the n-gram context u• tuw : Number of tables with word w in the n-gram context u• Gibbs sampling:

For t = 1 . . . T ,For w ∈ randperm({all counts in the model}),
1. Remove a customer w from the restaurant.
2. Add w to the restaurant at a random table following
the Pitman-Yor process.
◦ When a new table is selected, choose a dish bysending a proxy customer to the parent restaurant.
Introduction to Hierarchical Pitman-Yor Processes – p.16/22

Inference of hyperparameters• Through Data augmentation (adding auxiliary variables xu , yui ,and zuwkj ), 1 θ|u|u·−1 
cu·· −2 dx tx(1−x)uyui
0 up(s) =G0 (w)c0w··
θ|u|(d|u| i)1−yuiΓ(cu·· − 1)w
ui=1 yuictuwk−1u· (j − 1)zuwkj (1 − d|u| )1−zuwkj(19)
w k=1 j=1 zuwkj• Therefore, posterior for hyperparameters aretu· cuwk−1u· −1 t dn ∼ Be(1 +(1 − yui ), 1 +(1 − zuwkj )),|u|=n i=1u· −1 tθn ∼ Ga(αn +|u|=n i=1|u|=n w k=1 j=1

yui , βn +log xu ).

(20)
(21)

|u|=n

Introduction to Hierarchical Pitman-Yor Processes – p.17/22

Implementation

struct ngram {/* c_uxx */ngram *parent;
ngram **children;
restaurant **words;
int nchildren;
int nwords;
int ncounts;
int ntables;
int level;
int id;};struct restaurant {/* c_uwx */int id;int ntables;
int maxtables;
int ncounts;
int *tables;
ngram *context;};

Introduction to Hierarchical Pitman-Yor Processes – p.18/22

Small Experiments• “Austen” language modeling in FSNLP◦ http://nlp.stanford.edu/fsnlp/◦ 6. “Statistical inference: n-gram models over sparse data”

p.191–• Modified Kneser-Ney smoothing, SRI LM Toolkit% ngram -order 3 -lm austen3.arpa -ppl austen.test.dat
0 zeroprobs, logprob= -186076 ppl= 135.906 ppl1= 167.651• HPY Language model, Gibbs% hpylm -hhpylm, Hierarchical Pitman-Yor language model.
$Id: hpylm.c,v 1.17 2007/03/19 09:11:05 dmochiha Exp $usage: hpylm -n [order] -N [iteration] train model% hpylm -n 3 -N 50 austen.dat austen.n3
Gibbs 50 : iteration 725242 / 725242.. ETA: 0:00:00 (6 sec/sweep)
done.
% hpyppl -N 50 austen.n3 austen.test.dat
loading language model from austen.n3 ..
Gibbs 50 : iteration 725242 / 725242.. PPL = 130.936
Introduction to Hierarchical Pitman-Yor Processes – p.19/22
perplexity = 130.936

Seatings integrated out• cuwk 人の客 (単語) が tuw 個のテーブルに座る場合の数の総和を考えると,p(s) =

G0 (w)c0w··u· ) (θ|u| )d(t|u|wu(θ|u|)(cu·· )sd|u| (cuw· , tuw )

(22)

w

◦ テーブルごとの cuwk が必要なく, その総和 cuw だけですむ◦ sd (c, t) は type(−1, −d, 0) の一般化 Stirling 数で1. sd (0, 0) = sd (1, 1) = 1
2. sd (c, 0) = sd (0, t) = 0
3. sd (c, t) = sd (c − 1, t − 1) + (c − 1 − dt)sd (c − 1, t)(0 < t ≤ c)をみたす.

• Polya 分布との類似に注意p(x|α) =Γ( k αk )  Γ(nk + αk )p(x|p)p(p|α)dp = Γ( k αk + nk )Γ(αk )
k(23)Introduction to Hierarchical Pitman-Yor Processes – p.20/22

Prediction and Inference with seatings integrated out• モデル全体がハイパーパラメータおよびカウント cuw , tuw の推定値で記述できる時,

p(w|u) =

p(w, cuw , tuw |u)(24)

p(w|u, cuw , tuw )p(tuw |u, cuw )p(cuw |u)(25)

cuw tuw=
cuw tuw=

cuw

p(cuw |u)

p(w|u, cuw , tuw )p(tuw |u, cuw ).

(26)

tuw

• p(cuw |u) 及び p(tuw |u, cuw ) を推定 → LBP で行けるらしい◦ 実際には, p(cuw , tuw |u) の同時分布が必要 (行列)◦ カウント cuw が大きいとき, パラメータ量膨大− Gibbs では, (cuwk , tuw ) の確率の高い組だけを確定的にサンプリングして取り出している.
Introduction to Hierarchical Pitman-Yor Processes – p.21/22

Future Works• Topic modeling with HPY n-gram.
◦ How to combine HPY n-gram with EM? (HMM)◦ 計算量の多い sd (c, t) の近似• Mittag-Leffler distribution, Gamma process, Lévy measure, ..など, 知らないことが沢山• Dependent Dirichlet process (DDP) (Griffin & Steel 2004)◦ レストランで「客がしばらくすると席を立つ」ことを許す.

Introduction to Hierarchical Pitman-Yor Processes – p.22/22