2. 对于给定的训练集 ，其中 ，如果能用 中的一个超曲面将正负实例正确分开，则称这个问题为非线性可分问题。

3. 设原空间为 ，新的空间为 。定义

   从原空间到新空间的变换（映射）为： 。

   则经过变换 ：

   • 原空间 变换为新空间 ， 原空间中的点相应地变换为新空间中的点。
   • 原空间中的椭圆 变换为新空间中的直线 。
   • 若在变换后的新空间，直线 可以将变换后的正负实例点正确分开，则原空间的非线性可分问题就变成了新空间的线性可分问题。

4. 用线性分类方法求解非线性分类问题分两步：

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

   这一策略称作核技巧。

3.1.1 核函数定义

1. 设 是输入空间（欧氏空间 的子集或者离散集合）， 为特征空间（希尔伯特空间）。若果存在一个从 到 的映射 ，使得所有的 ， 函数 ，则称 为核函数。

   即：核函数将原空间中的任意两个向量 ，映射为特征空间中对应的向量之间的内积。

2. 实际任务中，通常直接给定核函数 ，然后用解线性分类问题的方法求解非线性分类问题的支持向量机。

   • 通常直接计算 比较容易，反而是通过 和 来计算 比较困难。

     • 首先特征空间 一般是高维的，甚至是无穷维的，映射 不容易定义。

     • 其次核函数关心的是希尔伯特空间两个向量的内积，而不关心这两个向量的具体形式。因此对于给定的核函数，特征空间 和 映射函数 取法并不唯一。

       • 可以取不同的特征空间 。
       • 即使是在同一个特征空间 里，映射函数 也可以不同。

3. • 在对偶问题的目标函数中的内积 可以用核函数 来代替。

     此时对偶问题的目标函数成为：

   • 分类决策函数中的内积也可以用核函数代替： 。

4. 核函数替代法，等价于：

   • 首先经过映射函数 将原来的输入空间变换到一个新的特征空间。
   • 然后将输入空间中的内积 变换为特征空间中的内积 。
   • 最后在新的特征空间里从训练样本中学习线性支持向量机。

5. 若映射函数 为非线性函数，则学习到的含有核函数的支持向量机是非线性分类模型。

   若映射函数 为线性函数，则学习到的含有核函数的支持向量机依旧是线性分类模型。

3.1.2 核函数选择

1. 在实际应用中，核函数的选取往往依赖领域知识，最后通过实验验证来验证核函数的有效性。

2. 若已知映射函数 ，那么可以通过 和 的内积求得核函数 。现在问题是：不用构造映射 ， 那么给定一个函数 判断它是否是一个核函数？

   即： 满足什么条件才能成为一个核函数？

   可以证明： 设 是对称函数， 则 为正定核函数的充要条件是：对任意 ， 对应的 矩阵： 是半正定矩阵。

1. • 多项式核函数： 。

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

   • 高斯核函数：

     

     • 它是最常用的核函数，对应于无穷维空间中的点积。
     • 它也被称作径向基函数 ，因为其值从 沿着 向外辐射的方向减小。
     • 对应的支持向量机是高斯径向基函数分类器() 。

   • 核函数： 。

     对应的支持向量机实现的就是一种神经网络。

3.2 学习算法

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

   • 输入：训练数据集 ，其中 。

   • 输出：分类决策函数

   • 算法步骤：

     • 选择适当的核函数 和惩罚参数 ，构造并且求解约束最优化问题：

     

     求得最优解

     • 计算： 。
     • 选择 的一个合适的分量 ，计算： 。
     • 构造分类决策函数 ： 。