svm分类识别算法运行流程

A. svm算法是什么

SVM(Support Vector Machine)中文名为支持向量机，是常见的一种判别方法。

支持向量机（Support Vector Machine, SVM）是一类按监督学习（supervised learning）方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面（maximum-margin hyperplane）。

数值求解特点：

SVM的求解可以使用二次凸优化问题的数值方法，例如内点法和序列最小优化算法，在拥有充足学习样本时也可使用随机梯度下降。

在二次凸优化问题中，SMO的每步迭代都严格地优化了SVM的对偶问题，且迭代会在有限步后收敛于全局极大值。SMO算法的迭代速度与所选取乘子对KKT条件的偏离程度有关，因此SMO通常采用启发式方法选取拉格朗日乘子。

在每次迭代时，SGD首先判定约束条件，若该样本不满足约束条件，则SGD按学习速率最小化结构风险；若该样本满足约束条件，为SVM的支持向量，则SGD根据正则化系数平衡经验风险和结构风险，即SGD的迭代保持了SVM的稀疏性。

B. svm算法是什么

SVM算法中文翻译为支持向量机，它的英文全称是Support Vector Machine。

之所以叫作支持向量机，是因为该算法最终训练出来的模型，由一些支持向量决定。所谓的支持向量，也就是能够决定最终模型的向量。SVM算法最初是用来解决二分类问题的，而在这个基础上进行扩展，也能够处理多分类问题以及回归问题。

SVM算法的历史

早在1963 年，着名的前苏联统计学家弗拉基米尔·瓦普尼克在读博士期间，就和他的同事阿列克谢·切尔沃宁基斯共同提出了支持向量机的概念。

但由于当时的国际环境影响，他们用俄文发表的论文，并没有受到国际学术界的关注。直到 20 世纪 90 年代，瓦普尼克随着移民潮来到美国，而后又发表了SVM 理论。此后，SVM 算法才受到应有的重视。如今，SVM 算法被称为最好的监督学习算法之一。

C. python svm 怎么训练模型

支持向量机SVM(Support Vector Machine)是有监督的分类预测模型，本篇文章使用机器学习库scikit-learn中的手写数字数据集介绍使用Python对SVM模型进行训练并对手写数字进行识别的过程。

准备工作

手写数字识别的原理是将数字的图片分割为8X8的灰度值矩阵，将这64个灰度值作为每个数字的训练集对模型进行训练。手写数字所对应的真实数字作为分类结果。在机器学习sklearn库中已经包含了不同数字的8X8灰度值矩阵，因此我们首先导入sklearn库自带的datasets数据集。然后是交叉验证库，SVM分类算法库，绘制图表库等。

读取并查看数字矩阵

从sklearn库自带的datasets数据集中读取数字的8X8矩阵信息并赋值给digits。

查看其中的数字9可以发现，手写的数字9以64个灰度值保存。从下面的8×8矩阵中很难看出这是数字9。

以灰度值的方式输出手写数字9的图像，可以看出个大概轮廓。这就是经过切割并以灰度保存的手写数字9。它所对应的64个灰度值就是模型的训练集，而真实的数字9是目标分类。我们的模型所要做的就是在已知64个灰度值与每个数字对应关系的情况下，通过对模型进行训练来对新的手写数字对应的真实数字进行分类。

从混淆矩阵中可以看到，大部分的数字SVM的分类和预测都是正确的，但也有个别的数字分类错误，例如真实的数字2，SVM模型有一次错误的分类为1，还有一次错误分类为7。

D. 目标检测算法图解：一文看懂RCNN系列算法

姓名：王咫毅

学号：19021211150

【嵌牛导读】CNN如此风靡，其衍生算法也是层出不穷，各种衍生算法也可以应用于各种应用场景，各类场合。本文则是了解每个衍生算法的各个使用场景、原理及方法。

【嵌牛鼻子】RCNN 目标检测

【嵌牛提问】RCNN系列算法有何区别和联系？

