Interpretable Rule Discovery Through Bilevel Optimization of Split-Rules of Nonlinear Decision Trees for Classification Problems

For supervised classification problems involving design, control, other\npractical purposes, users are not only interested in finding a highly accurate\nclassifier, but they also demand that the obtained classifier be easily\ninterpretable. While the definition of interpretability of a classifier can\nvary from case to case, here, by a humanly interpretable classifier we restrict\nit to be expressed in simplistic mathematical terms. As a novel approach, we\nrepresent a classifier as an assembly of simple mathematical rules using a\nnon-linear decision tree (NLDT). Each conditional (non-terminal) node of the\ntree represents a non-linear mathematical rule (split-rule) involving features\nin order to partition the dataset in the given conditional node into two\nnon-overlapping subsets. This partitioning is intended to minimize the impurity\nof the resulting child nodes. By restricting the structure of split-rule at\neach conditional node and depth of the decision tree, the interpretability of\nthe classifier is assured. The non-linear split-rule at a given conditional\nnode is obtained using an evolutionary bilevel optimization algorithm, in which\nwhile the upper-level focuses on arriving at an interpretable structure of the\nsplit-rule, the lower-level achieves the most appropriate weights\n(coefficients) of individual constituents of the rule to minimize the net\nimpurity of two resulting child nodes. The performance of the proposed\nalgorithm is demonstrated on a number of controlled test problems, existing\nbenchmark problems, and industrial problems. Results on two to 500-feature\nproblems are encouraging and open up further scopes of applying the proposed\napproach to more challenging and complex classification tasks.\n