带基数约束的次模+超模(BP)函数最大化问题的流算法

doi:10.15960/j.cnki.issn.1007-6093.2022.01.006

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 85-98.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.006

带基数约束的次模+超模(BP)函数最大化问题的流算法

连月芳¹, 张真宁¹^,*(), 赵中睿¹, 堵丁柱²

1. 北京工业大学数学学院运筹学与信息工程系, 北京 100124
2. 美国德克萨斯大学达拉斯分校计算机系, 美国德克萨斯州理查德森市 75080

收稿日期:2021-06-14 出版日期:2022-03-15 发布日期:2022-03-14
通讯作者: 张真宁 E-mail:zhangzhenning@bjut.edu.cn
作者简介:张真宁 E-mail: zhangzhenning@bjut.edu.cn
基金资助:
国家自然科学基金(12131003);国家自然科学基金(12001025)

Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint

Yuefang LIAN¹, Zhenning ZHANG¹^,*(), Zhongrui ZHAO¹, Dingzhu DU²

1. Department of Operations Research and Information Engineering, College of Mathematics, Beijing University of Technology, Beijing 100124, China
2. Department of Computer Science, University of Texas at Dallas, Richardson, TX75080, USA

Received:2021-06-14 Online:2022-03-15 Published:2022-03-14
Contact: Zhenning ZHANG E-mail:zhangzhenning@bjut.edu.cn

摘要/Abstract

摘要：

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$），我们设计了单轮读取数据的过滤-流算法，并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}}，1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下，能保证在较少的时间内得到与贪婪算法相同的最优值。

关键词: BP-函数最大化, 全局曲率, 边际收益递减率, 流算法, 基数约束

Abstract:

In this paper, wepropose streaming algorithms for the maximization ofsubmodular+supermodular functions with cardinality constraint, whichhas wide applications in data processing, machine learning andartificial intelligence. By means of the diminishing return ratioof the objective function, we design a one-pass sieve-streamingalgorithm and get the approximate ratio $\min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})^{2}}\right\}$. Numerical experiments show that the sieve-streaming algorithm is effective forthe BP-maximization problem and can guarantee the same result asthe greedy algorithm with less time if submodular function andsupermodular are in the same order of magnitude.

Key words: BP-function maximization, total curvature, diminishing return ratio, streaming algorithm, cardinality constraint

中图分类号:

O221.7

连月芳, 张真宁, 赵中睿, 堵丁柱. 带基数约束的次模+超模(BP)函数最大化问题的流算法[J]. 运筹学学报, 2022, 26(1): 85-98.

Yuefang LIAN, Zhenning ZHANG, Zhongrui ZHAO, Dingzhu DU. Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint[J]. Operations Research Transactions, 2022, 26(1): 85-98.

图/表 3

参考文献 31

