滴滴研究院副院长叶杰平 | 大规模稀疏和低秩学习

本文根据叶杰平教授在中国人工只能学会AIDL第二期，人工智能前沿讲习班-机器学习前沿所作报告《大规模稀疏和低秩学习》编辑整理而来 ，在未改变原意的基础上，略有删减。不足之处，望指正。

叶杰平，美国密歇根大学终身教授，密歇根大学数据研究中心管理委员会成员，美国明尼苏达大学博士毕业，现任滴滴研究院副院长。在NIPS, KDD, IJCAI, ICDM, SDM,  ACML, and PAKDD发表多篇论文. 他担任Data Mining and Knowledge Discovery, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Pattern Analysis and Machine Intelligence的编委. 2010年获得NSF CAREER Award。2010，2011，2012年分别获得KDD最佳论文提名，2013年获得KDD最佳论文奖。2014年获得ICML最佳学生论文奖。以下为叶杰平教授所做现场演讲的一部分， 主要对稀疏和低秩约束在机器学习上的应用进行了介绍。

大家下午好，非常高兴，能够和大家一起，分享低秩和稀疏两种方法，主要会讲解一些在large-scale方面的应用，也会稍微提一下滴滴的一些应用，大部分我讲的很多应用，都会用用在特征约减，与很多问题如滴滴，都会有很多样本，每天都有上千万的大规模数据量不同，很多问题有成千上百万维度的特征，如何对特征进行稀疏和低秩约束，是我们今天要讲的主要内容，今天的报告主要针对模型介绍，具体应用可以下面查阅文献，不会具体讲解。

本次报告主要对一些基础的稀疏模型，以及结构的稀疏模型进行讲解，并会简单介绍低秩的模型，以及一些优化加速算法，最后会给大家讲一下large-scale，以及如何将这些算法用在大规模的数据上。

大家可能都对稀疏的含义比较了解，这里的稀疏，可能表示模型特征的稀疏，也可能表示数据的稀疏，数据稀疏主要是指文件的keyword比较稀疏，这里我们主要是指模型特征的稀疏，比如说一维的线性回归或者矩阵，这里的稀疏就是指模型的特征会比较少。

我们引入一个正则的概念，通过一个简单的线性拟合，建立一条线来拟合样本点，假设有一个M阶的多项式来进行拟合，那么有M+1个参数需要估计，我们希望利用这个方式来进行预测优化，找到一个系数使得误差最小。对于每一点我们有一个预测值y，一个ground truth，通过优化M+1个变量，使得y与ground truth之间差异最小。当M为0的时候我们可以知道这是一条直线，当M等于3的时候就变成了一条曲线，等等。

通过实验结果。我们可以看到训练误差在M很大的时候很小，而测试误差很大，这也就是非常常见的过拟合的问题，M太小的时候，模型太简单，训练误差和测试误差都很大，这也就是欠拟合的问题，M取中间值时才会非常合适，这过拟合和欠拟合也是两个非常常见的机器学习问题。我们对这些系数进行分析，可以看到在，当M等于9的时候，系数非常大，也可以发现，如果overfit的情况，如果稍微抖动的话，会对系数有非常大的影响，自然而然的，我们需要对我们的模型加一个正则项，从而通过控制系数的大小，向可以接受的误差逼近，通过数据拟合项的范式约束，使得模型的误差变小，模型能够更加的拟合数据，再加上一个控制系数的正则项，使得模型的参数更加稳定。超参数λ用来控制稀疏的程度，当超参数λ等于0时，模型也就退化成了一般的线性回归，λ一般需要通过调节参数学习出来，通过实验可以发现，λ比较小的话模型就会容易过拟合，λ比较合适的话模型就会比较稳定。

通常，我们利用正则项来控制参数W的大小，这里可以用q norm作为正则项，来保证W比较小，当q=2的时候能够保证W有一个光滑的解析解，q=1时，正则项是一个凸函数，且能够使得W稀疏；q在大于等于1 的时候，该模型仍然是一个凸函数，好处就是能够保证找到最优解，q小于1时，模型就变得非凸了，但是能够找到一个稀疏解。

自然地，我们就要思考为什么L1范式能够得到一个稀疏解，这里我们给出一个简单的例子，前面时loss函数，后面是正则项，可以看到一范式为凸但不可微，会在x＝0时取到极值点，二范数在零点可微，但是不一定在零点取得极值点，另外一种对于一范数稀疏的解释是通过等高线的方式，可以发现一范数的约束能够使得loss函数在零点相交，而二范数是一个球，不一定与loss函数在零点相交，从而一范数能够使得解稀疏。

