Distribution Learning Meets Graph Structure Sampling
Arnab Bhattacharyya, Sutanu Gayen, Philips George John, Sayantan Sen, N. V. Vinodchandran
这项工作在PAC学习高维图形模型的问题与使用在线学习框架(高效)计算和图形结构的任务之间建立了一种新的联系。 我们观察到,如果我们使用日志损失函数将成倍加权平均值(EWA)或随机加权多数(RWM)预测器应用于分布P的序列样本,则预测者的预测产生的平均遗憾可用于绑定P和预测之间的预期KL差异。 EWA和RWM的已知遗憾界限,然后为学习贝叶斯网产生新的样本复杂性边界。 此外,这些算法可以在计算上对几个有趣的贝叶斯网类进行计算效率。 具体来说,我们给出了一个新的样本最优和多项式时间学习算法,用于未知结构的树,以及第一个用于在给定的和弦骨架上学习贝叶斯网的多项式样本和时间算法。
This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss function, the average regret incurred by the forecaster's predictions can be used to bound the expected...