机器学习斯坦福大学讲义

机器学习一斯坦福大学讲义第一课机器学习的动机与应用工具:需正版：Matlab.免费:Octave定义(ArthurSamuel1959)：在不直接针对问题进行编程的情况下，赋予计算机学习能力的研究领域。例：Arthur的下棋程序，计算走每一步获胜的概率，最终打败程序作者本人.(感觉使用决策树思想)定义2(TomMitchell1998)：一个合理的学习问题应该这样定义：对一个计算机程序来说，给它一个任务T和一个性能测量方法P,如果在经验E的影响下，P对T的测量结果得到了改进，那么就说改程序从E中学习了。如上例：E：程序不断和自己下棋的经历，T：下棋，P：和人类选手对弈的胜率课程的四大部分：1、有监督学习回归问题例：收集某地房屋价格统计、房屋大小和价格对应情况：画出一条拟合曲线，就可以通过房屋大小估计价格。有监督学习即给出一个数据集(正确的房屋价格及对应大小)此例为回归问题。回归意味着需要预测的变量是连续的分类问题分类问题中需要处理的变量是离散的例：判断肿瘤是恶性还是两性收集肿瘤大小和恶性/良性数据，大小为横轴，是否是恶性为纵轴（只有0,1）画图肿瘤可能由多个因素导致，引入年龄，大小为横轴，年龄为纵轴，恶性以叉表示，良性以圆圈表示画图，分析患肿瘤的区域还可引入更多属性，画在多维空间中无限维空间如何处理？将无限维映射到内存的算法？2,学习理论学习理论即解释学习型算法有效的原因（学习算法的理论基础）寻找什么样的算法能很好地近似不同的函数，训练集的规模是否合适3、无监督学习例：如上述肿瘤例子，图中的点不知道正确答案，而是由你从中找去一定的结构，即聚类。应用于生物基因工程，图像处理，计算机视觉等领域例：鸡尾酒会问题在嘈杂的鸡尾酒会中，将你感兴趣的声音提取出来运用两个不同位置的麦克分开来自不同位置的声音还能应用于文本处理等领域使用ICA算法，Matlab一行代码即可解决4、强化学习通过决策产生的结论或对或错，故产生一系列的决策。例：对一个模型飞机编写一个起飞程序，飞机在程序做了一连串错误决策是才会坠毁，只要做出连续的整体还不错的决策，即可保持飞机正常飞行强化学习的基本概念：回报函数（正反馈及负反馈），程序做出正确决策时给出正反馈，反之亦然。程序不断做出决策，在不断尝试获得尽量多的正反馈时，逐渐学习并做出正确决策关键在于要定义什么是正确决策，什么是错误决策，再设计算法获取尽量多的正反馈第二课监督学习应用与梯度下降本课内容：1、线性回归2、梯度下降3、正规方程组（复习）监督学习：告诉算法每个样本的正确答案，学习后的算法对新的输入也能输入正确的答案1、线性回归例：Alvin汽车，先让人开车，Alvin摄像头观看（训练），而后实现自动驾驶。本质是一个回归问题，汽车尝试预测行驶方向。例：上一节课的房屋大小与价格数据集Livingarea(feet2)Price(1000$s)2104Ilin1C00330240036914162323000540

引入通用符号：m=训练样本数乂=输入变量(特征)丫=输出变量(目标变量)(x,y)-一个样本第i个训练样本本例中：m：数据个数，X：房屋大小，y：价格监督学习过程：将训练样本提供给学习算法算法生成一个输出函数(一般用h表示，成为假设)这个函数接收输入，输出结果。(本例中为，接收房屋面积，输出房价)将x映射到y»如下图所示：Training

setILearningalgoritliin4(Ixvmgmaofx ah-apredictedy(Ixvmgmaof(predictedpnc«)ofbouse)

对假设进行线性表示：Mx)=鱼+"%通常来说，回归问题有多个输入特征。如上例中，我们还已知房屋的卧室数，即有个第二个特征。即x塞示大小,小表示卧室数，则可将假设写成：‘坨⑴=%+ati+%工2oh（工）=£OtXi=91x为了将公式写整洁，定义Co=1,则h可写成： i=On=特征数目，6参数。选择e的目的，是使h(x)与y的平方差尽量小。又由于有m个训练样本，需要计算每个样本的平方差，最后为了简化结果乘以1/2,即：我们要做的就是求:min(J(4)我们要做的就是求:min(J(4)求min。©))方法：梯度下降和正规方程组2、梯度下降梯度下降是一种搜索算法，基本思想：先给出参数向量一个初始值，比如0向量；不断改变，使得J(6)不断缩小。改变的方法：梯度下降如图所示，水平坐标轴表示名和”,垂直坐标表示J(6)

一开始选择0向量作为初始值，假设该三维图为一个三维地表,。向量的点位于一座“山”上。梯度下降的方法是，你环视一周，寻找下降最快的路径，即为梯度的方向，每次下降一小步,再环视四周，继续下降，以此类推。结果到达一个局部最小值，如下图：当然，若初始点不同，则结果可能为另一个完全不同的局部最小值，如下:表明梯度下降的结果依赖于参数初始值。梯度下降算法的数学表示：d,、6:=Gj

:=为赋值运算符，即表示程序中的的赋值语句。每一次将仇减去3对/(,)求偏导的结果，即沿最陡峭的“山坡”下降将偏导数展开分析：套咐=磊面付5=2-1(/(工)-y)-9(2(0-y)=(h0(x)-y)xj%：=%+a仅⑴一版(才⑴))婢).代入上式： J 3a：学习速度，即决定你下山时每•步迈多大。设的过小，收敛时间长，设的过大，可能会超过最小值(1) 批梯度下降算法：上述为处理一个训练样本的公式，将其派生成包含m个训练样本的算法，循环下式直至收敛：%:=%+a 仅⑴—法(1⑴))可)复杂度分析：对于每个师的每次迭代，即上式所示，时间为0(m)每次迭代(走一步)需要计算n个特征的梯度值，复杂度为。(mn)

