1、模式識(shí)別與神經(jīng)網(wǎng)絡(luò)Pattern Recognition And neural network,第一章 模式識(shí)別概述,Table of Contents,與課程相關(guān)的部分圖書,1.1 模式識(shí)別和模式的概念,感知：從環(huán)境獲取信息,計(jì)算機(jī)模式識(shí)別,模式識(shí)別：使計(jì)算機(jī)模仿人的感知能力，從感知數(shù)據(jù)中提取信息（判別物體和行為）的過(guò)程。,概念,姚明 ROCKETS 11,模式識(shí)別和模式的概念,人類具有很強(qiáng)的模式識(shí)別能力，時(shí)刻在完成某種模式識(shí)別的任務(wù)。 模式識(shí)別作為一門學(xué)科，是研究用機(jī)器完成自動(dòng)識(shí)別事物的工作。 模式識(shí)別學(xué)科形成于5060年代，與眾多學(xué)科有聯(lián)系，尤其與人工智能和圖像處理關(guān)系密切。 模式識(shí)別是

2、一門理論與應(yīng)用并重的技術(shù)科學(xué)。有廣泛的需求。 還在發(fā)展中，現(xiàn)有的理論與方法還有不足。,概念,模式識(shí)別的意義,數(shù)字化感知數(shù)據(jù)：來(lái)源豐富、數(shù)量巨大,概念,模式識(shí)別的難點(diǎn),感知數(shù)據(jù)：非結(jié)構(gòu)化（像素、波紋等）,概念,模式與模式類,樣本(sample, object, pattern)：一類事物的一個(gè)具體體現(xiàn)，對(duì)具體的個(gè)別事物進(jìn)行觀測(cè)所得到的某種形式的信號(hào)。 模式類(pattern class)：表示一類事物，如印刷體A與手寫體A屬同一類。B與A則屬于不同類。 樣本是具體的事物，而模式類是對(duì)同一類事物概念性的概括。 模式類與模式聯(lián)合使用時(shí)，模式表示具體的事物，而模式類則是對(duì)這一類事物的概念性描述。 模式

3、識(shí)別是從樣本到類別的映射。,概念,模式識(shí)別和模式的概念,Watanabe defines a pattern “as opposite of a chaos; it is an entity, vaguely defined, that could be given a name.” a fingerprint image a handwritten cursive word a human face a speech signal ,概念,模式識(shí)別和模式的概念,識(shí)別是時(shí)時(shí)刻刻發(fā)生的活動(dòng) 識(shí)別（Recognition)再認(rèn)知（Re-Cognition) 主要研究相似和分類問(wèn)題 有監(jiān)督分類 無(wú)監(jiān)

4、督分類 與其他學(xué)科的關(guān)系 統(tǒng)計(jì)學(xué) 人工智能 機(jī)器學(xué)習(xí) 運(yùn)籌學(xué)與最優(yōu)化,概念,模式識(shí)別與其他學(xué)科的關(guān)系,概念,模式識(shí)別學(xué)科位置,模式識(shí)別：計(jì)算機(jī)科學(xué)與電子工程交叉學(xué)科 中國(guó)：“控制科學(xué)與工程”一級(jí)學(xué)科 二級(jí)學(xué)科：控制理論與控制工程、模式識(shí)別與智能系統(tǒng)、系統(tǒng)工程等 西方：沒(méi)有自動(dòng)控制系 自動(dòng)控制：電子工程系、機(jī)械工程系 模式識(shí)別：電子工程系、計(jì)算機(jī)科學(xué)系,主要組織,國(guó)際組織 IAPR IEEE Computer Society: TC on PAMI (Pattern Analysis and Machine Intelligence) 國(guó)內(nèi)組織 中國(guó)自動(dòng)化學(xué)會(huì)：模式識(shí)別與機(jī)器智能(PRMI)專業(yè)

5、委員會(huì)，1981年成立，IAPR成員組織 中國(guó)計(jì)算機(jī)學(xué)會(huì)：人工智能與模式識(shí)別專業(yè)委員會(huì) 中國(guó)人工智能學(xué)會(huì),主要機(jī)構(gòu),國(guó)外 USA: MIT (Poggio), UIUC (Thomas Huang), CMU (T. Kanade), MSU (A.K. Jain), Maryland (Resenfeld, Chellappa) Canada: Toronto (Hinton), Concordia (C.Y. Suen) UK: Surrey (Kittler), MSR Cambridge (Bishop) France: INRIA 國(guó)內(nèi) MSRA, HKUST 中科院自動(dòng)化所、清華大

