《大话设计模式》——工厂方法模式

【机器学习】算法原理详细推导与实现(四):支持向量机(上)

在之前的文章中，包括线性回归和逻辑回归，都是以线性分界线进行分割划分种类的。而本次介绍一种很强的分类器【支持向量机】，它适用于线性和非线性分界线的分类方法。

函数间隔概念

为了更好的理解非线性分界线，区别两种分界线对于分类的直观理解，第一种直观理解需要考虑 logistic 回归，我们用一个 logistic 回归函数表示当 $y=1$ 时概率表示为：

\[ \begin{split} p(y=1|x;\theta)&=h(\theta) \\ &=g({\theta}^Tx) \\ &=g(z) \\ \end{split} \]

当 $h(\theta) \geq 0.5$ 时，即${\theta}^Tx \geq 0$ 时 $y=1$；同理当 $h(\theta) < 0.5$ 时，即${\theta}^Tx < 0$ 时 $y=0$。回顾 logistic 回归的图像如下所示：

【机器学习】算法原理详细推导与实现(四):支持向量机(上)

由上图可以看出：如果 ${\theta}^Tx >> 0$ 时，那么可以相当确定的预测$y=1$；如果 ${\theta}^Tx << 0$ 时，那么可以相当确定的预测$y=0$

当我们根据这样的样本拟合logistic 回归得出分类器时，这样的分类器是良好的。即对于所有的 $i$ ，如果 $y^{(i)}=1$，那么 ${\theta}^Tx^{(i)} >> 0$ ；如果 $y^{(i)}=0$，那么 ${\theta}^Tx^{(i)} << 0$ 。换句话说，如果我们根据训练集找到了合适的参数 $\theta$ ，那么我们的学习算法不仅会保证分类结果正确，更会进一步的保证对分类结果的 确定性。

假设训练集都是线性可分隔的，即一定有一条直线可以将训练集分开，假设${\theta}^Tx^{(i)} =0$ 代表中间那条分隔线，使得正样本和负样本到这条线的距离最大，即这条线是最优的分隔线：

【机器学习】算法原理详细推导与实现(四):支持向量机(上)

考虑上面3个点 A 、B和C。从图中我们可以确定A是×类别的，然而C我们是不太确定的，B还算能够确定。logistic 回归强调所有的点尽可能的远离中间那条线即可，由此可能造成如上所示，点C可能属于o类别也可能属于×类别，所以我们这里希望找到一个分隔线，使其所有的分类结果有足够的 确定性，这就是logistic 回归和支持向量机的不同点。

间隔器

函数间隔

支持向量机的符号和logistic 回归的符号有点差别。支持向量机的取值范围是 $y \in \{-1, 1\}$，而logistic 回归的取值范围是 $y \in \{0, 1\}$

logistic 回归的假设函数为：

\[ \begin{split} h(x)&=\theta_0x_0+\theta_1x_1+\theta_2x_2+…+\theta_nx_n \\ &=\theta^Tx \end{split} \]

其中这里假设 $x_0=1$。而支持向量机假设 $\theta_0=b$，即假设函数为：

\[ \begin{split} h(x)&=\theta_0+\theta_1x_1+\theta_2x_2+…+\theta_nx_n \\ &=b+\omega_1x_1+\omega_2x_2+…+\omega_nx_n \\ &=\omega^Tx+b \end{split} \]

即为：

\[ h_{w,b}(x)=g(\omega^Tx+b) \]

将其假设函数映射到 $y \in \{-1, 1\}$ 上：

\[ g(z)= \begin{cases} 1, & \text{z $\geq$ 0} \\ -1, & \text{z<0} \end{cases} \]

给定一个训练样本 $(x^{(i)}, y^{(i)})$，那么定义支持向量机的间隔函数为：

\[ \hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b) \]

对于这个式子的理解是:

如果 $y^{(i)}=1$，为了获得较大的函数间隔，你需要令$(\omega^Tx+b)$ 取得较大值，即$(\omega^Tx+b) >> 0$，得到的$\hat{\gamma}^{(i)}$是一个大正数
如果 $y^{(i)}=-1$，为了获得较大的函数间隔，那么唯一使其获得较大值的方式是，令$(\omega^Tx+b) << 0$ ，得到的$\hat{\gamma}^{(i)}$是一个大负数

这个定义捕捉到了我们之前对于函数间隔的直观理解的特点，在之前logistic 回归的直观理解中，如果$y^{(i)}=1$，我们希望$(\omega^Tx+b)$取较大的值；如果$y^{(i)}=-1$，我们希望$(\omega^Tx+b)$取较小的值，这个定义用一个公式捕捉到了，我们希望函数间隔去较大值的两种情况。

