許道云
摘 要:實(shí)例空間X的一個子集規(guī)定一個概念,表現(xiàn)為一個函數(shù)c:X→{0,1}。給定X上一個分布D,可能近似正確(PAC)學(xué)習(xí)算法的目的是基于獨(dú)立同分布樣本S,由算法產(chǎn)生一個近似函數(shù)hS,以高概率保證它與目標(biāo)函數(shù)c的誤差不超過給定誤差值。如果存在這樣的算法其樣本復(fù)雜性及時間復(fù)雜性受多項(xiàng)式界,則認(rèn)為目標(biāo)概念可以有效PAC學(xué)習(xí)。本文討論二維歐氏空間上有界線性凸區(qū)域定義的目標(biāo)概念的學(xué)習(xí)理論和方法,證明了有界線性凸區(qū)域定義的目標(biāo)概念是有效PAC可學(xué)習(xí)的,其方法可以推廣到n維歐氏空間上由超平面界定的有界凸區(qū)域?qū)?yīng)的目標(biāo)概念學(xué)習(xí)。
關(guān)鍵詞:
二維歐氏空間;線性凸區(qū)域;概念學(xué)習(xí);PAC算法
中圖分類號:TP301.6
文獻(xiàn)標(biāo)識碼: A
在機(jī)器學(xué)習(xí)中,對給定實(shí)例進(jìn)行分類是一種基本處理方法,其中二分類是重要而基礎(chǔ)的分類問題。當(dāng)實(shí)例空間較大或復(fù)雜時,精準(zhǔn)分類變得復(fù)雜或困難,依采樣進(jìn)行近似分類顯得有效和實(shí)用??赡芙普_(Probably Approximately Correct, PAC)算法提供了一種學(xué)習(xí)架構(gòu),其原理來源于依概率收斂假設(shè)。假定實(shí)例空間依賴于某個分布,通過獨(dú)立取樣得到容量為m的樣本S,如果存在一個算法A能夠產(chǎn)生一個輸出函數(shù)hS,當(dāng)m趨于無窮大時,hS依概率收斂于目標(biāo)函數(shù)c是PAC可學(xué)習(xí)的。形式上,對于任意給的誤差參數(shù)0<ε<1以及可靠性參數(shù)0<δ<1,存在一個正整數(shù)M,當(dāng)樣本容量m超過M時,算法輸出一個近似分類函數(shù)hS,至少以概率為(1-δ)確保hS與目標(biāo)分類函數(shù)c的誤差不超過ε。如果存在這樣的算法,其樣本復(fù)雜性M和算法的時間復(fù)雜性受1/ε,1/δ的多項(xiàng)式界,則稱目標(biāo)概念c是可以有效PAC學(xué)習(xí)的。PAC學(xué)習(xí)中,往往加強(qiáng)到對目標(biāo)概念集C、任意分布D下尋找有效PAC學(xué)習(xí)算法。如果這樣的算法存在,則稱概念集C是可以有效PAC學(xué)習(xí)的。
在本文中,假定實(shí)例空間X為二維歐氏空間R2,R2的一個子集的特征函數(shù)c:R2→{0,1}規(guī)定一個概念。文章重點(diǎn)討論有界線性凸區(qū)域規(guī)定的概念的PAC學(xué)習(xí)理論和方法,線性凸區(qū)域是由一組線性不等式界定的區(qū)域{(x,y):aix+biy≤ci(i=1,2,……,k)},有界性指區(qū)域內(nèi)的點(diǎn)被一個有界矩形(或圓)包含,目標(biāo)概念c定義為:c(x,y)=1aix+biy≤ci(i=1,2,……,k)成立。 本文給出了這類概念學(xué)習(xí)的理論和方法,并證明了它是可以有效PAC學(xué)習(xí)的。相關(guān)的理論和方法容易推廣到n維歐氏空間由超平面界定的有界凸區(qū)域規(guī)定的目標(biāo)概念的PAC學(xué)習(xí)。
這類概念的學(xué)習(xí)可以用于大范圍線性規(guī)劃問題可行解的近似識別。
1 PAC學(xué)習(xí)基礎(chǔ)知識
假定X為實(shí)例(數(shù)據(jù))空間,有限集Y作為數(shù)據(jù)標(biāo)記集,通常取Y={0,1}(或{-1,+1})。一個函數(shù)f:X→Y決定X中數(shù)據(jù)一個劃分(分類):f(x)=f(y)當(dāng)且僅當(dāng)x,y屬于同一類。X的一個子集稱為一個概念,可用其特征函數(shù)表示該子集。因此,形式上一個函數(shù)c:X→{0,1}表示一個概念,由概念構(gòu)成的集合C稱為概念集。本文中相關(guān)的基本知識來自于文獻(xiàn)[1], 更多的實(shí)例和應(yīng)用可參考文獻(xiàn)[2-4]。
5 結(jié)語
本文將軸對齊矩形概念的有效PAC學(xué)習(xí)方法一般化到歐氏平面上有界線性凸區(qū)域規(guī)定的概念學(xué)習(xí),其思想和方法在于有界線性凸區(qū)域是由有限條(k條)直線圍成的多邊形區(qū)域,在Pr[A]>ε條件下,幾何上可以構(gòu)造目標(biāo)區(qū)域A的邊界內(nèi)側(cè)的一條ε/k-環(huán)帶,該環(huán)帶由k個概率是ε/k區(qū)域構(gòu)成。并且,在條件Pr[A]>ε下,依樣本S從算法產(chǎn)生的目標(biāo)區(qū)域AS與其中之一不相交,此時有PrS~Dm[er(A,AS)>ε]≤k(1-εk)m≤kexp(-mεk)成立,由此估計(jì)算法的樣本復(fù)雜性。文中的方法對于n維歐氏空間中由超平面界定的有界線性凸區(qū)域的PAC學(xué)習(xí)方法與分析是有效的。
文中的方法適用于數(shù)據(jù)集中的數(shù)據(jù)按預(yù)定凸區(qū)域聚類及誤差分析,也可通過適當(dāng)變換在非歐空間中討論P(yáng)AC學(xué)習(xí)算法。
參考文獻(xiàn):
[1]MOHRI M,ROSTAMIZADEH A,TALWAKAR A.Foundations of Machine Learning[M].Cambridge:The MIT Press,2012.
[2]MITCHELL T M.機(jī)器學(xué)習(xí)[M].曾華軍,等譯.北京:機(jī)械工業(yè)出版社,2012.
[3]周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016.
[4]GOODFELLOW I,BENGIO Y,COURVILLE A.深度學(xué)習(xí)[M].趙申劍,等譯.北京:中國工信出版集團(tuán),2017.
(責(zé)任編輯:周曉南)