NLP学习笔记30-SVM 对偶、KTT，核函数

一序

本文属于贪心NLP训练营学习笔记系列。

二

Mapping Feature to High Dimensional Space

NLP学习笔记30-SVM 对偶、KTT，核函数

如图所示，转换是包含两部分的工作的，第一步是从低维特征向量转换为高维特征向量，第二步是根据高维向量特征训练分类器。

那么现在的任务也从原来的： $f(x)\to y$ 变成了 $f( \phi(x) ) \to y$ ,或者 f(u)=y

其中x是D维，u是 D^' 维。

至于具体升维操作，也就是把原来的特征做一些加减乘除，变成更多的特征。

$x=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \to u = \begin{pmatrix} x_1 \\ x_2 \\ x_1^2 \\ x_2^2 \end{pmatrix}$

这种方法在实操的时候有一个问题：时间复杂度增加。

例如原来的D=10，新的 D^' =10000,第一步时间复杂度的增加是1000倍。第二步也需要大量的时间。

解决这个问题的方法就是核函数（kernel trick），它的思想就是把上面的转换维度和构造分类器两个事情结合到一起。使得时间的复杂度没有明显的增加。

优化的技巧-拉格朗日: 等号条件处理

1无约束条件下的最优化问题
这种最优化问题比较简单，直接求导为0就可以得到。

2等式约束下的最优化问题

即除了目标函数之外，还有一些约束条件。通常这种最优化问题有两种方法

NLP学习笔记30-SVM 对偶、KTT，核函数

假设目标函数为 f(x) ，约束条件为 g_i(x) 。

关于为什么拉格朗日函数能写成 $min f(x)+ \lambda g(x)$ ,老师从几何角度去讲解：

NLP学习笔记30-SVM 对偶、KTT，核函数

最优解 x^* 有什么特点？就是这点上目标函数的梯度和直线的梯度是平行的, $\nabla f(x)|| \nabla g(x)$

基于这个特点，如果要变成相等就是要乘上一个系数 $\lambda$ :∇f(x)=λ∇g(x)，剩下就是公式位移变化，可得出带约束条件的对x偏导等于目标函数对x的偏导。

因此从几何上推导出来变形后的目标函数和原来带约束的目标函数是等价的。

3 多个条件multiple Equalities（泛化）

等式约束条件是有多个的。经过拉格朗日处理后：

$Minimize f(x)+\sum_{i=1}^{R}\lambda _ig_i(x)$

然后就是分别求偏导后等于0：

NLP学习笔记30-SVM 对偶、KTT，核函数

拉格朗日: 不等号条件处理

$minf(x) \\ st.h(x) \leq 0$

这里只有小于等于0的情况，因为即使是大于等于0的不等式也可以转换为《=0；

第1步：求出没有加限制条件的目标函数的最优解 x^*

第2步：验证 x^* 符合约束条件。此时 $\lambda =0,h(x) \leq 0$

2没有加限制条件的目标函数的最优解不满足约束条件

此时 NLP学习笔记30-SVM 对偶、KTT，核函数 $\lambda =0$ 起不到作用。那么最优解只能 h(x)=0

综合条件1、2，=》 $\lambda h(x)=0$

从几何上理解：见下面截图: f(x) 最优解应该 x^* ,但是不在 $h(x)\leq 0$ 范围内，最优解应该是绿色的 $x^{*'}$ ，对应 h(x)=0 线上。

NLP学习笔记30-SVM 对偶、KTT，核函数

KTT conditions

现在根据上面的结论，

$minf(x) \\st.g_i(x)=0 ;i=1,2,3,...,R \\ h_j(x) \leq 0;j=1,2,3,...,R^'$

我们可以写成： $minf(x)+\sum_{i=1}^{R}\lambda _i g_i(x)+ \sum_{j=1}^{ {R}'} \mu _jh_j(x)$

$st. \lambda _i,\mu _j \geq 0 \\ \mu _j h_j(x) =0 \ \forall j \\ h_j(x) \leq 0 \ \forall j$ 这三个约束称为 KKT条件。

KKT Condition of SVM

先回顾之前的SVM硬目标函数（不允许有误差）

$min\frac{1}{2}||w||^2 \\st. (w^T\cdot x_i+b)y_i-1\geq 0$

根据拉格朗日不等式的处理过程：

$Minimize \frac{1}{2}||w||^2+\sum_{i=1}^{n} \lambda_i [1-y_i(w^T\cdot x_i+b)]$

$st. \lambda _i \geq 0 \\\lambda_i [1-y_i(w^T\cdot x_i+b)] =0 \, \forall i \\1-y_i(w^T\cdot x_i+b) \leq 0$ 这就是SVM版本的KKT条件。

SVM由primal-form到dual-form

primal-form指的是用正常的逻辑思维进行构建的目标函数，那么为什么转换到dual-form（对偶的问题）

1、primal-form的问题比较难以解决因此转换到dual-form

2、在dual-form中可以看到一些有趣的insight。对于svm就是kernel trick。后面会讲（自己临时理解把特征空间从低维映射到高维从而线性可分，就是把非线性变成线性而且不增加计算量）。

kernel trick 不仅仅试用svm.还适合其他模型。

从dual-form求出的解，不一定能对应的primal-form，有时候不一样，Primal问题一般是全局解（optimal），Dual问题一般是子目标解（sub-optimal）。我们把全局解（optimal）和子目标解（sub-optimal）的差距叫gap，理想上gap是0。

SVM的dual-form

上面我们已经得到SVM的KKT表达式：

$Minimize \frac{1}{2}||w||^2+\sum_{i=1}^{n} \lambda_i [1-y_i(w^T\cdot x_i+b)]$

$st. \lambda _i \geq 0 \\\lambda_i [1-y_i(w^T\cdot x_i+b)] =0 \, \forall i \\1-y_i(w^T\cdot x_i+b) \leq 0$

分别对参数进行求偏导：

$\frac{\partial L}{\partial w} =0\to w+ \sum_{i=1}^{n} \lambda _i(-y_ix_i)=0\to w= \sum_{i=1}^{n} \lambda _i(y_ix_i)$

$\frac{\partial L}{\partial b} =0\to \sum_{i=1}^{n} \lambda _i(-y_i)=0\to \sum_{i=1}^{n} \lambda _i(y_i)=0$

代入目标函数，先看第一项：

$\frac{1}{2}||w||^2=\frac{1}{2}w^Tw=\frac{1}{2}(\sum_{i=1}^{n} \lambda _i(y_ix_i)) ^T(\sum_{j=1}^{n} \lambda _j(y_jx_j)) =\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda _i\lambda _jy_iy_jx_i^Tx_j$

第二项:

$\sum_{i=1}^{n} \lambda_i [1-y_i(w^T\cdot x_i+b)]=\sum_{i=1}^{n}\lambda_i -\sum_{i=1}^{n}\lambda_iy_i(w^T\cdot x_i+b ) \\=\sum_{i=1}^{n}\lambda_i -\sum_{i=1}^{n}\lambda_iy_i w^T\cdot x_i -\sum_{i=1}^{n}\lambda_iy_i b$

把 $\sum_{i=1}^{n} \lambda _i(y_i)=0$ ，以及w 代入。

= $\sum_{i=1}^{n}\lambda_i -\sum_{i=1}^{n}\lambda_iy_i (\sum_{i=1}^{n}\lambda_i x_iy_i )^T \cdot x_i =\sum_{i=1}^{n}\lambda_i-\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda _i\lambda _jy_iy_jx_i^Tx_j$

因此我们的公式就变成：

$\sum_{i=1}^{n}\lambda_i- \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda _i\lambda _jy_iy_jx_i^Tx_j$

$st. \: \forall i \ \lambda _i \geq 0 \\ \: \: \: \: \forall i \ \sum_{i=1}^{n} \lambda_iy_i =0 ,w=\sum_{i=1}^{n}\lambda _ix_iy_i \\ \forall i \ \lambda_i [1-y_i(w^T\cdot x_i+b)] =0$

这里只有 $\lambda$ 一个未知的参数，为什么要这样转换呢？

主要是因为在我们的目的让dual-from的公式中出现了 x_i^Tx_j ,我们就可以使用Kernel-Trick 核函数减少时间复杂度，甚至不增加复杂度。

接下来学习核函数的入门。

Kernel Trick

先回顾下之前将低维特征向量映射到高维特征向量会有什么问题，主要就是维度变大了，对应时间复杂度变大了。

下面截图的，用到了向量内积：两个向量a = [a1, a2,…, an]和b = [b1, b2,…, bn]的点积定义为： a·b=a1b1+a2b2+……+anbn

NLP学习笔记30-SVM 对偶、KTT，核函数

由上面的推导操作我们可以看到，虽然维度变成更高维的了，但是某些特定的操作（这里是计算内积）时间复杂度居然没有增加。

所以现在的任务就是怎么设计 $\phi(x) , \phi(z)$ ,使得 $O(\phi (x)^T\cdot \phi (z) )\approx O( x^Tz)$ ,这个 $\phi$ 就是SVM的Kernel trick。

k(x,y)=x^Ty

多项式核（Polynomial Kernel）:

k(x,y)=( 1+x^Ty)^d

高斯核（Gaussian Kernel）

$\LARGE k(x,y)=e^{(\frac{ -||x-y||^2}{2\sigma ^2})}$

关于如何设计核函数可以去搜索：mercer’s theorem 相关内容，这里比较复杂，老师没有展开讲。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/213717.html原文链接：https://javaforall.net

NLP学习笔记30-SVM 对偶、KTT，核函数

一序