【正文】 征組合在一起時所得J值為最大，直到特征數(shù)增加到d為止，該過程可以描述為：設(shè)所有的特征集合為Q，假設(shè)有一個已有個特征的特征集 ，對每一個未入選特征 ( 即中的特征) 計算其準(zhǔn)則函數(shù)。另外，為了提高小樣本的識別率，也可以給他們賦予較高的懲罰系數(shù)。針對C－SVM算法不適合處理大規(guī)模問題的缺陷，RSVM算法通過限制支持向量的選擇范圍來控制每次解方程的規(guī)模，擅長處理海量數(shù)據(jù)或者支持向量多的數(shù)據(jù)。例如，針對C－SVM算法中唯－可以調(diào)節(jié)的參數(shù)C沒有直觀解釋，在實際應(yīng)用中很難選擇合適的值的缺陷，v－SVM算法中用參數(shù)v取代C，該參數(shù)可以控制支持向量的數(shù)目和誤差，也易選擇。隨著對支持向量機(jī)研究的深入，許多研究人員提出了－些針對標(biāo)準(zhǔn)支持向量機(jī)C－SVM的變形算法，如v－SVM、One－class SVM、RSVM(reduced SVM)、WSVM(weighted svM)和Ls－svM(reast－square SVM)等算法。這種算法不需要大的矩陣存儲空間，特別適合稀疏樣本，算法避開了復(fù)雜的數(shù)值求解優(yōu)化問題的過程。外層循環(huán)在某個乘子集合中遍歷，將第一個不滿足優(yōu)化條件的乘子作為第一個被優(yōu)化對象，一旦找到第一個乘子，內(nèi)層循環(huán)尋找第二個乘子，使其在當(dāng)前迭代步中具有最大的改變量。盡管由于工作集規(guī)模的減小，使得迭代次數(shù)增加了很多，但每次迭代所需時間非常短，因此整體訓(xùn)練時間大大降低。(SMO)Platt提出了SMO算法。因此，如果每一步至少加入一個不滿足KKT條件的樣本，一系列的二次規(guī)劃子問題可保證最后單調(diào)收斂。這是一種在內(nèi)存耗費和訓(xùn)練時間上的折衷方法。因此，該方法通過提前估計哪些變量最終可能成為非支持向量或邊界支持向量，從而在進(jìn)一步優(yōu)化過程中刪除這些變量，使優(yōu)化規(guī)模減少，進(jìn)而提高優(yōu)化速度。算法是基于Zoutendijk可行方向法，選擇一個最陡的可行解下降方向d，d僅含q個非零成員，對應(yīng)的q個變量組成工作集，使得每一步尋優(yōu)獲得更大的幅度，從而在當(dāng)前迭代中取得最大的進(jìn)展，進(jìn)而加快收斂速度。但是在該方法中工作集的確定采用了隨機(jī)選取的方法，這將大大影響算法的收斂速度，同時Osuna關(guān)于算法收斂性的證明是錯誤的。因此在每次迭代中，該方法首先確定B，然后求解關(guān)于B的子QP問題，而保持N中變量不變。 Osuna等人提出了分解算法的基本框架。然而，如果支持向量的數(shù)目本身就比較多，隨著算法迭代次數(shù)的增多，工作樣本集也會越來越大，算法依舊會變得十分復(fù)雜。實際求解QP問題中的Hessian矩陣的規(guī)模由Z*l下降到最多SV*SV，SV為支持向量的數(shù)目。具體的作法是，選擇一部分樣本構(gòu)成工作樣本集進(jìn)行訓(xùn)練，剔除其中的非支持向量，并用保留的支持向量對剩余樣本進(jìn)行檢驗，將不符合訓(xùn)練結(jié)果(一般是指違反KKT條件)的樣本(或其中的一部分)與本次結(jié)果的支持向量合并成為一個新的工作樣本集，然后重新訓(xùn)練。即去掉Lagrange乘子等于零的訓(xùn)練樣本，不會影響原問題的解。第一類是所謂的“塊算法”(Chunking Algorithm)，是郵Boser，Guyon，Vapnik提出的。根據(jù)子問題的劃分和迭代策略的不同，又可以大致分為兩類。SVM方法的訓(xùn)練運算速度和對內(nèi)存容量的大量占用是限制它的應(yīng)用的主要方面，近年來人們針對方法本身的特點提出了許多算法來解決對偶尋優(yōu)問題。在輸入空間數(shù)據(jù)不能通過線性函數(shù)分開，但在特征空間卻是線性可分的。2．線性不可分SVM在現(xiàn)實世界中，很多分類問題都是線性不可分的，也就是說在原來的樣本空間中無法找到一個最優(yōu)的線性分類函數(shù)，但是根據(jù)廣義最優(yōu)超平面的思想，可以設(shè)法通過非線性變換將原樣本空間的非線性問題轉(zhuǎn)化為另一個空間中的線性問題。C的值太大時，雖然此時對訓(xùn)練樣本的識別率高，SVM的分類學(xué)習(xí)性能很好(如果不出現(xiàn)過適應(yīng)的話)，但此時的泛化性能較低。從上面的分析知道，懲罰系數(shù)C可以控制SVM的泛化性能和錯分率之間的折衷。間隔越大，泛化能力越強(qiáng)，所以C越小，SVM泛化能力越強(qiáng)，但顯然這時SVM的分類準(zhǔn)確率要降低。最優(yōu)分類面是在線性可分的前提下討論的，如果某些訓(xùn)練樣本不能滿足式(38)的條件，可以在條件中增加一個松弛項和懲罰系數(shù)C，使(3－8)變成,i=1,2,…l 314求廣義的最優(yōu)分類面(最大限度將樣本分開，同時使分類間隔最大)的問題可以表示為下面的二次規(guī)劃問題 315約束性條件變?yōu)?314)，其中這里可看作訓(xùn)練樣本關(guān)于分離超平面的偏差，時問題變?yōu)榫€性可分情形，C為某個指定的常數(shù)，它實際上起控制對錯分樣本懲罰程度的作用，是錯分樣本的比例與算法復(fù)雜度之間的折衷。解上述問題后得到的最優(yōu)分類函數(shù)是： 313上式中的求和實際上只對支持向量進(jìn)行，因為非支持向量對應(yīng)的均為0。且根據(jù)KuhnTucker(KKT)條件，這個優(yōu)化問題的解需滿足,i=1,…l 311若為最優(yōu)解，則 312上式說明最優(yōu)分類面的權(quán)系數(shù)向量是訓(xùn)練樣本的線性組合。要求分類線對所有樣本正確分類，就是要求它滿足，i=1,2,…l 38滿足上述條件(38)，并且使最小的分類面就叫做最優(yōu)分類面，過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面HH2上的訓(xùn)練樣本點就稱作支持向量(support vector)，因為這些點唯一的確定了一個最優(yōu)的分類面H，它們“支持”了最優(yōu)分類面，支持向量機(jī)由此得名。n維空間中線性判別函數(shù)的一般形式為，其中x是輸入向量，w是權(quán)值向量，b是閥值，分類線方程為。在問題的解決過程中，基于Mercer核的展開定理，通過升維和線性化，使得可用線性學(xué)習(xí)機(jī)解決非線性問題和回歸問題。支持向量機(jī)的主要思想是建立一個作為決策面的超平面，使得正類和反類能夠很好地分開，并且使隔離邊緣最大。所謂最優(yōu)分類線就是要求分類線不但能將兩類無錯誤的分開(訓(xùn)練錯誤率為0)，而且要使兩類的分類空隙最大(推廣性好，對未來樣本錯分的可能性小)。1．線性可分SVMSVM方法是從線性可分情況下的最優(yōu)分類面(Optimal Hyper plane)提出的。分類其實就是對樣本相似性及相似程度的判斷。因為從某種意義上它可以表示成類似神經(jīng)網(wǎng)絡(luò)的形式，支持向量機(jī)在起初也曾被叫做支持向量網(wǎng)絡(luò)。支持向量機(jī)方法是統(tǒng)計學(xué)習(xí)理論中最年輕的部分，其主要內(nèi)容在1992年至1995年間才基本完成，目前仍處在不斷發(fā)展階段。(4)新的準(zhǔn)則的實現(xiàn)方法(算法)—支持向量機(jī)。其主要內(nèi)容包括以下四個方面：(1)經(jīng)驗風(fēng)險最小化準(zhǔn)則下統(tǒng)計學(xué)習(xí)一致性的條件—學(xué)習(xí)理論的關(guān)鍵定理：(2)經(jīng)驗風(fēng)險和實際風(fēng)險之間的關(guān)系—推廣性的界。與傳統(tǒng)統(tǒng)計學(xué)相比，統(tǒng)計學(xué)習(xí)理論是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論，該理論針對小樣本統(tǒng)計問題建立了一套新的理論體系，在這種體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸進(jìn)性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結(jié)果。目前一種基于LevenbergMarquardt優(yōu)化算法的的BP神經(jīng)網(wǎng)絡(luò)在部分應(yīng)用領(lǐng)域得到了一些不錯的應(yīng)用。原因就是在追求經(jīng)驗風(fēng)險最小化的過程中，我們用一個復(fù)雜的模型去擬合現(xiàn)有的數(shù)據(jù)，結(jié)果使得對未知樣本的推廣能力降低，這就是過擬合，或叫過學(xué)習(xí)現(xiàn)象。用經(jīng)驗風(fēng)險的最小值代替期望風(fēng)險的最小值，就是所謂的經(jīng)驗風(fēng)險最小化原則。這其實是基于樣本數(shù)趨于無限大這樣一個假設(shè)的。因此人們根據(jù)概率論中大數(shù)定理的思想，采用算數(shù)平均代替式中使用的數(shù)學(xué)期望，即用： 36來逼近式(32)定義的期望風(fēng)險。(l)模式識別問題中的損失函數(shù)(以兩類問題為例)可以定義為： 33(2)函數(shù)擬合問題中的損失函數(shù)可以定義為： 34(3)概率密度估計問題，學(xué)習(xí)的目的是根據(jù)訓(xùn)練樣本確定x的概率分布。可以一般地表示為：變量y與x存在一定的未知依賴關(guān)系，即遵循某一未知的聯(lián)合概率F(x，y)(x與y之間的確定性關(guān)系可以看作是其特例)，機(jī)器學(xué)習(xí)問題就是根據(jù)l個獨立同分布觀測樣本：，…… 31在一組函數(shù)中求一個最優(yōu)的函數(shù)，使預(yù)測的期望風(fēng)險： 32最小，其中， 稱作預(yù)測函數(shù)集，w為函數(shù)的廣義參數(shù)，所以可以表示任何函數(shù)集，為由于用對y進(jìn)行預(yù)測而造成的損失，不同類型的學(xué)習(xí)問題有不同的損失函數(shù)，預(yù)測函數(shù)也稱作學(xué)習(xí)函數(shù)、學(xué)習(xí)模型或?qū)W習(xí)機(jī)器。由于其出色的學(xué)習(xí)性能，該技術(shù)已經(jīng)成為機(jī)器學(xué)習(xí)界的研究熱點，隨著研究的深入，SVM己由最初的二分類應(yīng)用，推廣到多分類(multi class)、多類別(multi label)、函數(shù)擬合、概率密度估計等應(yīng)用中，并展現(xiàn)了良好的學(xué)習(xí)和泛化性能。統(tǒng)計學(xué)習(xí)理論 (Statistical Learning Theory，簡稱SLT)是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論。用獲得的規(guī)律不僅可以解釋己知的實例，而且能夠?qū)ξ粗默F(xiàn)象做出正確的預(yù)測和判斷，這種能力稱為推廣能力，或是泛化能力。這種方法也要利用大量的訓(xùn)練樣本，建立非線性模型，雖然克服了傳統(tǒng)參數(shù)估計方法的困難，使人工神經(jīng)網(wǎng)絡(luò)方法已在很多實際的問題中取得了驚人的成功，但是這種方法缺乏一種統(tǒng)一的數(shù)學(xué)理論，基于經(jīng)驗風(fēng)險最小化原則(Empirical Risk Minimization，簡稱ERM)，容易陷入局部極小，而非全局最小，并出現(xiàn)過度擬合的現(xiàn)象，導(dǎo)致對未來數(shù)據(jù)預(yù)測的這種推廣能力差。所以一些理論上很優(yōu)秀的學(xué)習(xí)方法實際中表現(xiàn)卻可能不盡人意。因此只有當(dāng)采樣數(shù)據(jù)趨于無窮時，參數(shù)方法的訓(xùn)練結(jié)果才趨于真實的模型。但是，在處理大量的實際預(yù)測問題時，常常不知道模型的結(jié)構(gòu)形式。在這種方法中，是在已知參數(shù)結(jié)構(gòu)形式的前提下，通過訓(xùn)練數(shù)據(jù)，預(yù)測各參數(shù)的值。第三章 統(tǒng)計學(xué)習(xí)理論與支持向量機(jī)基于數(shù)據(jù)的機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中的重要方面，研究從觀測數(shù)據(jù)(樣本)出發(fā)尋找規(guī)律，利用這些規(guī)律對未來數(shù)據(jù)進(jìn)行預(yù)測。在入侵檢測系統(tǒng)分類器上,支持向量機(jī)的應(yīng)用也很廣泛。其中，支持向量機(jī)以其出色的學(xué)習(xí)性能 ,已經(jīng)成為繼神經(jīng)網(wǎng)絡(luò)之后新的研究熱點。與過濾器模式的流程圖相比，封裝器在評估特征子集時采用了與分類器相關(guān)的評價函數(shù) A，而不是無關(guān)評價函數(shù) M。圖21 基于過濾器模式的檢測系統(tǒng)流程基于封裝器模型的檢測系統(tǒng)詳細(xì)流程如圖22 所示。圖中出現(xiàn)的函數(shù)定義為 Generate(D)，根據(jù)數(shù)據(jù)集 D 生成一個特征子集 S；Eval(S，D，M)，根據(jù)數(shù)據(jù)集 D、評價函數(shù)M，對特征子集S進(jìn)行評估，返回γ；Build(TrD，)，通過TrD和最優(yōu)特征子集，建立分類器C；Test(TeD，C)，通過測試集 TeD 檢測分類器 C 的性能。一般來說,過濾器的特征選擇速度比較快,選擇的結(jié)果與采用的學(xué)習(xí)算法沒有關(guān)系,選擇效果比較差；封裝器特征選擇速度慢,需要交叉認(rèn)證和大量的計算資源,選擇結(jié)果依賴于采用的分類算法,選擇效果一般較好。特征選擇有兩種模型:過濾器和封裝器。根據(jù)評估函數(shù)與分類器的關(guān)系，特征選擇方法分成過濾器模式和封裝器模式兩種。特征選擇可以看作是一個優(yōu)化問題，其關(guān)鍵是建立一種評估標(biāo)準(zhǔn)來區(qū)分哪些特征組合有助于分類，哪些特征組合存在冗余性、部分或者完全無關(guān)。綜上所述，根據(jù)合理的啟發(fā)式規(guī)則可以設(shè)計出非常實用的次優(yōu)搜索方法應(yīng)用于特征選擇算法。實際的每輪的l、r可以根據(jù)特征的統(tǒng)計特點來制定。該方法改變上述一系列算法固定l、r的基本做法。但操作較為復(fù)雜，難以制定實際規(guī)則加以利用。前面所有討論過的算法甚至可以看作是它的特例算法。(7)廣義增l去r選擇方法。從一個完全特征集開始，依次刪除r個特征，再增加l個特征直到獲得滿足要求個數(shù)的特征。這種方法消除嵌套問題，因為某一步獲得的特征集不一定是下一步特征集的子集。這種方法允許在特征選擇過程中進(jìn)行回溯，如果l r，則該算法是自下而上的方法。不足之處在于有的時候，特征消除操作進(jìn)行太快，容易丟失重要的變量，導(dǎo)致找不到最優(yōu)的特征組。該方法是SBS算法的加速算法，它根據(jù)準(zhǔn)則函數(shù)在算法的每個循環(huán)當(dāng)中，一次性刪除一定個數(shù)的無用特征。該方法的優(yōu)勢在于充分考慮特征之間的統(tǒng)計相關(guān)特性，因而在采用同樣合理的準(zhǔn)則函數(shù)的時候，它的實際計算性能和算法的魯棒性要大大優(yōu)于SFS算法。該方法是一種自上而下的方法。SFS法每次只增加一個特征，它未考慮入選特征之間的統(tǒng)計相關(guān)性，而GSFS法可以克服這個缺點，當(dāng)然此時計算量變大了，相應(yīng)地，它比SFS法更可靠，此外它也無法剔除已入選的特征。(3)廣義序列前向選擇方法(Generalized Sequential Forward Selection，GSFS)。先把所需要的特征集合初始化為一個空集，每次向特征集合中增加一個特征，當(dāng)所需要的特征集合達(dá)到要求時所得到的特征集合作為算法運行的結(jié)果。(2)序列前向選擇方法(S