# Invertible Convolution with Symmetric Paddings

Bo Li
<EMAIL_ADDRESS>
###### Abstract

We show that symmetrically padded convolution can be analytically inverted via
DFT. We comprehensively analyze several different symmetric and anti-symmetric
padding modes and show that multiple cases exist where the inversion can be
achieved. The implementation is available at
https://github.com/prclibo/iconv_dft.

##  1 Introduction

Convolutional Neural Network (CNN) has achieved incredible success in computer
vision. It is shown to be effective in building transformation between the
highly complex distribution of image data domain to a latent feature domain
distribution that is easy to conduct tasks like classification or generation.
Recent studies have shown that there exist CNN operators that are invertible.
This makes it possible to build bidirectional transformation between the image
data domain and the latent feature domain. Such transformation is recognized
to be valuable in unifying the formulation of generative and discriminative
tasks and provides potential insights in revealing the interior process of
CNNs.

A plenty of research has been conducted in the past decades in designing
invertible CNN operators. As in Section 2, these works mainly focuses two
directions: 1) designing CNN operators with special structures that can be
analytically inverted; 2) constraining CNN training so that the network can be
numerically inverted. Besides these two approaches, it is known but less
studied that the vanilla convolution structure is analytically invertible if
satisfying very simple conditions. One typical example is that circularly-
padded convolution with equal input and output channels [3]. Compared with
other approaches, such structure provides most similar structural and
behavioral analogy to conventional CNN and supports analytical inversion.

We noticed that a disadvantage of the circular convolution is that circular
padding violates the spatial locality of CNN and might confuse the training of
the high layers whose input feature map sizes are small. A latter research
suggests that convolution with symmetric padding and symmetric kernel is also
invertible. However, existing study on the symmetric padding case is still
limited and only focuses on the simplest case. In this paper, we provide a
comprehensive study on the invertibility of symmetric padded convolution. We
show that multiple invertible convolution operators exist with different
combination of the symmetric padding modes of the input and the kernel. With
our analysis we are able to convert conventional a CNN network to its
invertible counterpart with only very small modification of structure and
efficiently compute analytical inversion with DFT.

##  2 Related Works

Normalizing flows design several special convolution operators to allow
inversion computation. These approaches are able to exactly compute likelihood
of the data and have attracted wide attention in recent research.
Representative works of normalizing flows include NICE, RealNVP and Glow.
These works replace conventional convolution layer with the specifically
designed coupling layers that are analytically invertible. Compared with
conventional convolution layers, the coupling layers are less flexible as the
its convolution is only applied on half on the input features. To increase
flexibility, a $1\times 1$ invertible convolution is appended to a coupling
layer. A variety of works have been proposed to further extend the methodology
of normalizing flow. For example, [7, 2, 5] make use of extra noise to augment
the feature space and increase capacity. [5] also enhances the performance by
introducing more complex layer connection.

The invertibility can also be achieved if the convolution follows certain
auto-regressive formulation. [6] replace a conventional convolution kernel
with an auto-regressive variant which only operates the prefix pixels at a
given position. [10] improves auto-regressive kernels to by rotating masked
kernels and claims better efficiency. These design is also shown to be
effective in constructing normalizing flows.

Coupling layers and auto-regressive structures both modifies conventional
convolutions. Recently there also have been some study on the invertibility of
conventional convolutions. By interpreting convolution in the DFT domain, it
is early known that convolution can be inverted by division in the frequency
domain. [8, 3] discuss this property in the circularly padded convolution. [9]
explores a simple case of symmetric padding which could enable invertible
convolution.

Besides the above analytical approach to invert a convolution operation.
Various works have studied to invert CNN in a numerical manner. [1] is a
representative work which makes use of fixed-point iteration approach to
numerically solve the network input from the output. [4] does not directly
invert a CNN network from a given output, but makes it possible to draw
samples from the input image domain given a energy-based network.

Although invertible networks have attracted wide-spread interest in machine
learning research in the past decades, it has to be admitted that the
performance of invertible networks is still disadvantageous compared to
conventional discriminative and generative models. More theoretical
development is still required to push the understanding of invertible networks
and the bidirectional relationship between image data domain and the latent
feature domain. The derivation in this paper is a further development to the
study of [8, 9, 3].

##  3 Methodologies

###  3.1 Preliminaries

In the derivation of this section, we first consider 1D signal cases for
simplicity and then extend it to 2D cases. Define
$\mathbf{x}=x_{0},x_{1},\dots,x_{N-1}$ as a 1D discrete signal of length $N$
and $\mathbf{X}=X_{0},X_{1},\dots,X_{N-1}$ as its DFT as

$\mathbf{X}=\mathcal{F}(\mathbf{x}),\quad
X_{k}=\sum_{n=0}^{N-1}x_{n}\cdot\exp(-\frac{i2\pi}{N}kn).$ (1)

Obviously, the convolution operation between a kernel $\mathbf{w}$ and
$\mathbf{x}$ with circular padding corresponds to multiplication in the
frequency domain of $\mathbf{X}$ and the DFT $\mathbf{W}$ of $\mathbf{w}$:

$\mathbf{y}=\mathsf{circular\\_conv}(\mathbf{w},\mathbf{x})\longleftrightarrow\mathbf{Y}=\mathbf{W}\circ\mathbf{X},$
(2)

where $y$ is the output signal and $Y$ is its DFT.

###  3.2 Invertibility of Circularly Padded Convolution

One can recover $\mathbf{y}$ from $\mathbf{x}$ and $\mathbf{w}$ via the
Fourier domain by

$\mathbf{X}=\mathsf{element\\_inverse}(\mathbf{W})\circ\mathbf{Y}.$ (3)

In practical computer vision models, $\mathbf{w}$ and $\mathbf{W}$ are 4D
tensors with dimensions of height, width, input channels and output channels.
$\mathsf{element\\_inverse}$ denotes element-wise matrix inversion on each
matrix element in $\mathbf{W}$ with the dimensions of input channels and
output channels. Two conditions are required for this inversion.

  1. 1.

$\mathbf{W}$ elements are invertible, i.e., input and output channels equal
and the element matrices are non-singular.

  2. 2.

$\mathbf{x}$ and $\mathbf{y}$ should be fully known, i.e., if $\mathbf{x}$ is
padded, values in $\mathbf{y}$ that corresponds to the padding area can be
inferred.

In the practice of deep learning, if a signal is arbitrarily padded, the
output feature map is actually a crop of the convolved padded signal. Without
knowing the cropped area of the output feature map, it is generally not
possible to compute $\mathbf{Y}$.

One special case is the circular padded convolution. In this cases, the
cropped area of the output feature map is periodical repeat of the output
feature map. Thus $\mathbf{Y}$ can be directly obtained as the DFT of the
output feature map.

We next show that besides circular padding, there exist multiple symmetric
padding modes that also support the inversion of convolution from the output
feature maps.

###  3.3 Symmetric Padding

HSHSWSWSZSZSHAHAWAWA Figure 1: 1D Illustration of several symmetric padding
modes mentioned in this paper. The black dots denotes a 1D discrete original
signal whose length is $N=4$. Empty circles denotes the reflection of the
original signal in the padding area. Gray dots denots extra added data samples
to achieve some required properties on the padded signal, c.f. Section 3.3.
Note that the signal is periodical and the left padding is wrapped to the
right side.

As in [11], 4 different padding modes exist for symmetric padding, namely
half-sample symmetry (HS), whole-sample symmetry (WS), half-sample anti-
symmetry (HA) and whole-sample anti-symmetry (WA).

Fig. 1 shows an example of the 4 padding modes in a 1D signal case. HS
reflects the whole signal. WS keeps the boundary point as the axis of symmetry
and reflect the rest of the signal. HA rotates the signal $180^{\circ}$ around
a half-sample at the boundary. WA rotates the signal $180^{\circ}$ around an
extra zero sample next to the signal boundary.

