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

2019-03-05 本文已影响0人 shenghaishxt

核技巧

非线性分类问题

如果能用 $R^n$ 中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。对应下图的例子，通过变换将左图中椭圆变换称右图中的直线，将非线性分类问题变换为线性分类问题。

核技巧的基本想法是通过一个非线性变换将输入空间（欧式空间 $R^n$ 或离散集合）对应于一个特征空间（希尔伯特空间 $\mathcal{H}$ ），使得在输入空间 $R^n$ 中的超曲面模型对应于特征空间 $\mathcal{H}$ 中的超平面模型（支持向量机）。

核函数的定义

设 $\mathcal{X}$ 是输入空间（欧式空间 $R^n$ 或离散集合）， $\mathcal{H}$ 是特征空间（希尔伯特空间），如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射：
$\begin{align*} \\& \phi \left( x \right) : \mathcal{X} \to \mathcal{H} \end{align*}$
使得对所有 $x,z \in \mathcal{X}$ ，函数 $K \left(x, z \right)$ 满足条件：
$\begin{align*} \\ & K \left(x, z \right) = \phi \left( x \right) \cdot \phi \left( z \right) \end{align*}$
则称 $K \left(x, z \right)$ 为核函数， $\phi \left( x \right)$ 为映射函数，式中 $\phi \left( x \right) \cdot \phi \left( z \right)$ 为 $\phi \left( x \right)$ 和 $\phi \left( z \right)$ 的内积。

核函数在支持向量机中的应用

在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及输入实例与实例之间的内积，它们都可以用核函数 $K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j)$ 来代替。这等价于经过映射函数 $\phi$ 将原来的输入空间变换到一个新的特征空间，将输入空间中的内积 $x_i \cdot x_j$ 变换为特征空间中的内积 $\phi(x_i) \cdot \phi(x_j)$ ，在新的特征空间里从训练样本中学习线性支持向量机。

在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

常用核函数

多项式核函数

$\begin{align*} \\& K \left( x, z \right) = \left( x \cdot z + 1 \right)^{p} \end{align*}$

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

高斯核函数

$\begin{align} \\& K \left( x, z \right) = \exp \left( - \dfrac{\| x - z \|^{2}}{2 \sigma^{2}} \right) \end{align}$

非线性支持向量机

将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数即可。

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

输入：训练数据集

线性可分训练数据集 $T={(x_1, y_1), (x_2, y_2),...,(x_N, y_N)}$ ，其中 $x_i \in R^n$ ， $y_i \in \{-1, 1\}$ ， $i=1,2,...,N$ 。

输出：分类决策函数

选取适当的核函数 $K(x, z)$ 和适当的参数 $C$ ，构造并求解最优化问题
$\begin{align*} \\ & \min_{\alpha} \dfrac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} K \left( x_{i}, x_{j} \right) - \sum_{i=1}^{N} \alpha_{i} \\ & s.t. \sum_{i=1}^{N} \alpha_{i} y_{i} = 0 \\ & 0 \leq \alpha_{i} \leq C , \quad i=1,2, \cdots, N \end{align*}$

求得最优解 $\alpha^{\star} = \left( \alpha_{1}^{\star}, \alpha_{1}^{\star}, \cdots, \alpha_{N}^{\star} \right)$ 。

选择 $\alpha^{\star}$ 的一个分量 $0 < \alpha_{j}^{\star} < C$ ，计算
$\begin{align*} \\ & b^{*} = y_{j} - \sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K \left( x_{i}, x_{j} \right) \end{align*}$
构造决策函数