机器学习 课件全套 张旭东 第1-18讲 -概述、统计基础 -深度生成模型-3

机器学习

MachineLearning

第一讲：导论

1.课程的主要目的机器学习已经成为一种解决诸多问题的有效工具，是多学科交叉的领域，应用面广泛；考虑工科类学生的知识基础，以面向解决实际应用为目标，开设一门将经典方法和深度学习平衡的“机器学习”课程。为学生掌握机器学习的本质和算法，以解决实际问题和为开展与本方向相关的研究打下基础。机器学习、深度学习和人工智能的关系（取自Chat-GPT的问答）机器学习、深度学习和人工智能是密切相关的三个概念。人工智能是一个更广泛的概念，它涵盖了所有能够模拟人类智能的技术和应用。而机器学习和深度学习都是实现人工智能的具体手段。机器学习是指通过让计算机从数据中学习规律和模式，来实现对未知数据的预测或分类。它是一种基于数据驱动的方法，通过提取数据中的特征，构建数学模型，让计算机自动发现数据中的规律和模式，并用于分类、预测等任务。深度学习是机器学习的一种分支，它使用多层神经网络来学习数据中的特征和模式。与传统机器学习算法相比，深度学习算法可以更好地处理大规模和高维度的数据，并且可以自动进行特征提取和选择。人工智能可以包括机器学习和深度学习在内，而机器学习和深度学习则是实现人工智能的重要手段。

2.本课程的主要内容课时要求：周3学时，研究生/本科生贯通课程，秋季学期，48（实际45）学时课程内容机器学习的基本知识（9学时）（基本概念、统计基础、回归学习、分类学习的基本算法，机器学习理论简介）核方法和支持向量机（4学时）决策树和集成学习（5学时）神经网络+深度学习（结构与算法）（10学时）无监督学习（聚类、EM算法、降维和隐变量学习）（4学时）强化学习+深度强化学习（9学时）深度生成模型（4学时）本课程内容的平衡性深度学习很重要，尤其几种商业化应用：计算机视觉、语音识别、自然语言处理、推荐系统等，既有大数据支持，又可以通过大规模计算系统进行训练（学习），取得许多重要进展。但并不是所有应用都有必要使用深度学习，许多问题用传统机器学习已可以取得很好的结果；目前神经网络的第三次复兴（以前有两次衰落过程），但并不能证明深度学习就是智能技术的终极方法，其他方法的延申或新方法仍有可能取得突破；作为机器学习的基础课程，选择在几种主要机器学习方法（包括深度学习作为一种重要方法）之间平衡。

课本教材：张旭东《机器学习》清华大学出版社，2024（14-5人工智能系列）C.M.Bishop,PatternRecognitionandMachineLearning,Springer,2006C.M.Bishop,H.Bishop,DeepLearning:FoundationsandConcepts,Springer,2024K.P.Murphy,ProbabilisticMachineLearning:AnIntroduction,MITPress,2022T.Hastie,etalTheElementsofStatisticalLearning,Springer,2009I.J.Goodfellow,Y.Bengio,etal,DeepLearning.2017R.Sutton,G.Barto,ReinforcementLearning,secondedition,2018MehryarMphriet.al.FoundationofMachineLearning,SecondEdition，MITPress,2018周志华《机器学习》清华大学出版社，2016李航《机器学习方法》，清华大学出版社，2022

参考书扩充阅读（超出技术层面）M.Minsky,TheSocietyofMind，心智社会，机械出版社，2018YannLeCun，QuandLaMachineApprend，杨立昆，科学之路-人、机器与未来，中信出版集团，2021机器学习的重要会议和刊物InternationalConferenceonMachineLearning,ICMLNeuralInformationProcessingSystem,NeurIPS其他（专业性）：COLT，ICLR，IJCAI、AAAI、

ICCV、CVPR、SIGIR、ICASSP、等等TheJournalofMachineLearningResearchMachineLearningNeuralComputationIEEETrans.OnNeuralNetworksandLearningSystemIEEETrans.OnPatternAnalysisandMachineIntelligencehttps///(在ML领域预发表网站影响很大）考核（清华课程的考核）作业：习题+仿真实验报告考试成绩：作业与课程报告（为主）结合预先要求：要求python编程能力，若没有python编程基础，请自学。助教有一个关于编程和project的指导性讲座（线上进行）3.机器学习(ML)的参考定义对于某类任务T和性能度量P，一个计算机程序被认为可以从经验E中学习是指，通过经验E的改进后，它在任务T上由性能度量P所衡量的性能有所提高。(Mitchell,1997)机器学习是指通过让计算机从数据中学习规律和模式，来实现对未知数据的预测或分类。它是一种基于数据驱动的方法，通过提取数据中的特征，构建数学模型，让计算机自动发现数据中的规律和模式，并用于分类、预测等任务。（ChatGPT）ML的主要类型

