ACM通信

研究突出了

技术角度:高维数据建模

作者:Santosh S. Vempala
ACM通讯，2012年2月，第55卷第2期，第112页
10.1145/2076450.2076473
评论

高维数据很难可视化和理解。这种情况一直都是如此，现在随着大型高维数据集的可用性和对它们的理解的需要，这种情况更加明显。

理解数据的经典统计学方法是找到一个可以生成数据的简单概率模型。模型通常是一个大域上的概率分布，每个数据点都是独立于同一个分布产生的。虽然也研究了不假设独立同分布数据点的更复杂的模型，但独立数据模型占主导地位，在许多情况下都是合理的。如果没有进一步的假设，即使这个框架也不会很有用或有趣，因为遇到的数据分布可以被认为是均匀的。关键是对复杂的大数据进行建模简单的分布。找到这样一个匹配(如果存在的话)可能会给出一个深刻的解释，简单分布的参数甚至可能具有预测能力。

使用什么发行版?中心极限定理表明最合理的候选者是高斯分布。这是任何总分布最终会收敛的结果。事实上，试图找到一个最适合给定数据集的单一高斯是一个常用的和有效的方法。利用数据的均值和协方差矩阵估计高斯分布。不幸的是，这只在相当特殊的情况下有效。

因此，我们得到了一个在统计学中广泛使用的框架，称为混合模型．这里我们假设数据是由少量已知类型分布的混合产生的;最常见的假设是高斯混合。问题是找到与给定数据的少量高斯混合的最佳拟合。分量的数量，k，比n，环境维度。不同于单一高斯函数的情况(k= 1)，在这种情况下，估计潜在的高斯分布是很简单的，但对于一般情况，这个问题变得困难得多k．即使是双高斯混合的情况也会在很长一段时间内保持开放。

卡莱，莫伊特拉和Valiant^3.演示如何解决两个任意混合的问题n维高斯函数。除了依靠简单而巧妙的简化到两种混合的情况1-维高斯，他们的分析依赖于以下关于高斯混合物可识别的基本事实:两个不同的高斯混合物有不同的密度函数;随着两种混合物的密度越来越近，混合物也必须越来越近(一种混合物的平均值、方差和混合重量必须与另一种混合物的平均值、方差和混合重量近似)。这样的性质对于一般的混合物不成立，甚至对于分布良好的混合物，如具有log凹密度的混合物也不成立，但对于高斯混合物是成立的。此外，与经典的证明不同，他们建立了一个多项式的样本数量的界限，需要在期望的精度内识别混合物的成分。令人惊讶的是，这是对来自经典指数界的样本复杂性的第一个改进，尽管混合模型已经研究了一个多世纪。⁵

他们的方法的关键见解是表明有限的一组矩(对于两个1维高斯的情况，6个矩)足以识别分量。有了这个工具，他们考虑了几个随机的一维投影n-维混合，识别每个分量的投影，根据原始分量正确聚类，从而对原始分量收集足够的约束来估计它们的均值、协方差矩阵和混合权重。

在一篇后续论文中，Moitra和Valiant⁴将此方法扩展到混合k复杂度指数增长的高斯函数k，但在所有其他参数中多项式;因此，多项式时间算法的任何固定k．一个简单的指数依赖k是不可避免的，即使在样本复杂性中，至少如果目标是在没有分离条件下识别任意高斯混合的分量。Belkin和Sinha还在一个更抽象(和一般)的环境中独立地证明了一个类似的边界，其中可能包含非高斯分量。¹

以下论文中的工作解决了一个重要的开放问题，建立了基本事实，从而推进了经典统计学，并为计算机科学提出了非常有趣的问题;其中:我们希望对非高斯混合(对于一般鲁棒可识别性不成立)做些什么?我们能处理带有噪声的高斯混合物吗?换句话说，是否存在一种不可知论算法来学习高斯混合物?也许最有趣的是，什么合理的假设会导致完全多项式甚至实用的算法?(该领域的许多工作假设组件之间是分离的，这可能是为了效率而不可避免的;例如，给出了一个多项式时间算法，假设每个组分大部分可以通过超平面与混合物的其余部分分离;²一个干净的猜想是，任何概率可分离的混合物在多项式时间内是可识别的)。

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2012 ACM股份有限公司

---

没有发现记录