国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于樣本的優(yōu)化

2021-09-22 01:55張智杰孫曉明張家琳陳衛(wèi)
大數(shù)據(jù) 2021年5期
關(guān)鍵詞:概率定義樣本

張智杰,孫曉明,張家琳,陳衛(wèi)

1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所,北京 100086;2. 中國(guó)科學(xué)院大學(xué),北京 100049;3. 微軟亞洲研究院,北京 100080

1 引言

為了解決實(shí)際生活中遇到的統(tǒng)籌優(yōu)化問(wèn)題,人們通常要建立一個(gè)問(wèn)題模型,并確定模型的參數(shù)和優(yōu)化目標(biāo)函數(shù),然后設(shè)計(jì)算法進(jìn)行求解。然而,在大數(shù)據(jù)時(shí)代,許多應(yīng)用場(chǎng)景無(wú)法提供足夠的信息來(lái)確定模型參數(shù)和目標(biāo)函數(shù)。人們只能通過(guò)觀察到的歷史樣本數(shù)據(jù)來(lái)獲取模型的信息,并進(jìn)行優(yōu)化。在這類(lèi)場(chǎng)景下,人們通常使用機(jī)器學(xué)習(xí)的方法進(jìn)行處理:首先近似地學(xué)習(xí)一個(gè)替代的目標(biāo)函數(shù),然后優(yōu)化這個(gè)替代的函數(shù)。盡管這個(gè)方法在實(shí)際應(yīng)用中獲得了巨大的成功,但是在很多實(shí)際問(wèn)題中,這個(gè)方法缺乏理論上的保證。事實(shí)上,它可能存在如下兩個(gè)問(wèn)題:① 即使針對(duì)原函數(shù)的優(yōu)化問(wèn)題是可求解或者可近似求解的,但是針對(duì)替代函數(shù)的優(yōu)化問(wèn)題也可能是不可近似的,這是因?yàn)樘娲瘮?shù)可能丟失了一些原函數(shù)所具有的良好性質(zhì)(如次模性);② 即使替代函數(shù)是可近似的,而且從整體上看和原函數(shù)很接近,但是它的最優(yōu)解相較于原函數(shù)的最優(yōu)解也可能是一個(gè)很差的近似。這些擔(dān)憂自然地引出了如下問(wèn)題:人們是否真的能從一系列樣本數(shù)據(jù)中求解目標(biāo)函數(shù)的優(yōu)化問(wèn)題?

1.1 樣本優(yōu)化模型

為了回答基于樣本的組合優(yōu)化是否可能的問(wèn)題,Balkanski E等人[1]定義了另一種計(jì)算模型——樣本優(yōu)化(optimization from samples,OPS)模型。

定義1(OPS模型)給定參數(shù)如果存在算法A(不一定是多項(xiàng)式時(shí)間的),給定參數(shù)并將樣本集作為輸入,其中,Si獨(dú)立同分布于D,,算法A返回S∈M,并滿足

則稱函數(shù)類(lèi) 在分布D下對(duì)于約束M是α-可優(yōu)化的。其中,α被稱為近似比,表示算法的解與最優(yōu)解的比值。算法使用的樣本數(shù)t被稱為算法的采樣復(fù)雜度。顯然,樣本分布D會(huì)顯著影響函數(shù)類(lèi)F在OPS模型下的可優(yōu)化性。例如,當(dāng)D總是返回空集作為樣本時(shí),不可能對(duì)問(wèn)題得到任何有意義的近似比。因此,人們轉(zhuǎn)而希望在某些“合理的”樣本分布下,優(yōu)化是可能的。此外,對(duì)于在查詢模型下具有常數(shù)近似比的問(wèn)題,人們通常希望它在OPS模型下也具有常數(shù)近似比。對(duì)于這類(lèi)問(wèn)題,如果存在分布D,當(dāng)將給定多項(xiàng)式數(shù)量的獨(dú)立同分布于D的樣本作為輸入時(shí),問(wèn)題存在常數(shù)近似算法,則稱它們(在OPS模型下)是可優(yōu)化的;反之,則稱它們是不可優(yōu)化的。

樣本優(yōu)化模型在目標(biāo)函數(shù)可優(yōu)化且可學(xué)習(xí)的情況下最具研究?jī)r(jià)值。Balcan M F等人[2]首先定義了集合函數(shù)的PMAC(probably mostly approximately correct learnability)-可學(xué)習(xí)性。