6、學(xué)、北京大學(xué)、上海交大、西安交大、南京理工大學(xué)、武漢大學(xué)等,1.2 模式識(shí)別系統(tǒng),數(shù)據(jù)獲取,預(yù)處理,特征提取與選擇,分類決策,分類器設(shè)計(jì),信號(hào)空間,特征空間,模式識(shí)別系統(tǒng)的組成,系統(tǒng),模式識(shí)別系統(tǒng)的密集計(jì)算特性,模式識(shí)別系統(tǒng)各子系統(tǒng)(預(yù)處理，特征提取與選擇，分類決策)具有典型的計(jì)算密集型特征。 模式識(shí)別系統(tǒng)設(shè)計(jì)階段一般需從樣本學(xué)習(xí)規(guī)則，需要大量的統(tǒng)計(jì)計(jì)算。,課程實(shí)驗(yàn)選用Matlab系統(tǒng),系統(tǒng),模式識(shí)別研究?jī)?nèi)容,數(shù)據(jù)預(yù)處理 視頻、圖像、信號(hào)處理 模式分割 模式/背景分離、模式-模式分離 運(yùn)動(dòng)分析 目標(biāo)跟蹤、運(yùn)動(dòng)模式描述 模式描述與分類 特征提取/選擇、模式分類、聚類、機(jī)器學(xué)習(xí) 模式識(shí)別應(yīng)用研究

7、針對(duì)具體應(yīng)用的方法與系統(tǒng),系統(tǒng),1.3 模式識(shí)別的方法,模版匹配法(templete matching) 統(tǒng)計(jì)方法(statistical pattern recognition)： 1950s- 神經(jīng)網(wǎng)絡(luò)方法(neural network)： 1980s- 結(jié)構(gòu)方法(句法方法)： 1970s- (structural pattern recognition ),支持向量機(jī)、核方法：1990s- 多分類器、集成學(xué)習(xí)：1990s- Bayes學(xué)習(xí)：1990s- 1990s-: 模式識(shí)別技術(shù)大規(guī)模應(yīng)用,模版匹配,首先對(duì)每個(gè)類別建立一個(gè)或多個(gè)模版 輸入樣本和數(shù)據(jù)庫(kù)中每個(gè)類別的模版進(jìn)行比較，例如求相關(guān)

8、或距離 根據(jù)相似性（相關(guān)性或距離）大小進(jìn)行決策 優(yōu)點(diǎn)：直接、簡(jiǎn)單 缺點(diǎn)：適應(yīng)性差 擴(kuò)展：彈性模版法,方法,統(tǒng)計(jì)方法,根據(jù)訓(xùn)練樣本，建立決策邊界(decision boundary) 統(tǒng)計(jì)決策理論根據(jù)每一類總體的概率分布決定決策邊界 判別式分析方法給出帶參數(shù)的決策邊界，根據(jù)某種準(zhǔn)則，由訓(xùn)練樣本決定“最優(yōu)”的參數(shù) 本課程的重點(diǎn)內(nèi)容,方法,句法方法,許多復(fù)雜的模式可以分解為簡(jiǎn)單的子模式，這些子模式組成所謂 “基元” 每個(gè)模式都可以由基元根據(jù)一定的關(guān)系來(lái)組成 基元可以認(rèn)為是語(yǔ)言中的詞語(yǔ)，每個(gè)模式都可以認(rèn)為是一個(gè)句子，關(guān)系可以認(rèn)為是語(yǔ)法 模式的相似性由句子的相似性來(lái)決定 1970s由付京蓀(K.S. F

9、u, Purdue Univ.)提出 優(yōu)點(diǎn)：適合結(jié)構(gòu)性強(qiáng)的模式 缺點(diǎn)：抗噪聲能力差，計(jì)算復(fù)雜度高,方法,神經(jīng)網(wǎng)絡(luò),進(jìn)行大規(guī)模并行計(jì)算的數(shù)學(xué)模型 具有學(xué)習(xí)、推廣、自適應(yīng)、容錯(cuò)、分布表達(dá)和計(jì)算的能力 優(yōu)點(diǎn)：可以有效的解決一些復(fù)雜的非線性問(wèn)題 缺點(diǎn)：缺少有效的學(xué)習(xí)理論,方法,幾種方法比較,方法,神經(jīng)網(wǎng)絡(luò)和統(tǒng)計(jì)模式識(shí)別的關(guān)系,方法,1.4 模式識(shí)別應(yīng)用,文本圖像分析，文本分類 語(yǔ)音識(shí)別 工業(yè)自動(dòng)化：零部件/物品分類 數(shù)據(jù)挖掘 多媒體數(shù)據(jù)檢索（文檔、圖像、視頻、音樂(lè)檢索 ） 生物特征識(shí)別，生物信息學(xué)，醫(yī)學(xué)圖像 空間探測(cè)與環(huán)境資源檢測(cè)，遙感圖像 安全監(jiān)控（身份識(shí)別、視頻監(jiān)控、交通監(jiān)控、音視頻監(jiān)聽(tīng)） ,生物

