人工智能7第七章機(jī)器學(xué)習(xí)

1、機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)要介紹的內(nèi)容要介紹的內(nèi)容l機(jī)器學(xué)習(xí)概述l統(tǒng)計(jì)學(xué)習(xí)理論的方法l基于符號的方法l連接主義的方法l遺傳與進(jìn)化的方法第七章機(jī)器學(xué)習(xí)第七章機(jī)器學(xué)習(xí) 2/20/20221機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)的定義的定義l機(jī)器學(xué)習(xí)還沒有統(tǒng)一的定義機(jī)器學(xué)習(xí)還沒有統(tǒng)一的定義l機(jī)器學(xué)習(xí)的一種定義機(jī)器學(xué)習(xí)的一種定義:機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識和新技能,并識別現(xiàn)有知識的學(xué)問。 l另一種機(jī)器學(xué)習(xí)定義機(jī)器學(xué)習(xí)定義：如果一個(gè)計(jì)算機(jī)程序針對某類任務(wù)T的用P衡量的性能根據(jù)經(jīng)驗(yàn)E來自我完善。那么我們稱這個(gè)計(jì)算機(jī)程序在從經(jīng)驗(yàn)E中學(xué)習(xí)，針對某類任務(wù)T，它的性能用P來衡量l任何智能系統(tǒng)必須具備學(xué)習(xí)的能力l學(xué)習(xí)是使得智能主體在與環(huán)境交

2、互的過程中改變自己. 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/20222機(jī)器學(xué)習(xí)研究機(jī)器學(xué)習(xí)研究的幾種觀點(diǎn)的幾種觀點(diǎn)l統(tǒng)計(jì)學(xué)習(xí)理論-基于統(tǒng)計(jì)理論進(jìn)行的推斷、預(yù)測等學(xué)習(xí)方法。l符號主義采用符號來表示問題域中的實(shí)體極其關(guān)系,通過對符號語言表示的規(guī)則進(jìn)行搜索，試圖用這些符號來推出新的、有效的并且也用這些符號表達(dá)的一般規(guī)則。l連接主義受生物神經(jīng)網(wǎng)絡(luò)系統(tǒng)的啟發(fā)，把知識表示為由小的個(gè)體處理單元組成的網(wǎng)絡(luò)的激活或者抑制狀態(tài)模式。學(xué)習(xí)是通過訓(xùn)練數(shù)據(jù)來修改網(wǎng)絡(luò)結(jié)構(gòu)和連接權(quán)值來實(shí)現(xiàn)。l遺傳和進(jìn)化觀點(diǎn)，在開始時(shí)有一組問題的后選解，根據(jù)他們解決問題的能力來進(jìn)化，適者生存，并相互交叉產(chǎn)生下一代解，

3、這樣，解不斷的增強(qiáng)就像達(dá)爾文描述的生物世界一樣第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/20223機(jī)器學(xué)習(xí)問題機(jī)器學(xué)習(xí)問題的表示的表示l系統(tǒng)s是要研究的對象，給定輸入x，得到輸出ylLM是所求的學(xué)習(xí)機(jī)，預(yù)測輸出yl機(jī)器學(xué)習(xí)目的根據(jù)給定的已知訓(xùn)練樣本，求取對系統(tǒng)輸入輸出之間依賴關(guān)系的估計(jì)，使它能夠?qū)ξ粗敵鲎鞒霰M可能準(zhǔn)確的預(yù)測。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述輸入x系統(tǒng)（s）背景知識輸出y學(xué)習(xí)機(jī)（LM）預(yù)測輸出y圖 機(jī)器學(xué)習(xí)問題的基本模型2/20/20224機(jī)器學(xué)習(xí)問題的形式化表示機(jī)器學(xué)習(xí)問題的形式化表示l已知變量y與輸入 x之間存在一定的未知依賴關(guān)系，l

