Mohamed Amine Menacer

Abdelfetah Boumerdas

Chahnez Zakaria

Kamel Smaili

A new language model based on possibility theory

Keywords: Machine Translation, probabilistic approach, the possibility theory, Language Model

Language modeling is a very important step in several NLP applications. Most of the current language models are based on probabilistic methods. In this paper, we propose a new language modeling approach based on the possibility theory. Our goal is to suggest a method for estimating the possibility of a word-sequence and to test this new approach in a machine translation system. We propose a wordsequence possibilistic measure, which can be estimated from a corpus. We proceeded in two ways: first, we checked the behavior of the new approach compared with the existing work. Second, we compared the new language model with the probabilistic one used in statistical MT systems. The results, in terms of the METEOR metric, show that the possibilistic-language model is better than the probabilistic one. However, in terms of BLEU and TER scores, the probabilistic model remains better.

Introduction

Language models are essential in many domains such as Statistical Machine Translation (SMT) [START_REF] Brown | A statistical approach to machine translation[END_REF], Automatic Speech Recognition (ASR) [START_REF] Rosenfeld | Two decades of statistical language modeling: Where do we go from here? p[END_REF], Optical Character Recognition (OCR) [START_REF] Srihari | Combining statistical and syntactic methods in recognizing handwritten sentences[END_REF] etc. They are generally used to ensure that a system not only produces the right words but also to output them in a fluent language.

In SMT, the main role of language models is to choose, among the huge number of hypotheses, the right translations. These models are generally based on the probability theory. They proceed by estimating the probability of a linguistic event 1 from a sufficiently large text corpus.

Many language models have been proposed and developed in literature, such as: cache based models [START_REF] Kuhn | A cache-based natural language model for speech recognition[END_REF], trigger based models [START_REF] Lau | Trigger-based language models: A maximum entropy approach[END_REF] and multi-gram models [START_REF] Deligne | Language modeling by variable length sequences: Theoretical formulation and evaluation of multigrams[END_REF]. These three models are strongly related with the n-gram model [START_REF] Jelinek | Continuous speech recognition by statistical-methods[END_REF], which is the most dominant and the most used model in the language modeling field. Other language models, based on other paradigms than n-gram, have been proposed. For instance, the connexionist language model, proposed by [START_REF] Bengio | Neural probabilistic language models[END_REF], which is very useful when the training data is limited.

There are various limitations of n-gram models. The classical limitations include, for example, the context-dependent issue. In fact, the probability assigned by the model is related to the context in which it occurs. This context is modeled by the size n of the model, which is, in many cases, insufficient to capture the underlying topic information. Moreover, there is another problem related to the probability theory: generally the probability assigned by these language models is significant especially with high and medium frequency events. However, when it comes to low frequency events, the theory breaks down and the model fails to assign reliable probabilities. Therefore, it turns to smoothing techniques to estimate the probability of the corresponding event.

In this paper, we present a new language modeling approach using the possibility theory [START_REF] Negoita | Fuzzy sets as a basis for a theory of possibility[END_REF], which is an alternative to the probability theory in order to deal with uncertainty. This paper is organized as follows: the next section briefly presents the probabilistic n-gram language models, followed by a description of the possibility theory and the motivation that encouraged us to use it. Then, the only work, in our knowledge, that has been done to model a possibilistic language model [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] is presented. Finally, we present and describe the language model based on the possibility theory along with some tests to compare its performances with those of the baseline language models.

Probabilistic n-gram language models

A probabilistic language model could be considered as a function that measures how likely a sentence can be expressed by a speaker in a particular language. In a more formal way, if the following word-sequences: e = e 1 e 2 ...e l is proposed by a system, then the probability P (e) can be decomposed and calculated as in [START_REF] Bengio | Neural probabilistic language models[END_REF].

P (e) = P (e 1 e 2 ...e l ) = l j=1 P (e j |e 1 e 2 ...e j-1 )

In formula (1), we notice that the probability of the word-sequence e depends on the conditional probability of each word e j knowing its history e 1 e 2 ...e j-1 . However, the length of the taken history is a major problem because it is impossible to find all the possible histories that can precede a given word. Consequently, the exact value of the probability P (e j |e 1 e 2 ...e j-1 ) cannot be calculated. To deal with this issue, the n-grams language model assumes that the word e j depends only on the n -1 words that precede it as it is shown in the equation [START_REF] Brown | A statistical approach to machine translation[END_REF].

P (e) = l j=1
P (e j |e j-n+1 e j-n+2 ...e j-1 )

