AAAI 2020 | 南京大學提出高效演化算法 EAMC：可更好解決子集選擇問題

2020 年 2 月 23 日
筆記

機器之心發佈

機器之心編輯部

日前，AAAI 2020 已在美國紐約隆重召開。不久之前，大會官方公布了今年的論文收錄信息：收到 8800 篇提交論文，評審了 7737 篇，接收 1591 篇，接收率 20.6%。為向讀者們分享更多的優質內容、促進學術交流，機器之心策划了多期AAAI 2020 論文線上分享。

近日，機器之心邀請了南京大學人工智能學院研究助理卞超通過線上分享的方式介紹他們入選 AAAI 2020 的研究論文《An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints》。這篇論文提出了一個高效的演化算法 EAMC，來解決一般約束下的子集選擇問題。本文將對這項研究成果進行介紹。

論文地址：http://www.lamda.nju.edu.cn/qianc/aaai20-eamc-final.pdf

子集選擇問題是一個 NP-hard 問題，並且具有很多應用場景，比如最大覆蓋、影響力最大化和傳感器放置。該問題的目標是從 n 個元素中，選擇滿足約束 c 的一個子集，使得目標函數 f 的值最大：

其中 f 和 c 都是單調的，但並不一定滿足子模性。

針對這類問題，現有的代表性算法有廣義貪心算法和 POMC。廣義貪心算法耗時較短，但是受限於它的貪心行為，其找到的解質量往往一般；POMC 作為隨機優化算法，可以使用更多的時間來找到質量更好的解，但是其缺乏多項式的運行時間保證。為此，這篇 AAAI 2020 論文提出了一個高效的演化算法 EAMC。通過優化一個整合了 f 和 c 的代理函數，它可以在多項式時間內找到目前已知最好的近似解。研究者還在最大覆蓋、影響力最大化和傳感器放置等任務上進行了實驗，結果表明該算法的表現優於廣義貪心算法。

前提說明與定義

令 R 和 R^+ 分別表示實數集和非負實數集。給定一個全集 V = {v_1, v_2, … , v_n}，研究的問題是在 V 的子集上的函數 f : 2^V → R。如果 ∀X ⊆ Y 時 f(X) ≤ f(Y)，則稱集合函數 f 是單調的，這說明往一個集合添加更多元素時永遠不會導致函數值減少。不失一般性地，假設，這些單調函數是歸一化的，即 f(∅) = 0。如果對於任意 X ⊆ Y ⊆ V 和 v ∉ Y，有 f(X∪{v})−f(X)≥f(Y∪{v})−f(Y)，則稱集合函數 f 是子模 (submodular) 函數，這表示該函數具有增益遞減性質，即向集合 X 增加元素時所帶來的收益大於向 X 的超集 Y 添加同樣的元素。

對於一個廣義的集合函數 f，如定義 1 所示的子模比（submodularity）的概念可用於度量 f 所具有的子模性的程度。當 f 單調時，有這兩個結論：（1）0 ≤ α_f ≤ 1；（2）α_f = 1 當且僅當 f 是子模函數。注意，在衡量 f 與子模性的相近程度方面還存在其它一些符號，比如 Krause and Cevher 2010; Das and Kempe 2011; Zhou and Spanos 2016 等中使用的符號。

定義 1：子模比。非負集合函數 f 的子模比定義為：

定義 2 所代表的總曲率描述了單調子模函數 f 與模塊度（modularity）的相近程度。很容易驗證 1 ≥ 1 – κ_f ≥ 0。在這篇論文中，研究者用κ_f 表示廣義單調函數。根據式（2），如果沒有子模性，則 1/α_f ≥ 1 – κ_f ≥ 0 成立。

定義 2：總曲率。定義單調子模集合函數 f 的總曲率為：

定義 3 給出了本研究所關注的問題，即最大化單調目標 f，使得單調成本函數 c 的上界處在預算 B 的約束下。f 和 c 並不必須都是子模函數。假設 f 由一個 value oracle 給定，即對於任意子集 X，都有一個算法可以查詢 oracle 以得到 f(X) 的值。和之前一些論文一樣，研究者也假設精確的成本函數 c 是無法得到的，而只能得到一個 ψ(n) 近似 cˆ，其中 ∀X ⊆ V : c(X) ≤ cˆ(X) ≤ ψ(n) · c(X)。這是因為在某些現實應用中，精確計算 c 所需的時間可能呈指數增長。

定義 3：文本所研究的廣義問題。給定一個單調目標函數 f : 2^V → R^+、一個單調成本函數 c : 2^V → R^+ 以及預算 B，目標是找到：

這篇論文在三種應用上通過實驗研究了單調子模目標函數。

第一種應用是最大覆蓋問題。給定一組覆蓋了元素全域的集合，最大覆蓋任務的目標是在一定成本預算下選擇出某些集合併使得這些集合的並集是最大的。可以很容易驗證：f 是單調的子模函數。

