求流模型下帶比率的集函數(shù)最大值問(wèn)題求解研究*

耿紅梅

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

0 引言

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

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

1.1 問(wèn)題提出

1.2 基本定義

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

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

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

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

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

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

定義6［10］（邊際增益）對(duì)于任意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)性）如果對(duì)于任意S ?T ?G，都有f（S）≤f（T），則稱集合函數(shù)f單調(diào)不減.

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

定義9［10］（次模最大化）一般來(lái)說(shuō)，次模函數(shù)的最大化問(wèn)題可以定義為：

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

2.2 已知最大單例值的算法

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

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

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

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

證明同樣考慮兩種情況.

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

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

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

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

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

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

3 結(jié)論

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