Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Executive Committee 
 Postdocs 
 Visitors 
 Students 
 Research 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 P/T Colloquia 
 Archive 
 Ulam Scholar 
 
 Postdoc Nominations 
 Student Requests 
 Student Program 
 Visitor Requests 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Tuesday, July 13, 2010
10:30 AM - 12:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Seminar

A New Algorithm for Learning Markov Network Structure

Praneeth Netrapalli
UT Austin & CNLS GRA

Markov Random Fields (MRFs), a.k.a. Graphical Models, serve as popular models for networks in the social and biological sciences, as well as communications and signal processing. A central problem is one of structure learning or model selection: given samples from the MRF, determine the graph structure of the underlying distribution. When the MRF is not Gaussian (like e.g. the Ising model) and contains cycles, structure learning is known to be NP hard even with infinite samples. Existing approaches typically focus on the sub-class of graphs with bounded degree; the complexity of many of these methods grows quickly in the degree bound. We develop a simple new algorithm for learning network structure. It learns the Markov neighborhood of a node by sequentially, greedily adding to it the node that produces the highest reduction in conditional entropy. We show exact structure recovery when either (a) the graph is a tree, or (b) the MRF is an Ising model (under conditions on the degree / girth / correlation decay) In a sense, our algorithm does for learning what Belief Propagation (BP) does for estimation: provide a very low-complexity local algorithm that is exact for trees and has surprisingly good performance for many graphs with loops. Joint work with : Siddhartha Banerjee, Sujay Sanghavi and Sanjay Shakkottai

Host: Misha Chertkov