分类器介绍的课件

模式识别概论模式识别概论模式识别概论模式识别概论中科院自动化所博士生模式识别课程讲义2010年10月14日刘成林Outline•模式和模式识别•模式识别方法分类•系统设计过程•系统设计过程•性能评价准则2模式和模式识别模式和模式识别模式和模式识别模式和模式识别•什么是模式–存在于数据中的物体（包括人、符号）、行为、关系等–数据：感知（视觉、听觉）数据，人工生成数据（网页、报表等）–模式的两个层次•样本(Sample,instance,example,vector,point,observation)•样本(Sample,instance,example,vector,point,observation)Apattern,asample,asampleset,asampleofpoints•类别(Class,category)例如：100个样本、10个类别3•什么是模式识别–（人、机器）对数据中存在的物体、行为、关系等模式进行检测(Detection)、描述(Description)和判别(Discrimination,identification,classification)的过程–核心技术：模式分类(PatternClassification)•Classification:synonymofPR(narrowsense)•检测：2-class(binary)•判别：2-class,multi-class•分类器设计：机器学习（一般是Supervised）•相关问题：特征生成、特征提取（变换）、特征选择、聚类（Unsupervised）数据获取预处理模式分割特征生成特征选择模式分类后处理设计(机器学习)DictionaryFile4DataacquisitionSegmentationPre-processingFeatureextractionPhysicalenvironmentPhysicalenvironmentPre-processingFeatureextraction/selectionTrainingdataFeatureextractionClassificationPost-processingFeaturesDecisionFeatureextraction/selectionModellearningFeaturesModel训练/测试过程中的模式预处理-特征提取必须完全一致一个例子一个例子一个例子一个例子姚明姚明姚明姚明/田亮田亮田亮田亮ROCKET8姚明姚明姚明姚明ROCKETS数据获取模式分割模式识别11预处理特征提取分类后处理116模式识别方法分类模式识别方法分类模式识别方法分类模式识别方法分类•Statistical:特征矢量–Parametric(Gaussian)•Structural:句法、结构–Syntacticparsing模式识别基本思想：Template/ModelMatchingFromCognitiontoRecognition按模式/模型表示方式分类–Parametric(Gaussian)–Non-parametric(k-NN)–Semi-parametric(GM)–Neural–Kernel(SVM)–Ensemble(Boosting)–Syntacticparsing–Stringmatching,tree–Graphmatching–HiddenMarkovmodel(HMM)–Markovrandomfield(MRF)HybridStatistical-Structural:Statisticalprimitive/relationshipAttributedgraphs,HMMandMRFareinstancesofhybridmodels7学习方法分类学习方法分类学习方法分类学习方法分类SupervisedUnsupervisedSemi-supervised样本标记程度分类器模型Single-labeled,multi-labeledGenerative(descriptive)modelDiscriminative(boundary)modelGenerativelearningDiscriminativelearning分类器模型学习准则8模式识别系统设计模式识别系统设计模式识别系统设计模式识别系统设计/评价过程评价过程评价过程评价过程LabeledSampleSetTrainingSetTestSetValidat.SetEstimat.Set•训练和测试过程分开，不同的样本集•训练过程中有模型选择问题ClassifierStructure,Hyper-parametersParameterEstimationValidationParameterEstimationTestingModelselection9分类器性能评价方法分类器性能评价方法分类器性能评价方法分类器性能评价方法•泛化性能(Generalization):TestAccuracy•数据划分方式–Cross-validation(rotation)•Leave-one-out(LOO)–Holdout–Randomsampling注意：训练/测试数据中的类别分布要一致！–Randomsampling–两个层次的划分•Performanceevaluation:Training+Test•Modelselection:Estimation+ValidationTrainingSetTestSetEstimationSetValidationSet选择模型（超参数）后再对所有的训练数据进行训练注意：训练/测试数据中的类别分布要一致！10性能评价准则性能评价准则性能评价准则性能评价准则•一般分类问题–正确率、错误率、拒绝率–组合代价•两类问题（verification,detection,retrieval等）1CERPPP++=12ERRwPwP=+TPFNFP11TruepositiveFalsepositiveFalsenegativeTruenegativeLabeledpositiveDetected•两类问题–Recall(sensitivity)(De:labeledpositive)–Precision(De:detected)1%%TPRFNTPTPFN==-=+TPPTPFP=+22=11RPFRPRP=++–Falsepositiverate(De:labelednegative)%1specificityFPFPFPTN==-+•多类问题的Recall,Precision,F-measure•比如文本分类•有些是多标记(Multi-labeled)•多个两类问题(One-vs-All)的平均12•多点比较–ROC(Receivingoperatingcharacteristic)curve•TP-FPtradeoffdependingondecisionthreshold•Amethodnotalwaysoutperformsanother–AUC(AreaUnderROCcurve)13•GeneralizationBound–Empiricalerror–Expectederror–Thefollowingboundholdswithprobability1(01)ηη-≤≤Ref:V.N.Vapnik,TheNatureofStatisticalLearningTheory,Springer,1995.1(01)ηη-≤≤h:Vapnik-Chervonenkis(VC)dimension.Itdefinesthelargestnumberofpointsthatcanbeseparatedinallpossiblewaysusingfunctionsofthegivenclass.14Bias-VarianceTradeoff15T.Hastie,T.Tibshrani,J.Friedman,TheElementsofStatisticalLearning,Springer,2001.Break统计模式识别统计模式识别统计模式识别统计模式识别中科院自动化所博士生模式识别课程讲义2010年10月14日刘成林Outline•统计模式识别的基本思想•Bayes决策•参数法(Parametric,Gaussian)18（下次课）•非参数法(Parzen,k-NN)•GaussianMixture,EM•Clustering统计模式识别的基本思想统计模式识别的基本思想统计模式识别的基本思想统计模式识别的基本思想•模式表示–特征矢量•特征到类别的映射–判别函数(Discriminantfunction)–比如T1=[,,]dxxx…1{,,}Mωω→x…max(,)iifωx2(,)||||fωμ=--xx19–比如•特征空间划分(决策区域){|(,)max(,)}iijjRffωω==xxx2(,)||||iifωμ=--xxR1R2R3Bayes决策决策决策决策•问题–模式表示：特征矢量–类别：–给定：•类条件概率密度T1=[,,]dxxx…,1,,iiMω=…(|),1,,ipiMω=x…20•类条件概率密度•先验概率•损失代价cij(由第j类错分到第i类的损失)•特殊情况：0-1代价–目的：将测试样本x分类到损失最小的类别1,0,ijijcij≠==(|),1,,ipiMω=x…()iPω•类别风险–0-1损失的情况•后验概率的计算(Bayes公式)1()(|)MiijjjRcPω==∑xx()(|)1(|)MiijjijiRcPPωω≠==-∑xxx(,)()(|)(|)()()(|)iiiiMjjpPpPpPpωωωωωω==∑xxxxx21•决策规则(Bayes规则)–0-1损失的情况(最大后验概率准则，MAP)–又称最大似然度规则argmin()iiRxargmax(|)iiPωx1jjj=∑(,)()(|)iiigPpωωω=xx(,)log()(|)iiigPpωωω=xxDiscriminantfunctionLikelihoodLog-likelihood•考虑拒绝的情况0,1,,rejectijrijcijc==≠1(|),1,,(),rejectiirPiMRcω-==xx…argmax(|),ifmax(|)1argmin()reject,otherwiseiiriiiiPPcRωω-=xxx22–实际中经常采用的策略•Soft-max•假设(,)(,)1e(|)eijfiMfjPγωγωω=≈∑xxx12(,)(,)(,)iijfffωωωxxx≫11211(,)(,)(,)[(,)(,)]e1max(|)ee1eiiiiififfffiPγωγωγωγωωω--≈=++xxxxxx12max(|)1(,)(,)iriiiPcffTωωω-⇔-xxx•Bayes决策的错误率(Bayesianerrorrate)()1()PerrorPcorrect=-11()(,)(|)()MiiiMiiiiMPcorrectPPPωωω===∈=∈∑∑xxRR231(|)()iMiiiPPdωω==∑∫xxR11()max(|)()max(|)()MiiiiMiiiPcorrectPPdPPdωωω====∑∫∑∫xxxxxxxMAPrule1(|)pxω2(|)pxωx2(|)pxω1(|)pxω241max(|)iiPω-x•Bayes决策的关键–类条件概率密度估计–先验概率：从训练样本估计或假设等概率–损失代价[cij]，一般为0-1代价Bayes决策用于模式分类决策用于模式分类决策用于模式分类决策用于模式分类25•概率密度估计方法–参数法：假定概率密度函数形式•Gaussian,Gamma,Bernouli–非参数法：可以表示任意概率分布•Parzenwindow,k-NN–S