AI Club讲义 硬间隔 SVM （入门）

向量 (Vector) 基础

向量是一个有“方向”和“大小”的对象，数学上表示为一个有序数组

$$\vec{v}=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]\in {\mathbb{R}}^n$$

基础运算

• 加法：逐元素相加：

$$\vec{a}+\vec{b}=\left[\begin{array}{c}{a}_1+b_1\\ a_2+b_2\end{array}\right]$$

• 数量乘（数乘向量）：每个元素都乘上一个常数 $k$：

$$k\cdot \vec{a}=\left[\begin{array}{c}k{a}_1\\ k{a}_2\end{array}\right]$$

范数 (Norm) $|w|$ 与归一化 (Normalization)

范数是衡量向量“大小”或“长度”的函数，不同范数有不同的“测量方式”

$L_p$ 范数的一般形式

$\Vert \vec{x}{\Vert }_p={\left({\sum }_{i=1}^n|x_i{|}^p\right)}^{1/p}$

$L_1$ 范数（曼哈顿距离 / 稀疏范数）

$$\Vert \vec{x}{\Vert }_1=\sum _{i=1}^n|x_i|$$

• 每一维的绝对值直接加起来
• 在几何上是“走街区”的距离（Manhattan Distance）
• 在机器学习中常用于稀疏性建模（L1正则化），例如 Lasso 回归

L2 范数（欧几里得距离 / 向量长度）

$$\Vert \vec{x}{\Vert }_2=\sqrt{\sum _{i=1}^n{x}_i^2}$$

• 最自然的“直线长度”
• 是我们默认理解的向量“大小”
• 在 SVM、最小二乘回归中广泛应用（如 Ridge Regression）

$L_{\infty }$ 范数（最大范数（Max Norm）或切比雪夫距离（Chebyshev Distance））

$$\underset{p\to \infty }{\lim }\Vert \vec{x}{\Vert }_p=\underset{i}{\max }|x_i|=\Vert \vec{x}{\Vert }_{\infty }$$

• 向量中最大绝对值分量

越大的 $p$，范数对大分量的惩罚越大（更“极端”）

定义（L2范数）向量的“长度”：

$$\Vert \vec{w}\Vert =\sqrt{w_1^2+w_2^2+\cdots +w_n^2}$$

或者

$$\Vert \vec{x}{\Vert }_2=\sqrt{\sum _{i=1}^n{x}_i^2}$$

单位向量（归一化）

$$\hat{w}=\frac{w}{\Vert w\Vert }$$

内积运算

设 $\vec{a},\vec{b}\in {\mathbb{R}}^n$，$\theta$ 是它们之间的夹角。
代数定义的点积
$\vec{a}\cdot \vec{b}={\sum }_{i=1}^n{a}_i{b}_i$
几何定义的点积
$\vec{a}\cdot \vec{b}=\Vert \vec{a}\Vert \cdot \Vert \vec{b}\Vert \cdot \cos \theta$
从几何角度出发，引入单位向量
$\hat{a}=\frac{\vec{a}}{\Vert \vec{a}\Vert }，\hat{b}=\frac{\vec{b}}{\Vert \vec{b}\Vert }$
单位向量点积的几何定义是
$\hat{a}\cdot \hat{b}=\cos \theta$
另一方面
$\hat{a}\cdot \hat{b}=\left(\frac{\vec{a}}{\Vert \vec{a}\Vert }\right)\cdot \left(\frac{\vec{b}}{\Vert \vec{b}\Vert }\right)=\frac{\vec{a}\cdot \vec{b}}{\Vert \vec{a}\Vert \cdot \Vert \vec{b}\Vert }$
两边同时乘以 $\Vert \vec{a}\Vert \cdot \Vert \vec{b}\Vert$，得到
$\vec{a}\cdot \vec{b}=\Vert \vec{a}\Vert \cdot \Vert \vec{b}\Vert \cdot \cos \theta$

$$\left|\vec{v}\right|=\sqrt{v_1^2+v_2^2+\cdots +v_n^2}$$

• 内积（点积）：两个向量的“相似度”，也是几何角度的夹角关系：

$$\vec{a}\cdot \vec{b}=a_1{b}_1+a_2{b}_2+\cdots +a_n{b}_n=\Vert \vec{a}\Vert \Vert \vec{b}\Vert \cos \theta$$

正交 (Orthogonal)

$$\vec{a}\cdot \vec{b}=0$$

情况	结果	意义
$\vec{a}\cdot \vec{b}>0$	夹角小于90度	同方向有投影
$\vec{a}\cdot \vec{b}=0$	夹角为90度	正交（垂直）
$\vec{a}\cdot \vec{b}<0$	夹角大于90度	方向相反（反向）

