November 6, 2023

Machine Learning andInformation Geometry
Introduction to Intelligent Systems Science II

Mahito Sugiyama

Learning Hierarchical Distribution (1/2)
DatasetBread Milk Apple
××ID 1 ○○×
ID 2 ○××
ID 3 ○○○
ID 4 ×○○ID 5 ×○×
ID 6 ○××
ID 7 ○○
×ID 8 ○

Lattice○○○ Freq: 0/8 = 0

○○×

○×○

×○○

○××

×○×

××○

Freq: 3/8 = 0.375

Freq: 6/8 = 0.75

Freq: 0/8 = 0

Freq: 2/8 = 0.25

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

×××

1/29

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
×○
××
○
○
×○

××
○
×○
×○
○

×××
○
×○
○
○

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

2/29

Matrix Balancing
p₁₁ p₁₂p₂₁ p₂₂

3/29

Matrix Balancing
Find r and s:(Make doublystochasticmatrix)=r₁ 0

p₁₁ p₁₂s₁ 00 r₂

p₂₁ p₂₂0 s₂

r₁s₁ p₁₁ r₁s₂ p₁₂
r₂s₁ p₂₁ r₂s₂ p₂₂∑j r₁sj p₁j = 1∑j r₂sj p₂j = 1∑i ris₁ pi₁ = 1 ∑i ris₂ pi₂ = 1

3/29

Sinkhorn-Knopp Algorithm• Alternately rescale all rows and columnsof a matrix 𝑃 to sum to 1
• Commonly used to compute entropy-regularized
Optimal transport (Wasserstein distance)– [Cuturi, 2013]

4/29

Revisit Matrix Balancing
p₁₁p₁₂

p₁₃

p₂₁

p₂₂

p₂₃

p₃₁

p₃₂

p₃₃
[Sugiyama, Nakahara, Tsuda, ICML2017]5/29

Introduce 𝜂η₁₂ η₁₃
η₁₁p₁₁ p₁₂ p₁₃
η₂₁p₂₁

p₂₂p₂₃

η₃₁
p₃₁

p₃₂

p₃₃
6/29

Introduce 𝜂η₁₂ η₁₃
η₁₁p₁₁ p₁₂ p₁₃
η₂₁p₂₁

p₂₂

p₂₃

η₃₁
p₃₁

p₃₂

p₃₃
6/29

Introduce 𝜂η₁₂ η₁₃
η₁₁p₁₁ p₁₂ p₁₃
η₂₁
p₂₁

p₂₂

p₂₃

η₃₁
p₃₁

p₃₂

p₃₃
6/29

Introduce 𝜂η₁₂ η₁₃
η₁₁
p₁₁ p₁₂ p₁₃
η₂₁
p₂₁

p₂₂

p₂₃

η₃₁
p₃₁

p₃₂

p₃₃
6/29

Introduce 𝜂
32
121

η₂₁
p₂₁

p₂₂

p₂₃

η₃₁
p₃₁

p₃₂

p₃₃

η₁₂ η₁₃
η₁₁p₁₁ p₁₂ p₁₃

6/29

Introduce 𝜃
p₁₁p₁₂

p₁₃

p₂₁

p₂₂

p₂₃
θ₂₂ θ₂₃

p₃₁

p₃₂

p₃₃
θ₃₂ θ₃₃

θij = log pij– log pi–₁j – log pij–₁+ log pi–₁j–₁

7/29

Introduce 𝜃
p₁₁

p₁₂

p₁₃

p₂₁

p₂₂

p₂₃
θ₂₂ θ₂₃

p₃₁

p₃₂

p₃₃
θ₃₂ θ₃₃

θij = log pij– log pi–₁j – log pij–₁+ log pi–₁j–₁

7/29

Introduce 𝜃
p₁₁

p₁₂

p₁₃

p₂₁

p₂₂

p₂₃
θ₂₂ θ₂₃

