Elamur Research
☰
home / papers / 2016 / FastText.zip: Compressing text classification models

FastText.zip: Compressing text classification models

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1612.03651

Summary

Linear text classifiers such as fastText are fast and accurate. Their word and n-gram embedding tables, though, can take hundreds of megabytes or even gigabytes, which keeps them off memory-limited devices like phones. The Facebook AI Research authors study how to shrink these models without losing accuracy. They first compare hashing-based binarization (LSH) with vector quantization, then build on product quantization (PQ, and its rotated variant OPQ) to encode the embedding matrices. Two changes make PQ work here. Each vector's norm and direction are quantized separately, because embedding norms vary a great deal. And a bottom-up scheme quantizes the input matrix first, then retrains the output layer before quantizing it too. Feature pruning, vocabulary hashing and Bloom filters cut the size further. On eight standard benchmarks (AG, Amazon, DBPedia, Sogou, Yahoo, Yelp), the compressed classifiers usually need about 100 times less memory than fastText, often under 100 kB, and lose only a little accuracy. This makes strong text classification practical on-device and gives reproducible compact baselines.

Key points

  • Embedding norms can differ by a factor of about 1000. Plain k-means pushes small-norm vectors toward zero, so the norm is coded on its own at the cost of one extra byte per vector.
  • Bottom-up PQ alone gives about 10× compression with no visible accuracy loss. Skipping the retraining step costs about 0.1–0.5% accuracy.
  • With pruning to 10K features and k=2, models shrink to about 78–79 kB. For example, DBPedia stays at 98.4%, the same as the uncompressed 56 MB model.
  • Compared with CNN baselines (Zhang et al. 2015; Xiao & Cho 2016), which take 1.2M–108M, fastText+PQ at 98K–889K matches or beats them. On AG it scores 91.9 vs 91.4 and 90.2.
  • On the large FlickrTag dataset, the full 12 GB model reaches 45.4. The quantized, retrained version with a 2M-feature cut-off reaches 45.5 in only 305 MB.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

369 papers of our library cite it (of the 140673 whose bibliographies we read); 23 of them have a page here, 346 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1612.03651 · arXiv 1612.03651

@misc{joulin2016fasttext,
  title = {{FastText.zip: Compressing text classification models}},
  author = {Joulin, Armand and Grave, Edouard and Bojanowski, Piotr and Douze, Matthijs and Jégou, Hérve and Mikolov, Tomas},
  year = {2016},
  doi = {10.48550/arxiv.1612.03651},
  eprint = {1612.03651},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1612.03651}
}

References