定義2(PMAC-可學(xué)習(xí)性)對(duì)于函數(shù)類(lèi)F和參數(shù),如果給定參數(shù)并將樣本集作為輸入,其中,Si獨(dú)立同分布于D,,存在輸出,并滿足

如果在每個(gè)分布D上都是α-PMAC-可學(xué)習(xí)的,則稱F在分布D上是α-PMAC-可學(xué)習(xí)的。

由定義2可知,函數(shù)類(lèi)F是α-PMAC-可學(xué)習(xí)的意味著在大多數(shù)輸入集合上(相對(duì)于分布D而言),存在某種算法學(xué)習(xí)到的函數(shù)值與真實(shí)的函數(shù)值很接近。并且,人們通常要求這對(duì)于任意的分布D均成立。而函數(shù)可優(yōu)化性的定義只要求存在分布D使之成立即可。

最后,覆蓋函數(shù)和影響力函數(shù)是這一領(lǐng)域的重要研究對(duì)象,下面介紹它們的定義。給定二部圖G=(L,R,E),其中,L和R分別表示左右兩邊的點(diǎn)集,E表示點(diǎn)之間的邊集。覆蓋函數(shù)定義為集合S?L的鄰居的個(gè)數(shù),即。而最大覆蓋問(wèn)題要求選取最多k個(gè)左邊的節(jié)點(diǎn),并最大化它們覆蓋的鄰居數(shù)。換言之,它要求在基數(shù)約束下最大化一個(gè)覆蓋函數(shù),即

影響力函數(shù)是覆蓋函數(shù)在一般有向圖上的推廣。它被定義在社交網(wǎng)絡(luò)(有向圖)G=(V,E,p)上,其中,V表示點(diǎn)集,E表示邊集,p表示概率向量,每條邊(u,v)∈E具有概率。每個(gè)節(jié)點(diǎn)存在激活和未激活兩種狀態(tài)。給定t=0的初始激活節(jié)點(diǎn)S0(被稱為種子集合),其他節(jié)點(diǎn)以如下方式被激活:在時(shí)刻t=1,2,3,…,首先令接著,對(duì)于每個(gè)節(jié)點(diǎn),令表示v的入鄰居,每個(gè)節(jié)點(diǎn)會(huì)以概率puv獨(dú)立地激活節(jié)點(diǎn)v。v一旦被激活,就會(huì)被加入St中。節(jié)點(diǎn)被激活的過(guò)程是不可逆的,因此有。一旦沒(méi)有新的節(jié)點(diǎn)被激活,此過(guò)程終止。顯然,這一過(guò)程最多進(jìn)行n-1步。因此,可以使用來(lái)表示激活節(jié)點(diǎn)的隨機(jī)序列。上述傳播過(guò)程被稱為獨(dú)立級(jí)聯(lián)傳播模型。給定S0,定義為最終的激活節(jié)點(diǎn)。影響力函數(shù) 被定義為,即種子集合S激活的節(jié)點(diǎn)數(shù)的期望。影響力最大化問(wèn)題要求選取一個(gè)大小不超過(guò)k的種子集合,并最大化它激活的期望節(jié)點(diǎn)數(shù),即

1.2 不可近似性結(jié)果

