(1.1.1.35)--统计机器学习概论人工智能导论.ppt

《(1.1.1.35)--统计机器学习概论人工智能导论.ppt》由会员分享，可在线阅读，更多相关《(1.1.1.35)--统计机器学习概论人工智能导论.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、视频编码与理解课程 (Video Coding and Content Understanding)统计机器学习概论(Introduction to Statistical Machine Learning)为什么需要机器学习？o美国航空航天局JPL实验室的科学家在Science（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得稳定而快速的发展oMachine learning forms the core of may present-day AI applicationsnGary Anthes,Future Watch:AI

2、comes of age,2009.1.2623为什么数字媒体技术中需要机器学习？媒体处理媒体类型单媒体复合媒体应用模式单机应用模式网络应用模式获取(创建)编 辑管 理 传 输检 索描 述展 现说 明编 码统计学习与模式识别4机器学习示例SARS RiskAgeGenderBlood PressureChest X-RayPre-Hospital AttributesAlbuminBlood pO2White CountRBC CountIn-Hospital Attributes5Books and Referenceso主要参考书nT.Hastie,R.Tibshirani,J.Fried

3、man,“The Elements of statistical Learning:Data Mining,Inference,and Prediction”,2001,Springer-Verlag.o其他参考书nV.N.Vapnik,“The Nature of Statistical Learning Theory”,2nd ed.,Springer,2000.6提 纲o机器学习方法概述o贝叶斯决策理论Bayesian Decision Theoryo常见统计学习方法o机器学习的难题与挑战o附录：n1、参考资料n2、代表性机器学习开发包介绍7一、统计学习方法概述8机器学习的发展o机器学习

4、=神经科学与认知科学+数学+计算平凡解问题James(19世纪末)：神经元相互连接McCulloch,Pitts(20世纪中期):“兴奋”和“抑制”Hebb(20世纪中期):学习律神经科学Barlow：功能单细胞假设Hebb：神经集合体假设Rosenblatt：感知机（1956）Rumelhart：BP（1986）PAC(Valiant 1984)Schapire：弱学习定理（1990）Freund：AdaBoost（1996）线性不可分问题（Minsky 1969）Vapnik：SVM（1991）有限样本统计理论线性空间表示？i.i.d问题一致性假设30年Widrow：Madline（196

5、0）Samuel：符号机器学习机器学习研究历程王珏,机器学习研究回顾与趋势,2004.9学习系统的一般模型System Input Variables:Hidden Variables:Output Variables:11机器学习的基本问题和方法o机器学习n根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。o机器学习问题的表示n根据n个独立同分布观测样本确定预测函数f(x,w)。n在一组函数f(x,w)中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小。Simon的学习模型12学习问题的一般表示o学习目标nGiven an

6、i.i.d.l-sample z1,zl drawn from a fixed distribution F(z)nFor a function class loss functions Q(z,),with in nWe wish to minimizetherisk,finding a function*nIn the case of equal risk,it becomes to minimize the error ratio.o相关概念n损失函数 loss function(L,Q)：the error of a given function on a given examplen

7、风险函数risk functional(R)：the expected loss of a given function on an example drawn from F(x,y)13学习问题的一般表示o学习的目的在于使期望风险最小化。由于可利用的信息只有样本，期望风险往往无法计算。o经验风险最小化归纳原则(The Empirical Risk Minimization(ERM)Inductive Principle)n核心思想：用样本定义经验风险。nDefine the empirical risk(sample/training error):nDefine the empirical

8、 risk minimizer:nLeast-squares and Maximum-likelihood are realisations of ERM14ERM准则与统计学习理论的发展o经验风险最小并不意谓着期望风险最小!n例子：神经网络的过学习问题。n训练误差小并不总能导致好的预测效果.若对有限的样本来说学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测.o需要建立在小样本情况下有效的学习方法n小样本条件下的统计学习理论n支持向量机(SVM)Why Learning is Difficult?oGiven a finite

