18

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

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

谢谢。

4

5 回答 5

44

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

通过考虑 2D/3D 中的点和线，您可以对这些概念有某种直觉。这是一对非常人为的例子......

二维散点图

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

3D 散点图

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

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

将问题映射到具有大量维度的空间中，使得问题更有可能成为线性可分的。

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

于 2009-07-19T09:40:55.237 回答
35

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

在许多情况下，不能线性可分的问题可以通过对数据点应用变换 phi() 来解决；据说这种变换将点变换为特征空间。希望是，在特征空间中，这些点将是线性可分的。（注意：这还不是内核技巧……敬请期待。）

可以看出，特征空间的维数越高，在该空间中线性可分的问题就越多。因此，理想情况下，希望特征空间尽可能高维。

不幸的是，随着特征空间维度的增加，所需的计算量也在增加。这就是内核技巧的用武之地。许多机器学习算法（其中包括 SVM）可以以这样一种方式制定，即它们对数据点执行的唯一操作是两个数据点之间的标量积。（我将用 表示 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)“活” ")——但我们仍然获得了转换到高维特征空间的好处。这称为内核技巧。

许多流行的内核，例如高斯内核，实际上对应于变换为无限维特征空间的变换 phi() 。内核技巧允许我们计算该空间中的标量积，而不必明确表示该空间中的点（显然，这在内存有限的计算机上是不可能的）。

于 2009-07-19T06:09:44.773 回答
3

主要区别（出于实际目的）是：线性问题要么确实有解决方案（然后很容易找到），要么您得到一个明确的答案，即根本没有解决方案。在你根本不知道问题之前，你确实知道这么多。只要是线性的，你就会得到答案；迅速地。

这背后的直觉是，如果你在某个空间中有两条直线，很容易看出它们是否相交，如果相交，很容易知道在哪里。

如果问题不是线性的——嗯，它可以是任何东西，而你几乎一无所知。

两个向量的点积仅表示以下内容：相应元素的乘积之和。所以如果你的问题是

c1 * x1 + c2 * x2 + c3 * x3 = 0

（您通常知道系数 c，并且您正在寻找变量 x），左侧是向量(c1,c2,c3)和的点积(x1,x2,x3)。

上面的方程（几乎）是线性问题的定义，所以点积和线性问题之间存在联系。

于 2009-07-18T21:01:57.497 回答
2
  1. 线性方程是齐次的，并且适用叠加。您可以使用其他已知解决方案的组合来创建解决方案；这就是傅立叶变换如此有效的原因之一。非线性方程不是齐次的，叠加不适用。非线性方程通常必须使用迭代增量技术进行数值求解。
  2. 我不确定如何表达点积的重要性，但它确实需要两个向量并返回一个标量。当然，标量方程的解比求解向量或高阶张量方程的工作量要少，因为要处理的分量更少。

我对这件事的直觉更多地基于物理学，所以我很难翻译成人工智能。

于 2009-07-18T20:56:43.573 回答
1

我认为以下链接也很有用...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data

于 2014-02-06T11:49:29.490 回答