【嵌牛正文】

在生活中，经常会遇到这样的一种情况，上班要出门的时候，突然找不到一件东西了，比如钥匙、手机或者手表等。这个时候一般在房间翻一遍各个角落来寻找不见的物品，最后突然一拍大脑，想到在某一个地方，在整个过程中有时候是很着急的，并且越着急越找不到，真是令人沮丧。但是，如果一个简单的计算机算法可以在几毫秒内就找到你要找的物品，你的感受如何？是不是很惊奇！这就是对象检测算法（object detection）的力量。虽然上述举的生活例子只是一个很简单的例子，但对象检测的应用范围很广，跨越多个不同的行业，从全天候监控到智能城市的实时车辆检qian测等。简而言之，物体检测是强大的深度学习算法中的一个分支。

在本文中，我们将深入探讨可以用于对象检测的各种算法。首先从属于RCNN系列算法开始，即RCNN、 Fast RCNN和 Faster RCNN。在之后的文章中，将介绍更多高级算法，如YOLO、SSD等。

1.解决对象检测任务的简单方法（使用深度学习）

下图说明了对象检测算法是如何工作。图像中的每个对象，从人到风筝都以一定的精度进行了定位和识别。

下面从最简单的深度学习方法开始，一种广泛用于检测图像中的方法——卷积神经网络（CNN）。如果读者对CNN算法有点生疏，建议 阅读此文 。

这里仅简要总结一下CNN的内部运作方式：

首先将图像作为输入传递到网络，然后通过各种卷积和池化层处理，最后以对象类别的形式获得输出。

对于每个输入图像，会得到一个相应的类别作为输出。因此可以使用这种技术来检测图像中的各种对象。

1.首先，将图像作为输入；

2.然后，将图像分成不同的区域；

3.然后，将每个区域视为单独的图像；

4.将所有这些区域传递给CNN并将它们分类为各种类别；

5.一旦将每个区域划分为相应的类后，就可以组合所有这些区域来获取具有检测到的对象的原始图像：

使用这种方法会面临的问题在于，图像中的对象可以具有不同的宽高比和空间位置。例如，在某些情况下，对象可能覆盖了大部分图像，而在其他情况下，对象可能只覆盖图像的一小部分，并且对象的形状也可能不同。

基于此，需要划分大量的区域，这会花费大量的计算时间。因此，为了解决这个问题并减少区域数量，可以使用基于区域的CNN，它使用提议方法选择区域。

2.基于区域的卷积神经网络

2.1 RCNN的思想

RCNN算法不是在大量区域上工作，而是在图像中提出了一堆方框，并检查这些方框中是否包含任何对象。RCNN 使用选择性搜索从图像中提取这些框。

下面介绍选择性搜索以及它如何识别不同的区域。基本上四个区域形成一个对象：不同的比例、颜色、纹理和形状。选择性搜索在图像中识别这些模式，并基于此提出各种区域。以下是选择性搜索如何工作的简要概述：

首先， 将图像作为输入：

然后，它生成初始子分段，以便获得多个区域：

之后，该技术组合相似区域以形成更大的区域（基于颜色相似性、纹理相似性、尺寸相似性和形状兼容性）：

最后，这些区域产生最终的对象位置（感兴趣的区域）；

下面是RCNN检测对象所遵循的步骤的简要总结：

1.首先采用预先训练的卷积神经网络；

2.重新训练该模型模型——根据需要检测的类别数量来训练网络的最后一层（迁移学习）；

3.第三步是获取每个图像的感兴趣区域。然后，对这些区域调整尺寸，以便其可以匹配CNN输入大小；

4.获取区域后，使用SVM算法对对象和背景进行分类。对于每个类，都训练一个二分类SVM；

最后，训练线性回归模型，为图像中每个识别出的对象生成更严格的边界框；

[对上述步骤进行图解分析]（ http://www.robots.ox.ac.uk/~tvg/publications/talks/Fast-rcnn-slides.pdf ）：