However, according to the previous equation, if the n-gram model fails to find a similar word-sequence in the training data, the probability of the n-gram could be assigned a zero value. This can be misleading because an unseen n-gram doesn't mean that it is wrong. Generally, some other techniques are used along with the n-gram language model in order to estimate and adjust the value of the probability P (e) and to avoid the problem of assigning zero probability to unseen n-grams; such methods are called the smoothing techniques.

The smoothing techniques can be divided into two groups: the first one concerns the count smoothing methods such as the add-one smoothing, the deleted estimation and Good-Turing smoothing. The second one considers interpolation and back-off based smoothing techniques like: linear interpolation, back-off, Witten-Bell smoothing [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF], Kneser-Ney smoothing [START_REF] Kneser | Improved backing-off for m-gram language modeling[END_REF] and Modified Kneser-Ney smoothing [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF]. However, there is no technique that performs well in all situations. For all these reasons, we propose to use another theory: the possibility theory.

The Possibility Theory

The possibility theory was proposed by Zadeh [START_REF] Negoita | Fuzzy sets as a basis for a theory of possibility[END_REF] in 1978 as an extension of fuzzy sets theory and fuzzy logic. It is a mathematical framework that deals with the representation of uncertain information resulting from incomplete knowledge [START_REF] Dubois | Possibility theory and statistical reasoning[END_REF].

Traditionally, all uncertainties of information are quantified and handled by the probability theory. However, the theory of probability knows some gaps in some cases like the famous Bertrand paradox [START_REF] Saporta | Probabilités, analyse des données et statistique[END_REF] where one could obtain several different values of probability for the same event only by changing the way of reasoning. The probability theory uses only one measurement to deal with uncertainty, which is the probability measure itself. Therefore, it is limited in certain situations. For example, if we affirm that the sentence "I eat an apple" is a well written English sentence with a probability of 0.8, we are faced with two problems. The first one is the percentage of error of this probability, which indicates the inaccuracy of respecting English language usage rules. The second issue concerns the uncertainty, i.e. there is a 80% chance that this sentence faithfully respects all the usage rules of the English language.

To take these phenomena into account, the possibility theory employs two measures: the necessity N and the possibility Π. The first allows to affirm that an event is possible with a certain degree and the second represents the degree of certainty of an event. Consequently, the possibility theory completes the probability theory.

In the same way, as in the probability theory, where the probability P can be obtained from the probability distribution, the possibility and necessity measures can be defined from the possibility distribution π in the possibility theory. But unlike the probability theory, the use of the possibility and the necessity measure in the possibility theory allows us to distinguish what is plausible from what is less plausible, what is normal from what is not, what is surprising from what is expected [START_REF] Dubois | Possibility theory[END_REF]. These advantages can be very useful to build a possibilistic language model that can reduce some limitations of the probabilistic language models.

The possibility distribution is a function of the universe Ω to the interval unit [0, 1] with the following interpretations: π(s) = 1 means that the event s is possible and π(s) = 0 means that the event s is considered as impossible.

In the finite state, the possibility and the necessity measures are defined as described in (3) and [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF].

Π(A) = max s∈A (π(s)) (3)
N (A) = min s ∈A (1 -π(s)) (4)
where A is a subset of the reference set Ω, representing a set of events. In summary, the uncertainty of a proposition or an event A in the possibilistic model is measured by the couple (Π(A), N (A)), unlike the probabilistic model where the uncertainty of an event is measured by only the probability P .

Related works

To our knowledge, the only language model based on the possibility theory is the one described in [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF]. This work uses the web as an open training corpus to improve language modeling. The reason behind using the web lies in the great and constantly growing volume of its textual documents. The resulting language model was integrated in a speech recognition system.

The basic idea behind the method of Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] is to consider the observed events and non-observed ones in the web. Therefore, two theories were employed: probability and possibility. The probability theory is used to take advantage of events observed on the Web, and the possibility theory is used to take advantage of unobserved events on the web.

To benefit from both theories: probability and possibility, Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] also proposed a method to combine the probability and the possibility measures.

Possibility estimated on a text corpus

The method proposed by Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] estimates the possibility of a word-sequence from the web or from a text corpus. The basic idea of this method is the following: for a given word-sequence, the possibility is estimated according to its sub-sequences. Consequently, the more sub-sequences of the original word-sequence exist in the training corpus, the higher this wordsequence is possible. A similar principle is used in the BLEU measure, which is used to evaluate the quality of a translation [START_REF] Papineni | Bleu: A method for automatic evaluation of machine translation[END_REF]. Thus, for a higher reliability of results, the size of the sub-sequences is given according to the order of the model. Every time a n-gram sub-sequence does not exist, the existence of all its (n -1)-grams sub-sequences is studied until a uni-gram level is reached.

