王 怡，常 青，王耀力，郝慧琴

（1.太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600；2.中國電信股份有限公司山西分公司，山西太原 030000）

當(dāng)前，數(shù)據(jù)摘要逐漸成為機(jī)器學(xué)習(xí)的研究熱點(diǎn)。然而數(shù)據(jù)摘要算法被證明在性別、種族和民族等敏感屬性方面存在偏見[1-2]，尤其在教育、招聘、銀行和司法系統(tǒng)等領(lǐng)域中[3-5]，所引起的公平性問題[6]得到了廣泛的關(guān)注。

對(duì)于上述問題，該文引入流式子模最大化算法[7]，在此基礎(chǔ)上改進(jìn)算法約束，考慮數(shù)據(jù)項(xiàng)的組成性，在每組中選取指定范圍內(nèi)的元素構(gòu)成具有代表性的子集，從而使提取出的子集更具有公平性和多樣性。

1 基于公平約束的流式子模算法

1.1 擬陣約束下的流式子模最大化模型

在很多情況下，考慮算法的穩(wěn)定性以及成本等問題，通常采用擬陣約束下的流式子模優(yōu)化模型[8-10]。

定義1：假設(shè)V表示原有數(shù)據(jù)集中n個(gè)元素的集合，V1…Vm是V的一個(gè)分劃，即是m個(gè)非負(fù)整數(shù)，k為基數(shù)約束，S為最優(yōu)子集。記:

則(V,L)是定義在V上的擬陣，稱為分劃擬陣。在分劃擬陣約束下的流式子模最大化模型可表示為：

1.2 改進(jìn)后的約束——公平約束

鑒于上述擬陣約束得到的集合S，當(dāng)原始數(shù)據(jù)集合V中含有某些如年齡、性別、種族等特定屬性時(shí)，會(huì)造成對(duì)某些特定屬性數(shù)據(jù)的代表性不足或者過強(qiáng)，無法保證集合S的公平性與多樣性。為了使選取出的集合S能夠公平代表原始數(shù)據(jù)集合V，對(duì)上述擬陣約束進(jìn)行改進(jìn)，提出了一種公平約束。

該文借鑒文獻(xiàn)[11-14]有關(guān)公平的思想，要求獲得的解集S與數(shù)據(jù)某些特定屬性(如種族、性別)相平衡，提出流式子模最大化下的公平約束，定義如下：

假定給定的數(shù)據(jù)集V是有顏色的，即給每個(gè)元素賦予一種顏色。對(duì)于顏色c=1,2,…,C，用Vc表示顏色c的元素集合，則b=1,2,…,C。對(duì)于每種顏色c，提取后的解集S必須包含每個(gè)顏色c的元素個(gè)數(shù)在指定的下界lc和上界uc之間。設(shè)k?Z是一個(gè)全局基數(shù)約束，該公平約束表示為：

則基于該公平約束下的流式子模最大化模型為:

由公平約束的定義可知，S滿足以下條件：

該文將滿足上述條件的S表示為“可擴(kuò)展”的。

2 公平約束下的流式子模算法

2.1 公平約束下的流式子模最大化算法

文獻(xiàn)[8]提出的擬陣約束子模優(yōu)化算法A(MSM算法)是目前性能最好的擬陣子模優(yōu)化算法，但該算法未考慮公平問題。因此該文基于MSM 算法進(jìn)行改進(jìn)，提出公平約束下的流式子模算法(FSM 算法)，步驟如下：

1）FSM 算法通過運(yùn)行A來構(gòu)造一個(gè)近似最大化f的解集SA。SA必定滿足上界，同時(shí)，對(duì)于每種顏色c，并行收集一個(gè)大小為|Bc|=lc的備份集Bc。

2）若SA不滿足其下界，則將SA擴(kuò)展為一個(gè)可行的解決方案S，即對(duì)于每一種顏色c，如果|SA∩Vc|＜lc，則從Bc中添加lc-|SA∩Vc|個(gè)元素來滿足下界。

FSM 算法偽代碼如下：

2.2 算法可行性分析

當(dāng)去掉公平約束F中的下界約束|S∩Vc|≥lc時(shí)，剩下的約束將會(huì)與式（1）相同，得到一個(gè)擬陣。然而在該擬陣約束下的流式子模最大化算法A得到的解可能會(huì)違反下界約束。為了兼顧下界約束，該文算法通過從A并行流中收集備份元素來擴(kuò)大解決方案，使之成為一個(gè)可行的解決方案。

然而，僅僅擴(kuò)大解決方案來滿足下界約束，可能會(huì)違反全局基數(shù)約束|S|≤k。正確的約束是解決方案具有式（5）的條件：“可擴(kuò)展”到一個(gè)可行集。為了說明該文所提出的算法能有效地找到可行解，需要證明符合公平約束的V的可擴(kuò)展子集的集合F仍然能構(gòu)成一個(gè)擬陣。下面給出公平約束符合擬陣約束性質(zhì)的證明。

