《机器学习》学习笔记

http://www-2.cs.cmu.edu/~tom/mlbook.html

第一章 引言

  1. 机器学习从不同的学科吸收概念,包括人工智能、概率和统计、计算复杂性、信息论、心理学和神经生物学、控制论以及哲学。
  2. 一个完整定义的学习问题需要一个明确界定的任务、性能度量标准以及训练经验的来源。
  3. 机器学习算法的设计过程包含许多选择,包括选项训练经验的类型、要学习的目标函数、该目标函数的表示形式以及从训练样例中学习目标函数的算法。

第二章 概念学习和从一般到特殊序

概念学习:给定一类别的若干正例和反例,从中获得该类别的一般定义。

概念学习也可以看作是一个搜索问题的过程,它在预定义的假设空间中搜索假设,使其与训练样例有最佳的拟合度。

归纳学习假设:任一假设如果在足够大的训练样例集中很好地逼近目标函数,它也能在未见实例中很好地逼近目标函数。

概念学习的方法:

  1. FIND-S:寻找极大特殊假设
  2. 变型空间和候选消除法

候选消除法寻找与训练样例一致的所有假设。

一致:一个假设能正确分类一组样例,则称该假设与这些样例一致

候选消除法能够表示与训练样例一致的所有假设。在假设空间中的这一子集被称为关于假设空间H和训练样例D的变型空间,因为它包含了目标概念的所有合理的变型。

列表后消除算法:首先将变型空间初始化为包含H中所有的假设,然后从中去除与任一训练样例不一致的假设。

候选消除算法:使用更简洁的变型空间表示法:将变型空间表示为它的极大一般G和极大特殊S成员,使用一般到特殊的偏序结构就可以生成S和G之间的所有假设。

一般来说,概念学习的最优查询策略,是产生实例以满足当前变型空间大约半数的假设。

归纳偏置:有偏的假设空间和无偏的学习器。

无偏学习的无用性:学习器如果不对目标概念的形式做预先的假定(归纳偏置),它从根本上无法对未见实例进行分类。

候选消除法的归纳偏置:目标概念c包含在给定的假设空间H中

第三章 决策树学习

应用最广的归纳推理算法之一,是一种逼近离散值函数的方法,对噪声有很好的健壮性、能够学习析取表达式。

决策树学习的归纳偏置是优先选择较小的树。

通畅决策树代表实例属性值约束的合取的析取式。

ID3算法的优势和不足:

  1. 假设空间包含所有的决策树,是关于现有属性的有限离散值函数的一个完整空间
  2. 遍历决策树空间时,ID3仅维护单一的当前假设,导致无法判断有多少个其它决策树也是与现有的训练数据一致的
  3. 基本的ID3算法在搜索中不进行回溯,可能导致局部最优
  4. 在搜索的每一步都使用当前的所有训练样例,以统计为基础决定怎样精化当前的假设,降低了对个别错误样例的敏感性

ID3的搜索范围是一个完整的假设空间,但它不彻底的搜索这个空间。归纳偏置来自于它的搜索策略,称为搜索偏置

变型空间候选消除算法的搜索范围是不完整的假设空间,但它完整地搜索这个空间。归纳偏置来自于它对搜索空间的定义,称为限定偏置

决策树学习需要考虑的问题:(C4.5 解决了其中多数问题)

  1. 确定决策树增长的深度
  2. 处理连续值的属性
  3. 选择一个恰当的属性刷选度量标准
  4. 处理属性值不完整的训练数据
  5. 处理不同代价的属性
  6. 提高计算效率

过渡拟合:给定一个假设空间H,一个假设h,如果存在其他的假设h',使得在训练样例上h的错误率比h'小,但在整个实例分布上h'的错误率比h小,那么就说假设h过渡拟合训练数据。

解决过渡拟合问题的几种途径:

  1. 及早停止树的增长,在ID3算法完美分类训练数据之前就停止树的增长
  2. 后修剪枝法,即允许树过渡拟合数据,然后对这个树进行后修剪

第四章 人工神经网络

人工神经网络提供了一种普遍而且实用的方法从样例中学习置为实数、离散值或向量的函数

