ICML 2016 NYC

Structure Learning ofPartitioned Markov Networks
Song Liu1, Taiji Suzuki2,Masashi Sugiyama3 and Kenji Fukumizu1
1. The Institute of Statistical Mathematics
2. Tokyo Institute of Technology, JST PRESTO
3. University of Tokyo1

Outline
1. Markov Network
2. Partitioned Markov Network
3. Learning Partitioned Markov Network
4. Experiments
5. Conclusion

2

Markov Network (MN)
• Markov Network: undirected graphical model, encoding
the conditional independence between random variables.

𝑃(𝑋1 , 𝑋2 , … , 𝑋𝑚 )𝑋𝑢 and 𝑋𝑣 are notconnected𝑋𝑢 ⊥ 𝑋𝑣 | 𝑋∖ 𝑋𝑢,𝑋𝑣𝑋𝑢𝑋𝑣

3

Learning Sparse Structure of MN• Hammersley-Clifford Theorem (Hammersley & Clifford,1971).

𝑋𝜙(𝑥1 , 𝑥2 )1

2𝑝 𝒙 ∝ ෑ 𝜙(𝒙𝑐 )𝑐∈𝑪Cliques 𝒄: fully connected sub-graph• Learning a sparse factorization of density function.
෡ = argmax𝚯 σ𝒙 log 𝑝(𝒙; 𝚯) − 𝜆 𝚯 , 𝚯 ∈ ℝ𝑚×𝑚 .
•𝚯• (Friedman et al., 2008)

1

Sparsity inducing norm
4

Why not learn a full MN?
Not a good idea…

• Too few samples.
• Full model is beyond our understanding.
• We are only interested in partial connections!
5Outline
1. Markov Network
2. Partitioned Markov Network
3. Learning Partitioned Markov Network
4. Experiments
5. Conclusion

6

Partitioned Networks
British Parliament(WIKIPEDIA: House of Commons of the United Kingdom)

Some networks are naturally partitioned.
7

Partitioned MN

Focus!

?

?
𝑋𝑣
𝑋𝑢

a full network?
? 𝑋𝑢𝑋𝑣?
?

?

a partitioned network• Discover intergroup links of a partitioned
network is key in many applications

8

Partitioned (Local) Markovian Property
𝑋1

𝑋2?

?
?

?

Partitioned Markovian Property:∀𝑋𝑢 ∈ 𝑋1, ∀𝑋𝑣 ∈ 𝑋2,If 𝑋𝑢 and 𝑋𝑣 are not connected,𝑋𝑢 ⊥ 𝑋𝑣 | 𝑋\{𝑋𝑢 ,𝑋𝑣 }𝑋 = (𝑋1, 𝑋2) is a partition of 𝑋.
Partitioned MN does not guarantee:∀𝑋𝑢 , 𝑋𝑣 ∈ 𝑋, If 𝑋𝑢 and 𝑋𝑣 are not connected,𝑋𝑢 ⊥ 𝑋𝑣 | 𝑋\{𝑋𝑢 ,𝑋𝑣}

9

Local Factorization of Partitioned MN
Recall, the full MN factorizes over the cliques(Hammersley Clifford Theorem).
𝑋

𝜙(𝑥1 , 𝑥2 )1

2𝑝 𝒙 ∝ ෑ 𝜙(𝒙𝑐 )𝑐∈𝑪Cliques 𝒄: fully connected sub-graph

What can we say about the partitioned MN?

10Factorization of Partitioned MN
𝑋1

𝑋2

Partitioned Ratio𝑝(𝑥1, 𝑥2) ∝𝑝(𝑥1)𝑝(𝑥2)ෑ 𝜙(𝒙𝑏 )𝑏 ∈𝑩𝑩: the set of Passage structures.

• An analog to Hamersley-Clifford Theorem• Factorization is over a novel structure: Passage.

11

Passage
𝑋1 𝑋2
𝑋1𝑋2

𝑋1…

𝑋2