Balkanski E等人[1]在OPS模型下研究了最大覆蓋問(wèn)題的近似性,即在基數(shù)約束下最大化一個(gè)覆蓋函數(shù)。此前,覆蓋函數(shù)被證明是(1-)-PMAC可學(xué)習(xí)的[4]。此外,在查詢模型下,最大覆蓋問(wèn)題是(1-e-1)-近似[5]的。因此,人們相信若采取“先學(xué)習(xí)后優(yōu)化”的策略,最大覆蓋問(wèn)題在OPS模型下是可優(yōu)化的。然而,令人驚訝的是,Balkanski E等人[1]證明了在OPS模型下,最大覆蓋問(wèn)題實(shí)際上是不存在常數(shù)近似的。換言之,盡管覆蓋函數(shù)是可學(xué)習(xí)的,卻不是可優(yōu)化的。這使基于樣本的組合優(yōu)化問(wèn)題得到一個(gè)否定性的回答。Balkanski E等人[1]的證明中構(gòu)造了一類(lèi)PMAC-可學(xué)習(xí)的覆蓋函數(shù),這類(lèi)函數(shù)在絕大多數(shù)輸入集合上能近似得很好,然而,這些近似良好的集合恰恰不是問(wèn)題的最優(yōu)解集,并且最優(yōu)解與這些集合的函數(shù)值有較大差別。這解釋了樣本優(yōu)化模型下不可近似性結(jié)果的由來(lái)。從概念上說(shuō),基于“先學(xué)習(xí)后優(yōu)化”的思路,原問(wèn)題通常可以被拆解為采樣模型下的學(xué)習(xí)問(wèn)題與查詢模型下的優(yōu)化問(wèn)題。盡管這兩個(gè)問(wèn)題都是容易解決的,將它們結(jié)合起來(lái)卻不能解決樣本優(yōu)化問(wèn)題。這是因?yàn)檫@兩個(gè)問(wèn)題的子目標(biāo)沒(méi)有完全對(duì)應(yīng),學(xué)習(xí)任務(wù)的子目標(biāo)只要求在絕大多數(shù)集合上學(xué)得好,但這些學(xué)得好的集合恰恰是在優(yōu)化意義上比較差的集合,因此對(duì)于原函數(shù)的優(yōu)化沒(méi)有幫助。

OPS模型十分容易被推廣到其他優(yōu)化問(wèn)題上,而類(lèi)似的不可近似性結(jié)果也出現(xiàn)在其他多個(gè)優(yōu)化問(wèn)題中。

眾所周知,無(wú)約束次模函數(shù)①對(duì)于,如果有則稱函數(shù)是次模的。最小化問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)精確求解[6]。此外,當(dāng)假定函數(shù)的取值在[0,1]之間時(shí),可以證明以均等的概率返回空集或者全集,就能夠得到一個(gè)1/2的加性近似[7]。針對(duì)這一問(wèn)題,Balkanski E等人[7]定義了如下OPS模型。

定義3給定參數(shù),如果存在算法A,給定參數(shù)并將樣本集作為輸入,其中,Si獨(dú)立同分布于,算法A返回,并滿足

Balkanski E等人[7]證明了,在OPS模型下存在一類(lèi)PAC-可學(xué)習(xí)的取值在[0,1]之間的次模函數(shù),對(duì)于任意分布D,將給定多項(xiàng)式數(shù)量的獨(dú)立同分布于D的樣本作為輸入,這類(lèi)函數(shù)不存在的加性近似。

上述不可近似性結(jié)果并不局限于組合優(yōu)化中。眾所周知,凸函數(shù)的最小化問(wèn)題也是多項(xiàng)式時(shí)間可解的。針對(duì)這一問(wèn)題,Balkanski E等人[8]定義了如下OPS模型。

定義4給定參數(shù),如果存在算法A,給定參數(shù)并將樣本集作為輸入,其中,xi獨(dú)立同分布于,算法A返回,并滿足

Balkanski E等人[8]證明了,在OPS模型下,存在一類(lèi)PAC-可學(xué)習(xí)的凸函數(shù)族,對(duì)于任意分布D,將給定多項(xiàng)式數(shù)量的獨(dú)立同分布于D的樣本作為輸入,這類(lèi)函數(shù)不存在(1/2-O(1))的加性近似。這個(gè)界是緊的(相當(dāng)于最優(yōu)的),這是因?yàn)榭梢宰C明返回x=(1/2,1/2,…,1/2)就能達(dá)到1/2的加性近似。

上述幾個(gè)結(jié)果表明,許多在查詢模型下可以優(yōu)化的問(wèn)題在采樣模型下卻是不可優(yōu)化的,盡管從樣本中可以學(xué)習(xí)到這些問(wèn)題的目標(biāo)函數(shù)。這說(shuō)明了函數(shù)是可學(xué)習(xí)的并不意味著它是可優(yōu)化的。

1.3 算法結(jié)果

后續(xù)有一系列工作嘗試?yán)@開(kāi)OPS模型下的不可近似性結(jié)果[9-13]。這樣的嘗試大致可以分為3類(lèi)。

