Submodular optimization and interpretable machine learning
Abstract
Submodular functions are used to characterize the diminishing-returns property, which appears in many application areas, including information summarization, sensor placement, viral marketing, and more. Optimizing submodular functions has a rich history in mathematics and operations research, while recently, the subject has received increased attention due to the prevalent role of submodular functions in a broad range of data-science applications. In this talk we will discuss two recent projects on the topic of interpretable classification, both of which make interesting connections with submodular optimization. For the first project, we address the problem of multi-label classification via concise and discriminative rule sets. Submodularity is used to account for diversity, which helps avoiding redundancy, and thus, controlling the number of rules in the solution set. In the second project we aim to find accurate decision trees that have small size, and thus, are interpretable. We study a general family of impurity functions, including the popular functions of entropy and Gini-index, and show that a simple enhancement, relying on the framework of adaptive submodular ranking, can be used to obtain a logarithmic approximation guarantee on the tree complexity.
Bio
Aristides Gionis is a WASP professor in KTH Royal Institute of Technology, Sweden, and an adjunct professor in Aalto University, Finland. He obtained his PhD from Stanford University, USA, and he has been a senior research scientist in Yahoo! Research. He has contributed in several areas of data science, such as data clustering and summarization, graph mining and social-network analysis, analysis of data streams, and privacy-preserving data mining. His current research is funded by the Wallenberg AI, Autonomous Systems and Software Program (WASP) and by the European Commission with an ERC Advanced grant (REBOUND) and the project SoBigData++.