机器学习-支持向量机（SVM）

多元函数的极值

定义
设函数，点
如果存在某个,使得对所有满足 且的点都有：

那么点就是在内的极大值点，反之则是极小值点。

二元函数的极值

为了方便说明这里用二元函数而作为例子，我们对二元函数的极值做单独的定义如下。
设函数在点的某一个邻域内有定义，对于该邻域内异于点的零一点，如果恒有：

则点为该邻域内的极大值点，反之则为极小值点。
定理1
若函数在点具有偏导数，且在点具有极值，则它在该点的偏导数必为0，即：

这个点是函数的驻点，根据定理1，具有偏导数的函数的极值点必为驻点，但是驻点不一定是极值点。

条件极值与拉格朗日乘数法

函数的自变量落在定义域内，并无其他限制条件，这一内函数求极值被称为无条件极值，如果有其他的附加限制条件则被称为有条件极值。求条件极值的一种方法就是拉格朗日乘数法。
设二元函数和在区域内有连续偏导数，则求在内满足的极值，可以转化为拉格朗日函数

设点是函数在条件下的极值点，即是函数的极值点且
设函数和 在点处有连续的偏导数且（这个是将隐函数改写成的必要条件），此时就可以设，即是关于的函数，将其带入到中则有
，如此便将二元函数转换成了一元函数，将二元函数求极值的问题转换成了一元函数求极值，一元函数求极值的必要条件是其一阶导数等于零，故这里将对求导

这里因为那么就涉及到了复合函数的求导，利用复合函数的求导法则即链式法则对进行处理，即先对求导再乘以对的导数
因为点是的极值点，所有

隐函数求导的时候对等式两边分别求导
这里对进行求导

即所以有

即

带入（1）有

即此时在条件下的极值存在需要满足的必要条件为

令有

等式（2）前面就是拉格朗日函数了，被称为拉格朗日乘子，
在上面的方程组中，存在三个未知数需要求解，只有两个方程很明显是解不出来的，所以还需要想办法寻找第三个方程解方程组。
对（3）两边同时乘以得到

即

因有（2）所以有
故有

即

成立，故有方程组

这里看似是三个方程其实还是两个方程，因为第二个方程是通过第一个方程推出来的，那么为什么需要这两个方程呢，还记得之前的假设么，
因为有这个假设才能定义，不然分母就为了，那么当真的为的时候呢，这时候就需要第二个方程了。
前面的推导中我们有 此时要求不为。那么这个方程组就不依赖于 或 了

所以得到结论，对于有条件极值函数的极值的拉格朗日乘数法基本步骤为：
构造拉格朗日函数：

得到方程组

这样求得的点是满足条件约束极值点求解的必要条件的但不够充分，解出的该点的充分性需要具体分析了。

矩阵分析中的拉格朗日乘子

含有等式约束的拉格朗日乘子法

只含一个等式

函数是参数向量的函数，约束条件为：

求的极值可以描述为：

根据上面的方法，使用拉格朗日乘子定义一个新的拉格朗日函数

然后构造方程

含多个等式

函数是参数向量的二次函数，约束条件为：

求的极值可以描述为：

定义拉格朗日函数

构造方程

含不等式约束的拉格朗日乘法

含有不等式约束的的函数极值求法一般使用对偶方法进行求解，首先定义原始问题

转换为拉格朗日函数

求原约束函数的极小值就是求这个拉格朗日函数的极小值
此时定义约束条件，则，则有：

此时求的极小值就是求的极大值

此时以及是满足约束条件的，但是的取值是任意的，我们需要分情况讨论，当满足约束与时，就等于，当不满足约束的时候 则，则，数学表达即为

所以我们只需再对求最小值就可以得到，也就是说无论满不满足约束都可以通过求最小值的方法求得解，即：

这是原始约束极小化问题变成无约束极小化问题后的代价函数，简称原始代价函数。
定义原始约束极小化问题的最优解：

说人话就是约束函数的极小值就是的解。这里就将一个约束极小化问题转化为了无约束极小化问题，这个函数被称为原始代价函数。
如何对这个原始代价函数进行求解？
有一个结论函数是凸函数函数是凹函数。这里对一个无约束凸函数求极值那么求得的局部极小值就是全局极限值点。
但如果函数是非凸非凹的又该如何处理呢？这里想将非凸非凹的函数转换为凸函数或者凹函数不久可以了，这中方法就是对偶方法。

对偶方法

我们想求一个函数的最小值，是否可以转换为求另一个函数的最大值，且这个函数总是凹函数就好了。这样求得的局部最大值就是全局最大值并且是原始函数的最小值。
在固定的情况下我们考虑求的下确界。

这个函数有如下性质

• 对每个固定的 ， 是拉格朗日函数关于 的全局下确界；
• 它自动满足弱对偶性：若 ，则
• g总是凹函数（因是仿射函数族的逐点下确界总是凹函数，所谓仿射函数在这里就是在固定的情况下是关于的仿射函数）

所以得出原始函数的对偶函数为：

通俗讲就是求原始问题的最小值问题变成了求固定的情况下的下确界的上确界，更一般的理解就是求最小值里的最大值。
因为这些最小值都是小于的，所以要在这里面找一个最接近的就是求下确界关于的上确界。
又因为是凹函数，那么求凹函数的极大值就很美丽了。
当满足约束 且满足约束的时候，有

