Eduardo Sany Laber

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.

ICML Conference 2024 Conference Paper

New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering

• Sanjoy Dasgupta
• Eduardo Sany Laber

Linkage methods are among the most popular algorithms for hierarchical clustering. Despite their relevance, the current knowledge regarding the quality of the clustering produced by these methods is limited. Here, we improve the currently available bounds on the maximum diameter of the clustering obtained by complete-link for metric spaces. One of our new bounds, in contrast to the existing ones, allows us to separate complete-link from single-link in terms of approximation for the diameter, which corroborates the common perception that the former is more suitable than the latter when the goal is producing compact clusters. We also show that our techniques can be employed to derive upper bounds on the cohesion of a class of linkage methods that includes the quite popular average-link.

TCS Journal 2023 Journal Article

Nearly tight bounds on the price of explainability for the k-center and the maximum-spacing clustering problems

• Eduardo Sany Laber
• Lucas Saadi Murtinho

The price of explainability for a clustering task can be defined as the unavoidable loss, in terms of the objective function, if we force the final partition to be explainable. Here, we study this price for the k-centers and maximum-spacing clustering problems. We provide nearly tight bounds for a natural model where explainability is achieved via decision trees.

ICML Conference 2021 Conference Paper

On the price of explainability for some clustering problems

• Eduardo Sany Laber
• Lucas Murtinho

The price of explainability for a clustering task can be defined as the unavoidable loss, in terms of the objective function, if we force the final partition to be explainable. Here, we study this price for the following clustering problems: $k$-means, $k$-medians, $k$-centers and maximum-spacing. We provide upper and lower bounds for a natural model where explainability is achieved via decision trees. For the $k$-means and $k$-medians problems our upper bounds improve those obtained by [Dasgupta et. al, ICML 20] for low dimensions. Another contribution is a simple and efficient algorithm for building explainable clusterings for the $k$-means problem. We provide empirical evidence that its performance is better than the current state of the art for decision-tree based explainable clustering.

ECAI Conference 2020 Conference Paper

Speeding up Word Mover's Distance and Its Variants via Properties of Distances Between Embeddings

• Matheus Werner
• Eduardo Sany Laber

The Word Mover’s Distance (WMD) proposed by Kusner et al. is a distance between documents that takes advantage of semantic relations among words that are captured by their embeddings. This distance proved to be quite effective, obtaining state-of-art error rates for classification tasks, but is also impracticable for large collections/documents due to its computational complexity. For circumventing this problem, variants of WMD have been proposed. Among them, Relaxed Word Mover’s Distance (RWMD) is one of the most successful due to its simplicity, effectiveness, and also because of its fast implementations. Relying on assumptions that are supported by empirical properties of the distances between embeddings, we propose an approach to speed up both WMD and RWMD. Experiments over 10 datasets suggest that our approach leads to a significant speed-up in document classification tasks while maintaining the same error rates.

ICML Conference 2020 Conference Paper

Teaching with Limited Information on the Learner's Behaviour

• Ferdinando Cicalese
• Sergio Filho
• Eduardo Sany Laber
• Marco Molinaro 0001

Machine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al. , ICML 2019], where the teaching is done interactively without having any knowledge of the Learner’s algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis $h^*$. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that $h^*$ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of $h^*$. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets.

ICML Conference 2019 Conference Paper

New results on information theoretic clustering

• Ferdinando Cicalese
• Eduardo Sany Laber
• Lucas Murtinho

We study the problem of optimizing the clustering of a set of vectors when the quality of the clustering is measured by the Entropy or the Gini impurity measure. Our results contribute to the state of the art both in terms of best known approximation guarantees and inapproximability bounds: (i) we give the first polynomial time algorithm for Entropy impurity based clustering with approximation guarantee independent of the number of vectors and (ii) we show that the problem of clustering based on entropy impurity does not admit a PTAS. This also implies an inapproximability result in information theoretic clustering for probability distributions closing a problem left open in [Chaudhury and McGregor, COLT08] and [Ackermann et al. , ECCC11]. We also report experiments with a new clustering method that was designed on top of the theoretical tools leading to the above results. These experiments suggest a practical applicability for our method, in particular, when the number of clusters is large.

ICML Conference 2018 Conference Paper

Binary Partitions with Approximate Minimum Impurity

• Eduardo Sany Laber
• Marco Molinaro 0001
• Felipe de A. Mello Pereira

The problem of splitting attributes is one of the main steps in the construction of decision trees. In order to decide the best split, impurity measures such as Entropy and Gini are widely used. In practice, decision-tree inducers use heuristics for finding splits with small impurity when they consider nominal attributes with a large number of distinct values. However, there are no known guarantees for the quality of the splits obtained by these heuristics. To fill this gap, we propose two new splitting procedures that provably achieve near-optimal impurity. We also report experiments that provide evidence that the proposed methods are interesting candidates to be employed in splitting nominal attributes with many values during decision tree/random forest induction.