43 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alekh Agarwal, Olivier Chapelle, Miroslav Dudı́k, and John Langford. A reliable effective terascale linear learning system. Journal of Machine Learning Research, 15(1):1111–1133, 2014. find
  2. Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity-inducing penalties. Foundations and Trends R in Machine Learning, 4(1):1–106, 2012. find
  3. Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization on the fly. In SIGKDD, pp. 671–680. ACM, 2014. find
  4. Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 39–52. Springer, 2010. find
  5. Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pp. 380– 388, May 2002. find
  6. Welin Chen, David Grangier, and Michael Auli. Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906, 2015. find
  7. Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Max-cover in map-reduce. In International Conference on World Wide Web, 2010. find
  8. Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks: Training neural networks with weights and activations constrained to +1 or -1. arXiv preprint arXiv:1602.02830, 2016. find
  9. M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Symposium on Computational Geometry, pp. 253–262, 2004. find
  10. Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. Indexing by latent semantic analysis. Journal of the American society for information science, 1990. find
  11. Misha Denil, Babak Shakibi, Laurent Dinh, Marc-Aurelio Ranzato, and Nando et all de Freitas. Predicting parameters in deep learning. In NIPS, pp. 2148–2156, 2013. find
  12. Uriel Feige. A threshold of ln n for approximating set cover. JACM, 45(4):634–652, 1998. find
  13. Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In CVPR, June 2013. find
  14. Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, June 2011. find
  15. Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional networks using vector quantization. arXiv preprint arXiv:1412.6115, 2014. — [arXiv:1412.6115](https://arxiv.org/abs/1412.6115) find
  16. Edouard Grave, Armand Joulin, Moustapha Cissé, David Grangier, and Hervé Jégou. Efficient softmax approximation for gpus. arXiv preprint arXiv:1609.04309, 2016. find
  17. Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In ICLR, 2016. find
  18. Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Hamming embedding and weak geometric consistency for large scale image search. In ECCV, October 2008. find
  19. Hervé Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. PAMI, January 2011. find
  20. Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. Springer, 1998. find our card
  21. Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. Bag of tricks for efficient text classification. arXiv preprint arXiv:1607.01759, 2016. find
  22. Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. NIPS, 2:598–605, 1990. find
  23. Zhouhan Lin, Matthieu Courbariaux, Roland Memisevic, and Yoshua Bengio. Neural networks with few multiplications. arXiv preprint arXiv:1510.03009, 2015. — [arXiv:1510.03009](https://arxiv.org/abs/1510.03009) find
  24. Andrew McCallum and Kamal Nigam. A comparison of event models for naive bayes text classification. In AAAI workshop on learning for text categorization, 1998. find
  25. Lukas Meier, Sara Van De Geer, and Peter Bühlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):53–71, 2008. find
  26. Tomas Mikolov. Statistical language models based on neural networks. In PhD thesis. VUT Brno, 2012. find
  27. Tomas Mikolov, Ilya Sutskever, Anoop Deoras, Hai-Son Le, Stefan Kombrink, and J Cernocky. Subword language modeling with neural networks. preprint, 2012. find
  28. Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric lshs for inner product search. In ICML, pp. 1926–1934, 2015. find
  29. Mohammad Norouzi and David Fleet. Cartesian k-means. In CVPR, June 2013. find
  30. Bo Pang and Lillian Lee. Opinion mining and sentiment analysis. Foundations and trends in information retrieval, 2008. find
  31. Alexandre Sablayrolles, Matthijs Douze, Hervé Jégou, and Nicolas Usunier. How should we evaluate supervised hashing? arXiv preprint arXiv:1609.06753, 2016. — [arXiv:1609.06753](https://arxiv.org/abs/1609.06753) find
  32. Jorge Sánchez and Florent Perronnin. High-dimensional signature compression for large-scale image classification. In CVPR, 2011. find
  33. Anshumali Shrivastava and Ping Li. Asymmetric LSH for sublinear time maximum inner product search. In NIPS, pp. 2321–2329, 2014. find
  34. Andreas Stolcke. Entropy-based pruning of backoff language models. arXiv preprint cs/0006025, 2000. find
  35. David Talbot and Thorsten Brants. Randomized language models via perfect hash functions. In ACL, 2008. find
  36. Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. Yfcc100m: The new data in multimedia research. In Communications of the ACM, 2016. find
  37. Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey. arXiv preprint arXiv:1408.2927, 2014. — [arXiv:1408.2927](https://arxiv.org/abs/1408.2927) find
  38. Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data - A survey. CoRR, abs/1509.05472, 2015. — [arXiv:1509.05472](https://arxiv.org/abs/1509.05472) find
  39. Sida Wang and Christopher D Manning. Baselines and bigrams: Simple, good sentiment and topic classification. In ACL, 2012. find
  40. Kilian Q Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In ICML, 2009. find
  41. Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In NIPS, December 2009. find
  42. Yijun Xiao and Kyunghyun Cho. Efficient character-level document classification by combining convolution and recurrent layers. arXiv preprint arXiv:1602.00367, 2016. — [arXiv:1602.00367](https://arxiv.org/abs/1602.00367) find
  43. Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In NIPS, 2015. find our card