一般来说，这种二次函数的/(')的三维图形为一个碗状，有•”个唯一的全局最小值。其等高线为一个套一个的椭圆形，运用梯度下降会快速收敛到圆心.梯度下降性质：接近收敛时，每次的步子会越来越小。其原因是每次减去a乘以梯度，但是梯度会越来越小，所以步子会越来越小。下图为使用梯度下降拟合的上例房屋大小和价格的曲线检测是否收敛的方法：检测两次迭代仇的改变量，若不再变化，则判定收敛更常用的方法：检验/(6),若不再变化，判定收敛批梯度下降算法的优点是能找到局部最优解，但是若训练样本m很大的话，其每次迭代都要计算所有样本的偏导数的和，时间过慢，于是采用下述另一种梯度下降方法。(2) 随机梯度下降算法(增量梯度下降算法)：Loop{fori=ltom,{0j:=%+a("⑴——("))x(j] (foreveryj).))每次计算可不需要再遍历所有数据，而是只需计算样本i即可。即批梯度下降中，走一步为考虑m个样本；随机梯度下降中，走一步只考虑1个样本。每次迭代复杂度为0(n)。当m个样本用完时，继续循环到第1个样本。上述使用了迭代的方法求最小值，实际上对于这类特定的最小二乘回归问题，或者普通最小二乘问题，存在其他方法给出最小值，接下来这种方法可以给出参数向量的解析表达式,如此一来就不需要迭代求解了。3、正规方程组给定一个函数J,J是一个关于参数数组的函数，定义J的梯度关于的导数，它自己也是一个向量。向量大小为n+1维(从0到n),如下：也两%/=： e/?n+1dj腐J所以，梯度下降算法可写成：

更普遍的讲，对于一个函数f,f的功能是将一个m*n的矩阵映射到实数空间上，即:f:RmxniR假设输入为m*n大小的矩阵A,定义f关于矩阵A的导数为:r_«z_dAwV"⑷= i-DAml导数本身也是个矩阵，包含了f关于A的每个元素的偏导数。如果A是一个方阵，即n*n的矩阵，则将A的迹定义为A的对角元素之和，即:ntrA=4t=itrA即为tr(A)的简化。一些关于迹运算符和导数的定理：trAB=trBAtrABC=trCAB=trBCA%trAB=BTtrA=trAT若2©匕tra=a6) 匕trABHC=CAB+CTABT有了上述性质，可以开始推导了:

定义矩阵X,称为设计矩阵，包含了训练集中所有输入的矩阵，第i行为第i组输入数据,即：（工⑴）7―一（工⑵）T一（的/_则由于/（工⑴）=（工⑴）的，所以可得:（Hd（（Hd（工⑴）_y⑴7'_ 2则有:又因为对于向量z,有Z2=2^4,则有:1工\（xe-yfiXO-y]=2*二1

=J⑻由上述最后一个性质可得：1万trAB^C=BT^TCT+BATC通过上述6个性质，推导:▽〃⑹=^0^(XO-y)T(XO-y)= (el'xTxe-铲x%-/xe+fy)=tr(OTXTX0-OTXTy-fXG+= (treTXTXe-2tryrX0)=1(XrXO+xl'xe-2XTy)=xTxe-倒数第三行中，运用最后一个性质将“/⑻置为0,则有：XrX0=XTy称为正规方程组可得：e=第三课欠拟合与过拟合概念本次课程大纲：1、局部加权回归：线性回归的变化版本2、概率解释：另一种可能的对于线性回归的解释3、Logistic回归：基于2的一个分类算法4、感知器算法：对于3的延伸，简要讲复习：(”卜⑴)-第i个训练样本令7。=1,以参数向量为条件，对于输入x,输出为：h(x)—仇勺=9T],i=0n为特征数量定义成本函数J,定义为：咐=若("I"m为训练样本通过正规方程组推导的结论：0=[XTX)~lXTy.1、过拟合与欠拟合通常，你选择交给学习算法处理的特征的方式对算法的工作过程有很大影响。例：上次课的例子中，用X1表示房间大小。通过线性回归，在横轴为房间大小，纵轴为价格的图中，画出拟合曲线。回归的曲线方程为：8。+8逐]若定义特征集合为：xl表示房子大小，x2表示房子大小的平方，使用相同的算法，拟合得到一个二次函数，在图中即为一个抛物线，即：0o+0ixi+02Xi：以此类推，若训练集有7个数据，则可拟合出最高6次的多项式,可以找到一条完美的曲线，该曲线经过每个数据点。但是这样的模型又过于复杂，拟合结果仅仅反映了所给的特定数据的特质，不具有通过房屋大小来估计房价的普遍性。而线性回归的结果可能无法捕获所有训练集的信息。所以，对于一个监督学习模型来说，过小的特征集合使得模型过于简单，过大的特征集合使得模型过于复杂。对于特征集过小的情况，称之为欠拟合(underfitting)；对于特征集过大的情况，称之为过拟合(overfitting)解决此类学习问题的方法：特征选择算法：一类自动化算法，在这类回归问题中选择用到的特征非参数学习算法：缓解对于选取特征的需求，引出局部加权回归参数学习算法(parametriclearningalgorithm)定义：参数学习算法是一类有固定数目参数，以用来进行数据拟合的算法。设该固定的参数集合为立线性回归即使参数学习算法的一个例子非参数学习算法(Non-parametriclearningalgorithm)定义：一个参数数量会随m(训练集大小)增长的算法。通常定义为参数数量虽m线性增长。换句话说，就是算法所需要的东西会随着训练集合线性增长，算法的维持是基于整个训练集合的，即使是在学习以后。2、局部加权回归(LocallyWeightedRegression)一种特定的非参数学习算法。也称作Loess。算法思想:假设对于一个确定的查询点X,在X处对你的假设h(x)求值。对于线性回归，步骤如下：1)拟合出e,使£i(y⑴-尹工⑴)2最小2)返回对于局部加权回归，当要处理X时：检查数据集合，并且只考虑位于X周围的固定区域内的数据点对这个区域内的点做线性回归，拟合出一条直线根据这条拟合直线对x的输出，作为算法返回的结果用数学语言描述即：D拟“，使(严一心⑴产最小w为权值，有很多可能的选择，比如：其意义在于，所选取的x(i)越接近X,相应的w(i)越接近1；x(i)越远离x,w(i)越接近Oo直观的说，就是离得近的点权值大，离得远的点权值小。这个衰减函数比较具有普遍意义，虽然它的曲线是钟形的，但不是高斯分布。°被称作波长函数，它控制了权值随距离下降的速率。它越小，钟形越窄，w衰减的很快；它越大，衰减的就越慢。3)返回总结：对于局部加权回归，每进行一次预测，都要重新拟合一条曲线。但如果沿着X轴对每个点都进行同样的操作，你会得到对于这个数据集的局部加权回归预测结果，追踪到一条非线性曲线。局部加权回归的问题：由于每次进行预测都要根据训练集拟合曲线，若训练集太大，每次进行预测的用到的训练集就会变得很大，有方法可以让局部加权回归对于大型数据集更高效，详情参见AndrewMoore的关于KD-tree的工作。3、概率解释概率解释所解决的问题：在线性回归中，为什么选择最小二乘作为计算参数的指标，使得假设预测出的值和真正y值之间面积的平方最小化？我们提供一组假设，证明在这组假设下最小二乘是有意义的，但是这组假设不唯一，还有其他很多方法可以证明其有意义。(1)假设1：假设输入与输出为线性函数关系，表示为：=〃工⑴+■”其中，为误差项，这个参数可以理解为对未建模效应的捕获，如果还有其他特征，这个误差项表示了一种我们没有捕获的特征，或者看成一种随机的噪声。假设服从某个概率分布，如高斯分布(正态分布)：£°)~研0.。2),表示一个均值是0,方差是°’的高斯分布。高斯分布的概率密度函数：v27ro\ 2。)根据上述两式可得:”忖)洌二会呻(一吟炉)V27ra\ 2a- /即，在给定了特征与参数之后，输出是一个服从高斯分布的随机变量，可描述为：y("|工⑴;6 (尹工⑴,02)*为什么选取高斯分布？便于数学处理对绝大多数问题，如果使用了线性回归模型，然后测量误差分布，通常会发现误差是高斯分布的。中心极限定律：若干独立的随机变量之和趋向于服从高斯分布。若误差有多个因素导致，这些因素造成的效应的总和接近服从高斯分布。注意：e并不是一个随机变量，而是一个尝试估计的值，就是说它本身是一个常量，只不过我们不知道它的值，所以上式中用分号表示。分号应读作“以…作为参数”，上式读作“给定x(i)以为参数的y(i)的概率服从高斯分布”。假设每个为IID(independentlyandidenticallydistributed)独立同分布即误差项彼此之间是独立的，并且他们服从均值和方差相同的高斯分布假设2：设e的似然性为(即给定x(i)以为参数的州的概率=L(优工㈤=p⑷、：6)由于只“是独立同分布，所以上式可写成所有分布的乘积：

假设3：极大似然估计：选取e使似然性L（e）最大化（数据出现的可能性尽可能大）定义对数似然函数为K8）：的）=°y/2rcro22父"-'上式两个加项，前一项为常数。所以，使似然函数最大，就是使后一项最小，即：1尸工（严一心⑴产i=l这一项就是之前的〕（e）,由此得证，即之前的最小二乘法计算参数，实际上是假设了误差项满足高斯分布，且独立同分布的情况，使似然最大化来计算参数。注意：高斯分布的方差对最终结果没有影响，由于方差一定为正数，所以无论取什么值，最后结果都相同。这个性质会在下节课讲到。

4、Logistic回归这是我们要学习的第一个分类算法。之前的回归问题尝试预测的变量y是连续变量，在这个分类算法中，变量y是离散的，y只取。1｝两个值。一般这种离散二值分类问题用线性回归效果不好。比如x<=3,y=0；x>3,Y=l,那么当x>3的样本占得比例很大是，线性回归的直线斜率就会越来越小，y=0.5时对应的x判决点就会比3大，造成预测错误。若y取值。1｝，首先改变假设的形式，使假设得到的值总在[0禺之间，即：h(x)U°，l]所以，选取如下函数:,、 ，T、 1h如=9(0tx)=]其中:g(?)=g(?)=1+e-zg函数一般被称为logistic函数，图像如下:z很小时，g(z)趋于0,z很大时，g(z)趋于1,z=0时，g(z)=0.5对假设的概率解释:假设给定X以为参数的y=l和y=0的概率:P(y=l\x\0)=h0(x)P(y=0|x;0)=1—he(x)的EP®।h⑼=SG））"0一加（工））”"可以简与成：参数的似然性：附=p（y\X；e）m=Hp"”工⑴网i=lm=n（原则严（「/（叫产”«=i求对数似然性：幽=10gL⑹m=^2bgM工⑴）+（1—y⑴）log（i—力（工⑴））S=1为了使似然性最大化，类似于线性回归使用梯度下降的方法，求对数似然性对e的偏导，即:0=0+。▽招。）因为求最大值，此时为梯度上升。偏导数展开:却⑻=（，薪jTi）广嬴0Q心=（y（i-g®7））-（i-！/）g（。％））叼=（y-ho（x））xj则：4：=%+a（严-砧］⑴））c?即类似上节课的随机梯度上升算法，形式上和线性回归是相同的，只是符号相反，八式x）为logistic函数，但实质上和线性回归是不同的学习算法。5、感知器算法在logistic方法中，g⑵会生成［0,1）之间的小数，但如何是g⑵只生成0或1?所以，感知器算法将g⑵定义如下：、（1ifz>0g⑶=［0ifzv0同样令瓦）（工）=g（e］），和logistic回归的梯度上升算法类似，学习规则如下：%：=%+a（y⑴一M（工⑴））工，尽管看起来和之前的学习算法类似，但感知器算法是一种非常简便的学习算法，临界值和输出只能是。或1,是比logistic更简单的算法。后续讲到学习理论是，会将其作为基本的构造步骤。第四课牛顿方法本次课程大纲：1、牛顿方法：对Logistic模型进行拟合2、指数分布族3、广义线性模型(GLM)：联系Logistic回归和最小二乘模型复习：Logistic回归：分类算法假设给定x以为参数的y=l和y=0的概率：P(y=\| =h0(x)P(y=0|x;0)=1-h0(x)赤1+€求对数似然性：绚)=logL(0)m=Xlog/i(x(,))+(1—y⑴)log(l—f二l对其求偏导数，应用梯度上升方法，求得：%：=4+°(严一加(工⑴))本次课程介绍的牛顿方法是一种比梯度上升快很多的方法，用于拟合Logistic回归1、牛顿方法假设有函数限），需要找使f⑼=0的e步骤：给出一个'的初始值对眼⑴求导，求导数为o时e的值（就是求f（e）切线与x轴交点）重复步骤2因为该点的导数值即为切线斜率，而斜率=该点y轴的值/该点X轴的变化值，所以e每次的变化值:*使用这个方法需要f满足一定条件，适用于Logistic回归和广义线性模型*一般初始化为0应用于Logistic回归:求对数似然的最大值，即求'（8）为。时的句根据上述推论，更新规则如下:牛顿方法的收敛速度：二次收敛每次迭代使解的有效数字的数目加倍：假设当前误差是0.1,一次迭代后，误差为0.001,再一次迭代，误差为0.0000001。该性质当解距离最优质的足够近才会发现。牛顿方法的一般化：e是一个向量而不是一个数字，一般化的公式为：0:=0-▽4(g)是目标函数的梯度，H为Hessian矩阵，规模是n*n,n为特征的数量，它的每个元素表示一个二阶导数：—必⑻L丽丽上述公式的意义就是，用一个一阶导数的向量乘以一个二阶导数矩阵的逆优点：若特征数和样本数合理，牛顿方法的迭代次数比梯度上升要少得多缺点：每次迭代都要重新计算Hessian矩阵，如果特征很多，则H矩阵计算代价很大2、指数分布族回顾学过的两种算法：对于P(y|x；e)：若y属于实数，满足高斯分布，得到基于最小二乘法的线性回归；若丫取{0,1},满足伯努利分布，得到Logistic回归。问题：如Logistic回归中，为何选择sigmoid函数？sigmoid函数是最自然的默认选择。接下来，会以这两个算法为例，说明它们都是广义线性模型的特例。考虑上述两个分布，伯努利分布和高斯分布：伯努利分布设有一组只能取0或1的数据，用伯努利随机变量对其建模：切方’~Bernoulli(<j)f则P(y=l；(p)=巴改变参数年，y=i这一事件就会有不同概率，会得到一类概率分布(而非固定的)。高斯分布引工冶〜八乂""”改变参数口，也会得到不同的高斯分布，即一类概率分布。上述这些分布都是一类分布的特例，这类分布称为指数分布族.指数分布族的定义：若一类概率分布可以写成如下形式，那么它就属于指数分布族：P(y；〃)=b(g)exp(/r(y)—a(〃))n-自然参数，通常是一个实数T(y)-充分统计量，通常，T(y)=y,实际上是一个概率分布的充分统计量(统计学知识)对于给定的a,b,T三个函数，上式定义了一个以n为参数的概率分布集合，即改变f］可以得到不同的概率分布。证明伯努利分布是指数分布族：Ber(<P).P(y=1;<p)=<p可知:p(y;p(y;。)exp(ylogd+(1-y)log(l-</>))y+log(l-0))y+log(l-0))由上式可见,n=log((p/(l・(p))，可解出：cp=l/(l+exp(-r))),发现得到logistic函数(之后讨论其原因)，则:T\y)=y丽)=-log(l-0)=log(l4-e。)帅)=1证明高斯分布是指数分布族：引工；'〜人广(〃,02),设方差为1(方差并不影响结果，仅仅是变量y的比例因子)这种情况下高斯密度函数为：b[y)=(l/\/27r)exp(-j/2/2)*指数分布族包括：高斯分布(正态分布)，多元正态分布;

