线性问题和非线性问题之间的区别？Dot-Product和Kernel技巧的本质

Question

内核技巧将非线性问题映射为线性问题.

我的问题是:
1.线性问题和非线性问题的主要区别是什么？这两类问题背后的直觉是什么？内核技巧如何帮助在非线性问题上使用线性分类器？
2.为什么点数产品在这两种情况下如此重要？

谢谢.

Answer 1

当人们说关于分类问题的线性问题时,它们通常意味着线性可分的问题.线性可分是指有一些函数可以将两个类分开,这两个类是输入变量的线性组合.例如,如果您有两个输入变量,x1并且x2有一些数字theta1,theta2那么该函数theta1.x1 + theta2.x2就足以预测输出.在二维中,这对应于直线,在3D中它变成平面并且在更高维空间中它变成超平面.

通过思考2D/3D中的点和线,您可以获得关于这些概念的某种直觉.这是一对非常人为的例子......

这是一个线性不可分割问题的图.没有可以分开红点和蓝点的直线.

但是,如果我们给每个点一个额外的坐标(特别是1 - sqrt(x*x + y*y)......我告诉你它是人为的),那么问题就变得线性可分,因为红色和蓝色点可以通过一个二维平面分开z=0.

希望这些例子展示了内核技巧背后的部分想法:

将问题映射到具有更多维度的空间使得问题更可能变得线性可分.

内核技巧背后的第二个想法(以及它如此棘手的原因)是,在非常高维空间中工作通常非常笨拙且计算成本高.但是,如果算法仅使用点之间的点积(您可以将其视为距离),那么您只需使用标量矩阵.您可以隐式地在更高维空间中执行计算,而无需实际执行映射或处理更高维数据.

Answer 2

许多分类器,其中包括线性支持向量机(SVM),只能解决线性可分离的问题,即属于类1的点可以通过超平面与属于类2的点分开.

在许多情况下,可以通过将变换phi()应用于数据点来解决不可线性分离的问题; 据说这种变换将点转换为特征空间.希望是,在特征空间中,点将是线性可分的.(注意:这不是核心技巧......敬请期待.)

可以证明,特征空间的维数越高,在该空间中可线性分离的问题的数量就越多.因此,理想情况下希望特征空间尽可能高维.

不幸的是,随着特征空间的维数增加,所需的计算量也增加.这就是内核技巧的用武之地.许多机器学习算法(其中包括SVM)可以通过这样的方式表达,即它们对数据点执行的唯一操作是两个数据点之间的标量积.(我将用x1表示x1和x2之间的标量乘积<x1, x2>.)

如果我们将点转换为特征空间,标量产品现在看起来像这样:

<phi(x1), phi(x2)>

关键的见解是存在一类称为内核的函数,可用于优化此标量积的计算.内核是K(x1, x2)具有该属性的函数

K(x1, x2) = <phi(x1), phi(x2)>

对于某些功能phi().换句话说:我们可以在低维数据空间(其中x1和x2"直播")中评估标量积,而无需转换到高维特征空间(其中phi(x1)和phi(x2)"直播) ") - 但我们仍然可以获得转换到高维特征空间的好处.这被称为核心技巧.

许多流行的内核,例如高斯内核,实际上对应于转换为infinte-dimensional特征空间的变换phi().内核技巧允许我们在这个空间中计算标量产品,而不必明确地在这个空间中表示点(显然,在具有有限内存量的计算机上这是不可能的).