For simplicity, we assume that all sides of an image input are always padded
in the same mode. A 1D signal that is padded in HS mode on both sides is
denoted as padded in HSHS mode. We denote the padded signal as
$\mathsf{HS}(\mathbf{x})$ and its DFT as $\mathbf{X}^{\mathsf{HS}}$. Similar
notation goes with other padding modes. Symmetric padding flip the signal and
append it to the origin one. We reveal several properties of symmetrically
padded signals.

  * •

In our case where the padding modes are the same on both sides, $N$ of the
padded signal is always even.

  * •

$\mathsf{WA}(\mathbf{x})$ and $\mathsf{HA}(\mathbf{x})$ have zero summation,
i.e., $X^{\mathsf{WA}}_{0}=\sum_{n}x^{\mathsf{WA}}_{n}=0$ and
$X^{\mathsf{HA}}_{0}=\sum_{n}x^{\mathsf{HA}}_{n}=0$.

  * •

$\mathsf{HS}(\mathbf{x})$ and $\mathsf{WA}(\mathbf{x})$ satisfies
$X^{\mathsf{HS}}_{N/2}=\sum_{n}(-1)^{n}x^{\mathsf{HS}}_{n}=0$ and
$X^{\mathsf{WA}}_{N/2}=\sum_{n}(-1)^{n}x^{\mathsf{WA}}=0$.

For an original signal with even length $N$, we further define an extra
padding mode zero-summed padding (ZSZS). For a signal $x$, we reflect the
signal and put extra samples of $2\sum_{n=0}^{N/2}x_{2n}$ and
$2\sum_{n=0}^{N/2}x_{2n+1}$ respectively on the two sides between the origin
and reflected signal. Obviously,

  * •

ZSZS is a special case of WSWS. ZSZS pads the signal similarly on its two
sides, i.e., by adding an extra sample.

  * •

Signals padded in ZSZS have zero summation ($X_{0}$).

  * •

In addition, substituting into (1) reveals that the ZSZS-padded signal also
satisfies $X_{N/2}=0$.

We next give a rough illustration on the invertibility of the symmetrically
padded convolution.

| $x$ | $X_{0}$ | $X_{N/2}$ | $w$ | $W_{0}$ | $W_{N/2}$ | $y$ | $Y_{0}$ | $Y_{N/2}$ | Inv
---|---|---|---|---|---|---|---|---|---|---
1 | HAHA | $0$ | $*$ | WSWS | $*$ | $*$ | HAHA | $0$ | $*$ | ✓
2 | WAWA | $0$ | $0$ | WSWS | $*$ | $*$ | WAWA | $0$ | $0$ | ✓
3 | HSHS | $*$ | $0$ | WSWS | $*$ | $*$ | HSHS | $*$ | $0$ | ✓
4 | WSWS | $*$ | $*$ | WSWS | $*$ | $*$ | WSWS | $*$ | $*$ | ✓
5 | ZSZS | $0$ | $0$ | WSWS | $*$ | $*$ | ZSZS | $0$ | $0$ | ✓
6 | HAHA | $0$ | $*$ | HSHS | $*$ | $0$ | WAWA | $0$ | $0$ |
7 | WAWA | $0$ | $0$ | HSHS | $*$ | $0$ | HAHA | $0$ | $0$ |
8 | HSHS | $*$ | $0$ | HSHS | $*$ | $0$ | WSWS | $*$ | $0$ |
9 | WSWS | $*$ | $*$ | HSHS | $*$ | $0$ | HSHS | $*$ | $0$ |
10 | ZSZS | $0$ | $0$ | HSHS | $*$ | $0$ | HSHS | $0$ | $0$ |
11 | HAHA | $0$ | $*$ | WAWA | $0$ | $0$ | HSHS | $0$ | $0$ |
12 | WAWA | $0$ | $0$ | WAWA | $0$ | $0$ | ZSZS | $0$ | $0$ | ✓
13 | HSHS | $*$ | $0$ | WAWA | $0$ | $0$ | HAHA | $0$ | $0$ |
14 | WSWS | $*$ | $*$ | WAWA | $0$ | $0$ | WAWA | $0$ | $0$ |
15 | ZSZS | $0$ | $0$ | WAWA | $0$ | $0$ | WAWA | $0$ | $0$ | ✓
16 | HAHA | $0$ | $*$ | HAHA | $0$ | $*$ | WSWS | $0$ | $*$ |
17 | WAWA | $0$ | $0$ | HAHA | $0$ | $*$ | HSHS | $0$ | $0$ |
18 | HSHS | $*$ | $0$ | HAHA | $0$ | $*$ | WAWA | $0$ | $0$ |
19 | WSWS | $*$ | $*$ | HAHA | $0$ | $*$ | HAHA | $0$ | $*$ |
20 | ZSZS | $0$ | $0$ | HAHA | $0$ | $*$ | HAHA | $0$ | $0$ |
Table 1: Padding mode transition in symmetrically padded convolution

###  3.4 Invertibility

We restrict our discussion for original signals with even length $N$ since we
will make use of the ZSZS mode to help analyze the transition relationship of
padding modes in convolution. This condition is feasible in computer vision
since images are usually of even sizes.

We consider (2) and study the padding mode of $\mathbf{Y}$ when $\mathbf{X}$
and $\mathbf{W}$ is symmetrically padded. The transition of the padding modes
are listed in Table 1.

  * •

We start from an example with $\mathsf{WS}(\mathbf{x})$, and
$\mathsf{WS}(\mathbf{w})$. It is easy to derive that the output is WSWS-
padded. Given an arbitrary output feature map $\mathbf{y}$, we can pad it as
$\mathsf{WS}(\mathbf{y})$ and obtain $\mathsf{WS}(\mathbf{x})$ via (3). Since
$\mathbf{W}^{\mathsf{WS}}$ is non-zero in general, the inversion is valid.
Same inversion can also be achieved for $\mathbf{x}$ padded in other modes
with $\mathsf{WS}(\mathbf{w})$.

  * •

For the case of $\mathsf{WA}(\mathbf{x})$ and $\mathsf{WA}(\mathbf{w})$, we
get $W^{\mathsf{WA}}_{0}\equiv W^{\mathsf{WA}}_{N/2}\equiv 0$, which make it
ill-posed to recover $X^{\mathsf{WA}}_{0}$ and $X^{\mathsf{WA}}_{N/2}$ from
the output. Fortunately, based on the property of $\mathsf{WA}(x)$ we priorly
know that $X^{\mathsf{WA}}_{N/2}\equiv X^{\mathsf{WA}}_{0}\equiv 0$. In
addition, it can be derived that the output of the padded convolution in this
case is always ZSZS and this form can be obtained by padding arbitrary
$\mathbf{y}$ signal. Thus we are able to recover $\mathbf{x}$ from arbitrary
output feature $\mathbf{y}$

  * •

For the case of $\mathsf{WA}(\mathbf{x})$ and $\mathsf{HS}(\mathbf{w})$, we
get $\mathsf{HA}(\mathbf{y})$ as output with
$Y^{\mathsf{HA}}_{0}=Y^{\mathsf{HA}}_{N/2}=0$. However, this does not always
hold for arbitrary $\mathsf{HA}(\mathbf{y})$. Thus we cannot recover
$\mathbf{x}$ from arbitrary $\mathbf{y}$.

  * •

For the case of $\mathsf{WS}(\mathbf{x})$ and $\mathsf{HS}(\mathbf{w})$, the
inversion is invalid since $W_{N/2}=0$ and $X_{N/2}\neq 0$, making it ill-
posed to recover $X_{N/2}$.

###  3.5 Invertible Convolution

With the above derivation, we discover multiple forms of invertible
convolution with symmetric padding for 1D signals. Different from [9] where
$\mathbf{w}$ is restricted to be symmetric, we show that anti-symmetric
$\mathbf{w}$ can also be used to form invertible convolution.

