SVM(上):SVM的优化目标及其对偶问题

/ 机器学习 / 没有评论 / 226浏览

线性分类器

我们知道,在logsitic regression中,我们用一条直线来进行分类: $$y=\omega^{T}x+b\tag{1.1}$$ 把测试样例带入(1)式,如果y>0则分类为1,如果y<0则分类为-1。

这里我们假设分类结果 \(y\in\{-1,1\}\),也就是分为两类{-1,1},而不是{0,1}两类,下同。

但是我们看如图的例子 在图中我们可以看到,有很多条直线都可以作为分类的边界,那么哪条直线分类是最好的呢?
直观上来看应该是离两边的点都尽量远的直线分类效果最好,因为这条直线能够把两类分的最清晰。
我们就把这种分类器叫做最优间隔分类器

最优间隔分类器

上面我们知道离两边的点都尽量远的直线分类效果最好,那么这个我们怎么定义距离或者叫间隔(margin)呢? 有两种间隔的定义:

几何间隔

几何间隔就可以理解为我们了解的欧式距离,我们知道在二维空间中,点 \((x,y)\) 到直线 \(ax+by+c=0\) 的距离公式是这样的:$$d=\frac{|ax+by+c|}{\sqrt{a^2+b^2}}\tag{2.1}$$ 而在多维空间中,点 \({x^{(i)}}\) 到直线 \(\omega^{T}x+b=0\) 的距离公式也是类似的:$$\gamma^{(i)}=\frac{|\omega^{T}x^{(i)}+b|}{|w|}\tag{2.2}$$ 证明:

过\(x\)做一条垂线与直线\(\omega^{T}x+b=0\)相交于点\(a\),那么向量\(\overrightarrow{ax}=x-a\)。
那么点x到直线的距离:$$\begin{equation}\begin{split} \|ax\|&=\frac{|\overrightarrow{ax}\cdot{\overrightarrow{\omega}}|}{\|\omega\|} =\frac{|{\omega}^{T}\cdot{(x-a)}|}{\|\omega\|}\\ &=\frac{|\omega^{T}x-\omega^{T}a|}{\|\omega\|} =\frac{|\omega^{T}x+b|}{\|\omega\|}\qquad\qquad(\omega^{T}a+b=0) \end{split}\end{equation} $$

函数间隔

给定一个训练样本\((x^{(i)},y^{(i)})\),这个点的函数间隔定义为: $$\hat{\gamma}^{(i)}=y^{(i)}(\omega^{T}x^{(i)}+b)\tag{2.3}$$ 由于 \(y\in\{-1,1\}\):

因此函数间隔永远为非负,即\(\hat{\gamma}^{(i)}=|\omega^{T}x^{(i)}+b|\)。这也是分类结果 \(y\in\{-1,1\}\) 而不是 \(y\in\{0,1\}\) 的一个优势。

观察函数间隔和几何间隔的表达式。有:

$$\gamma=\frac{\hat{\gamma}}{\|\omega\|}\tag{2.4}$$

优化目标

我们令\(\quad\gamma=min\gamma^{(i)},\hat{\gamma}=min\hat{\gamma}^{(i)}\)。那么我们要找到一个分类效果最好的直线,就是要找到一条直线使得所有的点到直线最小的几何间隔最大。

即找到$$max\quad \gamma$$ $$ s.t\qquad \frac{y^{(i)}(\omega^{T}x^{(i)}+b)}{\|\omega\|}\geq\gamma $$ 如果我们假设\(\hat{\gamma}=1\),根据式(2.4)那么就是要找到 $$max\quad\frac{1}{\|\omega\|}$$ $$ s.t\qquad y^{(i)}(\omega^{T}x^{(i)}+b)\geq1 $$ 也就是要找到

$$min\quad\frac{1}{2}{\|\omega\|}^{2}\tag{2.5}$$ $$s.t\qquad y^{(i)}(\omega^{T}x^{(i)}+b)\geq1$$

最后一个式子就是我们最优间隔分类器中常用的优化目标。
那怎么求解这个有约束的极值问题呢?有时候原问题很难求解,我们就把它转化为对偶问题,往往对偶问题相对比较容易求解。

对偶问题

拉格朗日乘子法

拉格朗日乘子法是用来求函数在有约束条件下的极值的一种方法,思想就是把有约束变成无约束的极值问题。 考虑如下的优化问题:$$min_\omega\quad f(\omega)$$ $$s.t.\quad h_i(\omega)=0,\quad i=1,...,l.$$ 我们可以转化为这样一个无约束优化问题(拉格朗日函数):$$\mathcal{L}(\omega,\beta)=f(\omega)+\sum_{i=1}^l\beta_{i}h_i(\omega)\tag{3.1}$$ 其中\(\beta_i\)就叫做拉格朗日乘子。 式(3.1)分别\(\mathcal{L}\)分别对\(\omega\),\(\beta_i\)求偏导数并置为0就可以求出\(\omega\)和\(\beta_i\)。

广义拉格朗日乘子法

