許道云

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025)

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

這類概念的學(xué)習(xí)可以用于大范圍線性規(guī)劃問題可行解的近似識(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è)劃分(分類):f(x)=f(y)當(dāng)且僅當(dāng)x,y屬于同一類。X的一個(gè)子集稱為一個(gè)概念，可用其特征函數(shù)表示該子集。因此，形式上一個(gè)函數(shù)c:X→{0,1}表示一個(gè)概念，由概念構(gòu)成的集合C稱為概念集。本文中相關(guān)的基本知識(shí)來自于文獻(xiàn)[1], 更多的實(shí)例和應(yīng)用可參考文獻(xiàn)[2-4]。

機(jī)器學(xué)習(xí)的任務(wù)是通過帶某種樣本(或經(jīng)驗(yàn))的算法學(xué)習(xí)方式得到一個(gè)近似函數(shù)c′:X→{0,1}，其中c與c′之間的“距離”誤差通常用概率表示er(c,c′):=Prx～D[c(x)≠c′(x)]，其中D表示空間X上的某個(gè)分布，而c′是可以由算法產(chǎn)生。

對(duì)于給定的概念集C, 以C中元作為目標(biāo)概念，能夠由算法產(chǎn)生的所有可能的近似函數(shù)構(gòu)成的集合稱為假設(shè)空間H。一般C與H不同，通常假定C?H。對(duì)于一個(gè)目標(biāo)概念c及一個(gè)假設(shè)h∈H，其泛化誤差定義為：

er(c,h) =Prx～D[c(x)≠h(x)]

=Ex～D[1c(x)≠h(x)]，

(1)

其中，函數(shù)1P為指性函數(shù)(條件P成立時(shí)取1，否則取0)。當(dāng)c固定時(shí)，在不引起歧義的情況下，簡(jiǎn)記為：R(h)=Prx～D[c(x)≠h(x)]。它是隨機(jī)變量1c(x)≠h(x)的數(shù)學(xué)期望，理論上是一個(gè)整體概念。

對(duì)于目標(biāo)概念c的算法學(xué)習(xí)，通常是采用抽樣學(xué)習(xí)，即依分布D下獨(dú)立取樣得到一個(gè)大小為m樣本S={x1,x2,……,xn},對(duì)于樣本S, 假定其樣本點(diǎn)的分類標(biāo)記可觀察到，從而形成一個(gè)帶標(biāo)記的數(shù)據(jù)集：

{(x1,y1),(x2,y2),……,(xn,yn)}，

基于樣本S及假設(shè)h，以如下公式定義h的經(jīng)驗(yàn)誤差：

(2)

對(duì)于給定的目標(biāo)概念c以及樣本S={x1,x2,……,xn}，帶標(biāo)樣本集為{(x1,y1),(x2,y2),……,(xn,yn)},如果c(xi)=yi(1≤i≤m)，稱樣本S與目標(biāo)概念c一致。一般選擇一個(gè)訓(xùn)練集(作為樣本集)與目標(biāo)概念c一致。

在學(xué)習(xí)算法中，有時(shí)可以通過目標(biāo)概念c對(duì)樣本S中樣本點(diǎn)進(jìn)行標(biāo)記。如：目標(biāo)概念為一個(gè)矩形cR時(shí)，落入cR內(nèi)的樣本點(diǎn)被標(biāo)記為1，否則標(biāo)記為0。此時(shí)，樣本S與目標(biāo)概念cR自然一致。

對(duì)一個(gè)假設(shè)h, 如果h(xi)=yi(1≤i≤m)，稱假設(shè)h與樣本S一致。

對(duì)于學(xué)習(xí)算法A, 如果對(duì)于任意的目標(biāo)概念c及任意獨(dú)立同分布(i.i.d.)樣本S, 以c和S作為算法的輸入，算法輸出的假設(shè)hS與樣本S一致，則稱算法A為樣本一致學(xué)習(xí)算法。

對(duì)于0<ε<1,0<δ<1，視ε為誤差參數(shù)，δ為可靠性參數(shù)，對(duì)于給定的目標(biāo)概念c以及假設(shè)空間H,一個(gè)假設(shè)h被稱為ε-good假設(shè)，如果泛化誤差R(h)≤ε；否則稱h為ε-bad假設(shè)。

PAC算法的核心問題是：設(shè)計(jì)一個(gè)學(xué)習(xí)算法A,使得由算法通過樣本學(xué)習(xí)(輸出)的hS是ε-bad假設(shè)的概率小于δ；或者說，通過對(duì)樣本的學(xué)習(xí)，算法輸出的hS是ε-good假設(shè)的概率至少是1-δ。

