支持向量機(jī)在統(tǒng)計(jì)機(jī)器學(xué)習(xí)中的應(yīng)用

支持向量機(jī)在統(tǒng)計(jì)機(jī)器學(xué)習(xí)中的應(yīng)用

近年來(lái)，統(tǒng)計(jì)機(jī)械學(xué)習(xí)是一種廣泛使用的機(jī)械學(xué)習(xí)方法。事實(shí)上，這是一種非常廣泛的方法。如果你不能或不需要建立一個(gè)嚴(yán)格的物理模型，你可以使用數(shù)學(xué)方法來(lái)計(jì)算這個(gè)問(wèn)題的世界。通常，這些模型并不是用于研究世界的物理解釋。然而，它可以反映問(wèn)題世界的現(xiàn)實(shí)，這就是“黑匣子”的原理。一般來(lái)說(shuō)，“黑匣子”的原理是基于統(tǒng)計(jì)方法，統(tǒng)計(jì)機(jī)器的學(xué)習(xí)本質(zhì)上是“黑匣子”原則的延續(xù)。統(tǒng)計(jì)機(jī)器學(xué)習(xí)理論派生的算法——支持向量機(jī)的優(yōu)點(diǎn)是什么?首先,支持向量機(jī)有有限樣本統(tǒng)計(jì)理論支持,它的算法設(shè)計(jì)不是僅僅以劃分為基礎(chǔ),而是在考慮了泛化能力的基礎(chǔ)下的劃分;其二,算法設(shè)計(jì)有幾何直觀(guān)的指導(dǎo);其三,最為重要,也是至今未被研究者重視的一點(diǎn)——核函數(shù)獨(dú)立于算法,即在理論上顯現(xiàn)地說(shuō)明了同一個(gè)問(wèn)題在兩個(gè)空間上的表示,這一方面為進(jìn)一步理論分析開(kāi)拓了必要的條件,另一方面,使得根據(jù)領(lǐng)域知識(shí)設(shè)計(jì)核映射成為可能.使用通用的核函數(shù)(例如,高斯類(lèi)核函數(shù))可以解決一些問(wèn)題,這也是目前采用最普遍的研究方法.但是,根據(jù)領(lǐng)域知識(shí)來(lái)設(shè)計(jì)核函數(shù),還未被研究者充分重視支持向量機(jī)是統(tǒng)計(jì)機(jī)器學(xué)習(xí)的一類(lèi)重要算法,其中SMO算法是實(shí)際應(yīng)用中較為有效的方法.SMO算法是將求解支持向量機(jī)的二次規(guī)劃問(wèn)題分解為一系列較小的問(wèn)題,從而實(shí)現(xiàn)串行最小優(yōu)化概括地說(shuō),就是首先通過(guò)用內(nèi)積函數(shù)定義的非線(xiàn)性變換將輸入空間變換到一個(gè)高維空間,然后在這個(gè)空間中求廣義的最優(yōu)分類(lèi)面.1svm訓(xùn)練空間問(wèn)題的處理支持向量機(jī)算法歸結(jié)為二次規(guī)劃(QP,QuadraticProgramming)求解問(wèn)題,已經(jīng)提出了許多針對(duì)大規(guī)模樣本集的SVM訓(xùn)練算法.目前已經(jīng)提出的訓(xùn)練算法大部分基于分解迭代的思想,即將原始的QP問(wèn)題分解成若干規(guī)模較小的QP問(wèn)題求解.具體來(lái)說(shuō),在每一步迭代計(jì)算中都要訓(xùn)練數(shù)據(jù)樣本集分解為兩個(gè)子集合B和N,只對(duì)工作集B中的數(shù)據(jù)樣本進(jìn)行優(yōu)化,則另一集合數(shù)據(jù)樣本所對(duì)應(yīng)的拉格朗日乘子不變.解決SVM訓(xùn)練存儲(chǔ)空間問(wèn)題的算法即Chunking算法,與將求解支持向量機(jī)的QP問(wèn)題分解為一系列較小的QP問(wèn)題的分解算法,一般使用的是用數(shù)值法求解,但往往會(huì)在計(jì)算機(jī)精度和計(jì)算復(fù)雜性方面帶來(lái)一些問(wèn)題.于是提出了串行最小優(yōu)化(SMO,SequentialMinimalOptimization)算法.SMO算法也是一種分解算法,其工作空間只包含兩個(gè)數(shù)據(jù)樣本,在每一步迭代中都只對(duì)兩個(gè)拉格朗日乘子進(jìn)行優(yōu)化,由于對(duì)拉格朗日乘子的線(xiàn)性等式約束,因此這是可能達(dá)到的最小優(yōu)化問(wèn)題.盡管SMO中QP子問(wèn)題增多了,但總的計(jì)算機(jī)速度大大提高了,而且這種算法完全不需要處理大矩陣,因而對(duì)存儲(chǔ)空間沒(méi)有額外要求,很大的SVM訓(xùn)練問(wèn)題也能用個(gè)人計(jì)算機(jī)進(jìn)行運(yùn)算.1.1smo算法原理SMO算法和其它SVM改進(jìn)算法一樣,都是把整個(gè)二次規(guī)劃問(wèn)題分解為很多易于處理的小問(wèn)題.所不同的是只有SMO算法把問(wèn)題分解到可能達(dá)到的最小規(guī)模,每次優(yōu)化只處理兩個(gè)數(shù)據(jù)樣本的優(yōu)化問(wèn)題,并且用解析的方法進(jìn)行處理.對(duì)于SVM來(lái)說(shuō),一次至少要同時(shí)對(duì)兩個(gè)數(shù)據(jù)樣本進(jìn)行優(yōu)化,即優(yōu)化對(duì)應(yīng)的Lagrange乘子,這是因?yàn)榈仁郊s束的存在使得不可能單獨(dú)優(yōu)化一個(gè)變量.SMO算法的最大特色就是可用解析方法求解每一個(gè)最小規(guī)模的優(yōu)化問(wèn)題,從而完全避免了迭代算法1.2拉格蘭家族乘數(shù)優(yōu)化假設(shè)優(yōu)化的Lagrange乘子對(duì)應(yīng)的數(shù)據(jù)樣本為第一個(gè)和第二個(gè),對(duì)應(yīng)的Lagrange乘子為a1.3遍歷非邊界數(shù)據(jù)樣本如果不采用任何方法,只是按順序抽取a這種方法先選擇最有可能需要優(yōu)化的a1)針對(duì)違反KKT條件的數(shù)據(jù)樣本,選擇另一個(gè)數(shù)據(jù)樣本與它配對(duì)優(yōu)化.選擇的依據(jù)是盡量使這一對(duì)數(shù)據(jù)樣本能取得最大優(yōu)化步長(zhǎng).對(duì)其中的Lagrange乘子a2)遍歷非邊界數(shù)據(jù)樣本或所有數(shù)據(jù)樣本.優(yōu)先選擇遍歷非邊界數(shù)據(jù)樣本,因?yàn)榉沁吔鐢?shù)據(jù)樣本更有可能需要調(diào)整,邊界數(shù)據(jù)樣本常常不能得到進(jìn)一步調(diào)整而留在邊界上.由于大部分?jǐn)?shù)據(jù)樣本都很明顯不可能是支持向量,因此對(duì)應(yīng)的Lagrange乘子一旦取得零值就無(wú)需再調(diào)整.遍歷非邊界數(shù)據(jù)樣本并選出他們當(dāng)中違反KKT條件為止.當(dāng)某一次遍歷發(fā)現(xiàn)沒(méi)有非邊界數(shù)據(jù)樣本得到調(diào)整時(shí),遍歷所有數(shù)據(jù)樣本,以檢驗(yàn)是否整個(gè)集合頁(yè)都滿(mǎn)足KKT條件.如果整個(gè)集合的檢驗(yàn)中又有數(shù)據(jù)樣本被進(jìn)一步進(jìn)化,則有必要在遍歷非邊界數(shù)據(jù)樣本.這樣,不停地在遍歷所有數(shù)據(jù)樣本和遍歷非邊界數(shù)據(jù)樣本之間切換,直到整個(gè)樣本集合都滿(mǎn)足KKT條件為止.以上用KKT條件對(duì)數(shù)據(jù)樣本所做的檢驗(yàn)都以達(dá)到一定精度就可以停止為條件.如果要求十分精確的輸出算法,則往往不能很快收斂.1.4非線(xiàn)性情況下誤差的重現(xiàn)每做完一次最小優(yōu)化,必須更新每個(gè)數(shù)據(jù)樣本的誤差,以便用修正過(guò)的分類(lèi)面對(duì)其他數(shù)據(jù)樣本再做KKT檢驗(yàn),在選擇第二個(gè)配對(duì)優(yōu)化數(shù)據(jù)樣本時(shí)用來(lái)估計(jì)步長(zhǎng).要更新數(shù)據(jù)樣本的誤差,首先要重置閾值bb如果最小優(yōu)化后的aba在非線(xiàn)性情況下,誤差的計(jì)算要用到所有已找到的支持向量及對(duì)應(yīng)的Lagrange乘子:在線(xiàn)性情況下,先重置分類(lèi)超平面的法向量ω,再根據(jù)u大部分重置工作都是以簡(jiǎn)單的非循環(huán)計(jì)算來(lái)完成的,這使得需要做很多次最小優(yōu)化的SMO算法不必在每次優(yōu)化后的重置中花費(fèi)太多時(shí)間.非線(xiàn)性情況下誤差的重置必須與所有支持向量逐個(gè)計(jì)算核函數(shù),核函數(shù)的計(jì)算本身就比點(diǎn)積運(yùn)算復(fù)雜,于是非線(xiàn)性情況下誤差的重置成為了SMO算法計(jì)算速度的瓶頸.1.5smo算法的優(yōu)勢(shì)SMO算法和其他SVM算法(塊算法、分解算法等)相比,既有共同點(diǎn),又有自己的獨(dú)特之處.其共同點(diǎn)是把一個(gè)大的優(yōu)化問(wèn)題分解為很多小問(wèn)題來(lái)處理.塊算法將新加入數(shù)據(jù)樣本中違反KKT條件的數(shù)據(jù)樣本,與原有的支持向量一起組成小問(wèn)題的數(shù)據(jù)樣本進(jìn)行優(yōu)化,優(yōu)化完畢后只保留其中的支持向量,再加進(jìn)來(lái)新的數(shù)據(jù)樣本進(jìn)入下一步;SMO則是把每一步的優(yōu)化問(wèn)題縮減到最小,把數(shù)據(jù)樣本集的大小固定為2,并且每一步用兩個(gè)新的Lagrange乘子替換原有的全部乘子.SMO的最大特色在于:在對(duì)二次規(guī)劃尋優(yōu)求解時(shí),把問(wèn)題分解到可能達(dá)到的最小規(guī)模,即每次優(yōu)化只處理兩個(gè)數(shù)據(jù)樣本的優(yōu)化問(wèn)題.這樣做的最大好處就是可以用解析的方法求解每一個(gè)最小規(guī)模,從而完全避免了二次規(guī)劃數(shù)值解法的復(fù)雜迭代過(guò)程,不但節(jié)省了計(jì)算時(shí)間,而且不會(huì)牽涉到迭代法造成的誤差積累.理論上,SMO的每一步最小優(yōu)化都不會(huì)造成任何誤差積累,如果用雙精度數(shù)計(jì)算,則舍入誤差幾乎可以忽略,所有的誤差只在于最后一遍檢驗(yàn)時(shí),以多大的公差要求所有Lagrange乘子滿(mǎn)足KKT條件.因此,可以說(shuō)SMO算法在速度和精度兩方面都得到了保證.SMO在計(jì)算所需內(nèi)存的節(jié)省上也頗有特色.由于SMO不涉及二次規(guī)劃數(shù)值解法,因而不必將核函數(shù)矩陣整個(gè)存放于內(nèi)存中,而二次規(guī)劃數(shù)值解法的每步迭代都要使用這個(gè)矩陣進(jìn)行運(yùn)算.SMO使用的內(nèi)存與數(shù)據(jù)樣本集的大小為線(xiàn)性關(guān)系,而不像其他SVM算法為平方關(guān)系.SMO算法對(duì)線(xiàn)性支持向量機(jī)最為有效,對(duì)非線(xiàn)性支持向量機(jī)則不能發(fā)揮出全部?jī)?yōu)勢(shì),這是因?yàn)樵诰€(xiàn)性情況下,每次最小優(yōu)化后的重置工作都是很簡(jiǎn)單的運(yùn)算,而在非線(xiàn)性時(shí)有一步加權(quán)求和,占用了主要的時(shí)間.其他SVM算法對(duì)線(xiàn)性和非線(xiàn)性區(qū)別不大,因?yàn)槎我?guī)劃數(shù)值解得算法將大量時(shí)間花費(fèi)在求數(shù)值解得運(yùn)算中.特殊情況是,當(dāng)大多數(shù)Lagrange乘子都在邊界上時(shí),SMO算法的效果會(huì)更好.盡管SMO的計(jì)算時(shí)間仍比數(shù)據(jù)樣本集的大小的增長(zhǎng)快得多,但比起其他方法,SMO算法還是適合大數(shù)量的數(shù)據(jù)樣本.2基于smo算法的自適應(yīng)學(xué)習(xí)支持向量機(jī)的數(shù)學(xué)模型可以歸結(jié)為一個(gè)有約束的二次規(guī)劃問(wèn)題.快速、準(zhǔn)確地求解二次規(guī)劃是SVM在實(shí)際應(yīng)用中的一個(gè)重要環(huán)節(jié).根據(jù)對(duì)SVM算法的理解,提出自適應(yīng)學(xué)習(xí)的思想,對(duì)SMO算法進(jìn)行改進(jìn),可使SVM算法更能適應(yīng)實(shí)際應(yīng)用快速、高效的需要.自適應(yīng)學(xué)習(xí)是在SMO算法的基礎(chǔ)上,將KKT條件作為判定新增數(shù)據(jù)樣本是否更新現(xiàn)有SVM分類(lèi)函數(shù)的依據(jù),包括新增數(shù)據(jù)樣本改變SVM分類(lèi)函數(shù)和新增數(shù)據(jù)樣本不改變SVM分類(lèi)函數(shù)兩個(gè)過(guò)程.新增數(shù)據(jù)樣本學(xué)習(xí)過(guò)程是使用新數(shù)據(jù)樣本更新現(xiàn)有SVM分類(lèi)函數(shù),使得擴(kuò)充數(shù)據(jù)樣本集處于最優(yōu)化狀態(tài);已有數(shù)據(jù)樣本學(xué)習(xí)過(guò)程是使指定的數(shù)據(jù)樣本不對(duì)SVM分類(lèi)函數(shù)產(chǎn)生影響,同時(shí)保持?jǐn)?shù)據(jù)樣本集的最優(yōu)化狀態(tài).SMO算法的求解是凸二次規(guī)劃尋優(yōu)問(wèn)題,自適應(yīng)學(xué)習(xí)是在已有的SMO算法求解凸二次規(guī)劃尋優(yōu)問(wèn)題的基礎(chǔ)上進(jìn)行的改進(jìn),所以自適應(yīng)學(xué)習(xí)與凸二次規(guī)劃尋優(yōu)問(wèn)題求解的關(guān)系非常密切.當(dāng)核函數(shù)類(lèi)型及其參數(shù)確定后,支持向量可完全描述整個(gè)數(shù)據(jù)樣本集的分類(lèi)特征,支持向量集是數(shù)據(jù)樣本集的一小部分.因此,如果新增數(shù)據(jù)樣本帶有原數(shù)據(jù)樣本集不包含的分類(lèi)信息,則學(xué)習(xí)后支持向量集必然發(fā)生變化,以體現(xiàn)新增數(shù)據(jù)樣本的新信息的加入.根據(jù)SMO算法的思想,分類(lèi)錯(cuò)誤是數(shù)據(jù)樣本違反KKT條件的特定情況,所以將KKT條件作為判定新增數(shù)據(jù)樣本是否更新現(xiàn)有SVM分類(lèi)函數(shù)的依據(jù).當(dāng)新增數(shù)據(jù)樣本滿(mǎn)足KKT條件時(shí),新增數(shù)據(jù)樣本將不會(huì)改變支持向量集;當(dāng)新增數(shù)據(jù)樣本違背KKT條件時(shí),新增數(shù)據(jù)樣本將使支持向量集發(fā)生變化根據(jù)上述的分析,提出了一種基于SMO算法的自適應(yīng)學(xué)習(xí)方法.在自適應(yīng)學(xué)習(xí)方法中,需要對(duì)新增數(shù)據(jù)樣本單獨(dú)進(jìn)行一次訓(xùn)練,得到新的SVM分類(lèi)函數(shù).整個(gè)過(guò)程對(duì)全部數(shù)據(jù)樣本只做一次違背KKT條件的驗(yàn)證.如果SVM分類(lèi)函數(shù)為f(x由于二值分類(lèi)問(wèn)題是SVM的最基本問(wèn)題,下面以二值分類(lèi)問(wèn)題為例,給出基于SMO算法的自適應(yīng)學(xué)習(xí)方法的處理步驟:1)檢驗(yàn)新增數(shù)據(jù)樣本是否違背SVM分類(lèi)函數(shù)的KKT條件,如果數(shù)據(jù)樣本沒(méi)有違背,則停止,SVM分類(lèi)函數(shù)為學(xué)習(xí)結(jié)果;否則,根據(jù)驗(yàn)證結(jié)果,新增數(shù)據(jù)樣本被分為違背SVM分類(lèi)函數(shù)的KKT條件的數(shù)據(jù)樣本集合和滿(mǎn)足SVM分類(lèi)函數(shù)的KKT條件的數(shù)據(jù)樣本集合.2)由新增數(shù)據(jù)樣本得到新的SVM分類(lèi)函數(shù)及新的支持向量集.3)檢驗(yàn)原數(shù)據(jù)樣本集中的數(shù)據(jù)樣本是否違背新的SVM分類(lèi)函數(shù)的KKT條件,如果沒(méi)有數(shù)據(jù)樣本違背,則算法停止,新的SVM分類(lèi)函數(shù)為增量學(xué)習(xí)結(jié)果;否則,原數(shù)據(jù)樣本集分為違背新的SVM分類(lèi)函數(shù)的KKT條件的數(shù)據(jù)樣本集合滿(mǎn)足新的SVM