10、特征識(shí)別,應(yīng)用,遙感圖像地表分類,應(yīng)用,醫(yī)學(xué)圖像分析,應(yīng)用,車牌識(shí)別,應(yīng)用,信函分揀,應(yīng)用,1.5 有關(guān)模式識(shí)別的若干問(wèn)題,模式類的緊致性： 集合中任意兩個(gè)內(nèi)點(diǎn)可以用光滑線連接，在該連線上的點(diǎn)也屬于這個(gè)集合。 每個(gè)內(nèi)點(diǎn)都有一個(gè)足夠大的鄰域，在該鄰域中只包含同一集合中的點(diǎn)。 假若每個(gè)模式類都滿足緊致性假設(shè)，則解決模式識(shí)別間題就不會(huì)碰到什么原則上的困難。但對(duì)于很多實(shí)際問(wèn)題這個(gè)假設(shè)是不成立的。 假設(shè)臨界點(diǎn)的數(shù)量與總的點(diǎn)數(shù)相比很少。 只耍各個(gè)模式類是可分的，總存在這樣一個(gè)空間，使變換到這個(gè)空間中的集合滿足緊致性要求。,有關(guān)模式識(shí)別的若干問(wèn)題,相似與分類：相似與分類問(wèn)題遠(yuǎn)不像集合表達(dá)那樣簡(jiǎn)單明了。集合的

11、概念可用來(lái)表現(xiàn)已經(jīng)分好的類，但對(duì)于怎樣分類和歸類則缺乏指導(dǎo)意義。 相似性度量：樣本xi和 xj是Rn空間中兩個(gè)點(diǎn)，它們間的某種距離的函數(shù) s(xi, xj)。 距離: d(xi, xj)=(xi - xj)T.(xi - xj)1/2 相似性度量1: s(xi, xj)=f(d(xi, xj) 相似性度量2: s(xi, xj)=cos() 分類都是帶有主觀性的行為，常缺乏純客觀的分類標(biāo)準(zhǔn)。 靠哪些特征決定相似并進(jìn)行分類，取決于行為的目的和方法。,模式識(shí)別和模式的概念,Pattern recognitionis the study of how machines can observe the

12、 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),概念,What is pattern recognition?,A pattern is an object, process or event that can be given a name. A pattern class (or category)

13、 is a set of patterns sharing common attributes and usually originating from the same source. During recognition (or classification) given objects are assigned to prescribed classes. A classifier is a machine which performs classification.,“The assignment of a physical object or event to one of seve

14、ral pre-specified categories” - Duda ) parametrized by the task is to find the “best” parameter * based on a set of training examples (x1,y1),(x,y) - supervised learning.,The task of learning: recognition which classification rule is to be used.,The way how to perform the learning is determined by a

15、 selected inductive principle.,Empirical risk minimization principle,The true expected risk R(q) is approximated by empirical risk,with respect to a given labeled training set (x1,y1),(x,y).,The learning based on the empirical minimization principle is defined as,Examples of algorithms: Perceptron,

16、Back-propagation, etc.,Overfitting and underfitting,Problem: how rich class of classifications q(x;) to use.,underfitting,overfitting,good fit,Problem of generalization: a small emprical risk Remp does not imply small true expected risk R.,Structural risk minimization principle,An upper bound on the

17、 expected risk of a classification rule qQ,where is number of training examples, h is VC-dimension of class of functions Q and 1- is confidence of the upper bound.,SRM principle: from a given nested function classes Q1,Q2,Qm, such that,select a rule q* which minimizes the upper bound on the expected

18、 risk.,Statistical learning theory - Vapnik & Chervonenkis.,Unsupervised learning,Input: training examples x1,x without information about the hidden state.,Clustering: goal is to find clusters of data sharing similar properties.,Classifier,Learning algorithm,Classifier,Learning algorithm (supervised),A broad class of unsupervised learning algorithms:,Example of unsupervised learning algorithm,k-Means clustering:,Goal is