FastText.zip: Compressing text classification models

Armand JoulinEdouard GravePiotr BojanowskiMatthijs DouzeHervé JégouTomas Mikolov

article2016arXiv1,365 citations

Proposes a product quantization approach to compress text classification models by two orders of magnitude with minimal accuracy loss, enabling fastText deployment on memory-constrained devices.

Listen

Text classification is vital for applications such as search ranking, email sorting, and spam filtering. However, standard high-performing models often require gigabytes of memory to store large vocabularies and embedding matrices, making on-device deployment difficult on resource-constrained platforms like smartphones.

The article demonstrates an effective compression pipeline that shrinks text classification models by multiple orders of magnitude while preserving competitive accuracy and fast processing speeds.

The researchers evaluated their approach on eight standard benchmark datasets and a large-scale hashtag prediction dataset with over 300,000 output labels. They combined several techniques: product quantization (a method that splits vectors into smaller pieces to store them compactly), separate encoding of vector magnitude and angle, vocabulary pruning based on feature importance and training-set coverage, and dictionary hashing.

The key findings show that standard product quantization compresses models by a factor of 10 without meaningful accuracy loss. When paired with structured vocabulary pruning and hashing, the pipeline achieves extreme compression—reducing model footprints by a factor of 1,000 to 4,000 (often shrinking models from over 100 megabytes down to less than 64 kilobytes) with an average accuracy drop of less than one percent. Retraining the output layer after compressing input matrices compensates for quantization distortions, and max-coverage pruning maintains strong predictive performance on massive datasets where naive pruning methods fail.

These results demonstrate that engineering teams can deploy lightweight, accurate language classifiers locally on edge hardware, substantially reducing server infrastructure costs, cloud latency, and memory overhead compared to heavier neural network alternatives.

Decision-makers should consider adopting this compression pipeline for embedded or mobile text processing tasks. If deployment demands extreme size reduction, teams should test model-specific cut-offs to ensure required feature coverage. Future work could explore scaling vector dimensions based on feature frequencies and splitting low-value words into character sub-units to further optimize performance on short inputs.

arXiv: 1612.03651
Cover for FastText.zip: Compressing text classification models

Abstract

We consider the problem of producing compact architectures for text classification, such that the full model fits in a limited amount of memory. After considering different solutions inspired by the hashing literature, we propose a method built upon product quantization to store word embeddings. While the original technique leads to a loss in accuracy, we adapt this method to circumvent quantization artefacts. Our experiments carried out on several benchmarks show that our approach typically requires two orders of magnitude less memory than fastText while being only slightly inferior with respect to accuracy. As a result, it outperforms the state of the art by a good margin in terms of the compromise between memory usage and accuracy.

Table of Contents

  • 1 Introduction
  • 2 Related work
  • 3 Proposed approach
  • 3.1 Text classification
  • 3.2 Bottom-up product quantization
  • 3.3 Further text specific tricks
  • 4 Experiments
  • 4.1 Small datasets
  • 4.2 Large dataset: FlickrTag
  • 5 Future Work
  • 6 Conclusion
  • References

