一類離散無向圖模型誘導的概念類的樣本壓縮方案

李本崇, 郭豐毅

(西安電子科技大學數學與統計學院, 陜西 西安 710126)

1 引言

泛化和壓縮是統計學習中的兩個重要方面. 泛化是指對現有知識的擴展, 而壓縮則強調對知識的簡化. 它們緊密相聯: 學習算法執行壓縮, 而壓縮能力保證了良好的泛化性能. 這種聯系的一種運用, 正是在統計學習中被廣泛遵從的奧卡姆剃刀準則: 如果輸入樣本可以被壓縮為一部分與其保持一致的子樣本, 良好的泛化性能就可以得到保證[1].

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

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

文章結構安排如下: 第二節介紹文中用到的主要定義和符號; 第三節給出了一類離散無向圖模型誘導的概念類的帶標簽樣本壓縮方案, 大小為其VC 維數, 并證明了方案是適當的; 第四節總結了本文的工作.

2 預備知識

2.1 概念、概念類、VC 維數

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

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

2.2 離散無向圖模型及其代數幾何表示

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

一個離散無向圖模型P是一族離散分布,P中X 上的一個分布P可表示為

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

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

其中k=ki,是由k維向量組成的集合, 其每一個向量的各分量均為正實數.

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

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

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

由于X1X2, 該離散無向圖模型對應的二次二項式的集合為

2.3 離散無向圖模型誘導的概念類

首先定義符號函數

其中x∈R. 給定一個離散無向圖模型, 其誘導的概念類C 為X 上的二值函數構成的集合, 即

考慮無向圖G1, 不存在一對概率分布P,Q∈P+使得

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

(0,0,0,0) 也不可能出現.

例2.2上例中, 離散無向圖模型誘導的概念類C1如圖2 所示, VCdim(C1)=3(見文獻[20]).

圖2 一個概念類C1

2.4 帶標簽樣本壓縮方案

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

3 主要結果

考慮圖1 中的無向圖G1, 若X1∈[2],X2∈[k2] (k2∈N,k2>2), 該離散無向圖模型對應() 個二次二項式

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

考慮(1) 式, 已知px(0,j),px(1,k),px(0,k),px(1,j)中的任意三個數值時, 即可得另一個概率值. 若已知{(x(0,j),0),(x(1,k),0),(x(1,j),1)},x(0,k)的標簽必為0, 否則會出現(0,0,1,1) 的情況. 同理, 若已知