首先，将图像作为输入：

然后，使用一些提议方法获得感兴趣区域（ROI）（例如，选择性搜索）：

之后，对所有这些区域调整尺寸，并将每个区域传递给卷积神经网络：

然后，CNN为每个区域提取特征，SVM用于将这些区域划分为不同的类别：

最后，边界框回归（Bbox reg）用于预测每个已识别区域的边界框：

以上就是RCNN检测物体的全部流程。

2.2 RCNN的问题

从上节内容可以了解到RCNN是如何进行对象检测的，但这种技术有其自身的局限性。以下原因使得训练RCNN模型既昂贵又缓慢：

基于选择性搜索算法为每个图像提取2,000个候选区域；

使用CNN为每个图像区域提取特征；

RCNN整个物体检测过程用到三种模型：

CNN模型用于特征提取；

线性svm分类器用于识别对象的的类别；

回归模型用于收紧边界框；

这些过程相结合使得RCNN非常慢，对每个新图像进行预测需要大约40-50秒，这实际上使得模型在面对巨大的数据集时变得复杂且几乎不可能应用。

好消息是存在另一种物体检测技术，它解决了RCNN中大部分问题。

3.了解Fast RCNN

3.1Fast RCNN的思想

RCNN的提出者Ross Girshick提出了这样的想法，即每个图像只运行一次CNN，然后找到一种在2,000个区域内共享该计算的方法。在Fast RCNN中，将输入图像馈送到CNN，CNN生成卷积特征映射。使用这些特征图提取候选区域。然后，使用RoI池化层将所有建议的区域重新整形为固定大小，以便将其馈送到全连接网络中。

下面将其分解为简化概念的步骤：

1.首先将图像作为输入；

2.将图像传递给卷积神经网络，生成感兴趣的区域；

3.在所有的感兴趣的区域上应用RoI池化层，并调整区域的尺寸。然后，每个区域被传递到全连接层的网络中；

4.softmax层用于全连接网以输出类别。与softmax层一起，也并行使用线性回归层，以输出预测类的边界框坐标。

因此，Fast RCNN算法中没有使用三个不同的模型，而使用单个模型从区域中提取特征，将它们分成不同的类，并同时返回所标识类的边界框。

对上述过程进行可视化讲解：

将图像作为输入：

将图像传递给卷积神经网络t，后者相应地返回感兴趣的区域：

然后，在提取的感兴趣区域上应用RoI池层，以确保所有区域具有相同的大小：

最后，这些区域被传递到一个全连接网络，对其进行分类，并同时使用softmax和线性回归层返回边界框：

上述过程说明了Fast RCNN是如何解决RCNN的两个主要问题，即将每个图像中的1个而不是2,000个区域传递给卷积神经网络，并使用一个模型来实现提取特征、分类和生成边界框。

3.2Fast RCNN的问题

Fast RCNN也存在一定的问题，它仍然使用选择性搜索作为查找感兴趣区域的提议方法，这是一个缓慢且耗时的过程，每个图像检测对象大约需要2秒钟。

因此，又开发了另一种物体检测算法——Faster RCNN。

4.了解Faster RCNN

4.1. Faster RCNN的思想

Faster RCNN是Fast RCNN的修改版本，二者之间的主要区别在于，Fast RCNN使用选择性搜索来生成感兴趣区域，而Faster RCNN使用“区域提议网络”，即RPN。RPN将图像特征映射作为输入，并生成一组提议对象，每个对象提议都以对象分数作为输出。

以下步骤通常采用Faster RCNN方法：

1.将图像作为输入并将其传递给卷积神经网络，后者返回该图像的特征图；

2.在这些特征图上应用RPN，返回提议对象及其分数；

3.在这些提议对象上应用RoI池层，以将所有提案降低到相同的大小；

4.最后，将提议传递到全连接层，该层在其顶部具有softmax层和线性回归层，以对对象的边界框进行分类和输出；

这里简要解释一下RPN是如何运作的：

