RI: SMALL: Fast Prediction and Model Compression for Large-Scale Machine Learning

为了处理大规模问题，人们提出了许多算法来提高机器学习模型的训练速度。然而，在现实世界的许多应用中，由于预测的时间和空间复杂性，瓶颈是在预测阶段而不是训练阶段。与在多台机器上运行几个小时的训练阶段不同，预测阶段通常在实时系统上运行；因此，每次预测都必须在几秒钟内完成，以便向用户提供即时反馈。此外，在移动设备上运行的应用程序对内存容量和计算资源有更严格的限制。为了解决这些问题，本研究开发了一系列新的机器学习算法，具有更快的预测时间和更小的模型尺寸。该项目的成果在机器学习模型对实时在线系统和设备应用的适用性方面产生了根本性的转变。软件包和实验平台在应用程序上进行测试后向公众开放。除了研究目标外，PI还追求教育目标，包括促进本科生研究，让科学和工程领域代表性不足的少数族裔参与研究，以及开发本科生和研究生数据科学课程。该项目的目标是开发新的方法来减少机器学习算法的预测时间和模型大小。该项目特别关注具有大输出空间（矩阵分解、极端多类/多标签分类）和高度非线性模型（核方法和深度神经网络）的机器学习应用。研究了一系列的近似算法，包括基于树的算法、聚类方法和亚线性时间搜索算法。为这些算法开发了一个统一的框架，并在理论和实践中研究了精度与预测时间/模型大小之间的权衡。所提出的算法在广泛的现实世界应用中进行了评估，包括在线网络服务和设备上的应用。

In order to handle large-scale problems, many algorithms have been proposed for improving the training speed of machine learning models. However, in many real world applications the bottleneck is at the prediction phase instead of the training phase due to the time and space complexity of prediction. Unlike the training phase that can run for several hours on multiple machines, the prediction phase usually runs on real-time systems; as a result, each prediction has to be done in a few seconds in order to provide immediate feedback to users. Furthermore, applications that run on mobile devices have even more strict constraints on memory capacity and computational resources. To address these issues, this research develops a new family of machine learning algorithms with faster prediction time and smaller model size. The outcome of this project creates a fundamental shift in the applicability of machine learning models to real-time online systems and on-device applications. Software packages and experimental platforms are made available to the public after being tested on applications. Besides the research objectives, the PI also pursues educational objectives including promoting undergraduate research, involving under-represented minorities in science and engineering, and developing undergraduate and graduate data science curriculums.The goal of this project is to develop novel approaches for reducing prediction time and model size of machine learning algorithms. In particular, the project focuses on machine learning applications with large output space (matrix factorization, extreme multi-class/multi-label classification), and highly nonlinear models (kernel methods and deep neural networks). A series of approximation algorithms are studied, including tree-based algorithms, clustering approaches, and sub-linear time search algorithms. A unified framework is developed for these algorithms and the trade-off between accuracy and prediction time/model size is studied both in theory and in practice. The proposed algorithms are evaluated on a broad range of real world applications, including online web services and on-device applications.