形式上表現(xiàn)為：將hS表示為A(S,c)=hS，以示算法A以(S,c)作為輸入，輸出hS。hS作為一個(gè)隨機(jī)變量函數(shù)滿足如下條件：

PrS～Dm[er(hS)>ε]<δor

PrS～Dm[er(hS)≤ε]≥1-δ，

(3)

這樣的算法(ε,δ)-學(xué)習(xí)算法，其中m稱為算法的樣本復(fù)雜性。

對(duì)于一個(gè)目標(biāo)概念c, 如果對(duì)于任意的參數(shù)對(duì)(ε,δ)，存在一個(gè)(ε,δ)-學(xué)習(xí)算法A 滿足條件：算法的樣本復(fù)雜性的下界被一個(gè)1/ε,1/δ,size(c)的多項(xiàng)式保護(hù)；即，存在一個(gè)多項(xiàng)式p(1/ε,1/δ,size(c))，使得對(duì)于任意的分布D,當(dāng)m≥p(1/ε,1/δ,size(c))時(shí)，算法輸出的假設(shè)hS滿足(3)式，則稱c是通過樣本PAC-可學(xué)習(xí)的，簡(jiǎn)稱PAC-可學(xué)習(xí)。

進(jìn)一步，如果算法A是關(guān)于1/ε,1/δ,size(c)的一個(gè)多項(xiàng)式算法，則稱目標(biāo)概念c是PAC-有效可學(xué)習(xí)的，對(duì)應(yīng)的算法稱為有效的PAC算法。一般，本質(zhì)上主要依賴于1/ε,1/δ的多項(xiàng)式。

可以看出：PAC算法的主要任務(wù)是基于樣本S，通過算法從假設(shè)空間H是獲取一個(gè)假設(shè)(函數(shù))hS，以其近似目標(biāo)概念(函數(shù))c，使其在任意給定的參數(shù)對(duì)0<ε,δ<1及任意分布D下，滿足條件(3),并且樣本復(fù)雜性下界受1/ε,1/δ的多項(xiàng)式保護(hù)。有效性則加強(qiáng)到算法本身的時(shí)間復(fù)雜性受1/ε,1/δ的多項(xiàng)式控制。

對(duì)概念c的學(xué)習(xí)實(shí)質(zhì)上是一種“函數(shù)逼近”，只不過這種逼近是依靠增大樣本容量提高精度(減小誤差)，問題是當(dāng)樣本復(fù)雜性要求受多項(xiàng)式保護(hù)時(shí)，如何設(shè)計(jì)合適的隨機(jī)算法，以保證當(dāng)樣本量m達(dá)到某個(gè)多項(xiàng)式p(1/ε,1/δ)級(jí)時(shí)，得到的hS滿足“至少以1-δ的概率使R(hS)≤ε。

一般，對(duì)于給定的目標(biāo)概念c、以及樣本實(shí)例S={x1,x2,……,xn}，算法產(chǎn)生的hS在S上可能不一致。可能會(huì)出現(xiàn)兩類錯(cuò)誤：正錯(cuò)(1-錯(cuò))：c(xi)=0，但hS(xi)=1；負(fù)錯(cuò)(0-錯(cuò))：c(xi)=1，但hS(xi)=0。

如果只產(chǎn)生一類錯(cuò)誤，則稱算法為單側(cè)隨機(jī)算法。當(dāng)樣本容量m固定時(shí)，算法分析的任務(wù)集中在估計(jì)概率PrS～Dm[er(hS)>ε]的上界，它是一個(gè)以(m,ε)為參數(shù)的函數(shù)e(m,ε)。最終，令e(m,ε)<δ反解出m≥m(ε,δ)，并檢驗(yàn)m(ε,δ)被一個(gè)1/ε,1/δ的多項(xiàng)式控制。

我們注意到：函數(shù)f:X→{0,1}與一個(gè)X的子集{x∈X:f(x)=1}一一對(duì)應(yīng)。為方便起見仍然記為f。在不引起歧義的情況下，x∈f指f(x)=1。對(duì)于X的一個(gè)分布D, 將概率Prx～D[x∈f]=Prx～D[f(x)=1]記為Prx～D[f]。于是，泛化誤差er(c,h)=Prx～D[c⊕h]，其中⊕表示集合之間的對(duì)稱差。

對(duì)于目標(biāo)概念c和假設(shè)h, 以h近似c的正錯(cuò)誤差和負(fù)錯(cuò)誤差分別為：

