开始Hard Margin svm的第二篇博文,本篇其实就是将一种代替QP的方法．$ $

相关知识

\[ \min\limits_{w} \quad f(w)\\ s.t. \quad h_{i}(w)=0,\quad i=1,2,\ldots,l. \]

好好学了高数的人都知道，可以使用拉格朗日乘数法,其实该方法是可以拓展到不等式的.首先，我们还是把最终需要优化的问题列出来

\[ \begin{align} &\min\limits_{w,b} \frac{1}{2}w^{T}w\\ 而且：\\ &y_{n}(w^{T}x_{n}+b)\geqslant1 \end{align} \]

公式推导

建于使用拉格朗日乘数法，做如下定义:

\[ \mathcal{L}(w,b,\alpha)=\frac{1}{2}||w||^{2}-\sum_{i=1}^{k}\alpha_{i}\begin{bmatrix} y^{(i)}(w^{T}x^{i}+b)-1 \end{bmatrix} \]

我们的问题就转换成\(\min \quad \mathcal{L}(w,b,\alpha)\)

接下来定义:

\[ \theta_{\mathcal{P}}(w,b,\alpha)=\max \limits_{\alpha_{i}\geq 0}\mathcal{L}(w,b,\alpha) \]

同时，很容易证明有：

\[ \theta_{\mathcal{P}}(w,b,\alpha)=\left\{\begin{matrix} \frac{1}{2}w^{T}w & \qquad \qquad if \quad y_{n}(w^{T}x_{n}+b)\geqslant1 \\ \infty & otherwise \end{matrix}\right. \]

那么我们的问题就变成:

\[ \begin{align} &p^{*}=\min\limits_{w,b} \max \limits_{\alpha_{i}\geq 0}\mathcal{L}(w,b,\alpha)\\ 而且：\\ &y_{n}(w^{T}x_{n}+b)\geqslant1 \end{align} \]

由于有如下的关系(仔细想一想):

\[ d^{*}=\max \limits_{\alpha_{i}\geq 0}\min\limits_{w,b} \mathcal{L}(w,b,\alpha)\leqslant\min\limits_{w,b} \max \limits_{\alpha_{i}\geq 0}\mathcal{L}(w,b,\alpha)=p^{*} \]

至于为什么要把右边的问题转换成左边的问题，那么肯定是因为其更好求解啦．不过现在的疑问是，满足什么约束条件，使得:

\[ d^{*}=p^{*} \]

结论就是著名的Karush-Kuthn-Tucker(KKT) conditions,首先声明，我下面写的KKT约束并不完整，只是针对该问题，更加详细的还是看Andrew Ng的推导．

\[ \begin{align} \frac{\partial }{\partial w_{i}}\mathcal{L}(w,b,\alpha)=0, &\quad i=1,\ldots n \\\\ \frac{\partial }{\partial b}\mathcal{L}(w,b,\alpha)=0,& \\\\ \alpha_{i}\begin{bmatrix} y^{(i)}(w^{T}x^{i}+b)-1 \end{bmatrix}=0, &\quad i=1,\ldots k\\\\ y^{(i)}(w^{T}x^{i}+b)-1\leq 0,&\quad i=1,\ldots k \\\\ \alpha_{i}\geq 0,&\quad i=1,\ldots k \end{align} \]

推导了了这么多，重新整理一下问题:

\[ \max \limits_{\alpha_{i}\geq 0}\min\limits_{w,b} \mathcal{L}(w,b,\alpha)\\ 而且:\\ 满足:KKT\quad conditions \]

接下来我们就要求出\[w,b\]:

\[ \begin{align} \nabla_{w}\mathcal{L}(w,b,\alpha)&=w-\sum_{i=1}^{m}\alpha_{i}y^{(i)}x^{(i)}=0\\ &\Downarrow\\ w&=\sum_{i=1}^{m}\alpha_{i}y^{(i)}x^{(i)}\\ \\ \frac{\partial }{\partial b}\mathcal{L}(w,b,\alpha)&=\sum_{i=1}^{m}a_{i}y^{(i)}=0 \end{align} \]

b的求解我这儿就不写了，大概就是将上面求得的结果带入原来的式子，然后求出来的．

\[ b=-\frac{\max_{i:y^{(i)=-1}}w^{T}x^{(i)}+\min_{i:y^{(i)=1}}w^{T}x^{(i)}}{2} \]

不过我想讲一下它形象的解释:最后的分类超平面到两类最近的点的距离是相等的.

最后那就是我们的超平面了，注意,我省了很多带入求解的过程

\[ \begin{align} w^{T}x+b&=(\sum_{i=1}^{m}\alpha_{i}y^{(i)}x^{(i)})^{T}x+b\\ &=\sum_{i=1}^{m}\alpha_{i}y^{(i)}<x^{(i)},x>+b \end{align} \]