下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 斯坦福大学机器学习课程个人笔记完整版

斯坦福大学机器学习课程个人笔记完整版.pdf

斯坦福大学机器学习课程个人笔记完整版

starsundog
2017-11-03 0人阅读 举报 0 0 暂无简介

简介:本文档为《斯坦福大学机器学习课程个人笔记完整版pdf》,可适用于工程科技领域

CS机器学习(个人笔记)目录()线性回归、logistic回归和一般回归()判别模型、生成模型与朴素贝叶斯方法()支持向量机SVM(上)()支持向量机SVM(下)()规则化和模型选择()Kmeans聚类算法()混合高斯模型和EM算法()EM算法()在线学习()主成分分析()独立成分分析()线性判别分析()因子分析()增强学习()典型关联分析()偏最小二乘法回归这里面的内容是我在年上半年学习斯坦福大学《机器学习》课程的个人学习笔记内容主要来自AndrewNg教授的讲义和学习视频。另外也包含来自其他论文和其他学校讲义的一些内容。每章内容主要按照个人学习时的思路总结得到。由于是个人笔记里面表述错误、公式错误、理解错误、笔误都会存在。更重要的是我是初学者千万不要认为里面的思路都正确。如果有疑问的地方请第一时间参考AndrewNg教授的讲义原文和视频再有疑问的地方可以找一些大牛问问。博客上很多网友提出的问题我难以回答因为我水平确实有限更深层次的内容最好找相关大牛咨询和相关论文研读。如果有网友想在我这个版本基础上再添加自己的笔记可以发送Email给我我提供原始的worddocx版本。另本人目前在科苑软件所读研马上三年了方向是分布式计算主要偏大数据分布式处理平时主要玩Hadoop、Pig、Hive、Mahout、NoSQL啥的关注系统方面和数据库方面的会议。希望大家多多交流以后会往博客上放这些内容机器学习会放的少了。Anyway祝大家学习进步、事业成功!对回归方法的认识JerryLeadcsxulijiegmailcom年月日摘要本报告是在学习斯坦福大学机器学习课程前四节加上配套的讲义后的总结与认识。前四节主要讲述了回归问题属于有监督学习中的一种方法。该方法的核心思想是从离散的统计数据中得到数学模型然后将该数学模型用于预测或者分类。该方法处理的数据可以是多维的。讲义最初介绍了一个基本问题然后引出了线性回归的解决方法然后针对误差问题做了概率解释。问题引入假设有一个房屋销售的数据如下:面积(m^)销售价钱(万元)helliphellip这个表类似于北京环左右的房屋价钱我们可以做出一个图x轴是房屋的面积。y轴是房屋的售价如下:如果来了一个新的面积假设在销售价钱的记录中没有的我们怎么办呢?我们可以用一条曲线去尽量准的拟合这些数据然后如果有新的输入过来我们可以在将曲线上这个点对应的值返回。如果用一条直线去拟合可能是下面的样子:绿色的点就是我们想要预测的点。首先给出一些概念和常用的符号。房屋销售记录表:训练集(trainingset)或者训练数据(trainingdata),是我们流程中的输入数据一般称为x房屋销售价钱:输出数据一般称为y拟合的函数(或者称为假设或者模型):一般写做y=h(x)训练数据的条目数(#trainingset),:一条训练数据是由一对输入数据和输出数据组成的输入数据的维度n(特征的个数#features)这个例子的特征是两维的结果是一维的。然而回归方法能够解决特征多维结果是一维多离散值或一维连续值的问题。学习过程下面是一个典型的机器学习的过程首先给出一个输入数据我们的算法会通过一系列的过程得到一个估计的函数这个函数有能力对没有见过的新数据给出一个新的估计也被称为构建一个模型。就如同上面的线性回归函数。线性回归线性回归假设特征和结果满足线性关系。其实线性关系的表达能力非常强大每个特征对结果的影响强弱可以有前面的参数体现而且每个特征变量可以首先映射到一个函数然后再参与线性计算。这样就可以表达特征与结果之间的非线性关系。我们用XXXn去描述feature里面的分量比如x=房间的面积x=房间的朝向等等我们可以做出一个估计函数:theta在这儿称为参数在这的意思是调整feature中每个分量的影响力就是到底是房屋的面积更重要还是房屋的地段更重要。为了如果我们令X=就可以用向量的方式来表示了:我们程序也需要一个机制去评估我们theta是否比较好所以说需要对我们做出的h函数进行评估一般这个函数称为损失函数(lossfunction)或者错误函数(errorfunction)描述h函数不好的程度在下面我们称这个函数为J函数在这儿我们可以做出下面的一个错误函数:这个错误估计函数是去对x(i)的估计值与真实值y(i)差的平方和作为错误估计函数前面乘上的是为了在求导的时候这个系数就不见了。至于为何选择平方和作为错误估计函数讲义后面从概率分布的角度讲解了该公式的来源。如何调整theta以使得J(theta)取得最小值有很多方法其中有最小二乘法(minsquare)是一种完全是数学描述的方法和梯度下降法。梯度下降法在选定线性回归模型后只需要确定参数theta就可以将模型用来预测。然而theta需要在J(theta)最小的情况下才能确定。因此问题归结为求极小值问题使用梯度下降法。梯度下降法最大的问题是求得有可能是全局极小值这与初始点的选取有关。梯度下降法是按下面的流程进行的:)首先对theta赋值这个值可以是随机的也可以让theta是一个全零的向量。)改变theta的值使得J(theta)按梯度下降的方向进行减少。梯度方向由J(theta)对theta的偏导数确定由于求的是极小值因此梯度方向是偏导数的反方向。结果为迭代更新的方式有两种一种是批梯度下降也就是对全部的训练数据求得误差后再对theta进行更新另外一种是增量梯度下降每扫描一步都要对theta进行更新。前一种方法能够不断收敛后一种方法结果可能不断在收敛处徘徊。一般来说梯度下降法收敛速度还是比较慢的。另一种直接计算结果的方法是最小二乘法。最小二乘法将训练特征表示为X矩阵结果表示成y向量仍然是线性回归模型误差函数不变。那么theta可以直接由下面公式得出但此方法要求X是列满秩的而且求矩阵的逆比较慢。选用误差函数为平方和的概率解释假设根据特征的预测结果与实际结果有误差isin(𝑖)那么预测结果𝜃𝑇𝑥(i)和真实结果𝑦(𝑖)满足下式:一般来讲误差满足平均值为的高斯分布也就是正态分布。那么x和y的条件概率也就是这样就估计了一条样本的结果概率然而我们期待的是模型能够在全部样本上预测最准也就是概率积最大。这个概率积成为最大似然估计。我们希望在最大似然估计得到最大值时确定theta。那么需要对最大似然估计公式求导求导结果既是这就解释了为何误差函数要使用平方和。当然推导过程中也做了一些假定但这个假定符合客观规律。带权重的线性回归上面提到的线性回归的误差函数里系统都是没有权重。带权重的线性回归加入了权重信息。基本假设是其中假设𝑤(i)符合公式其中x是要预测的特征这样假设的道理是离x越近的样本权重越大越远的影响越小。这个公式与高斯分布类似但不一样因为w(i)不是随机变量。此方法成为非参数学习算法因为误差函数随着预测值的不同而不同这样theta无法事先确定预测一次需要临时计算感觉类似KNN。分类和对数回归一般来说回归不用在分类问题上因为回归是连续型模型而且受噪声影响比较大。如果非要应用进入可以使用对数回归。对数回归本质上是线性回归只是在特征到结果的映射中加入了一层函数映射即先把特征线性求和然后使用函数g(z)将最为假设函数来预测。g(z)可以将连续值映射到和上。对数回归的假设函数如下线性回归假设函数只是𝜃𝑇𝑥。对数回归用来分类问题也就是预测结果属于或者的二值分类问题。这里假设了二值满足伯努利分布也就是当然假设它满足泊松分布、指数分布等等也可以只是比较复杂后面会提到线性回归的一般形式。与第节一样仍然求的是最大似然估计然后求导得到迭代公式结果为可以看到与线性回归类似只是𝜃𝑇𝑥(i)换成了ℎ𝜃(𝑥(𝑖))而ℎ𝜃(𝑥(𝑖))实际上就是𝜃𝑇𝑥(i)经过g(z)映射过来的。牛顿法来解最大似然估计第和第节使用的解最大似然估计的方法都是求导迭代的方法这里介绍了牛顿下降法使结果能够快速的收敛。当要求解f(theta)=时如果f可导那么可以通过迭代公式来迭代求解最小值。当应用于求解最大似然估计的最大值时变成求解ℓprime(𝜃)=的问题。那么迭代公式写作当theta是向量时牛顿法可以使用下面式子表示其中是ntimesn的Hessian矩阵。牛顿法收敛速度虽然很快但求Hessian矩阵的逆的时候比较耗费时间。当初始点X靠近极小值X时牛顿法的收敛速度是最快的。但是当X远离极小值时牛顿法可能不收敛甚至连下降都保证不了。原因是迭代点Xk不一定是目标函数f在牛顿方向上的极小点。一般线性模型之所以在对数回归时使用的公式是由一套理论作支持的。这个理论便是一般线性模型。首先如果一个概率分布可以表示成时那么这个概率分布可以称作是指数分布。伯努利分布高斯分布泊松分布贝塔分布狄特里特分布都属于指数分布。在对数回归时采用的是伯努利分布伯努利分布的概率可以表示成其中得到Phi=eeta这就解释了对数回归时为了要用这个函数。一般线性模型的要点是)y|xtheta满足一个以eta为参数的指数分布那么可以求得eta的表达式。)给定x我们的目标是要确定T(y)大多数情况下T(y)=y那么我们实际上要确定的是h(x)而h(x)=Ey|x。(在对数回归中期望值是Phi因此h是Phi在线性回归中期望值是mu而高斯分布中eta=mu因此线性回归中h=𝜃𝑇𝑥)。)eta=𝜃𝑇𝑥Softmax回归最后举了一个利用一般线性模型的例子。假设预测值y有k种可能即yisin{,,hellip,k}比如k=时可以看作是要将一封未知邮件分为垃圾邮件、个人邮件还是工作邮件这三类。定义那么这样即式子左边可以有其他的概率表示因此可以当做是k维的问题。T(y)这时候一组k维的向量不再是y。即T(y)要给出y=i(i从到k)的概率应用于一般线性模型那么最后求得而y=i时求得期望值那么就建立了假设函数最后就获得了最大似然估计对该公式可以使用梯度下降或者牛顿法迭代求解。解决了多值模型建立与预测问题。学习总结该讲义组织结构清晰思路独特讲原因也讲推导。可贵的是讲出了问题的基本解决思路和扩展思路更重要的是讲出了为什么要使用相关方法以及问题根源。在看似具体的解题思路中能引出更为抽象的一般解题思路理论化水平很高。该方法可以用在对数据多维分析和多值预测上更适用于数据背后蕴含某种概率模型的情景。判别模型、生成模型与朴素贝叶斯方法JerryLeadcsxulijiegmailcom年月日星期六判别模型与生成模型上篇报告中提到的回归模型是判别模型也就是根据特征值来求结果的概率。形式化表示为𝑝(𝑦|𝑥𝜃)在参数𝜃确定的情况下求解条件概率𝑝(𝑦|𝑥)。通俗的解释为在给定特征后预测结果出现的概率。比如说要确定一只羊是山羊还是绵羊用判别模型的方法是先从历史数据中学习到模型然后通过提取这只羊的特征来预测出这只羊是山羊的概率是绵羊的概率。换一种思路我们可以根据山羊的特征首先学习出一个山羊模型然后根据绵羊的特征学习出一个绵羊模型。然后从这只羊中提取特征放到山羊模型中看概率是多少再放到绵羊模型中看概率是多少哪个大就是哪个。形式化表示为求𝑝(𝑥|y)(也包括𝑝(𝑦))y是模型结果x是特征。利用贝叶斯公式发现两个模型的统一性:由于我们关注的是y的离散值结果中哪个概率大(比如山羊概率和绵羊概率哪个大)而并不是关心具体的概率因此上式改写为:其中𝑝(𝑥|y)称为后验概率𝑝(𝑦)称为先验概率。由𝑝(𝑥|y)lowast𝑝(𝑦)=𝑝(𝑥,𝑦)因此有时称判别模型求的是条件概率生成模型求的是联合概率。常见的判别模型有线性回归、对数回归、线性判别分析、支持向量机、boosting、条件随机场、神经网络等。常见的生产模型有隐马尔科夫模型、朴素贝叶斯模型、高斯混合模型、LDA、RestrictedBoltzmannMachine等。这篇博客较为详细地介绍了两个模型:http:blogsciencenetcnhomephpmod=spaceuid=do=blogid=高斯判别分析(Gaussiandiscriminantanalysis))多值正态分布多变量正态分布描述的是n维随机变量的分布情况这里的mu变成了向量sigma也变成了矩阵Sigma。写作𝛮(𝜇,𝛴)。假设有n个随机变量𝑋,𝑋,hellip,𝑋𝑛。mu的第i个分量是E(X𝑖)而Sigmaii=Var(𝑋𝑖)Sigmaij=Cov(𝑋𝑖,𝑋𝑗)。概率密度函数如下:其中|Sigma|是Sigma的行列式Sigma是协方差矩阵而且是对称半正定的。当mu是二维的时候可以如下图表示:其中mu决定中心位置Sigma决定投影椭圆的朝向和大小。如下图:对应的Sigma都不同。)模型分析与应用如果输入特征x是连续型随机变量那么可以使用高斯判别分析模型来确定p(x|y)。模型如下:输出结果服从伯努利分布在给定模型下特征符合多值高斯分布。通俗地讲在山羊模型下它的胡须长度角大小毛长度等连续型变量符合高斯分布他们组成的特征向量符合多值高斯分布。这样可以给出概率密度函数:最大似然估计如下:注意这里的参数有两个mu表示在不同的结果模型下特征均值不同但我们假设协方差相同。反映在图上就是不同模型中心位置不同但形状相同。这样就可以用直线来进行分隔判别。求导后得到参数估计公式:Phi是训练样本中结果y=占有的比例。mu是y=的样本中特征均值。mu是y=的样本中特征均值。Sigma是样本特征方差均值。如前面所述在图上表示为:直线两边的y值不同但协方差矩阵相同因此形状相同。mu不同因此位置不同。)高斯判别分析(GDA)与logistic回归的关系将GDA用条件概率方式来表述的话如下:y是x的函数其中都是参数。进一步推导出这里的theta是的函数。这个形式就是logistic回归的形式。也就是说如果p(x|y)符合多元高斯分布那么p(y|x)符合logistic回归模型。反之不成立。为什么反过来不成立呢?因为GDA有着更强的假设条件和约束。如果认定训练数据满足多元高斯分布那么GDA能够在训练集上是最好的模型。然而我们往往事先不知道训练数据满足什么样的分布不能做很强的假设。Logistic回归的条件假设要弱于GDA因此更多的时候采用logistic回归的方法。例如训练数据满足泊松分布那么p(y|x)也是logistic回归的。这个时候如果采用GDA那么效果会比较差因为训练数据特征的分布不是多元高斯分布而是泊松分布。这也是logistic回归用的更多的原因。朴素贝叶斯模型在GDA中我们要求特征向量x是连续实数向量。如果x是离散值的话可以考虑采用朴素贝叶斯的分类方法。假如要分类垃圾邮件和正常邮件。分类邮件是文本分类的一种应用。假设采用最简单的特征描述方法首先找一部英语词典将里面的单词全部列出来。然后将每封邮件表示成一个向量向量中每一维都是字典中的一个词的值表示该词在邮件中出现表示未出现。比如一封邮件中出现了ldquoardquo和ldquobuyrdquo没有出现ldquoaardvarkrdquo、ldquoaardwolfrdquo和ldquozygmurgyrdquo那么可以形式化表示为:假设字典中总共有个词那么x是维的。这时候如果要建立多项式分布模型(二项分布的扩展)。多项式分布(multinomialdistribution)某随机实验如果有k个可能结局AAhellipAk它们的概率分布分别是pphellippk那么在N次采样的总结果中A出现n次A出现n次hellipAk出现nk次的这种事件的出现概率P有下面公式:(Xi代表出现ni次)对应到上面的问题上来把每封邮件当做一次随机试验那么结果的可能性有种。意味着pi有个参数太多不可能用来建模。换种思路我们要求的是p(y|x)根据生成模型定义我们可以求p(x|y)和p(y)。假设x中的特征是条件独立的。这个称作朴素贝叶斯假设。如果一封邮件是垃圾邮件(y=)且这封邮件出现词ldquobuyrdquo与这封邮件是否出现ldquopricerdquo无关那么ldquobuyrdquo和ldquopricerdquo之间是条件独立的。形式化表示为(如果给定Z的情况下X和Y条件独立):𝑃(𝑋|𝑍)=𝑃(𝑋|𝑌,𝑍)也可以表示为:𝑃(𝑋,𝑌|𝑍)=𝑃(𝑋|𝑍)𝑃(𝑌|𝑍)回到问题中这个与NLP中的n元语法模型有点类似这里相当于unigram。这里我们发现朴素贝叶斯假设是约束性很强的假设ldquobuyrdquo从通常上讲与ldquopricerdquo是有关系我们这里假设的是条件独立。(注意条件独立和独立是不一样的)建立形式化的模型表示:𝜙i|y==𝑝(𝑥𝑖=|𝑦=)𝜙i|y==𝑝(𝑥𝑖=|𝑦=)𝜙y=𝑝(𝑦=)那么我们想要的是模型在训练数据上概率积能够最大即最大似然估计如下:注意这里是联合概率分布积最大说明朴素贝叶斯是生成模型。求解得:最后一个式子是表示y=的样本数占全部样本数的比例前两个表示在y=或的样本中特征Xj=的比例。然而我们要求的是实际是求出分子即可分母对y=和y=都一样。当然朴素贝叶斯方法可以扩展到x和y都有多个离散值的情况。对于特征是连续值的情况我们也可以采用分段的方法来将连续值转化为离散值。具体怎么转化能够最优我们可以采用信息增益的度量方法来确定(参见Mitchell的《机器学习》决策树那一章)。比如房子大小可以如下划分成离散值:拉普拉斯平滑朴素贝叶斯方法有个致命的缺点就是对数据稀疏问题过于敏感。比如前面提到的邮件分类现在新来了一封邮件邮件标题是ldquoNIPScallforpapersrdquo。我们使用更大的网络词典(词的数目由变为)来分类假设NIPS这个词在字典中的位置是。然而NIPS这个词没有在训练数据中出现过这封邮件第一次出现了NIPS。那我们算概率的时候如下:由于NIPS在以前的不管是垃圾邮件还是正常邮件都没出现过那么结果只能是了。显然最终的条件概率也是。原因就是我们的特征概率条件独立使用的是相乘的方式来得到结果。为了解决这个问题我们打算给未出现特征值赋予一个ldquo小rdquo的值而不是。具体平滑方法如下:假设离散型随机变量z有{,,hellip,k}个值我们用Phi𝑖=p(z=i)来表示每个值的概率。假设有m个训练样本中z的观察值是其中每一个观察值对应k个值中的一个。那么根据原来的估计方法可以得到说白了就是z=j出现的比例。拉普拉斯平滑法将每个k值出现次数事先都加通俗讲就是假设他们都出现过一次。那么修改后的表达式为:每个z=j的分子都加分母加k。可见。这个有点像NLP里面的加一平滑法当然还有n多平滑法了这里不再详述。回到邮件分类的问题修改后的公式为:文本分类的事件模型回想一下我们刚刚使用的用于文本分类的朴素贝叶斯模型这个模型称作多值伯努利事件模型(multivariateBernoullieventmodel)。在这个模型中我们首先随机选定了邮件的类型(垃圾或者普通邮件也就是p(y))然后一个人翻阅词典从第一个词到最后一个词随机决定一个词是否要在邮件中出现出现标示为否则标示为。然后将出现的词组成一封邮件。决定一个词是否出现依照概率p(xi|y)。那么这封邮件的概率可以标示为。让我们换一个思路这次我们不先从词典入手而是选择从邮件入手。让i表示邮件中的第i个词xi表示这个词在字典中的位置那么xi取值范围为{,,hellip|V|}|V|是字典中词的数目。这样一封邮件可以表示成n可以变化因为每封邮件的词的个数不同。然后我们对于每个xi随机从|V|个值中取一个这样就形成了一封邮件。这相当于重复投掷|V|面的骰子将观察值记录下来就形成了一封邮件。当然每个面的概率服从p(xi|y)而且每次试验条件独立。这样我们得到的邮件概率是。居然跟上面的一样那么不同点在哪呢?注意第一个的n是字典中的全部的词下面这个n是邮件中的词个数。上面xi表示一个词是否出现只有和两个值两者概率和为。下面的xi表示|V|中的一个值|V|个p(xi|y)相加和为。是多值二项分布模型。上面的x向量都是值下面的x的向量都是字典中的位置。形式化表示为:m个训练样本表示为:表示第i个样本中共有ni个词每个词在字典中的编号为。那么我们仍然按照朴素贝叶斯的方法求得最大似然估计概率为解得与以前的式子相比分母多了个ni分子由变成了k。举个例子:XXXY假如邮件中只有abc这三词他们在词典的位置分别是,,前两封邮件都只有个词后两封有个词。Y=是垃圾邮件。那么Phi|𝑦===Phi|𝑦==Phi|𝑦==Phi|y===Phi|y==Phi|y==Phi𝑦==Phi𝑦==假如新来一封邮件为bc那么特征表示为{,}。那么P(y=|x)=𝑝(𝑥,𝑦=)𝑝(𝑥)=𝑝(𝑥=*,|𝑦=)𝑝(𝑦=)𝑝(𝑥=*,)=Phi|𝑦=Phi|𝑦=Phi𝑦=Phi|𝑦=Phi|𝑦=Phi𝑦=Phi|𝑦=Phi|𝑦=Phi𝑦==lowastlowastlowastlowastlowastlowast=那么该邮件是垃圾邮件概率是。注意这个公式与朴素贝叶斯的不同在于这里针对整体样本求的𝛷𝑘|𝑦=而朴素贝叶斯里面针对每个特征求的𝛷xj=|𝑦=而且这里的特征值维度是参差不齐的。这里如果假如拉普拉斯平滑得到公式为:表示每个k值至少发生过一次。另外朴素贝叶斯虽然有时候不是最好的分类方法但它简单有效而且速度快。支持向量机(上)JerryLeadcsxulijiegmailcom年月日星期六简介支持向量机基本上是最好的有监督学习算法了。最开始接触SVM是去年暑假的时候老师要求交《统计学习理论》的报告那时去网上下了一份入门教程里面讲的很通俗当时只是大致了解了一些相关概念。这次斯坦福提供的学习材料让我重新学习了一些SVM知识。我看很多正统的讲法都是从VC维理论和结构风险最小原理出发然后引出SVM什么的还有些资料上来就讲分类超平面什么的。这份材料从前几节讲的logistic回归出发引出了SVM既揭示了模型间的联系也让人觉得过渡更自然。重新审视logistic回归Logistic回归目的是从特征学习出一个分类模型而这个模型是将特性的线性组合作为自变量由于自变量的取值范围是负无穷到正无穷。因此使用logistic函数(或称作sigmoid函数)将自变量映射到(,)上映射后的值被认为是属于y=的概率。形式化表示就是假设函数其中x是n维特征向量函数g就是logistic函数。的图像是可以看到将无穷映射到了(,)。而假设函数就是特征属于y=的概率。当我们要判别一个新来的特征属于哪个类时只需求ℎ𝜃(x)若大于就是y=的类反之属于y=类。再审视一下ℎ𝜃(x)发现ℎ𝜃(x)只和𝜃𝑇𝑥有关𝜃𝑇𝑥那么ℎ𝜃(x)g(z)只不过是用来映射真实的类别决定权还在𝜃𝑇𝑥。还有当𝜃𝑇𝑥≫时ℎ𝜃(x)=反之ℎ𝜃(x)=。如果我们只从𝜃𝑇𝑥出发希望模型达到的目标无非就是让训练数据中y=的特征𝜃𝑇𝑥≫而是y=的特征𝜃𝑇𝑥≪。Logistic回归就是要学习得到theta使得正例的特征远大于负例的特征远小于强调在全部训练实例上达到这个目标。图形化表示如下:中间那条线是𝜃𝑇𝑥=logistic回顾强调所有点尽可能地远离中间那条线。学习出的结果也就中间那条线。考虑上面个点A、B和C。从图中我们可以确定A是times类别的然而C我们是不太确定的B还算能够确定。这样我们可以得出结论我们更应该关心靠近中间分割线的点让他们尽可能地远离中间线而不是在所有点上达到最优。因为那样的话要使得一部分点靠近中间线来换取另外一部分点更加远离中间线。我想这就是支持向量机的思路和logistic回归的不同点一个考虑局部(不关心已经确定远离的点)一个考虑全局(已经远离的点可能通过调整中间线使其能够更加远离)。这是我的个人直观理解。形式化表示我们这次使用的结果标签是y=,y=替换在logistic回归中使用的y=和y=。同时将theta替换成w和b。以前的𝜃𝑇𝑥=thetatheta𝑥theta𝑥⋯theta𝑛𝑥𝑛其中认为x=。现在我们替换theta为b后面替换theta𝑥theta𝑥⋯theta𝑛𝑥𝑛为w𝑥w𝑥⋯w𝑛𝑥𝑛(即𝑤𝑇𝑥)。这样我们让𝜃𝑇𝑥=𝑤𝑇𝑥b进一步ℎ𝜃(x)=𝑔(𝜃𝑇𝑥)=g(𝑤𝑇𝑥b)。也就是说除了y由y=变为y=只是标记不同外与logistic回归的形式化表示没区别。再明确下假设函数ℎ𝑤,𝑏(x)=𝑔(𝑤𝑇𝑥b)上一节提到过我们只需考虑𝜃𝑇𝑥的正负问题而不用关心g(z)因此我们这里将g(z)做一个简化将其简单映射到y=和y=上。映射关系如下:g(z)={,zgeminus,z函数间隔(functionalmargin)和几何间隔(geometricmargin)给定一个训练样本(𝑥(𝑖),𝑦(𝑖))x是特征y是结果标签。i表示第i个样本。我们定义函数间隔如下:̂(i)=𝑦(𝑖)(𝑤𝑇𝑥(𝑖)𝑏)可想而知当𝑦(𝑖)=时在我们的g(z)定义中𝑤𝑇𝑥(𝑖)𝑏gê(i)的值实际上就是|𝑤𝑇𝑥(𝑖)𝑏|。反之亦然。为了使函数间隔最大(更大的信心确定该例是正例还是反例)当𝑦(𝑖)=时𝑤𝑇𝑥(𝑖)𝑏应该是个大正数反之是个大负数。因此函数间隔代表了我们认为特征是正例还是反例的确信度。继续考虑w和b如果同时加大w和b比如在(𝑤𝑇𝑥(𝑖)𝑏)前面乘个系数比如那么所有点的函数间隔都会增大二倍这个对求解问题来说不应该有影响因为我们要求解的是𝑤𝑇𝑥𝑏=同时扩大w和b对结果是无影响的。这样我们为了限制w和b可能需要加入归一化条件毕竟求解的目标是确定唯一一个w和b而不是多组线性相关的向量。这个归一化一会再考虑。刚刚我们定义的函数间隔是针对某一个样本的现在我们定义全局样本上的函数间隔说白了就是在训练样本上分类正例和负例确信度最小那个函数间隔。接下来定义几何间隔先看图假设我们有了B点所在的𝑤𝑇𝑥𝑏=分割面。任何其他一点比如A到该面的距离以𝛾(𝑖)表示假设B就是A在分割面上的投影。我们知道向量BA的方向是w(分割面的梯度)单位向量是𝑤||w||。A点是(𝑥(𝑖),𝑦(𝑖))所以B点是x=𝑥(𝑖)minus𝛾(𝑖)𝑤||w||(利用初中的几何知识)带入𝑤𝑇𝑥𝑏=得w𝑇(𝑥(𝑖)minus𝛾(𝑖)𝑤||w||)𝑏=进一步得到𝛾(𝑖)实际上就是点到平面距离。再换种更加优雅的写法:当||w||=时不就是函数间隔吗?是的前面提到的函数间隔归一化结果就是几何间隔。他们为什么会一样呢?因为函数间隔是我们定义的在定义的时候就有几何间隔的色彩。同样同时扩大w和bw扩大几倍||w||就扩大几倍结果无影响。同样定义全局的几何间隔最优间隔分类器(optimalmarginclassifier)回想前面我们提到我们的目标是寻找一个超平面使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。形象的说我们将上面的图看作是一张纸我们要找一条折线按照这条折线折叠后离折线最近的点的间距比其他折线都要大。形式化表示为:这里用||w||=规约w使得𝑤𝑇𝑥𝑏是几何间隔。到此我们已经将模型定义出来了。如果求得了w和b那么来一个特征x我们就能够分类了称为最优间隔分类器。接下的问题就是如何求解w和b的问题了。由于||w||=不是凸函数我们想先处理转化一下考虑几何间隔和函数间隔的关系gamma=̂||w||我们改写一下上面的式子:这时候其实我们求的最大值仍然是几何间隔只不过此时的w不受||w||=的约束了。然而这个时候目标函数仍然不是凸函数没法直接代入优化软件里计算。我们还要改写。前面说到同时扩大w和b对结果没有影响但我们最后要求的仍然是w和b的确定值不是他们的一组倍数值因此我们需要对̂做一些限制以保证我们解是唯一的。这里为了简便我们取̂=。这样的意义是将全局的函数间隔定义为也即是将离超平面最近的点的距离定义为||w||。由于求||w||的最大值相当于求||𝑤||的最小值因此改写后结果为:这下好了只有线性约束了而且是个典型的二次规划问题(目标函数是自变量的二次函数)。代入优化软件可解。到这里发现这个讲义虽然没有像其他讲义一样先画好图画好分类超平面在图上标示出间隔那么直观但每一步推导有理有据依靠思路的流畅性来推导出目标函数和约束。接下来介绍的是手工求解的方法了一种更优的求解方法。拉格朗日对偶(Lagrangeduality)先抛开上面的二次规划问题先来看看存在等式约束的极值问题求法比如下面的最优化问题:目标函数是f(w)下面是等式约束。通常解法是引入拉格朗日算子这里使用beta来表示算子得到拉格朗日公式为L是等式约束的个数。然后分别对w和beta求偏导使得偏导数等于然后解出w和beta𝑖。至于为什么引入拉格朗日算子可以求出极值原因是f(w)的dw变化方向受其他不等式的约束dw的变化方向与f(w)的梯度垂直时才能获得极值而且在极值处f(w)的梯度与其他等式梯度的线性组合平行因此他们之间存在线性关系。(参考《最优化与KKT条件》)然后我们探讨有不等式约束的极值问题求法问题如下:我们定义一般化的拉格朗日公式这里的𝛼𝑖和𝛽𝑖都是拉格朗日算子。如果按这个公式求解会出现问题因为我们求解的是最小值而这里的𝑔i(𝑤)le我们可以将𝛼𝑖调整成很大的正值来使最后的函数结果是负无穷。因此我们需要排除这种情况我们定义下面的函数:这里的P代表primal。假设𝑔i(𝑤)或者ℎi(𝑤)ne那么我们总是可以调整𝛼𝑖和𝛽𝑖来使得𝜃𝒫(w)有最大值为正无穷。而只有g和h满足约束时𝜃𝒫(w)为f(w)。这个函数的精妙之处在于𝛼𝑖ge而且求极大值。因此我们可以写作这样我们原来要求的minf(w)可以转换成求min𝑤𝜃𝒫(w)了。我们使用plowast来表示min𝑤𝜃𝒫(w)。如果直接求解首先面对的是两个参数而𝛼𝑖也是不等式约束然后再在w上求最小值。这个过程不容易做那么怎么办呢?我们先考虑另外一个问题D的意思是对偶将问题转化为先求拉格朗日关于w的最小值将alpha和beta看作是固定值。之后在求最大值的话:这个问题是原问题的对偶问题相对于原问题只是更换了min和max的顺序而一般更换顺序的结果是MaxMin(X)=MinMax(X)。然而在这里两者相等。用𝑑lowast来表示对偶问题如下:下面解释在什么条件下两者会等价。假设f和g都是凸函数h是仿射的(affine)。并且存在w使得对于所有的i𝑔𝑖(𝑤)。在这种假设下一定存在wlowast,𝛼lowast,𝛽lowast使得wlowast是原问题的解𝛼lowast,𝛽lowast是对偶问题的解。还有另外wlowast,𝛼lowast,𝛽lowast满足库恩塔克条件(KarushKuhnTucker,KKTcondition)该条件如下:所以如果wlowast,𝛼lowast,𝛽lowast满足了库恩塔克条件那么他们就是原问题和对偶问题的解。让我们再次审视公式()这个条件称作是KKTdualcomplementarity条件。这个条件隐含了如果𝛼lowast那么𝑔𝑖(𝑤lowast)=。也就是说𝑔𝑖(𝑤lowast)=时w处于可行域的边界上这时才是起作用的约束。而其他位于可行域内部(𝑔𝑖(𝑤lowast)的)点都是不起作用的约束其𝛼lowast=。这个KKT双重补足条件会用来解释支持向量和SMO的收敛测试。这部分内容思路比较凌乱还需要先研究下《非线性规划》中的约束极值问题再回头看看。KKT的总体思想是认为极值会在可行域边界上取得也就是不等式为或等式约束里取得而最优下降方向一般是这些等式的线性组合其中每个元素要么是不等式为的约束要么是等式约束。对于在可行域边界内的点对最优解不起作用因此前面的系数为。最优间隔分类器(optimalmarginclassifier)重新回到SVM的优化问题:我们将约束条件改写为:从KKT条件得知只有函数间隔是(离超平面最近的点)的线性约束式前面的系数𝛼𝑖也就是说这些约束式𝑔𝑖(w)=对于其他的不在线上的点(𝑔𝑖(w))极值不会在他们所在的范围内取得因此前面的系数𝛼𝑖=注意每一个约束式实际就是一个训练样本。看下面的图:实线是最大间隔超平面假设times号的是正例圆圈的是负例。在虚线上的点就是函数间隔是的点那么他们前面的系数𝛼𝑖其他点都是𝛼𝑖=。这三个点称作支持向量。构造拉格朗日函数如下:注意到这里只有𝛼𝑖没有𝛽𝑖是因为原问题中没有等式约束只有不等式约束。下面我们按照对偶问题的求解步骤来一步步进行首先求解的最小值对于固定的𝛼𝑖的最小值只与w和b有关。对w和b分别求偏导数。并得到将上式带回到拉格朗日函数中得到此时得到的是该函数的最小值(目标函数是凸函数)化简过程如下:ℒ(w,b,alpha)=‖𝑤‖minussum𝛼𝑖𝑦(𝑖)(𝑤𝑇𝑥(𝑖)𝑏)minus𝑚𝑖==w𝑇wminussum𝛼𝑖𝑦(𝑖)𝑤𝑇𝑥(𝑖)𝑚𝑖=minussum𝛼𝑖𝑦(𝑖)𝑏𝑚𝑖=sum𝛼𝑖𝑚𝑖==w𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minussum𝛼𝑖𝑦(𝑖)𝑤𝑇𝑥(𝑖)𝑚𝑖=minussum𝛼𝑖𝑦(𝑖)𝑏𝑚𝑖=sum𝛼𝑖𝑚𝑖==w𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minus𝑤𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minussum𝛼𝑖𝑦(𝑖)𝑏𝑚𝑖=sum𝛼𝑖𝑚𝑖==minusw𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minussum𝛼𝑖𝑦(𝑖)𝑏𝑚𝑖=sum𝛼𝑖𝑚𝑖==minusw𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minus𝑏sum𝛼𝑖𝑦(𝑖)𝑚𝑖=sum𝛼𝑖𝑚𝑖==minus(sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=)𝑇sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minus𝑏sum𝛼𝑖𝑦(𝑖)𝑚𝑖=sum𝛼𝑖𝑚𝑖==minussum𝛼𝑖𝑦(𝑖)(𝑥(𝑖))𝑇𝑚𝑖=sum𝛼𝑖𝑦(𝑖)𝑥(𝑖)𝑚𝑖=minus𝑏sum𝛼𝑖𝑦(𝑖)𝑚𝑖=sum𝛼𝑖𝑚𝑖==minussum𝛼𝑖𝑦(𝑖)(𝑥(𝑖))𝑇𝑚𝑖=,𝑗=𝛼𝑗𝑦(𝑗)𝑥(𝑗)minus𝑏sum𝛼𝑖𝑦(𝑖)𝑚𝑖=sum𝛼𝑖𝑚𝑖==sum𝛼𝑖𝑚𝑖=minussum𝑦(𝑖)𝑦(𝑖)𝛼𝑖𝛼𝑗(𝑥(𝑖))𝑇𝑚𝑖=,𝑗=𝑥(𝑗)minus𝑏sum𝛼𝑖𝑦(𝑖)𝑚𝑖=ldquo倒数第步rdquo推导到ldquo倒数第步rdquo使用了线性代数的转置运算由于𝛼𝑖和𝑦(𝑖)都是实数因此转置后与自身一样。ldquo倒数第步rdquo推导到ldquo倒数第步rdquo使用了(abchellip)(abchellip)=aaabacbabbbchellip的乘法运算法则。最后一步是上一步的顺序调整。最后得到:由于最后一项是因此简化为这里我们将向量内积表示为此时的拉格朗日函数只包含了变量𝛼𝑖。然而我们求出了𝛼𝑖才能得到w和b。接着是极大化的过程前面提到过对偶问题和原问题满足的几个条件首先由于目标函数和线性约束都是凸函数而且这里不存在等式约束h。存在w使得对于所有的i𝑔𝑖(𝑤)。因此一定存在wlowast,𝛼lowast使得wlowast是原问题的解𝛼lowast是对偶问题的解。在这里求𝛼𝑖就是求𝛼lowast了。如果求出了𝛼𝑖根据即可求出w(也是wlowast原问题的解)。然后即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。关于上面的对偶问题如何求解将留给下一篇中的SMO算法来阐明。这里考虑另外一个问题由于前面求解中得到w=sum𝛼𝑖𝑦(𝑖)𝑚𝑖=𝑥(𝑖)我们通篇考虑问题的出发点是𝑤𝑇𝑥𝑏根据求解得到的𝛼𝑖我们代入前式得到也就是说以前新来的要分类的样本首先根据w和b做一次线性运算然后看求的结果是大于还是小于,来判断正例还是负例。现在有了𝛼𝑖我们不需要求出w只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说与前面所有的样本都做运算是不是太耗时了?其实不然我们从KKT条件中得到只有支持向量的𝛼𝑖其他情况𝛼𝑖=。因此我们只需求新来的样本和支持向量的内积然后运算即可。这种写法为下面要提到的核函数(kernel)做了很好的铺垫。这是上篇先写这么多了。支持向量机SVM(下)JerryLeadcsxulijiegmailcom年月日星期四核函数(Kernels)考虑我们最初在ldquo线性回归rdquo中提出的问题特征是房子的面积x这里的x是实数结果y是房子的价格。假设我们从样本点的分布中看到x和y符合次曲线那么我们希望使用x的三次多项式来逼近这些样本点。那么首先需要将特征x扩展到三维(x,𝑥,𝑥)然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射(featuremapping)。映射函数称作ϕ在这个例子中ϕ(x)=𝑥𝑥𝑥我们希望将得到的特征映射后的特征应用于SVM分类而不是最初的特征。这样我们需要将前面𝑥公式中的内积从𝑥(),𝑥映射到𝜙(𝑥(𝑖)),𝜙(𝑥)。至于为什么需要映射后的特征而不是最初的特征来参与计算上面提到的(为了更好地拟合)是其中一个原因另外的一个重要原因是样例可能存在线性不可分的情况而将特征映射到高维空间后往往就可分了。(在《数据挖掘导论》PangNingTan等人著的《支持向量机》那一章有个很好的例子说明)将核函数形式化定义如果原始特征内积是x,𝑧映射后为𝜙(x),𝜙(𝑧)那么定义核函数(Kernel)为𝐾(𝑥,𝑧)=𝜙(𝑥)𝜙(𝑧)到这里我们可以得出结论如果要实现该节开头的效果只需先计算𝜙(𝑥)然后计算𝜙(𝑥)𝜙(𝑧)即可然而这种计算方式是非常低效的。比如最初的特征是n维的我们将其映射到n维然后再计算这样需要O(n)的时间。那么我们能不能想办法减少计算时间呢?先看一个例子假设x和z都是n维的𝐾(𝑥,𝑧)=(𝑥𝑧)展开后得𝐾(𝑥,𝑧)=(𝑥𝑧)=(sum𝑥𝑖𝑧𝑖𝑛𝑖=)(sum𝑥𝑗𝑧𝑗𝑛𝑗=)=sumsum𝑥𝑖𝑛𝑗=𝑥𝑗𝑧𝑖𝑧𝑗𝑛𝑖==sumsum(𝑥𝑖𝑛𝑗=𝑥𝑗)(𝑧𝑖𝑧𝑗)𝑛𝑖==𝜙(𝑥)𝜙(𝑧)这个时候发现我们可以只计算原始特征x和z内积的平方(时间复杂度是O(n))就等价与计算映射后特征的内积。也就是说我们不需要花O(n)时间了。现在看一下映射函数(n=时)根据上面的公式得到也就是说核函数𝐾(𝑥,𝑧)=(𝑥𝑧)只能在选择这样的ϕ作为映射函数时才能够等价于映射后特征的内积。再看一个核函数对应的映射函数(n=时)是更一般地核函数𝐾(𝑥,𝑧)=(𝑥𝑧𝑐)𝑑对应的映射后特征维度为(nd𝑑)。(这个我一直没有理解)。由于计算的是内积我们可以想到IR中的余弦相似度如果x和z向量夹角越小那么核函数值越大反之越小。因此核函数值是𝜙(𝑥)和𝜙(𝑧)的相似度。再看另外一个核函数这时如果x和z很相近(||xminusz||asymp)那么核函数值为如果x和z相差很大(||xminusz||≫)那么核函数值约等于。由于这个函数类似于高斯分布因此称为高斯核函数也叫做径向基函数(RadialBasisFunction简称RBF)。它能够把原始特征映射到无穷维。既然高斯核函数能够比较x和z的相似度并映射到到回想logistic回归sigmoid函数可以因此还有sigmoid核函数等等。下面有张图说明在低维线性不可分时映射到高维后就可分了使用高斯核函数。来自EricXing的slides注意使用核函数后怎么分类新来的样本呢?线性的时候我们使用SVM学习出w和b新来样本x的话我们使用𝑥来判断如果值大于等于那么是正类小于等于是负类。在两者之间认为无法确定。如果使用了核函数后𝑥就变成了𝜙(x)是否先要找到𝜙(x)然后再预测?答案肯定不是了找𝜙(x)很麻烦回想我们之前说过的只需将𝑥(𝑖),𝑥替换成𝐾(𝑥(𝑖),𝑥)然后值的判断同上。核函数有效性判定问题:给定一个函数K我们能否使用K来替代计算𝜙(𝑥)𝜙(𝑧)也就说是否能够找出一个𝜙使得对于所有的x和z都有𝐾(𝑥,𝑧)=𝜙(𝑥)𝜙(𝑧)?比如给出了𝐾(𝑥,𝑧)=(𝑥𝑧)是否能够认为K是一个有效的核函数。下面来解决这个问题给定m个训练样本*𝑥(),𝑥(),hellip,𝑥(𝑚)每一个𝑥(𝑖)对应一个特征向量。那么我们可以将任意两个𝑥(𝑖)和𝑥(𝑗)带入K中计算得到𝐾𝑖𝑗=𝐾(𝑥(𝑖),𝑥(𝑗))。I可以从到mj可以从到m这样可以计算出m*m的核函数矩阵(KernelMatrix)。为了方便我们将核函数矩阵和𝐾(𝑥,𝑧)都使用K来表示。如果假设K是有效的核函数那么根据核函数定义𝐾𝑖𝑗=𝐾(𝑥(𝑖),𝑥(𝑗))=𝜙(𝑥(𝑖))𝜙(𝑥(𝑗))=𝜙(𝑥(𝑗))𝜙(𝑥(𝑖))=𝐾(𝑥(𝑗),𝑥(𝑖))=𝐾𝑗𝑖可见矩阵K应该是个对称阵。让我们得出一个更强的结论首先使用符号𝜙𝑘(𝑥)来表示映射函数𝜙(𝑥)的第k维属性值。那么对于任意向量z得最后一步和前面计算𝐾(𝑥,𝑧)=(𝑥𝑧)时类似。从这个公式我们可以看出如果K是个有效的核函数(即𝐾(𝑥,𝑧)和𝜙(𝑥)𝜙(𝑧)等价)那么在训练集上得到的核函数矩阵K应该是半正定的(Kge)这样我们得到一个核函数的必要条件:K是有效的核函数==核函数矩阵K是对称半正定的。可幸的是这个条件也是充分的由Mercer定理来表达。Mercer定理:如果函数K是ℝntimesℝnrarrℝ上的映射(也就是从两个n维向量映射到实数域)。那么如果K是一个有效核函数(也称为Mercer核函数)那么当且仅当对于训练样例*𝑥(),𝑥(),hellip,𝑥(𝑚)其相应的核函数矩阵是对称半正定的。Mercer定理表明为了证明K是有效的核函数那么我们不用去寻找𝜙而只需要在训练集上求出各个𝐾𝑖𝑗然后判断矩阵K是否是半正定(使用左上角主子式大于等于零等方法)即可。许多其他的教科书在Mercer定理证明过程中使用了L范数和再生希尔伯特空间等概念但在特征是n维的情况下这里给出的证明是等价的。核函数不仅仅用在SVM上但凡在一个模型后算法中出现了x,z我们都可以常使用𝐾(𝑥,𝑧)去替换这可能能够很好地改善我们的算法。规则化和不可

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/137

斯坦福大学机器学习课程个人笔记完整版

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利