自适应采样的噪声子模型最大化及其在众包图像集摘要中的应用

AAAINov, 2015

自适应采样的噪声子模型最大化及其在众包图像集摘要中的应用

Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization

Adish Singla, Sebastian Tschiatschek, Andreas Krause

TL;DR提出了一种用于最大化未知子模函数的通用算法，该函数只能通过嘈杂的数据来访问，并利用探索模块建议好的元素以适应不同观察模型，解决覆盖率和多样性最大化的内容概括问题。

Abstract

We address the problem of maximizing an unknown submodular function that can only be accessed via noisy evaluations. Our work is motivated by the task of summarizing content, e.g., image collections, by leveragin

submodular function noisy evaluations summarization cardinality constraints exploration module

发现论文，激发创造

噪音下的次模优化

本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束 k>=2 的函数，有一个近似算法，其近似比例任意接近 1-1/e; 对于基数约束 k=1，有一种算法，其近似比率任意接近于 1/2。没有随机算法可以获得比 1/2+o (1) 更好的近似度；如果噪声是对抗性的，则不能获得任何非平凡的近似保证。

Jan, 2016

通过随机化实现子模函数最大化的长期公平性

通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

Apr, 2023

流式非单调子模最大化：实时个性化视频摘要

本文提出了第一个高效的单遍流式计算算法 Streaming Local Search，用于在独立系统和多重背包约束下，同时最大化非单调子模函数，解决实时提取和总结大规模视频流的问题。

Jun, 2017

具近似最优适应性和查询复杂度的非单调次模最大化

研究分布式情况下近似最大化非单调子模函数时算法适应性和查询复杂度的方法及其应用

Aug, 2018

线性子模最大化与赌徒反馈

在带有赌博反馈的子模函数优化中，考虑使用逼近算法来最大化线性结构的子模客观函数，通过模拟算法和实证研究检验了样本效率与线性结构的关系。

Jul, 2024

做更少，得更多：带子采样的流式子模最大化

该论文提出了首个一次遍历的流算法，用于求解子模最大化问题，采用数据采样，能够在各种情况下获得最紧密的逼近保证，同时具有最小的内存占用和对函数评估数量的最低要求，试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上

Feb, 2018

分布鲁棒子模最大化

通过直接优化偏差和方差的组合，该研究通过展示如何进行具有理论保证的高效算法，从而在次模函数中进行分布式鲁棒优化（DRO），从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。

Feb, 2018

具有近似最优的适应性和查询复杂度的子模最大化

本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。

Jul, 2018

可微子模最大化

本文提出一种针对子模函数的数据学习算法，可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布，本文提出一种可微的方式对模型进行优化。实证研究表明，该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。

Mar, 2018

约束次模优化问题的全动态算法

本研究在完全动态的环境下，旨在最大化基数约束下的单调子模函数，研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法，并结合经验研究证明了算法性能的优越性。

Jun, 2020