2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 4章 人工神经网络（ ANN）
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
人工神经网络提供了一种普遍且实用的方法从样例中学习值为实数、离散值或向量的函数
反向传播算法，使用梯度下降来调节网络参数以最佳拟合由输入 -输出对组成的训练集合
人工神经网络对于训练数据中的错误健壮性很好
人工神经网络已被成功应用到很多领域，例如视觉场景分析，语音识别，机器人控制
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
神经网络学习对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性很强的方法
对于某些类型的问题，如学习解释复杂的现实世界中的传感器数据，人工神经网络是目前知道的最有效的学习方法
反向传播算法
成功例子，学习识别手写字符，学习识别口语，
学习识别人脸
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
生物学动机
ANN受到生物学的启发，生物的学习系统是由相互连接的神经元组成的异常复杂的网络。
ANN由一系列简单的单元相互密集连接构成的，其中每一个单元有一定数量的实值输入，并产生单一的实数值输出
人脑的构成，大约有 1011个神经元，平均每一个与其他 104个相连
神经元的活性通常被通向其他神经元的连接激活或抑制
最快的神经元转换时间比计算机慢很多，然而人脑能够以惊人的速度做出复杂度惊人的决策
很多人推测，生物神经系统的信息处理能力一定得益于对分布在大量神经元上的信息表示的高度并行处理
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
生物学动机（ 2）
ANN系统的一个动机就是获得这种基于分布表示的高度并行算法
ANN并未模拟生物神经系统中的很多复杂特征
ANN的研究分为两个团体
– 使用 ANN研究和模拟生物学习过程
– 获得高效的机器学习算法，不管这种算法是否反映了生物过程
本书属于后一个研究团体
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
神经网络表示
ALVINN系统
– Pomerleau 1993
– 使用一个学习到的 ANN以正常的速度在高速公路上驾驶汽车
– ANN的输入是一个 30x32像素的网格，输出是车辆行进的方向
– 每个节点对应一个网络单元的输出，而从下方进入节点的实线为其输入
– 隐藏单元，输出仅在网络内部，不是整个网络输出的一部分
– 每个输出单元对应一个特定的驾驶方向，这些单元的输出决定哪一个方向是被最强烈推荐的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
神经网络表示（ 2）
ALVINN是很多 ANN的典型结构，所有单元分层互连形成一个有向无环图
通常,ANN图结构可以有很多种类型
– 无环或有环
– 有向或无向
本章讨论以反向传播算法为基础的 ANN方法
反向传播算法假定网络是一个固定结构，对应一个有向图，可能包含环
ANN学习就是为图中每一条边选取权值
大多数实际应用与 ALVINN相似
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
适合神经网络学习的问题
训练集合为含有噪声的复杂传感器数据，
例如来自摄像机和麦克风
需要较多符号表示的问题，例如决策树学习的任务，能够取得和决策树学习大体相当的结果
反向传播算法是最常用的 ANN学习技术
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
反向传播算法适合问题的特征
实例是用很多“属性 -值”对表示的
目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量
训练数据可能包含错误
可容忍长时间的训练
可能需要快速求出目标函数值
人类能否理解学到的目标函数是不重要的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
本章余后部分提纲
讨论训练单个单元的学习算法
介绍组成神经网络的几种主要单元
– 感知器（ perceptron）
– 线性单元（ liner unit）
– sigmoid单元（ sigmoid unit）
给出训练多层网络的反向传播算法
考虑几个一般性问题
– ANN的表征能力
– 假设空间搜索的本质特征
– 过度拟合问题
– 反向传播算法的变体
例子，利用反向传播算法训练识别人脸的 ANN
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
感知器
一种类型的 ANN系统是以感知器为基础
感知器以一个实数值向量作为输入，计算这些输入的线性组合，如果结果大于某个阈值，就输出 1，否则输出 -1
其中每个 wi是一个实数常量，或叫做权值，用来决定输入 xi对感知器输出的贡献率。特别地,-w0是阈值。
o t h e r w is e xwxwwxxo nnn 0..,11),.,.,( 1101
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
感知器（ 2）
两种简化形式，附加一个常量输入 x0=1，前面的不等式写成或写成向量形式
为了简短起见，把感知器函数写为其中，
00ni iixw
0xw
)sgn()( xwxo
otherw iseyy 011)s g n (
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
感知器（ 3）
学习一个感知器意味着选择权 w0,…,w n的值。所以感知器学习要考虑的候选假设空间 H就是所有可能的实数值权向量的集合 }|{ 1 nRwwH
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
感知器的表征能力
可以把感知器看作是 n维实例空间（即点空间）中的超平面决策面
对于超平面一侧的实例，感知器输出 1，
对于另一侧的实例，输出 -1
这个决策超平面方程是
可以被某个超平面分割的样例集合，称为线性可分样例集合
0xw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
感知器的表征能力（ 2）
单独的感知器可以用来表示很多布尔函数
表示 m-of-n函数
感知器可以表示所有的原子布尔函数：
与、或、与非、或非
然而，一些布尔函数无法用单一的感知器表示，例如异或
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
感知器的表征能力（ 3）
因为所有的布尔函数都可表示为基于原子函数的互连单元的某个网络，因此感知器网络可以表示所有的布尔函数。事实上，只需要两层深度的网络，比如表示析取范式
注意，要把一个 AND感知器的输入求反只要简单地改变相应输入权的符号
因为感知器网络可以表示大量的函数，而单独的单元不能做到这一点，所以我们感兴趣的是学习感知器组成的多层网络
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
感知器训练法则
虽然我们的目的是学习由多个单元互连的网络，但我们还是要从如何学习单个感知器的权值开始
单个感知器的学习任务，决定一个权向量，它可以使感知器对于给定的训练样例输出正确的 1或 -1
我们主要考虑两种算法
– 感知器法则
– delta法则
这两种算法保证收敛到可接受的假设，在不同的条件下收敛到的假设略有不同
这两种算法提供了学习多个单元构成的网络的基础
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
感知器法则
算法过程
– 从随机的权值开始
– 反复应用这个感知器到每个训练样例，只要它误分类样例就修改感知器的权值
– 重复这个过程，直到感知器正确分类所有的训练样例
感知器训练法则其中
iii www
ii xotw )(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
感知器法则（ 2）
为什么这个更新法则会成功收敛到正确的权值呢？
– 一些例子
– 可以证明（ Minskey & Papert 1969）
如果训练样例线性可分，并且使用了充分小的?
否则，不能保证
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
梯度下降和 delta法则
delta法则克服感应器法则的不足，在线性不可分的训练样本上，收敛到目标概念的最佳近似
delta法则的关键思想是，使用梯度下降来搜索可能的权向量的假设空间，以找到最佳拟合训练样例的权向量
delta法则为反向传播算法提供了基础，而反向传播算法能够学习多个单元的互连网络
对于包含多种不同类型的连续参数化假设的假设空间，梯度下降是必须遍历这样的空间的所有算法的基础
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
梯度下降和 delta法则（ 2）
把 delta训练法则理解为训练一个无阈值的感知器
指定一个度量标准来衡量假设相对于训练样例的训练误差
第 6章给出了选择这种 E定义的一种贝叶斯论证，
在一定条件下，使 E最小化的假设就是 H中最可能的假设
xwxo)(
Dd dd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
可视化假设空间
图 4-4
– 根据 E的定义，误差曲面是一个抛物面，存在一个单一全局最小值
梯度下降搜索从一个任意的初始权向量开始，然后沿误差曲面最陡峭下降的方向，以很小的步伐反复修改这个向量，
直到得到全局的最小误差点
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
梯度下降法则的推导
如何发现沿误差曲面最陡峭下降的方向？
– 通过计算 E相对向量 的每个分量的导数，这个向量导数被称为 E对于 的梯度，记作
– 当梯度被解释为权空间的一个向量时，它确定了使
E最陡峭上升的方向，所以这个向量的反方向给出了最陡峭下降的方向
梯度训练法则其中，
w?
w?
)(wE
www
)(wEw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
梯度下降法则的推导（ 2）
需要一个高效的方法在每一步都计算这个梯度
梯度下降权值更新法则
Dd idddi xotwE ))((
Dd idddi xotw )(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
梯度下降法则的推导（ 3）
表 4-1，训练线性单元的梯度下降算法
Gradient-Descent(training_examples,?)
training_examples中每个训练样例形式为序偶 <,t>,是输入值向量，
t是目标输出值,?是学习速率
初始化每个 wi为某个小的随机值
遇到终止条件之前，做以下操作
– 初始化每个?wi为 0
– 对于训练样例 training_examples中的每个 <,t>，做
把实例 输入到此单元，计算输出 o
对于线性单元的每个权增量?wi，做
wiwi+?(t-o)xi
– 对于线性单元的每个权 wi，做
wi?wi+?wi
x? x?
x?
x?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
梯度下降法则的推导（ 4）
梯度下降算法如下
– 选取一个初始的随机权向量
– 应用线性单元到所有的训练样例，根据公式 4.7计算每个权值的 更新权值
因为误差曲面仅包含一个全局的最小值，所以无论训练样例是否线性可分，算法都会收敛到具有最小误差的权向量，条件是使用足够小的学习速率
算法的一种常用改进方法是随着梯度下降步数的增加逐渐减小学习速率
w?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
梯度下降的随机近似
梯度下降是一种重要的通用学习范型，它是搜索庞大假设空间或无限假设空间一种策略
梯度下降应用于满足以下条件的任何情况
– 假设空间包含连续参数化的假设
– 误差对于这些假设参数可微
梯度下降的主要实践问题
– 有时收敛过程可能非常慢
– 如果在误差曲面上有多个局部极小值，那么不能保证找到全局最小值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
梯度下降的随机近似（ 2）
随机梯度下降（或称增量梯度下降）
– 根据某个单独样例的误差增量计算权值更新，得到近似的梯度下降搜索（随机取一个样例）
– 对表 4-1算法的修改
– 可以看作为每个单独的训练样例定义不同的误差函数
– 在迭代所有训练样例时，这些权值更新的序列给出了对于原来误差函数的梯度下降的一个合理近似
– 通过使下降速率的值足够小，可以使随机梯度下降以任意程度接近于真实梯度下降
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
梯度下降的随机近似（ 2）
标准梯度下降和随机梯度下降之间的关键区别
– 标准梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查每个训练样例来更新的
– 在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算（？）
– 标准梯度下降，由于使用真正的梯度，标准梯度下降对于每一次权值更新经常使用比随机梯度下降大的步长
– 如果标准误差曲面有多个局部极小值，随机梯度下降有时可能避免陷入这些局部极小值中
实践中，标准和随机梯度下降方法都被广泛应用
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
梯度下降的随机近似（ 3）
delta法则（增量法则），又称 LMS法则,Adaline法则、
Windrow-Hoff法则
公式 4.10与 4.4.2节的感知器法则的相似和区别
delta法则可以学习非阈值线性单元的权，也可以用来训练有阈值的感知器单元。
如果非阈值输出能够被训练到完美拟合这些值，那么阈值输出也会完美拟合它们
即使不能完美地拟合目标值，只要线性单元的输出具有正确的符号，阈值输出就会正确拟合目标值
尽管这个过程会得到使线性单元输出的误差最小化的权值，但这些权值不能保证阈值输出的误差最小化
（？）
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
感知器学习小结
感知器法则和 delta法则的关键差异
– 前者根据阈值化的感知器输出的误差更新权值
– 后者根据输入的非阈值化线性组合的误差来更新权值
这个差异带来不同的收敛特性
– 前者经过有限次的迭代收敛到一个能理想分类训练数据的假设，条件是训练样例线性可分
– 后者可能经过极长的时间，渐近收敛到最小误差假设，但无论训练样例是否线性可分都会收敛
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
感知器学习小结（ 2）
学习权向量的第 3种方法是线性规划
线性规划是解线性不等式方程组的一种通用的有效方法
这种方法仅当训练样例线性可分时有解
Duda和 Hart给出了一种更巧妙的适合非线性可分的情况的方法
更大的问题是，无法扩展到训练多层网络，而
delta法则可以很容易扩展到多层网络
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
多层网络和反向传播算法
多层网络能够表示种类繁多的非线性曲面
图 4-5描述了一个典型的多层网络和它的决策曲面
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
可微阈值单元
使用什么类型的单元来构建多层网络？
多个线性单元的连接仍产生线性函数，而我们希望构建表征非线性函数的网络
感知器单元可以构建非线性函数，但它的不连续阈值使它不可微，不适合梯度下降算法
我们需要的单元满足的条件
– 输出是输入的非线性函数
– 输出是输入的可微函数
Sigmoid单元，类似于感知器单元，但基于一个平滑的可微阈值函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
可微阈值单元（ 2）
图 4-6
sigmoid单元先计算它的输入的线性组合，
然后应用到一个阈值上，阈值输出是输入的连续函数其中
)( xwo
yey1 1)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
可微阈值单元（ 3）
sigmoid函数
– 也称 logistic函数
– 挤压函数
– 输出范围是 0到 1
– 单调递增
– 导数很容易用函数本身表示
sigmoid函数的变型
– 其他易计算导数的可微函数
– 增加陡峭性
– 双曲正切函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
反向传播算法
用来学习多层网络的权值
采用梯度下降方法试图最小化网络输出值和目标值之间的误差平方
网络的误差定义公式，对所有网络输出的误差求和
Dd o u tp u sk kdkd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
反向传播算法（ 2）
反向传播算法面临的学习任务
– 搜索一个巨大的假设空间，这个空间由网络中所有的单元的所有可能的权值定义，得到类似图 4-4的误差曲面
– 在多层网络中，误差曲面可能有多个局部极小值，梯度下降仅能保证收敛到局部极小值
– 尽管有这个障碍，已经发现对于实践中很多应用，反向传播算法都产生了出色的结果
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
反向传播算法（ 3）
表 4-2包含两层 sigmoid单元的前馈网络的反向传播算法
BackPropagation(training_examples,?,nin,nout,nhidden)
training_examples是序偶 <,>的集合，是网络输入值向量，是目标输出值。
是学习速率,nin是网络输入的数量,nhidden是隐藏层单元数,nout是输出单元数，从单元 i到单元 j的输入表示为 xji，单元 i到单元 j的权值表示为 wji。
创建具有 nin个输入,nhidden个隐藏,nout个输出单元的网络
初始化所有的网络权值为小的随机值
在遇到终止条件前
– 对于训练样例 training_examples中的每个 <,>：
把输入沿网络前向传播
– 把实例 输入网络，并计算网络中每个单元 u的输出 ou
使误差沿网络反向传播
– 对于网络的每个输出单元 k，计算它的误差项?k?ok(1-ok)(tk-ok)
– 对于网络的每个隐藏单元 h，计算它的误差项?h?oh(1-oh)
– 更新每个网络权值 wji?wji+?wji，其中?wji=jxji
x? t? x? t?
x? t?
x?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
反向传播算法（ 4）
表 4-2给出的反向传播算法适用于包含两层
sigmoid单元的分层前馈网络，并且每一层的单元与前一层的所有单元相连。
表 4-2是反向传播算法的增量梯度下降（或随机梯度下降）版本
使用的符号做了如下扩展
– 网络中每个节点被赋予一个序号，这里的节点要么是网络的输入，要么是网络中某个单元的输出
– xji表示节点 i到单元 j的输入,wji表示对应的权值
–?n表示与单元 n相关联的误差项。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
表 4-2的算法解释
从建立一个具有期望数量的隐藏单元和输出单元的网络并初始化所有的网络的权值为小的随机数开始
给定一个固定的网络结构，算法的主循环就对训练样例进行反复的迭代
对于每一个训练样例，它应用目前的网络到这个样例，计算出对这个样例网络输出的误差，
然后更新网络中所有的权值
对这样的梯度下降步骤进行迭代，直到网络的性能达到可接受的精度为止
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
反向传播算法的梯度下降法则
表 4-2的梯度下降权更新法则与 delta训练法则相似
类似 delta法则，依照以下三者来更新每一个权
– 学习速率?
– 该权值涉及的输入值 xji
– 该单元的输出误差
不同于 delta法则的地方
– delta法则中的误差项被替换成一个更复杂的误差项
j
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
反向传播算法的误差项
输出单元 k的误差项
–?k与 delta法则中的 (tk-ok)相似，但乘上了 sigmoid挤压函数的导数 ok(1-ok)。
隐藏单元 h的误差项
– 因为训练样例仅对网络的输出提供了目标值 tk，所以缺少直接的目标值来计算隐藏单元的误差值
– 采取以下的间接方法计算隐藏单元的误差项：对受隐藏单元 h影响的每一个单元的误差?k进行加权求和，
每个误差?k权值为 wkh,wkh就是从隐藏单元 h到输出单元 k的权值。这个权值刻画了隐藏单元 h对于输出单元 k的误差应负责的程度。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
表 4-2的算法解释（ 2）
表 4-2的算法随着每个训练样例的出现而递增地更新权，
这一点与梯度下降的随机近似算法一致
要取得误差 E的真实梯度，需要在修改权值之前对所有训练样例的?jxji值求和
在典型的应用中，权值的更新迭代会被重复上千次
有很多终止条件可以用来停止这个过程
– 迭代的次数到了一个固定值时停止
– 当在训练样例上的误差降到某个阈值以下
– 在分离的验证样例集合上的误差符合某个标准
终止条件很重要，太少的迭代无法有效地降低误差，
太多的迭代会导致对训练数据的过度拟合
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
增加冲量项
因为反向传播算法的应用如此广泛，所以已经开发出了很多反向传播算法的变体
修改权值更新法则，使第 n次迭代时的权值的更新部分地依赖于发生在第 n-1次迭代时的更新，比如
–?wji(n)=jxji+wji(n-1)
右侧第一项就是表 4-2中的权值更新法则，第二项被称为冲量项
梯度下降的搜索轨迹就像一个球沿误差曲面滚下，冲量使球从一次迭代到下一次迭代时以同样的方向滚动
冲量有时会使这个球滚过误差曲面的局部极小值或平坦区域
冲量也具有在梯度不变的区域逐渐增大搜索步长的效果，从而加快收敛
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
学习任意的无环网络
表 4-2的算法可以简单地推广到任意深度的前馈网络
第 m层的单元 r的?r值由更深的第 m+1层?值根据下式计算
将这个算法推广到任何有向无环结构也同样简单，而不论网络中的单元是否被排列在统一的层上，计算任意内部单元的?的法则是：,Downstream(r)是在网络中单元 r的直接下游单元的集合，即输入中包括 r的输出的所有单元
层1)1( ms ssrrrr woo
)()1( rD o w n s tr e a ms ssrrrr oo
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
反向传播法则的推导
随机梯度下降算法迭代处理训练样例，
每次处理一个，对于每个训练样例 d，利用关于这个样例的误差 Ed的梯度修改权值
ji
dji wEw
o u tp u tsk kkd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
符号说明
xji，单元 j的第 i个输入
wji，与 xji相关联的权值
netj，单元 j的输入的加权和
oj，单元 j计算出的输出
tj，单元 j的目标输出
,sigmoid函数
outputs，网络最后一层的输出单元的集合
Downstream(j)，单元 j的输出到达的单元的集合
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
随机梯度下降法则的推导
，分情况讨论 的推导
输出单元
jijdji jjdjid xn e tEw
n e t
n e tEwE
j
dnetE
j
j
j
d
j
d netooEnetE
j
doE
)(
)(
)(2
2
1
)(
2
1
)(
2
1
2
2
jj
j
jj
jj
jj
j
o u tp u tsk
kk
j
ot
o
ot
ot
ot
o
ot
o
)1()( jj
j
j
j
j oon e tn e tn e to
)1()( jjjjjd oootn etE
jijjjjjidji xoootwEw )1()(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
随机梯度下降法则的推导（２）
隐藏单元
)(
)(
)(
)(
)(
)(
)1(
)1(
jD o w n s tr e a mk
kjkjj
jD o w n s tr e a mk
jjkjk
jD o w n s tr e a mk j
j
kjk
jD o w n s tr e a mk j
j
j
k
k
jD o w n s tr e a mk j
k
k
jD o w n s tr e a mk j
k
k
d
woo
oow
ne t
o
w
ne t
o
o
ne t
ne t
ne t
ne t
ne t
ne t
E
j
dnetE
)()1( jD o w n s t r e a mk kjkjjjiji wooxw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
收敛性和局部极小值
对于多层网络，误差曲面可能含有多个不同的局部极小值，梯度下降可能陷入这些局部极小值中的任何一个
对于多层网络，反向传播算法仅能保证收敛到误差 E的某个局部极小值，不一定收敛到全局最小误差
尽管缺乏对收敛到全局最小误差的保证，反向传播算法在实践中仍是非常有效的函数逼近算法
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
收敛性和局部极小值（２）
网络的权越多，误差曲面的维数越多，也就越可能为梯度下降提供更多的逃逸路线
考虑随着训练中迭代次数的增加网络权值的演化方式
– 如果把网络的权值初始化为接近于 0的值，那么在早期的梯度下降步骤中，网络将表现为一个非常平滑的函数，近似为输入的线性函数，
这是因为 sigmoid函数本身在权值靠近 0时接近线性
– 仅当权值增长一定时间后，它们才会到达可以表示高度非线性网络函数的程度，可以预期在这个能表示更复杂函数的权空间区域存在更多的局部极小值
– 但是当权到达这一点时，它们已经足够靠近全局最小值，即便它是这个区域的局部最小值也是可以接受的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
收敛性和局部极小值（ 3）
用来缓解局部极小值问题的启发式规则
– 为梯度更新法则加一个冲量，可以带动梯度下降过程，冲过狭窄的局部极小值（原则上，也可能冲过狭窄的全局最小值）
– 使用随机的梯度下降而不是真正的梯度下降。随机近似对于每个训练样例沿一个不同的误差曲面有效下降，这些不同的误差曲面通常有不同的局部极小值，这使得下降过程不太可能陷入一个局部极小值
– 使用同样的数据训练多个网络，但用不同的随机权值初始化每个网络。如果不同的训练产生不同的局部极小值，那么对分离的验证集合性能最好的那个网络将被选中，或者保留所有的网络，输出是所有网络输出的平均值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
前馈网络的表征能力
布尔函数：任何布尔函数可以被具有两层单元的网络准确表示，尽管在最坏情况下所需隐藏单元的数量随着网络输入数量的增加成指数级增长。
– 考虑下面的通用方案：对于每一个可能的输入向量，
创建不同的隐藏单元，并设置它的权值使当且仅当这个特定的向量输入到网络时该单元被激活，这样就产生了一个对于任意输入仅有一个单元被激活的隐藏层，然后把输出单元实现为一个仅由所希望的输入模式激活的或门。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 55
前馈网络的表征能力（ 2）
连续函数：每个有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个结论适用于在隐藏层使用 sigmoid单元、在输出层使用（非阈值）线性单元的网络。所需的隐藏单元数量依赖于要逼近的函数。
任意函数：任意函数可以被一个有三层单元的网络以任意精度逼近。两个隐藏层使用 sigmoid单元，输出层使用线性单元，每层所需单元数不确定。
– 证明方法：首先说明任意函数可以被许多局部化函数的线性组合逼近，这些局部化函数的值除了某个小范围外都为 0；然后说明两层的 sigmoid单元足以产生良好的局部逼近
注意：梯度下降从一个初始值开始，因此搜索范围里的网络权向量可能不包含所有的权向量
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 56
假设空间搜索和归纳偏置
反向传播算法的假设空间是 n个网络权值形成的 n维欧氏空间。这个空间是连续的，与决策树学习和其他基于离散表示的方法的假设空间不同
假设空间的连续性以及误差 E关于假设的连续参数可微，
导致了一个定义良好的误差梯度，为最佳假设的搜索提供了一个非常有用的结构。
精确地刻画出反向传播学习的归纳偏置是有难度的，
它依赖于梯度下降搜索和权空间覆盖可表征函数空间的方式的相互作用性
把这一偏置粗略地刻画为在数据点之间平滑插值。如果给定两个正例，它们之间没有反例，反向传播算法会倾向于把这两点之间的点也标记为正例
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 57
隐藏层表示
反向传播算法的一个迷人特性是：它能够在网络内部的隐藏层发现有用的中间表示
– 训练样例仅包含网络输入和输出，权值调节的过程可以自由地设置权值，来定义任何隐藏单元表示，这些隐藏单元表示在使误差 E达到最小时最有效。
– 引导反向传播算法定义新的隐藏层特征，这些特征在输入中没有明确表示出来，但能捕捉输入实例中与学习目标函数最相关的特征
多层网络在隐藏层自动发现有用表示的能力是 ANN学习的一个关键特性。允许学习器创造出设计者没有明确引入的特征。
网络中使用的单元层越多，就可以创造出越复杂的特征
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 58
泛化、过度拟合和停止判据
权值更新算法的终止条件
– 一种选择是，对训练样例的误差降低至某个预先定义的阈值之下
这不是一个好的策略，因为反向传播算法容易过度拟合训练样例，降低对于其他未见实例的泛化精度
泛化精度：网络拟合训练数据外的实例的精度
图 4-9，尽管在训练样例上的误差持续下降，但在验证样例上测量到的误差先下降，后上升。
– 因为这些权值拟合了训练样例的“特异性”，而这个特异性对于样例的一般分布没有代表性。 ANN中大量的权值参数为拟合这样的“特异性”提供了很大的自由度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 59
过度拟合
为什么过度拟合发生在迭代的后期，而不是早期？
– 设想网络的权值是被初始化为小随机值的，使用这些几乎一样的权值仅能描述非常平滑的决策面
– 随着训练的进行，一些权值开始增长，以降低在训练数据上的误差，同时学习到的决策面的复杂度也在增加
– 如果权值调整迭代次数足够多，反向传播算法可能会产生过度复杂的决策面，拟合了训练数据中的噪声和训练样例中没有代表性的特征
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 60
过度拟合解决方法
权值衰减
– 它在每次迭代过程中以某个小因子降低每个权值，
这等效于修改 E的定义，加入一个与网络权值的总量相应的惩罚项，此方法的动机是保持权值较小，
从而使学习过程向着复杂决策面的反方向偏置
验证数据
– 一个最成功的方法是在训练数据外再为算法提供一套验证数据，应该使用在验证集合上产生最小误差的迭代次数，不是总能明显地确定验证集合何时达到最小误差
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 61
过度拟合解决方法（ 2）
一般而言，过度拟合是一个棘手的问题
交叉验证方法在可获得额外的数据提供验证集合时工作得很好，但是小训练集合的过度拟合问题更为严重
k-fold交叉方法
– 把训练样例分成 k份，然后进行 k次交叉验证过程，每次使用不同的一份作为验证集合，其余 k-1份合并作为训练集合。
– 每个样例会在一次实验中被用作验证样例，在 k-1次实验中被用作训练样例
– 每次实验中，使用上面讨论的交叉验证过程来决定在验证集合上取得最佳性能的迭代次数，然后计算这些迭代次数的均值
– 最后，运行一次反向传播算法，训练所有 m个实例并迭代 次
i
i
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 62
举例：人脸识别
训练样例
– 20个不同人的摄影图像
– 每个人大约 32张图像
不同的表情
– 快乐、沮丧、愤怒、中性
不同的方向
– 左、右、正前、上
不同的穿戴
– 是否带眼镜
– 共 624幅灰度图像
分辨率为 120x128，每个像素使用 0（黑）到 255（白）的灰度值描述
任务：学习图像中人脸的朝向
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 63
人脸识别 ——设计要素
输入编码
– ANN的输入必然是图像的某种表示，那么设计的关键是如何编码这幅图像
– 例如，可以对图像进行预处理，分解出边缘、亮度一致的区域或其他局部图像特征，然后把这些特征输入网络，问题是导致每幅图像有不同数量的特征参数，而 ANN具有固定数量的输入单元
– 把图像编码成固定的 30x32像素的亮度值，每个像素对应一个网络输入，把范围是 0到 255的亮度值按比例线性缩放到 0到 1的区间内，以使网络输入和隐藏单元、输出单元在同样的区间取值。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 64
人脸识别 ——设计要素（ 2）
输出编码
– ANN必须输出 4个值中的一个来表示输入图像中人脸的朝向
– 可以使用单一的输出单元来编码这 4种情况
– 这里使用 4个不同的输出单元，每一个对应 4种可能朝向中的一种，取具有最高值的输出作为网络的预测值。称为 1-of-n输出编码
选择 1-of-n的原因
– 为网络表示目标函数提供了更大的自由度
– 最高值输出和次高值输出间的差异可以作为对网络预测的置信度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 65
人脸识别 ——设计要素（ 3）
输出单元的目标值
– 一个显而易见的方法,<1,0,0,0>...
– 这里使用的方法,<0.9,0.1,0.1,0.1>...
– 避免使用 0和 1作为目标值的原因
sigmoid单元对于有限权值不能产生这样的输出
如果企图训练网络来准确匹配目标值 0和 1，梯度下降将会迫使权值无限增长
0.1和 0.9是 sigmoid单元在有限权值情况下可以完成的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 66
人脸识别 ——设计要素（ 4）
网络结构图
– 网络包含多少个单元以及如何互连？
– 最普遍的结构是分层网络，一层的每个单元向前连接到下一层的每一个单元
– 目前采用了包含两层 sigmoid单元的标准结构
– 隐藏单元的数量
3个，达到 90%的精度，训练时间约 5分钟
30个，提高 1~2个百分点，训练时间约 1个小时
– 实践发现，需要某个最小数量的隐藏单元来精确地学习目标函数，并且超过这个数量的多余的隐藏单元不会显著地提高泛化精度
– 如果没有使用交叉验证，那么增加隐藏单元数量经常会增加过度拟合训练数据的倾向，从而降低泛化精度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 67
人脸识别 ——设计要素（ 5）
学习算法的其他参数
– 学习速率 设定为 0.3，冲量设定为 0.3
– 赋予这两个参数更低的值会产生大体相当的泛化精度，但需要更长的训练时间
– 如果赋予更高的值，训练将不能收敛到一个具有可接受误差的网络
– 适用完全的梯度下降
– 输出单元的权值被初始化为小的随机值
– 输入单元的权值被初始化为 0
– 训练的迭代次数的选择可以通过分割可用的数据为训练集合和验证集合来实现
– 最终选择的网络是对验证集合精度最高的网络
– 最终报告的精度是在没有对训练产生任何影响的第三个集合 ——测试集合上测量得到的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 68
学习到的隐藏层表示
图中紧挨人脸图像下的 4个矩形，每个矩形描绘了网络中 4个输出单元中的一个权值，每个矩形中的 4个小方形表示和这个输出单元关联的 4个权值
隐藏单元的权值显示在输出单元的下边，每个隐藏单元接受所有 30x32个像素输入。与这些输入关联的
30x32个权值被显示在它们对应的像素的位置
针对每一个训练样例，梯度下降迭代 100次后的网络权值显示在图的下部。
– 如果一个人的脸是转向他的右面，那么他的亮度高的皮肤会大致与这个隐藏单元中的较大正值对齐，同时他的亮度低的头发会大致与负权值对齐，这导致此单元输出一个较大的值，
同样的图像会使第 3个隐藏单元输出一个接近 0的值。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 69
其他可选的误差函数
为权值增加一个惩罚项
– 把一个随着权向量幅度增长的项加入到 E中，这导致梯度下降搜寻较小的权值向量，从而减小过度拟合的风险，等价于使用权衰减策略
对误差增加一项目标函数的斜率或导数
– 某些情况下，训练信息中不仅有目标值，而且还有关于目标函数的导数
Dd ji jio u t p u tsk kdkd wotwE,22)(21)(
Dd o u t p u t sk i n p u t sj jdkdjdkdkdkd xoxtotwE 22)(21)(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 70
其他可选的误差函数（ 2）
使网络对目标值的交叉熵最小化
– 比如根据借贷申请者的年龄和存款余额，预测他是否会还贷，目标函数最好以申请者还贷的概率的形式输出，而不是输出明确的 0和 1。在这种情况下，
可以证明最小化交叉熵的网络可以给出最好的概率估计。交叉熵定义如下：
– 第 6章讨论了何时及为什么最可能的网络假设就是使交叉熵最小化的假设，并推导了相应的 sigmoid单元的梯度下降权值调整法则，还描述了在什么条件下最可能的假设就是使误差平方和最小化的假设。
)1lo g ()1(lo g ddDd dd otot
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 71
其他可选的误差函数（ 3）
通过权值共享改变有效误差函数
– 把与不同单元或输入相关联的权“捆绑在一起”，
强迫不同的网络权值取一致的值，通常是为了实施人类设计者事先知道的某个约束
– 约束了假设的潜在空间，减小了过度拟合的风险
– 实现方法，首先在共享权值的每个单元分别更新各个权值，然后取这些权值的平均，再用这个平均值替换每个需要共享的权值。
– 被共享的权值比没有共享的权值更有效地适应一个不同的误差函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 72
其他可选的误差最小化过程
梯度下降是搜寻使误差函数最小化的假设的最通用的方法之一，
但不是最高效的
不妨把权值更新方法看作是要决定这样两个问题：
– 选择一个改变当前权值向量的方向（梯度的负值）
– 选择要移动的距离（学习速率）
线搜索，每当选定了一条确定权值更新方向的路线，那么权更新的距离是通过沿这条线寻找误差函数的最小值来选择的
共轭梯度，进行一系列线搜索来搜索误差曲面的最小值，这一系列搜索的第一步仍然使用梯度的反方向，在后来的每一步中，选择使误差梯度分量刚好为 0并保持为 0的方向
像共轭梯度这样的方法对最终网络的泛化误差没有明显的影响，
唯一可能的影响是，不同的误差最小化过程会陷入不同的局部最小值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 73
递归网络
递归网络是有如下特征的人工神经网络
– 适用于时序数据
– 使用网络单元在时间 t的输出作为其他单元在时间
t+1的输入
– 递归网络支持在网络中使用某种形式的有向环
考虑一个时序预测任务
– 根据当天的经济指标 x(t)，预测下一天的股票平均市值 y(t+1)
– 训练一个前馈网络预测输出 y(t+1)，图 4-11a
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 74
递归网络
预测 y(t+1)时，考虑任意过去的时间窗内的信息，图 4-11b
图 4-11b那样的递归网络可以使用反向传播算法的简单变体来训练
把递归网络拷贝成几份，用不同拷贝间的连接替换掉反馈环，这个大的网络不再包含回路，所以可以直接使用反向传播算法来训练
实践中，我们仅保留一份递归网络和权值集合的拷贝，在训练了展开的网络后，可以取不同拷贝中权值的平均值作为最终网络的对应的权值
实践中，递归网络比没有反馈环的网络更难以训练，泛化的可靠性也不如后者，然而它们仍因较强的表征力而保持着重要性
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 75
动态修改网络结构
动态增长或压缩网络单元和单元间连接的数量
从一个不包含隐藏单元的网络开始，然后根据需要增加隐藏单元来增长网络，直到训练误差下降到某个可接受的水平
– 级联相关算法，每当加入一个新的隐藏单元，它的输入包括所有原始的网络输入和已经存在的隐藏单元的输出，网络以这种方式增长，积聚隐藏单元，直到网络的残余误差下降到某个可接受的水平
– 由于每一步仅有一层网络在被训练，级联相关算法显著减少了训练时间
– 算法的一个实际困难是，因为算法可以无限制地增加单元，
很容易过度拟合训练数据。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 76
动态修改网络结构
从一个复杂的网络开始修剪掉某些连接
– 判断某个权是否无关紧要的一种方法是看它的值是否接近 0
– 在实践中更加成功的方法是考虑这个权值的一个小的变化对误差的影响（连接的显著性）
– 最不显著的连接被拆除，重复这个过程，直到遇到某个终止条件为止（最优脑损伤法）
一般而言，动态修改网络结构的方法能否稳定地提高反向传播算法的泛化精度还有待研究
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 77
小结
人工神经网络为学习实数值和向量值函数提供了一种实际的方法，对于连续值和离散值的属性都可以使用，
并且对训练数据中的噪声具有很好的健壮性。
反向传播算法是最常见的网络学习算法
反向传播算法考虑的假设空间是固定连接的有权网络所能表示的所有函数的空间
包含 3层单元的前馈网络能够以任意精度逼近任意函数，
只要每一层有足够数量的单元。即使是一个实际大小的网络也能够表示很大范围的高度非线性函数
反向传播算法使用梯度下降方法搜索可能假设的空间，
迭代减小网络的误差以拟合训练数据
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 78
小结（ 2）
梯度下降收敛到训练误差相对网络权值的局部极小值。只要训练误差是假设参数的可微函数，
梯度下降可用来搜索很多连续参数构成的假设空间
反向传播算法能够创造出网络输入中没有明确出现的特征。
交叉验证方法可以用来估计梯度下降搜索的合适终止点，从而最小化过度拟合的风险
其他 ANN学习算法，递归网络方法训练包含有向环的网络，级联相关算法改变权和网络结构
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 79
补充读物
本书其他与 ANN学习相关的章节
– 第 6章给出了选择最小化误差平方和的贝叶斯论证，
以及在某些情况下，用最小化交叉熵代替最小化误差平方和的方法
– 第 7章讨论了为可靠学习布尔函数所需要的训练实例数量的理论结果，以及某些类型网络的 VC维
– 第 5章讨论了过度拟合和避免过度拟合的方法
– 第 12章讨论了使用以前知识来提高泛化精度的方法
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 80
补充读物（ 2）
发展历程
– McCulloch & Pitts
– Widrow & Hoff
– Rosenblatt
– Minsky & Papert
– Rumelhart & McClelland; Parker
教科书
– Duda & Hart
– Windrow & Stearns
– Rumelhart & McClelland
机器学习第 4章 人工神经网络（ ANN）
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
人工神经网络提供了一种普遍且实用的方法从样例中学习值为实数、离散值或向量的函数
反向传播算法，使用梯度下降来调节网络参数以最佳拟合由输入 -输出对组成的训练集合
人工神经网络对于训练数据中的错误健壮性很好
人工神经网络已被成功应用到很多领域，例如视觉场景分析，语音识别，机器人控制
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
神经网络学习对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性很强的方法
对于某些类型的问题，如学习解释复杂的现实世界中的传感器数据，人工神经网络是目前知道的最有效的学习方法
反向传播算法
成功例子，学习识别手写字符，学习识别口语，
学习识别人脸
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
生物学动机
ANN受到生物学的启发，生物的学习系统是由相互连接的神经元组成的异常复杂的网络。
ANN由一系列简单的单元相互密集连接构成的，其中每一个单元有一定数量的实值输入，并产生单一的实数值输出
人脑的构成，大约有 1011个神经元，平均每一个与其他 104个相连
神经元的活性通常被通向其他神经元的连接激活或抑制
最快的神经元转换时间比计算机慢很多，然而人脑能够以惊人的速度做出复杂度惊人的决策
很多人推测，生物神经系统的信息处理能力一定得益于对分布在大量神经元上的信息表示的高度并行处理
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
生物学动机（ 2）
ANN系统的一个动机就是获得这种基于分布表示的高度并行算法
ANN并未模拟生物神经系统中的很多复杂特征
ANN的研究分为两个团体
– 使用 ANN研究和模拟生物学习过程
– 获得高效的机器学习算法，不管这种算法是否反映了生物过程
本书属于后一个研究团体
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
神经网络表示
ALVINN系统
– Pomerleau 1993
– 使用一个学习到的 ANN以正常的速度在高速公路上驾驶汽车
– ANN的输入是一个 30x32像素的网格，输出是车辆行进的方向
– 每个节点对应一个网络单元的输出，而从下方进入节点的实线为其输入
– 隐藏单元，输出仅在网络内部，不是整个网络输出的一部分
– 每个输出单元对应一个特定的驾驶方向，这些单元的输出决定哪一个方向是被最强烈推荐的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
神经网络表示（ 2）
ALVINN是很多 ANN的典型结构，所有单元分层互连形成一个有向无环图
通常,ANN图结构可以有很多种类型
– 无环或有环
– 有向或无向
本章讨论以反向传播算法为基础的 ANN方法
反向传播算法假定网络是一个固定结构，对应一个有向图，可能包含环
ANN学习就是为图中每一条边选取权值
大多数实际应用与 ALVINN相似
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
适合神经网络学习的问题
训练集合为含有噪声的复杂传感器数据，
例如来自摄像机和麦克风
需要较多符号表示的问题，例如决策树学习的任务，能够取得和决策树学习大体相当的结果
反向传播算法是最常用的 ANN学习技术
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
反向传播算法适合问题的特征
实例是用很多“属性 -值”对表示的
目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量
训练数据可能包含错误
可容忍长时间的训练
可能需要快速求出目标函数值
人类能否理解学到的目标函数是不重要的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
本章余后部分提纲
讨论训练单个单元的学习算法
介绍组成神经网络的几种主要单元
– 感知器（ perceptron）
– 线性单元（ liner unit）
– sigmoid单元（ sigmoid unit）
给出训练多层网络的反向传播算法
考虑几个一般性问题
– ANN的表征能力
– 假设空间搜索的本质特征
– 过度拟合问题
– 反向传播算法的变体
例子，利用反向传播算法训练识别人脸的 ANN
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
感知器
一种类型的 ANN系统是以感知器为基础
感知器以一个实数值向量作为输入，计算这些输入的线性组合，如果结果大于某个阈值，就输出 1，否则输出 -1
其中每个 wi是一个实数常量，或叫做权值，用来决定输入 xi对感知器输出的贡献率。特别地,-w0是阈值。
o t h e r w is e xwxwwxxo nnn 0..,11),.,.,( 1101
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
感知器（ 2）
两种简化形式，附加一个常量输入 x0=1，前面的不等式写成或写成向量形式
为了简短起见，把感知器函数写为其中，
00ni iixw
0xw
)sgn()( xwxo
otherw iseyy 011)s g n (
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
感知器（ 3）
学习一个感知器意味着选择权 w0,…,w n的值。所以感知器学习要考虑的候选假设空间 H就是所有可能的实数值权向量的集合 }|{ 1 nRwwH
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
感知器的表征能力
可以把感知器看作是 n维实例空间（即点空间）中的超平面决策面
对于超平面一侧的实例，感知器输出 1，
对于另一侧的实例，输出 -1
这个决策超平面方程是
可以被某个超平面分割的样例集合，称为线性可分样例集合
0xw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
感知器的表征能力（ 2）
单独的感知器可以用来表示很多布尔函数
表示 m-of-n函数
感知器可以表示所有的原子布尔函数：
与、或、与非、或非
然而，一些布尔函数无法用单一的感知器表示，例如异或
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
感知器的表征能力（ 3）
因为所有的布尔函数都可表示为基于原子函数的互连单元的某个网络，因此感知器网络可以表示所有的布尔函数。事实上，只需要两层深度的网络，比如表示析取范式
注意，要把一个 AND感知器的输入求反只要简单地改变相应输入权的符号
因为感知器网络可以表示大量的函数，而单独的单元不能做到这一点，所以我们感兴趣的是学习感知器组成的多层网络
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
感知器训练法则
虽然我们的目的是学习由多个单元互连的网络，但我们还是要从如何学习单个感知器的权值开始
单个感知器的学习任务，决定一个权向量，它可以使感知器对于给定的训练样例输出正确的 1或 -1
我们主要考虑两种算法
– 感知器法则
– delta法则
这两种算法保证收敛到可接受的假设，在不同的条件下收敛到的假设略有不同
这两种算法提供了学习多个单元构成的网络的基础
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
感知器法则
算法过程
– 从随机的权值开始
– 反复应用这个感知器到每个训练样例，只要它误分类样例就修改感知器的权值
– 重复这个过程，直到感知器正确分类所有的训练样例
感知器训练法则其中
iii www
ii xotw )(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
感知器法则（ 2）
为什么这个更新法则会成功收敛到正确的权值呢？
– 一些例子
– 可以证明（ Minskey & Papert 1969）
如果训练样例线性可分，并且使用了充分小的?
否则，不能保证
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
梯度下降和 delta法则
delta法则克服感应器法则的不足，在线性不可分的训练样本上，收敛到目标概念的最佳近似
delta法则的关键思想是，使用梯度下降来搜索可能的权向量的假设空间，以找到最佳拟合训练样例的权向量
delta法则为反向传播算法提供了基础，而反向传播算法能够学习多个单元的互连网络
对于包含多种不同类型的连续参数化假设的假设空间，梯度下降是必须遍历这样的空间的所有算法的基础
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
梯度下降和 delta法则（ 2）
把 delta训练法则理解为训练一个无阈值的感知器
指定一个度量标准来衡量假设相对于训练样例的训练误差
第 6章给出了选择这种 E定义的一种贝叶斯论证，
在一定条件下，使 E最小化的假设就是 H中最可能的假设
xwxo)(
Dd dd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
可视化假设空间
图 4-4
– 根据 E的定义，误差曲面是一个抛物面，存在一个单一全局最小值
梯度下降搜索从一个任意的初始权向量开始，然后沿误差曲面最陡峭下降的方向，以很小的步伐反复修改这个向量，
直到得到全局的最小误差点
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
梯度下降法则的推导
如何发现沿误差曲面最陡峭下降的方向？
– 通过计算 E相对向量 的每个分量的导数，这个向量导数被称为 E对于 的梯度，记作
– 当梯度被解释为权空间的一个向量时，它确定了使
E最陡峭上升的方向，所以这个向量的反方向给出了最陡峭下降的方向
梯度训练法则其中，
w?
w?
)(wE
www
)(wEw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
梯度下降法则的推导（ 2）
需要一个高效的方法在每一步都计算这个梯度
梯度下降权值更新法则
Dd idddi xotwE ))((
Dd idddi xotw )(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
梯度下降法则的推导（ 3）
表 4-1，训练线性单元的梯度下降算法
Gradient-Descent(training_examples,?)
training_examples中每个训练样例形式为序偶 <,t>,是输入值向量，
t是目标输出值,?是学习速率
初始化每个 wi为某个小的随机值
遇到终止条件之前，做以下操作
– 初始化每个?wi为 0
– 对于训练样例 training_examples中的每个 <,t>，做
把实例 输入到此单元，计算输出 o
对于线性单元的每个权增量?wi，做
wiwi+?(t-o)xi
– 对于线性单元的每个权 wi，做
wi?wi+?wi
x? x?
x?
x?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
梯度下降法则的推导（ 4）
梯度下降算法如下
– 选取一个初始的随机权向量
– 应用线性单元到所有的训练样例，根据公式 4.7计算每个权值的 更新权值
因为误差曲面仅包含一个全局的最小值，所以无论训练样例是否线性可分，算法都会收敛到具有最小误差的权向量，条件是使用足够小的学习速率
算法的一种常用改进方法是随着梯度下降步数的增加逐渐减小学习速率
w?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
梯度下降的随机近似
梯度下降是一种重要的通用学习范型，它是搜索庞大假设空间或无限假设空间一种策略
梯度下降应用于满足以下条件的任何情况
– 假设空间包含连续参数化的假设
– 误差对于这些假设参数可微
梯度下降的主要实践问题
– 有时收敛过程可能非常慢
– 如果在误差曲面上有多个局部极小值，那么不能保证找到全局最小值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
梯度下降的随机近似（ 2）
随机梯度下降（或称增量梯度下降）
– 根据某个单独样例的误差增量计算权值更新，得到近似的梯度下降搜索（随机取一个样例）
– 对表 4-1算法的修改
– 可以看作为每个单独的训练样例定义不同的误差函数
– 在迭代所有训练样例时，这些权值更新的序列给出了对于原来误差函数的梯度下降的一个合理近似
– 通过使下降速率的值足够小，可以使随机梯度下降以任意程度接近于真实梯度下降
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
梯度下降的随机近似（ 2）
标准梯度下降和随机梯度下降之间的关键区别
– 标准梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查每个训练样例来更新的
– 在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算（？）
– 标准梯度下降，由于使用真正的梯度，标准梯度下降对于每一次权值更新经常使用比随机梯度下降大的步长
– 如果标准误差曲面有多个局部极小值，随机梯度下降有时可能避免陷入这些局部极小值中
实践中，标准和随机梯度下降方法都被广泛应用
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
梯度下降的随机近似（ 3）
delta法则（增量法则），又称 LMS法则,Adaline法则、
Windrow-Hoff法则
公式 4.10与 4.4.2节的感知器法则的相似和区别
delta法则可以学习非阈值线性单元的权，也可以用来训练有阈值的感知器单元。
如果非阈值输出能够被训练到完美拟合这些值，那么阈值输出也会完美拟合它们
即使不能完美地拟合目标值，只要线性单元的输出具有正确的符号，阈值输出就会正确拟合目标值
尽管这个过程会得到使线性单元输出的误差最小化的权值，但这些权值不能保证阈值输出的误差最小化
（？）
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
感知器学习小结
感知器法则和 delta法则的关键差异
– 前者根据阈值化的感知器输出的误差更新权值
– 后者根据输入的非阈值化线性组合的误差来更新权值
这个差异带来不同的收敛特性
– 前者经过有限次的迭代收敛到一个能理想分类训练数据的假设，条件是训练样例线性可分
– 后者可能经过极长的时间，渐近收敛到最小误差假设，但无论训练样例是否线性可分都会收敛
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
感知器学习小结（ 2）
学习权向量的第 3种方法是线性规划
线性规划是解线性不等式方程组的一种通用的有效方法
这种方法仅当训练样例线性可分时有解
Duda和 Hart给出了一种更巧妙的适合非线性可分的情况的方法
更大的问题是，无法扩展到训练多层网络，而
delta法则可以很容易扩展到多层网络
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
多层网络和反向传播算法
多层网络能够表示种类繁多的非线性曲面
图 4-5描述了一个典型的多层网络和它的决策曲面
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
可微阈值单元
使用什么类型的单元来构建多层网络？
多个线性单元的连接仍产生线性函数，而我们希望构建表征非线性函数的网络
感知器单元可以构建非线性函数，但它的不连续阈值使它不可微，不适合梯度下降算法
我们需要的单元满足的条件
– 输出是输入的非线性函数
– 输出是输入的可微函数
Sigmoid单元，类似于感知器单元，但基于一个平滑的可微阈值函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
可微阈值单元（ 2）
图 4-6
sigmoid单元先计算它的输入的线性组合，
然后应用到一个阈值上，阈值输出是输入的连续函数其中
)( xwo
yey1 1)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
可微阈值单元（ 3）
sigmoid函数
– 也称 logistic函数
– 挤压函数
– 输出范围是 0到 1
– 单调递增
– 导数很容易用函数本身表示
sigmoid函数的变型
– 其他易计算导数的可微函数
– 增加陡峭性
– 双曲正切函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
反向传播算法
用来学习多层网络的权值
采用梯度下降方法试图最小化网络输出值和目标值之间的误差平方
网络的误差定义公式，对所有网络输出的误差求和
Dd o u tp u sk kdkd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
反向传播算法（ 2）
反向传播算法面临的学习任务
– 搜索一个巨大的假设空间，这个空间由网络中所有的单元的所有可能的权值定义，得到类似图 4-4的误差曲面
– 在多层网络中，误差曲面可能有多个局部极小值，梯度下降仅能保证收敛到局部极小值
– 尽管有这个障碍，已经发现对于实践中很多应用，反向传播算法都产生了出色的结果
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
反向传播算法（ 3）
表 4-2包含两层 sigmoid单元的前馈网络的反向传播算法
BackPropagation(training_examples,?,nin,nout,nhidden)
training_examples是序偶 <,>的集合，是网络输入值向量，是目标输出值。
是学习速率,nin是网络输入的数量,nhidden是隐藏层单元数,nout是输出单元数，从单元 i到单元 j的输入表示为 xji，单元 i到单元 j的权值表示为 wji。
创建具有 nin个输入,nhidden个隐藏,nout个输出单元的网络
初始化所有的网络权值为小的随机值
在遇到终止条件前
– 对于训练样例 training_examples中的每个 <,>：
把输入沿网络前向传播
– 把实例 输入网络，并计算网络中每个单元 u的输出 ou
使误差沿网络反向传播
– 对于网络的每个输出单元 k，计算它的误差项?k?ok(1-ok)(tk-ok)
– 对于网络的每个隐藏单元 h，计算它的误差项?h?oh(1-oh)
– 更新每个网络权值 wji?wji+?wji，其中?wji=jxji
x? t? x? t?
x? t?
x?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
反向传播算法（ 4）
表 4-2给出的反向传播算法适用于包含两层
sigmoid单元的分层前馈网络，并且每一层的单元与前一层的所有单元相连。
表 4-2是反向传播算法的增量梯度下降（或随机梯度下降）版本
使用的符号做了如下扩展
– 网络中每个节点被赋予一个序号，这里的节点要么是网络的输入，要么是网络中某个单元的输出
– xji表示节点 i到单元 j的输入,wji表示对应的权值
–?n表示与单元 n相关联的误差项。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
表 4-2的算法解释
从建立一个具有期望数量的隐藏单元和输出单元的网络并初始化所有的网络的权值为小的随机数开始
给定一个固定的网络结构，算法的主循环就对训练样例进行反复的迭代
对于每一个训练样例，它应用目前的网络到这个样例，计算出对这个样例网络输出的误差，
然后更新网络中所有的权值
对这样的梯度下降步骤进行迭代，直到网络的性能达到可接受的精度为止
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
反向传播算法的梯度下降法则
表 4-2的梯度下降权更新法则与 delta训练法则相似
类似 delta法则，依照以下三者来更新每一个权
– 学习速率?
– 该权值涉及的输入值 xji
– 该单元的输出误差
不同于 delta法则的地方
– delta法则中的误差项被替换成一个更复杂的误差项
j
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
反向传播算法的误差项
输出单元 k的误差项
–?k与 delta法则中的 (tk-ok)相似，但乘上了 sigmoid挤压函数的导数 ok(1-ok)。
隐藏单元 h的误差项
– 因为训练样例仅对网络的输出提供了目标值 tk，所以缺少直接的目标值来计算隐藏单元的误差值
– 采取以下的间接方法计算隐藏单元的误差项：对受隐藏单元 h影响的每一个单元的误差?k进行加权求和，
每个误差?k权值为 wkh,wkh就是从隐藏单元 h到输出单元 k的权值。这个权值刻画了隐藏单元 h对于输出单元 k的误差应负责的程度。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
表 4-2的算法解释（ 2）
表 4-2的算法随着每个训练样例的出现而递增地更新权，
这一点与梯度下降的随机近似算法一致
要取得误差 E的真实梯度，需要在修改权值之前对所有训练样例的?jxji值求和
在典型的应用中，权值的更新迭代会被重复上千次
有很多终止条件可以用来停止这个过程
– 迭代的次数到了一个固定值时停止
– 当在训练样例上的误差降到某个阈值以下
– 在分离的验证样例集合上的误差符合某个标准
终止条件很重要，太少的迭代无法有效地降低误差，
太多的迭代会导致对训练数据的过度拟合
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
增加冲量项
因为反向传播算法的应用如此广泛，所以已经开发出了很多反向传播算法的变体
修改权值更新法则，使第 n次迭代时的权值的更新部分地依赖于发生在第 n-1次迭代时的更新，比如
–?wji(n)=jxji+wji(n-1)
右侧第一项就是表 4-2中的权值更新法则，第二项被称为冲量项
梯度下降的搜索轨迹就像一个球沿误差曲面滚下，冲量使球从一次迭代到下一次迭代时以同样的方向滚动
冲量有时会使这个球滚过误差曲面的局部极小值或平坦区域
冲量也具有在梯度不变的区域逐渐增大搜索步长的效果，从而加快收敛
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
学习任意的无环网络
表 4-2的算法可以简单地推广到任意深度的前馈网络
第 m层的单元 r的?r值由更深的第 m+1层?值根据下式计算
将这个算法推广到任何有向无环结构也同样简单，而不论网络中的单元是否被排列在统一的层上，计算任意内部单元的?的法则是：,Downstream(r)是在网络中单元 r的直接下游单元的集合，即输入中包括 r的输出的所有单元
层1)1( ms ssrrrr woo
)()1( rD o w n s tr e a ms ssrrrr oo
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
反向传播法则的推导
随机梯度下降算法迭代处理训练样例，
每次处理一个，对于每个训练样例 d，利用关于这个样例的误差 Ed的梯度修改权值
ji
dji wEw
o u tp u tsk kkd otwE 2)(21)(?
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
符号说明
xji，单元 j的第 i个输入
wji，与 xji相关联的权值
netj，单元 j的输入的加权和
oj，单元 j计算出的输出
tj，单元 j的目标输出
,sigmoid函数
outputs，网络最后一层的输出单元的集合
Downstream(j)，单元 j的输出到达的单元的集合
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
随机梯度下降法则的推导
，分情况讨论 的推导
输出单元
jijdji jjdjid xn e tEw
n e t
n e tEwE
j
dnetE
j
j
j
d
j
d netooEnetE
j
doE
)(
)(
)(2
2
1
)(
2
1
)(
2
1
2
2
jj
j
jj
jj
jj
j
o u tp u tsk
kk
j
ot
o
ot
ot
ot
o
ot
o
)1()( jj
j
j
j
j oon e tn e tn e to
)1()( jjjjjd oootn etE
jijjjjjidji xoootwEw )1()(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
随机梯度下降法则的推导（２）
隐藏单元
)(
)(
)(
)(
)(
)(
)1(
)1(
jD o w n s tr e a mk
kjkjj
jD o w n s tr e a mk
jjkjk
jD o w n s tr e a mk j
j
kjk
jD o w n s tr e a mk j
j
j
k
k
jD o w n s tr e a mk j
k
k
jD o w n s tr e a mk j
k
k
d
woo
oow
ne t
o
w
ne t
o
o
ne t
ne t
ne t
ne t
ne t
ne t
E
j
dnetE
)()1( jD o w n s t r e a mk kjkjjjiji wooxw
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
收敛性和局部极小值
对于多层网络，误差曲面可能含有多个不同的局部极小值，梯度下降可能陷入这些局部极小值中的任何一个
对于多层网络，反向传播算法仅能保证收敛到误差 E的某个局部极小值，不一定收敛到全局最小误差
尽管缺乏对收敛到全局最小误差的保证，反向传播算法在实践中仍是非常有效的函数逼近算法
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
收敛性和局部极小值（２）
网络的权越多，误差曲面的维数越多，也就越可能为梯度下降提供更多的逃逸路线
考虑随着训练中迭代次数的增加网络权值的演化方式
– 如果把网络的权值初始化为接近于 0的值，那么在早期的梯度下降步骤中，网络将表现为一个非常平滑的函数，近似为输入的线性函数，
这是因为 sigmoid函数本身在权值靠近 0时接近线性
– 仅当权值增长一定时间后，它们才会到达可以表示高度非线性网络函数的程度，可以预期在这个能表示更复杂函数的权空间区域存在更多的局部极小值
– 但是当权到达这一点时，它们已经足够靠近全局最小值，即便它是这个区域的局部最小值也是可以接受的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
收敛性和局部极小值（ 3）
用来缓解局部极小值问题的启发式规则
– 为梯度更新法则加一个冲量，可以带动梯度下降过程，冲过狭窄的局部极小值（原则上，也可能冲过狭窄的全局最小值）
– 使用随机的梯度下降而不是真正的梯度下降。随机近似对于每个训练样例沿一个不同的误差曲面有效下降，这些不同的误差曲面通常有不同的局部极小值，这使得下降过程不太可能陷入一个局部极小值
– 使用同样的数据训练多个网络，但用不同的随机权值初始化每个网络。如果不同的训练产生不同的局部极小值，那么对分离的验证集合性能最好的那个网络将被选中，或者保留所有的网络，输出是所有网络输出的平均值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
前馈网络的表征能力
布尔函数：任何布尔函数可以被具有两层单元的网络准确表示，尽管在最坏情况下所需隐藏单元的数量随着网络输入数量的增加成指数级增长。
– 考虑下面的通用方案：对于每一个可能的输入向量，
创建不同的隐藏单元，并设置它的权值使当且仅当这个特定的向量输入到网络时该单元被激活，这样就产生了一个对于任意输入仅有一个单元被激活的隐藏层，然后把输出单元实现为一个仅由所希望的输入模式激活的或门。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 55
前馈网络的表征能力（ 2）
连续函数：每个有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个结论适用于在隐藏层使用 sigmoid单元、在输出层使用（非阈值）线性单元的网络。所需的隐藏单元数量依赖于要逼近的函数。
任意函数：任意函数可以被一个有三层单元的网络以任意精度逼近。两个隐藏层使用 sigmoid单元，输出层使用线性单元，每层所需单元数不确定。
– 证明方法：首先说明任意函数可以被许多局部化函数的线性组合逼近，这些局部化函数的值除了某个小范围外都为 0；然后说明两层的 sigmoid单元足以产生良好的局部逼近
注意：梯度下降从一个初始值开始，因此搜索范围里的网络权向量可能不包含所有的权向量
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 56
假设空间搜索和归纳偏置
反向传播算法的假设空间是 n个网络权值形成的 n维欧氏空间。这个空间是连续的，与决策树学习和其他基于离散表示的方法的假设空间不同
假设空间的连续性以及误差 E关于假设的连续参数可微，
导致了一个定义良好的误差梯度，为最佳假设的搜索提供了一个非常有用的结构。
精确地刻画出反向传播学习的归纳偏置是有难度的，
它依赖于梯度下降搜索和权空间覆盖可表征函数空间的方式的相互作用性
把这一偏置粗略地刻画为在数据点之间平滑插值。如果给定两个正例，它们之间没有反例，反向传播算法会倾向于把这两点之间的点也标记为正例
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 57
隐藏层表示
反向传播算法的一个迷人特性是：它能够在网络内部的隐藏层发现有用的中间表示
– 训练样例仅包含网络输入和输出，权值调节的过程可以自由地设置权值，来定义任何隐藏单元表示，这些隐藏单元表示在使误差 E达到最小时最有效。
– 引导反向传播算法定义新的隐藏层特征，这些特征在输入中没有明确表示出来，但能捕捉输入实例中与学习目标函数最相关的特征
多层网络在隐藏层自动发现有用表示的能力是 ANN学习的一个关键特性。允许学习器创造出设计者没有明确引入的特征。
网络中使用的单元层越多，就可以创造出越复杂的特征
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 58
泛化、过度拟合和停止判据
权值更新算法的终止条件
– 一种选择是，对训练样例的误差降低至某个预先定义的阈值之下
这不是一个好的策略，因为反向传播算法容易过度拟合训练样例，降低对于其他未见实例的泛化精度
泛化精度：网络拟合训练数据外的实例的精度
图 4-9，尽管在训练样例上的误差持续下降，但在验证样例上测量到的误差先下降，后上升。
– 因为这些权值拟合了训练样例的“特异性”，而这个特异性对于样例的一般分布没有代表性。 ANN中大量的权值参数为拟合这样的“特异性”提供了很大的自由度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 59
过度拟合
为什么过度拟合发生在迭代的后期，而不是早期？
– 设想网络的权值是被初始化为小随机值的，使用这些几乎一样的权值仅能描述非常平滑的决策面
– 随着训练的进行，一些权值开始增长，以降低在训练数据上的误差，同时学习到的决策面的复杂度也在增加
– 如果权值调整迭代次数足够多，反向传播算法可能会产生过度复杂的决策面，拟合了训练数据中的噪声和训练样例中没有代表性的特征
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 60
过度拟合解决方法
权值衰减
– 它在每次迭代过程中以某个小因子降低每个权值，
这等效于修改 E的定义，加入一个与网络权值的总量相应的惩罚项，此方法的动机是保持权值较小，
从而使学习过程向着复杂决策面的反方向偏置
验证数据
– 一个最成功的方法是在训练数据外再为算法提供一套验证数据，应该使用在验证集合上产生最小误差的迭代次数，不是总能明显地确定验证集合何时达到最小误差
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 61
过度拟合解决方法（ 2）
一般而言，过度拟合是一个棘手的问题
交叉验证方法在可获得额外的数据提供验证集合时工作得很好，但是小训练集合的过度拟合问题更为严重
k-fold交叉方法
– 把训练样例分成 k份，然后进行 k次交叉验证过程，每次使用不同的一份作为验证集合，其余 k-1份合并作为训练集合。
– 每个样例会在一次实验中被用作验证样例，在 k-1次实验中被用作训练样例
– 每次实验中，使用上面讨论的交叉验证过程来决定在验证集合上取得最佳性能的迭代次数，然后计算这些迭代次数的均值
– 最后，运行一次反向传播算法，训练所有 m个实例并迭代 次
i
i
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 62
举例：人脸识别
训练样例
– 20个不同人的摄影图像
– 每个人大约 32张图像
不同的表情
– 快乐、沮丧、愤怒、中性
不同的方向
– 左、右、正前、上
不同的穿戴
– 是否带眼镜
– 共 624幅灰度图像
分辨率为 120x128，每个像素使用 0（黑）到 255（白）的灰度值描述
任务：学习图像中人脸的朝向
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 63
人脸识别 ——设计要素
输入编码
– ANN的输入必然是图像的某种表示，那么设计的关键是如何编码这幅图像
– 例如，可以对图像进行预处理，分解出边缘、亮度一致的区域或其他局部图像特征，然后把这些特征输入网络，问题是导致每幅图像有不同数量的特征参数，而 ANN具有固定数量的输入单元
– 把图像编码成固定的 30x32像素的亮度值，每个像素对应一个网络输入，把范围是 0到 255的亮度值按比例线性缩放到 0到 1的区间内，以使网络输入和隐藏单元、输出单元在同样的区间取值。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 64
人脸识别 ——设计要素（ 2）
输出编码
– ANN必须输出 4个值中的一个来表示输入图像中人脸的朝向
– 可以使用单一的输出单元来编码这 4种情况
– 这里使用 4个不同的输出单元，每一个对应 4种可能朝向中的一种，取具有最高值的输出作为网络的预测值。称为 1-of-n输出编码
选择 1-of-n的原因
– 为网络表示目标函数提供了更大的自由度
– 最高值输出和次高值输出间的差异可以作为对网络预测的置信度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 65
人脸识别 ——设计要素（ 3）
输出单元的目标值
– 一个显而易见的方法,<1,0,0,0>...
– 这里使用的方法,<0.9,0.1,0.1,0.1>...
– 避免使用 0和 1作为目标值的原因
sigmoid单元对于有限权值不能产生这样的输出
如果企图训练网络来准确匹配目标值 0和 1，梯度下降将会迫使权值无限增长
0.1和 0.9是 sigmoid单元在有限权值情况下可以完成的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 66
人脸识别 ——设计要素（ 4）
网络结构图
– 网络包含多少个单元以及如何互连？
– 最普遍的结构是分层网络，一层的每个单元向前连接到下一层的每一个单元
– 目前采用了包含两层 sigmoid单元的标准结构
– 隐藏单元的数量
3个，达到 90%的精度，训练时间约 5分钟
30个，提高 1~2个百分点，训练时间约 1个小时
– 实践发现，需要某个最小数量的隐藏单元来精确地学习目标函数，并且超过这个数量的多余的隐藏单元不会显著地提高泛化精度
– 如果没有使用交叉验证，那么增加隐藏单元数量经常会增加过度拟合训练数据的倾向，从而降低泛化精度
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 67
人脸识别 ——设计要素（ 5）
学习算法的其他参数
– 学习速率 设定为 0.3，冲量设定为 0.3
– 赋予这两个参数更低的值会产生大体相当的泛化精度，但需要更长的训练时间
– 如果赋予更高的值，训练将不能收敛到一个具有可接受误差的网络
– 适用完全的梯度下降
– 输出单元的权值被初始化为小的随机值
– 输入单元的权值被初始化为 0
– 训练的迭代次数的选择可以通过分割可用的数据为训练集合和验证集合来实现
– 最终选择的网络是对验证集合精度最高的网络
– 最终报告的精度是在没有对训练产生任何影响的第三个集合 ——测试集合上测量得到的
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 68
学习到的隐藏层表示
图中紧挨人脸图像下的 4个矩形，每个矩形描绘了网络中 4个输出单元中的一个权值，每个矩形中的 4个小方形表示和这个输出单元关联的 4个权值
隐藏单元的权值显示在输出单元的下边，每个隐藏单元接受所有 30x32个像素输入。与这些输入关联的
30x32个权值被显示在它们对应的像素的位置
针对每一个训练样例，梯度下降迭代 100次后的网络权值显示在图的下部。
– 如果一个人的脸是转向他的右面，那么他的亮度高的皮肤会大致与这个隐藏单元中的较大正值对齐，同时他的亮度低的头发会大致与负权值对齐，这导致此单元输出一个较大的值，
同样的图像会使第 3个隐藏单元输出一个接近 0的值。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 69
其他可选的误差函数
为权值增加一个惩罚项
– 把一个随着权向量幅度增长的项加入到 E中，这导致梯度下降搜寻较小的权值向量，从而减小过度拟合的风险，等价于使用权衰减策略
对误差增加一项目标函数的斜率或导数
– 某些情况下，训练信息中不仅有目标值，而且还有关于目标函数的导数
Dd ji jio u t p u tsk kdkd wotwE,22)(21)(
Dd o u t p u t sk i n p u t sj jdkdjdkdkdkd xoxtotwE 22)(21)(
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 70
其他可选的误差函数（ 2）
使网络对目标值的交叉熵最小化
– 比如根据借贷申请者的年龄和存款余额，预测他是否会还贷，目标函数最好以申请者还贷的概率的形式输出，而不是输出明确的 0和 1。在这种情况下，
可以证明最小化交叉熵的网络可以给出最好的概率估计。交叉熵定义如下：
– 第 6章讨论了何时及为什么最可能的网络假设就是使交叉熵最小化的假设，并推导了相应的 sigmoid单元的梯度下降权值调整法则，还描述了在什么条件下最可能的假设就是使误差平方和最小化的假设。
)1lo g ()1(lo g ddDd dd otot
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 71
其他可选的误差函数（ 3）
通过权值共享改变有效误差函数
– 把与不同单元或输入相关联的权“捆绑在一起”，
强迫不同的网络权值取一致的值，通常是为了实施人类设计者事先知道的某个约束
– 约束了假设的潜在空间，减小了过度拟合的风险
– 实现方法，首先在共享权值的每个单元分别更新各个权值，然后取这些权值的平均，再用这个平均值替换每个需要共享的权值。
– 被共享的权值比没有共享的权值更有效地适应一个不同的误差函数
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 72
其他可选的误差最小化过程
梯度下降是搜寻使误差函数最小化的假设的最通用的方法之一，
但不是最高效的
不妨把权值更新方法看作是要决定这样两个问题：
– 选择一个改变当前权值向量的方向（梯度的负值）
– 选择要移动的距离（学习速率）
线搜索，每当选定了一条确定权值更新方向的路线，那么权更新的距离是通过沿这条线寻找误差函数的最小值来选择的
共轭梯度，进行一系列线搜索来搜索误差曲面的最小值，这一系列搜索的第一步仍然使用梯度的反方向，在后来的每一步中，选择使误差梯度分量刚好为 0并保持为 0的方向
像共轭梯度这样的方法对最终网络的泛化误差没有明显的影响，
唯一可能的影响是，不同的误差最小化过程会陷入不同的局部最小值
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 73
递归网络
递归网络是有如下特征的人工神经网络
– 适用于时序数据
– 使用网络单元在时间 t的输出作为其他单元在时间
t+1的输入
– 递归网络支持在网络中使用某种形式的有向环
考虑一个时序预测任务
– 根据当天的经济指标 x(t)，预测下一天的股票平均市值 y(t+1)
– 训练一个前馈网络预测输出 y(t+1)，图 4-11a
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 74
递归网络
预测 y(t+1)时，考虑任意过去的时间窗内的信息，图 4-11b
图 4-11b那样的递归网络可以使用反向传播算法的简单变体来训练
把递归网络拷贝成几份，用不同拷贝间的连接替换掉反馈环，这个大的网络不再包含回路，所以可以直接使用反向传播算法来训练
实践中，我们仅保留一份递归网络和权值集合的拷贝，在训练了展开的网络后，可以取不同拷贝中权值的平均值作为最终网络的对应的权值
实践中，递归网络比没有反馈环的网络更难以训练，泛化的可靠性也不如后者，然而它们仍因较强的表征力而保持着重要性
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 75
动态修改网络结构
动态增长或压缩网络单元和单元间连接的数量
从一个不包含隐藏单元的网络开始，然后根据需要增加隐藏单元来增长网络，直到训练误差下降到某个可接受的水平
– 级联相关算法，每当加入一个新的隐藏单元，它的输入包括所有原始的网络输入和已经存在的隐藏单元的输出，网络以这种方式增长，积聚隐藏单元，直到网络的残余误差下降到某个可接受的水平
– 由于每一步仅有一层网络在被训练，级联相关算法显著减少了训练时间
– 算法的一个实际困难是，因为算法可以无限制地增加单元，
很容易过度拟合训练数据。
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 76
动态修改网络结构
从一个复杂的网络开始修剪掉某些连接
– 判断某个权是否无关紧要的一种方法是看它的值是否接近 0
– 在实践中更加成功的方法是考虑这个权值的一个小的变化对误差的影响（连接的显著性）
– 最不显著的连接被拆除，重复这个过程，直到遇到某个终止条件为止（最优脑损伤法）
一般而言，动态修改网络结构的方法能否稳定地提高反向传播算法的泛化精度还有待研究
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 77
小结
人工神经网络为学习实数值和向量值函数提供了一种实际的方法，对于连续值和离散值的属性都可以使用，
并且对训练数据中的噪声具有很好的健壮性。
反向传播算法是最常见的网络学习算法
反向传播算法考虑的假设空间是固定连接的有权网络所能表示的所有函数的空间
包含 3层单元的前馈网络能够以任意精度逼近任意函数，
只要每一层有足够数量的单元。即使是一个实际大小的网络也能够表示很大范围的高度非线性函数
反向传播算法使用梯度下降方法搜索可能假设的空间，
迭代减小网络的误差以拟合训练数据
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 78
小结（ 2）
梯度下降收敛到训练误差相对网络权值的局部极小值。只要训练误差是假设参数的可微函数，
梯度下降可用来搜索很多连续参数构成的假设空间
反向传播算法能够创造出网络输入中没有明确出现的特征。
交叉验证方法可以用来估计梯度下降搜索的合适终止点，从而最小化过度拟合的风险
其他 ANN学习算法，递归网络方法训练包含有向环的网络，级联相关算法改变权和网络结构
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 79
补充读物
本书其他与 ANN学习相关的章节
– 第 6章给出了选择最小化误差平方和的贝叶斯论证，
以及在某些情况下，用最小化交叉熵代替最小化误差平方和的方法
– 第 7章讨论了为可靠学习布尔函数所需要的训练实例数量的理论结果，以及某些类型网络的 VC维
– 第 5章讨论了过度拟合和避免过度拟合的方法
– 第 12章讨论了使用以前知识来提高泛化精度的方法
2003.12.18 机器学习 -人工神经网络 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 80
补充读物（ 2）
发展历程
– McCulloch & Pitts
– Widrow & Hoff
– Rosenblatt
– Minsky & Papert
– Rumelhart & McClelland; Parker
教科书
– Duda & Hart
– Windrow & Stearns
– Rumelhart & McClelland
