机器学习核方法

核方法

拉格朗日乘子法

参考：【整理】深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件

参考：拉格朗日乘子法和KKT条件

在求解最优化问题中，拉格朗日乘子法和KKT条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，有不等约束时使用KKT条件。

最优化问题的三种情况：(1)无约束条件 (2) 等式约束条件 (3) 不等式约束条件

等式约束条件

\[\begin{cases}min_x\quad f(x)\\s.t.\quad h(x)=0\end{cases}
\]

只有到等高线与目标函数的曲线相切的时候，可能取得最优值
对约束函数 $h(x)$ 也求梯度 $\bigtriangledown h(x)$，想让目标函数 $f(x)$ 的等高线和约束函数相切，则他们切点的梯度一定在一条直线上。
- 也即最优化解的时候 $\bigtriangledown_x f(x) = \lambda \bigtriangledown_x h(x)$
求解最优化问题转换为

\[\begin{cases}\bigtriangledown_x f(x) = \lambda \bigtriangledown_x h(x)\\ h(x)=0\end{cases}
\]
构造拉格朗日函数：$L(x,\lambda) = f(x)+\lambda h(x) $。
- $\bigtriangledown_x L(x^*,\lambda^*) =0$ 对应 $\bigtriangledown_x f(x) = \lambda \bigtriangledown_x h(x)$
- $\bigtriangledown_{\lambda} L(x^*,\lambda^*) =0$ 对应 $h(x)=0$
多个约束条件：$L(x,\lambda) = f(x)+\sum_{k=1}^l\lambda_kh_k(x)$
- 再联立方程组
  
  \[\begin{cases}\frac{\partial L}{\partial x_i}=0\\\frac{\partial L}{\partial \lambda_k}=0\end{cases}
  \]
- 得到的解为可能极值点

不等式约束条件

KKT条件：在满足一些有规则的条件下，一个非线性规划问题能有最优化解法的一个必要和充分条件

不等式约束条件的约束是一个可行域，约束情况有两种：(1) 极小值点在可行域内 ( 不包含边界 ) (2) 极小值点落在可行域外 (包括边界)

极小值点在可行域内时，约束不起作用，之间目标函数 $f(x)$ 梯度等于0求解
极小值点在可行域外，约束起作用，走到极小值点时，约束函数梯度和目标函数负梯度相同$-\bigtriangledown f(x) = \lambda \bigtriangledown h(x)\quad (\lambda>0)$

构造拉格朗日函数转换求解问题，对于不等式约束的优化，需要满足三个条件，满足三个条件的解 $x^*$ 就是极小值点，这三个条件就是著名的KKT条件，整合了上面两种情况的条件。

考虑凸函数的最优化问题

\[min\quad f(x)\quad s.t. \quad h(x) \le0
\]

定义拉格朗日函数为

\[L(x,\lambda) = f(x)+\lambda h(x)
\]

那么 $x^*$ 是极小值点且有唯一 $\lambda ^*$ 使得

$\bigtriangledown_x L(x^*,\lambda^*) =0$
$\lambda^* \ge 0$
$\lambda^* h(x^*)= 0$

凸优化问题中，KKT条件就是全局最小值的充要条件，若不是凸优化，KKT条件是极小值点的必要条件，KKT点是驻点，可能是极值点。极值点一定满足KKT条件，但满足KKT条件的点不一定是极值点。

非凸优化问题，需加一个正定条件，使得KKT条件成为充要条件。

$\bigtriangledown_x L(x^*,\lambda^*) =0$
$\lambda^* \ge 0$
$\lambda^* h(x^*)= 0$
$h(x^*)\le0$
$\bigtriangledown_{xx} L(x^*,\lambda^*) 组成的海塞矩阵是正定的$

最大间隔(margin maximization)

问题描述

对于线性函数分类成两类的数据，定义超平面上的点为一类，平面下的点为一类。记超平面为 $\theta^Tx+b=0$，平面上的区域为 $\theta^Tx+b>0$，平面下的区域为 $\theta^Tx+b<0$。