p₃₁

p₃₂

p₃₃
θ₃₂ θ₃₃

θij = log pij– log pi–₁j – log pij–₁+ log pi–₁j–₁

7/29

Introduce 𝜃
p₁₁

p₁₂

p₁₃

p₂₁

p₂₂

p₂₃
θ₂₂ θ₂₃p₃₁

p₃₂p₃₃
θ₃₂ θ₃₃

θij = log pij– log pi–₁j – log pij–₁+ log pi–₁j–₁

7/29

Balancing as Constraints on 𝜂 and 𝜃
32121

η₂₁
p₂₁

p₂₂

η₃₁
p₃₁

p₂₃
θ₂₂ θ₂₃p₃₂

p₃₃
θ₃₂ θ₃₃

η₁₂ η₁₃
η₁₁
p₁₁ p₁₂ p₁₃

θij = log pij– log pi–₁j – log pij–₁+ log pi–₁j–₁

Matrix balancing ⇔Satisfy ηi₁ = η₁i = 3 – i + 1
with keeping all θij
8/29

Introduce Partial Order Structure(p(s), θₛ, ηₛ)
p₁₁

p₁₂

p₁₃

p₂₁

p₂₂

p₂₃

p₃₁

p₃₂

p₃₃s

9/29

Partially Ordered Sets (Posets)2{a,b,c}{a,b,c}ℕ²

Network{a,b} {a,c} {b,c}{a}{b} {c}∅10/29

Incidence Algebra• Incidence algebra is defined over a poset (𝑆, ≤)– (Closed) Interval [𝑎, 𝑏] = {𝑠 ∈ 𝑆 ∣ 𝑎 ≤ 𝑠 ≤ 𝑏}

• Members of the incidence algebra arefunctions 𝛼(𝑎, 𝑏) from intervals [𝑎, 𝑏] to a scalar with
(𝛼 + 𝛽)(𝑎, 𝑏) = 𝛼(𝑎, 𝑏) + 𝛽(𝑎, 𝑏)∑(𝛼𝛽)(𝑎, 𝑏) =𝛼(𝑎, 𝑥)𝛽(𝑥, 𝑏)(convolution)

𝑎≤𝑥≤𝑏

11/29