（一种分类方式：任务）监督学习（Supervisedlearning）无监督学习（Unsupervisedlearning）弱监督学习半监督学习增强（或称强化）学习（Reinforcementlearning）自监督学习自监督学习4.监督学习（Supervisedlearning）数据集（标注集）分类(Classification)回归(Regression)SupervisedLearningorPredictive分类(Classification)问题例子垃圾邮件检测（spamemailornon-spamemail,C=2）手写数字识别(C>2)回归(Regression)问题例子股票、房价、人口等建模和预测通信信道建模和预测一个房价预测例（2个自变量，1个输出变量）单变量回归问题的图示：线性和多项式5.无监督学习（Unsupervisedlearning）Descriptive：todiscover“interestingstructure”inthedata。(knowledgediscovery)examplesofunsupervisedlearningDiscoveringclustersdensityestimationDiscoveringlatentfactorsdimensionalityreduction，PCAICA聚类的一个实例6.强化学习（Reinforcementlearning）Reinforcementlearningproblemsinvolvelearningwhattodo—howtomapsituationstoactions—soastomaximizeanumericalrewardsignal.7.构建机器学习算法：基本元素特定的数据集（从数据学习）评价函数/目标函数（误差函数/风险函数/收益）模型（不同类型、层次的各种模型：参数模型、非参数模型/线性模型、非线性模型/决策树、神经网络、深度神经网络。。。。）优化过程、优化算法7.1数据集示例：手写数字识别MNIST数据集美国国家标准与技术研究所发布60000个训练集图像及其标注10000个测试集图像及其标注28*28像素的手写数字图像CIFAR-10数据集CIFAR-10是一个包含60000张图片的数据集。其中每张照片为32*32的彩色照片，每个像素点包括RGB三个数值，数值范围0~255。所有照片分属10个不同的类别，分别是'airplane','automobile','bird','cat','deer','dog','frog','horse','ship','truck'其中五万张图片被划分为训练集，剩下的一万张图片属于测试集。CIFAR-10数据集示例7.2目标函数风险函数和经验风险函数表示数据的生成分布每个样本的损失函数风险函数经验风险函数（训练集代价函数）表示训练集的经验分布或N表示训练集的样本数目ML的训练和泛化由于实际中未知，ML的训练是以经验风险最小替代风险最小。经验风险最小若推知风险最小，称为泛化能力强。实际中，经验风险优化可能带来过拟合问题，使得泛化性能差。经验风险结合正则化等技术进行优化，可提升泛化能力。7.3模型、优化不同类型、层次的各种模型参数模型和非参数模型线性模型、非线性模型逻辑回归、决策树、SVM、神经网络、深度神经网络优化算法（一般是相对独立的模块）7.4机器学习的一些基本术语训练集、测试集训练误差、测试误差欠拟合（Under-fitting）过拟合（Over-fitting）泛化性能（Generalization）正则化（Regularization）8.一个回归综合例子：多项式曲线拟合PolynomialCurveFitting

参数方法样本集为选择平方误差和作为评价函数Sum-of-SquaresErrorFunction0thOrderPolynomial欠拟合1stOrderPolynomial欠拟合3rdOrderPolynomial9thOrderPolynomial过拟合不同阶的训练误差和测试误差（注意Over-fitting情况）Root-Mean-Square(RMS)Error:PolynomialCoefficients增加训练数据集规模降低过拟合DataSetSize:9thOrderPolynomial增加训练数据集规模降低过拟合DataSetSize:9thOrderPolynomial正则化（Regularization）保持训练集规模条件下的降低过拟合方法Penalizelargecoefficientvalues这是正则化约束的一种例子一种正则化对应一种“偏爱”选择，“权范数平方”对应的是偏爱范数小的权向量。Regularization:9thOrderPolynomialRegularization:Regularization:vs.PolynomialCoefficients9.一个分类例子：KNNK-nearestneighbors：KNN

三种类型，K=10MAP准则，分类区间如下图C=1，红C=2，绿C=3，蓝非参数化方法本例的分类边界KNN算法简述对于给定样本，其取类c的概率是K个近邻训练样本集合分类器输出（MAP）KNN算法讨论对于这个例子，若设K=1，则训练集分类误差为0，但分类边界复杂，泛化性能差（overfit）；取K=10，则分类边界更光滑，但训练集分类误差不为0.K的选择是一个重要问题。在训练集误差和泛化性之间平衡。10.维数灾难

（Thecurseofdimensionality）

划分一维空间，需要K格，D维空间，需要CurseofDimensionality

一些方法非常敏感于维数灾难，例如KNN，多项式模型一些模型和方法可更易适应于维数增加。11.深度学习（DeepLearning）起始约2006年，神经网络（NeuralNetwork：NN）方法的第三次复兴（热点2012年）；主要结构MLP，CNN，RNN等是传统NN和ML中已存在的；新结构：GAN、Transformer等。DL主要依靠大规模训练数据、大型计算集群、和改进的优化方法和专门的训练方法。尽管目前是最活跃的分支，但深度学习是机器学习的一种。目的之一是改善传统ML的泛化能力。深度学习是机器学习的一种经典方法机器学习深度学习之间关联数据集的增长规模大的数据集是解决问题的一个方法，很多应用没有大的数据集怎么办？深度学习系统神经元增长趋势规模增长是解决问题的一个方法，所有问题都能靠规模增长解决吗？12.一些应用领域图像分类和识别、计算机视觉语音识别自然语言处理推荐系统网络搜索引擎通信信道建模通信、雷达等的信号分类和识别智能机器人无人驾驶汽车无人机自主导航各种专业领域的特殊应用，等等13.机器学习的简短历史图灵：1950年发表“计算机器和智能”（ComputingMachineryandIntelligence)，图灵测试、机器学习、遗传算法、强化学习；1956年夏天达特茅斯会议（J.McCarthy,M.Minsky,C.Shannon,N.Rochester)McCullon-Pitts神经元（1943）；Minsky于1951年开发第一个硬件神经网；F.Rosenblatt（1957）提出感知机，Widrow（1960）提出Adaline（LMS，随机梯度）1980年夏，卡内基-梅隆大学第一届机器学习研讨会1980-90年代，神经网络复兴，BP算法1990年代-2000年代，统计学习成为主流，SVM、核方法、图模型决策树、集成学习等2006年—至今，神经网络再次复兴，深度学习强化学习（RL）也一直持续进展，80年代TD算法，Q学习，直到近期DRL（核心思想MDP，POMDP）本章思考题什么是机器学习？（或怎样理解机器学习？）机器学习的类型？构造机器学习系统的基本元素？模型的类型（参数模型、非参数模型等）怎样理解深度学习。几个主要名词（过拟合、泛化、正则性等）模型的参数和超参数？超参数的作用，怎样确定超参数。机器学习

MachineLearning

第二讲机器学习的统计与优化基础概率基础、概率函数举例、最大似然、贝叶斯方法、决策理论、信息理论概述、优化基础（注意：课本第2、3两章合并在一起概要讲述）1.概率复习-概率的基本关系边际概率公式（和公式）全概率公式（积公式）贝叶斯公式

随机变量的基本特征均值（1阶特征）方差（2阶特征）随机向量特征均值向量自相关矩阵自协方差矩阵2.函数期望的逼近（蒙特卡罗方法），通过对该PDF采样产生一组独立样本PDF逼近为的期望为：

