一類離散無(wú)向圖模型誘導(dǎo)的概念類的樣本壓縮方案

李本崇, 郭豐毅

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 陜西 西安 710126)

1 引言

泛化和壓縮是統(tǒng)計(jì)學(xué)習(xí)中的兩個(gè)重要方面. 泛化是指對(duì)現(xiàn)有知識(shí)的擴(kuò)展, 而壓縮則強(qiáng)調(diào)對(duì)知識(shí)的簡(jiǎn)化. 它們緊密相聯(lián): 學(xué)習(xí)算法執(zhí)行壓縮, 而壓縮能力保證了良好的泛化性能. 這種聯(lián)系的一種運(yùn)用, 正是在統(tǒng)計(jì)學(xué)習(xí)中被廣泛遵從的奧卡姆剃刀準(zhǔn)則: 如果輸入樣本可以被壓縮為一部分與其保持一致的子樣本, 良好的泛化性能就可以得到保證[1].

概念類的樣本壓縮方案由壓縮函數(shù)和重構(gòu)函數(shù)兩部分組成: 壓縮函數(shù)能夠?qū)⒂邢迾颖緣嚎s為帶標(biāo)簽或無(wú)標(biāo)簽的子樣本, 而重構(gòu)函數(shù)則能夠?qū)⑦@些子樣本恢復(fù)為與原始樣本一致的一個(gè)概念. 一個(gè)自然的問(wèn)題是: 是否每個(gè)概念類都有一個(gè)大小僅依賴于其VC(Vapnik-Chervonenkis)維數(shù)的壓縮方案?其中VC 維數(shù)是函數(shù)類復(fù)雜性的一個(gè)度量[2].文獻(xiàn)[3-4] 給出了一個(gè)猜想: 每個(gè)VC 維數(shù)為d的概念類都存在一個(gè)大小為O(d) 的樣本壓縮方案. 這個(gè)猜想引發(fā)了學(xué)者們的系列研究. 文獻(xiàn)[3] 為每個(gè)概念類C 構(gòu)建了大小為log ∣C∣的樣本壓縮方案. 文獻(xiàn)[5] 證明了關(guān)于樣本壓縮方案的緊致性定理, 并且還指出對(duì)于無(wú)限類的壓縮方案的存在性是從有限類的存在性中得出的, 因此只需要考慮有限的概念類. 文獻(xiàn)[6] 考慮了最大類的一個(gè)推廣: 極端類(基于三明治定理[7-8]), 并為極端類構(gòu)建了大小為d的帶標(biāo)簽壓縮方案. 文獻(xiàn)[9] 構(gòu)造了大小為exp(d) 的樣本壓縮方案. 對(duì)一些自然而重要的概念類, 學(xué)者們對(duì)其無(wú)標(biāo)簽樣本壓縮方案(壓縮函數(shù)將給定的樣本壓縮到樣本域的一個(gè)子集) 做了積極探索, 取得了顯著成果[10-14].

從代數(shù)幾何學(xué)的視角, 一個(gè)統(tǒng)計(jì)模型是一個(gè)實(shí)代數(shù)簇[15]. 考慮離散模型, 它是一些多項(xiàng)式的解集與概率單形的交集[16-17]. 文獻(xiàn)[18] 證明了一般離散無(wú)向圖模型(非完全圖) 誘導(dǎo)的概念類不屬于定向擬陣復(fù)形的范疇. 對(duì)于包含兩個(gè)頂點(diǎn)X1,X2且無(wú)邊連的無(wú)向圖,X1∈{0,1},X2∈{0,1,…,k2-1} (k2∈N,k2≥2). 針對(duì)該離散無(wú)向圖模型誘導(dǎo)的概念類, 文獻(xiàn)[18] 給出了一個(gè)帶標(biāo)簽壓縮方案, 但方案是非適當(dāng)?shù)? 本文考慮這類無(wú)向圖模型誘導(dǎo)的概念類, 基于文獻(xiàn)[19-20] 的工作, 應(yīng)用模型的二次二項(xiàng)式表示, 構(gòu)建了大小為其VC 維數(shù)的帶標(biāo)簽樣本壓縮方案, 證明了所提方案的適當(dāng)性.

