从线性到非线性模型

1、线性回归，岭回归，Lasso回归，局部加权线性回归

2、logistic回归，softmax回归，最大熵模型

3、广义线性模型

4、Fisher线性辨别和线性感知机

5、三层神经网络

6、支撑向量机

六、支撑向量机

在线性模型中，Fisher线性辨别和线性感知机可以说是以上所有模型的分类依据，前者是映照到一维执其两端进行分类，后者是在高维空间找一个线性超平面将两类离开（两类可扩大到多类）。支撑向量机属于后者，但重要有以下几点改良：

1）提出硬间隔线性可分，在感知机的基本上提出了线性可分假定（无丧失），最大化最小间隔

2）提出软间隔线性可分，得到了hinge丧失取代感知机的线性丧失(后面弥补一个线性模型丧失比较图)

3）联合核函数将数据映照到高维空间，使得模型具有非线性才能

4）具有感知机的一切解释性，同时目的函数的对偶情势是凸二次计划问题

硬间隔（最大化最小间隔分类器）：

线性感知机中由于没有线性可分假定，所以其目的函数定义为最小化错分样本的丧失，而硬间隔SVM则提出了一个线性可分假定，即样本在高维空间中线性可分，那末使得两类离开的超平面必定有没有穷个。硬间隔SVM则在这些超平面中找出最优的（即所有样本到超平面距离加和最小化），所以有以下目的函数：

min \sum_{i = 1}^{m} \frac{1}{| | w | |^{2}} y_{i} (w \cdot x_{i} + b)

其中

\frac{1}{| | w | |^{2}} y_{i} (w \cdot x_{i} + b)

为点到平面的几何间隔，去掉系数为函数间隔。最大化最小间隔分类器则采取等价情势—使得最难分的样本离超平面距离尽量的大—最大化最小间隔分类器

max_{w, b} γ s . t . \frac{1}{| | w | |^{2}} y_{i} (w \cdot x_{i} + b) > γ, i \in 1, 2... m

max_{w, b} \frac{γ}{| | w | |^{2}} s . t . y_{i} (w \cdot x_{i} + b) > γ, i \in 1, 2... m

令 $γ = 1$ 有：

min_{w, b} \frac{1}{2} | | w | |^{2} s . t . y_{i} (w \cdot x_{i} + b) - 1 > 0, i \in 1, 2... m

到此，上式为硬间隔分类器的原问题终究情势。上述问题可应用拉格朗日乘子法和对偶问题进行求解。

拉格朗日函数

min_{w, b} \frac{1}{2} | | w | |^{2} - \sum_{i = 1}^{m} α_{i} (y_{i} (w \cdot x_{i} + b) - 1) s . t . ▽ L (w, b, α_{i}) = 0 α_{i} (y_{i} (w \cdot x_{i} + b) - 1) = 0 α_{i} \geq 0 y_{i} (w \cdot x_{i} + b) - 1 > 0, i \in 1, 2... m

其中

▽ L (w, b, α_{i}) = 0

由Fritz John条件得出，

α_{i} (y_{i} (w \cdot x_{i} + b) - 1) = 0

为互补松弛条件，互补松弛条件与支撑向量有亲密关系。由上述束缚条件有：

\frac{▽ L (w, b, α_{i})}{w} = w - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} = 0 \frac{▽ L (w, b, α_{i})}{b} = \sum_{i = 1}^{m} α_{i} y_{i} = 0 b = y_{j} - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} \cdot x_{j}

将上式带入到拉格朗日函数，得到关于

α

表现的函数：

L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} + \sum_{i = 1}^{m} α_{i}

最大化关于

α

的函数即为原问题的对偶问题,以下：

max L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} + \sum_{i = 1}^{m} α_{i} \Leftrightarrow min \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} - \sum_{i = 1}^{m} α_{i} s . t . \sum_{i = 1}^{m} α_{i} y_{i} = 0 α_{i} \geq 0

解出上式目的函数

α

后，有

w, b

