《机器学习：算法视角（原书第2版）》 —3.4　线性可分性

3.4　线性可分性

感知器实际上计算的是什么？对于OR的例子来说，只有一个输出神经元，它尝试把神经元应该激活和不应该激活的情况区分开。观察图3-4右边的图形，很容易画一条直线来把十字形和圆形分开（这在图3-6中已经实现）。　图3-7　将数据分为两类的决策边界事实上，这正是感知器所做的：它尝试寻找这样一条直线（二维空间中是一条直线，三维空间中是一个平面（plane），在更高维度的空间中是一个超平面（hyperplane）），在直线的一边神经元都激活，而在另一边神经元都不激活。这条直线被称作决策边界，或者是判别函数（discriminant function）。图3-7给出了这样的一个例子。

为了理解这一点，回忆一下我们在实现部分使用的矩阵的表示符号，但是只考虑一个输入向量x。如果x·wT≥0，神经元会激活。其中的w是权重矩阵W的某一行，它是连接输入与某个特定神经元的权重，这就与OR的例子一样了，因为在那个例子中只有一个神经元。wT代表w的转置（transpose），用来把向量转化成列向量。a·b描述了两个向量的内积（标量积）。它通过把第一个向量的每个元素与第二个向量中对应的元素相乘，然后把所得的乘积相加来得到计算结果。你可能记得在高中时学过，a·b=abcosθ ，其中θ是a与b的夹角，a表示向量a的长度。因此内积计算的是两个向量间夹角的函数，并且所得的值根据向量的长度按比例扩大。这可以在NumPy中通过np.inner()函数计算得到。

回到感知器，所谓的边界，就是我们能在上面找到一个输入向量x1满足x1·wT=0。现在假设我们找到另一个输入向量x2，满足x2·wT=0。把这两个式子放在一起，我们能够得到：x1·wT=x2·wT(3.16)

(x1-x2)·wT=0(3.17)最后一个式子的含义是什么？为了使内积为0，a、b或者cosθ需要为0。a或b显然不可能为0，所以cosθ=0。这意味着θ=π/2（或-π/2），即两个向量间的夹角为直角。现在x1-x2代表的是穿过位于决策边界上的两点的一条直线，并且权重向量wT与这条线垂直，就像在图3-7中看到的那样。

所以，当给定一些数据，以及与之对应的目标输出的时候，感知器只是尝试寻找一条直线，使之能够把神经元激活的样例和神经元不激活的样例区分开。如果这样的直线存在，那再好不过，否则就会出现一些问题。存在这样一条直线的情况称作是线性可分（linearly separable）的情况。　图3-8　四个神经元的感知器所划分的不同决策边界那么如果我们想要学习的类别不是线性可分的，会怎么样呢？我们发现构造这样的一个函数是很容易的，甚至存在一个符合条件的逻辑函数。在我们考虑这些之前，有一个问题值得思考：当存在多于一个输出神经元的时候，会发生什么？每个神经元的权重都定义了一条直线，所以通过把多个神经元放在一起，我们得到了多条直线，每条直线都尝试把空间划分成不同的部分。图3-8给出了一个包含四个神经元的感知器计算得出的决策边界的例子，通过把不同的决策边界结合在一起，我们可以得到一个对不同类别的良好划分。

3.4.1　感知器收敛定理

实际上，我们并不能说已经达到1969年的水平。还有一个众所周知的重要事实：Rosenblatt的1962证明，给定一个线性可分的数据集，感知器将在有限次数的迭代之后收敛于某个分类方。实际上，迭代次数以1/γ2为界，其中γ是分离超平面与最接近的数据点之间的距离。这个定理的证明只需要一些代数知识，所以我们将在这里解决它。我们假设每个输入向量的长度x≤1，假定它们受某些常数R的限制，尽管不是严格必要。

首先，我们知道有一些权重向量w*可以分隔数据，因为我们假设它是线性可分的。 感知器学习算法旨在找到一些与w*平行或尽可能接近的向量w。为了检查两个向量是否平行，我们使用内积w*·w。当两个向量平行时，它们之间的角度是θ=0，因此cosθ=1，内积的大小是最大的。如果我们因此表明在每次权重更新时w*·w增加，那么我们几乎已经知道算法会收敛。但是，我们确实需要更多一点，因为w*·w=w*wcosθ，所以还需要检查w的长度没有增加太多。

因此，当我们考虑权重更新时，需要进行两项检查：w*·w的值和w的长度。

假设在算法的第t次迭代中，网络看到一个特定的输入x应该有输出y，并且出现了输入错误，所以yw(t-1)·x<0，其中上标（t-1）表示第（t-1）步的权重。这意味着需要更新权重。这个权重更新将是w(t)=w(t-1)·yx（为简单起见，我们设置η=1，因为它对感知器来说很好）。

要了解这将如何改变我们感兴趣的两个值，需要做一些计算：w*·w(t)=w*·(w(t-1)+yx)=w*·w(t-1)+yw*·x≥w*·w(t-1)+γ　(3.18)这里的γ是w*所定义的超平面到任意点间的最小距离。

这代表每次权重更新时，内积增加至γ，因此在t次权重更新后w*·w(t)≥tγ。利用这点使用柯西不等式（Cauchy-Schwartz inequality），我们可以取得w(t)长度的下限，也就是w*·w(t)≤w*w(t),即w*·w(t)≥tγ。

t步后的权重向量长度为：w(t)2=w(t-1)+yx2=w(t-1)2+y2x2+2yw(t-1)·x≤w(t-1)2+1　(3.19)最后一行的推导是由于y2=1，x≤1，如果w(t-1)与x垂直则网络报错。这也就是说w(t)2≤k。

合并不等式得tγ≤w(t-1)≤t（3.20）因此t≤1/γ2。所以，在我们进行了许多更新之后，算法必须已经收敛。

我们已经证明，如果权重是线性可分的，那么算法将收敛，并且这个时间是分离超平面和最近的数据点之间的距离的函数。我们称之为间隔（margin），在第8章中将看到一个明确使用它的算法。请注意，感知器会在获得所有训练数据后立即停止学习，因此无法保证只要有线性分隔符，它就会找到最大的间隔。此外，如果数据不是线性可分的，我们仍然不知道会发生什么。为了看到这一点，我们将继续这样一个例子。