This idea is formulated for a n-gram language model following a recursive equation. This equation determines a set of possibility distributions starting from π n until reaching π 1 :

π n (W ) = |Wn∩Cn|+α|Wn/Cn| |Wn| if n ≥ 1 0 else (5)
where:

-W : is a sequence of one or more words.

-W n : is a set of word sequences of size n in W .

-C n : is the set of word sequences of size n in the corpus C.

α: is the back-off coefficient with 0 ≤ α ≤ 1.

-/: is the set subtraction operator.

This formula takes into account, at the same time, the observed and the unobserved events. To calculate the possibility for a word-sequence W , the number of sub-sequences of size n of W present in the training corpus is normalized by the total number of sub-sequences of size n in W . Thus, to propose a precise possibility distribution, a back-off strategy is used recursively to interpolate high order possibilities from its sub-sequence possibilistic scores.

The possibility distribution defined above allows deriving the possibility measure as in equation [START_REF] Deligne | Language modeling by variable length sequences: Theoretical formulation and evaluation of multigrams[END_REF].

Π n (A) = max W ∈A (π n (W )) ( 6
)
where A is a set of sequences of n or more words.

If the whole corpus is considered as a unique element W , then:

Π n (W ) = π n (W ) (7)
6 A new approach based on the possibility theory

The approach proposed by Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] has some limits. For instance, when calculating the possibility of a word-sequence in their formula, the sequence is initially divided into a group of n-grams, then each n-gram is checked whether it exists in the training corpus or not. By doing so, all the extracted n-grams will have the same weight. This could be considered as a limit for the language model. In fact, even if a sequence of words belongs to a foreign language1 , the above formulation could give it a high possibility.

To overcome this limit, a novel approach, based on the same idea as that of Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] is proposed in our study. In fact, Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF] define the possibility of a word-sequence based on the existence or the non-existence of this sequence or its sub-sequences of size n in the training corpus. However, in our approach, we consider a weight estimated from a training corpus, which reinforces the possibility of a word-sequence that contains a subsequences often encountered. Furthermore, we interpolate the possibility of a sequence with that of the sequences of lower size. This allows, on one hand, to take into account the case where a sequence does not appear in the training data. On the other hand, it increases the possibility distribution. By considering these assumptions, the possibility-based language model estimates the possibility of a sequence of n words as follows:

π n (W ) = n k=1 λ k α k α i=1 N (w k i ) β k (8)
where:

-W k i : is the i-th sub-sequence of size k in W .

-N (W k i ): is the number of occurrences of the word w i of size k in the training corpus C.

α: is the number of unique sub-sequences w i of size k in the test corpus W .

β k : is the total number of sub-sequences of size k in the training corpus C.

α k = α α : where α is the number of units of size k in the test corpus that exist in the training corpus where α ≤ α.

λ k : is the possibility weighting coefficient.

i λ i = 1. Suggesting that λ 1 ≤ λ 2 ≤ ... ≤ λ n will ensure that a more important possibility is assigned to longer sequences.

For a word-sequence W , its possibility value is defined according to the sub-sequences composing it. For each sub-sequence of size k, we determine its ponderation estimated from the training corpus. Additionally, we back-off to smaller possibilistic model. This back-off is handled by the two coefficients λ k and α k .

To determine the value of the possibility measure for a test corpus C t made up of several word-sequences of size n or more, we apply the formula [START_REF] Dubois | Possibility theory and statistical reasoning[END_REF].

Π n (W ) = max W ∈Ct (π n (W )) (9)
If the test corpus is considered such as a long sentence W , then:

Π n (W ) = π n (W )) (10)
As in the method of Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF], the calculation of the possibility measure does not require the decomposition of the total possibility in conditional possibilities, which allows us to evaluate a word-sequence totally and not sequence by sequence as done with a probabilistic-based language models.

Tests and Results

In order to evaluate the performance of the possibilistic-language model, we consider two types of tests: the goal of the first test is to study the behavior of the new approach compared to that proposed by Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF]. In the second one, we compare our approach with the probabilistic model used by the Moses decoder during the translation process. This probabilistic language model is calculated using the KenLM language modeling tool [START_REF] Heafield | Kenlm: Faster and smaller language model queries[END_REF].

