人工神经网络--初寒

1. 回顾

在1957年，Rosenblatt提出了感知器算法，尽管前面一讲中，我们讲到了感知器算法有那么多的历史意义，但是在当时并没有引起轰动。虽然大家觉得将神经元数学模型引入到机器学习领域的尝试是非常新颖的，但是这个算法没有实际的应用。

2. 感知器算法的局限性及证明

以我们今天的观点来看，问题出在感知器算法只能解决线性可分数据集的分类，对于线性不可分的数据集感知器算法无能为力，但现实生活中大多数分类问题却都是线性不可分的。第一次明确说出上述这些话的人是Marvin Minsky，他是人工智能的先驱之一。在1969年，Marvin Minsky写了一本书《感知器》(Perceptrons)，在书中，他明确的定义了线性可分与非线性可分的概念，并指出感知器只能处理线性可分问题，同时，他用大量实际的例子论证了生活中很多分类问题是线性不可分的。

图1 Marvin Minsky(1927-2016)

下面我们看其中的一个例子，Minsky指出，识别一幅二值图像是不是连通图，这个问题是线性不可分的问题。

什么是连通图呢？它的意思是图中任意两个黑色的点都能找到一组黑色的点将他们连起来。例如下面的图2，图一、图二是连通图，图三、图四是非连通图。Minsky用数学严格地证明了识别一幅二值图像是不是连通图，是一个线性不可分的问题。

图2 二值图像连通图或非连通图

2.1 计算机中图像的存储形式

在讲述这个证明之前，我们需要先了解一下图像在计算机中的存储。在计算机中，图像是以矩阵的形式存储的。下图3(a)是一幅$512\times 512$的灰度图像，即这幅图像长有$512$个像素，宽也有$512$个像素，这些像素的点规则均匀的排布在图$3(b)512\times 512$的矩阵中，而矩阵中的每一个数是像素值，这幅图是$8bit$的灰度图。在这幅图中，像素值是$0-255$的整数，其中$0$代表纯黑色，$255$代表纯白色，而中间值代表各种不同的灰度。如果是彩色图，那么将会得到三个矩阵，每个矩阵分别代表红色$(R)$、绿色$(G)$、蓝色$(B)$三个颜色分量，而这三种分量的值也是在$0-255$之间。

图3(a) Lenna灰度图像

图3(b) Lenna灰度图像在计算机中的矩阵存储形式

图3(c) Lenna彩色图像

图3(d) Lenna彩色图像在计算机中的矩阵存储形式

我们这里提到二值图是指每个像素要么是白色，要么是黑色。我们用 0 0