性质	数学表达式	说明
交换律	$\vec{a}\cdot \vec{b}=\vec{b}\cdot \vec{a}$	次序无关
分配律	$\vec{a}\cdot (\vec{b}+\vec{c})=\vec{a}\cdot \vec{b}+\vec{a}\cdot \vec{c}$	向量加法上的分配性
数乘结合律	$(c\vec{a})\cdot \vec{b}=c(\vec{a}\cdot \vec{b})$	$c$ 是标量
正定性	$\vec{a}\cdot \vec{a}=\Vert \vec{a}{\Vert }^2\ge 0$，且 = 0 当且仅当 $\vec{a}=0$	点积自己的结果永不为负
零向量判定	$\vec{a}\cdot \vec{b}=0\Rightarrow$ 正交或有一方为零向量	判断垂直/线性无关

在SVM中用向量表示每一个样本点，而不是使用坐标系

矩阵 (matrix) 与转置 (transpose)

转置

将行换成列

$$A=\left[\begin{array}{cc}1& 2\end{array}\right]\Rightarrow A^T=\left[\begin{array}{c}1\\ 2\end{array}\right]$$

性质	数学表达式
$(A^T{)}^T=A$	二次转置还原原矩阵
$(A+B{)}^T=A^T+B^T$	加法可交换
$(AB{)}^T=B^T{A}^T$	乘法转置时顺序会颠倒
$(cA{)}^T=c{A}^T$（$c$是常数）	常数可提取

矩阵乘法：

如果 $A\in {\mathbb{R}}^{m\times n}$，$B\in {\mathbb{R}}^{n\times p}$，则：

$$C=AB\in {\mathbb{R}}^{m\times p}$$

矩阵乘法的本质：行向量与列向量的内积组合

超平面 (Hyperplane) 基础

在 $n$ 维空间中，一个超平面是一个维度为 $n-1$ 的线性子空间，可以表示为

$$w^{T}x+b=0$$

其中，$w$ 是法向量，决定平面的方向；$b$ 是偏置，决定平面的位置。

• $w$ 是一个 列向量，通常是 $n$ 维向量，表示超平面的法向量（即垂直于超平面的方向）。
• $x$ 是一个 列向量，表示输入空间中的一个点（样本）。
• $w^T$ 是 $w$ 的转置 (transpose)，因此 $w^{T}x$ 是两个向量的 内积（dot product），结果是一个标量。
• $b$ 是一个 偏置项（bias），决定了超平面在空间中的平移位置。
• 所以整个表达式 $w^{T}x+b$ 的值是一个 实数。

所有在 $w$ 方向上“投影相同”的点，形成一个平面。

也就是说，$w^{T}x+b=0$ 表示的是一个 正交于 $w$ 的面，这面上所有点的 $w$-投影都刚好被 $b$ 抵消掉，所以结果是 0。

几何解释：

• $w^{T}x+b>0$ 的点在超平面的一侧；
• $w^{T}x+b<0$ 的点在另一侧；
• $w^{T}x+b=0$ 的点恰好在超平面上。

在SVM中超平面是用于分类的边界，SVM寻找“最大间隔的超平面”来划分两个类别。

硬间隔 SVM

标记

$$f(x)=\text{sign}(w^{T}x+b)$$

• 如果 $f(x)=+1$，则 $x$ 被判定为正类；$f(x)=-1$，则为负类。

函数间隔

$\text{distance}=y_i|w^{T}x+b|$

几何间隔（margin）

函数间隔归一化结果就是几何间隔
$\text{distance}=\frac{|w^{T}x+b|}{\Vert w\Vert }$
找任意平面上的点 $x_H$

我们知道平面 $w^{T}x+b=0$ 上存在一些点，选一个 $x_H$ 满足：

$$w^T{x}_H+b=0$$

例如你可以从某个已知 $x$ 上去找 $x_H$，或者直接作为中间变量。

点 $x_0$ 到平面 $H$ 的距离，就是从 $x_0$ 到平面上一点 $x_H$ 的向量 $x_0-x_H$ 在法向量方向 $w$ 上的投影长度。

因为 $w$ 垂直于平面，投影就是垂直距离！

这个投影长度公式如下：

$$\text{distance}=\Vert {\text{proj}}_{\hat{w}}(x_0-x_H)\Vert =\left|\frac{w^T(x_0-x_H)}{\Vert w\Vert }\right|$$

利用 $w^T{x}_H=-b$ 将 $x_H$ 替换：

$$w^T(x_0-x_H)=w^T{x}_0-w^T{x}_H=w^T{x}_0+b$$

所以代入得：

$$\text{distance}=\left|\frac{w^T{x}_0+b}{\Vert w\Vert }\right|$$

即：

$$\boxed{\text{distance}=\frac{|w^{T}x+b|}{\Vert w\Vert }}$$

硬间隔 SVM 是支持向量机的最基础形式，要求所有训练样本必须被完全线性分开。

也就是说：

• 所有点都必须被一个超平面 $w^{T}x+b=0$ 正确地分开；
• 并且我们希望这个超平面“离所有点尽可能远”，即最大化间隔（margin）。

线性可分的二分类问题

给定训练集：

$$(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n),x_i\in {\mathbb{R}}^d,y_i\in \{-1,1\}$$

目标：找到一个超平面