w = \sum_{i = 1}^{m} α_{i} y_{i} x_{i} b = y_{j} - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} \cdot x_{j}

其中可以看出，w和b有样本点与

α

內积肯定。

但是回过火来想，线性可分假定是不现实，所以SVM在硬间隔线性可分的基本上提出软间隔线性可分。即许可线性不可分，但是须要进行必定的处分。以下图为软间隔线性可分，其中在支撑向量里面的点和错分的样本为线性不可分的点，虚线上的点为支撑向量。

软间隔SVM：

线性不可分意味着某些样本不满足函数间隔大于 $1$ 的束缚条件，为懂得决这个问题，可以对每一个样本引入一个松弛变量 $ξ_{i} \geq 0$ ，使得函数间隔加上松弛变量大于等于1，这样束缚条件变成：

y_{i} (w \cdot x_{i} + b) > 1 - ξ_{i}, i \in 1, 2.. m

同时对线性不可分的样本进行处分，因此目的函数变成：

m i n_{w, b} \frac{1}{2} | | w | | + C \sum_{i = 1}^{m} ξ_{i}

因此终究的线性不可分SVM的目的函数以下：

m i n_{w, b} \frac{1}{2} | | w | | + C \sum_{i = 1}^{m} ξ_{i} s . t . y i (w \cdot x i + b) > 1 - ξ_{i}, i \in 1, 2.. m ξ_{i} \geq 0, i \in 1, 2.. m

拉格朗日函数

m i n_{w, b} \frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{m} ξ_{i} - \sum_{i = 1}^{m} α_{i} (y_{i} (w \cdot x_{i} + b) - 1 + ξ_{i}) - \sum_{i = 1}^{m} β_{i} ξ_{i} s . t . ▽ L (w, b, ξ_{i}, α_{i}, β_{i}) = 0 α_{i} (y_{i} (w \cdot x_{i} + b) - 1 + ξ_{i}) = 0 β_{i} ξ_{i} = 0 α_{i} \geq 0 β_{i} \geq 0 y_{i} (w \cdot x_{i} + b) - 1 \geq 0, i \in 1, 2... m ξ_{i} \geq 0, i \in 1, 2.. m

由上述束缚条件有：

\frac{▽ L (w, b, α_{i})}{w} = w - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} = 0 \frac{▽ L (w, b, α_{i})}{b} = \sum_{i = 1}^{m} α_{i} y_{i} = 0 \frac{▽ L (w, b, α_{i})}{ξ_{i}} = C - α_{i} - β_{i} = 0 b = y_{j} - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} \cdot x_{j}

将上式带入到拉格朗日函数，得到目的函数关于

α ， β

表现的函数,同硬间隔的对偶函数一致：

L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} + \sum_{i = 1}^{m} α_{i}

最大化关于

α

的函数即为原问题的对偶问题，而对偶问题为原问题供给一个下界，即原问题的对偶问题以下：

max L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} + \sum_{i = 1}^{m} α_{i} \Leftrightarrow min \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} - \sum_{i = 1}^{m} α_{i} s . t . \sum_{i = 1}^{m} α_{i} y_{i} = 0 C - α_{i} - β_{i} = 0 α_{i} \geq 0 β_{i} \geq 0 \Leftrightarrow min \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} - \sum_{i = 1}^{m} α_{i} s . t . \sum_{i = 1}^{m} α_{i} y_{i} = 0 0 \leq α_{i} \leq C

解出上式目的函数

α, β

后，有

w, b

w = \sum_{i = 1}^{m} α_{i} y_{i} x_{i} b = y_{j} - \sum_{i = 1}^{m} α_{i} y_{i} x_{i} \cdot x_{j}

可以看出，w和b由样本点与

α

內积肯定，当

α_{i} = 0

表现第i个样本点满足

y_{i} (w \cdot x_{i} + b) - 1 \geq 0

条件，该点不在支撑向量内部，w与该点无关，支撑向量机的参数

w

只与支撑向量之内的点有关。

