Contrastive Divergence learning,
Product models,and Deep Belief Nets
Daichi Mochihashi
NTT Communication Science Laboratories

daichi@cslab.kecl.ntt.co.jp
SVM 2008 「夏の終りに」
Aug 31, 2008
NAIST

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.1/28

Overview• 混合モデルから Product モデルへ
◦ Products of Experts (PoE) (Hinton, 2002)• NIPS 2007: Deep Learning ワークショップ◦ http://www.iro.umontreal.ca/˜lisa/twiki/bin/view.cgi/

Public/DeepLearningWorkshopNIPS2007◦ 「Deep Belief Net」と次々に言わせるという Banquet ネタ• Contrastive Divergence 学習• 自然言語処理との (深い) 関係と展望

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.2/28

Mixture models and Product models• Mixture Modelp(x|Θ; Λ) =M

λm p(x|θm )

(1)

m=1

◦ データは「どれか 1 つ」のモデルから生成される• Product ModelM

m=1p(x|Θ) =  M
xp(x|θm )m=1 p(x|θm )(2)◦ データは「すべての制約」を満たされて生成◦ 現実のデータには, 多くの場合こちらが適当◦ 自然言語の場合,− PCFG, n-gram, ジェンダー, 文脈, リズム, …など

多くの条件を満たして文が生成されている (cf. 短歌や俳句)− 商品を選ぶにも, 「内容」
「デザイン」「緊急性」「広告効果」
etc..
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.3/28

Loglinear and Product of Experts
 λm fm (x)m p(x|θm )me⇐⇒ p(x|Λ) =  p(x|Θ) =  
λm fm (x)xm p(x|θm )
xme

(3)

• Product of Experts (PoE) … 1 つ 1 つのモデルが, パラメータ θを持つ確率分布• Loglinear は, 各モデルが (スケールされた) δ関数となる特別な場合

eλm fm (x)=eλm
1if fm (x) = 1otherwise(4)• 学習の目標 (Unsupervised) :◦ 各モデル p(·|θ1 ) · · · p(·|θM ) ができるだけ直交して (独立に)データを表現するように, パラメータ Θ を最適化する◦ 「積数」M の可変長化 (later)

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.4/28

Problem with Estimating PoE
m p(x|θm )p(x|Θ) =  (5)xm p(x|θm ) • 分配関数 Z = x m p(x|θm ) が容易には求まらない！
◦x はたとえば, 「可能な文 x すべてについての厖大な和」• Loglinear と違い, 一般に凸でない (× L-BFGS)• 教師なし学習.

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.5/28

Contrastive Divergence learning (Hinton 2000; 2002)• 一般に,

1p(x|θ) = f (x|θ)
Z; Z=f (x|θ)(6)

xとなるモデルを考えよう.
• データ X = {x1 , x2 , · · · , xN } について,
L = log p(X|θ) p̂(x)=Np̂(xi ) log p(xi |θ)(7)(8)

i=1を最大化することを考える.
• このとき, log p(x|θ) = log f (x|θ) − log Z なので,Contrastive Divergence learning,Product models,and Deep Belief Nets – p.6/28

Contrastive Divergence learning (2)∂∂log p(x|θ) =[log f (x|θ) − log Z]
∂θ∂θ
1 ∂
∂
log f (x|θ) −Z=∂θZ ∂θ
ここでかつ ∂∂ ∂
Z=f (x|θ)f (x|θ) =∂θ∂θ x∂θx1∂∂
log f (x|θ) =f (x|θ)∂θ
f (x|θ) ∂θ∂∂f (x|θ) = f (x|θ) log f (x|θ)
∴∂θ
∂θ

(9)
(10)

(11)

(12)

なので,(13)

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.7/28

Contrastive Divergence learning (3) f (x|θ) ∂∂log f (x|θ) −log f (x|θ)∂θ
Z ∂θxp̂(x)

∂∂log f (x|θ) −=p(x|θ) log f (x|θ)∂θ∂θx∂L
=
∂θ

(14)

(15)

p̂(x)

==

∂log f (x|θ)∂θ∂
log f (x|θ)∂θp̂(x)p0−−∂
log f (x|θ)∂θ∂
log f (x|θ)∂θ(16)
p(x|θ)(17)p∞• ここで, 経験分布 p̂(x) = p0 , モデル分布 p(x|θ) = p∞ とおいた.
◦ モデル分布は, MCMC を ∞ 回動かしてサンプルした分布と同じ
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.8/28

Contrastive Divergence learning (4)∂L=∂θ∂
log f (x|θ)
∂θ

p0−

∂
log f (x|θ)
∂θ

(18)
p∞

この差を計算して θ を最適化する代わりに,∂log f (x|θ)∂θ

p0−∂log f (x|θ)∂θ(19)
p1で微分を計算することにする• p1 は, データ x から MCMC 1 回分の reconstruction(confabulation)• こうしても, 結果はほとんど変わらない

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.9/28

Contrastive Divergence learning (5)
ここで,D(pn ||p∞ ) =pn (x) log pn (x) −xpn (x) log p∞ (x)

(20)

x