第一類(lèi)方法假設(shè)目標(biāo)函數(shù)f擁有額外的性質(zhì)。例如,Balkanski E等人[10]考慮了f是曲率為的單調(diào)②對(duì)于,如果, 則稱函數(shù)是單調(diào)的。次模函數(shù)的情況。曲率[14]是衡量單調(diào)次模函數(shù)線性程度的一個(gè)度量。曲率越小,函數(shù)越接近線性。例如,線性函數(shù)和覆蓋函數(shù)都滿足單調(diào)性和次模性,但是線性函數(shù)的曲率為0,而覆蓋函數(shù)的曲率為1。Balkanski E等人[10]證明了,在OPS模型下,當(dāng)樣本分布為約束上的均勻分布時(shí),問(wèn)題存在近似,并且這個(gè)近似比是最優(yōu)的。線性函數(shù)的曲率為0意味著線性函數(shù)即使在OPS模型下也是可以精確求解的。而覆蓋函數(shù)的曲率為1,這個(gè)結(jié)果和OPS模型下最大覆蓋問(wèn)題的不可近似性并不矛盾。

影響力最大化問(wèn)題是社交網(wǎng)絡(luò)研究中的核心問(wèn)題之一[3]。獨(dú)立級(jí)聯(lián)傳播模型下的影響力函數(shù)是單調(diào)次模函數(shù)的一個(gè)重要實(shí)例,而覆蓋函數(shù)又是此影響力函數(shù)的特例。因此,影響力函數(shù)在OPS模型下也是不可優(yōu)化的。由于影響力函數(shù)被定義在社交網(wǎng)絡(luò)G=(V,E,p)上,為了繞開(kāi)OPS模型下的不可近似性結(jié)果,Balkanski E等人[9]考慮了帶有社區(qū)結(jié)構(gòu)的社交網(wǎng)絡(luò)上的影響力函數(shù)。更具體地說(shuō),他們假設(shè)G是通過(guò)隨機(jī)區(qū)塊模型(stochastic block model)生成的,因此G可被高概率地劃分為若干社區(qū)C1,C2,… ,C?,且社區(qū)內(nèi)部的邊比較稠密,社區(qū)之間的邊比較稀疏。他們證明了,對(duì)于這樣生成的社交網(wǎng)絡(luò)和約束上的均勻分布,影響力最大化問(wèn)題存在常數(shù)近似算法。

可以發(fā)現(xiàn),上述方法不改變OPS模型本身,但是通常要求目標(biāo)函數(shù)具有良好的性質(zhì),因此其適用范圍有所限制。

第二類(lèi)方法弱化了優(yōu)化目標(biāo)。Rosenfeld N等人[13]提出了OPS模型的一個(gè)變種版本,稱之為DOPS(distributional optimization from samples)模型。

定義5(DOPS模型)給定參數(shù)如果存在算法A,對(duì)于任意分布D,給定獨(dú)立同分布于D的樣本集,參數(shù)并將另一批樣本集作為輸入,其中,Si獨(dú)立同分布于D,f∈F,,算法A返回并滿足

可以發(fā)現(xiàn),在DOPS模型中,不存在約束M,優(yōu)化目標(biāo)也不是尋找全局最優(yōu)解。模型的優(yōu)化目標(biāo)是在函數(shù)值未知的大小為m的樣本集T中尋找函數(shù)值最大的樣本。因此,優(yōu)化目標(biāo)取決于樣本分布D。算法可以使用另一批函數(shù)值已知的樣本集來(lái)收集函數(shù)f的信息,并最終達(dá)成上述目標(biāo)。需要注意的是,在OPS模型中,要求樣本數(shù)t關(guān)于基集合的大小是多項(xiàng)式的,表示問(wèn)題規(guī)模。因此,作為類(lèi)比,在DOPS模型中,要求t關(guān)于m是多項(xiàng)式的。

