Efficient online tree, rule-based and distance-based algorithms

The fast development of technology resulted in the constant production of data in different forms and from different sources. Contrary to what was observed in the first machine learning (ML) research works, there might be too much data to handle with traditional algorithms. Changes in the underlying data distributions might also render traditional ML solutions useless in real-world applications. Online ML (OML) aims to create solutions able to process data incrementally, with limited computation resource usage, and to deal with time-changing data distributions. Unfortunately, we have seen a recent growing trend in creating OML algorithms that solely focus on predictive performance and overlook computational costs. In regression tasks, the problem is even more pronounced when considering some of the most popular OML solutions: decision trees, decision rules, and ensembles of these models. We created improved and efficient OML algorithms from the algorithmic families mentioned, focusing on decreasing time and memory costs while maintaining competitive predictive performance. In this paper, we present an overview of the main contributions discussed in the Ph.D. thesis of the main author, which was awarded the best thesis prize by the Brazilian Computer Society in the 37th edition of the competition. Our proposals are either novel standalone OML algorithms or additions that can be paired with any existing tree or decision rule regressors.