許道云

摘 要：實(shí)例空間X的一個(gè)子集規(guī)定一個(gè)概念，表現(xiàn)為一個(gè)函數(shù)c：X→{0，1}。給定X上一個(gè)分布D，可能近似正確（PAC）學(xué)習(xí)算法的目的是基于獨(dú)立同分布樣本S，由算法產(chǎn)生一個(gè)近似函數(shù)hS，以高概率保證它與目標(biāo)函數(shù)c的誤差不超過(guò)給定誤差值。如果存在這樣的算法其樣本復(fù)雜性及時(shí)間復(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算法

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼： A

在機(jī)器學(xué)習(xí)中，對(duì)給定實(shí)例進(jìn)行分類(lèi)是一種基本處理方法，其中二分類(lèi)是重要而基礎(chǔ)的分類(lèi)問(wèn)題。當(dāng)實(shí)例空間較大或復(fù)雜時(shí)，精準(zhǔn)分類(lèi)變得復(fù)雜或困難，依采樣進(jìn)行近似分類(lèi)顯得有效和實(shí)用?？赡芙普_（Probably Approximately Correct， PAC）算法提供了一種學(xué)習(xí)架構(gòu)，其原理來(lái)源于依概率收斂假設(shè)。假定實(shí)例空間依賴(lài)于某個(gè)分布，通過(guò)獨(dú)立取樣得到容量為m的樣本S，如果存在一個(gè)算法A能夠產(chǎn)生一個(gè)輸出函數(shù)hS，當(dāng)m趨于無(wú)窮大時(shí)，hS依概率收斂于目標(biāo)函數(shù)c是PAC可學(xué)習(xí)的。形式上，對(duì)于任意給的誤差參數(shù)0<ε<1以及可靠性參數(shù)0<δ<1，存在一個(gè)正整數(shù)M，當(dāng)樣本容量m超過(guò)M時(shí)，算法輸出一個(gè)近似分類(lèi)函數(shù)hS，至少以概率為（1-δ）確保hS與目標(biāo)分類(lèi)函數(shù)c的誤差不超過(guò)ε。如果存在這樣的算法，其樣本復(fù)雜性M和算法的時(shí)間復(fù)雜性受1/ε，1/δ的多項(xiàng)式界，則稱(chēng)目標(biāo)概念c是可以有效PAC學(xué)習(xí)的。PAC學(xué)習(xí)中，往往加強(qiáng)到對(duì)目標(biāo)概念集C、任意分布D下尋找有效PAC學(xué)習(xí)算法。如果這樣的算法存在，則稱(chēng)概念集C是可以有效PAC學(xué)習(xí)的。

在本文中，假定實(shí)例空間X為二維歐氏空間R2，R2的一個(gè)子集的特征函數(shù)c：R2→{0，1}規(guī)定一個(gè)概念。文章重點(diǎn)討論有界線性凸區(qū)域規(guī)定的概念的PAC學(xué)習(xí)理論和方法，線性凸區(qū)域是由一組線性不等式界定的區(qū)域{（x，y）：aix+biy≤ci（i=1，2，……，k）}，有界性指區(qū)域內(nèi)的點(diǎn)被一個(gè)有界矩形（或圓）包含，目標(biāo)概念c定義為：c（x，y）=1aix+biy≤ci（i=1，2，……，k）成立。 本文給出了這類(lèi)概念學(xué)習(xí)的理論和方法，并證明了它是可以有效PAC學(xué)習(xí)的。相關(guān)的理論和方法容易推廣到n維歐氏空間由超平面界定的有界凸區(qū)域規(guī)定的目標(biāo)概念的PAC學(xué)習(xí)。

這類(lèi)概念的學(xué)習(xí)可以用于大范圍線性規(guī)劃問(wèn)題可行解的近似識(shí)別。

1 PAC學(xué)習(xí)基礎(chǔ)知識(shí)

假定X為實(shí)例（數(shù)據(jù)）空間，有限集Y作為數(shù)據(jù)標(biāo)記集，通常取Y={0，1}（或{-1，+1}）。一個(gè)函數(shù)f：X→Y決定X中數(shù)據(jù)一個(gè)劃分（分類(lèi)）：f（x）=f（y）當(dāng)且僅當(dāng)x，y屬于同一類(lèi)。X的一個(gè)子集稱(chēng)為一個(gè)概念，可用其特征函數(shù)表示該子集。因此，形式上一個(gè)函數(shù)c：X→{0，1}表示一個(gè)概念，由概念構(gòu)成的集合C稱(chēng)為概念集。本文中相關(guān)的基本知識(shí)來(lái)自于文獻(xiàn)[1]， 更多的實(shí)例和應(yīng)用可參考文獻(xiàn)[2-4]。

5 結(jié)語(yǔ)

本文將軸對(duì)齊矩形概念的有效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個(gè)概率是ε/k區(qū)域構(gòu)成。并且，在條件Pr[A]>ε下，依樣本S從算法產(chǎn)生的目標(biāo)區(qū)域AS與其中之一不相交，此時(shí)有PrS～Dm[er（A，AS）>ε]≤k（1-εk）m≤kexp（-mεk）成立，由此估計(jì)算法的樣本復(fù)雜性。文中的方法對(duì)于n維歐氏空間中由超平面界定的有界線性凸區(qū)域的PAC學(xué)習(xí)方法與分析是有效的。

文中的方法適用于數(shù)據(jù)集中的數(shù)據(jù)按預(yù)定凸區(qū)域聚類(lèi)及誤差分析，也可通過(guò)適當(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].趙申劍，等譯.北京：中國(guó)工信出版集團(tuán)，2017.

（責(zé)任編輯：周曉南）