Budget learning based on equivalent trees and genetic algorithm : application to fall detection algorithm embedding.

Summary Budget learning is a research field of growing interest that aims at including real world resource constraints into the design of machine learning models, mainly to reduce real environment prediction time. One common way of doing it is by modifying a pre-trained machine learning model, to fit the prediction time constraints while keeping as best as possible the model's prediction quality. However, in this case, the performance of these kinds of methods depends on the pre-trained model structure. To overcome this dependence, we propose to tackle the budgeted optimization problem, by using equivalent models with different structures and therefore different computation costs. The contribution of this work is to propose a genetic algorithm to decrease prediction time of random forest classifiers, by using equivalent decision trees. 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. Then a genome reduction operation, is iteratively applied on the individuals via pruning based mutations. Our experiments show an important impact of using equivalent decision trees on reachable random forest solutions with a budgeted prediction time. Results obtained on a synthetic data made of gaussian-shaped clusters and on a real industrial fall detection dataset, advocate for the use of equivalent random forest models in budget learning.