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

Equality_of_Opportunitiy - 副本.jpg

包括 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)。他们相信该方法可被扩展到其他类型的分布上,在接下来的研究中,他们将主要关注将该技术用到真实数据上。

产业MIT算法理论数据科学数据管理
暂无评论
暂无评论~