Rosenfeld N等人[13]證明了一個(gè)集合函數(shù)類(lèi)在DOPS模型下是α-可優(yōu)化的,當(dāng)且僅當(dāng)它是α-PMAC-可學(xué)習(xí)的。這種解決方式恰恰利用了之前“可學(xué)習(xí)但不可優(yōu)化”的矛盾之處。函數(shù)可學(xué)習(xí)說(shuō)明替代函數(shù)在絕大多數(shù)地方和目標(biāo)函數(shù)很接近,而這里的絕大多數(shù)是相對(duì)于分布D而言的。如果分布D較偏離函數(shù)最優(yōu)解,則會(huì)導(dǎo)致即使替代函數(shù)整體上接近目標(biāo)函數(shù),在最優(yōu)解附近可能也會(huì)偏離較遠(yuǎn),進(jìn)而使得全局優(yōu)化目標(biāo)很難達(dá)成。與之相對(duì)地,只針對(duì)函數(shù)值未知的樣本定義的優(yōu)化目標(biāo)會(huì)更容易達(dá)成。但是這個(gè)解決方式最終達(dá)成的優(yōu)化目標(biāo)依賴于樣本數(shù)據(jù)的分布,并不符合通常對(duì)集合函數(shù)的優(yōu)化問(wèn)題的要求。人們?nèi)匀幌M鄬?duì)合理的分布D能為原目標(biāo)函數(shù)的全局最優(yōu)解提供一定的理論保證。

第三類(lèi)方法既不假定目標(biāo)函數(shù)滿足額外的性質(zhì),也不弱化優(yōu)化目標(biāo),而是假設(shè)樣本攜帶額外的結(jié)構(gòu)信息,這樣的樣本被稱為結(jié)構(gòu)化樣本。Chen W等人[11]首先研究了這種方法,針對(duì)覆蓋函數(shù)提出了OPS模型的一個(gè)變種版本——結(jié)構(gòu)化樣本優(yōu)化(optimization from structured samples,OPSS)模型。

定義6(OPSS模型)給定參數(shù)如果存在算法A,給定參數(shù)并將樣本集作為輸入,其中,Si獨(dú)立同分布于D,為Si在二部圖G上的鄰居,算法A返回S∈M,并滿足

在OPSS模型中,算法不僅知道iS覆蓋的鄰居數(shù),還知道它具體覆蓋了哪些節(jié)點(diǎn),因此掌握了關(guān)于函數(shù)結(jié)構(gòu)的部分信息。Chen W等人[11]證明了,當(dāng)分布D滿足可行性、多項(xiàng)式大小的采樣概率和負(fù)相關(guān)性這3個(gè)條件時(shí),最大覆蓋問(wèn)題在OPSS模型下存在常數(shù)近似。因此,通過(guò)假設(shè)樣本是結(jié)構(gòu)化的,所得結(jié)果繞過(guò)了OPS模型下的不可近似性結(jié)果。

這一結(jié)果后來(lái)被推廣到獨(dú)立級(jí)聯(lián)模型下的影響力函數(shù)最大化問(wèn)題[12]。在OPSS模型下,算法的輸入是結(jié)構(gòu)化樣本,其中獨(dú)立同分布于D,給定的產(chǎn)生遵循獨(dú)立級(jí)聯(lián)模型的傳播過(guò)程。Chen W等人[12]證明了當(dāng)分布是乘積分布時(shí),影響力最大化問(wèn)題存在常數(shù)近似。

可以發(fā)現(xiàn),由于不同目標(biāo)函數(shù)的結(jié)構(gòu)各不相同,因此難以定義通用的OPSS模型,需要基于各個(gè)函數(shù)的結(jié)構(gòu)特點(diǎn)給出具有針對(duì)性的定義。本文將著重介紹OPSS模型下的算法結(jié)果。

2 OPSS模型

2.1 最大覆蓋問(wèn)題

Chen W等人[11]為OPSS模型下的最大覆蓋問(wèn)題設(shè)計(jì)了如下算法。

算法1:最大覆蓋問(wèn)題的OPSS算法

令T1=S1

以等概率返回T1和T2中的一個(gè)

算法1以相等的概率返回兩個(gè)可行解T1和T2中的一個(gè),其中T1=S1就是第一個(gè)樣本,而T2是通過(guò)在二部圖上運(yùn)行標(biāo)準(zhǔn)最大覆蓋問(wèn)題的k-近似算法得到的。二部圖是原圖G的一個(gè)近似,它是由樣本構(gòu)造出來(lái)的。對(duì)于節(jié)點(diǎn)uL∈ ,定義它在上的鄰居為用來(lái)近似它的真實(shí)鄰居

