SMO算法之SVM软间隔求解

1 引言

在上一篇文章中，笔者分别就SVM中软间隔与硬间隔目标函数的求解过程进行了介绍。但是在实际应用过程中，从效率的角度来讲那样的做法显然是不可取的，尤其是在大规模数据样本和稀疏数据中[1]。在接下来的这节内容中，笔者将会介绍一种新的求解算法，序列最小化优化算法来解决这一问题。

2 SVM软间隔求解

序列最小优化算法（Sequential Minimal Optimization, SMO）于1998年由John Platt所提出，并且SMO算法初次提出的目的就是为了解决SVM的优化问题[2]。SMO算法是一种启发式的算法，它在求解过程中通过以分析的方式来定位最优解可能存在的位置，从而避免了传统方法在求解中所遭遇的大量数值计算问题，并且最终以迭代的方式来求得最优解。在正式介绍SMO算法之前，笔者将先来介绍SMO算法的基本原理坐标上升算法（Coordinate Ascent）。

2.1 坐标上升算法

在之前的文章中，笔者详细的介绍了什么是梯度下降算法以及梯度下降算法的作用。对于一个待优化的目标函数来说，在初始化一个起始位置后，便可以以该点为基础每次沿着该点梯度的反方向向前移动一小步，以此来迭代求解得到目标函数的全局（局部）最优解。而所谓的坐标上升（下降）算法可以看作是初始位置只沿着其中的一个（或几个）方向移动来求解得到目标函数的全局（局部）最优解[3]，如图1所示。

图 1. 梯度上升与坐标上升图

$J({{w}_{1}},{{w}_{2}})=-0.5{{({{w}_{1}}-1)}^{2}}-{{(2{{w}_{2}}+1)}^{2}}$ $-0.5{{({{w}_{1}}-{{w}_{2}})}^{2}}$ $J({{w}_{1}},{{w}_{2}})$ $J({{w}_{1}},{{w}_{2}},...,{{w}_{n}})$ 来说可以通过如下步骤来进行求解

$w$ 为初始参数值；

${{w}_{1}},{{w}_{2}},...,{{w}_{n}}$ ${{w}_{i}},i=1,2,...,n$ ${{w}_{i}}$ ${{w}_{i}}$ ；

(3) 重复执行步骤(2)直到目标函数收敛或者是误差小于某一阈值结束。

$w_1,w_2$ 的求解表达式分别为

\begin{aligned} & w_{1}^{new}=\frac{1}{2}(w_{2}^{old}+1) \\ & w_{2}^{new}=\frac{1}{9}(w_{1}^{new}-4) \\ \end{aligned}\;\;\;\;\;\;(1)

$w_{1}^{old},w_{2}^{old}$ $w_1,w_2$ 的解。

${{w}_{i}}$ 顺序的选择这里采用了最为简单的按顺序依次进行，一种更优的做法便是每次选择余下常量中能够使得目标函数产生最大增量参数作为优化对象。

2.2 SMO算法思想

根据之前的内容可知，SVM软间隔最终需要求解的目标函数为

\begin{aligned} & \underset{\alpha }{\mathop{\max }}\,\underset{i=1}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \\ & s.t.\ \ 0\le {{\alpha }_{i}}\le C,\ i=1,2,...,m \\ & \ \ \ \ \ \ \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \\ \end{aligned}\;\;\;\;\;\;(2)

$\alpha_i$ $(2)$ $\alpha$ ${{\alpha }_{2}},...,{{\alpha }_{m}}$ ${{\alpha }_{1}}$ ${{\alpha }_{1}}$ ${{\alpha }_{1}}$ $(2)$ 中第2个约束条件有

\alpha_1y^{(1)}=-\sum_{i=2}^m\alpha_iy^{(i)}\;\;\;\;\;(3)

$(3)$ ${{y}^{(1)}}$ 有

\alpha_1y^{(1)}=-\sum_{i=2}^m\alpha_iy^{(i)}\;\;\;\;\;(4)

