8 支持向量机 (9) 如何通过对偶问题得到参数

这里的参数就是ω* 和b*
在（最大熵模型的）KKT条件中，不等式所对应的约束条件写成ci(x)，就是我们之前的gi=1-yi(ωxi+b)，要满足αici(x)=0，因为αi*>0，所以gi=0

因为yj不是-1就是+1，所以yj=1/yj

得到超平面和决策函数，就是把ω和b带入

线性可分支持向量机的对偶算法

对偶算法，由求极大极小值，到求min-θ(α)

将样本点带入优化问题

（x1·x1）=（3×3+3×3）=18
计算交叉项部分

最后得到式子

化简它，用一个约束条件，因为y1=y2=1，y3=-1，然后这个式子展开就是白字了

化简结果，记作S

要得到α1和α2，分别对它们求导

解出的结果不满足条件，因为α1、2都必须大于0

边界可能是α1、2=0的时候：

比较得知第二种可能性更小，所以解得α1、2，带入得α3

因为α1、3>0，说明x1和x3是支持向量，如下图

可以用支持向量找到ω* 和b*
求解参数：

所以ω1* 和ω2* 就是1/2和1/2了
随意用一个支持向量来得到b*

分离超平面就是将ω* 和b*带入，决策函数就是在前面加一个符号函数sign

---

有时候实例点落入了间隔区域内，甚至到了相反的区域内（容易成为判断错的点），那么原来的约束条件就不对了。
对于线性可分支持向量机，约束条件是让函数间隔都>=1，也就是yi(wxi+b)>=1。如果出现不符合这个约束的点，在间隔内，我们加一个参数ξ

如果实例点跑到对面的区域中，这时候函数间隔是负的

函数间隔

比如这个实例点，在分离面的下方，wxi+b<0，但yi是+1，那么相乘是负，这时要求函数间隔>=1，那么ξ要>1

这时候线性支持向量机是软间隔，有弹性因子ξi，也称松弛变量

目标函数要加上弹性因子，前面加参数C，决定ξ起作用的大小，称惩罚系数

优化问题为

求得w和b根据wx+b=0得到超平面和决策函数

怎么得到w* 和b* ，借助对偶算法

原始问题解决最小化问题

找到对应的广义拉格朗日函数，就找到了相应的对偶问题。借助拉格朗日乘子，上面配的是αi，下面配μi

那么原始问题和对偶问题就变成如下，右边是输出

对偶问题得到的拉格朗日乘子去得到w* 和b*
将内部极小化问题记作θD(α,ω)，求解参数就对拉格朗日函数求偏导，分别求ω、b、ξ的导，求解结果在左边

将得到的解带入拉格朗日函数，删去为0的项和合并同类项后

转换为求负的min

对偶问题就是求函数min时α取多少

约束条件要乘上拉格朗日乘子

这两个条件可以用来求b*
再带入KKT里的条件

反着的“E”是存在的意思。

在间隔边界上ξi=0，那么μi≠0，而它又大于0

找到0<αi* <c就是在间隔边界上的点了，这些点满足yj（wxj+b）=1，然后带入w*

对于惩罚参数C，可以用交叉验证

线性支持向量机软间隔算法

合页损失

损失表示成z：

松弛因子对那些误分类点和间隔内的点有效，将ξi简化，下标带+代表取合页损失，大于0代表需要考虑，是误分类的点，小于等于0的就不需要考虑，是正确分类或者在边界上的点

用这个表达式替代原始问题的函数

如果令1/2C=λ，就像正则化，后面这项就是关于复杂度的项（正则化项）

这个图横轴是函数间隔，记作t，纵轴是损失。对应0-1损失函数是：t<=0时取1，因为分类错误的时候是损失的时候，t>0是没有损失，记为0。红线是函数，不是连续的不可导

绿色线，感知机的损失函数考虑的是，如果误分类了，就找出来，用函数间隔表示，但是因为代表损失，比较的是正数，所以对应-t。