比较硬间隔和软间隔SVM发明二者的对偶问题非常相似，唯一不同的在于 $0 \leq α$ ， $0 \leq α \leq C$ ，也就是说在束缚条件上不能让 $α$ 值太大。而 $α$ 不为 $0$ 的意义就是该点线性不可分—在支撑向量之内，不能让 $α$ 太大的意义就是尽量的不要让样本在支撑向量太里面。这也就是处分项引入后的成果。

下面依据 $α, β$ 的取值来剖析样本点的一个地位，和样本点对SVM参数的影响：

当 $α_{i} = 0$ ,则 $β_{i} = C ， ξ_{i} = 0$ ，表现样本点在支撑向量上或之外的，之外的点对参数 $w$ 无价值

当 $0 < α_{i} < C$ ,则 $0 < β_{i} < C ， ξ_{i} = 0$ ，表现样本点在支撑向量上

当 $α_{i} = C$ ,则 $0 = β_{i}$ ，如果 $0 < ξ_{i} < 1$ ，表现样本在支撑向量内部，但分类准确

当 $α_{i} = C$ ,则 $0 = β_{i}$ ，如果 $ξ_{i} = 1$ ，表现样本在超平面上

当 $α_{i} = C$ ,则 $0 = β_{i}$ ，如果 $ξ_{i} > 1$ ，表现样本分类毛病

核函数：

核函数的应用重要是解决线性不可分问题，通过选择适合的核函数将样本从低维线性不可分映照到高维以后容易线性可分，实质上是一次空间上的非线性变换（特点映照），核函数可以嫁接到很多线性模型上，使其具有非线性才能，只是核函数的选择是一件难定的事。

而SVM与核函数有着天然的契合度，由于在SVM的对偶问题中，须要盘算样本之间的內积，而核函数的引入则可使得內积操作直接在核函数中隐式完成。

L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} \cdot x_{j} + \sum_{i = 1}^{m} α_{i}

在上式中有

x_{i} \cdot x_{j}

內积操作，当我们应用核技能时，常常须要定义一个核函数

ϕ (x)

进行特点空间变换，然后在新的特点空间中进行

ϕ (x_{i}) \cdot ϕ (x_{j})

內积操作，这使得盘算进程分两步完成。如果我们隐式的定义核函数以下：

K (x_{i}, x_{j}) = ϕ (x_{i}) \cdot ϕ (x_{j})

L (w, b, α) = - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} K (x_{i}, x_{j}) + \sum_{i = 1}^{m} α_{i}

直接定义 $K (x_{i}, x_{j})$ 作为核函数，而不管实际的核函数 $ϕ (x)$ 是如何将x映照到 $ϕ (x)$ 空间，然后在新的特点空间盘算內积。这样，我们就隐式完成了內积操作，将核函数与內积操作一步完成为 $K (x_{i}, x_{j})$ 。固然，核函数必需满足核函数的性质。

一般常采取的核函数有：

线性核 $K (x_{i}, x_{j}) = x_{i}^{T} x_{j}$

多项式核 $K (x_{i}, x_{j}) = (x_{i}^{T} x_{j})^{d}$

高斯核 $K (x_{i}, x_{j}) = e x p (- \frac{(x_{i} - x_{j})^{2}}{2 σ^{2}})$

拉普拉斯核 $K (x_{i}, x_{j}) = e x p (- \frac{| | x_{i} - x_{j} | |}{2 σ^{2}})$

sigmoid核 $K (x_{i}, x_{j}) = t a n h (β x_{i}^{T} x_{j} + θ)$

但是核技能中，最盲目的是如何选择适合核函数，或多核。

这里须要解释的是，SVM对核函数有一个本身的请求，核的大小必定是 $m^{2}$ 。由于SVM在做內积时是所有点彼此做內积，所以庞杂度是 $m^{2}$ 。这也是SVM难以适应大规模数据的场景，SVM的庞杂度 $m^{2} d$ 体现在內积上，带核的SVM的庞杂度体现在核函数的盘算上。而这不是核函数的特色，核函数中核的大小是自定义的。

SMO优化算法