函数表示数据的生成分布表示每个样本的损失函数风险函数是函数期望例如：则原理上经验风险是风险函数的蒙特卡洛逼近表示训练集的经验分布3概率函数举例二元分布和二项分布多元分布和多项分布高斯分布和混合高斯分布指数分布

3.1二元变量（BinaryVariables）Coinflipping:heads=1,tails=0BernoulliDistribution二项式分布Ncoinflips:BinomialDistribution3.2多元变量（MultinomialVariables）1-of-Kcodingscheme:

多项分布（TheMultinomialDistribution）

TheDirichletDistributionConjugatepriorforthemultinomialdistribution.3.3TheGaussianDistribution高斯分布的划分PartitionedGaussianDistributions划分的条件和边际分布PartitionedConditionalsandMarginals条件分布边际分布PartitionedConditionalsandMarginals

3.4MixturesofGaussiansOldFaithfuldatasetSingleGaussianMixtureoftwoGaussiansMixturesofGaussians(2)Combinesimplemodels

intoacomplexmodel:ComponentMixingcoefficientK=3

MixturesofGaussians

3.5指数族

TheExponentialFamilyWhereisthenaturalparameterandsog()canbeinterpretedasanormalizationcoefficient.指数族的一般性前面的高斯、二元、二项式、多元、多项式等分布均是指数分布的特例。指数分布的进一步讨论参考Bishop，Chp2.4.最大似然准则似然函数（LikelihoodFunction）：概率密度函数中的固定，由变化的函数，则称为似然函数，可表示似然函数为最大似然准则：（MaximumLikelihood）若存在IID样本似然函数为对数似然函数为（更常用）参数解为ML续最大似然=负对数似然最小化例1.二元分布参数的最大似然估计设有IID数据集：则联合分布对数似然函数ML解为例2.高斯向量概率密度的参数估计

概率密度函数样本集

是I.I.D的似然函数为对数似然函数为例2.（续）均值向量和自协方差矩阵的MLE例3.模型参数估计的例子

考虑只有两个样本点的简单例子样本集为I.I.D

设回归模型

设模型与标注存在逼近误差（高斯分布误差）

例3（续）由于样本集是I.I.D的，故可简化为

可解

5.贝叶斯（Bayesian）框架由联合分布得到后验分布(posteriordistribution)其中待学习参数的先验分布(Pirordistribution)贝叶斯点估计：MAP估计等价形式对数形式若存在IID样本MAP参数解为样本集下的MAP估计小样本集时，先验分布起到较明显作用但随样本集趋于很大时，先验分布作用减小渐近被忽略思考题：将ML的数值例子推广到MAP以均方误差作为消耗函数的贝叶斯参数学习后验期望方法在ML中，可以讨论更一般的全贝叶斯学习框架例1.简单说明贝叶斯参数学习

由例1（续），因此上式两边取对数，并求最大值点，得

例1（续）：另一方面，随N增加后验概率的变化Example:forN=0,1,2and10.高斯分布贝叶斯参数估计：一般向量情况假设样本集则可证明参数贝叶斯估计为：和参数后验概率为：6.决策论（DecisionTheory）一般机器学习中（统计框架下），首先完成模型学习，对于概率模型，给出新输入，需要进行决策推断（

Inferencestep）确定后验（条件）概率或联合概率、决策（Decisionstep）给定x,决定最优分类或回归结果

t.在有监督机器学习中，相对讲推断（Inference）是困难的，决策（decision）是相对简单的工作。决策是推断完成后的一步工作，学习过程主要完成推断过程二类情况，最小错分类率准则MinimumMisclassificationRate误分类概率由则分类准则：多类情况？分类的决策MinimumExpectedLossExample:classifymedicalimagesas‘cancer’or‘normal’DecisionTruth若发生错误的代价不同，可利用加权矩阵对不同错误判决加权定义：把分类为的损失（风险）

MinimumExpectedLoss总的期望损失总风险（条件损失）分类为的风险为使总风险为最小，对于给定，分类为的准则为使最小

MinimumExpectedLoss

二类情况的例子分类为的准则是即满足若取：分类准则简化为

MinimumExpectedLoss二类情况的例子（续）用先验分布和类条件分布替代后验分布，得到由：得：分类为的准则是称为似然比准则

拒绝判决选择在后验概率均小于预定门限时，拒绝判决。回归的决策定义损失函数为误差平方期望损失为由：得到：前提：已得到回归决策的示意图如果是高斯分布则回归输出：为什么分开推断与决策过程风险最小化需求(不同情况下损失加权矩阵可变化)拒绝判决可选择不平衡的类先验概率下的权衡多模型的组合注：目前多数情况下，推断和决策分为两步，（采用概率统计方法）也有一些方法是直接导出决策结果的。（采用非概率统计方法）不同模型比较：生成模型VS鉴别模型

（GenerativevsDiscriminative）1.Generativeapproach: Model UseBayes’theorem2.Discriminativeapproach: Modeldirectly3.DiscriminativeFunction直接得到等号左右哪种形式都等价比较1.信息最全，训练复杂性最高；2.适中；3.简单，丢失概率信息，例如：无法做Rejectoption和组合模型等

7.熵（Entropy）Importantquantityincodingtheorystatisticalphysicsmachinelearning

DifferentialEntropyPutbinsofwidth

alongthereallineDifferentialentropymaximized(forfixed)wheninwhichcase

条件熵（ConditionalEntropy）离散情况下条件熵的更有直观意义的表示KL散度TheKullback-LeiblerDivergence（1）用q逼近p，当q=p时，KL散度最小（2）当有N个样本，学习参数时，

最小KL散度等价于最大似然

互信息（MutualInformation）互信息的一个作用是判断x和y是否独立？或逼近独立。

8.非参数方法

NonparametricMethods在概率模型估计中，首先假设一种数学形式表示的概率（密度）函数，例如高斯分布、混合高斯分布等，通过样本估计表征该概率函数的参数。但这种预先假设的模型是否成立，在实际中可能无法保证。非参数方法（non-parametricmethod）没有预先假设，可处理任意概率分布非参数方法估计概率

