Item Details

Accelerating Decision Tree Ensemble Inference with an Automata Representation

Tracy II, Tommy
Format
Thesis/Dissertation; Online
Author
Tracy II, Tommy
Advisor
Stan, Mircea
Abstract
Decision tree ensembles including Random Forests and Boosted Regression Trees have become ubiquitous in the research domains of medicine, natural sciences, natural language processing, and information retrieval. With increasing data rates and new research into larger ensembles, accelerating the inference rate and reducing the power consumption of this class of machine learning models is critical. It also presents a variety of technical challenges. The random memory access pattern and execution divergence of decision tree traversal results in memory-bound von Neumann implementations. In this dissertation, we present a series of novel techniques to accelerate decision tree ensembles, by representing their constituent trees as spatial automata that exhibit sequential streaming memory access, and can be executed with high parallelism. We develop novel algorithms and an open source automata framework that allow machine learning and computer architecture researchers to accelerate their applications, as well as stimulate further research into the field of automata-based machine learning. Finally, we present an application study of these techniques and tools with a boosted regression tree-based Learn-to-Rank document ranking model.
Language
English
Published
University of Virginia, Department of Computer Engineering, PHD (Doctor of Philosophy), 2019
Published Date
2019-08-26
Degree
PHD (Doctor of Philosophy)
Collection
Libra ETD Repository
Logo for In CopyrightIn Copyright

Availability

Read Online