9、amount of training data,you have to derive a relation for an infinite domainoIn fact,there is an infinite number of such relationso.the hidden test points.15Learning as a Search Problem1617三类基本的机器学习问题(1)o模式分类问题：输出y是类别标号，两类情况下y=1,-1，预测函数称作指示函数(Indicator Function)，损失函数定义见下式，使期望风险最小就是Bayes决策中使错误率最小。18三

10、类基本的机器学习问题(2)o回归问题：输出y是连续变量，它是x的函数，损失函数定义见下式:19三类基本的机器学习问题(3)o概率密度估计问题：根据训练样本确定x的概率分布p(x,w)，则损失函数可定义为:20统计学习的基本方法o有监督/无监督学习n有监督(Supervised)：分类、回归n无监督(Unsupervised)：概率密度估计、聚类、降维n半监督(Semi-supervised)：EM、Co-trainingo其他学习方法n增强学习(Reinforcement Learning)n多任务学习(Multi-task learning)21有监督学习o标定的训练数据o训练过程：根据目标

11、输出与实际输出的误差信号来调节参数o典型方法n全局：BN,NN,SVM,Decision Treen局部：KNN、CBR(Case-base reasoning)S(x)=0 Class AS(x)1?nBoosting：结合低性能学习模型来产生一个强大的分类器组nBagging：结合多个不稳定学习模型来产生稳定预测n主动学习(Active learning)：主动选择训练样本BoostingoBoosting 是个非常强大的学习方法,它组合许多“弱”分类器来产生一个强大的分类器组。n弱分类器：性能只比随机选择好一点，设计简单且计算花费低。n最常用的弱分类器是决策树。o常见的Boosting算

12、法n离散AdaBoost,实数AdaBoost,LogitBoost和Gentle AdaBoostn它们有非常类似的总体结构。27Boostingo两类问题的算法：训练(step 13)和估计(step 4)n为每一个样本初始化使它们具有相同的权值(step 2),然后一个弱分类器f(x)在具有权值的训练数据上进行训练,计算错误率和换算系数cm(step 3b),被错分的样本的权重会增加,所有的权重进行归一化,并继续寻找若其他分类器M-1次,最后得到的分类器F(x)是这些独立的弱分类器组合的符号函数(step 4)。28Baggingp基本假设:nCombining many unstabl

13、e predictors to produce a ensemble(stable)predictor.nUnstable Predictor:训练数据的微小变化可能使得预测模型产生大的改变p不稳定模型：Neural Nets,treesp稳定模型：SVM,KNN.oEach predictor in ensemble is created by taking a bootstrap sample of the data.n引导样本：obtained by drawing N example at random,with replacement.oEncourages predictors t

14、o have uncorrelated errors.Unlabeled Data Set主动学习Intermediate SetClustering(K clusters)(Diversity Criterion)BatchSelect centroid of each cluster(Representativeness Criterion)Select M most informative examples(Informativeness Criterion)(1)(2)(3)产生式模型 vs 判别式模型oGenerative models:n建模(联合)概率分布：n利用Bayes th

15、eoremn典型方法：BN、HMM、CMFn问题的可解释性好oDiscriminative models:n直接用函数（而非概率）来建模n典型方法：SVM、LDAn一般来说，性能更好32二、贝叶斯决策理论33Bayes决策理论有什么用？o用不同方法可能得到多个不同的估计，哪个估计更好一些？n统计决策理论：比较统计过程的形式化理论o决策n是从样本空间S，到决策空间的一个映射，表示为D:S n评价决策有多种标准，对于同一个问题，采用不同的标准会得到不同意义下“最优”的决策。oBayes决策常用的准则n最小错误率准则n最小风险准则n最小条件错误率准则：在限定一类错误率条件下使另一类错误率为最小n最小

16、最大决策准则：Minimizing the maximum possible loss(or Maximizing the minimum gain)Linear Decision Boundaryx1x2x3hyperplanex1x2Non-linear Decision Boundaryx1x2x1x2x336问题描述：Classification Problemo给定：m个类，训练样本和未知数据o目标：给每个输入数据标记一个类属性o两个阶段：n建模/学习：基于训练样本学习分类规则.n分类/测试：对输入数据应用分类规则P(f1)f1鹅卵石救命稻草杆Pebbles Strawspebble