定義2：若～2V是V的所有可擴(kuò)展子集的集族，那么是一個(gè)擬陣。

證明如下：若是擬陣，必然滿足以下公理：設(shè)B包含擬陣中的所有極大集。則B滿足以下兩個(gè)公理：

①B。

②如果B1,B2∈B和x∈B1B2，則存在y∈B2B1，使得B1-x+y∈B（向下封閉性）。

這些公理表明向下封閉性的B（集合的所有子集）是一個(gè)擬陣。但是，B的向下封閉性等于，因?yàn)閂的任何子集只要能推廣到一個(gè)可行解，也能推廣到一個(gè)極大可行解。因此，只需要證明公理①和公理②。

公理①的證明只需假設(shè)≠?，即可得到B≠?。

對(duì)于公理②：已知B1,B2∈B,x∈B1B2,設(shè)c是x的顏色，一種簡(jiǎn)單的情況是當(dāng)B2B1包含某個(gè)元素y∈Vc，那么B1-x+y中每種顏色的元素?cái)?shù)與B1相同，因此B1-x+y也在B中。

現(xiàn)在假設(shè)另一種情況，即Vc∩B2?B1-x。那么有：

3 仿真實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)概述

該文討論的是公平約束下的數(shù)據(jù)摘要問題，為此通過以下指標(biāo)來進(jìn)行對(duì)比實(shí)驗(yàn)：

1）使用函數(shù)效用值和時(shí)間復(fù)雜度（運(yùn)行時(shí)間）來衡量算法的性能。

2）將違反公平的次數(shù)error(S)=定義為衡量公平的標(biāo)準(zhǔn)，總和項(xiàng)的每一項(xiàng)是依靠違反上界和下界元素的個(gè)數(shù)來量化的。

3）查看不同算法每個(gè)分組的選取元素的個(gè)數(shù)來衡量提取數(shù)據(jù)的多樣性。

實(shí)驗(yàn)所采用的效用函數(shù)為f(S)=M-d(v,e) 。其中，為數(shù)據(jù)集中的所有數(shù)據(jù)之和，其個(gè)數(shù)為n。

此外，平均每個(gè)分組提取到的元素為k/t，其中t表示分組的個(gè)數(shù)，根據(jù)該實(shí)驗(yàn)數(shù)據(jù)集的分組個(gè)數(shù)，設(shè)置上界uc=0.2k與下界lc=0.1k，以確保每個(gè)分組包含子集的10%～20%。

在很多應(yīng)用中，比如電影推薦[15-16]、圖形檢測(cè)[17]等，感興趣的是從龐大的數(shù)據(jù)集中提取出的部分集合與原始數(shù)據(jù)集相似，涵蓋想要的所有的屬性。

為了評(píng)估該文算法FSM 的可使用性，選用了兩種不同的數(shù)據(jù)集，第一種數(shù)據(jù)集為公共數(shù)據(jù)集Cencus1990，其中含有一些可能導(dǎo)致算法偏見的屬性（如年齡、身高、體重、性別、種族等），該實(shí)驗(yàn)選用該數(shù)據(jù)中的50 060 條記錄，希望從該數(shù)據(jù)集中提取到能夠涵蓋原始數(shù)據(jù)集的所有年齡段的子集。該實(shí)驗(yàn)根據(jù)年齡將數(shù)據(jù)分為六組：[0,29]、[30,39]、[40,49]、[50,59]、[60,69]、[70+]，各個(gè)年齡段的記錄數(shù)分別如下：1 379、18 093、15 354、8 210、6 521、503。

第二種數(shù)據(jù)集是從呂梁山山脈觀測(cè)得到的森林覆蓋類型數(shù)據(jù)，該數(shù)據(jù)集共包含8 種可燃物林木類型：華北落葉松（1）、云杉（2）、白樺（3）、山楊（4）、遼東櫟（5）、青木千（6）、側(cè)柏（7）、醋柳（8），包含每種可燃物類型對(duì)應(yīng)的海拔高度、土壤類型、坡度、坡向等12 種屬性。每種可燃物類型分別有87 145、60 450、58 762、45 040、42 098、20 625、534、456 條數(shù)據(jù)。由統(tǒng)計(jì)數(shù)據(jù)可得側(cè)柏（7）與醋柳（8）兩種可燃物類型的數(shù)據(jù)量較少，傳統(tǒng)算法在訓(xùn)練時(shí)容易忽略小樣本數(shù)據(jù)。

將該文的FSM 算法與隨機(jī)提取算法和MSM 算法進(jìn)行比較。

3.2 不同算法下?lián)p失成本及運(yùn)行時(shí)間對(duì)比

該文針對(duì)流式子模最大化算法進(jìn)行改進(jìn)，為驗(yàn)證該算法的有效性，對(duì)比上述幾種算法的函數(shù)效用值以及運(yùn)行時(shí)間。