$(4)$ ${{\alpha }_{1}}$ ${{\alpha }_{2}},...,{{\alpha }_{m}}$ ${{\alpha }_{2}},...,{{\alpha }_{m}}$ ${{\alpha }_{1}}$ 也是固定的。因此，在这样的情况下每次至少需要同时选择两个参数为变量，同时再固定住其它变量才能够最终求得所有参数。

${{\alpha }_{3}},...,{{\alpha }_{m}}$ ${{\alpha }_{1}},{{\alpha }_{2}}$ $(2)$ 中的约束条件有

{{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=-\sum\limits_{i=3}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}\;\;\;\;\;(5)

$(5)$ $\zeta$ 来表示

{{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=\zeta\;\;\;\;\;(6)

${{\alpha }_{1}}$ 表示为

{{\alpha }_{1}}=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}\;\;\;\;\;(7)

$(2)$ 中的目标函数便可以改写为

W({{\alpha }_{1}},{{\alpha }_{2}},...,{{\alpha }_{m}})=W((\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}},{{\alpha }_{2}},...,{{\alpha }_{m}})\;\;\;\;\;(8)

$(8)$ ${{\alpha }_{3}},...,{{\alpha }_{m}}$ $\alpha_2$ 的一元二次多项式。

a\alpha _{2}^{2}+b{{\alpha }_{2}}+c\;\;\;\;\;(9)

$(9)$ ${{\alpha }_{2}}$ ${{\alpha }_{2}}$ ${{\alpha }_{2}}$ $(6)$ ${{\alpha }_{1}}$ ${{\alpha }_{3}},...,{{\alpha }_{m}}$ $\alpha_1,\alpha_2,...,\alpha_m$ 。

以上就是SMO算法求解的主要思想。虽然看起来不太复杂，但是里面仍旧有很多值得深究的内容，下面开始正式介绍SMO算法的原理。

2.3 SMO算法原理

为了更加广义的表示SVM软间隔中的优化问题，可以通过如下形式来表示待求解的优化问题

\begin{aligned} & \underset{\alpha }{\mathop{\max }}\,\underset{i=1}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}}K({{x}^{(i)}},{{x}^{(j)}}) \\ & s.t.\ \ 0\le {{\alpha }_{i}}\le C,\ i=1,2,...,m \\ & \ \ \ \ \ \ \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \\ \end{aligned}\;\;\;\;\;\;(10)

$K(\cdot)$ 为任意核函数。

$\alpha_1,\alpha_2$ $(10)$ 便可以改写成如下形式[1]

\begin{aligned} & \underset{{{\alpha }_{1}},{{\alpha }_{2}}}{\mathop{\max }}\,{{\alpha }_{1}}+{{\alpha }_{2}}-\frac{1}{2}\alpha _{1}^{2}{{K}_{11}}-{{\alpha }_{1}}{{\alpha }_{2}}{{y}^{(1)}}{{y}^{(2)}}{{K}_{12}}-{{\alpha }_{1}}{{y}^{(1)}}\underset{i=3}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}{{y}^{(i)}}{{K}_{1i}} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}\underset{i=3}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}{{y}^{(i)}}{{K}_{2i}}+{{\Psi }_{constant}} \\ & s.t.\ \ 0\le {{\alpha }_{i}}\le C,\ i=1,2 \\ & \ \ \ \ \ \ {{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=-\sum\limits_{i=3}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=\zeta \\ \end{aligned}\;\;\;\;\;\;(11)

${{K}_{ij}}=K({{x}^{(i)}},{{x}^{(j)}})$ ${{\Psi }_{constant}}$ $\alpha_1,\alpha_2$ 无关的常量。

同时，记

\begin{aligned} & g(x)=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}K(x,{{x}_{i}})+b \\ & {{v}_{i}}=\sum\limits_{j=3}^{m}{{{\alpha }_{j}}}{{y}^{(j)}}K({{x}_{i}},{{x}_{j}})=g({{x}_{i}})-\underset{j=1}{\overset{2}{\mathop \sum }}\,{{\alpha }_{j}}{{y}^{(j)}}K({{x}_{i}},{{x}_{j}})-b,\ \ i=1,2 \\ \end{aligned}\;\;\;\;\;\;(12)

$(11)$ 可以改写为

\begin{aligned} & W({{\alpha }_{1}},{{\alpha }_{2}})={{\alpha }_{1}}+{{\alpha }_{2}}-\frac{1}{2}\alpha _{1}^{2}{{K}_{11}}-{{\alpha }_{1}}{{\alpha }_{2}}{{y}^{(1)}}{{y}^{(2)}}{{K}_{12}}-{{\alpha }_{1}}{{y}^{(1)}}{{v}_{1}} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}{{v}_{2}}+{{\Psi }_{constant}} \\ \end{aligned}\;\;\;\;\;\;(13)