首先，Faster RCNN从CNN获取特征图并将它们传递到区域提议网络。RPN在这些特征图上使用滑动窗口，每个窗口生成不同形状和大小的k个方框（ Anchor boxe）：

方框是固定尺寸的边界箱，具有不同的形状和尺寸。对于每个方框，RPN预测两件事：

预测锚是对象的概率；

用于边界框回归器调整锚点以更好地适合物体的形状；

在有了不同形状和大小的边界框后，将其传递到RoI池层。对每个提案并对其进行裁剪，以便每个提案都包含一个对象。这就是RoI池层所做的事情，它为每个方框提取固定大小的特征图：

然后将这些特征图传递到全连接层，该层具有softmax和线性回归层，最终对对象进行分类并预测已识别对象的边界框。

4.2Faster RCNN的问题

上述讨论过的所有对象检测算法都使用区域来识别对象，且网络不会一次查看完整图像，而是按顺序关注图像的某些部分，这样会带来两个复杂性的问题：

该算法需要多次通过单个图像来提取到所有对象；

由于不是端到端的算法，不同的系统一个接一个地工作，整体系统的性能进一步取决于先前系统的表现效果。

链接： https://www.jianshu.com/p/51fc039ae7a4

E. 分类算法 - SVM算法

SVM的全称是Support Vector Machine，即支持向量机，主要用于解决模式识别领域中的数据分类问题，属于有监督学习算法的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述。如图1所示，红色和蓝色的二维数据点显然是可以被一条直线分开的，在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条。图2和3分别给出了A、B两种不同的分类方案，其中黑色实线为分界线，术语称为“决策面”。每个决策面对应了一个线性分类器。虽然在目前的数据上看，这两个分类器的分类结果是一样的，但如果考虑潜在的其他数据，则两者的分类性能是有差别的。

之前在b站看到一个非常好的介绍！！十分推荐， 这是传送门

按照我自己的理解，以二维数据为例，我们喂给模型已经分类好的数据，那么假设有一线条可以将此部分数据正确划分为2大部分，这样可以形成2个等式，即横线两边的数值归类为1或者-1，一般情况下可以求出最大间隔即无数个解，因此需要一个限定条件求出最优的那条线条。限定方式为：无数个解形成一个解的范围，距离边缘相等的那条线条即是最优解。

有时候本来数据的确是可分的，也就是说可以用线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照线性分类支持向量机方法来分类。

以上讨论的都是在线性可分情况进行讨论的，但是实际问题中给出的数据并不是都是线性可分的，比如有些数据可能是曲线的。

那么这种非线性可分的数据是否就不能用SVM算法来求解呢？答案是否定的。事实上，对于低维平面内不可分的数据，放在一个高维空间中去就有可能变得可分。以二维平面的数据为例，我们可以通过找到一个映射将二维平面的点放到三维平面之中。理论上任意的数据样本都能够找到一个合适的映射使得这些在低维空间不能划分的样本到高维空间中之后能够线性可分。

当特征变量非常多的时候，在高维空间中计算内积的运算量是非常庞大的。考虑到我们的目的并不是为找到这样一个映射而是为了计算其在高维空间的内积，因此如果我们能够找到计算高维空间下内积的公式，那么就能够避免这样庞大的计算量，我们的问题也就解决了。实际上这就是我们要找的 核函数 ，即两个向量在隐式映射后的空间中的内积。

（1）对于边界清晰的分类问题效果好；
（2）对高维分类问题效果好；
（3）当维度高于样本数的时候，SVM 较为有效；
（4）因为最终只使用训练集中的支持向量，所以节约内存

（1）当数据量较大时，训练时间会较长；
（2）当数据集的噪音过多时，表现不好；
（3）SVM 不直接提供结果的概率估计，它在计算时直接使用 5 倍交叉验证。

（1）LR 与 SVM 都是分类算法；
（2）LR 与 SVM 都是监督学习算法；
（3）LR 与 SVM 都是判别模型；
（4）关于判别模型与生成模型的详细概念与理解，笔者会在下篇博文给出，这里不详述。
（5）如果不考虑核函数，LR 与 SVM 都是线性分类算法，也就是说他们的分类决策面都是线性的

这里需要说明的是，LR 也是可以用核函数的，因在 LR 算法里，每个样本点都必须参与决策面的计算过程，也就是说，如果在 LR 里也运用核函数的原理，那么每个样本点都必须参与核计算，这带来的计算复杂度是相当高的。所以在具体应用时，LR 很少运用核函数机制。

（1）损失函数不同；
（2）SVM 只考虑支持向量，而 LR 考虑全局（即远离的点对边界线的确定也起作用）；
（3）在解决非线性问题时，SVM 采用核函数的机制，而 LR 通常不采用核函数的方法；
（4）SVM 的损失函数就自带正则（损失函数中的12||w||2项），这就是为什么 SVM 是结构风险最小化算法的原因，而 LR 必须另外在损失函数上添加正则项；
（5）LR是参数模型，SVM是非参数模型，本质不同。
（6）在训练集较小时，SVM 较适用，而 LR 需要较多的样本。

（1）LR 与线性回归都是广义的线性回归；
（2）线性回归模型的优化目标函数是最小二乘，而 LR 则是似然函数；
（3）线性回归在整个实数域范围内进行预测，敏感度一致，而分类范围，需要在[0,1]。逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好。
（4）逻辑回归的模型本质上是一个线性回归模型，逻辑回归都是以线性回归为理论支持的。但线性回归模型无法做到 sigmoid 的非线性形式，sigmoid 可以轻松处理 0/1 分类问题。
（5）线性回归主要做预测，LR 主要做分类（如二分类）；

F. SVM算法原理

一、决策面方程

以二维空间为例，二维空间中任意一条直线方程可以写为

我们将其向量化，可以得到

设用向量w代表矩阵a1和a2，用向量x代表矩阵x1和x2，标量γ代表b，则方程可化表示为

从方程可知，一个n维空间的超平面在二维空间上的表现，可以是一条直线，或者一个曲线（二维空间中只能看到这个n维超平面穿过而无法看到其模样）， 超平面方程即是我们的决策面方程

二、函数间隔和几何间隔

在SVM监督学习中，我们规定标签数据为+1和-1两个值，这么做的目的， 可以计算出任意一个样本点在超平面方程上的表现结果的符号，与标签符号是否一致来判断分类的正确性 ，为此我们可以引入函数间隔的概念

但是当我们成比例的缩放w和γ，函数间隔的值也将成比例的变化，可是超平面的位置并没有发生任何变化，所以函数间隔并不是我们想要的分类间隔，为此，我们需要引入几何间隔的概念

还是以二维空间出发，任意一点到直线的距离可以写成

我们将其拓展到n维空间，直线方程即是我们的超平面方程，则n维空间中任何一点到超平面的距离可以写成

为此，我们引入几何间隔概念，其中||w||表示向量w的二范数

从几何间隔可以看出，就算等比例缩放w和γ，由于除上了||w||使得几何间隔的值不会改变，它只随着超平面位置的变化而变化，因此， 我们要寻找的分类间隔是几何间隔

三、不等式约束条件

SVM算法的目的是找到一个将分类效果达到最合理化的超平面，这个超平面即是分类器 。而评估分类器的好坏的标准就是分类间隔的大小

我们定义分类间隔的距离为d，好的分类器应该让所有样本点到决策面的几何间隔都大于等于d

化简上式，不等式两边同时除以d可得

由于||w||和d都是标量，可定义

则上式可化简为

在不等式两边同时乘以yi，即将两个式子化简为一个式子（这里体现了正是因为标签数据为+1和-1，才方便将约束条件变成一个约束方程）

这个约束方程的意义 即是任何样本点到超平面（分类器）的几何间隔都大于等于分类间隔

四、SVM最优化模型的数学描述

评估分类器的优劣是分类间隔的大小，且对于任意样本点都满足约束方程

由约束方程可知，当样本点落在支持向量边界上有如下关系

则分类间隔d可以表示为支持向量点到超平面的几何间隔

要让任何样本点都在d之外，即求分类间隔d的最大值，则目标函数可以写成

为了方便在后续最优化处理中对目标函数的求导，我们将目标函数做等效变化

由目标函数是二次的，而约束条件是线性的，则 SVM的数学模型即是：不等式约束条件下的二次型函数优化 ，而求解这一类优化问题，接下来我们需要构造 拉格朗乘子函数

五、引入拉格朗函数

目标函数是求解在约束条件g(x)下的二次型函数f(x)的最小值，直观上我们希望构造一个函数L(x)，使得L(x)在f(x)的可行解区域内的求出的值和f(x)求出的值完全一样，而在f(x)的可行解区域外，L(x)的值又接近无穷大，这么做的目的，使得我们可以用一个函数L(x)来等效表示原问题的g(x)和f(x)

拉格朗函数的目的，就是将约束条件融合到目标函数中，构造一个新函数来表示目标函数，将有约束的优化问题转化为无约束的优化问题

下面，我们构造拉格朗函数来表示目标函数

其中αi是拉格朗日乘子，每一个约束条件对应一个拉格朗日乘子，其中αi大于等于0

则原优化问题可以转化为

讨论如下条件(1)(2)：

(1) 当样本点不满足约束条件时，即说明在 可行解区域外

此时将αi置为正无穷大，那么θ(w)显然也是正无穷大

(2) 当样本点满足约束条件时，即说明在 可行解区域内

此时θ(w)的最小值就是原目标函数，于是综上所述，引入拉格朗乘子函数后，可以得到新的目标函数

我们用p*表示优化目标函数后的最优解，且与最初的目标函数等价

观察新的目标函数，如果直接求偏导数求解，那么一上来将面对w和b两个未知参数，而αi又是不等式约束，求解过程将非常复杂。换一个角度思考，如果将max和min的位置对调，变成如下新的目标函数

上式变化使用了 拉格朗日函数的对偶性，交换后的新问题即是原目标函数的对偶问题 ，我们用d*来表示对偶目标函数的最优解，可见d*的求导过程比p*相对容易，且d*<=p*，而当满足下列条件时，d*= p*

因为目标函数本身已经是一个凸函数，而优化问题又是求解最小值，所以目标函数的最优化问题就是凸优化问题，则接下来就要重点讨论KKT条件

六、KKT条件的描述

一个最优化模型能够表示成下列标准形式

其中f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，m和n分别是等式约束和不等式约束的数量

KKT条件即是规定f(x)的 最优值 必须满足以下(1)(2)(3)条件， 只有满足KKT条件，目标函数的最优化问题依然可以用拉格朗日乘子法解决

很明显，我们需要优化的目标函数属于带有不等式约束函数g(x)，所以条件二显然满足，下面我们来分析条件一和条件三的理论

七、目标函数的等高线与约束条件的最优值分析（条件一）

对于KKT条件一的分析，我们假设目标函数是f(x1,x2)的二元函数，它的图像在三维空间里是一个曲面，准确的来说是一个凸曲面

其中g(x1,x2)是约束方程，要求目标函数f(x1,x2)的最小值，即转化为 求g(x1,x2)=c这条曲线上的一点，使得f(x1,x2)取得最小值，换个比喻，就是在山上（目标函数曲面）寻找一条山路（约束条件曲线）的最低点

我们画出目标函数的等高线，来分析目标函数最优值和约束条件的关系

对于研究目标函数z=f(x1,x2)，当z取不同的值，即将曲线z投影在(x1,x2)组成的空间中（这里指的是二维空间），也就是曲面的等高线，上图中d1和d2即是两条目标函数的等高线，可以看出，当约束函数g(x1,x2)与目标函数的等高线有共同的交点， 即证明这组值同时满足在目标函数的可行域中，也符合约束条件的约束关系

如果等高线与g(x1,x2) 相交 ，则是一组目标函数的解，但是这个解一定不是最优解， 因为相交意味着肯定存在其它等高线在该条等高线的内部或者外部 ，可能会使得新的等高线与g(x1,x2)的交点更大或者更小，这就意味着只有当等高线与g(x1,x2) 相切 ，才可能得到最优解（切线可能多条）

所以最优解必须满足： 目标函数的负梯度方向与约束函数的梯度方向一致

而上式恒成立的条件就是： 拉格朗日乘子α >= 0 ，且这个式子就是目标函数对各个参数求偏导数的结果，即KKT的第一个条件：目标函数对各个参数的导数为0

八、分类讨论约束条件和拉格朗日乘子的组合（条件三）

对于KKT条件三，可以看出，因为所有的约束函数gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和后结果为0，要么某个约束函数gi(x)=0，要么其对应的αi=0

从一个案例出发来分析KKT条件三的逻辑，假设目标函数和约束函数是

将不等式约束构造出拉格朗日函数，并分别对x1和x2求偏导数

而KKT的条件三要求最优解满足 ∑α*g(x) = 0，在这个案例里α和g(x)只有一个，结合条件一，可以得到

根据之前的分析，最优值满足条件三的话，要么α=0，要么g(x)=0

（i）：如果α=0，则x1=1，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0，发现这组解违背了约束函数g(x)<0，则舍弃这组解

（ii）: 如果g(x1,x2)=0，则代入x1和x2的表达式到g(x)中，解出α=58/101>0，发现这组解不违背约束函数，则代入α解出x1=130/101，x2=88/101，则这组解有可能是最优解

综上(i)(ii)讨论，目标函数的最优值符合KKT条件三，也说明了 满足强对偶条件的优化问题的最优值必须满足KKT条件

九、求解对偶问题

上面分析了目标函数满足凸优化和KKT条件，则问题转化为求解原问题的对偶问题（即p*=d*）

根据对偶问题描述，先要求内侧w和b关于L(w,b,α)的最小化值，即求L对w和b的偏导数

将w和b的偏导数带入拉格朗函数化简得

整理一下最终化简结果为

从上述结果可以看出，样本的x和y是已知的，此时的 L(w,b,α)函数只有一个变量，即αi

我们归纳一下现在的目标函数为

现在目标函数变成了如上形式，其中αi>=0，这里隐含着一个假设，即数据100%线性可分，但是现实生活中，数据往往是不会那么规则的线性化，为此我们需要引入松弛变量

十、引入松弛变量

由于现实世界中的数据都是带有噪音的，也就是数据可能出偏离其正常的位置很远，而出现这种极端现象后往往会影响超平面的选择，也许将无法构造出将数据彻底分开的超平面出来

所以对于处理这种情况， SVM需要允许（妥协）出某些噪音很大的数据点能够偏离超平面，即允许其出现在超平面的错误的一侧 ，为此我们引入松弛变量C，这样我们的目标函数又变为

接下来为了研究讨论αi的取值范围，我们加上一个负号将目标函数等价转化为

十一、讨论拉格朗乘子的取值意义和其值域

回顾一下最初的约束条件为

设ui为该约束条件，可以归纳出αi关于约束函数的取值意义

αi只有满足上述3种情况，才能求出最优解，所以 当αi与约束条件ui冲突的时候，需要更新这些αi ，这也就是满足目标函数的第一个约束限制，即0<=αi<=C

而同时目标函数还受到第二个约束条件的限制，即

所以不能只更新一个αi因子，需要同时再次更新第二个αj因子，也就是 α因子总是成对的更新（αi对总是和αj配对），一增一减，此消彼长，才能保证加权和为0的约束 ，同时这也就是下面提及SMO算法的思想和多元函数化简为二元函数，在从二元函数化简为一元函数的难点

