【核方法】

核

  • 核的介绍
      内核方法是一类用于模式分析或识别的算法，其最知名的使用是在支持向量机（SVM）。模式分析的一般任务是在一般类型的数据（例如序列，文本文档，点集，向量，图像等）中找到并研究一般类型的关系（例如聚类，排名，主成分，相关性，分类）图表等）。内核方法将数据映射到更高维的空间，希望在这个更高维的空间中，数据可以变得更容易分离或更好的结构化。对这种映射的形式也没有约束，这甚至可能导致无限维空间。然而，这种映射函数几乎不需要计算的，所以可以说成是在低维空间计算高维空间内积的一个工具。

  • 核的诀窍
      内核技巧是一个非常有趣和强大的工具。 它是强大的，因为它提供了一个从线性到非线性的连接以及任何可以只表示两个向量之间的点积的算法。 它来自如下事实：如果我们首先将我们的输入数据映射到更高维的空间，那么我在这个高维的空间进行操作出的效果，在原来那个空间就表现为非线性。

  • 内核技巧非常有趣，因为不需要计算映射。 如果我们的算法只能根据两个向量之间的内积表示，我们所需要的就是用一些其他合适的空间替换这个内积。 这就是”技巧”的地方：无论使用怎样的点积，它都被内核函数替代。 核函数表示特征空间中的内积，如P1所示Xi转置*Xj。使用内核函数，该算法然后可以被携带到更高维空间中，而不将输入点显式映射到该空间中。 这是非常可取的，因为有时我们的高维特征空间甚至可以是无限维，因此不可能计算。在低维中计算高维数据的点积。

  • 核函数的性质
      核函数必须是连续的，对称的，并且最优选地应该具有正（半）定Gram矩阵。据说满足Mercer定理的核是正半定数，意味着它们的核矩阵只有非负特征值。使用肯定的内核确保优化问题将是凸的和解决方案将是唯一的。然而，许多并非严格定义的核函数在实践中表现得很好。一个例子是Sigmoid内核，尽管它广泛使用，但它对于其参数的某些值不是正半定的。 Boughorbel（2005）也实验证明，只有条件正定的内核在某些应用中可能胜过大多数经典内核。

  • 内核还可以分为各向异性静止，各向同性静止，紧凑支撑，局部静止，非稳定或可分离非平稳。此外，内核也可以标记为scale-invariant（规模不变）或scale-dependent（规模依赖），这是一个有趣的属性，因为尺度不变内核驱动训练过程不变的数据的缩放。

    核方法

  • 核方法kernel methods (KMs)是一类模式识别的算法。其目的是找出并学习一组数据中的相互的关系。用途较广的核方法有支持向量机、高斯过程等。核方法是解决非线性模式分析问题的一种有效途径，其核心思想是：首先，通过某种非线性映射将原始数据嵌入到合适的高维特征空间；然后，利用通用的线性学习器在这个新的空间中分析和处理模式。

  • 相对于使用通用非线性学习器直接在原始数据上进行分析的范式，核方法有明显的优势：

1.首先，通用非线性学习器不便反应具体应用问题的特性，而核方法的非线性映射由于面向具体应用问题设计而便于集成问题相关的先验知识。
2.再者，线性学习器相对于非线性学习器有更好的过拟合控制从而可以更好地保证泛化性能。
还有，很重要的一点是核方法还是实现高效计算的途径，它能利用核函数将非线性映射隐含在线性学习器中进行同步计算，使得计算复杂度与高维特征空间的维数无关。

  • 本文对核方法（kernel method）进行简要的介绍:
      核方法的主要思想是基于这样一个假设：“在低维空间中不能线性分割的点集，通过转化为高维空间中的点集时，很有可能变为线性可分的” ，例如有两类数据，一类为xb；另一部分为a<x<b。要想在一维空间上线性分开是不可能的。然而我们可以通过F(x)=(x-a)(x-b)把一维空间上的点转化到二维空间上，这样就可以划分两类数据F(x)>0，F(x)<0；从而实现线性分割。然而，如果直接把低维度的数据转化到高维度的空间中，然后再去寻找线性分割平面，会遇到两个大问题，一是由于是在高维度空间中计算，导致维度祸根（curse of dimension）问题；二是非常的麻烦，每一个点都必须先转换到高维度空间，然后求取分割平面的参数等等；怎么解决这些问题？答案是通过核戏法（kernel trick）。（pku, shinningmonster, sewm)Kernel Trick:定义一个核函数.核函数的表达方式一般都不会显式地写为内积的形式，即我们不关心高维度空间的形式。核函数巧妙地解决了上述的问题，在高维度中向量的内积通过低维度的点的核函数就可以计算了。这种技巧被称为Kernel trick。
  • 这里还有一个问题：“为什么我们要关心向量的内积？”，一般地，我们可以把分类（或者回归）的问题分为两类：参数学习的形式和基于实例的学习形式。参数学习的形式就是通过一堆训练数据，把相应模型的参数给学习出来，然后训练数据就没有用了，对于新的数据，用学习出来的参数即可以得到相应的结论；而基于实例的学习（又叫基于内存的学习）则是在预测的时候也会使用训练数据，如KNN算法。而基于实例的学习一般就需要判定两个点之间的相似程度，一般就通过向量的内积来表达。从这里可以看出，核方法不是万能的，它一般只针对基于实例的学习。
  • 紧接着，我们还需要解决一个问题，即核函数的存在性判断和如何构造？ 既然我们不关心高维度空间的表达形式，那么怎么才能判断一个函数是否是核函数呢？
    Mercer 定理：任何半正定的函数都可以作为核函数。所谓半正定的函数f(xi,xj)，是指拥有训练数据集合（x1,x2,…xn)，我们定义一个矩阵的元素aij = f(xi,xj)，这个矩阵式n*n的，如果这个矩阵是半正定的，那么f(xi,xj)就称为半正定的函数。这个mercer定理不是核函数必要条件，只是一个充分条件，即还有不满足mercer定理的函数也可以是核函数。

    几种常用的核

  • 常见的核函数有高斯核，多项式核等等，在这些常见核的基础上，通过核函数的性质（如对称性等）可以进一步构造出新的核函数。SVM是核方法应用的经典模型。

    线性核

  • 线性内核是最简单的内核函数。 它由内积<x，y>加上可选的常数c给出。 使用线性内核的内核算法通常等于它们的非内核对应物，即具有线性内核的KPCA与标准PCA相同。

    多项式核函数

  • 多项式核是非固定内核。 多项式内核非常适合于所有训练数据都归一化的问题。
  • 表达式：k（x，y）=（αx ^ T y + c）^ d。可调参数是斜率α，常数项c和多项式度d。

    高斯核

  • 高斯核是径向基函数核的一个例子。或者，它也可以使用来实现。可调参数sigma在内核的性能中起着主要作用，并且应该仔细地调整到手头的问题。 如果过高估计，指数将几乎呈线性，高维投影将开始失去其非线性功率。 另一方面，如果低估，该函数将缺乏正则化，并且决策边界将对训练数据中的噪声高度敏感。

    指数的内核

    指数核与高斯核密切相关，只有正态的平方被忽略。 它也是一个径向基函数内核。和高斯核确实很像，

    拉普拉斯算子核

  • 拉普拉斯核心完全等同于指数内核，除了对sigma参数的变化不那么敏感。 作为等价的，它也是一个径向基函数内核。