17、sStrawsf1f2决策边界37最大后验(Maximum A Posterior,MAP)分类o什么是最优分类器?o已有:类条件概率密度函数nThis is called the class-conditional probability describing the probability of occurrence of the features on category.o欲求:后验概率nmake a decision that maximize the conditional probability of the object,given certain feature measure

18、ments.nAlso called posterior probability function.p(x|1)p(x|2)类条件概率密度函数p(1|x)后验概率p(2|x)38Bayes最小错误率(MAP)决策oMAP决策:n以后验概率为判决函数:nChoose category/class that has the maximumnThis produces the optimal performance:minimum probability of error:oA classifier that achieves this optimal performance is called B

19、ayesian classifier.39MAP决策的错误率oBayes决策是一致最优决策。n使得每个观测值下的条件错误率最小因而保证了（平均）错误率最小。40MAP决策的扩展：最小Bayesian风险o决策的风险：n做决策要考虑决策可能引起的损失。n以医生根据白细胞浓度判断一个人是否患血液病为例：p没病(1)被判为有病(2)，还可以做进一步检查，损失不大；p有病(2)被判为无病(1)，损失严重。oDecision Risk tablenThe risk to make a decision :classify x(belong to class i)to class j,so:oDecisi

20、on Rule:41Bayes决策：讨论o基于Bayes决策的最优分类器oBayes决策的三个前提：n类别数确定n各类的先验概率P(Ci)已知n各类的条件概率密度函数p(x|Ci)已知o问题的转换：n基于样本估计P(Ci)和p(x|Ci)n基于样本直接确定判别函数学习问题42三、主要统计学习方法简介43统计学习方法o决策树o统计推理n用数据的似然度(likelihood)和假设(Hypothesis)的概率去预测新实例的值n朴素Bayes方法(Nave Bayes,NB)o基于实例的学习n最近邻方法(Nearest Neighbor)o神经网络(Neural Networks)o支持向量机(S

21、upport Vector Machine)o典型聚类方法：K-Means3.1 Decision TreesAt each step,choose the feature that“reduces entropy”most.Work towards“node purity”.All the dataf1f2Choose f2Choose f1Decision TreesCART(Breiman,1984)C4.5(Quinlan,1993)J48 463.2 Bayesian学习o基本思想n给定训练数据 ,计算每个假设 的概率n利用此概率来进行预测（注：预测时利用所有的假设，而不仅仅利用最好

22、的一个）o参数估计问题n若训练数据独立同分布(i.e.,i.i.d)，则n对分类问题，需要估计两个参数：类的先验概率P(Ci)和类条件概率密度p(x|Ci)对分类问题，假设hi可直接视为类属性Ci47Bayesian学习:参数估计的方法o类的先验概率P(Ci)的估计：n用训练数据中各类出现的频率估计n依靠经验o类条件概率密度p(x|Ci)估计的两种主要方法：n参数估计：概率密度函数的形式已知，而表征函数的参数未知，通过训练数据来估计p最大似然估计pBayes估计（最大后验估计）n非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计pKN-近邻法pParzen窗法48简

23、化模型：简单贝叶斯Nave Bayeso简单贝叶斯学习模型（NB）n将训练实例表示成属性(特征)向量A和决策类别变量C。n假定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作用于决策变量。n降低了学习的复杂性n在许多领域，表现出相当的健壮性和高效性oNB的特点n结构简单只有两层结构n推理复杂性与网络节点个数呈线性关系Ca1a2an-1an49NB用于分类oNB假设：设样本A表示成属性向量，如果属性ak对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积：o简单贝叶斯分类(SBC:Simple Bayesian Classifier)n一般认为，只有在独立性假定成立的