Passage
We define passage 𝐵 a sub-graph of 𝐺, such that𝑋𝐵 ∩ 𝑋1 ≠ ∅, 𝑋𝐵 ∩ 𝑋2 ≠ ∅, ∀𝑋𝑢 ∈ 𝑋1 ∩ 𝑋𝐵 and∀𝑋𝑣 ∈ 𝑋2 ∩ 𝑋𝐵 , 𝑋𝑢 , 𝑋𝑣 is in the edge set.
12

Outline
1. Markov Network
2. Partitioned Markov Network
3. Learning Partitioned Markov Network
4. Experiments
5. Conclusion

13

From Partitioned Ratio to Structure• Knowing factorization of Partitioned Ratio =Knowing passages structures in Partitioned MN.
If 𝑥𝑢 ∈ 𝑋1, 𝑥𝑣 ∈ 𝑋2 do not appear in
the same passage factor at least once,
𝑋𝑢 ⊥ 𝑋𝑣 | \𝑋𝑢 , 𝑋𝑣 (See Proposition 2 in the paper).
• Pairwise assumption:𝑝(𝑥1,𝑥2)∝ ς𝑏∈𝑩 𝜙 𝒙𝑏 = ς𝑏∈𝑩 ς𝑋𝑢,𝑋𝑣∈𝑋𝐵 ℎ𝑢,𝑣 𝑥𝑢, 𝑥𝑣
𝑝(𝑥 )𝑝(𝑥 )1214Learning Pairwise Partitioned Ratio• Given the partition 𝑃 𝒙 = 𝑃 𝒙1 , 𝒙2 , 𝒙 ∈ 𝑅𝑚 and𝑛𝑖𝑖
paired sample 𝒙1 , 𝒙2
∼ 𝑃, PR can be modelled
𝑖=1as:

1𝑔 𝒙; 𝜽 =exp ෍ 𝜽⊤𝑢,𝑣 𝒇 𝒙𝑢,𝑣𝑁 𝜽,𝑢≤𝑣• 𝑁 𝜽 is a normalization term:• 𝑁 𝜽 : = ∫ 𝑝 𝒙1 ∫ 𝑝 𝒙2 exp σ𝑢,𝑣 𝜽⊤𝑢,𝑣 𝒇 𝒙𝑢,𝑣𝑑𝒙2 𝑑𝒙𝟏
15

Learning Pairwise Partitioned Ratio• 𝑁 𝜽 can be approximated by U-statistics(Hoeffding, 1963)
1𝑗,𝑘⊤෡
• 𝑁 𝜽 ≈ 𝑁 𝜽 = 2 σ𝑗≠𝑘 exp σ𝑢,𝑣 𝜽𝑢,𝑣 𝒇 𝒙𝑢,𝑣𝑛𝑗𝑘

• where 𝒙[𝑗,𝑘] = 𝒙1 , 𝒙2.

Maximum Likelihood Mutual Information:(Suzuki et al., 2008):
𝜃መ = argmax 𝑃X log 𝑔 𝒙; 𝜽 − 𝜆 ෍ ||𝜽𝑢,𝑣 ||2𝚯𝑢,𝑣Included for sparsity
16Outline
1. Markov Network
2. Partitioned Markov Network
3. Learning Partitioned Markov Network
4. Experiments
5. Conclusion

17

Experiments: Bipartisanship• Learn the Bipartisanship in U.S. 109th senate.
• 45 Democrats, 55 Republicans.
• PMN learned over 645 recorded votes (Yea, Nay, not voting).
• Increasing regularization parameter until more than 15 edges.

vote agreement
vote disagreement18Outline
1. Markov Network
2. Partitioned Markov Network
3. Learning Partitioned Markov Network
4. Experiments
5. Conclusion

22

Conclusion• We learn interactions across two groups ofrandom variables.
• Such interaction is expressed via Partitioned
Markov Network.
• Learning sparse factorization of Partitioned
Ratio leads to the discovery of interactions
between two groups.

23