定義 4：最大覆蓋。給定一個元素集合 U、U 的一組子集 V ={S1, S2, . . . , Sn}、一個單調成本函數 c : 2^V →R^+ 以及預算 B，目標是找到：

第二種應用是影響力最大化，其目標是識別社交網絡中有影響力的用戶集。首先定義一個有向圖 G = (V, E) 來表示社交網絡，其中每個節點都是一個用戶，每條邊 (u, v) ∈ E（帶有概率 p_{u,v}）表示用戶 u 到 v 的影響力強度。給定預算 B，影響力最大化的目標是找到 V 的一個子集 X，使得由源自 X 的傳播而激活的節點的預期數量最大。獨立級聯（Independence Cascade/IC）是一種基礎的傳播模型。其使用一個集合 A_t 來記錄在時間 t 激活的節點；在時間 t+1，u ∈ A_t 的每個未激活的鄰近節點 v 都有 p_{u,v} 的概率被激活。這個過程不斷重複，直到到達沒有節點再被激活的時間。將由 X 的傳播而激活的節點集記為 IC(X)，這是一個隨機變量。目標 E[|IC(X)|] 被稱為影響力傳播度（influence spread），這是一個單調子模函數，其中 E[·] 是指隨機變量的期望。

定義 5：影響力最大化。給定一個有向圖 G = (V, E)，對於 (u, v)∈E，邊概率為 p_{u,v}；以及單調成本函數 c : 2^V →R^+ 和預算 B，目標是找到：

第三個應用是傳感器放置，其目標是決定有限數量的傳感器的放置位置，使得不確定度能最大限度地降低。令 o_j 表示一個隨機變量，其代表通過在位置 v_j 安裝傳感器而收集到的觀察數據。注意，對於已經觀察到子集 S 的隨機變量的總集合 U，其條件熵（即剩餘的不確定度）為 H(U | S) = H(U) − H(S)，其中 H(·) 表示熵。因此，這個任務的目標是選擇一個位置子集 X，使得 {o_j | v_j ∈ X} 的熵最大。已知熵 H(·) 是一個單調子模函數。

定義 6：傳感器放置。給定 n 個位置 V = {v_1, v_2, … , v_n}、單調成本函數 c : 2^V →R^+ 和預算 B，目標是找到：

對於這些應用，成本限制可能是簡單的規模限制，即 c(X) = |X|；或一般的線性成本限制，即

。但在某些情況中，這個限制可能更加複雜，比如路徑限制，這是單調非子模的。舉個例子，在移動機械人傳感領域，需要計入在不同位置之間移動的成本以及在這些位置進行測量的成本。用圖 G = (V, E) 表示所有位置的路徑網絡，其中 c_e 表示穿過一條邊 e ∈ E 的成本，c_v 表示訪問一個節點 v ∈ V 的成本。成本函數為

，其中

是訪問 X 中每個節點至少一次的最短行走的成本，這通常是非子模的，而且無法在多項式時間中得到準確的計算。本文的實驗中，線性約束和路由約束都會用到。

EAMC 算法

這一節介紹研究者為最大化有單調成本限制的單調函數所提出的一種簡單演化算法：EAMC。EAMC 不會最大化式（3）中的 f，而是引入了一個替代目標 g，並對其進行最大化，用數學表示為：

可以看到，g 同時納入了原有的目標函數 f 以及成本 cˆ。更小的 cˆ 值和更大的 f 值都會導致 g 的值更大。