4、即 存在一個(gè)未知的聯(lián)合概率F(x,y)，l機(jī)器學(xué)習(xí)根據(jù)n個(gè)獨(dú)立同分布觀測樣本(x1,y1), (xn,yn) ，在一組函數(shù)f(x,w)中求一個(gè)最優(yōu)的函數(shù)f(x,w0)對依賴關(guān)系進(jìn)行估計(jì)，使預(yù)測的期望風(fēng)險(xiǎn)最小第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述),(),(,()(yxdFwxfyLwRl其中， f(x,w)為預(yù)測函數(shù)集，L()為損失函數(shù)l預(yù)測函數(shù)又稱為學(xué)習(xí)函數(shù)或?qū)W習(xí)模型2/20/20225機(jī)器學(xué)習(xí)中的三類基本問題l模式識別l函數(shù)逼近l概率密度第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述輸入x系統(tǒng)（s）背景知識輸出y學(xué)習(xí)機(jī)（LM）預(yù)測輸出y2/20/20226模式識別問題的

5、損失函數(shù)l模式識別問題，其實(shí)是個(gè)分類問題l多模式識別問題可以分解成若干個(gè)兩模式識別問題l預(yù)測函數(shù)可只考慮二值函數(shù)ly是只取0，1l損失函數(shù)可定義為：第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述),( if 1),( if 0),(,(wxfxwxfxwxfyL2/20/20227函數(shù)逼近問題的損失函數(shù)ly是連續(xù)變量，是x的函數(shù)lf(x,w)是實(shí)函數(shù)l損失函數(shù)可定義為第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2),(),(,(wxfywxfyL2/20/20228概率密度估計(jì)問題的損失函數(shù)l學(xué)習(xí)的目的是根據(jù)訓(xùn)練樣本確定x 的概率分布。l將密度函數(shù)記為p(x,w)，l損失函數(shù)可以

6、定義為：第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述),(ln(),(wxpwxpL2/20/20229經(jīng)驗(yàn)風(fēng)險(xiǎn)l期望風(fēng)險(xiǎn) 是預(yù)測函數(shù)在整個(gè)樣本空間上出錯(cuò)率的數(shù)學(xué)期望l期望風(fēng)險(xiǎn)必須依賴于聯(lián)合概率的信息l聯(lián)合概率未知，因此期望風(fēng)險(xiǎn)實(shí)際上不可求l傳統(tǒng)的學(xué)習(xí)方法采用了經(jīng)驗(yàn)風(fēng)險(xiǎn)來近似期望風(fēng)險(xiǎn)l定義經(jīng)驗(yàn)風(fēng)險(xiǎn)第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述),(,(1)(1wxfyLnwRiniiemp2/20/202210經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化l經(jīng)驗(yàn)風(fēng)險(xiǎn)為訓(xùn)練樣本集上的平均錯(cuò)誤率l設(shè)計(jì)學(xué)習(xí)函數(shù)使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。l經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化與期望風(fēng)險(xiǎn)最小化的等價(jià)前提是樣本數(shù)據(jù)足夠多l(xiāng)只有在樣本數(shù)趨于無窮大時(shí)，其性

7、能才有理論上的保證。l但在小樣本的情況下，期望風(fēng)險(xiǎn)最小化到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化并沒有可靠的理論依據(jù)，只是直觀上合理的想當(dāng)然做法。l在實(shí)際應(yīng)用中，一般難以取得理想的效果。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202211推廣能力（泛化能力）l學(xué)習(xí)機(jī)器對未來輸出進(jìn)行正確預(yù)測的能力稱為推廣能力（或泛化能力）。l在某些情況下，當(dāng)訓(xùn)練誤差過小反而會導(dǎo)致推廣能力的下降這就是過學(xué)習(xí)問題。l出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因：一是因?yàn)閷W(xué)習(xí)樣本不充分；二是學(xué)習(xí)機(jī)器設(shè)計(jì)不合理。這兩個(gè)問題是互相關(guān)聯(lián)的。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202212預(yù)測問題舉例預(yù)測問題舉例 l綠色曲線

8、：y=sin(2x)l藍(lán)點(diǎn)：有隨機(jī)噪聲的樣本l目標(biāo)：曲線擬合，以便對新的輸入值x，預(yù)測輸出y第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202213多項(xiàng)式曲線擬合（回歸）多項(xiàng)式曲線擬合（回歸）第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述l學(xué)習(xí)，首先要選擇一種模型形式l這里，我們選擇多項(xiàng)式曲線l由于多項(xiàng)式對于未知參數(shù)是線性的l這種模型稱為線性模型2/20/202214確定參數(shù)確定參數(shù) w w第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述l如何訓(xùn)練模型（確定w）l因?yàn)槭蔷€性模型l風(fēng)險(xiǎn)函數(shù)選擇誤差平方和l我們要確定我們要確定w，使風(fēng)險(xiǎn)最小，使風(fēng)險(xiǎn)最小21),(21)(

9、nnNntwxywR2/20/202215 多項(xiàng)式次數(shù)多項(xiàng)式次數(shù)M的選擇的選擇the best fit to the function第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述l欠擬合：對數(shù)據(jù)擬合差l表示性差l過擬合：對訓(xùn)練數(shù)據(jù)精確擬合，對函數(shù)表示差2/20/202216測試數(shù)據(jù)進(jìn)行評價(jià)測試數(shù)據(jù)進(jìn)行評價(jià)均方根 (RMS) 誤差(風(fēng)險(xiǎn)):N: 標(biāo)準(zhǔn)化平方根: 在同一尺度下度量 ERMS 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述l從圖中看出：泛化性依賴Ml選擇：M=3-9l過擬合：對訓(xùn)練數(shù)據(jù)精確擬合，對函數(shù)表示差l在M=9，為什么會震蕩？2/20/202217多項(xiàng)式系數(shù)多項(xiàng)式

10、系數(shù) 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述l用不同次數(shù)下的w，考察欠擬合與過擬合問題l隨著M的增加，為了擬合隨機(jī)噪音，w在變大2/20/202218數(shù)據(jù)集規(guī)模產(chǎn)生的影響數(shù)據(jù)集規(guī)模產(chǎn)生的影響 數(shù)據(jù)集越大，擬合數(shù)據(jù)的模型就越靈活第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202219預(yù)測函數(shù)復(fù)雜性與泛化能力預(yù)測函數(shù)復(fù)雜性與泛化能力 l 從前例可以看出： “最優(yōu)擬合函數(shù)”不一定能正確代表原來的函數(shù)模型。l原因是：用一個(gè)復(fù)雜的模型去擬合有限的樣本，結(jié)果就會喪失推廣能力。l有限樣本下學(xué)習(xí)機(jī)器的復(fù)雜性與推廣性之間的矛盾。l 有時(shí)，已知問題是某個(gè)比較復(fù)雜的模型： 由于訓(xùn)練樣

11、本有限，如用復(fù)雜預(yù)測函數(shù)去學(xué)習(xí)效果通常不如用相對簡單的預(yù)測函數(shù)。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202220統(tǒng)計(jì)學(xué)習(xí)理論的主要內(nèi)容統(tǒng)計(jì)學(xué)習(xí)理論的主要內(nèi)容l統(tǒng)計(jì)學(xué)習(xí)理論被認(rèn)為是目前針對小樣本統(tǒng)計(jì)估計(jì)和預(yù)測學(xué)習(xí)的最佳理論。l它從理論上較系統(tǒng)地研究了：經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化規(guī)則成立的條件、有限樣本下經(jīng)驗(yàn)風(fēng)險(xiǎn)與期望風(fēng)險(xiǎn)的關(guān)系如何利用這些理論找到新的學(xué)習(xí)原則和方法l其主要內(nèi)容包括如下四個(gè)方面：經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則下統(tǒng)計(jì)學(xué)習(xí)一致性的條件；在這些條件下關(guān)于統(tǒng)計(jì)學(xué)習(xí)方法推廣性的界的結(jié)論；在這些界的基礎(chǔ)上建立的小樣本歸納推理原則；實(shí)現(xiàn)這些新的原則的實(shí)際方法。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.

12、1 7.1概述概述2/20/202221學(xué)習(xí)過程一致性學(xué)習(xí)過程一致性l學(xué)習(xí)一致性的結(jié)論是統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)l一致性條件，保證在經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則下得到的最優(yōu)方法當(dāng)樣本無窮大時(shí)趨近于使期望風(fēng)險(xiǎn)最小的最優(yōu)結(jié)果。l學(xué)習(xí)過程的一致性：(x1,y1) ，(xn.yn)是n個(gè)獨(dú)立同分布樣本f(x,w*) 最優(yōu)預(yù)測函數(shù)Min(Remp(w) = Remp(w*|n) 是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小值R(w*|n) 為相應(yīng)的真實(shí)風(fēng)險(xiǎn)值（期望風(fēng)險(xiǎn)值）R (w0) = inf(R(w) 為實(shí)際的最小真實(shí)風(fēng)險(xiǎn)值（期望風(fēng)險(xiǎn)值）如果： Remp(w*|n) R (w0) ， R(w*|n) R (w0) 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí)

13、7.1 7.1概述概述2/20/202222學(xué)習(xí)過程一致性的條件學(xué)習(xí)過程一致性的條件l非平凡一致性:如果預(yù)測函數(shù)集中每個(gè)函數(shù)都滿足一致性l 學(xué)習(xí)理論關(guān)鍵定理：對于有界的損失函數(shù)，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小 化學(xué)習(xí)一致的充分必要條件是經(jīng)驗(yàn)風(fēng)險(xiǎn)在如下意義上一致地收斂于真實(shí)風(fēng)險(xiǎn)其中，P表示概率， Remp(w)、R (w)分別表示在n個(gè)樣本下的經(jīng)驗(yàn)風(fēng)險(xiǎn)和真實(shí)風(fēng)險(xiǎn)。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述0 0)()(sup(limwRwRPempwn2/20/202223定義指標(biāo)，衡量函數(shù)集性能定義指標(biāo)，衡量函數(shù)集性能l學(xué)習(xí)理論關(guān)鍵定理沒有給出什么樣的學(xué)習(xí)方法能夠滿足這些條件l為了研究函數(shù)集在經(jīng)驗(yàn)風(fēng)險(xiǎn)

14、最小化原則下的學(xué)習(xí)一致性問題和一致性收斂的速度l定義一些指標(biāo)：指示函數(shù)集的熵（VC熵）和生長函數(shù)退火的VC熵VC維第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202224指示函數(shù)集的熵和生長函數(shù)指示函數(shù)集的熵和生長函數(shù)l指示函數(shù)集：f(x,w)l樣本集：Zn=zi=(xi,yi) i=1,nl函數(shù)集中的函數(shù)能對這組樣本實(shí)現(xiàn)的不同種分類數(shù)目：N(Zn)l隨機(jī)熵：H(Zn)=In(N(Zn) (函數(shù)集在這組樣本上的)l指示函數(shù)集的熵（VC熵）：H(n)=E(In(N(Zn) (與樣本無關(guān))l由于VC熵與樣本的分布有關(guān)l生長函數(shù)： G(n)=In(max(N(Zn) 第第七七章機(jī)器

15、學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202225退火的VC熵l定義為：Hann(n)=In(E(N(Zn)lJensen不等式aiInxiIn(aixi)lH(n)Hann(n)G(n)nIn2第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202226學(xué)習(xí)過程一致收斂的充分必要條件l函數(shù)集學(xué)習(xí)過程一致收斂的充分必要條件是對任意的樣本分布， 都有l(wèi)im G(n)/n = 0這時(shí)學(xué)習(xí)過程收斂速度一定是快的l函數(shù)集學(xué)習(xí)收斂速度快的充分必要條件是lim Hann(n)/n = 0 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202227生長函數(shù)的性質(zhì)l 所

16、有函數(shù)集的生長函數(shù)或者：G(n)=nIn2l或者G(n)h In(n/h +1) nhl其中，h是一個(gè)整數(shù)l可以看出，生長函數(shù)要么是線性的，要么以參數(shù)為h 的對數(shù)函數(shù)為上界。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述G(n)nIn2nhhIn(n/h+1)2/20/202228VC維l函數(shù)集能夠把樣本集打散：函數(shù)集中的函數(shù)有2h種形式把h個(gè)樣本的樣本集分為兩類，l指示函數(shù)集的VC維：函數(shù)集能夠打散的最大樣本集的h如果指示函數(shù)集的生長函數(shù)是線性的，其VC維為無窮大如果生長函數(shù)以參數(shù)為h的對數(shù)函數(shù)為上界，則函數(shù)集的VC維是hlVC維是對由學(xué)習(xí)機(jī)器實(shí)現(xiàn)的分類函數(shù)族的容量或表示能力的測度。第

17、第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202229VC維與學(xué)習(xí)過程一致性l 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化學(xué)習(xí)過程一致的充分必要條件是函數(shù)集的VC維有限，l且這時(shí)收斂速度是快的。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202230推廣性的界l對于兩類分類問題，對指示函數(shù)集中的所有函數(shù)，經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)之間至少以概率1- 滿足：第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述)()()(hnwRwRempl稱為置信范圍，或VC信任l置信范圍既受置信概率概率1-的影響，也受VC維和樣本數(shù)目的影響l當(dāng)n/h較小時(shí)，置信范圍較大，用經(jīng)驗(yàn)風(fēng)險(xiǎn)近似真實(shí)風(fēng)險(xiǎn)就有較大的誤差l

18、當(dāng)n/h較大，則置信范圍就會很小，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的最優(yōu)解就接近實(shí)際的最優(yōu)解。2/20/202231對對推廣性界的說明推廣性界的說明l推廣性的界是對于最壞情況的結(jié)論l給出的界在很多情況下是松弛的，尤其當(dāng)VC維比較高時(shí)更是如此。l VC維無窮大時(shí)這個(gè)界就不再成立l這種界往往只在對同一類學(xué)習(xí)函數(shù)進(jìn)行比較時(shí)是有效的，用于指導(dǎo)從函數(shù)集中選擇最優(yōu)的函數(shù)l在不同函數(shù)集之間比較卻不一定成立。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202232函數(shù)子集序列（子集結(jié)構(gòu)）函數(shù)子集序列（子集結(jié)構(gòu)）l經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則在樣本數(shù)目有限時(shí)不合理：需要同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍。l 考慮分解函數(shù)集S=

19、f(x,w)為一 個(gè)函數(shù)子集序列（或叫子集結(jié)構(gòu)）: S1S2SnS:使各個(gè)子集能夠按照置信范圍的大小排列，也就是按VC維的大小排列，即： h1h2hnhSl同一個(gè)子集中置信范圍就相同第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202233結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則SRMl在每一個(gè)子集中尋找最小經(jīng)驗(yàn)風(fēng)險(xiǎn)l通常它隨著子集復(fù)雜度的增加而減小l選擇最小經(jīng)驗(yàn)風(fēng)險(xiǎn)與置信范圍之和最小的子集，就可以達(dá)到期望風(fēng)險(xiǎn)的最小，l這個(gè)子集中使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的函數(shù)就是要求的最優(yōu)函數(shù)。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202234 Sn S*經(jīng)驗(yàn)風(fēng)險(xiǎn)經(jīng)驗(yàn)風(fēng)險(xiǎn)置信范置信范

20、圍圍真實(shí)風(fēng)險(xiǎn)的界真實(shí)風(fēng)險(xiǎn)的界h1h*hnhS1S*Sn結(jié)構(gòu)風(fēng)險(xiǎn)最小化圖示結(jié)構(gòu)風(fēng)險(xiǎn)最小化圖示風(fēng)險(xiǎn)風(fēng)險(xiǎn)第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述欠學(xué)習(xí)欠學(xué)習(xí)過學(xué)習(xí)過學(xué)習(xí)2/20/202235合理的函數(shù)子集結(jié)構(gòu)應(yīng)滿足合理的函數(shù)子集結(jié)構(gòu)應(yīng)滿足l兩個(gè)基本條件：l一是每個(gè)子集的VC維是有限的且滿足h1h2hnhSl二是每個(gè)子集中的函數(shù)對應(yīng)的損失函數(shù)或者是有界的非負(fù)函數(shù)，或者對一定的參數(shù)對（p,k）滿足如下關(guān)系 第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2,sup1pRzdFzQkppklQ(z,)為損失函數(shù)2/20/202236結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則下，分類器的設(shè)計(jì)過程結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則下

21、，分類器的設(shè)計(jì)過程l設(shè)計(jì)過程包括以下兩方面任務(wù)：選擇一個(gè)適當(dāng)?shù)暮瘮?shù)子集，使之對問題來說有最優(yōu)的分類能力；從這個(gè)子集中選擇一個(gè)判別函數(shù)，使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小。l第一步相當(dāng)于模型選擇，而第二步則相當(dāng)于在確定了函數(shù)形式后的參數(shù)估計(jì)。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/202237尋找具體使用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的方法尋找具體使用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的方法l結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則比經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則更科學(xué)l最終目的是在經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍之間進(jìn)行折中l(wèi)實(shí)際上實(shí)施這一原則并不容易l如果能夠找到一種子集劃分方法，使得不必逐一計(jì)算就可以知道每個(gè)子集中所可能取得的最小經(jīng)驗(yàn)風(fēng)險(xiǎn)，l則兩步任務(wù)就可以分開

22、進(jìn)行：先選擇使置信范圍最小的子集，然后在其中選擇最優(yōu)函數(shù)。l結(jié)構(gòu)風(fēng)險(xiǎn)最小化的一般原則可以用不同的方法實(shí)現(xiàn)l支持向量機(jī)是其中最成功的一個(gè)通過固定經(jīng)驗(yàn)風(fēng)險(xiǎn)而最小化置信范圍實(shí)現(xiàn)的。第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.1 7.1概述概述2/20/2022387.2 線性分類器線性分類器第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202239線性分類器定義線性分類器定義 l在二類分類問題中,如果我們的學(xué)習(xí)函數(shù)選擇為：第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器)(bxiwsignyil這種學(xué)習(xí)函數(shù)稱為線性分類器2/20/202240考慮對下面情況的分類

23、考慮對下面情況的分類第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202241采樣線性分類，可以這樣采樣線性分類，可以這樣第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202242采樣線性分類，也可以這樣采樣線性分類，也可以這樣Copyright 2001, 2003, Andrew W. Moore第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202243采樣線性分類，還可以這樣采樣線性分類，還可以這樣Copyright 2001, 2003, Andrew W. Moore第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí)

24、 7.2 7.2 線性分類器線性分類器2/20/202244分類超平面分類超平面l有訓(xùn)練集： (xi, yi), i=1,2,N; yi+1,-1l如果分類函數(shù)y=wx+b，能夠正確訓(xùn)練集l超平面（Hyperplane）: wx+b=0l稱為分類超平面第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202245分類間隔分類間隔l樣本點(diǎn)(xi, yi),到超平面H的函數(shù)間隔：yi (w xi+b) l幾何間隔: 只需換成歸一化函數(shù)(w/|w|，b/|w|)l分類間隔（樣本集到分類超平面的間隔）:樣本集中所有點(diǎn)到分類超平面間隔（幾何間隔）中的最小值第第七七章機(jī)器學(xué)習(xí)章機(jī)

25、器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202246感知機(jī)算法感知機(jī)算法第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器l給定線性可分樣集S，學(xué)習(xí)率R+lW0=0, b0=0,k;lR=max |xi|;ldol k=0;l for(i=1;in;i+)l if (yi(wk xi+bk)0)l wk+1=wk+ yi xi;l bk+1=bk+ yi R2;l k+;l while(k0)2/20/202247分類間隔與誤分次數(shù)的關(guān)系分類間隔與誤分次數(shù)的關(guān)系 l在采樣感知機(jī)算法時(shí)，在采樣感知機(jī)算法時(shí)，l若分類間隔=，R=max |xi| i=1,.,n，則：第

26、第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器l誤分次數(shù)一定程度上代表分類器的誤差 l分類間隔越大的解，它的誤差上界越小。l最大化分類間隔成了訓(xùn)練階段的目標(biāo)22R誤分次數(shù)2/20/202248最優(yōu)分類面最優(yōu)分類面l要求分類面能將兩類正確分開(訓(xùn)練錯(cuò)誤率為0),l且使分類間隔最大第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器2/20/202249固定斜率時(shí)，最大間隔分固定斜率時(shí)，最大間隔分類面的導(dǎo)出類面的導(dǎo)出l設(shè)過兩類中最靠近分類面的點(diǎn)的線分別為：w x+b = k1 l1w x+b = k2 l2l平行移動分類面，使：K1= k2 = kl令w= w/k,

27、 b= b/k, 則l1, l2 變?yōu)椋簑 x+b = 1 w x+b = 1l分類面則為：w x+b = 0第第七七章機(jī)器學(xué)習(xí)章機(jī)器學(xué)習(xí) 7.2 7.2 線性分類器線性分類器wx+b1wx+b非線性分劃代價(jià)：2維空間內(nèi)積6維空間內(nèi)積非線性分類非線性分類2/20/202266為此，引進(jìn)函數(shù)有211222222112211221122( ,)( 1) 12 2 2 ijijijijijijijijijK x xxxxxxxxxxxxxxxxx 比較(2)和(3)，可以發(fā)現(xiàn)2( ,)() 1)ijijK x xxx(3)2( ( )()( ,)() 1)ijijijxxK x xx x這是一個(gè)重要

28、的等式，提示6維空間中的內(nèi)積可以通過計(jì)算 中2維空間中的內(nèi)積 得到。( ( )()ijxx( ,)ijK x x()ijx x非線性分類非線性分類2/20/202267實(shí)現(xiàn)非線性分類的思想實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù) ，一旦選定了函數(shù)，就可以求解最優(yōu)化問題2( ,)() 1)ijijK x xxx( ,)ijK x x( )x111l1i1min ,2. . 0 0,1,lllijijijjijjiiiy yK x xstyC il *1(,)Tl得 ，而決策函數(shù)2/20/202268*1(

29、 )sgn( , )liiiif xyK x xb決策函數(shù)其中*1( ,) |0ljiiijjibyyK x xjjC ( , ) iK x x 核函數(shù)實(shí)現(xiàn)非線性分類的思想實(shí)現(xiàn)非線性分類的思想2/20/202269設(shè) 是 中的一個(gè)子集。稱定義在 上的函數(shù) 是核函數(shù)(正定核或核)，如果存在著從 到某一個(gè)空間 的映射 :( )xx nR ( ,)K x xHilbert使得( ,)( ( )( )K x xxx其中 表示 中的內(nèi)積() Hilbert核函數(shù)核函數(shù)(核或正定核核或正定核)定義定義2/20/202270l多項(xiàng)式內(nèi)核l徑向基函數(shù)內(nèi)核RBFlSigmoind內(nèi)核( ,)()qiiK x x

30、x xc22|( ,)expiixxK x x( ,)tanh( ()iiK x xx xc目前研究最多的核函數(shù)主要有三類：得到q 階多項(xiàng)式分類器每個(gè)基函數(shù)中心對應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動確定包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動確定核函數(shù)的選擇核函數(shù)的選擇2/20/202271多項(xiàng)式內(nèi)核多項(xiàng)式內(nèi)核The kind of kernel represents the inner product of two vector(point) in a feature space of dimension.For exampledyxyxK),(ddn12/20/202272Ed

31、gar Osuna(Cambridge,MA)等人在等人在IEEE NNSP97發(fā)發(fā)表了表了An Improved Training Algorithm for Support Vector Machines ,提出了提出了SVM的分解算法，即將原問題分的分解算法，即將原問題分解為若干個(gè)子問題，按照某種迭代策略，通過反復(fù)求解子解為若干個(gè)子問題，按照某種迭代策略，通過反復(fù)求解子問題，最終使得結(jié)果收斂于原問題的最優(yōu)解。問題，最終使得結(jié)果收斂于原問題的最優(yōu)解。傳統(tǒng)的利用二次型優(yōu)化技術(shù)解決對偶問題時(shí)：傳統(tǒng)的利用二次型優(yōu)化技術(shù)解決對偶問題時(shí)：n 需要計(jì)算存儲核函數(shù)矩陣。當(dāng)樣本點(diǎn)數(shù)較大時(shí)，需要很需要計(jì)算存

32、儲核函數(shù)矩陣。當(dāng)樣本點(diǎn)數(shù)較大時(shí)，需要很大的存儲空間。例如：當(dāng)樣本點(diǎn)超過大的存儲空間。例如：當(dāng)樣本點(diǎn)超過4000時(shí)，存儲核函數(shù)時(shí)，存儲核函數(shù)矩陣就需要多達(dá)矩陣就需要多達(dá)128兆內(nèi)存；兆內(nèi)存；n SVM在二次型尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，通常在二次型尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，通常尋優(yōu)算法占用了算法時(shí)間的主要部分。尋優(yōu)算法占用了算法時(shí)間的主要部分。SVMSVM尋優(yōu)尋優(yōu)算法算法2/20/202273考慮去掉Lagrange乘子等于零的訓(xùn)練樣本不會影響原問題的解，采用一部分樣本構(gòu)成工作樣本集進(jìn)行訓(xùn)練，移除其中的非支持向量，并把訓(xùn)練結(jié)果對剩余樣本進(jìn)行檢驗(yàn)，將不符合KKT條件的樣本與本次結(jié)果的支持

33、向量合并成為一個(gè)新的工作集。然后重新訓(xùn)練，如此重復(fù)獲得最優(yōu)結(jié)果。例如：基于這種思路的 算法。根據(jù)子問題的劃分和迭代策略的不同，大致分為：1. 塊算法(Chunking Algorithm)：SMOSVM尋優(yōu)尋優(yōu)算法算法2/20/202274SMO使用了塊與分解技術(shù)，而SMO算法則將分解算法思想推向極致，每次迭代僅優(yōu)化兩個(gè)點(diǎn)的最小子集，其威力在于兩個(gè)數(shù)據(jù)點(diǎn)的優(yōu)化問題可以獲得解析解，從而不需要將二次規(guī)劃優(yōu)化算法作為算法一部分。盡管需要更多的迭代才收斂，但每個(gè)迭代需要很少的操作，因此算法在整體上的速度有數(shù)量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內(nèi)存中存儲核矩陣。塊算法(Chunkin

34、g Algorithm)：SVM尋優(yōu)尋優(yōu)算法算法2/20/202275SMO算法每次迭代時(shí)，在可行的區(qū)域內(nèi)選擇兩點(diǎn)，最大化目標(biāo)函數(shù)，從而優(yōu)化兩個(gè)點(diǎn)的最小子集。無論何時(shí)，當(dāng)一個(gè)乘子被更新時(shí)，調(diào)整另一個(gè)乘子來保證線性約束條件成立，保證解不離開可行區(qū)域。每步SMO選擇兩個(gè)參數(shù)優(yōu)化，其他參數(shù)固定，可以獲得解析解。盡管需要更多的迭代才收斂，但每個(gè)迭代需要很少的操作，因此算法在整體上的速度有數(shù)量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內(nèi)存中存儲核矩陣。SVM尋優(yōu)尋優(yōu)算法算法2/20/202276SVM尋優(yōu)尋優(yōu)算法算法類別名稱測試樣本數(shù)錯(cuò)誤分類數(shù)準(zhǔn)確度（%）政治146497.26軍事83010

35、0經(jīng)濟(jì)137397.81法律32293.75農(nóng)業(yè)106298.11體育90198.89衛(wèi)生34197.06工業(yè)87297.70科技111298.20交通40197.50生活91198.90宗教30100天氣24291.67合計(jì)9842197.872/20/202277SMO算法核緩存算法SMO算法在每次迭代只選擇兩個(gè)樣本向量優(yōu)化目標(biāo)函數(shù)，不需要核矩陣。雖然沒有核矩陣操作，但仍需要計(jì)算被選向量和訓(xùn)練集中所有樣本向量的核函數(shù)，計(jì)算次數(shù)為2n（n為訓(xùn)練集中的樣本數(shù)）。如果訓(xùn)練集中的樣本選取有誤，在噪聲比較多的情況下，收斂會很慢，迭代次數(shù)很多，則核函數(shù)的計(jì)算量也是非?？捎^的，SMO 算法的優(yōu)點(diǎn)就完成失

36、去了。同時(shí)，考慮到文本分類的文本向量一般維數(shù)比較大，核函數(shù)的計(jì)算將會非常耗時(shí)，尤其在高價(jià)多項(xiàng)式核和高斯核等核函數(shù)的計(jì)算中表現(xiàn)更加明顯。SVM尋優(yōu)尋優(yōu)算法算法2/20/202278SMO算法核緩存算法在內(nèi)存中為SMO算法核函數(shù)開辟n行m列的核矩陣空間。其中：n為訓(xùn)練集中的樣本數(shù)；m是為可調(diào)節(jié)參數(shù)，根據(jù)實(shí)際的內(nèi)存大小進(jìn)行調(diào)整，每列存放訓(xùn)練集中某個(gè)樣本向量與訓(xùn)練集中所有樣本向量的核函數(shù)計(jì)算結(jié)果列表。在核矩陣列頭生成m個(gè)節(jié)點(diǎn)的雙向循環(huán)鏈表隊(duì)列，每個(gè)節(jié)點(diǎn)指向核矩陣的列，通過雙向循環(huán)鏈表隊(duì)列實(shí)現(xiàn)核矩陣中的核函數(shù)列喚入喚出操作。同時(shí)，為了實(shí)現(xiàn)樣本向量的核函數(shù)列的快速查找，為每個(gè)訓(xùn)練樣本向量設(shè)計(jì)了快速索引列表

37、，通過索引列表判斷該訓(xùn)練樣本向量的核函數(shù)列是否在核矩陣中，并確定在哪一列。SVM尋優(yōu)尋優(yōu)算法算法2/20/202279SVM尋優(yōu)尋優(yōu)算法算法l選擇一個(gè)訓(xùn)練集，通過調(diào)整核緩沖參數(shù)的大小，記錄不同核緩存大小情況下訓(xùn)練時(shí)間，結(jié)果如下表：核緩存大小(Mb)訓(xùn)練樣本數(shù)核矩陣迭代次數(shù)訓(xùn)練時(shí)間(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407

38、261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:122/20/202280通過引入核緩存機(jī)制，有效的改進(jìn)了通過引入核緩存機(jī)制，有效的改進(jìn)了SMOSMO算法，提算法，提高了文本分類的訓(xùn)練速度。在核緩存機(jī)制中采用高了文本分類的訓(xùn)練速度。在核緩存機(jī)制中采用簡單的簡單的hashhash查找算法和隊(duì)列查找算法和隊(duì)列FILOFILO算法，有效提高算法，有效提高了核矩陣查找和喚入喚出操作的效率。設(shè)置核矩了核

39、矩陣查找和喚入喚出操作的效率。設(shè)置核矩陣列參數(shù)，通過調(diào)節(jié)列參數(shù)，可以靈活的根據(jù)系陣列參數(shù)，通過調(diào)節(jié)列參數(shù)，可以靈活的根據(jù)系統(tǒng)運(yùn)行情況調(diào)整訓(xùn)練的時(shí)間和空間開銷，避免因統(tǒng)運(yùn)行情況調(diào)整訓(xùn)練的時(shí)間和空間開銷，避免因系統(tǒng)空間開銷過大使系統(tǒng)運(yùn)行效率下降，反而影系統(tǒng)空間開銷過大使系統(tǒng)運(yùn)行效率下降，反而影響訓(xùn)練速度。響訓(xùn)練速度。SVM尋優(yōu)尋優(yōu)算法算法2/20/202281活動向量集選擇算法 當(dāng)訓(xùn)練樣本數(shù)非常大的時(shí)候，如果系統(tǒng)能夠提供的核緩沖當(dāng)訓(xùn)練樣本數(shù)非常大的時(shí)候，如果系統(tǒng)能夠提供的核緩沖大小很有限，那么能夠同時(shí)保存在核緩沖中訓(xùn)練樣本的核大小很有限，那么能夠同時(shí)保存在核緩沖中訓(xùn)練樣本的核函數(shù)數(shù)目在訓(xùn)練樣本數(shù)中

40、所占比例將非常的小。在訓(xùn)練過函數(shù)數(shù)目在訓(xùn)練樣本數(shù)中所占比例將非常的小。在訓(xùn)練過程中，訓(xùn)練樣本在核緩沖中的核函數(shù)命中率將顯著下降，程中，訓(xùn)練樣本在核緩沖中的核函數(shù)命中率將顯著下降，導(dǎo)致核緩沖中的核函數(shù)被頻繁的喚入喚出，而每執(zhí)行一次導(dǎo)致核緩沖中的核函數(shù)被頻繁的喚入喚出，而每執(zhí)行一次喚入喚出操作將引起系統(tǒng)重新計(jì)算訓(xùn)練樣本的核函數(shù)，核喚入喚出操作將引起系統(tǒng)重新計(jì)算訓(xùn)練樣本的核函數(shù)，核緩存的作用被很大程度的削弱了。如果出現(xiàn)這樣的情況，緩存的作用被很大程度的削弱了。如果出現(xiàn)這樣的情況，要么增加系統(tǒng)的存儲空間；要么減少訓(xùn)練樣本數(shù)，才能提要么增加系統(tǒng)的存儲空間；要么減少訓(xùn)練樣本數(shù)，才能提高系統(tǒng)的訓(xùn)練速度。為解

41、決訓(xùn)練樣本數(shù)多，系統(tǒng)內(nèi)存空間高系統(tǒng)的訓(xùn)練速度。為解決訓(xùn)練樣本數(shù)多，系統(tǒng)內(nèi)存空間小的矛盾，本文通過活動向量集選擇算法，比較好地解決小的矛盾，本文通過活動向量集選擇算法，比較好地解決了這個(gè)問題。了這個(gè)問題。 SVM尋優(yōu)尋優(yōu)算法算法2/20/202282活動向量集選擇算法 算法的主要思想是：定期檢查訓(xùn)練樣本集，在收斂前預(yù)算法的主要思想是：定期檢查訓(xùn)練樣本集，在收斂前預(yù)先確定訓(xùn)練樣本集中一些邊界上的點(diǎn)（先確定訓(xùn)練樣本集中一些邊界上的點(diǎn)（alpha=0alpha=0，或者，或者alpha=Calpha=C）是否以后不再被啟發(fā)式選擇，或者不再被判定為）是否以后不再被啟發(fā)式選擇，或者不再被判定為最有可能違例

42、，如果存在這樣的點(diǎn)，將它們從訓(xùn)練樣本集最有可能違例，如果存在這樣的點(diǎn)，將它們從訓(xùn)練樣本集中剔除出去，減少參加訓(xùn)練的樣本數(shù)。該算法基于如下的中剔除出去，減少參加訓(xùn)練的樣本數(shù)。該算法基于如下的認(rèn)識：經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為認(rèn)識：經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為0 0，該點(diǎn)被當(dāng)前估計(jì)的支持向量集所確定的超平面區(qū)分得很開，該點(diǎn)被當(dāng)前估計(jì)的支持向量集所確定的超平面區(qū)分得很開，即使以后支持向量集發(fā)生變化，該點(diǎn)也不會是最靠近超平即使以后支持向量集發(fā)生變化，該點(diǎn)也不會是最靠近超平面的點(diǎn)，則可以確定該樣本不是支持向量；經(jīng)過多次迭代面的點(diǎn)，則可以確定該樣本不是支持向量；經(jīng)過多次迭代

43、后，如果樣本的拉格朗日乘子一直為非常大的后，如果樣本的拉格朗日乘子一直為非常大的C C常數(shù)，即使常數(shù)，即使以后支持向量集發(fā)生變化，該點(diǎn)也不會遠(yuǎn)離超平面，則可以后支持向量集發(fā)生變化，該點(diǎn)也不會遠(yuǎn)離超平面，則可以確定該樣本是上邊界處的支持向量以確定該樣本是上邊界處的支持向量SVM尋優(yōu)尋優(yōu)算法算法2/20/202283活動向量集選擇算法 這樣就可以在這樣就可以在SMO算法收斂前，提前將邊界上的點(diǎn)從訓(xùn)算法收斂前，提前將邊界上的點(diǎn)從訓(xùn)練樣本集中剔除，逐漸縮小參加訓(xùn)練的活動樣本集，從而練樣本集中剔除，逐漸縮小參加訓(xùn)練的活動樣本集，從而減少減少SMO算法對核緩存空間的要求，提高訓(xùn)練速度。算法對核緩存空間的要

44、求，提高訓(xùn)練速度。訓(xùn)練開始前，訓(xùn)練活動集樣本初始化為全部訓(xùn)練樣本。每訓(xùn)練開始前，訓(xùn)練活動集樣本初始化為全部訓(xùn)練樣本。每經(jīng)過一定次數(shù)的迭代（比如迭代經(jīng)過一定次數(shù)的迭代（比如迭代1000次），如果算法還沒次），如果算法還沒有收斂，應(yīng)檢查活動集中的向量，檢查是否有訓(xùn)練樣本可有收斂，應(yīng)檢查活動集中的向量，檢查是否有訓(xùn)練樣本可以不參加迭代運(yùn)算。以不參加迭代運(yùn)算。檢查完當(dāng)前活動向量集中所有樣本后，產(chǎn)生了新的活動向檢查完當(dāng)前活動向量集中所有樣本后，產(chǎn)生了新的活動向量集。如果新的活動向量集的樣本數(shù)減少一成以上（含一量集。如果新的活動向量集的樣本數(shù)減少一成以上（含一成），則可以收縮當(dāng)前活動向量集，用新的活動向量

45、集替成），則可以收縮當(dāng)前活動向量集，用新的活動向量集替換當(dāng)前活動向量集。當(dāng)活動向量集的樣本數(shù)減少到一定的換當(dāng)前活動向量集。當(dāng)活動向量集的樣本數(shù)減少到一定的程度，對核緩存空間的要求不是很大的時(shí)候，繼續(xù)減少訓(xùn)程度，對核緩存空間的要求不是很大的時(shí)候，繼續(xù)減少訓(xùn)練樣本對訓(xùn)練速度的提高就非常有限了，這時(shí)就沒有必要練樣本對訓(xùn)練速度的提高就非常有限了，這時(shí)就沒有必要再減少訓(xùn)練樣本了。再減少訓(xùn)練樣本了。SVM尋優(yōu)尋優(yōu)算法算法2/20/202284將工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，將工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，迭代過程選擇一種合適的換入換出策略，將剩余樣本中的迭代過程選擇一種

46、合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進(jìn)行等量交換，即使支持向一部分與工作樣本集中的樣本進(jìn)行等量交換，即使支持向量的個(gè)數(shù)超過工作樣本集的大小，也不改變工作樣本集的量的個(gè)數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進(jìn)行優(yōu)化。規(guī)模，而只對支持向量中的一部分進(jìn)行優(yōu)化。例如例如: 算法算法2. 固定工作樣本集固定工作樣本集 (Osuna et al.)：LightSVMSVM尋優(yōu)尋優(yōu)算法算法2/20/202285SVM applicationslPattern recognitionFeatures: words countslDNA array e

47、xpression data analysisFeatures: expr. levels in diff. conditionslProtein classificationoFeatures: AA composition2/20/202286Handwritten Digits Recognition2/20/202287Applying SVMs to Face DetectionlThe SVM face-detection system1. Rescale the 1. Rescale the input image input image several timesseveral

48、 times2. Cut 19x19 2. Cut 19x19 window patterns window patterns out of the out of the scaled imagescaled image3. Preprocess the 3. Preprocess the window using masking, window using masking, light correction and light correction and histogram equalizationhistogram equalization4. Classify the 4. Class

49、ify the pattern using pattern using the SVMthe SVM5. If the class corresponds 5. If the class corresponds to a face, draw a rectangle to a face, draw a rectangle around the face in the around the face in the output image.output image.2/20/202288Applying SVMs to Face DetectionlExperimental results on

50、 static imagesSet A: 313 high-quality, same number of facesSet B: 23 mixed quality, total of 155 faces2/20/202289Applying SVMs to Face DetectionlExtension to a real-time systemAn example An example of the skin of the skin detection detection module module implementeimplemented using d using SVMsSVMsFace Face Detection Detection on the PC-on the PC-based based Color Real Color Real Time Time SystemSystem2/20/202290References2/20/2022912/20/202292EBL的初始狀態(tài)的初始狀態(tài)一、一個(gè)目標(biāo)概念依賴與具體的應(yīng)用，可以是一個(gè)分類，要證明的定理，達(dá)到目標(biāo)的一個(gè)計(jì)劃，問題求解程序的啟發(fā)式信息等二、一個(gè)訓(xùn)練實(shí)例 目標(biāo)概念的實(shí)例三、領(lǐng)域知識用于解釋訓(xùn)練實(shí)