${{\alpha }_{1}}=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}$ $(13)$ ${{\alpha }_{2}}$ 目标函数

\begin{aligned} & W({{\alpha }_{2}})=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}+{{\alpha }_{2}}-\frac{1}{2}{{(\zeta -{{\alpha }_{2}}{{y}^{(2)}})}^{2}}{{K}_{11}} \\ & -(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{\alpha }_{2}}{{y}^{(2)}}{{K}_{12}}-(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{v}_{1}}-\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}{{v}_{2}} \end{aligned}\;\;\;\;\;\;(14)

$(14)$ $\alpha_2$ 的导数为

\begin{aligned} & \frac{\partial W}{\partial {{\alpha }_{2}}}=-{{y}^{(1)}}{{y}^{(2)}}+1+\zeta {{y}^{(2)}}{{K}_{11}}-{{\alpha }_{2}}{{K}_{11}}+2{{\alpha }_{2}}{{K}_{12}} \\ & -\zeta {{y}^{(2)}}{{K}_{12}}+{{v}_{1}}{{y}^{(2)}}-{{\alpha }_{2}}{{K}_{22}}-{{y}^{(2)}}{{v}_{2}} \end{aligned}\;\;\;\;\;\;(15)

$(15)$ 为0可以得到

{{\alpha }_{2}}=\frac{{{y}^{(2)}}\left( {{y}^{(2)}}-{{y}^{(1)}}+\zeta {{\text{K}}_{11}}-\zeta {{\text{K}}_{12}}+{{v}_{1}}-{{v}_{2}} \right)}{{{K}_{11}}-2{{K}_{12}}+{{K}_{22}}}\;\;\;\;\;\;(16)

此时，记

\begin{aligned} & \eta ={{K}_{11}}-2{{K}_{12}}+{{K}_{22}} \\ & {{E}_{i}}=g({{x}_{i}})-{{y}^{(i)}}=\left( \sum\limits_{j=1}^{m}{{{\alpha }_{j}}}{{y}^{(j)}}K({{x}_{i}},{{x}_{j}})+b \right)-{{y}^{(i)}},\ \ i=1,2 \\ \end{aligned}\;\;\;\;\;\;(17)

$\alpha _{1}^{old},\alpha _{2}^{old}$ $(17)$ $\zeta =\alpha _{1}^{old}{{y}^{(1)}}+\alpha _{2}^{old}{{y}^{(2)}}$ $(16)$ 有

\begin{aligned} & \alpha _{2}^{new}=\frac{{{y}^{(2)}}}{\eta } \left[ {{y}^{(2)}}-{{y}^{(1)}}+\left( \alpha _{1}^{old}{{y}^{(1)}}+\alpha _{2}^{old}{{y}^{(2)}} \right){{K}_{11}} \right. \\ & -\left( \alpha _{1}^{old}{{y}^{(1)}}+\alpha _{2}^{old}{{y}^{(2)}} \right){{K}_{12}}+g({{x}_{1}})-\sum\limits_{j=1}^{2}{\alpha _{j}^{old}}{{y}^{(j)}}{{K}_{1j}} \\ & -b-g({{x}_{2}})+\sum\limits_{j=1}^{2}{\alpha _{j}^{old}}{{y}^{(j)}}{{K}_{2j}}+\left. b \right] \end{aligned}\;\;\;\;\;\;\;(18)

