November 24, 2023

Boltzmann Machines
Data Mining 05 (データマイニング)

Mahito Sugiyama (杉山麿人)

Today’s Outline• Boltzmann Machines (Ising models):
A fundamental probabilistic model of deep learning– Gibbs distribution– The learning equation– Gibbs sampling• Relationship to the deep architecture– DBM (Deep Boltzmann Machines)

1/24

Learning Hierarchical Distribution (1/2)
DatasetBread Milk Apple00ID 1 110ID 2 100ID 3 111ID 4 011ID 5 010ID 6 100ID 7 110ID 8 1

Lattice110

Freq: 3/8 = 0.375

100

Freq: 6/8 = 0.75

111

Freq: 0/8 = 0101011010

001

Freq: 0/8 = 0

Freq: 2/8 = 0.25

Freq: 5/8 = 0.625 Freq: 2/8 = 0.25

000
2/24

Learning Hierarchical Distribution (2/2)
MLElog(prob.) = –10.41 + 9.43[Bread] + 8.52[Milk] – 9.84[Apple]– 9.03[Bread&Milk] + 9.43[Milk&Apple]

BoltzmannmachineBreadMilkApple

Bread Milk Apple

01
00
11010010101
100010111

Prob. from data?
0.375?
?
0.375?
0.25?

Learned prob.
0.0000300109
0.3749599867
0.1499903954
0.0000000016
0.2250096042
0.0000200043
0.0999895960
0.1500004008

3/24

Boltzmann Machines• A Boltzmann machine (BM) is represented as an undirected graph
𝐺 = (𝑉, 𝐸) with 𝑉 = {1, 2, … , 𝑛} and 𝐸 ⊆ {{𝑖, 𝑗} ∣ 𝑖, 𝑗 ∈ 𝑉}
• The energy function Φ∶{0, 1}𝑛 → ℝ of a BM 𝐺 is defined as∑∑Φ(𝒙; 𝜽) = −𝜃𝑖 𝑥𝑖 −
𝜃𝑖𝑗 𝑥𝑖 𝑥𝑗𝑖∈𝑉{𝑖,𝑗}∈𝐸– 𝒙 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ {0, 1}𝑛– 𝜽 = (𝜃1 , 𝜃2 , … , 𝜃𝑛 , 𝜃12 , 𝜃13 , … , 𝜃𝑛−1𝑛 ) is a parameter vector forvertices (bias) 𝜃1 , … , 𝜃𝑛 and edges (weight) 𝜃12 , … , 𝜃𝑛−1𝑛– 𝜃𝑖𝑗 = 0 if {𝑖, 𝑗} ∉ 𝐸
4/24

Gibbs Distribution• Probability 𝑝(𝒙; 𝜽) is obtained for each 𝒙 ∈ {0, 1}𝑛 asexp(−Φ(𝒙, 𝜽))𝑝(𝒙; 𝜽) =𝑍(𝜽)• 𝑍(𝜽) is a partition function such that∑
𝑍(𝜽) =exp(−Φ(𝒙; 𝜽))𝒙∈{0,1}𝑛to ensure the condition∑𝒙∈{0,1}𝑛𝑝(𝒙) = 1• The distribution 𝑃 composed of 𝑝(𝒙) is called Gibbs distribution
5/24