文章結(jié)構(gòu)安排如下: 第二節(jié)介紹文中用到的主要定義和符號(hào); 第三節(jié)給出了一類離散無(wú)向圖模型誘導(dǎo)的概念類的帶標(biāo)簽樣本壓縮方案, 大小為其VC 維數(shù), 并證明了方案是適當(dāng)?shù)? 第四節(jié)總結(jié)了本文的工作.

2 預(yù)備知識(shí)

2.1 概念、概念類、VC 維數(shù)

一個(gè)概念c是指從域X 映射到{0,1} 的一個(gè)函數(shù). 本文假定∣X∣是有限的, 這里∣X∣指X 的基數(shù). 一個(gè)概念c也可以看作是X 的一個(gè)子集,x∈c當(dāng)且僅當(dāng)c(x)=1.一個(gè)概念類C 是定義在X 上的一個(gè)函數(shù)族, 是具有相同域的概念構(gòu)成的一個(gè)集合.

考慮X 的子集A, 類C 在A上的限制是一個(gè)概念類C∣A{c∩A∶c∈C}. 如果∣C∣A∣=2∣A∣,則稱A被概念類C 打散,其中∣A∣是A的基數(shù). 進(jìn)一步,概念類C 的VC維數(shù)定義為

2.2 離散無(wú)向圖模型及其代數(shù)幾何表示

考慮簡(jiǎn)單無(wú)向圖. 一個(gè)無(wú)向圖G= (V,E) 包含一個(gè)頂點(diǎn)集V和一個(gè)無(wú)序頂點(diǎn)對(duì)的集合E. 如果圖G中的任兩個(gè)頂點(diǎn)之間都存在一條邊, 則稱圖G是完全的.設(shè)圖G′= (V′,E′), 若V′?V且E′?E, 則稱G′為G的子圖. 若子圖G′的頂點(diǎn)集V′中任意兩個(gè)頂點(diǎn)對(duì)應(yīng)原圖G中的邊均在E′中, 則稱G′為圖G的導(dǎo)出子圖. 給定一個(gè)無(wú)向圖G, 一個(gè)團(tuán)指的是G的一個(gè)極大完全導(dǎo)出子圖, 用κG來(lái)表示G的所有團(tuán)的集合. 本文中,V={X1,X2,…,Xn}, 每個(gè)Xi表示一個(gè)離散隨機(jī)變量,Xi∈[ki]={0,1,…,ki-1},ki∈N 且ki≥2. 進(jìn)一步, 令X=(X1,X2,…,Xn) 是一個(gè)n-維向量, 則樣本空間X =[ki].

一個(gè)離散無(wú)向圖模型P是一族離散分布,P中X 上的一個(gè)分布P可表示為

其中x=(x1,x2,…,xn)∈X,ψK(x) 是定義在X 上的只通過(guò)K中變量取值依賴X 的非負(fù)實(shí)函數(shù). 本文僅考慮P中正概率分布, 記為P+.

接下來(lái)介紹離散無(wú)向圖模型的代數(shù)幾何表示. 考慮實(shí)多項(xiàng)式環(huán)R[X], 它的未定元是初等概率px1x2…xn. 考慮一個(gè)子集I?R[X], 若滿足: (1) 0 ∈I; (2) 如果f,g∈I,則f+g∈I;(3)如果f∈I且h∈R[X],hf∈I;則稱它是一個(gè)理想.每一個(gè)理想I∈R[X]對(duì)應(yīng)一個(gè)簇

其中k=ki,是由k維向量組成的集合, 其每一個(gè)向量的各分量均為正實(shí)數(shù).

給定一個(gè)無(wú)向圖G, 如果(Xi,Xj)?E, 則稱給定{X1,X2,…,Xn}{Xi,Xj} 時(shí)Xi與Xj獨(dú)立, 記為XiXj∣{X1,X2,…,Xn}{Xi,Xj}, 稱為一個(gè)對(duì)條件獨(dú)立情形. 每一個(gè)XiXj∣{X1,X2,…,Xn}{Xi,Xj} 對(duì)應(yīng)二次二項(xiàng)式的一個(gè)集合: ?xi,x′i∈[ki],?xj,x′j∈[kj], ?z∈[kl],