根据这个约束和α因子需要成对更新，假设我们选取的两个拉格朗乘子为α1和α2，则更新之前是old，更新之后是new，且更新前后需要满足和为0的约束

两个因子同时更新显然非常困难，所以需要先求出第一个αj的解，再用αj的解去表示更新第二个αi的解 ，后文的SMO算法会阐述这一点。因此需要先确定αj的取值范围，假设L和H分别为它的下界和上界，结合目标函数的约束限制来综合讨论L和H的取值关系

（i）：当y1和y2异号时，可以得到

移项可得a2 = a1 - A，此时α的取值范围如下图所示

所以此时α的上下界H和L为

（ii）：当y1和y2同号时，可以得到

移项可得a2 = -a1 + A，此时α的取值范围如下图所示

所以此时α的上下界H和L为

综上(i)(ii)的讨论，通过y1和y2的异号或者同号，可以推导出α更新后的上下界分别为

这个公式显得非常的重要，它将α因子限制在有效的矩形范围内，在SMO算法中，当我们更新完α后，由于α可能会被更新得很大或很小，因此需要经过裁剪来保证α的在约束条件内

12、SMO算法的思想

回顾之前第九，第十，第十一步的分析，目标函数为

目标函数只包含n个变量α的 多元函数 ，且带有两个约束条件，我们的 目的是求出目标函数的最小值，即找到一组α的组合，使得目标函数取得最小值

由第十一步的分析，我们需要不断更新这n个α因子，通过迭代来逼近函数达到最小值，但是如果一次性更新n个参数，将会有n!种组合，那么时间复杂度将会非常高，为此我们首先想到 坐标上升（下降）法

来通过一个例子来说明坐标上升法的思路

可知案例中要求一个三元函数的最大值， 算法的思想是每次迭代时只更新一个维度，通过多次迭代直到收敛来优化函数的最值 ，求出三个变量的偏导数推出其关系

通过迭代即就可以求出其最值

SMO算法借鉴了坐标上升（下降）法的思想来优化α因子组合，但是由于目标函数的第二个约束条件有加权和为0的限制，导致每次迭代时候不能只更新一个因子αi，必须同时更新与之配对的另一个因子αj，此消彼长才能保证加权和为0（第十一步中已提及）

所以SMO算法思想是将原始问题中，求解n个参数的二次规划问题，分解成了多个子二次规划问题来分别求解，每一个子问题只需要求解2个参数，即将多元函数推导为二元函数，再将二元函数推导为一元函数

13、多元函数推导为二元函数

目标函数是关于α的N元函数，通过SMO的算法思想，假设每次迭代更新，选取一对α1和α2的组合，其余的乘子不变， 首先需要将α1和α2从目标函数中分离出来 ，也就是将多元函数推导为二元函数

从N元函数中分离出α1和α2因子

由于上式推导结果过于复杂，我们定义2个表达式来表示上式常量部分，用来简化上式

又由于单独存下的常数项对以后的求导没有贡献，所以我们提出单独的常数项定义为Constant

带入vi和Constant表达式，则结果化简为

至此，我们将 多元函数推导为含有α1和α2变量的二元函数 ，接下来将这个二元函数推导为一元函数

14、二元函数推导为一元函数

我们需要推导出α1和α2的关系，然后用α2来表示α1带入二元函数，就可以推导出关于α2的一元函数了

由目标函数的第二个约束条件

同理根据SMO算法思想，从约束条件中分离出α1和α2

将等式两边同时乘以y1，可推导出α1和α2的关系

同理，我们定义两个表达式r和s来表示上式的常量部分，用来简化上式关系

带入r和s后，α1和α2的关系推导为

下面将α1带入我们的二元函数中，可得

至此， 我们将二元函数推导为只含有一个变量α2的一元函数 ，接下来终于可以对目标函数求导了

15、求解一元函数的偏导数，推导出第一个拉格朗乘子的递推关系

我们对一元函数求α2的偏导数为0

带入s=y1*y2和y2*y2=1，整理上式可求出α2