Alg. 1 and 2 shows the pseudo-code of the forward and inverse pass of the
proposed invertible convolution. In practice, when defining such invertible
convolution, one selects the padding modes for input $\mathbf{x}$ and
$\mathbf{w}$ from Table 1 and pads the signals according to Fig. 1. In the
forward pass, we implement the symmetrically padded convolution as an
equivalent form of circularly padded convolution on symmetrically padded
signals. The circularly padded convolution is generally accessible in modern
deep learning frameworks and supports automatic gradient computation. In the
inverse pass, we implement (3). Note that $\mathbf{w}$ should also be padded
to have the same size with $\mathbf{x}$ so that their DFT can be properly
computed. In deep learning training frameworks, $\mathbf{w}$ is denoted as a
small parameter tensor. We first pad $\mathbf{w}$ in the selected padding mode
and then resized the padded kernel by filling $0$ to the intended size. The
resized kernel has the same padding mode as required.

Input: $\mathbf{x}$, $\mathbf{w}$,
$\mathsf{x\\_pad}\in\\{\mathsf{WS},\mathsf{WA},\mathsf{HS},\mathsf{HA},\mathsf{ZS}\\}$,
$\mathsf{w\\_pad}\in\\{\mathsf{WS},\mathsf{WA}\\}$

Output: $\mathbf{y}$, $\mathsf{y\\_pad}$

1

2Determine $\mathsf{y\\_pad}$ via Table 1;

3

4$\mathbf{y}^{\prime}\leftarrow\mathsf{circular\\_conv}(\mathsf{x\\_pad}(\mathbf{x}),\mathsf{w\\_pad}(\mathbf{w}))$;

$\mathbf{y}\leftarrow\mathsf{y\\_pad}^{-1}(\mathbf{y}^{\prime})$

Algorithm 1 Forward pass of invertible symmetrically padded convolution

Input: $\mathbf{y}$, $\mathbf{w}$,
$\mathsf{y\\_pad}\in\\{\mathsf{WS},\mathsf{WA},\mathsf{HS},\mathsf{HA},\mathsf{ZS}\\}$,
$\mathsf{w\\_pad}\in\\{\mathsf{WS},\mathsf{WA}\\}$

Output: $\mathbf{y}$, $\mathsf{y\\_pad}$

1

2Determine $\mathsf{x\\_pad}$ via Table 1;

3
$\mathbf{Y}^{\mathsf{y\\_pad}}\leftarrow\mathcal{F}(\mathsf{y\\_pad}(\mathbf{y}))$,
$\mathbf{W}^{\mathsf{w\\_pad}}\leftarrow\mathcal{F}(\mathsf{w\\_pad}(\mathbf{w}))$;

4

5$\mathbf{X}^{\mathsf{x\\_pad}}\leftarrow\mathsf{element\\_inverse}(\mathbf{W}^{\mathsf{w\\_pad}})\circ\mathbf{X}^{\mathsf{x\\_pad}}$;

6
$\mathbf{x}^{\prime}\leftarrow\mathcal{F}^{-1}(\mathbf{X}^{\mathsf{x\\_pad}})$;

$\mathbf{x}\leftarrow\mathsf{x\\_pad}^{-1}(\mathbf{x}^{\prime})$

Algorithm 2 Inverse pass of invertible symmetrically padded convolution

