Model Interpretability through the Lens of Computational Complexity
In spite of several claims stating that some models are more interpretable than others -- e.g., "linear models are more interpretable than deep neural networks" -- we still lack a principled notion of interpretability to formally compare among different classes of models. We make a step towards such a notion by studying whether folklore interpretability claims have a correlate in terms of computational complexity theory. We focus on local post-hoc explainability queries that, intuitively, attempt to answer why individual inputs are classified in a certain way by a given model. In a nutshell, we say that a class $\mathcal{C}_1$ of models is more interpretable than another class $\mathcal{C}_2$, if the computational complexity of answering post-hoc queries for models in $\mathcal{C}_2$ is higher than for those in $\mathcal{C}_1$. We prove that this notion provides a good theoretical counterpart to current beliefs on the interpretability of models; in particular, we show that under our definition and assuming standard complexity-theoretical assumptions (such as P$\neq$NP), both linear and tree-based models are strictly more interpretable than neural networks. Our complexity analysis, however, does not provide a clear-cut difference between linear and tree-based models, as we obtain different results depending on the particular post-hoc explanations considered. Finally, by applying a finer complexity analysis based on parameterized complexity, we are able to prove a theoretical result suggesting that shallow neural networks are more interpretable than deeper ones.

\subsection{The complexity of \textsc{MinimumChangeRequired}}
\label{ssec:mcr}

In what follows we determine the complexity of the \textsc{MinimumChangeRequired} problem for the three classes of models that we consider.
\begin{restatable}{proposition}{kminchange}
\label{prp:k-minchange}
The \textsc{MinimumChangeRequired} query is (1) in $\text{\rm PTIME}$ for FBDDs, (2) in $\text{\rm PTIME}$ for perceptrons, and (3) $\text{\rm NP}$-complete for MLPs.
\end{restatable}
\begin{proofsketch}
This query has been shown to be solvable in \text{\rm PTIME}~for \emph{ordered} binary decision diagrams (OBDDs, a restricted form of FBDDs) by Shih et al.~\cite[Theorem 6]{shih2018formal} (the query is called \emph{robusteness} in the work of Shih et al.~\cite{shih2018formal}). 
We show that the same proof applies to FBDDs.
Recall that in an FBDD every internal node is labeled with a feature index in~$\{1,\ldots,n\}$.
The main idea is to compute a quantity~$\mathrm{mcr}_u({\bm{x}}) \in \mathbb{N}\cup \{\infty\}$ for every node~$u$ of the FBDD~$\mathcal{M}$.
This quantity 
represents the minimum number of features that we need to flip in~${\bm{x}}$ to 
modify the classification~$\mathcal{M}({\bm{x}})$ 
if we are only allowed to change features associated with the paths from~$u$ to some leaf in the FBDD.
One can easily compute these values by processing the FBDD bottom-up.
Then the minimum change required for~${\bm{x}}$ is the value~$\mathrm{mcr}_r({\bm{x}})$ where~$r$ is the root of~$\mathcal{M}$,
and thus we simply return \textsc{Yes} if~$\mathrm{mcr}_r({\bm{x}})\leq k$, and~\textsc{No} otherwise.

For the case of a perceptron~$\mathcal{M}=({\bm{w}},b)$ and of an instance~${\bm{x}}$, let us assume without loss of generality that~$\mathcal{M}({\bm{x}})=1$.
We first define the \emph{importance}~$s(i) \in \mathbb{Q}$ of every input feature at position~$i$ as follows: if~$x_i =1$ then~$s(i) \coloneqq w_i$, and if~$x_i=0$ then~$s(i) \coloneqq -w_i$. Consider now the set~$S$ that contains the top~$k$
most important input features for which~$s(i) > 0$. We can easily show that it is enough to check whether flipping every feature in~$S$ 
changes 
the classification of~${\bm{x}}$, in which case we return~\textsc{Yes}, and return~\textsc{No} otherwise.