必分別重構為 (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 種情況, 每種對應一個大小為3 的帶標簽壓縮集, 記為Part 1, 其中Part 1 對應的帶標簽壓縮集構成的集合記為L1. 剩余的6 種情況, 每種對應四個大小為3 的壓縮集, 此部分記為Part 2, 其中Part 2 對應的壓縮集構成的集合記為L2. C2的一個壓縮方案如表1 所示, 這里x(1),x(2),x(3),x(4)代表x(0,j),x(1,k),x(0,k),x(1,j).

表1 C2 的一個帶標簽壓縮方案

用B1,B2,…,Bn分別記2k2個域點需要滿足的每個二次二項式對應的域集, 其中n=(), 考慮樣本S(∣S∣≥k2+1) 來自于C2中的某個概念c. 基于表1, 下面給出C2的帶標簽壓縮方案.

帶標簽壓縮方案:

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

若B′≠?, 則依據壓縮方案Part 1, 從B′的每個元素中移除一個相應樣本點, 剩余樣本點的集合記為D. 再令

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

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

若B′′≠?, 則可通過L2重構出每個Bt中的未知樣本點. 其余的未知樣本點可利用L1重構(使用{(x(0,i),y(0,i)),(x(1,i),y(1,i))} 對應的二次二項式). 若y(0,j),y(1,j)標簽未知, 任意補充y(0,j)或y(1,j)的值, 通過樣本點{(x(0,i),y(0,i)),(x(1,i),y(1,i))} 和補充點對應的二次二項式預測相應未知樣本點. 輸出重構出的概念.

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

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

證明由于∣S∣≥k2+1, 至少存在一對樣本點{(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).

考慮樣本點{(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) 時, 由壓縮算法可得樣本點(x(0,j),1)被移除; (y(0,j),y(1,j)) = (0,0) 時, (x(1,j),0) 被移除; (y(0,j),y(1,j)) = (1,0) 時, 樣本點{(x(0,j),1),(x(1,j),0)} 中任意一個可被移除. 即得∣s∣≤k2+1.

情形2: ?i∈{0,…,k2-1}, (y(0,i),y(1,i))=(0,1). 與情形1 類似, 通過壓縮算法可得∣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.

綜上所述, 壓縮算法可產生一個大小至多為k2+1 的壓縮集s. 下面考慮重構. 若∣s∣

情形1: (y(0,i),y(1,i))=(1,0). 當y(0,j)=1 時,由壓縮方案可得y(1,j)=0;當y(0,j)=0時, 由壓縮方案可得y(1,j)=0; 當y(1,j)=1 時,y(0,j)=1; 當y(0,j)=0 時,y(1,j)=1. 同理,(y(0,i),y(1,i))=(0,1) 時也可預測出相應的樣本點.

情形2: (y(0,i),y(1,i))=(0,0). 當y(0,j)=1 時, 由壓縮方案可得y(1,j)=1; 當y(0,j)=0時, 由壓縮方案可得y(1,j)=0; 當y(1,j)=1 時,y(0,j)=1; 當y(0,j)=0 時,y(1,j)=0. 同理,(y(0,i),y(1,i))=(1,1) 時也可預測出相應的樣本點.

若子樣本s提供的信息不足以重構為某個概念, 則需要補充一些樣本點, 此時重構出的概念屬于概念類C2嗎？

定理3.2對于圖1 的無向圖G1,X1∈[2],X2∈[k2], 壓縮方案重構出來的概念都屬于概念類C2.

證明由定理3.1 中重構的證明可知, 通過方案重構出的任一概念對應的二次二項式中(x(0,j),x(1,k),x(0,k),x(1,j)) 對應標簽不存在(0,0,1,1) 或(1,1,0,0) 的情況. 要證方案重構出的概念屬于C2, 即證存在一對分布P,Q對應此概念. 概念類C2有2k2個域點, 記為x(0,0),x(1,0),…,x(1,k2-1). 下面分情況討論域點對應的標簽.

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

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

當k2=2 時, 至少存在

使得

例如

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

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

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

由情形2 保證存在相應的概念.

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

當k2=3 時, 至少存在一對

使得

例如

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

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

由情形4 保證存在相應的概念.

綜上所述, 重構出的概念都在概念類C2中, 所提的壓縮方案是適當的.

下面看一個例子.

例3.1X1∈[2],X2∈[3], 令C3表示該離散無向圖模型誘導的概念類, 則它的域為{x(0,0),x(1,0),x(0,1),x(1,1),x(0,2),x(1,2)}. 對應的二次二項式為:

(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 維數是4[20]. 若樣本

它是C3的一個概念, 例如

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

重構時, 通過二次二項式(1) 預測x(1,1)的標簽為1; 通過二次二項式(2) 預測x(1,2)的標簽為0. 即精確恢復S1.

若樣本S2={(x(0,0),1),(x(1,0),0),(x(1,1),0),(x(1,2),0)}, 由算法知S2本身就是一個壓縮集. 重構時, 通過二次二項式(1) 預測x(0,1)的標簽為1; 通過二次二項式(2) 預測x(0,2)的標簽為1. 輸出的概念為

此概念屬于C3, 例如

若樣本S3= {(x(0,0),1),(x(1,0),0)}, 此時可補充x(0,1)的標簽為0;x(0,2)的標簽為1. 重構時, 通過二次二項式(1) 預測x(1,1)的標簽為0; 通過二次二項式(2) 預測x(1,2)的標簽為0. 輸出的概念為

此概念屬于C3, 例如

由定理3.1, 可得如下結論成立.

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

圖3 無向圖G2

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

4 總結

本文考慮一類離散無向圖模型誘導的概念類, 構建了大小為其VC 維數的帶標簽樣本壓縮方案, 證明了方案的適當性. 對于一個一般的離散無向圖模型, 其誘導的概念類是否存在一個大小為O(d) 的樣本壓縮方案, 是一個待解決的問題.