記Ipairwise(G)是R[X] 中由所有對(duì)條件獨(dú)立情形對(duì)應(yīng)的二次二項(xiàng)式生成的理想.Hammersley-Clifford 定理表明=P+(見(jiàn)文獻(xiàn)[19]).

例2.1圖1 中的G1是一個(gè)簡(jiǎn)單無(wú)向圖, 其中V={X1,X2},κG1={{X1},{X2}},E=?. 若X1,X2∈[2], 則X 中有四個(gè)元素:x(0,0),x(1,1),x(0,1),x(1,0).

由于X1X2, 該離散無(wú)向圖模型對(duì)應(yīng)的二次二項(xiàng)式的集合為

2.3 離散無(wú)向圖模型誘導(dǎo)的概念類

首先定義符號(hào)函數(shù)

其中x∈R. 給定一個(gè)離散無(wú)向圖模型, 其誘導(dǎo)的概念類C 為X 上的二值函數(shù)構(gòu)成的集合, 即

考慮無(wú)向圖G1, 不存在一對(duì)概率分布P,Q∈P+使得

取值為(1,1,0,0) 或(0,0,1,1). 由于

(0,0,0,0) 也不可能出現(xiàn).

例2.2上例中, 離散無(wú)向圖模型誘導(dǎo)的概念類C1如圖2 所示, VCdim(C1)=3(見(jiàn)文獻(xiàn)[20]).

圖2 一個(gè)概念類C1

2.4 帶標(biāo)簽樣本壓縮方案

一個(gè)帶標(biāo)簽的樣本是一個(gè)集合S= {(x(1),y(1)),…,(x(m),y(m))}, 其中x(i)∈X,y(i)∈{0,1}. 概念類C 的一個(gè)帶標(biāo)簽樣本壓縮方案由一個(gè)壓縮函數(shù)g和一個(gè)重構(gòu)函數(shù)h組成, 函數(shù)g將一個(gè)來(lái)自C 中某個(gè)概念的樣本映射到一個(gè)帶標(biāo)簽的子樣本, 即壓縮集. 函數(shù)h將子樣本映射到X 上的一個(gè)與原始樣本一致的概念. 如果對(duì)于任何樣本S,有h(g(S))∈C, 則稱此壓縮方案是適當(dāng)?shù)? 否則稱為不適當(dāng)?shù)?

3 主要結(jié)果

考慮圖1 中的無(wú)向圖G1, 若X1∈[2],X2∈[k2] (k2∈N,k2>2), 該離散無(wú)向圖模型對(duì)應(yīng)() 個(gè)二次二項(xiàng)式

其中j,k∈[k2],j2 時(shí)可能存在(0,0,0,0)的情況,即k2>2 時(shí)最多有14 種情況,記為C2,其中VCdim(C2)=k2+1(見(jiàn)文獻(xiàn)[20]).

考慮(1) 式, 已知px(0,j),px(1,k),px(0,k),px(1,j)中的任意三個(gè)數(shù)值時(shí), 即可得另一個(gè)概率值. 若已知{(x(0,j),0),(x(1,k),0),(x(1,j),1)},x(0,k)的標(biāo)簽必為0, 否則會(huì)出現(xiàn)(0,0,1,1) 的情況. 同理, 若已知

必分別重構(gòu)為 (0,0,1,0), (0,1,0,0), (1,0,0,0), (1,1,0,1), (1,1,1,0), (0,1,1,1),(1,0,1,1). 這8 種情況, 每種對(duì)應(yīng)一個(gè)大小為3 的帶標(biāo)簽壓縮集, 記為Part 1, 其中Part 1 對(duì)應(yīng)的帶標(biāo)簽壓縮集構(gòu)成的集合記為L(zhǎng)1. 剩余的6 種情況, 每種對(duì)應(yīng)四個(gè)大小為3 的壓縮集, 此部分記為Part 2, 其中Part 2 對(duì)應(yīng)的壓縮集構(gòu)成的集合記為L(zhǎng)2. C2的一個(gè)壓縮方案如表1 所示, 這里x(1),x(2),x(3),x(4)代表x(0,j),x(1,k),x(0,k),x(1,j).

表1 C2 的一個(gè)帶標(biāo)簽壓縮方案

