Learning Juntas under Markov Random Fields
This work addresses a fundamental challenge in machine learning by enabling efficient supervised learning through structure learning of undirected graphical models, which is novel but incremental as it builds on existing smoothed analysis techniques.
The paper tackles the problem of learning juntas under Markov Random Fields (MRFs) by providing a polynomial-time algorithm that works in a smoothed analysis framework with perturbed external fields, generalizing prior work on product distributions. The result is an algorithm that efficiently learns O(log n) juntas, combining unsupervised structure learning with greedy supervised learning.
We give an algorithm for learning $O(\log n)$ juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework where only the external field has been randomly perturbed. This is a broad generalization of the work of Kalai and Teng, who gave an algorithm that succeeded with respect to smoothed product distributions (i.e., MRFs whose dependency graph has no edges). Our algorithm has two phases: (1) an unsupervised structure learning phase and (2) a greedy supervised learning algorithm. This is the first example where algorithms for learning the structure of an undirected graphical model lead to provably efficient algorithms for supervised learning.