上面定义的某一个样本的函数间隔为：$\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$，那么针对全局样本得到的一个超平面的函数间隔定义为：

\[ \hat{\gamma}=min\hat{\gamma}^{(i)},(i=1,2,…,m) \]

代表在全部的训练样本上，以分类正例和负例置信度最低的那个函数间隔为准，即 函数间隔是最差的情况，也要能很好的分类正负 。

实际上，这种直观理解存在一个小问题，要使函数间隔取较大的值是非常容易的，比如说：如果我们的参数是$\omega$和$b$，那么我们可以将$\omega$变为原来的2倍，将$b$也变为原来的2倍：

\[ \omega \to 2\omega，b \to 2b \]

那么根据函数间隔的定义：

\[ \hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b) \]

如果把$\omega$和$b$变为原来的2倍，那么我可以很容易的使函数间隔加倍。所以单纯的以最大化函数间隔为目标是没有多大意义的，因为通过对参数翻倍就可以使函数间隔获得任意大的值，也许我们可以解决这个问题。通过添加一个正规化条件，使得$\omega$的长度为1，即$||\omega||=1$

几何间隔

分类器的确定边界会由平面给出，假设存在一个$B$点在分割面上，其他任何一点，比如$A$点到分割面的距离，这就是几何间隔

【机器学习】算法原理详细推导与实现(四):支持向量机(上)

那么上图的$A$点和分割面成$90°$夹角，即法向量表示为$\frac{\omega}{||\omega||}$，$A$点到分割面的距离为${\gamma}$（没有帽子的是几何间隔，有帽子的是函数间隔$\hat{\gamma}$），假设$A$点的坐标为$(x^{(i)},y^{(i)})$，$B$点的坐标为(x,y)，那么可以得到$x=x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||}$(利用初中的几何知识)，因为$\frac{\omega}{||\omega||}$是长度为1且与超平面垂直的单位向量，用点$x^{(i)}$减掉${\gamma}^{(i)}\frac{\omega}{||\omega||}$就是超平面上面点$B$的$x$坐标了。因为分割面上面的点都满足$\omega^Tx+b=0$，而点B在分割面上，所以也满足$\omega^Tx+b=0$，，即：

\[ \omega^T(x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||})+b=0 \]

进一步化简得到：

\[ {\gamma}^{(i)}=\frac{\omega^Tx^{(i)}+b}{||\omega||}=(\frac{\omega}{||\omega||})^Tx^{(i)}+\frac{b}{||\omega||} \]

上述是假设已经对样本分好了正确的类别，那么如果点$A$是样本，即很多个类似于点$A$的样本$(x^{(i)},y^{(i)})$，那么上述公式转化为：

\[ {\gamma}^{(i)}=y^{(i)}((\frac{\omega}{||\omega||})^Tx^{(i)}+\frac{b}{||\omega||}) \]

现在这样子的形式和之前的函数间隔形式非常相似，除了在这里我们对向量$\omega$进行了标准化。所以像之前一样，我们希望几何间隔取较大的值，也就是意味着如果我们对训练样本进行了正确的分类，那么这些样本在分类正确的一面距离分割面的距离越大越好，这里用乘上$y^{(i)}$来判断样本正负分类的方向。

这里有几个非常容易得到的结论：

如果$||\omega||=1$，那么函数间隔等于几何间隔

几何间隔=函数间隔 / $||\omega||$

同样，如果同时扩大 $\omega$ 和 $b$，那么$||\omega||$也会相应的扩大，结果无影响。所以针对全局样本得到的一个超平面的函数间隔定义为：

\[ \gamma=min \gamma ^{(i)},(i=1,2,…,m) \]

最优间隔分类器

最优间隔分类器是指选择合适的$\gamma$、$\omega$、$b$，使得间隔最大，也就是说满足函数：

\[ max_{\gamma,\omega,b}->\gamma \]

\[ y^{(i)}(\omega^Tx+b) \geq \gamma,(||\omega||=1) \]

虑几何间隔和函数间隔的关系，即$\gamma=\frac{\hat{\gamma}}{||\omega||}$，那么上面可以转化为：

\[ max_{\gamma,\omega,b}->\frac{\hat{\gamma}}{||\omega||} \]

\[ y^{(i)}(\omega^Tx+b) \geq \hat{\gamma} \]