设观测取自概率分布p(x)并考虑包含x的小区域R，则样本数N充分大，若有K个样本落在区域R，则概率P近似为如果区域R的体积

V充分小,区域内p(x)近似常数，则概率P两个P相等，故

核密度估计核密度估计:固定V,从数据中估计K.设区域R是围绕x的超立方体，定义核(Parzenwindow)

K可数为如下，因此PDF估计为

核密度估计为避免不连续，可采用光滑窗函数，例如高斯窗任意核函数需满足核函数的尺度影响估计性能.hactsasasmoother.K近邻密度估计固定K，估计体积V，是的围绕x的超球体包含K个样本。为包含K个样本的体积，故K近邻不是一个好的密度估计方法，但可以构成学习模型。Kactsasasmoother.K-近邻分类器GivenadatasetwithNkdatapointsfromclassCkand,wehaveandcorrespondinglySince,Bayes’theoremgivesK-Nearest-NeighboursforClassificationK=1K=3K近邻回归样本集

K近邻样本集合为

9.优化技术概述最小化的数学形式描述为定义函数梯度最优解的基本条件：最优点上梯度为0最基本的迭代算法：梯度下降算法给出一个初始猜测值

按下式重复迭代直到收敛注：最大化问题的梯度解为梯度上升算法

迭代步长参数调整算法收敛性凸函数与优化定义：凸函数

定理：

或当且仅当Hessian矩阵

是半正定的则该函数是凸的。优化问题：若目标函数是严格凸函数，优化问题可以保证得到全局最小值。

对于非凸的目标函数，优化问题的解要困难得多。机器学习

MachineLearning

第三讲：回归的基本学习算法1.线性回归模型特征向量（输入向量）扩充特征向量权系数向量则线性回归模型为线性回归模型（续）给出训练序列对于给出的损失函数最小化，得到回归参数对于给出的新特征向量，得到预测值2.扩充：线性基函数回归模型特点：对参数向量线性，对特征向量非线性对特征向量映射基函数：线性基函数模型：特例：线性回归是线性基函数回归的特例：基函数集的例子-1对应线性回归模型对应线性基函数回归模型3.基本线性回归模型的学习独立同分布条件（I.I.D）的训练数据集对每个样本，模型与标注之间存在误差

一维情况下，线性回归表示的例子通过最大似然原理导出线性回归的学习算法

的概率密度函数所有样本的标注值表示为向量由样本集的I.I.D性得似然函数取对数似然为对数似然函数最大，对应平方误差和最小ML导出线性回归的学习算法（续）重写误差平方和其中ML导出线性回归的学习算法（续）求解系数向量系数向量满足方程

（线性回归的最小二乘（LS）解）权系数向量得到后，线性回归函数确定为线性回归在训练集上的输出向量线性回归的几何解释线性回归对每一个标注值的逼近误差向量回归误差正交性4.线性回归模型的递推学习对数据集计算平均梯度从初始猜测值

按梯度下降算法更新随机梯度下降算法（stochasticgradientdescent，SGD）误差和可分解为一个样本的梯度利用一个样本梯度对权系数向量的更新梯度是随机的，每次迭代样本是随机选取的小批量SGD算法从数据集随机抽取一小批量样本小批量SGD算法如下一般收敛性条件5.正则化线性回归正则化：在目标函数中增加约束参数向量的量一种常用选择为参数向量的范数平方约束参数向量的正则化LS解为正则化目标函数与贝叶斯框架的等价性！更一般的正则化对更一般的q值，定义正则化目标函数LassoQuadratic注：贝叶斯框架下，一个q取值对应参数向量的一种不同的先验概率假设q=1，Lasso解趋向于稀疏化

更一般的正则化q<1:稀疏化q>1:非稀疏化6.线性基函数回归输入向量映射：线性基函数回归模型线性基函数回归系数向量的解为基函数数据矩阵为三维向量例子数值实例内在输入输出模型采样样本方式

基函数回归右图：不同参数的实验结果注意过拟合和正则化机器学习

MachineLearning

第四讲：分类的基本学习算法1.分类问题（Classification）数据集（标注集）分类(Classification)对于2类问题对于K(>2)类问题（K-to-1编码）基本分类问题表示分类的三种基本模型(1).判决函数模型线性模型由训练集学习参数（或用验证集确定超参数）广义线性模型（generalizedlinearmodels）为激活函数分类的三种基本模型（续）(2).判决（概率）模型由数据集直接训练后验概率，由决策论确定输出简写为表示数据集分类的三种基本模型（续）(3).生成（概率）模型首先得到和或：再由Bayes公式得可以求得，能够生成更多数据2.判决函数方法

（DiscriminantFunctions）线性分类（2类、多类），LS优化Fisher线性判决函数（2类、多类）（统计方法的传统技术）投影到低维空间，投影可分辨力最大化感知器算法（ThePerceptronAlgorithm）（MLP的最简化形式，曾起到重要作用）传统算法（略，祥见教材5.2节）3.逻辑回归（LogisticRegression）（概率判决模型）3.1二类问题定义：logisticssigmoid函数用logisticsigmoid表示类的后验概率logisticssigmoid函数的性质对权向量的线性系统其中本节直接采用基函数线性形式时取

二分类后验概率的表示另：由训练样本直接学习参数对于新的输入计算类后验概率并分类二分类逻辑回归参数学习训练样本集变换的样本集几个简写二分类逻辑回归参数学习（续）似然函数负对数似然函数：交叉熵准则二分类逻辑回归参数学习（续）目标函数对的梯度，可导出为SGD算法：单一样本对梯度的贡献为二分类逻辑回归参数学习（续）随机梯度算法学习参数学习率参数注：可按一定次序使用，甚至可循环使用直到收敛，也可用小批量平均梯度。二分类逻辑回归参数学习（续）IRLS算法*（IterativeReweightedLeastSquares)利用牛顿迭代思想，需要汉森矩阵HIRLS算法其中H正定，有唯一最优解NXM矩阵第n行IRLS算法这里N维向量这是一个R作为加权矩阵的加权LS，每次需重新计算R，重新运行LS，直到收敛。故名：IRLS。正则化逻辑回归（