$(18)$ 进一步化简后可得

\alpha_2^{new}=\alpha_2^{old}+\frac{y^{(2)}(E_1-E_2)}{\eta}\;\;\;\;\;\;(19)

${{\alpha }_{2}}$ ${{\alpha }_{2}}$ 还没有经过约束条件裁剪。

$(11)$ ${{\alpha }_{1}},{{\alpha }_{2}}$ $[0,C]\times[0,C]$ $(11)$ ${{\alpha }_{1}},{{\alpha }_{2}}$ 还必须位于平行于盒子对角线的线段上，如图2所示。

$\alpha_1,\alpha_2$ 修正图

${{\alpha }_{1}},{{\alpha }_{2}}$ $\alpha _{2}^{new}$ $\alpha _{2}^{new}$ 满足

L\le \alpha _{2}^{new}\le H\;\;\;\;\;\;\;(20)

$L$ $H$ 是图2中线段的两个端点。

${{y}^{(1)}}\ne {{y}^{(2)}}$ 则

L=\max (0,\alpha _{2}^{old}-\alpha _{1}^{old}),\ \ \ H=\min (C,C+\alpha _{2}^{old}-\alpha _{1}^{old})\;\;\;\;\;\;(21)

${{y}^{(1)}}={{y}^{(2)}}$ 则

L=\max (0,\alpha _{2}^{old}+\alpha _{1}^{old}-C),\ \ \ H=\min (C,\alpha _{2}^{old}+\alpha _{1}^{old})\;\;\;\;\;\;(22)

$\alpha _{2}^{new}$ 裁剪后的值应该为

\begin{aligned} \alpha_{2}^{new,clipped}= \begin{cases} H, & \alpha_2^{new}>H \\ \alpha_2^{new}, & L\leq\alpha_2^{new}\leq H \\ L, & \alpha_2^{new}< L \end{cases} \end{aligned}\;\;\;\;\;\;(23)

${{\alpha }_{1}}=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}$ $\zeta =\alpha _{1}^{old}{{y}^{(1)}}+\alpha _{2}^{old}{{y}^{(2)}}$ 可得

\begin{aligned} & \alpha _{1}^{new}=(\alpha _{1}^{old}{{y}^{(1)}}+\alpha _{2}^{old}{{y}^{(2)}}-\alpha _{2}^{new,clipped}{{y}^{(2)}}){{y}^{(1)}} \\ & =\alpha _{1}^{old}+{{y}^{(1)}}{{y}^{(2)}}(\alpha _{2}^{old}-\alpha _{2}^{new,clipped}) \end{aligned}\;\;\;\;\;\;(24)

${{\alpha }_{1}},{{\alpha }_{2}}$ ${{\alpha }_{3}},...,{{\alpha }_{m}}$ ${{\alpha }_{1}},{{\alpha }_{2}},...,{{\alpha }_{m}}$ 的最优解。

$b$ 求解

${{\alpha }_{i}},{{\alpha }_{j}}$ $b$ 的值。

\begin{aligned} & \ \ \ \ \ \ {{\alpha }_{i}}=0\ \ \ \ \Rightarrow \ \ \ \ {{y}^{(i)}}({{W}^{T}}{{x}^{(i)}}+b)\ge 1 \\ & \ \ \ \ \ \ {{\alpha }_{i}}= C\ \ \ \Rightarrow \ \ \ \ {{y}^{(i)}}({{W}^{T}}{{x}^{(i)}}+b)\le 1 \\ & 0<{{\alpha }_{i}} < C\ \ \ \ \Rightarrow \ \ \ \ {{y}^{(i)}}({{W}^{T}}{{x}^{(i)}}+b)=1 \\ \end{aligned}\;\;\;\;\;(25)

$0<\alpha _{1}^{new}< C$ $(25)$ 中的第3个KKT条件可知