$$w^{\top }x+b=0$$

将正负样本严格分开，并最大化到两类样本的间隔。

最大间隔分类器（Hard Margin）

任意一个样本 $(x_i,y_i)$，几何间隔定义为：

$${\gamma }_i=\frac{y_i(w^{\top }{x}_i+b)}{\Vert w\Vert }$$

${\gamma }_i$ 表示第 $i$ 个样本点 $x_i$ 到分类超平面 $w^{T}x+b=0$ 的有符号距离（即“带方向”的几何间隔）：

• ${\gamma }_i>0$ → 分类正确
• ${\gamma }_i<0$ → 分类错误
• ${\gamma }_i=0$ → 正好落在超平面上

符号	名称	类型/范围	作用
${\gamma }_i$	几何间隔	实数	点 $x_i$ 到超平面的带符号距离
$y_i$	标签	$-1,+1$	表示 $x_i$ 是正类还是负类
$x_i$	输入样本	向量 $\in {\mathbb{R}}^n$	样本特征向量
$w$	法向量/权重	向量 $\in {\mathbb{R}}^n$	决定超平面的方向
$b$	偏置	实数	控制超平面的位置
$w^{\top }{x}_i$	点积/预测值	实数	决定 $x_i$ 落在超平面的哪一侧
$\Vert w\Vert$	向量长度	非负实数	用于归一化距离，决定几何间隔尺度

是否线性可分

Darren Engwirda

最优间隔分类器

小样本、非线性及高维模式识别

整个分类器的几何间隔为：

$$\gamma =\underset{i}{\min }{\gamma }_i$$

SVM的目标

$$\underset{w,b}{\max }\left(\underset{i}{\min }{\gamma }_i\right)$$

也就是最大化所有样本中最小几何间隔。

最大间隔分类（max-margin classification）

原始优化问题（Primal Form）

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{s.t.}& y_i(w^{\top }{x}_i+b)\ge 1,i=1,\dots ,n\end{array}$$

这相当于最大化间隔的二次规划问题。

判断是否线性可分

低维 / 数据量小：直接观测
高维 / 数据量大：检查凸包（convex hull）是否相交

凸包是一个凸的闭合曲线（曲面），而且刚好包住了所有的数据。

如果数据不是线性可分的，我们就必须要采用一些特殊的方法，比如SVM的核技巧把数据转换到更高的维度上，在那个高维空间数据更可能是线性可分的（Cover定理）。

4. 线性变换与空间映射

定义：

线性变换是保持加法和数量乘法性质的变换，通常由一个矩阵来表示：

$$T(x)=Ax$$

其中 $A$ 是变换矩阵，$x$ 是输入向量，$T(x)$ 是输出。

举例：

二维旋转、投影、拉伸等都是线性变换。

在SVM中：

• 把输入样本 $x$ 通过变换（尤其在核SVM中）映射到高维空间以实现线性可分。

---

🎯 在SVM中：

SVM优化的是：

$$\text{maximize margin}\Rightarrow \min \frac{1}{2}\Vert w{\Vert }^2$$

这直接影响决策边界的宽度。

---

6. 拉格朗日乘子法（对偶优化）

定义：

用于有约束优化问题，通过引入“乘子”把约束合入目标函数中。

一般形式：

最小化 $f(x)$，满足 $g_i(x)\le 0$，构造：

$$\mathcal{L}(x,\lambda )=f(x)+\sum {\lambda }_i{g}_i(x)$$

🎯 在SVM中：

SVM的优化问题：

• 主问题：求解 $w,b$
• 对偶问题：引入 ${\alpha }_i$ 拉格朗日乘子，最终转化为：

$$\underset{\alpha }{\max }\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

对偶问题更适合加核函数，因此非常关键。

---

7. 特征空间与升维（用于核SVM）

升维思想：

在原空间中无法线性分割的点，通过一个映射 $\varphi (x)$ 变换到更高维空间，使其线性可分。

$$x\mapsto \varphi (x)$$

例如将 $(x_1,x_2)$ 变为 $(x_1,x_2,x_1^2,x_2^2,x_1{x}_2)$。

✅ 核函数：

核技巧让我们可以直接计算高维内积：

$$K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$$

常见核函数：

• 线性核 $K(x,y)=x^{T}y$
• 多项式核 $K(x,y)=(x^{T}y+c{)}^d$
• 高斯核 $K(x,y)=\exp (-\gamma |x-y{|}^2)$

---

8. 正定矩阵与Gram矩阵（核函数的有效性依据）

Gram矩阵定义：

对于数据集 $x_1,x_2,...,x_n$，Gram矩阵是：

$$G_{ij}=K(x_i,x_j)$$

✅ 正定矩阵：

矩阵 $A$ 是正定的当且仅当对任意非零向量 $x$，有：

$$x^{T}Ax>0$$

🎯 在SVM中：

• 核函数有效的充要条件是其对应的 Gram 矩阵是对称正定的。
• 这保证优化问题是凸的，解是全局最优。