Latent Dirichlet kernel &Bayesian kernels
Daichi Mochihashi

daichi.mochihashi@atr.jp
ATR SLT, Department 2 (SLR)Über SVM 2004
Aug 3, 2004, NAIST

Latent Dirichlet kernel & Bayesian kernels – p.1/16

Introduction• 確率分布の間のカーネル (↔ データ点間のカーネル)

K(p(θ|x), p(θ|y)) ↔ K(x, y)• 適切な prior を設定することで，事前知識を自然に取りこめる• “Latent Dirichlet kernel” for documents◦ 最尤推定の罠を回避することができる◦ 文書の「長さ」を (正規化することなく) 自然にカーネルに反映できる.

Latent Dirichlet kernel & Bayesian kernels – p.2/16

Kernel for probability distributions• Probability Product Kernel (PPK):Kβ (p, p ) =p(x)β p (x)β dx(1)◦ パラメータ: β (意味は後で説明)◦ Positive semidefinite.

• β = 1 : Expected Likelihood KernelK(p, p ) =p(x)p (x)dx(2)= p(x)p (x) = p (x)p(x)(3)◦ 互いに見た，相手の確率分布の期待値．

Latent Dirichlet kernel & Bayesian kernels – p.3/16

Bhattacharyya kernel• β = 1/2 : Bhattacharyya kernel (Bhattacharyya 1943,Kondor & Jebara 2003)
 
K(p, p ) =p(x) p (x)dx(4)◦ K(p, p ) ≡ 1.
• Hellinger 距離: bound of KL divergence 2
1H(p, p ) =p(x) − p (x) dx2
• H(p, p ) = 2 − 2K(p, p ) .

(5)

Latent Dirichlet kernel & Bayesian kernels – p.4/16

Example: Gaussian PPK• D 次元の 2 つの Gaussian の PPK:
1−2βD2 β
 −2|Σ0 | |Σ||Σ |×12K(N (µ, Σ), N (µ , Σ )) = (2π)

β T −11 TT −1 exp − (µ Σ µ − µ Σ µ ) + µ0 Σ0 µ022(6)• 特に，共分散行列が diagonal: σ 2 I であれば，2

22 −D2K(N (µ, σ I), N (µ , σ I)) = (4πσ ) 22exp −|µ − µ | /4σ

2 −D22= (4πσ ) 2 exp −|x̄ − x̄ | /4σ(µ = x̄, µ= x̄ )

(7)

∴ RBF kernel が導かれる．
Latent Dirichlet kernel & Bayesian kernels – p.5/16

