May, 2017

马尔科夫随机场的信息论特性及其算法应用

PDF
TL;DR通过建立适当的零和游戏，采用概念上的方法来证明相互信息的下限，进而推广到具有高阶交互作用的任意马尔科夫随机场，从而获得在 n 个节点上学习具有 r 阶相互作用的有界次数图上的马尔科夫随机场的算法，样本复杂度为 log (n)，时间复杂度为 n^r。
markov random fieldsising modelslearning algorithmsmutual informationbounded degree graphs
发现论文，激发创造
  • 均场近似：信息不等式、算法和复杂度

    本文提供了一种新的较优 KL 误差的均场近似上下界，并推广到高阶马尔可夫随机场。结合组合数学和优化技术，我们还研究了估计 Ising 模型及马尔可夫随机场自由能的算法问题。我们提供了多种算法，在多项式时间复杂度内误差均控制在某个界内。

    Feb, 2018

  • 高维下选择二元图模型的信息论极限

    研究二元马尔可夫随机场中，图形选择问题在高维情况下的信息论局限性，为具有最多 k 条边的 p 个定点图的类 $Gpk$ 以及最高 degree 不超过 d 的 p 个定点图的类 $Gpd$，提出了正确图形选择的必要和充分条件，并建立了一个图形译码器，该译码器适用于样本量 n>c'k² log (p) 和 n>c'd³ log (p)。

    May, 2009

  • 从样本中重建马尔科夫随机场：一些简单的观察和算法

    使用马尔可夫随机场重建算法重建依赖结构，并且在观察到低噪声时可获得高概率的成功率。

    Dec, 2007

  • 关于学习伊辛模型的信息论极限

    本文提出了一种计算 Ising 模型底层图形恢复的样本复杂性下界的通用框架，其中隔离出两个关键图形结构成分，可以用于指定样本复杂度下界。

    Nov, 2014

  • 使用乘法权重学习图形模型

    给出一种用于学习 Markov 随机场（MRF）或无向图模型的简单的、乘性权重更新算法 ——Sparsitron 算法，特别适用于学习 t 阶 MRFs 结构，并具有近乎最优的样本复杂度和多项式的运行时间。同时，该算法还可以学习 Ising 模型上的参数，生成接近真实 MRF 的统计距离假设，并给出了学习稀疏广义线性模型（GLMs）的解决方案。

    Jun, 2017

  • 马尔可夫网络结构的贪婪学习

    提出了一种新的自然算法，用于从样本中学习一般离散图形模型（即马尔可夫随机场）的图结构，它是一种贪心的算法，并且具有较低的计算复杂度，并且通过节点度数、图大小以及因子图的环来表征其样本复杂度，在此基础上将其专门用于 Ising 模型。

    Feb, 2012

  • 对称秩一矩阵估计的互信息：复制公式的证明

    该论文研究如何采用严谨的方法证明低秩矩阵的对称秩一情况的互信息，进而表达最小均方误差和表征检测相位转变；同时介绍了一种被称为近似消息传递的迭代算法在贝叶斯最优条件下的优越性，并提出了通用的解决其他问题的方法。

    Jun, 2016

  • 学习算法泛化能力的信息论分析

    本研究提出了一种基于信息理论的泛化误差上界方法，用以控制模型的输入输出互信息，进而指导在数据适配和泛化之间寻找平衡点。在此基础上，我们探索了一些方法，包括利用相对熵或随机噪声来正则化 ERM 算法等。这些方法扩展和改进了 Russo 和 Zou 的最近工作。

    May, 2017

  • 信息论泛化界的统一框架

    文中提出了一种利用概率去相关引理、对测度空间中的的概率测度进行对称化、配对和链化等技术来获得学习算法信息论泛化界限的一般性方法，进而得到新的期望值和高概率条件下泛化误差的上界，特别地，还包括了基于互信息、条件互信息、随机链和 PAC-Bayes 不等式等现有泛化界限的特例。此外，Fernique-Talagrand 上界也是一个特例。

    May, 2023

  • 形式语言和统计物理学中的临界性

    该研究论文阐述了对于正则文法的符号间互信息随符号间距离指数衰减的特性，然而对于上下文无关文法则符合幂律分布；并且将该现象与统计力学、湍流以及宇宙膨胀等领域的幂律相关性做了联系，以及阐述了这种现象在机器学习中的潜在应用。除此之外，该研究论文还提出了一种合理的互信息量的量化方式，并探讨了该现象在更复杂的贝叶斯网络中的推广。

    Jun, 2016