伯努利分布(01问题建模)，多项式分布(对k个结果的事件建模)：泊松分布(对计数过程建模)；伽马分布，指数分布(对实数的间隔问题建模)；B分布，Dirichlet分布(对小数建模)；Wishart分布(协方差矩阵的分布)...3、广义线性模型GLM选定了一个指数分布族后，怎样来推导出一个GLM呢?假设：⑴y|上:ExponcntialFamilyS),即假设试图预测的变量y在给定x,以e作为参数的条件概率，属于以n作为自然参数的指数分布族例：若要统计网站点击量y,用泊松分布建模(2)给定X,目标是求出以x为条件的T(y)的期望E[T(y)|x],即让学习算法输出h(x)=E[T(y)|x]即自然参数和输入特征x之间线性相关，关系由e决定。仅当n是实数时才有意义。若n是一个向量，仍=9ix推导伯努利分布的GLM：y\i\0^ExponentialFamily(7/),伯努利分布属于指数分布族对给定的X,0,学习算法进行一次预测的输出：ho(x)=E[y\x-,0]=6=1/(1+ef)=1/(1+0-叼得到logistic回归算法。正则响应函数：g(n)=E[y；n],将自然参数n和y的期望联系起来正则关联函数：g1推导多项式分布的GLM：多项式分布是在k个可能取值上的分布，即y£{l，…,k},如将收到的邮件分成k类，诊断某病人为k种病中的一种等问题。(1)将多项式分布写成指数分布族的形式：设多项式分布的参数：°1 且2二1,5表示第i个取值的概率分布，最后一个参数可以由前k-1个推导出，所以只将前k-1个01，•••，以T视为参数。多项式分布是少数几个T(y)!=y的分布，丁⑴叶化)都定义成一个k-l维的列向量，表示为：丁。)="1"00,丁⑵='0-10,T(3)=.0.01-0'00，丁的=■00000010这样定义T(y)是为了将多项式分布写成指数分布族形式。*定义符号：指示函数，1{Jl{True}=1,l{False}=0,即大括号内命题为真，值为1,；否则为0。例：1{2=3}=0,1{1+1=2}=1用T(y)i表示T(y)的第i个元素，则T(y)i=l{y=i}根据参数<p的意义(<pi表示第i个取值的概率分布)，可推出:

p(y;。)=而V=i}p(y;。)=朴E}/{7...就£3lg}°『(小理(加…碗-E匕|(7®Lexp((T(y))ilog(01)+(T(!/))2log(内)+…+(1—£：二；(丁5)))log(@Q)cxp((T(y))ilog(%/以)+(T(y))2bg(曲/娟+…+ log(a-i/<M+bg(c〃))My)exp(7，T(y)-a(〃))可得:log(珈/如log(如AMn= ;10gsi/<Ma(q)=Tog(以)咐)=I.证明多项式分布式指数分布族。再用n表示（p：/=IogOkMe”史<t>k6Me”。人•£e”。人•£e”£6=1

i=l（2）根据上述假设（3）中自然参数和输入x的线性关系，可求得:（3）根据上述假设（2）中的输出h（x）=E[T（y）|x],可求得:he(x)=E[T(y)|x;0]1{〃=1}l{y=A:-1}010252)=1exp(^i)

OXp(^T)称这种回归算法为softmax回归，是logistic回归的推广。Softmax回归的训练方法和logistic相似，通过极大似然估计找到参数6,其对数似然性为:mW=Ebgp（y"3"；e）

再通过梯度上升或牛顿方法找对数似然性的最大值，即可求出参数e»第五课生成学习算法本次课程大纲：1、生成学习算法2、高斯判别分析（GDA,GaussianDiscriminantAnalysis）高斯分布（简要）对比生成学习算法&判别学习算法（简要）3、朴素贝叶斯4、Laplace平滑复习：分类算法：给出一个训练集，若使用logistic回归算法，其工作方式是观察这组数据，尝试找到一条直线将图中不同的类分开，如下图。之前讲的都是判别学习算法，本课介绍一种不同的算法：生成学习算法。1、生成学习算法例：对恶性肿瘤和良性肿瘤的分类除了寻找一个将两类数据区分的直线外，还可以用如下方法：遍历训练集，找到所有恶性肿瘤样本，直接对恶性肿瘤的特征建模：同理，对良性肿瘤建模。对一个新的样本分类时，即有一个新的病人时，要判断其是恶性还是良性，用该样本分别匹配恶性肿瘤模型和良性肿瘤模型，看哪个模型匹配的更好，预测属于恶性还是良性。这种方法就是生成学习算法。两种学习算法的定义：判别学习算法：直接学习p(y|x),即给定输入特征，输出所属的类或学习得到一个假设hB(x),直接输出0或1生成学习算法：对p(x|y)进行建模，p(x|y)表示在给定所属的类的情况下，显示某种特征的概率。处于技术上的考虑，也会对p(y)进行建模。p(x|y)中的x表示一个生成模型对样本特征建立概率模型，y表示在给定样本所属类的条件下例：在上例中，假定一个肿瘤情况y为恶性和良性，生成模型会对该条件下的肿瘤症状x的概率分布进行建模- 对p(x|y)和p(y)建模后，根据贝叶斯公式p(y|x)=p(xy)/p(x)=p(x|y)p(y)/p(x),可以计算：p(y=l|x)=p(x|y=l)p(y=l)/p(x),其中，p(x)=p(x|y=O)p(y=O)+p(x|y=l)p(y=l)2、高斯判别分析GDAGDA是一种生成学习算法。GDA的假设条件:假设输入特征XGRn,并且是连续值。假设p(x|y)满足高斯分布高斯分布基础知识：设随机变量z满足多元高斯分布，z~N(p，E),均值向量为P，协方差矩阵为Z。其概率密度函数为：以工；出E)=.°XP(W(工一।(工一")多元高斯分布为一元高斯分布的推广，也是钟形曲线，z是一个高维向量。多元高斯分布注意两个参数即可：均值向量p协方差矩阵z=E[(Z-E[Z])(Z-E[Z])t]=E[(x-m)(x-p)t]多元高斯分布图：左图：p=0,Z=I(单位矩阵)中图：尸0,X=0.6l,图形变陡峭右图：口=0,E=2I,图形变扁平三图中M=0,10.50.51；工=10.80.81三图中M=0,10.50.51；工=10.80.81J可见增加矩阵对角元素的值，即变量间增加相关性,高斯曲面会沿zl=z2（两个水平轴）方向趋于扁平。其水平面投影图如下:即增加2对角线的元素，图形会沿45°角，偏转成一个椭圆形状。若Z若Z对角线元素为负，图形如下:1 -0.5-0.5 11 1 -0.5-0.5 11 -0.8-0.8 130.80.81不同p的图形如下:M分别为:-0.5

0-1-1.5y决定分布曲线中心的位置。GDA拟合:给出训练样本如下图所示:观察正样本(图中的x),拟合正样本的高斯分布，如图中左下方的圆，表示p(x|y=l)观察负样本(图中的圈)，拟合负样本的高斯分布，如图中右上方的圆，表示p(x|y=O)通过这两个高斯分布的密度函数，定义出两个类别的分隔器，即图中的直线这条分隔器宜线比之前的logistic拟合的直线要复杂GDA模型：yzBernoulli（^）x\y—0zE）x\y=1z写出其概率分布：p（y）=/P（h®=0）=加二Z0exp（一,（1・谢」（工一闲P（l|y=l）=（27T）n/；E1/2exp（J（工一出）'£1（丁一”）参数包括（P，po,pl,3对数似然性为：m=logjjp（工⑴，严:

d=l

m=logJJp（yl/；〃oM,Z）P（"0）.

i=l由于第一个等式为xy的联合概率，将这个模型命名为联合似然性(Jointlikelihood)o*对比logistic回归中的对数似然性：m1(0)=logJ""!p(yw|xw；0)由于计算的是y在x条件下的概率，将此模型命名为条件似然性(conditionallikelihood)通过对上面对数似然性求极大似然估计，参数的结果为：1二。{严=1}，=1-£；小{*=0}〃 _ £21{-=1}工⑴1工s=— 工⑴-)(工⑴一"W))74=1<p:训练样本中标签为1的样本所占的比例M0：分母为标签为0的样本数，分子是对标签为0的样本的x(i)求和，结合起来就是对对标签为0的样本的x(i)求均值，与高斯分布参数p为均值的意义相符pl：与pO同理，标签改为1GDA预测：预测结果应该是给定x的情况下最可能的y,等式左边的运算符argmax表示计算p(y|x)最大时的y值，预测公式如下：argmaxp(j/|x)My)p(y)argmaxp(j/|x)=argmax - y p(")=argmaxp(x|3/)p(y).因为p(x)独立于y,所以可以忽略p(x)。*如果p(y)为均匀分布，即每种类型的概率都相同，那么也可以忽略p(y)，要求的就是使p(x|y)最大的那个y。不过这种情况并不常见。GDA和logistic回归的联系:例：假设有一个一维训练集，包含一些正样本和负样本，如下图x轴的叉和圈，设叉为0,圈为1,用GDA对两类样本分别拟合高斯概率密度函数p(x|y=0)和p(x|y=l),如下图的两个钟形曲线。沿x轴遍历样本，在x轴上方画出其相应的p(y=l|x)。如选x轴靠左的点，那么它属于1的概率几乎为0,p(y=l|x)=0,两条钟形曲线交点处，属于0或1的概率相同，p(y=l|x)=0.5,x轴靠右的点，输出1的概率几乎为1,p(y=l|x)=l。最终发现，得到的曲线和sigmoid函数曲线很相似。简单来讲，就是当使用GDA模型时,p(x|y)属于高斯分布，计算p(y|x)时，几乎能得到和logistic回归中使用的sigmoid函数一样的函数。但实际上还是存在本质区别的。使用生成学习算法的优缺点：给出两个推论：推论1：x|y服从高斯分布=>p(y=l|x)是logistic函数该推论在反方向不成立。推论2：x|y=l~Poisson(Xl),x|y=0~Poisson(XO)=>p(y=l|x)是logistic函数x|y=l~Poisson(入1)表示x|y=l服从参数为XI泊松分布推论3：x|y=l~ExpFamily(r]l),x|y=0~ExpFamily(r]0)=>p(y=l|x)是logistic函数推论2的推广，即x|y的分布属于指数分布族，均可推出结论。显示了logistic回归在建模假设选择方面的鲁棒性。优点：推论1反方向不成立，因为x|y服从高斯分布这个假设更强，GDA模型做出了一个更强的假设，所以，若x|y服从或近似服从高斯分布，那么GDA会比logistic回归更好，因为它利用了更多关于数据的信息，即算法知道数据服从高斯分布。缺点：如果不确定x|y的分布情况，那么判别算法logistic回归性能更好。例如，预先假设数据服从高斯分布,但是实际上数据服从泊松分布，根据推论2,logistic回归仍能获得不错的效果。生成学习算法比判决学习算法需要更少的数据。如GDA的假设较强，所以用较少的数据能拟合出不错的模型。而logistic回归的假设较弱，对模型的假设更为健壮，拟合数据需要更多的样本。3、朴素贝叶斯另一种生成学习算法。例：垃圾邮件分类实现一个垃圾邮件分类器，以邮件输入流作为输入，确定邮件是否为垃圾邮件。输出y为。1},1为垃圾邮件，0为非垃圾邮件。首先，要将邮件文本表示为一个输入向量x,设已知一个含有n个词的字典，那么向量x的第i个元素。1}表示字典中的第i个词是否出现在邮件中，x示例如下：aaardvarkaardwolf1buy0Jzygmurgy要对p(x|y)建模，x是一个n维的{0,1}向量，假设n=50000,那么x有2A50000种可能的值，一种方法是用多项式分布进行建模(伯努利分布对01建模，多项式分布对k个结果建模)，这样就需要”50000-1个参数，可见参数过多，下面介绍朴素贝叶斯的方法。假设xi在给定y的时候是条件独立的，则x在给定y下的概率可简化为：P(Q,…，工50000®)=p(x\\y)pixi\y,Xi)p(xs\y,xi,X2)•••p(xsooooh，»•••,^49999)=P(^lMHghOp(司y)….(±50000》)n=JJp(词!/)t=l这个假设直观理解为，已知一封邮件是不是垃圾邮件(y),以及一些词是否出现在邮件中，这些并不会帮助你预测其他的词是否出现在邮件中。虽然这个假设不是完全正确的，但是朴素贝叶斯依然应用于对邮件进行分类，对网页进行分类等用途。*对于朴素贝叶斯，我的理解为：通过指定一些垃圾邮件的关键词来计算某个邮件是垃圾邮件的概率。具体讲，就是给定字典后，给出每个词的p(xi|y=l),即这个词xi在垃圾邮件中出现的概率，然后对于一个邮件，将邮件所有词的p(xi|y)的相乘，就是邮件为垃圾邮件的概率。再简化一些，规定p(xi|y=l)={0,l},即划定一些关键词，这些关键词在邮件中出现的概率就是这封邮件为垃圾邮件的概率。模型参数包括：0i|y=l=p(xi=l|y=l)<Di|y=0=p(xi=l|y=0)

①y=p(y=l)

联合似然性:m£(如，如吟1)=ne，严)

