Learning Hybrid Interpretable Models: Theory, Taxonomy, and Methods
Authors: Julien Ferry
Gabriel Laberge
Ulrich Aïvodji
Venue: Accepted by TMLR ()

Abstract: A hybrid model involves the cooperation of an interpretable model and a complex black box. At inference, any input of the hybrid model is assigned to either its interpretable or complex component based on a gating mechanism. The ratio of data samples sent to the interpretable component is referred to as the model transparency. 
Despite their high potential, Hybrid Interpretable Models remain under-studied in the interpretability/explainability literature. In this paper, we remedy this fact by presenting a thorough investigation of such models from three perspectives: Theory, Taxonomy, and Methods. 
First, we highlight the potential generalization benefits of sending samples to an interpretable component by deriving a Probably-Approximately-Correct (PAC) generalization bound. This guarantee indicates a sweet spot for optimal transparency, which suggests that redirecting inputs to an interpretable model can act as regularization. Secondly, we provide a general taxonomy for the different ways of training such models: the Post-Black-Box and Pre-Black-Box paradigms. These approaches differ in the order in which the interpretable and complex components are trained. We show where the state-of-the-art Hybrid-Rule-Set and Companion-Rule-List fall in this taxonomy. 
Thirdly, we implement the two paradigms in a single method: HybridCORELS, which extends the CORELS algorithm to Hybrid Interpretable Modeling. By leveraging CORELS, HybridCORELS provides a certificate of optimality of its interpretable component and precise control over transparency. We finally show empirically that HybridCORELS is competitive with existing approaches and performs just as well as a standalone black box (or even better) while being partly transparent.

Published in Transactions on Machine Learning Research (08/2024)
Learning Hybrid Interpretable Models: Theory, Taxonomy, and Methods
Julien Ferry
iferryGloas.j
Operations Reseorch, Combinatorial Optimization ond Constraints LAAS-CNRS, Université de Toulouse, CNRS
Toulouse, France
Gabriel Laberge
gabricl. @ookyyttt...oo.l.....c.
Génie Informatique et Génie Logiciel
Polytechnique Montréal
Montréal, Canada
UIrich Aïvodji
wirich, wirich wiwoohhjoojjjeeemm.....
Software and Information Technology Engineering École de Technologie Supérieure
Montréal, Conada
Reviewed on OpenReview: https: // openreview. net/ formm id= XzaSGIStXP
Abstract
A Hybrid Interpretable Model involves the cooperation of an interpretable model and a complex black-box. At inference, any input of the model assigned to either its inter- pretable or complex component based on a gating mechanism. The ratio of data samples sent the interpretable component is referred to the model transparency. Despite their high potential, Hybrid Interpretable Models remain under-studied in the interpretability/ explainability literature. In this paper, remedy this fact by presenting thorough inves- tigation of such models from three perspectives: Theory, Taxonomy, and Methods. First, we highlight the potential generalization benefits of sending samples to an interpretable com- ponent by deriving a Crobabb--Approximaaty--CCo guarantee indicates a sweet spot for optimal transparency, which suggests that redirecting inputs to an interpretable model can act regularization. Socondly, we provide general laxonomy for the different ways of training such models: the Post-Black. Bor and Pre- Black-Box Box paradigms. These approaches differ in the order in which the interpretable and complex components are trained. We show where the stato-of-tho-art Hyybrid-Rule-So and Companion- Caopanion-Rule-Liae Rule-List fall in this taxonomy. Thirdly, we implement the two paradigms in a single method: HybridCORELS, which extends the CORELS algorithm to Hybrid In- terpretable Modeling. By leveraging CORELS, HybridCORELS provides a certificate of optimality of its interpretable component and precise control over transparency. We finally show empirically that HybridCORELS is competitive with existing approaches and performs just well standalone black-box (or even better) while being partly transparent.
(PAC) generalization bound. This
1 Introduction
The ever-increasing integration of machine learning models in high-stakes decision-making contexts such as healthcare, justice, or finance (e.g., kidney exchange (Aziz et al. 2021), recidivism prediction (Angwin et al. 2016) or credit scoring (Aniccto al. (020)) has fostered a growing demand for transparency recent years. Current workhorses address transparency concerns machine learning include black- box explanation and transparent design techniques (Guidotti et al. 2018). Black-box explanation techniques aim at explaining

---

Published in Transactions on Machine Learning Research (08/2024)
Query æ
0.75
0.74
Accuracy
Gate
Send to hg?
0.73
Yes
No
0.72
0.71
Simple Model (a))
Opaque Model ((())
0.70
0.0
0.2
0.4
0.6
0.8
1.0
Transparency
(a)
(b)
CRL
HyRS
HybridCORELSPost
HybridCoRELSPre
Figure 1: Overview of Hybrid Interpretable Modeling. (a) General schematic of a Hybrid Interpretable Model where, at inference time, gating mechanism determines whether to send the instance to the interpretable component h2 or to the complex one he- (b) Letting transparency be the ratio of samples sent to the interpretable component ha, the trade-off between accuracy and transparency can be measured and compared across different Hybrid Interpretable Models.
complex machine learning models in a post-hoc fashion with global explanations such as Trepan (Craven & Shavlik 1995) and BETA [Lakkarjuu et al.) 2017) or local explanations such as LIME (Ribeiro et al. 2016)
and SHAP (Lundberg & Lee 2017). On the other hand, transparent design concerns the development of
inherently interpretable models such as rule lists (Rivest 1987 Angelino et al. (017), rule sets (Rijnbeck &
Kors
2010), decision trees (Breiman] 2017), and scoring systems (Ustun & Rudin 2016
However, both black-box explanations and transparent design face performance and trustworthiness chal- lenges that can prevent their wide adoption. On the one hand, while inherently interpretable models can be more easily understood and adopted by non-domain experts, their out-of-the-bon performance can be worse than non-transparent models. Morcover, training such models to optimality is often NP-hard due to their discrete nature. On the other hand, black boxes can elsort allain high performance but their decision mechanisms are opaque and hard understand by both experts and non-experts. Also, post-hoc explana- tions of these complex models have boen shown to be unreliable and highly manipulable by ill-intentioned entities (Aivodji et al.) 2019 Slack et al. 2020 Dimanov et al. 2020 Aivodji et al.) 2021 Laberge et al. 2022 This conundrum between black-box transparent designs is colloquially referred to the "accuracy- transparency trade-off", that is, one has to choose between transparent models with lower performance or opaque models that perform well but whose explanations are not trustworthy. Still, this trade-off is not a iuantitative measure but rather a part of the collective imagination of researchers. For this reason, the trade-off has been hcavily criticized and even labeled myth (Rudin) 2019). But the question remains, does such trade-off exist? And if it does, there a way to quantitatively measure it? Or even optimize it?
To explore such questions, we will not treat black-box and transparent designs as dichotomics. Rather, we will explore the continuum between the two philosophies by studying Hybrid Interpretable Models (Wang) 2019 Pan et al.) 2020 Wang & Lin 202I): predictors that involve the cooperation of an interpretable model and a complex black box. At inference time, any input is assigned to either its interpretable or complex component based on a gating mechanism, see Figure [ (a). The intuition behind this type of modeling is that not all examples in dataset are hard to classify.
2

---

Published in Transactions on Machine Learning Research (08/2024)
The model's transparency is defined as the ratio of samples that are sent to the interpretable part (Wang 2019 Pan et al.] 2020; Wang & Lin, 2021). The higher the transparency, the more model predictions can be understood and certified. However, the interpretable component could make more errors than its complex counterpart. Therefore, an integral part of Hybrid Interpretable Models is to empirically explore the racuraayy trade-off and find the best compromises, see Figure 1 (b). Note that the accuracy- transparency trade-off becomes something we mcasure and optimize.
Despite their high potential, Hybrid Interpretable Models remain under-studied in the interpretability /ex-- plainability literature. One of the reasons could be that learning interpretable models is very hard (often NP-Hard), and fitting Hybrid Interpretable Model on top can only be harder. To address this issue, past studies have optimized such models using simulated annealing heuristics (Wang) 2019; Pan et al. 2020). More specifically, they employed a rule-set/mule-list as the interpretable component and trained it by ran- domly adding/ weemoving/pemmttiiii
rules for fixed number of steps. Nevertheless, we show empirically that the stochasticity of these simulated anncaling heuristic hinders the ability of practitioners to consistently atlain a larget level of transparency. Given the recent development of highly efficient libraries for training interpretable models to optimality (e.g., CORELS for rule-lists (Angelino et al., 2017), GOSDT for decision trees (Hu et al. 2019)), it may now be possible to train Hybrid Interpretable Models to optimality, even when adding a hard constraint on transparency level.
To encourage additional research, we offer a fundamental investigation of such models from three perspec- tives: Theory, Taxonomy, and Methods, focusing on binary classification for the Theory and Methods parts. From the theory point of view, we explore Hybrid Interpretable Models. The aim of this guarantee is not to provide tight bounds directly relevant to practitioners, but rather to highlight the potential generalization benefits of sharing samples between a complex and simple model. This is evidenced by a sweet spot of the bound's tightness w.r.t the model trans- parency. Secondly, we provide a general taxonomy for the different ways of training Hybrid Interpretable Models: the Post-Black- Bor and Pre-Black-Boz paradigms. These approaches differ in the order in which the interpretable and complex components are trained. We show where slate-of-the-ar Hybrid Interpretable Models fall in this taxonomy. Thirdly, we implement the two paradigms in a single method: HybridCORELS, which extends the library CORELS. By leveraging CORELS, HybridCORELS provides a certificate of op- timality of its interpretable component and precise control over transparency. We finally show empirically that HybridCORELS is competitive with existing Hybrid Interpretable Models, and performs just as well as a standalone black box (or even better) while being partly transparent. To resume, our contributions are:
Correct (PAC) generalization bound of
We theoretically study Hybrid Interpretable Models under the PAC-Learning framework and derive a generalization bound. We show that said bound depends on the amount of data classified by each component of the Hybrid Interpretable Model and that an optimal transparency value exists.
We introduce a laxonomy of Hybrid Interpretable Models' learning methods, identifying two main families: the Pre- Black-Boz paradigm and the Dost-Black-Bor Bor paradigm. We instantiate the pro- posed Pre-Black Bor paradigm using notion of black-bor specialization via re-weighting. In a nutshell, within the Pre-Black- Box paradigm, input regions handled by the black-box are known be- fore it is trained. Thus, one can specialize the black-box on said regions by assigning larger weights to the appropriate training samples.
We review state- ofrtre-rtttett methods for learning rule- based Hybrid Interpretable Models, and show that they all fall into the
Bor category.
We extend the CORELS algorithm for learning optimal rule lists into HybridCOREI.Spor and HybridCORELSp... which learn rule-based Hybrid Interpretable Models within the Post- Sett-Back--anr and Pre- Pre-Black- Black- paradigms respectively. Both implementations provide optimality guarantees in terms of training accuracy and explicit control of the model tronsperency.
We empirically compare HybridCORELSpie and HybridCORELSpos with state-of-the-ar methods for learning rule-based Hybrid Interpretable Models. Both methods offer competitive trade-offs between accuracy and transparency.
3

---