= −H(pn ) − log p∞ pn ∝ −log p∞ pn(21)に注意すると,−∂p0 ||p∞ − p1 ||p∞ =∂θm∂log p∞∂θmp0∂
log p(x|θm )∂θm=−∂log p∞∂θm−p0∂log p(x|θm )∂θm∂log p(x|θ)
∂θ

−+p1

p1p∞

∂
log p(x|θ)∂θp∞(22)
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.10/28

Contrastive Divergence learning (6)=∂log p(x|θm )∂θmp0−∂
log p(x|θm )∂θmp1.

(23)

よって,

∂D
=
∂θm

∂
log p(x|θm )
∂θmp0

−

∂
log p(x|θm )∂θm(24)
p1を MCMC 1 ステップから計算して, θm を更新すればよい. Contrastive Divergence learning,Product models,and Deep Belief Nets – p.11/28

Contrastive Divergence learning (7): 図解• “Self supervised boosting” (Welling, Zemel, Hinton 2001; SVM勉強会, 2002) からの図(a)252520201515101055(c)00−5−5−10−10−15−15−20−20−25−40−30−20−100102030−25−4040−30−20−10010203040• 1 次元の場合は, ホワイトボードで説明

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.12/28

Relationship to other works (1/2)• “Contrastive Estimation” (Smith and Eisner, ACL 2005)… CD とほとんど同じ (本人は浅い理解で違うと主張している)◦ CE は∂L=fj |xi λ − fj |N (xi )λ(25)∂λjiを解いて λj を最適化
◦ これはp(xi |N (xi ), Λ)(26)

iを最大化していることに相当◦ N は “Neighborhood” 関数で,− 1 語削除/前後 2 単語入れ替え/部分単語列削除/任意の単語置換− などを考える
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.13/28

Relationship to other works (2/2)• “A Discriminative Language Model with Pseudo-NegativeExamples” (Okanohara, ACL 2007)… CD と基本的に同じ◦ “擬似負例” をモデルから生成して, 全文最大エントロピー法のパラメータを学習◦ 学習には, オンラインマージン最大化法を使う (ここが違う)◦ クラス bigram を使った拡張◦ 全文 ME には, 誰も適用していなかった

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.14/28

Text modeling through Products of Experts• Rate Adapting Poisson (RAP) Model(Gehler, Holub, Welling: ICML 2006)
http://www.kyb.tuebingen.mpg.de/bs/people/pgehler/rap/
BinomialhWxPoisson

Figure 1. Markov random field representation of the RAP model.

p(x, h) ∝i

exi
λi
xi !

jpj
ehj
·1 − pj hj !(Mj −hj )!

• 単語観測ベクトル: x, 隠れトピック層: hwij xi hj
ij



(27)

Energy• Restricted Boltzmann Machine というニューラルネットの一種• “Prior” というものはない◦ 正規化定数 Z は計算不可能 (に近い)Contrastive Divergence learning,Product models,and Deep Belief Nets – p.15/28

RAP (2): Conditional distribution• x と h の条件つき分布は Poisson,Binomial になる
Po λi exp(wij hj )p(x|h) =ip(h|x) =(28)jBin σ(βj +j

wij xi ), Mj(29)i◦ σ(x) = 1/(1 + exp(−x)) : シグモイド関数◦ βj = log pj /(1−pj ) とおいた
• 観測値 xn から隠れ層 hn がサンプルでき, hn から“Reconstruction” x̃n がサンプルできる

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.16/28

RAP (3): Marginal distribution• 潜在トピック層 h を周辺化して消去すると,p(x) ∝iexi·λixi !

ejMj(1 + exp(wij xi −βj ))
i





“activation”

(30)トピック j に関する x のトピック j の確率密度 ≥ 1◦ x の確率  Poisson 出現 × ニューラルネットの Activationの積− x が「スポーツ」トピックで適当かつ, 「政治」のactivation が 0 でもよい(∵ e0 = 1)

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.17/28

RAP (4): 学習• 正規化定数 Z はわからないので, Contrastive Divergence で学習(Mj = 1 とした) δ log λi ∝ xi p̂ − xi p̃δβj∝ −σ(wj ·x − βj )p̂ − σ(wj ·x − βj )p̃

δwij ∝ xi σ(wj ·x − βj )p̂ − xi σ(wj ·x − βj )p̃

(31)

• “Reconstruction” p̃ は x → h → x̃ で作った, モデルからの擬似データ

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.18/28

RAP (5): 実験• 20 Newsgroup :0.9
0.8
0.7Precision

0.6
0.5
0.4
0.3

RAP 100 dimensions
PLSI 250 dimensions
LSI 175 dimensions
TF−IDF

0.2
0.10 −310−210−1

Recall01010Figure 4. RPC plot on a log-scale of the 20 Newsgroups dataset
for various models. As a baseline the retrieval results with tfidf reweighed word-counts are shown. Number of topics for eachmodel was chosen by optimizing 1-NN classification performanceon the test set corresponding to the average precision for retrieving a single document (left most marker).

• Reuters-21578 :

0.44
0.42

Area under RPC

0.4
0.38
0.36
0.34
0.32
0.3
RAP
PLSI
LSI

