从样本中学习序列选择，用有限数据优化排序效果。
Learning Submodular Sequencing from Samples
- 基于随机序列样本学习序列优化策略，不依赖完整函数信息。
- 在多项式样本下实现与函数曲率相关的近似比。
- 适合无法获取完整收益函数的真实场景，如电商推荐排序。
本文研究序列子模最大化问题：通过选择和排序项目序列以优化复合子模函数。不同于以往假设可访问效用函数的工作，本文假设仅提供一组样本，每个样本包含一个随机序列及其对应的效用值。我们提出一种算法，在多项式数量的样本（来自两阶段均匀分布）下，可实现依赖于各子模函数曲率的近似比。该方法适用于多种现实场景，如在线零售平台的产品排序，其中完全掌握效用函数往往不可行。实验表明，该算法在数据有限的情况下仍能给出实用的序列优化方案，证明了有限数据在序列任务中的巨大潜力。技术上，该工作将“从样本中优化”的研究从集合函数推广至序列相关函数。
原文摘要 · Abstract (English)
This paper addresses the problem of sequential submodular maximization: selecting and ranking items in a sequence to optimize some composite submodular function. In contrast to most of the previous works, which assume access to the utility function, we assume that we are given only a set of samples. Each sample includes a random sequence of items and its associated utility. We present an algorithm that, given polynomially many samples drawn from a two-stage uniform distribution, achieves an approximation ratio dependent on the curvature of individual submodular functions. Our results apply in a wide variety of real-world scenarios, such as ranking products in online retail platforms, where complete knowledge of the utility function is often impossible to obtain. Our algorithm gives an empirically useful solution in such contexts, thus proving that limited data can be of great use in sequencing tasks. From a technical perspective, our results extend prior work on ``optimization from samples'' by generalizing from optimizing a set function to a sequence-dependent function.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。