用B1,B2,…,Bn分別記2k2個(gè)域點(diǎn)需要滿足的每個(gè)二次二項(xiàng)式對(duì)應(yīng)的域集, 其中n=(), 考慮樣本S(∣S∣≥k2+1) 來(lái)自于C2中的某個(gè)概念c. 基于表1, 下面給出C2的帶標(biāo)簽壓縮方案.

帶標(biāo)簽壓縮方案:

(1)壓縮算法: 輸入樣本S. 在樣本中選定一對(duì)樣本點(diǎn){(x(0,i),y(0,i)),(x(1,i),y(1,i))}(選擇時(shí)優(yōu)先考慮滿足(y(0,i),y(1,i))=(0,1) 或(1,0) 的點(diǎn)). 令

若B′≠?, 則依據(jù)壓縮方案Part 1, 從B′的每個(gè)元素中移除一個(gè)相應(yīng)樣本點(diǎn), 剩余樣本點(diǎn)的集合記為D. 再令

如果D′≠?, 保留樣本點(diǎn){(x(0,i),y(0,i)),(x(1,i),y(1,i))}, 利用壓縮方案Part 2 從D′的每個(gè)元素中移除一個(gè)樣本點(diǎn), 將保留的樣本點(diǎn)記為s并輸出.

(2) 重構(gòu)算法: 輸入一個(gè)大小至多為k2+1 的子樣本s. 在子樣本中選定一對(duì)樣本點(diǎn){(x(0,i),y(0,i)),(x(1,i),y(1,i))} (優(yōu)先選擇(y(0,i),y(1,i))=(0,1) 或(1,0) 的點(diǎn)). 令

若B′′≠?, 則可通過(guò)L2重構(gòu)出每個(gè)Bt中的未知樣本點(diǎn). 其余的未知樣本點(diǎn)可利用L1重構(gòu)(使用{(x(0,i),y(0,i)),(x(1,i),y(1,i))} 對(duì)應(yīng)的二次二項(xiàng)式). 若y(0,j),y(1,j)標(biāo)簽未知, 任意補(bǔ)充y(0,j)或y(1,j)的值, 通過(guò)樣本點(diǎn){(x(0,i),y(0,i)),(x(1,i),y(1,i))} 和補(bǔ)充點(diǎn)對(duì)應(yīng)的二次二項(xiàng)式預(yù)測(cè)相應(yīng)未知樣本點(diǎn). 輸出重構(gòu)出的概念.

下面證明本文構(gòu)建方案的正確性. 首先說(shuō)明所構(gòu)建的算法產(chǎn)生了一個(gè)大小至多為k2+1 的壓縮集, 且由該壓縮集重構(gòu)出的概念與樣本S是一致的.

定理3.1輸入一個(gè)樣本S, 該方案輸出一個(gè)大小至多為k2+1 的壓縮集s, 重構(gòu)出的概念與原始樣本S是一致的.

證明由于∣S∣≥k2+1, 至少存在一對(duì)樣本點(diǎn){(x(0,i),y(0,i)),(x(1,i),y(1,i))} 在樣本S中, 其中i∈{0,…,k2-1}. (y(0,i),y(1,i)) 的取值有以下三種情形.

情形1: ?i∈{0,…,k2-1}, (y(0,i),y(1,i))=(1,0).

考慮樣本點(diǎn){(x(0,j),y(0,j)),(x(1,j),y(1,j))},其中j∈{0,…,k2-1},j≠i,(y(0,j),y(1,j))有三種可能的情況: (y(0,j),y(1,j)) = (1,1) 時(shí), 由壓縮算法可得樣本點(diǎn)(x(0,j),1)被移除; (y(0,j),y(1,j)) = (0,0) 時(shí), (x(1,j),0) 被移除; (y(0,j),y(1,j)) = (1,0) 時(shí), 樣本點(diǎn){(x(0,j),1),(x(1,j),0)} 中任意一個(gè)可被移除. 即得∣s∣≤k2+1.

情形2: ?i∈{0,…,k2-1}, (y(0,i),y(1,i))=(0,1). 與情形1 類似, 通過(guò)壓縮算法可得∣s∣≤k2+1.

情形3: ?i∈{0,…,k2-1}, 有y(0,i)=y(1,i)= 0 或y(0,i)=y(1,i)= 1. 然后可由方案Part 2 輸出壓縮集s, ∣s∣≤k2+1.