0.28
0.26
0.24
25

50

75

100

125

150

175

Latent dimensionality

200225250

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.19/28

RAP (6): 長所• RAP の長所: 文書 x が与えられると, “Latent representation” は

β + Wx(32)として簡単に求まる (行列・ベクトルの積は超高速)◦ LDA や HDP では複雑な最適化が必要◦ Gaussian 表現されている →カーネルマシン等への応用; 後で◦ 正確な統計的意味づけがある− 単なるニューラルネットではない• RBM は, ニューラルネットの世界では “Harmonium” として知られていたらしい (Smolensky 1986)◦ ただし, Hinton(2002) のような効率的な学習法はなかった• 指数分布族に一般化可能◦ “Exponential Family Harmoniums” (Welling, Rosen-Zvi,Hinton: NIPS 2004)
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.20/28

From Harmoniums to Deep Belief Nets
• Deep Belief Nets (Hinton+ 2006, Neural Computation)◦ RBM を階層化
◦ “Encoder” と “Decoder” の組み合わせで, ある隠れ層の結果を次の層の入力として順番に CD 学習◦ Variational bound を順に最大化している (らしい)• “Semi-supervised Learning of Compact Document

Representations with Deep Networks” (Ranzato, Szummer(Microsoft), ICML 2008)
Code 2
Code 1
Input count

Encoder 2
Decoder 3

Encoder 1
Decoder 2
Decoder 1

Code 3
Encoder 3

Classifier 3Classifier 2Classifier 1

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.21/28

Deep Document Representation (Ranzato&Szummer 2008)• 第 1 層は, Poisson(Decoder)+Gaussian(Encoder) … RAP と同じ• 第 2 層以降では, Gaussian(Decoder)+Gaussian(Encoder)1
Input +
count xLabel ylog

WElogisticCodezWDrateexpNLL+WCsoftmax

CElosscFigure 2. The architecture of the ﬁrst stage has three components: (1) an encoder, (2) a decoder (Poisson regressor),and (3) a classiﬁer. The loss is the weighted sum of crossentropy (CE) and negative log-likelihood (NLL) under thePoisson model.

◦ Encoder: z ∼ σ(W log(x+1) + bE ) : 全層
◦ Decoder: x ∼ Po(β exp(WD z + bD )) : 第 1 層x ∼ N(WD z + bD , σ)

: 第 2 層以降
Contrastive Divergence learning,Product models,and Deep Belief Nets – p.22/28

Semi-supervised Learning• 文書ラベルを考慮した Semi-Supervised Learning

L = ER + αEC(33)を最小化. (α = 0 で生成モデル)• ER : Reconstruction errorER =β exp(WD z + bDi ) − (xi WD z + xi bDi − log(xi !)) (34)i

• EC : Classification error◦ 隠れ層 z からラベルを予測する

Ci z+bCi )= Pexp(Wi exp(WCi z+bCi )EC = − K
i=1 yi log ŷiyˆi(35)Contrastive Divergence learning,Product models,and Deep Belief Nets – p.23/28

分類問題への適用• “Using Deep Belief Nets to Learn Covariance kernels for

Gaussian Processes”, Salakhutdinov and Hinton, NIPS 2007
• Gaussian Process: ベイズカーネルマシン◦ 線形回帰の重みベクトル w を積分消去◦ データ: D = {(yi , xi )} (i = 1 . . . N )◦ ガウス分布で予測

p(y|x, D, σ 2 ) = N(kT (K + σ 2 I)−1 y, Σ)(36)− k, K : カーネル行列− k = K(x, X)− K = K(X, X)◦ y が離散の場合は, 予測にシグモイドをかませる

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.24/28

分類問題への適用 (2)• 通常のカーネルマシンの問題点:◦ 確率モデルでない (ex. SVM)
◦ 要素 (ex. 単語) 間のカーネルが ID カーネルだったりする− Tree kernel 等も最後は単語の比較に帰着• Deep Belief Nets の隠れ層 (Gaussian) を Gaussian Process の入力とする


1
hi |xi − hj |xj
Kij = α exp −2β2(37)◦ h|x, W : DBN による入力 x の map◦ α, β は GP 分類器を作った後, 予測に関して Optimize する

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.25/28

Future Agenda• 隠れ層の数/素子数の自動決定?
• 時系列モデルへの拡張?
◦ 言語モデルとしては一応 (tRBM; Mnih, Hinton 2007) があるが‥• Structured Output の場合?

⇓• GP 等のカーネルマシンとの連繋が興味深いContrastive Divergence learning,Product models,and Deep Belief Nets – p.26/28

最後に• 京阪奈に来て, 今年でちょうど 10 年
◦ 1998 年 NAIST M1 入学◦ 色々ありました.. (ATR etc.)• 当時興味を持っていたことは, 未だ光を失っていない◦ 統計的な洗練 (でもまだ充分ではない)◦ 現役の人は, 自分の問題意識を大事にしてほしい• そろそろ京阪奈を出たい?

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.27/28

Fin• ご静聴ありがとうございました。

Contrastive Divergence learning,Product models,and Deep Belief Nets – p.28/28