min \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} x_{i} x_{j} - \sum_{i = 1}^{m} α_{i} s . t . \sum_{i = 1}^{m} α_{i} y_{i} = 0 0 \leq α_{i} \leq C

SVM优化问题是一个典范的带束缚凸二次计划，传统的梯度办法不能直接应用于带束缚优化问题，下面先介绍一种坐标上升优化算法，算法的思想是对多个参数的优化求解问题，可以每次只斟酌一个变量，而固定其他所有变量，对一个变量进行目的优化，内重复每一个变量进行优化，外重复直到迭代到收敛。其收敛性相似于EM算法。

由于内层重复每次只转变一个变量，所以坐标上升算法的搜索路径与坐标轴平行

但是，如果每次只转变一个变量来优化SVM，那末必定不满足 $\sum_{i = 1}^{m} α_{i} y_{i} = 0$ 束缚。所以SMO算法在座标上升算法基本上又以下两点改良：

1）为了满足 $\sum_{i = 1}^{m} α_{i} y_{i} = 0$ 束缚，每次迭代优化选择两个变量，其中一个自动变量，另外一个被动变量

2）在选择两个变量进行优化时，采取启示式搜索策略，自动变量选择背背KKT条件最严重的一个变量 $α_{1}$ ，在选定 $α_{1}$ 后，被动变量 $α_{2}$ 选择变更规模最大的，在优化 $α_{1}$ 和 $α_{2}$ 时应用高低剪辑来使得 $α_{1}$ 和 $α_{2}$ 满足 $0 \leq α_{i} \leq C$ 束缚

现在来看SMO算法，固定m-2个变量不变，将目的函数转化为关于 $α_{1}$ 和 $α_{2}$ 的函数：

min \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{j} y_{j} K (x_{i}, x_{j}) - \sum_{i = 1}^{m} α_{i} min W (α_{1}, α_{2}) = \frac{1}{2} α_{1}^{2} K_{11} + \frac{1}{2} α_{2}^{2} K_{22} + y_{1} y_{2} α_{1} α_{2} K_{12} + y_{1} α_{1} \sum_{i = 3}^{m} y_{i} α_{i} K_{i 1} + y_{2} α_{2} \sum_{i = 3}^{m} y_{i} α_{i} K_{i 2} - (α_{1} + α_{2}) s . t . α_{1} y_{1} + α_{2} y_{2} = - \sum_{i = 3}^{m} α_{i} y_{i} = ς 0 \leq α_{i} \leq C

其中

K_{i j} = K (x_{i}, x_{j})

。

为了求解两个变量的二次计划问题，首先我们剖析束缚条件，可以看出 $α_{1}$ 和 $α_{2}$ 的可行域是盒子内的一条对角线上，其中盒子由不等式肯定，对角线由等式肯定，而且由于 $y_{1}$ 和 $y_{2}$ 的不肯定性致使存在两种情形：

至于对角线的地位取决于当前 $α_{1}$ 和 $α_{2}$ 的值。由于优化进程中，我们首先优化的是 $α_{2}$ ，而后由等式束缚肯定 $α_{1}$ ，所以我们剖析 $α_{2}$ 的变更规模：

当 $y_{1} \neq y_{2}$ 时： $L = m a x (0, α_{2} - α_{1})$ ， $H = m i n (C, C + α_{2} - α_{1})$

当 $y_{1} = y_{2}$ 时： $L = m a x (0, α_{2} + α_{1} - C)$ ， $H = m i n (C, α_{2} + α_{1})$

其中L是为了保证 $α_{2}$ 的变更不会让 $α_{1} < 0$ ，H是为了保证 $α_{2}$ 的变更不会让 $α_{1} > C$ 。

一样，由于我们首先优化的是 $α_{2}$ ，所以我们采取 $α_{2}$ 来表现 $α_{1}$ ：

$α_{1} = \frac{(ς - α_{2} y_{2})}{y_{1}}$ ，代入 $min W (α_{1}, α_{2})$ 有（省略了推导步骤）：

