Learning Succinct Models: Pipelined Compression with L1-Regularization, Hashing, Elias-Fano Indices, and Quantization

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 2774–2784, Osaka, Japan, December 11-17 2016. Learning Succinct Models: Pipelined Compression with L1-Regularization, Hashing, Elias–Fano Indices, and Quantization Hajime Senuma† ‡ and Akiko Aizawa‡ † †University of Tokyo, Tokyo, Japan ‡National Institute of Informatics, Tokyo, Japan {senuma,aizawa}@nii.ac.jp Abstract The recent proliferation of smart devices necessitates methods to learn small-sized models. This paper demonstrates that if there are m features in total but only n = o(√m) features are required to distinguish examples, with Ω(log m) training examples and reasonable settings, it is possible to obtain a good model in a succinct representation using n log2 m n +o(m) bits, by using a pipeline of existing compression methods: L1-regularized logistic regression, feature hashing, Elias–Fano indices, and randomized quantization. An experiment shows that a noun phrase chunking task for which an existing library requires 27 megabytes can be compressed to less than 13 kilobytes without notable loss of accuracy. 1 Introduction The age of smart devices has arrived. Cisco reports that, as of 2015, smartphones and tablets account for 15% of IP traffic (against 53% for PCs), and further predicts that, by 2020, this share will have grown to 43%, surpassing the 29% of PCs (Cisco Systems, 2016). This trend increases the need for intelligent processing for these platforms. Hence, the study of statistical methods for natural language process- ing (NLP) systems on mobile devices has received considerable attention in recent years (Ganchev and Dredze, 2008; Hagiwara and Sekine, 2014; Chen et al., 2015). Among the various issues in this setting, storage costs pose a particular challenge, because the size of the resulting models often grow quickly. Even a simple noun phrase (NP) chunker can easily take dozens of megabytes if na¨ıvely implemented. Suppose we have m features. A direct implementation then consumes Z(A)+O(mζ), where Z(A) represents the size of an alphabet A, or a feature dictionary that maps a feature string to an index into its parameter vector, and O(mζ) represents the space complexity of a dense real vector as the parameter where using ζ bits to achieve a certain amount of float precision (64m if using double-precision floats). These large-sized models are not only inefficient in terms of network bandwidth, but also significantly increase energy consumption (Han et al., 2016). Therefore, it is vital to devise a method that achieves as small a model as possible. One of the basic properties of information theory says that, to represent a set of n non-negative integers less than m (or, equivalently, a bit vector of size m containing n 1s), we need at least Bm,n = ⌈log2 (m n ) ⌉ ≈ n log2 m n bits. Recent studies in theoretical computer science show that it is possible to compress a set of non-negative integers while keeping some primitive operations under suc- cinct representations, that is, data structures using only Bm,n + o(m) bits. As an analogy to succinct data structures, one may ask a question: if there …

Content truncated to 500 words