{'fraction_non_alphanumeric': 0.050443378398022966, 'fraction_numerical': 0.013858603479187867, 'mean_word_length': 4.399790685504971, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient MDI Adaptation for n-gram Language Models

This paper presents an efficient algorithm for n-gram language model adaptation under the minimum discrimination information (MDI) principle, where an out-of-domain language model is adapted to satisfy the constraints of marginal probabilities of the in-domain data. The challenge for MDI language model adaptation is its computational complexity. By taking advantage of the backoff structure of n-gram model and the idea of hierarchical training method, originally proposed for maximum entropy (ME) language models, we show that MDI adaptation can be computed in linear-time complexity to the inputs in each iteration. The complexity remains the same as ME models, although MDI is more general than ME. This makes MDI adaptation practical for large corpus and vocabulary. Experimental results confirm the scalability of our algorithm on very large datasets, while MDI adaptation gets slightly worse perplexity but better word error rate results compared to simple linear interpolation.


Introduction
The n-gram language model (LM) still plays an important role in today's automatic speech recognition (ASR) pipeline. There are several reasons: (i) n-gram LMs can be represented by weighted finite-state transducers (WFST) and integrated into first-pass decoding [2], (ii) training and querying n-gram LMs are cheaper than neural LMs, (iii) in practice, the best performance is achieved by interpolating n-gram and neural LMs [3].
Consider a common scenario when one hopes to develop an ASR system for a new application, while little training data is available and collecting sufficient domain-specific (in-domain) data requires a considerable amount of time and efforts. The limited data is too small to estimate a robust LM. Fortunately, we can do better by capitalizing on some large, general-domain background (out-of-domain) corpus assuming the out-of-domain data may contain much information common with the application domain. This motivates LM adaptation [4,5], which is to estimate a robust LM based on both in-and out-of-domain data.
The question is how to combine information from the two sources in a suitable manner? The commonly used approaches for n-gram LMs fall under two categories: model interpolation and constraint-based methods. The model interpolation methods can be either linear (simple linear [6], history-dependent [7], Bayesian [8] interpolation) or non-linear (log-linear [9] interpolation, fill-up technique [10]). Note that simple linear interpolation is very effective and probably the most popular adaptation method. Recently, [8] found that count-merging, as a special case of maximum a posterior (MAP) adaptation, is theoretically similar to Bayesian interpolation. On the other hand, the constraintbased methods [11], such as ME or MDI models, attempt to choose the adapted LM such that it satisfies some constraints in the adaptation domain, while staying as close as possible to some prior distribution, measured by, e.g., Kullback-Leibler distance. This paper investigates the MDI adaptation.
There has been previous work on MDI adaptation for n-gram LMs [12,13,14,15,16,17,18,19,20,21], with several variants of task definition, e.g., adaptation for cache model, withinor cross-corpus adaptation. Although MDI has appealing theoretical properties, the computation is non-trivial and expensive, which grows almost exponentially (detailed in section 3) with the size of the vocabulary [5] in a naive implementation. To reduce the complexity, [18,16] proposed approximation algorithms and [22,23] devised parallelization to speed up the computation. [17] proposed a linear-time algorithm for unigram constraints. On the other hand, there has been work on ME model that utilizes the back-off structure of the LMs to reduce computational complexity to linear time per iteration [1], but it is not clear whether the same trick can carry over to MDI which is more general than ME. Besides, regarding model performance, most previous work has found that MDI adaptation performs slightly worse than simple linear interpolation [20], but we are interested to see if there can be any difference when operating on very large corpus once we have an efficient MDI algorithm for arbitrary marginal distribution constraints. Moreover, in the experiment, we will propose a novel approach of applying MDI adaptation to improve the firstpass LM while keeping the model size unchanged.
We will review MDI adaptation in section 2. In section 3, we describe our efficient algorithm and describe some implementation concerns. In section 4, we show experiments to demonstrate the scalability of the algorithm and compare the perplexities and word error rates with linear interpolation, the baseline. We will conclude with future work in section 5.

n-gram Language Model
A language model (LM) is a probability distribution over word sequences W = w1w2 . . . wL, usually reduced to a word-byword probability via the chain rule p(W ) = L i=1 p(wi|w i 1 ), where w j i ≡ wi, wi+1, . . . , wj. An n-gram LM assumes that this distribution depends only on the previous n − 1 words, i.e., is the history hi of word wi. We omit the index i when the context is clear.
Given the vocabulary V , n-gram LM defines a set of conditional probabilities p(w|h) for any hw ∈ V n . However, the space V n is very large that not every n-gram hw is seen in the training data, known as the data sparsity problem. Thus, smoothing techniques have been used to estimate the probability p(w|h) for the unseen n-grams. The most popular techniques is backing-off. The idea is to recursively estimate p(w|h) of unseen n-grams based on the lower order (n−1)-gram probabilities p(w|h ), where h = w i−1 i−n+2 , which may have been seen in the corpus. More specifically, where the discounted probability p * (w|h) and the back-off weight bow(h) are together to ensure the conditional probability sums to one: w∈V p(w|h) = 1. We will consider n-gram LMs having back-off structure in the rest of the paper. In practice, such LMs are stored in ARPA format [24]. Note that LMs smoothed by interpolation [24] can also be stored as ARPA. We measure the size of an n-gram LM as the total number of entries of order 1, . . . , n when the LM is represented as ARPA.

MDI Adaptation
The idea of LM adaptation under the minimum discrimination information (MDI) principle is to compute the adapted distribution such that it satisfies the constraints characterizing in-domain distribution, and also stays closest to the out-of-domain distribution.
The constraints are usually expressed as marginal distributions. Formally, given (i) the vocabulary V , (ii) the out-domain LM pout(w|h), (iii) the empirical history distributionp(h) which is commonly approximated by either the in-domain probabilities pin(h) or out-of-domain pout(h), and (iv) K marginal distributionsp(Si) where Si ⊂ V n , i = 1, . . . , K derived from the indomain data, the adapted LM p ad (w|h) is defined by minimizing the following conditional Kullback-Liebler (KL) divergence: while satisfying the constraints: where fi are indicator functions of (h, w) ∈ Si. Note that Eq. 3 can also be viewed as the KL divergence between the joint distribution p(h, w) and pout(h, w) assuming they have the same history distributionp(h). Also notice in the case that pout is the uniform distribution, p ad is indeed a maximum entropy model. If the constraints in Equation 4 are consistent, the solution of the above optimization problem exists and is unique [25]. It has the following form, with parameters {λi}.
where the scaling factor α(h, w) = exp ( K i=1 λifi(h, w)), and Z(h, λ1, . . . , λK ) is the normalization term summing up the numerators. This solution can be obtained by generalized iterative scaling (GIS) algorithm [25], sketched in Algorithm 1, or some of its modern fast counterparts [23]. The iterations can be terminated when the results converge or nearly converge.

Efficient Algorithm: The Hierarchical
Training Method The challenge for implementing the above GIS algorithm is its computational complexity resulting from Line 4 (normalization) and 8 (marginalization). A naive implementation may take O(K * # of seen histories * |V |) time per iteration [5]. An improvement can be made to O(# of seen histories * |V |+K) if we store the constraints in Line 7 in a hash table and accumulate the summation in Line 8, but this complexity is still astronomical when the corpus and vocabulary V is large. Thus, we need to re-organize the summation happening in Line 4 and 8.
3.1. The Hierarchical Training Method: MDI v.s. ME To overcome this challenge, the hierarchical training method [1] has been proposed for ME models. The algorithm only requires linear time to its inputs per iteration, i.e., the number of seen entries in pout plus K. The trick is based on the back-off structure of probability p (n) (w|h). In this paper, we show that similar algorithmic trick can be applied to MDI with additional cares. This

Algorithm 1 Generalized Iterative Scaling (GIS) Algorithm
Require: V , pout(w|h),p(h) andp(Si) 1: Set λ for each seen history h in training data do 5: Compute normalization term: Update each entry of back-off LM: 8: for j = 1, · · · , K do 9: Marginalize: 10: end for 12: n := n + 1 13: end while 14: return p (n) (w|h) as p ad means MDI adaptation incurs no extra computation complexity although it is more general than ME. The key is to handle the non-uniform pout appropriately.
To illustrate the idea, we take trigram LM as an example. Consider a general LM p(w3|w 2 1 ) that has the back-off structure as in Equation 1. We also define a set of real-valued scaling factors c(w 3 1 ), w 3 1 ∈ V 3 to be some default constant value except for K of them having non-default values. Now, we hope to compute the left-aligned and right-aligned summation of the product of p(w3|w 2 1 ) and the general scaling factor c(w 3 1 ): The right-hand-sides only differ in the subscript of summation.
In fact, ΣL corresponds to computing the normalization term (Line 4), and ΣR is related to marginalization (Line 8). Notice that in ME, p(w3|w 2 1 ) is just a uniform distribution. 3.2. Computing ΣL(w 2 1 ) as normalization for history w 2 1 In Equation 6, we compute ΣL(w 2 1 ) by summing over w3 ∈ V given history w 2 1 , which costs |V | addition operations. However, this cost can be reduced to the number of seen n-grams given w 2 1 by dynamic programming, much less than |V |.
As of complexity, computing ΣL(∅) requires O(|V |) time. ΣL(w 2 1 ) and ΣL(w2) can be computed from the ΣL of the lowerorder n-grams with the complexity of the number of seen ngrams along the way, plus the number of distinct scaling factors K (at most), as each non-default c(·) term is accessed only once. Thus, overall, the total time is proportional to the number of seen entries in pout(w3|w 2 1 ) plus K. Recall in the ME case, p(·) and bow(·) can be seen as 1, and the above equation can be simplified to contain only the scaling factor c(·)'s [1].

Computing ΣR
Consider Eq. 8, where we compute the right-aligned ΣR(w 3 2 ) by summing over w1 ∈ V . Similarly, we define the lower or higher order right-aligned summation ΣR(w3) as follows: Obviously, ΣR(w3) requires more computation than ΣR(w 3 2 ) and ΣR(w 3 1 ). Unfortunately, dynamic programming does not work here anymore to compute ΣR(w3) from ΣR(w 3 2 ). Instead, we will make use of the idea of shared computation, which means we go over the data for only one pass, but we accumulate the values correspondingly to all related constraints.
First, let us compute ΣR(w 3 2 ) as follows: For simplicity, we denote the auxiliary function g(w2) = w 1 ∈V bow(w 2 1 ) in the second term above, and we will address the computation of g(·) later. Notice that the decomposition of ΣR looks quite different from section 3.2, as ΣR(w 3 2 ) is not decomposed to the sub-problem ΣR(w3) or vice versa. Besides, if we let p(·) and bow(·) be 1, it becomes the case for ME model. At the same time, let us see how to compute ΣR(w3): We denote g(∅) = w 2 ∈V bow(w2) · g(w2). Assuming that the values of g(·) are known, now we can come up with an algorithm to compute ΣR by observing the equations of ΣR(w3), ΣR(w 3 2 ) and ΣR(w 3 1 ) together. The algorithm enumerates the seen ngrams in LM p(w3|w 2 1 ) and all non-default scaling factor c(·)'s, and adds the value as specified in the equations to the ΣR with arguments matching the suffix of the n-gram. The complexity is O(n * # of entries in p(w|h)), with n being a small constant. Now, the remaining problem is how to compute the auxiliary function g(·) as defined previously. It turns out that this is a right-aligned summation in the ME case. More specifically, their scaling factors are c(w 2 1 ) = bow(w 2 1 ) or c(w 2 1 ) = bow(w 2 1 ) * bow(w2). Thus, computing g(·) can be shown to be also in linear time. In fact, computing the auxiliary function g (·) is what makes the algorithm for MDI different from that of ME.

The back-off structure of p ad (w|h)
Before computing the marginals in Line 8 of Algorithm 1, we still need to show that the probability p (n) (w|h) or p ad (w|h) in Equation 5 has the back-off structure. This is important not only for the computational purpose -that the tricks for ΣL and ΣR can be applied here -but also for being able to represent the final adapted LM in ARPA format.
We claim that, if pout is a back-off model as in Equation 1, then so is the exponential models p (n) and p ad . We prove this by giving the back-off expression of p ad : The lower order n-grams of p ad are defined analogously. There will be at most (# entries in pout + # entries in pin) entries in p ad , same as in linear interpolation.

Computing marginalization as ΣR
Finally, we come to compute the marginals in Line 8 of Algo. 1: Since it has been proved that p (n) is a back-off LM, we can view w p (n) (w|h)fi(h, w) as a right-aligned sum. However, we need to further consider the multiplication termp(h). Fortunately, the same trick computing ΣR can be applied here, with some modification of the auxiliary function g. For example, let g(w2) = w 1 ∈Vp (w 2 1 )bow(w 2 1 ), and then it can be treated in two ways efficiently, either (i) ifp(w 2 1 ) is an unsmoothed maximum likelihood estimation, there will be a lot of zeros forp(w 2 1 ), or (ii) ifp(w 2 1 ) =p(w2|w1) * p(w1) has a smoothed distribution, andp(w2|w1) has the back-off structure, then this amounts to compute some right-aligned sum. It can be shown that the computational complexity of marginalization is linear in both ways. We omit the details here due to space limit. Interested readers can refer to Appendix A at the end of the paper. In all, we have shown how Algorithm 1 can be implemented efficiently.

Implementation Issues
Special care should be taken when dealing with n-grams w 3 1 which containing <s> or <\s>, or whose suffix w 3 2 is not seen. To further speed up the computation, the algorithm can be implemented in a vectorized manner with group-by operation for summing up probabilities of n-grams of the same suffix.

Experimental Results
We will show the scalability of our algorithm and the effectiveness of MDI adaptation with two different ways of application. 118.0 3.9 120.0 3.9 Table 1: Comparing the perplexity (PPL) and word error rate (WER, in %) of LMs with no adaptation, interpolation and MDI adaptation. We simulate the LM adaptation scenario by taking three speech corpora, Wall Street Journal (WSJ), Switchboard (SWBD) and AMI-IHM (AMI) as in-domain data, and Google One Billion Words [26] and Librispeech [27] as out-of-domain data. We normalize the Google dataset with the similar scripts generating normalized Librispeech LM training texts, resulting 702 million and 803 million words respectively. We compute trigram LMs using the SRILM tool [28] with Kneser-Ney smoothing and default settings, or use default Kaldi's LMs. We find the normalized Google dataset always out-perform Librispeech as the out-of-domain corpus, so we only report the results for Google dataset. We are interested whether the rich LM information in the very large corpus can help the LM and ASR task in the application domains. We use count thresholds to select the in-domain constraints, i.e., the marginals are considered reliable when the counts of the n-grams is above the threshold.

Scalability
We implemented the proposed efficient version of Algorithm 1 in Python with Numpy and Pandas. In Figure 1, we compare the run-time per iteration in seconds with various size of out-ofdomain LM (blue) and various number of constraints (blue). The in-and out-of-domain data are taken to be SWBD and Google. We sample the out-of-domain data at different sizes measured by the total number of seen entries in the ARPA file, and record the run-time per iteration. We control the number of constraints by using different constraint count thresholds. We can see that both lines shows linear scalability, and the run-time is denominated by the size of out-of-domain data. Besides, it usually takes 60 ∼ 80 iterations for the algorithm to converge to a near optimal solution, which may be improved by more advanced optimization algorithms.

Effectiveness of Adaptation
We compare the LMs with and without adaptation, and with different adaptation methods, i.e., simple linear interpolation and MDI. We evaluate the LMs in perplexity (PPL) and word error rate (WER) when used in an hybrid ASR system. We use the latest recipes in the open-source speech recognition toolkit Kaldi [29] to run the ASR experiments. The acoustic model uses factorized TDNN architecture [30] and is trained with LF-MMI criteria [31]. The features are 40-dimensional MFCC features with 100-dimensional i-vectors appended to the MFCC. The training data is augmented with speed and volume perturbation.

Performance in the Rescoring
As in a common adaptation scenario, we adapt the large, out-ofdomain LM to satisfy the marginal distribution constraints derived from the in-domain data. As the Google corpus is large, the resulting LM can have 61 ∼ 76 million entries depending on the vocabulary (which is AMI 50k, SWBD 30k, WSJ 20k). So the LMs are used for rescoring. From the right half of Table 1, we can see that LM adaptation is effective for both interpolation and MDI. The interpolated LMs have better perplexity most of the time, which is consistent with previous work [14,20], but we also find that MDI adapted LMs have better WER. Also note the constraints we use for MDI, where 5-3-2 means count thresholds of 5, 3, 2 are used for selecting unigrams, bigrams and trigrams as constraints. Thus, in fact, MDI sees less information of the indomain data than interpolation, e.g., the MDI(6-4-3) above sees the least in-domain data. However, MDI requires additional information about the history distributionp(h), for which we take the maximum-likelihood in-domain pin(h) as an approximation.

Performance in the First-Pass Decoding
We propose a novel approach of applying MDI adaptation: instead of adapting the out-of-domain LM, we adapt the small, indomain LM, which is used in the first pass decoding of ASR, so that it preserves the marginals of the larger and better interpolated LM. The constraints are selected to be all seen entries in the in-domain LM, such that the model size remains unchanged after adaptation. The results are a bit surprising. As we can see in the left half of Table 1, the perplexity of the first-pass LM gets improved significantly and lies between the default and interpolated LMs. The first-pass WER also gets improved, not so much though. It seems this is the advantage of MDI over interpolation: we have better control of the resulting model size. We are going to investigate into this interesting observation as the future work.

Conclusion and Future Work
In this paper, we propose an efficient MDI adaptation algorithm for n-gram LMs. The algorithm relies on the back-off structure of the LMs, and takes linear time per iteration. We show empirically our algorithm is truly scalable to very large corpus. We also find that MDI adaptation gets close perplexity to linear interpolation, but better WER. The methods for computing marginals and normalization terms are general and may benefit some more advanced optimization algorithms. Regarding MDI models, it may be important to study whether the better feature selection and history distribution estimation methods can affect the performance. Lastly, as we have observed in the experiments, we will study using MDI adaptation to improve small LMs for the first-pass decoding of ASR.