RegularizedLogisticRegression）也可加更一般的正则化项，例如：q=1（或<1）对应稀疏逻辑回归。抗逻辑回归的overfitting！梯度向量SGD权更新公式为3.2多类逻辑回归Multiclasslogisticregression定义Softmax函数这里对每一类定义类后验概率对每一类定义和学习权向量多类逻辑回归MulticlasslogisticregressionSoftmax函数的性质这里多类逻辑回归参数学习训练样本集变换的样本集这里令：多类逻辑回归参数学习似然函数多类逻辑回归参数学习存在约束条件多类逻辑回归参数学习目标函数对各参数向量的梯度随机梯度对每一个参数向量，可分别应用随机梯度算法迭代例子：两类，分别用LS分类和逻辑回归绿线是逻辑回归紫线是LS的边界3.3例例子：右下角增加几个野点，LS分类明显变差，逻辑回归基本不变三类情况，即使是清晰可分的，LS分类也很差（右）此例中，逻辑回归分类比较理想若可通过数据集模型化：、类C1的后验概率可写为其中#（2）#（1）4.分类的生成模型

或4.1离散生成模型：NaïveBayes输入向量的每个分量取值离散，先假设取值（0，1），y对应二类分类假设例

离散生成模型：NaïveBayes用y=1表示C1，y=0表示C2用如下符号类条件概率4.2NaïveBayes学习样本集设类概率为NaïveBayes学习联合概率表示1NaïveBayes学习联合概率表示2NaïveBayes学习样本联合概率训练样本满足I.I.D，似然函数负对数似然NaïveBayes学习似然函数对各参数求导解得NaïveBayes学习似然函数解得NaïveBayes学习似然函数解得4.3NaïveBayes推断给出新输入，进行分类NaïveBayes分类第2类的后验类概率为可推广到输入各分量取值为M个值的情况NaïveBayes分类存在的一个问题若存在和则，无法做出判断希望不存在4.4拉普拉斯平滑克服零概率比值问题拉普拉斯平滑（Laplacesmoothing）设且定义有样本集标准ML估计：拉普拉斯平滑为拉普拉斯平滑参数估计NaïveBayes参数学习改进为机器学习

MachineLearning

第5讲：机器学习流程和性能评估1.机器学习基本流程1.1数据清洗和预处理数据清洗：缺失特征填补和异常数据剔除样本Z-得分为

判断为异常值。常用的方法是将其剔除归一化两种形式：取值范围归一化，概率分布归一化预处理取值归一化概率归一化1.2特征工程特征选择：过滤法；包装法；嵌入法特征提取：降维、变换域、特定特征抽取1.3训练集、测试集和验证超参数：模型阶（例：多项式拟合的阶M，KNN的参数K，正则项参数）。一般不能通过训练过程获得，而是需要通过验证过程确定。模型选择、超参数选择等泛化性能测试，在测试集误差逼近泛化误差。验证和测试情况一：独立的训练集和测试集，两个集合独立地产生自同一个数据生成分布，训练集训练模型，通过测试误差逼近泛化误差，这是理想情况。情况二：独立的训练集和测试集。将训练集分成两部分，一部分（例如80%），用于训练；另一部分（例如20%），用作确定超参数，并称为验证集（validationset），用该验证集确定超参数。超参数确定和训练获得模型参数后，再用测试集测试性能（逼近泛化误差）。测试集的几种构成和测试方法（续）情况三：交叉验证（crossvalidation(CV)）。数据集规模有限，将训练集分为K折（Kfolds），每次训练留出一折作为验证集，其余作为训练集，进行一次训练和验证，然后循环操作（见下页图）。取每次验证集的误差平均，作为验证误差。K=5的示例如下页图。情况四：K=N，每次只有一个样本作为验证集，称为留一验证（leave-oneoutcrossvalidation,orLOOCV）

。交叉验证示意2.机器学习系统的实际性能评价在样本集上进行实际性能评价回归的基本评估指标：均方误差分类的基本指标：分类错误率和分类准确率精度和查全率（针对二分类定义）样本集：300正类、9700负类该例子中，若将所有样本判为负例，则Acc=0.97一种比较总体优劣的方法是采用AUG参数，一个分类器AUG参数（AreaUnderROCCurve）表示为其ROC曲线之下和坐标横轴之间的面积3.机器学习模型的误差分解以回归模型作为讨论对象，考虑平方误差模型的误差期望（泛化误差）最优回归模型是误差分解模型的误差分解泛化误差由三部分组成：偏、方差和固有误差模型简单，方差小，偏大；模型复杂，方差大，偏小误差分解的数值实例例:25个数据集，在基函数回归下，变化正则化参数

.模型误差的方差和偏折中示例误差分解的数值实例例:25个数据集，在基函数回归下，变化正则化参数

.模型误差的方差和偏折中示例误差分解的数值实例例:25个数据集，在基函数回归下，变化正则化参数

.模型误差的方差和偏折中示例误差分解实例无法直接观测到，

采样过程为

采样数据构成I.I.D数据集

采用K近邻回归算法训练模型为（非参数模型，且

K越小对应模型越复杂）

该问题的统计最优模型为

直接求得误差分解为

第一项是偏，K越大模型越简单，偏越大；第二项是方差，K越大，模型越简单方差越小-注释

