高维遗憾最小化
High-dimensional Regret Minimization
Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Wong
AI 速读 基于摘要
提出 FHDR 框架，利用稀疏线性偏好，通过轻量交互在高维数据上快速发现关键属性，从而降低交互式遗憾最小化的交互轮数与执行时间。
cs.DB · cs.CG · cs.IR
查看原文摘要
Multi-criteria decision making over large databases is fundamental to many real-world applications. Interactive regret minimization has emerged recently as a promising approach that combines the controllable output size of top-$k$ queries with the flexibility of skyline queries, without requiring users to explicitly specify a utility function. Instead, the system iteratively presents a small set of options, learns the user's implicit preferences from their selections, and progressively refines its recommendations. However, modern applications such as housing search and financial product selection often involve hundreds of attributes. Existing interactive methods either fail to scale to such high-dimensional data or require excessive user interaction, frequently exceeding $1000$ rounds. We address this limitation with FHDR (Fast High-Dimensional Reduction), a framework that exploits sparse linear preferences to discover key attributes through lightweight interactions. We also propose AttributeSubset, an efficient single-round algorithm that returns a compact recommendation set without further feedback. In our experiments on real datasets, FHDR completes in under $0.03$s and requires fewer than $30$ interaction rounds under the default setting. Extensive experiments on both synthetic and real-world datasets show that FHDR outperforms the best-known baselines by at least one order of magnitude in execution time and by up to several orders of magnitude in interaction cost. These results establish FHDR as a new state of the art for scalable interactive regret minimization.