在有偏差的情况下最大化子模函数进行推荐
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
本文提出了一种能够动态地为信息源进行排序,同时又能保证重复信息的减少不会影响子模函数的最优化问题算法,并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。
Jul, 2014
本文通过研究 subset selection 问题中的系统性和无意识偏见,探讨了在加入公平性约束条件下如何提高选择结果的质量,发现这与使用 multiwinner 得分函数的方式有很大关系,有些函数只需要少量排名即可达到近似最佳解,而对于其他函数却需要大量排名进行修正,并提供了工具进行实证验证。
Jun, 2023
通过直接优化偏差和方差的组合,该研究通过展示如何进行具有理论保证的高效算法,从而在次模函数中进行分布式鲁棒优化(DRO),从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。
Feb, 2018
本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法,旨在提高对次模优化的建模范围,尤其应用于单个或多个基序,背包以及具有分散鲁棒性的标准约束条件,该算法适用于离线和在线设置,并且在线问题的双标准解决方案具有 sub-linear 的遗憾。
Oct, 2017
研究论文中,我们探讨了序列次模优化的基本问题,针对从一个给定集合中选择和排序 k 个项目的场景,最大化 k 个(可能非单调的)次模函数的加权求和,其中每个函数 f_j 将序列中的前 j 个项目作为输入。不同于过去关于单调情形的研究,本文首次考虑了具有非单调次模函数的问题,并提出了对于灵活和固定长度约束以及具有相同效用函数的特殊情况的有效解决方案。通过视频推荐领域的实证评估,我们提出的算法的有效性得到了验证。这项研究的结果对推荐系统和组合优化等多个领域具有重要意义,其中项目的排序对于整体价值具有显著影响。
Aug, 2023
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013