八、支持向量机

决策函数：f(x)=sign(wx+b)，其中sign函数像感知机，而ωx+b则像逻辑斯蒂回归；

8.1逻辑回归与支持向量机

8.1.1 支持向量机与感知机以及逻辑斯蒂回归的关系

逻辑斯蒂回归：
Y∈{0,1}，那么其概率就是：

这样一来就可以得到：

因为ω本身就是n维，然后再带上个b之后参数向量就变成了n+1维的

关系到了概率，就用极大似然来估计，先弄出来似然函数：

可以通过遍历法（计算量大且耗时）、求偏导(解析解)（这题很难得表达式）、迭代法（牛顿/梯度下降法）来求解最优参数ω^*

但是，上述方法并没关注其几何意义，但是几何意义却可以帮我们快速求解；

先回顾下逻辑斯蒂回归分类：
假如此时P(Y=1|X)>0.5那么意味着Y=1类，反之亦然；而这个性质体现在log函数中则是：

而当P(Y=1|X)<0.5时：

那么就有了：

那么ωx+b=0就是一个超平面了，这样就把逻辑斯蒂回归变成了具有几何意义的感知机了。

8.1.2 为啥叫支持向量机

分离超平面可能不唯一——>

分类确信度

上面的式子意味着离超平面距离越远，分类确信度越高；

分类正确性：判断这个分类是不是正确的指标，若判断正确，那么y_i就和ωx_i+b同号：
几何间隔：既能度量确信度又能度量正确性，记作γ_i：

——>最有用的点就是 距离超平面最近的点：

就是下面红框的三个点：

想要找到最佳的分离超平面就是使最小的这些点分的越开越好，也就是最小间隔最大化（极大极小问题）：

在Rⁿ空间中一个点就对应了一个n维向量，而这些向量则被叫做支持向量

8.2 线性可分支持向量机（书上P112，这里的线性可分是个理想化状态）

8.2.1 线性可分支持向量机的学习问题

几何间隔：当ωx+b正确分类时，几何间隔就可以写为：

其中，||ω||代表 欧氏距离，在这里的含义就是：

然后再对γ_i进行拆解，变成了：

其中，x_i和y_i都是已知量，那么现在的问题就是怎么求出未知量ω和b；
这里就用到了 最小几何间隔最大化 ：

实际上就是把所有的几何间隔全都求一边然后找出其最小值：

然后就是优化问题：找到最大值所对应的参数ω和b，注意有约束条件γ最小：

因为这里共有N个γ，所以就有了N个约束条件，且 都是不等式约束

函数间隔：对上面的优化问题进行简化

其与几何间隔的关系：

把上面优化问题的几何间隔全都用函数间隔替换后就变成了：

8.2.2 超平面可识别性

问题：超平面方程发生 成比例的变化 那么函数间隔的值也会发生成比例的变化，不过超平面并没有改变——>同一个超平面可能对应不同的表达式
方法：那么就需要对其法向量ω（参数向量）加一些约束条件，比如规范化，即令||ω||=1，使得间隔确定；
例子：
下面这两个表达式代表了 同一个超平面 ：

但是由于其参数不同，所以得到的函数间隔也不同；接下来我们将参数向量ω进行规范化就得到了新的表达式，并将新的系数记为单位向量ω=(3/5,4/5)^T：

这样一来，就多了上面的优化问题的约束条件就多了一个：

这样的话，需要在n维单位超球面上求解优化问题，但是新的约束条件让计算过程更加复杂

既然分母变起来麻烦，那就变分子，也就是在γ^上加个约束条件，比如令其等于某一常量，那么优化问题就变成了：

