支持向量机

《统计学习方法》笔记 第7章

Posted by Cheereus on January 28, 2020

第7章 支持向量机

7.1 线性可分支持向量机与硬间隔最大化

7.1.1 线性可分支持向量机

给定线性可分训练数据集,通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

\[\omega^* \cdot x + b^*=0\]

以及相应的分类决策函数

\[f(x)=\text{sign}(\omega^* \cdot x + b^*)\]

称为线性可分支持向量机。

7.1.2 函数间隔和几何间隔

函数间隔:

对于给定的数据集 $T$ 和超平面 $(\omega,b)$,定义超平面 $(\omega,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔为

\[\hat{\gamma_i}=y_i(\omega\cdot x+b)\]

定义超平面 $(\omega,b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(\omega,b)$ 关于 $T$ 中所有样本点 $(x_i,y_i)$ 的函数间隔之最小值,即

\[\hat{\gamma}=\underset{i=1,\cdots,N}{\min}\hat{\gamma_i}\]

几何间隔:

对于给定的训练数据集 $T$ 和超平面 $(\omega,b)$,定义超平面 $(\omega,b)$ 关于样本点 $(x_i,y_i)$ 的几何间隔为

\[\gamma_i=y_i\bigg(\frac{\omega}{\lVert\omega\rVert}\cdot x_i +\frac{b}{\lVert\omega\rVert}\bigg)\]

定义超平面 $(\omega,b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(\omega,b)$ 关于 $T$ 中所有样本点 $(\omega,b)$ 的几何间隔之最小值,即

\[\gamma=\underset{i=1,\cdots,N}{\min}\gamma_i\]

由上述定义可知,函数间隔和几何间隔有下面的关系:

\[\gamma_i=\frac{\hat\gamma_i}{\lVert\omega\rVert}\] \[\gamma=\frac{\hat\gamma}{\lVert\omega\rVert}\]

7.1.3 间隔最大化

1. 最大间隔分离超平面

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$;

输出:最大间隔分离超平面和分类决策函数。

(1) 构造并求解约束最优化问题:

\[\underset{\omega,b}{\min}\frac{1}{2}\lVert\omega\rVert^2\] \[s.t.\ \ y_i(\omega\cdot x_i+b)-1 \geq 0,\ \ i=1,2,\cdots,N\]

求得最优解 $\omega^\star,b^\star$。

(2) 由此得到分离超平面:

\[\omega^*\cdot x+b^*=0\]

分类决策函数:

\[f(x)=\text{sign}(\omega^*\cdot x+b^*)\]
2. 最大间隔分离超平面的存在唯一性

若训练数据集 $T$ 线性可分,则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

3. 支持向量和间隔边界

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)。支持向量是使约束条件式等号成立的点,即

\[y_i(\omega\cdot x_i+b)-1=0\]

对 $y_i=+1$ 的正例点,支持向量在超平面

\[H_1:\omega\cdot x+b=1\]

上。对 $y_i=-1$ 的正例点,支持向量在超平面

\[H_2:\omega\cdot x+b=-1\]

上。在 $H_1$ 和 $H_2$ 上的点就是支持向量。$H_1$ 和 $H_2$ 之间的距离称为间隔(margin)。间隔依赖于分离超平面的法向量 $\omega$,等于$\frac{2}{\lVert\omega\rVert}$。$H_1$ 和 $H_2$ 称为间隔边界。

在决定分离超平面时只有支持向量起作用,而其他实例点不起作用。由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机。

7.1.4 学习的对偶算法

为了求解线性可分支持向量机的最优化问题,将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual problem)得到原始问题(primal problem)的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。

线性可分支持向量机学习算法

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$;

输出:分离超平面和分类决策函数

(1) 构造并求解约束最优化问题

\[\underset{\alpha}{\min}\ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\] \[s.t.\ \ \sum_{i=1}^Na_iy_i=0\] \[a_i\geq 0, \ i=1,2,\cdots,N\]

求得最优解 $\alpha^\star=(\alpha^\star,\alpha^\star,\cdots,\alpha^\star_N)^T$。

(2) 计算

\[\omega^*=\sum_{i=1}^N\alpha^*_iy_ix_i\]

并选择 $\alpha^\star$ 的一个正分量 $\alpha^\star_j>0$,计算

\[b^*=y_i-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\]

(3) 求得分离超平面

\[\omega^*\cdot x+b^*=0\]

分类决策函数:

\[f(x)=\text{sign}(\omega^*\cdot x+b^*)\]

在线性可分支持向量机中,$\omega^\star$ 和 $b^\star$ 只依赖于训练数据中对应于 $\alpha^\star_i>0$ 的样本点 $(x_i,y_i)$,而其他样本点对 $\omega^\star$ 和 $b^\star$ 没有影响。我们给训练数据中对应于 $\alpha^\star_i>0$ 的实例点 $x_i\in R^n$ 称为支持向量。

7.2 线性支持向量机与软间隔最大化

7.2.1 线性支持向量机

对于给定的线性不可分的训练数据集,通过求解凸二次规划问题,即软间隔最大化问题,得到的分离超平面为

\[\omega^* \cdot x + b^*=0\]

以及相应的分类决策函数

\[f(x)=\text{sign}(\omega^* \cdot x + b^*)\]

称为线性支持向量机。

7.2.2 学习的对偶算法

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$;

输出:分离超平面和分类决策函数。

(1) 选择惩罚函数 $C>0$,构造并求解凸二次规划问题

\[\underset{\alpha}{\min}\ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\] \[s.t.\ \ \sum_{i=1}^Na_iy_i=0\] \[0 \leq a_i \leq C, \ i=1,2,\cdots,N\]

求得最优解 $\alpha^\star=(\alpha^\star,\alpha^\star,\cdots,\alpha^\star_N)^T$。

(2) 计算 $\omega^\star=\displaystyle\sum_{i=1}^N\alpha^\star_iy_ix_i$

选择 $\alpha^\star$ 的一个分量 $\alpha_j^\star$ 适合条件 $0<\alpha^\star_j<C$,计算

\[b^*=y_i-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\]

(3) 求得分离超平面

\[\omega^*\cdot x+b^*=0\]

分类决策函数:

\[f(x)=\text{sign}(\omega^*\cdot x+b^*)\]

7.2.3 支持向量

见原书附图

7.2.4 合页损失函数

线性支持向量机学习还有另外一种解释,就是最小化以下目标函数:

\[\sum_{i=1}^N[1-y_i(\omega\cdot x_i+b)]_++\lambda\lVert\omega\rVert^2\]

目标函数的第一项是经验损失风险,函数

\[L(y(\omega\cdot x+b))=[1-y_i(\omega\cdot x_i+b)]_+\]

称为合页损失函数(hinge loss function)。下标“$+$”表示以下取正值的函数。

\[[z]_+=\begin{cases} z, \ z>0\\0, \ z \leq 0 \end{cases}\]

这就是说,当样本点 $(x_i,y_i)$ 被正确分类且函数间隔(确信度) $y_i(\omega\cdot x+b)$ 大于 $1$ 时,损失是 $1-y_i(\omega\cdot x+b)$。

7.3 非线性支持向量机与核函数

7.3.1 核技巧

1.非线性分类问题

用线性分类方法求解非线性分类问题分为两步:

首先使用一个变换将原空间的数据映射到新空间;然后在新空间里用线性分类学习方法从训练数据中学习分类模型。

核技巧就属于这样的方法。

2.核函数的定义

设 $\mathcal{X}$ 是输入空间(欧式空间 $R^n$ 的子集或离散集合),又设 $\mathcal{H}$ 为特征空间(希尔伯特空间)。如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射

\[\phi(x): \mathcal{X}\rightarrow\mathcal{H}\]

使得对所有 $x,z\in\mathcal{X}$,函数 $K(x,z)$ 满足条件

\[K(x,z)=\phi(x)\cdot\phi(z)\]

则称 $K(x,z)$ 为核函数,$\phi(x)$ 为映射函数,式中 $\phi(x)\cdot\phi(z)$ 为 $\phi(x)$ 和 $\phi(x)$ 的内积。

3.核技巧在支持向量机中的应用

在核函数 $K(x,z)$ 给定的条件下,可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的,不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧,它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。

7.3.2 正定核

假设 $K(x,z)$ 是定义在 $\mathcal{X}\times\mathcal{X}$ 上的对称函数,并且对任意的 $x_1,x_2,\cdots,x_m\in\mathcal{X},\ K(x,z)$ 关于 $x_1,2_2,\cdots,x_m$ 的 $\text{Gram}$ 矩阵是半正定的。可以依据函数 $K(x,z)$,构成一个希尔伯特空间(Hilbert space),其步骤是:首先定义映射 $\phi$ 并构成向量空间 $\mathcal{S}$;然后在 $\mathcal{S}$ 上定义内积构成内积空间;最后将 $\mathcal{S}$ 完备化构成希尔伯特空间。

正定核的充要条件

设 $K:\mathcal{X}\times\mathcal{X}\rightarrow R$ 是对称函数,则 $K(x,z)$ 为正定核的充要条件是对任意 $x_i\in\mathcal{X},\ i=1,2,\cdots,m,\ K(x,z)$ 对应的 $\text{Gram}$ 矩阵:

\[K=[K(x_i,x_j)]_{m\times m}\]

是半正定矩阵。

7.3.3 常用核函数

1.多项式核函数(polynomial kernel function)

对应的支持向量机是一个 $p$ 次多项式分类器。

2.高斯核函数(Gaussian kernel function)

对应的支持向量机是高斯径向基函数(radial basis function)分类器。

3.字符串核函数(string kernel function)

7.3.4 非线性支持向量分类机

定义:从线性分类训练集,通过核函数与软间隔最大化,或凸二次规划,学习得到的分类决策函数

\[f(x)=\text{sign}\bigg(\sum_{i=1}^N a_i^* y_i K(x,x_i)+b\bigg)\]

称为非线性支持向量机,$K(x,z)$ 是正定核函数。

非线性支持向量机学习算法

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$;

输出:分类决策函数。

(1) 选取适当的核函数 $K(x,z)$ 和适当的参数 $C$,构造并求解最优化问题

\[\underset{\alpha}{\min}\ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\] \[s.t.\ \ \sum_{i=1}^Na_iy_i=0\] \[0 \leq a_i \leq C, \ i=1,2,\cdots,N\]

求得最优解 $\alpha^\star=(\alpha^\star,\alpha^\star,\cdots,\alpha^\star_N)^T$。

(2) 选择 $\alpha^\star$ 的一个正分量 $0<\alpha^\star_j<C$,计算

\[b^*=y_i-\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)\]