在優化過程中，EAMC 會保留一個種群 P，然後新生成的解 x' 只會與 bin(|x'|) 中解進行比較。bin(|x'|) 的定義為：

也就是說，x' 只與 P 中與 x' 有同樣大小的解相比。這樣的設置會讓這個解群 P 更加多樣化，由此能夠提升該算法的搜索能力。由於問題式 (3) 需要在滿足預算限制的同時實現 f 的最大化，所以 EAMC 只會考慮滿足 cˆ(x')≤B 的 x'；在運行過程中，除了有最大 g 值的解之外，每個 bin 都保留有截至目前所生成的最大 f 值的解。

算法 3 描述了 EAMC 的執行過程。從空集 0^n 開始（行 1），不斷嘗試改善每個 bin 中的解的 g 值（行 2-21）。在每次迭代中，通過隨機翻轉從當前 P 中選出的解 x 來生成一個新的解 x'（行 3-4）；而且只有當 x' 滿足限制條件時才會被包含進 P 中（行 5）。如果 bin(|x'|) = ∅，則將 x' 添加進 P，並將 u^|x'| 和 v^|x'| 分別用於保留有目前所生成的最大 g 和 f 值的大小為 |x'| 的兩個解（行 7-9）；否則，x' 與 bin(|x'|) 中的解進行比較，如果截至目前生成的最大 g 或 f 得到提升，則更新 bin(|x'|)（行 10-18）。可以看到，每個 bin(i) 都只包含解 u^i 和 v^i，它們可能是一樣的。在 T 輪迭代後，P 中有最大 f 值的解被輸出（行 22）。注意，因為行 5，P 中的所有解都必須滿足約束。

EAMC 需要知道子模比 α_f，因為替代目標 g 需要使用它。對於子模的 f，α_f = 1。對於非子模的 f，精確計算 α_f 可能需要指數級的時間，不過可以在 α_f 上使用一個下限來替代。注意，α_f 的這個下限在一些單調非子模應用中已被推導出來，比如貝葉斯實驗設計和行列式函數最大化。

理論分析

這一節為 EAMC 的一般近似界給出了證明，如定理 3 所示。相比於定理 2，EAMC 能實現與 POMC 同樣的近似保證，即

，但預期的運行時間是多項式的上限。其證明依賴於引理 1，可以直觀地看到，這意味着對於任意子集，某個特定項的包含都至少能將 f 提升一定量，這個量與離最佳結果的當前距離成比例。這裡假設 ∀v ∈ V : cˆ({v}) ≤ B；因為在優化前可以將任意 cˆ({v}) > B 的 v 直接移除。

證明。通過分析如下定義的量 J_max，可以證明該定理。

令 P_max 表示 EAMC 運行期間種群 P 的最大規模。研究者首先表明，在至多 enP_max 個預期數量的迭代後，J_max ≥ 1。很容易看到，解 0^n 將總是位於 P 中，因為只有同樣規模大小的解可以進行比較，而 0^n 是大小為 0 為唯一解。根據引理 1，翻轉一個 0^n 的一個特定 0 位（即添加一個特定項）可以生成一個新的解 x'，使得：

其中由於 ∀r ∈ R : 1 − r ≤ e^−r，後一個不等號是成立的。在每輪迭代中，x' 都至少能以

的概率生成，其中 1/P_max 是從解群選出 0^n 的概率的下界，

是在保持其它位不變的同時翻轉 0^n 的特定比特的概率。因此，生成 x' 的預期迭代次數至多為 enP_max。注意，根據式 (6) 和 (7)，

。如果 x' 包含在 P 中，則有 J_max ≥ 1；否則，bin(1) 中必然存在一個 g 值更大的解，這意味着 J_max ≥ 1。

假設當前的 J_max = i。根據算法 3 的行 11-13 和行 17，bin(i) 中解的最大 g 值不會減小，因此 J_max 也不會減小。這說明總是存在滿足

的 x ∈ bin(i)。

接下來考慮 J_max 增大，直到找到一個 f 值至少為

的解。令 x 表示有最大 g 值的解。根據引理 1，翻轉 x 的特定 0 位可以生成一個滿足 |x'| = i + 1 的解 x'，且

其中，由於 J_max = i，根據

，第一個不等式成立；而根據 ∀r ∈ R : 1 − r ≤ e^−r，最後一個不等式也成立。因此，可以得到

。在每輪迭代中，x' 能以至少

的概率生成，這說明在生成滿足 |x'| = i + 1 和

的 x' 之前的預期迭代數量至多為 enP_max。然後，考慮 cˆ(x') 的兩種情況：

（1）如果 cˆ(x') > B，則式 (8) 說明

。令

，則有：

其中，根據定義 1，第一個不等式成立；根據 α_f ∈ [0, 1]，最後一個不等式成立。在每輪迭代中，可通過選擇 0^n 並翻轉特定的 0 位來生成 y（以至少 1/enP_max 的概率發生）。因此，在至多 enP_max 個預期迭代輪數中可以生成 y。根據行 7-10 和 14-17 中 P 的更新流程，可以知道一旦生成了 y，P 總是包含一個滿足 f(z) ≥ f(y) 的解 z ∈ bin(1)。可以驗證，總是存在一個滿足 f(z') ≥ f(x) 的解 z' ∈ bin(i)。根據算法 3 的行 22，最後返回的解會是 f 值最大的解。因此，EAMC 輸出的解的 f 值至少為：

（2）如果 cˆ(x') ≤ B，根據行 7-13 和 17 的更新流程，可知 x' 將被加入到 P 中，因為不存在滿足 g(z) ≥ g(x') 的 z ∈ bin(i + 1)；否則 g(z) ≥ g(x') ≥ f(X˜)，這與 J_max 的定義相矛盾。現在，J_max = i + 1.

重複以上分析，EAMC 將輸出滿足

的解 z，這意味着達到了所需的近似保證，或者 J_max 將繼續增大，直到到達最大值 n。後面的情況意味着 cˆ(1^n) ≤ B，而 EAMC 將輸出 1^n；因為 f 單調，所以這是最優的。

現在來看看預期的迭代總數。要使 J_max ≥ 1，預期的迭代數量最大為 enP_max；為了將 J_max 從 1 增大到 n，預期的迭代數量至多為 (n-1) · enP_max；為了生成 y，預期的迭代數量至多為 enP_max。因為 bin(i) 中最多有兩個解，其中 1 ≤ i ≤ n – 1（算法 3 的行 17）；而 bin(0) 和 bin(n) 最多只有一個解，有 P_max ≤ 2n。因此，預期的迭代總數至多為