【文章內(nèi)容簡介】 時，得到k(k ? 1)/2個分類結(jié)果，分類時采用一種投票策略，最后得票最多的類別即為該樣本的類別。第二章 支持向量機（SVM）原理 SVM的產(chǎn)生與發(fā)展支持向量機(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學習問題中。 支持向量機方法是建立在統(tǒng)計學習理論的VC 維理論和結(jié)構(gòu)風險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。自1995年Vapnik在統(tǒng)計學習理論的基礎(chǔ)上提出SVM作為模式識別的新方法之后，SVM一直倍受關(guān)注。同年，Vapnik和Cortes提出軟間隔(soft margin)SVM，通過引進松弛變量度量數(shù)據(jù)的誤分類(分類出現(xiàn)錯誤時大于0)，同時在目標函數(shù)中增加一個分量用來懲罰非零松弛變量(即代價函數(shù))，SVM的尋優(yōu)過程即是大的分隔間距和小的誤差補償之間的平衡過程；1996年，Vapnik等人又提出支持向量回歸 (Support Vector Regression，SVR)的方法用于解決擬合問題。SVR同SVM的出發(fā)點都是尋找最優(yōu)超平面，但SVR的目的不是找到兩種數(shù)據(jù)的分割平面，而是找到能準確預(yù)測數(shù)據(jù)分布的平面，兩者最終都轉(zhuǎn)換為最優(yōu)化問題的求解；1998年，Weston等人根據(jù)SVM原理提出了用于解決多類分類的SVM方法(MultiClass Support Vector Machines，MultiSVM)，通過將多類分類轉(zhuǎn)化成二類分類，將SVM應(yīng)用于多分類問題的判斷：此外，在SVM算法的基本框架下，研究者針對不同的方面提出了很多相關(guān)的改進算法。例如，Suykens提出的最小二乘支持向量機 (Least Square Support Vector Machine，LS—SVM)算法，Joachims等人提出的SVM1ight，張學工提出的中心支持向量機 (Central Support Vector Machine，CSVM)，Scholkoph和Smola基于二次規(guī)劃提出的vSVM等。此后，臺灣大學林智仁(Lin ChihJen)教授等對SVM的典型應(yīng)用進行總結(jié)，并設(shè)計開發(fā)出較為完善的SVM工具包，也就是LIBSVM(A Library for Support Vector Machines)。上述改進模型中，vSVM是一種軟間隔分類器模型，其原理是通過引進參數(shù)v，來調(diào)整支持向量數(shù)占輸入數(shù)據(jù)比例的下限，以及參數(shù)來度量超平面偏差，代替通常依靠經(jīng)驗選取的軟間隔分類懲罰參數(shù)，改善分類效果；LSSVM則是用等式約束代替?zhèn)鹘y(tǒng)SVM中的不等式約束，將求解QP問題變成解一組等式方程來提高算法效率；LIBSVM是一個通用的SVM軟件包，可以解決分類、回歸以及分布估計等問題，它提供常用的幾種核函數(shù)可由用戶選擇，并且具有不平衡樣本加權(quán)和多類分類等功能，此外，交叉驗證(cross validation)方法也是LIBSVM對核函數(shù)參數(shù)選取問題所做的一個突出貢獻；SVM1ight的特點則是通過引進縮水(shrinking)逐步簡化QP問題，以及緩存(caching)技術(shù)降低迭代運算的計算代價來解決大規(guī)模樣本條件下SVM學習的復(fù)雜性問題。 統(tǒng)計學習理論基礎(chǔ)與傳統(tǒng)統(tǒng)計學理論相比，統(tǒng)計學習理論(Statistical learning theory或SLT)是一種專門研究小樣本條件下機器學習規(guī)律的理論。該理論是針對小樣本統(tǒng)計問題建立起的一套新型理論體系，在該體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在有限信息條件下得到最優(yōu)結(jié)果。Vapnik等人從上世紀六、七十年代開始致力于該領(lǐng)域研究，直到九十年代中期，有限樣本條件下的機器學習理論才逐漸成熟起來，形成了比較完善的理論體系——統(tǒng)計學習理論。統(tǒng)計學習理論的主要核心內(nèi)容包括：(1)經(jīng)驗風險最小化準則下統(tǒng)計學習一致性條件；(2)這些條件下關(guān)于統(tǒng)計學習方法推廣性的界的結(jié)論；(3)這些界的基礎(chǔ)上建立的小樣本歸納推理準則；(4)發(fā)現(xiàn)新的準則的實際方法(算法) SVM原理SVM方法是20世紀90年代初Vapnik等人根據(jù)統(tǒng)計學習理論提出的一種新的機器學習方法，它以結(jié)構(gòu)風險最小化原則為理論基礎(chǔ)，通過適當?shù)剡x擇函數(shù)子集及該子集中的判別函數(shù)，使學習機器的實際風險達到最小，保證了通過有限訓練樣本得到的小誤差分類器，對獨立測試集的測試誤差仍然較小。支持向量機的基本思想是：首先，在線性可分情況下，在原空間尋找兩類樣本的最優(yōu)分類超平面。在線性不可分的情況下，加入了松弛變量進行分析，通過使用非線性映射將低維輸入空間的樣本映射到高維屬性空間使其變?yōu)榫€性情況，從而使得在高維屬性空間采用線性算法對樣本的非線性進行分析成為可能，并在該特征空間中尋找最優(yōu)分類超平面。其次，它通過使用結(jié)構(gòu)風險最小化原理在屬性空間構(gòu)建最優(yōu)分類超平面，使得分類器得到全局最優(yōu)，并在整個樣本空間的期望風險以某個概率滿足一定上界。其突出的優(yōu)點表現(xiàn)在：(1)基于統(tǒng)計學習理論中結(jié)構(gòu)風險最小化原則和VC維理論，具有良好的泛化能力，即由有限的訓練樣本得到的小的誤差能夠保證使獨立的測試集仍保持小的誤差。(2)支持向量機的求解問題對應(yīng)的是一個凸優(yōu)化問題，因此局部最優(yōu)解一定是全局最優(yōu)解。(3)核函數(shù)的成功應(yīng)用，將非線性問題轉(zhuǎn)化為線性問題求解。(4)分類間隔的最大化，使得支持向量機算法具有較好的魯棒性。由于SVM自身的突出優(yōu)勢，因此被越來越多的研究人員作為強有力的學習工具，以解決模式識別、回歸估計等領(lǐng)域的難題。．最優(yōu)分類面和廣義最優(yōu)分類面SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來的，基本思想可用圖1來說明。對于一維空間中的點，二維空間中的直線，三維空間中的平面，以及高維空間中的超平面，圖中實心點和空心點代表兩類樣本，H為它們之間的分類超平面，H1，H2分別為過各類中離分類面最近的樣本且平行于分類面的超平面，它們之間的距離△叫做分類間隔(margin)。 最優(yōu)分類面示意圖所謂最優(yōu)分類面要求分類面不但能將兩類正確分開，而且使分類間隔最大。將兩類正確分開是為了保證訓練錯誤率為0，也就是經(jīng)驗風險最小(為O)。使分類空隙最大實際上就是使推廣性的界中的置信范圍最小，從而使真實風險最小。推廣到高維空間，最優(yōu)分類線就成為最優(yōu)分類面。設(shè)線性可分樣本集為是類別符號。d維空間中線性判別函數(shù)的一般形式為是類別符號。d維空間中線性判別函數(shù)的一般形式為，分類線方程為。將判別函數(shù)進行歸一化，使兩類所有樣本都滿足，也就是使離分類面最近的樣本的，此時分類間隔等于，因此使間隔最大等價于使 (或)最小。要求分類線對所有樣本正確分類，就是要求它滿足 （21）滿足上述條件(21)，并且使最小的分類面就叫做最優(yōu)分類面，過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面H1，H2上的訓練樣本點就稱作支持向量(support vector)，因為它們“支持”了最優(yōu)分類面。利用Lagrange優(yōu)化方法可以把上述最優(yōu)分類面問題轉(zhuǎn)化為如下這種較