ICML Conference 2014 Conference Paper

Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost

• Ferdinando Cicalese
• Eduardo Sany Laber
• Aline Medeiros Saettler

In several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables’ assignments). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.

TCS Journal 2008 Journal Article

A randomized competitive algorithm for evaluating priced AND/OR trees

• Eduardo Sany Laber

Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a μ ( T ) -competitive deterministic polynomial time algorithm, where μ ( T ) is the number of leaves that must be read, in the worst case, in order to determine the value of T. Furthermore, they proved that μ ( T ) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we take a step towards solving this problem by presenting a 5 6 μ ( T ) -competitive randomized polynomial time algorithm. This contrasts with the best known lower bound μ ( T ) / 2.

SODA Conference 2006 Conference Paper

On the competitive ratio of evaluating priced functions

• Ferdinando Cicalese
• Eduardo Sany Laber

STOC Conference 2005 Conference Paper

A new strategy for querying priced information

• Ferdinando Cicalese
• Eduardo Sany Laber

This paper focuses on competitive function evaluation in the context of computing with priced information. A function f is given together with a cost c x for each variable x of f. The cost c x has to be paid to read the value of x. The problem is to design algorithms that query the values of the variables sequentially in order to compute the function while trying to minimize the total cost incurred. Competitive analysis is employed to evaluate the performance of the algorithms. We describe a novel approach for devising efficient algorithms in this setting. We apply our approach to several classes of functions which have been studied in the literature of computing with priced information. In all cases considered, our approach provides algorithms that achieve better bounds than the best known algorithm for the same class of functions.More precisely, for the class of monotone boolean functions, we give a polynomial time algorithm with extremal competitiveness (k+l - √ min(k,l)) where k (l) denotes the minimum number of variables that one must read, in the worst case, in order to prove that the function under consideration evaluates to 1 (0). This dramatically improves upon the best known result which is an exponential time 2 max(k, l)-competitive algorithm. For the subclass of monotone boolean functions known as Threshold Trees we further improve our bounds and give a polynomial time algorithm with extremal competitive ratio 1.618 max(k, l).We then apply our methodology to classes of non-boolean functions. We consider the case of the so called Game Trees . We improve upon previously published results for this class of functions providing a polynomial time algorithm with extremal competitive ratio 1.5 γ(f), where γ(f) is a lower bound on the extremal competitive ratio of any deterministic algorithm.Finally, we consider the case when f is the function min (minimum). In this case, we are able to determine the optimal competitiveness for the problem. In fact we provide an algorithm with an (n-2)-competitive ratio, which matches the known lower bound.

TCS Journal 2003 Journal Article

The complexity of makespan minimization for pipeline transportation

• Ruy Luiz Milidiú
• Artur Alves Pessoa
• Eduardo Sany Laber

SPTP is a model for the pipeline transportation of petroleum products. It uses a directed graph G, where arcs represent pipes and nodes represent locations. In this paper, we analyze the complexity of finding a minimum makespan solution to SPTP. This problem is called SPTMP. We prove that, for any fixed ε>0, there is no η 1−ε -approximate algorithm for the SPTMP unless P=NP, where η is the input size. This result also holds if G is both planar and acyclic. If G is acyclic, then we give a m-approximate algorithm to SPTMP, where m is the number of arcs in G.

TCS Journal 2002 Journal Article

A strategy for searching with different access costs

• Eduardo Sany Laber
• Ruy Luiz Milidiú
• Artur Alves Pessoa

Let us consider an ordered set of keys A={a1<⋯<an}, where the probability of searching ai is 1/n, for i=1, …, n. If the cost of testing each key is similar, then the standard binary search is the strategy with minimum expected access cost. However, if the cost of testing ai is ci, for i=1, …, n, then the standard binary search is not necessarily the best strategy. In this paper, we prove that the expected access cost of an optimal search strategy is bounded above by 4C ln(n+1)/n, where C=∑i=1 n ci. Furthermore, we show that this upper bound is asymptotically tight up to constant factors. The proof of this upper bound is constructive and generates a 4 ln(n+1)-approximated algorithm for constructing near-optimal search strategies. This algorithm runs in O(n2) time and requires O(n) space, which can be useful for practical cases, since the best known exact algorithm for this problem runs in O(n3) time and requires O(n2) space.

SODA Conference 2001 Conference Paper

On binary searching with non-uniform costs

• Eduardo Sany Laber
• Ruy Luiz Milidiú
• Artur Alves Pessoa