我们研究了学习无向高斯树和有向高斯多叉树的最优算法,考虑了分布学习和结构学习两个问题,通过推导出显式的有限样本保证并给出匹配的下界证明两种方法的最优性,同时进行了数值实验以比较各种算法的性能表现。
Feb, 2024
本研究介绍了一种基于干预实验数据的一致且可扩展的本地方法,用于学习线性高斯多叉树的因果结构。该方法首先学习多叉树的骨架,然后定向其边缘,输出为代表真实潜在分布的多叉树的干预等价类的 CPDAG。我们使用二阶统计和低维边缘分布来实现骨架和定向恢复过程。通过对合成数据集的不同情景进行性能评估,并将算法应用于基因表达干预数据集,我们的模拟研究表明我们的方法快速且准确度高,能处理包含数千个节点的问题。
Nov, 2023
本文考虑从数据中学习最大似然多叉树的任务,首先证明了最优分支(或 Chow-Liu 树)是最佳多叉树的很好近似,随后证明了该学习问题是 NP 难的,甚至在某些恒定因子的近似解中也无法很好地解决。
Jan, 2013
从有可能被破坏数据中学习普通离散贝叶斯网络的确切骨架的问题,我们建立在分布鲁棒优化和回归方法基础上,提出通过在有界 Wasserstein 距离或 KL 散度内的一族分布上最小化最不利风险来进行优化。该最坏情况风险考虑了异常值的影响。该方法适用于一般的分类随机变量,无需假设真实性、顺序关系或特定的条件分布形式。我们提出了高效的算法,并证明了所提出的方法与标准的正则化回归方法密切相关。在渐进保证下,对于有界度图,我们证明了具有对数样本复杂性的成功结构学习。通过对合成数据集和真实数据集的数值研究验证了我们方法的有效性。代码可在 https 的 URL 中获得。
本文提出了可分解先验,一种针对树形信念网络的先验族。在完整观测数据下,可以通过贝叶斯学习来确定结构和参数,后验概率也是可分解的,并且可以在多项式时间内完全确定。
本文探究了基于树结构的重建问题上低项式多项式的性能,并显示了与基于多项式的算法相比其存在的限制,此外还提出了相关的开放性问题.
Sep, 2021
研究了在部分样本被恶意破坏的情况下学习贝叶斯网络的问题,在这种情况下,提出了第一个计算有效、维度无关的鲁棒性学习算法,样本复杂度接近最优,能够实现线性比例的错误率,该算法在合成和半合成数据上表现良好。
Jun, 2016
本文研究从数据中学习离散变量贝叶斯网络的算法的复杂度结果,结果表明即使具有独立性、推理或信息神谕,识别高得分的结构也很困难,负面结果也适用于每个节点最多有 K 个父母的离散变量贝叶斯网络,其中 k > 3。
Oct, 2012
本研究开发了一种递归约束算法,能够高效地将结构性边缘信息引入学习贝叶斯网络 (BN) 的过程,并提供了该算法的理论保证,进一步表明有界树宽 BN 可以在不增加复杂度的情况下学习。
Dec, 2021
该研究建立了 PAC 学习高维图模型与图结构计数和采样的新联系,使用在线学习框架,给出了新的样本复杂度界限以及面向树形和给定和弦骨架的贝叶斯网络的多项式样本和时间算法。
May, 2024