直觀的算法設(shè)計(jì)如下:如果某個(gè)單元素集{u}從分布D中被采樣出來(lái),那么算法能完全知曉NG(u)的信息。然而,從D中采樣出來(lái)的可能是一個(gè)大集S,對(duì)于節(jié)點(diǎn)uS∈ ,NG(u)的信息被隱 藏 在NG(S)中。幸運(yùn)的是,如果節(jié)點(diǎn)同時(shí)屬于兩個(gè)樣本S1、S2,那么有。因此,算法1使用包含節(jié)點(diǎn)的樣本的鄰居的交集作為節(jié)點(diǎn)u的真實(shí)鄰居的估計(jì),以便盡可能地揭露u的真實(shí)鄰居的信息。

為了對(duì)算法1進(jìn)行嚴(yán)格的理論分析,需要假定算法在如下假設(shè)下運(yùn)行。

假設(shè)1假設(shè)2L上的分布D滿足如下3個(gè)條件。

● 可行性。樣本S~D總是可行的,即

● 多項(xiàng)式大小的采樣概率。存在常數(shù)c>0,對(duì)于每個(gè)節(jié)點(diǎn)

● 負(fù)相關(guān)性。對(duì)于S~D,隨機(jī)變量是負(fù)相關(guān)的,即

上述3個(gè)條件都是非常自然的。特別地,第二個(gè)條件意味著L中的所有元素都有足夠的概率被采樣到。第三個(gè)條件直觀上意味著u出現(xiàn)在樣本中這一事件的發(fā)生會(huì)減少其他節(jié)點(diǎn)出現(xiàn)在樣本中的概率。顯然,這個(gè)條件降低了許多個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)在樣本中的概率,有助于算法1揭示特定節(jié)點(diǎn)的鄰居的信息。一些典型的分布均滿足假設(shè)1,例如上的均勻分布 D≤k以及上的均勻分布Dk?;诩僭O(shè)1,可以證明:

定理1對(duì)于任意δ∈ ( 0,1),給定任意標(biāo)準(zhǔn)最大覆蓋問(wèn)題的k-近似算法,令表示算法1返回的解,OPT表示原圖G上的最優(yōu)解。如果分布D滿足假設(shè)1且樣本數(shù)其中,c是假設(shè)1中的參數(shù),那么

如果只要求常數(shù)近似比,則假設(shè)1中“可行性”的條件可以被放寬為Chen W等人[11]還證明了如下結(jié)論。

● 當(dāng)樣本分布D為均勻分布 D≤k或 Dk時(shí),存在算法能夠達(dá)到近似比。

● 移除假設(shè)1中的任意一個(gè)條件,存在滿足剩下兩個(gè)條件的某個(gè)分布D,在這一分布下不存在常數(shù)近似算法。這意味著為了得到OPSS模型下最大覆蓋問(wèn)題的常數(shù)近似算法,假設(shè)1的3個(gè)條件都是必須滿足的。

2.2 影響力最大化問(wèn)題

Chen W等人[12]采取如下框架求解OPSS模型下的影響力最大化問(wèn)題:首先學(xué)習(xí)邊的概率,然后在學(xué)習(xí)到的社交網(wǎng)絡(luò)上求解影響力最大化問(wèn)題。其中,學(xué)習(xí)邊概率的任務(wù)被稱為網(wǎng)絡(luò)推斷(network inference)問(wèn)題,它的嚴(yán)格定義如下:給定結(jié)構(gòu)化樣本,其中獨(dú)立同分布于D,給定的產(chǎn)生遵循獨(dú)立級(jí)聯(lián)模型的傳播過(guò)程,,要求計(jì)算一個(gè)概率向量,使得

為了求解上述問(wèn)題,Chen W等人[12]假設(shè)產(chǎn)生種子的分布是乘積分布,即對(duì)于樣本S~D,事件之間是相互獨(dú)立的。

在是乘積分布的假設(shè)下,Chen W等人[12]提出了一個(gè)高效求解網(wǎng)絡(luò)推斷問(wèn)題的方案。為了描述這一方案,需要定義一些符號(hào)。記是激活節(jié)點(diǎn)的隨機(jī)序列。對(duì)于節(jié)點(diǎn)u,定義,表示u被選為種子的概率。對(duì)于節(jié)點(diǎn)v∈V,定義,表示v在一個(gè)時(shí)間步之內(nèi)被激活的概率。節(jié)點(diǎn)v既有可能因?yàn)楸贿x為種子而激活,也有可能被種子激活。因此,ap(v)定義中的隨機(jī)性既來(lái)自種子分布D,也來(lái)自圖G上第一個(gè)時(shí)間步之內(nèi)的傳播過(guò)程。此 外,定 義表示節(jié)點(diǎn)u不是種子時(shí)相應(yīng)的條件概率。Chen W等人[12]的關(guān)鍵性觀察如下。