綜上所述, 壓縮算法可產(chǎn)生一個(gè)大小至多為k2+1 的壓縮集s. 下面考慮重構(gòu). 若∣s∣

情形1: (y(0,i),y(1,i))=(1,0). 當(dāng)y(0,j)=1 時(shí),由壓縮方案可得y(1,j)=0;當(dāng)y(0,j)=0時(shí), 由壓縮方案可得y(1,j)=0; 當(dāng)y(1,j)=1 時(shí),y(0,j)=1; 當(dāng)y(0,j)=0 時(shí),y(1,j)=1. 同理,(y(0,i),y(1,i))=(0,1) 時(shí)也可預(yù)測(cè)出相應(yīng)的樣本點(diǎn).

情形2: (y(0,i),y(1,i))=(0,0). 當(dāng)y(0,j)=1 時(shí), 由壓縮方案可得y(1,j)=1; 當(dāng)y(0,j)=0時(shí), 由壓縮方案可得y(1,j)=0; 當(dāng)y(1,j)=1 時(shí),y(0,j)=1; 當(dāng)y(0,j)=0 時(shí),y(1,j)=0. 同理,(y(0,i),y(1,i))=(1,1) 時(shí)也可預(yù)測(cè)出相應(yīng)的樣本點(diǎn).

若子樣本s提供的信息不足以重構(gòu)為某個(gè)概念, 則需要補(bǔ)充一些樣本點(diǎn), 此時(shí)重構(gòu)出的概念屬于概念類C2嗎？

定理3.2對(duì)于圖1 的無(wú)向圖G1,X1∈[2],X2∈[k2], 壓縮方案重構(gòu)出來(lái)的概念都屬于概念類C2.

證明由定理3.1 中重構(gòu)的證明可知, 通過(guò)方案重構(gòu)出的任一概念對(duì)應(yīng)的二次二項(xiàng)式中(x(0,j),x(1,k),x(0,k),x(1,j)) 對(duì)應(yīng)標(biāo)簽不存在(0,0,1,1) 或(1,1,0,0) 的情況. 要證方案重構(gòu)出的概念屬于C2, 即證存在一對(duì)分布P,Q對(duì)應(yīng)此概念. 概念類C2有2k2個(gè)域點(diǎn), 記為x(0,0),x(1,0),…,x(1,k2-1). 下面分情況討論域點(diǎn)對(duì)應(yīng)的標(biāo)簽.

情形1: ?i∈{0,…,k2-1}, 有(y(0,i),y(1,i))=(1,1). 此時(shí)P和Q滿足條件P=Q即可得到相應(yīng)概念.

情形2: ?i,j∈{0,…,k2-1}, 有(y(0,i),y(1,i))=(1,1), (y(0,j),y(1,j))=(0,0).

當(dāng)k2=2 時(shí), 至少存在

使得

例如

當(dāng)k2> 2 時(shí), 記{0,…,k2-1} 中滿足(y(0,i),y(1,i)) = (1,1) 的個(gè)數(shù)為m, 滿足(y(0,j),y(1,j))=(0,0) 的個(gè)數(shù)為n,m+n=k2. 將(p(0,0),p(1,0),q(0,0),q(1,0)) 同時(shí)除以m, 并將這m對(duì)值對(duì)應(yīng)至域{(x(0,i),x(1,i))} 上, 此時(shí)有

同理,將(p(0,1),p(1,1),q(0,1),q(1,1))同時(shí)除以n,并將這n對(duì)值對(duì)應(yīng)至域{(x(0,j),x(1,j))}上. 即得到相應(yīng)的概念.

情形3: ?i,j∈{0,…,k2-1}, 有

由情形2 保證存在相應(yīng)的概念.

情形4: ?i,j,l∈{0,…,k2-1}, 有

當(dāng)k2=3 時(shí), 至少存在一對(duì)

使得

例如

當(dāng)k2>3 時(shí),記0,…,k2-1 中滿足(y(0,i),y(1,i))=(1,1)的個(gè)數(shù)為m,(y(0,j),y(1,j))=(0,0) 的個(gè)數(shù)為n, (y(0,l),y(1,l)) = (1,0) 的個(gè)數(shù)為v,m+n+v=k2. 類似情形2 中的做法, (p(0,0),p(1,0),q(0,0),q(1,0)) 同時(shí)除以m; (p(0,1),p(1,1),q(0,1),q(1,1)) 同時(shí)除以n;(p(0,2),p(1,2),q(0,2),q(1,2)) 同時(shí)除以v, 將這些比值對(duì)應(yīng)到相應(yīng)的域上, 即可得到相應(yīng)的概念.

