本文考虑从数据中学习最大似然多叉树的任务,首先证明了最优分支(或 Chow-Liu 树)是最佳多叉树的很好近似,随后证明了该学习问题是 NP 难的,甚至在某些恒定因子的近似解中也无法很好地解决。
Jan, 2013
本研究介绍了一种基于干预实验数据的一致且可扩展的本地方法,用于学习线性高斯多叉树的因果结构。该方法首先学习多叉树的骨架,然后定向其边缘,输出为代表真实潜在分布的多叉树的干预等价类的 CPDAG。我们使用二阶统计和低维边缘分布来实现骨架和定向恢复过程。通过对合成数据集的不同情景进行性能评估,并将算法应用于基因表达干预数据集,我们的模拟研究表明我们的方法快速且准确度高,能处理包含数千个节点的问题。
Nov, 2023
有限样本保证 + 边界度多树 + 高效算法 + 政权时间和样本复杂度 + 信息理论样本复杂度下界
Oct, 2023
该论文提出了一种基于高斯混合模型的数据学习算法,可用于密度估计、数据聚类、高斯混合参数估计等问题,同时考虑了高维情况下的实际问题。
Apr, 2010
在固定 $k$ 个任意高斯分布的混合物和常量级别的数据污染的情况下,我们提出了一个用于稳健估计的多项式时间算法。该算法的主要工具有基于平方和方法的有效局部聚类算法和允许 Frobenius 范数和低秩项误差的新型张量分解算法。
Dec, 2020
本文研究了高维图估计和密度估计问题,并使用基于森林结构无向图模型的一族密度估计器。对于图估计,研究了估计具有限制树大小的森林的问题,并开发了一种近似算法。
Jan, 2010
本文介绍了用于两种基本高维学习问题的新型、计算有效和差分隐私算法:学习多元高斯分布和在布尔超立方体上学习乘积分布。我们的算法的样本复杂度几乎与这些任务的最优非隐私学习器的样本复杂度相匹配,表明隐私在这些问题上是几乎免费的。
May, 2018
本文解决了高维度任意固定数目成分的高斯混合分布在多项式学习方面存在问题的问题,提供了降维方法来将学习高维混合分布降至低维学习问题,并利用实代数几何学工具提供了多项式族分布的学习方法。
本文提出了新的学习算法,利用树状张量网络在最小二乘法下逼近高维函数,通过使用基于多变量函数的主成分分析的一般化,给定张量网络的维树或结构,提供一种生成嵌套张量子空间序列的算法,通过使用从先前生成的子空间依赖的分布生成的样本计算投影。提供期望下的误差界限。提出了适应特征空间和等级以达到规定误差的实用策略。还提出了一种通过合适的变量配对逐渐构建维度树的算法,允许进一步减少达到该错误所需的样本数。数值实验说明了所提出算法的性能,并表明可以得到稳定的逼近值,样本数接近于估计的张量网络的自由参数数目。
Apr, 2021
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020