{{y}^{(1)}}({{W}^{T}}{{x}^{(1)}}+b)={{y}^{(1)}}g({{x}_{1}})={{y}^{(1)}}\left( \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{K}_{1i}}+b \right)=1\;\;\;\;\;\;(26)

进一步可得

\sum_{i=1}^m\alpha_iy^{(i)}K_{1i}+b=y^{(1)}\;\;\;\;\;\;(27)

$(27)$ 有

b_{1}^{new}={{y}^{(1)}}-\underset{i=3}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}{{y}^{(i)}}{{K}_{1i}}-\alpha _{1}^{new}{{y}^{(1)}}{{K}_{11}}-\alpha _{2}^{new,clipped}{{y}^{(2)}}{{K}_{12}}\;\;\;\;\;(28)

$(17)$ $E_i$ 的定义可知

{{E}_{1}}=\underset{i=3}{\overset{m}{\mathop \sum }}\,{{\alpha }_{i}}{{y}^{(i)}}{{K}_{1i}}+\alpha _{1}^{old}{{y}^{(1)}}{{K}_{11}}+\alpha _{2}^{old}{{y}^{(2)}}{{K}_{12}}+{{b}^{old}}-{{y}^{(1)}}\;\;\;\;\;\;(29)

$(29)$ $(28)$ 的前两项可以改写为

{{y}^{(1)}}-\sum\limits_{i=3}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{K}_{1i}}={{b}^{old}}-{{E}_{i}}+\alpha _{1}^{old}{{y}^{(1)}}{{K}_{11}}+\alpha _{2}^{old}{{y}^{(2)}}{{K}_{12}}\;\;\;\;\;\;(30)

$(30)$ $(28)$ 可得

b_{1}^{new}={{b}^{old}}-{{E}_{1}}-{{y}^{(1)}}{{K}_{11}}(\alpha _{1}^{new}-\alpha _{1}^{old})-{{y}^{(2)}}{{K}_{12}}(\alpha _{2}^{new,clipped}-\alpha _{2}^{old})\;\;\;\;\;\;(31)

$0<\alpha _{2}^{new,clipped}< C$ 时有

b_{2}^{new}={{b}^{old}}-{{E}_{2}}-{{y}^{(1)}}{{K}_{12}}(\alpha _{1}^{new}-\alpha _{1}^{old})-{{y}^{(2)}}{{K}_{22}}(\alpha _{2}^{new,clipped}-\alpha _{2}^{old})\;\;\;\;\;\;\;(32)

$\alpha _{1}^{new},\alpha _{2}^{new,clipped}$ $b_{1}^{new},b_{2}^{new}$ $\alpha _{1}^{new},\alpha _{2}^{new,clipped}$ $0$ $C$ $b_{1}^{new},b_{2}^{new}$ ${{b}^{new}}$ ，即

