模式識別教學(xué)課件第一章緒論

1、Pattern Recognition辦公地點(diǎn)：主樓501Email:Contents 1Introduction to Pattern Recognition 2Bayesian Decision Theory 3Maximum-Likelihood & Bayesian Parameter Estimation 4Linear Discriminant Functions5Feature Extraction & Selection6Unsupervised Learning & Clustering References1 Richard O. Duda, Peter E. Hart,

2、David G. Stork, Pattern Classification, 2nd Edition, John Wiley & Sons, Inc. 2001(模式分類，李宏東 姚天翔等譯，北京：機(jī)械工業(yè)出版社，2003年9月 2模式識別，邊肇祺，張學(xué)工等編 著，清華大學(xué)出版社，2000年1月第2版3 Vladimir N. Vapnik, The Nature of Statistical Learning, Springer-Verlag, New York, NY, 1995 (中譯本統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)，張學(xué)工譯，清華大學(xué)出版社，2000年9月)References主要期刊和會議In

3、ternational Journal of Pattern Recognition and Artificial Intelligence (IJPRAI) (http:/ ) Pattern Recognition Pattern Recognition Letter Machine Learning Neural Computation模式識別與人工智能 CVPR、ICPR、ICML、COLTNIPS1929年 G. Tauschek發(fā)明閱讀機(jī)，能夠閱讀0-9的數(shù)字。30年代 Fisher提出統(tǒng)計(jì)分類理論，奠定了統(tǒng)計(jì)模式識別的基礎(chǔ)。6070年代，統(tǒng)計(jì)模式識別發(fā)展很快，但由于被識別的模式愈

4、來愈復(fù)雜，特征也愈多，出現(xiàn)“維數(shù)災(zāi)難”。但由于計(jì)算機(jī)運(yùn)算速度的迅猛發(fā)展，這個問題得到一定克服。統(tǒng)計(jì)模式識別仍是模式識別的主要理論。Machine Perception模式識別的發(fā)展史模式識別的發(fā)展史50年代 Noam Chemsky 提出形式語言理論美籍華人付京蓀提出句法(結(jié)構(gòu))模式識別。60年代 L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應(yīng)用。80年代 Hopfield提出神經(jīng)元網(wǎng)絡(luò)模型理論。近些年人工神經(jīng)元網(wǎng)絡(luò)在模式識別和人工智能上得到較廣泛的應(yīng)用。90年代小樣本學(xué)習(xí)理論，支持向量機(jī)也受到了很大的重視。Machine PerceptionChapter 1: Int

5、roduction to Pattern Recognition Machine Perception An Example Pattern Recognition Systems The Design Cycle Learning and Adaptation Methods of Pattern Recognition ConclusionMachine PerceptionBuild a machine that can recognize patterns:Speech recognitionFingerprint identificationOCR (Optical Characte

6、r Recognition)DNA sequence identification IntroductionPattern recognition is the study of how machines can observe the environment, learn to distinguish patterns of interest from their background, and make sound and reasonable decisions about the categories of the patterns. (Anil K. Jain)模式識別：把一組研究對

7、象，根據(jù)其某些特征進(jìn)行識別并分類。Machine PerceptionWhat is a Pattern ?模式是指人所生活的客觀世界的總稱。模式（Pattern）：指一組包含了對事物所具有的特征和信息的描述。a fingerprint imagea handwritten cursive worda human facea speech signalA irisMachine Perception識別(Recognition)識別(Recognition)再認(rèn)知(Re-Cognition) 主要研究相似和分類問題 有監(jiān)督分類 無監(jiān)督分類模式識別是模擬人的某些功能:模擬人的視覺：計(jì)算機(jī)+光學(xué)系

8、統(tǒng)模擬人的聽覺：計(jì)算機(jī)+聲音傳感器模擬人的嗅覺和觸覺：計(jì)算機(jī)+傳感器Machine PerceptionAn example設(shè)想有一個魚類加工廠，希望能將傳送帶上魚的品種分類過程自動進(jìn)行。SpeciesSea bass(鱸魚)Salmon(鮭魚)Problem AnalysisSet up a camera and take some sample images to extract featuresLength長度Lightness光澤Width寬度Number and shape of fins鰭的數(shù)目和形狀Position of the mouth, etc嘴的位置等This is th

9、e set of all suggested features to explore for use in our classifier!An examplePreprocessing用分割技術(shù)將不同的魚分離開來，或者將魚同背景分開 將每條魚的數(shù)據(jù)送入特征提取器，其作用是通過測量特定的“特征”或“屬性”來簡化原始數(shù)據(jù) The features are passed to a classifierClassificationSelect the length of the fish as a possible feature for discrimination An exampleSampli

10、ngAn exampleAn exampleThe length is a poor feature alone!Select the lightness as a possible feature.An exampleThreshold decision boundary and cost relationship Move our decision boundary toward smaller values of lightness in order to minimize the cost (reduce the number of sea bass that are classifi

11、ed salmon!)Task of decision theoryAn exampleAdopt the lightness and add the width of the fishLightnessWidthFishx = x1, x2TAn exampleAn example怎樣才能事先知道其中哪個特征對分類性能最重要呢?因?yàn)槠渲心承┨卣骱芸赡苁侨哂嗟摹１热?，如果魚眼睛的顏色、與寬度完全相關(guān)，那么分類器的性能將不因增加了魚眼顏色這一特征而有任何改善。An example即使不考慮獲得更多特征時所需的額外的計(jì)算量。是否真的有必要采用非常多的特性呢？這樣作是否會給將來在非常高維的空間中進(jìn)行