W (α_{2}) = a α_{2}^{2} + b α_{2} + c

求导后得到：

\frac{▽ W (α_{2})}{α_{2}} = \frac{y_{2} (((g (x_{2}) - y_{2}) - (g (x_{1}) - y_{1})))}{(K_{11} + K_{22} - 2 K_{12})}

记

E_{i} = g (x_{i}) - y_{i}

，

η = (K_{11} + K_{22} - 2 K_{12})

有：

\frac{▽ W (α_{2})}{α_{2}} = \frac{y_{2} (E_{2} - E_{1})}{η}

所以：

α_{2}^{u n e w} = α_{2}^{o l d} + \frac{y_{2} (E_{1} - E_{2})}{η}

回到高低剪辑，终究

α_{2}

的更新值为：

α_{2}^{n e w} = {\begin{matrix} H, α_{2}^{u n e w} > H \\ α_{2}^{u n e w}, L \leq α_{2}^{u n e w} \leq H \\ L, α_{2}^{u n e w} < L \end{matrix}

再由

\sum_{i = 1}^{m} α_{i} y_{i} = 0

得：

α_{1}^{n e w} = α_{1}^{o l d} + y_{1} y_{2} (α_{2}^{o l d} - α_{2}^{n e w})

最后更新b，由KKT条件当

0 \leq α_{j} \leq C

时，有

b = y_{j} - \sum_{i = 1}^{m} α_{i} y_{i} K_{i j}

当 $0 \leq α_{1} \leq C$ 时：

b^{n e w} = y_{1} - \sum_{i = 1}^{m} α_{i} y_{i} K_{i 1} + α_{1}^{o l d} y_{1} K_{11} + α_{2}^{o l d} y_{2} K_{21} - α_{1}^{n e w} y_{1} K_{11} - α_{2}^{n e w} y_{2} K_{21} = - E_{1} - y_{1} K_{11} (α_{1}^{n e w} - α_{1}^{o l d}) - y_{2} K_{21} (α_{2}^{n e w} - α_{2}^{o l d}) + b^{o l d}

一样，当

0 \leq α_{2} \leq C

时：

b

由

α_{2}

来肯定。

如果二者同时满足条件时,那末二者肯定的 $b$ 是一致的，如果等式取到的话，解释点在支撑向量上或之内，此时 $b$ 取二者之间。

下面来看SMO的启示式搜索策略：

1）自动变量选择背背KKT条件最严重的点，即优先断定支撑向量上的点是不是满足KKT条件，其次检验全部训练样本是不是满足KKT条件

由上面对 $α$ 与样本点地位的剖析可得到以下关系：

α_{i} = 0 \Leftrightarrow y_{i} g_{i} \geq 1 0 \leq α_{i} \leq C \Leftrightarrow y_{i} g_{i} = 1 α_{i} = C \Leftrightarrow y_{i} g_{i} \leq 1

由上面关系，可以知道哪些点在支撑向量上，哪些点在支撑向量外，哪些点在支撑向量内，优先选择支撑向量上的点来断定是不是背背KKT条件，由于这些点是背背KKT条件最严重的点，也是对超平面最有价值的点。

2）被动变量选择在给定自动变量后，被动变量随之变更规模最大的点，由于前面导出 $α_{2}^{u n e w} = α_{2}^{o l d} + \frac{y_{2} (E_{1} - E_{2})}{η}$ 所以被动变量选择依附于 $| E_{1} - E_{2} |$ 的大小，选择最大的，加速盘算速度。

3）值得注意的是，每次迭代更新 $α_{1}^{n e w}$ 和 $α_{2}^{n e w}$ 以后，须要更新 $E_{1}^{n e w}$ 和 $E_{2}^{n e w}$ 。

支撑向量机回归

支撑向量机回归应用的就是Hinge丧失来定义目的函数，一样是线性模型 $h_{θ} (x) = θ^{T} x$ ，由Hinge丧失定义以下目的函数：

min_{θ} C \sum_{i = 1}^{m} L_{ϵ} (h_{θ} (x^{i}) - y^{i}) + λ | | w | |^{2}

其中

L_{ϵ} (z) = {\begin{matrix} 0, | z | \leq ϵ \\ | z | - ϵ, o t h e r \end{matrix}

，可以看出支撑向量机回归其实就是借用Hinge丧失，而其理论解释值得思考。

丧失函数加正则项的一般懂得

机器学习模型中，绝大多数的模型可以懂得丧失函数加正则项的情势，本篇文章从线性到非线模型中提到的所有模型都可以懂得为丧失函数加正则项：

\arg min_{w} L (w) + λ Ω (w) s . t .

其中正则项重要包含 0范数 1范数 2范数，丧失函数重要包含以下

平方丧失 $L (z) = (y - θ^{T} x)^{2}$ 线性回归

线性丧失 $L (z) = y - θ^{T} x$ 线性感知机

对数丧失 $L (z) = l o g (1 + e x p (- z))$ Logistic回归，softmax回归，

Hinge丧失 $L (z) = m a x (0, 1 - z)$ ，支撑向量机

指数丧失 $L (z) = e x p (- z)$ ，Adaboost

红：0-1丧失，蓝：线性丧失，绿：Hinge丧失，紫虚：对数丧失，青虚：指数丧失

如何选择适合的丧失函数加正则项是模型选择的一个依据，丧失函数的选择依附于数据的散布，而且不同的模型都有各自的特色，在选择模型时很难说那个模型优于其他模型，须要综合各方面因素选择。

总结：

矩阵运算弥补

正则项-范数

拉格让日乘子法与对偶问题弥补

拉格朗日乘子法通过引入松弛变量得到目的函数局部最优解的必要条件

拉格朗日乘子法的一般情势：

min_{x} f (x) s . t . g_{i} (x) \geq 0 h_{j} (x) = 0

引入松弛变量

w, v

也称拉格朗日乘子，朗格朗日函数以下：

min L (x, w, v) = f (x) - w_{i} g_{i} (x) - v_{j} h_{j} (x)

如果

\bar{x}

是目的函数的局部最优解，那末

\bar{x}

的一阶必要条件以下：

▽ L (x, w, v) = 0 w_{i} g_{i} (x) = 0 w_{i} \geq 0 g_{i} (x) \geq 0 h_{j} (x) = 0

其中

w_{i} g_{i} (x) = 0

为互补松弛条件,梯度为0条件由Frizt John条件得到。

一般来说，到拉格朗日乘子法以后我们还不能解出目的函数的局部最优解，由于目的函数还是一个引入松弛变量的带束缚优化问题。不过我们可以通过剖析拉格朗日函数的局部最优解来得到其对偶问题。

在给定 $x$ 时，对 $L (x, w, v)$ 求极大值时，当 $x$ 不满足所有必要条件时，那末必定致使 $L (x, w, v)$ 无最大值，当且仅当 $x$ 满足所有必要条件时 $L (x, w, v)$ 有极大值，且极大值为 $f (x)$

L = {\begin{matrix} f (x), x 满 足 必 要 条 件 \\ - \infty ， 否 则 \end{matrix}

所以，所有束缚条件的等价条件是

L (x, w, v)

存在极大值，所以原问题就变成了一个极小极大问题

min_{x} L (x, w, v) (s . t .) = min_{x} max_{w, v} L (x, w, v)

定义一个对偶问题，即定义一个用

w, v

变量来表现的目的函数：

θ_{D} (w, v) = min_{x} L (x, w, v)

最大化

θ_{D} (w, v)

即为原问题的对偶问题，下面证明对偶问题为原问题供给下界：

max_{x, v, w_{i} > 0} θ_{D} (w, v) = max_{w, v, w_{i} > 0} min_{x} L (x, w, v)

又由于：

max_{x, v, w_{i} > 0} min_{x} L (x, w, v) \leq min_{x} max_{w, v} L (x, w, v)

所以对偶问题为原问题供给下界。

从线性到非线性模型-支持向量机