第1章 绪论

• 对于一个学习算法a,若它在某问题上比学习算法b好,则必然存在另一些问题,在那里b比a好.即"没有免费的午餐"定理(No Free Lunch Theorem,NFL).因此要谈论算法的相对优劣,必须要针对具体的学习问题

第2章 模型评估与选择

• m次n折交叉验证实际上进行了m*n次训练和测试

• 可以用F1度量的一般形式Fβ来表达对查准率/查全率的偏好:[图片上传失败...(image-e771e-1549689693020)]

• 偏差度量了学习算法的期望预测与真实结果的偏离程度,即学习算法本身的拟合能力,方差度量了同样大小的训练集的变动所导致的学习性能的变化,即数据扰动造成的影响.噪声表达了当前任务上任何学习算法所能达到的期望泛化误差的下界,即学习问题本身的难度.

第3章 线性模型

• 线性判别分析(LDA)是一种经典的监督线性降维方法:设法将训练样例投影到一条直线上,使同类样例的投影点尽可能接近,异类样例的投影点尽可能远离.对新样本分类时根据投影点的位置来确定类别.
• 多分类学习的分类器一般有以下三种策略:

1. 一对一(OvO),N个类别产生N * (N - 1) / 2种分类器
2. 一对多(OvR或称OvA),N个类别产生N - 1种分类器
3. 多对多(MvM),如纠错输出码技术

• 解决类别不平衡问题的三种方法:

1. 过采样法,增加正例使正负例数目接近,如SMOTE:思想是合成新的少数类样本,合成的策略是对每个少数类样本a,从它的最近邻中随机选一个样本b,然后在a、b之间的连线上随机选一点作为新合成的少数类样本.
2. 欠采样法,减少负例使正负例数目接近,如EasyEnsemble:每次从大多数类中抽取和少数类数目差不多的重新组合,总共构成n个新的训练集,基于每个训练集训练出一个AdaBoost分类器（带阈值）,最后结合之前训练分类器结果加权求和减去阈值确定最终分类类别.
3. 再缩放法

第4章 决策树

• ID3决策树选择信息增益最大的属性来划分:

1. 信息熵:[图片上传失败...(image-6718b5-1549689693019)]

2. 信息增益:[图片上传失败...(image-2eaea3-1549689693019)]

• C4.5决策树选择增益率大的属性来划分,因为信息增益准则对可取值数目较多的属性有所偏好.但增益率会偏好于可取值数目较少的属性,因此C4.5算法先找出信息增益高于平均水平的属性,再从中选择增益率最高的.另外,C4.5决策树采用二分法对连续值进行处理,使用时将划分阈值t作为参数,选择使信息增益最大的t划分属性.采用样本权值对缺失值进行处理,含有缺失值的样本同时划入所有结点中,但相应调整权重.

1. 增益率:[图片上传失败...(image-6b8c1d-1549689693019)]

2. a的固有值:[图片上传失败...(image-67ee19-1549689693019)]

• CART决策树则选择基尼指数最小的属性来划分,基尼系数反映了从数据集中随机抽取的两个样本类别不一致的概率,注意CART是二叉树,其余两种都为多叉树.

1. 基尼值衡量的纯度:[图片上传失败...(image-321f09-1549689693019)]

2. 基尼指数:[图片上传失败...(image-d6f7f8-1549689693019)]

• 剪枝是决策树对付过拟合的主要手段,分为预剪枝和后剪枝.

1. 预剪枝对每个结点在划分前先进行估计,若该结点的划分不能带来决策树泛化性能提升,则停止划分.预剪枝基于"贪心"本质,所以有欠拟合的风险.
2. 后剪枝是先生成一棵完整的决策树,然后自底向上对非叶结点考察,若该结点替换为叶结点能带来决策树泛化性能提升,则将子树替换为叶结点.缺点是时间开销大.

• 决策树所形成的分类边界是轴平行的,多变量决策树(斜决策树)的每一个非叶结点都是一个线性分类器,因此可以产生斜的划分边界.

第5章 神经网络

• 误差逆传播算法(BP算法)是迄今为止最成功的神经网络学习算法.关键点在于通过计算误差不断逆向调整隐层神经元的连接权和阈值.标准BP算法每次仅针对一个训练样例更新,累积BP算法则根据训练集上的累积误差更新.

[图片上传失败...(image-e0e096-1549689693026)]

