English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In Machine Learning, the $\mathsf{SHAP}$-score is a version of the Shapleyvalue that is used to explain the result of a learned model on a specificentity by assigning a score to every feature. While in general computingShapley values is an intractable problem, we prove a strong positive resultstating that the $\mathsf{SHAP}$-score can be computed in polynomial time overdeterministic and decomposable Boolean circuits. Such circuits are studied inthe field of Knowledge Compilation and generalize a wide range of Booleancircuits and binary decision diagrams classes, including binary decision treesand Ordered Binary Decision Diagrams (OBDDs).  We also establish the computational limits of the SHAP-score by observingthat computing it over a class of Boolean models is always polynomially as hardas the model counting problem for that class. This implies that bothdeterminism and decomposability are essential properties for the circuits thatwe consider. It also implies that computing $\mathsf{SHAP}$-scores isintractable as well over the class of propositional formulas in DNF. Based onthis negative result, we look for the existence of fully-polynomial randomizedapproximation schemes (FPRAS) for computing $\mathsf{SHAP}$-scores over suchclass. In contrast to the model counting problem for DNF formulas, which admitsan FPRAS, we prove that no such FPRAS exists for the computation of$\mathsf{SHAP}$-scores. Surprisingly, this negative result holds even for theclass of monotone formulas in DNF. These techniques can be further extended toprove another strong negative result: Under widely believed complexityassumptions, there is no polynomial-time algorithm that checks, given amonotone DNF formula $\varphi$ and features $x,y$, whether the$\mathsf{SHAP}$-score of $x$ in $\varphi$ is smaller than the$\mathsf{SHAP}$-score of $y$ in $\varphi$.

On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results