In the following section, the results obtained from the two tests are presented and discussed.

Experiment on language modeling

In this test, we considered the English corpus of EUROPARL [START_REF] Koehn | Europarl: A Parallel Corpus for Statistical Machine Translation[END_REF]. This corpus is composed of the proceedings of the European Parliament since 1996. Table 1 illustrates the number of sentences and the number of words in this corpus. We subdivided the corpus in three parts as follows:

-80% used as training data which corresponds to a vocabulary of 111 072 distinct words. -10% used for tuning and more specifically for estimating the values of λ k .

-The last 10% of the corpus used as test data.

We achieved several experiments concerning the possibility-language model on four other corpora. The aim of the first corpus is to study the possibility of a text that is well written in the source language (English). The two other corpora are poorly written in English and the final corpus is written in a foreign language (French). The purpose of these three last tests is to check if the possibilitic-language model estimates correctly their possibility, if so, the possibility of these two corpora should be low.

Statistics on the four test corpora are presented in the table 2. -Europarl is taken from test data (10% of the Europarl corpus).

-RandEuroparl is randomly generated from the vocabulary wordlist.

-RandEnglish is randomly generated from an English wordlist.

-Foreign is well written in French.

Before testing our possibilistic-language model, we show the influence of the interpolation coefficient λ k on the calculation of the possibility measure. Initially, we fixed the values of λ k in order to make the sub-sequence of size n more possible than the one of size n -1 and so on. Then, we estimated the values of λ k using a greed search algorithm on the development corpus. Table 3 illustrates the total number of sentences and words, as well as the size of the vocabulary. The values of λ k fixed by hand and evaluated by a greed search algorithm are shown in table 4. The values of the possibility corresponding to these λ k and for n = 4 are given in table 5. We can notice that the values of the possibility measure obtained after the estimation of the values λ k are a bit higher compared to the values obtained by fixing λ k by hand. This is because of the high values of λ k assigned to the n-grams of lower order (uni-grams and 2-grams), which are generally more frequent than the n-grams of higher order (3 and 4-grams).

Next, we compared the values of the possibility given by our language model and the one proposed by Oger and Linarès [START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF]. The results of this comparison are illustrated in table 6. We notice that in both approaches the possibility value is low for the test corpora, which are badly written in English (the two corpora RandEuroparl and RandEnglish) or written in a foreign language. For the test corpus that is well written in English (Europarl Corpus), the value of the possibility is high in both approaches. We notice also that for the two approaches, the value of the possibility increases with the reduction of the model size. This is due to the n-grams of the lower order (1 and 2-grams) which are generally frequent in the training corpus.

Experiment on Machine Translation

In the second test, we achieved a comparison between our possibilistic language model and the probabilistic model within machine translation systems. In order to do that, we train a French to English translation model using Moses decoder [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF] and its tools. Some statistics about the data used to train the translation model are illustrated in table 7. In order to compare between the two models, a corpus test of 1000 sentences (∼ 33000 words) has been selected. The translation process uses the possibilisticlanguage model and then a baseline language model (probabilistic). To achieve this goal, we proceeded as follows:

1. We used Moses decoder and its toolkit to translate the sentences and associate to each one a list of its 1000 best translations proposed by the decoder. 2. For each sentence, we sorted its 1000 best translations, in a decreasing order, using the probabilistic model. 3. For each sentence, we kept only its best translation. 4. Finally, we used the MultEval tool [START_REF] Clark | Better hypothesis testing for statistical machine translation: Controlling for optimizer instability[END_REF] to calculate three scores: BLEU [START_REF] Papineni | Bleu: A method for automatic evaluation of machine translation[END_REF], METEOR [START_REF] Denkowski | Meteor 1.3: Automatic metric for reliable optimization and evaluation of machine translation systems[END_REF] and TER [START_REF] Snover | A study of translation edit rate with targeted human annotation[END_REF] in order to evaluate the quality of the translations.

The previous steps have been used to evaluate the probabilistic language model. In order to evaluate the possibilistic-language model, the same steps (from 1 to 4) are used except for the second one where we sorted the sentences using our possibilistic model. The results concerning the two models are illustrated in table 8. It is clear that the possibilistic-language model ensures the best values for METEOR compared to the baseline one. However, the two metrics BLEU and TER, confirm that the probabilistic language model achieves better results. This performance is encouraging since in [START_REF] Callison-Burch | Further meta-evaluation of machine translation[END_REF], the authors show that the ME-TEOR score correlates most with human judgment when MT is achieved from any language to English (which is the case in our system). However, the BLEU score correlates best when the translation is done from English into another language.