Special Elements• Delta function 𝛿:
1 if 𝑎 = 𝑏
𝛿(𝑎, 𝑏) = {0 otherwise• Zeta function 𝜁:𝜁(𝑎, 𝑏) = {(integral)

1 if 𝑎 ≤ 𝑏0 otherwise• Möbius function 𝜇 = 𝜁 −1 : 𝜁𝜇 = 𝛿(differential)

12/29

(𝜁, 𝜇) Leads to Non-Singularity• For a poset (𝑆, ≤), let 𝑆 = {𝑠1 , 𝑠2 , … , 𝑠𝑛 }• Let us define the zeta matrix 𝐙 ∈ {0, 1}𝑛×𝑛 as𝑧𝑖𝑗 = 𝜁(𝑠𝑖 , 𝑠𝑗 )• Relationship between 𝜁 and 𝜇 guarantees that
𝐙 is always regular:
𝐙−1 = 𝐌

such that𝑚𝑖𝑗 = 𝜇(𝑠𝑖 , 𝑠𝑗 )– 𝐌 ∈ ℤ𝑛×𝑛

13/29Möbius Inversion Formula• Given a poset 𝑆, for any functions 𝑓, 𝑔 ∶ 𝑆 → ℝ,
the Möbius inversion formula is given as∑∑∑⎧ 𝑔(𝑥) =𝜁(𝑠, 𝑥)𝑓(𝑠) =𝜁(𝑠, 𝑥)𝑓(𝑠) =𝑓(𝑠)⎪𝑠∈𝑆𝑠≤𝑆𝑠≤𝑥∑∑⎨ 𝑓(𝑥) =𝜇(𝑠, 𝑥)𝑔(𝑠) =𝜇(𝑠, 𝑥)𝑔(𝑠)⎪𝑠≤𝑆𝑠∈𝑆⎩

14/29

E.g.1: Inclusion-Exclusion PrincipleA∪B∪CA

B

CA∩B A∩C B∩CA∩B∩C|A∪B∪C|= |A|+|B|+|C|–|A∩B|–|A∩C|–|B∩C|+|A∩B∩C|f (X) = |X| g(X) = |X \ ⋃ Y|f (X) = ∑Y≤X g(Y)g(X) = ∑Y≤X μ(Y,X) f (Y)

Y⊂X

15/29

Log-Linear Model on Poset [ICML2017]∑• For probability 𝑝∶𝑆 → (0, 1) with 𝑥∈𝑆 𝑝(𝑥) = 1,introduce 𝜃 and 𝜂 as∑𝜃𝑥 =𝜇(𝑠, 𝑥) log 𝑝(𝑠),𝑠∈𝑆∑∑𝜂𝑥 =𝜁(𝑥, 𝑠)𝑝(𝑠) =𝑝(𝑠)𝑠∈𝑆𝑠≥𝑥• From the Möbius inversion formula, log-linear model is:∑∑
log 𝑝(𝑥) =𝜁(𝑠, 𝑥)𝜃 𝑠 =𝜃𝑠𝑠∈𝑆𝑠≤𝑥– In the matrix form: log 𝒑 = 𝐙𝜃

16/29

Log-Linear Model on Poset(p(x), θx, ηx)x

17/29

Log-Linear Model on Poset(p(x), θx, ηx)log p(x) = ∑s≤x θsx

17/29

Log-Linear Model on Poset(p(x), θx, ηx)log p(x) = ∑s≤x θsxηx = ∑s≥x p(s)17/29

Exponential Family• The log-linear model on posets belongs tothe exponential family• 𝜃 : Natural parameter• 𝜂 : Expectation parameter

18/29

Binary Log-Linear Model{0, 1}3111(= Boltzmann machine)

110 101 011
100 010 001
000[Luo & Sugiyama, AAAI2019]19/29

Binary Log-Linear Model{0, 1}3111

110 101 011(= Boltzmann machine)log p(x) = –ψ + ∑i θixi + ∑i,jθijxixj + ···= ∑s≤x θs

For x with xi₁ = ··· = xik = 1,100 010 001
ηx = 𝔼[xi₁···xik] = Pr(xi₁ = ··· = xik = 1)
= ∑s≥x p(s)000[Luo & Sugiyama, AAAI2019]19/29

Dually Flat Structure• Let 𝜓(𝜃) = −𝜃(⊥)(convex, partition function)∑
Legendre transformation
𝜓(𝜃) ,,,,,,,,,,,,,,,,,,,,,,→ 𝜙(𝜂) =𝑝(𝑥) log 𝑝(𝑥)𝑥∈𝑆• (𝜓(𝜃), 𝜙(𝜂)) leads to dually flat coordinate system (𝜃, 𝜂):𝜕∇𝜓(𝜃) = 𝜂,𝜓(𝜃) = 𝜂 𝑥𝜕𝜃𝑥
𝜕∇𝜙(𝜂) = 𝜃,𝜙(𝜂) = 𝜃 𝑥
𝜕𝜂 𝑥20/29

Riemannian Metric (Fisher Information)
∑
𝜕 𝜕𝜕
𝜂 =
𝜁(𝑥, 𝑠)𝜁(𝑦, 𝑠)𝑝(𝑠) − 𝜂 𝑥 𝜂 𝑦𝜓(𝜃) =
𝜕𝜃𝑥 𝜕𝜃𝑦𝜕𝜃 𝑥 𝑦 𝑠∈𝑆∑𝜕𝜕 𝜕𝜃𝑦 =𝜇(𝑠, 𝑥)𝜇(𝑠, 𝑦)𝑝(𝑠)−1𝜙(𝜂) =𝜕𝜂 𝑥 𝜕𝜂𝑦𝜕𝜂 𝑥𝑠∈𝑆𝔼𝑠 [𝜕𝜕log 𝑝(𝑠)log 𝑝(𝑠)] = 𝛿(𝑥, 𝑦)
𝜕𝜂
𝜕𝜃 𝑥𝑦

21/29

Riemannian Metric (Fisher Information)∑𝜕𝜕𝔼𝑠 [𝜁(𝑥, 𝑠)𝜁(𝑦, 𝑠)𝑝(𝑠) − 𝜂 𝑥 𝜂 𝑦log 𝑝(𝑠)log 𝑝(𝑠)] =𝜕𝜃 𝑥𝜕𝜃 𝑦𝑠∈𝑆∑𝜕𝜕𝜇(𝑠, 𝑥)𝜇(𝑠, 𝑦)𝑝(𝑠)−1𝔼𝑠 [log 𝑝(𝑠)log 𝑝(𝑠)] =𝜕𝜂 𝑥𝜕𝜂 𝑦𝑠∈𝑆𝔼𝑠 [𝜕𝜕log 𝑝(𝑠)log 𝑝(𝑠)] = 𝛿(𝑥, 𝑦)𝜕𝜂𝜕𝜃 𝑥𝑦22/29

Mixed Coordinate System• Many problems are formulated as coordinate mixing

P = ( θ1, θ2, ..., θi–1, θi, θi+1, ..., θₙ )Q = ( η1, η2, ..., ηi–1, θi, θi+1, ..., θₙ )R = ( η1, η2, ..., ηi–1, ηi, ηi+1, ..., ηₙ )e-projection(MLE)m-projection

Pythagorean theorem:(Q is always unique)
KL(P, R) = KL(P, Q) + KL(Q, R)
23/29

Mixed Coordinate System (Example)• Many problems are formulated as coordinate mixing

P = ( 0 , 0 , ..., 0 , 0 , 0, ..., 0 )

Q = ( η1, η2, ..., ηi–1, 0 , 0, ..., 0 )

R = ( η1, η2, ..., ηi–1, ηi, ηi+1, ..., ηₙ )Uniform dist.
Empirical dist.

Pythagorean theorem:(Q is always unique)
KL(P, R) = KL(P, Q) + KL(Q, R)
24/29

Two Submanifolds
Q = (η1,η2,...,ηi–1,θi,θi+1,...,θₙ)Fix
P = (θ1,θ2,...,θi–1,θi,θi+1,...,θₙ)(Model manifold)e-projection
= MLE
Fix
R = (η1,η2,...,ηi–1,ηi,ηi+1,...,ηₙ) (Data manifold)
25/29

Gradient methods for e-projection• e-projection is convex optimization• Gradient descent (first-order):𝜃 next ← 𝜃 − 𝜀(𝜂 − 𝜂̂ target )• Natural gradient (second-order)
𝜃 next ← 𝜃 − 𝐺 −1 (𝜂 − 𝜂̂ target )– 𝐺 is Fisher information matrix w.r.t. 𝜃• Coordinate descent [Hayashi, Sugiyama, Matsushima, DSAA2020]

26/29

Boltzmann Machine Training
BoltzmannmachineSamplespace 1111
1110

1100 1010
1000 0100
0000
27/29

Boltzmann Machine Training
BoltzmannmachineSamplespace 1111

θ=011101100 1010

η=η1000 0100
0000
27/29

Matrix Balancing
3x3 matrix
as poset:

η=3–i+1

θ=θ

28/29

Summary• Information geometric formulation forpartial order structures– Learning process can be achieved as a projectionin the parameter space (dually flat manifold)• Several applications– Boltzmann machines– Matrix (Tensor) balancing

29/29