二維歐氏空間內(nèi)線性凸區(qū)域概念的PAC學(xué)習(xí)算法

許道云

摘 要：實(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é)任編輯：周曉南）