i=l求得参数结果：Ojg0j|y=O如£3g=15=Ojg0j|y=O如£31{“)=1}-1{7？=1八*=0}£♦1{…。}-£乙1{严=1}mei|y=l的分子为标记为1的邮件中出现词j的邮件数目和，分母为垃圾邮件数，总体意义就是训练集中出现词j的垃圾邮件在垃圾邮件中的比例。0i|y=O就是出现词j的非垃圾邮件在非垃圾邮件中的比例。0y就是垃圾邮件在所有邮件中的比例。求出上述参数，就知道了p(x|y)和p(y),用伯努利分布对p(y)建模，用上式中p(xi|y)的乘积对p(x|y)建模，通过贝叶斯公式就可求得p(y|x)*实际操作中，例如将最近两个月的邮件都标记上“垃圾”或“非垃圾”，然后得到(x(l),y(l))...(x(m),y(m)),x(i)为词向量，标记出现在第i个邮件中的词，y(i)为第i个邮件是否是垃圾邮件。用邮件中的所有出现的词构造字典，或者选择出现次数k次以上的词构造字典。朴素贝叶斯的问题：设有一封新邮件中出现一个字典没有的新词，设其标号为30000,因为这个词在垃圾邮件和非垃圾邮件中都不存在，则p(x3000|y=l)=0,p(x30000|y=0)=0,计算p(y=l|x)如下：p(y=l|x)=p(x|y=l)p(y=l)/(p(x|y=l)p(y=l)+p(x|y=0)p(y=0))STp(x|y=l)=p(x|y=0)=0(p(x30000|y=l)=p(x30000|y=0)=0.则乘积为0),则p(y=l|x)=0/0,则结果是未定义的。其问题在于，统计上认为p(x30000|y)=0是不合理的。即在过去两个月邮件里未出现过这个词，就认为其出现概率为0,并不合理。概括来讲，即之前没有见过的事件，就认为这些事件不会发生，是不合理的。通过Laplace平滑解决这个问题。4、Laplace平滑根据极大似然估计，P(y=l)=#"l"s/(#"O"s+#"l"s),即y为1的概率是样本中1的数目在所有样本中的比例。Laplace平滑就是将分子分母的每一项都加1,,即：p(y=l)=(#"l"s+l)/(#"0"s+l+riMs+l)例：给出一支球队5场比赛的结果作为样本，5场比赛都输了，记为0,那么要预测第六场比赛的胜率，按照朴素贝叶斯为：p(y=l)=0/(5+0)=0,即样本中没有胜场，则胜率为0,显然这是不合理的。按照Laplace平滑处理，p(y=l)=0+1/(5+1+0+1)=1/7,并不为0,且随着负场次的增加，p(y=l)会一直减小，但不会为0。更一般的，若y取k中可能的值，比如尝试估计多项式分布的参数，得到下式：如一m,即值为j的样本所占比例，对其用Laplace平滑如下式：%= •对于朴素贝叶斯，得到的结果为：_£3时)=1八♦=1}+16g"一£下{”)=1}+2—_W=")=o}+1*。--£21{/)=0}+2-在分子上加1,分母上加2,解决了0概率的问题。第六课朴素贝叶斯本次课程大纲：1、朴素贝叶斯-朴素贝叶斯事件模型2、神经网络（简要）3、支撑向量机（SVM）铺垫-最大间隔分类器复习：1、朴素贝叶斯一种生成学习算法，对p（x|y）建模。例：垃圾邮件分类以邮件输入流作为输入，输出y为{0,1},1为垃圾邮件，。为非垃圾邮件。将邮件文本表示为一个输入向量xxie{0,1},表示字典中的第i个词是否出现在邮件中x长度为n,n为字典的词数3）该模型称为多元伯努利事件模型aaardvark