存在不只一个超平面可以正确分类所给数据，选择哪个是最好的。需要一个超平面来最大化类别间距。

前序

给定一个线性函数 $y=2x+3$，有点 (0,3) 和 ($-\frac{3}{2}$,0) 在函数上，将 $y=2x+3$ 变形为 $2x-y+3=0$，写成向量形式

\[(2,-1)\left[\begin{matrix}x\\y\end{matrix}\right]+3=0
\]

进一步记作

\[(2,-1)\left[\begin{matrix}x_1\\x_2\end{matrix}\right]+3=0
\]

构造成 $\theta^T x+\theta_0=0$ 的形式，其中 $\theta^T$ 的方向垂直于函数斜率方向，等于函数法线方向。

SVM 最大分类问题

选择什么样的 $w$ 和 $b$，使得 $wx+b=0$ 将数据集分类最大化，间距最大。记数据集为 $D=\{(x^{(1)},y^{(1)}),...,(x^{(N)},y^{(N)})\}$，其中 $x \in R^n$，$y \in \{-1,+1\}$，给定 $x^{(i)}$则

\[w^T x^{(i)}+b>0\quad if\quad y^{(i)}=1 \\w^T x^{(i)}+b<0 \quad if \quad y^{(i)}=-1
\]

重新缩放数据，对于在边界 $w^Tx+b=1$ 上或边界之内的，以及在边界 $w^Tx+b=-1$ 上或边界之内的。所有数重写等式为

\[y_i(w^Tx_i+b)\ge 1
\]

计算间距

定义一个点 $x_1$ 在边界 $wx+b=-1$ 上，另一个类中距离 $x_1$ 最近的点 $x_2$ 在边界 $wx+b=1$ 上，，且 $x_2=x_1+\lambda w$

$\lambda$ 是大于0的常数
$w$ 是垂直于 $wx+b=0$ 的向量

则 $margin$ 为 $||x_2-x_1||=||\lambda w||=\lambda||w||$

\[w x_2+b=1\Rightarrow w(x_1+\lambda w)+b=1\Rightarrow wx_1+\lambda w^Tw+b=1
\]

又 $wx_1+b=-1$

则 $ \lambda w^Tw =2 \Rightarrow \lambda=\frac{2}{||w||^2}$

所以 $margin$ 为 $||x_2-x_1||=\lambda||w||=\frac{2}{||w||^2}\cdot ||w||=\frac{2}{||w||}$

问题转化

寻找最大间距的边界问题转化为带不等式约束的优化问题

\[\begin{cases}max_w \frac{2}{||w||}\\s.t.\quad y_i(wx_i+b)\ge 1\end{cases}
\]

写成拉格朗日乘子法适用类型

\[\begin{cases}min_w \frac{1}{2}||w||^2\\s.t.\quad 1-y_i(wx_i+b)\le 0\end{cases}
\]

因为 $L-2norm$ 求导时方便

\[L(w,\lambda)=\frac{1}{2}||w||^2+\alpha_i[1-y_i(wx_i+b)]
\]

SVM 软间隔

参考：《SVM笔记系列之五》软间隔线性支持向量机

机器学习核方法

拉格朗日对偶问题

引子

eg：拉格朗日函数 $L(x,\lambda)=x^2+\lambda(b-x)$

\[\frac{\partial L}{\partial x}=2x-\lambda=0\quad \Rightarrow \quad x^*=\frac{\lambda}{2}\\\frac{\partial L}{\partial \lambda}=b-x=0\quad \Rightarrow \quad x=b \quad \Rightarrow \quad \frac{\lambda}{2}=b\quad \Rightarrow \quad \lambda^*=2b
\]

又 $\lambda\ge 0$，则 $\lambda^*=max(0,2b)$

则拉格朗日函数写成

\[max_{\lambda}min_x(x^2+\lambda(b-x))
\]

正文

