MIT CSAIL实验室新算法：能在损坏数据中寻找模式

包括 MIT 计算机科学与人工智能实验室（MIT CSAIL）的研究员在内一组团队创造出了一系列新算法，能够高效的在高维数据中拟合概率分布。

数据分析，尤其是大数据分析，大多是将数据拟合到数学模型的问题，最熟悉的例子就是线性回归，也就是找到数据点近似分布的线。将数据拟合到概率分布，比如贝尔曲线，也很常见。

然而，如果数据集只有一些损坏的条目，也就是说损坏的难以测量，标准的数据拟合技术就不行了。该问题在高维数据或带有许多变量的数据中更为严重，而这类数据在数字化时代又是普遍存在的。

众所周知，从 20 世纪 60 年代早期开始，就有一些算法能够除掉高维数据中的损坏数据（corruption），但过去 50 年提出的算法没有一个在变量超过 12 的时候很实用。

该进行改变了。在本月初，来自 MIT CSAIL 实验室、南加州大学、加州大学圣迭戈分校的一组研究人员在 IEEE Symposium on Foundations of Computer Science 上展示了一系列新的算法，能够高效的在高维数据中拟合概率分布。

引人注目的是，在同一会议上，来自 Georgia Tech 的研究人员提出了一个非常类似的算法。

在能够忍受损坏数据的「稳健统计」或统计方法上的首创工作是由统计学家完成的，但新的论文都来自一堆计算机科学家。这可能反射出该领域内注意力的转向，开始注意模型拟合技术的计算效率。

MIT Rockwell International Career Development 助理教授 Ankur Moitra 说，「从理论计算机科学的优势来看，很明显一个能被有效解决的问题有多稀少。如果你从假设作为开始，就会很糟糕，因为这是低效的。你应该从你知道你能高效进行的事情开始，并搞清楚如何将它们合在一起从而更稳健。」Moitra 也是 MIT-USC-UCSD 项目的领导者之一。

抵制损坏数据

为了理解稳健统计之后的原理，Moitra 解释说想想正态分布，贝尔曲线，数学的说法也就是一维高斯分布。一维高斯分布完全由两个参数所描述：平均值和方差。

如果数据集中的数据（假设是给定人群的身高）能被高斯分布很好的描述，那平均值就是算术上的平均。但假设你有一个包含 100 位女性身高的数据集，其中大部分身高是 64 英寸，一些很高，一些很低。其中一人的身高因某些原因达到 1000 英寸。用算术平均得到女性平均身高是 6.4 英尺，不是 5.4 英尺。

一种避免这种荒谬结果的方法是评估平均值，不采用数据的算术平均，而是找到其中值。使用中值评估平均值的算法要更为稳健。

中值只是平均值的近似值，而且随着变量的增多该近似的准确率会急剧下降。大数据分析可能需要测试千个甚至百万个变量。在这种情况下，平均值的中值近似法基本不能用。

异常点识别

一种将高维数据集中的损坏数据清除掉的方法是采用数据图的 2-D 交叉界面，并观察它们看起来是否像高斯分布。如果不是，你可能置入了一类假的数据点，比如 80 英尺高的女人，这些数据点可被轻易的切除。

问题是，将先前已知的算法应用到该方法时，找到损坏数据所需要的交叉界面的数是维度量的一个指数函数。相比之下，这组研究人员发现一种算法，这种算法的运行时间随着数据维度的数量以更合理的比率增长（计算科学术语来讲就是 polynomially）。

他们的算法依赖两种洞见。首先是在测量数据集离分布范围（近似同样的形状）多远时使用什么 metric。这能让他们分别是否淘汰了足够的损坏数据，从而更好的拟合。

另一种洞见是如何识别界面开始交叉时的数据的区域。为了做到这一点，研究人员依靠被称为分布的峰态（kurtosis of a distribution）来测量其 tails 的大小，或者说是数据距离平均值降低的速率。再次强调，有多种从数据样本中推断 Kurtosis 系数的方法，选择正确的一个是该算法的核心。

研究人员的这种方法能结合高斯分布，也能结合其他常见的分布——乘积分布（product distribution）。他们相信该方法可被扩展到其他类型的分布上，在接下来的研究中，他们将主要关注将该技术用到真实数据上。