• 缓解BP神经网络过拟合有两种常见策略:

1. 早停:若训练集误差降低但验证集误差升高则停止训练.
2. 正则化:在误差目标函数中增加一个描述网络复杂度的部分(较小的连接权和阈值将使神经网络较为平滑).

• 跳出局部最小,寻找全局最小的常用方法:

1. 以多组不同参数初始化多个神经网络,选择最接近全局最小的
2. 模拟退火
3. 随机梯度下降

• 典型的深度学习模型就是很深层的神经网络.但是多隐层神经网络难以直接用经典算法进行训练,因为误差在多隐层内逆传播时往往会发散.无监督逐层训练(如深层信念网络,DBN)和权共享(如卷积神经网络,CNN)是常用的节省训练开销的策略.

第6章 支持向量机

• 支持向量机中的原始样本空间不一定存在符合条件的超平面,但是如果原始空间是有限维,则总存在一个高维特征空间使样本线性可分.核函数就是用来简化计算高维特征空间中的内积的一种方法.核函数选择是支持向量机的最大变数.常用的核函数有线性核,多项式核,高斯核(RBF核),拉普拉斯核,Sigmoid核.对文本数据常用线性核,情况不明时可先尝试高斯核.
• 软间隔是缓解支持向量机过拟合的主要手段,软间隔允许某些样本不满足约束.
• 支持向量回归可以容忍预测输出f(x)和真实输出y之间存在ε的偏差,仅当偏差绝对值大于ε时才计算损失.
• 支持向量机中许多规划问题都使用拉格朗日对偶算法求解,原因在于改变了算法复杂度.原问题的算法复杂度与样本维度有关,对偶问题的样本复杂度与样本数量有关.如果使用了升维的方法,则此时样本维度会远大于样本数量,在对偶问题下求解会更好.

第7章 贝叶斯分类

• 基于贝叶斯公式来估计后验概率的困难在于类条件概率是所有属性上的联合概率,难以从有限的训练样本直接估计而得.因此朴素贝叶斯分类器采用了"属性条件独立性假设"来避开这个障碍.
• 朴素贝叶斯分类器中为了避免其他属性携带的信息被训练集中未出现的属性值"抹去",在估计概率值时通常要进行"平滑",常用拉普拉斯修正.
• 属性条件独立性假设在现实中往往很难成立,于是半朴素贝叶斯分类器采用"独依赖估计(ODE)",即假设每个属性在类别之外最多仅依赖于一个其他属性.在此基础上有SPODE,TAN,AODE等算法.
• 贝叶斯网又称信念网,借助有向无环图来刻画属性之间的依赖关系,并用条件概率表来描述属性的联合概率分布.半朴素贝叶斯分类器是贝叶斯网的一种特例.
• EM(Expectation-Maximization)算法是常用的估计参数隐变量的方法.基本思想是:若参数θ已知,则可根据训练数据推断出最优隐变量Z的值(E);若Z的值已知,则可方便地对参数θ做极大似然估计(M).

第8章 集成学习

• 集成学习先产生一组个体学习器,再用某种策略将它们结合起来.如果集成中只包含同种类型的个体学习器则叫同质集成,其中的个体学习器称为基学习器,相应的学习算法称为基学习算法.如果包含不同类型的个体学习器则叫异质集成,其中的学习器常称为组件学习器.
• 要获得好的集成,个体学习器应"好而不同".即要有一定的准确性,并且要有多样性.
• 目前的集成学习方法大致分为两大类:

1. 序列化方法:个体学习器间存在强依赖关系,必须串行生成.
2. 并行化方法:个体学习器间不存在强依赖关系,可同时生成.

• Boosting先从初始训练集训练出一个基学习器,再根据基学习器的表现对训练样本分布进行调整,使做错的训练样本在后续受到更多关注(给予更大的权重或重采样).然后基于调整后的样本分布来训练下一个基学习器;直到基学习器的数目达到指定值T之后,将这T个基学习器加权结合.Boosting主要关注降低偏差,因此能基于泛化性能相当弱的学习器构建出很强的集成.代表算法有AdaBoost.
• Bagging是并行式集成学习方法最著名的代表.它基于自助采样法,采样出T个含m个训练样本的采样集,基于每个采样集训练出一个基学习器,再将这些基学习器进行简单结合.在对预测输出进行结合时,常对分类任务使用投票法,对回归任务使用平均法.Bagging主要关注降低方差,因此在不剪枝决策树,神经网络等易受样本扰动的学习器上效用更明显.代表算法有随机森林.
• 随机森林在以决策树为基学习器构建Bagging的基础上,进一步引入了随机属性选择.即先从属性集合(假定有d个属性)中随机选择一个包含k个属性的子集,再从这个子集中选择一个最优属性进行划分.当k=d时,基决策树与传统决策树相同.当k=1时,则随机选择一个属性用于划分.一般推荐k=log2d.
• 学习器结合可能会从三个方面带来好处:

1. 统计:可能有多个假设在训练集上达到同等性能,单学习器可能因误选而导致泛化性能不佳,结合多个学习器会减小这一风险.
2. 计算:通过多次运行之后进行结合,降低陷入糟糕局部极小点的风险.
3. 表示:结合多个学习器,相应的假设空间有所扩大,有可能学得更好的近似.

• 结合策略:

1. 平均法:对数值型输出,最常见的策略是平均法.一般而言,在个体学习器性能相差较大时使用加权平均法,性能相近时使用简单平均法.权重一般也是从训练数据中学习而得.
2. 投票法:对分类任务来说,最常见的策略是投票法.又可细分为绝对多数投票法,相对多数投票法,加权投票法.绝对多数投票法允许"拒绝预测",若必须提供预测结果则退化为相对多数投票法.若基学习器的类型不同,则类概率值不能直接比较,需要将类概率输出转化为类标记输出后再投票.
3. 学习法:当训练数据很多时,一种更强大的策略是通过另一个学习器来结合.Stacking是学习法的典型代表.我们把个体学习器称为初级学习器,用于结合的学习器称为次级学习器或元学习器.Stacking用初级学习器的输出作为样例输入特征,用初始样本的标记作为样例标记,然后用这个新数据集来训练次级学习器.一般用初级学习器的输出类概率作为次级学习器的输入属性,用多响应线性回归(Multi-response Linear Regression,MLR)作为次级学习算法效果较好.

• 多样性增强常用的方法有:数据样本扰动,输入属性扰动,输出表示扰动,算法参数扰动.

第9章 聚类

• 聚类既能作为一个找寻数据内在分布结构的单独过程,也可以作为其他学习任务的前驱过程.

• 我们希望"物以类聚",也就是聚类结果的"簇内相似度"高且"簇间相似度"低.聚类性能度量大致有两类.一类是将聚类结果与参考模型进行比较,称为外部指标,常用的有JC,FMI,RI;另一类是直接考察聚类结果,称为内部指标,常用的有DBI,DI.

• 有序属性距离计算最常用的是闵可夫斯基距离,当p=2时即欧氏距离,当p=1时即曼哈顿距离.[图片上传失败...(image-53bb0a-1549689693016)]

• 对无序属性可采用VDM(Value Difference Metric),将闵可夫斯基距离和VDM结合即可处理混合属性,当不同属性的重要性不同时可使用加权距离.

• 我们基于某种形式的距离来定义相似度度量,但是用于相似度度量的距离未必一定要满足距离度量的基本性质,尤其是直递性.在现实任务中有必要通过距离度量学习来基于数据样本确定合适的距离计算式.

• 原型聚类假设聚类结构能通过一组原型刻画.通常算法先对原型进行初始化,然后对原型进行迭代更新求解.常用的原型聚类算法有k均值算法,学习向量量化,高斯混合聚类.

• 密度聚类假设聚类结构能通过样本分布的紧密程度确定.通常从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇.常用算法有DBSCAN

• 层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构.代表算法有AGNES.

第10章 降维与度量学习

• 懒惰学习在训练阶段只把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理,如k近邻学习(kNN).急切学习则在训练阶段就对样本进行学习处理.

• 若任意测试样本x附近任意小的δ距离范围内总能找到一个训练样本,即训练样本的采样密度足够大,或称为密采样,则最近邻分类器(1NN)的泛化错误率不超过贝叶斯最优分类器的错误率的两倍.

• 在高维情形下出现的数据样本稀疏,距离计算困难等问题称为"维数灾难".处理高维数据的两大主流技术是降维和特征选择.

• 降维亦称维数约简,即通过某种数学变换将原始高维属性空间转变为一个低维子空间.能进行降维的原因是与学习任务密切相关的或许仅仅是数据样本的某个低维分布,而不是原始高维空间的样本点.