引理1給定任意u,v∈V且u≠v,

引理1的證明思路如下:在一個(gè)時(shí)間步之內(nèi),節(jié)點(diǎn)v或者被節(jié)點(diǎn)u之外的節(jié)點(diǎn)激活,或者被節(jié)點(diǎn)u激活。由于D是乘積分布,可以得到

重新排列式(10)便可以得到引理1中的結(jié)果。

有了引理1后,就可以通過(guò)估計(jì)qu、ap(v)和來(lái)估計(jì)puv。

算法2:網(wǎng)絡(luò)推斷算法

對(duì)于所有u,v∈V,分別估計(jì)和

假設(shè)2存在參數(shù)和使得

● 對(duì)于所有v∈V, ap(v)≤1?α;

在假設(shè)2下,可以證明如下定理。

定理2在假設(shè)2下,令表示算法2返回的邊的概率,表示真實(shí)的邊概率。給定,如果樣本的數(shù)量,那么

接著介紹如何利用網(wǎng)絡(luò)推斷算法解決OPSS模型下的影響力最大化問(wèn)題。Narasimhan H等人[15]證明了如下引理。

引理2給定S?V和任意兩個(gè)概率向量,并滿足,用σp表示定義在圖G= (V,E,p)上的影響力函數(shù),那么

為了得到一個(gè)在任何社交網(wǎng)絡(luò)上均能運(yùn)行的OPSS算法,Chen W等人[12]采取了處理最大覆蓋問(wèn)題時(shí)所用的技術(shù)。具體地說(shuō),算法首先對(duì)每個(gè)節(jié)點(diǎn)v∈V估計(jì)ap(v)的值,并比較它們與給定閾值的大小。如果ap(v)大于給定閾值,那就意味著節(jié)點(diǎn)v以高概率在一步之內(nèi)被激活,此時(shí),算法將它的所有入邊的概率設(shè)置為1;如果ap(v)小于此閾值,那么假設(shè)2的條件被滿足,可以使用網(wǎng)絡(luò)推斷算法估計(jì)v的所有入邊的概率。經(jīng)過(guò)上述步驟可以得到一張新圖。算法在這張新圖上運(yùn)行k-近似的影響力最大化算法,并得到一個(gè)解。算法使用第一個(gè)樣本作為另一個(gè)解,最終以等概率返回兩個(gè)解中的一個(gè)。

算法3:影響力最大化問(wèn)題的OPSS算法

f or 每個(gè)v∈Vdo

else

對(duì)于所有u,v∈V,分 別 估 計(jì)、和

end if

end for

以等概率返回1T和2T中的一個(gè)

上述算法與最大覆蓋問(wèn)題的OPSS算法(算法1)的設(shè)計(jì)思路是一致的。ap(v)接近1意味著節(jié)點(diǎn)v以高概率在一步之內(nèi)被激活,因此網(wǎng)絡(luò)推斷算法的假設(shè)不被滿足,算法無(wú)法學(xué)習(xí)到節(jié)點(diǎn)v的入邊概率。幸運(yùn)的是,這同時(shí)意味著任意一個(gè)樣本都能夠以高概率激活節(jié)點(diǎn)v。因此算法無(wú)須學(xué)習(xí)節(jié)點(diǎn)v的入邊概率,而是直接把它們?cè)O(shè)置為1。這樣的設(shè)置幾乎不改變樣本激活節(jié)點(diǎn)v的概率。

上述設(shè)計(jì)使得算法能夠處理任意ap(v),從而移除了假設(shè)2中關(guān)于ap(v)的條件。而作為代價(jià),算法需要假設(shè)樣本的期望大小不超過(guò)k/2,從而保證采樣出來(lái)的樣本高概率是可行的。因此,算法需要在下面的假設(shè)下運(yùn)行。

假設(shè)3存在參數(shù),使得

顯然,假設(shè)3的兩個(gè)條件都是針對(duì)樣本分布的,不針對(duì)社交網(wǎng)絡(luò)。因此,算法3在任何社交網(wǎng)絡(luò)都可以成功運(yùn)行??梢宰C明,算法3是一個(gè)常數(shù)近似算法。