一范数最经典的就是96年的LASSO问题，我们有数据矩阵A，每一行代表样本，列代表特征，有标签y，可以代表分类和回归问题，我们这里用一个简单的线性模型取取预测y，呢么Ax-y就是一个拟合项，一范数就是正则项，使得x的系数稀疏，从而去掉一些无关项，如对疾病不相关的基因，从而增强了模型的可解释性，自动做了特征选择，有效的避免过拟合，这样子，稀疏可以同时选择特征，并且建立了模型。下面我们会讲一些结构性的计算，这个模型能够同时作特征选择和进行回归或分类。这里我们举一个在MRI上面的应用。利用简单的logit回归，加上一个稀疏先验，利用MRI图像进行病人和正常人的分类，并且同时实现了探寻哪一些脑区信号与疾病的相关与否，找到了与疾病相关的一些特征，之前提到的y都是比较简单的，只有一列，但是很多场景下，y可能有很多值，我们特征可能时很多的特征，y可能是1维的比如说有病无病，也可能多维的比如说每个脑区的一些判别，这样不仅每个点都是多维的，label也可能是有很多维，这样就是一个两边都是多维的big data问题，模型也从从一个一列，变成了一个矩阵，扩展了一个平方的关系。如果不增加正则项，这种问题将会非常难以解决。假设有一千个数据，x和y都是一百万维，这个模型就会是一个非常大的矩阵，如果没有正则项，这个模型将几乎无法求解。需要加入很多的假设，如低秩假设，这个模型也就可以对数据矩阵进行分解，也就使得我们的维度降低，最后在假设稀疏，进一步降低了系数的维度，现在的数据量都比较低，特征特别大，我的一个合作者进行了一个比较大的项目，把所有的数据整合在一起，有两三万个数据，但仍然不算很多，未来的数据如果越来越大的话，模型会越来约精确，现有数据不足，所以只能对模型加入很多假设，从而保证模型的有效性，当然，数据还是第一重要的。

系数学习在很多领域中都有很广泛的应用，如生物医学，图像处理，neuroscience，机器学习等等，我们最终的目的是找到一个超参数，一个常用的方法是使用交叉检验，在一个广泛的超参数空间中，选择一个最优的超参数，这种方法可能会存在一种缺陷，一个更好的方法是使用stability selection. 相当于对每个数据进行子采样，然后进行多次筛选，选择最好的参数，具体的可以在文章中查阅，里面有很强的理论证明。它会对问题进行很多子采样，所以会进行很多次的lasso求解，因此需要一个特别快的算法，这也是我们今天主要要讲得，如何在大规模的数据上进行计算。

刚刚对基础进行了讲解，下面我们对几个模型进行讲解，刚刚提到过LASSO可以同时解决提取参数和预测两个任务，并且具有是的提取的特征具有理论可解释性，同时非常容易推广。我们知道，很多特征是有结构的，特征与特征之间并不是独立的，特征之间是可以分组，我们首先介绍一些结构LASSO，这里给出一个例子，特征之间会有光滑性，我们给出了一个所有脑区的特征，我们可以发现向邻近的点会比较类似，特征的光滑性有时间和空间上的光滑性，比如说，相邻时刻之间的数据以及相邻空间的数据是具有相似性的，所以很多问题都是有光滑性的，也会有一些问题具有一些树的结构，以及一些问题可能具有一些网的结构，得到特征值之间的相似性。当我们获得我们的这些特征之间的先验知识之后，如果对lasso进行推广，利用我们的特征之间的信息，结构的lasso也就应运而生。和lasso类似，损失函数可以根据问题相关设计，如logit回归或者最小二乘回归等等，来表示对数据的拟合程度，重点是如何设计我们的penalty，lasso是L1-norm，仅仅是稀疏，特征之间没有任何假设，但是如果我们有特征直接结构的先验知识，那么我们可以在正则项这里进行推广，一般是利用一个凸的方法，来得到我们需要的结构，这里我们根据结构的先验信息，有Fused LASSO（光滑性），Graph LASSO（图结构）, Group LASSO（组结构）以及树结构LASSO（树结构）。

考虑到光滑性，可以通过增加一项差分项的方式，有效的保证相邻的两项是相近的，参数是类似的，最终的结果我们会发现最后的结果相邻的系数都是相同的。每一段都是一个常数，而且很多都是稀疏的，这样子就能够简化模型，降低模型的复杂性，同时实验发现，这种方式能够有效的提升符合这种特点的数据的效果。

第二个推广是考虑到很多数据的特征是相关的，比如说是蛋白质的特征之间是相关的，类似fused LASSO，我们增加一个penalty，使得相关的特征具有相同的结构，考虑到相关性可能是反向，可以增加一个绝对值解决这个问题，解决相关但是符号不一致的问题，这个问题会稍微复杂一点，是一个非凸问题，同样在试验中，我们发现，加了graph结构之后，模型效果会好很多。

