arXiv:2502.07214cs.LGcs.AI2025-02被引 1

提出多成本函数下的帕累托最优可追溯算法,兼顾真实场景复杂性。

Pareto Optimal Algorithmic Recourse in Multi-cost Function

  • 将可追溯问题建模为加权多目标优化,处理不可导与离散成本函数。
  • 通过epsilon-net实现大规模图上近似帕累托最优解,验证可扩展性。
  • 理论严谨,适合需要公平、透明决策的高风险应用如信贷审批。

在决策系统中,算法可追溯旨在识别最小成本行动以改变个体特征,从而获得期望结果。然而,由于系统环境多样性和个人差异,单一成本函数难以量化,尤其在多准则情形下。现有方法多采用基于梯度的方法,假设成本函数可微,往往不适用于现实场景,导致次优解且缺乏严格的理论基础,影响可解释性、可靠性和透明度。本文提出一个处理非可微与离散多成本函数的可追溯框架,将可追溯问题建模为多目标优化,并根据重要性分配权重,识别帕累托最优推荐。为证明可扩展性,引入epsilon-net概念,证明可找到近似帕累托最优动作。实验显示不同准则间的权衡关系及在大规模图上的可扩展性。相比当前启发式方法,本方法具有更强理论基础,更符合真实世界需求。

原文摘要 · Abstract (English)

In decision-making systems, algorithmic recourse aims to identify minimal-cost actions to alter an individual features, thereby obtaining a desired outcome. This empowers individuals to understand, question, or alter decisions that negatively affect them. However, due to the variety and sensitivity of system environments and individual personalities, quantifying the cost of a single function is nearly impossible while considering multiple criteria situations. Most current recourse mechanisms use gradient-based methods that assume cost functions are differentiable, often not applicable in real-world scenarios, resulting in sub-optimal solutions that compromise various criteria. These solutions are typically intractable and lack rigorous theoretical foundations, raising concerns regarding interpretability, reliability, and transparency from the explainable AI (XAI) perspective. To address these issues, this work proposes an algorithmic recourse framework that handles non-differentiable and discrete multi-cost functions. By formulating recourse as a multi-objective optimization problem and assigning weights to different criteria based on their importance, our method identifies Pareto optimal recourse recommendations. To demonstrate scalability, we incorporate the concept of epsilon-net, proving the ability to find approximated Pareto optimal actions. Experiments show the trade-off between different criteria and the methods scalability in large graphs. Compared to current heuristic practices, our approach provides a stronger theoretical foundation and better aligns recourse suggestions with real-world requirements.

可追溯多目标优化帕累托决策公平

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。