编者按：本文根据叶杰平教授在中国人工智能学会AIDL第二期人工智能前沿讲习班【机器学习前沿】所作报告《大规模稀疏和低秩学习》编辑整理而来。
叶杰平 滴滴研究院副院长 美国密歇根大学终身教授，密歇根大学大数据研究中心管理委员会成员，美国明尼苏达大学博士毕业，现任滴滴研究院副院长。他担任Data Mining and Knowledge Discovery, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Pattern Analysis and Machine Intelligence的编委. 2004年获得ICML最佳学生论文奖。2010年获得NSF CAREER Award。2010，2011，2012年分别获得KDD最佳论文提名，2013年获得KDD最佳学生论文奖。
以下内容是本次报告的上篇，由亚萌，夏睿共同编辑。雷锋网(：雷锋网)(：雷锋网)AI科技评论后续会整理出本次报告的下篇。
大家好！今天下午主要是跟大家分享这两个领域的研究：稀疏和低秩。这个报告跟滴滴的应用没有直接的关系。本次报告主要对一些基础的稀疏模型，以及结构的稀疏模型进行讲解，并会简单介绍低秩的模型，以及一些优化加速算法，最后会给大家讲一下如何将这些算法用在大规模的数据上。
Part 1 : 稀疏学习的一些基础概念稀疏学习的“稀疏”是指很多模型的系数是0，这里是模型比较稀，可以是一维的，线性回归，或者矩阵的模型。
先讲一下正则，从简单一个线性的拟合，有这么多点，用一条线去拟合这些点，这里我们简单用多项式（Polynomial），有M+1个参数，为了优化问题而把最佳的系数选出来。这个就是用线性回归，每个点有一个预测，预测是多项式给定，一个ground truth，我们希望找到系数，使这个误差最小，这是非常常用的方式。
当M=0或1的时候是一条直线，当M=3或9的时候就成了曲线。这里两条曲线，一个是在训练集上，一个是在测试集上，我们发现当M的值处于中间的时候，效果最好，两头都不行，这是机器学习里常见的问题。当M=9的时候，一下子出现了过拟合。
所以模型需要加一个正则项，控制系数的大小。我们希望这个曲线拟合这个数据，系数也不要太大，太大就会overfit。超参数λ用来控制系数的大小，需要通过model selection选出来。
我们利用正则项q norm来控制参数的大小，来保证参数的绝对值比较小。q 可以取任意的值，当q大于等于1时，是凸函数，其中的好处是你可以在其中找到最优解。当q小于1时，就变成了非凸问题，找到最优解就比较困难了。所以1是一个临界点。
L1为什么得到稀疏解？
这里我们给出一个简单的例子，前面是loss函数，后面是正则项，可以看到一范式为凸但不可微，会在x＝0时取到极值点，二范式在零点可微，但是不一定在零点取得极值点，另外一种对于一范式稀疏的解释是通过等高线的方式，可以发现一范式的约束能够使得loss函数在零点相交的可能性更大，而二范式是一个球，与loss函数在零点相交的可能性不大，从而一范式能够使得解稀疏。一范式最经典的就是96年的LASSO问题 。
A是数据矩阵，每一行代表样本，列代表特征，有标签y。用一个简单的线性模型来预测y，那么Ax-y就是一个拟合项，一范数就是正则项，使得x的系数稀疏，有很多是0，从而去掉一些无关项。这个好处就是，你自动做了一些特征选择。又选了特征、又选了模型，这样分析、推广都比较方便一些。
下面是一个具体的应用实例，建造一个模型，区分这些脑成像，哪些是正常的，哪些是不正常的。其中要找到一些跟疾病相关的特征。
之前提到的y都是比较简单的，只有一列，但是很多场景下，y可能有很多值。比如说在Imaging Genetics，特征可以是一个或者无数个基因。比如说把脑区变成很多个区，每个区域的体积或者面积作为一个Y，这样这个Y有几百个。还可以图像每个点是一维，这样Y也可以是几百万，X是几百万的，Y也是几百万的，两边都非常大，这个模型就从100万变成了100万的平方。这个时候如果不加正则项，问题就没法解。这时模型可以用稀疏，先假设这个矩阵非常低，这样参数个数减少很多。
我的一个合作者进行了一个比较大的项目，把世界上200多个医院所有的数据整合在一起，有两三万个数据，但仍然不算很多，未来的数据如果越来越大的话，模型会越来越精确，现有数据不足，所以只能对模型加入很多假设，从而保证模型的有效性。当然，数据还是第一重要的，数据量如果不够大，这个模型无论怎么学可能都还是有问题的。
稀疏学习在很多领域中都有很广泛的应用，如生物医学，图像处理，信号处理，神经科学，机器学习等等。在实际问题里我们需要找到一个参数，一个常用的方法是使用交叉检验（cross validation），在一个广泛的超参数空间中，选择一个最优的参数，这种方法在稀疏模型里可能会存在缺陷，一个更好的方法是使用stability selection，相当于对每个数据进行子采样，然后进行多次筛选，选择最好的参数。具体的可以在文章中查阅，里面有很强的理论保证，因为它会对问题进行很多子采样，所以会进行成千上万次的lasso求解，因此需要一个特别快的算法，这也是我们今天主要要讲的，如何让模型在大规模的数据上进行计算。
下面讲几个模型。Lasso模型前面讲到，好处是有理论保证，模型和特征一起建立，非常容易推广。我们知道，很多特征是有结构的，特征与特征之间并不是独立的。
我们首先介绍一些结构Lasso，这里给出一个例子，特征之间会有光滑性，我们给出了一个所有脑区的特征，我们可以发现向邻近的点会比较类似，特征的光滑性有时间和空间上的光滑性，比如说，相邻时刻之间的数据以及相邻空间的数据是具有相似性的，所以很多问题都是有光滑性的，也会有一些问题具有一些树的结构，以及一些问题可能具有一些网的结构，得到特征值之间的相似性。当我们获得我们的这些特征之间的先验知识之后，如果对lasso进行推广，利用我们的特征之间的关系，结构的lasso也就应运而生。和lasso类似，损失函数可以根据问题相关设计，如逻辑回归或者最小二乘回归等等，来表示对数据的拟合程度，重点是如何设计我们的penalty，lasso是L1 norm，仅仅是稀疏，特征之间没有任何假设，但是如果我们有特征直接结构的先验知识，那么我们可以在正则项这里进行推广，一般是利用一个凸的方法，来得到我们需要的结构。
下面举几个例子。这里我们根据结构的先验信息，有Fused Lasso（光滑性），Graph Lasso（图结构）, Group Lasso（组结构）以及树结构Lasso（树结构）。
?Fused Lasso（光滑性）
特征有光滑性，相邻的特征会比较像。那么penalty可以加一项，第一项还是稀疏，保证很多段都是0；除此之外，在利用数据的光滑性再加一项，就是说每相邻两项减一下，这样就保证相邻的是相近的，系数是相似的。每一段都是一个常数，而且很多都是稀疏的，这样子就能够简化模型，降低模型的复杂性，同时实验发现，这种方式能够有效的提升符合这种特点的数据的效果。
?Graph Lasso（图结构）
第二个推广，如果你的结构是graph，比如蛋白质，哪些蛋白质是相关的，如果两个特征相关，这个可以简单认为是刚才那个Fused LASSO的推广。我们增加一个penalty，使得相关的特征具有相同的结构。这个可以认为就是一个简单的graph case，就是一条线，当然这个graph case也可以很复杂。这个缺点是，它是强相关的，所以不一定是正相关，可能是负相关的，这也是有可能的。比如很多场景，你提高我就下降了，但它的比例是类似的，这个时候需要加一个绝对值。你正1，我其实也可以负1，只要值类似就好了。
?Group Lasso（组结构）
第三个推广是很多特征会有一种组的结构，最典型的应用就是在脑影像的分析中，很多脑区或者体素之间有一定的组约束的，同时滴滴也有很多场景，如司机，终点，天气等等，还有categorical variable。很多特征必须放在一组里才有一定的意义。因此group LASSO就是用来解决这种存在组结构的问题。
比如每个脑区可以当成一个group，基因我们知道有些group。假设categorical variable的值有四种模型：ATCG，怎么去表达呢？一种方式就是变成向量，4种可能性，如最右图所示。这四个特征，其实单看其中一个是没有什么意义的，四个在一块才是有意义的。这么一个特征用四维来表示，所以把这四个值作为一个group。所以早期发明group，就是解决这个categorical variable类型的问题。
下图最左边是 L1，挑了一些特征，如果是有group structure的话，比如前面四个特征是一个group、后面三个是一个group、最后四个是一个group。那么每个group都是一个一个四维向量，你去算它的 q norm。比如q=2,算每个向量的长度，如果这里有100个group，算出来是100个值，然后就把100个值加起来。这个导致的结果是说，group这个系数要么一起等于0，或者都不等于0，也就是说这四个特征如果在同一个组里面，要么全部被挑出来，要么全部不挑出来。
一个应用就是Multi－task learning。假设Y有很多列，X也有很多列，每一行作为一个group加起来。这个结果是说，任何一个特征要么所有的task都有用，或者所有task都没用。如果用这个模型来挑特征，所有task挑出来的特征是一样的。
举个例子，让你去判断写的是什么字母。有180个人来写ABCD，你要去预测那个字母是什么。因为每个人的写法不一样，所以有几种做法，一种是把所有的人写的所有的字母放块，一个模型去预测，不管谁写的全部放在一块。
另外一个极端是，每个人建一个模型，因为每个人的写法不一样。两种模型都有缺点。第一个模型的缺点是，它的样本区别可能很大，用一个模型可能不能够覆盖所有的特征。第二个模型的缺点是，每个人的样本量可能不够大，这会导致每个人的模型都不是特别精确。
而Multi-task learning就是在中间建一个模型，相当于兼顾到两种方法。方法是：建180个模型，每个人都建立一个模型，同时每个模型是相关的，不是独立的，所有模型一起学。
相关性怎么建呢？我们希望所有的模型挑出的重要特征是一样的，所有特征不同的模型绑在一块，要么都挑，要么都不挑。这个结果比模型1、模型2都要好。
讲一个滴滴应用的例子。它有一个场景是让司机挑能跟他顺路的乘客。这里就有一个模型，看乘客是不是跟我顺路的模型。那么我就给乘客排序，把最顺路的乘客放在最前面。
早期在大城市运行的时候，比如北京、上海这些订单量比较大的城市，这个模型挺精确的，但放在小城市，这个模型就比较长，因为数据量不够大，这个时候我们就采取了Multi-task learning。其实每个城市是一个模型，如果全部叠在一块了，模型效果不好，因为每个城市的特征不太一样，交通状况也不一样，每个城市的生活、消费水平都不一样。如果每个城市建一个模型也不好，因为小城市数据量不大效果不好。所以我们每个城市建一个模型，而每个模型又不是完全独立的，有一些相关性，甚至可以迁移学习，大城市模型建好后直接可以迁移到小城市，这也是可以的。
?树结构Lasso（树结构）
最后一个是树。Group Lasso考虑的情况还是比较简单，只是把特征分成很多组。在很多场景下，特征可以做更精细的划分，比如先把它分成10个组，然后每个组的特征又可以把它细分成10个组，有一个分层的结构，这个信息量会更大。就是说特征的相似性是有这么一个树结构的，这个时候用group Lasso效果就不好，应该用树，树显然是比group更加复杂一些。
我这里举一个例子，可能不是最恰当的例子，但能说明怎么用。
假设我们每个样本一个图，这是脑成像的图。这个树结构，最上面表示整个图，在这个树的最顶端是整幅图，如果把这个脑区每个横纵都分四份，这样把它分成16个小图，第一层就16个节点；类似的往下每一个图又分成16个，以此类推，组成一个树结构。最后两个节点之间的距离可以精确的表达特征实际的相似性，这很多场景都是可以用的。
这里可以建一个tree的Lasso，怎么建呢？第一层，最上面是把所有特征都放在上面。假设有8个特征，最上面8个特征都有。第二层有三个group，每一层把特征划分开，每一层都是group Lasso，再把每一层group Lasso加起来。
Part3 : 低秩模型下面讲一下低秩模型。很多问题都可以用矩阵来表示。通常，矩阵中的一些值是未知的，因此需要用观测值去预测丢失值。比如说图像，可能会有一些图像被树覆盖，要用观测值去预测被遮挡的部分。
或者说collaborative filtering，一种场景是行代表用户，列代表电影，每个用户被要求给电影打分，但不是所有的用户都对所有的电影打分，所以我们需要去预测这些缺失的数据。
同样滴滴有类似的问题，假设这个城市我们需要预测现在的交通状况是顺畅的还是拥堵的，我们有观测值，只要某个区域有一辆我们平台的车在开，就能知道它的速度，也就知道这个路段的交通状况。但北京大部分区域我们没有车在开，不知道交通状况，这样我们需要通过观测的值去预测我们没有观测的值，这个非常重要，我们如果能知道北京现在所有路段的交通状况，就能做很多事情，比如说路径规划，做A到B的时间预估等等，所以类似的有大部分区域是未知的问题，我们都需要去预测。
如果不做任何假设，这个问题是很难解决的。因此，我们引入低秩假设。
我们认为这个矩阵这些缺失值填进去之后得到的这个矩阵是低秩的，也就是说其实对每个问题它的主要核心的因素是少量的。 数学上等价于希望最后得到的矩阵X 的秩（Rank）越小越好。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，从而保证低秩。
叶杰平演讲下篇内容，请持续雷锋网报道。
