Apr, 2024
自适应组合最大化：超过近似贪心策略
Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies
Shlomi Weitzman, Sivan Sabato
TL;DR我们研究了自适应组合最大化问题，在机器学习中是一个核心挑战，并应用于主动学习以及其他许多领域。我们研究贝叶斯设置下，考虑最大化目标在基数约束和最小成本覆盖下。我们提供了新的综合近似保证，包括之前的结果，并且更加加强了它们。我们的近似保证同时支持最大增益比以及接近次模效用函数，包括了在基数约束和最小成本覆盖下的最大化保证。此外，我们对一种修改后的先验提供了近似保证，这对于获得独立于先验最小概率的主动学习保证至关重要。此外，我们发现了一种自适应选择策略的新参数，称之为 “最大增益比”。我们展示了这个参数比之前近似保证中使用的贪婪近似参数要更加宽松，并展示了它可以提供比之前结果更强的近似保证。特别地，我们展示了最大增益比永远不会大于策略的贪婪近似因子，并且它可以大为缩小。这为自适应组合最大化中有用的策略特性提供了新的见解。