做网站要哪些人员,国网,做宠物的网站有哪些,长安东莞网站设计周志华老师亲讲-西瓜书全网最详尽讲解-1080p高清原版《机器学习初步》 周志华机器学习#xff08;西瓜书#xff09;学习笔记#xff08;持续更新#xff09; 周志华《Machine Learning》学习笔记 绪论
基本术语
数据集#xff08;data set#xff09;#xff1a;一堆… 周志华老师亲讲-西瓜书全网最详尽讲解-1080p高清原版《机器学习初步》 周志华机器学习西瓜书学习笔记持续更新 周志华《Machine Learning》学习笔记 绪论
基本术语
数据集data set一堆关于某种事物的 数据的集合示例instance或样本(sample)每条记录是关于一个事件或对象的描述称为一个示例或样本属性attribute或特征feature反映事件或对象在某方面的表现或性质的事项例如“颜值”属性值attribute value属性上的取值例如“美丽动人”学习learning或训练training从数据中学得模型的过程训练数据training data:训练过程中使用的数据训练样本training sample:训练数据中的每一个样本训练集training set:训练样本组成的集合假设hypothesis:学得模型对应了关于数据的某种潜在的规律也称假设真相或真实ground-truth:这种潜在规律自身分类classification:预测的是离散值的学习任务例如‘0’、‘1’ 分类中又分为二分类和多分类任务。 二分类顾名思义只需分2类一般分别称为“正类”与“反类”且一般正类用“1”表示反类用“0”表示。 回归regression:预测的是连续值的学习任务测试test学得模型后对其进行预测的过程测试样本test sample:被预测的样本监督学习:训练数据有标记信息的学习过程也叫有导师学习无监督学习训练数据木得标记信息的学习过程也叫无导师学习 分类和回归属于典型的监督学习问题聚类属于无监督学习问题。 分类训练数据已经有人为标记信息计算机通过学习这些训练数据把未出现在训练样本中的陌生的数据 分到已有的类别中的过程聚类训练数据中没有任何标记信息计算机需要自行寻找特征将这些数据分为几个簇然后把陌生的数据分到计算机自己划分的几个簇中的过程 聚类clustering把训练集中样本分为若干组每一组称为一“簇”cluster泛化机器学习所学得模型适用于陌生数据的能力。 机器学习的目的使学得的模型可以更好地适用于未知样本。 我们常说泛化性能优劣即模型对于陌生数据的适用性的好坏。 一般我们假设全体数据在样本空间上满足一个未知的分布那么学习的目的就可以认为寻找最契合这个分布的一个函数来把训练样本完美的分到各自的类中。一般情况下训练样本越多我们得到的关于该分布的信息就越多这样就越有可能找到这个函数也就越有可能通过学习活得具有强泛化能力的模型。 假设空间
归纳和演绎是科学推理的两大基本手段前者是从特殊到一般的“泛化”过程即从具体的事实归结出一般性规律后者则是从一般到特殊的“特化”即从基础原理推导出具体状况。 学习过程可以看作是一个在所有假设组成的空间中进行搜索的过程目的是找到与训练集匹配的假设。而现实中可能会有多个假设和训练集一致即存在一个与训练集一致的“假设集合”称之为“版本空间”
归纳偏好
机器学习算法在学习过程中对某种假设类型的偏好称为归纳偏好 需要注意任何一个机器学习算法都有其归纳偏好否则将无法产生确定的学习结果 NFL定理或者没有免费的午餐定理No Free Lunch Theorem:算法A若在某问题上比另一个算法B好比存在另一些问题算法B比算法A好。换言之无论学习算法A多么聪明学习算法B多么笨拙它们的期望性能完全一样总误差与学习算法无关 但需要注意,NFL定理的前提是所有问题出现的机会相同或所有问题同等重要,但是实际情况并非如此. NFL定理最重要的寓意是:具体问题具体分析!即脱离具体问题而空泛的谈论什么学习算法更好毫无意义. 最优方案按需设计度身定制奥卡姆剃刀原则主张选择和经验观察一致的 最简单假设。若无必要勿增实体
习题
下列有关机器学习基本术语的说法错误的是
A、从数据中学得模型的过程称为“学习”或“训练”
B、训练过程中使用的数据称为“训练数据”每一个样本称为一个“训练样本”训练样本组成的集合称为“训练集”
C、学得模型对应了关于数据的某种潜在的规律称为“假设”
D、学习过程就是为了找出数据的某种潜在规律这个规律自身一般称为“数据特征”
解析学习过程是为了找出数据的某种潜在规律这种规律自身一般称为假设从数据中学得模型的过程称为学习也可以称为训练训练过程使用的数据称为训练数据其中的样本称为训练样本。
以下关于机器学习预测任务的说法错误的是
A、一般地预测任务是希望通过对训练集进行学习建立一个从输入空间 x xx 到输出空间 y yy 的映射 B、对于二分类任务一般令 y { − 1 , 1 } y{-1,1}y{−1,1}或 { 0 , 1 } {0,1}{0,1} C、对于回归问题一般 y R yRyR D、预测任务不需要训练样本的的标记信息 解析监督学习需要训练样本的标记信息
学出来的模型适用于新样本的能力称为 ____ 能力。该能力越强说明学得的模型越能很好地适用于整个样本空间。 解析泛化 泛化能力generalization ability是指机器学习算法对新样本的适应能力。 学习的目的是学到隐含在数据背后的规律对具有同一规律的学习集以外的数据经过训练的网络也能给出合适的输出该能力称为泛化能力。这种能力也是学习到的模型对未知数据的预测能力这个未见过的测试数据必须是和训练数据处于同一分布,不在同一分布的数据是不符合独立同分布假设的对同一规律不同的数据集的预测能力。通常通过测试误差来评价学习方法的泛化能力。学得模型后使用其进行预测的过程称为____。 解析测试 学得模型后使用其进行预测的过程称为测试 (testing) 被预测的样本称为测试样本 (testing sample)。下列说法错误的是
A、模型是通过学习算法得到的
B、机器学习通常解决高度不确定性和复杂性的问题
C、分类和回归是监督学习的代表
D、机器学习一定需要类别标记 解析D 聚类等任务不需要类别标记
下列说法错误的是
A、学得模型适用于新样本的能力称为“泛化”能力
B、机器学习一般有“独立同分布”假设
C、机器学习在只要见过的数据上做好就行了未见过样本上的性能不重要
D、一般假设拿到的所有数据都来自一个潜在的分布 解析C机器学习主要用于处理未来的新数据
把见过的汽车分成若干组这是一个____分类/回归/聚类任务 解析聚类 把见过的汽车分组这样一个任务中任务本身并未要求按什么样的准则划分、划分为什么样的类别这样我们很难对汽车加上合适的label并将其看作是一个监督学习来实现分类过程。故本题应为无监督学习中的聚类任务本题应填聚类。
模型评估与选择
经验误差和过拟合
何为一个好的模型错误率低、精确度高、召回率高等指标都可以但视具体任务和使用者需求而异。在评价模型性能时我们更希望它泛化能力强。
错误率Eerror rate分类错误的样本数a/总样本数m精度(accuracy)1 - 错误率E误差(error)更一般地把学习器的实际预测输出和样本的真实输出之间的差异称为误差训练误差training error或经验误差empirical error:学习器模型也称为学习器在训练集上的误差。经验误差并非越小越好因为会出现过拟合泛化误差generalization error或测试误差:在新样本上的误差。泛化误差越小越好
实际希望的是在新样本上能表现得很好的学习器。但可能出现的问题是
欠拟合underfitting对训练样本的一般性质尚未学好。例如以为有四肢就是人类。过拟合或过配overfitting对训练样本学得太“好”已经把训练样本本身的一些特点作为所有潜在样本都会具有的一般性质。例如长得帅才是人类。 进行模型评估和选择 没有未来数据如何知道模型的泛化能力涉及到评估方法的设计对某个具体任务的需求把握是性能度量要考虑的。 例如信用卡欺诈的检测本身发生的概率就极低那么认定所有的都不是欺诈准确率高达99%但不能实现找出欺诈的目标并没有意义。为了说明模型在统计意义上表现好我们最需要考虑比较检验
评估方法
测试集应该与训练集互斥即测试样本尽量不在训练集中出现、未在训练过程中使用过。 通常我们会得到一个含m个样例的数据集如何通过适当处理划分为训练集S和测试集T有以下三种常见做法
留出法hold-out
留出法即直接将数据集D划分为两个互斥的集合其中一个作为训练集S另一个作为测试集T保证S∩T∅且S∪TD。 在划分训练集和测试集之后根据在测试集上不同算法的表现选择最优的算法然后再用该算法去在全部的数据M上训练的模型给用户。
交叉验证法cross validation
交叉验证法即将数据集D划分为k个大小相似的互斥子集即DD1∪D2∪…∪DkDi∩Dj∅(i≠j)。每个子集Di都尽可能保持数据分布的一致性即从D中分层采样得到。然后每次用k-1个子集的并集作为训练集剩下的那个子集作为测试集这样就可以得到k组训练/测试集从而进行k次训练和测试最终返回这k次测试的均值。 留一法(Leave-One-Out简称LOO)假定数据集D中有m个样本令km则会发现m个样本只有唯一的划分方法来划分为m个子集——每个子集一个样本所以留一法的训练集与数据集D相比只差一个样本故留一法中被实际评测的模型与期望评估的用D训练出的模型很相似因此留一法的评估结果往往被认为较准确。 但是未必永远适用记住NFL“没有免费的午餐”定理在机器学习各个环节都是适用的。
自助法bootstrap sampling
在留出法和交叉验证法中由于保留了一部分样本作为测试所以实际评估的模型中所使用的训练集比D小而我们希望评估的是D训练出的模型所以这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小但计算复杂度又太高了。 自助法是种较好的解决方案。自助法以自助采样(bootstrap sampling)为基础自助采样也叫“可重复采样”与“有放回采样” 给定包含m个样本的数据集D我们对它进行采样产生数据集D’每次从D中随机选一个样本将其拷贝如D’中再将其放回D中重复m次那么就可以得到包含m个样本的数据集D’。显然D中一部分样本会在D’中多次出现而另一部分不出现由一个简单的估计可以得到样本在m次采样中不被采到的概率约为
把D’当做训练集D-D’作为测试集则实际评估模型与期望评估模型都有m个训练样本而我们仍然有数据总量1/3的样本用于测试这样的测试结果称为“包外估计”。 小结 自助法在数据量较少难以有效划分训练集和测试集的时候很有用然而自助法改变了初始数据分布引入了估计偏差故在初始数据量足够的时候留出法和交叉验证法更常用一些。
调参和最终模型
调参parameter tuning:在进行模型评估和选择时除了要对使用学习算法进行选择还需要对算法参数进行设定即“参数调节”或“调参”其中模型选择指的是确定变量将使用的算法是变量将确定的算法参数也是变量对其的确定都是模型选择的过程。
我们通常把学得模型在实际使用中遇到的数据称为测试数据为了加以区分
验证集(validation set)模型评估与选择中用于评估测试的数据集。 注意调参数的过程也是训练过程的一部分则调参数的数据集不能来自测试集。 例如在研究对比不同算法的泛化性能时我们用测试集上的判别效果来估计泛化性能而把训练数据另外划分为测试集和验证集基于验证集上的性能来进行模型选择和调参。
性能度量performance measure
对学习器的泛化性能进行评估不仅需要有效可行的实验估计方法还需要有衡量模型泛化能力的评价标准即性能度量。性能度量反映了任务需求。 要评估学习器f的性能就要把学习器预测结果f(x)和真实标记y进行比较。 本文已提到过的错误率和精度是分类任务种最常用的两种性能度量既适用于二分类任务也适用于多分类任务 但是我们通常会有更复杂的需求引入查准率和查全率与F1. 对于二分类任务可将样例根据其真实类别与学习器预测类别的组合划分为真正例(true positive)、假正例(false positive)、真反例(true negative)与假反例(false negative)四种情形。分别对应为TP、FP、TN、FN。 TP被模型预测为正类的正样本实际为正预测也为正。 TN被模型预测为负类的负样本实际为负预测也为负。 FP被模型预测为正类的负样本实际为负预测为正。 FN被模型预测为负类的正样本实际为正预测为负。 查准率和查全率是一对矛盾的度量。一般查准率高时查全率往往偏低而查全率高时查准率偏低。考虑如何均衡两者一种办法是F1度量
比较检验
假设检验
交叉验证t检验
McNemar检验
习题
为了说明模型在统计意义上表现好我们最需要考虑 A、评估方法 B、性能度量 C、比较检验 D、以上三个选项都不需要考虑 解析C 比较检验主要是用于判断模型是否在统计意义上表现良好其余A选项的评估方法主要用于衡量模型在未来的表现好坏B选项性能度量是针对具体问题给定的度量标准对不同问题不太一样如欺诈问题10次欺诈99990次非欺诈如果全分类为非欺诈虽然精度很大但是对该问题没有意义。下列什么方法可以用来获得从原始数据集中划分出“测试集” A、留出法 B、交叉验证法 C、自助法 D、以上三个选项都可以 解析D调参以什么集合上的性能作为评价标准 A、训练集 B、测试集 C、验证集 D、以上选项都可以 解析C当我们使用一个多项式函数去逼近数据集时下面哪一个说法是正确的 A、多项式的次数是超参数 B、多项式的系数是超参数 C、多项式的次数必须通过数据去学习 D、以上说法都是正确的 解析A 在使用多项式逼近数据集时会人工赋予多项式次数x的多少次方然后通过训练数据学习多项式的系数ywxb的w和b因此多项式的次数是超参数而多项式的系数不是超参数。超参数虽然可以通过学习得到但一般由人工决定C选项太过绝对。在训练集上的误差被称作 A、泛化误差 B、经验误差 C、测试误差 D、以上三个选项都不对 解析B 训练误差training error或经验误差empirical error:学习器模型也称为学习器在训练集上的误差。经验误差并非越小越好因为会出现过拟合 泛化误差generalization error或测试误差:在新样本上的误差。泛化误差越小越好当学习任务对数据分布的轻微变化比较鲁棒且数据量较少时适合使用什么样的数据集划分方式 A、留出法 B、交叉验证法 C、自助法 D、以上三个选项都可以 解析C 本题关键是考虑“数据量较少”此时无论是使用留出法还是交叉验证法都会使得训练集数据量进一步变少而使用自助法则不会有这样的问题不改变样本数量其次考虑“对数据分布轻微变化比较鲁棒”说明使用自助法时带来的训练数据分布变化不会有太多负面影响。考虑一个三分类数据集其由30个西瓜30个苹果30个香蕉构成。先有一个学习策略为预测新样本为训练集中样本数目最多类别的分类器存在多个类别样本数量一样多时则随机选择一个类别预测请问通过什么评估方式会导致其平均准确率为0。____留出法/交叉验证每一折样本数大于1/留一法 解析留一法
线性模型
基本形式
给定由d个属性描述的示例x(x1; x2; ……;xd),其中xi是x在第i个属性上的取值线性模型linear model试图学得一个通过属性的的线性组合来进行预测的函数即 一般用向量形式写为 其中 线性模型形式简单、易于建模、有很好的可解释性。
线性回归
对离散属性 若属性值间存在“序”order关系 可通过连续化将其转化为连续值。 例如属性“身高”的取值“高”“矮”可转化为{1.00.0}三值属性“高度”的取值“高”“中”“低”可转化为{1.00.50.0}若属性值间不存在序关系 假定有k个属性值则通常转化为k维向量 例如属性“瓜类”的取值“西瓜”“南瓜”“黄瓜”可转化为001010100 给定数据集D {(x1,y1),(x2,y2),…,(xm,ym)}其中xi (xi1;xi1;…;xid),yi ∈R。线性回归linear regression试图学得一个线性模型以尽可能准确地预测实值输出标记。线性回归试图学得 确定w和b 关键在于如何衡量f(x)和y之间的差别。均方误差是回归任务中最常用的性能度量则可试图把均分误差最小化即 均方误差具有很好的几何意义它对应了常用的欧几里得距离或简称“欧氏距离”Euclidean distance。基于均方误差最小化来进行模型求解的方法称为最小二乘法least square method。在线性回归中最小二乘法就是试图找到一条直线使所有样本到直线上的欧氏距离之和最小。 求解w和b使均方误差最小化的过程称为线性回归模型的最小二乘“参数估计”parameter estimation。可对E(w,b)分别对w和b求导并令导数为0解得闭式closed-form解。
多元线性回归 更一般的情形是如同先前提到的数据集D样本由d个属性描述。此时我们试图学得
称为“多元线性回归”multivariate linear regression。 类似的可利用最小二乘法对w和b进行估计。为便于讨论我们把w和b吸收入向量形式 w ^ \widehat{w} w (w;b),相应的把数据集D表示为m*(d1)大小的矩阵X,其中每行对应于一个示例该行前d个元素对应于示例的d个属性值最后一个元素恒置为1即 再把标记也写为向量形式则有 对 w ^ \widehat{w} w 求导并令其为0得 w ^ \widehat{w} w 最优解的闭式解。 如果XTX为满秩矩阵或者正定矩阵那么令上式为零有 现实中XTX往往不是满秩矩阵许多任务中会遇到变量的数目超过样例数的情况导致X的列数多于行数显然不满秩此时会解出多个**w^**满足均方误差最小的条件选择哪一个作为输出就是问题常见的做法是引入正则化regularization项。
广义线性模型 考虑能否让模型预测值逼近y的衍生物例如假设我们认为示例所对应的输出标记是在指数尺度上变化则可将输出标记的对数作为线性模型逼近的目标即lnywTxb。这就是对数线性回归log-linear regression。实质上是在求取 输入空间到输出空间的非线性函数映射。如上图所示对数函数起到了将线性回归模型的预测值和真实标记联系起来的作用。
更一般地考虑单调可微函数g()这样得到的模型称为“广义线性模型”generalized linear model。显然对数线性回归是广义线性模型在g()ln()时的特例。
对率回归
上一节讨论了如何使用线性模型进行回归学习当要做的是分类任务是只需找一个单调可微函数把分类任务的真实标记y和线性回归模型的预测值联系起来。 考虑二分类任务其输出标记y∈{01}而线性回归模型产生的预测值zwTxb是实值需要把实值z转换为0/1值。最理想的是“单位阶跃函数”unit-step function 即若预测值z大于零就判为正例小于零则判为反例预测值为临界值零则可任意判别。 但是从上图可知单位阶跃函数不连续则不能直接作为广义线性模型我们希望能找到在一定程度上近似单位阶跃函数的“替代函数”surrogate function,且能单调可微。 而对数几率函数logistic function正是这样一个常用的替代函数。 若将y视为样本x作为正例的可能性则1-y是其反例可能性两者的比值 y 1 − y \frac{y}{1-y} 1−yy称为“几率”odds,反映了x作为正例的相对可能性。对几率取对数则得到“对数几率”log odds,也称logit l n y 1 − y ln\frac{y}{1-y} ln1−yy
由此看出实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率则其对应的模型称为“对数几率回归”logistic regression,也称logit regression。注意虽然名字是“回归”但实际是一种分类学习方法。
对数回归几率对率回归方法优点; 无需事先假设数据分布可得到“类别”的近似概率预测可直接应用现有数值优化算法求取最优解
对率回归求解 先验概率prior probability指根据以往经验和分析。在实验或采样前就可以得到的概率。 后验概率posterior probability指某件事已经发生想要计算这件事发生的原因是由某个因素引起的概率。 下面来确定式中的w和b。把式中的y视为类后验概率估计py1|x,则 可重写为 显然有 于是可通过“极大似然法”maximum likelihood method来估计w和b。 对率回归模型最大化“对数似然”log-likelihood 即令每个样本属于其真实标记的概率越大越好。
线性判别分析 线性判别分析Linear Discriminant Analysis,简称LDA是一种经典的线性学习方法。在二分类问题上因为最早由Fisher提出也称“Fisher判别分析”。 LDA的思想非常朴素给定训练样例集设法把样例投影到一条直线上使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离在对新样本进行分类时将其投影到同样的这条直线上再根据投影点的位置来确定新样本的类别。 若将数据投影到直线w上则两类样本的中心在直线上的投影分别为wTμ0和wTμ1若将所有样本点都投影到直线上则两类样本的协方差分别为wT∑0w和wT∑1w。 要让同类样例投影点尽可能接近可以让同类样例投影点的协方差尽可能小而欲使异类样例的投影点尽可能远离可以让类中心之间的距离尽可能大。同时考虑这两个因素则可得到欲最大化的目标 定义“类内散度矩阵”within-class scatter matrix和“类间散度矩阵”between-class scatter matrix则上式J可重写为下图所示即LDA欲最大化的目标 W的闭式解其实是N-1个最大广义特征值所对应的特征向量组成的矩阵。 若将W视为一个投影矩阵则LDA将样本投影到了N-1维空间上N-1往往远小于数据原有的属性数 于是LDA也常被视为一种经典的监督降维技术。 【学长小课堂】什么是奇异值分解SVD视频版20min 奇异值分解SVD(文字版) 拉格朗日乘子法即拉格朗日乘数法其主要思想是引入一个新的参数 λ 即拉格朗日乘子将约束条件函数与原函数联系到一起使能配成与变量数量相等的等式方程从而求出得到原函数极值的各个变量的解。 类别不平衡 前面介绍的分类学习方法都有一个共同的基本假设即不同类别的训练样例数目相当。 类别不平衡class-imbalance指分类任务中不同类别的训练样例数目差别很大的情况类别不平衡需要处理的情况小类比大类更重要。 本节以反例样例较多为例展开。类别不平衡学习的一个基本策略再缩放rescaling现有技术主要有三类
过采样oversampling 增加一些正例使得正、反例数目接近再进行学习。即对训练集里的正类样例进行“过采样”。 注意不能简单地对初始正例样本进行重复采样否则会导致严重的过拟合。过采样法的代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例。 欠采样(undersampling) 去除一些反例是得正、反例数目接近再进行学习。即直接对训练集里的反类样例进行“欠采样” 欠采样法若随即丢弃反例可能丢失一些重要信息。欠采样的代表性算法EasyEnsemble是利用集成学习机制把反例划分为若干集合供不同学习器使用这样对每个学习器来看都进行了欠采样但在全局来看却不会丢失重要信息。 阈值移动(threshold-moving) 直接基于原始训练集进行学习但在用训练好的分类器进行预测时把嵌入到其决策过程中
习题
对数几率回归为什么不能通过令偏导为0求解 A、均方损失函数太复杂 B、均方损失非凸 C、均方损失没有偏导为0的点 D、均方损失没有极值点 解析B下列关于梯度下降法描述错误的是 A、可以用于求解对数几率回归 B、是一种迭代求解的方法 C、可以比较好的并行化 D、可以高效地求解所有凸优化问题 解析D极大似然法最大化____函数 解析似然在线性判别分析中类内散度矩阵的计算方法是将每个类别的样本与其____[最近样本/类别均值]进行求差然后对差值向量进行矩阵乘积 解析类别均值下列哪个模型不是广义线性模型 解析D下列哪个选项不是多元线性回归使用正则化的原因 A、计算机数值精度有限 B、样例维度大于样例数 C、样例的采样过程存在偏差 D、存在大量线性相关的样例 解析C在求解对率回归时下列哪个选项不是极大似然法的优势 A、优化目标是凸函数 B、具有闭式解 C、可以使用梯度下降法下列有关线性判别分析和主成分分析的说法错误的是 A、两者都是通过线性变换将数据转换到新的坐标系中 B、两者都是数据降维方法 C、主成分分析主要用于有监督学习线性判别分析主要用于无监督学习 D、主成分分析主要用于提取数据中的主要成分线性判别分析主要用于分类 解析0.500 解析0.535比较上述两题求得的斜率值最小二乘法求得的斜率____(大于/等于/小于) 最小化数据集到线性模型欧式距离的平方和求得的斜率。这一结论对一般问题也成立可尝试证明之。 解析小于OvR是一种常用的多分类方法该方法每次将一个类的样例作为正例、所有其他类的样例作为反例。对于类别均衡的10分类问题若使用OvR以及阈值移动法来训练则阈值应设为____ (保留3位小数)。 解析0.100
决策树
决策树也称判定树根据上下文有时指学习方法有时指学得的树。
决策树的基本流程 一般的一颗决策树包含一个根节点若干个内部节点和若干个叶节点。叶节点对应于决策结果其他每个节点则对应于一个属性测试 每个节点包含的样本集合根据属性测试的结果被划分到子节点中 根节点包含样本全集。 从根节点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强即处理未见示例能力强的决策树其基本流程遵循简单且直观的“分而治之”策略。
信息增益划分
一般而言随着划分过程不断进行我们希望决策树的分支节点所包含的样本尽可能属于同一类别即节点的“纯度”越来越高。 假定当前样本集合D中第k类样本所占的比例为pk(k1,2……|y|)则D的信息熵定义如下 假定离散属性a有V个可能的取值{a1,a2, …,aV}若使用a来对样本集D进行划分则会产生V个分支节点其中第v个分支结点包含了D中所有在属性a上取值为aV的样本记为Dv。我们可根据上式计算出Dv的信息熵再考虑到不同的分支结点所包含的样本数不同给分支结点赋予权重|Dv|/|D|即样本数越多的分支节点其影响越大。 计算出用属性a对样本集D进行划分所获得的“信息增益”information gain。 一般而言信息增益越大则意味着使用属性a来进行划分所获得的“纯度提升”越大。从而我们可以用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。 其他属性划分准则
上述的信息增益准则对可取值数目较多的属性有所偏好为减少这种偏好可能带来的不利影响C4.5决策树算法不直接使用信息增益而是使用“增益率”gain ratio来选择最优化分属性。 增益率准则对可取值数目较少的属性有所偏好则C4.5并非直接选择增益率最大的候选划分属性而是使用一个启发式因为关键在于如何界定何为纯净先从候选划分属性中找出信息增益高于平均水平的属性抵消偏向于分支数多的情况再从中选择增益率最高的。 CART决策树使用“基尼指数”Gini index来选择划分属性。数据集D的纯度可用基尼值来度量
决策树的剪枝
剪枝pruning是决策树学习算法对付过拟合的主要手段。在决策树学习中为了尽可能正确分类训练样本结点划分过程将不断重复有时会造成决策树分支过多就有可能因训练样本学得“太好”以致于把训练集自身的一些特点作为所有数据都具有的一般性质而导致过拟合。因而可通过主动去掉一些分支降低过拟合的风险。
决策树剪枝的基本策略有“预剪枝”prepruning和“后剪枝”(post-pruning)。 预剪枝指在决策树生成过程中对每个结点在划分前先进行估计若当前节点的划分不能带来决策树泛化性能提升则停止划分并将当前节点标记为叶节点后剪枝先从训练集生成一颗完整的决策树再自底向上地对非叶节点进行考察若将该节点对应的子树替换成叶节点能带来决策树泛化性能提升则将该子树替换为叶节点。
预剪枝和后剪枝 预剪枝 预剪枝基于信息增益原则来进行划分属性选择 预剪枝使得决策树的很多分支都没有“展开” 优点 降低了过拟合的风险减少了决策树的训练时间开销和测试时间开销 缺点 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降但在其基础上进行的后续划分却有可能导致性能显著提高预剪枝基于“贪心”本质禁止这些分支展开给预剪枝决策树带来了欠拟合的风险 后剪枝 后剪枝思想类似于预剪枝不同之处在于后剪枝是自下而上 该情况中验证集精度虽无提高但根据奥卡姆剃刀原则剪枝后的模型更好。因此实际的决策树算法在这种情况下通常要剪枝本教程为绘图的方便采取了不剪枝的保守策略。 一般情况下后剪枝决策树的欠拟合风险很小泛化性能往往会优于预剪枝决策树 但后剪枝过程是在生成决策树之后进行的并且要自底向上地对树中的所有非叶节点进行逐一考察则其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多
预剪枝VS后剪枝
缺失值的处理 习题
对视频中出现的西瓜数据集2.0《机器学习》教材第76页划分前的信息熵为0.998若使用编号属性进行划分则信息增益为____保留3位小数 解析0.998决策树划分时当遇到以下哪种情形时将结点标记为叶节点其类别标记为当前样本集中样本数最多的类 A、当前属性集为空或所有样本在所有属性上取值相同 B、当前属性集不为空或所有样本在所有属性上取值相同 C、当前结点包含的样本集合为空或当前属性集为空 D、当前结点包含的样本集合为空或所有样本在所有属性上取值相同 解析A若数据集的属性全为离散值决策树学习时____可以/不可以把用过的属性再作为划分属性。 解析不可以通常来说子节点的基尼不纯度与其父节点是什么样的关系 A、通常更低 B、通常更高 C、永远更高 D、永远更低 解析A
支持向量机
支持向量机基本型 由于训练集的局限性或噪声的因素训练集外的样本可能比上图中的训练样本更接近两个类的分割界使得很多划分超平面出现错误而正中间受影响最小。换言之这个划分超平面是最鲁棒的对未见示例的泛化能力最强。 鲁棒性即健壮性指应对异常情况的处理能力。换言之指一个系统或组织抵御或克服不利条件的能力 其中w(w1;w2;……wd)为法向量决定了超平面的方向 b为位移项决定了超平面和原点之间的距离。 显然划分超平面可以被法向量w和位移b确定下面将其记为w,b。样本空间中任意点x到超平面w,b的距离可写为上式r。 假设超平面w,b能把训练样本正确分类即对于xi,yi∈D 若yi1,则有wTb0;若yi-1,则有wTb0令 如上个课件图所示距离超平面最近的这几个训练样本点使上式的等号成立将其称为“支持向量”support vector两个异类支持向量到超平面的距离之和为 γ 2 ∣ ∣ w ∣ ∣ γ\frac{2}{||w||} γ∣∣w∣∣2将之称为“间隔”margin 欲找到具有“最大间隔”maximum margin的划分超平面即找到能满足上上图中式子约束的参数w和b使得γ最大。 为了最大化间隔等价于最大化||w||-1,又等价于最小化||w||2。于是可重写为上图式子即支持向量机Support Vector Machine,简称SVM的基本型。
对偶问题和解的特性
对上式使用拉格朗日乘子法可得到其“对偶问题”dual problem。具体而言对上式的每条约束添加拉格朗日乘子αi≥0则该问题的拉格朗日函数可写为下图所示。 解出α后求出w和b即可得到模型。从对偶问题中解出的αi是式中的拉格朗日乘子它恰好对应着训练样本xi,yi.且有不等式约束则上述过程需满足KKTKarush-Kuhn-Tucker条件。 对任意训练样本xi,yi总有αi0或yif(xi)1.当αi0则该样本将不会在式中的求和出现也就不会对f(x)有任何影响若αi0则必有yif(xi)1所对应的样本点位于最大间隔边界上是一个支持向量。这表明支持向量机的一个重要性质训练完成后大部分的训练样本都无需保留最终模型只和支持向量有关。解的稀疏性
求解方法 如何求解该问题呢 这是一个二次规划问题可使用通用的二次规划算法来求解。但是该问题的规模正比于训练样本数会在实际任务中造成很大的开销。为了避免开销大的问题大牛们通过利用问题本身的特性提出了很多高效算法SMOSequential Minimal Optimization序列最小优化算法是其中一个代表。 SMO的基本思路是先固定αi之外的所有参数再求αi上的极值。由于存在约束 当固定αi之外的其他变量则αi可由其他变量导出。故SMO每次选择两个变量αi和αj并固定其他参数。因此在参数初始化后SMO不断执行如下两个步骤直至收敛
选取一对需要更新的变量αi和αj固定αi和αj之外的参数求解上上式获得更新后的αi和αj 注意只需选取的αi和αj中有一个不满足KKT条件目标函数就会在迭代后增大。直观上看 KKT条件违背的程度越大则变量更新后可能导致的目标函数增幅越大。因此SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值增长最快的变量但由于比较各变量所对应的目标函数增幅的复杂度过高因此SMO采用了一个启发式使选取的两变量所对应样本之间的间隔最大。 一种直观的解释是这样的两个变量有很大的差别与对两个相似的变量进行更新相比对它们进行更新会带给目标函数值更大的变化。 SMO算法之所以高效正是由于在固定其他参数后仅优化两个参数的过程能做到非常高效。
特征空间映射
在之前的讨论中我们假设训练样本是线性可分的即存在一个划分超平面能将训练样本正确分类。但在现实任务中原始样本空间内也许并不存在一个能拿个正确划分两类样本的超平面看例如下图的“异或”问题。 对这类的问题可将样本从原始空间映射到一个更高维的特征空间使得样本在这个特征空间内线性可分。例如下图中把原始的二维空间映射到一个合适的三维空间就能找到一个合适的划分超平面。 且当原始空间是有限维即属性数优先则一定存在一个高维特征空间使样本可分。
核函数
求解上式涉及计算φ(xi)Tφ(xj)这是样本xi和xj映射到特征空间之后的内积。由于特征空间维数可能很高甚至可能是无穷维因此直接计算φ(xi)Tφ(xj)通常是困难的。为了避开这个问题可设想这样的一个函数 即xi和xj在特征空间的内积就等于它们在原始样本空间中通过函数k(,)计算的结果。有了这样的函数就不必直接去计算高维甚至无穷维 特征空间中的内积。则可重写为
求解后可得 这里的函数k(,)就是“核函数”kernel function。上式表明模型最优解可通过训练样本的核函数展开这一展式也称“支持向量展式”support vector expansion 上述定理表明只要一个对称函数所对应的核矩阵半正定恰满足距离矩阵的含义它就能作为核函数使用。 事实上对于一个半正定核矩阵总能找到一个与之对应的映射φ。换言之任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”Reproducing Kernel Hilbert Space,简称RKHS的特征空间。 通过前面的讨论可知我们希望样本在特征空间内线性可分则特征空间的好坏对支持向量机的性能至关重要。需要注意的是在不知道特征映射的形式时我们并不知道什么样的核函数是合适的而核函数也只是隐式地定义了这个特征空间。故“核函数选择”成为支持向量机的最大变数。若核函数选择不合适则意味着把样本映射到了一个不合适的特征空间很可能导致性能不好。这方面有一些基本的经验例如对文本数据通常采用线性核情况不明时可先尝试高斯核 常用的核函数如下 还可以通过函数组合得到例如
软间隔SVM
前面的讨论中我们一直假定训练样本在样本空间或特征空间中是线性可分的即存在一个超平面能将不同类的样本完全划分开。但在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分退一步说即便找到了某个核函数使训练集在特征空间中线性可分也很难判定这个看似线性可分的结果不是由过拟合造成的。 缓解该问题的一个方法是允许支持向量机在一些样本上出错。故引入“软间隔”soft margin的概念。 具体而言前面介绍的支持向量机形式是要求所有样本均满足约束即所有样本都必须划分正确这称为“硬间隔”hard margin而软间隔则是允许某些样本不满足约束 在最大化间隔的同时不满足约束的样本应尽可能少允许有一些不满足约束但不能都不满足。因而优化目标可写为 其中C0(C越小容忍度越大)是一个常数l0/1是“0/1损失函数” 当C为无穷大时使所有样本均满足约束当C取有限值时允许有一些样本不满足约束。 l0/1非凸、非连续数学性质不太好使得优化目标不易直接求解。因此人们通常用其他一些函数来代替l0/1称为“替代损失”surrogate loss。替代损失函数一般具有较好的数学性质例如通常是凸的连续函数且是l0/1的上街。常用的替代损失函数有
当采用hinge损失优化目标变为 引入松弛变量可重写为下式。这就是常用的“软间隔支持向量机” 显然下式中每个样本都有一个对应的松弛变量用以表征该样本不满足约束的程度。但是这仍是一个二次规划问题。因此可通过拉格朗日乘子法得到拉格朗日函数 αiμi是拉格朗日乘子。 求偏导并变换可得对偶问题 与硬间隔的对偶问题的唯一差别对偶变量αi的约束不同。 软间隔的KKT条件为
正则化
我们还可以把上式中的0/1损失函数换为别的替代损失函数来得到其他学习模型这些模型的性质和所用的替代函数直接相关但它们具有一个共性优化目标中的第一项用来描述划分超平面的“间隔”大小另一项用来表述训练集上的误差可写为更一般的形式如下式。 C用于对二者进行折中。从经验风险最小化的角度来看Ωf表述了我们希望获得具有何种性质的模型例如希望获得复杂度较小的模型这为引入领域知识和用户意图提供了途径另一方面该信息有助于消减假设空间从而降低了最小化训练误差的过拟合风险。从该角度而言上式称为“正则化”regularization问题Ωf称为正则化项C称为正则化常数。Lp范数norm是常用的正则化项。
如何使用SVM 考虑回归问题。给定训练样本D希望学得一个回归模型使得f(x)和y尽可能接近w和b是待确定的模型参数。 对于样本x,y传统回归模型通常直接基于模型输出f(x)和真实输出y之间的差别来计算损失当且仅当f(x)和y完全相同时损失才为0 支持向量回归Support Vector Regression,简称SVR假设我们能容忍f(x)和y之间最多有ε的偏差即仅当f(x)和y之间的差别绝对值大于ε时才计算损失。这相当于以f(x)为中心构建了一个宽度为2ε的尖阁待若驯良样本落入此间隔带则认为是被预测正确的 则SVR问题支持向量回归可形式化为 其中C为正则化常数lc是图中的ε-不敏感损失ε-insensitive loss函数 引入松弛变量ξi和ξ^i重写为 习题
下面关于支持向量机的说法错误的是 A、支持向量机基本型是一个凸二次规划问题 B、将训练样本分开的超平面仅由支持向量决定 C、支持向量机的核心思想是最大化间隔 D、以上选项存在说法错误的 解析D下面关于支持向量机对偶问题的说法错误的是 A、对偶问题需要满足KKT条件 B、通过对偶问题推导出的模型表达式能够体现解的稀疏性 C、在推导对偶问题时引入的拉格朗日乘子没有约束条件 D、对偶问题的最优值是原始问题最优值的下界 解析CD下面关于SMO算法说法正确的是 A、是一个迭代更新的算法 B、先选取KKT条件违背程度最大的变量 C、当变量固定后原始问题具有闭式解 D、以上说法都是正确的 解析D在求解支持向量机截距项的时候错误的说法是 A、通过任意支持向量都能够求解出截距项 B、为了提高鲁棒性通常使用所有支持向量求解的平均值 C、通过任意样本都能够求解出截距项 D、截距项的求解能够体现支持向量机学习到的超平面仅与少量支持向量有关在统计学习中归纳偏好项通过相关的项确定。 A、结构风险 B、经验风险 C、结构风险与经验风险 D、以上答案都不对 解析A
神经网络
神经网络是由具有适应性的简单单元组成的广泛并行互连的网络它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。当我们在机器学习中谈论神经网络时指的是“神经网络学习”或者说是机器学习和神经网络这两个学科领域的交叉部分。
神经网络模型
神经网络中最基本的成分是神经元(neuron)模型即上述定义中的“简单单元”。在生物神经网络中每个神经元和其他神经元相连当它“兴奋” 时就会向相连的神经元发送化学物质从而改变这些神经元内的电位若某神经元的电位超过了一个“阈值”threshold那么它就会被激活即“兴奋”起来向其他神经元发送化学物质。 将上述情形抽象出的简单模型就是一直沿用至今的“M-P神经元模型”。在这个模型中神经元接收到来自n个其他神经元传递过来的输入信号这些输入信号通过带权重的连接connection进行传递神经元接收到的总输入值将与神经元的阈值进行比较然后通过“激活函数”activation function处理以产生神经元的输出。激活函数也称响应函数 理想的激活函数是阶跃函数它把输入值映射为输出值“0”或“1”其中“0”对应于神经元抑制“1”对应于神经元兴奋。但是阶跃函数具有不连续、不光滑等不太好的性质因此实际常用Sigmoid函数作为激活函数。典型的Sigmoid函数如下图所示它把可能在较大范围内变化的输入值挤压到01输出值范围内因此有时也称为“挤压函数”squashing function 把多个这样的神经元按一定的层次结构连接起来就得到了神经网络。只需将一个神经网络视为包含了许多参数的数学模型这个模型是若干个相互嵌套代入而得。 感知机Perceptron由两层神经元组成如下图 输入层接收外界输入信号后传递给输出层输出层是M-P神经元也称“阈值逻辑单元”threshold logic unit。 更一般地给定训练数据集权重wii1,2,…n以及阈值θ可通过学习得到。阈值θ可视为一个固定输入为-1.0的“哑结点”dummy node所对应的连接权重wn1这样权重和阈值的学习可统一为权重的学习。感知机的学习规则非常简单对训练样例(xy若当前感知机的输出为 y ^ \widehat{y} y ,则感知机权重将这样调整 其中η∈01称为学习率learning rate。从上式可看出若感知机对训练样例x,y预测正确即 y ^ \widehat{y} y y则感知机不发生变化否则将根据错误的程度进行权重调整。 需要注意的是感知机只有输出层神经元进行激活函数处理即只拥有一层功能神经元functional neuron其学习能力非常有限。 若两类模式是线性可分的即存在一个线性超平面能够将它们分开。 “非线性可分”意味着用线性超平面无法划分。 要解决非线性可分问题需考虑使用多层功能神经元。例如下图中这个简单的两层感知机就能解决异或问题与、或、非问题是线性可分的异或问题是非线性可分的。输出层和输入层之间的一层神经元被称为隐层或隐含层hidden layer隐含层和输出层神经元都是拥有激活函数的功能神经元。 更一般地常见的神经网络是形如下图的层级结构每层神经元和下一层神经元全互连神经元之间不存在同层连接也不存在跨层连接。这样的神经网络结构通常称为“多层前馈神经网络”multi-layer feedforward neural networks“前馈”并不意味着信号不能向后传而是指网络拓扑结构上不存在环或回路,其中输入层神经元接受外界输入隐层和输出层神经元对信号进行加工最终结果由输出层神经元输出换言之输入层神经元仅是接受输入不进行函数处理隐层和输出层包含功能神经元。则下图a通常称为“两层网络”为避免歧义本书称其为“单隐层网络”。只需包含隐层即可称为多层网络。神经网络的学习过程就是根据训练数据来调整神经元之间的“连接权”connection weight以及每个功能神经元之间的阈值换言之神经网络“学”到的东西蕴含在连接权和阈值中。
万有逼近能力 万有逼近性并非神经网络独有例如傅里叶变换泰勒展示等也具有。 强调神经网络具有万有逼近性是为了说明解是可以找到的我们要做的是去逼近。
BP算法推导
误差逆传播error BackPropagation,简称BP算法是迄今最成功的神经网络学习算法。现实任务中使用神经网络时大多在使用BP算法进行训练。BP算法不仅可用于多层前馈神经网络还可用于其他类型的神经网络例如训练递归神经网络。但通常说“BP网络”时一般是指用BP算法训练的多层前馈神经网络。 缓解过拟合 习题
神经网络模型的两个最重要的要素是什么 A、网络结构、激活函数 B、网络结构、神经元模型 C、激活函数、学习算法 D、学习算法、神经元模型 解析B下列哪个模型不具备万有逼近性 A、线性模型 B、泰勒展开 C、傅里叶变换 D、决策树 解析A多层前馈网络具有的强大表示能力称为神经网络的____性 (4个字)。 解析万有逼近下列关于BP算法的描述哪个是错误的 A、BP算法适用于平方损失等许多常用损失函数 B、BP算法是迄今最成功、最常用的神经网络算法 C、BP算法的正式完整描述最早出现在1974年Werbos的博士学位论文中 D、BP算法只能用于回归任务 解析DBP算法的每一轮采用的是什么学习规则 A、广义感知机学习规则 B、广义最小二乘学习规则 C、广义决策树学习规则 D、广义支持向量机学习规则 解析A以下哪种情况下停止训练以缓解过拟合 A、训练误差降低、验证误差降低 B、训练误差降低、验证误差升高 C、训练误差升高、验证误差降低 D、训练误差升高、验证误差升高 解析B在误差目标函数中增加连接权平方和这一项后训练过程将偏好比较____(大/小)的 连接权。 解析小下列关于BP算法使用小步长优化神经网络的说法中正确的是哪个 A、一定能学到最优解 B、可以较好的避免振荡现象 C、训练速度快 D、学得的解比使用大步长具有更小的泛化误差 解析B多层前馈神经网络可以视为线性函数与激活函数的复合而单隐层前馈神经网络中这种复合的次数有限因而单隐层前馈神经网络的万有逼近性对激活函数有一定要求。你认为使用下列哪个激活函数的单隐层前馈神经网络能具有万有逼近性质 A、双曲正切函数 B、常值函数 C、线性函数 D、三次函数 解析A下列哪个选项的步长调整方法是给出的四种方案中最好的 A、先使用较大的步长后使用较小的步长 B、先使用较小的步长后使用较大的步长 C、一直使用较大的步长 D、一直使用较小的步长 解析A学习率即每次迭代的步长下列关于万有逼近描述正确的是哪个选项 A、万有逼近是神经网络独有的性质 B、神经网络的万有逼近性表明可以很容易的找到一个很好的解 C、具有万有逼近性是将神经网络作为机器学习模型的前提 D、神经网络的万有逼近性可以指导我们设置隐层神经元数 解析C具有10个隐层结点的单隐层网络在处理输入维度为6维的三分类任务时 (有3个输出层结点)网络中共有____ (填写一个整数) 个参数。 解析103实际应用中常使用试错法来设置隐层神经元数当问题较复杂时通常使用较____(多/少) 隐层神经元。 解析多当神经网络参数寻优陷入局部极小时____(过/欠)拟合更有可能发生。 解析欠
贝叶斯分类器
贝叶斯决策论Bayesian decision theory是概率框架下实施决策的基本方法对分类任务来说在所有相关概率都已知的理想情况下贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。下面以多分类任务来解释其基本原理。
贝叶斯决策论
假设有N种可能的类别标记即y{c1c2,……,cn}λij是把一个标记为cj的样本误分类为ci所产生的损失。基于后验概率P(ci|x)可获得将样本x分类为ci所产生的期望损失expected loss即在样本x上的“条件风险”conditional risk 先验概率prior probability指根据以往经验和分析。在实验或采样前就可以得到的概率。 后验概率posterior probability指某件事已经发生想要计算这件事发生的原因是由某个因素引起的概率。 我们的任务是寻找一个判定准则h以最小化总体风险。显然对每个样本x若h能最小化条件风险则总体风险也将被最小化这就产生了贝叶斯判定准则Bayes decision rule为最小化总体风险只需在每个样本上选择那个能使条件风险最小的类别标记即 称h*为贝叶斯最优分类器Bayes optimal classifier与之对应的总体风险R(h*)称为贝叶斯风险Bayes risk。1 - R( h*)反映了分类器所能达到的最好性能即通过机器学习所能产生的模型精度的理论上限。 若损失函数取0-1损失有
生成式和判别式模型
想要使用贝叶斯判定准则来最小化决策风险首先要获得后验概率P(c|x)但是在现实任务种这通常难以直接获得。从该角度来看 机器学习要实现的是基于有限的训练样本集尽可能准确地估计出后验概率P(c|x)。主要有两种策略
“判别式模型”discriminative models给定x可通过直接建模P(c|x)来预测c。之前学习的决策树、BP神经网络、支持向量机都可归入判别式模型的范畴。生成式模型generative models先联合概率分布P(x,c)建模再由此获得P(c|x)
贝叶斯分类器和贝叶斯学习
贝叶斯分类器 ! 贝叶斯学习
贝叶斯分类器 属于频率主义流派统计学习属于频率主义θ是确定存在的直接估计出来θ 贝叶斯学习 属于贝叶斯主义想要先把θ背后的分布找出来再找出来θ本身所谓的为了分类借助把世界本原找出来作为中间问题
极大似然估计
极大似然估计Maximum Likelihood Estimation简称MLE是一种根据数据采样来估计概率分布的经典方法。常用的策略是先假定总体具有某种确定的概率分布再基于训练样本对概率分布的参数进行估计。运用到类条件概率px | c 中假设px | c 服从一个参数为θ的分布问题就变为根据已知的训练样本来估计θ。极大似然法的核心思想就是估计出的参数使得已知样本出现的概率最大即使得训练数据的似然最大。
求最大似然估计参数步骤 1.写出似然函数2.对似然函数取对数并整理3.求导数令偏导数为0得到似然方程组4.解似然方程组得到所有参数即为所求。 需注意的是这种参数化的方法虽能使类条件概率估计变得相对简单但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。在现实应用中想要做出能较好地接近潜在真实分布的假设往往需在一定程度上利用关于应用任务本身的经验知识否则仅凭“猜测”来假设概率分布形式很可能产生误导性的结果。
朴素贝叶斯分类器
基于贝叶斯公式来估计后验概率P(c|x)的主要困难在于类条件概率P(c|x)是所有属性上的联合概率难以从有限的训练样本直接估计而得。为了避免这个问题朴素贝叶斯分类器naive Bayes classifier采用了“属性条件独立性假设”attribute conditional independence assumption对已知类别假设所有属性相互独立。换言之假设每个属性独立地对分类结果发生影响。则类条件概率P(c|x)可改写为 拉普拉斯修正
相比原始贝叶斯分类器朴素贝叶斯分类器基于单个的属性计算类条件概率更加容易操作需要注意的是若某个属性值在训练集中和某个类别没有一起出现过这样会抹掉其它的属性信息因为该样本的类条件概率被计算为0。因此在估计概率值时常常用进行平滑smoothing处理拉普拉斯修正Laplacian correction就是其中的一种经典方法具体计算方法如下 当训练集越大时拉普拉斯修正引入的影响越来越小。对于贝叶斯分类器模型的训练就是参数估计因此可以事先将所有的概率储存好当有新样本需要判定时直接查表计算即可。
习题
极大似然中若直接连乘易造成什么现象 A、下溢 B、上溢 C、内存不足 D、计算开销大 解析A用取对数解决极大似然估计____需要/不需要假设某种概率分布形式 解析需要拉普拉斯修正实质上假设了属性值与类别服从什么先验分布 A、均匀分布 B、二项分布 C、泊松分布 D、正态分布 解析A贝叶斯最优分类器____达到了/没达到了贝叶斯风险。 解析达到了下列说法错误的是 A、极大似然估计做了独立同分布假设 B、极大似然估计的任务是利用训练集估计参数 C、极大似然估计需先假设某种概率分布形式 D、极大似然估计属于贝叶斯主义 解析D考虑二分类问题若数据集中有100个样本其中负类样本有48个。令 c 表示正类则 P© 的估计值是____保留2位小数 解析0.52最小化分类错误率的贝叶斯最优分类器为对每个样本选择能使以下哪个选项最大的类别标记 A、后验概率 B、类条件概率 C、先验 D、以上都不是 解析A拉普拉斯修正适用于 A、朴素贝叶斯分类器 B、半朴素贝叶斯分类器 C、贝叶斯网 D、以上答案都对 解析D在训练样本的数量一定的情况下与朴素贝叶斯分类器相比半朴素贝叶斯分类器对拉普拉斯修正的需求更____(大/小)。 解析大
集成学习和聚类
集成学习ensemble learning通过构建并结合多个学习器来完成学习任务有时也被称为多分类器系统multi-classifier system、基于委员会的学习committee-based learning等。
集成学习
集成学习的一般结构为先产生一组“个体学习器”individual learner再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生例如C4.5决策树算法、BP神经网络算法等此时集成中只包含同种类型的个体学习器例如“决策树集成”中全是决策树“神经网络集成”中全是神经网络这样的集成是“同质”的homogeneous。同质集成中的个体学习器也称为“基学习器”base learner相应的学习算法称为“基学习算法”base learning algorithm。集成也可包含不同类型的个体学习器例如同时包含决策树和神经网络这样的集成是“异质”的heterogenous。异质集成的个体学习器由不同的学习算法生成就不再有基学习算法相应的个体学习器一般不称为基学习器而称为“组件学习器”component learner或直接称为个体学习器。 集成学习通过将多个学习器进行结合常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”weak learner尤为明显则集成学习的很多理论研究都是针对弱学习器弱学习器指泛化性能稍微优于随即猜测的学习器。例如在二分类问题上精度略高于50%的分类器进行的而基学习器有时也直接称为弱学习器但需注意的是虽然从理论上来说使用弱学习器集成足以获得很好的性能但在实践中出于种种考虑例如希望使用较少的个体学习器或是重用关于常见学习器的一些经验等人们往往会使用比较强的学习器。 好而不同
集成学习把多个学习器结合起来如何能获得比最好的单一学习器更好的性能呢考虑一个简单的例子在二分类任务中假定三个分类器在三个测试样本上的表现如下图所示其中对号表示分类正确❌表示分类错误集成学习的结果通过投票法voting产生即“少数服从多数”。这个例子体现出要获得好的集成个体学习器应“好而不同”即个体学习器要有一定的“准确性”即学习器不能太坏且要有“多样性”diversity即学习器间要有差异。 考虑二分类的简单情形假设基分类器之间相互独立能提供较高的差异度且错误率相等为 ε则可以将集成器的预测看做一个伯努利实验易知当所有基分类器中不足一半预测正确的情况下集成器预测错误所以集成器的错误率可以计算为 此时集成器错误率随着基分类器的个数的增加呈指数下降但前提是基分类器之间相互独立在实际情形中显然是不可能的假设训练有A和B两个分类器对于某个测试样本显然满足PA1 | B1 PA1因为A和B为了解决相同的问题而训练因此在预测新样本时存在着很大的联系。因此个体学习器的“准确性”和“差异性”本身就是一对矛盾的变量准确性高意味着牺牲多样性所以产生“好而不同”的个体学习器正是集成学习研究的核心。现阶段有三种主流的集成学习方法Boosting、Bagging以及随机森林Random Forest接下来将进行逐一介绍。
两类常用的集成学习方法
根据个体学习器的生成方式目前的集成学习方法大致可分为两大类 个体学习器间存在强依赖关系、必须串行生成的序列化方法。代表有Boosting个体学习器间不存在强依赖关系、可同时生成的并行化方法。代表有Bagging和随机森林Random Forest
Boosting
Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似先从初始训练集训练出一个基学习器再根据基学习器的表现对训练样本进行调整使得先前基学习器做错的训练样本在后续受到更多关注然后基于调整后的样本分布来训练下一个基学习器如此重复进行直到基学习器数目达到事先指定的值T最终把这个T个基学习器进行加权结合。 换言之Boosting是一种串行的工作机制即个体学习器的训练存在依赖关系必须一步一步序列化进行。其基本思想是增加前一个基学习器在训练训练过程中预测错误样本的权重使得后续基学习器更加关注这些打标错误的训练样本尽可能纠正这些错误一直向下串行直至产生需要的T个基学习器Boosting最终对这T个学习器进行加权结合产生学习器委员会。 Boosting族算法最著名的代表是AdaBoost因此下面主要是对AdaBoost算法进行介绍。AdaBoost使用的是指数损失函数因此AdaBoost的权值与样本分布的更新都是围绕着最小化指数损失函数进行的。看到这里回想一下之前的机器学习算法不难发现机器学习的大部分带参模型只是改变了最优化目标中的损失函数如果是Square loss那就是最小二乘了如果是Hinge Loss那就是著名的SVM了如果是log-Loss那就是Logistic Regression了。 AdaBoost算法的指数损失函数定义为 具体说来整个Adaboost 迭代算法分为3步 初始化训练数据的权值分布。如果有N个样本则每一个训练样本最开始时都被赋予相同的权值1/N。训练弱分类器。具体训练过程中如果某个样本点已经被准确地分类那么在构造下一个训练集中它的权值就被降低相反如果某个样本点没有被准确地分类那么它的权值就得到提高。然后权值更新过的样本集被用于训练下一个分类器整个训练过程如此迭代地进行下去。将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后加大分类误差率小的弱分类器的权重使其在最终的分类函数中起着较大的决定作用而降低分类误差率大的弱分类器的权重使其在最终的分类函数中起着较小的决定作用。
可以看出AdaBoost的核心步骤就是计算基学习器权重和样本权重分布那为何是上述的计算公式呢这就涉及到了我们之前为什么说大部分带参机器学习算法只是改变了损失函数就是因为大部分模型的参数都是通过最优化损失函数可能还加个规则项而计算梯度下降坐标下降等得到这里正是通过最优化指数损失函数从而得到这两个参数的计算公式具体的推导过程此处不进行展开。
Boosting算法要求基学习器能对特定分布的数据进行学习即每次都更新样本分布权重这里书上提到了两种方法“重赋权法”re-weighting和“重采样法”re-sampling 重赋权法 : 对每个样本附加一个权重这时涉及到样本属性与标签的计算都需要乘上一个权值。 重采样法 : 对于一些无法接受带权样本的及学习算法适合用“重采样法”进行处理。方法大致过程是根据各个样本的权重对训练数据进行重采样初始时样本权重一样每个样本被采样到的概率一致每次从N个原始的训练样本中按照权重有放回采样N个样本作为训练集然后计算训练集错误率然后调整权重重复采样集成多个基学习器。 从偏差-方差分解来看Boosting算法主要关注于降低偏差每轮的迭代都关注于训练过程中预测错误的样本将弱学习提升为强学习器。从AdaBoost的算法流程来看标准的AdaBoost只适用于二分类问题。
Bagging和随机森林
Bagging是并行式集成学习方法基于自助采样法bootsrtap sampling。所谓“并行”即基学习器的训练之间没有前后顺序可以同时进行Bagging使用“有放回”采样的方式选取训练集对于包含m个样本的训练集进行m次有放回的随机采样操作从而得到m个样本的采样集这样训练集中有接近36.8%的样本没有被采到。按照相同的方式重复进行我们就可以采集到T个包含m个样本的数据集从而训练出T个基学习器最终对这T个基学习器的输出进行结合。 算法流程 可以看出Bagging主要通过样本的扰动来增加基学习器之间的多样性因此Bagging的基学习器应为那些对训练集十分敏感的不稳定学习算法例如神经网络与决策树等。从偏差-方差分解来看Bagging算法主要关注于降低方差即通过多次重复训练提高稳定性。不同于AdaBoost的是Bagging可以十分简单地移植到多分类、回归等问题。总的说起来则是AdaBoost关注于降低偏差而Bagging关注于降低方差。 随机森林Random Forest 简称RF是Bagging的一个扩展变体。RF在已决策树为基学习器构建Bagging集成的基础上进一步在决策树的训练过程中引入了随机属性选择。具体而言传统决策树在选择划分属性时是在当前节点的属性集合假设有d个属性中选择一个最有属性而在RF中 对基决策树的每个结点先从该节点的属性集合中随机选择一个包含k个属性的子集再从这个子集中选择一个最优属性用于划分。此处的参数k控制了随机性的引入程度一般推荐值klog2d。 换言之它的基学习器固定为决策树多棵树也就组成了森林而“随机”则在于选择划分属性的随机随机森林在训练基学习器时也采用有放回采样的方式添加样本扰动同时它还引入了一种属性扰动即在基决策树的训练过程中在选择划分属性时RF先从候选属性集中随机挑选出一个包含K个属性的子集再从这个子集中选择最优划分属性。 这样随机森林中基学习器的多样性不仅来自样本扰动还来自属性扰动从而进一步提升了基学习器之间的差异度。相比决策树的Bagging集成随机森林的起始性能较差由于属性扰动基决策树的准确度有所下降但随着基学习器数目的增多随机森林往往会收敛到更低的泛化误差。同时不同于Bagging中决策树从所有属性集中选择最优划分属性随机森林只在属性集的一个子集中选择划分属性因此训练效率更高。
多样性度量
在集成学习中基学习器之间的多样性是影响集成器泛化性能的重要因素。因此增加多样性对于集成学习研究十分重要一般的思路是在学习过程中引入随机性常见的做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。
数据样本扰动即利用具有差异的数据集来训练不同的基学习器。例如有放回自助采样法但此类做法只对那些不稳定学习算法十分有效例如决策树和神经网络等训练集的稍微改变能导致学习器的显著变动。输入属性扰动即随机选取原空间的一个子空间来训练基学习器。例如随机森林从初始属性集中抽取子集再基于每个子集来训练基学习器。但若训练集只包含少量属性则不宜使用属性扰动。输出表示扰动此类做法可对训练样本的类标稍作变动或对基学习器的输出进行转化。 算法参数扰动通过随机设置不同的参数例如神经网络中随机初始化权重与随机设置隐含层节点数。 多样性的定义是集成学习中的圣杯问题
聚类
在“无监督学习”unsupervised learning中训练样本的标记信息是未知的目标是通过对无标记训练样本的学习来揭示数据的内在性质和规律为进一步的数据分析提供基础。
监督无监督分类聚类回归密度估计
无监督学习任务中研究最多、应用最广的的“聚类”clustering.聚类则是试图将数据集的样本划分为若干个互不相交的类簇从而每个簇对应一个潜在的类别。 聚类直观上来说是将相似的样本聚在一起从而形成一个类簇cluster。那首先的问题是如何来度量相似性similarity measure呢这便是距离度量在生活中我们说差别小则相似对应到多维样本每个样本可以对应于高维空间中的一个数据点若它们的距离相近我们便可以称它们相似。那接着如何来评价聚类结果的好坏呢这便是性能度量性能度量为评价聚类结果的好坏提供了一系列有效性指标。
距离计算 我们知道属性分为两种连续属性和离散属性有限个取值。对于连续值的属性一般都可以被学习器所用有时会根据具体的情形作相应的预处理例如归一化等而对于离散值的属性需要作下面进一步的处理若属性值之间存在序关系则可以将其转化为连续值例如身高属性“高”“中等”“矮”可转化为{1, 0.5, 0}。 若属性值之间不存在序关系则通常将其转化为向量的形式例如性别属性“男”“女”可转化为{1,00,1}。
在进行距离度量时易知连续属性和存在序关系的离散属性都可以直接参与计算因为它们都可以反映一种程度我们称其为“有序属性”而对于不存在序关系的离散属性我们称其为“无序属性”显然无序属性再使用闵可夫斯基距离就行不通了。
对于无序属性我们一般采用VDM进行距离的计算例如对于离散属性的两个取值a和b定义 于是在计算两个样本之间的距离时我们可以将闵可夫斯基距离和VDM混合在一起进行计算 若我们定义的距离计算方法是用来度量相似性例如下面将要讨论的聚类问题即距离越小相似性越大反之距离越大相似性越小。这时距离的度量方法并不一定需要满足前面所说的四个基本性质这样的方法称为非度量距离non-metric distance。 聚类方法概述 习题
下列关于Boosting算法中样本权重调整的说法中错误的是哪个 A、所有样本的权重和保持不变 B、前一个基学习器分错的样本会获得更大的权重 C、只要权重调整的方向正确Boosting算法的性能就可以获得理论保证 D、决策树可以直接处理带权重的样本 解析CBoosting是一种____ (同质/异质) 集成学习方法。 解析同质下列关于Bagging算法描述中错误的是哪个 A、Bagging算法中每个基学习器使用相同的数据集 B、分类任务中使用投票法获得输出 C、回归任务中使用平均法获得输出 D、Random Forest是具有代表性的Bagging算法 解析A下列关于误差-分歧分解的说法中正确的是哪个 A、这一分解表明特定条件下集成学习的性能与个体学习器多样性正相关 B、这一分解体现了多样性在回归、分类等机器学习任务中的重要性 C、这一分解给出了一种可操作的多样性定义 D、这一分解中的误差可以使用训练误差进行估计 解析A随机森林与传统决策树构成的森林相比多样性往往____(更高/相同/更低)。 解析更高
