计算（软间隔）SVM分类器等同于使下面表达式最小化
[
1
n
∑
i
=
1
n
max
(
0
,
1
−
y
i
(
w
⋅
x
i
+
b
)
)
]
+
λ
‖
w
‖
2
.
(
2
)
{\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}.\qquad (2)}
如上所述，由于我们关注的是软间隔分类器，
λ
{\displaystyle \lambda }
选择足够小的值就能得到线性可分类输入数据的硬间隔分类器。下面会详细介绍将(2)简化为二次规划问题的经典方法。之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。
原型
编辑
最小化(2)可以用下面的方式改写为目标函数可微的约束优化问题。
对所有
i
∈
{
1
,
…
,
n
}
{\displaystyle i\in \{1,\,\ldots ,\,n\}}
我们引入变量
ζ
i
=
max
(
0
,
1
−
y
i
(
w
⋅
x
i
+
b
)
)
{\displaystyle \zeta _{i}=\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)}
。注意到
ζ
i
{\displaystyle \zeta _{i}}
是满足
y
i
(
w
⋅
x
i
+
b
)
≥
1
−
ζ
i
{\displaystyle y_{i}(w\cdot x_{i}+b)\geq 1-\zeta _{i}}
的最小非负数。
因此，我们可以将优化问题叙述如下
minimize
1
n
∑
i
=
1
n
ζ
i
+
λ
‖
w
‖
2
{\displaystyle {\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|w\|^{2}}
subject to
y
i
(
x
i
⋅
w
+
b
)
≥
1
−
ζ
i
and
ζ
i
≥
0
,
for all
i
.
{\displaystyle {\text{subject to }}y_{i}(x_{i}\cdot w+b)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.}
这就叫做原型问题。
对偶型
编辑
通过求解上述问题的拉格朗日对偶（英语：Duality (optimization)），得到简化的问题
maximize
f
(
c
1
…
c
n
)
=
∑
i
=
1
n
c
i
−
1
2
∑
i
=
1
n
∑
j
=
1
n
y
i
c
i
(
x
i
⋅
x
j
)
y
j
c
j
,
{\displaystyle {\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},}
subject to
∑
i
=
1
n
c
i
y
i
=
0
,
and
0
≤
c
i
≤
1
2
n
λ
for all
i
.
{\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.}
这就叫做对偶问题。由于对偶最小化问题是受线性约束的
c
i
{\displaystyle c_{i}}
的二次函数，所以它可以通过二次规划算法高效地解出。
这里，变量
c
i
{\displaystyle c_{i}}
定义为满足
w
→
=
∑
i
=
1
n
c
i
y
i
x
→
i
{\displaystyle {\vec {w}}=\sum _{i=1}^{n}c_{i}y_{i}{\vec {x}}_{i}}
.
此外，当
x
→
i
{\displaystyle {\vec {x}}_{i}}
恰好在间隔的正确一侧时
c
i
=
0
{\displaystyle c_{i}=0}
，且当
x
→
i
{\displaystyle {\vec {x}}_{i}}
位于间隔的边界时
0
<
c
i
<
(
2
n
λ
)
−
1
{\displaystyle 0 。因此， w → {\displaystyle {\vec {w}}} 可以写为支持向量的线性组合。 可以通过在间隔的边界上找到一个 x → i {\displaystyle {\vec {x}}_{i}} 并求解 y i ( w → ⋅ x → i + b ) = 1 ⟺ b = y i − w → ⋅ x → i . {\displaystyle y_{i}({\vec {w}}\cdot {\vec {x}}_{i}+b)=1\iff b=y_{i}-{\vec {w}}\cdot {\vec {x}}_{i}.} 得到偏移量 b {\displaystyle b} 。（注意由于 y i = ± 1 {\displaystyle y_{i}=\pm 1} 因而 y i − 1 = y i {\displaystyle y_{i}^{-1}=y_{i}} 。） 核技巧 编辑 假设我们要学习与变换后数据点 φ ( x → i ) {\displaystyle \varphi ({\vec {x}}_{i})} 的线性分类规则对应的非线性分类规则。此外，我们有一个满足 k ( x → i , x → j ) = φ ( x → i ) ⋅ φ ( x → j ) {\displaystyle k({\vec {x}}_{i},{\vec {x}}_{j})=\varphi ({\vec {x}}_{i})\cdot \varphi ({\vec {x}}_{j})} 的核函数 k {\displaystyle k} 。 我们知道变换空间中的分类向量 w → {\displaystyle {\vec {w}}} 满足 w → = ∑ i = 1 n c i y i φ ( x → i ) , {\displaystyle {\vec {w}}=\sum _{i=1}^{n}c_{i}y_{i}\varphi ({\vec {x}}_{i}),} 其中 c i {\displaystyle c_{i}} 可以通过求解优化问题 maximize f ( c 1 … c n ) = ∑ i = 1 n c i − 1 2 ∑ i = 1 n ∑ j = 1 n y i c i ( φ ( x → i ) ⋅ φ ( x → j ) ) y j c j = ∑ i = 1 n c i − 1 2 ∑ i = 1 n ∑ j = 1 n y i c i k ( x → i , x → j ) y j c j {\displaystyle {\begin{aligned}{\text{maximize}}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi ({\vec {x}}_{i})\cdot \varphi ({\vec {x}}_{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k({\vec {x}}_{i},{\vec {x}}_{j})y_{j}c_{j}\\\end{aligned}}} subject to ∑ i = 1 n c i y i = 0 , and 0 ≤ c i ≤ 1 2 n λ for all i . {\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.} 得到。与前面一样，可以使用二次规划来求解系数 c i {\displaystyle c_{i}} 。同样，我们可以找到让 0 < c i < ( 2 n λ ) − 1 {\displaystyle 0 的索引 i {\displaystyle i} ，使得 φ ( x → i ) {\displaystyle \varphi ({\vec {x}}_{i})} 位于变换空间中间隔的边界上，然后求解 b = w → ⋅ φ ( x → i ) − y i = [ ∑ k = 1 n c k y k φ ( x → k ) ⋅ φ ( x → i ) ] − y i = [ ∑ k = 1 n c k y k k ( x → k , x → i ) ] − y i . {\displaystyle {\begin{aligned}b={\vec {w}}\cdot \varphi ({\vec {x}}_{i})-y_{i}&=\left[\sum _{k=1}^{n}c_{k}y_{k}\varphi ({\vec {x}}_{k})\cdot \varphi ({\vec {x}}_{i})\right]-y_{i}\\&=\left[\sum _{k=1}^{n}c_{k}y_{k}k({\vec {x}}_{k},{\vec {x}}_{i})\right]-y_{i}.\end{aligned}}} 最后，可以通过计算下式来分类新点 z → ↦ sgn ( w → ⋅ φ ( z → ) + b ) = sgn ( [ ∑ i = 1 n c i y i k ( x → i , z → ) ] + b ) . {\displaystyle {\vec {z}}\mapsto \operatorname {sgn}({\vec {w}}\cdot \varphi ({\vec {z}})+b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k({\vec {x}}_{i},{\vec {z}})\right]+b\right).} 现代方法 编辑 用于找到SVM分类器的最近的算法包括次梯度下降和坐标下降。当处理大的稀疏数据集时，这两种技术已经被证明有着显著的优点——当存在许多训练实例时次梯度法是特别有效的，并且当特征空间的维度高时，坐标下降特别有效。 次梯度下降 编辑 SVM的次梯度下降算法直接用表达式 f ( w → , b ) = [ 1 n ∑ i = 1 n max ( 0 , 1 − y i ( w ⋅ x i + b ) ) ] + λ ‖ w ‖ 2 . {\displaystyle f({\vec {w}},b)=\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}.} 注意 f {\displaystyle f} 是 w → {\displaystyle {\vec {w}}} 与 b {\displaystyle b} 的凸函数。因此，可以采用传统的梯度下降（或SGD（英语：Stochastic gradient descent））方法，其中不是在函数梯度的方向上前进，而是在从函数的次梯度中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 n {\displaystyle n} 而增加或减少。[13] 坐标下降 编辑 SVM的坐标下降算法基于对偶问题 maximize f ( c 1 … c n ) = ∑ i = 1 n c i − 1 2 ∑ i = 1 n ∑ j = 1 n y i c i ( x i ⋅ x j ) y j c j , {\displaystyle {\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},} subject to ∑ i = 1 n c i y i = 0 , and 0 ≤ c i ≤ 1 2 n λ for all i . {\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.} 对所有 i ∈ { 1 , … , n } {\displaystyle i\in \{1,\,\ldots ,\,n\}} 进行迭代，使系数 c i {\displaystyle c_{i}} 的方向与 ∂ f / ∂ c i {\displaystyle \partial f/\partial c_{i}} 一致。然后，将所得的系数向量 ( c 1 ′ , … , c n ′ ) {\displaystyle (c_{1}',\,\ldots ,\,c_{n}')} 投影到满足给定约束的最接近的系数向量。（通常使用欧氏距离。）然后重复该过程，直到获得接近最佳的系数向量。所得的算法在实践中运行非常快，尽管已经证明的性能保证很少。[14]
