发布时间:2023-01-21 09:00
AI 科技大本营按:本文节选自微软亚洲研究院机器学习研究团队刘铁岩、陈薇、王太峰、高飞合著的《分布式机器学习:算法、理论与实践》一书。为了让大家更好地理解分布式机器学习,AI科技大本营联合华章科技特别邀请到了本书的作者之一——微软亚洲研究院副院长刘铁岩老师进行在线公开课分享,详情请见文末信息,还有福利哦~~
分布式机器学习并非分布式处理技术与机器学习的简单结合。一方面,它必须考虑机器学习模型构成与算法流程本身的特点,否则分布式处理的结果可能失之毫厘、谬以千里;另一方面,机器学习内含的算法随机性、参数冗余性等,又会带来一般分布式处理过程所不具备的、宜于专门利用的便利。
——节选自周志华老师对该书的推荐语
线性模型
线性模型是最简单的,也是最基本的机器学习模型。其数学形式如下:g(x;w)=。有时,我们还会在的基础上额外加入一个偏置项b,不过只要把x扩展出一维常数分量,就可以把带偏置项的线性函数归并到的形式之中。线性模型非常简单明了,参数的每一维对应了相应特征维度的重要性。但是很显然,线性模型也存在一定的局限性。
首先,线性模型的取值范围是不受限的,依据w和x的具体取值,它的输出可以是非常大的正数或者非常小的负数。然而,在进行分类的时候,我们预期得到的模型输出是某个样本属于正类(如正面评价)的可能性,这个可能性通常是取值在0和1之间的一个概率值。为了解决这二者之间的差距,人们通常会使用一个对数几率函数对线性模型的输出进行变换,得到如下公式:
经过变换,严格地讲,g(x;w)已经不再是一个线性函数,而是由一个线性函数派生出来的非线性函数,我们通常称这类函数为广义线性函数。对数几率模型本身是一个概率形式,非常适合用对数似然损失或者交叉熵损失进行训练。
其次,线性模型只能挖掘特征之间的线性组合关系,无法对更加复杂、更加强大的非线性组合关系进行建模。为了解决这个问题,我们可以对输入的各维特征进行一些显式的非线性预变换(如单维特征的指数、对数、多项式变换,以及多维特征的交叉乘积等),或者采用核方法把原特征空间隐式地映射到一个高维的非线性空间,再在高维空间里构建线性模型。
核方法与支持向量机
核方法的基本思想是通过一个非线性变换,把输入数据映射到高维的希尔伯特空间中,在这个高维空间里,那些在原始输入空间中线性不可分的问题变得更加容易解决,甚至线性可分。支持向量机(Support Vector Machine,SVM)[10]是一类最典型的核方法,下面将以支持向量机为例,对核方法进行简单的介绍。
支持向量机的基本思想是通过核函数将原始输入空间变换成一个高维(甚至是无穷维)的空间,在这个空间里寻找一个超平面,它可以把训练集里的正例和负例尽最大可能地分开(用更加学术的语言描述,就是正负例之间的间隔最大化)。那么如何才能通过核函数实现空间的非线性映射呢?让我们从头谈起。
假设存在一个非线性映射函数Φ,可以帮我们把原始输入空间变换成高维非线性空间。我们的目的是在变换后的空间里,寻找一个线性超平面,它能够把所有正例和负例分开,并且距离该超平面最近的正例和负例之间的间隔最大。这个诉求可以用数学语言表述如下:
其中,是离超平面最近的正例和负例之间的间隔(如图2.6所示)。
图2.6 最大化间隔与支持向量机
以上的数学描述等价于如下的优化问题:min12w2
上式中的约束条件要求所有的正例和负例分别位于超平面的两侧。某些情况下,这种约束可能过强,因为我们所拥有的训练集有时是不可分的。这时候,就需要引入松弛变量,把上述优化问题改写为:
其实这种新的表述等价于最小化一个加了正则项的Hinge损失函数。这是因为当小于0的时候,样本被超平面正确地分到相应的类别里,ξi=0;反之,ξi将大于0,且是的上界:最小化ξi就相应地最小化了。基于以上讨论,其实支持向量机在最小化如下的目标函数:
其中,是正则项,对它的最小化可以限制模型的空间,有效提高模型的泛化能力(也就是使模型在训练集和测试集上的性能更加接近)。
为了求解上述有约束的优化问题,一种常用的技巧是使用拉格朗日乘数法将其转换成对偶问题进行求解。具体来讲,支持向量机对应的对偶问题如下:
在对偶空间里,该优化问题的描述只与和的内积有关,而与映射函数本身的具体形式无关。因此,我们只需定义两个样本和之间的核函数k(xi,xj),用以表征其映射到高维空间之后的内积即可:
至此,我们弄清楚了核函数是如何和空间变换发生联系的。核函数可以有很多不同的选择,表2.1列出了几种常用的核函数。
事实上,只要一个对称函数所对应的核矩阵满足半正定的条件,它就能作为核函数使用,并总能找到一个与之对应的空间映射。换言之,任何一个核函数都隐式地定义了一个“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space,RKHS)。在这个空间里,两个向量的内积等于对应核函数的值。
决策树与Boosting
决策树也是一类常见的机器学习模型,它的基本思想是根据数据的属性构造出树状结构的决策模型。一棵决策树包含一个根节点、若干内部节点,以及若干叶子节点。叶子节点对应最终的决策结果,而其他节点则针对数据的某种属性进行判断与分支:在这样的节点上,会对数据的某个属性(特征)进行检测,依据检测结果把样本划分到该节点的某棵子树之中。通过决策树,我们可以从根节点出发,把一个具体的样本最终分配到某个叶子节点上,实现相应的预测功能。
因为在每个节点上的分支操作是非线性的,因此决策树可以实现比较复杂的非线性映射。决策树算法的目的是根据训练数据,学习出一棵泛化能力较强的决策树,也就是说,它能够很好地把未知样本分到正确的叶子节点上。为了达到这个目的,我们在训练过程中构建的决策树不能太复杂,否则可能会过拟合到训练数据上,而无法正确地处理未知的测试数据。常见的决策树算法包括:分类及回归树(CART)[21],ID3算法[11],C4.5算法[22],决策树桩(Decision Stump)[23]等。这些算法的基本流程都比较类似,包括划分选择和剪枝处理两个基本步骤。
划分选择要解决的问题是如何根据某种准则在某个节点上把数据集里的样本分到它的一棵子树上。常用的准则有:信息增益、增益率、基尼系数等。其具体数学形式虽有差别,但是核心思想大同小异。这里我们就以信息增益为例进行介绍。所谓信息增益,指的是在某个节点上,用特征j对数据集D进行划分得到的样本集合的纯度提升的程度。信息增益的具体数学定义如下:
其中,是特征的取值集合,而是特征取值为的那些样本所组成的子集;Entropy(D)是样本集合D的信息熵,描述的是D中来自不同类别的样本的分布情况。不同类别的样本分布越平均,则信息熵越大,集合纯度越低;相反,样本分布越集中,则信息熵越小,集合纯度越高。样本划分的目的是找到使得划分后平均信息熵变得最小的特征,从而使得信息增益最大。
剪枝处理要解决的问题是抑制过拟合。如果决策树非常复杂,每个叶子节点上只对应一个训练样本,一定可以实现信息增益最大化,可这样的后果是对训练数据的过拟合,将导致在测试数据上的精度损失。为了解决这个问题,可以采取剪枝的操作降低决策树的复杂度。剪枝处理有预剪枝和后剪枝之分:预剪枝指的是在决策树生成过程中,对每个节点在划分前先进行估计,如果当前节点的划分不能带来决策树泛化性能的提升(通常可以通过一个交叉验证集来评估泛化能力),则停止划分并且将当前节点标记为叶子节点;后剪枝指的是先从训练集中生成一棵完整的决策树,然后自底向上地考察去掉每个节点(即将该节点及其子树合并成为一个叶子节点)以后泛化能力是否有所提高,若有提高,则进行剪枝。
在某些情况下,由于学习任务难度大,单棵决策树的性能会捉襟见肘,这时人们常常会使用集成学习来提升最终的学习能力。集成学习有很多方法,如Bagging[24]、Boosting[25]等。Boosting的基本思路是先训练出一个弱学习器,再根据弱学习器的表现对训练样本的分布进行调整,使得原来弱学习器无法搞定的错误样本在后续的学习过程中得到更多的关注,然后再根据调整后的样本分布来训练下一个弱学习器。如此循环往复,直到最终学到的弱学习器的数目达到预设的上限,或者弱学习器的加权组合能够达到预期的精度为止。最终的预测模型是所有这些弱学习器的加权求和:
其中,是加权系数,它既可以在训练过程中根据当前弱学习器的准确程度利用经验公式求得,也可以在训练过程结束后(各个弱学习器都已经训练好以后),再利用新的学习目标通过额外的优化手段求得。
有研究表明Boosting在抵抗过拟合方面有非常好的表现,也就是说,随着训练过程的推进,即便在训练集上已经把误差降到0,更多的迭代还是可以提高模型在测试集上的性能。人们用间隔定理(Margin Theory)[26]来解释这种现象——随着迭代进一步推进,虽然训练集上的误差已经不再变化,但是训练样本上的分类置信度(对应于每个样本点上的间隔)却仍在不断变大。到今天为止,Boosting算法,尤其是与决策树相结合的算法如梯度提升决策树(GBDT)[27]仍然在实际应用中挑着大梁,是很多数据挖掘比赛的夺冠热门。
神经网络
神经网络是一类典型的非线性模型,它的设计受到生物神经网络的启发。人们通过对大脑生物机理的研究,发现其基本单元是神经元,每个神经元通过树突从上游的神经元那里获取输入信号,经过自身的加工处理后,再通过轴突将输出信号传递给下游的神经元。当神经元的输入信号总和达到一定强度时,就会激活一个输出信号,否则就没有输出信号(如图2.7a所示)。
图2.7 神经元结构与人工神经网络
这种生物学原理如果用数学语言进行表达,就如图2.7b所示。神经元对输入的信号进行线性加权求和:,然后依据求和结果的大小来驱动一个激活函数ψ,用以生成输出信号。生物系统中的激活函数类似于阶跃函数:
但是,由于阶跃函数本身不连续,对于机器学习而言不是一个好的选择,因此在人们设计人工神经网络的时候通常采用连续的激活函数,比如Sigmoid函数、双曲正切函数(tanh)、校正线性单元(ReLU)等。它们的数学形式和函数形状分别如图2.8所示。
图2.8 常用的激活函数
1.全连接神经网络
最基本的神经网络就是把前面描述的神经元互相连接起来,形成层次结构(如图2.9所示),我们称之为全连接神经网络。对于图2.9中这个网络而言,最左边对应的是输入节点,最右边对应的是输出节点,中间的三层节点都是隐含节点(我们把相应的层称为隐含层)。每一个隐含节点都会把来自上一层节点的输出进行加权求和,再经过一个非线性的激活函数,输出给下一层。而输出层则一般采用简单的线性函数,或者进一步使用softmax函数将输出变成概率形式。
图2.9 全连接神经网络
全连接神经网络虽然看起来简单,但它有着非常强大的表达能力。早在20世纪80年代,人们就证明了著名的通用逼近定理(Universal Approximation Theorem[28])。最早的通用逼近定理是针对Sigmoid激活函数证明的,一般情况下的通用逼近定理在2001年被证明[29]。其数学描述是,在激活函数满足一定条件的前提下,任意给定输入空间中的一个连续函数和近似精度ε,存在自然数Nε和一个隐含节点数为Nε的单隐层全连接神经网络,对这个连续函数的-逼近精度小于ε。这个定理非常重要,它告诉我们全连接神经网络可以用来解决非常复杂的问题,当其他的模型(如线性模型、支持向量机等)无法逼近这类问题的分类界面时,神经网络仍然可以所向披靡、得心应手。近年来,人们指出深层网络的表达力更强,即表达某些逻辑函数,深层网络需要的隐含节点数比浅层网络少很多[30]。这对于模型存储和优化而言都是比较有利的,因此人们越来越关注和使用更深层的神经网络。
全连接神经网络在训练过程中常常选取交叉熵损失函数,并且使用梯度下降法来求解模型参数(实际中为了减少每次模型更新的代价,使用的是小批量的随机梯度下降法)。要注意的是,虽然交叉熵损失是个凸函数,但由于多层神经网络本身的非线性和非凸本质,损失函数对于模型参数而言其实是严重非凸的。在这种情况下,使用梯度下降法求解通常只能找到局部最优解。为了解决这个问题,人们在实践中常常采用多次随机初始化或者模拟退火等技术来寻找全局意义下更优的解。近年有研究表明,在满足一定条件时,如果神经网络足够深,它的所有局部最优解其实都和全局最优解具有非常类似的损失函数值[31]。换言之,对于深层神经网络而言,“只能找到局部最优解”未见得是一个致命的缺陷,在很多时候这个局部最优解已经足够好,可以达到非常不错的实际预测精度。
除了局部最优解和全局最优解的忧虑之外,其实关于使用深层神经网络还有另外两个困难。
首先,因为深层神经网络的表达能力太强,很容易过拟合到训练数据上,导致其在测试数据上表现欠佳。为了解决这个问题,人们提出了很多方法,包括DropOut[32]、数据扩张(Data Augmentation)[33]、批量归一化(Batch Normalization)[34]、权值衰减(Weight Decay)[35]、提前终止(Early Stopping)[36]等,通过在训练过程中引入随机性、伪训练样本或限定模型空间来提高模型的泛化能力。