er1(c,h)=Prx～D[hc],er0(c,h)=Prx～D[ch]并且er(c,h)=er1(c,h)+er0(c,h)。

用圖1表示其誤差關(guān)系：

圖1 概念c與假設(shè)h之間的誤差Fig.1 Error between concept c and hypothesish

2 學(xué)習(xí)算法的樣本復(fù)雜性估計(jì)方法

本節(jié)通過一個(gè)經(jīng)典的目標(biāo)概念學(xué)習(xí)范例，介紹一種學(xué)習(xí)算法樣本復(fù)雜性估計(jì)的方法。

取實(shí)例空間X為二維歐氏平面R2，標(biāo)記集取為Y={0,1}。在平面上，邊平行于座標(biāo)軸的矩形稱為軸對(duì)齊矩形。以軸對(duì)齊矩形r作為目標(biāo)概念cr，對(duì)于點(diǎn)x∈R2,cr(x)=1?x∈r(含矩形邊界)。

考慮如下PAC學(xué)習(xí)算法A：

(1) 輸入一個(gè)矩形r；

(2) 依分布D以i.i.d.在平面R2取樣S={x1,x2,……,xn}；(固定某個(gè)分布D)

(3) 記落入矩形r的樣本點(diǎn)為Sr，在平面R2取一個(gè)含Sr中點(diǎn)的最小軸對(duì)齊矩形rS;

(4) 輸出rS決定的假設(shè)(函數(shù))hS(hS(x)=1?

x∈rS(x∈R2))。

可以看出：算法中產(chǎn)生的rS?r。從而，輸出的假設(shè)(函數(shù))hS“只可能出現(xiàn)負(fù)錯(cuò)，不會(huì)出現(xiàn)正錯(cuò)”。

以下過程是估計(jì)樣本復(fù)雜性：對(duì)于任意給定的0<ε<1，估計(jì)PrS～Dm[er(hS)>ε]的上界。

當(dāng)er(r)≤ε時(shí)，即er(r)=Prx～D[x∈r]≤ε。由于rS?r，自然有er(rS)=Prx～D[x∈rS]≤ε。從而PrS～Dm[er(hS)≤ε]=1，或PrS～Dm[er(hS)>ε]=0。

因此，不妨假設(shè)er(r)=Prx～D[x∈r]>ε。從幾何上，視矩形r的面積大于ε。

于是，從r的四條邊開始，分別以每條邊向r的內(nèi)部從空矩形開始以線掃描式擴(kuò)充成四個(gè)軸對(duì)齊矩形r1,r2,r3,r4，使其滿足如下條件：

Prx～D[ri]=ε/4(i=1,2,3,4),

(4)

由于Prx～D[r]>ε，四個(gè)小矩形r1,r2,r3,r4的生成是可行的。幾何上表現(xiàn)為如圖2。

圖2 目標(biāo)概念r內(nèi)部邊緣區(qū)域Fig.2 Marginal area inside of traget concept r

由四個(gè)小矩形的構(gòu)造方法，我們有：

Prx～D[r1∪r2∪r3∪r4]

≤Prx～D[r1]+Prx～D[r2]+Prx～D[r3]+Prx～D[r4]=ε。

(5)

直觀上，r1,r2,r3,r4構(gòu)成目標(biāo)概念內(nèi)側(cè)的一個(gè)ε-環(huán)帶，簡(jiǎn)稱為r的一個(gè)單(內(nèi))側(cè)ε-區(qū)域。該區(qū)域由4個(gè)ε/4段構(gòu)成。

由算法中矩形rS的構(gòu)造及rS?r，er(hS)=Prx～D[r S]。因此，如果er(hS)>ε，則矩形rS至少與r1,r2,r3,r4之一的交為空集。若不然，rS與r1,r2,r3,r4的交都不空，則由軸對(duì)齊性質(zhì)，矩形rS在幾何上呈現(xiàn)如圖3中虛線矩形狀態(tài)。

圖3 基于樣本S的假設(shè)hS與4個(gè)子區(qū)域相交Fig.3 Hypothesie hS based on sample S intersects with four subareas

于是，由rS決定的假設(shè)(函數(shù))hS滿足：

er(hS)

=Prx～D[r S]

≤Prx～D[r1∪r2∪r3∪r4]

≤Prx～D[r1]+Prx～D[r2]+Prx～D[r3]+Prx～D[r4]

≤ε，

此與er(hS)>ε矛盾。

因此，我們有：如果er(hS)>ε，則rS與r1,r2,r3,r4的之一的交為空集。

不妨設(shè)rS∩r1=?，此時(shí)矩形rS在幾何上呈現(xiàn)如圖4中虛線矩形狀態(tài)。