(3) 构造决策函数:

\[f(x)=\text{sign}\bigg(\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)+b^*\bigg)\]

7.4 序列最小最优化方法(sequential minimal optimization, SMO)

输入:线性可分的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{R}^n,y \in \{+1,-1\},i=1,2,\cdots,N$,精度 $\epsilon$;

输出:近似解 $\hat{\alpha}$

(1) 取初始值 $\alpha^{(0)}$,令 $k=0$;

(2) 选取优化变量 $\alpha^{(k)}_1,\alpha^{(k)}_2$,解析求解两个变量的最优化问题,求得最优解 $\alpha^{(k+1)}_1,\alpha^{(k+1)}_2$,更新 $\alpha$ 为 $\alpha^{(k+1)}$;

(3) 若在精度 $\epsilon$ 范围内满足停机条件

\[\sum_{i=1}^N\alpha_iy_i=0,\ \ 0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\] \[y_i\cdot g(x_i)\begin{cases}\geq1, \{x_i\vert\alpha_i=0\}\\=1,\{x_i\vert0<\alpha<C\}\\ \leq1,\{x_i\vert\alpha_i=C\} \end{cases}\]

其中,

\[g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_j\cdot x_i)+b\]

则转 (4),否则令 $k=k+1$,转 (2);

(4) 取 $\hat{\alpha}=\alpha^{(k+1)}$。

第7章完结


如果对您有帮助,欢迎赞助一杯咖啡!