支持向量機(jī)的并行學(xué)習(xí)與增量學(xué)習(xí)方法研究.pdf

1、支持向量機(jī)(supportvectormachine，SVMs)已經(jīng)被廣泛地應(yīng)用于機(jī)器學(xué)習(xí)和模式識(shí)別等領(lǐng)域，是目前最常用的一種模式識(shí)別方法。然而，當(dāng)使用支持向量機(jī)處理大規(guī)模問(wèn)題時(shí)，支持向量機(jī)還存在以下局限性：1)由于支持向量機(jī)的訓(xùn)練過(guò)程實(shí)質(zhì)是求解一個(gè)二次規(guī)劃問(wèn)題，而二次規(guī)劃問(wèn)題的求解時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(N3)和O(N2)。所以當(dāng)訓(xùn)練集規(guī)模巨大時(shí)，支持向量機(jī)的訓(xùn)練時(shí)間會(huì)太長(zhǎng)，同時(shí)還會(huì)導(dǎo)致內(nèi)存空間的不足；2)支持向量機(jī)的訓(xùn)練結(jié)果

2、是用支持向量表示的。支持向量數(shù)量太大將導(dǎo)致超出內(nèi)存限制，使得分類(lèi)器不能全部裝入內(nèi)存。這將影響分類(lèi)器的使用；3)由于計(jì)算機(jī)系統(tǒng)的不可靠性，集中表示的分類(lèi)器將面臨失效的嚴(yán)重風(fēng)險(xiǎn)；4)二次規(guī)劃問(wèn)題的求解過(guò)程本質(zhì)是面向批量數(shù)據(jù)，已經(jīng)訓(xùn)練好的支持向量機(jī)無(wú)法將新增加的訓(xùn)練樣本納入。 當(dāng)前網(wǎng)格計(jì)算已經(jīng)實(shí)現(xiàn)商業(yè)應(yīng)用，并行處理技術(shù)和模塊化結(jié)構(gòu)已經(jīng)被廣泛地引入了分類(lèi)器設(shè)計(jì)。為了充分利用分布式計(jì)算資源解決支持向量機(jī)的上述局限性，本論文研究了支持向量機(jī)

3、的并行學(xué)習(xí)和增量學(xué)習(xí)問(wèn)題。我們?cè)噲D回答這樣兩個(gè)問(wèn)題：一個(gè)是如何進(jìn)行有效的問(wèn)題分解或分類(lèi)器的組合，在確保一般化能力沒(méi)有顯著降低或沒(méi)有降低的前提下，加速支持向量機(jī)處理大規(guī)模模式分類(lèi)問(wèn)題的訓(xùn)練過(guò)程。二是如何進(jìn)行有效的分類(lèi)器組合，以實(shí)現(xiàn)支持向量機(jī)的增量學(xué)習(xí)。本文的主要貢獻(xiàn)在以下幾個(gè)方面： (1)提出了一種新的等分聚類(lèi)算法，并將該算法嵌入最小最大模塊化支持向量機(jī)(M3-SVMs)。該等分聚類(lèi)算法的特點(diǎn)是能比較均勻地實(shí)現(xiàn)訓(xùn)練集的分割，盡可能

4、保證M3-SVMs在并行執(zhí)行時(shí)各處理器間的負(fù)載平衡。當(dāng)訓(xùn)練數(shù)據(jù)分布不是同分布時(shí)，聚類(lèi)分割方法使數(shù)據(jù)的分割體現(xiàn)數(shù)據(jù)本身的分布特征，能減少因數(shù)據(jù)分割帶來(lái)的分類(lèi)信息損失。實(shí)驗(yàn)表明：基于等分聚類(lèi)算法的最小最大模塊化支持向量機(jī)方法加速了訓(xùn)練過(guò)程，提高了一般化能力。在性別識(shí)別實(shí)際應(yīng)用中，顯示了很好的應(yīng)用效果。 (2)提出了分層并行支持向量機(jī)訓(xùn)練算法。該算法采用“交叉合并規(guī)則”并行地將非支持向量逐層篩減，使得非支持向量不會(huì)反復(fù)進(jìn)入優(yōu)化過(guò)程。實(shí)

5、驗(yàn)表明：當(dāng)支持向量所占比重較小時(shí)，該算法與通常訓(xùn)練支持向量機(jī)的方法相比有兩個(gè)優(yōu)點(diǎn)：第一，在保證分類(lèi)器推廣能力的前提下，能提高支持向量機(jī)的訓(xùn)練速度。第二，減少了支持向量的數(shù)目，這一優(yōu)點(diǎn)有利于提高支持向量機(jī)的響應(yīng)速度，降低支持向量機(jī)在軟件和硬件實(shí)現(xiàn)時(shí)的成本。 (3)提出了并行支持向量機(jī)可信多數(shù)投票算法。該算法根據(jù)分類(lèi)器的分類(lèi)置信度實(shí)現(xiàn)分類(lèi)器的選擇，分類(lèi)器的選擇策略能減小組合分類(lèi)器的方差(Variance)。實(shí)驗(yàn)表明：該算法能使組合分

6、類(lèi)器獲得更好的一股化能力。該算法不但能保持與標(biāo)準(zhǔn)支持向量機(jī)幾乎相同的一般化能力，還能顯著地減少訓(xùn)練和測(cè)試總時(shí)間。 (4)提出了基于分類(lèi)器組合的支持向量機(jī)增量學(xué)習(xí)算法。通過(guò)每接收到一個(gè)訓(xùn)練集就訓(xùn)練一個(gè)能輸出后驗(yàn)概率的支持向量機(jī)，該算法實(shí)現(xiàn)了對(duì)塊狀數(shù)據(jù)流的處理。該算法根據(jù)支持向量機(jī)輸出的后驗(yàn)概率來(lái)計(jì)算分類(lèi)置信度，然后采用平均貝葉斯規(guī)則實(shí)現(xiàn)分類(lèi)器組合。實(shí)驗(yàn)表明：該算法不但能保持原來(lái)學(xué)習(xí)到的知識(shí)，還能學(xué)習(xí)到新增樣本中包含的知識(shí)。該算法具