亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于選擇性抽樣的SVM增量學(xué)習(xí)算法的泛化性能研究

        2019-05-08 12:59:02
        計算機測量與控制 2019年4期
        關(guān)鍵詞:分率馬爾可夫增量

        (1.湖北大學(xué) 計算機與信息工程學(xué)院,武漢 430062; 2.武漢晴川學(xué)院 計算機科學(xué)學(xué)院,武漢 430204)

        0 引言

        基于支持向量機(support vector machine,SVM)的分類算法[1],不僅在解決非線性、小樣本、高維模式識別和克服“維數(shù)災(zāi)難”等問題上中表現(xiàn)出了特有的優(yōu)勢,而且還具有堅實的統(tǒng)計學(xué)習(xí)理論基礎(chǔ)[2-3],簡潔的數(shù)學(xué)模型以及良好的泛化性能。因此,SVM被廣泛應(yīng)用到時間序列預(yù)測[4]、回歸分析[5]、人臉圖像識別等各個領(lǐng)域。盡管SVM理論基礎(chǔ)堅實,泛化性能良好,但經(jīng)典SVM算法是批量式處理,即訓(xùn)練樣本一次性被輸入到計算機內(nèi)存中,所以在處理大規(guī)模數(shù)據(jù)時會面臨內(nèi)存限制[6]以及學(xué)習(xí)效率低等問題。因此具有增量學(xué)習(xí)功能的數(shù)據(jù)分類技術(shù)應(yīng)運而生,Syed等人[7]最早提出增量學(xué)習(xí),其解決問題的核心在于每一次隨機選取算法能夠處理的數(shù)據(jù)量進行訓(xùn)練,留下支持向量,再加入新的訓(xùn)練樣本繼續(xù)訓(xùn)練,依此過程訓(xùn)練學(xué)習(xí)。近年來,孔銳等人[8]提出一種新的SVM增量學(xué)習(xí)算法,該算法首先選擇可能成為支持向量的邊界向量,以達到減少訓(xùn)練的樣本數(shù)量。Li等人[9]提出基于超平面距離的支持向量機增量學(xué)習(xí)算法,采用Hyperplane-Distance方法提取樣本,選取最有可能成為支持向量的樣本構(gòu)成邊緣向量集以提高訓(xùn)練速度。

        上述增量學(xué)習(xí)算法都是基于樣本是獨立同分布的假設(shè),該假設(shè)無論在理論上,還是實際應(yīng)用中都是非常強的,因現(xiàn)實機器學(xué)習(xí)[10]中不服從獨立同分布的數(shù)據(jù)很是廣泛,所以為非獨立同分布的數(shù)據(jù)更適用于機器學(xué)習(xí),減弱獨立同分布的假設(shè)得到了相關(guān)學(xué)者的關(guān)注,Zou等人[11]證明了具有一致遍歷馬爾可夫鏈樣本的ERM算法是一致的,且一致遍歷馬爾可夫鏈在SVM中也得到了應(yīng)用,如Xu等人[12]證明了SVM泛化性能馬氏抽樣要優(yōu)于隨機抽樣。針對樣本是獨立同分布的假設(shè)在實際應(yīng)用中相對牽強,且獨立隨機抽樣的時效普遍偏低,數(shù)據(jù)存在非全局性等缺點,提出一種新的SVM增量學(xué)習(xí)算法。該算法利用馬氏抽樣選取具有一致遍歷馬爾可夫鏈性質(zhì)的訓(xùn)練樣本集,研究增量學(xué)習(xí)的特性,并與基于隨機抽樣的SVM增量學(xué)習(xí)算法和文獻[15]提出的增量學(xué)習(xí)算法做出比較。分別從分類錯誤率、支持向量個數(shù)和抽樣與訓(xùn)練總時間三個方面對比增量學(xué)習(xí)算法性能,選用基準數(shù)據(jù)集作為樣本數(shù)據(jù),經(jīng)實驗表明,基于選擇性抽樣的SVM增量學(xué)習(xí)算法泛化性能更好。

        1 相關(guān)知識

        針對SVM增量學(xué)習(xí)所涉及到的概念以及一致遍歷馬爾可夫鏈等內(nèi)容,本節(jié)將給予介紹以及給出相關(guān)的定義。

        1.1 支持向量機

        基于SVM的二分類器,是在給定的空間下,尋找能夠分割兩類樣本且具有最大間隔的超平面。設(shè)帶有類別標記的輸入模式集X?Rn為二分類數(shù)據(jù)集,類別標簽為Y={+1,-1},輸入集的每一個數(shù)據(jù)點,都有一個類別標簽與之對應(yīng)即X→Y,從中取大小為l的樣本作為原始空間訓(xùn)練集:S={s1=(x1,y1),s2=(x2,y2),…,sl=(xl,yl)},其中xi∈X,yi∈Y,i=1,2,…,l。SVM目標是求解可以分割兩類樣本點的超平面wx+b=0的最優(yōu)解,將求解問題可以歸納為式(1)二次規(guī)劃問題:

        (1)

        其中:C正則化參數(shù),ε為松弛變量。

        借助Lagrange乘子法,轉(zhuǎn)化為對偶問題:

        (2)

        只需求解式(2)即可獲取最優(yōu)分類面,若原始空間中求取的分類面效果不佳,依據(jù)泛函理論知識。存在一種滿足Mercer核條件的核函數(shù):K(xi,xj)=<Φ(xi)·Φ(xj)>,可通過線性映射Φ:Rn→H,x→Φ(x)將輸入空間映射到Hilber空間中,則相應(yīng)的決策函數(shù)為:

        其中非零的拉格朗日乘子(αi≠0)對應(yīng)的樣本點稱作為支持向量。支持向量個數(shù)越少,則表明SVM的分類器越稀疏。

        1.2 增量學(xué)習(xí)

        傳統(tǒng)的增量學(xué)習(xí)算法樣本的選擇是隨機抽樣,選取的樣本之間不具備關(guān)聯(lián)性。在第2節(jié)將介紹一種基于選擇性抽樣的SVM增量學(xué)習(xí)算法。

        1.3 一致遍歷馬爾可夫鏈

        實際應(yīng)用中很多模型產(chǎn)生的樣本在本質(zhì)上是自然涌現(xiàn)的而非獨立同分布,如市場預(yù)測,語音識別等,這些數(shù)據(jù)并不符合機器學(xué)習(xí)中數(shù)據(jù)獨立同分布的假設(shè)。所以通過減弱樣本是獨立同分布的情形,利用一致遍歷馬爾可夫鏈模型進行算法泛化性能研究。如下給出一致遍歷馬爾可夫鏈的概念:

        定義(Z,E)為一個可測空間,則一個隨機變量序列{Zt}t≥1以及一系列轉(zhuǎn)移概率測度Pn(S|zi),S∈E,zi∈Z共同構(gòu)成一個馬爾可夫鏈,假定:

        Pn(S|zi):=P{Zn+i∈S|Zj,j

        記Pn(S|zi)為n步轉(zhuǎn)移概率:從初始狀態(tài)為zi的時刻i開始,經(jīng)過n步迭代后狀態(tài)為zn+i屬于集合S的概率。若轉(zhuǎn)移概率不依賴于在時刻i之前的Zj狀態(tài)集,稱具有馬爾可夫性質(zhì),即:Pn(S|zi):=P{Zn+i∈S|Zi=zi},故馬爾可夫鏈特性:若給定當(dāng)前狀態(tài),則馬爾可夫鏈的將來和過去狀態(tài)都是獨立的。

        假設(shè)給定測度空間(Z,E)上的兩個測度為μ1和μ2,將測度μ1和μ2的全變差定義為:

        2 基于選擇性抽樣的增量學(xué)習(xí)算法

        基于選擇性抽樣的SVM增量學(xué)習(xí)算法中利用馬氏抽樣選取增量樣本集,馬氏抽樣通過定義每一次抽樣的轉(zhuǎn)移概率來選擇樣本數(shù)據(jù),構(gòu)建出具有馬爾可夫性質(zhì)的樣本集。記DTR為訓(xùn)練集,DTE為測試集,T為增量學(xué)習(xí)次數(shù),N為每次增量樣本的大小,損失函數(shù)[13]定義為l(f,z)=(1-f(x)y)+?;谶x擇性抽樣的SVM增量學(xué)習(xí)算法步驟如下:

        算法1:SVM增量學(xué)習(xí)算法

        輸入:DTR,DTE,T,N,q。

        4)令k=2。

        5)令u=1。

        8)若P=1,y*yu=-1或P<1,則依轉(zhuǎn)移概率P接受樣本z*;若P=1、y*yu=1則依轉(zhuǎn)移概率P′=min{1,e-y*fk-1/e-yufk-1}接受樣本z*;若有連續(xù)n個候選樣本z*不能被接受,此時依轉(zhuǎn)移概率P″=min{1,qP}接受樣本z*,如果z*不能被接受,返回步驟7),否則令u=u+1,zu=z*。

        10)若k≤T,返回步驟5),否則,獲取抽樣與訓(xùn)練總時間,支持向量數(shù)目,并使用分類模型fT計

        算在測試集DTE中錯分率。

        輸出:錯分率、支持向量個數(shù)、抽樣與訓(xùn)練總時間

        評注1:算法1利用數(shù)據(jù)子集分類模型的均值來定義起始轉(zhuǎn)移概率,可以避免因初始轉(zhuǎn)移概率的定義而導(dǎo)致算法可能會具有的較大波動性。為快速生成馬氏樣本集,根據(jù)文獻[12]的研究,在算法1中引進了兩個參數(shù)n和q,其中n為候選樣本連續(xù)被拒絕的次數(shù),q為解決當(dāng)損失函數(shù)l(f,z)值較小時,在以概率接收候選樣本時需要花費大量的時間而引入的常數(shù)。

        3 數(shù)值實驗

        本章將對實驗選取的數(shù)據(jù)集,實驗結(jié)果,實驗分析做出闡述,為讓實驗更具有效性與說服力,在實驗中,對于同一個數(shù)據(jù)集,均在數(shù)據(jù)子集劃分、增量次數(shù)、每次增量數(shù)據(jù)量完全相同的情況下進行實驗。

        在實驗結(jié)果比較中,記“iid”為基于隨機抽樣的SVM增量學(xué)習(xí)算法,“Markov”為基于選擇性抽樣的SVM增量學(xué)習(xí)算法。

        3.1 實驗參數(shù)及數(shù)據(jù)集

        實驗選取Matlab2016a作為編程軟件,在CPU為Inter(R)Core(TM)i7-7500 @2.7 GHz,RAM為8 G的環(huán)境中編程(因計算機內(nèi)存限制,其中數(shù)據(jù)集Skin在CPU為Intel(R)Xeon(R) E5-1603-v4@2.8 GHz,RAM為32 G的環(huán)境中實驗)。處理高維數(shù)據(jù)時映射核函數(shù)選用高斯徑向基函數(shù)[14],算法通過10倍交叉驗證從候選集[-0.01,-0.1,0,1,10,100, 1000,10000]中選取正則化參數(shù)C=1000。為更好證明算法的泛化能力,實驗分別選取3維至300維的二分類數(shù)據(jù)集進行算法的泛化能力研究。實驗所選取的9個數(shù)據(jù)集如表1所示。

        表1 9個實驗數(shù)據(jù)集

        3.2 與隨機抽樣增量學(xué)習(xí)算法對比

        為讓實驗更具說服力,實驗中對于同一個數(shù)據(jù)集分別進行三次增量實驗,即T值分別取10,20,30次,且每次增量樣本會依據(jù)算法步驟1劃分出的數(shù)據(jù)子集規(guī)模而定義較大的值,即N值。

        實驗結(jié)果如表2所示,其中表的第二列為“數(shù)字/數(shù)字”,如數(shù)據(jù)集Skin中的10/8000,表示數(shù)據(jù)集Skin增量10次(10個子集),每次增量的樣本數(shù)為8000;20/5000則表示數(shù)據(jù)集Skin增量20次(20個子集),每次增量的樣本數(shù)為5000;為充分的表明基于選擇性抽樣的SVM增量學(xué)習(xí)算法的泛化能力,實驗分別從錯誤分類率,支持向量個數(shù),抽樣與訓(xùn)練總時間三個方面對比基于選擇性抽樣的SVM增量學(xué)習(xí)算法和基于隨機抽樣的SVM增量學(xué)習(xí)算法。

        由表3的實驗結(jié)果可以看出,基于選擇性抽樣的SVM的增量學(xué)習(xí)算法無論在T與N取何值時錯誤分類率均低于基于隨機抽樣的SVM增量學(xué)習(xí)算法,且能在保證錯分率低的同時,能大幅度減少支持向量個數(shù)和抽樣與訓(xùn)練總時間。因為基于選擇性抽樣的SVM的增量學(xué)習(xí)算法中增量樣本非隨機選取,而是通過計算樣本之間的轉(zhuǎn)移概率判斷是否接

        表2 數(shù)值實驗結(jié)果

        受樣本,所以通過馬氏抽樣選取的樣本之間具有關(guān)聯(lián)性,可以很大程度的避開噪聲等因素對數(shù)據(jù)的影響。

        為更好地展示實驗效果,圖1給出了基于選擇性抽樣的SVM的增量學(xué)習(xí)算法和基于隨機抽樣的SVM增量學(xué)習(xí)算法的實驗數(shù)據(jù)集部分錯分率詳細對比圖、支持向量對比圖、抽樣與訓(xùn)練總時間對比圖。

        從圖1的(a)與(d)中可以看出,基于選擇性抽樣的SVM增量學(xué)習(xí)算法,在增量樣本相同的情況下,隨著增量次數(shù)的增加,錯分率總體呈下降趨勢,且錯分率逐漸趨于平穩(wěn),而基于隨機抽樣的SVM增量學(xué)習(xí)算法,波動較大。

        從圖1的(b)與(e)中可以看出,無論增量次數(shù)T和增量樣本量N取何值,基于選擇性抽樣的SVM增量學(xué)習(xí)算法比基于隨機抽樣SVM增量學(xué)習(xí)算法的支持向量數(shù)目要少,即分類模型更稀疏。

        從圖1的(c)與(f)中可以看出無論增量次數(shù)T和增量樣本量N取何值,基于選擇性抽樣的SVM增量學(xué)習(xí)算法學(xué)習(xí)效率有很大程度的提升。

        圖1 實驗結(jié)果詳細對比圖

        3.3 與文獻[15]中算法對比

        1)算法對比:自Syed等人[7]提出增量學(xué)習(xí)算法以來,以其優(yōu)異的算法性能得到了許多學(xué)者的青睞,同時很多改進的增量學(xué)習(xí)算法也相繼被提出,雖然在算法性能上有一定程度的優(yōu)化,但基本都是建立在樣本是獨立同分布的假設(shè)情形,本質(zhì)并沒有改變。

        Xu等人[15]提出的增量學(xué)習(xí)算法,其核心也是利用馬氏抽樣選取樣本進行增量學(xué)習(xí)(X-ISVM)。基于選擇性抽樣的SVM增量學(xué)習(xí)算法(M-ISVM)與之最大的區(qū)別有以下幾點:

        (1)X-ISVM算法在訓(xùn)練集上沒有進行子集劃分,在整體訓(xùn)練集進行樣本選取。M-ISVM算法則是在每一個數(shù)據(jù)子集上選取樣本。

        (2)X-ISVM算法馬氏抽樣的初始轉(zhuǎn)移概率是依據(jù)第一次隨機抽樣的分類模型定義,M-ISVM算法是通過合成2→T的數(shù)據(jù)子集的分類模型來定義馬氏抽樣的初始轉(zhuǎn)移概率。

        (3)文獻[15]實驗中數(shù)據(jù)集都以T=10,N=500(T=20,N=300;T=20,N=400;T=30,N=200)為基準進行增量學(xué)習(xí),增量樣本數(shù)據(jù)量選取數(shù)據(jù)量較小,不具備說服力;M-ISVM算法則是根據(jù)數(shù)據(jù)子集規(guī)模的大小來定義N的值,且N值一般定義較大。

        2)數(shù)值實驗與結(jié)果:為更好地比較兩種算法的泛化能力,在基準數(shù)據(jù)集下,對于每一個數(shù)據(jù)集分別進行T=10,N=500(T=10N依據(jù)劃分的數(shù)據(jù)子集規(guī)模定義較大值);T=20,N=300(T=20N依據(jù)數(shù)據(jù)子集規(guī)模定義較大值)的實驗,對于每個數(shù)據(jù)集實驗重復(fù)5次,然后根據(jù)每次實驗增量最后的分類模型求取五次實驗的平均錯分率,平均支持向量和5次抽樣與訓(xùn)練的總時間(s)。

        表3 T次(T=10)增量學(xué)習(xí)后實驗結(jié)果對比

        表4 T次(T=10)增量學(xué)習(xí)后實驗結(jié)果對比

        表5 T次(T=20)增量學(xué)習(xí)后實驗結(jié)果對比

        表6 T次(T=20)增量學(xué)習(xí)后實驗結(jié)果對比

        表3為在T=10,N=500時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實驗數(shù)據(jù);表5為在T=10N依據(jù)數(shù)據(jù)子集規(guī)模取值時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實驗數(shù)據(jù)。

        表5為在T=20,N=300時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實驗數(shù)據(jù);表6為在T=20N依據(jù)數(shù)據(jù)子集規(guī)模取值時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實驗數(shù)據(jù)。

        表中的第一列為“數(shù)據(jù)集名-數(shù)字”,如“Skin-500”表示從Skin數(shù)據(jù)集中每次增量500個訓(xùn)練樣本,即算法中N=500。

        從表3~6中可以看出,M-ISVM算法,在增量次數(shù)相同的情況下,增量的樣本量無論大小,平均錯分率,平均支持向量,抽樣與訓(xùn)練總時間表現(xiàn)都優(yōu)于X-ISVM算法,且方差更低,說明算法穩(wěn)定性好。因為M-ISVM算法在馬氏抽樣起始轉(zhuǎn)移概率的定義上利用了2→T的數(shù)據(jù)子集的分類模型,而X-ISVM算法只利用了第一次隨機抽樣的分類模型,在每次增量的數(shù)據(jù)上,M-ISVM算法分別從每一次數(shù)據(jù)子集中選取,而X-ISVM則在整體訓(xùn)練集中選取,所以M-ISVM算法能更好地兼顧全局性,很大程度上避免實驗結(jié)果的偶然性。實驗結(jié)果表明,M-ISVM算法的泛化性能優(yōu)于X-ISVM算法。

        4 結(jié)束語

        傳統(tǒng)的增量學(xué)習(xí)都是建立在樣本是獨立同分的假設(shè)情形下,樣本的選取都是基于獨立隨機抽樣,這種假設(shè)并不能完全符合實際環(huán)境中樣本的分布情況。基于選擇性抽樣的SVM增量學(xué)習(xí)算法,通過減弱樣本是獨立同分布的假設(shè)情形,利用馬氏抽樣方式選取具有一致遍歷馬爾可夫鏈性質(zhì)的樣本進行增量學(xué)習(xí),文章中與基于隨機抽樣的SVM增量學(xué)習(xí)算法和文獻[15]提出的算法做出比較。實驗結(jié)果表明,基于選擇性抽樣的SVM增量學(xué)習(xí)算法在SVM分類問題上泛化性能更好。

        猜你喜歡
        分率馬爾可夫增量
        量率對應(yīng) 解決問題
        提質(zhì)和增量之間的“辯證”
        “價增量減”型應(yīng)用題點撥
        解分數(shù)問題例談
        分數(shù)應(yīng)用題常見錯例剖析
        基于均衡增量近鄰查詢的位置隱私保護方法
        保費隨機且?guī)в屑t利支付的復(fù)合馬爾可夫二項模型
        基于SOP的核電廠操縱員監(jiān)視過程馬爾可夫模型
        利用分率巧解題
        應(yīng)用馬爾可夫鏈對品牌手機市場占有率進行預(yù)測
        久久精品国产亚洲av调教| 久久精品国产亚洲av蜜臀| 一级免费毛片| 亚洲国产精品久久久久婷婷软件| 日本一区二区三区丰满熟女| 狠狠色丁香婷婷久久综合| 成人网站免费大全日韩国产| 亚洲欧洲日产国码无码AV一| 久久99精品波多结衣一区| 一区二区三区在线观看视频精品 | 999国内精品永久免费视频| 91精品久久久久含羞草| 国产白浆一区二区三区佳柔 | 在线视频播放观看免费| 亚洲av无码专区国产乱码4se| 无码精品日韩中文字幕| 国产无码十八禁| 国产精品毛片毛片av一区二区| 国产69久久精品成人看| 台湾佬娱乐中文22vvvv| 久久国产精品免费一区六九堂 | 亚洲av五月天一区二区| 99久久免费国产精品| 91视频88av| 日韩av他人妻中文字幕| 色哟哟亚洲色精一区二区| 免费观看性欧美大片无片| 国产午夜精品久久久久99| 男女啪啪动态视频在线观看| 国产又大又硬又粗| 7878成人国产在线观看| 男女干逼视频免费网站| 日本一二三区在线观看视频| 亚洲色欲久久久综合网| 亚洲福利天堂网福利在线观看| 乳乱中文字幕熟女熟妇| 中文无码伦av中文字幕| 亚洲91av| 国产免费一区二区三区三| 极品尤物一区二区三区| 一本一本久久a久久精品综合|