8.3 线性支持向量机与软间隔最大化（P125）
8.3.1 线性支持向量机
- 区别：对于线性可分向量机而言，需要满足的条件就是yi(ωix+b)≥1就可以了，但是在线性支持向量机里头并不是所有点都满足上面这个条件，竟然会出现下图中黄/绿色的点，所以就要用松弛变量/弹性因子来对他们进行满足条件；
-
对于间隔内的点：由于一些点位于间隔区域内，那么其函数间隔肯定就＜1，这时候要加上一个松弛变量ξi使其≥1，这里的ξi ∈ (0,1)：
对于间隔外的点：对于这些点而言，它们的函数间隔明显是小于-1的（即函数间隔的绝对值大于1，但是因为错了方向，函数间隔将小于-1），公式还是上边那个，但是里面的ξi > 1；
我们称上面这个表达式为软间隔；
此时新的目标函数就变成了：
这里的C是惩罚系数，决定了原始参数和松弛变量之间的影响权重：
⚪C越大代表了误分类起到的作用更大，也可以说对误分类的惩罚力度大，这时候就更关注第二项；
⚪C越小代表正确分类的参数作用更大，对误分类的惩罚力度小，这时候就更关注第一项
这样一来，优化问题就变成了：
对于这个优化问题，可以继续按照之前的思路解得ω*和b*，然后得到相应的分离超平面和决策函数
8.3.2 学习的对偶算法
-
原理：将上面的优化问题转化成对偶问题来进行求解，为了与之前一般形式的不等式形式一致，那就转换成≤的样子（此处共有2N个条件）：
想要得到对偶问题，就要先得到其拉氏函数，那么就要用上拉氏乘子，这里给第一个约束条件用αi，第二个用μi，这样就得到了拉氏函数：
然后用极小极大问题（原始问题）来进行求解：
转换成对偶问题就是：
对于原始问题来说，最终所得到的是ω*和b*（ξ对于超平面和决策函数没用）；
对于对偶问题来说，最终所得到的是α*和μ*，然后再带回到拉氏函数中得到对应的ω*和b*
-
求解过程：
1.内部极小化：对于ω，b，ξi求偏导并令其为0：
求解得：
对于第三个来说实际上有N个式子
然后带回到拉氏函数中，最终得到：
2.外部极大化问题：
乘了个-1就变成了极小化问题：
其约束条件为：
共有N+1个约束条件
3.利用KKT条件来解：
先把KKT条件搬过来：
对于等式第一项就是用偏导数=0的解；
对于条件第一项就是：
对于条件第二项就是：
对于条件第三项就是：
目标：从上述条件中找出b的最优解，根据ω和ξ的条件可以得到：
接下来根据yj(ω*xj+b)=1（此处的yj的值为±1，所以 移项后还是yj）就得到了b*的表达式：
那么最终的分离超平面和决策函数也就出来了；
-
算法：
①当0<αi*<C时，那么对应的实例点就在边界上；
②当αi*>C时，此时ξi≠0了，那么就有这几种情况：
8.3.3 合页损失
-
合页损失函数：
其对应的图形是：
-
作用：用和也损失可以把原始问题中的ξ去掉，方便计算，对于原来的ξ而言：
然后把ξ变成和合页损失函数就是：
替代原始问题中的ξ后目标函数就变成了：
通过倍数变化（除以C）转换成另一种形式的等价表达式：
其中λ=1/2C，这里就是正则化的表达式
-
三个损失函数的比较：
图形：
表达式：
0-1损失函数：
感知机损失：
合页损失函数：
0-1损失函数不是连续可导的，所以一般不作为目标函数；
感知机的损失是当分类错误时(t≤0)有损失，不然就没有；
线性支持向量机的损失是当间隔小于等于1时(t≤1)为特殊点，有损失，不然就没有；
所以后面两种都可以拿来做目标函数
8.4 非线性支持向量机与核函数（P133）
8.4.1 非线性支持向量机
-
线性支持向量机的特点：
1.线性可分：
存在一个分离超平面把所有点全都正确分开；
2.线性不可分：
也能找到一个超平面，但是可能会出现误分类点，不过数量不多；
-
非线性支持向量机特点：
非线性可分：
如上图所示，虽然无法用直线（线性模型）将正负实例正确分开，但是可以用一条椭圆曲线（非线性模型）将其正确分开；
非线性不可分：
对应于线性不可分； -
分离超曲面：就是上面的那个椭圆所对应的表达式，但是在实际应用中可能不止是个椭圆，也有可能是个多次方程；
以椭圆的那个为例，其对应的方程就是：
令(x(1))2和(x(1))2分别记作z1和z2，那么就变成了先行表达式：
——>新问题：如何将原空间的点映射到新空间上去—>核函数
8.4.2 核函数（P134）
线性可分支持向量机中的目标函数：
原空间：就是输入的特征对应的输入空间，有个 内积 ，记作x1·x2;
新空间：也得有个 内积，记作z1·z2——>新问题：如何找到新空间内积；
运用映射函数就可以实现下面的功能：
-
核函数：
例子：
已知核函数：
其中x,z都属来自于输入空间R2（二维欧氏空间），先把核函数展开：
1.第一种映射：令H=R3，那么为了凑出上面的展开式就令：
那么其内积就是：
这就说明这个映射时成立的
2.第二种映射：还是令H=R3，但是映射函数变成了：
上面的映射也是成立的；
3.第三种映射：令H=R4，相应的映射函数就变成了：
上述例子在都说 同一个核函数可以存在多个映射 ，但是最重要的还是找到核函数K，这样才能解决问题
8.4.3 从向量空间到希尔伯特空间
由于原来的内积一定是>0的，所以转换后的核函数也要满足这个条件；
-
正定核：
步骤：1.找到一个对称函数K(x,z)，x,z∈X，要求对∀x1,....,xm∈X对应的 Gram矩阵 半正定
注意，这里的Gram矩阵不太一样：
稍微扩展下就是：
若将A进行变化后可以变成D，那么其必然≥0：
那么判断一个矩阵是否半正定就有如下两个方法：
1.看看所有的 特征根 是不是都≥0；
2.看看主子行列式是不是都≥0；
2.根据对称函数K(x,z)，构成一个希尔伯特(Hilbert)空间（这一步先构建一个向量空间）
多种空间定义：
所谓空间其实就是一个集合，然后在这个集合上定义了多种运算规则，如果任取空间中的向量，经过上述一系列运算后，新生成的向量还属于这个空间内，这就满足了要求；
所以我们只需要按照上面的步骤，经过「向量空间」、「内积空间」、「赋范空间」，最终找到「希尔伯特空间」就可以啦。
具体步骤：(1)定义映射Φ:x->K(·,x)并以此来构成向量空间(这个·是说这里有个值，但是还不知道是啥），先找一个空间，使得原始向量通过这个映射之后，对于加法和乘法运算是封闭的。可以写成：
这里是对于K(·,xi)的线性组合，然后运算后得到一个元素，记作f
由元素f构成集合S，那么S就是一个向量空间了，因为其对于 加法和数乘运算 是封闭的。
验证：
3.在集合S上定义内积，从而找到内积空间
需要在S的基础上定义内积空间 ，假设定义了一个运算符*，其含义为对于∀f,g∈S，都有：
要证其为内积，那么就要实现下面的四个条件：
第二项就是分配律；第三项就是交换律，由于K是对称的，所以一定实现；第四项的特殊情况是若f*f=0，那么f就是0向量
验证每个条件：
充分性（从f=0推出他俩乘积为0）：当f=0时，f(·)=Σi=1mΣj=1mαiαjK(xi,xj)=0，这里的xi是任意的，所以K(·,xi)不可能恒为零，那么只能让αi=0，于是：
这样充分性就证好了；
必要性（上面反一下）：先证个辅助结论：
证明过程：取任意λ∈R，f+λg∈S。然后用第一部分，可以得到(f+λg)*(f+λg)≥0，这个不等式对于任意λ都恒成立。然后将其整理为关于λ的二次不等式：
上面方程可以化为aλ2+bλ+c≥0,显然，a=g*g≤0；若要让这个不等式恒成立，那么就是让（也就是二次方程没有/就一个与x轴的交点）：
把g取特殊情况：g(·)=K(·,x)，那么f*g=Σi=1mαiK(x,xi)，再套用下刚刚证明的公式：
最右边还有个K(xi,xj)；来自于下面的展开式：
化简一下就是
又因为ff=0，所以上面的不等式的右侧就为0
然后根据夹逼准则*可以得到：
也就是：
跟前面一样的道理，只有αi=0，上面的式子才能恒成立，所以f=0，这样的话必要性也就证好了；
这样一来S就变成了内积空间
4.在S上定义范数，从而变成赋范空间，最后就可以升级成希尔伯特空间：
定义赋范空间：
核函数K有个再生性的特点，已知有个f：
那么与K(·,x)求内积就是：
而两个核函数的内积，还是核：
8.4.4 正定核的充要条件（P139)
-
充要条件：设K：X × X是R维的对称函数，则K(x,z)为正定核的充要条件是对∀xi∈X，i=1,...,m，K(x,z)对应的Gram矩阵就是：K = K[(xi,xj)]m×m是半正定矩阵，这也就是说：
证明：略，要看的话去书上看看，挺详细的；
-
正定核的等价意义：
实际应用时可以先找到一个对称函数，然后输入任取的m个元素，对应的Gram矩阵是半正定的，则K(x,z)就是正定核函数，就可以用到算法中去了；不过检验这个矩阵是否正定并不容易
