High-Dimensional Graphical Model Selection

Published on 2012-01-258312 Views

We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as

NIPS Conference 2011 - Granada

Presentation

High-Dimensional Graphical Model Selection00:00

Graphical Models: Definition - 106:27:24

Graphical Models: Definition - 214:19:13

Graphical Models: Definition - 318:39:27

Graphical Models: Definition - 418:56:00

Structure Learning of Graphical Models - 121:30:37

Structure Learning of Graphical Models - 228:50:58

Tree Graphical Models: Tractable Learning - 133:41:03

Tree Graphical Models: Tractable Learning - 236:42:26

Tree Graphical Models: Tractable Learning - 341:28:23

Tree Graphical Models: Tractable Learning - 441:34:19

Tree Graphical Models: Tractable Learning - 548:16:51

Learning Graphical Models Beyond Trees - 153:07:00

Learning Graphical Models Beyond Trees - 260:12:37

Learning Graphical Models Beyond Trees - 367:59:53

Learning Graphical Models Beyond Trees - 474:14:17

Related Work in Structure Learning79:11:44

Outline - 192:06:49

Intuitions: Conditional Mutual Information Test - 192:26:35

Intuitions: Conditional Mutual Information Test - 2100:15:47

Intuitions: Conditional Mutual Information Test - 3111:55:51

Intuitions: Conditional Mutual Information Test - 4113:40:11

Intuitions: Conditional Mutual Information Test - 5115:32:41

Tractable Graph Families: Local Separation120:03:09

Setup: Ising and Gaussian Graphical Models - 1174:04:29

Setup: Ising and Gaussian Graphical Models - 2174:26:50

Setup: Ising and Gaussian Graphical Models - 3174:43:30

Setup: Ising and Gaussian Graphical Models - 4174:50:43

Setup: Ising and Gaussian Graphical Models - 5175:05:20

Regime of Tractable Learning - 1183:40:20

Regime of Tractable Learning - 2184:00:05

Regime of Tractable Learning - 3201:06:07

Tractable Graph Families and Regimes - 1207:13:52

Tractable Graph Families and Regimes - 2207:33:42

Tractable Graph Families and Regimes - 3207:44:56

Tractable Graph Families and Regimes - 4207:53:16

Example: girth g, maximum degree Δ219:53:29

Algorithm for Structure Learning - 1235:51:52

Algorithm for Structure Learning - 2236:14:43

Algorithm for Structure Learning - 3249:59:22

Guarantees on Conditional Mutual Information Test250:39:57

Lower Bound on Sample Complexity - 1258:39:24

Lower Bound on Sample Complexity - 2259:24:05

Proof Ideas - 1261:31:32

Proof Ideas - 2261:45:04

Proof Ideas - 3261:59:40

Proof Ideas - 4270:14:40

Summary and Outlook270:36:50