线性支持向量机的损失函数，黑色线是它的上界

线性支持向量机比感知机要求高一些，这也是为什么它可以找到唯一的超平面。

非线性支持向量机

对于线性不可分，用松弛变量，软间隔的办法。

对于非线性支持向量机，用已解决的办法去解决新问题。椭圆方差如黄色字，在欧式空间。现在做一个变换将x(1)^2=z(1)，得到绿色字，在欧式空间里是直线。我们把它换一个空间，在Hilbert空间，是线性

问题：如何将原空间点映射到新空间？用核函数
原空间（x，欧式空间）：输入的所有特征对应的空间。计算关键在内积
新空间（z，Hilbert/希尔伯特空间）上仍需要内积运算，需要在新空间计算zi和zj的内积

希望找到映射Φ(x)从欧式空间X变换为Hilbert空间H

定义H空间的内积，要确定zi和zj。zi = Φ(xi)，zj = Φ(xj)
zi · zj = Φ(xi) · Φ(xj) = K(xi · xj)
这里得到的内积用核函数表示，就是K

假如已经得到K的式子，那么Φ可以取什么呢
因为x和z都是二维空间的，得到核函数的形式

那取什么映射能得到这个核函数？

假如新空间是三维的，那映射就是把二维变成三维。定义一个三维的Φ，内积就是核函数K，说明定义的映射成立

换一种方式定义映射，算内积，这次也成立

所以对于同一个核函数，可能存在多个映射
无论有多少个映射，最终都是同一个函数，优化问题中最重要的是核函数，所以没必要找映射Φ，确定K就可以。

我们要找核函数，还得是正定核函数，因为要替代原来的内积定义，对于同一个向量的内积一定是大于等于0的值，所以核函数也满足这个条件。

在新空间里的K是一个肯定是一个对称函数，即使互换xi和xj位置也不影响，于是要求是：
1、找到对称函数K，x和z来自原始空间、输入空间X。要求矩阵是半正定

“倒A”表示任意
原来的Gram矩阵用内积定义如左，新的用对称函数得到矩阵

半正定
矩阵A，对于半正定、半负定、正定、负定，含义如下

要这么判断一个矩阵是半正定比较麻烦，可以变换。如果A分解后一组非0的特征根，这些特征根大于0
经常变化，带入“二次型”中，表现为yT D y，这么这里得到的是平方和的形式，自然>=0

所以第一个找K的方法，是找特征根，因为分解之后得到的D，就是由特征根组成的对角阵。如果A全部>=0，那么就是半正定的。

第二种方法，如果是半正定的，那么行列式是>=0的。如果从头看到尾都是>=0的说明是半正定的

如果能用K构造成H空间，就是在定义内积的基础上，找到了投影之后的空间

具体：
1、定义映射Φ，在此基础构成向量空间。（向量空间可以做线性空间后仍属于这个空间，所以也称线性空间，也就是加法和乘法（数乘，而不是向量相乘的内积）后还是这个空间）。定义内积空间是对加法和数乘、内积都封闭
如果想知道向量的长度，定义范数，得到赋范线性空间
二范数，表示两个范数的距离问题
在多维空间里定义以上加法和数乘、内积、范数，构成欧式空间

如果研究收敛性和极限，希望所有点都在空间里，叫Banach空间

定义另一种内积、范数，也完备，就是Hilbert空间

所以要一步步来，先得到向量空间。找映射，映射过去得到K函数作用的结果，点表示这里有一个函数但不知形式。假如已经定义映射，要保证是向量空间，那么对加法和数乘是封闭的。于是在这个基础上定义线性组合，记作f(·)

f构成集合S，S就是向量空间

下面定义向量和向量的乘积，定义一个新的内积
2）在S上定义内积：内积空间
“ * ”表示一种运算，如果* 是内积，要满足4个条件

（省略证明可以是内积运算的过程）

3）在S上定义范数（赋范线性空间/赋范向量空间），升级为H空间