Constrained prediction time random forests using equivalent trees and genetic programming: application to fall detection model embedding

Budgeted learning is a research field of growing interest that aims at including real world resource constraints into the design of machine learning models, for instance to reduce real environment prediction time. One family of method to do so consists in simplifying a pre-trained machine learning model in order to fit the prediction time constraints, while keeping model's prediction accuracy as best as possible. However we show in this work that the performance of these kinds of methods strongly depends on the pre-trained model structure. To overcome this dependence, we propose to tackle the budgeted prediction time optimization problem, by using equivalent classifiers with different structures and therefore different computation costs. The main contribution of this work is to propose an innovative evolutionary computing approach to decrease the prediction time of random forest classifiers, by using the notion of equivalence between decision trees. This method is applied for a real-time fall detection system embedding. Our genetic algorithm relies on two core operations : classifier equivalence and decision tree pruning. The first step of our method consists in building, from a pre-trained random forest, an initial population of random forests, that share the same decision function but have different structures using a randomized equivalent trees generation procedure. Then a genome reduction operation is iteratively applied on the individuals via random pruning based mutations. Our experiments show good reduction of random forests prediction time, as well as an efficient impact of using equivalent decision trees to reach better budgeted prediction time solutions. Results obtained both on a synthetic data made of gaussian-shaped clusters and on a real industrial fall detection dataset, advocate for the efficiency of our genetic random pruning approach in reducing random forests prediction time and for the use of equivalent decision trees in budgeted learning.