Decision Tree Learning

Abstract

We increasingly encounter artificial intelligence-based technology in our daily lives, from smart home devices to self-driving cars to invisible systems running on our internet. Many artificial intelligence techniques use machine learning, algorithms that learn to predict or act based on collected data. Unfortunately, the most popular machine learning techniques, such as neural networks and ensembles, are so complex that humans cannot understand how they make predictions. Without understanding the prediction process, it is difficult to trust the model. Therefore, in this dissertation, we work on algorithms that learn models that are understandable to humans. The type of model we consider is a decision tree, a flowchart-like model that can easily be visualized so humans can understand it. These models ask a series of questions about an input and use the answers to derive a prediction.

Decision trees were popularized in the 1980s and extensively studied, but there is still room for improvement. The most popular algorithms for learning decision trees are fast but do not necessarily lead to the best performance. They are not robust, meaning tiny changes in the data can negatively influence the quality of their predictions. Also, the existing algorithms cannot be directly applied to problems where multiple sequential predictions have to be made. Therefore, this dissertation studies several techniques for learning decision trees for robustness and sequential decision making problems.

In Part I of the dissertation, we consider the problem of optimizing decision trees to make good predictions while being robust to small changes in the data. In Chapter 4, we tackle the problem of learning good decision trees quickly in this setting. We improved the runtime of an existing algorithm by speeding up one of the key operations. In Chapter 5, we solve the problem of finding the best possible robust decision tree. The idea is to formulate the problem as an Integer-Linear Program, a special mathematical problem that can be solved with highly optimized algorithms. In Chapter 6, we propose a method that allows learning of models that are more flexible in terms of robustness, i.e., by allowing data changes in different shapes. To create an efficient algorithm, we optimize only the model’s predictions, not the model’s question part. Finally, in Chapter 7, we use techniques for improving data privacy to enable robustness against another kind of data change: someone adding or removing data.

Part II of this dissertation is about sequential decision making problems. In these settings, we control a device or agent that tries to achieve some goal in a potentially uncertain environment. Sequential decision making problems are significantly different from the supervised learning problems considered in Part I since the data is not pre-collected. This class of problems encompasses many real-life problems; one of the simplest of those could be a thermostat that measures the temperature in a room and needs to decide whether to turn a heater on or off constantly. Highly complex problems such as self-driving cars can be modeled similarly. We aim to find a controller represented by a simple decision tree for such problems. Such a controller is called a policy, and by representing it with a small decision tree, humans can understand it. In Chapter 9, we assume that we have a perfect mathematical description of the problem and use it to find the best possible decision tree via Integer Programming techniques. Later in Chapter 10, we assume that we can only interact with the environment and do not have a mathematical description of the problem. In this setting, we find good policies by iteratively updating the tree to achieve better scores using gradient information.

In our research, we have developed various algorithms for learning decision trees in settings that are hard to optimize with existing methods: robust predictions and sequential decision making. We hope that our work on decision tree learning for these settings allows human-understandable machine learning to be used in more real applications in the future. By improving model understanding and robustness, we aim to enable machine learning systems that humans can trust.