第三个推广是很多特征会有一种组的结构，最典型的应用就是在脑影像的分析中，很多脑区或者体素之间有一定的组约束的，同时滴滴也有很多场景，如司机，终点，天气等等，还有基因的categorical variable。我们可以很多特征必须放在一组里才有一定的意义。因此group LASSO也就应运而生来解决这种存在组结构的问题， 解决思路是，通过L1-norm来筛选特征，如果有这种组的先验信息，可以先提供对这些组先计算Lp-norm，在计算这几个group的L1-norm，在通过加入这种形式的penalty，会使得相同组的要么全为零，妖媚全部被调出来。具体的应用就是multi-task，假设我们有k个task，每一行做一个group，然后用L1Lp做penalty，这样会使得该特征对于所有的task要么都被提取，或者同时不被提取。比如说手写字符识别，有两种极端是，一种是把所有的字母放在一起，进行训练，另外一种是每个人建立一个不同的模型，第一个模型不能有很好的泛化性能，第二个模型会导致模型很复杂，而且每个人的数据可能不足，而multi-task是介于两者之间的一种方式，希望建立每个人的模型是相关的，每个模型提取的特征是一样的，可以看到，字符识别的结果相较之前的两种方法都要好。

很多时候，简单把各个特征简单的分成各个组可能是不够的，特征之间可能会有一些更加精细的结构，比如说分层的结构，这样子特征之间会有更多的信息，如果特征的相似性具有一种树结构，那么简单的使用group LASSO 效果就不好，因此我们就需要引入树的特征，这样会使得模型有更好的效果，这里简单举一个例子，假设每个样本是一个图，最上层就是整个脑区，在树的最顶端，如果我们对脑区进行划分，类似的可以继续的继续划分，一直到体素，这样子就会组成一个树的结构，如果两个体素在同一个树下，它们的特征就会很类似，如果它们不类似，那么就说明它们距离很远，这样子就是一个树的特征。我们也就可以基于此，建立一个树的lasso，每一层做一个group 的LASSO，这样会使得如果上层为零，那么，该结点的所有连接都会为零，在脑影像上面的实验也表明，树约束能够使得我们挑出的特征聚集在某一些脑区，使得模型结果更加具有可解释性。

下面讲一下低秩模型，这里会将的快一些，我最后会讲一些screening，有很多问题都可以用矩阵来表示，很多时候，矩阵中的一些值是未知的，因此需要用观测值去预测丢失值，比如说图像，可能会有一些图像被树覆盖，需要用观测值去预测被遮挡的部分。或者说collaborative filter，行代表用户，列代表等级，每个用户被要求给电影打分，但不是所有的用户都对所有的电影打分，所以我们需要去预测这些缺失的数据。再考虑netflix问题，很多打分都是丢失的，我们如何用有限的数据来预测大量的缺失的数据。如果不做任何假设，这个问题是很难解决的，因此，我们引入低秩假设。对于每个问题，首要核心的问题是少量的低秩的。Rank可以通过SVD分解，通过非零的奇异特征数就是矩阵的rank。我们希望的模型就是希望矩阵的秩比较小。

低秩模型与稀疏模型比较类似，这里我们假设红色的是观测点，白色为缺失点，X是我们需要预测的，该问题第一项为数据拟合项，我们需要M与X类似，同时希望我们填补之后的X能够保持低秩特性，是的主要因素数量比较少，并用λ控制这个数量。由于rank是非奇异的，因此问题的求解会存在问题，是一个NP-难问题，常用的方法使用rank的上确界trace-norm来逼近它，同时trace-norm是一个连续的凸问题，使得问题更加容易求解，且能够使得奇异值变为零，最终低秩。

最近也有很多方法将其转变成为非凸的问题，将X转换成U和V相乘的形式，从而使得X的秩降低，通过求解U和V对X进行预测，，通过不断的固定U求解V在固定V求解U，最终收敛，这样求解更加快速。

还有一种方法是将X转换成类似SVD的形式，把矩阵转换为向量的问题，将矩阵X转化成r个秩等于1的矩阵相乘再相加，对X进行预测，使得矩阵X的秩小于r，从而保证低秩。

下面我们主要会讲一些优化的算法，比如lasso，结构的稀疏等等，模型大概会有怎么样的优化结果，我们处理的很多问题都是连续凸不可导的问题，主要会讲一些流行的解放，并介绍一些加速算法。

我们的问题几乎都可以分解成为loss 和penalty的形式，假设loss是可微的凸问题，penalty是不可到的凸问题，目前主要有以下解决方法：1）将不光滑的问题转化为光滑的问题，2）坐标下降方法，3）ADMM算法，4）次梯度下降，5）梯度下降，6）加速梯度下降等等。下面会主要讲解坐标下降以及ADMM。

坐标下降算法的想法很简单，假设模型有一百万维的数据，需要优化一百万维的数据，那么我们会每次只优化一维的特征，依次优化，不断迭代，一直到收敛。很多大问题的解法可以用这种方法很快速的求解。

当问题是光滑且凸的时候，坐标下降算法一定可以收敛，当问题不光滑的时候，当不光滑的部分是可分的，那么坐标下降算法也可以收敛。坐标下降算法的有点事可以很容易的计算，同时能够非常快的收敛。但是缺点是当loss比较复杂时，会很明显的降低速度，且不一定有解。

快速讲一下ADMM，ADMM算法假设有两个变量fx＋gz，然后给定一个约束，将其放入两组变量，我们可以首先是生成增广拉格朗日，再增加penalty，从此就可以通过反复依次对xzy优化对模型求解。