这样子就取消了$||\omega||=1$的约束了，但是目标函数目前不是凸函数，无法求得最优值，没发直接带入优化算法里面去计算，所以这里还是需要改写一下。前面说到同时扩大$\omega$和$b$对结果没有影响，但我们最后要求的仍然是$\omega$和$b$的确定值，不是他们的一组倍数值，因此，我们需要对$\hat{\gamma}$做一些限制，以保证我们解是唯一的。这里为了简便取$\hat{\gamma}=1$，这样的意义是将全局的函数间隔定义为 1 ，也即是将离超平面最近的点的距离定义为$\frac{1}{||\omega||}$。这里解释一下为什么这么定义，因为求解$\frac{1}{||\omega||}$的最大值相当于求$\frac{1}{2}||\omega||^2$的最小值，因此改写的结果为：

\[ min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2 \]

\[ y^{(i)}(\omega^Tx+b) \geq 1 \]

这下定义变成只有线性约束了，而且是个典型的二次规划问题（目标函数是自变量的二次函数），利用算法可以轻松求解。

拉格朗日对偶

含有等式约束形式的求解最值

这里需要用到微积分知识中的拉格朗日乘子法，它可以用来求解像这样的优化问题，例如在满足一定数量的约束条件的前提下，求解最小化、最大化问题，在这里先简要的介绍一下它的一种一般化的形式。拉格朗日乘子法是这样的：假设有一个函数$f(\omega)$，你想使他最大化或者最小化，与此同时需要满足一些约束条件：

\[ min_{\omega}->f(\omega) \]

对于每个 $i$，必须保证约束函数的值为0：

\[ h_i(\omega)=0,i=1,2,…,l \]

给定这些约束，我可以写成向量的形式，将整个向量表示成$h(\omega)$：

\[ \begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ … \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0} \]

上面表示所有的元素都是 $0$ 向量。如果像求解这个最优化问题，利用拉格朗日乘子法，首先应该创建一个拉格朗日算子：

\[ \Gamma(\omega,\beta)=f(\omega)+\sum_{i=1}^l\beta_ih_i(\omega) \]

它应该等于原始的目标函数加上这些限制函数的线性组合，这些参数$\beta_i$被称为拉格朗日算子，然后解决这个问题的方法是，对每一个原始值求偏导之后将其设为0：

\[ \frac{\partial_{\Gamma}}{\partial_{\omega_i}}=0;\frac{\partial_{\Gamma}}{\partial_{\beta_i}}=0 \]

分别对$\omega$和$\beta$求偏导，使其偏导数等于0，理论上可以解出一个$w^*$最优解，是这个最优解的必要条件是：存在$\beta^*$使得这些偏导数的值为0。所以根据这个结论，求解的过程是：

用拉格朗日乘子法创建一个拉格朗日算子

之后相对于原始参数$\omega$和拉格朗日算子$\beta$求偏导数，并令偏导数等于0

之后对方程组进行求解，最后检查下得到的解是否确实为一个最小值

至于为什么引入拉格朗日乘子法可以求出极值，原因是$f(\omega)$的$d_{\omega}$变化方向受其他不等式的约束，$d_{\omega}$的变化方向与$f(\omega)$的梯度垂直时才能获得极值，而且在极值处，$f(\omega)$的梯度与其他等式梯度的线性组合平行，因此他们之间存在线性关系。(kkt条件)

含不等式约束形式的求解最值

然后我们探讨有不等式约束的极值问题求法，假设不仅仅存在约束条件$h_i(\omega)=0$，还存在约束条件$g_i(\omega)\leq 0$，问题如下所示：

\[ min_{\omega}->f(\omega) \]

对于每个 $i$，必须保证约束函数$h(\omega)$的值为0：

\[ h_i(\omega)=0,i=1,2,…,l \]

对于每个 $i$，必须保证约束函数$g(\omega)$的值小于等于0：

\[ g_i(\omega)\leq 0,i=1,2,…,k \]

给定这些约束，我可以写成向量的形式，可以用向量表示成：

\[ \begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ … \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0} \]

\[ \begin{bmatrix} g_1(\omega) \\ g_2(\omega) \\ … \\ g_k(\omega) \\ \end{bmatrix} \leq \overrightarrow{0} \]

在这种情况下，既有等式约束条件也有不等式约束条件，那么利用拉格朗日乘子法，首先应该创建两个拉格朗日算子：

\[ \Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega) \]

