耿紅梅

（揚(yáng)州工業(yè)職業(yè)技術(shù)學(xué)院）

0 引言

近幾十年來，數(shù)據(jù)以流模型的方式傳輸?shù)那闆r受到了大量的關(guān)注.在提取海量數(shù)據(jù)信息的過程中，出現(xiàn)了受基數(shù)約束的非次模集函數(shù)最大化問題［1］.然而，事實上，對于非次模函數(shù)的最大值，要想求解其精確值是非常困難的，很難在多項式時間內(nèi)得到它的精確解.但是這些非次模優(yōu)化問題的廣泛應(yīng)用又使其求解成為必須［2］.因此，往往通過犧牲精度來換取時間，即在多項式時間內(nèi)得到問題的一個近似解，這便是近似算法［3］.在流模型下，如果收益函數(shù)是次模函數(shù)，則稱該模型為流次模函數(shù)最大化問題.對于流次模優(yōu)化的問題，Badanidiyuru［4］引入衡量其算法性能的4 個指標(biāo)，分別為：（1）數(shù)據(jù)流被讀取（訪問）的次數(shù)；（2）空間復(fù)雜性，指存儲數(shù)據(jù)的規(guī)模；（3）運(yùn)行時間，一般指計函數(shù)值的調(diào)用（查詢）次數(shù)；（4）近似比，指流結(jié)束時算法輸出解的值與當(dāng)前流下最優(yōu)值的比［4］.與傳統(tǒng)離線模型的近似算法相比，流算法更加注重存儲空間的有效性，學(xué)者們提出許多適用于流模型次模最大化問題的算法，比如基數(shù)約束流次模最大化問題［5］、背包約束流次模最大化問題［6］、獨(dú)立系統(tǒng)約束的流次模最大化問題、帶滑動窗口的次模最大化問題和在線次模最大化問題等［7］.對于大規(guī)模流數(shù)據(jù)的次模優(yōu)化問題，由于之前的次模優(yōu)化算法需要反復(fù)訪問完整的數(shù)據(jù)集，人們不能將它們直接應(yīng)用于海量流數(shù)據(jù)，因此Badanidiyuru團(tuán)隊在《Streaming submodular maximization：massive data summarization on the fly》一文中提出了一種求解在基數(shù)約束下的次模極大化問題的有效方法.在大規(guī)模機(jī)器學(xué)習(xí)應(yīng)用中，除了流算法，還有其他一些關(guān)于次模集函數(shù)最大化的算法，包括在線算法、隨機(jī)貪婪算法、分散式演算法等［8］.該文主要通過構(gòu)造一個滿足流模型下條件的帶比率集函數(shù)，改進(jìn)之前已有的算法，并進(jìn)行分析和證明，以獲得相應(yīng)的近似比，更快速更精確地解決在提取海量流數(shù)據(jù)信息的過程中出現(xiàn)的受基數(shù)約束的非次模集函數(shù)最大化問題.

1 相關(guān)理論概述

1.1 問題提出

1.2 基本定義

定義1［9］（多項式時間算法）稱一個算法是多項式時間可解的，如果該算法對于問題輸入占有空間大小為n的時間復(fù)雜度為O（nk），其中k是一個非負(fù)整數(shù).

定義2［9］（P類）所有可以用確定型圖靈機(jī)在多項式時間內(nèi)求解的判定問題.

定義3［9］（NP 類）所有可以用非確定型圖靈機(jī)在多項式時間內(nèi)接受的判定問題實例.

定義4［9］（近似比）一個α－近似算法A定義如下：對于實例x，可以證明算法A的近似解A（x）的值不會比最優(yōu)值OPT的α倍更多（或更少，這取決于具體問題）.

系數(shù)α稱為算法A的近似比.

定義5［10］（次模函數(shù)）如果對于任意子集X，Y ?G，有f（X）＋f（Y）≥f（X ∩Y）＋f（X ∪Y），則稱集合函數(shù)f是次模函數(shù).

定義6［10］（邊際增益）對于任意e ∈G和S ?G，△f（e，S）＝f（e ｜S）＝f（S ∪｛e｝）－f（S）表示數(shù)據(jù)e加到集合S中產(chǎn)生的邊際增益.

定義7［10］（單調(diào)性）如果對于任意S ?T ?G，都有f（S）≤f（T），則稱集合函數(shù)f單調(diào)不減.

定義8［10］（歸一化）如果f（?）＝0，則稱集合函數(shù)f是歸一化的.

定義9［10］（次模最大化）一般來說，次模函數(shù)的最大化問題可以定義為：

其中集合函數(shù)f：2G→R ≥0在具有基數(shù)約束的子集S上，即｜S ｜≤k.

定義10［13］（非次模）非次模集函數(shù)f 的定義：對于任意S ?T，e ?T，γ ∈［0，1］有

2 算法設(shè)計

該文改進(jìn)了在流模型下滿足基數(shù)約束的求解非次模函數(shù)最大化問題的3種算法.算法的主要思想是提前設(shè)置一個閾值，這些算法的結(jié)果從一個空集開始，即S ＝?，如果新元素同時滿足閾值條件和基數(shù)約束，就將其添加到解集S中.

2.1 已知最優(yōu)值的算法

