西瓜书阅读笔记——第6章-支持向量机(硬间隔6.1、6.2)

强烈推荐配合西瓜书阅读使用的南瓜书和南瓜书作者录制的学习视频【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导直播合集。

硬间隔支持向量机

模型

几何角度

找距离正负样本都最远的超平面，与感知机的区别，该模型的超平面解是唯一的，泛化性能更好，不偏不倚。

数学角度

点到超平面的距离公式：

支持向量support vector

距离超平面最近的这几个训练样本使得等式等号成立称为支持向量。

间隔margin

两个异类支持向量到超平面的距离之和。

几何间隔

模型

策略

由上面可推断，一个好的超平面，数据集\(X\)样本点中，距离该超平面几何间隔最小的样本点的几何间隔\(γ\)越大越好。

对于一般约束优化问题，希望以下表示：

最小化目标函数
将约束条件转化为\(g_i(·)≤0\)或\(h_i(·)=0\)的形式

于是，进一步将上式转化为： \[ \begin{align} \min_{\mathbf w,b}\space \frac{1}{2}||\mathbf w||^2 \\s.t. \space 1-y_i(\mathbf w^T\mathbf x_i+b)≤0,\space i=1,2,...,m \end{align} \] 此优化问题为含不等式约束的优化问题，且为凸优化问题。

凸优化问题

拉格朗日对偶可以求解一版的约束优化问题，支持向量机通常采用拉格朗日对偶来求解。

算法

拉格朗日对偶

对偶函数\(\Gamma (\mathbf μ,\mathbf λ)\)有两点重要的性质：

无论优化问题是否是凸优化问题，其对偶函数\(\Gamma (\mathbf μ,\mathbf λ)\)恒为凹函数。

证明1：对于确定的\(\mathbf x\)，\(L(\mathbf x,\mathbf μ,\mathbf λ)\)是仿射函数，仿射函数既是凸的也是凹的（二阶导=0），保凸运算中凸函数的逐点上确界还是凸的，凹函数的逐点下确界还是凹的。对偶函数为其下确界，所以是凹函数。

证明2：为什么拉格朗日对偶函数一定是凹函数(逐点下确界)
当\(\mathbf μ\succeq0\)，\(\Gamma (\mathbf μ,\mathbf λ)\)构成了上述优化问题最优值\(p^*\)的下界：\(\Gamma (\mathbf μ,\mathbf λ)≤p^*\)。

证明：

拉格朗日对偶问题

上面提到该优化问题中当\(\mathbf μ\succeq0\)，\(\Gamma (\mathbf μ,\mathbf λ)≤p^*\)，显然\(\Gamma (\mathbf μ,\mathbf λ)\)的最大值（\(d^*\)）\(≤\)上述优化问题最优值\(p^*\)，此时称为“弱对偶性”成立；而当\(d^*=p^*\)时，称为“强对偶性”成立。

也就是说，当“强对偶性”成立时，我们可以将上述优化问题（称为“主问题”）转化为：求满足\(\mathbf μ\succeq0\)约束条件下，对偶函数\(\Gamma (\mathbf μ,\mathbf λ)\)的最大值优化问题，该问题称为“拉格朗日对偶问题”： \[ \begin{align} \max \space \Gamma(\mathbf μ,\mathbf λ) \\s.t. \space\mathbf μ\succeq0 \end{align} \]

强对偶性成立的条件

当主问题满足某些充分条件时，强对偶性成立。常见的充分条件有Slater条件：“若主问题是凸优化问题，且可行集\(\widetilde D\)中存在一点能使得所有不等式约束的不等号成立，则强对偶性成立”。

转化为拉格朗日对偶问题有什么好处

无论主问题是否为凸优化问题，对偶问题恒为凸优化问题，因为对偶函数\(\Gamma (\mathbf μ,\mathbf λ)\)恒为凹函数（加个负号即可转为凸函数），约束条件\(\mathbf μ\succeq0\)恒为凸集。

KKT条件(Karush-Kuhn Tucker)

推导思路1：

综上，我们通过：支持向量机的主问题->拉格朗日函数->拉格朗日对偶函数->拉格朗日对偶问题，一系列转换，将求解主问题转化为先对拉格朗日函数求\(\mathbf x\)的偏导令其为0，带到拉格朗日对偶函数中求解出\(\mathbf μ,\mathbf λ\)，再带回求解\(\mathbf w,b\)得到超平面的解。

那么在本问题中，对拉格朗日函数求偏导：

接着，带回拉格朗日函数中，并考虑约束得到拉格朗日对偶问题，求解拉格朗日乘子：

求得拉格朗日乘子后，进一步求出\(\mathbf w,b\)可得到模型：

上述过程满足的KKT条件：

推导思路2：

为什么支持向量机通常都采用拉格朗日对偶求解呢？

无论主问题是何种优化问题，对偶问题恒为凸优化问题，因此更容易求解（尽管支持向量机的主问题本就是凸优化问题），而且原始问题的时间复杂度和特征维数呈正比（因为未知量是\(\mathbf w\)，维度=特征维度\(N\)），而对偶问题和数据量成正比（因为未知量是\(\mathbf α\)，维度=样本维度\(m\)），当特征维数远高于数据量的时候拉格朗日对偶更高效；

对偶问题能很自然地引入核函数，进而推广到非线性分类问题（最主要的原因）。