测试误差和泛化误差曲线呈现一种类似“U”曲线。对于传统的单一机器学习模型“U”曲线具有一般性；-但在深度学习中，当深度网络复杂度达到一定规模后，测试误差的表现更加复杂；-对于集成学习中一些方法，如随机森林和提升算法，测试误差一般也并没有呈现出“U”曲线，换言之，集成学习更不易出现过拟合问题。-机器学习是仍在快速发展中的领域，在发展中一些传统结论，可能被不断补充和修改。4.PAC，概率近似正确PAC：ProbablyApproximatelyCorrect。主要由Valiant（1984）等发展的一种理论，2010年获图灵奖，第一位机器学习领域的图灵奖得主。Vapnik和Chervonenkis提出VC维并研究了无限假设空间的计算理论。参考书：ShaiShalev-Shwartz&ShaiBen-David,UnderstandingMachineLearning:FromTheorytoAlgorithms.CambridgePress,2014.（中文版，张文生等，“理解机器学习”，机械工业出版社，2016）M.Mohri,etal.FoundationofMachineLearning,MITPress,2012,(中文版，张文生译，机器学习基础，机械出版社）4.1.一个引理设

是N个独立同分布的随机变量，均服从伯努利分布，且

定义样本均值为

为一个固定值，则

Hoeffding不等式4.2.二元分类问题训练集来自概率训练误差定义二元分类问题（续）泛化误差假设集是通过训练集按ERM得到最优假设使得泛化误差最小的假设实际中二元分类问题（续）假设集的例子ERM解转化为对如下参数的求解2分类假设4.3假设集为有限集合的界为有界集1.对一个任意，比较其训练误差和泛化误差关系取一个定义伯努利变量训练误差假设集为有限集合的界（续）利用引理的Hoeffding不等式，得用表示故：假设集为有限集合的界（续）故有假设集为有限集合的界（续）取得（#1）对于任意，以概率至少，满足

需要的样本集满足（#1），且有

误差界定理假设集为有限集合的界（续）2.经验误差最小假设和泛化误差最小假设的界经验误差最小假设泛化误差最小假设得到泛化误差假设集为有限集合的界（续）泛化误差界的基本定理假设集为有限集合的界（续）（样本复杂度的基本推论）4.4.假设集为无限集合的界VC维的定义

VC维的定义VC维的例子：二维线性分类器假设集为无限集合的界（续）无限集合的界受VC维控制假设集为无限集合的界（续）样本复杂度机器学习

MachineLearning

第6讲：核函数与SVM1.核函数由特征向量构造特征映射函数，即则核函数的一种定义是核函数满足对称性一个简单的核函数例子则核函数正定性设有样本集可定义则有矩阵这里称为Gram矩阵（核矩阵），是对称的半正定矩阵。例：可直接构造核函数，分解为特征映射函数的标量积形式两维的例子：构造：相当于则是合格的核函数直接构造并判断有效核函数对于任意样本集Mercer定理（默瑟定理）如下核矩阵是对称的半正定矩阵。设有函数如下定理说明其是否是核函数函数是核函数的充分和必要条件是利用简单核构造新核函数是有效核，如下构造核利用简单核构造新核函数简单核和构造核相当于是纯二阶函数相当于是不高于二阶的函数（见下页）一个核函数例子构造核高斯核由于故高斯核写为故高斯核确实是一个有效核2*

线性基函数回归的对偶表示和核表示正则化约束函数为对w求导为0，得这里上页中的将带入得到对偶目标函数定义和线性回归的对偶表示和核表示（续）对偶目标函数写成核形式对a求导为0，得回归问题解的核表示为线性回归的对偶表示和核表示（续2）3.预备：不等式约束的拉格朗日方法LagrangeMultipliers令：不等式约束的拉格朗日方法（续）最优解需解如下方程并满足如下KKT（Karush-Kuhn-Tucker）条件不等式约束的拉格朗日方法（续）对函数的最小化，约束条件不变则拉格朗日函数为则求解方程和KKT条件不变。对参数求L函数最大。可证明：以上最优问题的求解可分解为如下原解对偶最优解为是凸函数，是放射函数，且

则：对偶解与原解同解若有4.支持向量机SupportVectorMachine：SVM针对两类分类问题。线性分类函数分类输出训练集预备知识：点到决策超平面距离任意点到决策超平面（红线）的距离请练习证明此式！4.1可分情况的SVM（线性可分或特征空间可分）学习函数分类边界训练集可分性指：存在一个分类边界，满足如下对正样对负样对所有样本可分情况下，分界线不是唯一的，怎样的分界线具有最好泛化性右边的三条分界线均可正确分类训练集，哪个具有最好泛化性？感知机可能训练得到任何可能的分界线，受控于初始和样本次序1.对于可分情况，存在一个分类边界，可正确分类所有训练样本，这种分类器不是唯一的。可分情况的SVM（续1）2.一个更可信的分类器，使得样本点与边界距离尽可能远。3.对于任意样本，其与分类边界的距离为可分情况的SVM（续2）求一个分类边界，使样本离边界的最近距离（间隔）最大化，即（#1）可分情况的SVM（续3）定义函数距离设则函数距离改变c倍，距离不变。强加最近距离点的函数距离为1，即（#1）的优化问题难以求解。改变表示。（#2）可分情况的SVM（续4）则所有样本满足约束条件（#1）的优化问题变为（#3）（#4）可分情况的SVM（续5）组合并重写（#3）（#4）为约束优化问题。S.T.可分情况的SVM（续6）为解约束最优，构造拉格朗日函数如下拉格朗日乘数（#5）可分情况的SVM（续7）令：得：（#6）可分情况的SVM（续8）将（#6）带入（#5）得到对偶表示，最大化约束条件其中为核函数（#7）可分情况的SVM（续9）以上的优化问题，称为二次规划问题。可用二次规划标准算法实现，运算复杂度参数求得后，将（#6）中带入，得分类输出可分情况的SVM（续10）SVM优化结果分析解满足的KKT条件为由KKT条件3或相应样本对结果无贡献或离分类边界最近距离点，支持向量可分情况的SVM（续11）仅由支持向量表示输出分类表达式支持向量数量较少这是一种稀疏表示。可分情况的SVM（续12）设支持向量序号集合为对一个支持向量有，故得至此所有参数均求得。两边同时乘tn可分情况的SVM（续13）例子：取高斯核函数，则特征空间可分图中标出：分界线最小距离线（Margin边界）等值线支持向量4.2不可分情况的SVM对于不可分的一般情况，改进SVM方法引入松弛变量（SlackVariables）对于处于最小距离线（margin）上或正确一侧对于其他，则令对于处于分界线上的点，则（#1）不可分情况的SVM（续1）对于处于边界线和最小距离线之间的点对于处于边界线错误一侧不可分情况的SVM（续2）考虑松弛，将可分情况的约束推广到带松弛约束推广到如下约束最小化控制超参数（#2）（#3）不可分情况的正则化解释引入正则化项，允许部分样本不满足放松到满足则L1正则化的目标函数为最小化：不可分情况的正则化解释正则化方法除了对不可分有效，即使可分情况，也可避免为了适应野值样本，而使得分界线的泛化性能变差，如下右图有一个野值样本，为了保证野值样本分类正确，泛化性明显变差。不可分情况的SVM（续3）考虑（#3）的目标函数和（#1）（#2）约束拉格朗日函数为拉格朗日因子（#4）不可分情况的SVM（续4）KKT条件不可分情况的SVM（续5）令得（利用KKT条件第4行）不可分情况的SVM（续6）上页式带入拉格朗日公式，得到拉格朗日对偶问题，最大化下式S.T.盒约束注意：此处优化问题与可分情况的优化目标式相同，约束条件不同，解二次规划问题。不可分情况的SVM（续7）带入，得输出表达式与可分情况相同，即分类输出不可分情况的SVM（续8）不可分情况，SVM优化结果分析或相应样本对结果无贡献或由KKT条件若则故落在最小边界线的点则支持向量若则落在最小边界线外正确分类落在分界线外错误分类不可分情况的SVM（续9）确定，对于满足如下集合的点以上点集记为，支持向量集对故：4.3不可分SVM的另一种解释定义：合页损失函数（hingelossfunction）则有：SVM等价为正则化合页目标函数：损失函数的例子：合页、感知机、0-1一种变化的SVM：ν-SVM最大化S.T.

是超参数表示的点的比例5.多分类SVM（MulticlassSVM)SVM是本身针对2分类问题的，是一种决策方法多分类需要各种扩展方法。一种K类分类器：

