人工神经网络(第一次寒冬)

你还能举出一个非线性可分的问题的例子吗
同时请用严格的数学去证明它是非线性可分的

在1957年
罗森布拉特提出了感知器算法
尽管前面一讲中
我们讲到了感知器算法有那么多重要的历史意义
但是在当时并没有引起轰动
虽然大家觉得将神经元数学模型引入到机器学习的领域
尝试是非常新颖的
但是这个算法却没有实际的应用
以我们今天的观点来看
问题出在感知器算法只能解决线性可分数据集的分类
对于线性不可分的数据集
感知器算法无能为力
而现实生活中大多数分类问题却都是线性不可分的
第一次明确说出上面这些话的人是marin minsky
他是人工智能的先驱之一
在1969年
insky写了一本书
叫做感知器perceptures
在书中他明确地定义了线性可分和非线性可分的概念
并指出感知器只能处理线性可分问题
同时他用大量实际的例子论证的
现实生活中的很多分类问题都是线性不可分的
我们来看其中的一个例子
ikey指出
识别一幅二值图像是不是连通图
这个问题是线性不可分的问题
什么是连通图呢
他的意思是图中任意两个黑色的点都能找到一组黑色的点
将它们连起来
例如下面的图
前两幅是连通图
后两幅是非连通图
ikey用数学严格地证明了
识别一幅二值图像是不是连通图是一个线性不可分的问题
在讲述这个证明前
我们需要讲一下图像在计算机中的存储
在计算机中
图像是以矩阵的形式存储的
左图是一幅512×512的图像
意思是说这幅图像的长由512个像素
宽也有512个像素
这些像素的点规则均匀的排布成右边
12×512的矩阵
而矩阵的每一个数是像素值
这幅图是巴比特的灰度图
在这幅图中
项数值是0~255的整数
其中零代表纯黑色
55代表纯白色
而中间值代表各种不同的灰度
那么将会得到三个矩阵
每个矩阵分别代表红色
而绿色g和蓝色b3 种颜色分量
而这三种分量的值也是在0~255之间
我们这里提到二值图是指每个像素要么是白色
要么是黑色
我们用零代表白色
用一代表黑色
那么二字图也可以表示为一个值为零或一的矩阵
我们可以把这些像素值从左到右
从上到下逐一的抄下来
这样就可以形成一个列向量x假设原图长为m宽为n
那么这个列向量x的维度将会是m乘以n
而标签y仍然取两个值
等于正一
表示x是连通图
等于-1
表示x不是连通图
接下来我们要证明识别联通图的问题是非线性可分的
我们用反证法假设这个问题是线性可分的
那么一定存在omega和b使得当y等于正一时
欧米伽的转置乘以x加b是大于零的
当欧米伽等于-1时
欧米伽的转置乘以x加b是小于零的
为此可以考察如下四张图
容易看出图一和图二是连通的
图三和图四是非连通的
同时我们将它们的几条边分别编号放在最左边那张图上供参考
请看由于图一是联通的
它所对应的标签y等于正一
因此我们有1+2+3+5+6
再加上b是大于零的
其中一代表的是编号为一的那条边上的像素值分别乘以omega相应的分量
然后再求和的结果
其他的定义也是类似的
同样的道理
图二是连通的
可以推出1+2+3+4+7
再加上b是大于零的
而图三是非连通的
则有1+2+3+4+5加上b是小于零的
图四是非连通的
则有1+2+3+6+7加上b是小于零的
现在我们将公式一加上公式二
将会得到两倍的
+2+3加上b再加上4+5+6+7是大于零的
而将公式三加上公式四
我们将得到两倍的
+2+3加上b再加上4+5+6+7是小于零的
注意到上面两个不等式左边是同一个数
而这个数不可能既大于零
又小于零
因此产生矛盾
而这个矛盾是假设联通图是可以线性可分而引起的
所以识别连通图的问题是非线性可分的
在mini这本书中举了几十个这样非线性可分的例子
这些例子都是常见的分类问题
最巧妙的一点是
它不是从实际收集数据中得到结论
而是以数学证明得到结论
他的书为基于感知器算法的应用研究画上了句号
从1969年到1980年
这10年左右的时间里
人工神经网络方面的研究陷入停滞
历史上称为人工神经网络研究的第一次寒冬
我总是觉得这种方法并不准确
因为在此之前
感知器算法的应用也不火热
没有夏天
哪来冬天呢
直到上个世纪80年代初
人工神经网络才迎来了复苏
基于多个神经元的多层神经网络诞生了
初步具备了解决非线性可分问题的能力
在下一讲中
我们会继续论述
本讲的末尾留两道思考题给大家
第一请证明一笔画问题是非线性可分的
即区分两类二字图像
一种可以一笔画出
另一种不能一笔画出
要证明这个问题是线性可分的
如下
我们给出了可以一笔画出以及不能一笔画出的图像的例子
第二你还能举出一个非线性可分的问题的例子吗
同时请用严格的数学去证明它是非线性可分的
本讲内容就到这里
谢谢同学们

发表评论

邮箱地址不会被公开。 必填项已用*标注