24、时候，SBC才能获得精度最优的分类效率；或者在属性相关性较小的情况下，能获得近似最优的分类效果。50扩展：贝叶斯网(Bayes Network)=P(A)P(S)P(T|A)P(L|S)P(B|S)P(C|T,L)P(D|T,L,B)P(A,S,T,L,B,C,D)条件独立性假设有效的表示CPT:T L B D=0 D=10 0 0 0.1 0.90 0 1 0.7 0.30 1 0 0.8 0.20 1 1 0.9 0.1 .Lung CancerSmokingChest X-rayBronchitisDyspnoeaTuberculosisVisit to AsiaP(D|T,L,B)P(

25、B|S)P(S)P(C|T,L)P(L|S)P(A)P(T|A)贝叶斯网络是表示变量间概率依赖关系的有向无环图513.3基于实例的学习Instance-basedoBayeis方法的缺陷n参数估计误差o不描述概率分布，而直接描述决策规则，如最近邻规则：n直接从训练数据构造假设nK近邻方法K-NNn最近邻方法NN:K=152K-NN方法o对输入样本 x,从训练样本中找到与x距离最近的K个最近样本，以它们最可能的类标签来分类xxk=1k=653K-NN的性能o亚优：在训练样本足够的情况下，错误概率小于最优错误率的两倍.nWhere:is the probability of error for B

26、ayesian inference(Optimal)and NN rule;o不能在有限的样本下获得同样的断言.54K-NN的关键问题o距离度量n最常用方法:euclideann更好的距离度量:normalize each variable by standard deviationn离散数据：Hamming distanceoK的选择nIncreasing k reduces variance,increases biaso高维空间的可区分性差nFor high-dimensional space,problem that the nearest neighbor may not be ve

27、ry close at all!o大数据量时计算开销大nMust make a pass through the data for each classification.This can be prohibitive for large data sets.nIndexing the data can help;for example KD trees55Euclidean DistanceoEuclidean Distance between x and pk is:oThe decision rule based on this metric is called theminimum E

28、uclidean Distance(MED)classifier.56Mahalanobis Distanceo用方差的倒数来进行加权，相当于使决策界从方差较大的一方朝方差较小一方移动:nLet the distribution be approximated by a multivariate normal density.The Mahalanobis distance from x to m is given by:nWhere is the covariance matrix and is the sample mean of the prototype.57胞体胞体(Soma)枝蔓（

29、枝蔓（Dendrite）胞体胞体(Soma)轴突（轴突（Axon）突触（突触（Synapse）人工神经元模拟生物神经元的一阶特性。n输入：X=(x1,x2,xn)n联接权：W=(w1,w2,wn)Tn网络输入：net=xiwin向量形式：net=XWn激活函数：fn网络输出：o=f(net)InputsignalSynapticweightsSummingfunctionActivationfunctionLocalFieldvOutputox1x2xnw2wnw1w0 x0=+14.4神经网络(NN)：模拟人脑的学习58x1x2xno1o2onwnmw11w1mw2mwn1输出层输入层典型网

30、络结构:简单单级网59输出层x1o1w11w1mx2o2w2mxnomwn1输入层V典型网络结构:单级横向反馈网60典型网络结构:多级网输出层隐藏层输入层o1o2omx1x2xn61典型网络结构:循环网x1o1输出层隐藏层输入层x2o2omxn3.5 支持向量机oSVM是一种基于统计学习理论的机器学习方法，是由Boser,Guyon,Vapnik于1992年提出，目前已经取得了广泛的成功应用。o统计学习理论的主要目标n专门研究小样本下的机器学习规律n追求现有信息条件下的最优结果（结构风险最小化）62Vapnik63结构风险最小化原则o实际风险由两部分组成：n经验风险(训练误差)nVC置信范围(

31、VC confidence)：学习机器的VC维及训练样本数有关。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)o结构风险最小化(SRM)的基本思想n在有限训练样本下，学习机器的VC维越高则置信范围越大,真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因。n机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。64结构风险最小化示意图65最优分类面o最优分类面n分类间隔(Margin).n分类间隔最大:实际上就是对推广能力的控制，这是SVM的核心思想之一.输入:S=(xi,yi)Rn -

