Improved Language Models for Word Prediction and Completion with Application to Hebrew

ABSTRACT

Language models (LMs) are important components of many applications that work with natural language, such as word prediction and completion programs, automatic speech recognition, and machine translation. In this paper, we introduce various types of improvements for LMs dealing with word prediction and completion in Hebrew. Whereas previous systems for the Hebrew language apply known variants of existing LMs without any alteration, this study presents two types of improvements concerning the LMs: one is general and the other is special for the Hebrew language. These improvements enable all tested LMs to improve their keystroke saving abilities.

Introduction

Word Prediction is the process in which words that are likely to follow in a given text are suggested by displaying a list of most relevant words. Word Prediction enables a user to select a word from a given list to reduce the number of keystrokes necessary for typing, saving physical effort, time, and spelling errors. The process of Word Prediction is as follows: As the writer types a word(s), the software produces one word or a list of word choices. Each time a word is added, the list is updated. When the target word appears in the list, it can be selected and inserted into the ongoing text with a single keystroke. Typically, word lists are numbered, and words can be selected by typing the corresponding number. If the word the user seeks is not predicted, the writer must enter the word.

Word Completion is the process in which words that include the entered letter sequence are suggested by displaying a list of the most relevant words. The process of Word Completion is as follows: As the writer types the first letter or letters of a word, the software produces one word or a list of words beginning with the entered letter sequence. Each time a letter is added, the list is updated. When the target word appears in the list, it can be selected and inserted into the ongoing text with a single keystroke. Typically, word lists are numbered and words can be selected by typing the corresponding number. If the word that the user seeks is not predicted, the writer must enter the next letter of the word.

Word prediction and completion features are provided by various software, e.g., database query tools, e-mail programs, search engine interfaces, text editors, web browsers, word processors, and fast texting in small form factor devices. These features speed up human-computer interactions, saving physical effort, time, and spelling errors.

The original purpose of word prediction and completion was to assist people with physical disabilities to increase their typing speed (Tam and Wells 2009) and to decrease the number of keystrokes required to either write or complete a word (Anson et al. 2006). The main aims of word prediction are to increase typing speed and to reduce writing errors (particularly for dyslexic people). However, word prediction and completion have also been shown to be helpful for anyone who types text, especially those who use text editors, mobile phones, search engines, and short message services. In addition, Word Prediction software often allows users to enter their own words into the word prediction dictionaries either manually or by “learning” inputted words (Beukelman and Mirenda 2008; Darragh, Witten, and James 1990).

Augmentative and alternative communication (AAC) is used by individuals to compensate for their impairments in the expression or comprehension of written or spoken language (Calculator et al. 2004; Fossett and Mirenda 2009). AAC is utilized by individuals with a variety of congenital conditions, such as autism, cerebral palsy, and intellectual disabilities and acquired conditions, such as amyotrophic lateral sclerosis, aphasia, and traumatic brain injury (Beukelman and Mirenda 2005).

AAC’s users are able to input (letter by letter) over 10–15 words per minute (WPM), despite many users suffering from motor impairment resulting in a typing speed of one WPM or less (Trnka et al. 2009).

Word prediction and completion programs commonly utilize language models that attempt to capture the properties of a language. These LMs provide the user with one or more suggestions for completing the current or, occasionally, the following word (Darragh and Witten 1991; Trnka et al. 2009; Wandmacher and Antoine 2007).

The main evaluation measure for word prediction is keystroke savings (KSs) (Carlberger et al. 1997; Newell, Langer, and Hickey 1998; Li and Hirst 2005; Trnka and McCoy 2008), which measure the saving percentage in keys pressed compared to letter-by-letter text entry. KS is computed using the following formula: (chars—keystrokes) /chars × 100, where chars represents the number of characters in the text, including spaces and newlines, and keystrokes is the minimum number of key presses required to enter the text using word prediction, including the keystroke to select a prediction from the list and a key press at the end of each utterance.

Whereas previous systems for the Hebrew language present applications of known variants of existing LMs without any alteration, this study presents two improvements concerning the LMs: one is general and the other is special for the Hebrew language. These improvements contribute to improve the KS rate.

This article is organized as follows: The section ‘Previous Word Completion and Prediction Systems’ presents a number of previous prediction systems as well as several previous prediction systems for Hebrew. The section ‘Language Models and Their Combinations’ describes LMs in general and LM combinations. The section ‘Improved LMs for Hebrew Word Completion and Prediction’ presents the proposed Improved LMs for word prediction and completion in Hebrew. The section ‘Experimental Setup and Results’ describes the examined corpora and the experimental results and analyzes them. The final section summarizes, concludes, and proposes future directions.

Previous word completion and prediction systems

PAL (Swiffin et al. 1985), one of the first word prediction systems, suggests most frequent words that match a partially typed word, ignoring the context of the typed word. WordQ (for English) (Shein et al. 2001) and Profet (for Swedish) (Carlberger 1997; Carlberger et al. 1997) use not only word unigrams but also bigrams for word prediction.

Concentrating solely on n-grams’ distribution statistics for prediction occasionally results in the suggestion of syntactically inappropriate words, whereas utilizing syntactic knowledge, such as POS tags of a language, can filter such suggestions. Systems such as Syntax PAL (Morris et al. 1992) (for English) and Prophet (Carlberger 1997) (for Swedish) base their predictions on syntactic knowledge of a language. Syntax PAL and Prophet are improvements of their previous systems PAL and Profet, respectively. Syntax PAL has decreased the errors caused by PAL and has made it possible for users to write longer and more complicated sentences. Prophet required 33% fewer keystrokes than Profet, its predecessor. A survey on text prediction systems was conducted by Garay-Vitoria and Abascal (2006).

Previous Hebrew word prediction systems

Netzer, Adler, and Elhadad (2008) were the first to present the results of a Hebrew word prediction system. Their system applied three methods: (1) Statistical knowledge—Markov LMs for unigrams, bigrams, and trigrams, (2) Syntactic knowledge—POS tags and phrase structures, and (3) Semantic knowledge—Associating words into categories and finding a group of rules that constrain the prospective following word.

They tested their system on three corpuses of 1, 10, and 27 M words. The best results were obtained after training a hidden Markov LM on the largest corpus. In contrast to expectation, the use of morpho-syntactic information, such as POS tags, lowered the prediction results. The best results were achieved using statistical data, resulting in KS of 29% with nine word proposals, 34% for seven proposals, and 54% for a single proposal.

HaCohen-Kerner and Greenfield (2012) presented another Hebrew word prediction system. Their system was composed of the following components: (1) Sorted lists of words, frequent nouns, and frequent verbs, (2) Six corpuses containing approximately 177 M words, (3) Three LMs (trigram, bigram, and unigram) that were automatically generated using the Microsoft Research Scalable Language-Model-Building Tool¹ and the aforementioned corpora, (4) Results of queries sent to the Google Search Engine,² (5) A morphological analyzer³ generated by MILA,⁴ and (6) A cache containing the 20 most recently typed words.

The KSs rates (between 54% and 72%) reported in HaCohen-Kerner and Greenfield (2012) were higher than those reported in Netzer, Adler, and Elhadad (2008). However, these two systems were trained and tested on different corpora. In any event, it seems that a larger corpus enables improvement in the prediction results. Both studies discovered that when an LM is based on text documents from different domains, better results are achieved without a morphological analyzer.

Whereas Netzer, Adler, and Elhadad (2008) and HaCohen-Kerner and Greenfield (2012) did not define and apply any combinations of LMs (but rather simple n-gram LMs), HaCohen-Kerner, Applebaum, and Bitterman (2014) defined and applied 16 specific variants belonging to five general types of LMs: (1) Basic LMs (unigrams, bigrams, trigrams, and quadgrams), (2) Backoff LMs, (3) LMs Integrated with tagged LMs, (4) Interpolated LMs, and (5) Interpolated LMs Integrated with tagged LMs. These 16 variants were compared in terms of KS for Hebrew word prediction and completion using three types of Israeli web newspaper corpora. The tested corpora contained only 2.1 M tokens to save runtime for the 16 variants of LMs.

The foremost KS results (18–42% for word prediction and 44–63% for word completion after having the first seven or more letters of the tested words) were achieved with the LMs of the most complex variety, the interpolated LMs integrated with tagged LMs. The improvements of the KS rates for completion of a word after having at least five letters were less than 1% for all corpora. That is to say, the contribution of the various LMs and the combinations of LMs are primarily expressed for either prediction or completion of words for less than five letters.

However, these three studies only presented applications of known variants of existing LMs without any alteration. In this research, we present two improvements concerning the LMs: one is general and the other is specific to the Hebrew language.

Language models and their combinations

The most commonly applied LMs are statistical n-gram LMs. An n-gram is a contiguous sequence of n items (e.g., characters, words, phonemes, or syllables) from a given sequence of text or speech. These LMs try to capture the syntactic and semantic properties of a language by estimating the probability of an item in a sentence given the preceding n−1 items. An n-gram (N = 1, 2, 3, 4, …) word LM for a specific corpus gives a probability to each sequence of N consecutive words in the corpus according to its distribution in the discussed corpus. LMs with N = 1, 2, 3, and 4 are referred to as unigrams, bigrams, trigrams, and quadgrams (also known as fourgrams), respectively.

The simplest version of an n-gram LM is a list of specific n-grams that occur in a given corpus (corpora) and their frequency of occurrence. Unigram LMs only calculate the probabilities of single words without considering their context, i.e., the words before or after the target word. In the majority of IR’s tasks, unigram LMs (as opposed to complex LMs) are most commonly used because they are sufficient to determine the topic from a piece of text (Wang et al. 2011). However, for word prediction and completion tasks, unigram LMs are entirely insufficient. N-gram LMs (N > 1) are necessary to capture the context of the word at hand and to enable a better word prediction or completion.

Wandmacher and Antoine (2006) and Trnka and McCoy (2007) showed that n-gram LMs for word prediction are domain-sensitive. Namely, an n-gram LM trained and tested on a corpus with a different topic and/or style may not perform well when compared to an LM trained and tested on a relevant corpus.

Mikolov (2012) in his doctoral dissertation presented various limitations of n-gram LMs: (1) N-gram LMs assume exact match of the tested n-gram, which is not always true. (2) Regular n-gram LMs do not represent patterns that contain more than three or four words. (3) With increasing order of the n-gram LM, the number of possible parameters increases exponentially. (4) There will be never enough training data to estimate parameters of high-order n-gram LMs.

Part-of-speech taggers enable the generation of more general LMs (Brants 2000). Such LMs include sequences of n consecutive tags and their frequencies of occurrence. Ghayoomi and Daroodi (2008) showed that the integration of POS tags in LMs for the Persian language improves the KS rate. Aliprandi et al. (2007) improved a previous POS trigram model for the Italian-inflected language by two types of unification of two trigrams into a single one. These improvements led to an additional 8% KS and a lower number of POS trigrams.

Various additional combinations of LMs have been performed by several systems. For instance, Kimelfeld et al. (2007) used combinations of LMs and HITS algorithms for XML retrieval. They show that combined LMs generally yield better results in identifying large collections of relevant elements. Kirchhoff et al. (2006) applied various combinations of LMs for large-vocabulary conversational Arabic speech recognition, including an LM that uses a backoff procedure in which both words and/or additional morphological features can be used in tandem. They report that combinations of more than one LM usually have a more significant effect; the greatest reduction (0.5% absolute) is obtained by combining stream models with a class-based model involving all three morphological components (roots, stems, and morph classes). McMahon (1994) in the 2nd chapter of his PhD dissertation supplied an overview of word-based LMs in general and combinations of LMs in particular. McMahon describes a few combination variations using several LMs, such as weighted combinations, to produce an interpolated LM and a backoff use of LMs that either uses one LM or utilizes an additional LM, contingent on a strict set of conditions. Wu et al. (2010) applied combinations of LMs for sentence correction and compared them. Stymne (2011)applied combinations of LMs for spell-checking techniques to allow the replacement of unknown words and data cleaning for translation of Haitian Creole SMS. Beyerlein (1998) found that integrating bigram, trigram, and quadgram LMs (with two additional acoustic models) into one LM leads to lower error rates than searching for the “best” combination of a specific LM and a particular acoustic model. Shaik et al. (2012) proposed hierarchical hybrid LMs for open vocabulary continuous speech recognition hybrid vocabularies. They integrated word LMs and character LMs. ‏

Improved LMs for Hebrew word completion and prediction

Basic LMs

In this subsection, we briefly describe the 16 specific variants belonging to five types of LMs implemented in HaCohen-Kerner, Applebaum, and Bitterman (2014). The tagged LMs used the tagger built by Adler (2007, 2008). This tagger achieved 93% accuracy for word segmentation and POS tagging when tested on a corpus of 90 K tokens.

1) The Basic LM type includes four variants of the four most elementary word-based LMs: unigrams, bigrams, trigrams, and quadgrams and solely utilizes a single LM.

2) The Backoff LM type includes three variants: the backoff quadgram LM, the backoff trigram LM, and the backoff quadgram LM. The implemented backoff LM is based on the exclusive use of the highest n-gram basic LM. If this fails to yield results, we then attempt to use the (n−1)-gram LM.

3) The Backoff integrated LM and Tagged LM types include two variants. The first variant (called the conservative) uses the backoff quadgram LM. Only in the case that there are at least two proposals with the same highest result proposed by the n-gram LM do we attempt to choose between them based on the compatible tagged n-gram LM. If no selection is made, we attempt the (n−1)-gram LM and so on. The second variant is Backoff Integrated Tagged LMs with Basic LMs. This variant first activates the tagged quadgram LM. According to the likely POS-tag, it retrieves in context the word that is most likely to fit this POS-tag using the compatible n-gram LM.

4) The Interpolated LM type includes four variants that synthesize all four basic types of n-gram LMs (unigram, bigram, trigram, and quadgram). The implemented variants are: (1) Fixed Equal Weights (0.25) for each n-gram LM; (2) Fixed Unequal Weights that distributes the weights as follows: 0.4, 0.3, 0.2, and 0.1 for the quadgram, trigram, bigram, and unigram LMs, respectively; (3) A different weight is given to each n-gram LM according to its relative rate of successful predictions and completions of words. We call this model interpolated LM with relative weights; and (4) Similar to the previous variant with a special statistical treatment of the first word in each sentence, this treatment is based on the distribution of the first word in all sentences.

5) The synthesized LM type (interpolated and integrated LM and tagged LM) includes three variants as follows: (1) Fixed unequal weights of 0.4, 0.3, 0.2, and 0.1 for the quadgram, trigram, bigram, and unigram LMs, respectively; (2) Weights are given to each n-gram LM according to its relative rate of successful word predictions and completions; and (3) Weights are given to each n-gram LM according to its relative rate of successful word predictions and completions with a special statistical treatment for the first word in each sentence based on the distribution of the first word in all sentences. Table 1 presents the names of the models and their abbreviations, which are used in the rest of the paper.

Table 1. The names of the models and their abbreviations.

#	Name of model	Abb.	#	Name of model	Abb.
1	Unigram	U	9	Backoff integrated tagged LMs with basic LMs	BIT
2	Bigram	B	10	Interpolated LM with fixed equal weights	IFE
3	Trigram	T	11	Interpolated LM with fixed unequal weights	IFU
4	Quadgram	Q	12	Interpolated LM with dynamic weights	ID
5	Backoff bigram	BB	13	Interpolated LM with super dynamic weights	ISD
6	Backoff trigram	BT	14	Synthesized LM with fixed unequal weights	SF
7	Backoff quadgram	BQ	15	Synthesized LM with dynamic weights	SD
8	Backoff integrated LM and taggedLM—conservative	BIC	16	Synthesized LM with super dynamic weights	SSD

Improved LMs

In contrast to the three previous systems for the Hebrew language (mentioned in Section 2) that presented applications of known variants of existing LMs without any alteration, this study presents two types of improvements for the LMs: one is general and the other is specific to the Hebrew language. These improvements contribute to improving the KS rate. The LMs presented in this study extend and improve different aspects of the LMs presented in HaCohen-Kerner, Applebaum, and Bitterman (2014), which are briefly presented in Section 4.1.

In the rest of this section, we present two methods related to the test of the LMs on the experimented corpora and two types of improvements concerning the LMs. Some of them were tested on all LMs, and some were tested on the most advanced variant of LM. One improvement is general and technical, and the other is specific to the Hebrew language. These improvements contribute to improving the KS.

The two methods related to the test of the LMs on the experimented corpora are as follows:

1. Each corpus was split into a training set (90%) and a test set (10%) as opposed to HaCohen-Kerner, Applebaum, and Bitterman (2014), where they trained and tested on the same corpus in each experiment. This is probably the reason why the results achieved in the current research are lower than those reported in HaCohen-Kerner, Applebaum, and Bitterman (2014). It is not correct to test on the same database from which learning was conducted. The real ability of a model should be tested on a corpus different than the one from which it learned.

2. In addition to the calculation of the KS measure that was performed in the three previous systems for Hebrew, we also calculated the perplexity measure in a limited way. A practical informal definition of perplexity is the number of different tokens that an n-gram LM refers as potential candidate tokens following a given sequence that contains N−1 tokens. The perplexity measure was computed for the quadgram backoff model, and the values are presented in the Table 2.

Table 2. The perplexity’s values for the quadgram backoff model.

A7	Haaretz	Themarker
920.04	3514.15	2477.60

The very high values of the perplexity measure for the quadgram backoff model on the three corpora (between 920 and 3514 per word) show that this measure is less relevant than the KS to our research. These values are much higher compared to the lowest perplexity value (approximately 247 per word) that has been published on the Brown Corpus (Brown et al. 1992) using a trigram model.

In addition, the perplexity measure in word n-grams LMs usually relates to word prediction, whereas in our research, we also address word completion. Moreover, the time needed for the computation of the perplexity measure for all LMs was extremely high compared to the time needed for the computation of the KS measures for the same LMs. Therefore, we decided to work only with the KS measure.

The two improvements concerning the LMs are as follows: (1) A general technical improvement, which is not specific to Hebrew. This is the non-repetition improvement: the LM model does not suggest the same word one by one; and (2) A specific improvement related to the Hebrew language—the prefix improvement: if the model offers a word in Hebrew that is a prefix of another word in Hebrew whose length contains at least two letters more than the length of the word at hand, the user (or the program itself) will choose it (an offer of a word with a length of only one additional letter will not be chosen because its selection needs one keystroke). For example, let us assume that the word that the user wants to write is “followed.” He types “foll” and the LM offers the word “follow.” It makes sense that he would choose this word because this word is a prefix of the desired word “followed.”

Experimental setup and results

Examined corpora

In this study, we tested our LMs on three corpora, two of which were tested in HaCohen-Kerner, Applebaum, and Bitterman (2014). The examined corpora are three Israeli newspaper corpora (Arutz Sheva (A7),⁵ Haaretz,⁶ and Themarker (TM)⁷). The three newspaper corpora contain 2,477,947 tokens, slightly more than the 2,130,477 tokens included in the three newspaper corpora used in HaCohen-Kerner, Applebaum, and Bitterman (2014). The only difference is that the Haaretz corpus replaced the NRG⁸ corpus. The NRG corpus was removed from the experiments in this study because it contained two huge files, and each of them was approximately 150 times larger than all other 2500 files from the same corpus.

In this research, we work with a simplified definition of a token in Hebrew as follows: a token is a string of contiguous characters between two spaces, or between a space and any punctuation mark. A token can also be an integer, real number, or a number with a colon (time, for example: 2:00). All other symbols are tokens themselves, except apostrophes and quotation marks in a word (with no space), which in many cases symbolize acronyms or citations. A token can present a single Hebrew word or a group of words, such as the following token “וכשתבואי” (VeKsheTavoee), which includes five words “and when you will come.”

These corpora represent three different types of Israeli web newspapers: Israel’s political left-center, economic, and national religious. The diversity of the three corpora allows for testing of the performance of all LMs on various news genres. Table 3 presents general information regarding the examined corpora.

Table 3. General information regarding the examined corpora.

Corpus	# of tokens	# of different tokens	# of files	Avg. # of tokens in a file	Std of tokens in file	Median of tokens in a file	Leng-th of avg. token	Std of token length	Median of token length
A7	880382	58587	8724	100.91	92.05	75	4.04	1.99	4.0
Haaretz	898988	81104	1677	536.07	538.84	378	3.92	2.10	4.0
Themarker	698577	58199	835	836.62	316.40	786	3.99	2.09	4.0

LM experiments on newspaper corpora

HaCohen-Kerner, Applebaum, and Bitterman (2014) tested 16 specific LMs belonging to five types of LMs. Each LM was tested on the three corpora (NRG, Themarker, and A7). In this research, we investigated 32 specific LMs belonging to the same five types of LMs. Each LM was tested on the three corpora (Haaretz, Themarker, and A7 mentioned in Section 5.1).

In this study, we simulated the process of user interaction in the following manner: we went over each word in each sentence in the test corpus. We attempted to predict the next word in its entirety. If we failed to do so, we tried to predict a single character at a time until a space or a dot (or any other punctuation mark) was reached or until the next word was correctly proposed.

The KS (see definition toward the end of Section 1) values are reported when only one suggestion (with the highest result) is proposed. The KS results of all LMs are shown for each corpus in a separate table (Tables 4–6). The rows of each table show two results for each LM’s variant: one for the basic variant, which is presented in HaCohen-Kerner, Applebaum, and Bitterman (2014), and one (with a “+” to the right of the LM’s abbreviation) that represents the variant with the prefix and non-repetition additions (see Section 4.2). The leftmost column presents the tested LM (i.e., its abbreviation, the full name can be found in Table 1). The second-to-left column shows the KS result for prediction of a word in its entirety. The third-to-left column shows the KS result for the completion of a word after having the first letter of the discussed word. The fourth-eighth-to-left columns present the KS result for the completion of a word after having at least the first 2–6 letters of the word, respectively. The ninth column shows the KS result for the completion of a word after having at least the first seven letters (7+) of the discussed word. The rightmost column shows the relative improvement in % between the “7+” result of the improved variant of the LM (with “+” near the LM’s name) and the “7+” result of the basic variant of the same L (without “+” near the LM’s name).

Table 4. The KS results of LMs for the A7 corpus.

[1] LM	Prediction	1	2	3	4	5	6	7+	Relative improvement in %
U	0.96	3.3	8.09	14.84	19.91	21.81	22.43	23.45	10.78
U+	0.96	3.3	8.43	16.05	22.33	24.78	25.3	25.97
B	8.44	13.56	17.31	19.01	19.64	19.77	19.8	21.22	3.64
B+	8.44	14.15	17.95	19.8	20.47	20.57	20.59	22
T	7.9	9.46	10.44	10.91	11.19	11.25	11.27	12.83	2.2
T+	7.9	9.72	10.65	11.17	11.48	11.55	11.56	13.11
Q	6.19	6.92	7.6	8.03	8.3	8.36	8.38	9.97	1.96
Q+	6.19	7.01	7.71	8.19	8.5	8.57	8.58	10.17
BB	8.7	14.65	20.24	25.72	29.84	31.5	32.01	32.95	7.66
BB+	8.7	15.26	21.06	27.1	32.25	34.34	34.81	35.47
BT	11.76	16.84	21.84	27.13	31.22	32.87	33.38	34.32	7.24
BT+	11.76	17.47	22.63	28.54	33.58	35.67	36.14	36.81
BQ	12.24	17.06	21.99	27.28	31.3	33.02	33.53	34.47	7.2
BQ+	12.24	17.67	22.7	28.68	33.72	35.81	36.28	36.95
BIC	12.73	17.46	22.37	27.71	31.81	33.41	33.92	34.86	7.22
BIC+	12.73	17.46	22.99	29.17	34.24	36.02	36.72	37.37
BIT	11.76	16.27	20.6	25.41	29.22	30.92	31.41	32.36	7.33
BIT+	11.76	16.27	21.43	26.25	31.17	33.42	34.62	34.73
IFE	12.23	16.94	21.97	27.24	31.19	32.77	33.26	34.21	7.59
IFE+	12.23	16.94	22.5	28.63	33.44	35.26	36.16	36.8
IFU	12.29	17.02	22.04	27.3	31.24	32.83	33.31	34.26	7.57
IFU+	12.29	17.02	22.58	28.76	33.5	35.32	36.2	36.86
ID	12.26	16.99	22.01	27.28	31.23	32.81	33.3	34.24	7.6
ID+	12.26	16.99	22.57	28.66	33.46	35.29	36.19	36.85
ISD	12.27	17.07	22.05	27.31	31.25	32.84	33.32	34.27	7.6
ISD+	12.27	17.0	22.6	28.68	33.52	35.33	36.23	36.88
SF	12.77	17.48	22.5	27.85	31.97	33.56	34.06	35	7.82
SF+	12.77	17.48	23.34	29.37	34.44	36.34	37.15	37.73
SD	12.75	17.45	22.47	27.82	31.94	33.53	34.03	34.97	7.84
SD+	12.75	17.41	23.32	29.34	34.42	36.33	37.13	37.71
SSD	12.75	17.53	22.43	27.83	31.94	33.54	34.03	34.97	7.84
SSD+	12.75	17.53	23.33	29.35	34.42	36.34	37.14	37.71

Table 5. The KS results of LMs for the Haaretz corpus.

[2] LM	Prediction	1	2	3	4	5	6	7+	Relative improvement in %
U	0.96	3.3	8.09	14.84	19.91	21.81	22.43	23.45	10.78
U+	0.96	3.3	8.43	16.05	22.33	24.78	25.3	25.97
B	8.44	13.56	17.31	19.01	19.64	19.77	19.8	21.22	3.64
B+	8.44	14.15	17.95	19.8	20.47	20.57	20.59	22
T	7.9	9.46	10.44	10.91	11.19	11.25	11.27	12.83	2.2
T+	7.9	9.72	10.65	11.17	11.48	11.55	11.56	13.11
Q	6.19	6.92	7.6	8.03	8.3	8.36	8.38	9.97	1.96
Q+	6.19	7.01	7.71	8.19	8.5	8.57	8.58	10.17
BB	8.7	14.65	20.24	25.72	29.84	31.5	32.01	32.95	7.66
BB+	8.7	15.26	21.06	27.1	32.25	34.34	34.81	35.47
BT	11.76	16.84	21.84	27.13	31.22	32.87	33.38	34.32	7.24
BT+	11.76	17.47	22.63	28.54	33.58	35.67	36.14	36.81
BQ	12.24	17.06	21.99	27.28	31.3	33.02	33.53	34.47	7.2
BQ+	12.24	17.67	22.7	28.68	33.72	35.81	36.28	36.95
BIC	12.73	17.46	22.37	27.71	31.81	33.41	33.92	34.86	7.22
BIC+	12.73	17.46	22.99	29.17	34.24	36.02	36.72	37.37
BIT	11.76	16.27	20.6	25.41	29.22	30.92	31.41	32.36	7.33
BIT+	11.76	16.27	21.43	26.25	31.17	33.42	34.62	34.73
IFE	12.23	16.94	21.97	27.24	31.19	32.77	33.26	34.21	7.59
IFE+	12.23	16.94	22.5	28.63	33.44	35.26	36.16	36.8
IFU	12.29	17.02	22.04	27.3	31.24	32.83	33.31	34.26	7.57
IFU+	12.29	17.02	22.58	28.76	33.5	35.32	36.2	36.86
ID	12.26	16.99	22.01	27.28	31.23	32.81	33.3	34.24	7.6
ID+	12.26	16.99	22.57	28.66	33.46	35.29	36.19	36.85
ISD	12.27	17.07	22.05	27.31	31.25	32.84	33.32	34.27	7.6
ISD+	12.27	17.0	22.6	28.68	33.52	35.33	36.23	36.88
SF	12.77	17.48	22.5	27.85	31.97	33.56	34.06	35	7.82
SF+	12.77	17.48	23.34	29.37	34.44	36.34	37.15	37.73
SD	12.75	17.45	22.47	27.82	31.94	33.53	34.03	34.97	7.84
SD+	12.75	17.41	23.32	29.34	34.42	36.33	37.13	37.71
SSD	12.75	17.53	22.43	27.83	31.94	33.54	34.03	34.97	7.84
SSD+	12.75	17.53	23.33	29.35	34.42	36.34	37.14	37.71

Table 6. The KS results of LMs for the Themarker corpus.

[2] LM	Prediction	1	2	3	4	5	6	7+	Relative improvement in %
U	0.96	3.03	6.73	12.63	16.75	18.27	18.74	19.98	47.8
U+	1.21	4.41	10.82	20.42	26.5	28.56	29.04	29.53
B	4.2	6.78	9.038	10.36	10.74	10.83	10.86	12.45	74.25
B+	7.77	13.72	17.84	19.75	20.34	20.41	20.43	21.69
T	1.71	2.4	2.94	3.407	3.6	3.65	3.66	5.32	64.62
T+	3.91	5.52	6.47	6.974	7.22	7.27	7.28	8.76
Q	0.66	1.01	1.42	1.859	2.05	2.09	2.11	3.78	41.65
Q+	1.7	2.39	3.05	3.532	3.78	3.82	3.83	5.35
BB	8.05	14.14	20.75	27.59	31.54	33.03	33.54	34.33	9.27
BB+	8.05	15.02	21.81	29.67	34.8	36.62	37.04	37.51
BT	8.87	14.7	21.18	27.97	31.91	33.4	33.9	34.69	9.3
BT+	8.87	15.66	22.28	30.1	35.21	37.03	37.45	37.92
BQ	8.97	14.73	21.22	28	31.94	33.43	33.93	34.72	9.3
BQ+	8.97	15.7	22.31	30.12	35.23	37.05	37.47	37.94
BIC	9.19	15.04	21.57	28.34	32.26	33.75	34.25	35.03	9.01
BIC+	9.19	15.94	22.71	30.87	35.1	37.15	37.64	38.19
BIT	8.22	13.89	19.79	25.9	29.65	31.2	31.71	32.48	3.94
BIT+	8.22	13.89	19.92	26.44	30.39	32.01	32.81	33.76
IFE	8.88	14.7	21.32	28.02	31.81	33.25	33.73	34.54	9.69
IFE+	8.88	15.7	22.45	30.53	35.15	37.04	37.31	37.89
IFU	9.01	14.83	21.39	28.09	31.89	33.32	33.8	34.62	9.38
IFU+	9.01	14.83	22.23	30.61	35.23	37.2	37.18	37.86
ID	8.95	14.77	21.36	28.07	31.86	33.3	33.78	34.59	9.68
ID+	8.95	14.77	22.3	30.68	35.3	37.18	37.56	37.94
ISD	8.98	14.88	21.4	28.1	31.89	33.33	33.81	34.62	10.58
ISD+	8.98	14.88	23.54	30.62	35.74	37.31	37.89	38.17
SF	9.18	15.07	21.7	28.44	32.35	33.84	34.34	35.13	8.88
SF+	9.18	15.07	23.14	31.16	36.1	37.36	37.36	38.28
SD	9.19	15.04	21.7	28.44	32.35	33.84	34.35	35.13	9.0
SD+	9.19	15.04	23.15	31.17	36.11	37.38	37.36	38.29
SSD	9.15	15.12	21.7	28.44	32.35	33.84	34.34	35.13	8.99
SSD+	9.15	15.12	23.15	31.17	36.11	37.37	37.36	38.29

Conclusions drawn from Table 4:

• The prefix and non-repetition additions are beneficial. The “+” variants (representing the variants with the prefix and non-repetition additions) are always better than the basic LM’s variants for word completion after having the first two or more letters. The improvement rate between each LM’s variant and its corresponding “+” variant varies between 3% and 11% and between 7% and 8% for the four best variants (colored with red).

• Regarding the KS results for word prediction, the synthesized LM’s variants (the three most complex and advanced LMs (# 14–16 in Table 1) are the best LMs with KS results approximately 16.8%. Much better results are achieved for word completion after having a few letters.

• Regarding the KS results for word completion after having at least seven letters, it is unclear which LM’s variant is the best LM. The results of four different advanced “+” variants are ≥ 46% and are rather similar. The best LM’s variant is the most complex one, SSD+ (the “synthesized LM with super dynamic weights” variant) with a KS result of 46.73%.

• The basic n-gram models can be ranked according to their KS results (for at least three known letters) in the following descending order: bigram, unigram, trigram, and quadgram. The limited success of the trigram and quadgram LMs is probably because the discussed corpora are relatively small, and in many cases, the “correct” word is not presented at all or it lacks the highest frequency as the last word in the n-gram strings (for n ≥ 3). Furthermore, there are many more potential three or four gram strings than potential two gram strings; therefore, it is less likely to predict or complete the correct word. Due to these factors, the results of the quadgram produced poorer results than the trigram.

• For most of the LMs’ variants, the more known letters for each word that should be completed, the better the KS results. Improvements greater than 1% along the same variant (row) were achieved until word completion of five letters. After having at least five letters, the KS improvement rates were less than 1% for all LM’s variants.

  Conclusions drawn from Table 5:

  • In contrast to the results for the A7’s corpus (Table 4):The synthesized LM’s variants are the best LMs with a KS result of 12.8% lower than the matching results for the A7 corpus (~16.8%).

  • The best KS results for word completion after having at least seven letters for the Haaretz corpus (~37.7%) are significantly lower than the best KS results for the A7 corpus (~46.5%). A logical explanation for this finding is that the Haaretz corpus has a broader range of n-grams words (81104 different tokens) than the compatible number of different tokens in the A7 corpus (58587 different tokens) and fewer repetitions of n-grams words; therefore, the statistical LMs are less successful.

  • The basic n-gram models for the Haaretz corpus (unigram, bigram, trigram, and quadgram) are different from the results for the A7 (bigram, unigram, trigram, and quadgram).

• Similar to the results for the A7’s corpus:

  • The prefix and non-repetition additions are beneficial. The “+” variants are always better than the basic LM’s variants for word completion after having the first two or more letters. The improvement rate between each LM’s variant and its corresponding “+” variant varies between 2% and 11% and between 7% and 8% for almost all of the variants in general and for the three best variants (colored with red).

  • In most cases, all LMs’ variants produced higher KS results the more known letters they had. Improvements greater than 1% along the same variant (row) were achieved until word completion of five letters. After having at least five letters, the KS improvement rates were less than 1% for all LM’s variants.

  Conclusions drawn from Table 6:

• In contrast to the results for the A7’s corpus (Table 4):

  • The synthesized LM’s variants are the best LMs with a KS result of approximately 9.2%, significantly lower than the matching results for the A7 corpus (~16.8%) and the Haaretz corpus (~12.8%).

  • The prefix and non-repetition additions are more successful than those reported for the two previous corpora. The “+” variants are always better than the basic LM’s variants for word completion after having the first two or more letters. The improvement rate between each LM’s variant and its corresponding “+” variant varies between 4% and 74% (!) and between 9% and 11% for almost all of the variants in general and 9% for the three best variants (colored with red). A possible partial explanation of these findings is that this corpus covers a more limited domain (the economic domain) and there are relatively more groups of words that share common prefixes.

  • The basic n-gram models can be ranked according to their KS results (for at least four known letters) in the following descending order: unigram, bigram, trigram, and quadgram. These results are similar to those of the Haaretz corpus and in contrast to those of the A7 corpus.

• Similar to the results for the A7’s corpus:

  • In most cases, all LMs’ variants produced higher KS results the more known letters they had. Improvements greater than 1% along the same variant (row) were achieved until word completion of five letters. After having at least five letters, the KS improvement rates were less than 1% for all LM’s variants.

The best LM for both word prediction and completion for all of the three examined corpora (Tables 4–6) is the improved synthesized LM type (the interpolated and integrated LM and tagged LM) for all three variants. For word completion, all LM’s variants that include the two additions are better than the basic LM’s variants. These additions are not relevant for word prediction.

To identify which improvement is the best and whether one of the improvements can be omitted, we separately measured the improvement rate of each improvement (1—prefix and, 2—non-repetition). Due to the high run time (a few weeks) needed to generate Tables 4–6, we performed the experiments only for the most complex variant, the SSD+ for all of the three corpora.

Table 7 presents the contribution rate of the prefix and/or the non-repetition additions over the three web newspaper corpora. For each corpus, four rows are presented. The first row presents the basic variant (HaCohen-Kerner, Applebaum, and Bitterman 2014); the second row (with “1” adjacent to the right of the name of the model) presents the result after adding addition # 1 (the prefix improvement); the third row (with “2”) presents the result after adding addition # 2 (the non-repetition improvement); and finally, the row with “+” presents the result after adding both additions.

Table 7. The contribution of each addition to the SSD+ model.

(1) Corpus	Prediction	1	2	3	4	5	6	7+
A7	16.8	24.43	31.52	37.74	41.29	42.54	42.92	43.36
A7 1	16.8	24.43	31.76	38.29	42.46	43.83	44.46	45.33
A7 2	16.8	25.62	32.82	39.66	44.06	45.51	45.79	46.07
A7 +	16.8	24.43	32.66	39.64	44.13	45.61	45.9	46.73
Haaretz	12.75	17.53	22.43	27.83	31.94	33.54	34.03	34.97
Haaretz1	12.75	17.52	22.53	28.17	32.99	34.83	35.25	36.14
Haaretz2	12.22	17.63	22.78	28.69	33.64	35.66	36.1	36.81
Haaretz+	12.75	17.53	23.33	29.35	34.42	36.34	37.14	37.71
Themarker	9.15	15.12	21.7	28.44	32.35	33.84	34.34	35.13
Themarker1	9.15	15.12	21.85	28.96	33.21	34.74	35.34	35.99
Themarker2	8.85	15.72	22.377	30	35.03	36.78	37.22	37.62
Themarker+	9.15	15.12	23.15	31.17	36.11	37.37	37.36	38.29

Conclusions drawn from Table 7:

• The two additions contribute to improving the KS rate only for word completion. These additions are not relevant for word prediction.

• The non-repetition addition was better than the prefix addition.

• The best variant for each LM for all of the three examined corpora is the “+” variant, which uses both improvements, i.e., the use of both additions leads to the best improvement.

Summary, conclusions, and future work

Whereas previous systems for the Hebrew language apply known variants of existing LMs without any alteration, in this study, we introduced four types of improvements concerning the LMs or the methods to test them. These improvements have been either fully or partially applied on 16 different variants of five types of LMs dealing with word prediction and completion in Hebrew.

The best LM for both word prediction and completion for all of the three examined corpora is the improved synthesized LM type (the interpolated and integrated LM and tagged LM) for all three variants. For word completion, the non-repetition and the Hebrew prefix improvements improved the KS rate for all of the LM’s variants. That is to say, all LM’s variants that include these improvements are better than the basic LM’s variants for word completion. The non-repetition improvement was better than the prefix improvement. However, the use of both improvements led to the best KS results.

Future directions for research would be to define and apply: (1) The use of dotted Hebrew to improve the KS for Hebrew texts; (2) Other types of LMs (e.g., LMs acquired by sampling of n-grams from documents or sampling of documents in order to speed up the construction of LMs) for this task as well as for other domains, applications and languages; and (3) Integration of LMs with other software components (e.g., POS-tagger, a morphological analyzer, and a cache model).

Notes

^1. http://research.microsoft.com/en-us/downloads/78e26f9c-fc9a-44bb-80a7-69324c62df8c/

^2. http://www.google.com/

^3. http://www.mila.cs.technion.ac.il/eng/tools_analysis.html

^4. http://www.mila.cs.technion.ac.il/eng/about.html

^5. Arutz Sheva is an Israeli national religious media network. It offers free podcasts, live streaming radio, a daily e-mail news update, streaming video, and 24-hour updated text news.

^6. Haaretz is Israel’s oldest daily newspaper. It was founded in 1918 and is now published in both Hebrew and English. Both Hebrew and English editions can be read on the Internet.

^7. Themarker is an economic news website that offers ongoing coverage of the capital markets in Israel and globally, high-tech, advertising and media industries, real estate, labor market, consumer markets, the Israeli legal world, communication, vehicles, and transportation.

^8. NRG is the online edition of the Israeli newspaper Maariv. Whereas most of the content on the website comes from the print edition, some of the material is written exclusively for the web edition.