定理3對(duì)于任意,給定任意標(biāo)準(zhǔn)影響力最大化問(wèn)題的k-近似算法,令表示算法3返回的解表示原圖G上的最優(yōu)解。如果分布D滿足假設(shè)3且樣本數(shù)那么

最后,若把假設(shè)3中的第一個(gè)條件改為“存在常數(shù)c>0,使得”,仍然能夠通過(guò)修改算法得到一個(gè)常數(shù)近似比。如果,那么可以修改算法得到一個(gè)-近似。

3 未來(lái)研究方向

樣本優(yōu)化仍然有許多可以進(jìn)一步研究的方向。

● 針對(duì)OPSS模型下的最大覆蓋問(wèn)題和影響力最大化問(wèn)題,降低現(xiàn)有算法的查詢復(fù)雜度。此外,目前影響力最大化的OPSS算法假設(shè)樣本分布是乘積分布。如何突破這樣的獨(dú)立采樣假設(shè)是一個(gè)十分重要的開(kāi)放問(wèn)題,一種可能的方法是將文中的方法與極大似然估計(jì)方法結(jié)合。

● 對(duì)更多的目標(biāo)函數(shù)定義適當(dāng)?shù)慕Y(jié)構(gòu)化樣本,并研究它們?cè)贠PSS模型下的近似性。一個(gè)直接的例子是線性閾值模型下的影響力最大化函數(shù)(筆者已經(jīng)得到了這方面的初步結(jié)果)??梢园l(fā)現(xiàn),OPSS模型是一個(gè)表達(dá)能力豐富、能夠挖掘函數(shù)內(nèi)在結(jié)構(gòu)性質(zhì)的模型。因此,在OPSS模型下研究各類(lèi)優(yōu)化問(wèn)題是一個(gè)十分有潛力的研究方向。

● 研究更多的方法以繞開(kāi)標(biāo)準(zhǔn)OPS模型下的不可近似性結(jié)果。更多這樣的研究一方面有助于人們應(yīng)對(duì)不同的應(yīng)用場(chǎng)景,另一方面有助于人們理解樣本數(shù)據(jù)與函數(shù)可優(yōu)化性的內(nèi)在聯(lián)系。

● 研究從樣本中優(yōu)化凸函數(shù)的可能性。目前所有繞開(kāi)OPS模型不可近似性結(jié)果的方法都是針對(duì)集合函數(shù)而言的。對(duì)于實(shí)函數(shù),尤其是具有良好優(yōu)化性質(zhì)的凸函數(shù),尚沒(méi)有這方面的研究??紤]到凸函數(shù)在連續(xù)優(yōu)化中的重要地位,對(duì)它的進(jìn)一步研究是十分必要的。

4 結(jié)束語(yǔ)

本文總結(jié)了OPS模型及其變種模型下的不可近似性結(jié)果和算法成果,并展望了相關(guān)的未來(lái)研究方向。OPS模型是數(shù)據(jù)驅(qū)動(dòng)的優(yōu)化的重要研究方法之一,值得進(jìn)行更加深入的研究。

猜你喜歡
概率定義樣本
以愛(ài)之名,定義成長(zhǎng)
概率統(tǒng)計(jì)中的決策問(wèn)題
概率統(tǒng)計(jì)解答題易錯(cuò)點(diǎn)透視
概率與統(tǒng)計(jì)(1)
概率與統(tǒng)計(jì)(2)
嚴(yán)昊:不定義終點(diǎn) 一直在路上
定義“風(fēng)格”
規(guī)劃·樣本
人大專(zhuān)題詢問(wèn)之“方城樣本”
隨機(jī)微分方程的樣本Lyapunov二次型估計(jì)
青冈县| 昭觉县| 资讯 | 安化县| 会同县| 读书| 聂荣县| 平舆县| 南投县| 广饶县| 班戈县| 比如县| 平安县| 肃南| 牙克石市| 邹平县| 霍邱县| 哈尔滨市| 昌邑市| 鞍山市| 和顺县| 奇台县| 确山县| 杨浦区| 阜城县| 金川县| 揭东县| 定兴县| 梁平县| 青阳县| 芷江| 江西省| 凤庆县| 玉龙| 舒城县| 玉林市| 手游| 秀山| 蓝田县| 西昌市| 武陟县|