Question

1. 非线性分类问题是指利用非线性模型才能很好的进行分类的问题。

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

3. 设原空间为 $ MathJax-Element-269 $ ，新的空间为 $ MathJax-Element-270 $ 。定义

   从原空间到新空间的变换（映射）为： $ MathJax-Element-271 $ 。

   则经过变换 $ MathJax-Element-272 $ ：

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

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

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

   这一策略称作核技巧。

3.1 核函数

3.1.1 核函数定义

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

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

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

   • 学习是隐式地在特征空间进行的，不需要显式的定义特征空间和映射函数。

   • 通常直接计算 $ MathJax-Element-320 $ 比较容易，反而是通过 $ MathJax-Element-290 $ 和 $ MathJax-Element-310 $ 来计算 $ MathJax-Element-320 $ 比较困难。

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

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

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

3. 在线性支持向量机的对偶形式中，无论是目标函数还是决策函数都只涉及输入实例之间的内积。

   • 在对偶问题的目标函数中的内积 $ MathJax-Element-304 $ 可以用核函数 $ MathJax-Element-301 $ 来代替。

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

     $ L(\vec\alpha)=\frac 12 \sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j\tilde y_i\tilde y_jK(\mathbf {\vec x}_i,\mathbf {\vec x}_j)-\sum_{i=1}^{N}\alpha_i $

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

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

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

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

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

3.1.2 核函数选择

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

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

   即： $ MathJax-Element-320 $ 满足什么条件才能成为一个核函数？

   可以证明： 设 $ MathJax-Element-315 $ 是对称函数， 则 $ MathJax-Element-320 $ 为正定核函数的充要条件是：对任意 $ MathJax-Element-317 $ ， $ MathJax-Element-320 $ 对应的 Gram 矩阵： $ MathJax-Element-319 $ 是半正定矩阵。

3. 对于一个具体函数 $ MathJax-Element-320 $ 来说，检验它为正定核函数并不容易。因为要求对任意有限输入集 $ MathJax-Element-321 $ 来验证 $ MathJax-Element-322 $ 对应的 Gram 矩阵是否为半正定的。

   因此，实际问题中往往应用已有的核函数。

8. 常用核函数：

   • 多项式核函数： $ MathJax-Element-323 $ 。

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

   • 高斯核函数：

     $ K(\mathbf {\vec x},\mathbf {\vec z})=\exp(-\frac{||\mathbf{\vec x}-\mathbf{\vec z}||^{2}}{2\sigma^{2}}) $
     • 它是最常用的核函数，对应于无穷维空间中的点积。
     • 它也被称作径向基函数radial basis function:RBF ，因为其值从 $ MathJax-Element-439 $ 沿着 $ MathJax-Element-390 $ 向外辐射的方向减小。
     • 对应的支持向量机是高斯径向基函数分类器(radial basis function) 。

   • sigmod核函数： $ MathJax-Element-327 $ 。

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

3.2 学习算法

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

   • 输入：训练数据集 $ MathJax-Element-511 $ ，其中 $ MathJax-Element-329 $ 。

   • 输出：分类决策函数

   • 算法步骤：

     • 选择适当的核函数 $ MathJax-Element-333 $ 和惩罚参数 $ MathJax-Element-384 $ ，构造并且求解约束最优化问题：
     $ \min_{\vec\alpha} \frac 12 \sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j\tilde y_i\tilde y_jK(\mathbf {\vec x}_i,\mathbf{\vec x}_j) -\sum_{i=1}^{N} \alpha_i\\ s.t. \quad \sum_{i=1}^{N}\alpha_i\tilde y_i=0\\ C \ge \alpha_i \ge 0,i=1,2,\cdots,N $

     求得最优解 $ MathJax-Element-332 $

     当 $ MathJax-Element-333 $ 是正定核函数时，该问题为凸二次规划问题，解是存在的。

     • 计算： $ MathJax-Element-334 $ 。
     • 选择 $ MathJax-Element-335 $ 的一个合适的分量 $ MathJax-Element-336 $ ，计算： $ MathJax-Element-337 $ 。
     • 构造分类决策函数 ： $ MathJax-Element-338 $ 。