{{b}^{new}}=\left\{ \begin{aligned} & b_{1}^{new},\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0<\alpha _{1}^{new}< C \\ &#038; b_{2}^{new},\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0<\alpha _{2}^{new,clipped}< C \\ &#038; (b_{1}^{new}+b_{2}^{new})/2,\ \ \ otherwise \\ \end{aligned} \right. \;\;\;\;\;\;(33)

2.5 SVM算法求解示例

经过前面几部分内容的介绍，相信各位读者朋友对于如何通过SMO算法来求解SVM中的参数已经有了一定的了解。同时，对于整个求解过程还可以通过如下一段伪代码来进行表示[5]

输入：


xxxxxxxxxx
7
1
$C$惩罚项系数；
2
3
$tol$：误差容忍度；
4
5
$max\_passes$：当$\alpha_i$不再发生变化时继续迭代更新的最大次数；
6
7
$(({{x}^{(1)}},{{y}^{(1)}}),...,({{x}^{(m)}},{{y}^{(m)}}))$：训练集；

输出：


xxxxxxxxxx
3
1
$\alpha\in\mathbb{R}^m$：求解得到的拉格朗日乘子；
2
3
$b\in\mathbb{R}$：求解得到的偏置。


xxxxxxxxxx
25
1
初始化所有 alpha_i = 0, b = 0, passes = 0
2
while (passes < max_passes)
3
    num_changed_alphas = 0
4
    for i = 1,...,m
5
        计算 E_i
6
        if ((y_i*E_i < -tol and a_i < C)||(y_i*E_i > tol and alpha_i > 0))
7
            随机选择j，且j不等于i
8
            计算 E_j
9
            保存：alpha_i_old = alpha_i,alpha_j_old = alpha_j
10
            计算 L 和 H
11
            if (L == H):
12
                continue
13
            计算 eta
14
            if (eta >- 0):
15
                continue
16
            计算 alpha_j并裁剪
17
            if (|alpha_j - alpha_j_old| < 10e-5):
18
                continue
19
            分别计算alpha_i, b_1, b_2
20
            计算b
21
            num_changed_alphas += 1
22
    if (num_changed_alphas == 0):
23
        passes += 1
24
    else:
25
        passes = 0

$C=0.2$ ，那么最终的求解结果为


xxxxxxxxxx
7
1
data_x = np.array([[5, 1], [0, 2], [1, 5], [3., 2], [1, 2], [3, 5], [1.5, 6], [4.5, 6], [0, 7]])
2
data_y = np.array([1, 1, 1, 1, 1, -1, -1, -1, -1])
3
alphas, b = smo(C=.2, tol=0.001, max_passes=200, data_x=data_x, data_y=data_y)
4
print(alphas) #[0.   0.   0.2   0.142   0.   0.2   0.142   0.   0.]
5
print(b)# 2.66
6
w = compute_w(data_x,data_y,alphas)
7
print(w)# [-0.186,  -0.569]

图 3. SVM软间隔示例图

$\alpha_3=\alpha_6=0.2$ $\alpha_4=\alpha_7=0.142$ $(1,5),(3,5)$ $(3,2),(1.5,6)$ $w=(-0.186,-0.569)$ $b=2.66$ 。需要注意的是，为了作图方便，图3中左右两边各自还有两个样本点没有画出，所以上述代码中有9个样本。

3 总结

$\alpha$ $b$ 的求解方法；最后以伪代码的形式展示了SMO算法的求解过程，并通过一个实例进行了展示。

本次内容就到此结束，感谢您的阅读！如果你觉得上述内容对你有所帮助，欢迎分享至一位你的朋友！若有任何疑问与建议，请添加笔者微信'nulls8'或加群进行交流。青山不改，绿水长流，我们月来客栈见！

引用

[1] John C. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, Microsoft Research Technical Report MSR-TR-98-14.

[2] https://en.wikipedia.org/wiki/Sequential_minimal_optimization

[3] https://en.wikipedia.org/wiki/Coordinate_descent

[4] Andrew Ng, Machine Learning, Stanford University, CS229, Spring 2019.

[5] Machine Learning, Stanford University, CS229, Autumn 2009.

[6] https://github.com/moon-hotel/MachineLearningWithMe

SMO算法之SVM软间隔求解

于2021年9月3日2021年9月3日由空字符发布

1 引言

2 SVM软间隔求解

2.1 坐标上升算法

2.2 SMO算法思想

2.3 SMO算法原理

$b$ 求解

2.5 SVM算法求解示例

3 总结

引用

机器学习

从零实现ID3与C4.5决策树算法

机器学习

高斯朴素贝叶斯原理与实现

机器学习

三种常见的聚类内部评价指标

SMO算法之SVM软间隔求解

于2021年9月3日2021年9月3日由 空字符 发布

1 引言

2 SVM软间隔求解

2.1 坐标上升算法

2.2 SMO算法思想

2.3 SMO算法原理

2.4 偏置b求解

2.5 SVM算法求解示例

3 总结

引用

相关文章

机器学习

从零实现ID3与C4.5决策树算法

机器学习

高斯朴素贝叶斯原理与实现

机器学习

三种常见的聚类内部评价指标

于2021年9月3日2021年9月3日由空字符发布

$b$ 求解