32、1,1,对应于yi,xi 可表示为两类:xi H1,yi=-1 xi H2,yi=1目标:找到一个分类函数(x)=wx+b能够对训练数据 xi 正确分类,对其他的输入能够正确推广.进一步说:找到一个超平面 H :wx+b=0和两个与H平行且等距离的 H1:wx+b=1 H2:wx+b=-1数学模型66最优分类面-直观描述(a)小的分类间隔 (small margin)(b)大的分类间隔(larger margin).最优分类面就是要求分类面能将两类正确分开(训练错误率为0),且使分类间隔最大A-A+MalignantBenignA+A-67支持向量直观地说，支持向量是两类集合边界上的点。所有非

33、支持向量的数据都可以从训练数据集合中去掉而不影响问题解的结果。对于新的数据点 x,要对其进行分类只需要计算 f(x)=sign(w x+b)其中w 和b是支持向量对应的参数。68SVM的分类问题oSVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题线性可分问题近似线性可分问题线性不可分问题SVM LearningoFinding the Decision BoundaryoLet x1,.,xn be our data set and let yi 1,-1 be the class label of xioThe decision boundary should clas

34、sify all points correctly oThe decision boundary can be found by solving the following constrained optimization problem69The Dual ProblemoIt is known as the dual problem:if we know w,we know all ai;if we know all ai,we know woThe original problem is known as the primal problemoThe objective function

35、 of the dual problem needs to be maximized!oThe dual problem is therefore:Properties of i when we introduce the Lagrange multipliersThe result when we differentiate the original Lagrangian w.r.t.b70Extension to Non-linear Decision BoundaryoSo far,we have only considered large-margin classifier with

36、a linear decision boundaryoHow to generalize it to become nonlinear?oKey idea:transform xi to a higher dimensional space to“make life easier”nInput space:the space the point xi are locatednFeature space:the space of f(xi)after transformationoWhy transform?nLinear operation in the feature space is eq

37、uivalent to non-linear operation in input spacenClassification can become easier with a proper transformation.In the XOR problem,for example,adding a new feature of x1x2 make the problem linearly separable71Transforming the DataoComputation in the feature space can be costly because it is high dimen

38、sionalnThe feature space is typically infinite-dimensional!oThe kernel trick comes to rescuef()f()f()f()f()f()f()f()f(.)f()f()f()f()f()f()f()f()f()f()Feature spaceInput spaceNote:feature space is of higher dimension than the input space in practice72The Kernel TrickoRecall the SVM optimization probl

39、emoThe data points only appear as inner productoAs long as we can calculate the inner product in the feature space,we do not need the mapping explicitlyoMany common geometric operations(angles,distances)can be expressed by inner productsoDefine the kernel function K by73Examples of Kernel Functionso

40、Polynomial kernel with degree doRadial basis function kernel with width snClosely related to radial basis function neural networksnThe feature space is infinite-dimensionaloSigmoid with parameter k and q nIt does not satisfy the Mercer condition on all k and q74753.6聚类方法：K-MeansoGiven a set of examp

41、les Dn=z1,z2,znoSearch for K prototypes k of disjoint subsets Sk of Dn in order to minimizewhere k is the mean of the examples in subset Sk:oWe could use any distance,not just the Euclidean distance.Batch K-MeansoInitialization:select randomly K examples zj in Dn as initial values of each koAt each

42、batch iteration:nFor each prototype k,put in the emptied set Sk the examples of Dn that are closer to k than to any other jk.nRe-compute the value of each k as the average of the examples in Sk.oThe algorithm stops when no prototype moves anymore.oIt can be shown that the K-Means criterion will neve

43、r increase.76Batch K-Means(图示1)77Batch K-Means(图示2)78Batch K-Means(图示3)7980四、机器学习的难题与挑战注：以下部分内容引自周志华机器学习挑战王珏机器学习的难题与分析机器学习的难题(1)81维数灾难问题82维数灾难问题83维数灾难问题84维数灾难问题85机器学习的难题(2)训练数据问题训练数据问题nPU 学习问题:只有正例和未标记数据的学习问题，从仅部分标记的正例和其它的未标记数据上学习最优分类器n数据推广性86机器学习的难题(3)结构输出问题结构输出问题87挑战(1)：泛化能力共性问题：几乎所有的领域，都希望越准越好p提高