这里的$\alpha_i$和$\beta_i$都是拉格朗日算子。如果按这个公式和之前的方法求解，即求解最小值$min f(\omega)$会出现问题。因为我们求解的是最小值，而这里的$g_i(\omega) \leq 0$，我们可以将$\alpha_i$调整成很大的正值，来使最后的函数结果是负无穷。因此我们需要排除这种情况，即需要定义下面的函数：

\[ \theta_P(\omega)=max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta) \]

以上公式，假设$g_i(\omega) \geq 0$或者$h_i(\omega) \neq 0$，那么可以调整参数$\alpha_i$和$\beta_i$使得$\theta_P(\omega)$的最大值为正无穷。

分布式事务

但是当$g_i(\omega)$和$h_i(\omega)$满足约束条件$g_i(\omega)\leq 0$和$h_i(\omega)=0$时，$\theta_p(\omega)$的最大值为$f(\omega)$。所以上面式子可知，当$g_i(\omega) \geq 0,h_i(\omega) \neq 0$时$\theta_P(\omega)=\infty$，当$g_i(\omega)\leq 0,h_i(\omega)=0$时$\theta_P(\omega)=f(\omega)$：

\[ \theta_P(\omega)= \begin{cases} f(\omega), & g_i(\omega)\leq 0,h_i(\omega)=0 \\ \infty, & g_i(\omega) \geq 0,h_i(\omega) \neq 0 \end{cases} \]

这样原来要求的$min f(\omega)$可以转换成求$min \theta_P(\omega)$，因为$\theta_P(\omega)$的最小值为$f(\omega)$，$f(\omega)$越小则$\theta_P(\omega)$越小，即求$min f(\omega)$等于求$min \theta_P(\omega)$：

\[ min_{\omega} \theta_P(\omega)=min_{\omega} max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta) \]

拉格朗日对偶步骤

下面使用$p^*$来表示$min_{\omega} \theta_P(\omega)$，如果直接求解，首先面对的是两个参数$\alpha,\beta$，这个过程不容易求解。因此这里引入拉格朗日对偶，即函数$\theta_P$的对偶函数$\theta_D$，它是一个以$\alpha$和$\beta$为变量的函数：

\[ \theta_D(\alpha,\beta)=min_{\omega} \Gamma(\omega,\alpha,\beta) \]

由求解$\theta_P(\omega)$的最小值$min_{\omega} \theta_P(\omega)$的推理步骤可知，$\theta_D(\alpha,\beta)$求解最大值的函数为

\[ max_{(\alpha,\beta:\alpha_i \geq 0)} \theta_D(\alpha,\beta)=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta) \]

这个问题是原问题的对偶问题，相对于原问题只是更换了$max$和$min$的顺序，而一般更换$max$和$min$顺序总有如下式子成立：

\[ max (min(x)) \leq min (max(x)) \]

所以有：

\[ d^* \leq p^* \]

\[ d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} (min_{\omega} \Gamma(\omega,\alpha,\beta)) \leq min_{\omega} (max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta))=p^* \]

下面会解释在什么条件下两者会相等$d^*=p^*$。

假设$f(\omega)$和$g_i(\omega)$都是凸函数，$h_i(\omega)=\alpha_i^T\omega+b_i$，并且存在$\omega$使得所有的$i$都有$g_i(\omega)<0$。在这种假设下，一定存在$\omega^*,\alpha^*,\beta^*$使得$\omega^*$是原问题$p^*$的解，$\alpha^*,\beta^*$是对偶问题$d^*$的解，以及$d^*=p^*=\Gamma(\omega^*,\alpha^*,\beta^*)$，这时$\omega^*,\alpha^*,\beta^*$满足kkt条件：

\[ \frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\omega_i}}=0,i=1,2,…,n \]

\[ \frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\beta_i}}=0,i=1,2,…,l \]

\[ \alpha_i^*g_i(\omega^*)=0,i=1,2,…,k \]

\[ g_i(\omega^*) \leq 0,i=1,2,…,k \]

\[ \alpha^* \geq 0,i=1,2,…,k \]

如果$\omega^*,\alpha^*,\beta^*$满足了kkt条件，那么他们就是原问题和对偶问题的解。而$\alpha_i^*g_i(\omega^*)=0,i=1,2,…,k$被称作是kkt条件，这个条件隐含了如果$\alpha^*>0$，那么$g_i(\omega^*)=0$。也就是说，$g_i(\omega^*)=0$时，$\omega$处于边界上，而当$\alpha^*=0$时，其$g_i(\omega^*) \leq 0$，即$\omega$不在边界上在可行域内。

最优函数间隔器

重新回到 svm 的优化问题，在上面我们需要优化的问题是：