1	Agrawal R, Gollapudi S, Halverson A, et al. Diversifying search results[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining, 2009: 5-14.
2	Golovin D , Krause A . Adaptive submodularity: Theory and applications in active learning and stochastic optimization[J]. Journal of Artificial Intelligence Research, 2012, 42 (1): 427- 486.
3	Gomez-Rodriguez M , Leskovec J , Krause A . Inferring networks of diffusion and influence[J]. ACM Transactions on Knowledge Discovery from Data, 2010, 5 (4): 1- 37.
4	Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003: 137-146.
5	Wei K, Iyer R, Bilmes J. Submodularity in data subset selection and active learning[C]//Proceedings of International Conference on Machine Learning (ICML), 2015.
6	Topkis D M . Supermodularity and Complementarity[M]. Princeton: Princeton University Press, 2011.
7	Nemhauser G L , Wolsey L A , Fisher M L . An analysis of approximations for maximizing submodular set functions-I[J]. Mathematical Programming, 1978, 14 (1): 265- 294. doi: 10.1007/BF01588971
8	Conforti M , Cornuéjols G . Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem[J]. Discrete Applied Mathematics, 1984, 7 (3): 251- 274. doi: 10.1016/0166-218X(84)90003-9
9	Sviridenko M , Vondrák , J , Ward J . Optimal approximation for submodular and supermodular optimization with bounded curvature[J]. Mathematics of Operations Research, 2017, 42 (4): 1197- 1218. doi: 10.1287/moor.2016.0842
10	Bai W, Bilmes J A. Greed is Still Good: Maximizing Monotone Submodular+Supermodular (BP)functions[C]//International Conference on Machine Learning, 2018: 304-313.
11	Ji S, Xu D, Li M, et al. Stochastic greedy algorithm is still good: Maximizing submodular+ supermodular functions[C]//World Congress on Global Optimization, 2019: 488-497.
12	Muthukrishnan S. Data streams: algorithms and applications[M]//Foundations and Trends in Theoretical Computer Science, 2005: 117-236.
13	Ajtai M, Jayram T S, Kumar R, et al. Approximate counting of inversions in a data stream[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing, 2002: 370-379.
14	Dueck D, Frey B J. Non-metric affinity propagation for unsupervised image categorization[C]//2007 IEEE 11th International Conference on Computer Vision, 2007: 1-8.
15	El-Arini K, Guestrin C. Beyond keyword search: discovering relevant scientific literature[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011: 439-447.
16	El-Arini K, Veda G, Shahaf D, et al. Turning down the noise in the blogosphere[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009: 289-298.
17	Gomes R, Krause A. Budgeted nonparametric learning from data streams[C]//Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010: 391-398.
18	Zoubin G. Scaling the indian buffet process via submodular maximization[C]//International Conference on Machine Learning, 2013: 1013-1021.
19	Badanidiyuru A, Mirzasoleiman B, Karbasi A, et al. Streaming submodular maximization: massive data summarization on the fly[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014: 671-680.
20	Yu Q , Li H , Liao Y , et al. Fast budgeted influence maximization over multi-action event logs[J]. IEEE Access, 2018, 6, 14367- 14378. doi: 10.1109/ACCESS.2018.2809547
21	Norouzi-Fard A, Tarnawski J, Mitrovic S, et al. Beyond 1/2-approximation for submodular maximization on massive data streams[C]//International Conference on Machine Learning, 2018: 3826-3835.
22	Elenberg E, Dimakis A G, Feldman M, et al. Streaming weak submodularity: interpreting neural networks on the fly[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 4044-4054.
23	Wang Y J , Xu D C , Wang Y S , et al. Non-submodular maximization on massive data streams[J]. Journal of Global Optimization, 2020, 76 (4): 729- 743. doi: 10.1007/s10898-019-00840-8
24	Barbosa R, Ene A, Nguyen H L, et al. The power of randomization: distributed submodular maximization on massive datasets[C]//International Conference on Machine Learning, 2015: 236-1244.
25	Barbosa R, Ene A, Nguyen H L, et al. A new framework for distributed submodular maximiza tion[C]//2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016: 645-654.
26	Buchbinder N, Feldman M, Schwartz R. Online submodular maximization with preemption[C]//Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, 2014: 1202-1216.
27	Chakrabarti A , Kale S . Submodular maximization meets streaming: matchings, matroids, and more[J]. Mathematical Programming, 2015, 154 (1): 225- 247.
28	Mirzasoleiman B, Badanidiyuru A, Karbasi A, et al. Lazier than lazy greedy[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2015: 1812-1818.
29	Fujishige S . Submodular Functions and Optimization[M]. Amsterdam: Elsevier, 2005.
30	Bian A A, Buhmann J M, Krause A, et al. Guarantees for greedy maximization of non submodular functions with applications[C]//Proceedings of the 34th International Conference on Machine Learning (ICML), 2017: 498-507.
31	杨瑞琪, 徐大川, 杜东雷, 等. 次模函数最大化的流算法综述[J]. 运筹学学报, 2020, 24 (2): 73- 86.

性能	近似比	存储空间	运行时间	读取次数
算法1	$ \min\left\{\frac{\alpha\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})}\right\} $	$ k $	$ \mathrm{O}(1) $	1
算法2	$ \min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})}\right\} $	$ O\left(\frac{k \log (k/\gamma)}{\varepsilon}\right) $	$ O\left(\frac{\log (k/\gamma)}{\varepsilon}\right) $	2
算法3	$ \min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})^{2}}\right\} $	$ O\left(\frac{k\log (k / \gamma)}{\varepsilon}\right) $	$ O\left(\frac{\log (k / \gamma)}{\varepsilon}\right) $	1

带基数约束的次模+超模(BP)函数最大化问题的流算法

Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 31

相关文章 1

编辑推荐

Metrics

本文评价