Finally, \text{\rm NP}~membership of MCR for MLPs is clear: guess a partial instance~${\bm{y}}$ with~$\mathrm{d}({\bm{x}}, {\bm{y}}) \leq k$ and check in polynomial time that~$\mathcal{M}({\bm{x}}) \neq \mathcal{M}({\bm{y}})$. We prove hardness with a simple reduction from the~\textsc{VertexCover} problem for graphs, which is known to be \text{\rm NP}-complete. 
\end{proofsketch}

Notice that this result immediately yields Theorems~\ref{theo:fbdd-mlp}, \ref{theo:perceptron-mlp}, and  \ref{prop:perceptron-fbdd} for the case of MCR. 

\subsection{The complexity of \textsc{MinimumSufficientReason}}

We now study the complexity of \textsc{MinimumSufficientReason}. 
The following result yields Theorems~\ref{theo:fbdd-mlp}, \ref{theo:perceptron-mlp}, and  \ref{prop:perceptron-fbdd} for the case of MSR. 

\begin{restatable}{proposition}{ksuff}
\label{prp:ksuff}
The \textsc{MinimumSufficientReason} query is (1) $\text{\rm NP}$-complete for FBDDs (and hardness holds already for decision trees), (2) in~$\text{\rm PTIME}$ for perceptrons, and (3) $\Sigma_2^p$-complete for MLPs.
\end{restatable}
\begin{proofsketch}
Membership of the problem in the respective classes is easy. We show \text{\rm NP}-completeness of the problem for FBDDs by a nontrivial reduction from the 
\text{\rm NP}-complete problem of determining whether a directed acyclic graph has a dominating set of size at most~$k$~\cite{King_2005}. 
For a perceptron~$\mathcal{M}=({\bm{w}},b)$ and an instance~${\bm{x}}$, assume without loss of generality that~$\mathcal{M}({\bm{x}})=1$. 
As in the proof of Proposition~\ref{prp:k-minchange}, we consider the importance of every component of ${\bm{x}}$, and prove that it is enough to check whether the $k$ most important features of ${\bm{x}}$ are a sufficient reason for it, in which case we return~\textsc{Yes}, and simply return~\textsc{No} otherwise.
Finally, the~$\Sigma_2^p$-completeness for~MLPs is obtained again using a technical reduction from the problem called \textsc{Shortest Implicant Core}, defined and shown to be~$\Sigma_2^p$-complete by Umans~\cite{Umans2001}.
\end{proofsketch}

To refine our analysis, we also consider the natural problem of \emph{checking} if a given partial instance is a sufficient reason for an instance.

\begin{center}
\fbox{\begin{tabular}{rl}
Problem: & \textsc{CheckSufficientReason (CSR)} \\
Input: & Model $\mathcal{M}$, instance~${\bm{x}}$ and a partial instance ${\bm{y}}$ \\
Output: & \textsc{Yes}, if ${\bm{y}}$ is a sufficient reason for~${\bm{x}}$ wrt. $\mathcal{M}$, and \textsc{No} otherwise
\end{tabular}}
\end{center}

We obtain the following (easy) result. 

\begin{restatable}{proposition}{checksuff}
\label{prp:checksuff}
The query \textsc{CheckSufficientReason} is (1) in~$\text{\rm PTIME}$ for FBDDs, (2)~in~$\text{\rm PTIME}$ for perceptrons, and (3) $\text{\rm co-NP}$-complete for MLPs.
\end{restatable}

We note that this result for FBDDs already appears in~\cite{darwiche2002knowledge} (under the name of \emph{implicant check}).
Interestingly, we observe that this new query maintains the comparisons in terms of c-interpretability, in the sense that~$\mathcal{C}_\text{FBDD}$ and~$\mathcal{C}_\text{Perceptron}$ are
strictly more c-interpretable than $\mathcal{C}_\text{MLP}$ with respect to~CSR.


\subsection{The complexity of \textsc{CountCompletions}}