The symmetric padding in [9] is a special case of Table 1 (row #4) with
$\mathbf{x}$ and $\mathbf{w}$ both padded as WSWS. A padded kernel
$\mathsf{WS}(\mathbf{w})$ can be interpreted as a kernel with restricted
degree of freedom, i.e., the symmetric points must have equal values. This
restricts the flexibliity of the kernel and make it impossible to learn the
anti-symmetric components in a kernel. To increase the capacity to learn anti-
symmetric kernels, we can additionally extend the symmetrically padded
convolution with parallel anti-symmetrically padded convolution (row #12 or
#15).

The extension of Table 1 is a nature in that the padding modes of the two
dimensions follows the 1D transition relationship independently. Take row #4
and #12 as two selected modes for symmetric and anti-symmetric padding. There
exist 4 different combinations for the 2D padding modes. Note that by
decomposing symmetrically and anti-symmetrically on two dimensions, a 2D
signal can be decomposed into 4 components. These components corresponds to
the 4 padding modes respectively.

##  4 Implementation

###  4.1 Implementation Details

In the implementation of the conventional convolution, a kernel is expressed
as a small (e.g., $3\times 3$) learnable patch. To enable (2), we need to pad
and resize a kernel $\mathbf{w}$ to the same size as the input signal
$\mathbf{x}$. In our implementation, we convert a conventional $\mathbf{w}$ to
$\mathbf{w}+\mathsf{flip}(\mathbf{w})$ for the symmetric case and
$\mathbf{w}-\mathsf{flip}(\mathbf{w})$ for the anti-symmetric case to achieve
a equivalently padded kernel. This new kernel can be then fed to the
conventional convolution operator to realize our proposed invertible
convolution.

###  4.2 Source code

The PyTorch source code can be accessed at
https://github.com/prclibo/iconv_dft.

###  4.3 Numerical Stability

We notice that when stacking multiple invertible layers as a network, the
numerical error of the inverse pass is accumulated. Executing the computation
in double precision helps alleviate the numerical error.

##  5 Conclusions

We comprehensively analyze several different symmetric and anti-symmetric
padding modes for the convolution operation and show that multiple cases exist
where the convolution can be inverted. We consider this derivation as a
contribution to the research of invertible networks and generative models.

##  6 Acknowledgement

Appreciation goes to Marc Finzi for his kind help in this research.

## References

  * [1] Jens Behrmann, Will Grathwohl, Ricky TQ Chen, David Duvenaud, and Jörn-Henrik Jacobsen.  Invertible residual networks.  In International Conference on Machine Learning, pages 573–582. PMLR, 2019.
  * [2] Jianfei Chen, Cheng Lu, Biqi Chenli, Jun Zhu, and Tian Tian.  Vflow: More expressive generative flows with variational data augmentation.  In International Conference on Machine Learning, pages 1660–1669. PMLR, 2020.
  * [3] Marc Finzi, Pavel Izmailov, Wesley Maddox, Polina Kirichenko, and Andrew Gordon Wilson.  Invertible convolutional networks.  In Workshop on Invertible Neural Nets and Normalizing Flows, International Conference on Machine Learning, volume 2, 2019.
  * [4] Will Grathwohl, Kuan-Chieh Wang, Jörn-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky.  Your classifier is secretly an energy based model and you should treat it like one.  arXiv preprint arXiv:1912.03263, 2019.
  * [5] Matej Grcić, Ivan Grubišić, and Siniša Šegvić.  Densely connected normalizing flows.  Advances in Neural Information Processing Systems, 34:23968–23982, 2021.
  * [6] Emiel Hoogeboom, Rianne Van Den Berg, and Max Welling.  Emerging convolutions for generative normalizing flows.  In International Conference on Machine Learning, pages 2771–2780. PMLR, 2019.
  * [7] Chin-Wei Huang, Laurent Dinh, and Aaron Courville.  Augmented normalizing flows: Bridging the gap between generative flows and latent variable models.  arXiv preprint arXiv:2002.07101, 2020.
  * [8] Mahdi Karami, Laurent Dinh, Daniel Duckworth, Jascha Sohl-Dickstein, and Dale Schuurmans.  Generative convolutional flow for density estimation.  In Workshop on Bayesian Deep Learning NeurIPS 2018. Curran Associates, Inc., Red Hook, NY, 2018.
  * [9] Mahdi Karami, Dale Schuurmans, Jascha Sohl-Dickstein, Laurent Dinh, and Daniel Duckworth.  Symmetric convolutional flow.  In Workshop on Invertible Neural Nets and Normalizing Flows (INNF), ICML, 2019.
  * [10] Xuezhe Ma, Xiang Kong, Shanghang Zhang, and Eduard Hovy.  Macow: Masked convolutional generative flow.  Advances in Neural Information Processing Systems, 32, 2019.
  * [11] Stephen A Martucci.  Symmetric convolution and the discrete sine and cosine transforms.  IEEE Transactions on Signal Processing, 42(5):1038–1051, 1994.


11institutetext:  National Trusted Embedded Software Engineering Technology
Research Center, East China Normal University, China 22institutetext: Griffith
University, Australia 33institutetext: National University of Singapore,
Singapore

# Extracting Optimal Explanations for Ensemble Trees via Logical Reasoning

Gelin Zhang 11 Zhé Hóu 22 Yanhong Huang 11 Jianqi Shi 11 Hadrien Bride 22 Jin
Song Dong 2233 Yongsheng Gao 22

###### Abstract

Ensemble trees are a popular machine learning model which often yields high
prediction performance when analysing structured data. Although individual
small decision trees are deemed explainable by nature, an ensemble of large
trees is often difficult to understand. In this work, we propose an approach
called optimised explanation (OptExplain) that faithfully extracts global
explanations of ensemble trees using a combination of logical reasoning,
sampling and optimisation. Building on top of this, we propose a method called
the profile of equivalent classes (ProClass), which uses MAX-SAT to simplify
the explanation even further111The code is available at
https://github.com/GreeenZhang/OptExplain.. Our experimental study on several
datasets shows that our approach can provide high-quality explanations to
large ensemble trees models, and it betters recent top-performers.

###### Keywords:

Explainable Artificial Intelligence (XAI) Random Forest Classification Rule
Extraction.

##  1 Introduction

#### Background.

Ensemble trees are a family of machine learning techniques that combine
individual decision trees to form a better prediction model. Examples include
random forest [14, 2], which combines strong learners (e.g., large trees) to
reduce variance and avoid overfitting. Boosting [7, 9], on the other hand,
combines weak learners (e.g., small trees) to reduce bias. Ensemble trees are
very successful in today’s data analytics competitions and applications; they
are especially suited to analyse _structured data_ such as databases and
spreadsheets, where they sometimes outperform deep learning [20].

Although decision trees are often deemed an explainable, or even a “white-box”
model, such an impression usually refers to a single, short decision tree. In
the context of ensemble trees such as the models generated by random forest or
boosting, there can be a large number of trees and each tree can be gigantic.
For example, to achieve a 0.76+ area-under-the-curve (AUC) for the 1 million
flight dataset [20], Silas [3, 15] trains a model of 100 trees and each tree
has more than 32,000 branches. Such a model certainly does not manifest itself
in an explainable manner to the general user. The main goal of this work is to
extract faithful explanations for such large-scale models.

There are several existing methods for analysing and interpreting machine
learning models. For example, the LIME tool [22] and the SHAP values [16] are
both promising techniques for solving this problem. We will discuss more
details of related work in Section 5. However, most existing work is done from
a statistics perspective. Such methods use a prediction model as a black-box
and attempt to find statistical (e.g., linear) approximations of the model. By
contrast, our philosophy is that we should analyse the internal working of the
model and obtain an understanding of how it works logically. Further, many
existing techniques are focused on _local explanations_ , that is, how the
model predicts for a particular data instance. This work is primarily about
_global explanations_ , which explains how the model behaves generally. Part
of the reasons why we choose ensemble trees is that decision trees are no
strangers to logicians. For example, binary decision diagrams, which have a
similar form, are widely used in theorem proving [10] and model checking [25].
The tree structure is well-understood in the logic and verification community,
and there are many possibilities to apply logical reasoning to analysing
ensemble trees.

#### Our approach.

In our previous work [15], we have used sampling and maximum satisfiable
subset to extract the decision logic of the model. However, it is non-trivial
to manually adjust the sampling parameters, which may lead to vastly different
explanations. Default parameters often lead to very simple explanations that
diverge from the original model. In this paper, we propose an integrated and
automated framework for providing global explanations. Moreover, our goal is
not just to give _an_ explanation as is done in the literature, but to give
_the optimal_ explanation in terms of _simplicity_ and _faithfulness_.

An outline of our approach follows: we extract logical formulae from a set of
trees where each branch forms a “decision rule”. We then reduce the size of
the model by filtering out low-quality nodes (i.e., sub-formulae) and
branches. We also devise a customised formulae simplification algorithm to
obtain logically equivalent smaller models. In case there are still too many
decision rules, we group the rules into “equivalent classes” to further
abstract the model. The parameters in the above process are optimised using
particle swarm towards a sweet spot of simplicity and faithfulness. As an
extra step, we can simplify the explanation using MAX-SAT to obtain even more
abstract representations of each equivalent class, which we call the “profiles
of classes”. Such profiles can provide straightforward and even visual
explanations of the model.

The utilities of this work are manifold. First, our approach can provide
human-understandable explanations that are very close to the original ensemble
trees model in predictive behaviour. Second, such an explanation can also be
used as an approximation of the original model. For example, verification of
machine learning models is another popular topic, but a general sound and
complete verification algorithm for ensemble trees have proven impractical
[26]. As a step back, we can look at the software testing scenario: since the
explanation mimics the behaviour of the original model, if it violates a
property, then it is likely that the original model would fail the
verification, too. In such cases, we can use the explanation to constrain the
search space when finding counterexamples. Finally, this work can serve as a
stepping stone towards explaining deep learning. There are existing methods
for converting neural networks to decision trees [13] exactly for explanation
purposes. However, these methods only induce a single decision tree, whose
predictive performance is incomparable to the deep learning model. One may
convert neural networks to a set of decision trees instead, then this work can
be directly applied to obtain explanations.

#### Contributions.

The main contributions of this paper are as follows:

  1. 1.

We formalise ensemble trees into logical formulae and develop simplification
and abstraction algorithms that are specialised for machine learning.

  2. 2.

We propose an automated explanation extraction method called _OptExplain_ ,
which combines logical reasoning, sampling, and bio-inspired optimisation.

  3. 3.

We also develop a method called _ProClass_ that computes the abstractions of
each (equivalent) class using MAX-SAT.

  4. 4.

Through case studies and experiment, we show that our method is practical and
useful on different datasets. It also outperforms similar tools.

The remainder of this paper is organised as follows: Section 2 describes the
preliminary concepts, Section 3 details the proposed approach, Section 4 gives
case studies and experiment, Section 5 discusses related work, and Section 6
concludes the paper.

##  2 Preliminaries

In this section, we redefine decision trees and their ensembles from a logical
language point of view.

###  2.1 Decision Trees With a Logical Foundation

$F_{1}$$F_{2}$(0,6)(2,1)(3,1)falsefalsetruetrue Figure 1: An example decision
tree.

In supervised learning, a structured dataset for classification is defined as
set of _instances_ of the form $(\vec{x},y)$ where
$\vec{x}=[x_{1},...,x_{n}]$, $n\in\mathbb{N}$, is an input vector called
_features_ and $y$ is an outcome value often called the _label_. We denote by
$X$ the feature space and $Y$ the outcome space.

A _decision tree_ is composed of internal nodes (diamonds in Fig. 1) and
terminal nodes called leaves (ovals in Fig. 1). Each internal node is
associated with a logical formula over a feature. Each leaf node contains a
set of instances, which yield a _vote distribution_ of the form
$(n_{1},\cdots,n_{m})$ where $m$ is the number of classes and $n_{i}$ ($1\leq
i\leq m$) is the number of instances of the corresponding class. For example,
in Fig. 1, the leftmost leaf node $(0,6)$ indicates that there are $0$ class0
instances and $6$ class1 instances. Without loss of generality, we focus on
binary trees, in which internal nodes have two successors respectively called
the left and right child nodes. By convention, the instances that satisfy the
logical formula of an internal node go to the right child node, and those that
do not satisfy go to the left child node. For example, in Fig. 1, let $I$ be
the set of training instances associated with the root node, $I_{1}\subset I$
be the subset that satisfies the formula $F_{1}$, then $I_{1}$ will be the set
of instances associated with the right child node (with formula $F_{2}$), and
$I_{2}=I\setminus I_{1}$ will be the set of instances associated with the left
child (leaf) node.

Given a decision tree, any input vector (or instance) is associated with a
single leaf. A decision tree is, therefore, a compact representation of a
function of the form $t:X\to\mathbb{N}^{m}$, where $m$ is the number of
classes. The output of a decision tree is a distribution of _votes_ for each
class. To obtain an outcome in $Y$, we take the class with the most votes.

###  2.2 Ensemble of Decision Trees

We adopt the definitions of Cui et al. [4]. Let an ensemble be a set of
decision trees of size $T$. It gives the weighted sum of the trees as follows:

$E(x)=\sum_{i=1}^{T}w_{i}\cdot t_{i}(x)$ (1)

where $E$ is the function for the ensemble, $w_{i}$ and $t_{i}$ are
respectively the weight and function for each tree. The summation aggregates
the weighted votes from each tree and obtains the final votes for each class.
Thus, the ensemble is also a function of the signature $E:X\to\mathbb{N}^{m}$
and requires a voting mechanism to obtain the outcome. We give some famous
examples of ensemble trees below.

#### Bagging.

Each decision tree is trained using a subset of the dataset that is sampled
uniformly with replacement. The remaining instances form the out-of-bag (OOB)
set. When selecting the best formula at each decision node in a tree, only a
subset of the features are considered. This is commonly found in algorithms
such as Random Forest [2]. Bagging grows large trees with low bias and the
ensemble reduces variance.

#### Boosting.

Boosting trains weak learners, i.e., small trees, iteratively as follows:

$E_{i+1}(x)=E_{i}(x)+\alpha_{i}\cdot t_{i}(x)$ (2)

where $t_{i}$ is the weak leaner trained at iteration $i$ and $\alpha_{i}$ is
its weight. The final ensemble is thus a special case of $E(x)$ above where
$w_{i}$ is $\alpha_{i}$. The ensemble reduces bias.

AdaBoost [7] focuses on training instances that are misclassified in the
previous iteration by optimising $\alpha_{i}$ and $t_{i}$ in the formula
below:

$\operatorname*{minimise}_{\alpha_{i},t_{i}}\sum_{j=0}^{N}L(y^{(j)},E_{i}(x^{(j)})+\alpha_{i}\cdot
t_{i}(x^{(j)}))$ (3)

where $L$ is a loss function measuring the difference between the actual
outcome $y^{(j)}$ of instance $j$ and $E_{i+1}(x^{(j)})$. AdaBoost often uses
exponential loss $L(a,b)=e^{-a\cdot b}$ in which case the weak learners are
trained by weighted instances.

Gradient Boosting [8] is a generalisation of the above minimisation where each
tree is trained using

$t_{i}(x^{(j)})\approx-\frac{\partial L(y^{(j)},E_{i}(x^{(j)}))}{\partial
E_{i}(x^{(j)})}$ (4)

which is equivalent to training a regression tree using original data points
but with new outcome values defined by the negative gradient. In this case,
$\alpha_{i}$ is the learning rate.

In this work, we evaluate our approach using random forest, but our approach
can also be adapted to handle boosting models.

##  3 The Proposed Method: OptExplain and ProClass

Figure 2: An overview of the proposed method.

This section details our ensemble trees explanation extraction approach. We
give an overview of our approach in Figure 2. First, we get a set of decision
rules by traversing the random forest. This set of decision rules is made up
of branch formulae for all the trees in the forest. The size of this set is
usually large, and we need to simplify the set in order to obtain a smaller
set that is as close as possible to the prediction ability of the original
model. We keep the nodes and branches with good quality to get the final
explanation set. The preciseness of the simplification process and the scale
of the explanation are related to the input parameters, and we get the
optimized parameters through the bionic optimization algorithm PSO (Particle
Swarm Optimization). There is two fitness function in optimization process,
one dedicate to generate optimal explanations while the other one is to
generate explanations used by profile.

###  3.1 From Decision Trees to Decision Rules

Given a decision tree defined in Section 2, it is straightforward to obtain
the formula that is associated with each internal node. From there, we can
obtain the “decision logic” of a branch via the _branch formula_ of the
following form:

$(\bigwedge F)\rightarrow D$ (5)

where $\bigwedge F$ is the conjunction of all the (possibly negated) internal
node formula on the branch, and $D$ is the vote distribution at the leaf node.
That is, if the branch goes through a node $F$ to the right branch, then we
include $F$ in the conjunction, otherwise we include $\lnot F$. We refer to a
formula of the above form as a _decision rule_.

It is worth noting that, by the construction of decision trees, the branches
are _exclusive_ to each other. That is, a data instance can never satisfy
multiple branch formulae from the same tree at the same time. As a result, a
decision tree $t$ can be converted into a set of mutually exclusive decision
rules, denoted as $R_{t}$. $R_{t}$ can be used in classification tasks by
finding the decision rule that satisfies an instance and outputting the class
of the largest number of votes.

The above method can be extended to handle an ensemble of trees produced by
random forest [2] or boosting [7, 8]. In such cases, we need to consider a set
$E$ of trees, and we need to multiply the vote distribution $D$ of each tree
by its weight in the ensemble. The result, which we refer to as $R_{E}$, is
the union of the set of decision rules from each tree.

Unlike the set of decision rules for a single tree, that for an ensemble of
trees may contain decision rules that are _not_ exclusive to each other. In
fact, for an ensemble $E$ of $n$ trees and for any data instance, there should
be exactly $n$ decision rules in the set $R_{E}$ that are satisfied by the
instance — one from each tree. To use $R_{E}$ in classification tasks, one can
find the subset of decision rules that are satisfied by an instance $x$ and
aggregate the weighted vote counts for each class from those rules. The class
with the highest weighted count is the output, which we refer to as
$R_{E}(x)$. The following result is straightforward:

###### Proposition 1

For any ensemble trees model $E$ and any data instance $x$, suppose $R_{E}$ is
the set of decision rules of $E$ derived by the method above, then
$E(x)=R_{E}(x)$.

In the sequel, we shall denote the original ensemble trees model as $E$ and
the converted set of decision rules as $R_{E}$.

###  3.2 Simplification of Decision Rules

As discussed in Section 1, some ensemble trees models used in real-life
applications are enormous and complex. Consequently, the converted set of
decision rules for such a model consists of a huge number of rules and each
rule may be a very long formula. To reduce the complexity of the explanation,
we consider simplifying the set of decision rules in two dimensions: the
length of the rules and the number of the rules.

Continuing from the output $R_{E}$ of Section 3.1, each formula in $R_{E}$ is
a branch formula, which we can simplify using a node filter as step one.

######  Parameter 1 (Node Filter $\theta$)

We measure the “quality” of a node ($NQ$) by information gain (IG):

$NQ(n)=IG(n)$ (6)

where $n$ is the target node. We scan the nodes of each branch in each tree,
and remove the nodes with $NQ$ below $\theta$, which is a real positive
number.

The second step is to simplify each branch formula by merging the nodes.

###### Lemma 1

For any branch formula $(\bigwedge F_{i})\rightarrow D$, where each $F_{i}$ is
the formula associated with a node on the branch, the left-hand side can be
simplified to conjunction normal form (CNF) with at most $n$ conjuncts, where
$n$ is the number of features of the dataset.

###### Proof

By the construction of decision trees, for any two conjuncts $v\geq l$ and
$v\geq l^{\prime}$ over a numeric feature $v$ that appears in $\bigwedge
F_{i}$, we can simplify them into one conjunct $v\geq l^{\prime\prime}$ where
$l^{\prime\prime}=max(l,l^{\prime})$.

For any two conjuncts $v\geq l$ and $\lnot(v\geq l^{\prime})$ over $v$, if
$l<l^{\prime}$, then they can be simplified to $l\leq v<l^{\prime}$.
Otherwise, we have $l\geq l^{\prime}$. In this case, the two conjuncts do not
have an intersection, and there would be no instances at the leaf node and the
training algorithm should not let this case happen.

For any two conjuncts $\lnot(v\geq l)$ and $\lnot(v\geq l^{\prime})$ over $v$,
they can be simplified to $v<l^{\prime\prime}$ where
$l^{\prime\prime}=min(l,l^{\prime})$.

For any two conjuncts $v^{\prime}\in C$ and $v^{\prime}\in C^{\prime}$ over a
nominal feature $v^{\prime}$, they can be simplified into one conjunct
$v^{\prime}\in C^{\prime\prime}$ where $C^{\prime\prime}=C\cap C^{\prime}$. If
any of the two conjuncts is negated, e.g., $\lnot(v^{\prime}\in C)$, we can
simply take the complement set $C^{\prime\prime\prime}=C_{v}\setminus C$,
where $C_{v}$ is the full set of permitted discrete values of the feature $v$,
and convert the negated conjunct into $v^{\prime}\in C^{\prime\prime\prime}$.
The remainder of the proof is analogous.

Thus, the left-hand side of the branch formula can be simplified to one
conjunct per feature. ∎

Note that the simplification of Lemma 1 preserves logical equivalence of the
set of decision rules while the other steps of this section do not. One may
ask why do we use the node filter when Lemma 1 can merge the nodes. The reason
is that using all the nodes in a branch may result in very narrow and focused
explanations, so we use $\theta$ as a parameter to adjust the scope.

The above two steps aim to shorten the decision rules. The third step is to
reduce the number of rules by filtering out those of low quality.

######  Parameter 2 (Rule Filter $\phi$)

We measure the “quality” of a decision rule ($RQ$) by the following formula:

$RQ(r)=\frac{(log_{2}(m)-H(l_{r}))}{log_{2}(m)}\times Acc$ (7)

where $r$ is the target rule, $m$ is the number of classes, $H(l_{r})$ is the
entropy of the leaf of the rule, and $Acc$ is the accuracy of the
corresponding tree on the OOB dataset. We remove a rule if its $RQ$ is less
than $\phi$, which is a real number between $0$ and $1$.

The fourth step merges decision rules into _groups of the same class
signature_.

######  Parameter 3 (Leaf Merger $\psi$)

Given a vote distribution $(n_{1},\cdots,n_{m})$, where $m$ is the number of
classes, we convert the distribution into ratios
$(\xi_{1}$,$\cdots$,$\xi_{m})$ where each $\xi_{i},1\leq i\leq m$, is the
ratio of class $i$ in the leaf node. The class signature of this leaf node is
defined as the tuple
$(\lceil\xi_{i}/\psi\rceil,\cdots,\lceil\xi_{m}/\psi\rceil)$, where $\psi$ is
a real number between $0$ and $1$.

Using the above definition, we divide the set of decision rules into a set of
sets $\\{G_{1},\cdots,G_{j}\\}$. Each $G_{i}$, $1\leq i\leq j$, contains the
set of rules of the same class signature. Intuitively, a larger $\psi$ yields
fewer distinct equivalent classes/groups and vice versa. We use this parameter
to control the number of groups in the final explanation.

For a large-scale random forest, the filtered rules are still a large-scale
formula set. In the last step, we control the number of decision rules we get.

######  Parameter 4 (Size Filter $k$)

In each $G_{i}$, we take the number of instances in the leaf node of each rule
as the weight of the rule, and we select $k$ rules in a weight-first manner.

Associating each rule with the weight is crucial because now the vote
distribution has been converted into ratios, and we have lost the information
of the number of votes in the distribution. The weight retains this
information. For example, we would prefer a ratio of $(0.7,0.3)$ with 100
votes to overwhelm a ratio of $(0.1,0.9)$ with 10 votes.

To summarise, we denote the composition of the above steps as $Simp$, and
write the simplification procedure as follows:

$Simp(R_{E},\theta,\phi,\psi,k)=R_{E}^{\prime}$ (8)

where $R_{E}^{\prime}$ is a set of sets of decision rules where each rule has
a weight. We use $R_{E}^{\prime}$ as our explanation to the original model.

###  3.3 Prediction

To use $R_{E}^{\prime}$ in a classification task, let $x$ be a data instance,
we first find all the decision rules in $R_{E}^{\prime}$ that are satisfied by
$x$, then multiply the class signature of each rule by the corresponding
weight, and finally add up to get a tuple. The class with the largest value is
the output. This procedure is denoted as $R_{E}^{\prime}(x)=c$ where $c$ is a
class. We give an example in Fig. 3 where we put the satisfied rules in red
boxes.

Figure 3: An example of the prediction procedure using the simplified rules
$R_{E}^{\prime}$.

###  3.4 Optimal Explanations

Now we consider a step further: how to evaluate explanations and find the
optimal one? Intuitively, a good explanation should meet the following two
criteria:

  * •

The classification behaviour of the explanation $R_{E}^{\prime}$ should be
similar to the original model $E$.

  * •

The explanation should be concise and small.

We use fidelity to measure the first criterion. Fidelity is defined as the
degree of similarity between the predictions of $R_{E}^{\prime}$ and $E$ on
unseen data [21]. First, we take the test set without labels as $D$. Then we
use the classification results on $D$ from the original model $E$ as the
“ground truth”. Lastly, we evaluate the classification accuracy of the
explanation $R_{E}^{\prime}$ on $D$ as fidelity. The fidelity component is
denoted as $N(R_{E}^{\prime},E,D)$.

The second criterion is scale which is measured by the total number of
conjuncts in the rules of $R_{E}^{\prime}$ and is denoted as
$L(R_{E}^{\prime})$.

The _score_ of an explanation $R_{E}^{\prime}$ is defined as

$S_{opt}(R_{E}^{\prime})={N(R_{E}^{\prime},E,D)\times\epsilon}+\frac{1-\epsilon}{1+e^{5\times(\frac{L(R_{E}^{\prime})}{m\times
n}-1)}}$ (9)

where $\epsilon$ is a real number between 0 and 1, $n$ is the number of
features, and $m$ is the number of classes. The intuition is that the score
grows linearly with fidelity, but it drops significantly when the explanation
is too large. The second component is a sigmoid-shaped function. Also, a large
$\epsilon$ puts more importance on fidelity, and a small $\epsilon$ puts more
importance on scale.

(a) The effect of $\theta$ and $\phi$ on scale coverage. (The original scale
is 65247.)

(b) The effect of $k$ on fidelity.

Figure 4: The effect of parameters on the two criterion.

The parameters in Section 3.2 introduce a great variety of potential
explanations. Particularly, the two parameters $\theta$ and $\phi$ control the
strictness of the node filter and the rule filter respectively. We experiment
on the diabetes dataset [6] to explore the effect of parameters on the two
criteria. Fig. 4(a) shows the effect of the $\theta$ and $\phi$ on scale. As
$\theta$ and $\phi$ rise, we get significantly smaller explanations. Even when
$\theta$ and $\phi$ are both 0, the scale has dropped by about 20% compare to
the original model due to Lemma 1. We also explore the effect of $k$ on
fidelity. We set $\theta$ to 0.65 and $\phi$ to 0.7. Fig. 4(b) shows the
average of 50 tests. The results show that a relatively small value of $k$ can
get a fidelity close to all the rules.

To obtain an optimal explanation, we use the _linearly decreasing inertia
weigh particle swarm optimization_ algorithm (LDIW-PSO) [24] to optimise the
parameters mentioned above with the $S_{opt}$ as the fitness, which is the
objective function to be optimised. Then we apply the optimal parameters to
Simp and obtain the optimal explanation $R_{opt}$. We refer to the above
procedure as _OptExplain_.

###  3.5 Profile of Equivalent Classes

An explanation with high fidelity usually has large scale, while a concise
explanation can allow users to quickly understand the predictive behavior of
the model at the sacrifice of fidelity. Sometimes the latter is preferred to
draw a high-level conclusion of the classification behavior. We propose a new
method called the Profile of Equivalent Classes (ProClass), which is a more
concise description of classes based on the extracted decision rules.

The ProClass process is based on the $R_{E}^{\prime}$ obtained by Equation 8.
The $R_{E}^{\prime}$ may contain several groups, each has no more than $k$
rules. Then we merge the decision rules in each group by solving a weighted
maximum satisfiable (MAX-SAT) problem to get a new explanation
$R_{E}^{\prime\prime}$. Different from Section 3.4, ProClass requires more
rules as input, and the number of groups is equal to the number of classes.
The number of groups in $R_{E}^{\prime\prime}$ is denoted as
$M(R_{E}^{\prime\prime})$. For the above needs, we defined another score for
the optimization in _ProClass_ :

$S_{pro}(R_{E}^{\prime\prime})=(m-M(R_{E}^{\prime\prime})+1)\times
L(R_{E}^{\prime\prime})$ (10)

where $m$ is the number of classes. Using $S_{pro}$ as fitness, we obtain the
optimized result is denoted as $R_{opt}^{\prime}$. An ideal $R_{opt}^{\prime}$
has $m$ groups $\\{G_{1},\cdots,G_{m}\\}$. For each group $G_{i}$ ($1\leq
i\leq m$), we associate the weight of each rule to each of its conjuncts, and
send all the weighed conjuncts in the group to a SAT solver such as Z3 [18].
The solver will return a subset of satisfied conjuncts that maximise the total
weight. After solving the MAX-SAT problem for each $G_{i}$, we obtain a subset
of conjuncts. Then we simplify the conjuncts into one rule $r_{i}^{\prime}$
using Lemma 1. Performing the above steps on all groups, we get the profile of
equivalent classes denoted as $R_{pro}$, which has the form

$R_{pro}=\\{r_{1}^{\prime}\rightarrow S_{1},\cdots,r_{m}^{\prime}\rightarrow
S_{m}\\}.$

where $r_{i}^{\prime}$ is the logic for predicting the class $S_{i}$.

##  4 Case Studies and Experiment

In this section, we demonstrate our method through case studies. We used
scikit-learn to train random forest models. We implemented our method in
Python and evaluated it on multiple datasets: adult, credit, diabetes, german,
mnist, spambase, all of which are available on OpenML [19]. There are two
important parameters in LDIW-PSO algorithm: particle size and iteration
period. In our experiments, both particle size and iteration period are set to
20 by default. Experiments were conducted on a machine with an Intel Core
i9-7960X CPU and 32GB RAM.

###  4.1 Case Study 1: Diabetes Prediction

We first evaluate _OptExplain_ on diabetes dataset [6], which has 8 features,
2 classes, and 768 samples. The eight features are the number of times
pregnant (preg), plasma glucose concentration (plas), diastolic blood pressure
(pres), 2-hour serum insulin (insu), triceps skinfold thickness (skin), body
mass index (mass), diabetes pedigree function (pedi) and age. We randomly
select 100 samples as the testing set, and the rest as the training set. Then
we train a random forest with 100 trees and unlimited depth.

Table 1: Optimized parameters and predictive performance of the explanation. $(\phi,\theta,\psi,k)$ | $R_{E}$ |  | $R_{opt}$
---|---|---|---
scale | accuracy |  | scale | accuracy | fidelity
(0.55, 0.45, 0.83, 3.0) | 102584 | 80% |  | 6 | 80% | 92%
Table 2: The optimal explanation $R_{opt}$. Groups |  | Class Signature
---
(negative,positive)
Rules | Weight
Group1 | (2.0 , 0.0) | $pedi\leq 0.7$ | 30
$plas\leq 130.0$ | 23
| $plas\leq 157.5$ | 21
Group2 | (0.0 , 2.0) | $mass>28.7$ | 30
$age>27.5$ | 22
| $plas>122.5$ | 20

We set $\epsilon$ to 0.9, and _OptExplain_ will produce an explanation
$R_{opt}$. The result is shown in Table 1 and Table 2. Recall that $R_{E}$ is
equivalent to the original model $E$ (Proposition 1). Both $R_{E}$ and
$R_{opt}$ have 80% accuracy on the test set. $R_{E}$ has 11106 rules with
102584 conjuncts, while $R_{opt}$ has 6 rules with 6 conjuncts. The fidelity
of $R_{opt}$ is 92%, which means it is very similar to the original model. By
observing the decision rules, users can analyze what role each feature plays
in the prediction process. In this explanation, if an instance has
$plas>157.5$, then the chance of prediction positive diabetes is high.

Table 3: The profile of equivalent classes of a random forest model for diabetes. negative |  | positive |
---|---|---|---
$2.0<preg\leq 2.5$ |  | $7.5<preg\leq 8$ |
$90<plas\leq 91.5$ |  | $173.5<plas\leq 175$ |
$74<pres\leq 74.5$ |  | $70<pres\leq 71$ |
$28.5<skin\leq 29$ |  | $23.5<skin\leq 24$ |
$61.5<insu\leq 63$ |  | $126.5<insu\leq 127.5$ |
$25.9<mass\leq 26$ |  | $32.9<mass\leq 33$ |
$pedi=0.2$ |  | $pedi=0.5$ |
$23.5<age\leq 24$ |  | $33<age\leq 33.5$ |

Table 3 gives the profile of equivalent classes derived from $ProClass$. The
profile is divided into two groups corresponding to equivalent class labels:
negative diabetes and positive diabetes. Medical practitioners can quickly
obtain the salient feature values corresponding to each class according to the
profile.

###  4.2 Case Study 2: Digit Recognition (MNIST)

In order to visually demonstrate the profile, we use the MNIST dataset [19] to
illustrate $ProClass$. The MNIST dataset contains 70,000 images of size 28
$\times$ 28 pixels. In order to reduce the complexity, we randomly picked
10,000 samples from the dataset as the training set, and train a random forest
with 100 trees and 15 max-depth. $ProClass$ produces a profile $R_{pro}$ which
gives the range of some pixels. Then we take the median of the range as the
pixel value. The remaining pixels that do not appear in the profile are set to
light blue.

Figure 5: As visualisation of $R_{pro}$ on MNIST.

From Fig. 5 we can see the profile’s visualization of each digit. For
peripheral pixels that are not significant in the prediction, the profile will
not give a description. As we can see, the profiles indeed yield human-
understandable visualisation of each class.

###  4.3 Experiment and Comparison

We compared the proposed method to a baseline method — Hara and Hayashi’s
approach named degragTrees [11]. In their work, defragTrees has been compared
with BATrees [1], inTrees [5] and Node Harvest [17]. Their result suggests
that defragTrees generated smaller set of rules with higher fidelity than the
other methods. We choose the following datasets: adult, credit, diabetes,
german, spambase [6]. We split the datasets into two subsets at random: a 70%
training set, and a 30% testing set. Then we train the ensemble trees with 100
trees and 10 max-depth for _OptExplain_ and defragTrees. For _OptExplain_ , we
set two experimental groups and set $\epsilon$ as 0.5 and 0.9 respectively.

Table 4: _OptExplain_ and defragTrees Data | defragTrees |  | _OptExplain_ |
---|---|---|---|---
|  $\epsilon$=0.5 |  |  $\epsilon$=0.9 |
scale | fidelity% |  | scale | fidelity% |  | scale | fidelity% |
adult | 65.5 | 81.9 |  | 37.2 | 87.0 |  | 43.2 | 88.4 |
credit | 8.7 | 85 |  | 2.8 | 94.2 |  | 9.8 | 94.6 |
diabetes | 14.2 | 74.8 |  | 4 | 85.8 |  | 8.3 | 88.3 |
german | 5.4 | 69.8 |  | 19 | 87.3 |  | 50.2 | 88.7 |
spambase | 82 | 91.7 |  | 22 | 91.6 |  | 40.6 | 92.9 |

We compare the two methods with respect to the two criteria: scale and
fidelity. We conducted the experiment over ten random data realizations for
each dataset. Table 4 shows the average values of the ten tests. The number in
bold is the best scale/fidelity value for each dataset. Table 4 shows that the
scale of explanations generated by _OptExplain_ with 0.5 $\epsilon$ is the
smallest except on the german dataset, and the fidelity is generally better
than defragTrees. The small-scale explanation on german generated by
defragTrees has much lower fidelity. _OptExplain_ with 0.9 $\epsilon$ can
generate the highest fidelity explanation with similar scale than defragTrees.
In both settings of $\epsilon$, _OptExplain_ generates superior explanations
in most cases.

Figure 6: Mean elapsed time comperision. (The y-axis is logarithmic scale.)

Finally, we visually compare the computation time in Fig. 6, and show the mean
time of 10 tests. We run _OptExplain_ on models of 100 trees with depth of 10,
20, and 30 respectively. The method defragTrees on 100 trees and depth 10 is
also used as a reference. The results show that _OptExplain_ has better
computational performance than defragTrees on adult, diabetes and spambase.
_OptExplain_ can also deal with very large models, and for the above three
datasets, _OptExplain_ can generate explanations for trees of depth 30 faster
than defragTrees can for depth 10. For a concrete example, the mean
computation time of _OptExplain_ on the adult dataset is 1,949 s, while the
time of defragTrees is 5,797 s (both depth 10).

##  5 Related Work

There are a variety of approaches for tackling machine learning
interpretability. Some recent and popular ones are focused on local
explanations. LIME [22] is such a tool that finds linear approximations of the
prediction model and gives importance weights for certain predicates used in
the prediction. Anchors [23] generates “if-then” style explanations for
predictions. Such explanations have similar forms as our decision rules and
are considered intuitive and easy to understand by the user. Shapley (SHAP)
Values [16] are often used to extract importance scores and impacts on
features. Like LIME, SHAP also provides user-friendly graphical presentations
(e.g., bar charts) for explaining predictions. It should be noted that SHAP
can also be used to obtain global feature importance. The above three methods
are _model-agnostic_ , which means that in the process of providing
explanations and making machine learning more “white-box”, they take
prediction models as a “black-box” and attempt to find patterns of _features_
when the model makes predictions. An advantage is that they can be applied to
different machine learning techniques, including ensemble trees and neural
networks. CHIRPS [12] is another technique for local explanations. In contrast
to the above techniques, CHIRPS looks into decision trees and uses frequent
pattern mining on decision nodes to obtain decision rules as the explanation.

Global explanations are more closely related to this work. Recent examples
include Hara and Hayashi’s approach [11] that uses Bayesian model selection to
extract decision rules. Deng’s inTrees [5] extracts, selects and prunes rules
from a set of decision trees and uses frequent pattern analysis to summarise
rules into a smaller prediction model.

Most relevant techniques come from a statistics perspective. Their
simplification process often consists of selection, pruning and frequency
analysis. By contrast, our work comes from a logician’s point of view and, on
top of the usual selection and pruning operations, uses automated reasoning to
simplify logical formulae and find abstractions of equivalent classes. We see
many related methods as complementary ones rather than competitors because
they output in different forms. For example, one can combine SHAP values and
our work to form a more comprehensive explanation.

##  6 Conclusion and Future Work

This paper presents a streamlined procedure for extracting optimal _logical_
explanations from ensemble trees models. As an additional feature, our method
can also output the “profile” of each class so that the user can _see_ how the
model predicts in different cases. We give two case studies to illustrate how
our method works and show that our method outperforms state-of-the-art through
experimental results.

As future work, we plan to use this work to perform efficient verification
tasks. In particular, we will use the optimal explanation as an approximation
of the original model and try to “debug” the model against user-specified
properties. The rules that violate the property can serve as constraints to
narrow down the search space when finding counterexamples. Another important
future direction is to convert deep neural networks to ensemble trees and
extend this work to explain deep learning.

## References

  * [1] Breiman, L., Shang, N.: Born again trees (1996)
  * [2] Breiman, L.: Random forests. Machine Learning 45(1), 5–32 (Oct 2001)
  * [3] Bride, H., Dong, J., Dong, J.S., Hóu, Z.: Towards dependable and explainable machine learning using automated reasoning. In: Formal Methods and Software Engineering - 20th International Conference on Formal Engineering Methods, ICFEM 2018, Gold Coast, QLD, Australia, November 12-16, 2018, Proceedings. pp. 412–416 (2018)
  * [4] Cui, Z., Chen, W., He, Y., Chen, Y.: Optimal action extraction for random forests and boosted trees. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 179–188. KDD ’15, ACM, New York, NY, USA (2015). https://doi.org/10.1145/2783258.2783281, http://doi.acm.org/10.1145/2783258.2783281
  * [5] Deng, H.: Interpreting tree ensembles with intrees. International Journal of Data Science and Analytics 7(4), 277–287 (2019)
  * [6] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [7] Freund, Y., E Schapire, R.: A short introduction to boosting. Journal of Japanese Society for Artificial Intelligence 14, 771–780 (10 1999)
  * [8] Friedman, J.H.: Greedy function approximation: A gradient boosting machine. Annals of Statistics 29, 1189–1232 (2000)
  * [9] Friedman, J.H.: Stochastic gradient boosting. Computational statistics & data analysis 38(4), 367–378 (2002)
  * [10] Goré, R., Olesen, K., Thomson, J.: Implementing tableau calculi using bdds: Bddtab system description. In: Automated Reasoning - 7th International Joint Conference, IJCAR 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 19-22, 2014. Proceedings. pp. 337–343 (2014)
  * [11] Hara, S., Hayashi, K.: Making tree ensembles interpretable: A bayesian model selection approach. In: International conference on artificial intelligence and statistics. pp. 77–85. PMLR (2018)
  * [12] Hatwell, J., Gaber, M.M., Azad, R.M.A.: Chirps: Explaining random forest classification. Artificial Intelligence Review 53, 5747–5788 (2020)
  * [13] Hinton, G., Frosst, N.: Distilling a neural network into a soft decision tree (2017), https://arxiv.org/pdf/1711.09784.pdf
  * [14] Ho, T.K.: Random decision forests. In: Proceedings of 3rd international conference on document analysis and recognition. vol. 1, pp. 278–282. IEEE (1995)
  * [15] Ltd, D.I.P.: Silas. https://depintel.com/silas/ (2018)
  * [16] Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30, pp. 4765–4774. Curran Associates, Inc. (2017), http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf
  * [17] Meinshausen, N.: Node harvest (2009)
  * [18] de Moura, L., Bjørner, N.: Z3: An efficient smt solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 337–340. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)
  * [19] OpenML: openml.org. https://www.openml.org (Accessed 2019)
  * [20] Pafka, S.: A minimal benchmark for scalability, speed and accuracy of commonly used open source implementations of the top machine learning algorithms for binary classification. https://github.com/szilard/benchm-ml (2018)
  * [21] Papenmeier, A., Englebienne, G., Seifert, C.: How model accuracy and explanation fidelity influence user trust. arXiv preprint arXiv:1907.12652 (2019)
  * [22] Ribeiro, M.T., Singh, S., Guestrin, C.: ”why should I trust you?”: Explaining the predictions of any classifier. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016. pp. 1135–1144 (2016)
  * [23] Ribeiro, M.T., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explanations. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32 (2018)
  * [24] Shi, Y., Eberhart, R.C.: Empirical study of particle swarm optimization. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). vol. 3, pp. 1945–1950 Vol. 3 (1999). https://doi.org/10.1109/CEC.1999.785511
  * [25] Sun, J., Liu, Y., Dong, J.S., Pang, J.: PAT: Towards flexible verification under fairness. Lecture Notes in Computer Science, vol. 5643, pp. 709–714. Springer (2009)
  * [26] Törnblom, J., Nadjm-Tehrani, S.: Formal Verification of Random Forests in Safety-Critical Applications: 6th International Workshop, FTSCS 2018, Gold Coast, Australia, November 16, 2018, Revised Selected Papers, pp. 55–71 (01 2019)