\[ min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2 \]

\[ y^{(i)}(\omega^Tx^{(i)}+b) \geq 1 ,i=1,2,…,m \]

这里将约束条件改成：

\[ g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1 \leq 0 ,i=1,2,…,m \]

而kkt条件可知，如果$\alpha_i > 0$就一定意味着$g_i(\omega,b)=0$(因为 $\alpha_i^*g_i(\omega^*)=0,i=1,2,…,k$ )，也就是存在训练样本$(x_i,y_i)$使得函数间隔为1，即$g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1=0$。它到底表示了什么可以用图展示一下：

【机器学习】算法原理详细推导与实现(四):支持向量机(上)

你有一些训练样本和一个分隔超平面，根据上面的假设$\alpha_i > 0$(换个说法是$\alpha_i \neq 0$)就一定会有函数间隔为1的样本，即上图中虚线部分，这些里超平面最近的样本。在这个用图展示的例子中，所有离超平面较远样本的函数间隔都大于1。

从上面图形可以看出：通常情况下，可以发现只有很少数量的训练样本函数间隔等于1，在上面的图中只有3个样本的函数间隔等于1，只有少量的样本到超平面的距离是最小距离，这些样本我们称之为支持向量，支持向量机的支持向量就是这个意思

支持向量的数量一般都会很少，即大多数情况下拉格朗日算子$\alpha_i =0$，如果$\alpha_i = 0$，那么其对应的样本就可能不是支持向量($g_i(\omega) \leq 0$)。

回到上面的优化问题，由于只有$g_i(\omega)$，所以上面的拉格朗日函数：

\[ \Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega) \]

变成：

\[ \Gamma(\omega,\alpha)=f(\omega)+\sum_{i=1}^m\alpha_ig_i(\omega) \]

$\implies$

\[ \Gamma(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1] \]

注意到这里只有 $\alpha_i$ 没有 $\beta_i$ 是因为原问题中没有等式约束，只有不等式约束。

下面按照对偶问题的求解步骤，即需要定义下面的函数：：

\[ d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta) \]

首先求解最小值$min_{\omega} \Gamma(\omega,\alpha,\beta)$，对于固定的$\alpha_i$，$\Gamma(\omega,\alpha,\beta)$的最小值只与$\omega$和$b$有关。所以分别对$\omega$和$b$求偏导：

\[ \nabla_{\omega}\Gamma(\omega,b,\alpha)=\omega-\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}=0 \]

$\implies$

\[ \omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \]

上面得到$\Gamma(\omega,\alpha,\beta)$最小值时$\omega$的取值。

对$b$求偏导得到：

\[ \frac{\partial_{\Gamma(\omega,b,\alpha)}}{\partial_{b_i}}=\sum^m_{i=1}\alpha_iy^{(i)}=0 \]

将上面求偏导得到的两个式子，即代入到如下拉格朗日的函数中：

\[ \begin{split} \Gamma(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1] \\ &=\frac{1}{2}\omega^T\omega-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\omega^T\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}(\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1}\alpha_iy^{(i)}(x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_iy^{(i)}(x^{(i)})^T\alpha_jy^{(j)}x^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)} \end{split} \]

最后得到：

\[ \Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)} \]

$(x^{(i)})^Tx^{(j)}$ 即为向量内积，简化表达为$<x^{(i)},x^{(j)}>$

由于前面知道，对$b$求偏导时$\sum_{i=1}^m\alpha_iy^{(i)}=0$时可以使$b$取得最小值，所以最后一项$b\sum_{i=1}^m\alpha_iy^{(i)}$的值为0，最小值$min_{\omega} \Gamma(\omega,\alpha,\beta)$的式子转化为：

\[ \Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)},x^{(j)}> \]

该式子只剩下$\alpha$是未知变量，现在利用拉格朗日对偶函数求解未知函数$\alpha$

而对于原有拉格朗日对偶函数：

\[ d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta) \]

所以原有对偶问题可以定义为：

\[ max_{\alpha}\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)},x^{(j)}> \]

\[ \alpha_i \geq 0,i=1,2,…,m \]

\[ \sum_{i=1}^m\alpha_iy^{(i)}=0 \]

综上所述，只要求出$\alpha$，就可以根据公式：

\[ \omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \]

求得$\omega$，一旦求出了$\alpha$和$\omega$，就可以很容易的求出$b$，如下图所示，已知$\omega$可以确定超平面的方向，如下所示：

【机器学习】算法原理详细推导与实现(四):支持向量机(上)