[数据结构与算法]第6章 支持向量机理解记录

6.1 间隔与支持向量

需要找到一个划分超平面，使得对于样本集的划分的鲁棒性最好，并且对新样本的泛化能力更好。

划分超平面可以使用wTx + b = 0;进行描述，其中的w向量是平面的法向量，b决定了位移项（决定了超平面和原点之间的距离）。然后获得平面中的点到超平面的距离，如果对与样本的预测值来说，当y = +1的时候，将该样本带入之后可以得到上述超平面的值>0，然后是对y = -1的情况，那么得到对应的超平面的值<0。对可以实现上述判断的向量来说，这两个向量称为支持向量。

两个不同类的支持向量到超平面的距离的和称为间隔。

找到最大间隔的方法：在满足上述判断y = +1或y = -1的情况下，使得间隔最大。也就是最大化||w||^-1，也就是最大化||w||^2，那么就得到了支持向量机的基本型。

6.2对偶问题

对上述的支持向量机的基本型来说，使用拉格朗日乘子法可以得到该式子对应的对偶问题。

具体操作：对上述的条件中的每个式子添加拉格朗日乘子ai，而后对得到的对偶式子对w向量和b位移向量进行求导，而后根据求导的结果将对偶问题化为：了支持向量机的对偶问题的表达式，此后在解出a，求出w和b便可以得到模型。上述的过程需要满足的是KKT条件。

KKT条件：

Ai >= 0；yi * (f(xi) - 1) >= 0；ai(yi*f(xi)-1) = 0；

对上述的KKT条件来说，其中总有ai = 0；或者yi * f(xi) = 1；

如果是ai = 0；那么样本不会在上述的对偶模型的式中出现，也不会对f(x)有任何的影响，如果是ai > 0，那么必有yi * f(x) = 1，那么此时对应的样本位于最大间隔边界上，是一个支持向量。这显示出现了对于每个样本来说，如果对支持向量机模型的基本型来说，可以将||w|| ^ 2的值最大化，那么对该基本型对应的对偶模型式来说，其中的KKT条件的第三个式应当满足的是，ai > 0，且yi * f(x) ?= 1，这种情况下有：该样本就是支持向量机需要的支持向量。

为了解决基本型对应的对偶式的解决（即：w和b的确定），使用了一种高效的算法：SMO算法。

SMO的基本思路是：先固定ai之外的所有参数，然后球ai上的极值，由于有约束求和ai*yi = 0，那么先固定ai之外的变量，则ai可以由其他变量导出。SMO每次选择ai 和 aj两个变量，先固定其他参数，然后在参数初始化之后，不断执行：1.选取一对需要更新的ai和aj的变量；2.固定ai和aj之外的参数，然后求解支持向量机基本型对应的对偶式模型，然后获得更新后的ai和aj。

SMO选择的ai和aj是两个具有较大间隔的样本向量对应的拉格朗日乘子，这种选择是启发式选择，是因为选择这两个向量对模型的更新可以带来更大的变化。

使用上述方法的更新ai的原理：当选择了固定其他变量值，只有ai和aj两个变量的情况下，可以将其他固定的变量式移动到等式的右边，然后将该固定变量的值的综合记为c，而后那么aj也可以被ai表示，这样一来，对于基本型得到支持向量机的对偶式来说，其中只有ai一个变量进行二次规划，而对于这种式子来说 是一定有闭式解的。

对b来说可以使用任意一个支持向量对yi * f(x) ?= 1进行求解，进而可以得到b。

但是往往有更鲁棒性的做法，使用所有支持向量求得每一个获得b的平均值。

6.3核函数

对非线性可分的样本来说，可以将样本集映射到更高维的空间中，使得样本集在该空间中变的线性可分。（一定存在一个高纬度的空间使得线性可分）。

方法：使用fai(x)将原来的样本集进行高纬度的变换之后，得到了高纬度的向量。然后按照上述的过程得到对应的拉格朗日乘子法对应的式子。

注意式子中的fai(x)^ T * fai(x)，由于转换之后的样本向量的维度很高，所以采用另外一种计算方法。将上述样本在高维空间中的内积转换为样本在低维空间中使用某一个函数计算的结果。这里的函数就是核函数。然后得到的是支持向量展式。

关于核函数的定理：对任意的数据D来说，核矩阵K总是半正定的。那么，总是可以找到映射fai（），换言之，任何一个核函数都定义了一个称为：再生核希尔伯特空间。RKHS。

重点：核函数的选择就是支持向量机的重点。

6.4 软间隔和正则化

软间隔就是可以不满足：yi * f(x) >= 1。也就是在最大化间隔的同时，不满足约束的样本尽可能少。其中，对软间隔的支持向量机来说，增加了损失函数。

损失函数的作用是：是软间隔基本型中的必备的函数，主要是用来对KKT条件中的第三个式子：yi * f(x) >= 1。的一种泛化（自己理解）。

一般情况下会使用替代损失来替代其中的损失函数。

常用的损失替代函数：hinge损失，指数损失，对率损失。

之后将包含替代损失的基本型转换为拉格朗日乘子法对应的式子，并且其中包含了松弛变量，松弛变量的作用是：表征该样本不满足约束（即KKT中的第三个条件表达式）的程度。

而后使用求偏导等方法得到对应的对偶问题。同时对软间隔问题来说也有KKT条件（和硬间隔的不一样）。

结构风险和经验风险的组成了比较典型的优化目标函数。

此外还使用了正则化项（这里有：L2范数，L0范数）。为了防止过拟合的风险。

6.5支持向量回归

只有当预测值 - 实际值 > e的时候才可以成为误差，这一点和传统的回归模型不一样。

那么根据上述的假设条件，使用的模型表达式为：1/2 * ||w|| ^ 2 + C * 求和lamda e (f(xi) - yi)，其中的lamda e 是e-不敏感损失函数。引入松弛变量ei和ei^,这样的话上述的式子变成：1/2 * ||w|| ^ 2 ?+ C * 求和 (ei + ei^)，而后使用拉格朗日乘子法，然后通过将上述式子关于对应的w，b，ei，ei^求导来得到对应的对偶问题的模型表达式。同时该表达式也需要满足KKT条件。

然后得到对应的SVR的解的形式，然后在得到ai之后，由于条件中有ai > 0，且ai < C。那么一定有ei = 0，这样就得到了b的值。一般还是求得多个b的平均值。同样也可以使用核函数方法进行一个降维的计算。

6.6 核方法

实际上，对于上述的各种使用核函数进行简化计算的模型式来说有一个表示定理，对再生核希尔伯特空间H，对于任意单调递增函数oumiga，存在优化问题：F(h)，其的解可写为：h*(x) = 求和*aik(x,xi)；

对于核LDA，KLDA使用核函数方法。

假设：通过某种映射fai：X -> F，将样本映射到一个特征空间F，然后在F中执行线性判别分析，以求得：对应的线性判别分析模型公式，KLDA的学习目标是：在F空间中的关于样本集在F空间中的类间散度矩阵和类内散度矩阵之比的式子。

这里使用核函数来计算模型中需要确定的各种参数，用核函数表示对应的h(x)函数，从而得到对应的KLDA的a参数（这里的a参数是用来表示原来维度中参数w的），然后得到投影函数h（x）。

重点：其中，对于原来的第i类样本在特征空间F中的均值需要用核矩阵得到，同时使用核矩阵的内积作为原来的类内散度矩阵，那么就得到了对应的使用核函数之后的KLDA的目标函数，之后再使用类似于LDA的求解方法获得其中对应的a矩阵，进而得到h(x)。

（这其中选择的核函数为：映射fai(x)的内积。）