此处取r^=1(想取啥都可以），也就是距离超平面最近的点距离都是1，那么优化问题就变成了：

其等价于：

若实际的γ^与设定值有不同也没关系，就当成设定的值来算就可以了
这样的话约束条件仍是N个，但是目标函数的简洁了许多，并把γ^=1这个约束条件隐藏在其中

8.2.3 线性可分支持向量机的学习问题是凸优化问题吗？（P116）

凸优化问题：就是约束最优化问题，需要先证明||ω||是个凸函数，同时去证y_i(ωx_i+b)≥1是仿射函数
从||ω||的计算公式中不难看出其为一个凸函数，图像如下：

接下来证明仿射函数（最高次数为1的多项式函数），先对不等式进行换位：

很明显这是一个一次函数，满足仿射函数的要求；这也就说明了其有最优解

书上的定义是f(ω)和g_i(ω)都是凸函数并且h_i(ω)是仿射函数的叫凸优化问题；而f(ω)是二次函数且g_i(ω)是仿射函数时，就变成了凸二次规划问题

8.2.3 证明最优的唯一性

实际上就是要从存在性和唯一性两个角度出发：

存在性：已知训练集 线性可分，那么一定存在超平面ωx+b=0（||ω||不可能为0，因为零平面所有的实例点是无法分清的）可以将其正确分开
唯一性：用 反证法 来进行证明，先假设存在两个最优解(ω₁^*,b₁^*),(ω₂^*,b₂^*)，显然||ω₁^*||=||ω₂^*||=c，再构造新参数ω=(ω₁^*+ω₂^*)/2,b=(b₁^*+b₂^*)/2：
1.对于ω： c ≤ ||ω|| ≤ 1/2 ||ω₁^*||+1/2 ||ω₂^*|| = c——>||ω||=c=1/2 ||ω₁^*||+1/2 ||ω₂^*||
那也就是说ω₁^*与ω₂^*一定要在同一条直线上，不然就是下述情况：

如果ω₁^*与ω₂^*不在同一直线上，那么就可以构成一个平行四边形，然后其中的三角形就有了下面不等式的关系，就与题设不符

所以ω₁^* = λ ω₂^*，又已知他俩的模都是c，所以λ只能取±1，但是如果取-1，那么ω就为0，但此时的(ω,b)就不是可行解，所以λ只能取1，即ω₁^* = ω₂^*

2.对于b：
接下来看b₁^*和b₂^*是否相等：
由于上面证明了两个ω相等，所以把两个解写作(ω^*,b₁^*和(ω^*,b₂^*)
写出第一个解的超平面：ωx+b₁^*=0，那么其支持向量以及对应间隔为：

而第二个超平面ωx+b₂^*=0的支持向量以及对应间隔为：

由公式可以推出两个b的公式用于判断他俩是否相等：

注意，这两个b直接进行除法的时候这个ω不能约！（这是个向量内积/0向量），所以使用作差来求解

对于第一个超平面来说：

同理，对于第二个超平面来说：

上面两个不等式说明：ω^*(x₁-x~2~)=0，同理可得对于x_i``的差也是等于0，那么就是说b₁^* - b₂^* = 0，所以最优解就只有一个

8.2.4 最大间隔法（P116)

算法：

这里优化问题的目标函数变成这样是为了方便后面求导

对于这个函数图像而言，其函数间隔为2，几何间隔为2/||ω||，H1，H2称为间隔边界

例题：在感知机模型的例题中所得到的分离超平面并不唯一，不过支持向量机就可以得到唯一的最优分离超平面

已知三个样本点的坐标分别是：

由于此时的样本是二维的，那么对应的ω也就是二维的，那么就可以构造优化问题了：
1.构造优化问题：

2.解决优化问题（找分离超平面和决策函数）：得到最优解对应的ω^*和b^*

蓝色区域代表第一个约束条件，紫色区域代表第二个约束条件，橙色区域代表第三个约束条件；当b发生变化时，区域所在位置也会发生变化

目标函数最小就说明重叠区域的点与原点的距离最小：

也就是橙色区域和蓝色区域的边界重合的时候，化成公式就是：

这样就可以算出b了，然后再把b带回到第二条公式就有了ω₁+ω₂=1
然后就把上面得到的两个式子带回到目标函数中得到如下方程：

最后就是求这个方程取最小值时ω₁的值，算出来是1/2，那么ω₂也就有了，这样超平面和决策函数就算出来了

由于x₁和x₃是位于超平面上的最小间隔点，所以他俩就是支持向量

8.2.5 对偶问题

首先，构建拉氏函数：

里头的α就是N维优化问题对应的N个拉氏乘子组成的向量

然后将括号打开：

因为目标函数是求出最小值，那么这个式子对应的 原始问题 可以写成：

那么其 对偶问题 就是：

将上面式子的 内部极小化 后所得函数记作θ_D(α)；这样一来，对偶问题就变成了两部分：

1.内部极小化：希望得到θ_D(α)，先将原函数对ω和b求偏导并令其为0：

其对应的解就是：

再将解带回到拉氏函数中从而得到θ_D(α)：

2.外部极大化：
要优化的式子可以写成：

这个式子中可以看出我们最终就把问题转为了求解最优α的凸优化问题，接下来就是看如何根据α^*求得对应的ω^*和b^*;

8.2.6 如何通过对偶问题获得参数（P122,定理7.2）

KKT条件：

约束条件就是：

第一项中的x就相当于此处的ω，此处的表达式就是：

求解得：

由于线性可分支持向量机不包括等值约束，那么就不包含h_j(x^*)了；
第二项把x拿ω和b替换掉后就变成了：

若α为零向量那么就无法得到分离超平面，所以其不能为0。这样一来，就是要让g_j(ω,b)=0，将满足的点记为(x_j,y_j)，这样就有了b^*的表达式：

又因为y_j=±1，所以y_j=1/y_j，这样一来函数就变成了：