论文标题
查询最佳算法，用于查找反事实
A Query-Optimal Algorithm for Finding Counterfactuals
论文作者
论文摘要
我们设计了一种算法，用于查找具有强大理论保证其性能的反事实算法。对于任何单调型号$ f：x^d \ to \ {0,1 \} $和实例$ x^\ star $，我们的算法使\ [{s（f）^{o（δ_f（x^\ star）} \ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \ d} $ x^\ star $：最近的实例$ x'$ to $ x^\ star $，$ f（x'）\ ne f（x^\ star）$。 $ s（f）$是$ f $的灵敏度，lipschitz常数的离散类似物，$Δ_f（x^\ star）$是$ x^\ star $到其最近的反事实的距离。以前最著名的查询复杂性是$ d^{\，o（δ_f（x^\ star））} $，可以通过Brute-Force Local Search实现。我们进一步证明了$ s（f）^{ω（δ_f（x^\ star））} +ω（\ log d）$的下限在任何算法的查询复杂性上，从而表明我们算法的保证基本上是最佳的。
We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model $f : X^d \to \{0,1\}$ and instance $x^\star$, our algorithm makes \[ {S(f)^{O(Δ_f(x^\star))}\cdot \log d}\] queries to $f$ and returns {an {\sl optimal}} counterfactual for $x^\star$: a nearest instance $x'$ to $x^\star$ for which $f(x')\ne f(x^\star)$. Here $S(f)$ is the sensitivity of $f$, a discrete analogue of the Lipschitz constant, and $Δ_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\,O(Δ_f(x^\star))}$, achievable by brute-force local search. We further prove a lower bound of $S(f)^{Ω(Δ_f(x^\star))} + Ω(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.