Knowls

  1. Knowl 1 — Normalized Product Quantization for Word and N-Gram Embeddings

    model/method

    In linear text classification models, storing dense embedding matrices for large vocabularies and n-grams requires substantial memory. Standard Product Quantization (PQ) splits a dd-dimensional vector x∈Rd\mathbf{x} \in \mathbb{R}^d into kk subvectors x1,…,xk∈Rd/k\mathbf{x}^1, \dots, \mathbf{x}^k \in \mathbb{R}^{d/k} and quantizes each subvector to the nearest centroid among 2b2^b codebook centroids (b=8b=8 bits per subquantizer) using kk-means:

    x^=∑i=1kqi(xi)\hat{\mathbf{x}} = \sum_{i=1}^k q_i(\mathbf{x}^i)

    However, text embedding norms vary widely (by ratios up to 1000:11000:1 between maximum and minimum norms). Because standard kk-means minimizes squared L2L_2 reconstruction error, it tends to map low-norm vectors to zero, severely hurting classification accuracy.

    Normalized Product Quantization (NPQ) circumvents this artifact by decomposing each embedding vector x\mathbf{x} into its scalar L2L_2 norm ∥x∥2\|\mathbf{x}\|_2 and its unit-direction vector u=x/∥x∥2\mathbf{u} = \mathbf{x} / \|\mathbf{x}\|_2:

    1. The direction vector u\mathbf{u} is quantized into kk subquantizers (k∈[2,d/2]k \in [2, d/2], typically k=d/2k = d/2).
    2. The scalar norm ∥x∥2\|\mathbf{x}\|_2 is quantized separately into a 1-dimensional codebook of 2b2^b scalar values using an additional bb bits (typically 1 extra byte per vector).

    This magnitude/direction decoupling allows faithful reconstruction of low-norm discriminative embeddings with no significant drop in classification performance.

  2. Knowl 2 — Bottom-Up Retraining for Quantized Factorized Classifiers

    model/method

    For any vector quantizer satisfying the Lloyd optimality conditions, the reconstructed vector magnitude is systematically underestimated because the expected squared magnitude is reduced by the mean quantization error:

    E[∥x^∥2]=E[∥x∥2]−E[∥x−x^∥2]\mathbb{E}[\|\hat{\mathbf{x}}\|^2] = \mathbb{E}[\|\mathbf{x}\|^2] - \mathbb{E}[\|\mathbf{x} - \hat{\mathbf{x}}\|^2]

    In a low-rank linear text classifier parameterized as f(xn)=BAxnf(\mathbf{x}_n) = B A \mathbf{x}_n, where A∈Rd×VA \in \mathbb{R}^{d \times V} is the input feature embedding matrix and B∈RC×dB \in \mathbb{R}^{C \times d} is the linear output classification matrix over CC classes, direct off-the-shelf quantization of AA and BB degrades classification accuracy by 0.1%0.1\% to 0.5%0.5\%.

    To correct for this distortion, a bottom-up retraining procedure is applied:

    1. The input embedding matrix AA is quantized into A^\hat{A} using product quantization.
    2. The input matrix is frozen at A^\hat{A}, and the uncompressed output matrix BB is retrained on the training data to adapt its weights to the quantized input representations.
    3. The retrained output matrix BB is quantized into B^\hat{B} using product quantization.

    This bottom-up retraining recovers the loss in classification accuracy across diverse datasets.

  3. Knowl 3 — Online Max-Cover Vocabulary Pruning

    algorithm

    When reducing vocabulary size by keeping only a budget of KK features (words and n-grams), purely ranking embeddings by norm can leave certain training documents with zero retained features. To guarantee document coverage while maximizing retained representation weight, feature selection is posed as a constrained set-cover problem:

    max⁡S⊆V∑s∈Swss.t.∣S∣≤K,P1S≥1∣D∣\max_{S \subseteq V} \sum_{s \in S} w_s \quad \text{s.t.} \quad |S| \le K, \quad P \mathbf{1}_S \ge \mathbf{1}_{|\mathcal{D}|}

    where VV is the full set of vocabulary features, D\mathcal{D} is the training document collection, ws=∥as∥2w_s = \|\mathbf{a}_s\|_2 is the L2L_2 norm of the embedding vector as\mathbf{a}_s corresponding to feature ss, and P∈{0,1}∣D∣×∣V∣P \in \{0, 1\}^{|\mathcal{D}| \times |V|} is the binary document-feature occurrence matrix (Pd,s=1P_{d,s} = 1 if feature ss occurs in document dd).

    The optimization is solved using an online greedy algorithm:

    Input: Training document collection D\mathcal{D}, feature set VV, feature weights ws=∥as∥2w_s = \|\mathbf{a}_s\|_2, budget KK
    Output: Selected feature subset SS
    S←∅S \leftarrow \emptyset
    for each document d∈Dd \in \mathcal{D} do
        if no feature in document dd belongs to SS then
            s∗←arg⁡max⁡s∈dwss^* \leftarrow \arg\max_{s \in d} w_s
            S←S∪{s∗}S \leftarrow S \cup \{s^*\}
        end if
    end for
    if ∣S∣<K|S| < K then
        R←V∖SR \leftarrow V \setminus S
        sort RR in descending order of wsw_s
        S←S∪first (K−∣S∣) elements of RS \leftarrow S \cup \text{first } (K - |S|) \text{ elements of } R
    end if
    return SS
  4. Knowl 4 — Norm-Based vs. Entropy-Based Vocabulary Pruning

    empirical result

    Selecting features based on the L2L_2 norm of their trained embedding vectors ∥as∥2\|\mathbf{a}_s\|_2 outperforms unsupervised frequency- or entropy-based selection for text classifier compression. High-entropy/frequency words are dominated by non-discriminative stopwords and punctuation, whereas high-norm embeddings correspond to strongly class-discriminative tokens.

    Word Entropy Rank Norm Rank Word Entropy Rank Norm Rank
    . 1 354 mediocre 1399 1
    , 2 176 disappointing 454 2
    the 3 179 so-so 2809 3
    and 4 1639 lacks 1244 4
    i 5 2374 worthless 1757 5
    a 6 970 dreadful 4358 6
    to 7 1775 drm 6395 7
    it 8 1956 poorly 716 8
    of 9 2815 uninspired 4245 9
    this 10 3275 worst 402 10

    On the Amazon full review dataset, the top 10 words ranked by entropy consist entirely of punctuation and stopwords (e.g., '.', ',', 'the', 'and'), all having low norm ranks. Conversely, the top 10 words ranked by embedding norm are sentiment-laden terms ('mediocre', 'disappointing', 'worst', 'worthless') that provide high discriminative power despite moderate corpus frequency.

  5. Knowl 5 — Dictionary Elimination via Feature Hashing and Index Pruning

    model/method

    Storing raw character strings for words and n-grams in the dictionary accounts for 1 to 2 MB of memory in standard models. This overhead is eliminated by mapping both words and n-grams directly into a fixed set of MM hash buckets using a hash function.

    When vocabulary pruning is combined with feature hashing to retain only KK active bucket embeddings:

    1. Sorted Index List + Binary Search: An array of the KK surviving bucket indices is stored. At test time, verifying whether a hashed feature belongs to the pruned vocabulary requires a binary search with time complexity O(log⁡K)O(\log K) and a memory footprint of several hundred kilobytes.
    2. Bloom Filter Alternative: A Bloom filter achieves O(1)O(1) membership testing at test time with lower memory overhead, but false positives introduce corrupted embedding lookups that degrade test accuracy compared to exact index tables.
  6. Knowl 6 — Extreme Compression Performance on Standard Text Classification Benchmarks

    data/table

    Combining Normalized Product Quantization with k=1k = 1 subquantizer, feature hashing, and aggressive norm-based feature pruning compresses fastText models to under 64 KiB64\,\text{KiB}, 32 KiB32\,\text{KiB}, and 16 KiB16\,\text{KiB} on standard sentiment and topic classification datasets (d=8d=8, 2M initial buckets).

    Dataset Full Size Full Acc. (%) 64KiB Acc. (%) 32KiB Acc. (%) 16KiB Acc. (%)
    AG 65M 92.1 91.4 90.6 89.1
    Amazon full 108M 60.0 58.8 56.0 52.9
    Amazon pol. 113M 94.5 93.3 92.1 89.3
    DBPedia 87M 98.4 98.2 98.1 97.4
    Sogou 73M 96.4 96.4 96.3 95.5
    Yahoo 122M 72.1 70.0 69.0 69.2
    Yelp full 78M 63.8 63.2 62.4 58.7
    Yelp pol. 77M 95.7 95.3 94.9 93.2
    Average diff. 0.0 -0.8 -1.7 -3.5

    Compared to uncompressed models of size 65–122 MB, the compressed models achieve compression factors between ×1000\times 1000 and ×4000\times 4000 with an average accuracy drop of only 0.8%0.8\% at 64 KiB64\,\text{KiB} and 1.7%1.7\% at 32 KiB32\,\text{KiB}.

  7. Knowl 7 — Model Size and Accuracy Comparison with Character-Level CNNs

    data/table

    FastText combined with Normalized Product Quantization (k=d/2k = d/2) and vocabulary pruning matches or outperforms character-level Convolutional Neural Networks (CNNs) in classification accuracy while requiring two to three orders of magnitude less memory at inference time.

    Dataset Zhang et al. (2015) Xiao Cho (2016) fastText+PQ (k=d/2k=d/2)
    Acc. (%) Size Acc. (%) Size Acc. (%) Size (RAM)
    AG 90.2 108M 91.4 80M 91.9 889K
    Amazon full 59.5 10.8M 59.2 1.6M 59.6 449K
    Amazon pol. 94.5 10.8M 94.1 1.6M 94.3 449K
    DBPedia 98.3 108M 98.6 1.2M 98.5 98K
    Sogou 95.1 108M 95.2 1.6M 96.5 98K
    Yahoo 70.5 108M 71.4 80M 71.7 889K
    Yelp full 61.6 108M 61.8 1.4M 63.3 98K
    Yelp pol. 94.8 108M 94.5 1.2M 95.5 449K

    CNN sizes assume float32 storage, while fastText+PQ reports active memory consumed in RAM during test time. Across all 8 benchmarks, fastText+PQ operates in under 1 MB of RAM while achieving equal or higher accuracy than character CNN architectures.

  8. Knowl 8 — Large-Scale Multi-Class Quantization and Pruning on FlickrTag

    empirical result

    On the FlickrTag hashtag prediction task (312,116 classes, 1,427,667 words, 10M n-gram buckets, hierarchical softmax, embedding dimension d=256d=256), the uncompressed baseline occupies 12 GiB12\,\text{GiB} and achieves 45.4%45.4\% accuracy.

    1. Input and Output Matrix Quantization: Applying product quantization (k=128k=128) to both input matrix AA and output matrix BB, combined with separate norm encoding and bottom-up retraining, reduces model size from 12 GiB12\,\text{GiB} to 1.5 GiB1.5\,\text{GiB} (8×8\times reduction) with zero loss in test accuracy (45.4%45.4\%).
    2. Pruning Method Comparison: When pruning the quantized model down to 2M and 1M embeddings, Max-Cover pruning preserves 88.4%88.4\% test set document coverage (identical to the unpruned full model) and maintains 45.5%45.5\% and 43.9%43.9\% accuracy at 305 MiB305\,\text{MiB} and 179 MiB179\,\text{MiB} respectively.
    3. Failure of Naive Pruning: Naive norm pruning drops test coverage to 73.2%73.2\% (2M) and 61.9%61.9\% (1M), yielding lower accuracy (41.6%41.6\% and 35.8%35.8\%). Entropy pruning drops coverage to 70.5%70.5\%, yielding 32.1%32.1\% (2M) and 30.5%30.5\% (1M) accuracy.