• 多维缩放是一种经典的降维方法.它使原始空间中样本之间的距离在低维空间中得以保持.

• 主成分分析(PCA)是最常用的一种降维方法.如果要用一个超平面对所有样本进行恰当的表达,这个超平面应该具有最近重构性和最大可分性两种性质.基于这两种性质可以得到主成分分析的等价推导.PCA可以使样本的采样密度增大,同时在一定程度上起到去噪的效果.[图片上传失败...(image-9ab20f-1549689693016)]

• 线性降维方法有可能丢失低维结构,因此要引入非线性降维.一种常用方法是基于核技巧对线性降维方法进行核化.如核主成分分析(KPCA).

• 流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法.流形在局部具有欧氏空间性质.将低维流形嵌入到高维空间中,可以容易地在局部建立降维映射关系,再设法将局部映射关系推广到全局.常用的流形学习方法有等度量映射和局部线性嵌入等.

• 对高维数据进行降维的主要目的是找到一个合适的低维空间.事实上,每个空间对应了在样本属性上定义的一个距离度量,度量学习直接尝试学习出一个合适的距离度量.常用方法有近邻成分分析(NCA).

第11章 特征选择与稀疏学习

• 对当前学习任务有用的属性称为相关特征,没什么用的属性称为无关特征.从给定特征集合中选择出相关特征子集的过程称为特征选择.特征选择是一个重要的数据预处理过程.
• 冗余特征是指包含的信息可以从其他特征中推演出来的特征.冗余特征在很多时候不起作用,但若某个冗余特征恰好对应了完成学习任务所需的中间概念,则该冗余特征反而是有益的.
• 子集搜索:可以采用逐渐增加相关特征的前向搜索,每次在候选子集中加入一个特征,选取最优候选子集.也可以采用每次去掉一个无关特征的后向搜索.这些策略是贪心的,但是避免了穷举搜索产生的计算问题.
• 子集评价:特征子集A确定了对数据集D的一个划分,样本标记信息Y对应着对D的真实划分,通过估算这两个划分的差异就能对A进行评价.可采用信息熵等方法.
• 过滤式选择先对数据集进行特征选择,然后再训练学习器,特征选择过程与后续学习器无关.Relief(Relevant Features)是一种著名的过滤式选择方法.该方法设计了一个相关统计量来度量特征的重要性.
• 包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价标准.因此产生的最终学习器的性能较好,但训练时的计算开销也更大.LVW(Las Vegas Wrapper)是一个典型的包裹式特征选择方法,它在拉斯维加斯方法框架下使用随机策略来进行子集搜索,并以最终分类器的误差为特征子集评价准则.
• 嵌入式选择是将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成.例如正则化.
• L1正则化(Lasso)是指权值向量w中各个元素的绝对值之和.L1正则化趋向选择少量的特征,使其他特征尽可能为0,可以产生稀疏权值矩阵,即产生一个稀疏模型,可以用于特征选择.L1正则化是L0正则化的最优凸近似.
• L2正则化(Ridge)是指权值向量w中各个元素的平方和然后再求平方根.L2正则化趋向选择更多的特征,让这些特征尽可能接近0,可以防止模型过拟合(L1也可以).
• 字典学习也叫稀疏编码,指的是为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低的过程.
• 压缩感知关注的是利用信号本身的稀疏性,从部分观测样本中恢复原信号.分为感知测量和重构恢复两个阶段,其中重构恢复比较重要.可利用矩阵补全等方法来解决推荐系统之类的协同过滤(collaborative filtering)任务.

由于第一次阅读,12章开始的内容仅作概念性了解.

第12章 计算学习理论

• 计算学习理论研究的是关于通过计算来进行学习的理论,目的是分析学习任务的困难本质,为学习算法提供理论保证,并提供分析结果指导算法设计.
• 计算学习理论中最基本的是概率近似正确(Probably Approximately Correct,PCA)学习理论.由此可以得到PAC辨识,PAC可学习,PAC学习算法,样本复杂度等概念.
• 有限假设空间的可分情形都是PAC可学习的.对于不可分情形,可以得到不可知PAC可学习的概念,即在假设空间的所有假设中找到最好的一个.
• 对二分类问题来说,假设空间中的假设对数据集中示例赋予标记的每种可能结果称为对数据集的一种对分.若假设空间能实现数据集上的所有对分,则称数据集能被假设空间打散.假设空间的VC维是能被假设空间打散的最大数据集的大小.
• 算法的稳定性考察的是算法在输入发生变化时,输出是否会随之发生较大的变化.

