论文标题
有效地学习和测试潜在树模型
Learning and Testing Latent-Tree Ising Models Efficiently
论文作者
论文摘要
我们提供了用于学习和测试潜在树模型的时间和样品效率算法，即只能在其叶子节点上观察到的Ising模型。在学习方面，我们获得了学习的有效算法，用于学习树的结构化ISING模型，其叶子节点分布在总变化距离上接近，从而改善了先前的工作结果。在测试侧，我们提供了一种有效的算法，该算法的样品较少，用于测试两个潜在树模型是否具有在总变化距离处接近还是远距离的叶子节点分布。我们通过在树结构模型的叶子节点分布之间显示出新的定位结果来获得我们的算法。
We provide time- and sample-efficient algorithms for learning and testing latent-tree Ising models, i.e. Ising models that may only be observed at their leaf nodes. On the learning side, we obtain efficient algorithms for learning a tree-structured Ising model whose leaf node distribution is close in Total Variation Distance, improving on the results of prior work. On the testing side, we provide an efficient algorithm with fewer samples for testing whether two latent-tree Ising models have leaf-node distributions that are close or far in Total Variation distance. We obtain our algorithms by showing novel localization results for the total variation distance between the leaf-node distributions of tree-structured Ising models, in terms of their marginals on pairs of leaves.
