美国密歇根州立大学终身教授金榕：大数据的挑战与随机机器学习算法

【CSDN现场报道】2015年12月10-12日，由中国计算机学会（CCF）主办，CCF大数据专家委员会承办，中国科学院计算技术研究所、北京中科天玑科技有限公司与CSDN共同协办，以“数据安全、深度分析、行业应用”为主题的 2015中国大数据技术大会 （Big Data Technology Conference 2015，BDTC 2015）在北京新云南皇冠假日酒店盛大开幕。

2015中国大数据技术大会首日全体会议中最后一个演讲者是美国密歇根州立大学终身教授金榕，他的演讲主题是“随机机器学习算法——让大数据上的不可能变为可能”。演讲期间，他首先指出了时下机器学习所存在的主要挑战——数据体量和高维数据，随后他对随机算法、随机投影、对偶随机投影等方面进行了详细介绍。金榕在演讲最后进行了展望，主要包括三个方面：Impossibility定理存在于多种随机机器学习方法；研发新的理论和方法提升这些随机方法的下界；应用这些改进的随机机器学习方法。

美国密歇根州立大学终身教授金榕

以下为演讲实录

金榕：我今天主要分享机器学习算法，在过去的十年里，不管在学术界还是工业界有一件非常大的飞跃性事情，我觉得很值得讨论一下。那就是大数据，怎么处理大量数据中的信息，让有用的价值能够被社会充分的利用起来，这是今天分享的重点。我们通常说大数据都是说数据量很大，来自《ComputerWorld》的数据显示， 2012年已存在 2.7ZB 数据，而在2020年将达到 40ZB 数据； 另外一个是数据量快速，例如网络用户每分钟都产生大量数据： YouTube用户上传超过300小时新视频、SnapChat用户传递 284,722篇信息、Facebook 用户共享4,166,667篇内容。再者，数据是高维的，例如在图像分类和在线广告任务中，经常使用上百万维的特征。

数据规模的重要性

数据在不断地增长，数据量很大的时候是非常重要的一件事情，因为数据只有到了一定的程度的量才会发生质的变化，有一个例子是Matrix Completion（矩阵补全），就是给你一个表，有一部分的数据你知道，有一部分数据你不知道，没有办法拆出来，这个东西就是矩阵补全。矩阵补全非常重要，几乎所有的机器学习的问题都可以表示成矩阵补全的问题，这里显示的聚类，也可以看成矩阵补全。

矩阵补全非常有意思的结果是怎样的？我们这边的横轴是数据量，考虑在矩阵里能够看到的数据量，纵轴是恢复误差，拆出来的结果和真实结果的误差，肯定是数据量越多拆的误差越高，当数据低于一定程度的时候，这可以是非常显示的刻划出来，在数据小于一定量的时候，不管怎么做总是拆的很糟糕，几乎没有太大的区别。只有当你的数据大于一定量的时候，突然你可以拆的非常准，如果按原来的说法，在一个的情况下，你可以拆的很完美，没有任何的错误。所以我们说大数据，只有当数据到一定的程度的时候，有些事情才是可能的，当你的数据小于这个的时候，不管你怎么做都永远不可能。

大数据带来的困难

我们大家一直在谈大数据的挑战，来到阿里之前我没有意识到，来了之后觉得这个事情真的是big deal。做任何统计是最重要的一件事情，比如这里非常基础、简单的任务——矩阵平均，即便只是简简单单地做大数据下的平均，也是一个big deal，每一个矩阵都是很大（1Bx1M）。在应用里头，这个矩阵记录了每个人对每个商品行为的矩阵，这个矩阵是非常大的，但每天记录下的矩阵是很稀疏的，虽然说你有几百万几千万的商品，但通常每个人只有在很少量的商品上的行为，你希望把这些矩阵加起来，平均表达出在一个人在很长的周期内的行为是什么样的，但是一个disaster就发生了，如果矩阵做一个平均、求和，这个矩阵会变成一个death的矩阵，如果不做任何smart commutation，这个事情实际上是非常昂贵的，而且存储也是昂贵的。我在阿里的第一件事情，就是我能不能做一个这样的平均，我虽然不能算出确切结果，但有没有办法说我可以算出大概结果？最后一个很简单的办法，就是用一个随机算法做这个事情。

随机算法的好处

所谓的机器学习问题（Learning Problem），一般的机器学习问题会写成这样的形式，考虑有一堆训练样本，有一个叫Lost Function，用来比较预测和现实的差别，并分析这些差别。通常，Learning Problem就是找到一个解，确认这个解能够给出正确的预测和训练样本，通常可以把它变成一个优化问题来做。

解决该问题的主要挑战在于两个方面：一个方面是样本数量很大（1Bx1M），还有一个问题是维度非常高，通常来讲都是亿级，要解决的不会是一个简单的问题。一个成熟的解决方案就是随机算法。相信很多人都有意无意地使用到随机算法，比如用LR、SGD。

随机算法有两个好处：

1. 随机算法的Efficient，包括两个方面，第一个方面是即使针对大规模样本也 不需要多次扫描数据，另一个方面，如果是非常高维的数据，一个简单的办法是可以使用随机投影（Random Projection）来降低维度，这样可以不用直接解决高维问题；
2. 随机算法的Effective，就是它通常有最小化泛化误差 (Generalization Error) ，不仅仅是计算简化，同时也可以提供很强的保证。