反向传播算法适合具有以下特征的问题:

  1. 实例是用很多"属性-值"表示的
  2. 目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量
  3. 训练数据可能包含错误
  4. 可容忍长时间的训练
  5. 可能需要快速求出目标函数值
  6. 人类能否理解学到的目标函数是不重要的

正反样例可以被某一超平面分隔的称为线性可分样例集合

感知器训练法则:在有限次使用感知器训练法则后,训练过程会收敛到一个能正确分类所有训练样例的权向量,前提是训练样例线性可分,并且使用了充分小的学习速率

如果训练样例不是线性可分,那么delta法则会收敛到目标概念的最佳近似

应用梯度下降的主要实践问题:

  1. 有时候收敛过程可能非常慢
  2. 如果在误差曲面上有多个局部极小值,那么不能保证这个过程会找到全局最小值

梯度下降和随机梯度下降的区别:

  1. 梯度下降是在权值更新前对所有样例汇总误差,而随机梯度下降的权值是通过考察每个训练实例来更新的
  2. 梯度下降中,权值更新的每一步对多个样例求和,计算量大;一般使用比随机梯度下降更大的步长
  3. 随机的梯度下降有时可能避免陷入局部最小值

反向传播算法:对于多层网络,反向传播算法仅能保证收敛到误差的某个局部极小值,不一定收敛到全局最小误差。用来缓和局部极小值问题的常见启发式规则包括:

  1. 为梯度更新法则加一个冲量项
  2. 随用随机的梯度下降
  3. 使用同样的数据训练多个网络,但用不同的随机权值初始化每个网络

前馈网络的表征能力:

  1. 任何布尔函数可以被具有两层单元的网络准确表示
  2. 每个有界的连续函数可以由一个两层的网络以任一小的误差逼近
  3. 任意函数可以被一个有三层单元的网络以任意精度逼近

第五章 评估假设

给定的数据有限时,要学习一个概念并估计其将来的精度,存在两个很关键的困难: 1. 估计的偏差 2. 估计的方差

样本错误率:可用数据样本上该假设的错误率:对于从X中抽取的样本S,某假设关于S的样本错误率是该假设错误分类的实例在S中所占的比例

真实错误率:分布为x的整个实例集合上该假设的错误率:

中心极限定理:独立同分布(未知分布)的随机变量的总和遵循正态分布

估计量:针对一个随机变量Y,被用来估计一个基准总体的某一参数p

Y的估计偏差:作为p的估计量是E[Y]-p,无偏估计量是指该偏差为0

N%置信区间:用于估计参数p,该区间包含p的概率为N%

应用二项分布的条件包括:

  1. 有一基本实验,其输出可被描述为某一随机变量Y,随机变量Y有两种取值(0,1)
  2. 在实验的任一次尝试中Y=1的概率为p,p与其他的尝试无关。

估计偏差为一数字量,而归纳偏置为一个断言集合

通常描述某估计的不确定性的方法是使用置信区间,真实的值以一定的概率落入该区间中。这样的估计称为置信区间估计。

推导置信区间的一般方法:

  1. 确定基准总体中要估计的参数p
  2. 定义一个估计量Y,他的选择应为最小方差的无偏估计量。
  3. 确定控制估计量Y的概率分布D,包括其均值和方差
  4. 通过寻找阈值L和U确定N%置信区间,以使这个按D分布的随机变量有N%的概率落入L和U之间。

第六章 贝叶斯学习

P(D|h)常被称为给定h时数据D的似然度,而使P(D|h)最大的假设被称为极大似然假设

基本概率公式表: 1. 乘法规则 2. 加法规则 3. 贝叶斯规则 4. 全概率规则

某学习算法被称为一致学习器,说明它输出的假设在训练样例上有0错误率

最小描述长度准则:将贝叶斯公式表示为以2为底的对数形式,使其信息熵最小化

朴素贝叶斯分类器:一般来说,新实例的最可能分类可通过合并所有假设的预测得到,用后验概率来加权。在布尔概念学习问题中,使用变型空间方法,对一新实例的贝叶斯最优分类是在变型空间的所有成员中进行加权选举获得的,每个候选假设都用后验概率加权

GIBBS算法:非最优,解决贝叶斯最优分类器开销很大的问题

朴素贝叶斯分类器基于一个简单的假设:在给定目标值时属性之间相互条件独立(该假设通常过于严格)