Sample Space of BM
Boltzmann
Machine (BM)12{1,2,3,4}Samplespace{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

4
3{1}

{2}

{3}{4}

Ø
6/24

Parameters 𝜃
Boltzmann
Machine (BM)12{1,2,3,4}
θijSamplespace{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}4
3{1}θi{2}{3}{4}Ø
7/24

Probability Computation
Boltzmann
Machine (BM)12{1,2,3,4}
θijSamplespace{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}4
3{1}θi{2}{3}{4}Ø8/24

Learning of BM by MLE• Given a dataset 𝐷 = {𝒙(1) , 𝒙(2) , … , 𝒙(𝑁) }, the objective of learning
Boltzmann machines is to maximize the (log-)likelihood(Maximum Likelihood Estimation; MLE)
Find 𝜽 that maximizes𝑁∏𝑝(𝒙(𝑘) ; 𝜽) = 𝑝(𝒙(1) ; 𝜽) ⋅ 𝑝(𝒙(2) ; 𝜽) ⋅ ⋯ ⋅ 𝑝(𝒙(𝑁) ; 𝜽)

𝑘=1

– The probability of generating the given dataset by a BM

• The log-likelihood is usually used:
𝐿𝐷 (𝜽) = log𝑁∏𝑘=1

𝑝(𝒙(𝑘) ; 𝜽) =𝑁∑log 𝑝(𝒙(𝑘) ; 𝜽)

𝑘=1

9/24

Gradient of 𝜃
• The gradient of 𝐿𝐷 (𝜽) w.r.t. 𝜃𝑖 and 𝜃𝑖𝑗 is obtained as
𝜕𝐿𝐷 (𝜽)= |{𝒙(𝑘) ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 1}| − 𝑁 𝜂𝑖 ,𝜕𝜃𝑖𝜕𝐿𝐷 (𝜽)= |{𝒙(𝑘) ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 𝑥(𝑘)𝑗 = 1}| − 𝑁 𝜂𝑖𝑗
𝜕𝜃𝑖𝑗⏟⎴⎴⎴⎴⎴⎴⎴⎴⎴⏟⎴⎴⎴⎴⎴⎴⎴⎴⎴⏟ ⏟⏟⏟datamodelwhere∑𝑝(𝒙; 𝜽)1[𝑥𝑖 = 1]
⎧ 𝜂𝑖 = 𝐄𝜽 [𝑥𝑖 ] = Pr(𝑥𝑖 = 1) =𝒙∑⎨ 𝜂𝑖𝑗 = 𝐄𝜽 [𝑥𝑖 𝑥𝑗 ] = Pr(𝑥𝑖 = 𝑥𝑗 = 1) =𝑝(𝒙; 𝜽)1[𝑥𝑖 = 𝑥𝑗 = 1]
𝒙⎩

10/24

Learning Equation of BM• 𝐿𝐷 (𝜽) is maximized when the gradient is zero ⇐⇒ For all 𝜃𝑖 , 𝜃𝑖𝑗
1⎧|{𝒙(𝑘) ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 1}| = 𝜂𝑖𝑁
⎨ 1|{𝒙 ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 𝑥(𝑘)𝑗 = 1}| = 𝜂𝑖𝑗⎩ 𝑁 (𝑘)– This is known as learning equation of BM– 𝜂 coincides with the frequency used in itemset mining

11/24

Frequency 𝜂Boltzmann
Machine (BM)12{1,2,3,4}Samplespace{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}43η13{1}{2}{3}{4}

Ø12/24

Empirical Frequency• For the empirical distribution 𝑃̂ with1
̂𝑝(𝒙)= |{𝒙(𝑘) ∈ 𝐷 ∣ 𝒙(𝑘) = 𝒙}|,𝑁
define1𝜂̂𝑖 = |{𝒙(𝑘) ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 1}|
𝑁1
𝜂̂𝑖𝑗 = |{𝒙(𝑘) ∈ 𝐷 ∣ 𝑥(𝑘)𝑖 = 𝑥(𝑘)𝑗 = 1}|
𝑁• The learning equation becomes𝜂̂𝑖 = 𝜂𝑖 , 𝜂̂𝑖𝑗 = 𝜂𝑖𝑗
13/24

KL Divergence Minimization• Given two distributions 𝑃, 𝑄, the Kullback–Leibler (KL) divergencefrom 𝑃 to 𝑄:∑𝑝(𝑥)𝐷KL (𝑃, 𝑄) =𝑝(𝑥) log𝑞(𝑥)𝑥• Maximizing the (log)likelihood is equivalent tô 𝑃)
minimizing the KL divergence: min𝑃∈𝒮 𝐷KL (𝑃,– 𝒮: the set of Gibbs distributions

14/24

Optimization: Gradient Ascent
Algorithm 1: Learning of BM by gradient ascent
Initialize 𝜽 with some values; 𝑡 ← 0;
2 repeat3
foreach 𝑖 ∈ 𝑉 do)((𝑡+1)(𝑡)4𝜃𝑖← 𝜃𝑖 + 𝜀 𝜂̂𝑖 − 𝜂𝑖 ;16

foreach {𝑖, 𝑗} ∈ 𝐸 do()
(𝑡)
(𝑡+1)
𝜃𝑖𝑗 ← 𝜃𝑖𝑗 + 𝜀 𝜂̂𝑖𝑗 − 𝜂𝑖𝑗 ;7𝑡 ←𝑡+1

58until 𝜽(𝑡)

=𝜽

(𝑡+1)

;
15/24

Combinatorial Explosion• The serious problem of learning BMs: combinatorial explosion!!
• The time complexity of computation of 𝜂𝑖 :∑𝜂𝑖 =𝑝(𝒙; 𝜽)1[𝑥𝑖 = 1]𝒙∈{0,1}𝑛is 𝑂(2𝑛 ) and it is impossible to evaluatê– This is required to get the gradient 𝜂(𝑥)− 𝜂(𝑥)• Solution: approximate it by Gibbs sampling

16/24

Gibbs Sampling (1/2)• A Markov chain Monte Carlo (MCMC) algorithm• We can generate samples from the current Gibbs distribution– 𝑛 variables are dependent with each other– The partition function is not needed• After obtaining enough sample 𝑆 = {𝒔1 , 𝒔2 , … , 𝒔𝑀 } by Gibbs
sampling, 𝜂𝑖 can be approximated as1
𝜂𝑖 ≈ | { 𝒔 ∈ 𝑆 ∣ 𝑠𝑖 = 1} |,𝑀}1 {𝜂𝑖𝑗 ≈ | 𝒔 ∈ 𝑆 ∣ 𝑠𝑖 = 𝑠𝑗 = 1 |𝑀
17/24

Gibbs Sampling (2/2)• For 𝒙 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ), the conditional probability of the 𝑖thevariable being 𝑥𝑖 with fixing others is𝑝(𝑥1 , … , 𝑥𝑖−1 , 𝑥𝑖 , 𝑥𝑖+1 , … , 𝑥𝑛 )𝑝𝑖 =𝑝(𝑥1 , … , 𝑥𝑖−1 , 0, 𝑥𝑖+1 , … , 𝑥𝑛 ) + 𝑝(𝑥1 , … , 𝑥𝑖−1 , 1, 𝑥𝑖+1 , … , 𝑥𝑛 )exp(𝜆𝑖 𝑥𝑖 ),=1 + exp(𝜆𝑖 )∑𝜆 𝑖 = 𝜃𝑖 +𝜃𝑖𝑗 𝑥𝑗𝑗≠𝑖