Published in Transactions on Machine Learning Research (08/2024)
(a) Example of a region S (shown thick square) where complex model he He (with [Hel 2 overly complex.
(b) The complex model he can be replaced by simpler one h2 E Hs (with [Ha] 2*). The Hybrid Interpretable Model has size |Hyb] = 224
Figure 2: Toy example with X = 10, 1] x [0, 1]. Here the complex models He are all the ways to color the 36 width-1 squares. The simpler models H. are all the ways to color the width-2 squares in the middle.
2 Hybrid Interpretable Models: a Theoretical Analysis
This section formally introduces Hybrid Interpretable Models and analyzes them under the PAC-Learning framework. A generalization bound is derived and the potential benefit of sharing samples between models is highlighted.
2.1 Definitions
Let X' be the input space and let He, He be two sets of binary classifiers h: : X {0, 1). We shall impose that [H., < |Hel < 0o so that H. represents simple set of models while He represents a complex set of models. Finally, we let P be a set of subsets of X' (for instance, P may be the power set of X, or the set of linear half- spaces). The intuition behind Hybrid Interpretable Modeling is that there may exist a region Qt E where complex model he E He overkill and could be replaced by simpler model h, H. without significant drop in performance. Formally, a Hybrid Interpretable Model is a triplet (he hy Q2 E Hyb = He H.s that instantiates function of the form
i E Ω hc(x)) otherwise.
(2(())
Væ E X. (he, (g. =
Figure 2 presents an informal argument favoring this modeling choice. We will additionally assume that the smaller hypothesis space Hy involves models that are interpretable such rule lists, sparse decision trees, scoring systems, etc. This assumption will not affect the theoretical analysis, which will just rely on |H,| being small, but it will specify the desiderata of the Hybrid Interpretable Models. Indeed, if h, is interpretable, then we would like the region Ω on which it operates to be as big as possible without hindering performance. The size of Ω is called the transparency.
Definition 1 (Transparency) Letting D be a distribution over X {0, 1} representing the binary classi- fication task and Dx be its marginal over X, the transparency
Cn
P x E Ω2
(1)
D>
is the ratio of samples sent to the interpretable component. In opposition, the opacity CT = P PANDA is the ratio sent to the black-box.
lx E 52
The rest of this section is structured as follows: in Section 2.2 we prove that finite Hybrid Interpretable Models (i.e., |Hyb] < oo) are PAC-Lcarnable. That is, if we fit them using a finite dataset with sufficiently many examples, then generalization to unscen samples is guaranteed. Afterward, Section 2.3 studies the impact of transparency the bound, and "sweet spot" for transparency is highlighted.
4

---

Published in Transactions on Machine Learning Research (08/2024)
2.2 PAC-Learnability
The PAC-Learnability framework requires the Realizability Assumption (Shale-Shwarrz & Ben-David 2014 Definition 2.1).
Assumption 1 (Realizability) There exists a model (he, hgg Str) E Hyb that makes perfect predictions on the distribution D over X x 10.1}:
(2.y)~ ho((he, = P
Nh h (x) * y] =
(2)
Intuitively, the predictions of the optimal Hybrid Interpretable Model (he (2)) match the true label y for any possible input æ.
To learn such model, we can employ the Empirical Risk Minimization (ERM) principle, which consists of sampling dataset of M iid examples S = {(x!1, ,y ) Ddd, defining the empirical risk
M
Es( hus 21)
Σ
1lher h, (x) + y
(3)
and minimizing it across Hyb
(hes h, 22s FF):))(S())
arg min Es( ha 92)- (l)
Notice that we do not scale the empirical risk by a factor NY does not affect ERM. Solving Equation 2.2 difficult because it requires fitting two models h2 he as well the partition over which they operate. Yet, if the optimal partition O is known in advance, it could be treated fixed so that ERM only focuses fitting h2 and he-
1 seeing as multiplication by a constant factor
Assumption 2 (Oracle Region) Given Hyb and distribution D that respect Assumption one has oracle access to the optimal region ft* Consequently, ERM sets Q = Q* and focuses on fitting he and he.
Theorem Given |Hyb| < oo and some > 0, for any distribution D where Assumption 1 holds, the following is true for any training set size M:
IP SNDM
P IColho he 1)s) > > Σ
Ble, Ca. He, Ho,
OEP
with
Ble, Ca. He, Ho, H), = (1-1Hol- H. - + -Hole -eM +MH.MMHHHHHHH..... Cre (/H)) Additionally, if Assumption holds, the bound tightens
S~DD [Co((he, he, 9) > 5 B(c, Car, He. He. M).
(4)
Proof The complete proof is provided in Appendix A
This generalization bound involves several key quantities: the amount of data M, the transparency Co and opacity O7 as well as the complexities of the hypothesis spaces [Hal and [Ho]- The coming subsection presents how these various parameters impact the bound.
These theoretical bounds have several limitations. First, taking Co 0 leads to trivial bound of 1. The same thing occurs when setting Co 1. Basically, the bound is trivial unless input samples are shared between the complex and simple models. Sccondly, the bound requires the knowledge of transparency On = P E Ω] which cannot. be computed exactly in practice since the data-generating distribution D is unknown. The only way to practically estimate this quantity to count how many data instances land in the region Z Thirdly, the bound can be loose as computation relics on applying the union bound repeatedly over P, He, and Hs. Still, for Ca E|0, 1[, and any e EJ0, 1] the bound decreases as M increases which implies that learning Hybrid Interpretable Models is possible in theory.
5

---

Published in Transactions on Machine Learning Research (08/2024)
(a) Region f
(b) Region 922
(c) Region Ω2
(d) Region f2
Figure 3: Four Hybrid Interprotable Models that are functionally equivalent but have different regions Ω.
2.3 Fine- Tuning the Transparency
Q**) from Equation 2 need not be unique. Indood, given the flcxibility of choosing the region on which the simple model is applied, we could have two models with the same functional output. Figure presents a toy example of four Hybrid Interpretable Models that all functionally equivalent but with different regions Ω
A particular property of Hybrid Interpretable Models that the optimal model h,,
Consequently, the Assumption 2 that grants oracle access to Ω could be generalized to give access to a set of optimal regions { Which region should then be returned by the learning algorithm? Using the empirical error as a criterion would not work, since any ERM fitted using these optimal regions would return an error 0. A more principled approach is to select the region based on the generalization bound. Fixing some region Q2 for the ERM algorithm, Equation provides an upper bound B(e, Co. Has H. M) on the probability of exceeding the error e. To render the analysis independent of the choice of a specific threshold c, we invostigate the Average Bound
B(Ca, He, Hy, M): /'' min ((, Cn. He, M) de
(5)
function of the transparency Cp. The minimum between 1 and the bound is taken to avoid trivial bounds for probabilitics. Note that B(Cn, He, Hy, M) takes values in [0, 1] and is smaller than 1 if and only if there exists an error e that occurs with probability PSSDDM [LD( (he, ht, I)s) c] <.
Example Let H. as the set of all binary depth-3 decision trees (7 internal nodes and 8 leaves with binary outcomes) fitted on 20 binary features (X' {0, 1)22). This hypothesis space has size |Hs = 2 x 20 x 192 18* 1.94 10 Let He be any hypothesis space that is larger than H. by some factor [Hel] N [Ha]. Figure (b) presents the Average Bound function of transparency. Given He, Hs. and M, there is "sweet spot" where the Average Bound is smallest
Ch arg arg B(Co, He, Ha, M). CaE(o.1]
(6)
Looking more specifically at Figure (a). increasing N reduces the optimal transparency. Simply put, the more complex He, the more input samples must be sent to h2 to avoid overfitting. According to Figure $ (b), the optimal transparency does not seem to vary with M, at least when N = 100. Figure 4 (c) illustrates the generalization bound as function of when fixing the transparency to its optimal value. We note that the bound is informative since tells us that the true risk is unlikely to exceed 10%, 20%, 40% in various settings.
We conclude this example by emphasizing that Figure 4 is mostly of theoretical interest, practitioners must take it with a grain of salt. More precisely, the exact values of the "sweet spot" for transparency are not indicative of the values one would obtain in real-life experiments. This because our analysis performed on an upper bound, which we hope still captures the generalization dynamics of Hybrid Interpretable Models. In real-life applications, the existence of an optimal transparency must be assessed experimentally.

---

Published in Transactions on Machine Learning Research (08/2024)
M--20
M0-00 N-11
Band BIC
M-400 N-1K
Avegge Bound B.
66
M-1100
M-400
N-100K
6.18
Co
0.5-
M-200
M-500 N-100
6.17
644
Bic
M-1000,
0.4
0.00-
N-1000
N0000000
0.3
0.5
0.3
0.6
0.0
0.2
10.0
1.0
Transpaency Ch
Transporercy Ch
Ernor
(a) Varying N with M 400.
(b) Varying M with N = 100.
(c) Varying M and N.
Figure 4: (a)&(b) Average Bound B function of transparency Ca- We observe "sweet spot" with min- imal Average Bound, which depends on N (ratio of the hypothesis spaces' sizes [ (c) The corresponding generalization bounds when fixing Cg to its optimal value. Note that the bound is informative and tells us that the true risk unlikely exceeds 10%, 20%, 40% in various settings.
2.4 Takeaways & Improvements
Although the bound makes strong assumptions that may not hold in practical applications, our theoretical analysis leads to fundamental insights:
1. Training Hybrid Interpretable Models is theoretically possible given enough data.
Important parameters that influence generalization are the complexities [H,,] and Hell the trans- parency Cn, and the number of data points M.
3. There exists "sweet spot" of the bound in terms of transparency, suggesting that sharing inputs between simple and complex model can improve generalization. Later in the manuscript, this will be demonstrated empirically on the COMPAS dataset, see Figure 12 (c).
There are many ways to improve our gencralization bound, left for future work.
First, the bound should be extended to account for infinite hypothesis spaces He and H. (e.g. linear models with few and many coefficients) whose complexity can be characterized with the VC Dimension Rademacher Complexity (Mohri et al., 2018). This extension is not trivial because bounds based on the VC Dimension employ Sauer's Lemma (Shalev-Shwarlz & Ben-David 2014 Lemma 6.10), which only holds when M is larger than the VC Dimension. However, bounds for Hybrid Interpretable Models must account for the possibility of sending very few samples to either h, of ha- We envision leveraging Binomial tail inequalities to bound the probability of these undesirable events.
Second, the Roalizability Assumption (Assumption 1 should be removed, allowing for imporfect optimal models CD (hh ht (tt)*=== > 0. In that case, the Agnostic- Agnostie-PAC-Leanee PAC-Learnability framework (Shalev-Shwartz & Ben- David 2014 Definition 3.3) should be used to bound the probability of failure PS- [CD((he, heg U)ss) (D( hgg )2*))++++ + c]. Such guarantees would be obtained by leveraging uniform convergence bounds based on the VC Dimension or Rademacher Complexity.
Third, PAC-Bayes guarantees (Alquier et al.) 2024) could tighten the union bound over all regions Ener by specifying a prior probability distribution over P favoring high transparency regions. This would allow to get rid of Assumption 2 Additionally, PAC-Bayes offer an alternative characterization of infinite He and H..

---

Published in Transactions on Machine Learning Research (08/2024)
3
Learning Hybrid Interpretable Models: Taxonomy and Methods
We now introduce our proposed taxonomy of Hybrid Interpretable Models learning frameworks. We then show how rule-based classifiers can be used lo implement Hybrid Interpretable Models. Finally, we position state-of-the-art methods within the proposed taxonomy.
3.1 Taxonomy of Hybrid Interpretable Models Learning Frameworks
A major challenge in training Hybrid Interpretable Models is that two models must be trained instead of one. Given the proliferation of out-of-the-box implementations of complex model he; such as Scikit-Leary and XGBoost classifiers, it would be simpler to rely on them via their pre-existing fit and predict methods. Henceforth, we encourage Hybrid Interpretable Model training procodures to be agnostic to the type of black-box he-
We now leverage the previous PAC generalization bound to derive a learning objective. As a reminder, we defined in the previous scction the data-generating distribution D, the training set == ((x )] DM, training imputs Sx (x(() R= and the transparency Cn == Pa [ar E Q] [Sx n /|//Sx) also demonstrated that two important quantities influencing generalization are the complexity of the simple hypothesis space H₂ and the transparency Cg- Since "smaller is better" in any learning objective, we should The learning objective would then be
actually minimize the opacity C = |Sx [f]/
obj( h. (Q. 5) [he har + X KN, +B SS U
[
[Sx
where KH, is complexity measure of Hy and X.3 > 0 are regularization hyperparameters that control the complexity of H. and the opacity Ca. Equation 7 presents the learning of Hybrid Interpretable Models in its most abstract form and we shall make it more specific shortly. We first present several ways to minimize the objective over the space Hyb = He x H. x P that differ on the order in which h2 and he are trained.
3.1.1 The Bost-Black-Ba Box Paradigm: Wrapping an Interpretable Model around the Complex One
The Post-Black- Box paradigm consists of training the black-box first and then fitting the interpretable model and regions on top. The interpretable components h, and Ω can thus be seen regions where it is overkill. A key advantage of this paradigm is that users owning a pro-trained black-box with high performance can easily wrap an interpretable model on top of it to get an increase of transparency. Furthermore, because it fitted after the black-box the interpretable model h, can be trained with the knowledge of the black- box mistakes, and specifically try to capture the corresponding examples and classify them correctly. In such case, effectively corrects these misclassifications from the perspective of the overall Hybrid Interpretable Model. We illustrate the Post-Black- Boz paradigm in Figure (Top).
simplification of he in
3.1.2 The
Box Paradigm: Black-Box Specialization by Reweighting
In the Pre-Black-Be Boz paradigm, the simple model h, and region Ω are fitted first, and the black-box is trained on the remaining examples. To avoid overfitting when training the black-box on few samples (since the number of examples left to the black-box can be arbitrarily small), we propose to leverage a weighted training set with higher weights to instances (1) and smaller (but non-zero) weights to instances (+)) E Ω
c [
( eQ]
Wi (1,2, M), W;
(8)
== e 1 [ali)en]
The non-uniform weights rely on a specialization coefficient a 2 0: the higher a, the more he focuses on data in Q. The hyperparameter a is fine-tuned in practice. Figure 5 (Bottom) illustrates the Pre- Black- Bow paradigm pipcline. We note that many classifiers in the Scikit-Learn and XGBoost packages support non-uniform data weights in their training procedure. Hence, the Pre-Black- Box paradigm is also black-box-agnoste
8

---

Published in Transactions on Machine Learning Research (08/2024)
Fit h2 and S on top
Dataset S
Train he
Train hs and
Fit he with weights wi
Figure 5: Two paradigms for learning Hybrid Interpretable Models. (Top) In the Post-Black- Black-BBzz paradigm, a black-box first trained on the whole dataset. Then, the interpretable components are fitted on top of the black-box to simplify it regions where it overkill. (Boutom) In the Pre-Black Box paradigm, the interpretable part of the model is trained identify a region where the task is simple. Afterward, the black- box model is fitted the data with specialization weights wy to encourage high performance instances outside Q. Here, the weights visualized the markers' size.
3.2
Modeling
One of the important design choices of Hybrid Interpretable Model is the space of possible subsets Ω where the interpretable model will operate. An example from previous work model these sets via hyperplanes (Wang & Lin 2021 An alternative is to employ rule-based model (e.g., rule list rule set) and define Ω2 as
2r = fx E X' cover 1).
where cover(r, x) if respects the condition in at least of the rules in The advantage of using rule-based models to partition the input space is that they are interpretable by design, hence they can also serve as the simple hypothesis space H.. That is, we can assign label to an input depending on which rule captures it.
if 18 & Age $ 22 and gender-male then return y ==
else if Prior-Crimes then return y
else
return (x)
Since a rule-based model encodes both the region Ω and the simple function h, on this region, we can think of rule-based Hybrid Interpretable Models as a tuple (herr) E Ho x H, instead of a triplet (her ha Z). The lcarning objective on the training set S bocomes
obj( S) Es((her)) [S]
[Sx n 1
|r| +
(9)
18x
where we measure the complexity of by its length |r].

---

Published in Transactions on Machine Learning Research (08/2024)
1.0
1.0
0.8
0.8
Transparency
Transparency
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
10-3
10-2
10-1
10"
10-3
10-2
10-1
10
(a) COMPAS dataset
(b)
UCT Adult Income dataset.
Figure 7: Instability of the Transparency of HyRS for different random seeds. A very small jitter applied to the points to remove juxtapositions.
3.3 Rule-Based Post-Black-Box Hybrid Interpretable Models
Now that we have introduced several learning paradigms as well as rule-based Hybrid Interpretable Models, we describe two methods from the literature that apply the Post- Black- Boz paradigm with rule-sets and rule-lists.
3.3.1 Hybrid Rule-Set (HyRS)
This model has been introduced by Wang (0199) and considers a rule set r = r+ Ur_ that combines set of positive rules r++ and a set negative rules r.. The resulting tuple (he, r) takes the form of Figure
if cover(r4, then return else cover(r-,.*) then return clsc
The complexity of the interpretable model is the total number of rules Irl and the learning objective of Equation 9 is used. The minimization of this combinatorial problem is tackled by a simu- lated annealing search algorithm where neighborhoods are defined as random perturbations of the rule-sets r+ and r-..
return hx(x)
Figure 6: Hybrid Rule-Set.
One of the drawbacks of HyRS that the user does not have precise control over the transparency Cg. There are two design choices in HyRS that lead this issue. First, the only way to control the desired transparency to increase the hyperparameter to incentivize larger rule coverage. Still, because soft constraint is used, one has to conduct line search over 3 to get the desired transparency. Secondly, since the local search algorithm employed to find the rules is inherently stochastic, several runs of the training procedure with the same hyperparameters can lead to very different models and, by extension, different transparencies. Figure shows different reruns of HyRS on two datascts for 20 different values of that span four orders maguitude. We see that the relation between transparency and I is hardly monotonic because of the variance between reruns. Moreover, the transparency does not vary smoothly w.r.t as in the UCT Adult Income dataset, where the transparency jumps from 0 to 0.5 around 8 = 10
3.3.2
Companion Rule-List (CRL)
An alternative method called Companion-Rule-Ine (CRL) has later been developed order to address previous limitations (Pan al. 2020). Notably, CLR streamlines the transacyy tradeoff by returning multiple Hybrid Interpretable Models with increasing transparency. To how, given rule list.
10

---

Published in Transactions on Machine Learning Research (08/2024)
8-
6-
Run
Run
4-
2-
2
0.00
0.25
0.50 Transparency
0.75
1.00
0.00
0.25
0.50 Transparency
0.75
1.00
(a) CRL COMPAS
(b) CRL Adult Income
0.70
0.82
0.69
Accuracy
Accuracy
0.80
0.68
0.78
0.67
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9 1.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7 0.8
0.9
1.0
Transparency
Transparency
(c) HybridCORELS on COMPAS
(d) HybriCCORELS on Adult Income
Figure 8: Comparison between the test set transparencics attainable by CRL and HybridCORELS. (a)&(b) The transparencies yielded by CRL runs with various random seeds, each indicated by a different color. (d) Test set accuracies and transparencies resulting from many runs of HybridCORELSS with various transparency constraints Cmin E [0.2, 0.3, 0.4, 0.5, 0.7, 0.9.
insert the black-box at any level of the else-if statements. For instance, Figure g presents three tuples (he, r) that are derived from the same list of three rules ra)
if cover(r1, æ) then return 1
if cover(r1. x)) then return 1 else if cover(r2, œ) then return 0
if cover(r1, x) then return 1
else
else if cover(r2, x) then return 0
return hx)x)
else
else if cover(rs, x) then return
return he (z:
else
return he(x))
Figure 9: A rule list r [Fi, ra) encodes three Hybrid Interpretable Models (herr) with increasing transparency (from left to right).
Returning multiple Hybrid Interpretable Models allows users to decide what Hybrid Interpretable Model to use based on their desired transparency. The training objective of CRL no longer the accuracy but rather the Area- Under-the- Curve (AUC) of the Models. A regularization À |r| is used to avoid long rule-lists. Similarly to HyRS, CRL is trained with
curve of the different Hybrid Interpretable
11

---

Published in Transactions on Machine Learning Research (08/2024)
simulated annealing search algorithm where neighborhoods are defined as random perturbations of the rule-list r. Although CRL offers more possibilities for transparency, we find that the inherent stochasticity of the learning procedure still hinders the ability to consistently reach target transparency. Figure S (a)&{() present experiments conducted on the COMPAS and UCI Adult Income where a CRL model was fitted for 10 different random seeds. The different levels of transparency attained by each run are presented as colored lines. For the COMPAS dataset, if user wishes for a transparency of at least 0.5, then on half of the runs, they would need to go up to about 0.75 transparency. For Adult Income, if end-user requires transparency of at least 0.25, then half of the runs, they would need to go up to 0.5 transparency.
The coming section will introduce HybridCORELS, an alternative framework for fitting Hybrid Interprotable Models where desired transparencies are imposed via a hard constraint
SSx n
2 Cmin
(10)
[Sx]
rather than soft one. As presented in Figure (c)&(d), if a user targets transparency Cuin E [0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9), the resulting test set transparency remains close to constraint Coii Unlike
Figure 7 (b) and Figure g (b), we do not observe transparency jump from 0 to 0.5 on the Adult Income dataset.
4 HybridCORELS: Learning Optimal Hybrid Interpretable Models
We now present our algorithm to learn optimal Hybrid Interpretable Models. First, we introduce the CORELS algorithm, initially proposed to learn optimal rule lists. Then, we describe the integration of a hard constraint on transparency. Finally, we propose HybridCORELSpor (respectively, HybridCOREISpe)) a modified version of CORELS to learn optimal Hybrid Interpretable Models within the Post- Black- Box (respectively, Pre-Black- -Bla) framework.
4.1 Learning Optimal Rule Lists: the CORELS Algorithm
Rule lists are interpretable classifiers formed by an ordered list of if-then rules r, followed by a default prediction go [Rivest 1987). The set of ordered rules preceding the default prediction called a prefix. One can observe that any rule list d = (r, represents a classification function, while any prefix defines partial classification function, defined within its support 2 (examples matching at least one of the rules within r)
To learn Certifiable Optimal RulE ListS, Angelino et al. (2017) proposed CORELS, a branch-and-bound algorithm. It represents the search space of rule lists using a prefix tree, in which each node corresponds to a prefix r. Adding a default prediction qo to r allows the building of a rule list d = vo). In CORELS' prefix tree, the children nodes of r correspond to prefixes formed by adding exactly one rule at the end of
r. Thus, the r-rooted sub-tree corresponds to all possible extensions of r. CORELS objective function for rule list d (r) on dataset S is a weighted sum of classification error and sparsity:
Es(d) + X-Irl
obj(d, S) = [S]
(11)
where Ls(d) measures the number of errors (incorrect classifications) made by d on S (as defined in (3) and |r| is the length (number of rules) of rule list d's prefix r.
Let S, = S n (St, 13) be the subset of S captured by some prefix r. Just like any branch-and- algorithm, CORELS uses an objective lower bound to prune the prefix tree, and eventually guide the scarch in a best-first search fashion. For each node of the prefix tree (corresponding to a prefix r), it measures the best objective function value that may be reached by extending prefix r. If this value is worse than the best solution known so far, then the r-rooted sub-trce can be pruned safely. Let Ls, (r) count the number of mistakes made by prefix (measured on its support set Sr), and incons(S) denote the minimum number of examples of S that can never be classified correctly, because they have the exact same features vectors
12

---

Published in Transactions on Machine Learning Research (08/2024)
some other examples, but with different label. CORELS' objective lower bound for prefix r dataset S is then computed as follows:
lb(r, 5) Ls, (r) incons(S") S.) (Irl + 1)
(12)
||]
Intuitively, Ls, (r) incons(S S,) corresponds to the minimum number of errors that any extension of can make, given the errors made by r and the errors that can not be avoided due to data inconsistency. CORELS uses several efficient data structures to speed up the computation by breaking down symmetries (Angelino itt al. 2017 For instance, a prefix permutation map ensures that only the most accurate permutation of every set of rules is kept. The CORELS pscudo-code presented as Algorithm [ Appendix B.2
Because it performs global optimization, CORELS builds state-of the-art rule lists in terms of predictive accuracy. On the contrary, exact methods which do not require rules pre-mining do not scale well, and greedy approaches which are very popular for learning decision trees usually produce badly performing rule lists. Sections 4.3 and 4.4 will describe how the objective function [1] and its lower bound [12] can be modified to Iearn Hybrid Interpretable Models within the Post-Black- Bor and Pre-Black Box paradigms.
4.2 Ensuring Definee Transparency Level
As seen in Sections 3.3. 3.3.2
employing a hard constraint on transparency
SSp
2 Cmin
(13)
|s]
rather than a soft one (i.e., through a regularization coefficient as done within HyRS/CRT) allows for more precise control over the test set transparency. To enforce constraint (13) using the CORELS branch-and- bound algorithm,
modify the best solution update subroutine, to only perform the update operation if the candidate prefix satisfies the transparency requirement. This guarantees that any returned solution will satisfy [13 while maintaining optimality as the exploration and bounds are not modified.
13 ensures the strict respect of a user-defined transparency level, we also integrate transparency using a regularization term 3. (SS S.I[SS. This allows to break ties: two models exhibit the same accuracy and sparsity levels, then this regularization term will favor the one with higher transparency. In practice, we set the associated regularization coefficient 3 & value small enough to only break ties B A.
Even constraint
4.3 Post-Black-oo framework: HybridCORELSpor
We now introduce HybridCoRELSyos. a modified version of CORELS producing optimal Hybrid Inter- pretable Models within the BosttBlack-Bor Boz paradigm. More precisely, HybridCORELSped first trains a black-box model (or takes as input pre-trained black-box model). Then, given a minimum transparency constraint 13 it builds prefix optimizing the overall model's accuracy and sparsity.
Objective Given black-bor box he's training set predictions, HybridCORELSpor builds prefix capturing at least proportion of Cmin of the training data (transparency constraint (13)) and minimizing the following objective function:
objpost (r, 8) == Es((har r)) + + 1 3-
|S SS
|S|
[S]
(14)
+ (
1S S.1
+ +
|r|
+ B.
[
[S]
Objective lower bound CORELS original objective lower bound 12 is still valid and tight in this setup, so we do not need to modify it. Indoed, the crror term lower bound Ls, (r) + incons(S") SS) is unchanged, as all remaining black-box errors Lsys, may potentially be corrected by extending r, but the errors already
13

---

Published in Transactions on Machine Learning Research (08/2024)
made by prefix and those related to remaining inconsistencies can not be avoided. Then, the transparency regularization term can not be used within the objective lower bound, as this term can always reach 0 by sufficiently extending prefix r. Finally, the lower bound over the sparsity regularization term still holds: any extension of prefix r must have at least |r| + rules.
Finally, HybridCORELLSees the smallest among those satisfying the transparency constraint (13). This means that, given fixed black- box predictions and desired transparency level, it produces an optimal Hybrid Interpretable Model in terms of securay/spparsity. We provide the HybridCORELSper pseudo-code as Algorithm 2 in the Appendix B.3
an exact method: provably returns a prefix r for which obj (r, S) 14 is
4.4 Pre-Black-Box framework: HybridCORELSPre
HybridCORELSpee is the first algorithm to implement our proposed prefix optimizing accuracy and sparsity, given a minimum transparency constraint (13). Then, it trains the black-box part by specializing it on the uncaptured examples, using the weighting scheme (S) As aforementioned in Section 3.1.2] the Pre- nee-Black-Bol paradigm intrinsically limits the possible collaboration between both parts of tuple r), as is not possible for the black-box part to correct the mistakes made by the interpretable part. However, it possible to consider the inconsistencies left to the black-box part while training the interpretable part, which implements a form of collaboration.
Boz paradigm. It first builds
Objective HybridCORELSpp builds prefix capturing at least Cuin of the training data (transparency constraint (33 and minimizing the overall classificat ion error lower bound (based on both prefix r's errors and the inconsistencies let to the black-box part) and sparsity:
obipre (r, ST Lss (r) + incons(S (.)) A- 1-111++ 8-
|8 \ S.
(15)
S
[S]
where the error term Σs, (r) + incons(S \ S.)) counts the errors of (herr) assuming the black-box performs perfectly. It hence provides tight bound Ls. (r) + incons(S \ S,) argmin, Ls((her)))
12 (leveraging both the pre- fix's errors and the inconsistent examples among the uncaptured ones) is still valid and tight in this setup, we do not need to modify it. Indeed, the error term is tight: it is not possible for any extension of r to avoid the errors already made by r nor the inconsistencics within the remaining examples. The sparsity term is also light as any extension o must have a length of at least |r|+1. As for HybridCORELSPeet the opacity term can not be used within the objective lower bound, as can always reach 0. An interesting observation is that lb(r, S) > objpre ST) for any prefix (since < X as indicated in Section 4.2 This means that, for any prefix satisfying the transparency constraint 13 will not be extended since this can only worsen its objective. So, prefix extensions are only performed in order to meet the transparency constraint (3)
Objective lower bound CORELS' original objective lower bound lb(r, S)
Finally, HybridCORELSpr is an exact method: it provably returns a prefix r for which obipre (r, (r, S) 15)
is the smallest among those satisfying the transparency constraint (13). This means that, given desired transparency level, produces an optimal prefix (interpretable part of the final model) in terms of (he, r) accuracy upper bound and sparsity. If the black-box performs perfectly, then the overall model is cortifiably optimal. We provide the HybridCORELSp.. pseudo-code as Algorithm 3 in the Appendix B.3
We additionally introduce in the Appendix C another possible implementation of the Pre-Black-A paradigm based on the CORELS algorithm but optimizing an objective function different from that of HybridCORELSpe.. This new variant HlybridCORELLSsee.oooo NoCollab learns a prefix by maximizing its accu- racy on the subset S,, without accounting for the task left to the black-box part. Appendix C.I provides a description of this algorithm and Appendix C22 empirically compares it with HybridCORELSpee The experiments confirm that SybridCORELSSpe.Nee to high transparency regimes, due to the lack of collaboration between both parts of the (he,r) tuple.
is not competitive with HybridCORELSp.. in medium
14

---

Published in Transactions on Machine Learning Research (08/2024)
5 Experiments
In this section, we empirically evaluate our proposed algorithms. We first introduce our experimental setup. Then, we use HybridCORELSpre to show that the Pre-Black- paradigm is suitable to learn Hybrid Interpretable Models, and we report the impact of the specialization coefficient on the performance of the black-box. Afterward, we compare HybridCORELSpie and HybridCRRELSpet with two thie-ooftthe-rtt methods: Hybrid-Rulc-So (HyRS) and Companion-Rule-Tie (CRL).
5.1 Setup
Datascts In experiments, consider several datascts with various prediction tasks and sizes:
The COMPAS datased datasef[ Janalyzed by Angwin et al. 2016 contains 6,150 records from criminal offenders in the Broward County of Florida collected from 2013 and 2014. The corresponding binary classification task is to prodict whether person will re-offend within two years.
The UCI Adult Income dataset (Dua & Grall 2017 stores demographic attributes of 48,842 individuals from the 1994 U.S. census. Its binary classification task is to predict whether or not a particular person makes more than 50K USD per year.
The ACS Employment dataset DDng et al. 2021] is an extension of the UCI Adult Income dataset that includes more recent Census data (2014-2018). The goal is to predict if a person is em- ployed/unde unemployed based on 10 sociocconomic factors. The specific dataset contained information on 203,358 constituents of the Texas state in 2018.
Rules mining To ensure a fair comparison between Hybrid Interpretable Models, we pre-mined a set of rules T for each dataset. The prefixes were then restricted select rules r T so any difference performance is solely attributable to the learning algorithms and not the quality of the rules. To mine the rules, the datasets were first binarized using quantile for numerical features and one-hot encoding for calegorical features. Then, the FP-Growth algorithın (Han et al.) 2000) was applied to identify rules of cardinality 1-2 and support of at least 1%. To these sets of rules, we also added the negation of each rule in the original binarized dataset. Finally, the 300 rules with the largest support were kept to generate Y. We ended up with [ = 230 rules on COMPAS and [T] = 300 on the UCI Adult Income and ACS Employment datasets.
Black-boxes In all experiments we used the following Scikit-learn Pedregosa et al. 2011 classifiers an AdaBoostClassifior, and a Such black-boxes are in line with the setup considered in the literature (Wang) 2019). We further detail the hyper-parameters tuning of these models in sections 5.2 and 5.3 We note that the Hybrid Interprotable Models studied (HyRS, CRL, and HybridCORELS) are not tied to any specific black-box, nor to a specific implementation. Indeed, they are black- back--bx--aee box- agn-ssic by design.
black-boxes: a RandomforestClassiiien
Implementation details Our algorithms HybridCORELSpe.. and HybridCORELSp.. (as well its HybniäCCoRELLPre..occcaaa variant discussed in the Appendix C are integrated into a user-friendly Python module, publicly available on PyP and GitHul They build upon the original CORELS (nnellno et al. 2017) C++ implementation and its Python wrapper All experiments are run on a computing grid over a set of homogeneous nodes using Intel Platinum 8260 Cascade Lake @2.4Ghz CPU.
HybridCORELS transparency regularization coefficient B setting In all our experiments us- ing HybridCORELSp.. or HybridCOEELSpes. we set the transparency regularization cocfficient 3 min( 2 ))) to only break ties but ensure that no accuracy nor sparsity will be rraded-off for transparency.
http:://gthabb.ccm/rrreeeeesse/
http://gttaab.cc//creel///yggg
15

---

Published in Transactions on Machine Learning Research (08/2024)
5.2 Exploring the Black-Box Paradigm
Objective The objective of this subsection is to assess the appropriateness of the Pre-Black-Bil paradigm for learning accurate tuples (he, r). To this end, we use proposed algorithm implementing this framework: HybridCRRELSpee depicted in Section 4.4 More precisely, we explore the effect of the specialization coefficient on the accuracy of the black-box.
Setup For the three datasets presented in Section 5.1 experiments are run for five different train/test splits, with 80% of the data used for training and the remaining 20% for testing. We use HybridCORELSp to produce r) for several transparency levels: low (0.25), medium (0.5), high (0.75, 0.85) and very high (0.95). For the prefix building part, we optimize the hyperparameters of HybridCORELSp. using grid search over the following values: À E {10-?, 1003, 10 10=4), miRsupport E {0.01, 0.05, 0.10), and the objective-guide lower-bound- guided, and BFS search policies. For each experiment, the prefix yiclding the best (training) accuracy upper-bound (considering the prefix's errors as well as the inconsistencies left to the black-box part, as depicted in 15 is retained. The Scikit-learn (Pedregosa et al. 2011 black-boxes are chosen to with default parameters, with min sarl___mpll______ = 10 and max mar__epth 10. The black-boxes are finally trained using different values for the specialization coefficient a, ranging from (no specialization) to 10 (highly specialized).
be either an AdaBoostClassifin parameters and a Random/ooestClasssfff
BraddeentBostinnaassffii
with default
Results
We first assess the performance of the learned prefixes at various transparency levels by reporting
1 Σs, (r) + incons(S SS)
(16)
[S]
which upper bounds the full model accuracy 1 Es((he, r))|[S), Looking at Figure 10 we note that the upper bound decreases for larger transparencies, implying that prefixes with larger support make more errors. Additionally, since prefix transparencies on the training set are very close to the enforced coistraint, there must be a conflict between accuracy and transparency. Indeed, if a prefix with very high accuracy and transparency were available, the learning algorithm would systematically select it irrespective of the transparency constraint. We finally observe that transparency generalizes well: the test set transparency levels are very close to the training set ones.
Once the prefixes are learned, we study the effect of the specialization coefficient on the performances of the downstream black-box. More precisely, for several values of a, we report in Figure I1 the train and test set black-box accuracies
Esys, (ho) \ Sp1
(17)
for the adasoostClassifier. Results for the two other black-boxes are publicly available on our GitHub repository Note that this accuracy only involves data samples that land outside the support of the prefix, and so it is not representative of the overall accuracy 1 - (s((her))//S)) We focus three different transparency levels: low (0.25), medium (0.50) and very high (0.95), since the trends observed for high and very high values (0.75, 0.85 and 0.95) are the same.
At a first glance, specialization (a 2 1) appears to improve test black-box accuracy compared to non- specialization (a = 0). For ACS-Emppoy with 0.95 transparency, specialization leads to a 2ppts improvement in test accuracy. Morcover, 0.95 transparency regimes on Adult Income enjoy 1ppt accuracy increase when setting 1.
To more systematically assess the benefits of specialization, we define the improvement rate the proportion of runs (out of all our performed experiments) for which given value of 2 1 led to an improvement of black-box test accuracy I7 compared to setting a = O. Investigating an improvement rate, rather than an average accuracy over reruns is necessary because different accuracies vary greatly between datasets. Over
httpfr//gghhhaaocoooooooo//rrrer reaults..s
16

---

Published in Transactions on Machine Learning Research (08/2024)
0.77
0.79
0.9
0.9
Overall Arcuracy Upper Bound
0.78
Actual Profix Covarage
0.8
Coverage
Accuracy Upper
0.77
0.75
0.76
0.6
0.6
0.74
Actual
0.74
0.4
0.4
0.72
0.72
0.3
0.5
0.7
0.7
0.9
Min. Transparency Constraint
Min. Transparency Constraint
(a) ACS Employment dataset.
0.90
Overall Accuracy Upper Bound
0.87
0.8
0088
Coverage
Actual Prefix Coverage
Overall Accuracy Upper
0.88
0.86
0.6
0.87
0.6
0.86
0.84
0.4
0.4
0.84
0.3
00.3
0.83
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Transparency Constraint
Transparency
(b) UCI Adult Income dataset.
0.76
0.710
0.9
Overal Accuracy Upper Bound
Overall Accuracy Upper Bound
0.75
0.705
0.8
Actual Profix Caverage
0.74
Actual Prefx Coverage
0.7
0.700
0.73
0.6
0.72
0.5
0.71
0.5
0.690
0.1
0.70
0.685
-0.3
0.69
0.3
0.3
0.4
0.6
0.7
0.8
0.9
0.9
Min. Transparency Constraint
Min. Transparency Constraint
(c) COMPAS dataset.
x Overall Accuracy Upper Bound (train)
Overall Accuracy Upper Bound (test)
Actual Prefix Coverage (train)
Actual Prefix Coverage (test)
Figure 10: Training and test. performances of the prefixes learned using HybridCOREISSpee We report the /tait/test transparencies and accuracy upper bound (Equation 16 The plots show both average values and standard deviation across the five runs with different random seeds.
17

---

Published in Transactions on Machine Learning Research (08/2024)
Transparency (0.25)
Medium Transparency
Very High Transparecyy
0.730
0.729
0.720
0.710
0.728
Black Box Accuraty
0.715
Bleck Box Accuracy
0.727
0.700
BlackBox
0.726
0.705
0.690
0.724
0.723
0.695
0.670
10
10
Specialization Coefficient
Specialization Confficient
Specialization Confficient
(a) ACS Employment dataset.
Transparency (0.25)
Medium Transparency
Very High Transparency
0.792
0.778
0.720
Accurecy
Black Accuracy
0.776
BlackOox Accursty
0.715
0.790
0.774
0.705
0.700
0.772
0.788
0.770
0.690
0.685
10
Specielization Coefficient
Specialication Coefficient
Specialization Coefficient
(b) UCT Adult Income dataset.
Low Transparency (0.25)
Medium Transparency (0.50)
Very High Transparency (0.95)
0.650
0.750
0.670
Back Box Accuracy
Black-ox Accuracy
0.700
0.665
0.630
BiockBox
0.620
0.600
0.610
0.655
0.550
10
10
10
Specialization Coofficient
Specialization Coefficiint
Specialization Confficient
(c) COMPAS dataset.
Accuracy (train)
Accuracy (test)
Accuracy (test)
Figure 11: Training and test accuracy (Equation 17 of the black-box h, (AdaBosttClassifier)) learned using HybridCORELSpee on different datasets, for different transparency levels. The plots show both average values and standard deviation across the five runs with different random seeds.
18

---

Published in Transactions on Machine Learning Research (08/2024)
all experiments with the AdaBoottCaasiifer black-box, the improvement rate was highest for a 2, with value of 93.33%. The improvement rate was 73.33% for = 5, and only 66.6% for a 8.
Experiments with the other two black-box types confirm that the improvement rate is higher for moderate specialization a E {1,2]. Consequently, a general "rule of the thumb" is to set a to or 2. For simplicity, the remainder of the manuscript will employ this basic rule. Nevertheless, the optimal specialization problem dependent, and so future work should investigate tuning with cross-validation.
We end this section by noting a peculiar pattern: the test set performances presented in Figures 10 are often better than the training set performance. This might suggest that data leakage is occurring, leading to overoptimistic performance assessment on test. In Appendix D we lay these concerns to rest by demon- strating that the overall lest. accuracies 1 - (she r)) are lower than their training set counterparts. The illusion that test performances are "too good" is induced by the fact that Figures & II do not report actual accuracics.
5.3 Tradeoffs and Comparison with the State-of-the-Ae
The aim of this subsection is to explore the trade-offs between the accuracy and transparency of several Hybrid Interpretable Models: : the state-of-the-art HyRS and CRL methods, as well as our proposed HybridCORELSPat and HybridCORELSpe algorithms. These experiments serve the secondary purpose of advertising the considerable amounts of transparency that can be attained while maintaining high perfor- mance.
Objective
Setup For these experiments, each dataset was split into training (60%), validation (20%), and test (20%) sets. We randomly generate five such splits and average the results over them. More precisely, for each split, the training set is used to train the models (the prefix and the black-box). The prefix and black-box hyperparameters are optimized using the validation set. Finally, the resulting Hybrid Interpretable Models are evaluated on the test set. Note that while we hereafter focus on such test performances, the training and validation curves show similar trends, and the associated results are all provided on our GitHub repository"
We, we detail the training and hyper-parameters optimization procedures for the prefixes and black-boxes.
Tee-Black-Boo method setup The experiments using the HybridCORELSp- algorithm are divided into two phases. First, for each dataset (out 3) and each random split (out of 5), we learn prefixes on the training 0.9, 0.925, 0.95, 0.975)). The following hyperparameters values are tried x E {10-2, 10-3, 10-4), minr E {0.01, 0.05, 0.10), and the objective-guided, lower-bound- guided, and BFS search policies for HybridCORELSpe. prefix learning is limited to a maximum CPU time of hour and a maximum memory use of 8 GB. For each experiment (dataset random split minimum transparency), the prefix yielding the best validation accuracy upper bound is kept. In second phase, for each retained prefix, we try three different Scikit-learn (Pedregosa et al.) 2011) black-boxes: RandomForestCClassiiiee an AdaBostCCaassifier and a using the Hyperopt (Bergstra et al. 2013) Python library and its Tree of Parzen Estimators (TPE) algo- rithm, with 100 iterations. Just like the prefixes in the first phase, the black-baxes are trained using the training split (60%) and the hyperparameters are selected based on the validation split (20%) performances. Note that, as for the training set, the validation set loss is weighted to encourage the black-box to accurately classify the examples belonging to f. Based on the observations from Section 5.2 we adopt a rule of thumb and set the specialization coefficient a = 1, which corresponds to moderate black-box specialization. Op- timizing the value of a using the separate validation set (as is done for the other hyperparameters) would be possible, and would likely improve the results, since sticking to one configuration does not allow adapting to the different scenarios. We chose to not do so and let the choice of a as an interesting rescarch avenue, order to keep the size of the hyperparameters' grid comparable among the different methods.
set with 12 different minimum transparency constraints (Cmiu E [0.1, 0.2,
Each
The black-box hyperparameters are tunod
19

---

Published in Transactions on Machine Learning Research (08/2024)
Best-Black-Bor methods setup Three methods correspond to the Post- Best-Black-Bil Box paradigm: HybridCORETI.pet HyRS (Wang] 2019) and CRT. (Pan et al. 2020). The experiments using these meth- ods are divided into two phases. First, for each dataset (out of 3) and each random split (out of 5), we train three different Scikit-learn (Pedregosa et al. 2011 black-boxes: a RandomforestClassiffi AdaBoostClassifier, and a Frradiiettoostingllassssss
an The black-box hyperparameterss are tuned us- ing the Hyperopt (Bergstra et al. 2013) Python library and its Tree of Parzen Estimators (TPE) algorithm, with 100 iterations. The black-boxes are trained using the training split (60%) and their hyperparameters are selected based on the validation split (20%) performances.
In the second phase of the experiments, we train the interpretable parts (he:r) for the three com- pared methods, using the he learned in the previous phase. The prefix training is performed on the training split (60%), while the hyperparameters values are selected based on the validation split (20%) performances. For HybridCOREL.Spet we consider 12 different minimum transparency con- straints (Cmin E [0.1, 0.3. 0.8, 0. 0.925, 0.95, 0.975)), and the following hyperparametors values: A E (100- 10-3, 10= muport {0.01, 0.05, 0.10), and the objeclive-guided, lower--ound-guided,, and BFS search policies. For the HyRS method, similarly to Wang (2019), we use 10 different values for its À hyperparameter (ranging logarithmically from 10-3 to 10 10- and 10 different values for its 8 hyperparameter (ranging logarithmically from 10-3 to 10%). For CRL, we consider 10 different values for its temperature hyperparameter (ranging linearly from 10 to 10-2) and 10 different values for its À hyperparameter (rang- ing logarithmically between 10 and 10- For all three methods HybridCORELSpee the hyperparameter grid is roughly of size 100. As in the HybridCORELSp. experiments, prefix building is limited to maximum CPU time of 1 hour and a maximum memory use of 8 GB.
HyRS, and CRL,
Final results computation After trying out all hyperparameters, we are left with a Pareto front repre- senting the Hybrid Interpretable Models that are not dominated in terms of both validations set accuracy and transparency. Still, since the black box and its prefix were fine-tuned on the validation set, we argue that this Pareto front an over-optimistic description of the true generalization of (he,r). For this reason, we decided to take the Pareto-optimal models validation, and compute their accuracy and transparency on the test set, which has not been used yet in this experiment. Hence, we can obtain unbiased measures of the accuracy and transparency for these models. These final measures of accuracy/ / transparency are used to compare the different approaches and assess whether increasing transparency can lead to equivalent /better generalization.
Results The lest set accuracy/traassparenc trade-offs of the different Hybrid Interpretable Models are shown in Figure 12 for each dataset and blx type. We highlight three main insights from these results.
First, on almost all datasets and black-box types, the methods HybridCORELSpe and HybridCORELSpe.. are better or equivalent to HyRS and CRL. The only exception HybridCOREI in high transparency regimes (0.85-1.0) on the ACS Employment dataset. HybridCORELS offers competitive trade-offs because, given a transparency constraint, it builds the prefix that provably maximizes accuracy, exploring the whole search space of prefixes through a global optimization method. In Figure I we show an example tuple (he,r) for each of the four methods fitted on the same data split (train haaiii/vaaaaaiioooo (ttttt) of the ACS Em- ployment dataset with an AdaBoost black-box. These models were selected on the basis of having the highest test accuracies for a test transparency between 0.6 and 0.8. We note that HybriCOREESSp, and HybridCOREII.pea are competitive with CRL and even employ similar rules, for example, ("age_ _iihh"hhhh" and "Female"], ["Reference person" and "No di disability"], and ["age_high" and "Native"]. HyRS on the other hand, performs worst than the other three since it has a lesser accuracy and transparency.
Second, using HybridCORELS on the ACS Employment and UCI Adult Income datasets, one can reach high transparcncy values (0.7) while retaining the same performance as the black-box (0.0 transparency). This observation is consistent across all black-box lypes, which suggests that complex models are often overkill in certain regions of the input space and can safely be replaced by a simpler model on those inputs. From the point of view of ccrtiffctiion/maittaance /maintenance of a machine learning model, being able to assign a majority of inputs to an interpretable component is tremendous step forward. For instance, since rule lists are interpretable, one might be able to certify that the prefix works properly/safel. on the region Ω, that
20

---

Published in Transactions on Machine Learning Research (08/2024)
0.74
0.74
0.74
Accuracy
Accuracy
0.73
0.73
0.73
0.72
0.72
0.72
0.71
0.71
0.71
0.78.0
0.78.0
0.78.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Transparency
Transparency
Transparency
(a) ACS Employment dataset.
0.85
0.85
0.85
0.84
0.84
0.84
Accuracy
Accuracy
Accuracy
0.83
0.83
0.83
0.82
0.82
0.82
0.81.
0.81
0.8
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Transparency
Transparency
Transparency
(b) UCT Adult Income dataset.
0.68
0.68
Accuracy
Accuracy
Accuracy
0.67
0.67
0.67
0.66
0.66
0.66
0.65
0.65
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Transparency
Transparency
Transparency
(c) COMPAS dalaset.
CRL
HyRS
HybridCoRELSPost
HybridCORELSPre
Figure 12: Test set accuracy/transparecc tradc-offs for various Hybrid Interpretable Models and datasets. The Pareto front. for each method is represented as a line and the filled bands encode the std across the five data splits. Results are provided for several black-boxes: (Left) AdaBoost, (Middle) Random Forests, (Right) Gradient Boosted Trees.
21

---

Published in Transactions on Machine Learning Research (08/2024)
If [*age_ ["age_nedd _nd_inndd"" and "No Cognitive difficulty"] then if ("age_high") then
else AdaBoost ()
(a) HyRS: Test Accuracy 72.8%, Transparency 64.3%
if ""age_high" and "Fenale"] then 0
else If "'gg_hhigh" and "Mative"] then
else if *Rafarence person" and "No disability"] then else if "Hueband/vile and "No disability") then if ('Cogaitive difficulty" and *not
householder"] then
else
AdaBoost
(b) CRL: Test Accuracy 73.7%, Transparency 75.8%.
then 0 else if ('Husband/vife" and "Male"] then
if ("Disability" and
else if ['age_ highh and "Mative" then else if "'ag_hhigh" and "Fanala"] then else if
''eeference person" and "No disability"! then else if ['Bachelor degree"] then 1
AdaBoost() ()
(c) HybridCOREL.Sp. Test Accuracy 74.0%, Transparency 70.1 %.
['age_bigh" and "Fensle"] then else if ['usband/vifee and *No disability"] then else if h'age_high" and "Mative" then
else if [*aaterance person" and "No disability"] then else
AdaBoost
(d) HybridCORELSP... Test Accuracy 73.7%, Transparency 73.0%.
Figure 13: Example of Hybrid Interpretable Models obtained by the diffcrent mothods on the same data split of the ACS Employment datasel with a AdaBoost black-box.
if PPrior CCines=0" and "Age >=30"] then 0 else ["Prior Crimen >5* and "Aga=24-30" then else "Prioor -cr crines=1-8 and "Age>=30" then else RandomPorest ()
(a) HybridCREELSpe: Test Accuracy 68.1%, Transparency 42.7%
Figure 14: Example Hybrid Interpretable Model obtained by HybridCOREL.Sp.. on the COMPAS dataset with a Random Forest black-box. Consistent with Figure 12 this model generalizes better than the black- box alone.
will contain the majority of examples seen in deployment. For the minority of instances that fall outside the region, certification might require the verification of the opaque decisions by committee of domain experts. Such verification might be time-consuming but, the higher the transparency, the fewer examples this committee would need to verify regularly.
Third, when studying HybridCORELSpe fitted on COMPAS, one can consistently observe a "sweet spot" for transparency where the generalization is maximal and even better than the standalone black-box. The existence of such "sweet spot", highlights the regularization effect of sharing inputs between a complex and simple model. This generalization improvement is mainly observed with the HybridCOREISS.. method,
22

---

Published in Transactions on Machine Learning Research (08/2024)
which constitutes an argument in favor of the Ce-BBlac--oor paradigm. We report in Figure 14 example model learned with HybridCOREI.Spe box. As we observe, just adding three simple rules before the black-box model allows for test accuracy improvements. Note that keeping the same performance while increasing transparency is also desirable (as was the case with the ACS Employment and UCT Adult Income datasels).
COMPAS, which generalizes better than a standalone black-
6 Conclusion
In this paper, we laid the foundations for a promising line work that was initiated some years ago: hybridizing interpretable and black-box models "take the best of both worlds' (Wang 2019 Pan et al., 2020 Wang & Lin 2021). More precisely, we first provided theoretical evidence that such models have generalization advantages, while also being easier certify and understand. We then proposed taxonomy of learning algorithms aimed at producing such models, along with generic framework implementing the (new) Pre-Black- Box paradigm. We introduced algorithms belonging to two identified paradigms, namely Pre- Pre-Black- Box and Post- Black- Compared to otate-of-the-art methods, our proposed approaches, coined HybridCORELSpre and HybridCORELSpput certify the optimality of the learned models and provide direct control over the desired transparency level. Our experiments demonstrated the ability of the proposed Pre- Black- Boz paradigm and the high competitivity of our algorithms with the state-of-the-ee Furthermore, empirical findings suggest that this new paradigm may lead to better-generalizing models. Investigating the reasons for this observation is interesting future work.
Studying Hybrid Interpretable Models that are not rule- based is a promising research avenue. Going beyond rule lists would require adapting other optimal search-based learning algorithms- for instance those producing optimal sparse decision trees instead of adapting CORELS as was done in this work. Moreover, the value of the specializalion coefficient a was set via a. "rule of thumb" and optimizing its value with cross-validation on a problem-by-proline by-problem basis an important research direction. Finally, beyond the Box frameworks, could envision third end-to-end paradigm where the black-box and simple models are trained simultaneously. While this approach could provide global optimality guarantees, it is also very challenging because two models must be optimized within unique framework.
Box and
7 Broader Impact Statement
Hybrid Interpretable Models explore the accuracy-trrassparenc, trade-offs, but they do not address the lack of explainability of black-box models. As a result, Hybrid Interpretable Models are not adequate for critical systems where explanations are required for any model decision. This is because the few decisions relayed to the black-box box cannot be faithfully explained. Rather, Hybrid Interpretable Models are potentially useful for tasks where imperfect explanations are sometimes acceptable. In such settings, the interpretable component can be used to get the "big picture" of the model behavior, while post-hoe methods (e.g. LIME and SHAP) can be used to get imperfect explanations of the black-box on "edge cases".
Moreover, a rule-based model is only as good as ils premined rules. A poor collection of rules can cause performance degradation but also discrimination. Indeed, as evidenced by Figure 13, rule-based models can discriminate basod on protected attributes such as gender and ethnicity. Consequently, we caution against the premature use of our work and advocate that practitioners exclude protected attributes from their rules before applying HybridCOREIS.
23

---

Published in Transactions on Machine Learning Research (08/2024)
References
UIrich Aīvodji, Hiromi Arai, Olivier Fortineau, Sébastien Gambs, Satoshi Hara, and Alain Tapp. Fairwashing: the risk of rationalization. In International Conference on Machine Learning, pp. 161 170. PMLR, 2019.
Uhrich Aivodji, Hiromi Arai, Sébastien Gambs, and Satoshi Hara. Characterizing the risk of fairwashing. Advances in Newral Information Processing Systems, 34:14822 14834, 2021.
Pierre Alquier et al. User-friendly introduction pac-bayes bounds. Foundations and Trendso in Machine Learning, 17 2024.
Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo I. Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. J. Mach. Learn. Res., 1-234:1-233::7 2017. URL
http://jmlr httpa///rrr/pppppe//////////11-1 11tm11mmmm.m111
Julia Angwin, Jell Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. propublica (2016). ProPublica, May, 23, 2016.
Maisa Cardoso Aniceto, Flavio Barboza, and Herbert Kimura. Machine learning predictivity applied to consumer croditworthiness, Future Business Journal, 6(1):37, 2020.
Haris Aziz, Ágnes Csch, John P. Dickerson, and Duncan C. McElfresh. Optimal kidney exchange with im- munosuppressants. In Thirly-Fifee AAAI Conference on Artificial Intelligence, AAAI 2021, Thirly- Third Conference on Innovative Applications of Artificial Intelligence, LAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 21
29. AAAI Press, 2021. doi: 10.1609 16609/AAALTT /A/AAAALLL331111007 URL https://doi.org// 1609/ v3511.
16073
James Bergstra, Daniel Yamins, and David Cox. Making a science of model search: Hyperparameter op- timization in hundreds of dimensions for vision architectures. In International conference machine learnóng, pp. 115 123. PMLR, 2013.
Leo Breiman. Classification and regression trees. Routledge, 2017.
Mark Craven and Jude Shavlik. Extracting treo-structured representations of trained networks. Advances in neural information processing systems, 8, 1995.
Botty Dimanov, Umang Bhatt, Mateja Jamnik, and Adrian Weller. You shouldn't trust me: Learning models which conceal unfairness from multiple explanation methods. In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang (eds.), ECAI 2020- 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Sontiago de Compostela, Spain, August 29 September 2020 Inchuding 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pp. 2473 2480. IOS Press, 2020. doi: 10.3233 FF2233//A022035 URL https://doii httt:::///oiiorg/o.... 3233/FFAA22000080
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Newral Information Processing Systems 34: Annual Con- ference on Newral Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 6478 6490, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.iit ics. uci edu/
m
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM compaling surceys (CSUR), 51 (5):1 1-24 2018.
Jiawei Han, Jian Pei, and Yiwen Yin. Mining frequent patterns without candidate generation. ACM sigmod record, 19 2000.
24

---

Published in Transactions on Machine Learning Research (08/2024)
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advonces in Neural Informa- tion Processing Systems, 32, 2019.
Gabriel Laberge, Ulrich Aivodji, and Satoshi Hara. Fooling shap with stealthily biased sampling. arXiv preprint ar Xiv:2200.. 154 19, 2022.
Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Interpretable & explorable approxi- mations of black box models. arXiv preprint vrXie:170.001133 2017.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Aduances in neural information processing systems, 30, 2017.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Danqing Pan, Tong Wang, and Satoshi Hara. Interpretable companions for black-bos models. In Interna- lional conference on artificial intelligence and stalisties, pp. 2444 2454. PMLR, 2020.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and dala mining, pp. 1135 1144, 2016.
Peter R Rijnbeck and Jan A Kors. Finding short and accurate decision rule in disjunctive normal form by exhaustive search. Machine learning, 80(1):33 62, 2010.
Ronald L. Rivest. Learning decision lists. Mach. Learn., 2(3):229 246, 1987. doi: 10.1007/BF000056680
URL
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use inter- pretable models instead. Nature machine intelligence, 155):206 215, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 180-186, 2020.
Berk Ustun and Cynthia Rudin. Supersparse linear integer models for optimized medical scoring systems. Machine Learning, (3):349-39) 391, 2016.
Tong Wang. Gaining free or low-cost interpretability with interpretable partial substitute. In International Conference on Machine Learning, pp. 6505-6514 PMLR, 2019.
Tong Wang and Qihang Lin. Hybrid predietive models: When an interpretable model collaborates with black-box model. J. Mach. Learn. Res., 22:137 1, 2021.
25

---

Published in Transactions on Machine Learning Research (08/2024)
A Proof of Theorem 2
Theorem 1 Given |Hyb] < oo and some > 0, for any distribution D where Assumption 1 Sollowing is true for any braining set size M:
holds, the
P SNDA
((hee h, 01s) > o Σ
B(e, Cn, He, Hs, M),
OEP
wilh
(e, Cst, He, Has M) = (1-17al- Hs -eds C 110++(11 -1111t1|-1HHa eM 1 +|Hol| *+Cn)
Additionally, if Assumplion holds, the bound lightens
P [CD Ns, R)s) > e) S Ble, Car, S~DM
H Hes Hy. M).
(18)
Proof The distribution D is fixed apriori and our only assumption about it is that perfect triplet (hr, hr (2) E Hyb exists. Consequently, we must have Es( has 2)s) = O. Given e > 0, our main objective to upper bound the probability PS-DM (Cp((he, [S h, {2)s) > c| which corresponds to the proba- bility of "failure" by the ERM model. Letting Hyb, = {(he, h, Q2 E Hyb Lo((he, Q)) e) be the set of all "failing" models, we have that
P L hr {)ss > >
((e: ((h has 22 Hyb, with Es( h2 {i)
SWDD
(19)
P SWIM
Bhe h2 E Hyb, with Es h, 2) O].
REP
where we have used the union bound over all Ω E P. From this point on, we will assume that the domain Ω is fixed. Consequently, the distribution D be seen a mixture of two distributions De, D. with disjoint have D C2DD Cn,, The edge cases supp(D) C. 9 and supp(D) lt are
supports Q and Ω. Formally, covered by setting Cn 1, 1, = and =0 c= respectively. Sampling from such a mixture distribution D is a two-step process. First, one chooses a number of instances m ~ Bin(C M) from a binomial law of M trials and probability Cn of success. Then one samples m simple examples Sg ~ D and samples M m hard examples S. ~ DMM- This leads to
(he hr Q) E Hyb, with Es((he, h. 2)) =0]
SwDA
P
BBee hs 22) E Hyb, with Es.us, hsys2)) =
m.BBin(Cn,.M. 5m-Dth S.-D.--m
(20)
M
b(m;
P S.-D
B(ee h,, E Hyb, with Es.us, (fhes h, 12)) = 0],
0=0
Se-DAi
where b(m; Ca, M) = 0 and m M that occur with probability CM and C.M. The issue here is that one must bound the population loss of the whole Hybrid Interpretable Model while only one of its sub-models is evaluated on empirical data. This is solved by using trivial bounds
= (M M- are the binomial coefficients. This formula has two edges
Q
IP
B h2, Q) E Hyb, with Σs. (ha) =
S_
(21)
( h Q) E Hyb, with Es (h₂) = $ 1.
8, S
Assuming Cn E,0, 1[, the probability of these edge cases occurring goes to zero as M + co, and the triviality of Equation 21 becomes irrelevant.
26

---

Published in Transactions on Machine Learning Research (08/2024)
Case 0 m M Since the expected loss can be rewritten
CDl h2s Q2) = CTLD, (he) + CaLD,
we have that
(ho Se e and LD, (ha) S c CD((hor No, 92)) S E,
which implies
(he, h,, 2) E Hyb, = he E Ho, or hg E Ha,e. where He.e == the E Ho (h.) >e and Ha,s := (h, E H, LD, (hg) > E} are the sets of complex and simple models "failing" on the distributions D. and D., Note that the "or" in (22) is not exclusive and both parts of the model may fail simultaneously. Therefore, the following holds
(22)
F Sy-Dm
[h has 22) E Hyb, with Ês.us, ((he hs (1) 0]
P S, SenDhf
11 E Hes s.t. (he) = 0} or {3 E Hole s.t. L.s. = 0}]
P
Bhe E Ha,e stt. (h(h)) = +
IP S-Dm
3hg E Ha,e stt. sh)).) = 0]
S-D m
- Hele ((M c(M + |
where we have used the inequality PS-Dy [3, E Ha, s.t, Es(h)) = 0] < H2.ee (Equation 2.9 Shalev-
Shwartz & Ben-David (2014)), and a similar one for He. Going back to Equation 20 we get
P SWDD (3eh, h2, 22 E Hyb, with Es((her hes 22) =
M
b(m; Ca
[3 hsr 22 E Hyb with Es.us. (he, hr (2)
S.D SanDirm
M-1 l
< SCM
+ CN -
bmm; Co, M) ()Hoeeeee-MMMMMM + |Holl
m=1
M-1
CM
CM
|Hc
b(m; Co. M)e M + |74
Σ
b(m; Cr. M)e cm
0
m=1
M-1
CM 12
CM
|Hc
b(m; CT,Y M)e + -1H,1
Σ
b(m; Ca. M)e -em
(1 - |Htl - |7L le
JC + +(1 - --Hal - |HL cM
JCM
+
1
M
Hel
Σ
b(m: C.. M) + +776ol
Σ
b(m; Ca. M) em
m==
m=0
(1 - He 17 eM -cM JCM + +(1 17,
HHll -M )
11
|Hol + Cn + + + AM = B(c, Cn. He, Hs.M)
In the last step, the following identity was used identity
M
6(m; Co. M)e (Che Cr)
Finally, combining this with Equation 19 leads to the desired result
IP [LD(( hy ()s)
Σ
B(c, Ca. Ho, M).
SwDA
DEP
27

---

Published in Transactions on Machine Learning Research (08/2024)
Under Assumption 2 stating that the optimal region Ω is known in advance, the proof is the same except that no union bound over Q E P is required because ERM is guaranteed to return the region Q
B Pseudo-Codes of the HybridCORELS algorithms
While the CORELS algorithm and our proposed HybridCORELS variants were already introduced in Sec- tion 4 we describe them in more detail in this appendix section. We first introduce some necessary notation that we later use to provide a dctailed pscudo-code and description of the CORELS algorithm. We then depict our proposed variants HybridCORELSPoa and HybridCORELSppe for learning Hybrid Interpretable Models.
B.1 Notations
To formally describe the pseudo-code the CORELS algorithm and those of our modified HybridCORELS variants, we first need to introduce some more detailed notation. As mentioned in Section 4.1 a rule list d consists in an ordered set of rules r, called a prefix, followed by a default decision go- Then, we note: d = qo). Each individual rule ry involved within prefix r consists of an antecedent a, ("if" part of the rule, consisting in Boolcan assertion over the features' values) and consequent qi ("then" part of the rule, consisting in prediction). We note: Ti a; + yú and r ... with |r] the length of prefix r.
B.2 CORELS
The pseudo-code of the CORELS algorithm is provided within Algorithm I As mentioned in Section 4.1, CORELS is branch-and-bound algorithm exploring a prefix tree, in which each node corresponds to prefix and its children are prefixes formed by extending r. At each step of the exploration, the nodes belonging to the exploration frontier are sorted within priority queue Q, ordered according to a given search policy. CORELS implements several such policies, including Breadth First Search, Depth First Search, and several Best First Searches. While these policics define the order in which the nodes of the prefix tree are ordered (and may affect the convergence speed), note that they do not affect optimality, and must all lead to the same optimal objective function value given sufficient. time and memory. At each step of the exploration, the most promising prefix is popped from the priority queue Q (line 4). If its lower bound is greater than the best objective found so far (i.e., it is discarded. Otherwise, it is used to build rule list by appending a default prediction go (line D If the resulting rule list d has a better objective function than the best one reached so far, the current best solution is updated at line g Finally, each possible extension of r formed by adding a new rule at the end of r gives a new node which is pushed into the priority queue at line 12 The exploration is completed (and optimality proved) once the priority queue is empty. Note that efficient data structures are used to cut the prefix tree symmetries: for instance, prefix permutation map ensures that only the best permutation of every set of rules is kept.
not lead to rule list improving the current best objective function),
B.3 HybridCORELS
A key difference between our proposed HybridCORELS algorithms and the original CORELS is that our methods aim lcarning prefixes (expressing partial classification functions) while CORELS' purpose is learn rule lists (classification functions). Both HybridCORELSpes. and HybridCORELSp.. return prefixes (and not rule lists) and take input an initial best known prefix Td satisfying the transparency constraint (while the original CORELS takes as input I satisfying the transparency constraint is a constant majority prediction: yd + [[True + qu)] (whose transparency is 1.0). In practice, we use such trivial initial solution for all our experiments.
initial rule list d²). A simple choice for the initial prefix
The pscudo-code of HybridCOREISSpe a different objective function (14) at line 6. aimed at evaluating the overall Hybrid Interpretable Model's performances. One can note that the computation of the new objective function objpost (r; S) requires access
provided in Algorithm 2 Key modifications include the use of
28

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm CORELS
Input: Training data 5 with set of pro-mined antecodents T; initial best obj(d", 5)
known rule list d such that
Output: (d', ,²*) in which d' rule list with the minimum objective function value
1: (d t 2d
2: + (=queue(()
Initially the queue contains the empty prefix () Stop when the queue is empty
3: while Q not empty do
4: r+ x-pol)
if lb(r, S) < 2" then
d + (r)
Set default prediction go to minimize training error Compute objective obj(d,
Ed( + +r-rrl
= obj(d, 5) |8|
8:
2 < 2" then
(0) t (d,
D. Update best rule list and objective Antecedent not involved in Set a's consequent to minimize training error > Enqueue extension of with new rule Tnew
10:
for in Y (a; Fr, Er,r; = -4) do
11:
Tnew (a +0-))
12:
Q.push(r U knew)
13:
(d' ;-"=²*) (9)
Algorithm HybridCORELSPe..
Input: Training data with set of pre-mined antecedents T; minimum transparency value Cmin; initial prefix r0 such that 1S,al [ST 2 Cmin; pre-trained black-box model he Output: (r",2") in which is a prefix with the minimum objective function value 1: (r". (r) + (r9,2%)
2: Q (-queue(()
b Initially the queue contains the emply prefix () Stop when the queue is empty
3: while Q not empty do
r r+ x-popp((
if lb(r, < 2 then
= Ess (he) + x . + |svs.| [S]
6:
[8]
> Compute objective objpost (r, S)
if = and S. 2 Cmin then
7:
(19,29) t 2r)
b Update best prefix and objective Antecedent not involved in r D Set a's consequent, to minimize training error > Enqueue extension of with new rule Tnew
for in T {a, 3r, Er.r, a. do
10:
Tnew (a +
11:
Q.push(r U Unew)
12:
(r*, f- (r)
to the pre-trained black-box les which is part of the algorithm's 's inputs. The original CORELS" lower bound is valid and tight for our new objective (as discussed in Section 4.3 so we keep this computation unchanged at line Finally, to ensure that the built prefix satisfies a given transparency constraint 13 this condition is verified line before updating the current best solution line
The pseudo-code of HybridCORELSp.. provided in Algorithm Again, the objective function computa- tion is modified line e to use proposed obipre (r, S) objective 15 As before, the original lower bound is
still valid (as discussed in Section
4.4) so we leave it unchanged at Tine 5 Just like for HybridCOREILSp..o
the transparency constraint 13 is checked line right before the current best solution update (line 8 Once the optimal prefix y* is known, the black-box part can be trained (which is not represented in the pseudo-code) using our proposed specialization scheme as described Section 3.1.2
Finally, both our proposed approaches are anytime: the user can specify any desired running time and memory limits, and the algorithm returns the current. best solution and objective value (r if one of the
29

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 3 HybridCORELSpr.
Input: Training data S with set of pre-mined antecedents T; minimum transparency value Cmlni initial prefix r0 such that |S,a|
[S] 2 Cmin
Output: (r",²") ) in which 1" is prefix with the minimum objective function value 2¹
1: (x",29) + (r",2")
Q ((quueu(())
Initially the queue contains the empty prefix ( Stop when the queue is emply
while Q not emply do r r+ +-poopp(
if 1b(r, < then
2 + Eincomsin A |r| B. 18.8. [S]
Compute objective objpre (r. S)
[S]
7:
if < 2 and 2 Cmin then
[8T
8:
(0),2) t (r,
D Update bost prefix and objective D Antecedent not involved in r Set a's consoquent q to minimize training error
9:
for a in r {a, | a
10:
Fnow + (a + Q.pus((r knew)
11:
Enqueue exlension of with new rule Tnew
12:
(r" 2²) + (9)
limits is hit and the priority queue is not empty. Even optimality is not guaranteed in such case, the ability to precisely bound running limes and memory prints very practical feature for real-life applications.
C Another Bee-Black-Boo Implementation for HybridCORELS
In this appendix section, we describe another possible implementation of the Pre-Black- Bor paradigm based on the CORELS algorithm but optimizing a different objective function. We discuss the theoretical differ- ences with the HybridCORELSy.. algorithm introduced in Section 4.4 and empirically compare the two methods.
C.1 HybrddCORELSpe.Ncca.n Theoretical Presentation
We now introduce another possible variant of CORELS implementing the coin it HybridCORFFISSrx.xccalll
does not account for the task left paradigm. We because contrary to the HybridCOREI.S... algorithm introduced in Section 4.4 the prefix learning phase of HybridCCRRELSSse..ooo. to the black-box part. Instead, the prefix is learned to maximize its own accuracy, which results in the remainnin examples (that will be handled by the black-box model) being the hardest ones to classify, While black-box spocialization could be helpful to deal with such difficult tasks, we observe that, in practice, has to deal with many inconsistent examples, which considerably lowers its performances.
Objective HybridCORELSp NoCullab builds a prefix capturing at least proportion of Cunin of the training data (transparency constraint 13 and minimizing the weighted sum of r's classification error and sparsity:
obj pre (r, (r) [S,
S Szl [
+ +r B.
(23)
Objective lower bound CORELS' original lower bound 12 does not hold for objective function (23
Indeed, the difficulty here that objpre.nocollab quantifies a prefix's error only on the subset of examples that it classifies (S,), hence is possible directly consider the inconsistent examples incons(S \ S,) in lb (1 extension of may not capture them at all. To obtain tight lower bound Ib Ibpre.nocollab: one noeds consider simultancously the support S, and errors (r. of prefix r, as well as the labels cardinalities among each group inconsistent examples (also called set of equivalent points in the context of CORFLS (Angelino al. 2017)). A pre-processing step computes list G of inconsistent groups of ezamples.
30

---

Published in Transactions on Machine Learning Research (08/2024)
Each group g G.g C S is defined by its number of minority examples ming (those with the least frequent label among group g), and its number of majority examples majg- In fact, our previously introduced count of unavoidable errors uses such groups for its computation: incons(S) = Egeg (ming). For each group g E G not captured by prefix r (g & Sy); we verify whether capturing its examples could lower the current peefx'' min, maingtmag
(s)(r) [.
error rate: Cp.9 =
Then:
Es, (r) Egeg.gEs, Cp.g" -ming
Ib lbpre.nocollab(r S)
SSp1 + Enerarss Saa" (ming + majg)
+ (K,+
(24)
Finally, loprecnocollab precisely quantifies the best objective function that can be reached based on prefix r, by only capturing inconsistent groups of examples that improve the objective function (lowering the error rate). The definition of Cp.g uses a less or equal operator because in case the error rale is unchanged after capturing additional group of inconsistent examples, the operation should be performed as it would increase the coverage (and the associated regularisation term). There exists (partial) classification function whose crror rate is exactly the one computed in ibpre,nocollab, so this bound is tight.
Finally, SyyrrdCCORELSpe.Nocca 23 the smallest among those satisfying the transparency constraint (13) This means that, given desired transparency level, produces an optimal prefix (interpretable part of the fi- nal model) in terms of accuracy/sparsityy The pseudo-code of DorridCORRIISSppeacacllil is similar to that of HybridCORELSpp presented in Algorithm 3 except that the objective function obj (r, S) and lower bound lb(r, S) on lines 6 and are replaced by obipre,noentaa(rr S) and Ibpre,nocollab(r. S), as introduced in equations 23 and 24
is an exact method: it provably returns a prefix r for which
(r, objpre.nocollaa S)
Again, note that within this proposed implementation, the prefix learning phase does not consider the difficulty of the task let to the black-box learning part. For datasets containing inconsistent examples, this could result in sub-optimal overall accuracy in regimes of medium to high transparency, when collaboration between both parts of the Hybrid Interpretable Model is required.
C.2 HybridCORELLSPr.ooro Pre, Empirical Evaluation
We ran the experiments of Section 5.3 using HybridCORELS NoCollaa (with the same setup as HybridCORELSPee) and provide comparison with HybridCORELSp. within Figure 15 The results show that for very low transparency values, HybridCORELLppe.oooo close performances. Indeed, in such regimes, most of the classification task is handled by the black-box part of the model and the absence of collaboration with the interprotable part does not really matter. We observe the same phenomenon in regimes of very high transparency, where most of the examples are classified by the interpretable part. However, in regimes of medium to high transparency, we observe a significant drop of HybridCORELSpw. NoCollah's 's performances. This trend is particularly visible with the ACS Employment dataset. It can be explained by the absence of collaboration between both parts of the model: the prefix learning sacrifices the black-box performances (sending it most of the inconsistent. examples) to obtain the most accurate prefix possible. While this policy leads to slightly more accurate interpretable parts com- pared to the prefixes learned by HybridCOREISpee. it also harms the overall model accuracy considerably, and the obtained trade-offs are not competitive with those produced by HybridCOREI.sp. As observed in Section 5.3 with HybridCOREI.Spes on the COMPAS dataset, Hybrid Interpretable Models with in- termediate transparency values exhibit better test accuracies than the standalone black-box, due to better generalization. Again, this constitutes an argument in favor of the Pre-Black- Bor paradigm, this trend was not observed with the other Post- Black- Box methods.
and HybridCORELSpr have very
NoCoolaa
We provide in Figure 16 examples of Hybrid Interpretable Models found with HybridCORELSpr on the same data splits of the ACS Employment dataset and
and HlybridCORRELSpp.No.....o transparencies roughly 80%. We observe, as aforementioned, that the black-boxes trained after the HlybridCORELSPeeN..... prefixes exhibit considerably lower performances. On the other hand, the prefix and black-box parts of the models trained using HybridCOREI have comparable classification
31

---

Published in Transactions on Machine Learning Research (08/2024)
performances, the former trained while accounting for the inconsistent samples that would be left for the later to classify.
0.75
0.75
0.75
0.74
0.74
0.74
Accuracy
Accuracy
0.73
0.73
0.73
0.72
0.72
0.72
0.71
0.71
0.7g
0.70 0.0
0.70
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.3
1.0
Transparency
Transparency
Transparency
(a) ACS Employment dataset.
0.85
0.85
0.85
0.84
0.84
Accuracy
Accuracy
0.83
0.82
0.82
0.82
0.81
0.0
0.2
0.4
0.6
0.8
1.0
0.81
0.0
0.2
0.4
0.6
0.8
1.0
0.81
0.0
0.2
0.4
0.6
0.8
1.0
Transparency
Transparency
Transparency
(b)
UCI Adult Income dataset.
0.68
0.68
0.68
Accuracy
Accuracy
0.67
0.67
0.66
0.66
0.65
0.65
0.2
L.0
Transparency
Transparency
Transparency
(c) COMPAS dataset.
HybridCoRELSPre
HybridCCORELSPreNoCColaa
Figure 15: Test set accuracy Ltranpparancccy trade-off's for our two The Pareto front for each method is represented as a line and the filled bands encode the std across the five data split reruns. Results are provided for several black-boxes: (Left) AdaBoost, (Middle) Random Forests, (Right) Gradient Boosted Trees.
variants of HybridCORET.S.
32

---

Published in Transactions on Machine Learning Research (08/2024)
If ["age_high" high" and "Fenale"] then 0 (ace 71.3%)
if "'usband/viife" and "No disability") ] then (ace 71.9%)
else if ['age_hte high" and "Native"] then 0 (ace 64.5%)
else If 'Bachelor'ss degree" and "Ro disability") then (acc 84.8%)
else if
and "No diesbility" then (ace 82.3%) ['high school diplona' and "No disability"] then (ace 60.0%)
''efeerence
else if
else
AdaBoost () (ace 71.9%)
(a) HybridCORELSpee Test Accuracy 73.7%, Transparency 80.2%.
['age_lox" and "Reference person'] then (acc 82.2%)
else if ('Disability") then (ace 77.7%)
if "aag_mediun") then (ace 79.2%)
else if "age_low" and "Married"] then (ace 69.1%)
else if ('Hueband/wife and "Female") then (ace 68.6%)
else if ["age_low* and else
child householder") then (ace 59.0%)
AdaBoost () (acc 60.4%)
(b) HybraCCORELSp..ccola.
Test Accuracy 71.7%, Transparency 80.3%.
Examples of Hybrid Interpretable Models obtained on the ACS Employment dataset with Ad- aBoost black-boxee and the same train/ train/validee /aliiiaiiioottstt split. The models with transparency closest 80% were selected. We note that the black-box has worst performance in SybridCORELSPpe.eccaoa than HybridCORELSprr seeing as the prefix sent it the inconsistent examples.
Figure 16:
D
Additional Discussion on the Pre- Tre-Black-Bor Box Paradigm
illustrated the impact the specialization coefficient a used in the Pre-Black Box paradigm. However, these experiments also highlighted a peculiar pattern the test set. performances are often signíf- icantly larger than their training set counterparts. For instance, Figure 10 (c) suggests that COMPAS test accuracies can be 5 ppts larger than training accuracies. Similarly, Figure 11 (b) with 0.95 transparency
Section 5.2
suggests that test set accuracies can be ppts larger than train. How is this possible? Is there data leakage between the training and test sets?
To lay these concerns to rest, we did additional data analysis by comparing the training and test accuracies ((ee r))[[5] all Hybrid Interpretable Models trained in Section 5.2.
On COMPAS, 81% of the Hybrid Interpretable Models have a lower test accuracy than training accuracy.
On Adult, 89% of the Hybrid Interpretable Models have a lower test accuracy than training accuracy.
On ACS-Employ, 94% of the Hybrid Interpretable Models have lower test accuracy than training accuracy.
In any cases where the test accuracy better than training accuracy, the gap never more than 0.5 ppts, lot less than the 5 ppts and 2 ppts suggested by Figures T0 & The reason behind these apparent contradictions is that both Figures do not show train/test accuracies of the full tuple (he, r). Rather, they plot quantitics related (but not equivalent) to the full accuracy.
Figure 10 illustrates Upper Bounds on the train/test set accuracies (cf. Equation 16), which sum the errors of the prefix on its support and the unavoidable errors sent the black-box due data inconsistencies. Since these are upper bounds (not actual accuracies), the fact that they higher on test is peculiar, but not indicative of any data leakage. In fact, compared these Upper Bounds with the actual accuracies the train/test sets:
On average, on COMPAS, the upper bounds overestimate train accuracy by 1 ppts and test accuracy by ppts.
33

---

Published in Transactions on Machine Learning Research (08/2024)
On average, Adult, the upper bounds overestimate the train accuracy by 2 ppts and the test accuracy by 4 ppts.
On average, on CCS-Emplog, the upper bounds overestimate the train accuracy by 1.6 ppts and the test accuracy by 2.7 ppts.
This explains why, in Figure 10 these upper bounds are better on the test set, while the actual accuracy is better on the training set.
Figure 11 illustrates the train/test accuracy of the black-box evaluated samples that land in Ω (ef. Equation 17). This quantity is not necessarily representative of the full Hybrid Interpretable Model accuracy for two reasons. First, the full performance must additionally account for the errors made by the prefix over Ω. Second, the black-box training accuracy evaluates the black-bor box on the training samples that land in f. However, this region was determined beforehand by minimizing Equation 15 on the same training samples. Seeing as Equation 15 penalizes the prefix for making errors on it is possible that the hardest training samples (those that could not be predicted by a short rule list) were sent to f2. Consequently, the distributions of training samples landing in Q is not necessarily the same the distribution of fresh test samples landing in f2
34


Reviews:
[{"review_id": "NNTQmk5rFN", "reviewer": "Reviewer_ufqm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "One extremely interesting result obtained by this paper is that hybrid models can have better accuracies than more complex black-box models that have no transparency. Hybrid models are thus a pareto improvement on black-box models in terms of both accuracy and transparency. This is a surprising result, and the authors provide some theoretical justification for it, and also show this empirically in (at least) one of the three datasets they examine.\n\nThis finding is a great argument for further study of hybrid models, which the paper claims is an under-explored area.\n\nIn my view, the paper does not have very serious weaknesses - a summary of moderate to minor issues follows, with more detail in the next section. From a technical standpoint:\n\n1. The lack of cross-validation over the specialization coefficient, alpha, is a statistical issue. Currently, the authors choose the value of alpha based on both training and test data (presumably the entire dataset), and then use this value while evaluating against other methods - this bleeds test data into the model, creating bias at the evaluation stage. Alpha should be treated like any other hyperparameter and be optimized through cross-validation.\n\n2. An important question I have about hybrid models in general: what if we need an explanation for a sample that is sent to the black-box? For example, if the model is designed to accept or reject applications for a loan, how would we explain rejection decisions that are routed through the black-box? This is particularly problematic if the transparent model would have disagreed with the black-box model on this sample. If we choose to default to the decision of the transparent model in all cases of disagreement, then this would make the hybrid model strictly worse than the transparent model. How do the authors imagine hybrid models to be used in practice?\n\nFrom a stylistic standpoint:\n\n3. There are several claims of being \"thorough\", which should be dialed back. The paper undertakes an exploration of an understudied area, so there are likely a very large number of possible approaches. The authors have made choices to restrict their analysis to a specific subset of approaches, which is fine. But claims that this foray is comprehensive are misleading and should be omitted.\n\n4. The writing quality is good, but feels quite verbose and repetitive. Often, discussion-style comments are interwoven throughout other sections, including sentences of a more speculative nature. This makes it difficult to extract the signal from the noise. I would encourage the authors to make efforts to condense the writing where possible, and to separate raw observations from interpretations and speculation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a new framework to think about hybrid interpretable models, which send a fraction of the data that lies in a fixed domain to a simpler, more transparent model, and the remainder to a more complex black-box model. The paper provides a theoretical analysis, identifying two families of learning methods (pre- and post-), and a new algorithm for learning rule-based hybrid models. The paper evaluates the new algorithm (both pre- and post- versions) on three public datasets, showing improved performance over certain existing algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "What follows is a list of moderate and minor changes. I would look to the authors' responses to comments 1-3, 10, 14-16, and 23-26, while making my recommendation.\n\n1-4. As above.\n\n5. (p.1, third line from bottom) \"worst\" should be \"worse\"\n6. (p.3) Clarify that HybridCORELS provides a certificate of optimality in terms of accuracy\n7. (Fig 2b) Missing mathcal in caption for H_s\n8. (Sec 2.3) It is unclear to me why an average over epsilon provides a measure of \"looseness\" of the bound. The optimal transparency isn't obtained at the point where the bound is least loose, it is obtained at the point where the bound is smallest (which is what is effectively done in Fig 4a). The word \"looseness\" feels misleading to me. Is there a better nomenclature?\n9. (Sec 2.4, point 3) Whenever the authors say that hybrid models may obtain better generalization, this sounds very speculative. They should at least mention the fact that they see this in their experiments in Section 5.3.\n10. (Sec 2.4) Also, can the authors provide some intuition as to why the optimal transparency is non-zero?\n11. (Sec 3.1, 2nd paragraph) Second sentence grammar\n12. (Sec 3.1.1) The claim that the interpretable model is able to \"correct the mistakes\" made by the black-box sounds non-intuitive and should be qualified. One normally expects the black-box model to be more accurate.\n13. (Sec 3.1.1 and 3.1.2) The overall writing here feels very speculative and discussion-heavy - for example, \"however, it could also cause overfitting\". the discussion is not balanced since there is no mention of the lack of expressivity of the transparent model. Reading this, one is made to feel that the black box is less accurate and also less transparent. It would be better to stick to describing the approach, and maybe have a separate section to provide intuitions/discussion.\n14. (Sec 3.3.1) Criticisms of HyRS should be toned down. It is unclear why the objective is considered \"extremely complex\". One strategy to obtain a given transparency could be to run the algorithm for different beta until we obtain the desired transparency - why is this not a possibility? Also, isn't some degree of variance normal in ML, and can't we choose the run with greatest accuracy?\n15. (Sec 3.3.2) The paper states that for CRL, one obtains transparencies of 0.75 when keeping a target of 0.5, and that this may affect accuracy. Is a decrease in accuracy observed in practice? What are the accuracies of the points in Fig 9?\n16. For both HyRS and CRL, there are significant \"jumps\" in the transparency on the UCI Adult dataset. The part where transparency jumps in Fig 7b is probably because some rule becomes \"active\" at that beta value, and captures around half the dataset. Does HybridCORELS achieve fewer jumps in Fig 12? If not, then these criticisms should be avoided.\n17. (p.13, line 2 and line 4) \"counts\" should be \"count\"; \"features vector\" should be \"feature vectors\"\n18. (Sec 5.1) Why are a pre-mined set of rules used, instead of using a strategy similar to a decision tree?\n19. (Sec 5.2) Please separate _observations_ about the results from _interpretations_ drawn.\n20. (Sec 5.2, results section, 2nd paragraph) There are some conflicting statements here: first it is claimed that higher alpha is better (which is indeed seen from the figures). Then, it is justified that specializing the black-box on the samples not sent to the transparent model is a good thing. This undercuts the need to introduce alpha in Section 3.1.2 in the first place, because now overfitting is considered to be good. Then, later in the paragraph, it is claimed that a small alpha (around 1) is good, because it maximizes the \"improvement rate\". But it is not clear to me why we care about improvement rate - shouldn't we care more about the raw hybrid test accuracy?\n21. (Fig 10) Is the variance in the plots over multiple runs or over the 3 different black box models? This has not been specified. If over multiple runs, then which black-box model is shown, and can we see the others? If the variance is over models, then can we see the variance over multiple runs?\n22. (Fig 10) It would be useful to see the performance at 100% transparency as well, as a baseline.\n23. (Fig 10) Why (and how) is test accuracy consistently higher than training accuracy?\n24. (Fig 11) Once again, test accuracy is higher than training accuracy in many instances - how is this possible?\n25. (Fig 11) Taking an optimal value of alpha from these plots does not appear well-motivated, since there is a lot of noise and no clear trend. The main trend appears to be higher accuracy for higher alpha. In any case, alpha should be optimized through cross-validation in the hybrid model (as mentioned in point 1)\n26. (Fig 12) For different fixed transparency values, it would be very useful to understand where all of these models fall on the precision-recall curve, not just understanding accuracy (i.e., recall).\n27. (Sec 6, line 1) Please cite.", "broader_impact_concerns": "A broader impact statement has not been provided. My main concerns with impact are summarized in point 2, regarding practical usage of hybrid models, and providing explanations for decisions that are routed through the black-box.\n\nI would also recommend that the authors think about other ethical concerns and add a broader impact section (e.g., cautioning against premature use of their work; poor choices of pre-mined rules which could cause discrimination, etc.), since their work lies in the domain of Fairness, Accountability, Transparency and Explainability of AI models.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lz4jIIQ2io", "reviewer": "Reviewer_mhQa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The motivation is clear and well stated. I agree with that higher levels of transparency would increasing the trustworthiness of decision-making coming from black box machine learning models. Thus, it is important for a wider adoption of such models. \n\nThe paper reads somehow well, but after section 2 the presentation becomes a bit clumsy and harder to follow.\n\nThe authors consider rule-based hybrid interpretable models for binary classification; this should be states earlier.\n\nThe level of transparency defined as the ratio of samples that are sent to the interpretable part. Can you say something aboutt he ratio of samples that can be explained by the interpretable part? \n\nAnother weakness is the lack theoretical content. The PAC bound seems to be quite loose, which seems to give weak indications of this sweet-spot. Therefore, I have troubles linking it practice.\n\nThe authors mention that the bound in Thm 1 is loose. Any idea of how to tighten it?\n\nYou assume that there exists a perfect model in (1). Please format it as an assumption. How important is this assumption for the analysis of Thm 1? \n\nInstead of ERM, could other principles be used? Like risk-sensitive principles, VaR, CVaR?\n\nThe authors shows that a hybrid model trained sufficiently many examples (a finite dataset) can have a PAC-guarantee on new unseen samples. I feel that in this setting it would be more obvious to provide PAC-Bayesian generalizations bounds instead [Alquier, 2024] - where priors could be informative or not.\n\nIt is a drawback that the specialization coefficient $\\alpha$ has to be fine-tuned in practice. Is there way to come around this? Or do you have some ideas on how to tune it during training?\n\nPierre Alquier. User-friendly introduction to PAC-Bayes bounds. Foundations and Trends® in Machine Learning,\n2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper study hybrid models, which is a mixture of interpretable and complex black box models. The authors provide a PAC generalization bound, which gives the indication of a sweet-spot for an optimal level transparency of the hybrid model. Thus, their hybrid models can better balance the level of transparency in the decision making of the model - namely the accuracy-transparency trade-off.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper should be carefully proof-read; language, capitalization and italics are used differently for the same word. Moreover, the format and notation could also be improved as this make the paper tricky to read. I will try to highlight some of the instances below.\n\nIn the first sentence of the introduction, the authors could maybe give some references?\n\nSometimes the authors write \"Hybrid Interpretable Models\" and sometimes just \"Hybrid Models\" and \"hybrid models\".\n\nExplain in more details what these heuristics are? \"To address this issue, past studies have optimized such models using local search heuristics (Wang, 2019; Pan et al., 2020).\"\n\nToo many parenthesis: \"Given the recent development of highly efficient libraries for training interpretable models to optimality (e.g., CORELS for rule-lists (Angelino et al., 2017), GOSDT for decision trees (Hu et al., 2019))),...\"\n\nPlease put your assumptions into an assumption format. It is not easy to find the assumptions when they are written in text. Do the same for examples and definitions.\n\nMention in abstract and introduction you consider binary classifiers as it is first stated on page 4.\n\nSome notation is defined several times, and some notation is not defined (only the appendix). E.g., $C_{\\Omega}$ is defined several times and $C_{\\bar{\\Omega}}$ is only defined the appendix.\n\nI think there is a mistake in the definition of $C_{\\Omega}$ as is states $x\\sim\\mathcal{D}$ where $\\mathcal{D}$ is the distribution over $\\mathcal{X}\\times\\{0,1\\}$.\n\nMake the example if the binary depth-3 decision tree into a example format.\n\nLast sentence on page 7 reads badly.\n\nSomething is wrong with \"min\\_transp\"?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vyz7t3Yxbu", "reviewer": "Reviewer_skY7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I found no major drawbacks. The study is thorough, the topic will surely match the interest of the audience, and the paper is well-written.\n\n\\+ The study is thoroughly done from theory to experiment. The theoretical analysis provides meaningful implications of the potential advantage of hybrid models, and the empirical results also support them to some extent.\n\n\\+ The taxonomy given for the two different strategies of hybrid modeling is nice. It will be helpful in designing new methods, too.\n\n\\- Although the empirical results seem to support the theoretical claims to some extent, the significance of comparisons is sometimes unclear. I list such points in the next form (Requested Changes).\n\n\\- The need for the excess length of the paper does not look so obvious. I would suggest trying to streamline the main part even only slightly, e.g. by deferring some empirical results to the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study so-called hybrid interpretable models, that is, the combination of simple rule lists and black-box machine learning models such as random forest. The paper not only provides the theoretical analysis such as the PAC learnability and the error bound but also proposes concrete algorithms and showcases their empirical performance. The proposed methods can precisely control the transparency level (i.e., the ratio of samples classified by a simple model or a black-box model), which was not possible with existing hybrid modeling methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1) In Section 5.2:\n> As expected, higher values of the specialization coefficient $\\alpha$ lead to higher training accuracy of the black-box part.\n\nThis claim does not seem so obvious in Figure 11. In many cases, at least visually, the difference between small $\\alpha$ and large $\\alpha$ does not seem significant according to the error bars. I would suggest making the claim more specific.\n\n(2) In Section 5.2, please make the definition of the \"improvement rate\" clearer.\n\n(3) The comparison in Section 5.3 (Figure 12) is clear for the ACS Employment dataset, but for the other two datasets, the significance of the difference is much less clear. Why is this the case? Some comments will be helpful.\n\n(4) Just out of curiosity, do you have any comments on hybrid modeling where the hypothesis space of the black-box model is infinite? For example, is there a possibility to do some sort of theoretical analysis? This might also be of readers' interest.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: One detailed reviewer-author discussion reveals an interesting discrepancy between training/testing performance, as well as some unresolved questions about the tuning of $\alpha$. The authors did not completely resolve these issues, and I strongly encourage the authors to consider the reviewer as being representative of an interested reader, who might have similar questions while reading the final manuscript. I encourage the authors to make changes to the manuscript to resolve these issues to the best of their ability, with minor changes.
Decision: Accept (poster)