为证据组合优化设计决策感知的近似方法,提升实际决策质量。
Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization
- 基于决策后果而非距离度量,优化证据质量
- 在随机实例中减少决策翻转比例超过传统方法
- 适用于需实时决策的优化场景,如路径规划
经典的质量函数简化方法依赖于如Jaccard或Jousselme等内在距离,以保持近似与原始证据体的接近性。本文关注质量函数用于线性组合优化问题且成本具有不确定性的情况。此时应保留的是决策结果的质量,而非函数间的距离。提出一种决策感知近似方法,以最小化真实成本下决策的遗憾为目标。在最短路径问题上,距离最优近似会改变正确决策,而该方法在非可忽略比例的随机实例中保持原决策。证明了单点误差界,将其转化为标量情形下的精确动态规划,并扩展至在线版本,在最终成本未知时即可剪枝焦点元素。实验表明,无论使用线性目标还是非线性代理指标,该压缩方法均比表示感知压缩更少发生决策翻转。
原文摘要 · Abstract (English)
Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。