Coverage note — None was omitted; all primary contributions—including Normalized Product Quantization (NPQ), separate norm encoding, bottom-up retraining, online max-cover pruning, hashing/Bloom filter dictionary reduction, and empirical evaluations on standard benchmarks and the large-scale FlickrTag dataset—are fully covered.

References

  1. 1.Alekh Agarwal, Olivier Chapelle, Miroslav Dud<unk>ık, and John Langford. A reliable effective terascale linear learning system. Journal of Machine Learning Research, 15(1):1111–1133, 2014.
  2. 2.Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity-inducing penalties. Foundations and Trends<unk><sup>®</sup> in Machine Learning, 4(1):1–106, 2012.
  3. 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.
  4. 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.
  5. 5.Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pp. 380–388, May 2002.
  6. 6.Welin Chen, David Grangier, and Michael Auli. Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906, 2015.
  7. 7.Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Max-cover in map-reduce. In International Conference on World Wide Web, 2010.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 12.Uriel Feige. A threshold of ln n for approximating set cover. JACM, 45(4):634–652, 1998.
  13. 13.Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In CVPR, June 2013.
  14. 14.Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, June 2011.
  15. 15.Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional networks using vector quantization. arXiv preprint arXiv:1412.6115, 2014.
  16. 16.Edouard Grave, Armand Joulin, Moustapha Ciss<unk>é, David Grangier, and Herv<unk>é J<unk>égou. Efficient softmax approximation for gpus. arXiv preprint arXiv:1609.04309, 2016.
  17. 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.
  18. 18.Herv<unk>é J<unk>égou, Matthijs Douze, and Cordelia Schmid. Hamming embedding and weak geometric consistency for large scale image search. In ECCV, October 2008.
  19. 19.Herv<unk>é J<unk>égou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. PAMI, January 2011.
  20. 20.Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. Springer, 1998.
  21. 21.Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. Bag of tricks for efficient text classification. arXiv preprint arXiv:1607.01759, 2016.
  22. 22.Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. NIPS, 2:598–605, 1990.
  23. 23.Zhouhan Lin, Matthieu Courbariaux, Roland Memisevic, and Yoshua Bengio. Neural networks with few multiplications. arXiv preprint arXiv:1510.03009, 2015.
  24. 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.
  25. 25.Lukas Meier, Sara Van De Geer, and Peter B<unk>ùhlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):53–71, 2008.
  26. 26.Tomas Mikolov. Statistical language models based on neural networks. In PhD thesis. VUT Brno, 2012.
  27. 27.Tomas Mikolov, Ilya Sutskever, Anoop Deoras, Hai-Son Le, Stefan Kombrink, and J Cernocky. Subword language modeling with neural networks. preprint, 2012.
  28. 28.Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric lshs for inner product search. In ICML, pp. 1926–1934, 2015.
  29. 29.Mohammad Norouzi and David Fleet. Cartesian k-means. In CVPR, June 2013.
  30. 30.Bo Pang and Lillian Lee. Opinion mining and sentiment analysis. Foundations and trends in information retrieval, 2008.
  31. 31.Alexandre Sablayrolles, Matthijs Douze, Herv<unk>é J<unk>égou, and Nicolas Usunier. How should we evaluate supervised hashing? arXiv preprint arXiv:1609.06753, 2016.
  32. 32.Jorge S<unk>ánchez and Florent Perronnin. High-dimensional signature compression for large-scale image classification. In CVPR, 2011.
  33. 33.Anshumali Shrivastava and Ping Li. Asymmetric LSH for sublinear time maximum inner product search. In NIPS, pp. 2321–2329, 2014.
  34. 34.Andreas Stolcke. Entropy-based pruning of backoff language models. arXiv preprint cs/0006025, 2000.
  35. 35.David Talbot and Thorsten Brants. Randomized language models via perfect hash functions. In ACL, 2008.
  36. 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.
  37. 37.Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey. arXiv preprint arXiv:1408.2927, 2014.
  38. 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.
  39. 39.Sida Wang and Christopher D Manning. Baselines and bigrams: Simple, good sentiment and topic classification. In ACL, 2012.
  40. 40.Kilian Q Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In ICML, 2009.
  41. 41.Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In NIPS, December 2009.
  42. 42.Yijun Xiao and Kyunghyun Cho. Efficient character-level document classification by combining convolution and recurrent layers. arXiv preprint arXiv:1602.00367, 2016.
  43. 43.Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In NIPS, 2015.

Citation

MLA
Joulin, A., et al. “FastText.zip: Compressing Text Classification Models”. arXiv, 2016, http://arxiv.org/abs/1612.03651v1.
APA
Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., & Mikolov, T. (2016). FastText.zip: Compressing text classification models. arXiv. http://arxiv.org/abs/1612.03651v1
Chicago
Joulin, A., E. Grave, P. Bojanowski, M. Douze, H. Jégou, and T. Mikolov. 2016. “FastText.zip: Compressing Text Classification Models”. arXiv. http://arxiv.org/abs/1612.03651v1.
Harvard
Joulin, A. et al. (2016) “FastText.zip: Compressing text classification models”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1612.03651v1.
Vancouver
1. Joulin A, Grave E, Bojanowski P, Douze M, Jégou H, Mikolov T (2016) FastText.zip: Compressing text classification models. arXiv

BibTeX

@article{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},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1612.03651v1},
  eprint = {1612.03651}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Published with permission