圖4 基于樣本S的假設(shè)hS與4個(gè)子區(qū)域之一不相交目Fig.4 Hhypothesie hS based on sample S does not intersects with one of four subareas

可見，一次取樣事件“rS∩r1=?”發(fā)生等價(jià)于“樣本點(diǎn)不落入r1”，其概率至多為(1-ε/4)。

從而，m次獨(dú)立取樣“m個(gè)樣本點(diǎn)不落入r1” 的概率至多為(1-ε/4)m。因此，我們有：

PrS～Dm[er(hS)>ε]

≤4(1-ε/4)m。

(6)

由不等式1-x0)，有PrS～Dm[er(hS)>ε]≤4(1-ε/4)m<4exp(-mε/4)。

注：在學(xué)習(xí)算法A的第(3)步中，我們可以取一個(gè)包含目標(biāo)矩形r，并且不含落在r外側(cè)的樣本點(diǎn)的最大軸對(duì)齊矩形作為hS。 此時(shí)算法“只出現(xiàn)正錯(cuò)，而不會(huì)出現(xiàn)負(fù)錯(cuò)”。討論方法是對(duì)稱的。

上述方法的主要思想是：

構(gòu)造目標(biāo)概念c的一個(gè)單側(cè)概率ε-區(qū)域，該區(qū)域由4個(gè)ε/4段構(gòu)成。在er(hS)>ε條件下，算法基于樣本S產(chǎn)生的假設(shè)rS至少與r1,r2,r3,r4的之一不相交(比如：不落入r1)。由此，對(duì)于一次取樣，事件“rS∩r1=?”發(fā)生的概率至多為(1-ε/4)，m次取樣不落入該子區(qū)域的概率至多為(1-ε/4)m。由(6)式估計(jì)樣本復(fù)雜性。

3 二維有界線性凸區(qū)域表示及誤差區(qū)域

二維平面R2上線性凸區(qū)域A由一組線性不等式規(guī)定：

aix+biy≤ci(i=1,2,……,k),

(7)

其矩陣形式為：

(8)

定義A={(x,y)∈R2:aix+biy≤ci(i=1,2,……,k)}。若存在一個(gè)正數(shù)M>0,使得對(duì)任意的(x,y)∈A，有|x|+|y|≤M，則稱A有界。幾何上它由k條邊aix+biy=ci(i=1,2,……,k)圍成的封閉有界區(qū)域。如圖5所示。

為方便討論，不妨假定(7) 式中每一個(gè)不等式都是獨(dú)立的。即，任意刪去一個(gè)不等式將得到另一個(gè)更大的區(qū)域。

圖5 封閉的有界凸區(qū)域Fig.5 Closed bounded convex region

形式上，一個(gè)軸對(duì)齊矩形r可以定義為：

r={(x,y)∈R2:a≤x≤b,c≤y≤d}(a

它對(duì)應(yīng)一組不等式a≤x,x≤b,c≤y,y≤d。等價(jià)于

-x≤-a,x≤b,-y≤-c,y≤d,

統(tǒng)一到式(7)形式，其矩陣形式為：

給定平面R2一個(gè)分布D, 對(duì)于固定的0<ε<1，假定Pr(x,y)～D[A]>ε，則存在一個(gè)正向量(δ1,δ2,δ3,δ4)T(稱為帶寬向量)滿足如下條件：

(1)子矩形條件

(9)

(2) 邊界區(qū)域分段區(qū)域概率均分條件(對(duì)照?qǐng)D2中r1,r2,r3,r4)

(10)

Pr(x,y)～D[A1]

=Pr(x,y)～D[A2]=Pr(x,y)～D[A3]

=Pr(x,y)～D[A4]=ε/4。

(11)

概率均分在每個(gè)小區(qū)域上這主要是為了描述方便。其實(shí)，不必要求概率均分，只需4個(gè)正常數(shù)

為將方法延伸到一般凸區(qū)域。我們可能通過如下方法得到A1,A2,A3,A4。

以A1為例：A1對(duì)應(yīng)約束條件 -x≤-a，帶寬參數(shù)為δ1。

直線-x=-a“下移”δ1，得到新的約束條件：-x≤-a-δ1。其它約束條件不變，得到一個(gè)子區(qū)域：

邊界段子區(qū)域A1=r-B1(原始矩形r減去

其它約束條件對(duì)應(yīng)的子區(qū)域?yàn)椋?/p>

邊界區(qū)域是為誤差分析設(shè)定的。