随机算法的挑战（以随机投影为例）

随机算法很好，但是总体来讲，随机算法还是有很多的局限的，我的演讲用一个很简单的随机投影问题来讨论，来看一下随机算法的问题在哪里。

随机投影是一种非常简单的方法，而且应用广泛。一个高维矩阵X，long long vector，处理起来很麻烦，计算量很大，而且可以证明优化收敛速度跟维度是有关系的。一个简单的做法，针对非常长的vector，乘上一个非常fat的随机矩阵S，乘完以后得到一个很短vector的X point，很低维度的表示，就把这个X point变成我的数据，用低维的数据来优化问题，在低维空间学习。这个好的解是一个很矮的vector，我还要回到原来的空间上去，把原来的矩阵转置一下，又变成一个很长的vector，就变成最后的解。几乎所有的random projection都可以这么做：把一个（很长的）vector用一个随机矩阵变成一个很短很短的vector，算出一个解来，再把矩阵转置，把最优解一乘就可以了。这是一个非常简单的算法，是使用广泛，而且有无限多的paper分析这个东西有没有效。几乎所有的paper都告诉你这个东西很有效，也可以证明它很有效，但是我觉得所有的paper都很理想化，通常会假设原来的问题是一个很容易解的问题，可以证明所有的东西都是对的，但不幸的是，如果你的问题是比较难分类的问题，它告诉你的所有story都是假的。所以这其中隐藏了一个非常有趣的几何泛函的问题，一百多年前就已经被well study。也就是说，这个W star是真正的最优解，把所有的高维数据放进去让机器run获得的最优解，而所有W star cute就是刚才说的用随机投影的算法降维得到的解，你可以证明这两个解通常会有非常大的差别，这个差别跟原来的vector应该是一个数量级的。

所以说run随机投影的算法拿到的解，跟原来的解有很大的差别。这是不是因为我描述了一个非常特定的过程，这个中间的过程造成这个解不好，所以是不是尝试一下变化一个问题就有机会拿到更好的解呢？非常不幸地告诉你，这是不可能的，这也就是我说的Impossibility Theorem，可以证明这个事情不管怎么玩，只要做随机投影，不管你怎么去解这个w star cute，这两个解永远是差别很大，这和怎么解的问题都没有半毛钱关系。而且非常奇怪这个东西一百多年前都知道了，不知道为什么没有人提出来。但是对我来说这个事情很有意思，我能不能做其他的事情，稍微加一点限制，就能让我这个疏密的问题解掉？

对偶随机投影的优化

这是五年前让我很感兴趣的一个问题，我们创造了一个对偶随机投影 (Dual Random Projection)，非常简单、非常神奇，把随机投影得到的w star cute这个解塞到每一个Lost Function里去，然后去求一个导数，这里称为alpha i，最后的解是用每一个training instance和alpha i对应，所以你需要做的，不是直接采用随机投影得到的解，而是用随机投影的解去算它的对偶变量，用对偶变量去win每一个training instance。

如果take原来的解，加上这个对偶恢复（Dual Recovery）的东西，可以证明结果和实际最优解之间的差距非常小。并且我们可以看到从这个过程中没有多加太多的计算量，one more time就可以给出这个解。我想用这个例子说明，这些由于Impossibility造成的困难有时候是可以克服的，对我来讲这应该是一个非常重要的事情。

结果验证

我举一个很简单的例子，我当时用的比较短的空间维数（N=50,000，d=20,000，r=10），从图中大家可以看到，如果直接用随机投影，error一直很高，但是做一个Dual Recovery，error就很低了。

这个就是我们用到RCV1 data set（800,000 文本， 40,000 特征），如果你的维数很小直接用随机投影，你的Accuracy非常低；但是如果你愿意走one more step，就是Dual Recovery Step，你可以大大提高Accuracy。

以前在2003年的Fine-Grained Challenge上头，我们也使用它，所谓的Fine-Grained，不是简简单单地把image区分成一个个的鸟、花、狗、鞋子、汽车……，还需要知道这是具体的什么鸟、什么类型的花。当时用了一个所谓的度量学习设计我们的方法，但是维度应该是到了百亿级，所有的计算都是使用对偶随机映射大幅提升计算速度，最后的Accuracy如图。

应用: 在线展示广告

最后展示一个在线展示广告的应用。在线展示广告包括商铺、用户、平台三个要素。商铺（供给方）方面，通过挑选Tag来选择潜在客户；用户（需求方）方面，通过分析用户行为，为每个用户打上合适的Tag，平台方面，通过标签将广告分发给合适的用户。

通过常用的贪心算法，则需求/供给不匹配：有些目标，用户有强需求，但迫于商家的广告预算，只有较弱供给；有些目标，用户的需求较少，但是商家的广告供给较多。因此，需要为每个用户找最合理的标签，最大化收入和最小化供需不匹配，是一个规模巨大的优化问题。

借助对偶随机投影，上十亿的用户，数千标签，在2小时内获得结果，降低了供需不匹配，显著提升了广告收益。全局优化前后对比如图。

未来展望

展望未来，主要包括三个方面：

1. Impossibility定理存在于多种随机机器学习方法， 例如：主动学习、聚类、低秩矩阵分解……。
2. 研发新的理论和方法提升这些随机方法的下界，将理论上的不可能变成可能。
3. 应用这些改进的随机机器学习方法，将更多大数据上的不可能变成可能。