机器学习及其Python实践 (4).pdf

机器学习及其Python实践第4章 统计学习理论与支持向量机第4章 统计学习理论与支持向量机 机器学习 任务T、损失函数L（性能度量P或学习策略R）、样本数据集D（历史经验）、学习算法A、模型（函数）、新样本 人的学习过程：归纳推理（从个别推及一般），学习知识；演绎推理（从一般推及个别），将知识应用于实际 机器学习中模型的训练过程也是一种归纳推理（从样本数据集到模型），使用模型对新样本进行预测则属于演绎推理（将模型应用于新样本）第4章 统计学习理论与支持向量机从样本数据集学习到的模型是否适用于总体分布上的所有样本呢？训练集上学习到的模型，其在总体分布上的性能表现被称为模型的泛化性能如果学习到的模型在总体分布上的性能与在训练集上的性能一致，则称学习过程具有一致性统计学习理论就是围绕泛化性能，研究学习过程一致性 充分必要条件 泛化误差的上界 影响泛化误差的因素 如何设计具有泛化能力的学习模型4.1 统计学习理论 数据集 学习问题与ERM归纳原则=1,1,2,2,()(,)，(,)=;4.1 统计学习理论 数据集 学习问题与ERM归纳原则=1,1,2,2,()(,)，(,)=;阚道宏4.1 统计学习理论 数据集 学习问题与ERM归纳原则 学习过程的一致性=1,1,2,2,()(,)，(,)=;4.1 统计学习理论 ERM归纳一致性的充要条件 学习理论的关键定理4.1 统计学习理论 ERM归纳一致性的充要条件 ERM归纳是否具有一致性，这与学习任务、模型假设有关 学习任务的概率分布()通常是未知的。如果概率分布()是已知的，那就没必要通过ERM归纳的方法来解决问题。例如分类问题，如果已知概率分布，那么直接使用贝叶斯分类器就可以了 统计学习理论通常不会关注某个具体的概率分布，而是针对任意的概率分布，并将研究目标聚焦到假设空间（即备选函数集合）上，主要是研究假设空间与ERM归纳一致性之间的关系4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维 机器学习模型的假设空间是一组预设的备选函数集合，通常包含有无穷多个备选函数 假设空间的复杂度与ERM归纳一致性有着密切关系。为此，统计学习理论提出了增长函数（growth function）与VC维（Vapnik-Chervonenkis dimension）的概念，用于度量假设空间的复杂度阚道宏4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维阚道宏4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维阚道宏4.1 统计学习理论 ERM归纳一致性的充要条件 增长函数与VC维mG(m)dVCG(m)=dVC(ln(m/dVC)+1)G(m)=mln24.1 统计学习理论 泛化误差上界与PAC可学习 机器学习不是追求没有泛化误差，而是要与经验误差一致，即学习过程具有一致性，这样才能保证通过样本数据学习到的模型具有普遍意义 既然有误差，那么误差的上界在哪里，即泛化后最大的误差会到什么程度？误差上界与哪些因素有关呢？对于机器学习来说，泛化误差的上界越小越好4.1 统计学习理论 泛化误差上界与PAC可学习 统计学习理论关于泛化误差上界的两个定理4.1 统计学习理论 泛化误差上界与PAC可学习 统计学习理论关于泛化误差上界的两个定理4.1 统计学习理论 泛化误差上界与PAC可学习 统计学习理论关于泛化误差上界的两个定理4.1 统计学习理论 泛化误差上界与PAC可学习 PAC可学习4.1 统计学习理论 两种机器学习的归纳原则 泛化误差上界与经验误差、假设空间的VC维成正比，与训练集的样本容量成反比的 这实际上给出了降低泛化误差上界的三个主要途径，对学习模型与学习算法的设计具有直接的指导意义 +.（4 20）4.1 统计学习理论 两种机器学习的归纳原则 经验风险最小化归纳原则降低经验误差 +.（4 20）给 定 训 练 集=1,1,2,2,、假 设 空 间 =;和损失函数 ;，经验风险最小化（即ERM）就是将训练集上经验误差（即经验风险）=1=1 ;.最小的函数;当作泛化误差 最小的函数，或者说是将训练集上经验误差 最小的模型参数当作泛化误差 最小的模型参数。阚道宏4.1 统计学习理论 两种机器学习的归纳原则 经验风险最小化归纳原则降低经验误差 +.（4 20）4.1 统计学习理论 两种机器学习的归纳原则 结构风险最小化归纳原则降低泛化误差 式4-20的另一个重要意义在于，可以通过调节假设空间复杂度，对经验误差和置信范围做适当的平衡或折中，最终让两者之和（即学习模型的泛化误差上界）最小 设计一个VC维为的备选函数集=;，使其具有一定的结构，这一结构是由一系列嵌套的函数子集组成的 +.（4 20）4.1 统计学习理论 两种机器学习的归纳原则 结构风险最小化归纳原则降低泛化误差 函数子集的VC维是有限的，并且1 2 .（4 22）1 2 .函数子集的损失函数是有界非负的实函数，即0 ;.dVC误差 HkH1 H置信范围经验误差泛化误差上界过拟合欠拟合=1,1,2,2,;4.1 统计学习理论 方差与偏差阚道宏4.1 统计学习理论 方差与偏差4.2 线性可分支持向量机 支持向量机（Support Vector Machine，缩写SVM）模型是在SRM归纳原则启发下所做的一个非常有创新意义的实践，其最初目的是为解决小样本情况下的二分类问题 给定二分类问题的训练集 SVM最基本的想法是基于训练集找到一个能将两类样本分开的超平面=1,1,2,2,其中是维样本特征，1,+1是其对应的类别标记（+1表示正例，1表示反例）阚道宏4.2 线性可分支持向量机 最优分类超平面与支持向量x1x2+-x1x2+-rTxi+b=1Txi+b=-1Tx+b=04.2 线性可分支持向量机 最优分类超平面与支持向量x1x2+-x1x2+-rTxi+b=1Txi+b=-1Tx+b=0 +.（4 20）4.2 线性可分支持向量机 最优分类超平面与支持向量4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 拉格朗日乘子法是一种求解约束条件下函数极值的方法 通过引入拉格朗日乘子，可将个变量与个约束条件的最优化问题转化成+个变量的无约束优化问题 SVM在求解最优分类超平面时就应用了该方法4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 二元函数的拉格朗日乘子法h(x*)f(x*)h(x)=0 x*f(x)=c3f(x)=c1f(x)=c2f(x*)g(x)=0 x*f(x)=c3f(x)=c1f(x)=c2g(x)0 x*x*阚道宏4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 二元函数的拉格朗日乘子法h(x*)f(x*)h(x)=0 x*f(x)=c3f(x)=c1f(x)=c2f(x*)g(x)=0 x*f(x)=c3f(x)=c1f(x)=c2g(x)0 x*x*min2 s.t.=0.（4 30）4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 二元函数的拉格朗日乘子法h(x*)f(x*)h(x)=0 x*f(x)=c3f(x)=c1f(x)=c2f(x*)g(x)=0 x*f(x)=c3f(x)=c1f(x)=c2g(x)0 x*x*阚道宏4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 二元函数的拉格朗日乘子法h(x*)f(x*)h(x)=0 x*f(x)=c3f(x)=c1f(x)=c2f(x*)g(x)=0 x*f(x)=c3f(x)=c1f(x)=c2g(x)0 x*x*4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 多元函数的拉格朗日乘子法min s.t.=0，=1,2,.s.t.0，=1,2,.（4 36）4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 多元函数的拉格朗日乘子法 原问题与对偶问题阚道宏4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 多元函数的拉格朗日乘子法 原问题与对偶问题阚道宏4.2 线性可分支持向量机 拉格朗日乘子法与对偶问题 多元函数的拉格朗日乘子法 原问题与对偶问题阚道宏4.2 线性可分支持向量机 最优分类超平面求解算法min,122，s.t.+1，=1,2,.（4 29）阚道宏4.2 线性可分支持向量机 最优分类超平面求解算法min,122，s.t.+1，=1,2,.（4 29）4.2 线性可分支持向量机 最优分类超平面求解算法阚道宏4.2 线性可分支持向量机 最优分类超平面求解算法=1=11=12=1.（4 54）4.2 线性可分支持向量机 最优分类超平面求解算法min,122，s.t.+1，=1,2,.（4 29）=1,1,2,2,4.3 非线性可分的支持向量机4.2节讨论的SVM有一个前提条件，就是训练样本在特征空间是线性可分的，即存在超平面能将两个类的样本点完全划分开，但实际应用中经常会出现线性不可分的情况解决线性不可分问题有两种方法 一是对式4-27的硬间隔（hard margin）条件做适当放松，改用弹性的软间隔（soft margin）二是将特征映射到高维空间，使其在高维特征空间变成线性可分+1，对所有正例样本,，即=+1+1，对所有反例样本,，即=1.（4 27）4.3 非线性可分的支持向量机 线性支持向量机+1，对所有正例样本,，=+1+1，对所有反例样本,，=1.+1，=1,2,.+1 ，0，=1,2,.（4 62）=1越小越好阚道宏4.3 非线性可分的支持向量机 线性支持向量机4.3 非线性可分的支持向量机 线性支持向量机4.3 非线性可分的支持向量机 线性支持向量机 软间隔SVM的几何意义 1号正例样本点 2号正例样本点 3号正例样本点 4号正例样本点x1x2+-1Tx+b=023421-21+=1支持向量：训练样本,所对应的拉格朗日乘子0 4.3 非线性可分的支持向量机 非线性支持向量机 对实际应用中出现的线性不可分情况，可以将特征映射到高维空间，使其在高维特征空间变成线性可分3=12+224.3 非线性可分的支持向量机 非线性支持向量机阚道宏4.3 非线性可分的支持向量机 非线性支持向量机,=2.4.3 非线性可分的支持向量机 引入核函数是一种将线性问题求解方法推广至非线性问题的常用手段 将线性SVM求解方法推广至非线性SVM 将线性的PCA降维方法推广至非线性的核PCA降维 但目前对于如何定义或选择核函数还缺乏理论指导，因此核函数还只是一种解决非线性问题的技巧，俗称为核技巧（kernel trick）4.4 SVM分类器及其Python实现 设计SVM分类器的过程4.4 SVM分类器及其Python实现 SMO算法 求解对偶问题 序列最小优化学习（SMO）算法最优拉格朗日乘子=1,2,min12=1=1 =1s.t.0 ，=1,2,=1=0.（4 65）阚道宏4.4 SVM分类器及其Python实现 设计SVM分类器的过程 Scikit-learn库中的SVM分类器模型 LinearSVC，线性SVM分类器 SVC，同时支持线性SVM和非线性SVM阚道宏4.4 SVM分类器及其Python实现 设计SVM分类器的过程 Scikit-learn库中的SVM分类器模型“digits dataset”手写数字数据集第4章 统计学习理论与支持向量机 本章学习要点 经验误差与泛化误差、ERM/SRM归纳原则、学习过程一致性及其充分必要条件、假设空间及其复杂度、增长函数与VC维、泛化误差的上界、影响泛化误差的因素、设计具有泛化能力的学习模型、PAC可学习、学习模型的方差与偏差、线性可分/线性/非线性支持向量机、拉格朗日乘子法与对偶问题、序列最小优化算法