Outcome indistinguishability
Outcome indistinguishability
复制标题
DOI：
10.1145/3406325.3451064
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
C. Dwork;Michael P. Kim;Omer Reingold;G. Rothblum;G. Yona
中科院分区：
文献类型：
--
作者：
C. Dwork;Michael P. Kim;Omer Reingold;G. Rothblum;G. Yona
预测算法将数字分配给个人，这些数字被普遍理解为个人的“概率”--癌症诊断后五年存活的概率是多少？--这些数字越来越成为改变生活的决定的基础。基于复杂性理论和密码学对计算不可区分性的理解，我们引入了结果不可区分性。无法区分结果的预测因素(OI)为结果提供了一个生成性模型，这些结果不能基于产生的现实生活观察有效地驳斥。我们研究了OI定义的层次结构，其严格性随着区分者可以访问所讨论的预测器的程度而增加。我们的发现表明，OI的行为本质上不同于之前研究的不可区分概念。首先，我们在层次结构的所有级别上提供构造。然后，利用最近开发的机器来证明平均情况下的细粒度硬度，我们获得了更严格的OI形式的复杂性的下界。这一艰难的结果为政治论点提供了第一个科学依据，即在检查算法风险预测工具时，审计师应该被授予访问算法的先知权限，而不仅仅是历史预测。
Prediction algorithms assign numbers to individuals that are popularly understood as individual “probabilities”—what is the probability of 5-year survival after cancer diagnosis?—and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are Outcome Indistinguishable (OI) yield a generative model for outcomes that cannot be efficiently refuted on the basis of the real-life observations produced by . We investigate a hierarchy of OI definitions, whose stringency increases with the degree to which distinguishers may access the predictor in question. Our findings reveal that OI behaves qualitatively differently than previously studied notions of indistinguishability. First, we provide constructions at all levels of the hierarchy. Then, leveraging recently-developed machinery for proving average-case fine-grained hardness, we obtain lower bounds on the complexity of the more stringent forms of OI. This hardness result provides the first scientific grounds for the political argument that, when inspecting algorithmic risk prediction instruments, auditors should be granted oracle access to the algorithm, not simply historical predictions.