What follows is our main complexity result regarding the query \textsc{CountCompletions},
which yields Theorems~\ref{theo:fbdd-mlp}, \ref{theo:perceptron-mlp}, and  \ref{prop:perceptron-fbdd} for the case of CC. 
\begin{restatable}{proposition}{counting}
\label{prp:counting}
The query \textsc{CountCompletions} is (1) in $\text{\rm PTIME}$ for FBDDs, (2) \text{$\#$}\text{\rm P}-complete for perceptrons, and (3) \text{$\#$}\text{\rm P}-complete for MLPs.
\end{restatable}

\begin{proofsketch}
Claim (1) is a a well-known fact that is a direct consequence of the definition of FBDDs; indeed, we can easily compute by bottom-up induction of the FBDD a quantity representing for each node the number of positive completions of the sub-FBDD rooted at that node (e.g.,
see~\cite{darwiche2002knowledge,wegener2004bdds}). We prove (2) by showing a reduction from
the \text{$\#$}\text{\rm P}-complete problem \textsc{$\#$Knapsack}, i.e., counting the number of solutions to
a~$0/1$ knapsack input.\footnote{Recall that such an input consists of natural numbers (given in binary)
$s_1,\ldots,s_n, k \in \mathbb{N}$, and a solution to it is a set $S \subseteq
\{1,\ldots,n\}$ with $\sum_{i \in S} s_i \leq k$.}
For the last
claim, we show that~MLPs with ReLU activations can simulate arbitrary Boolean formulas, 
which allows us to directly conclude~(3) since counting the number of
satisfying assignments of a Boolean formula is \text{$\#$}\text{\rm P}-complete.
\end{proofsketch}


\paragraph{Comparing perceptrons and MLPs.}
Although the query \textsc{CountCompletions} is \text{$\#$}\text{\rm P}-complete for perceptrons, we can still show that the complexity goes down to \text{\rm PTIME}~if we assume the weights and biases to be integers given in unary; this is commonly called \emph{pseudo-polynomial time}.
\begin{restatable}{proposition}{pseudo}
\label{prp:pseudo}
The query \textsc{CountCompletions} can be solved in pseudo-polynomial time for perceptrons (assuming the weights and biases to be integers given in unary).
\end{restatable}
\begin{proofsketch}
This is proved by first reducing the problem to \textsc{$\#$Knapsack}, and then using a classical dynamic
programming algorithm to solve \textsc{$\#$Knapsack} in pseudo-polynomial time.
\end{proofsketch}

This result establishes a difference between perceptrons and MLPs in terms of CC, as this query remains \text{$\#$}\text{\rm P}-complete for the latter
even if weights and biases are given as integers in unary. Another difference is established by the fact that \textsc{CountCompletions} for perceptrons can be 
efficiently approximated, while this is not the case for MLPs. To present this idea, we briefly recall the notion 
of 
{\em fully polynomial randomized
approximation scheme} (FPRAS~\cite{jerrum1986random}), which 
is heavily used to refine the analysis of the complexity of \text{$\#$}\text{\rm P}-hard problems. 
Intuitively, an FPRAS is a polynomial time algorithm that computes with high probability a
$(1-\epsilon)$-multiplicative approximation of the exact solution, for
$\epsilon > 0$, in polynomial time in the size of the input and in the parameter
$1 / \epsilon$. 
We show:

\begin{restatable}{proposition}{approx}
\label{prp:approx}
The problem \textsc{CountCompletions} restricted to perceptrons
admits an FPRAS (and the use of randomness is not even needed in this case). This is not the case for MLPs, on the other hand, at least under standard 
complexity assumptions. 
\end{restatable}










\subsection{Specific models}
\label{subsec:models}

\paragraph{Binary decision diagrams.}
A \emph{binary decision diagram} (BDD~\cite{wegener2004bdds}) is a rooted
directed acyclic graph~$\mathcal{M}$ with labels on edges and nodes, verifying:
(i) each leaf is labeled with~$\true$ or with~$\false$; (ii) each internal node (a
node that is not a leaf) is labeled with an element of~$\{1,\ldots,n\}$; and
(iii) each internal node has an outgoing edge labeled~$1$ and another
one labeled~$0$.  
Every instance ${\bm{x}}=(x_1,\ldots,x_n)\in \{0,1\}^n$ defines a unique path $\pi_{\bm{x}}$ from the root to a leaf in $\mathcal{M}$, 
which satisfies the following condition: for every non-leaf node~$u$ in~$\pi_{\bm{x}}$, if~$i$ is the label of~$u$, then 
the path~$\pi_{\bm{x}}$ goes through the edge that is labeled with~$x_i$.
The instance ${\bm{x}}$ is positive, i.e.,~$\mathcal{M}({\bm{x}}) \coloneqq 1$, 
if the label of the leaf in the path $\pi_{\bm{x}}$
is~$\true$, and  negative otherwise.  The \emph{size}~$|\mathcal{M}|$
of~$\mathcal{M}$ is its number of edges.  A binary decision
diagram~$\mathcal{M}$ is \emph{free} (FBDD) if for every path from the root to a
leaf, no two nodes on that path have the same label. A \emph{decision tree} is
simply an FBDD whose underlying graph is a tree. 
 

\paragraph{Multilayer perceptron (MLP).} 
A multilayer perceptron $\mathcal{M}$ with $k$ layers is defined by a
sequence of {\em weight} matrices ${\bm{W}}^{(1)},\ldots,{\bm{W}}^{(k)}$, {\em bias} vectors ${\bm{b}}^{(1)},\ldots,{\bm{b}}^{(k)}$, 
and {\em activation} functions~$f^{(1)},\ldots,f^{(k)}$. 
Given an instance ${\bm{x}}$, we inductively define 
\begin{equation}\label{eq:mlp}
{\bm{h}}^{(i)} \coloneqq f^{(i)}({\bm{h}}^{(i-1)}{\bm{W}}^{(i)} + {\bm{b}}^{(i)}) \quad \quad \quad (i \in \{1,\dots,k\}),
\end{equation}
assuming that ${\bm{h}}^{(0)}\coloneqq {\bm{x}}$. The output of $\mathcal{M}$ on ${\bm{x}}$ is defined as 
$\mathcal{M}({\bm{x}}) := {\bm{h}}^{(k)}$.
In this paper we assume all weights and biases to be rational numbers. 
That is, we assume that there exists a sequence of positive integers $d_0,d_1,\ldots,d_k$ 
such that ${\bm{W}}^{(i)}\in \mathbb{Q}^{d_{i-1}\times d_i}$ and ${\bm{b}}^{(i)}\in \mathbb{Q}^{d_i}$.
The integer $d_0$ is called the \emph{input size} of $\mathcal{M}$, and $d_k$ the \emph{output size}.
Given that we are interested in binary classifiers, we assume that $d_k=1$.
We say that an~MLP as defined above has $(k-1)$ \emph{hidden layers}.
The {\em size} of an~MLP $\mathcal{M}$, denoted by $|\mathcal{M}|$, is the total size of its weights and biases, in which the size of
a rational number $\nicefrac{p}{q}$ is $\log_2(p)+\log_2(q)$ (with the convention that $\log_2(0)=1$).

We focus on~MLPs in which all internal functions $f^{(1)},\dots,f^{(k-1)}$ are the ReLU function~$\ensuremath{\operatorname{relu}}(x)\coloneqq \max(0,x)$.
Usually, MLP binary classifiers are trained using the \emph{sigmoid} 
as the output function~$f^{(k)}$.
Nevertheless, when an MLP classifies an input (after training), it takes decisions by simply using 
the \emph{pre activations}, also called \emph{logits}.
Based on this and on the fact that we only consider already trained~MLPs, 
we can assume without loss of generality that the output function~$f^{(k)}$ is the \emph{binary step} function,
defined as~$\ensuremath{\operatorname{step}}(x)\coloneqq 0$ if~$x<0$, and~$\ensuremath{\operatorname{step}}(x)\coloneqq 1$ if~$x\geq 0$.

\paragraph{Perceptron.}
A perceptron is an MLP with no hidden layers (i.e., $k=1$). 
That is, a perceptron~$\mathcal{M}$ is defined by a pair~$({\bm{W}},{\bm{b}})$
such that~${\bm{W}}\in\mathbb{Q}^{d\times 1}$ and~${\bm{b}}\in \mathbb{Q}$, and the output is~$\mathcal{M}({\bm{x}})=\ensuremath{\operatorname{step}}({\bm{x}}{\bm{W}}+{\bm{b}})$.
Because of its particular structure, a perceptron is usually defined as a pair~$({\bm{w}},b)$ with~${\bm{w}}$ a rational vector and~$b$ a rational number.
The output of~$\mathcal{M}({\bm{x}})$ is then~$1$ if and only if 
$\langle {\bm{x}},{\bm{w}}\rangle + b\geq 0$, where~$\langle {\bm{x}},{\bm{w}}\rangle$ denotes the dot product between~${\bm{x}}$ and~${\bm{w}}$.


\subsection{Specific queries}

Given instances~${\bm{x}}$ and~${\bm{y}}$, 
we define~$\mathrm{d}({\bm{x}},{\bm{y}}) \coloneqq \sum_{i=1}^n|{\bm{x}}_i-{\bm{y}}_i|$ as the number of components in which~${\bm{x}}$ and~${\bm{y}}$ differ. 
We now formalize the minimum-change-required problem, which checks if the output of the model can be changed by flipping  
the value of at most~$k$ components in the input. 

\begin{center}
\fbox{\begin{tabular}{rl}
Problem: & \textsc{MinimumChangeRequired (MCR)} \\
Input: & Model $\mathcal{M}$, instance ${\bm{x}}$, and~$k \in \mathbb{N}$ \\
Output: & \textsc{Yes}, if there exists an instance ${\bm{y}}$ with $\mathrm{d}({\bm{x}},{\bm{y}}) \leq k$ \\ 
& and $\mathcal{M}({\bm{x}})\neq\mathcal{M}({\bm{y}})$, and \textsc{No} otherwise
\end{tabular}}
\end{center}

Notice that, in the above definition, instead of ``finding'' the minimum change we state the problem as a \textsc{Yes}/\textsc{No}
query (a decision problem) by adding an additional input~$k \in \mathbb{N}$ and then asking for a change of size at most~$k$.
This is a standard way of stating a problem to analyze its complexity~\cite{arora2009computational}.
Moreover, in our results, when we are able to solve the problem in \text{\rm PTIME}~then we can also output a minimum change, and it is clear that if the decision problem is hard then the optimization problem is also hard. Hence, we can indeed state our problems as decision problems without loss of generality.

To introduce our next query, recall that a partial instance is a vector~${\bm{y}}=(y_1,\ldots,y_n) \in \{0,1,\bot\}^n$, and a completion of 
it is an instance~${\bm{x}}=(x_1,\ldots,x_n) \in \{0,1\}^n$ such that for every~$i$ where~$y_i \in \{0,1\}$ it holds that~$x_i = y_i$.
That is, ${\bm{x}}$ coincides with ${\bm{y}}$ on all the components of~${\bm{y}}$ that are not $\bot$.
Given an instance~${\bm{x}}$ and a model~$\mathcal{M}$, a \emph{sufficient reason for~${\bm{x}}$ with respect to~$\mathcal{M}$}~\cite{shih2018symbolic} is a partial instance~${\bm{y}}$, such that 
${\bm{x}}$ is a completion of~${\bm{y}}$ and every possible completion~${\bm{x}}'$ of~${\bm{y}}$ satisfies~$\mathcal{M}({\bm{x}}')=\mathcal{M}({\bm{x}})$.
That is, knowing the value of the components that are defined in~${\bm{y}}$ is enough to determine the output~$\mathcal{M}({\bm{x}})$.
Observe that an instance~${\bm{x}}$ is always a sufficient reason for itself, and that~${\bm{x}}$ could have multiple (other) sufficient reasons.
However, given an instance~${\bm{x}}$, the sufficient reasons of~${\bm{x}}$ that are most interesting are those having the least possible number of defined components; indeed, it is clear that the less defined components a sufficient reason has, the more information it provides about the decision of~$\mathcal{M}$ on~${\bm{x}}$.
For a partial instance~${\bm{y}}$, let us write~$\|{\bm{y}}\|$ for its number of components that are not~$\bot$.
The previous observations then motivate our next interpretability query.
\begin{center}
\fbox{\begin{tabular}{rl}
Problem: & \textsc{MinimumSufficientReason (MSR)} \\
Input: & Model $\mathcal{M}$, instance ${\bm{x}}$, and~$k \in \mathbb{N}$ \\
Output: & \textsc{Yes}, if there exists a sufficient reason~${\bm{y}}$ for ${\bm{x}}$ wrt.~$\mathcal{M}$ with $\|{\bm{y}}\|\leq k$, \\
& and \textsc{No} otherwise

\end{tabular}}
\end{center}
As for the case of MCR, notice that we have formalized this interpretability query as a decision problem.
The last query that we will consider refers to counting the number of {positive completions} for a given partial instance.

\begin{center}
\fbox{\begin{tabular}{rl}
Problem: & \textsc{CountCompletions (CC)} \\
Input: & Model $\mathcal{M}$, partial instance ${\bm{y}}$ \\
Output: & The number of completions ${\bm{x}}$ of ${\bm{y}}$ such that $\mathcal{M}({\bm{x}})=1$
\end{tabular}}
\end{center}

Intuitively, this query informs us on the proportion of inputs that are accepted by the model, given that some particular features have been fixed; or, equivalently,
on the \emph{probability} that such an instance is accepted, assuming the other features to be uniformly and independently distributed. 


\subsection{Main interpretability theorems}

We can now state our main theorems, which are illustrated in Figure~\ref{fig:main-results}. 
In all these theorems we use~$\mathcal{C}_\text{MLP}$ to denote the class of all models (functions from $\{0,1\}^n$ to $\{0,1\}$)
that are defined by MLPs, and similarly for~$\mathcal{C}_\text{FBDD}$ and~$\mathcal{C}_\text{Perceptron}$.
The proofs for all these results will follow as corollaries from the detailed complexity analysis that we present in Section~\ref{sec:complexity}.
We start by stating a strong 
separation between FBDDs and~MLPs, which holds for all the queries presented above. 


\begin{theorem}\label{theo:fbdd-mlp}
$\mathcal{C}_\text{\emph{FBDD}}$ is strictly more c-interpretable than $\mathcal{C}_\text{\emph{MLP}}$
with respect to
\textsc{MCR}, \textsc{MSR}, and~\textsc{CC}.
\end{theorem}

For the comparison between perceptrons and MLPs, 
we can establish a strict separation for MCR and~MSR , but not for CC. In fact, 
CC has the same complexity for both classes of models, which means that none of these classes strictly 
``dominates'' the other in terms of c-interpretability for~CC. 

\begin{theorem}\label{theo:perceptron-mlp}
$\mathcal{C}_\text{\emph{Perceptron}}$ is strictly more c-interpretable than $\mathcal{C}_\text{\emph{MLP}}$ 
with respect to
~\textsc{MCR} and \textsc{MSR}. In turn, the problems $\textsc{CC}(\mathcal{C}_\text{\emph{Perceptron}})$ and 
$\textsc{CC}(\mathcal{C}_\text{\emph{MLP}})$ are both complete for the same complexity class. 
\end{theorem}

The next result shows that, in terms of c-interpretability, the relationship between FBDDs and perceptrons is not clear, 
as each one of them is strictly more c-interpretable than the other for some explainability query.

\begin{theorem}\label{prop:perceptron-fbdd}
The problems~$\textsc{MCR}(\mathcal{C}_\text{\emph{FBDD}})$
and~$\textsc{MCR}(\mathcal{C}_\text{\emph{Perceptrons}})$ are both in~\text{\rm PTIME}.
However,~$\mathcal{C}_\text{\emph{Perceptron}}$ is strictly more c-interpretable
than~$\mathcal{C}_\text{\emph{FBDD}}$ with respect to~\textsc{MSR},
while~$\mathcal{C}_\text{\emph{FBDD}}$ is strictly more c-interpretable
than~$\mathcal{C}_\text{\emph{Perceptron}}$ with respect to~\textsc{CC}.
\end{theorem}

We prove these results in the next section, where for each query~$Q$ and class of models~$\mathcal{C}$ we pinpoint the exact complexity of the problem~$Q(\mathcal{C})$.

\begin{figure}[H]
	\input{figures/diagram-results}
	\caption{Illustration of the main interpretability results. Arrows depict that the pointed class of models is harder with respect to the query that labels the edge. We omit labels (or arrows) when a problem is complete for the same complexity class for two classes of models.}
	\label{fig:main-results}
\end{figure}




\section{Introduction}
\label{sec:introduction}
\input{introduction}

\section{A framework to compare interpretability}
\label{sec:framework}
\input{framework}


\section{Instantiating the framework and main results}
\label{sec:instantiation}
\input{instantiation}

\section{The complexity of explainability queries}
\label{sec:complexity}
\input{complexity}

\section{Parameterized results for MLPs in terms of number of layers}
\label{sec:p-complexity}
\input{p-complexity}

\section{Discussion and concluding remarks}
\label{sec:discussion}
\input{discussion}

\section{Broader impact}
Although interpretability as a subject may have a broad practical impact, our results in this paper are mostly theoretic,
so we think that this work does not present any foreseeable societal consequences.

\begin{ack}
Barceló and Pérez are funded by Fondecyt grant 1200967.
\end{ack}

\newpage 
\bibliographystyle{abbrv}







\subsection{Hardness}
\label{subsec:p-hardness}
\input{p-hardness}

\subsection{Membership}
\label{subsec:p-membership}
\input{p-membership}









\section{Simulating Boolean formulas/circuits with MLPs}
\label{sec:simulation}
\input{simulations}


\section{Proof of Proposition~\ref{prp:k-minchange}}
\label{sec:proof-5}
\input{proof-5}


\section{Proof of Proposition~\ref{prp:ksuff}}
\label{sec:proof-6}
\input{proof-6}


\section{Proof of Proposition~\ref{prp:checksuff}}
\label{sec:proof-7}
\input{proof-7}


\section{Proof of Proposition~\ref{prp:counting}}
\label{sec:proof-8}
\input{proof-8}


\section{Proof of Proposition~\ref{prp:pseudo}}
\label{sec:proof-9}
\input{proof-9}


\section{Proof of Proposition~\ref{prp:approx}}
\label{sec:proof-10}
\input{proof-10}

\section{Background in parameterized complexity}
\label{sec:p-background}
\input{p-background}



\section{Proof of Proposition~\ref{prp:mlpt}}
\label{sec:proof-11}
\input{proof-11}


\section{Proof of Proposition~\ref{prp:result-layers}}
\label{sec:proof-12}
\input{proof-12}


2020-10-26T01:14:43.000
2010
2010.12265
en
https://arxiv.org/abs/2010.12265
In spite of several claims stating that some models are more interpretable than others -- e.g., "linear models are more interpretable than deep neural networks" -- we still lack a principled notion of interpretability to formally compare among different classes of models. We make a step towards such a notion by studying whether folklore interpretability claims have a correlate in terms of computational complexity theory. We focus on local post-hoc explainability queries that, intuitively, attempt to answer why individual inputs are classified in a certain way by a given model. In a nutshell, we say that a class $\mathcal{C}_1$ of models is more interpretable than another class $\mathcal{C}_2$, if the computational complexity of answering post-hoc queries for models in $\mathcal{C}_2$ is higher than for those in $\mathcal{C}_1$. We prove that this notion provides a good theoretical counterpart to current beliefs on the interpretability of models; in particular, we show that under our definition and assuming standard complexity-theoretical assumptions (such as P$\neq$NP), both linear and tree-based models are strictly more interpretable than neural networks. Our complexity analysis, however, does not provide a clear-cut difference between linear and tree-based models, as we obtain different results depending on the particular post-hoc explanations considered. Finally, by applying a finer complexity analysis based on parameterized complexity, we are able to prove a theoretical result suggesting that shallow neural networks are more interpretable than deeper ones.
Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Machine Learning (cs.LG)
Model Interpretability through the Lens of Computational Complexity
Qwen/Qwen-72B
1. YES
2. YES