Fast Identification of Optimal Monotonic Classifiers

Abstract

MotivationBivariate monotonic classifiers (BMCs) are based on pairs of input features. Like many other models used for machine learning, they can capture non-linear patterns in high-dimensional data. At the same time, they are simple and easy to interpret. Until now, the use of BMCs on a genome scale was hampered by the high computational complexity of the search for pairs of features with a high leave-one-out performance estimate. ResultsWe introduce the fastBMC algorithm, which drastically speeds up the identification of BMCs. The algorithm is based on a mathematical bound for the BMC performance estimate while maintaining optimality. We show empirically that fastBMC speeds up the computation by a factor of at least 15 already for a small number of features, compared to the traditional approach. For two of the three clinical datasets that we consider here, the resulting possibility of considering much larger sets of features translates into significantly improved classification performance. As an example for the high degree of interpretability of BMCs, we discuss a straightforward interpretation of a BMC glioblastoma survival predictor, an immediate novel biomedical hypothesis, options for biomedical validation, and treatment implications. ConclusionsfastBMC enables the rapid construction of robust and interpretable ensemble models using BMC, facilitating the discovery of interesting gene pairs and their contributions to the underlying biology. AvailabilityWe provide the first open-source implementation for learning BMCs, and an implementation of fastBMC in particular, all in Python, at https://github.com/oceanefrqt/fastBMC.