The Integer Approximation of Undirected Graphical Models
Nico Piatkowski, Sangkyun Lee, Katharina J. Morik · 2014
Machine learning on resource constrained ubiquitous devices suffers from high energy consumption and slow execution time. In this paper, it is investigated how to modify machine learning algorithms in order to reduce the number of consumed clock cyclesnot by reducing the asymptotic complexity, but by assuming a weaker execution platform. In particular, an integer approximation to the class of undirected graphical models is proposed. Algorithms for inference, maximum-a-posteriori prediction and parameter estimation are presented and approximation error is discussed. In numerical evaluations on synthetic data, the response of the model to several influential properties of the data is investigated. The results on the synthetic data are confirmed with a natural language processing task on an open data set. In addition, the runtime on low-end hardware is regarded. The overall speedup of the new algorithms is at least 2× while overall loss in accuracy is rather small. This allows running probabilistic methods on very small devices, even if they do not contain a processor that is capable of executing floating point arithmetic at all.