For a Boolean function $\Phi\colon\{0,1\}^d\to\{0,1\}$ and an assignment to
its variables $\mathbf{x}=(x_1, x_2, \dots, x_d)$ we consider the problem of
finding the subsets of the variables that are sufficient to determine the
function value with a given probability $\delta$. This is motivated by the task
of interpreting predictions of binary classifiers described as Boolean circuits
(which can be seen as special cases of neural networks). We show that the
problem of deciding whether such subsets of relevant variables of limited size
$k\leq d$ exist is complete for the complexity class
$\mathsf{NP}^{\mathsf{PP}}$ and thus generally unfeasible to solve. We
introduce a variant where it suffices to check whether a subset determines the
function value with probability at least $\delta$ or at most $\delta-\gamma$
for $0<\gamma<\delta$. This reduces the complexity to the class
$\mathsf{NP}^{\mathsf{BPP}}$. Finally, we show that finding the minimal set of
relevant variables can not be reasonably approximated, i.e. with an
approximation...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 131,277 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible