Ney Implementation of Word Based Statistical Language Models

Abstract. In this paper we present an efficient data structure for storing trigram, bigram and unigram counts. The amount of memory required has been reduced by 53 % compared to straightforward approaches. The average access time for retrieving information

IMPLEMENTATION OF WORD BASED STATISTICAL LANGUAGE MODELSFrank Wessel, Stefan Ortmanns and Hermann NeyLehrstuhl fur Informatik VI, RWTH Aachen, University of Technology, D-52056 Aachen, Germany, Phone/Fax:+49 241 f8021616/8888219g, E-mail: wessel@informatik.rwth-aachen.de trigram, bigram and unigram counts. The amount of memory required has been reduced by 53% compared to straightforward approaches. The average access time for retrieving information from the data structure has also slightly been reduced. Based upon this special data structure we have implemented several types of language models and applied them to the North American Business (NAB '94) recognition task. We show that both, the perplexity and the error rate could be reduced compared to the o cial NAB '94 trigram language model.

Abstract. In this paper we present an e cient data structure for storing

1 INTRODUCTIONThe main task of statistical language modelling is to provide a speech recognition system with the a-priori probabilities for a word sequence w1:::wN . In order to be able to compute the widely used bigram and trigram language models, we have to count how often a trigram or bigram, i.e. a word triple or a word pair, has been seen in a training corpus. We can then compute the probability estimate for the trigram u; v; w as: N (u; v; w) p(wju; v )=; N (u; v ) with N (u; v; w) denoting the number of times the trigram u; v; w has occured in the training corpus. To overcome the well-known zero frequency problem, some sort of discounting must be applied to the relative freqencies. The words are usually replaced by word indices which correspond to their position in a lexically sorted vocabulary. Using this text representation, there are several approaches to compute the relative frequency of a trigram:{ The whole training corpus can then easily be stored in a one-dimensional array. Whenever the probability of a speci c trigram is needed, its frequency can simply be calculated by counting the occurrences of the event in the corpus. Assigning two bytes for each word we need 480 MByte to store the whole NAB '94 Corpus consisting of about 240 million words. It is useful to introduce another array, in which the next occurence of a word in the training corpus is stored. The memory cost then rises up to 1.4 GByte. 55

Abstract. In this paper we present an efficient data structure for storing trigram, bigram and unigram counts. The amount of memory required has been reduced by 53 % compared to straightforward approaches. The average access time for retrieving information

corpus size bigrams: ( 1 ( trigrams: ( 1 (

Table 1. Statistics for the NAB'94 Corpus.N u; v< N u; v>

N u; v

N u; v; w

< N u; v; w>

N u; v; w

)=1 ( ) 256 ) 255 )=1 ( ) 256 ) 255<<

240 million words 51 888 422 4 848 006 100 779 41 885 919 17 956 245 71 907

{ The second approach computes the smoothed relative frequencies of all tri-

grams beforehand and stores these probability estimates, herewith avoiding the time consuming computations during the speech recognition process. The trigram probabilities can be easily retrieved using the word indices of the words in the trigram. As the main disadvantage, experiments which require modi cations of the count

s N (u; v; w) (e.g. computing Leaving-One-Outprobabilities on the training corpus) can no longer be performed. Another disadvantage is the still large amount of memory needed, when no cut-o s are applied to the counts. of the trigrams instead of their probabilities. Nevertheless, the memory requirement is very high as presented below. We will show that by using the special structure of the counts the memory cost and the average access time can be reduced.

{ The third approach which we have decided to follow is to store the counts

2 STORING THE COUNTSA rather straigthforward solution to the storing problem is the following: Unigrams, bigrams and trigrams are stored in one array each. Starting with the rst word u in the trigram u; v; w, we look for the second word v in the list of successors which make up a certain part in the bigram list. Applying the same scheme to the trigram list, we can easily nd the word w and the corresponding count N (u; v; w) using binary search. With this approach the memory cost sums up to 420 MByte. Assuming, that the trigram frequencies are almost identical for training and testing, we can easily compute the average number of accesses to the data structure which is needed to nd a speci c trigram: X X N (u; v) ld (SUC(u)+ 1)? 1+ ld (SUC(u; v)+ 1)? 1]; (1) with SUC(u; v) denoting the number of di erent words w succeeding the wordpair u; v in the training and N being the training corpus length. With this approximation we obtain the following results: Finding a trigram takes 17.8 search accesses on average and 29 accesses in the worst case. 56u vN

Abstract. In this paper we present an efficient data structure for storing trigram, bigram and unigram counts. The amount of memory required has been reduced by 53 % compared to straightforward approaches. The average access time for retrieving information

UnigramsBigrams

N(u,v) = 1Trigrams

N(u,v,w) = 11

u

20000N(u,vN(u,v,w)w

Abstract. In this paper we present an efficient data structure for storing trigram, bigram and unigram counts. The amount of memory required has been reduced by 53 % compared to straightforward approaches. The average access time for retrieving information

special case there only exists one successor w following v and the position of the word w in the trigram singleton list e …… 此处隐藏：8984字，全部文档内容请下载后查看。喜欢就下载吧 ……