F10-SGD: Fast Training of Elastic-net Linear Models for Text Classification and Named-entity Recognition
Stanislav Peshterliev Alexander Hsieh Imre Kiss

[
    [
    December 30, 2023
=====================


Voice-assistants text classification and named-entity recognition (NER) models are trained on millions of example utterances. Because of the large datasets, long training time is one of the bottlenecks for releasing improved models. In this work, we develop F10-SGD, a fast optimizer for text classification and NER elastic-net linear models. On internal datasets, F10-SGD provides 4x reduction in training time compared to the OWL-QN optimizer without loss of accuracy or increase in model size. Furthermore, we incorporate biased sampling that prioritizes harder examples towards the end of the training. As a result, in addition to faster training, we were able to obtain statistically significant accuracy improvements for NER.

On public datasets, F10-SGD obtains 22% faster training time compared to FastText for text classification. And, 4x reduction in training time compared to CRFSuite OWL-QN for NER.




§ INTRODUCTION



Our commercial voice-assistant natural language understanding (NLU) system uses linear MaxEnt models <cit.> for text classification, and linear-chain CRF models <cit.> for named-entity recognition (NER). There are several desirable properties that makes these models suitable for NLU:


  * They achieve high accuracy given the right set of features <cit.>.

  * They produce probabilistic output, which allows combining multiple models in a recognition pipeline <cit.>.



  * They can be compressed to run on hardware-constrained devices <cit.>.


To train MaxEnt and CRF models, we minimize an objective function that includes the negative log-likelihood of the training dataset and elastic-net regularization. The elastic-net regularization combines the L1 and L2 penalties on the model weights. The L1 penalty, sum of absolute weights, serves as feature selection mechanism by forcing the unimportant model weights to zero. The L2 penalty, sum of squared weights, helps avoid overfitting by preventing weights that are excessively large.

A popular way to train elastic-net linear models is the Orthant-Wise Limited-memory Quasi-Newton Optimizer (OWL-QN) <cit.>. OWL-QN is a variant of the LBFGS <cit.> quasi-Newton optimization method that supports the L1 penalty. OWL-QN produces compact and accurate models, and it can be speed-up using multiple CPU threads. 

In our voice-assistant's NLU, we classify user utterance text into hundreds of classes. We have a hierarchical classification system, where we use MaxEnt to first perform domain classification (DC) and then intent classification (IC). DC predicts the general domain  of an utterance. IC predicts the user intent within a domain. For example, for the utterance “play music”, DC predict Music and IC predict PlayMusicIntent, and for the utterance “how is the weather”, DC predicts Weather and IC predicts GetWeatherIntent. This NLU architecture where intents are separated by domain allows us to efficiently train the IC models in parallel on their respective domain-specific training data. However, the MaxEnt DC training still has to be done on the entire training dataset. A DC model training with OWL-QN using 28 CPU threads on 50 million utterances takes around 2 hours. 

For NER, we use one CRF model per domain to recognize domain-specific named-entities, such as artist name and song name for the Music domain. For example, in the sentence “play desert rose by sting”, NER labels “desert rose” as a song and “sting” as an artist. The CRF models are more complex and slower to train compared to the MaxEnt models. An NER model training with OWL-QN using 28 CPU threads on a large domain with 6 million utterances takes around 2 hours 40 min.


Continuous improvement of the NLU system requires frequent retraining of the DC, IC, and NER models. However, the long training times for DC and NER are a bottleneck. In this work, we focus on machine learning optimization methods to improve training efficiency. We develop a fast optimizer called F10-SGD which on large internal datasets trains MaxEnt and CRF models 4 times faster compared to OWL-QN without loss of accuracy or increase in the model size.

Our contributions are the following:


  * We combine Stochastic Gradient Descent (SGD) optimization techniques for parallel training and elastic-net regularization into a fast and accurate trainer.

  * We improve the accuracy of the NER model using biased sampling that prioritizes harder examples towards the end of the training.


  * We perform evaluations on internal and public datasets. On internal datasets, F10-SGD is 4x faster with half the CPU threads compared to OWL-QN. On external datasets, we speed-up training by 22% and 3.4-3.7x against FastText and CRFSuite respectively.



Why not GPU? An important constrain for our use case is to develop a fast optimizer for CPU instead of GPU. Our model building platform trains many models per week, and allocating GPU for each training is expensive.



§ RELATED WORK




<cit.> advocated for using SGD in large scale machine learning optimization. He developed CRFSGD[<http://leon.bottou.org/projects/sgd>] and demonstrated the effectiveness of SGD for training CRF models. <cit.> developed the popular CRFSuite toolkit, which includes an SGD trainer based on CRFSGD, and an optimized implementation of the OWL-QN trainer. A limitation of both CRFSGD and CRFSuite is that they do not use multiple CPU threads to speed up training. Also, their SGD implementations do not support L1 regularization.






 
Scikit-learn <cit.> and Vowpal Wabbit <cit.> provide fast SGD implementations for logistic regression models (note that logistic regression is equivalent MaxEnt). Both support L1 regularization using cumulative penalty <cit.> and truncated gradient <cit.>. Scikit-learn SGD does not support parallel SGD, and in Vowpal Wabbit parallel SGD is not supported, though it can be simulated via sending raw training examples over sockets to multiple Vowpal Wabbit processes that share the same memory.

FastText <cit.> is linear embedding model for text classification. It supports asynchronous multi-threaded SGD training via Hogwild <cit.>, which makes training fast. However, FastText does not support L2 or dropout regularization, leading to suboptimal performance on small datasets. Also, it does not support L1 for feature selection, but it does have a quantization option <cit.> to reduce the model size after training.



§ BACKGROUND




 §.§ Elastic-net Linear Models


Probabilistic linear models have the general form as shown in Equation <ref>, where x is an input example, y is a prediction target, w_i is a weight for the feature function ϕ_i, and Z is a partition function that normalizes the probability. If the prediction target y is a class as in IC and DC, the model is a MaxEnt. If the prediction target y is sequence of labels as in NER, the model is a CRF.





    p(x|y)    = 1/Z(x)exp∑_i w_i ϕ_i(x,y)


Equation <ref> shows the optimization objective for MaxEnt and CRF. It includes the negative log-likelihood over the training set D with size N, and the L1 and L2 penalties.





    F(w) =   ∑_j^N L_j(w) + λ_1 w_1 + λ_2/2w_2^2 
    
    L_j(w)    = -log p(y_j | x_j; w)


To optimize F, we use the gradient ∇ F in Equation <ref>. The function  returns: -1 for negative, 1 positive, or 0 for every weight of w.  is necessary to define the sub-gradient of F for zero weights since the absolute |·| function in the L1 penalty is not differentiable at zero.



    ∇ F    = ∑_j^N ∇ L_j + λ_1 (w) +  λ_2 w


The definitions of ∇ L_j and p(x|y) differ for MaxEnt and CRF, and are not covered in this paper.



 §.§ OWL-QN


OWL-QN is an optimization method that iteratively adjusts the model parameters towards the optimal value. Algorithm <ref> provides a high-level simplified description of OWL-QN that helps explain its computational bottlenecks, but does not describe the algorithm in details.





OWL-QN approximates the inverse hessian H^e using the last m weight differences V, and gradient differences G. The quality of the approximation H^e depends on the size m, a recommended value for m is between 4 and 7.



In step 3, OWL-QN computes an update direction d using H^e and the gradient ∇^e F over N training examples. Then, in step 4 it performs a line search in the direction d. For a large N even one epoch takes significant time, and OWL-QN typically needs m epochs to find good approximation H^e, and tens or even hundreds of epochs to converge.

Parallelization. We can speed-up OWL-QN by using multiple CPU threads to compute F and ∇ F. Each CPU thread t receives a subset of the training dataset D and computes the forward scores ∑_j^D_t L_j and the gradients ∑_j^D_t∇ L_j. Then, the results are aggregated to compute F and ∇ F.



§ F10-SGD




We propose using SGD as a fast alternative to OWL-QN for training MaxEnt and CRF models. Similar to OWL-QN, SGD is an iterative optimization method. It uses the gradient approximation ∇ F_j in Equation <ref>. ∇ F_j is calculated from ∇ L_j for a single random training example. The weights w are then updated with learning rate α, without relying on the inverse hessian. Since w is updated many times during a single epoch, SGD typically needs fewer epochs to converge compared to OWL-QN. 





    ∇ F_j    = ∇ L_j + λ^'_1 (w) + λ^'_2 w
    λ^'_1    = λ_1/N  λ^'_2 = λ_2/N


In ∇ F_j we divide λ_1 and λ_2 by the number of examples N since w is updated N times per epoch.

F10-SGD in Algorithm <ref> is a parallel version of SGD, also known as Hogwild. Each CPU thread t receives a random subset of the training dataset D, and updates the weights w. The weight updates are not synchronized, so it is possible for threads to override each other. However, the algorithm has a nearly optimal rate of convergence for models where many training examples have non-overlapping features <cit.>, which is the case for linear MaxEnt and CRF models.








Learning Rate. For SGD to converge, it is critical that the learning rate α is neither too large nor too small. We start with an initial learning rate α_0, and decay it linearly during training using αα_0 (1 - k / N ×𝐸𝑝𝑜𝑐ℎ𝑠) <cit.>. We tune α_0 on a held-out development set using grid search.







The learning rate α depends on the iteration counter k. To have the same α with multiple threads  across identical runs, we have to update k atomically. Otherwise, α is going to differ, which causes fluctuation of the weights w and makes it harder to reproduce previous models. The same atomicity consideration applies to the L1 and L2 algorithms below. 

















 §.§ Lazy Updates




For linear MaxEnt and CRF models, w typically has millions of weights for features corresponding to different words and phrases in the training data. Fortunately, a single example j has only a small set of active features ϕ_i(x_j, y_j), so we can compute ∇ L_j efficiently using only the weights i. However, the computation of ∇ F_j requires applying the L1 and L2 penalties of the full weight vector w which is slow. Thus, it is essential to perform “lazy” L1 and L2 updates only on the active features.

Lazy L2. To make the L2 update lazy, we use the weight rescaling approach in Algorithm <ref> <cit.>. The key observation is that the L2 penalty can be seen as rescaling w by (1 - αλ^'_2) at every update, Equations <ref>-<ref>. Thus, we can represent w^k as ŵ^k s_k and update the unscaled weights ŵ^k and the scaler s_k independently. At the end of every epoch, we multiply the weights ŵ^k_i by s_k and reset s_k  1. 





    w^k + 1w^k - α∇^k L_j - αλ^'_2 w^k 
    w^k + 1w^k (1 - αλ^'_2) - α∇^k L_j



















    ŵ^k + 1ŵ^k + 1/2 - αλ^'_1 (ŵ^ks_k)

Lazy L1. To make the L1 update lazy, we use the cumulative L1 penalty approach <cit.> in Algorithm <ref>. First, from Equation <ref>, we note that the L1 update rarely makes weights ŵ zero, so it does reduce model size. Thus, we modify the L1 update to clip weights to zero if they cross the zero threshold after applying the L1 penalty. Second, to lazily update a weight ŵ^k_i, we have to maintain the cumulative L1 penalty u_k, the L1 penalty that is already applied to the weight q^k_i, and update the weight with the difference, steps 6 and 8 of Algorithm <ref>. At the end of every epoch, we run  for every weight i and reset u_k+1  0 and q^k+1_i  0.


Note that in step 3 we have to divide by the scaler s_k+1 to boost the L1 penalty in order to account for the L2 regularization.





 §.§ Active Bias Sampling


Active bias sampling <cit.> is a technique that can speed-up SGD convergence by emphasizing harder examples towards the end of the training. This is useful for NLU since there are many frequent training examples that are easy and can be deprioritize, e.g. “play music”, “how is the weather”, “stop”. 

In Algorithm <ref>, we add active bias sampling to F10-SGD by replacing the random shuffle with sampling form discrete distribution P_s(j) at specified epoch. P_s(j) assigns higher probability to medium confidence examples, and lower probability to high and low confidence examples. We prioritize medium confidence examples and not low confidence ones, as the latter are more likely to be outliers.




We define P_s(j) in Equation <ref>. p̅_h(x_j|y_j) is the average of the past h iteration probabilities p^k(x_j|y_j). The term 1 - p̅_h(x_j|y_j) can be interpreted as the union of the alternative prediction probabilities. And, ε is a smoothing prior that makes sure we assign non-zero probability to training examples with confidence close to one, otherwise the model may “forget” to recognize them.





    P_s(j)    = p̅_h(x_j|y_j)(1 - p̅_h(x_j|y_j)) + ε
    ε   = 1N∑_j^N p̅_h(x_j|y_j) (1 - p̅_h(x_j|y_j))















In addition to sampling from P_s, we change the learning rate of the examples that we sampled. This way, we unbias the gradient estimation and ensure convergence <cit.>. For each sample j, we have an importance weight v_j = P_s(j) / V that is multiplied to the learning rate α. Where V = 1N∑_j^N p̅_h(x_j|y_j) (1 - p̅_h(x_j|y_j)) + ε is normalization factor that makes 1N∑_j^N v_j = 1, i.e. we do not change the global learning rate.





§ RESULTS



We evaluated F10-SGD on internal and public datasets. We used a Linux machine with Intel Xeon E5-2670 2.60 GHz 32 cores processor and 244 GB memory. The code is compiled with GCC 4.9 and -O3 optimization flags.

Evaluation metrics. We use accuracy for MaxEnt and F1 score for NER[<github.com/sighsmile/conlleval>]. We test for statistically significant differences using the Wilcoxon test <cit.> with 1000 bootstrap resamples and p-value < 0.05.



 §.§ Internal Datasets


We evaluated F10-SGD against OWL-QN for DC, and the NER domains Music, Shopping and Cinema. The datasets details are in Table <ref>. We use the development dataset for tuning the learning rate α and the L1/L2 hyper-parameters.

The reported speed improvements are only caused by the change in the optimizer. Since, the feature extraction, decoding, and model serialization are unchanged.



 
































MaxEnt DC. Table <ref> shows the MaxEnt DC results. The accuracy difference between F10-SGD and OWL-QN is not statistically significant, although F10-SGD accuracy is slightly higher. For DC, F10-SGD  AB does not bring additional accuracy improvements. The reason is that the model learns to assign high confidence to most of the sentences in the first 7 epochs of the training, and there are not many medium confidence sentences for the active bias sampling to prioritize. The training speeds of F10-SGD and F10-SGD AB are approximately 4x faster with half the number of CPU threads compared to OWL-QN. It takes only 10 epochs for SGD to reach the same accuracy level of OWL-QN with 250 epochs. Also, we get an additional 20% speed up if we use 28 CPU threads.






Note that the Hogwild SGD does not scale linearly with the number of CPU threads <cit.>. Training with 28 CPU threads is only 20% faster than with 14 CPU threads. That is because of memory contention between the different threads for updating the shared parameter vector. When using more CPU threads, we get increased accuracy fluctuations from 0.02 to 0.04 across training runs.





CRF Domain NER. In Table <ref>, the F1 score difference between OWL-QN and F10-SGD is not statistically significant for Music NER and Cinema NER, and statistically significantly worse for Shopping NER. F10-SGD AB statistically significantly improves F1 score for the Music and Cinema NER models, and for Shopping the F10-SGD AB difference with OWL-QN is not statistically significant. Similar to DC, the training speed of F10-SGD and F10-SGD AB is about 4x faster with half the number of CPU threads compared to OWL-QN. It takes only 10 epochs for F10-SGD AB to reach a comparable or better level of F1 score as 200 epochs with OWL-QN. Also, for Music NER, we get an additional 36% speed up if we use 28 CPU threads. When training with 28 CPU threads, the F1 score fluctuation increases from 0.02 to 0.05.

We performed additional experiments on 24 domains, but for lack of space we do not present the results. The average training time reduction was 4x and the relative F1 score improvement of 0.5%.









 §.§ Public Datasets


We tested F10-SGD on public datasets against FastText (version from November 2018) for text classification and against CRFSuite (version 0.12) for NER. Both packages provide on of the fastest public implementations for their respective tasks.

MaxEnt. For the text classification evaluations, we used 8 datasets prepared by <cit.>. We tuned the hyper-parameters for MaxEnt and FastText on a part of the training data, and used 5 epochs and 4 threads for training. For FastText we used 10 word embedding dimension, which is the same as <cit.>.

Table <ref> shows the results. F10-SGD MaxEnt achieves 22% relative speed-up compared to FastText, and it's faster to train on 7 out of 8 datasets. The MaxEnt models are faster to train on datasets with smaller number of classes, and the FastText models are comparable or faster with large number of classes because the dense output layer of FastText is CPU cache efficient. Furthermore, the MaxEnt models have smaller size compared to the FastText models because the former's vocabulary is pruned by the L1 regularization. The accuracy is comparable at 0.28% average relative difference.



CRF. For the NER evaluations, we used the CoNLL-2003 English NER dataset <cit.>, and the Ontonotes 5.0 English NER dataset <cit.>. We tuned the CRF hyper-parameters on the dedicated development sets, and we used one thread for training because CRFSuite does not support training with multiple threads.

Table <ref> shows the results. F10-SGD CRF achieves 3.4x-3.7x relative speed-up compared to CRFSuite with the OWL-QN optimizer. We trained with 10 and 20 epochs for F10-SGD and 50 and 100 epochs for CRFSuite. For both algorithms less epochs degrade F1 and more epochs do not improve F1. The F1 score differences between the best configurations for F10-SGD and CRFSuite are not statistically significant. F10-SGD AB does not improve the F1 score on the public datasets because there are less “easy” examples to deprioritize compared to the internal NLU datasets.











§ CONCLUSIONS



Fast model training is important for continuous improvement of voice-assistant's NLU. However, training times are increasing as our datasets are growing. To reduce model training time, we developed the F10-SGD optimizer that can train elastic-net linear models for text classification and NER up to 4x faster compared to OWL-QN. This is accomplished without loss of accuracy or increase in model size. In addition, F10-SGD with active bias sampling provides small but statistically significant improvements in NER F1 scores on NLU datasets.







acl_natbib

