The increasing attention to the interpretability of machine learning models has led to the development of methods to explain the behavior of black-box models in a post-hoc manner. However, such post-hoc approaches generate a new explanation for every new input, and these explanations cannot be checked by humans in advance. A method that selects decision rules from a finite ruleset as explanation for neural networks has been proposed, but it cannot be used for other models.In this paper, we propose a model-agnostic explanation method to find a pre-verifiable finite ruleset from which a decision rule is selected to support every prediction made by a given black-box model. First, we define an explanation model that selects the rule, from a ruleset, that gives the closest prediction; this rule works as an alternative explanation or supportive evidence for the prediction of a black-box model. The ruleset should have high coverage to give close predictions for future inputs, but it should also be small enough to be checkable by humans in advance. However, minimizing the ruleset while keeping high coverage leads to a computationally hard combinatorial problem. Hence, we show that this problem can be reduced to a weighted MaxSAT problem composed only of Horn clauses, which can be efficiently solved with modern solvers.Experimental results showed that our method found small rulesets such that the rules selected from them can achieve higher accuracy for structured data as compared to the existing method using rulesets of almost the same size.

Abstract In some applications, acquiring covariates comes at a cost which is not negligible. For example in the medical domain, in order to classify whether a patient has diabetes or not, measuring glucose tolerance can be expensive. Assuming that the cost of each covariate, and the cost of misclassification can be specified by the user, our goal is to minimize the (expected) total cost of classification, i.e. the cost of misclassification plus the cost of the acquired covariates. We formalize this optimization goal using the (conditional) Bayes risk and describe the optimal solution using a recursive procedure. Since the procedure is computationally infeasible, we consequently introduce two assumptions: (1) the optimal classifier can be represented by a generalized additive model, (2) the optimal sets of covariates are limited to a sequence of sets of increasing size. We show that under these two assumptions, a computationally efficient solution exists. Furthermore, on several medical datasets, we show that the proposed method achieves in most situations the lowest total costs when compared to various previous methods. Finally, we weaken the requirement on the user to specify all misclassification costs by allowing the user to specify the minimally acceptable recall (target recall). Our experiments confirm that the proposed method achieves the target recall while minimizing the false discovery rate and the covariate acquisition costs better than previous methods.

Clustering, like covariate selection for classification, is an important step to compress and interpret the data. However, clustering of covariates is often performed independently of the classification step, which can lead to undesirable clustering results that harm interpretability and compression rate. Therefore, we propose a method that can cluster covariates while taking into account class label information of samples. We formulate the problem as a convex optimization problem which uses both, a-priori similarity information between covariates, and information from class-labeled samples. Like ordinary convex clustering [1], the proposed method offers a unique global minima making it insensitive to initialization. In order to solve the convex problem, we propose a specialized alternating direction method of multipliers (ADMM), which scales up to several thousands of variables. Furthermore, in order to circumvent computationally expensive cross-validation, we propose a model selection criterion based on approximating the marginal likelihood. Experiments on synthetic and real data confirm the usefulness of the proposed clustering method and the selection criterion.

Deep neural networks achieve high predictive accuracy by learning latent representations of complex data. However, the reasoning behind their decisions is difficult for humans to understand. On the other hand, rule-based approaches are able to justify the decisions by showing the decision rules leading to them, but they have relatively low accuracy. To improve the interpretability of neural networks, several techniques provide post-hoc explanations of decisions made by neural networks, but they cannot guarantee that the decisions are always explained in a simple form like decision rules because their explanations are generated after the decisions are made by neural networks.In this paper, to balance the accuracy of neural networks and the interpretability of decision rules, we propose a hybrid technique called rule-constrained networks, namely, neural networks that make decisions by selecting decision rules from a given ruleset. Because the networks are forced to make decisions based on decision rules, it is guaranteed that every decision is supported by a decision rule. Furthermore, we propose a technique to jointly optimize the neural network and the ruleset from which the network select rules. The log likelihood of correct classifications is maximized under a model with hyper parameters about the ruleset size and the prior probabilities of rules being selected. This feature makes it possible to limit the ruleset size or prioritize human-made rules over automatically acquired rules for promoting the interpretability of the output. Experiments on datasets of time-series and sentiment classification showed rule-constrained networks achieved accuracy as high as that achieved by original neural networks and significantly higher than that achieved by existing rule-based models, while presenting decision rules supporting the decisions.

In some real world applications, acquiring covariates for classification can be cost-intensive and should be limited as much as possible. For example, in the medical setting, a doctor cannot just perform all possible types of tests to classify whether the patient has diabetes or not. The decision of classifying or acquiring more covariates before classifying is dependent on the costs of new covariates and the expected optimal cost of misclassification (Bayes risk). However, estimating the latter is a formidable task due to the estimation of a high dimensional probability density and intractable integrals. In this work, we show that for linear classifiers this task can be considerably simplified, leading to a one dimensional integral for which we propose an efficient approximation. Experimental results on three datasets show consistent improvements over previously proposed methods for cost-sensitive classification. We also demonstrate that our proposed Bayes risk estimation procedure can benefit from additional unlabeled data which can be helpful when only small amount of labeled data is available.

The interpretability of machine learning models is a crucial factor if human experts have to check and explain why decisions are made. Because of the growing interest in in-terpretability, a simple rule-based model called a decision list has recently regained attention, and several techniques are proposed to improve the accuracy of decision lists by exploiting the power of modern high-speed processors. However, even with the help of modern processors, optimizing decision lists is still difficult and inefficient because of the discrete nature of decision lists. In this paper, we propose an algorithm that optimizes decision lists in a continuously relaxed form, instead of optimizing them in the original discrete form. First, from a given rule set, we construct a continuous decision list that is a continuously relaxed version of a decision list. It is optimized using a continuous optimization method and is finally converted into a decision list of the original discrete form. This approach can exploit the efficiency of continuous optimization methods supported by the optimization frameworks recently developed for deep learning. In experiments, our algorithm performed more efficiently than the state-of-the-art decision list learning algorithms, i.e., it achieved significantly higher accuracies in shorter times on large datasets.

We consider the problem of multi-dimensional orthogonal range searching in linear space for any d dimensions. The kd-tree achieves O(n(d−1)/d) query time for range counting, which is optimal among bounding-box tree structures, and it has been considered to be the best complexity bound in practice for four decades, while the non-overlapping k-range achieves O(n∊) query time in theory. Several two-dimensional data structures have better query times than the kd-tree, but have never been generalized to higher dimensions in linear space. In this paper, we propose a new succinct data structure, called the KDW-tree, which requires less space partitioning than the kd-tree and achieves O(n(d−2)/d log n) time for range counting. This is the first succinct data structure that has a lower time complexity than the kd-tree in arbitrary dimensions. In experiments, our data structure significantly outperformed the kd-tree using linear space both for range counting and sum queries in low dimensions for high selectivity.

Given the user's input as a query, auto-completion selects the top-k strings with the highest scores from the strings matching the query in a dictionary. A recent study [14] proposed space-efficient data structures for top-k prefix matching for auto-completion. In practical applications, however, top-k substring matching is required for many purposes. In this paper, we present a novel approach to solve the top-k substring matching problem. We combined two trie-based data structures derived from the same dictionary for prefix and key search, and we search them alternately leveraging the implicit tree structure shared by them. Experimental results show that our algorithm can suggest top-k completion sufficiently fast, while taking much less space than a compressed full-text index of the dictionary.