[读书笔记]《西瓜书》第六章 支持向量机
![[读书笔记]《西瓜书》第六章 支持向量机](/images/machine-learning_huda146d3825fc6d502e05b38609bff098_23368_900x500_fit_q75_box.jpg)
第六章 支持向量机
6.1 间隔与支持向量
核心思想
- 支持向量机是一种分类学习方法
- 基于训练集在样本空间中找到一个划分超平面，将不同类别的样本分开
关键问题
如何找到最合理的超平面？
应该去找到以"最大间隔"（maximum margin）划分两类样本，并位于“正中间”的划分超平面
-
找到具有“最大间隔”的划分超平面
-
”正中间“：
-
因为该划分超平面对训练样本局部扰动的“容忍”性最好
- 训练样本的局限性
- 训练样本的噪声因素
-
这样的划分超平面的方式所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强
-
因此我们可以推断在这个需求下，超平面与两个支持向量之间是平行的
引发了问题：如何求解最大间隔？
举例说明
PS：虽然西瓜书中给的例子是二分类支持向量机的例子，但是不意味着SVM只能做二分类任务，多分类也是可以的~
给定训练集 $$ D={(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m)},y_i \in {-1, +1 } $$ 在样本空间中，划分超平面可通过如下线性方程来表示（直线的斜截式方程表示） $$ \boldsymbol{w}^\text{T}\boldsymbol{x} + b = 0 $$
- $\boldsymbol{w}=(w_1;w_2;…;w_d)$为法向量，决定了超平面的方向
- $b$ 为位移项，决定了超平面与原点之间的距离
样本空间中任意点 $\boldsymbol{x}$ 到超平面 $(\boldsymbol{w},b)$ 的距离公式可写为 $$ r = \frac{|\boldsymbol{w}^\text{T}\boldsymbol{x} + b|}{\lVert \boldsymbol{w} \rVert} $$
前面的线性判别分析中已经出现过一次了~
假设超平面能够将所有训练样本正确分类
即对于 $(\boldsymbol{x}_i,y_i) \in D$，
- 若 $y_i= +1$ 则有 $\boldsymbol{w}^\text{T}\boldsymbol{x}_i+b>0$;
- 若 $y_i= -1$ 则有 $\boldsymbol{w}^\text{T}\boldsymbol{x}_i+b<0$;
即可在图中画出两条相应的直线 $\boldsymbol{w}^\text{T}\boldsymbol{x}+b = 1$ 和 $\boldsymbol{w}^\text{T}\boldsymbol{x}+b = -1$
- 对于正例样本 $(y_i = +1)$ 来说 $\boldsymbol{w}^\text{T}\boldsymbol{x}_i+b \ge +1$
- 对于负例样本 $(y_i = -1)$ 来说 $\boldsymbol{w}^\text{T}\boldsymbol{x}_i+b \le -1$
则超平面直线方程为 $\boldsymbol{w}^\text{T}\boldsymbol{x}+b = 0$
概念
-
距离到超平面最近的几个训练样本点使两条虚线等号成立，它们被称为“支持向量”（support vector）
-
两个异类支持向量到超平面的距离之和为“间隔”（margin）
- 例子中的间隔值为 $\gamma = \frac{2}{\lVert\boldsymbol{w}\rVert}$
如何求解最大间隔？
即找到在分类直线约束之下的参数 $\boldsymbol{w}$ 和 $b$，使得 $\gamma$ 最大
即，在本例中：
$$
\underset{\boldsymbol{w},b}{\max} \frac{2}{\lVert \boldsymbol{w} \rVert} \\
\text{s.t.} \quad y_i(\boldsymbol{w}^\text{T}\boldsymbol{x}_i + b) \ge 1 , \quad i=1,2,…,m
$$
可见 欲最大化 $\Vert \boldsymbol{w} \Vert ^{-1}$，即最小化 $\Vert \boldsymbol{w} \Vert ^2$
即，在本例中：
$$
\underset{\boldsymbol{w},b}{\min} \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 \\
\text{s.t.} \quad y_i(\boldsymbol{w}^\text{T}\boldsymbol{x}_i + b) \ge 1 , \quad i=1,2,…,m
$$
这个方程就是支持向量机（support vector machine）的基本型
PS：整个支持向量机看下来，其实就可以简单的理解为在求三个平面，两个参数，即如何构建两个超平面将样本集剥离开，同时选择一个超平面位于这两个超平面之间，同时为了满足最大化泛化效果，我们需要将这三个超平面平行处理，于是我们可知，只需求解两个参数即可，一是确定三个超平面方向的 $\boldsymbol{w}$ ，二是确定中间超平面的位置的 $b$
6.2 对偶问题
凸优化问题（OPT，convex optimization problem）
PS：西瓜书中提及了，但是信息量很少。因为在前一篇博文中铺垫了相应知识，所以这里就不重复赘述了
凸二次优化
拉格朗日乘子法
核心思想
将有约束的凸二次优化问题转化为无约束的二次规划问题，然后用梯度下降法进行求解
构造拉格朗日函数
假设原问题为 $\min f(x) \quad \text{s.t.} \quad g(x)=0$，其中 $f(x)$ 和 $g(x)$ 满足二次规划定义
构造拉格朗日函数 $$ L(x,\lambda) = f(x) + \lambda g(x) $$ 其中的 $\lambda$ 即称作拉格朗日乘子，$\lambda \ge 0$
更一般形式：
假设原凸二次优化问题为
$$
\begin{align}
& \min f(x) \\
\text{s.t.} & \quad g_i(x) = 0, i=1,2,…,m \\
& \quad h_j(x) \le 0, j=1,2,…,p
\end{align}
$$
构造拉格朗日函数
$$
\begin{align}
& L(x,\boldsymbol{\lambda},\boldsymbol{\mu}) = f(x) + \sum_{i=1}^m\lambda_i g_i(x) + \sum_{j=1}^p\mu_jh_j(x) \\
\text{s.t.} \\
& \quad \bigtriangledown_x L = 0 \\
& \quad g_i(x) = 0, i=1,2,…,m \\
& \quad h_j(x) \le 0, j=1,2,…,p \\
& \quad \mu_j \ge 0 \\
& \quad \mu_jh_j(x)=0, j=1,2,…,p
\end{align}
$$
K.K.T.条件（Karush-Kuhn-Tucker）
即在原问题为不等式约束时构造拉格朗日函数求解凸二次优化问题的时候，所形成的必要条件
上一篇博文中有介绍
对偶问题（Dual Problem）
形式为：
$$ \underset{x}{\min}\underset{\lambda \ge 0,\mu}{\max} L(x, \lambda, \mu) => \underset{\lambda \ge 0,\mu}{\max} \underset{x}{\min} L(x, \lambda, \mu) $$
可以简单理解：对偶问题只是将原始问题（primal problem）调换了min和max的位置，意义为“从一堆胖子里挑一个最瘦的 要比 从一堆瘦子里挑一个最胖的 还胖！”
这里记为：
$$ g(\lambda, \mu) = \underset{x}{\min} L(x, \lambda, \mu) $$
- 称之为拉格朗日对偶函数（Lagrange Dual Function）
- 是原始问题的一个下界
SVM对偶问题
PS：还是那个核心问题——如何求解最大间隔？
最大间隔基本型的方程：
$$
\underset{\boldsymbol{w},b}{\min} \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 \\
\text{s.t.} \quad y_i(\boldsymbol{w}^\text{T}\boldsymbol{x}_i + b) \ge 1 , \quad i=1,2,…,m
$$
求解过程
为每条约束添加拉格朗日乘子 $\alpha_i \ge 0$, 则 $\boldsymbol{\alpha} = (\alpha_1;\alpha_2;…;\alpha_m)$
得到拉格朗日函数
$$ L(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 + \sum_{i=1}^m \alpha_i(1-y_i(\boldsymbol{w}^{\text{T}}\boldsymbol{x}_i +b)) $$
令 $L(\boldsymbol{w},b,\boldsymbol{\alpha})$ 对 $\boldsymbol{w}$ 和 $b$ 分别求偏导为零可得
- $\boldsymbol{w}=\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i$
- $0=\sum_{i=1}^m \alpha_i y_i$
带入拉格朗日函数中，即可得到原问题的对偶问题为：
$$
\underset{\boldsymbol{\alpha}}{\max} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_j y_iy_j \boldsymbol{x}_i^{\text{T}}\boldsymbol{x}_j \\
\text{s.t.} \quad \sum_{i=1}^m \alpha_iy_i = 0, \alpha_i \ge 0, i=1,2,…,m
$$
K.K.T.条件
$$
\begin{cases}
& \alpha_i \ge 0; \\
& y_if(\boldsymbol{x}_i) - 1 \ge 0; \\
& \alpha_i(y_if(\boldsymbol{x}_i) - 1) = 0;\\
\end{cases}
$$
解出 $\boldsymbol{\alpha}$ 后，求出 $\boldsymbol{w}$ 与 $b$ 即可得到模型
$$
\begin{align}
f(x) & = \boldsymbol{w}^{\text{T}}\boldsymbol{x} + b \\
& = \sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i^{\text{T}}\boldsymbol{x} + b
\end{align}
$$
到这里周志华老师总结了一下支持向量机的优点：
- 该算法模型的规模正比于训练样本数量
- 训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关
- 其算法复杂度主要与支持向量的数目有关
6.3 核函数
异或问题与非线性映射
关键问题
原始样本空间内并不存在一个能正确划分两类样本的超平面
PS：这个问题是不是很眼熟？在前一章，神经网络中就讨论过这个问题，即两层的感知机模型就可以解决这个异或问题~
解决方案
将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分
PS：引用Caltech的课堂用语 “我们几乎可以认为（We are safe but not certain）原本在低维中线性不可分的数据集在足够高的维度中存在线性可分的超平面。”
定义 $\boldsymbol{x} \mapsto \phi(\boldsymbol{x})$ 表示将原始样本映射后的特征向量
在特征空间中划分超平面的模型为： $$ f(\boldsymbol{x}) = \boldsymbol{w}^{\text{T}}\phi(\boldsymbol{x}) + b $$ 问题转化
SVM标准型转化为
$$
\begin{align}
& \underset{\boldsymbol{w}, b}{\min} \quad \frac{1}{2}{\lVert\boldsymbol{w}\rVert}^2 \\
& \text{s.t.} \quad y_i(\boldsymbol{w}^{\text{T}}\phi(\boldsymbol{x_i})+b) \ge 1, i=1,2,…,m.
\end{align}
$$
对偶问题转化为
$$
\begin{align}
\underset{\boldsymbol{\alpha}}{\max} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_j y_iy_j\phi(\boldsymbol{x}_i)^{\text{T}}\phi(\boldsymbol{x}_j) \\
\quad \text{s.t.} \quad \sum_{i=1}^m \alpha_iy_i = 0, \alpha_i \ge 0, i=1,2,…,m
\end{align}
$$
核函数（Kernel Function）
虽然我们定义了一个非线性映射函数，将原始样本特征进行了转换，但是与此同时产生的问题：样本的特征空间维数可能很高，甚至是无穷，所以引发了核函数的产生
通过观察我们可以看出，求解转化后的对偶问题涉及到计算 $\phi(\boldsymbol{x}_i)^{\text{T}}\phi(\boldsymbol{x}_j)$，这是样本 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 映射到特征空间之后的内积
定义核函数
$$ \kappa(\boldsymbol{x}_i,\boldsymbol{x}_j) = \left \langle \phi(\boldsymbol{x}_i),\phi(\boldsymbol{x}_j) \right \rangle = \phi(\boldsymbol{x}_i)^{\text{T}}\phi(\boldsymbol{x}_j) $$
即 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\kappa(·,·)$ 计算的结果，其中的 $\kappa(·,·)$ 即所谓的核函数
PS：个人理解为，之前需要我们将每一个样本通过一个非线性映射函数 $\phi$ 转化为另一个特征空间中的样本，但是我们无法很方便的求解这个 $\phi$ ，所以核函数直接避开了这个，只求解其样本与样本之间的内积后的函数。
对偶问题
转化为
$$
\underset{\boldsymbol{\alpha}}{\max} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_j y_iy_j\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j) \\
\quad \text{s.t.} \quad \sum_{i=1}^m \alpha_iy_i = 0, \alpha_i \ge 0, i=1,2,…,m
$$
求解为
$$
\begin{align}
f(\boldsymbol(x)) & = \boldsymbol{w}^{\text{T}}\phi(\boldsymbol{x}) + b \\
& = \sum_{i=1}^m \alpha_iy_i\phi(\boldsymbol{x}_i)^{\text{T}}\phi(\boldsymbol{x}) + b \\
& = \sum_{i=1}^m\alpha_iy_i\kappa(\boldsymbol{x},\boldsymbol{x}_i) + b
\end{align}
$$
即模型最优解可通过训练样本的核函数展开得到 —— 支持向量展式（support vector expansion）
定理
令 $\mathcal{X}$ 为输入空间，$\kappa(·,·)$ 是定义在 $\mathcal{X} \times \mathcal{X}$ 上的对称函数，则 $\kappa$ 是核函数当且仅当对任意数据 $D = { \boldsymbol{x}_1, \boldsymbol{x}_2, … , \boldsymbol{x}_m }$
“核矩阵”（kernel matrix）$\mathbf{K}$ 总是半正定的
常见核函数
性质
- 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则对于任何正数 $\gamma_1$，$\gamma_2$，其线性组合 $\gamma_1\kappa_1 + \gamma_2\kappa_2$ 也是核函数
- 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则核函数的直积 $\kappa_1 \otimes \kappa_2(\boldsymbol{x},\boldsymbol{z}) = \kappa_1(\boldsymbol{x},\boldsymbol{z})\kappa_2(\boldsymbol{x},\boldsymbol{z})$ 也是核函数
- 若 $\kappa_1$ 为核函数，则对于任意函数 $g(\boldsymbol{x})，\kappa(\boldsymbol{x}, \boldsymbol{z}) = g(\boldsymbol{x})\kappa_1(\boldsymbol{x})g(\boldsymbol{z})$ 也是核函数
6.4 软间隔与正则化
软间隔
产生原因
- 在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分
- 即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难确定这个貌似线性可分的结果是不是由于过拟合造成的
对比概念
软间隔（soft margin）：允许某些样本不满足约束
硬间隔（hard margin）：所有样本都必须划分正确
公式 $$ \underset{\boldsymbol{w},b}{\min} \quad \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 + C\sum_{i=1}^m \ell_{0/1} \left ( y_i(\boldsymbol{w}^{\text{T}}\boldsymbol{x}_i + b) - 1 \right ) $$ 其中 $C > 0$ 是一个常数，$\ell_{0/1}$ 是“0/1损失函数”
$$
\ell_{0/1}(z) =
\begin{cases}
1, & \text{if} \quad z < 0； \\
0, & \text{otherwise.}
\end{cases}
$$
其中的 $z = y_i(\boldsymbol{w}^{\text{T}}\boldsymbol{x}_i + b)$
- 约束的原始条件是样本分类正确，即 $z$ 式大于 1，那么 $z$ 式小于 0 时，即样本分类错误的情况
- 对于当前这个损失函数，当分类正确时，相当于没有出现损失，所以记为 0
针对常数 $C$ 的不同情况
-
当 $C$ 无穷大时，该方程就变成了SVM基本型，即迫使所有样本均满足约束条件
个人理解：当 $C$ 无穷大时，迫使整个式子的要求最小值时，需要使得后半个式子值逼近 0，则迫使了每个样本均分类正确才行
-
当 $C$ 为有限值时，该方程就变成了允许一些样本不满足条件的情况
个人理解：即整个式子的最小值取值情况不再依据后半个式子影响，因为其在有限样本的情况下，值为某个固定有限值
替代损失（surrogate loss）
因为 $\ell_{0/1}$ “0/1损失函数” 是非凸且不连续函数，故在数学计算中不方便求值，因此考虑一些替代函数
常见的三种替代损失函数
- hinge损失：$\ell_{hinge}(z)=\max(0,1-z)$
- 指数损失（exponential loss）：$\ell_{\exp}(z)=\exp(-z)$
- 对率损失（logistic loss）：$\ell_{\log}(z)=\log(1+\exp(-z))$
软间隔支持向量机标准型
西瓜书中 采用 hinge损失函数 替代原始的损失函数
$$ \underset{\boldsymbol{w},b}{\min} \quad \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 + C\sum_{i=1}^m \max \left (0, 1 - y_i(\boldsymbol{w}^{\text{T}}\boldsymbol{x}_i + b) \right ) $$
这时引入一个新的概念“松弛变量”（slack variables）$\xi_i \ge 0$，用来表示每一个样本不满足约束的程度
转化为：
$$
\begin{align}
& \underset{\boldsymbol{w},b}{\min} \quad \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 + C\sum_{i=1}^m \xi_i \\
\text{s.t.} \quad & y_i(\boldsymbol{w}^{\text{T}}\boldsymbol{x}_i + b) \ge 1- \xi_i \\
\quad & \xi_i \ge 0，i=1,2,…,m
\end{align}
$$
若采用对率损失函数代替"0/1"损失函数则几乎得到了对率回归模型
- 支持向量机与对率回归的优化目标相近，通常情形下它们的性能也相当
- 对率回归的优势主要在于其输出具有自然的概率意义，即在给出预测标记的同时也给出了概率
- 支持向量机的输出不具有概率意义，欲得到概率输出需进行特殊处理
- 对率回归能直接用于多分类任务
- 支持向量机则需要进行推广
正则化（regularization）问题
SVM软间隔的一般形式 $$ \underset{f}{\min} \Omega(f) + C\sum_{i=1}^m \ell(f(\boldsymbol{x}_i), y_i) $$
从经验风险最小化的角度来看，第一项表述了我们希望获得具有何种性质的模型，这为引入领域知识和用户意图提供了途径；另一方面，该信息有助于削减假设空间，从而降低了最小化训练误差的过拟合风险
-
第一项 $\underset{f}{\min} \Omega(f)$
- 结构风险（structural risk）：用于描述模型的某些性质
- 正则化项
-
第二项 $\sum_{i=1}^m \ell(f(\boldsymbol{x}_i), y_i)$
- 经验风险（empirical risk）：用于描述模型与训练数据的契合程度
-
常数系数 $C$
- 用于进行两个风险的折中系数
- 正则化常数
6.5 支持向量回归
支持向量回归（Support Vector Regression，简称SVR）
对比
- 传统回归模型是基于模型输出与真实输出之间的差别来计算损失，当且仅当两者完全相同时，损失才为零
- 假设模型输出与真实输出之间最多有 $\epsilon$ 的偏差，即仅当模型输出与真实输出之间的差别绝对值大于 $\epsilon$ 时才统计损失
相当于构建了宽度为 $2\epsilon$ 的间隔带
公式
$$
\underset{\boldsymbol{w},b}{\min} \quad \frac{1}{2}{\lVert \boldsymbol{w} \rVert}^2 + C\sum_{i=1}^m \ell_{\epsilon} \left( f(\boldsymbol{x}_i) - y_i \right)
$$
其中 $\ell_{\epsilon}$ 为 $\epsilon$ - 不敏感损失（$\epsilon$ - insensitive loss）函数
$$
\ell_{\epsilon}(z) =
\begin{cases}
0, & \text{if} \quad |z| \le \epsilon； \\
|z| - \epsilon, & \text{otherwise.}
\end{cases}
$$
同样引入松弛变量 $\xi_i$ 和 $\hat{\xi}_i$
$$
\begin{align}
& \min_{\boldsymbol{w},b,\xi_i,\hat{\xi}_i} \frac{1}{2}{\Vert\boldsymbol{w}\Vert}^2 + C\sum_{i=1}^m(\xi_i - \hat{\xi}_i) \\
\text{s.t.} & \quad f(\boldsymbol{x}_i) -y_i \le \epsilon + \xi_i \\
& \quad y_i - f(\boldsymbol{x}_i) \le \epsilon + \hat{\xi}_i \\
& \quad \xi_i \ge 0 , \hat{\xi}_i \ge 0, i=1,2,…,m
\end{align}
$$
PS：这里引入了两个松弛变量，通过公式看出，即对于线性回归过程中的直线方程，两个参数代表对应的两边严格程度，或者可以简单理解两个松弛变量决定了这个超平面在这个间隔带中的位置~
转化对偶问题进行求解
引入拉格朗日乘子 $\mu_i \ge 0, \hat{\mu}_i \ge 0, \alpha_i \ge 0, \hat{\alpha}_i \ge 0$
$$
\begin{align}
& L(\boldsymbol{w},b,\boldsymbol{\alpha},\hat{\boldsymbol{\alpha}},\boldsymbol{\xi},\hat{\boldsymbol{\xi}},\boldsymbol{\mu},\hat{\boldsymbol{\mu}}) \\
& = \frac{1}{2}{\Vert{\boldsymbol{w}}\Vert}^2 + C\sum_{i=1}^m(\xi_i + \hat{\xi}_i) \\
& - \sum_{i=1}^m\mu_i\xi_i - \sum_{i=1}^m\hat{\mu}_i\hat{\xi}_i \\
& + \sum_{i=1}^m\alpha_i(f(\boldsymbol{x}_i)- y_i - \epsilon - \xi_i) \\
& + \sum_{i=1}^m\hat{\alpha}_i(y_i - f(\boldsymbol{x}_i)- \epsilon - \hat{\xi}_i)
\end{align}
$$
利用拉格朗日乘子法的对偶问题求出的 SVR 解的形式
$$ f(\boldsymbol{x}) = \sum_{i=1}^m (\hat{\alpha}_i - \alpha_i)\boldsymbol{x}_i^{\top}\boldsymbol{x}_j + b $$
性质
- 能使解中的 $(\hat{\alpha}_i - \alpha_i) \neq 0$ 的样本即为 SVR 的支持向量，他们必落在 $\epsilon$ - 间隔带之外
- 落在 $\epsilon$ - 间隔带中的样本都满足 $\alpha_i = 0$ 且 $\hat{\alpha}_i = 0$
- SVR 的支持向量仅是训练样本的一部分，即其解仍具有稀疏性
如何确认b？
首先这个问题的来源是，对于每一个样本 $(\boldsymbol{x}_i, y_i)$
都有 $(C-\alpha_i)\xi_i = 0$ 且 $\alpha_i(f(\boldsymbol{x}_i) - y_i - \epsilon - \xi_i) = 0$
求得到 $b = y_i + \epsilon - \sum_{i=1}^m (\hat{\alpha}_i - \alpha_i)\boldsymbol{x}_i^{\top}\boldsymbol{x}_j$
理论上可以任意选取满足条件的样本求得b，但是为了更加鲁棒，通常会选取多个满足条件的样本求解b后取平均值
引入核函数后最终解的形式为： $$ f(\boldsymbol{x}) = \sum_{i=1}^m(\hat{\alpha}_i - \alpha_i)\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) + b $$
6.6 核方法
通过前面的例子可以得到一个道理为：给定训练样本，若不考虑偏移项 $b$，则无论 SVM 还是 SVR，学得的模型总能表示成核函数的线性组合
表示定理（representer theorem）
令 $\mathbb{H}$ 为核函数 $\kappa$ 对应的再生核希尔伯特空间，$\Vert h\Vert_{\mathbb{H}}$ 表示空间中关于 $h$ 的范数，对于任意单调递增函数 $\Omega:[0, \infty] \mapsto \mathbb{R}$ 和任意非负损失函数 $\ell:\mathbb{R}^m \mapsto [0,\infty]$
优化问题： $$ \min_{h \in \mathbb{H}} F(h) = \Omega({\Vert h \Vert}_{\mathbb{H}}) + \ell(h(\boldsymbol{x}_i),…,\boldsymbol{x}_m)) $$ 解的形式: $$ h^*(\boldsymbol{x}) = \sum_{i=1}^m \alpha_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) $$
核方法（kernel methods）
一系列基于核函数的学习方法，统称为”核方法“
通过 “核化”（即引入核函数）来将线性学习器拓展为非线性学习器
PS：这里西瓜书引入了一个KLDA算法作为示例说明
核线性判别分析（Kernelized Linear Discriminant Analysisi，简称KLDA）
通过某种映射 $\phi: \mathcal{X} \mapsto \mathbb{F}$ 将样本映射到一个特征空间 $\mathbb{F}$，然后在 $\mathbb{F}$ 中执行线性判别分析
目标函数为： $$ h(\boldsymbol{x}) = \boldsymbol{w}^{\top}\phi(\boldsymbol{x}) $$ 求解目标为：
$$ \max_{\boldsymbol{w}}J(\boldsymbol{w}) = \frac{\boldsymbol{w}^{\top}\mathbf{S}^{\phi}_b\boldsymbol{w}}{\boldsymbol{w}^{\top}\mathbf{S}^{\phi}_w\boldsymbol{w}} $$
使用核函数 $\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \phi(\boldsymbol{x}_i)^{\top}\phi(\boldsymbol{x}_j)$ 来隐式地表达这个映射和特征空间 $\mathbb{F}$
-
$\mathbf{K} \in \mathbb{R}^{m \times m}$ 为核函数 $\kappa$ 所对应的核矩阵
-
令 $\mathbf{I}_i \in {1,0}^{m \times 1}$ 为第 $i$ 类样本的指示向量（就简单理解成one-hot encoding）
于是求解目标转化为： $$ \max_{\boldsymbol{\alpha}} J(\boldsymbol{\alpha}) = \frac{\boldsymbol{\alpha}^{\top}\mathbf{M}\boldsymbol{\alpha}}{\boldsymbol{\alpha}^{\top}\mathbf{N}\boldsymbol{\alpha}} $$
- $\hat{\boldsymbol{\mu}}_0 = \frac{1}{m_0}\mathbf{MI}_0$
- $\hat{\boldsymbol{\mu}}_1 = \frac{1}{m_1}\mathbf{MI}_1$
- $\mathbf{M} = (\hat{\boldsymbol{\mu}}_0 - \hat{\boldsymbol{\mu}}_1)(\hat{\boldsymbol{\mu}}_0 - \hat{\boldsymbol{\mu}}_1)^{\top}$
- $\mathbf{N} = \mathbf{KK}^{\top} - \sum_{i=0}^1 m_i{\hat{\boldsymbol{\mu}}_i}{\hat{\boldsymbol{\mu}}_i}^{\top}$
![[读书笔记]《西瓜书》第六章 支持向量机 铺垫](https://cdn.jsdelivr.net/gh/Ryuchen/ryuchen.github.io@master/images/machine-learning_huda146d3825fc6d502e05b38609bff098_23368_700x350_resize_q75_box.jpg)