情形5: ?i,j,l∈{0,…,k2-1}, 有

由情形4 保證存在相應(yīng)的概念.

綜上所述, 重構(gòu)出的概念都在概念類C2中, 所提的壓縮方案是適當(dāng)?shù)?

下面看一個(gè)例子.

例3.1X1∈[2],X2∈[3], 令C3表示該離散無(wú)向圖模型誘導(dǎo)的概念類, 則它的域?yàn)閧x(0,0),x(1,0),x(0,1),x(1,1),x(0,2),x(1,2)}. 對(duì)應(yīng)的二次二項(xiàng)式為:

(1)px(0,0)?px(1,1)-px(0,1)?px(1,0),

(2)px(0,0)?px(1,2)-px(0,2)?px(1,0),

(3)px(0,1)?px(1,2)-px(0,2)?px(1,1).

C3的VC 維數(shù)是4[20]. 若樣本

它是C3的一個(gè)概念, 例如

利用壓縮算法移除樣本點(diǎn)(x(1,1),0), (x(1,2),0) 得到壓縮集

重構(gòu)時(shí), 通過(guò)二次二項(xiàng)式(1) 預(yù)測(cè)x(1,1)的標(biāo)簽為1; 通過(guò)二次二項(xiàng)式(2) 預(yù)測(cè)x(1,2)的標(biāo)簽為0. 即精確恢復(fù)S1.

若樣本S2={(x(0,0),1),(x(1,0),0),(x(1,1),0),(x(1,2),0)}, 由算法知S2本身就是一個(gè)壓縮集. 重構(gòu)時(shí), 通過(guò)二次二項(xiàng)式(1) 預(yù)測(cè)x(0,1)的標(biāo)簽為1; 通過(guò)二次二項(xiàng)式(2) 預(yù)測(cè)x(0,2)的標(biāo)簽為1. 輸出的概念為

此概念屬于C3, 例如

若樣本S3= {(x(0,0),1),(x(1,0),0)}, 此時(shí)可補(bǔ)充x(0,1)的標(biāo)簽為0;x(0,2)的標(biāo)簽為1. 重構(gòu)時(shí), 通過(guò)二次二項(xiàng)式(1) 預(yù)測(cè)x(1,1)的標(biāo)簽為0; 通過(guò)二次二項(xiàng)式(2) 預(yù)測(cè)x(1,2)的標(biāo)簽為0. 輸出的概念為

此概念屬于C3, 例如

由定理3.1, 可得如下結(jié)論成立.

定理3.3對(duì)于圖3 中的無(wú)向圖,令X1∈[2],Xi∈[ki],C4表示該離散無(wú)向圖模型誘導(dǎo)的概念類, 其中ki∈N,ki≥2,i=2,3. 則C4存在一個(gè)大小為k2(k3+1)的帶標(biāo)簽樣本壓縮方案. 進(jìn)一步, 對(duì)于任意包含兩個(gè)團(tuán)K1={X1,X2,…,Xn1},K2={X2,X3,…,Xn}且X1∈[2] 的無(wú)向圖, 對(duì)應(yīng)的離散無(wú)向圖模型誘導(dǎo)的概念類存在一個(gè)大小為VC 維數(shù)的樣本壓縮方案.

圖3 無(wú)向圖G2

定理3.3 的結(jié)論與文獻(xiàn)[18] 中定理3.5 和推論3.6 相同, 證明也是一致的. 在此不再贅述.

4 總結(jié)

本文考慮一類離散無(wú)向圖模型誘導(dǎo)的概念類, 構(gòu)建了大小為其VC 維數(shù)的帶標(biāo)簽樣本壓縮方案, 證明了方案的適當(dāng)性. 對(duì)于一個(gè)一般的離散無(wú)向圖模型, 其誘導(dǎo)的概念類是否存在一個(gè)大小為O(d) 的樣本壓縮方案, 是一個(gè)待解決的問(wèn)題.