滴滴研究院副院长叶杰平:大规模稀疏和低秩学习(上)

2017-09-10 10:30:36  阅读:3140+ 出处:新浪科技 作者:孙红雷 责任编辑:孙红雷

编者按:本文根据叶杰平教授在中国人工智能学会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求解,因此需要一个特别快的算法,这也是我们今天主要要讲的,如何让模型在大规模的数据上进行计算。

Part 2: 四大结构化稀疏学习模型

下面讲几个模型。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,从而保证低秩。

叶杰平演讲下篇内容,请持续雷锋网报道。

“如果发现本网站发布的资讯影响到您的版权,可以联系本站!同时欢迎来本站投稿!