是一种二分类模型，SVM 和感知机一样，也会找到一个将样本分类的超平面，感知机：只要求能把样本分开，不管你分得多紧。SVM：不仅要分开，还要“分得最开”（即最大化边界间隔）。自然SVM模型的学习策略就是间隔最大化
该平面距离两个类别的最近样本最远
超平面（回顾）
支持向量机（SVM）中，w是定义分类超平面的权重向量，也可以叫做法向量（normal vector）。它决定了超平面的位置和方向。
SVM 中的分类超平面由以下方程定义： \(w^Tx + b = 0\)
- x：输入样本（特征向量）
- w：权重向量，超平面的法向量（垂直于超平面）
- b：偏置项（bias），控制超平面距离原点的远近
这条超平面将数据空间分成两个区域，对应于两个类别（正类和负类）：
- \(w^Tx + b > 0\)：预测为正类 (+1)
- \(w^Tx + b < 0\)：预测为负类 (-1)
函数间隔和几何间隔
函数间隔 (Functional Margin)-确信度
定义： 对于一个样本点 \((x_i, y_i)\)，假设超平面由 w 和 b 定义，即 \(f(x)=w^Tx + b\)，那么这个点的函数间隔定义为： \(\hat{\gamma}_i = y_i(w^Tx_i + b)\)
函数间隔（functional margin）是支持向量机（SVM）中用来衡量：一个样本点离分类器远不远、分类对不对
解释：
- \(y_i \in \{+1, -1\}\)，表示真实类别；
- \(w^Tx_i + b\) 是模型对样本 \(x_i\) 的预测结果（未经过激活函数）；
- 所以 \(y_i(w^Tx_i + b)\) 是预测结果的正确性和确信度(符号是否一致)：
- 如果结果是正数，说明预测正确；
- 如果值越大，说明分类 “更有把握”；
- 如果是负的，说明分类错误。
注意：函数间隔受 w 的缩放影响。你把 w 和 b 同时乘以一个数，函数间隔也会变大，但实际上超平面并没有 “真正改变”。
几何间隔 (Geometric Margin)
定义： 几何间隔是样本点 \(x_i\) 到超平面的 “真正的几何距离”，定义为： \(\gamma_i = \frac{y_i(w^Tx_i + b)}{\|w\|}\)
解释：
- 分子是函数间隔；
- 分母是权重向量 w 的范数；
- 这就把函数间隔 “标准化” 了，去除了缩放影响；
- 几何间隔才是真正衡量点到超平面的距离。
总结
| 概念 | 定义公式 | 是否真实距离 | 是否受 w缩放影响 |
|---|---|---|---|
| 函数间隔 | yi(wTxi+b) | ❌ 不是距离 | ✅ 受影响 |
| 几何间隔 | ∥w∥yi(wTxi+b) | ✅ 是距离 | ❌ 不受影响 |
如果 \(\|w\| = 1\)，那么函数间隔和几何间隔相等。如果超平面参数 w 和 b 成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。
间隔最大化
线性可分离的超平面有无穷多个但是间隔最大的分离超平面是唯一的。对训练数据集找到几何间隔最大的超平面意味着不仅将正负实例点分开，而且对最难分的实例点也有足够大的确信度将其分开，求最大间隔分离超平面可以转化为以下约束最优化问题：
- w,b 按照比例变化，γ ̂也按照比例变化；
- γ ̂的变化对结果没有影响；
支持向量和间隔边界
支持向量(Support vector)：分离超平面距离最近的样本点。支持向量是约束条件式等号成立的点。
间隔(margin)：支持向量之间的距离，间隔以来于分离超平面的法向量w，等于2/||w||
间隔边界：距离分类超平面（决策边界）最远、且仍接触支持向量的两条平行边界线
例：
数据与例 2.1 相同。已知一个如图 7.4 所示的训练数据集，其正例点是\(x_1=(3,3)^{\mathrm{T}}\)，\(x_2=(4,3)^{\mathrm{T}}\)，负例点是\(x_3=(1,1)^{\mathrm{T}}\)，试求最大间隔分离超平面。
解 ：按照算法 7.1，根据训练数据集构造约束最优化问题： \(\begin{align*} \min_{w,b}&\frac{1}{2}(w_1^2 + w_2^2)\\ \text{s.t.}&\ 3w_1 + 3w_2 + b\geq1\\ &4w_1 + 3w_2 + b\geq1\\ & – w_1 – w_2 – b\geq1 \end{align*}\) 求得此最优化问题的解\(w_1 = w_2=\frac{1}{2}\)，\(b = – 2\)。于是最大间隔分离超平面为 \(\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2 = 0\) 其中，\(x_1=(3,3)^{\mathrm{T}}\)与\(x_3=(1,1)^{\mathrm{T}}\)为支持向量。
凸优化问题和KKT条件
凸优化问题：一个目标函数是凸函数，并且约束条件（等式/不等式）也构成凸集的优化问题
把优化问题看成“找最低点”的过程：
- 凸优化：目标函数像碗的形状，无论从哪里出发，最终都能走到唯一的最低点（最优解）
- 非凸优化：像“山谷+山峰”，可能有多个局部最小值，不好找全局最优
满足 KKT 条件意味着一定是最优解（在凸优化问题中），KKT 条件是最优解的充分必要条件（对 SVM 这类问题来说）
硬间隔线性SVM学习的对偶算法
常常被用于约束最优化问题中，通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，被用在最大熵模型和支持向量机等许多统计学习方法中
这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。
这一步的目标是将原始问题转换为仅关于 α的问题（也叫“对偶问题”）,做题时，我们直接解决对偶问题，不需要再对目标函数对w和b求偏导，事实上，此时的目标函数因为刚对w和b求偏导得来，已经没有w和b。所以我们需要对目标函数求关于\(alpha\)的偏导数
- N：样本数量（训练集中总的样本数）
- yi,yj：第 i个和第 j 个样本的类别标签（取值为 +1 或 -1）
限制条件解释：
- 样本的权重αi乘以类别标签yi加起来必须等于 0
- 每个拉格朗日乘子（αi\alpha_iαi）必须是非负数。
解原始问题 (7.13)~(7.14) 可以转换为求解对偶问题 (7.22)~(7.24) 。
例题：
当目标函数的极小值点不在这个区域内时，最优解必然会出现在边界上。
线性SVM与软间隔最大化
线性支持向量机
松弛变量ξi
惩罚参数C
设问题 (7.32)~(7.34) 的解是 \(w^*\)，\(b^*\)，于是可以得到分离超平面 \(w^*\cdot x + b^* = 0\) 及分类决策函数 \(f(x)=\text{sign}(w^*\cdot x + b^*)\)。称这样的模型为训练样本线性不可分时的线性支持向量机，简称为线性支持向量机。
软间隔 SVM(线性可分/不可分)的对偶算法
支持向量
线性不可分时为什么变复杂了？因为我们允许了“违约”，即：
- 一些点可以不满足函数间隔 ≥ 1
- 有些点甚至可以被误分类
这是通过引入松弛变量 ξi实现的。
软间隔 SVM 的支持向量定义变为：只要 αi∗>0，该样本就是支持向量（无论它是否落在间隔边界上）
从图上来说线性SVM的支持向量可以出现在间隔边界上或之间的任何位置
- 在间隔边界上
- 落在间隔与分界面之间
- 被分错（甚至在分界面另一侧）
图 7.5 所示，这时的支持向量要比线性可分时的情况复杂一些。图中，分离超平面由实线表示，间隔边界由虚线表示，正例点由 “○” 表示，负例点由 “×” 表示。图中还标出了实例 \(x_i\) 到间隔边界的距离 \(\frac{\xi_i}{\|w\|}\)。
合页损失函数(SVM的另一种解释)
推导：
非线性SVM与核函数
非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题。对图 7.7 所示的例子，通过变换，将左图中椭圆变换成右图中的直线，将非线性分类问题变换为线性分类问题。
用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。
核函数定义
核技巧（Kernel trick ）的想法是，在学习与预测中只定义核函数\(K(x,z)\)，而不显式地定义映射函数\(\phi\)。通常，直接计算\(K(x,z)\)比较容易，而通过\(\phi(x)\)和\(\phi(z)\)计算\(K(x,z)\)并不容易。注意，\(\phi\)是输入空间\(\mathbf{R}^n\)到特征空间\(\mathcal{H}\)的映射，特征空间\(\mathcal{H}\)一般是高维的，甚至是无穷维的。
例题：核函数与映射函数的关系：——如何用核函数等价实现高维空间的内积运算
下面通过一个例子观察 核函数（Kernel Function） 与 映射函数（Feature Mapping） 的关系，以解释为什么“在高维空间做内积”的效果，可以通过“低维空间中的核函数”来实现
使用一个核函数： \(K(x,z)=(x\cdot z)^2\) 实际计算中并不显式地将x和z映射到高维空间，只通过核函数直接得到高维空间的内积结果。核技巧的核心：不显式求 ϕ(x)，直接用 K(x,z) 计算，节省计算并允许映射到无限维空间
假设输入空间是二维：\(x = (x^{(1)},x^{(2)})^{\mathrm{T}}\)，我们使用核函数： \(K(x,z)=(x\cdot z)^2\)
目标：找到一个映射\(\phi(x)\)，使得： \(K(x,z)=\phi(x)\cdot\phi(z)\) 也就是想找到一个函数\(\phi(x)\)，把二维x映射到高维空间，让高维空间的点积等于核函数的值。(答案不唯一)
公式中的x和z都是列向量，属于输入空间\(\mathbb{R}^2\)。
- \(x = \begin{pmatrix}x^{(1)}\\x^{(2)}\end{pmatrix}\in\mathbb{R}^2\)
- \(z = \begin{pmatrix}z^{(1)}\\z^{(2)}\end{pmatrix}\in\mathbb{R}^2\)
上标 (1)、(2)表示向量的分量（分量下标）
- \(x^{(1)}\)：表示向量x的第一个分量（第一个维度）
- \(x^{(2)}\)：表示向量x的第二个分量
所以\(x\cdot z\)是它们的标准点积（内积）： \(x\cdot z = x^{(1)}z^{(1)} + x^{(2)}z^{(2)}\in\mathbb{R}\)
\(\begin{align*} (x\cdot z)^2&=(x^{(1)}z^{(1)} + x^{(2)}z^{(2)})^2=(x^{(1)}z^{(1)})^2 + 2x^{(1)}z^{(1)}x^{(2)}z^{(2)}+(x^{(2)}z^{(2)})^2\\ &=x^{(1)^2}z^{(1)^2}+2x^{(1)}x^{(2)}z^{(1)}z^{(2)}+x^{(2)^2}z^{(2)^2}\\ &=[(x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2]\cdot[(z^{(1)})^2,\sqrt{2}z^{(1)}z^{(2)},(z^{(2)})^2] \end{align*}\)
容易验证：\(\phi(x)\cdot\phi(z)=(x\cdot z)^2 = K(x,z)\)
得出结论： 因此可以定义一个特征映射： \(\phi(x)=((x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2)^T\in\mathbf{R}^3\) 使得： \(\phi(x)\cdot\phi(z)=K(x,z)\)
同样： \(\phi(x)=\frac{1}{\sqrt{2}}((x^{(1)})^2 – (x^{(2)})^2,2x^{(1)}x^{(2)},(x^{(1)})^2 + (x^{(2)})^2)^{\mathrm{T}}\) \(\phi(x)=((x^{(1)})^2,x^{(1)}x^{(2)},x^{(1)}x^{(2)},(x^{(2)})^2)^{\mathrm{T}}\)
再次验证其内积：
\(\begin{align*} \phi(x)\cdot\phi(z)&=(x^{(1)}z^{(1)})^2 + x^{(1)}x^{(2)}z^{(1)}z^{(2)}+x^{(1)}x^{(2)}z^{(1)}z^{(2)}+(x^{(2)}z^{(2)})^2\\ &=(x^{(1)}z^{(1)})^2 + 2x^{(1)}x^{(2)}z^{(1)}z^{(2)}+(x^{(2)}z^{(2)})^2=(x\cdot z)^2 \end{align*}\)
它比第一个维度更高（4 维而不是 3 维）
核技巧在SVM中的应用
常用核函数
序列最小最优化算法（SMO）
SVM的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容易很大时，这些算法往往变得非常低效，以致无法使用。如何高效地实现SVM就成为一个重要问题。
序列最小优化算法（Sequential Minimal Optimization, SMO）是其中一种快速学习算法。可用于求解如下凸二次规划的对偶问题
SVM 就是在所有合法超平面中找那个“间隔最大”的，而 SMO 是帮我们一步步找出对应的 αi\alpha_iαi，从而构造出这个超平面。
SMO算法：SMO算法是一种启发式算法，基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么解就得到了。否则，选择两个变量，固定其它变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数变得更小。重要的是，这时子问题可以通过解析方法求解，就可以大大提高计算速度。
子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
整个SMO算法包括两个部分：
- 求解两个变量二次规划的解析方法
- 选择变量的启发式方法。
两个变量二次规划的求解方法
我们在数学上先不考虑“上下界（0 和 C）”，直接根据公式算出一组新的最优解，这个值叫做“未经剪辑的α₂。这是你“理想情况下”可以取的 α₂ 值，但它不一定落在合法区间 [0, C] 内。因为如果这个值超出了合法范围，就要“剪回”到范围内
\(alpha_1\)和\(alpha_2\)的关系，互相可推得
假设选择的两个变量为\(\alpha_1,\alpha_2\)，其他变量\(\alpha_i (i = 3,4,\cdots,N)\)是固定的，于是 SMO 最优化问题可以写成
其中ζ是常数，目标函数省略了不含α1,α2的常数项
由于只有两个变量，约束可以用二维空间中的图形表示：
目标函数所对应的优化问题中所包含的2个约束，艾尔法