18/24

Algorithm 2: Gibbs Sampling
Initialize 𝒙 with some values;
2 repeat3
foreach 𝑖 ∈ {1, 2, … , 𝑛} do
4
if 𝑝𝑖 ≥ random value 𝑢 ∈ [0, 1] then5𝑥𝑖 ← 16else
7𝑥𝑖 ← 01Output 𝒙 and use it for the next initial vector
9 until getting enough sample;
819/24

Introducing Hidden Variables• To increase the representation power of BMs,
we can introduce hidden variables• When there are hidden nodes, the (log-)likelihood is maximized
with respect to the distribution in which the hidden variables aremarginalized out• Let 𝑉 and 𝐻 be visible and hidden nodes

20/24

Outcome Space with Hidden Variable
Boltzmann
Machine (BM)12

{1,2,3,4}

Samplespace{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}43Hiddenvariable{1}{2}{3}{4}

Ø
21/24

Restricted Boltzmann Machines (RBMs)
BoltzmannMachine (BM)12{1,2,3,4}Sample
space{1,2,3} {1,2,4} {1,3,4} {2,3,4}{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}43Hiddenvariable{1}{2}{3}{4}

Ø22/24

Learning of RBMs
• Given a dataset 𝐷 = {𝒗(1) , … , 𝒗(𝑁) }, learning equations in RBMs are
1 ∑𝑁𝑣= 𝜂𝑖 (visible, 𝑖 ∈ 𝑉)
𝑁 𝑘=1 (𝑘)𝑖
1 ∑𝑁sig(𝜆(𝑘)𝑗 ) = 𝜂𝑗 (hidden, 𝑗 ∈ 𝐻)
𝑁 𝑘=1
1 ∑𝑁𝑣 sig(𝜆(𝑘)𝑗 ) = 𝜂𝑖𝑗 , (visible–hidden)
𝑁 𝑘=1 (𝑘)𝑖∑exp(𝜆(𝑘)𝑗 )sig(𝜆(𝑘)𝑗 ) =, 𝜆(𝑘)𝑗 = 𝜃𝑗 +𝜃𝑖𝑗 𝑣(𝑘)𝑖
1 + exp(𝜆(𝑘)𝑗 )𝑖
23/24

Deep Boltzmann Machines (DBMs)
BoltzmannMachine (BM)1

{1,2,3,4}

Samplespace4

2ndlayer{1,2,3} {1,2,4} {1,3,4} {2,3,4}

3

1stlayer{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}2Visiblelayer{1}{2}

{3}

{4}

Ø24/24