即

在取上确界

即

此时原始问题与其对偶问题的对偶性恒成立不需要任何其他的条件，被称为弱对偶成立。
倘若时则被称为强对偶成立。
强对偶成立是有一定条件限制的

slater条件

原始问题是凸优化问题，即以及都是凸函数，是仿射函数。
slater条件即：

KKT条件

支持向量机

对一个训练集进行分类学习，其基本思想就是通过一个分类超平面将训练集分开。能将训练姐分开的超平面有很多，学习算法的逻辑就是找到最优的超平面对训练数据及性能划分，
一般来讲要将两个训练集的中间分开最好，分类超平面导两侧训练集的距离越大越好，距离越大越有利于容忍更多的样本噪声，所以我们的任务就是找到一个距离最大的分类超平面。
我们用线性方程来对这个超平面进行描述

其中是超平面的法向量是位移。那么两个被分开的训练样本集就可以通过下面的方程组进行描述

当 时认为是某一类样本（正例），当 认为是另一类样本（反例）。 这里的表示的就是支持向量距离分类超平面的距离又被称为函数间隔，
这个距离是未被归一化的距离，其是认为定义的，你也可以定义其为，但是为了方便计算这里就定义为
那么我们要求最大距离，首先要定义距离，在多维空间中某一点导一个超平面的距离用下面的公式进行计算，这个距离被称为几何距离，是归一化的距离，其与法向量的长度是无关的。

推导
… 待定

距离超平面最近的几个训练样本集被称为支持向量，两个异类支持向量导分类超平面的距离之和为

根据上面的定义支持向量到分类超平面的未归一化距离被定义为可以将这个式子进行转化

所以我们的目标是找到的最大值，即：

为了使得间隔最大，只需要使最小，为了便于计算将等价为，所以将上式重写为

这就是支持向量机的基本型。
这是一个二次凸优化问题，可以用拉格朗日乘子法进行求解。
首先将其转化为拉格朗日函数

其原始代价函数

将原始问题转为对偶问题

对来说这是一个凸函数，所以直接对其求偏导就可以求到最小值。
首先对求偏导。

所以

对求偏导

得到

将（5）与（4）带入到（6）可以得到

考虑（5）的约束得到对偶问题。

同时需要满足KKT条件

• 不等式约束
• 非负性
• 互补松驰性
  
  将（4）带入到分类超平面方程中
  
  对应任意一个样本，当时，样本的位置对结果没有影响，所以 不能取，
  当时有即对应的样本点位于最大间隔边界上，即一个支持向量。
  这表明了支持向量机训练结束后大部分样本都不需要保留，最终模型只与支持向量有关。
  根据（7）需要求得，通过（8）与（9）求得，使用SMO算法进行求解。

线性不可分样本的支持向量机

样本噪声导致的线性不可分

当两类样本搅合在一起不能明显地通过一条直线或者超平面分开的时候就就需要用到“软间隔支持向量机”，这种线性不可分又不是完全分不开而是因为数据采样误差等因素导致的样本失真。
所谓“软间隔”集让我们的模型能够一定程度上容忍样本的噪声。通俗的讲就是样本能够落到分类超平面与过支持向量的超平面之间的区域。
当然这个容忍是有限度的，如果不设限那么所有的样本就都可以落在这个区间，这样也就意味着分类间隔可以任意大，于是分类就没了意义，所以我们引入了惩罚项，
当分类间隔越大惩罚越重，这样就避免了其无限的扩大。所以优化目标可以写作

其中 ,称为损失函数，其取值只有两个

当取大于1的时候越大对目标函数的影响也就越大，当C趋于无穷大的时候迫使目标函数极大，这样就会使得所有样本都满足要求，当C取有限值的时候将会对结果产生有限的影响，
所以通过调节C的大小可以控制软间隔宽度。这个0/1损失函数虽然功能上满足需求但是在数学上却不是一个好的选择，其是一个阶跃函数非凸非凹不宜求解，所以往往使用其他的函数来对该函数进行替代
常见的替代函数有
hinge损失函数：

指数损失：

对率损失：

这里以hinge损失函数为例带入目标函数

引入松弛变量原始问题改写为

上面就是软间隔支持向量机 含有两个不等式 引入拉格朗日乘子转换为

对求偏导

对求偏导

对求偏导

带入原问题后得到表达式 然后将原问题转为对偶问题如下 （和之前的操作一样）

满足KKT条件

经过变换处理的原始问题可以写为更一般的形式

其中 被称为结构化风险 被称为经验风险

完全不可分的支持向量机

将不可分的低维数据通过函数变换升维到更高维从而变为线性可分的问题。如果升为无限维的话那么结果必然是线性可分的，但是无限维带来的问题是计算量巨大无比。
有一种方法可以使得我们不需要结算所有维度的数据，只需要找到一个替代函数其结果与升维后的结果抑制就行，这个函数就是核函数
设将样本从低维映射到高维的函数为
则分类超平面的方程变为

最大化分类间隔的原始问题变为

对偶问题变为

核函数就是找到一个函数使得使得

这样就使得无限维的向量内积计算变成了在原样本空间中的函数的计算结果，就是核函数。
常见的核函数
线性核

多项式核

高斯核

拉普拉斯核

sigmod核

支持向量回归

…