第13章 半监督学习

• 主动学习是指先用有标记样本训练一个模型,通过引入额外的专家知识,将部分未标记样本转变为有标记样本,每次都挑出对改善模型性能帮助大的样本,从而构建出比较强的模型.
• 未标记样本虽未直接包含标记信息,但若它们与有标记样本是从同样的数据源独立同分布采样而来,则它们所包含的关于数据分布的信息对建模大有裨益.
• 要利用未标记样本,需要有一些基本假设,如聚类假设,流形假设.
• 半监督学习可进一步划分为纯半监督学习和直推学习.前者假定训练数据中的未标记样本并非待预测的数据,而后者则假定学习过程中所考虑的未标记样本恰是待预测数据.
• 生成式方法是直接基于生成式模型的方法.此类方法假设所有数据都是由同一个潜在的模型生成的.这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来.
• 半监督支持向量机(S3VM)是支持向量机在半监督学习上的推广.S3VM试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面.
• 除此之外,还有图半监督学习,基于分歧的方法(如协同训练),半监督聚类等学习方法.

第14章 概率图模型

• 机器学习最重要的任务,是根据一些已观察到的证据来对感兴趣的未知变量进行估计和推测.生成式模型考虑联合分布P(Y,R,O),判别式模型考虑条件分布P(Y,R|O).
• 概率图模型是一类用图来表达变量相关关系的概率模型.若变量间存在显式的因果关系,常使用贝叶斯网.若变量间存在相关性但难以获取显式的因果关系,常使用马尔可夫网.
• 隐马尔可夫模型(Hidden Markov Model,HMM)是结构最简单的动态贝叶斯网.主要用于时序数据建模,在语音识别,自然语言处理等领域有广泛应用.隐马尔可夫模型中有状态变量(隐变量)和观测变量两组变量.
• 马尔可夫链:系统下一时刻的状态仅有当前状态决定,不依赖于以往的任何状态.
• 马尔可夫随机场(Markov Random Field,MRF)是典型的马尔可夫网.每一个结点表示一个或一组变量,结点之间的边表示两个变量之间的依赖关系.
• 条件随机场是判别式模型,可看作给定观测值的马尔可夫随机场.
• 概率图模型的推断方法大致分为两类.第一类是精确推断,代表性方法有变量消去和信念传播.第二类是近似推断,可大致分为采样(如MCMC采样)和使用确定性近似完成近似推断(如变分推断).

第15章 规则学习

• 规则学习是指从训练数据中学习出一组能用于对未见示例进行判别的规则.规则学习具有较好的可解释性,能使用户直观地对判别过程有所了解.
• 规则学习的目标是产生一个能覆盖尽可能多的样例的规则集,最直接的做法是序贯覆盖,即逐条归纳:每学到一条规则,就将该规则覆盖的训练样例去除.常采用自顶向下的生成-测试法.
• 规则学习缓解过拟合的常见做法是剪枝,例如CN2,REP,IREP等算法.著名的规则学习算法RIPPER就是将剪枝与后处理优化相结合.
• 命题规则难以处理对象之间的关系,因此要用一阶逻辑表示,并且要使用一阶规则学习.它能更容易地引入领域知识.著名算法有FOIL(First-Order Inductive Learner)等.

第16章 强化学习

• 强化学习的目的是要找到能使长期累积奖赏最大化的策略.在某种意义上可看作具有"延迟标记信息"的监督学习问题.
• 每个动作的奖赏值往往来自于一个概率分布,因此强化学习会面临"探索-利用窘境",因此要在探索和利用中达成较好的折中.ε-贪心法在每次尝试时以ε的概率进行探索,以均匀概率随机选取一个动作.以1-ε的概率进行利用,选择当前平均奖赏最高的动作.Softmax算法则以较高的概率选取平均奖赏较高的动作.
• 强化学习任务对应的马尔可夫决策过程四元组已知的情形称为模型已知.在已知模型的环境中学习称为"有模型学习".反之称为"免模型学习".
• 从人类专家的决策过程范例中学习的过程称为模仿学习.