Example 2 : Multinomial PPK• 多項分布 θ̂ = (θ1 , θ2 , . . . , θK ), ) の PPK は，X 語の 2 つの文書θˆ = (θ1 , θ2 , . . . , θKに対して，K(p(x|θ̂), p(x|θˆ )) =KX
 12(θi θi )

.

(8)

i=1

◦ = homogeneous polynomial kernel, degree X/2.
◦ 文書の長さが同じ X 語でないと比べられない(x で積分 (和) がとれないため.)

Latent Dirichlet kernel & Bayesian kernels – p.6/16

EF as a Gibbs distribution• Exponential Familyp(x|θ) ∝ exp(θ · φ(x) + a(x))
1∝
exp(H(x, θ)).
Zθ(θ : 自然パラメータ) (9)(H(x, θ) = θ · φ(x) + a(x))∴ p(x|θ)β ∝ exp(β(θ · φ(x) + a(x)))= exp(βH(x, θ)).
• ゆえに，PPK(β )Kβ (p, p ) =



(10)

1(β = )
T(11){p(x|θ)β }{p (x|θ)β }dx(12)は，温度 T = 1/β のもとでの Expected likelihood kernel?
(quasi Heat Kernel.)

Latent Dirichlet kernel & Bayesian kernels – p.7/16

PLSI for two documents• 文書 d = w があったとき，トピック t = t1 . . . tK に対して， p(t|w, d) ∝ p(w|t)p(t|d)
p(w|t) ∝ d n(w, d)p(t|w, d)p(t|d) ∝ w n(w, d)p(t|w, d)(13)

以下，λ = {p(t|d)} とおく．
• 文書 d, d の affinity = トピック混合比 λ, λ の近さ◦ KL, Jensen-Shannon◦ Information diffusion kernel• 問題: λ は点推定

◦ オーバーフィット (ex. とても短い文書)◦ 長い文書も短い文書も一点 λ で代表?

↓p(λ|d), p(λ|d ) の比較. (Latent Dirichlet kernel)
Latent Dirichlet kernel & Bayesian kernels – p.8/16

Latent Dirichlet kernel (1)• p(λ|d) = Dir(λ|α) (Dirichlet 分布)α∗ = argmax
α= argmaxαp(w|λ)p(λ|α)dλ |d|(14)p(wi |zk )λk p(λ|α)dλ.

(15)

i=1 k• この α は単純な EM アルゴリズムでは求まらない.

(隠れ変数が階層化されているため)Latent Dirichlet kernel & Bayesian kernels – p.9/16

Latent Dirichlet kernel (2)• Variational Bayes EM algorithm (Attias 1999)

⇐⇒q(Z) ∝ explog p(Y, Z|θ)q(θ)q(θ) ∝ explog p(Y, Z|θ)q(Z) · p(θ)(VB-Estep)(VB-Mstep)(16)

q(zit = 1|d) ∝ p(wi |t) exp(Ψ(α0 + nt ))K α0 +nt −1(17)q(λ|d)∝(⇔ α = α0 + nt )t=1 λt|d|where nt =q(zit = 1|d)

(18)

i=1

• (17) 式を iterate することで，文書 d に対するハイパーパラ

メータ α が得られる．

Latent Dirichlet kernel & Bayesian kernels – p.10/16

Latent Dirichlet kernel (3)• 文書 d, d について，それを生成したトピックの Dirichlet 分布のハイパーパラメータ α, β が得られたので，Bhattacharyyakernel の場合，
 
K(d, d ) =p(λ|α) p(λ|β)dλ(19)
 =


Γ(α )
 0i Γ(αi )

1/2
i


α /2−1/2
λi i·Γ(β ) 0i Γ(βi )1/2

β /2−1/2

λi ii(20)1/2 1Γ(Γ(α0 )Γ(β0 )i2 {αi + βi })=· 1.
Γ( 2 i {αi + βi })i Γ(αi )Γ(βi )(21)

Latent Dirichlet kernel & Bayesian kernels – p.11/16dλLatent Dirichlet kernel (4)• β = 1/2 (Bhattacharyya) でなくともよい (β = 1, あるいは最適な「温度」は実験的に決まる)• 文書の「長さ」を自然にカーネルとして取りこむことが可能◦ 二つの Dirichlet 分布の重なり◦ 短い文書はなだらかな推定，長い文書は鋭いピーク(のこともある)Latent Dirichlet kernel & Bayesian kernels – p.12/16

Is LDA perfect?
• No.
• (事前の)LDA によって決まった，topic simplex の内部しか表現できない．(山本 2003/SLP48)◦ 極端な偏りのある文書 (simplex から外れる)• このことの原因: p(w|zt ) が点推定であること.
◦ p(w|zt ) を Dirichlet 分布とする◦ Dirichlet mixture of Dirichlet mixture?

Latent Dirichlet kernel & Bayesian kernels – p.13/16

Kernel machine ≡ SVM• Herbrich & Graepel (1999): “Bayesian Learning in

Reproducing Kernel Hilbert Spaces”◦ 最初から二値分類 (SVM) を前提にしている⇓
萎え萎え．orz• NLP でのカーネルは，出口がみんな SVM• 分類問題以外での NLP でのカーネルの使い道は?
◦ 詳しい方教えて下さい．
• Bayes Point Machine についてはもっと勉強します‥．

Latent Dirichlet kernel & Bayesian kernels – p.14/16

おまけ: SVMsequel• http://www.isi.edu/˜hdaume/SVMsequel/• 常識??
• Linear, Polynomial, RBF, . . ., などの普通のカーネルの他に，◦ Tree kernel◦ String kernel (DP (O(nm))/Suffix Tree (O(n + m)))◦ Information diffusion kernel◦ Gram 行列直接指定などが実装されている．
• カーネルを自分で追加可能• Ocaml で書かれている (バイナリあり)◦ Ocaml コンパイラが必要な人は，

cl:˜daiti-m/arch/linux/bin/ にパスを通して下さい．
Latent Dirichlet kernel & Bayesian kernels – p.15/16

SVMsequel サンプル
dot.ml より:

let denseKernel k x y =let xdoty = dotValue x y inmatch k withLinearKernel -> xdoty| PolynomialKernel (a,b,d) -> (a +. b *. xdoty) ** d| RbfKernel g -> exp (g *. (2. *. xdoty -. dotValue x x | SigKernel (a,b) -> tanh (a +. b *. xdoty)| IdKernel b ->let v = acos xdoty in(4.*.3.14159265*.b) ** (-0.5 *. (float_of_int l -.
exp (0. -. v *. v /. b)• 注: let は関数定義 (と変数束縛の両方).

Latent Dirichlet kernel & Bayesian kernels – p.16/16