Two Topics in Compression and Interpretability

Abstract
The talk will cover two topics related to the issue of building compact representations of information that allow for “easy” access.​


In the first part of the talk, we will focus on the problem of building interpretable decision trees. Decision trees are generally preferred among ML models when interpretability is a crucial issue. However, the interpretability/explainability of a decision tree critically depends on some of its structural parameters, e.g., size or average/max depth of its leaves. We will discuss a novel criterion for measuring the interpretability of a decision tree based on the sparsity of the set of attributes that are required to explain the classification of the examples. We will characterise the best possible guarantees achievable by a decision tree that optimises both the new measure and the more classical measures of worst-case and average depth.​


In the second part of the talk, we focus on the problem of allowing fast access to elements of a compressed text. This is a major issue in the employment of compressed data structures. The setting we analyse regards the celebrated Lempel and Ziv compression. We investigate the problem of constructing LZ-like parsings under the constraint that, given a position p of the original text and the encoding of such a text based on the parsing, it is possible to identify the character in position p by performing a bounded number of accesses to the encoding. We show that this problem is, in general, hard (compared to the linearity of producing unconstrained shortest LZ-like encodings), and we discuss approximation guarantees.




Biography
Ferdinando Cicalese has been a professor of Computer Science at University of Verona (Italy) since 2014. He received the master's and PhD degrees in computer science from the University of Salerno (Italy) in 1995 and 2001, respectively. From 2001 to 2014, he was first an assistant professor and then associate professor at University of Salerno and from 2004 to 2009, he was research group leader at Bielefeld University (Germany). His research interests are in the area of algorithms and complexity (with a special emphasis on combinatorial search algorithms and decision tree construction optimisation), information theory, compression and fault-tolerant error-correction codes.​


Dr. Cicalese is the recipient of the 2004 Sofja Kovalevskaja award from the Humboldt Foundation and the Germany BMBF. He is the author of more than 120 scientific publications, including a Springer monograph on fault tolerant search algorithms. Dr. Cicalese has been a guest editor of international journals and a PC member and program chair of several international conferences.