人工智能7第七章機器學習

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

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

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

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

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

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

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

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

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

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

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

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

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

14、最小化原則下的學習一致性問題和一致性收斂的速度l定義一些指標：指示函數(shù)集的熵（VC熵）和生長函數(shù)退火的VC熵VC維第第七七章機器學習章機器學習 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ù)能對這組樣本實現(xiàn)的不同種分類數(shù)目：N(Zn)l隨機熵：H(Zn)=In(N(Zn) (函數(shù)集在這組樣本上的)l指示函數(shù)集的熵（VC熵）：H(n)=E(In(N(Zn) (與樣本無關)l由于VC熵與樣本的分布有關l生長函數(shù)： G(n)=In(max(N(Zn) 第第七七章機器

15、學習章機器學習 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第第七七章機器學習章機器學習 7.1 7.1概述概述2/20/202226學習過程一致收斂的充分必要條件l函數(shù)集學習過程一致收斂的充分必要條件是對任意的樣本分布， 都有l(wèi)im G(n)/n = 0這時學習過程收斂速度一定是快的l函數(shù)集學習收斂速度快的充分必要條件是lim Hann(n)/n = 0 第第七七章機器學習章機器學習 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是一個整數(shù)l可以看出，生長函數(shù)要么是線性的，要么以參數(shù)為h 的對數(shù)函數(shù)為上界。第第七七章機器學習章機器學習 7.1 7.1概述概述G(n)nIn2nhhIn(n/h+1)2/20/202228VC維l函數(shù)集能夠把樣本集打散：函數(shù)集中的函數(shù)有2h種形式把h個樣本的樣本集分為兩類，l指示函數(shù)集的VC維：函數(shù)集能夠打散的最大樣本集的h如果指示函數(shù)集的生長函數(shù)是線性的，其VC維為無窮大如果生長函數(shù)以參數(shù)為h的對數(shù)函數(shù)為上界，則函數(shù)集的VC維是hlVC維是對由學習機器實現(xiàn)的分類函數(shù)族的容量或表示能力的測度。第

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

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

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

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

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

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

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

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

25、器學習 7.2 7.2 線性分類器線性分類器2/20/202246感知機算法感知機算法第第七七章機器學習章機器學習 7.2 7.2 線性分類器線性分類器l給定線性可分樣集S，學習率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ù)的關系分類間隔與誤分次數(shù)的關系 l在采樣感知機算法時，在采樣感知機算法時，l若分類間隔=，R=max |xi| i=1,.,n，則：第

26、第七七章機器學習章機器學習 7.2 7.2 線性分類器線性分類器l誤分次數(shù)一定程度上代表分類器的誤差 l分類間隔越大的解，它的誤差上界越小。l最大化分類間隔成了訓練階段的目標22R誤分次數(shù)2/20/202248最優(yōu)分類面最優(yōu)分類面l要求分類面能將兩類正確分開(訓練錯誤率為0),l且使分類間隔最大第第七七章機器學習章機器學習 7.2 7.2 線性分類器線性分類器2/20/202249固定斜率時，最大間隔分固定斜率時，最大間隔分類面的導出類面的導出l設過兩類中最靠近分類面的點的線分別為：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第第七七章機器學習章機器學習 7.2 7.2 線性分類器線性分類器wx+b1wx+b非線性分劃代價：2維空間內(nèi)積6維空間內(nèi)積非線性分類非線性分類2/20/202266為此，引進函數(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這是一個重要

28、的等式，提示6維空間中的內(nèi)積可以通過計算 中2維空間中的內(nèi)積 得到。( ( )()ijxx( ,)ijK x x()ijx x非線性分類非線性分類2/20/202267實現(xiàn)非線性分類的思想實現(xià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ù)實現(xiàn)非線性分類的思想實現(xiàn)非線性分類的思想2/20/202269設 是 中的一個子集。稱定義在 上的函數(shù) 是核函數(shù)(正定核或核)，如果存在著從 到某一個空間 的映射 :( )xx nR ( ,)K x xHilbert使得( ,)( ( )( )K x xxx其中 表示 中的內(nèi)積() Hilbert核函數(shù)核函數(shù)(核或正定核核或正定核)定義定義2/20/202270l多項式內(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 階多項式分類器每個基函數(shù)中心對應一個支持向量，它們及輸出權值由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點數(shù)是由算法自動確定核函數(shù)的選擇核函數(shù)的選擇2/20/202271多項式內(nèi)核多項式內(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的分解算法，即將原問題分的分解算法，即將原問題分解為若干個子問題，按照某種迭代策略，通過反復求解子解為若干個子問題，按照某種迭代策略，通過反復求解子問題，最終使得結果收斂于原問題的最優(yōu)解。問題，最終使得結果收斂于原問題的最優(yōu)解。傳統(tǒng)的利用二次型優(yōu)化技術解決對偶問題時：傳統(tǒng)的利用二次型優(yōu)化技術解決對偶問題時：n 需要計算存儲核函數(shù)矩陣。當樣本點數(shù)較大時，需要很需要計算存

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

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

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

35、0經(jīng)濟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合計9842197.872/20/202277SMO算法核緩存算法SMO算法在每次迭代只選擇兩個樣本向量優(yōu)化目標函數(shù)，不需要核矩陣。雖然沒有核矩陣操作，但仍需要計算被選向量和訓練集中所有樣本向量的核函數(shù)，計算次數(shù)為2n（n為訓練集中的樣本數(shù)）。如果訓練集中的樣本選取有誤，在噪聲比較多的情況下，收斂會很慢，迭代次數(shù)很多，則核函數(shù)的計算量也是非常可觀的，SMO 算法的優(yōu)點就完成失

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

37、，通過索引列表判斷該訓練樣本向量的核函數(shù)列是否在核矩陣中，并確定在哪一列。SVM尋優(yōu)尋優(yōu)算法算法2/20/202279SVM尋優(yōu)尋優(yōu)算法算法l選擇一個訓練集，通過調(diào)整核緩沖參數(shù)的大小，記錄不同核緩存大小情況下訓練時間，結果如下表：核緩存大小(Mb)訓練樣本數(shù)核矩陣迭代次數(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通過引入核緩存機制，有效的改進了通過引入核緩存機制，有效的改進了SMOSMO算法，提算法，提高了文本分類的訓練速度。在核緩存機制中采用高了文本分類的訓練速度。在核緩存機制中采用簡單的簡單的hashhash查找算法和隊列查找算法和隊列FILOFILO算法，有效提高算法，有效提高了核矩陣查找和喚入喚出操作的效率。設置核矩了核

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

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

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

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

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

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

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

46、合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進行等量交換，即使支持向一部分與工作樣本集中的樣本進行等量交換，即使支持向量的個數(shù)超過工作樣本集的大小，也不改變工作樣本集的量的個數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進行優(yōu)化。規(guī)模，而只對支持向量中的一部分進行優(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)一、一個目標概念依賴與具體的應用，可以是一個分類，要證明的定理，達到目標的一個計劃，問題求解程序的啟發(fā)式信息等二、一個訓練實例 目標概念的實例三、領域知識用于解釋訓練實