44、泛化能力是永远的追求目前泛化能力最强的技术：支持向量机（SVM）产生途径：理论-实践集成学习（ensemble learning）产生途径：实践-理论挑战(1)：泛化能力（续）第一个挑战：今后10年能否更“准”？如果能，会从哪儿来？挑战(2)：速度共性问题：几乎所有的领域，都希望越快越好p加快速度也是永远的追求“训练速度”vs.“测试速度 训练速度快的往往测试速度慢：k近邻 测试速度快的往往训练速度慢：神经网络挑战(2)：速度（续）第二个挑战：今后10年能否更“快”？能做到“训练快”、“测试也快”吗？如果能，如何做？挑战(3)：可理解性共性问题：绝大多数领域都希望有“可理解性”例子：医疗诊断

45、地震预测目前强大的技术几乎都是（或基本上是）“黑盒子”神经网络、支持向量机、集成学习p“黑盒子”能满足需要吗？挑战(3)：可理解性（续）第三个挑战：今后10年能否产生“白盒子”？是和“黑盒子”完全不同的东西，还是从“黑盒子”变出来？挑战(4)：数据利用能力传统的机器学习技术 对有标记数据进行学习“标记”事件所对应的结果共性问题：随着数据收集能力飞速提高、Internet的出现，在大多数领域中都可以很容易地获得大量未标记数据 例子：医学图象分析 垃圾邮件过滤p没有标记的数据是没用的吗？挑战(4)：数据利用能力（续）共性问题：在绝大多数领域中都会遇到“坏”数据，有时甚至只有“坏”数据 例子：海军舰

46、队 Web“坏”数据 大量噪音、属性缺失、不一致、传统的“坏”数据处理方式 “扔掉”p“坏”数据一点用也没有吗？第四个挑战：今后10年能否“数据通吃”？如何“吃”？挑战(4)：数据利用能力（续）挑战(5)：代价敏感目前的机器学习技术 降低错误率p“错误”是没有区别的吗？把“好”当成“坏”把“坏”当成“好”共性问题：大多数领域中的错误代价都不一样 例子：入侵检测 癌症诊断一样吗？第五个挑战：今后10年能否“趋利避害”？在达到较低的总错误率的基础上，如何“趋”、如何“避”？挑战(5)：代价敏感（续）挑战：More 在任何一个挑战上取得突破性进展，都可能成为对机器学习的重要贡献Magic of Ma

47、chine Learning100Magic of Machine Learning101主流期刊和会议oJournals:nJournal of Machine Learning ResearchnMachine LearningnIEEE Transactions on Pattern Analysis and Machine IntelligencenNeural ComputationnIEEE Transactions on Neural NetworksnIEEE Transactions on Knowledge and Data EngineeringoConferences:

48、nNIPS:Neural Information Processing SystemsnCOLT:Computational Learning TheorynICML:International Conference on Machine LearningnKDD:Knowledge Discovery and Data Mining in Database102相关资料oBooks:nC.Bishop.Neural Networks for Pattern Recognition,1995.nV.Vapnik.The Nature of Statistical Learning Theory

49、,1995.nT.Hastie,R.Tibshirani,J.Friedman.The elements of Statistical Learning,2001.nB.Schlkopf,A.J.Smola.Learning with Kernels,2002.103104附录、典型机器学习包介绍典型的机器学习开发包oOpenCV：Machine Learning Libraryn介绍内容来自OpenCV机器学习中文参考手册oWeka：Machine learning/data mining software written in Javan介绍的PPT节选自E.FrankMachine Learning with WEKAoSVM开发包nLIBSVMnSVM-Lightno105OpenCV structureCXCOREbasic structures and algoritms,XML support,drawing functionsCVImage processingand visionHighGUIGUI,Image and Video I/OMLMachine Learning algorithmsCVCamvideo stream processing106OpenCV-ML:Overviewo机器学习库（MLL）是一些用于分类、回归和数据聚类的类和函数n通用类和