[读书笔记]《西瓜书》第六章 支持向量机 铺垫
![[读书笔记]《西瓜书》第六章 支持向量机 铺垫](/images/machine-learning_huda146d3825fc6d502e05b38609bff098_23368_900x500_fit_q75_box.jpg)
第六章 支持向量机 铺垫
这个章节是被誉为机器学习第一道拦路虎的模型——支持向量机(support vector machine)，不过从原理上看这个章节并不难，也一下就能懂，但是其涉及到的知识就很难了~ 借用B站shuhuai008老哥在支持向量机视频讲解中说的一句话：”SVM有三宝：间隔、对偶、核技巧“。所以这个章节中，支持向量机也计划分为三个篇博文来进行阐述，主要是想引入一些自己学习过程中补充的知识当做笔记记录一下，具体的安排如下：”对偶篇“《凸优化问题》、”间隔篇“《支持向量机》、”核技巧“《核函数理解》。
最优化问题
最优化问题的讨论主要是在运筹学中第一次接触，但是当时还是本科生，我清晰的记得那时候上《微观经济学》这门课的时候还不是很上心，所以也没有认真学。导致现在还要时不时的子集补充一下里面的知识点内容，不过好在最近在查找一些凸优化处理的时候发现了一个上海财经大学的老师讲的视频课程，所以结合视频和子集搜集到的内容整理了这篇博文。
其实是最优化问题主要是运筹学中用的最多，其实主要是用数学+管理学的知识来对实际生产问题进行建模。那么什么是最优化问题，老师在视频中给了一个最一般话的介绍（定义）：最优化问题是决策问题，选择一些可以执行的策略来使得目标最优，一个最优化问题包括以下几个方面：决策变量；一个或多个目标函数；一个由可行策略组成的集合，可由等式或不等式进行刻画。
最一般的形式为：
通过不同的角度可以将最优化问题的基本形式划分成很多的类别：
- 无约束优化/有约束优化
- 线性/非线性优化
- 连续优化/离散优化
- 单目标优化/多目标优化
- 动态规划
- 随机规划
- 鲁棒优化
然后我们在支持向量机中需要讨论的凸优化问题其实就是最优化问题中非常重要的一类，也是被研究的很透彻的一类，因为凸优化问题的特性，使得我们最希望在机器学习的问题中，将想要求解的最终问题（大部分情形下为损失函数的表达形式）转化或者证明就是凸优化问题，则此问题就可以借助前人的工作得到一个很好的解决。
PS：显然梯度下降法也是最优化问题的无约束优化问题中的一种。
凸优化问题
接下来的内容摘自 SIGAI 知乎专栏 《理解凸优化》
在最优化问题中，借助导数的定义和公式，我们可以推导出
$x$ 是问题的一个最优解 => $x$ 点处的梯度等于0
但是梯度等于0知识取得极值的必要条件而不是充分条件，如果我们能将这个必要条件变成充分条件
$x$ 点处的梯度等于0 => $x$ 是问题的一个最优解
即如果我们能够对原始的最优化问题加以限定条件，使得问题得到简化，那么就可以保证上面的等式成立了，因此凸优化问题就被引出。
PS：这里引一下B站上海财经大学的崔老师的视频，配和上面那篇知乎的文章一起食用效果更佳
凸集
对于 $n$ 维空间中点的集合 $C$，如果对集合中的任意两点 $x$ 和 $y$，以及实数 $0 \le \theta \le 1$，都有： $$ \theta x + (1-\theta)y \in C $$ 则称该集合为凸集。如果把这个集合画出来，其边界是凸的，没有凹进去的地方。直观来看，把该集合中的任意两点用直线连起来，直线上的点都属于该集合。相应的，点： $$ \theta x + (1 - \theta)y $$ 称为点 $x$ 和 $y$ 的凸组合。下图是凸集和非凸集的示意图，左边是一个凸集，右边是一个非凸集：
机器学习中常见的一些凸集的例子：
$n$ 维是向量空间 $R^n$
如果 $x, y \in R^n$，则有：$\theta x + (1-\theta)y \in R^n$
这一结论的意义在于如果一个优化问题是不带约束的优化，则其优化变量的可行域是一个凸集。
仿射子空间
给定 $m$ 行 $n$ 列的矩阵 $A$ 和 $m$ 维向量 $b$，仿射子空间定义为如下向量的集合： $$ {x \in R^n: Ax = b} $$
这一结论的意义在于，如果一组约束是线性等式约束，则它确定的可行域是一个凸集。
多面体
多面体定义为如下向量的集合： $$ {x \in R^n: Ax \le b} $$ 它就是线性不等式围城的区域。
这一结论的意义在于，如果一组约束时线性不等式约束，则它定义的可行域是凸集。
此外还有一个重要的结论是：多个凸集的交集还是凸集。
这些内容在知乎的文章中都有证明，因为这里只是做支持向量机的前期知识铺垫准备的，所以就不摘录全部的证明过程了，希望看到上面👆证明的可以参见文末给出的链接
凸函数
在微积分中我们学习过凸函数的定义，下面来回忆一下。在函数的定义域内，如果对于任意的 $x$ 和 $y$ ，以及实数 $0 \le \theta \le 1$，都满足如下条件： $$ f(\theta x + (1- \theta)y) \le \theta $$ 则函数为凸函数。这个不等式和凸集的定义类似。从图向上看，一个函数如果是凸函数，那么它是向下凸出去的。用直线连接函数上的任何两个点 $A$ 和 $B$，线段 $AB$ 上的点都在函数的上方，如下图所示：
如果把上面不等式中的等号去掉，即： $$ f(\theta x + (1-\theta)y) < \theta f(x) + (1-\theta)f(y) $$ 则称函数是严格凸函数。凸函数的一阶判定规则为： $$ f(y) \ge f(x) + \nabla f(x)^{\text{T}}(y-x) $$ 其几何解释为函数在任何点处的切线都位于函数的下方。对于一元函数，凸函数的判定规则为其二阶导数大于等于0，即：$f'(x) \ge 0$。如果去掉上式的等号，则函数是严格凸函数。对于多元函数，如果它是凸函数，则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的，则函数是严格凸函数。
Hessian矩阵
Hessian矩阵是由多元函数的二阶偏导函数组成的矩阵。如果函数 $f(x_1, x_2, …, x_n)$ 二阶可导，Hessian矩阵定义为：
这是一个 $n$ 阶矩阵。一般情况下，多元函数的混合二阶偏导数与求导次序无关，即： $$ \frac{\partial^2f}{\partial x_i \partial x_j} = \frac{\partial^2f}{\partial x_j \partial x_i} $$ 因此Hessian矩阵是一个对称矩阵，它可以看作二阶导数对多元函数的推广。Hessian矩阵简写为 $\nabla^2f(x)$ 。对于如下多元函数： $$ f(x, y, z) = 2x^2 - xy + y^3 -3z^2 $$ 它的Hessian矩阵为：
根据多元函数极值判别法，假设多元函数在点 $M$ 的梯度为0，即 $M$ 是函数的驻点，则有：
- 如果Hessian矩阵正定，函数在该点有极小值
- 如果Hessian矩阵负定，函数在该点有极小值
- 如果Hessian矩阵不定，则不是极值点（鞍点）
这里可以看做是一元函数极值判别法对多元函数的推广，Hessian矩阵正定类似于二阶导数大于0，其他的以此类推。对于 $n$ 阶矩阵 $A$，对于任意非0的 $n$ 维向量 $x$ 都有： $$ x^{\text{T}}Ax > 0 $$ 则称矩阵 $A$ 为正定矩阵。判定矩阵正定的常用方法有一下几种：
- 矩阵的特征值全大于0
- 矩阵的所有顺序主子式都大于0
- 矩阵合同于单位阵 $I$
类似的，如果一个 $n$ 阶矩阵 $A$，对于任何非 0 的 $n$ 维向量 $x$，都有： $$ x^{\text{T}}Ax < 0 $$ 则称矩阵 $A$ 为负定矩阵。如果满足： $$ x^{\text{T}}Ax \ge 0 $$ 则称矩阵 $A$ 为半正定矩阵。
一个重要的结论是凸函数的非负线性组合是凸函数，假设 $f_i$ 是凸函数，并且 $W_i \ge 0$，则： $$ f(x) = \sum_{i=1}^k w_i f_i(x) $$ 是凸函数。
凸优化
有了凸集和凸函数的定义之后，我们就可以给出凸优化的定义。如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。凸优化问题可以形式化的写成：
$$
\min f(x) \quad \text{s.t.} \quad x \in C
$$
其中 $x$ 为优化问题，$f$ 为凸目标函数，$C$ 是优化变量的可行域，是一个凸集。凸优化问题的另一种通用的写法是：
$$
\begin{align}
& \min f(x) \\
\text{s.t.} & \quad g_i(x) \le 0, i=1,…,m \\
& \quad h_i(x) = 0, i=1,…,p
\end{align}
$$
其中 $g_i(x)$ 是不等式约束函数，为凸函数；$h_i(x)$ 是等式约束函数，为仿射函数。上面的定义中不等式的方向非常重要，因为一个凸函数的 0-下水平集 是凸集。因此这些不等式共同定义的可行域是一些凸集的交集，仍然为凸集。通过将不等式两边同时乘以-1，可以保证把不等式写成小于号的形式。前面已经证明仿射空间是凸集，因此加上这些等式约束后可行域还是凸集。
求解方法
其实对于凸优化问题的求解算法很多，之前《第五章 神经网络 铺垫》那篇博文中的梯度下降法就是其中一种，其他的还有牛顿法，拟牛顿法，共轭梯度法等。这些都暂时还用不上，所以暂时不用补充进来，优先补充进来的就是拉格朗日乘对偶法。
PS：以下博文内容主要来自 SIGAI 的知乎文章《用一张图理解SVM的脉络》
在西瓜书第六章节支持向量机的求解过程中，其对应的求解过程就是使用拉格朗日对偶法求解的最终结果。
最简单的SVM从线性分类器导出，根据最大化分类间隔的目标，我们可以得到线性可分问题的SVM训练时求解的问题。但现实应用中很多数据是线性不可分的，通过加入松弛变量和惩罚因子，可以将SVM推广到线性不可分的情况，具体做法是对违反约束条件的训练样本进行惩罚，得到线性不可分的SVM训练时优化的问题。这个优化问题是一个凸优化问题，并且满足Slater条件，因此强对偶成立，通过拉格朗日对偶可以将其转化成对偶问题求解。
到这里为止，支持向量机还是一个线性模型，只不过允许有错分的训练样本存在。通过核函数，可以将它转化成非线性模型，此时的对偶问题也是一个凸优化问题。这个问题的求解普遍使用的是SMO算法，这是一种分治法，它每次选择两个变量进行优化，这两个变量的优化问题是一个带等式和不等式约束条件的二次函数极值问题，可以求出闭式解，并且这个问题也是凸优化问题。优化变量的选择通过KKT条件来确定。
拉格朗日乘子法
在大学的时候学过的微积分中学过对于既有等式约束又有不等式约束的问题求解时，我们可以采用拉格朗日乘子法来进行求解。
对于凸优化问题的通式来说：
$$
\begin{align}
& \min f(x) \\
\text{s.t.} & \quad g_i(x) \le 0, i=1,…,m \\
& \quad h_i(x) = 0, i=1,…,p
\end{align}
$$
与之对应的拉格朗日乘子函数为：
$$
L(x, \lambda, \mu) = f(x) + \sum_{j=1}^p \lambda_jh_j(x) + \sum_{k=1}^q\mu_kg_k(x)
$$
这其中 $\lambda_j，\mu_k$ 称为拉格朗日乘子。最优解为 $\boldsymbol{x}^*$ ，且这个解必须同时满足如下条件：
$$
\begin{align}
h_j(\boldsymbol{x}^*) = 0 \\
g_k(\boldsymbol{x}^*) \le 0 \\
\nabla_x L(\boldsymbol{x}^*) = 0 \\
\lambda_j \neq 0 \\
\mu_k \ge 0 \\
\mu_kg_k(\boldsymbol{x}^*) = 0 \\
\end{align}
$$
除了原来应该满足的等式约束和不等式约束之外，唯独多了一个 $\mu_kg_k(\boldsymbol{x}^*) = 0$ 这一个条件。
拉格朗日对偶法
知道拉格朗日乘子法之后，对偶则是其一种求解手段，它将一个优化问题转化为另一个更容易求解的问题，这两个问题是等价的。常见的对偶有拉格朗日对偶、Fenchel对偶。
采用同样的方式构造拉格朗日函数： $$ L(x, \lambda, \mu) = f(x) + \sum_{j=1}^p \lambda_jh_j(x) + \sum_{k=1}^q\mu_kg_k(x) $$ 同样这其中 $\lambda_j，\mu_k$ 称为拉格朗日乘子，但不同的是 $\lambda_j$ 必须满足 $\lambda_j \ge 0$ 的约束。接下来将上面的问题转化为如下所谓的原问题的形式，其最优解为： $$ p^* = \min_x \max_{\lambda,\mu} L(x, \lambda, \mu) $$ 等式右边的含义是先固定住变量 $x$ ，将其看成常数，让拉格朗日函数对乘子变量 $\lambda，\mu$ 求最大值。消掉这两组变量之后，再对变量 $x$ 求最小值。
而对偶问题与其最优解为： $$ d^* = \max_{\lambda,\mu} \min_{x} L(x,\lambda,\mu) $$ 与上面的做法相反，这里是先固定拉格朗日乘子，调整 $x$ 让拉格朗日函数对 $x$ 求极小值，然后再调整拉格朗日乘子对函数求极大值。
PS：当然这里有很严谨的证明，但是参考的这篇文章没有给出，同样我个人也建议现阶段略过
原问题和对偶问题只是改变了求极大值和极小值的顺序，每次操控的变量是一样的。如果原问题和对偶问题都存在最优解，则对偶问题的最优值不大于原问题的最优值，即： $$ d^* = \max_{\lambda,\mu} \min_{x} L(x,\lambda,\mu) \le \min_x \max_{\lambda,\mu} L(x, \lambda, \mu) $$ 这称为弱对偶问题，原问题最优值与对偶问题最优值的差 $p^* - d^*$ 称为对偶间隙。如果原问题和对偶问题有相同的最优解，我们就可以把求解原问题转化为求解对偶问题，这称为强对偶。强对偶成立的一种前提条件是Slater条件。
Slater条件指出，一个凸优化问题如果存在一个候选 $x$ 使得所有不等式约束都严格满足，即对于所有的 $i$ 都有 $g_i(x) < 0$ （注意这里不等式不取等号）。则存在 $x^, \lambda^,\mu^$ 使得它们分别为原问题和对偶问题的最优解，并且： $$ p^ = d^* = L(x^*, \lambda^*, \mu^*) $$ Slater条件是强对偶成立的充分条件而不是必要条件。强对偶的意义在于：我们可以将求原问题转化为求对偶问题，有些时候对偶问题比原问题更容易求解。强对偶只是将原问题转化成对偶问题，而这个对偶问题怎么求解则是另外一个问题。
PS：结合上面的知识点，我们可以得到Slater的一个性质，即原问题P可以等价于对偶问题D的一个充分条件，该条件确保了鞍点的存在。
K.K.T. 条件
通过上面👆的内容，我们知道了Slater条件是使强对偶成立的充分非必要条件，那么我们如何在确保使用Slater条件求出的鞍点就是我们期望的最优解呢？这个时候就需要 K.K.T.条件。
K.K.T. 条件可以描述为一下三个条件 $$ g_i(x) \le 0 \quad i=1,2,…,p \qquad \text{and} \qquad h_j(x) = 0 \quad j=1,2,…,q $$
第一个约束条件表明：最优点 $x$ 必须满足所有等式及不等式限制条件，也就是说最优点必须是一个可行解，这一点也是我们所有目标拉格朗日函数的目标前提
$$ \nabla f(x^*) + \sum_{i=1}^p \alpha_i \nabla g_i(x^*) + \sum_{j=1}^q \beta_j \nabla h_j(x^*) = 0 $$
第二个约束条件表明：在最优点 $x$，$\nabla f$ 必须是 $\nabla g_i$ 和 $\nabla h_j$ 的线性组合
$$ \beta_j \neq 0 \quad \text{and} \quad \alpha_i \ge 0 \quad \text{and} \quad \alpha_i g_i(x^*) = 0 \quad i=1,2,…,p $$
第三个约束条件表明：拉格朗日乘子不等式的一些限制，对于不等式的拉格朗日乘子限制条件有方向性，所以每一个 $\alpha$ 都必须大于或等于零，而等式限制条件没有方向性，只是 $\beta$ 不等于 0。
![[读书笔记]《西瓜书》第五章 神经网络 补充六](https://cdn.jsdelivr.net/gh/Ryuchen/ryuchen.github.io@master/images/machine-learning_huda146d3825fc6d502e05b38609bff098_23368_700x350_resize_q75_box.jpg)