“Resource-Efficient Machine Learning in 2 KB RAM for the Internet of Things”, 2017 (; backlinks):
This paper develops a novel tree-based algorithm, called Bonsai [a strong and shallow non-linear tree based classifier], for efficient prediction on IoT devices—such as those based on the Arduino Uno board having an 8 bit ATmega328P microcontroller operating at 16 MHz with no native floating point support, 2 KB RAM and 32 KB read-only flash.
Bonsai maintains prediction accuracy while minimizing model size and prediction costs by: (1) developing a tree model which learns a single, shallow, sparse tree with powerful nodes; (2) sparsely projecting all data into a low-dimensional space in which the tree is learnt; and (3) jointly learning all tree and projection parameters.
Experimental results on multiple benchmark datasets demonstrate that Bonsai can make predictions in milliseconds even on slow microcontrollers, can fit in KB of memory, has lower battery consumption than all other algorithms while achieving prediction accuracies that can be as much as 30% higher than state-of-the-art methods for resource-efficient machine learning.
Bonsai is also shown to generalize to other resource constrained settings beyond IoT by generating substantially better search results as compared to Bing’s L3 ranker when the model size is restricted to 300 bytes.
…The models closest to Bonsai are Decision Jungles (Shotton et al 201311ya) and LDKL (Jose et al 201311ya). Bonsai improves upon LDKL by learning its tree in a low-dimensional space, learning sparse branching functions and predictors and generalizing the model to multi-class classification, ranking, etc. Decision Jungles are similar to Bonsai in that they share node parameters using a DAG structure. Unfortunately, Decision Jungles need to learn deep tree ensembles with many nodes as they use weak constant classifiers as leaf node predictors. Bonsai can have lower model size and higher accuracy as it learns a single, shallow tree in a low-dimensional space with non-linear predictors.