动机
推理引擎应用事先提供的规则,学习系统则用例子调整表示方式或参数。这个区分有用,却不是绝对分界:学到的决策树可以成为规则系统,神经网络也可为另一个推理程序提供特征。两者共同的限制是,预测只能使用表示方式保留下来的信息。
例如消息分类器只记录某些字词是否出现,便可学它们与类别的关联,却不能区分映到同一向量的两句话。若语序改变意思,词袋在优化之前已丢掉必要信息;再努力拟合也无法凭空重建。因此,表示方式与学习规则要一起分析。
本节从明确模型推导两个基本更新,并分析决策树的一个分割准则。保证范围刻意清楚:感知器界需要正间隔,梯度是局部导数而不是全局优化保证,训练样本熵减少也不是未来准确率保证。
定义
定义 3.1.1
(标记例子与线性分数)
二元标记例子为 ,其中特征 ,标记 。线性分数为 。要含偏置,可把输入扩为 ,并给最后一维独立权重。下文范数与间隔条件都要应用于扩充后向量。零分数的预测惯例要说明;本节在 时视作错误或边界违反而更新。
概念视角结构
特征映射产生等价类
固定确定性特征映射 ,任何形如 的预测器,都对相同特征向量给相同输出。因此 把输入分成不可区分的类。如果任务要求同一类内两项有不同标记,任何 都不能同时正确。这是表示方式的限制,与采哪个优化器无关。例如 “dog bites person” 与 “person bites dog” 的字数向量相同,施事与受事却互换,所以只看字数的预测器必须同样对待它们。
词数可对某些分类任务提供有用证据,同时丢掉句法。更完整的语言系统须指定分词、歧义、组合结构及评估任务,不能只因向量维度大便说已处理这些问题。
定义 3.1.2
(感知器更新)
感知器由 开始;遇违反例子便作 ,否则不变。该例子的带号分数增加 ,因为 。但别的例子分数可能下降,故一次修正不表示错误总数单调减少。
定义 3.1.3
(平方损失、梯度步与单隐层网络)
对可微模型 及实数目标 ,平方损失为 。梯度下降以指定步长 作 。单隐层、标量线性输出的网络写成:
假设激活函数 在当前值可微。其他输出激活及损失会给不同导数。Sigmoid 为 ,其导数为 。整流线性函数在零不可微,算法须另订次梯度等处理约定,不能悄悄把普通导数公式用到不可微点。
定义 3.1.4
(熵、条件熵与信息增益)
有限样本中,均匀抽取一个训练项目的类别记为 。若类别比例为 ,以 bit 为单位的经验熵是:
约定 ,与连续延伸一致。属性 把样本分为值 的子组,比例为 。条件熵为 ,信息增益为父熵减条件熵。决策树可贪心地挑最大增益,但仍需停止、同分及剪枝规则。
定理/命题
定理 3.1.5
(正间隔下的感知器错误界)
假设所有出现例子满足 ,且存在同一单位向量 ,令每个例子皆有 。由零开始、在 时更新的感知器,不论呈现次序,至多更新 次。此界数更新次数,不数两次错误之间可能出现的正确分类例子。
命题 3.1.6
(指定网络的反向传播)
对上述可微标量输出网络及 ,设 。在当前参数下,
若损失是批次平均,先平均各例子的导数,再同时更新参数。
两个结果回答不同问题。第一个在强几何假设下保证有限进展;第二个计算指定函数的准确局部敏感度,没有声称损失曲面凸,也没有声称反复更新会到最佳参数。
命题 3.1.7
(信息增益非负)
对一个非空标记样本按属性 分割,条件熵满足 ,所以信息增益 至少为零。
证明思路
证明
(对齐线性增长,范数只按平方根增长)
只按真正发生的更新编号, 表示更新 次后权重。每次与分隔向量的内积至少增加 ,所以 。另一方面,在需更新的例子上:
归纳得 。由 Cauchy–Schwarz 及 ,有 。若 ,除以 再平方即得界;零更新情况直接成立。有限可分样本若循环呈现,最终必有一整轮没有更新,否则无穷多个有错轮次会违反有限更新界。
证明透视
两个增长界缺一不可
共同分隔方向令对齐程度随错误次数线性增长,只在非正带号分数时更新则令范数至多以平方根速度增长。大量更新时两者矛盾,因而终止。没有共同正间隔,第一条界便消失;不是只在违反时更新,范数展开的交叉项便未必非正。所以不能把此证明原封不动套到任意梯度更新或互相矛盾的标记。
证明
(逐组参数的链式法则)
反向传播先由 开始。输出对 的导数为 、对 为一,立即得到输出层导数。由 到输出的路径,链式法则依次乘 、、 及输入 ;偏置的最后导数则为一。反向模式微分的意义,是重用共同的下游敏感度,避免每个参数都重算整条复合函数。
可微损失在非零梯度处满足 (),所以充分小正步长会局部降低损失;这不保证任意固定步长安全,也不保证泛化。
证明
(熵函数的凹性)
在 凹,端点按连续延伸。父组类别比例向量是子组向量的加权平均,逐坐标套凹性再相加,得 ,所以真正同一样本分割的信息增益非负。
此论证没有说关联在总体中稳定;独特标识符能令每个子组纯粹,却只是记住样本。
数据不可分时,感知器的循环永远完成不了一轮无错误的遍历。
自然的下一个问题
若不存在分离向量会怎样?
数据不可分时,感知器的循环永远完成不了一轮无错误的遍历。
这个上界假设存在间隔。若没有任何 使每个带号分数都满足 ,循环便不会结束,因为一轮没有更新的完整遍历本身就给出这样的 。例如 取两次,标记分别为 和 , 会由 变成 ,再变回 ,如此重复。别的规则能否仍找到好的分类器是另一个问题,本定理并未回答。
例题详解
例题 3.1.8
(含偏置感知器的追踪)
扩充例子为 与 。零权重先被第一例触发,成为 。第二例的分数为 ,带号分数为 ,故不更新。原来一维输入的边界是 。取单位分隔向量 ,两间隔为 ,所以可取 ,得至多五次更新。这是上界,不是声称实际要五次。
例题 3.1.9
(完整指定的一步神经更新)
输入 ,一个 sigmoid 隐单元,参数 ,目标 ,步长 。有 ,激活导数为 。对 的梯度依次为 。同时更新得到 。新隐输入为 ,输出约 ,损失由 降至约 。重新前向计算可核对导数符号及意义。
例题 3.1.10
(信息增益可能偏好记忆)
八项数据有四正四负,父熵为一 bit。属性 A 产生两个同样大小子组,类别数为 及 ;各熵约为 ,所以增益约 。若用标识符分成八个单项子组,增益达一 bit,却未必能处理新标识符,因为没有相应分支。训练增益要与表示方式、正则化及未见数据评估一起解读。
常见错误
反例模式
线性特征不能表示 XOR
令 为正类, 为负类。若仿射分数 能严格分隔,相加两正例不等式给 ,相加两负例却给 ,矛盾。加入特征 即可分隔,因它的符号正是标记。此处找不到线性分隔,不是感知器步长太小的证据。
常见错误
(在同一次梯度步中混用新旧参数)
一次梯度步的所有导数必须在同一组旧参数计算。若先改 ,再用新值计算 ,便定义了另一算法,结果也不再是所述损失的梯度步。在单一隐单元的例子中, 用的是旧的 ,而不是更新后的 。
常见错误
(把零信息增益读成无关)
对 XOR 表 ,单独按 或 分割,每个子组都恰有每种标记各一行,所以两个增益都是零;但两个属性合起来完全决定标记。零增益只表示这一次单独分割没有改变标记比例。
常见错误
(把学到的关联当作规则、把分数当作概率)
专家系统也不只有推理引擎。知识获取须找出领域规则、适用条件与例外;解释须指出哪些规则被触发;维护须处理冲突及过时知识。学到的关联不自动是逻辑有效蕴涵。神经分数若没有合适模型、目标及校准检查,也不能直接当可靠概率。分类错误率、训练损失及信心是不同量。
总结
学习结合表示方式、目标或更新规则,以及样本假设。正间隔给感知器错误界;链式法则给神经梯度,却不提供全局最优或泛化定理;信息增益衡量样本标记减少,可以奖励记忆。更改优化器之前,先检查特征能否分清任务要求区分的情况。
练习
练习 3.1.11
(由零开始,循环呈现 及 ,在带号分数非正时以感知器规则更新。求首两次更新、具正间隔的单位分隔向量,以及定理的更新界。)
核心
解答(3)
- 1
进行首两次更新
在 时第一例的带号分数为 ,所以 。第二例有 ,带号分数为零,也更新:。再循环一轮,带号分数为正(皆为 ),不再更新。
- 2
选取分隔向量并读出间隔
关键一步
取 ,两个带号间隔都是 ,所以 ,且 。
依据: 定理需要一个固定单位向量,使每个带号分数至少为 。
- 3
应用上界
。实际发生两次更新,所以此顺序及零分数约定恰达上界。
练习 3.1.12
(把上述神经例题的目标改为 ,重新计算梯度,给出步长 的同时更新,并解释输出偏置改变的方向。)
核心
解答(3)
- 1
重算前向值与误差
前向值仍为 、、,但现在 。
- 2
以旧参数计算梯度
、、、。
依据: 所有导数都使用旧的 。
- 3
作同时更新
步长 给出 、、、。 为正,表示增大输出偏置会局部增大损失;减去梯度便降低偏置,使输出朝目标零移动。
练习 3.1.13
(某父样本有六个正例、两个负例;一个二元属性把它分成类别数同为 的两组。求信息增益,并说明为何子组不纯却增益为零。)
基础
解答(2)
- 1
计算各个熵
父组与两个子组的正类比例都是 ,所以三个熵都等于 bit。
- 2
计算加权子熵与增益
两个子组权重各为二分之一,加权子熵为 bit,与父熵相同,所以增益为零。分割可以重排记录而不改变标记比例。零增益不表示标记本身确定,也不表示此属性永远不能与其他属性联合发挥作用。
练习 3.1.14
(证明确定性特征映射的不可区分性,并应用到上述语序互换的两个句子;再提出一个明确的新增特征来区分两者,但不要声称它解决一般语言理解。)
综合证明
解答(3)
- 1
利用 是特征向量的函数
设 为确定性特征映射, 为任何函数,并假设 。
- 2
比较输出
关键一步
对两边用同一函数 ,得 。若任务要求 与 有相反标记,预测器至少在其中一项出错。
- 3
应用到句子并加入特征
两个句子的字数特征相同,所以任何只依这些特征的预测器都不能区分它们。特征“是否出现有序相邻词 dog-bites”在指定分词下,于第一句为一、于第二句为零,因此能区分这一对。否定、改述、长距依赖及歧义文法仍是独立问题;新增特征没有一般语义完备的保证。
依据: 两个句子的字数向量相同。
∎