回到最优间隔分类器的优化目标,即式(2.5)。这里约束条件是个不等式,不是上面拉格朗日乘子法中的等式约束。于是我们就把拉格朗日乘子法进行扩展。 我们把下面的优化目标,叫做主优化问题(primal optimization problem): $$min_\omega\quad f(\omega)\tag{3.2}$$ $$s.t. \quad g_i(\omega)\leq0,\quad i=1,...,k$$ $$ \qquad\quad h_i(\omega)=0,\quad i=1,...,l.$$ 为了解决这个问题,我们首先定义一个广义拉格朗日函数(generalized Lagrangian): $$\mathcal{L}(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_{i}g_i(\omega)+\sum_{i=1}^l\beta_{i}h_i(\omega)\tag{3.3}$$ 在这个函数里,\(\alpha_i\)和\(\beta_i\)都是拉格朗日乘子
把主优化问题转化为拉格朗日函数,我们可以就把有约束条件的优化问题转化为无约束的优化问题,只是多了2个未知参数\(\alpha_i\)和\(\beta_i\)。 考虑$$\theta_p(\omega)=\mathop{max}\limits_{\alpha_i,\beta_i:\alpha_i\geq0}\mathcal{L}(\omega,\alpha,\beta)\tag{3.4}$$ 如果(3.4)不满足(3.2)中的任何一个约束条件:

如果满足了(3.2)中的约束条件,由于\(\sum_{i=1}^k\alpha_{i}g_i(\omega)\leq0\),同时\(\sum_{i=1}^l\beta_{i}h_i(\omega)=0\), 因此\(\theta_p(\omega)=f(\omega)\)。 综上: $$\theta_p(\omega)= \begin{cases} f(\omega)&\text{满足限制条件}\\ +\infty&\text{不满足限制条件} \end{cases}$$ 因此原优化问题转化为$$\mathop{min}\limits_{\omega}\theta_p(\omega)$$ 即$$\mathop{min}\limits_{\omega}\mathop{max}\limits_{\alpha_i,\beta_i:\alpha_i\geq0}\mathcal{L}(\omega,\alpha,\beta)$$

对偶问题

我们令\(\theta_D(\alpha,\beta)=\mathop{min}\limits_{\omega}\mathcal{L}{(\omega,\alpha,\beta)}\) 则原优化问题的对偶优化问题为:$$\mathop{max}\limits_{\alpha,\beta:\alpha \geq0}\ \mathop{min}\limits_{\omega}\mathcal{L}{(\omega,\alpha,\beta)}= \mathop{max}\limits_{\alpha,\beta:\alpha \geq0}\theta_D(\alpha,\beta)$$ 令主优化问题的最优解为\(p^\star\),对偶问题的最优解为\(d^\star\)。
由于一个函数的最大值的最小值要大于等于该函数的最小值的最大值,因此有: $$d^\star=\mathop{max}\limits_{\alpha,\beta:\alpha \geq0}\ \mathop{min}\limits_{\omega}\mathcal{L}{(\omega,\alpha,\beta)}\leq\mathop{min}\limits_{\omega}\mathop{max}\limits_{\alpha_i,\beta_i:\alpha_i\geq0}\mathcal{L}(\omega,\alpha,\beta)=p^\star$$

假设:在原问题中,\(f\) 和\(g_i\)都是凸函数,\(h_i\)是仿射函数。并且\(\ \exists \omega,for\ \forall i,\ g_i(\omega)<0\)

如果满足以上的条件,那么一定存在\(\omega^\star\),\(\alpha^\star\),\(\beta^\star\)。使得\(p^\star=d^\star=\mathcal{L}(\omega^\star,\alpha^\star,\beta^\star)\),即满足强对偶性
而且\(\omega^\star\),\(\alpha^\star\),\(\beta^\star\)满足以下的Karush-Kuhn-Tucker(KKT)条件: $$\begin{align}\frac{\partial}{\partial\omega_i}\mathcal{L}(\omega^\star,\alpha^\star,\beta^\star)\ &=\ 0,\ i=1,...,n\\ \frac{\partial}{\partial\beta_i}\mathcal{L}(\omega^\star,\alpha^\star,\beta^\star)\ &=\ 0,\ i=1,...,l\\ \alpha_i^\star g_i(\omega^\star)\ &= \ 0,\ i=1,...,k\\ g_i(\omega^\star)\ &\leq \ 0,\ i=1,...,k\\ \alpha^\star\ &\geq \ 0,\ i=1,...,k\end{align}$$

最优间隔分类器的优化问题

利用广义拉格朗日乘子法,我们就可以把最优间隔分类器的优化目标(2.5)转化为拉格朗日函数: $$\mathcal{L}(\omega,b,\alpha)=\frac{1}{2}\omega^{T}\omega+\sum_{i=1}^{m}\alpha_i(1-{y^{(i)}(\omega^{T}x^{(i)}+b)})\tag{3.5}$$ 根据广义拉格朗日乘子法中的讨论,主优化问题\(\ min\ \frac{1}{2}\omega^{T}\omega\ (s.t.\ ...)\ =\ min\ max\ \mathcal{L}\)。
接下来我们求该问题的对偶问题,即\(\ \mathop{max}\limits_{\alpha}\ \mathop{min}\limits_{\omega,b}\ \mathcal{L}\)。首先需要求得\(\ \mathop{arg\ min}\limits_{\omega,b}\mathcal{L}(\omega,b,\alpha)\),我们把\(\mathcal{L}(\omega,b,\alpha)\)分别对\(\omega,b\)求偏导并置为0。 $$\frac{\partial\mathcal{L}}{\partial\omega}=\omega-\sum_{i=1}^m\alpha_i y^{(i)} x^{(i)}=0\tag{3.6}$$ $$\frac{\partial\mathcal{L}}{\partial b}=\sum_{i=1}^m\alpha_i y^{(i)}=0\tag{3.7}$$ 上面我们通过求导求得\(\mathcal{L}\)对于\(\omega\)和\(b\)的最小值,因此把式(3.6),(3.7)代入式(3.5)中化简可以得到主优化问题的对偶问题: $$max\ \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i \alpha_j y^{(i)} y^{(j)} (x^{(i)})^{T}x^{(j)}\tag{3.8}$$ $$s.t.\qquad \sum_{i=1}^m \alpha_i y^{(i)}=0,\ \alpha_i\geq0 $$

核函数