one-versus-the-rest

用SVM分两类，K作为正样，其他K-1作为负类分类输出其他方法，各有一些利弊6.回归SVM（SVMsforRegression)为了获得稀疏表示，定义新的误差函数，取代误差平方和。ε-不敏误差函数ε-insensitiveerrorfunction正则化误差函数为（C为反正则化系数）(#1)ε-不敏误差函数与平方误差比较回归SVM（续1）对每一个点定义两个松弛变量和对应对应对应（#2）通过松弛变量，所有点满足下式回归SVM（续2）(#3)回归SVM（续3）由松弛变量的定义，（#1）目标函数改写为结合（#2）（#3）的约束，得拉格朗日函数为参数为（#4）回归SVM（续）计算各导数（#5）回归SVM（续4）将（#5）带入拉格朗日表达式，得到对偶表示，即最大化下式并有盒约束和（#6）回归SVM（续5）解以上二次规划问题，求得由的表达式，得回归的预测公式为回归SVM（续6）KKT条件，结合KKT条件可对回归SVM的结果做分析。回归SVM（续7）回归SVM结果分析必有处在的上边界上处在的上边界上侧必有为0，处在下边界上，>0处于下边界下侧或的点称为支持向量（两者不会同时非0）回归SVM（续8）求偏置参数b对于支持向量中一些点则故得：对的点也求得一个b，两者平均的结果更好一种变化的回归SVM：回归ν-SVM一种变化的回归SVM描述如下最大化：S.T.回归ν-SVM的例子蓝圈表示支持向量使用的是高斯核7.SVM的一个优化算法：SMOSequentialMinimaloptimization预备知识：坐标上升算法（CoordinateAscent：CA）最大化如下目标函数每次固定其他变量，只求对变量的优化，即该过程序列循环执行，直到收敛！示例CA两维情况下CA的示例CA优化算法，应用于SVM优化，即如下问题S.T.由于约束可改写为

SVM的一个优化算法：SMO（续1）故用CA算法对SVM优化，

一次至少优化两个系数，固定其他系数SVM的一个优化算法：SMO（续2）每次选两个系数，不失一般性，选由约束条件在算法中，由于其他系数假设是常数，故是常数带入目标函数SVM的一个优化算法：SMO（续3）注意，由于盒约束和约束方程，得SVM的一个优化算法：SMO（续4）综合考虑，得到解SVM的一个优化算法：SMO（续5）每次的一对优化变量的选取采用启发式，首先选择一个不满足KKT条件的点对应的系数再选择可能引起大的改变的系数组成一对，循环迭代，直到收敛。算法的细节描述参考[JohnPlatt,1999]SVM有SVMLight、LIBSVM等专用软件包，主要通用平台也支持SVMSVM的一点说明在SVM中，最容易应用的是线性SVM方法，

即核函数取2.在比较复杂的分类问题中，怎样选择好

的核函数，是一个没有解决的问题，人为

因素和启发式方法为主。3.大规模问题SVM的优化有若干研究，SMO

是其中之一。第7讲

决策树与集成学习

DecisionTreeand

EnsembleLearning决策树算法：ID3和C4.5分类和回归树：CARTBagging和随机森林提升、AdaBoost和提升树课本第7、8章合在一起讲授1.决策树决策树（decisiontree）是一种分层的决策结构，可用于分类和回归；决策树对于特征向量各分量混合属性的情形，尤其有效决策树模型具有树型结构，学习过程中由样本集形成一棵可做分层判决的树；推断（预测）时，对于一个新的特征向量，从树的根结点起分层判决，达到可给出最后结果的叶结点，完成一次推断；决策树推断速度快，可解释性强，是一种应用非常广泛的算法；以决策树为基础树，可直接形成随机森林或提升树（集成学习），得到更高的分类率或回归精度。决策树的一些术语根结点叶结点：可以得出结果的结点决策树的结构是分层的结构，由结点和边组成内部结点特征向量有若干特征可离散、连续在一个结点，特征取值决定边的分支样本集2.ID3算法和信息增益ID3算法基本思路：（每个特征取值离散）通过一个准则找到一个最合适的特征，以这个特征作为根结点；根结点对应了样本集的所有样本，确定一个特征作为根结点，由该特征的各取值形成相应的几条边，引出下一层的结点；每一条边对应了根结点特征的一个取值，根据该特征的不同取值把样本集分成几组，每一组形成一子样本集；子样本集的特征向量中，将根结点已用到的特征删去，每一个子样本集对应一条边下端的结点；满足条件的节点定为叶节点，并确定对应输出，否则递归执行。不纯性度量（impuritymeasure）ID3算法时用熵表示不纯性实际计算经验熵不纯性度量（续）不纯性度量（续）由特征的取值形成边，边的下端为下一层的结点ID3算法例：看电影样本集数据集的经验熵每个特征的增益最终的决策树一个新的输入：女友去、未完成、不需要、喜欢”最后的决策是“去看电影”。3.C4.5算法Quinian于1993年发表；ID3中用信息增益选择特征时偏向选择取值数多的特征，C4.5用信息增益率来选择特征，适用于特征之间取值数目比较分散的情况；针对ID3易于过拟合的问题，在树构造过程中引入剪枝技术；ID3的特征只能取离散值，若一个特征是连续数值量，则需要预先离散化，C4.5既可以处理离散特征，也可处理连续特征；能够处理样本特征不完整的情况。CART算法CART是分类与回归树的缩写：ClassificationAndRegressionTree:CART。由Breiman等1984年提出。CART的结构一般是一棵二叉树，每一个内部节点有两条分支CART用于分类，称为分类树；用于回归，称为回归树。4.1分类树考虑二叉树结构CART算法的不纯性度量：基尼指数基尼指数计算为若两类情况下，熵的一半与基尼指数的关系图基尼指数作为测试条件看电影的CART分类树4.2CART回归树回归树的不纯性函数使用平方误差回归树：在根结点需要选出一个特征和一个切分点，使得，并计算逼近误差回归树：回归树：回归树的一个数值实例一个更深回归树的实例5.决策树的一些扩展问题连续数值变量正则化和剪枝技术预剪枝技术后剪枝技术缺少属性的训练样本问题逻辑表达式和解释性6.集成学习-1：

Bagging和随机森林（RandomForests）在决策树基础上的集成学习方法:对样本进行随机采样，对采样样本生成决策树，多决策树组合。

Breiman20016.1自助采样和Bagging算法Bagging（bootstrapaggregation）算法(1)(2)(3)特点：6.2随机森林算法描述（RandomForests）通过进一步增加随机性：随机选取特征，提高有效性随机森林做预测对spam数据集，Bagging、随机森林和提升树性能比较性能比较7.集成学习-2：提升和AdaBoost算法提升（boosting）类算法，组合若干个弱学习器构成一个强学习器。（串行结构）AdaBoost由Freund和Schapiro于1995年提出AdaBoost算法AdaBoost算法的基本思想：（1）对基学习器进行多轮调用；（2）在每一轮调用时，都对样本集中每个样本在损失函数中的权重进行调整（3）初始时所有样本具有相等的权重，但在经过每一轮，被正确分类的样本给予较小权重，没有被正确分类的样本权重增加（4）难以正确分类的样本会持续获得高权重，使得后续基学习器重点关注和解决较难分类的样本。基本的AdaBoost算法用于2分类问题，以

表示两类

AdaBoost算法描述AdaBoost算法描述（续）AdaBoost算法的示例：三轮提升，得到对所有样本正确分类的集成分类器。图中分别用“+”和“-”表示样本的类型AdaBoost的泛化性能评价对于手写英文字母（OCR）数据集（16000训练样本，4000测试样本），使用C4.5决策树做基分类器利用AdaBoost集成方法，随提升数增加时训练误差和测试误差的变化曲线8.加法模型和提升树算法加法模型表示为定义目标函数

加法模型优化问题为模型分步更新前向一步优化问题简化为加法模型和提升树算法（续）基学习器

采用决策树，则构成提升树

一棵决策树的模型表示决策树的参数：，J是树深度

提升树模型表示为加法模型和提升树算法（续）第t轮决策树参数的确定为如下优化问题

实现示例-1：指数函数和AdaBoost

加法模型和提升树算法（续）实现示例-2：平方误差函数-回归提升树对于回归问题，取参数优化问题为定义残差：第t轮决策树，目标函数以残差替代标注值训练一棵决策树回归提升树算法引入了收缩参数！9.梯度提升树算法（gradientboostingdecisiontree,GBDT）在一般情况下，定义新的等价残差为负梯度引入收缩参数

对于一系列损失函数，引入梯度提升决策树算法并应用于回归和分类决策树和集成学习小结决策树简单、可解释性强，但性能不高集成学习可有效提升单学习器的性能以决策树为基本学习器构成随机森林，是一种高效、并行性强的集成算法AdaBoost是一种有效的串行分类提升算法提升树尤其梯度提升树（GBDT）构成一类广泛的集成算法GBDT的增强版，XGBoost或LightGBM等可在性能或有效性方面进一步提升（可参考其网络社区）。机器学习

MachineLearning

第8讲：神经网络与深度学习-INeuralNetworkandDeepLearning1.1神经元结构

激活值

神经元的输出1.多层感知机（前馈神经网络）激活函数例子

1.2前馈神经网络Feed-ForwardNeuralNetworkMultilayerPerceptron：MLP以一个三层网络为例：二个隐藏层几个名词：激活（activations)激活函数（activationfunction）输入、输出、隐藏单元

一个三层神经网络例子一个三层神经网络的表示第一层激活权系数偏置神经元输出第一层激活函数

第二层单元的激活第二层神经元的输出一个三层神经网络的表示（续）

第三层：输出层激活一个三层神经网络的表示（续）

输出端的每个输出记为

不同类型输出一般有不同的非线性输出函数神经网络的输出表示1.一般回归输出激活函数是直通函数

2.一个二分类任务的输出

3.一个K类分类器输出用softmax函数

一般多层感知机的运算关系输入定义为

神经网络的非线性映射两层回归网络可表示为

两层神经网络二分类输出三层神经网络二分类输出：深层嵌套神经网络的非线性映射（续）2.神经网络通用逼近定理逼近定理：对于紧支输入空间的任意连续函数，一个线性输出的两层神经网络，只要具有充分大的隐藏单元，则可以以任意精度逼近该函数。3.可以构成更多层数的更一般神经网络。可构成深度神经网络（DNN）。2.权空间对称性：对于M个隐藏单元的神经网络，其权空间的对称