Thus, the advantage of METEOR is that it establishes correspondences between the reference and candidate translation on word matching, synonyms or words with the same root. However, the BLEU and TER scores are based on an explicit word matching between translation and reference. Some sample translations, using the two language models, compared to the reference translation are given in table 9. These examples, among many others, show that the approach we propose achieves better translations, which could be considered as new references for the BLEU measure to help improve the quality of the translation even better. we also need to look at some of the issues of the Treaty of Amsterdam.

we also have to analyse some of the issues, created by the Treaty of Amsterdam.

we also have to look at some of the challenges created by Amsterdam.

nous devons conserver ce droit afin de défendre un intérêt national.

we should retain the right to defend their national interests.

we must keep this law, in order to defend the right to a national interest.

we have to retain that right to defend a national interest.

Conclusion

To conclude, in this paper, we presented a new language model based on the possibility theory while the majority of the language models used in speech recognition and machine translation are based on probabilistic approach. The interest of this new model is that it takes into account the uncertainty. We expect that this new method, which shows the feasibility of the principle, would be an alternative to classical language models. We have tested this method in a real machine translation system, and it achieved promising results. In fact, in terms of METEOR, our model is better than the baseline one while it is less efficient in terms of BLEU. Knowing that METEOR is more correlated with human judgments since this measure has been designed to overcome the weakness of BLEU and NIST. That is why we are optimistic about the interest of this approach in the near future.

Table 1 .

 1 Statistics on the EUROPARL corpus.

	Language	|S|	|W |
	English	2 218 201 53 974 751

Table 2 .

 2 Statistics on the test corpora.

	Corpus	|S|	|W |
	Europarl	35 000 966 990
	RandEuroparl 35 000 1 032 197
	RandEnglish	35 011 1 031 452
	Foreign	34 722 907 024

Table 3 .

 3 Statistics on the development corpora.

	Language	|S|	|W |	|V |
	English 200 773 5 605 794 45 849

Table 4 .

 4 Values of λ k fixed by hand and estimated by a greed search algorithm.

	n	λ k	λ Hand λ Calc
		λ1	0.1	0.23
	4	λ2 λ3	0.2 0.3	0.24 0.26
		λ4	0.4	0.27
		λ1	0.2	0.32
	3	λ2	0.3	0.33
		λ3	0.5	0.35
	2	λ1 λ2	0.4 0.6	0.49 0.51

Table 5 .

 5 The possibility-language model values with estimates and fixed λ k .

	Corpus	Π Hand n	(w) Π Calc n	(w)
	Europarl	0.33	0.46
	RandEuroparl 0.01	0.03
	RandEnglish	0.03	0.06
	Foreign	0.005	0.01

Table 6 .

 6 Comparison between our language model and the one proposed by Oger and Linarès[START_REF] Oger | Web-based possibilistic language models for automatic speech recognition[END_REF].

	Corpus	n	Πn(W )	Π Oger n	(W )
		4	0.45	0.49
	Europarl	3	0.6	0.77
		2	0.77	0.95
		4	0.02	1.52 × 10 -7
	RandEuroparl	3	0.04	1.52 × 10 -5
		2	0.06	1.52 × 10 -3
		4	0.06	3.56 × 10 -7
	RandEnglish	3	0.08	3.56 × 10 -5
		2	0.12	3.56 × 10 -3
		4	0.012	3.11 × 10 -4
	Foreign	3	0.017	4.07 × 10 -3
		2	0.026	0.07

Table 7 .

 7 EUROPARL French-English bilingual corpus statistics.

	Language	|S|	|W |	|V |
	French	1 579 312 48 576 991 128 051
	English 1 579 312 53 974 751 111 072

Table 8 .

 8 Metric scores (BLEU, Meteor and Translation Error Rate -TER-) for all systems.

	Metric	System Prob 1 System Poss 2
	BLEU ↓	28,6	27,5
	METEOR ↑	32,1	33,2
	TER ↑	52,9	57,1

Table 9 .

 9 Example of a translation using the probabilistic language model and the possibilistic one.

	source	trans Prob LM	trans Poss LM	reference
	nous devons
	également analyser
	certains des enjeux
	créés par le traité
	d'Amsterdam.

A linguistic event is the succession of one or several words.

This is possible for close languages which share several words such as English and French.

The system where probabilistic language model is used.

The system where possibilistic-language model is used.