12、分類操作埋下了“禍根”？假設(shè)在上述任務(wù)中，其他的特征要么太難以測量，要么對分類器毫無用處(甚至起反作用)。這樣，將只有兩個特征好用。An example如果分類的判決模型非常復(fù)雜，分界面也十分復(fù)雜(而不再像圖1-4那樣是一簡單分界直線)，所有的訓(xùn)練樣本可以被完美的正確分類(如圖1-5所示)，雖然如此，這樣一個結(jié)果也依然不令人滿意。 An exampleAn example過分復(fù)雜的模型將導(dǎo)致復(fù)雜的判決曲線。設(shè)計(jì)分類器的中心目標(biāo)是能夠?qū)π聵颖?比如以前從未見過的某條魚)做出正確的反應(yīng)，這就是“推廣能力”(generalization) 。圖1-5那種復(fù)雜的判決邊界過分“調(diào)諧” (tune)到某些

13、特定的訓(xùn)練樣本上了，而不是類別的共同特征，或者說是待分類的全部鱸魚(或者鮭魚)的總體模型。An example雖然這種判決曲線對訓(xùn)練樣本可以得到完美的分類效果，但是對將來的新模式推廣能力很差。例如，圖1-5中標(biāo)記“？”的新模式應(yīng)該更像是鮭魚。然而卻被分類為鱸魚。An example自然地，想采集更多的訓(xùn)練樣本，以獲得特征向量的更好估計(jì)。例如，可以使用類別樣本的概率分布?？墒?，在某些模式識別問題中，能夠比較容易獲得的樣本數(shù)據(jù)十分有限。即使在連續(xù)的特征空間中已經(jīng)有大量的樣本點(diǎn)，可是如果按照圖1-5的思路，分類器將給出極度復(fù)雜的判決邊界，而且將不太可能很好地處理全新的樣本模式。An example尋

14、求某種“簡化”分類器的方案。分類器所需的模型或判別邊界將不需要像圖1-5那樣復(fù)雜。如果已經(jīng)能夠更好的分類新的測試樣本，那么即使它對訓(xùn)練樣本集的分類性能不夠好，也應(yīng)該接受它。但是，假如在設(shè)計(jì)“復(fù)雜”的分類器時其推廣能力可能不是很好，那么，又將如何精確和定量的設(shè)計(jì)相對“簡單”一些的分類器呢?An exampleAn example圖1-6圖中標(biāo)示出的判決曲線是對訓(xùn)練樣本的分類性能和分界面復(fù)雜度的一個最優(yōu)折中。系統(tǒng)怎樣才能自動得出圖1-6所示的那種相對簡單的分界曲線，以使得其性能比圖1-4的直線分界面，或者圖1-5復(fù)雜分界曲線更為優(yōu)越？假設(shè)能夠做到“推廣能力”和“復(fù)雜度”的折中，又將怎么樣去預(yù)測系統(tǒng)

15、對新模式的推廣能力如何呢？統(tǒng)計(jì)模式識別要研究的中心問題。An exampleConclusionAn example錯誤率0.1500 0.03330.13330.0833An exampleConclusionAn exampleConclusionAn exampleConclusionAn exampleConclusionPattern Recognition SystemsPattern Recognition SystemsPattern Recognition SystemsSensingUse of a transducer (camera or microphone)PR s

16、ystem depends of the bandwidth, the resolution sensitivity distortion of the transducerSegmentation and groupingPatterns should be well separated and should not overlapFeature extractionDiscriminative featuresInvariant features with respect to translation, rotation and scale.ClassificationUse a feat

17、ure vector provided by a feature extractor to assign the object to a categoryPost ProcessingExploit context input dependent information other than from the target pattern itself to improve performancePattern Recognition SystemsThe Design CycleData collectionFeature ChoiceModel ChoiceTrainingEvaluati

18、onComputational ComplexityThe Design CycleData CollectionHow do we know when we have collected an adequately large and representative set of examples for training and testing the system?Feature ChoiceDepends on the characteristics of the problem domain. Simple to extract, invariant to irrelevant tra

19、nsformation insensitive to noise.The Design CycleModel ChoiceUse data to determine the classifier. Many different procedures for training classifiers and choosing modelsTrainingUnsatisfied with the performance of our fish classifier and want to jump to another class of modelEvaluationMeasure the err

20、or rate (or performance and switch from one set of features to another one)The Design CycleComputational ComplexityWhat is the trade-off between computational ease and performance?(How an algorithm scales as a function of the number of features, patterns or categories?)The Design CycleLearning and A

21、daptationSupervised learningA teacher provides a category label or cost for each pattern in the training setUnsupervised learningThe system forms clusters or “natural groupings” of the input patternsReinforcement LearningThe most typical way to train a classifier is to present an input, compute its

22、tentative category label, and use the known target category label to improve the classifier. In reinforcement learning or learning with a critic, no desired category signal is given; instead, the only teaching feedback is that the tentative category is right or wrong.模板匹配統(tǒng)計(jì)方法句法方法神經(jīng)網(wǎng)絡(luò)Methods of Pattern Recognition模板匹配首先對每個類別建立一個或多個模板輸入樣本和數(shù)據(jù)庫中每個類別的模板進(jìn)行比較，求相關(guān)或距離根據(jù)相關(guān)性或距離大小進(jìn)行決策優(yōu)點(diǎn)：直接、簡單缺點(diǎn)：適應(yīng)性差變形模板Met