上述方法具有一般性，它是一般二維凸區(qū)域規(guī)定的目標(biāo)概念學(xué)習(xí)的基礎(chǔ)。

一般地，對(duì)于由(8)式定義的二維有界線性凸區(qū)域A, 在給定分布D下，假定Pr[A]>ε，必有正帶寬向量(δ1,δ2,……,δk)T，滿足條件：

(12)

及k個(gè)子區(qū)域：

(13)

其中ei=(0,…,0,1,0,…,0)T為k維單位向量中的i個(gè)向量。即，除第i個(gè)分量為1外，其余分量均為0。

4 二維有界線性凸區(qū)域目標(biāo)概念的PAC學(xué)習(xí)算法

設(shè)目標(biāo)概念c:R2→{0,1}由二維平面R2上有界線性凸區(qū)域A規(guī)定。凸區(qū)域A由一組線性不等式給出：A={(x,y)∈R2:aix+biy≤ci(i=1,2,……,k)}。

假定在R2賦予一個(gè)分布D, 設(shè)S為容量為m獨(dú)立同分布樣本：

S=(P1,……,Pm),Pj=(xj,yj)(1≤j≤m)。

PAC學(xué)習(xí)算法B：

(1)輸入凸區(qū)域A：aix+biy≤ci(i=1,2,……,k)}，及樣本

S=(P1,……,Pm)Pj=(xj,yj)(1≤j≤m);

(2)對(duì)每個(gè)i=1,2,……,k，計(jì)算

(3)輸出凸區(qū)域AS:aix+biy≤ci-di(i=1,2,……,k)}。

注：(1) 在算法B中，如果有樣本點(diǎn)Pj=(xj,yj)落入?yún)^(qū)域A內(nèi)部, 則對(duì)每個(gè)i,有di>0。

(2) 算法輸出的凸區(qū)域AS是區(qū)域A內(nèi)包含S中樣本點(diǎn)的最小同型凸區(qū)域。這里同型指邊界直線由原始區(qū)域邊界直線平移得到(因?yàn)榧s束條件的系數(shù)矩陣不變)。

余下對(duì)算法的分析基本上與(軸對(duì)齊矩形概念)學(xué)習(xí)算法A的分析路徑一致。

定理：二維歐氏空間上由有界結(jié)性凸區(qū)域定義的目標(biāo)概念是有效PAC可學(xué)習(xí)的。

證明：含有k個(gè)約束條件的有界結(jié)性凸區(qū)域A可以由3k個(gè)參數(shù)(ai,bi,ci)(i=1,2,……,k)確定。因此，可以用3k來度量A的規(guī)模。由于k作為一個(gè)常數(shù)，獨(dú)立于樣本性和時(shí)間復(fù)雜性本質(zhì)分析。因此，在分析時(shí)可以忽略。

可以看出：算法B的時(shí)間復(fù)雜性為O(m)。于是，分析的重點(diǎn)在樣本復(fù)雜性m。

對(duì)于任意給定的誤差參數(shù)0<ε<1，以及可靠性參數(shù)0<δ<1。

固定ε，對(duì)于任意給定的R2的分布D, 以及樣本S=(P1,……,Pm),Pj=(xj,yj)(1≤j≤m)。類似軸對(duì)齊矩形概念的分析方法，不妨假設(shè)Pr[A]>ε。

對(duì)每一個(gè)固定的約束條件aix+biy≤ci，存在一個(gè)δi>0，滿足條件(12)(13)。

在式(12)(13)中，令A(yù)i=A-Bi，則A1∪……∪Ak構(gòu)成A有內(nèi)側(cè)的一個(gè)ε/k-環(huán)帶。如果對(duì)于任意的i有AS∩Ai≠?，則由AS?A，我們有：

er(A,AS)≤Pr[A1∪……∪Ak]≤Pr[A1]+……+Pr[Ak]=ε。

因此，在er(A,AS)>ε的假定下，至少存在某個(gè)i，使得AS∩Ai=?。于是，對(duì)于來自獨(dú)立同分布的取樣樣本S=(P1,……,Pm)，我們有：

PrS～Dm[er(A,AS)>ε]

≤PrS～Dm[?(1≤i≤k):AS∩Ai=?]

(14)

因此，二維歐氏空間上由有界結(jié)性凸區(qū)域定義的目標(biāo)概念是有效PAC可學(xué)習(xí)的?！?/p>

5 結(jié)語

文中的方法適用于數(shù)據(jù)集中的數(shù)據(jù)按預(yù)定凸區(qū)域聚類及誤差分析，也可通過適當(dāng)變換在非歐空間中討論P(yáng)AC學(xué)習(xí)算法。