# Explanations for Neural Networks by Neural Networks
## 3 \(\mathcal{I}\)-Nets for Sparse Polynomials  
When choosing a function family for the generated explanations, a trade-off between performance and interpretability has to be considered. While functions that are too simple might not be able to approximate the network function well, a function that is too complex might not improve the interpretability. Here, we introduce a specific instance of \(\mathcal{I}\)-Nets, where \(g\) is a sparse polynomial. Within this approach, the user can adjust the level of complexity themself by defining the maximum degree \(d\) of the polynomial and the number of monomials (i.e., the sparsity) \(s\). As usual, we consider a polynomial to be a multivariate function  
\[g(x_{1},\ldots,x_{n})=\sum_{i=1}^{s}c^{(i)}\prod_{j=1}^{n}x_{j}^{d^{(i)}},\]  
where \(d^{(i,j)}\) is the exponent of variable \(j\) in monomial \(i\), and \(s\) is the number of monomials. With an increasing number of variables and a higher degree of the polynomial, the number of possible monomial terms expands rapidly and is calculated as \(\binom{n+d}{d}\), where \(d\) is the degree and \(n\) the number of variables. Therefore, a cubic, bivariate polynomial has \(\binom{2+3}{3}=10\) possible coefficients, each belonging to one of the following monomials:  
\( \begin{array}{ll}0.&x_{0}^{3}x_{1}^{0}=x_{0}^{3}\\ 1.&x_{0}^{2}x_{1}^{1}=x_{0}^{2}x_{1}\\ 2.&x_{0}^{3}x_{1}^{0}=x_{0}^{2}\\ 3.&x_{0}^{4}x_{1}^{1}=x_{0}x_{1}^{2}\\ 4.&x_{0}^{4}x_{1}^{1}=x_{0}x_{1}\\ 5.&x_{0}^{4}x_{1}^{1}=x_{0}\\ 6.&x_{0}^{4}x_{1}^{1}=x_{1}^{3}\\ 7.&x_{0}^{4}x_{1}^{1}=x_{1}^{2}\\ 8.&x_{0}^{4}x_{1}^{1}=x_{1}\\ 9.&x_{0}^{4}x_{1}^{0}=1\end{array} \)  
Accordingly, it is straightforward to represent the bivariate, cubic polynomial \(g(x_{0},x_{1})=3x_{0}^{3}+x_{0}^{1}-5x_{0}x_{1}^{2}-3x_{1}-4\) as a vector \(\theta_{g}^{\prime}\) of the coefficients, according to the encoding in Figure 2a. The order of the elements in \(\theta_{g}^{\prime}\) is sorted by the enumeration of monomials shown above. It is easy to see that such a systematic evaluation of monomials exists for all \(n\) and \(d\). In this paper, we are concerned with _sparse_ polynomials, where only a small number of monomials have nonzero coefficients. The reason for focusing on sparse polynomials is twofold. First, we are concerned with _explanations_ that can be inspected and interpreted by humans. Although there is no universal agreement about what constitutes an interpretable representation [9], we follow [PERSON] et al. [2] who use model complexity as a proxy for interpretability. Thus, we argue that the number of monomials has to be relatively small to serve as a useful and human-understandable representation. Secondly, constraining the number of monomials is a form of regularization, preventing overfitting. For sparse polynomials, the representation in Figure 2a is very inefficient, especially for an increasing number of variables and degree. For instance, assuming we want to represent a cubic polynomial with 10 variables, we would need a vector \(\theta_{g}^{\prime}\) of length \(\binom{10+3}{3}=286\), even if just a small number of monomials has non-zero coefficients. Additionally, it is difficult for a neural network to predict zero coefficients when using this representation, since linear outputs are not tailored towards predicting a value of 0. This would eventually result in dense polynomials with many small coefficients, which precludes interpretability. Thus, to efficiently represent and predict sparse polynomials, we define an alternative representation, comprising the coefficient values along with the corresponding monomial indices. This way, the function \(g(x_{0},x_{1})=3x_{0}^{3}+x_{0}^{1}-5x_{0}x_{1}^{2}-3x_{1}-4\) can be represented as the vector \(\theta_{g}\), shown in Figure 2b. Within \(\theta_{g}\), the first \(s\) entries represent the coefficients and the second \(s\) entries represent the corresponding monomial indices in the systematic  
Figure 2: Polynomial representations: Comparison of dense and sparse polynomial representations for an exemplary polynomial.