求解最大间隔问题中的拉格朗日函数

\[L(w,\lambda)=\frac{1}{2}||w||^2+\alpha_i[1-y_i(wx_i+b)]
\]

写成

\[L=min_{w,b}max_{\alpha_i} \frac{1}{2}||w||^2+\sum_{\alpha_i}\alpha_i[1-y_i(wx_i+b)]
\]

则其对偶问题为

\[L=max_{\alpha_i}min_{w,b} \frac{1}{2}||w||^2+\sum_{\alpha_i}\alpha_i[1-y_i(wx_i+b)]
\]

我们先求对偶问题 $min_{w,b} \frac{1}{2}||w||^2+\sum_{\alpha_i}\alpha_i[1-y_i(wx_i+b)]$，根据KKT条件

$\frac{\partial L}{\partial w}=0 \quad \Rightarrow \quad w-\sum_i\alpha_iy^{(i)}x^{(i)}=0\quad \Rightarrow \quad w=\sum_i\alpha_iy^{(i)}x^{(i)}$

$\frac{\partial L}{\partial b}=0\quad \Rightarrow \quad \sum_i\alpha_iy^{(i)}=0$
则可使用 $\alpha$ 替换 $w$ 和 $b$

\[L=\frac{1}{2} (\sum_i\alpha_iy^{(i)}x^{(i)})^T\sum_i\alpha_iy^{(i)}x^{(i)}+\sum_{\alpha_i}\alpha_i[1-y^{(i)}(\sum_j\alpha_jy^{(j)}x^{(j)}x^{(i)}+b)]\\=\frac{1}{2}(\sum_i\alpha_iy^{(i)}x^{(i)})(\sum_j\alpha_jy^{(j)}x^{(j)})+\sum_{\alpha_i}\alpha_i[1-y^{(i)}(\sum_j\alpha_jy^{(j)}x^{(j)}x^{(i)}+b)]\\=\frac{1}{2}(\sum_i\sum_j\alpha_iy^{(i)}x^{(i)}\alpha_jy^{(j)}x^{(j)})+\sum_i \alpha_i-\sum_i\sum_j \alpha^{(i)} \alpha^{(j)}y^{(i)}y^{(j)}x^{(i)}x^{(j)}+b\sum_i\alpha^{(i)}y^{(i)}\\=\sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j\alpha_iy^{(i)}x^{(i)}\alpha_jy^{(j)}x^{(j)}+b\sum_i\alpha^{(i)}y^{(i)}
\]

因为 $\sum_i\alpha_iy^{(i)}=0$，所以

\[L=\sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j\alpha_iy^{(i)}x^{(i)}\alpha_jy^{(j)}x^{(j)}\quad (i,j=1,2,...,N)\\s.t. \quad \alpha \ge 0 ,\quad \sum_i\alpha_iy^{(i)}=0
\]

所以问题转化为

\[L=max_{\alpha_i}(\sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j\alpha_iy^{(i)}x^{(i)}\alpha_jy^{(j)}x^{(j)}\quad (i,j=1,2,...,N)\\s.t. \quad \alpha \ge 0 ,\quad \sum_i\alpha_iy^{(i)}=0)
\]

支持向量

原始拉格朗日函数 $L(w,\lambda)=\frac{1}{2}||w||^2+\alpha_i[1-y_i(wx_i+b)]$，如果判对了 $y_i(wx_i+b)>1$ ，则 $[1-y_i(wx_i+b)]<0$ 。目的是使得 $L$ 最大，则 $\alpha=0$，如果数据远离边界被正确分类，那么权重 $\alpha=0$，如果数据在边界上，$[1-y_i(wx_i+b)]=0$，那就变成等式优化，$\alpha >0$。也就是说在边界上的点$\alpha >0$，对优化很重要。边界上的点叫 $support\quad vector$。

$SVM$ 是一个线性优化，做的事情是使得边界最大，边界上的点叫 $support\quad vector$，其他的点权重置零。