aardwolfbuyzygmiirgy

假设Xi在给定y的时候是条件独立的，则x在给定y下的概率可简化为：P(G tsooooW)=pCn|y)p(工2®,工i)p(g|y,乃,n)…p(x5oooo|j/,工i,…，工.iwoo)=p(x1|y)p(工2W)p(工3旧)…p(x5/oooo\y)n=根据朴素贝叶斯公式，求p(y|x)根据朴素贝叶斯公式，求p(y|x)最大时的y：argmaxp(^|x)=成也)p(y)argmax y p(工)argmaxp(x|t/)p(j/).y算法变化版本：1)让xi取多个值,xi€{l,2，…,k},类似上式有：p(x|y)=TTP(xi|y),但是p(xi|y)变成多项式分布，而不是伯努利分布。例：估计房屋面积预测房屋能否被卖掉，将房屋面积分成几个离散区间，如0-,1000为xi=l,1000-1500为xi=2,1500-2000为xi=3,2000以上为xi=42)如上例处理邮件(文本)中，x向量记录每个词出现的次数(而不是是否出现)多项式事件模型/(0(0 (0\接上例，给出一封邮件，将它表示成特征向量：(/，12，•一，]凡),ni表示邮件中词的数量，xj是个到词典的索引，表示该词在词典的位置。如邮件中有300个词，那么特征向量x(i)长度为300,若词典有50000个词，每个元素xj的取值范围为{1,2,.,50000}♦P(xy)=(]-[p(xjy))p(y)则生成模型的联合概率p(xy)为:n为邮件长度上式理解：邮件内容满足一些概率分布，有一些随机分布在生成这些邮件。过程为：首先确定y,即是否为垃圾邮件，决定一个人是否向你发送垃圾邮件后，遍历邮件的300个词，按照某种概率分布生成一些词，基于他们是否向你发送垃圾邮件模型参数：(iPkly.1=P(Xj=A|y=1)表示某人决定向你发送垃圾邮件(y=i)时，选择词k的概率，类似有：3kb=o=P(Xj=A|y=。)<Py=p(y=1)给出训练集后，求极大似然估计：m°。,0i|y=l)=i=lm(z \=JJI]7「(工丁|%刖=0，厢=1))P®⑴;。!/).i=l\J=1 /得到：*~ £飓1{-=im_£圈£蜀1{4)=人-八严=0}- £匚1{/)=0m——=1}%= .m上面第一个式子，分子的意思是，对所有标签为1的邮件求和，之后对垃圾邮件中的词k求和，所以分子实际上就是训练集中所有垃圾邮件中词k出现的次数。分母是训练集中所有垃圾邮件的长度。比值的含义就是所有垃圾邮件中，词k占的比例。表示生成垃圾邮件时选择词k的概率。应用Laplace平滑，分子加1,分母加总词数(字典大小，xi可能取值的数目)：_-W=2=i}+i的1--汇力{/=1}"卜1£随£%1{3"=A八*=0}+1的"*" —{/)=o}%+IH-事实上，多项式事件模型比之前的模型要好，可能是因为考虑了词出现的次数这个因素。但此问题仍存在争论。非线性分类算法例:logistic回归中，假设值小于0.5预测0,大于0.5预测1。即给定一个训练集，logistic回归会找到一条直线(牛顿方法或梯度下降)，将正负样本合理分开.但有时数据不能被一条直线分开，需要一种算法，学习非线性的分界线。上一讲的推论：x|y=l~ExpFamily(ql),x|y=0~ExpFamily(q0)=>p(y=l|x)是logistic函数即x|y的分布属于指数分布族，可推出后验分布是logistic函数。朴素贝叶斯模型也属于指数分布族，所以也是用logistic线性分类器。下面介绍一种非线性分类器。2、神经网络假设特征是x0,xl,x2,x3,x0设置为1,用连线表示logistic回归单元，圆圈表示计算节点，下图中间的节点以x0等特征作为输入，h/x)作为输出，这是一个sigmoid函数。为了找到非线性的界限，需要找到一种方式，表示出能够输出非线性分界限的假设。