如圖1 所示，該文FSM 算法的函數(shù)效用值略低于MSM 算法，但優(yōu)于隨機(jī)提取算法。這是由于復(fù)雜約束的引入會(huì)不可避免導(dǎo)致算法效用降低。從實(shí)驗(yàn)來看，F(xiàn)SM 算法與MSM 算法相比效用值近似，甚至在提取的個(gè)數(shù)越大時(shí)，F(xiàn)SM 效用值與MSM 算法一致。

圖1 不同算法下的函數(shù)效用值

流式子模最大化算法的運(yùn)行時(shí)間是通過子模函數(shù)調(diào)用的次數(shù)來衡量的[7]，與隨機(jī)提取算法運(yùn)行時(shí)間定義不一致，因此隨機(jī)提取算法未涉及運(yùn)行時(shí)間的對(duì)比。

如圖2 所示，該文提出的FSM 算法的運(yùn)行時(shí)間明顯低于其他算法。且隨著k的增大，F(xiàn)SM 算法對(duì)比MSM 算法運(yùn)行效率有顯著提升。在“森林”數(shù)據(jù)集下，當(dāng)k為70 時(shí)，F(xiàn)SM 的算法比MSM 算法運(yùn)行時(shí)間降低了8.6%。說明FSM 算法能大大減少時(shí)間復(fù)雜度，尤其在應(yīng)用大型數(shù)據(jù)摘要問題中，F(xiàn)SM 算法更具有優(yōu)越性。

圖2 不同算法下的運(yùn)行時(shí)間

3.3 不同算法下違反公平的次數(shù)對(duì)比

該文通過設(shè)置上界uc和下界lc來保證算法提取出的子集包含想要的數(shù)據(jù)屬性值的所有范圍，以此顯示該文算法的公平性。因此將違反上界和下界元素的個(gè)數(shù)定義為違反公平的次數(shù)error 。通過對(duì)比不同算法違反公平的次數(shù)error 來驗(yàn)證該文算法的公平性。

由圖3 可知，隨著提取元素個(gè)數(shù)k的不斷增大，MSM 算法與隨機(jī)提取算法會(huì)出現(xiàn)不同程度的error。如當(dāng)k設(shè)定為70，Cencus1990 數(shù)據(jù)集下隨機(jī)提取算法的error 為28，MSM 算法的error 為21。而該文FSM 算法違反公平的次數(shù)始終為0，可有效保證提取的子集不會(huì)違反上界和下界，證明了該文算法的公平性。

圖3 不同算法下的違反公平的次數(shù)情況

3.4 不同算法下的各個(gè)分組元素提取情況

該文所提算法的目的在于能夠提取各個(gè)分組的元素，以使提取出的代表性子集具有多樣性。通過分析查看不同算法下各個(gè)分組元素提取情況來證明算法的有效性。

分別選取k=30、k=70 不同情況來查看不同算法下的各個(gè)分組元素提取情況，如表1-4 所示。

表1 Cencus1990 k=30 時(shí)不同算法下不同年齡段元素提取情況

表2 Cencus1990 k=70 時(shí)不同算法下不同年齡段元素提取情況

表3 “森林”k=30 時(shí)不同算法下不同林型元素提取情況

該文所提FSM 算法的核心在于對(duì)每個(gè)屬性分組數(shù)據(jù)的提取添加了上界uc與下界lc約束。如表1-表4 所示，當(dāng)提取數(shù)據(jù)k為30 時(shí)，上界值為0.2k=6，下界值為0.1k=3。因此屬性每個(gè)分組被提取出的數(shù)據(jù)個(gè)數(shù)應(yīng)當(dāng)在3-6 之間。對(duì)比在Cencus1990 公共數(shù)據(jù)集和“森林”數(shù)據(jù)集下，隨機(jī)提取算法與MSM 算法無法保證提取到所有分組類型的數(shù)據(jù)。在“森林”數(shù)據(jù)集中，當(dāng)提取元素個(gè)數(shù)k=70 時(shí)，隨機(jī)提取算法未提取到林型（8）的數(shù)據(jù)，MSM 算法未能提取到林型（7）和林型（8）的數(shù)據(jù)?？梢钥闯觯徽搆取何值，F(xiàn)SM 算法提取的子集更具有代表性與多樣性，證明了該文算法有良好的魯棒性。

表4 “森林”k=70 時(shí)不同算法下不同林型元素提取情況

4 結(jié)論

該文討論了數(shù)據(jù)摘要的代表性問題，提出了一種公平約束下的流式子模最大化算法，使選出的代表性子集能夠涵蓋提取屬性的所有范圍。實(shí)驗(yàn)表明，在該文模型下采用流式子模優(yōu)化算法，相比其他流式算法，時(shí)間復(fù)雜度減少8.6%以上，且提取出的摘要的多樣性與穩(wěn)定性更強(qiáng)，可以適用于更復(fù)雜的場(chǎng)景中。