贝叶斯信念网描述的是一组变量所遵从的概率分布,它通过一组条件概率来指定一组条件独立性假定。表示一组变量的联合概率分布。贝叶斯信念网提供了一种中间的方法,他比朴素贝叶斯分类器中条件独立性的全局假定的限制更少,又比在所有变量中计算条件依赖更可行。

第七章 计算学习理论

样本复杂度:学习器要收敛到成功的假设(以较高的概率),需要多少训练样例?

计算复杂度:学习器要收敛到成功的假设(以较高的概率),需要多大的计算量?

出错界限:在成功收敛到一个假设前,学习器对训练样例的错误分类有多少次?

假设h的关于目标概念c和分布Y的真实错误率为h误分类根据Y随机抽取的实例概率

训练错误率:训练样例中被h误分类的样例所占的比例

关于学习复杂度的分析多数围绕着这样的问题:"h的观察到的训练错误率对真实错误率产生不正确估计的可能性有多大?"。

PAC(可能近似正确)可学习性:对C中任意目标概念c,若在观察到合理数目的训练样例并执行了合理的计算量后,L以概率(1-delta)输出一个真实错误率小于epsion的假设h,则我们称概念类别C是可以被使用H的L所PAC学习的。

第八章 基于实例的学习

已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述。但与此不同,基于实例的学习方法只是简单地把训练样例存储起来。从这些实例中泛化的工作被推迟到必须分类新的实例时。

基于实例的学习方法包括最近邻法和局部加权回归法,它们都假定实例可以被表示为欧式空间中的点。

对k-近邻算法的一个明显改进是对k个近邻的贡献进行加权

k-近邻算法的归纳偏置:一个实例的分类与在欧式空间中它附近的实例的分类相似

回归:逼近一个实数值的目标函数

残差:逼近目标函数时的误差

核函数:一个距离函数,用来决定每个训练样例的权值

局部加权回归:

第九章 遗传算法

遗传算法的输入包括:

  1. 用来排序候选假设的适应度函数
  2. 定义算法终止时适应度的阈值
  3. 要维持的群体的大小
  4. 决定如何产生后继群体的参数(即淘汰率和变异率)

第十章 学习规则集合

学习规则集合的几种办法:

  1. 学习决策树、然后将此树转换为一等价的规则集合
  2. 遗传算法,用位串编码每个规则几何,然后用遗传搜索算子来探索整个假设空间

序列覆盖算法:学习一个规则、移去它覆盖的数据、再重复这一过程;最后析取以上学习到的规则;

由于是贪婪搜索,没有回溯,所以它不能保证找到能覆盖样例的最小或最佳规则

如何学习一个规则:一般到特殊的柱状搜索

序列覆盖算法和决策树学习算法的异同:

  1. 序列覆盖算法每次学习一个规则,移去覆盖的样例后在剩余样例上重复这一过程;决策树算法使用单个搜索过程来搜索可接受的决策树
  2. 序列覆盖算法的搜索方向是从一般到特殊;决策树学习算法是从特殊到一般
  3. 序列覆盖算法是一个生成再测试搜索,范围为所有合法假设;决策树学习算法是样例驱动搜索,以使训练样例个体约束假设的生成
  4. 是否需要对规则进行后修剪以及怎样后修剪
  5. 指引学习一个规则搜索方向的规则性能的的定义

序列覆盖算法针对学习命题规则集(即无变量的规则),而一阶Horn子句学习带有变量的规则。

形式逻辑中的基本术语:

所有表达式由常量、变量、谓词符号(取值只能为真假)以及函数符号组成

项是任意常量、任意变量或应用到任意项上的任意函数

文字是应用到项上的任意谓词或其否定

基本文字:不包含任何变量的文字

负文字:包含否定谓词的文字

正文字:不包含否定谓词的文字

子句是多个文字的任意析取,其中所有的变量假定是全称量化的

Horn子句是包含至多一个正文字的子句

置换:将某些变量替换为某些项的函数

Horn子句的前件被称为子句体或者子句先行词,后件被称为子句头或子句推论

第十一章 分析学习

第十二章 归纳和分析学习的结合

第十三章 增强学习

发表评论

电子邮件地址不会被公开。