参考了西瓜书，《机器学习》周志华
背景
在超平面（比如三维立体，甚至更高维）上，找到一个分类面
\[\boldsymbol{w}^T \boldsymbol{x} + b = 0 \]看起来很陌生，其实直线方程和 \(Ax + By + C = 0\) 一个道理，只不过拓展到了高维，另外注意这里的 \(\boldsymbol{x}\) 是指一个高维变量
使得分类面上方都是正例（\(y = +1\)），下方都是反例（\(y = -1\)）
支持向量机
如果止步于此，就只是普通的线性模型罢了，而接下来引出支持向量最重要的特性——稀疏性
样本到分类面距离为
\[|r| = \frac{\boldsymbol{w}^T \boldsymbol{x} + b}{||\boldsymbol{w}||} \]其中，分母的符号是向量二范数，即向量的欧几里得距离，也就是向量取模，另外注意这里的 \(\boldsymbol{x}\) 是指一个样本
同直线方程一样，参数等比例放缩时，方程本质不变，即所代表的分类面不变，那么不妨让距离分类面最近的点 \(\boldsymbol{x}_p\) 的分母部分值最小（类似单位化，只不过我们平常的单位化都是把分母置为 \(1\) ），即 \(\boldsymbol{w}^T \boldsymbol{x}_p + b = \pm 1\)，则有
\[y_i \cdot (\boldsymbol{w}^T \boldsymbol{x}_i + b) \geq 1 \]注意这里 \(\boldsymbol{x}_i\) 是指第 \(i\) 个样本点，\(y_i\) 是正反例的取值
显然，我们要让样本离分类面尽可能远，\(|r|\) 尽可能大，那么分母就要尽可能小
则问题就变成了
\[\begin{aligned} \min_{\boldsymbol{w},b}\ \ &\frac{1}{2} ||\boldsymbol{w}||^2\\ \text{s.t.}\ \ &y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \geq 1 \end{aligned} \]注意，系数 \(\frac{1}{2}\) 是为了之后求导化简方便，选择平方是为了省去二范数的开根并且保证单调性不变（都是非负的）
显然，该问题是凸优化问题，可以用现成的凸二次规划算法解决，但是还有一种性能更优的算法，需要以此引出对偶问题
拉格朗日乘数法
与线性判别分析 LDA 类似，对约束下的凸优化问题，采用拉格朗日乘数法
首先化成目标函数取最小，约束条件小于等于 0 的一般形式，然后左边乘上拉格朗日乘子
\[\begin{aligned} L(\boldsymbol{w},b;\boldsymbol{\alpha}) &= \frac{1}{2}||\boldsymbol{w}||^2 + \sum_{i=1}^m\alpha_i \cdot g(\boldsymbol{x}_i)\\ &= \frac{1}{2}||\boldsymbol{w}||^2 + \sum_{i=1}^m\alpha_i\big(1-y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)\big) \end{aligned} \]再次提醒，其中 \(\boldsymbol{x}_i\) 不是变量，是样本数据，是已知量，\(\boldsymbol{w},b\) 是待优化参数，\(\boldsymbol{\alpha}\) 是拉格朗日乘子
仅此转化，问题还不等价，因为拉格朗日乘子法针对的是等式约束，而这里是不等式约束，还需要满足 KKT 条件：
\[\left\{ \begin{aligned} &g(\boldsymbol{x}_i) \leq 0\\ &\alpha_i \geq 0 \\ &\alpha_i \cdot g(\boldsymbol{x}_i) = 0 \end{aligned} \right. \]最主要的就是第三个条件，要么 \(\alpha_i = 0\)，要么 \(g(\boldsymbol{x}_i) = 0\)，前者即代表最优解不在等式约束上（即在 \(g(\boldsymbol{x}_i) < 0\) 内有最优解），后者表示最优解在等式约束上，即此时不等式约束取等了，此时的 \(\boldsymbol{x}_i\) 即为所谓支持向量
不难看出，这相当于我们找出了 \(\alpha_i\) 不等于 0 的项作为约束条件，去空间上找到 \(\boldsymbol{w},b\) 使得原函数取得最小值的解
这便是支持向量机最大的特点——稀疏性
偏导
接下来，将 \(L(\boldsymbol{w},b;\boldsymbol{\alpha})\) 分别对 \(\boldsymbol{w}, b\) 求偏导得
\[\begin{aligned} L(\boldsymbol{w},b;\boldsymbol{\alpha}) &= \frac{1}{2}\boldsymbol{w}^T I\boldsymbol{w} + \sum_{i=1}^m (\alpha_i - \alpha_iy_i \boldsymbol{x}_i^T \boldsymbol{w} - \alpha_iy_ib) \\ \frac{\partial}{\partial \boldsymbol{w}} L(\boldsymbol{w},b;\boldsymbol{\alpha}) &= I\boldsymbol{w} - \sum_{i=1}^m \alpha_iy_i\boldsymbol{x}_i \\ &= \boldsymbol{w} - \sum_{i=1}^m \alpha_iy_i\boldsymbol{x}_i \end{aligned} \]注意这里 \(I\) 表示单位阵，这里做了两个转换，一个是向量二范数的等价形式，展开计算一下就能理解，另一个是我自己看的比较舒服的，把变量放到最后的形式，求导利用了两个公式
\[\begin{aligned} \frac{\partial}{\partial \boldsymbol{w}} \boldsymbol{w}^T \boldsymbol{x} = \frac{\partial}{\partial \boldsymbol{w}} \boldsymbol{x}^T \boldsymbol{w} &= \boldsymbol{x} \\ \frac{\partial}{\partial \boldsymbol{w}} (\boldsymbol{Aw}+\boldsymbol{u})^T\boldsymbol{B} (\boldsymbol{Aw}+\boldsymbol{u}) &= 2\boldsymbol{AB}(\boldsymbol{Aw} + \boldsymbol{u}) \end{aligned} \]同理对 \(b\) 求导（一维变量求导不过多赘述），令二者等于 0，得
\[\begin{aligned} \boldsymbol{w} &= \sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i \\ 0 &= \sum_{i=1}^m \alpha_i y_i \end{aligned} \]回代入原式得
\[\begin{aligned} L(\boldsymbol{w},b;\boldsymbol{\alpha}) &= \frac{1}{2}\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i^T \sum_{j=1}^m \alpha_j y_j \boldsymbol{x}_j + \sum_{i=1}^m \alpha_i - \sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i^T \sum_{j=1}^m \alpha_j y_j \boldsymbol{x}_j \\ &= \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j \end{aligned} \]对偶问题转化
\[\inf_{\boldsymbol{w}^*,b^*} L(\boldsymbol{w}^*,b^*;\boldsymbol{\alpha}) \leq L(\boldsymbol{w}^*,b^*;\boldsymbol{\alpha}) \leq \frac{1}{2}||\boldsymbol{w^*}||^2 \]inf 表示下确界 infimum，\(\boldsymbol{w}^*,b^*\) 表示，最后一个不等式放缩掉了约束项（必定小等于 0）
注意最左边对于 \(\boldsymbol{w},b\) 来说是与其无关的"常量"，而与 \(\boldsymbol{\alpha}\) 有关的"变量"
可以理解为，对于一个二次函数，找到一条平行于 x-axis 的直线 y=b 不断向上移动，触碰到这个二次函数的最底部时，取得不等式的相等条件，即优化参数 \(\boldsymbol{\alpha}\) 使得 \(L(\boldsymbol{\alpha};\boldsymbol{w}^*,b^*)\) 最大
\[\begin{aligned} \max _{\boldsymbol{\alpha}}\ & L(\boldsymbol{\alpha};\boldsymbol{w},b) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j \\ \text{s.t.}\ & \sum_{i=1}^m y_i \alpha_i = 0 \\ & \alpha_i \geq 0 \end{aligned} \]解出 \(\boldsymbol{\alpha}\) 后即可求出 \(\boldsymbol{w},b\)，此时可以舍去 \(\alpha_i = 0\) 的样本，很好地体现了 SVM 的稀疏性
注意 \(b\) 的求解方法是，将 \(\boldsymbol{w}\) 代入方程 \(y_i = \boldsymbol{w}^T + b\)
但是解参数的过程中 \(\boldsymbol{\alpha}\) 是正比于样本数的，直接用二次优化反而使得问题更加复杂，实际过程中一般使用 SMO 迭代优化
SMO
类似线性方程组求解，超越方程求解的迭代法，求取一个近似解
首先确定一个初值 \(\boldsymbol{\alpha}\)，然后取出一对待更新变量 \(\alpha_i, \alpha_j\) ，原先的优化目标函数就具有如下形式
\[\begin{aligned} f(\alpha_i, \alpha_j) = P\alpha_i + Q\alpha_j + R\alpha_i\alpha_j + S \end{aligned} \]由 \(0 = \sum_{i=1}^m \alpha_i y_i\)
\[y_i \alpha_i + y_j \alpha_j = - \sum_{k \neq i, k \neq j} y_k \alpha_k \]则原优化目标变成一个只与 \(\alpha_i\) 有关的二次优化问题，但是要注意 \(\alpha_i, \alpha_j \geq 0\) 的约束，或者说定义域
直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。于是，SMO 先选取违背 KKT 条件程度最大的变量，第二个变量应选择一个使目标函数值减小最快的变量，但由于比较各变量所对应的目标函数值减幅的复杂度过高，因此 SMO 采用了一个启发式：使选取的两变量所对应样本之间的间隔最大
此时，可解得 \(\boldsymbol{w}\)，为了增强模型鲁棒性，\(b\) 的一般取对每个支持向量解出的值的平均
核函数
为了将问题拓展到非线性空间，总是可以通过增加维数（当然可以不增加，甚至减少，比如 LDA）来将非线性分类问题映射到更高维的空间，使得问题在这个更高维度的空间线性可分，比如对异或问题 \(x_1 \oplus x_2\) 增加第三维度 \(x_1 x_2\)
最终，其实就是把样本 \(x_i\) 的 m 维数据拓展为 \(\phi(x_i)\) 的 n 维数据，分类面变为
\[\boldsymbol{w} \phi(\boldsymbol{x}_i) + b = 0 \]注意到，此时大部分公式基本无差，只是 \(\boldsymbol{x}_i\) 变为 \(\phi(\boldsymbol{x}_i)\)，但是有个关键地方
\[\begin{aligned} L(\boldsymbol{w},b;\boldsymbol{\alpha}) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j) \end{aligned} \]这里，我们记
\[\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j) = \phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j) \]并称之为核函数，而对于每一对 \(i,j\)，都有一个运算结果（标量），把这些标量按下标放入矩阵，即得到核矩阵
显然，从物理意义上出发，两个参数是对称的，或者说可交换位置的，故核矩阵是对称的。以及，本身向量内积某种程度上反映了两个向量的相似程度，主对角线上元素显然是较大的。此外，核矩阵运算结果是半正定的。
事实上，对于一个半正定核矩阵，总能找到一个与之对应的 \(\phi\)，换言之，任何一个核函数都隐式地定义了一个称为 Reproducing Kernel Hilbert Space 的特征空间
那么如何构造核函数？答案是比较困难，一般有几个现成的核函数，其中高斯核与线性核最常用
软间隔
待施工
标签：frac,函数,推导,sum,boldsymbol,alpha,aligned,向量 From： https://www.cnblogs.com/LacLic/p/17449201.html