将之前画的小单元拼在一起，得到神经网络。特征输入到若干个sigmoid单元，在输入到另外一个sigmoid单元，得到输出。中间节点的输出值设为al,a2,a3。这些中间节点称为隐藏层，神经网络可以由多个隐层。每个中间节点有一系列参数:%=g(x3a)),g(z)=7-X—X।ca2,a3同理。g为sigmoid函数。最终的输出值为:3G)=9(k心)其中，a向量由al,a2,a3组成。一种学习模型参数的方法是，利用成本函数j(e),使用梯度下降使j(e)最小。即用梯度下降使得神经网络的预测结果和你观察到的训练集中的样本标签尽可能接近。在神经网络中，这种方法称为反向传播。3、支撑向量机铺垫-最大间隔分类器另外一种能生成非线性分类器的学习算法。本节课先介绍另外一类线性分类器，在下一讲或者下下讲中，利用支撑向量机的想法，进行一些巧妙的改动和扩展，让它可以生成非线性分界线。两种对于分类的直观理解：考虑logistic回归，计算Ux：输出1<=>eTx>=o；输出o<=>eTx<o如果Mx>〉。，相当确定的预测y=l；如果eTx<<0,相当确定的预测y=0对于所有的i，如果y=l,eTx(il»o,如果y=o,eTx(i)«o,那么我们认为分类器是良好的。即如果我们根据训练集找到了参数，我们的学习算法不仅需要保证分类结果正确，更要进一步保证分类结果的确定性。假设训练集是线性可分割的，即一定有一条直线可以将训练集分开。那么直观来看,我们一定会选择和正负样本都有一定距离的直线。后面讲到分类器的几何间隔时，再正式讨论。支撑向量机中改动的符号：输出ye{-1,+1)h输出的假设值也改为{-1,+1}g(z)={1,如果z>=0;-1,如果z<0}之前在使用式：h6(x尸g(Mx)时，假设xO=l且X为n+1维向量，现在忽略这两个假设，表示为：hw,b(x)=g(wTx+b),这里的b相当于原来的w相当于原来。除去剩余部分，长度为n维。将截距b单提出来，方便引出支撑向量机。函数间隔:

一个超平面(w,b)和某个特定训练样本(x(i),y(i))对应的函数间隔定义为一个超平面(w,b)和整个训练集的函数间隔定义为分界线距离样本越远效果越好)几何间隔一个超平面(w,b)和某个特定训练样本(x(i),y(i))对应的函数间隔定义为一个超平面(w,b)和整个训练集的函数间隔定义为分界线距离样本越远效果越好)几何间隔隔线的距离AB就是几何距离即相对于整个训练集的函数间隔定义为所有相对于样本的函数间隔的最坏情形(上述讲到几何距离定义为：一个训练样本对应的点到由超平面确定的分隔线的距离。如下图A到分参数(w,b)定义了一个分类器，例如定义了一个线性分界线如果y(i)=l，为了获得较大的函数间隔，需要令wTx(i)+b>>0如果y(i)=-l,为了获得较大的函数间隔，需要令wTx(i)+b<<0如果y(i"wTx(i)+b)>0,意味着分类结果正确和分隔线垂直的单位向量表示为：w/||w||,AB这段距离表示为丫(i),丫上有小三角表示函数间隔，没有表示几何间隔。若A点表示x(i),那么点B表示为：由于点B在分隔线上，它应该还满足："扁)可以解出：⑴“工⑴+b/®/⑴b。=(血］+阿,上式说明，对于一个训练样本x(i),到由参数W和b确定的分隔平面之间的距离，可以由上式得到。由于上述一直假设对样本进行了正确的分类，所以更一般的，将几何间隔定义为：这个定义和函数间隔很相似，不同点是对向量W进行了标准化。同样，希望几何间隔也是越大越好。结论：如果I|w|1=1,函数间隔等于几何间隔。更一般的，几何间隔等于函数间隔除以||w|I。一个超平面(w,b)和整个训练集的几何间隔定义为：(a)7=min7•和函数间隔类似,取样本中最小的几何间隔。最大间隔分类器可以看做是支撑向量机的前身,是一种学习算法，选择特定的W和b,使几何间隔最大化。最大分类间隔是下述这样的优化问题：max7mb7s.t.y⑴ ⑴+6)27,z=1,....mIHI=L即选择Y，w,b是丫最大，同时满足条件：所选取的最大几何间隔必须保证每个样本的结合间隔至少为丫。最大间隔分类器的效果和logistic回归结果差不多好，深入研究这个分分类器，可以用一种更巧妙的方法让其支持无限维的特征空间，得到有效的非线性分类器第七课最优间隔分类器问题本次课程大纲：1、最优间隔分类器2、原始优化问题&对偶优化问题(KKT条件)3、SVM对偶问题4、核方法(下一讲)复习：支撑向量机中改动的符号：输出yF{-l,+l}h输出的假设值也改为g(z)={1,如果z>=0;-1,如果z<0}hw.b(x)=g(wTx+b),这里的b相当于原来的w相当于原来。除去。0剩余部分，长度为n维。将截距b单提出来，方便引出支撑向量机。函数间隔：一个超平面(w,b)和某个特定训练样本(x(i),y(i))对应的函数间隔定义为:夕⑴=严(mJx+b).参数(w,b)定义了一个分类器，例如定义了一个线性分界线。如果y(i)=l,为了获得较大的函数间隔，需要令wTx(i)+b>>0；如果y(i)=-l,为了获得较大的函数间隔，需要令wTx(i)+b<<0如果y(D(wTx(i)+b)>0,意味着分类结果正确一个超平面(w,b)和整个训练集的函数间隔定义为：7=min夕⑴.3=1,…,m即相对于整个训练集的函数间隔定义为所有相对于样本的函数间隔的最坏情形(上述讲到,分界线距离样本越远效果越好)。几何间隔：几何间隔定义为：f(―)-这个定义和函数间隔很相似，不同点是对向量W进行了标准化。同样，希望几何间隔也是越大越好。结论：如果I|w|1=1,函数间隔等于几何间隔。更一般的，几何间隔等于函数间隔除以I|w|I.一个超平面(w,b)和整个训练集的几何间隔定义为：7=min

d=l,…,m和函数间隔类似，取样本中最小的几何间隔。性质：可以任意比例缩放W和b,因为任意缩放w和b都不会改变超平面wTx+b=0的位置。这一性质在后续讨论中带来很大便利。1、最优间隔分类器最优间隔分类器可以看做是支撑向量机的前身，是一种学习算法，选择特定的W和b,使几何间隔最大化。最优分类间隔是下述这样的优化问题：max^,Wi67s.t. a:⑴+b）27,i=1,...,mIHl=i.即选择Y，w,b使丫最大，同时满足条件：所选取的最大几何间隔必须保证每个样本的几何间隔至少为Y。即，找到一个超平面，在将正负样本分开的同时，使超平面到正负样本间的距离尽可能大。由于w和b可随意缩放，约束条件||w||=l,使得函数间隔等于几何间隔。但是这个约束本身是一个非常糟糕的非凸性约束。要求解的参数w在一个球体表面，如果想得到一个凸优化问题，必须保证如梯度下降算法这种局部最优值搜索算法不会找到局部最优值，而非凸性约束不能满足这个条件，所以需要改变优化问题。为了解决上述问题，提出下面的最优化问题：Amax7wfc扁s.t.严（w7工⑴+b）?夕,z=I,....m即将函数间隔除以I|w|I的值最大化，而这个值其实就是几何间隔，只是上一个优化问题的另一种表述。最优化目标是，最大化几何间隔，同时保证函数间隔不小于丫八，即求最大的Y"，但是丫八上限是最小的函数间隔的值。对w添加约束条件：丫A=1，即函数间隔为1，即使,"（"/工⑴+6）式子的最小值为1。这个一个隐含的缩放条件。将这个约束加入到第二个最优化问题中，得到最终的最优间隔分类器：min-y.w.b511Ml2s.t.y⑴（u/工⑴+b）21,i=1,...,m这是一个凸优化问题，且没有局部最优值，可以通过梯度下降找到全局最优值。2,原始优化问题&对偶优化问题（KKT条件）原始问题如要求下式的值：minu,f(w)s.t.hi(w)=0,i=1,...,Z.即最小化函数f(w),并满足约束条件hi(w)=0,可以将hi写成0向量。创建拉格朗日算子：£(孙夕)=/(w)+£即

i=l即等于原始目标函数加限制函数的线性组合，其中参数B称为拉格朗日乘数。则，如果对下式求偏导数置为0,即可求出解：de八de——=0；>ttt=0,

dwid(3i对上述两个偏导数方程求解，检查得到的解是否为最小值即可.拉格朗日乘数法的一般形式，也称为原始问题：min”，f(w)s.t.<0,ht(w)=0,i=1,...此时，拉格朗日算子为：k I£(w,a,°)=/(w)4-£ongi(w)+£0ihi(w).

i=l i=l此时a和B为拉格朗日乘数，定义:

Op(w)=max£(w,a,/?).a,0：Qi>Q上式中的p表示原始问题(primal),如果w违反了约束条