在經(jīng)典的次模極大化貪婪算法中，會在每次迭代中選擇具有高邊際值的元素，但是在流模型中決定當(dāng)前元素是否具有足夠的邊際增益是一個挑戰(zhàn).一般的想法是以某種方式將其與最優(yōu)值OPT進(jìn)行比較.如果能夠知道所有的數(shù)據(jù)信息，就可以利用二分法找到最優(yōu)值.但在流模型中，要找到最優(yōu)值并不容易，因此，在該文中假設(shè)了OPT為式（1）的最佳值.此外，還需要設(shè)置一個直觀的值來模擬滿足αOPT ≤v ≤OPT 的最優(yōu)值，其中α ∈［0，1］.將遞減收益率γ與v相結(jié)合，改進(jìn)了之前已有算法的系數(shù)，重新構(gòu)造一個特定的閾來計算新的來源元素.

算法1給定一個基集G，令n ＝｜G ｜，整數(shù)k ≤n，一個集合函數(shù)f，f 的遞減收益率為γ ∈［0，1］，參數(shù)α ∈［0，1］，實數(shù)v∈［αOPT，OPT］，令S ∶＝?，i ∶＝1.

步驟2如果i ＝n，輸出S；否則，令i ∶＝i ＋1，再回到步驟1.

傳遞次數(shù)、存儲元素的內(nèi)存和每個元素的更新時間（讀取新元素時的oracle調(diào)用次數(shù)）可以通過以下引理來估計.

引理1只掃描一次數(shù)據(jù)流，存儲最多k 個元素，每個元素有O（1）更新時間.

為了分析算法的性能保證，提出以下技術(shù)引理來判斷子集S 在每一個循環(huán)中的平均質(zhì)量水平.

引理2在子集為S 的算法的每一個循環(huán)中，有

證明可以通過數(shù)學(xué)歸納法來證明式（2）.

定理1對于任意給定的實數(shù)α ∈［0，1］和具有遞減收益率γ ∈［0，1］的非次模函數(shù)f，算法產(chǎn)生一個集合S，使得｜ S ｜≤k，且f（S）≥，其中OPT是式（1）的最優(yōu)值.

證明考慮以下關(guān)于約束算法輸出的解集S的基數(shù)的2種情況.

2.2 已知最大單例值的算法

引理3算法掃描數(shù)據(jù)流兩次，最多存儲O（klog（k／γ）／ε）個元素，每個元素的更新時間為O（log（k／γ）／ε）.

下面的引理表明最優(yōu)值候選集包含一個接近真正最優(yōu)值的值.

引理4存在一個值v ∈Vε，使得（1－ε）OPT ≤v ≤OPT.

定理2算法對于任意0 ＜ε ＜1，0 ≤γ ≤1輸出解集S，使得｜S ｜≤k，且有f（S）≥

證明同樣考慮兩種情況.

2.3 更新近似最優(yōu)值候選集的算法

算法3給定一個基集G，令n ＝｜G ｜，整數(shù)k ≤n，一個帶有遞減收率γ ∈［0，1］的集合函數(shù)f，設(shè)m：＝0，i：＝1，V0：＝?，V：＝｛（1 ＋ε）l｜l ∈Z｝.對于每一個v ∈V，設(shè)Sv：＝?.

其中｜Sv｜＜k，則設(shè)Sv∶＝Sv∪｛ei｝，刪除所有Sv，使v ∈Vi－1＼Vi.

引理5［2］算法只掃描一次數(shù)據(jù)流，最多存儲O（klog（k／γ）／ε）個元素，每個元素有O（log（k／γ）／ε）更新時間.

下面的引理6表明了閾值在i（v）之前不滿足.因此，可以假設(shè)從一開始就檢查每一個v.

引理7對于任意ε ∈（0，1），算法產(chǎn)生了滿的解集S，其中γ是f的遞減收益率.

3 結(jié)論

該文研究了流模型下受基數(shù)約束的非次模集函數(shù)的最大化問題，主要改進(jìn)了三種利用遞減收益率的算法.算法1 只掃描一次數(shù)據(jù)流.存儲元素的內(nèi)存為k，每個元素的更新時間為O（1），近似比為，其中α ∈［0，1］為參數(shù)，γ ∈［0，1］為集合函數(shù)的遞減收益率.算法1 要求知道最優(yōu)值，但實際上這通常是不可能的，而算法2構(gòu)造了一組數(shù)字，其中至少有一個數(shù)字接近最優(yōu)值.為此，算法2 必須掃描數(shù)據(jù)流兩次并存儲O（klog（k／γ）／ε）個元素.算法2 的近似比為，每個元素的更新時間為O（log（k／γ）／ε）.在算法3中，當(dāng)每次掃描數(shù)據(jù)流中的新元素時，就會更新近似最優(yōu)值的候選集.因此，它只需要掃描一次數(shù)據(jù)流就可以保持相同的近似比率、儲存元素的內(nèi)存以及算法2中每個元素的更新時間.其實，除了利用遞減收益率，還有一些其他方法也可以用來研究非次模函數(shù)，比如次模比和曲率.現(xiàn)有工作中關(guān)于次模最大化的研究有很多，但是對于非次模最大化的問題有待更加深入的研究和探討.