提出首个在马尔可夫随机场中高效学习对数级混合函数的算法。
Learning Juntas under Markov Random Fields
- 分两阶段：先无监督学结构，再贪心有监督学习。
- 可在光滑化马尔可夫随机场中多项式时间学习 O(log n) 个混合变量。
- 首次实现图模型结构学习直接推动高效监督学习，适合理论学习者。
我们提出了一个在光滑分析框架下，针对外部场被随机扰动的马尔可夫随机场（MRFs），可在多项式时间内学习 $O(/log n)$ 个混合函数的算法。这推广了 Kalai 与 Teng 的工作，后者仅适用于无依赖关系的光滑乘积分布（即边集为空的 MRF）。该算法包含两个阶段：(1) 无监督结构学习；(2) 贪心有监督学习。这是首个通过学习无向图模型结构，从而获得可证明高效的监督学习算法的例子。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。