Author name cluster

Marco Molinaro

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2025 Journal Article

Decision trees with short explainable rules

Victor F.C. Souza
Ferdinando Cicalese
Eduardo Sany Laber
Marco Molinaro

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explainability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our new measure (which we call the explanation size) and the more classical measures of worst-case and average depth. We also show that from our characterizations it is possible to obtain polynomial algorithms that guarantee O ( ln ⁡ n ) -approximation (hence optimal if P ≠ N P ) for the minimization of both the average/worst-case explanation size and the average/worst-case depth.

Details DOI

NeurIPS Conference 2022 Conference Paper

Decision Trees with Short Explainable Rules

Victor Feitosa Souza
Ferdinando Cicalese
Eduardo Laber
Marco Molinaro

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explanability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our newmeasure (which we call the {\em explanation size}) and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees $O(\ln n )$-approximation (hence optimal if $P \neq NP$) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.

PDF Details

TCS Journal 2011 Journal Article

On the complexity of searching in trees and partially ordered structures

Ferdinando Cicalese
Tobias Jacobs
Eduardo Laber
Marco Molinaro

We study the problem of minimizing the weighted average number of queries to identify an initially unknown object in a poset. We show that for general posets, there cannot be any o ( log n ) -approximation algorithm unless NP ⊆ TIME ( n O ( log log n ) ). When the Hasse diagram of the partially ordered set has the structure of a tree, the problem is equivalent to the following tree search problem: in a given rooted tree T = ( V, E ) a node has been marked and we want to identify it. In order to locate the marked node, we can perform node queries. A node query u asks whether the marked node lies in the subtree rooted at u. A function w: V → Z + is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper the complexity of this problem had remained open. We prove that the above tree search problem is NP -complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 we show that the problem is polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP -complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O ( | V | log | V | ) time for trees with degree at most 2 (paths). Our results sharply contrast with those for the variant of the problem where one is interested in minimizing the maximum number of queries. In fact, for the worst case scenario, linear time algorithms are known for finding an optimal search strategy [K. Onak, P. Parys, Generalization of binary search: searching in trees and forest-like partial orders, in: FOCS’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 2006, pp. 379–388; S. Mozes, K. Onak, O. Weimann, Finding an optimal tree searching strategy in linear time, in: SODA’08: Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 1096–1105].

Details DOI