The existence of huge volumes of documents written in multiple languages in Internet lead to investigate novel approaches to deal with information of this kind. We propose to use a statistical approach in order to tackle the problem of dealing with crosslingual natural language tasks. In particular, we apply the IBM alignment model 1 with the aim of obtaining a statistical bilingual dictionary which may further be used in order to approximate the relatedness probability of two given documents (written in different languages). The experimental results sucessfully obtained in three different tasks -text classification, information retrieval and plagiarism analysis- highlight the benefit of using the presented statistical approach.
The fast growth of the Internet and the increasing presence of multilinguality on the web poses new challenges for Natural Language Processing (NLP) technology. This fact leads us to the necessity of developing novel techniques to manage multilingual data. Indeed, the growing demand of NLP systems that deal with multilingual information induces the development and evaluation of multilingual systems in international events such as the Cross Language Evaluation Forum (CLEF)3 and the Text Analysis Conference (TAC)4.
It is easy to find examples of NLP applications in which more than one
language is involved. In this paper, we focus on three specific multilingual
applications: bilingual Text Classification (TC), crosslingual Information Retrieval
(IR) and crosslingual plagiarism. The proliferation and categorisation of
multilingual documentation has become a common phenomenon in many official
institutions and private companies. The most significant case is the EU
parliament and commission, in which most official documents are translated into
more than 20 languages, and categorised according to the Eurovoc thesaurus [
4 http://www.nist.gov/tac/ In this scenario, we could take advantage of redundancy and word correlation across languages to improve the accuracy of text classifiers. Moreover, users may be interested in information which is in a language other than their own native one. A common language scenario is where a user has some comprehension ability for a given language but the user is not sufficiently proficient to confidently specify a search query in that language. Thus, a search engine that may deal with this crosslingual problem should be of a high benefit. Finally, another multilingual application would be crosslingual plagiarism. In particular, this latter application is a real problem which ocurrs very frequently, for instance, in academic environments. It consists of the detection of text fragments which have been translated or partially rewritten from one original language without the adequate reference to the original text. The crosslingual component added to traditional NLP tasks incorporates a higher level of complexity which must be studied adequately.
Most of the current approaches to crosslingual NLP use conventional
monolingual NLP techniques that usually incorporate a decoupled translation process
as a preprocessing step to bridge the crosslingual gap. However, this two-step
approach is too sensitive to translation errors, and in general to the accumulative
effect of errors. In fact, even if we have a highly accurate NLP system, translation
errors may prevent us from obtaining the desired performance. To overcome this
drawback, we propose to bring together source and target documents written
in two different languages as input to a direct probabilistic crosslingual NLP
system which integrates both steps, translation and the specific NLP task, into
a single one. In order to carry out this integrated approach to crosslingual
applications, we propose to employ the IBM alignment model 1 (M1), which was
firstly introduced for statistical Machine Translation (MT) [
The M1 model, the first of the IBM models, is basically defined as a statistical
bilingual dictionary that captures word correlation across languages. In
statistical MT, the M1 model has traditionally been an important component part in
applications such as the alignment of bilingual sentences [
The rest of this paper is structured as follows. Section 2 presents the M1 model together with the maximum likelihood estimation of its parameters using the Expectation-Maximisation (EM) algorithm. In Section 3 we introduce the three crosslingual applications in which the M1 model has been applied and we describe how the M1 model has been integrated. Section 4 shows the experimental results obtained on actual tasks related to the proposed crosslingual applications. Finally, conclusions and further work are discussed in Section 5. 2.1
where A(x, y) denotes the set of all possible alignments from x to y. Now, we can factorise the term p(x, a | y) at the word-level from left to right Let x = x1 . . . xj . . . x|x| be a sentence in a certain source language of known length |x| and y = y1 . . . yi . . . y|y| is its corresponding translation in a different target language of known length |y|. Let X and Y denote the source and target vocabularies, respectively.
To derive the M1 model we start from the target-conditional probability distribution p(x | y), for which we define the alignment hidden variable a = a1 · · · aj · · · a|x|. The alignment variable connects each source word to exactly one target word aj = {0, · · · , i, · · · , |y|}, being 0 the position of the NULL5 word p(x | y) =
p(x, a | y)
X a∈A(x,y) (1) (2) (3) (4) (5) |x| p(x, a | y) = Y p(xj , aj | xj1−1, aj1−1, y) j=1 |x| = Y p(aj | xj1−1, aj1−1, y) p(xj | xj1−1, aj1, y)
j=1 where p(aj | xj−1, aj1−1, y) is an alignment probability function (p.f.) and 1 p(xj | xj1−1, aj1, y) is a lexical p.f. or statistical dictionary.
The well-known M1 model is defined by making the following two assumptions. First, we assume that the probability of aligning a source position to a target position is uniform p(x, a | y; Θ) = Y|x| 1 j=1 |y| + 1 p(xj | yaj ) 5 The NULL word represents the target word to which those source words with no direct translation are connected.
p(aj | xj1−1, aj1−1, y) :=
1 |y| + 1
p(xj | xj1−1, aj1, y) := p(xj | yaj ) Then, we also assume that the probability of translating a source word does only depend on the target word to which is aligned where p(xj | yaj ) is a statistical bilingual dictionary. Thus, we can rewrite Eq. (2) under assumptions in Eqs. (3) and (4) as where the parameter vector is a statistical bilingual dictionary.
Θ = p(u | v) u ∈ X , v ∈ Y The model using indicator vectors Now we change the nature of the original alignment variable aj ∈ {0, . . . , |y|} from an integer value into an indicator vector aj = (aj0, aj1, . . . , aj|y|)t. in order to ease the presentation of the parameter estimation of the M1 model. The vector aj values one in the ith position and zeros elsewhere, if the source position j is aligned to the target position i. Equivalently to Eq. (5), we have 2.2
In this section we present the maximum likelihood estimation of the parameter vector Θ for the M1 model with respect to a set of N independent bilingual samples (X, Y ) = ((x1, y1), . . . , (xn, yn), . . . , (xN , yN ))t, where the sequence of source and target words of the nth sample is xn = xn1, . . . , xnj , . . . , xn|x| and yn = yn1, . . . , yni, . . . , yn|y| , respectively.
The log-likelihood function of Θ, which we would like to maximise, is
N |xn| |yn| L(Θ; X, Y ) = X X log X n=1 j=1
1 i=0 |yn| + 1 p(xnj | yni).
(12) According to this notation, the initial model in Eq. (1) can be rewritten as |x| |y| p(x, a | y; Θ) = Y Y j=1 i=0
1 |y| + 1 p(xj | yi) aji
.
|x| |y| p(x | y; Θ) = Y X j=1 i=0
1 |y| + 1 p(xj | yi).
Eq. (9) is the usual form of the M1 model. The M1 model makes the naive assumption that source words are conditionally independent given y |x| p(x | y; Θ) = Y p(xj | y) j=1 where
|y| 1 p(xj | y) = X p(xj | yi)
i=0 |y| + 1 is the average probability of xj to be translated into a target word in y. (6) (7) (8) (9) (10) (11) Now, let A be the set of alignment indicator vectors associated with the bilingual pairs (X, Y ) with
A = (a1, . . . , an, . . . , aN )t . (13) The variable A is the alignment missing data in the M1 model, since this information is not present in the bilingual samples (X, Y ). Indeed, if the alignment information were available, the estimation of the parameter p(u | v) would be as easy as counting how many times the source word u is aligned to the target word v in (X, Y ) and normalise adequately. However, we do not know how the bilingual samples are aligned, and the maximisation of Eq. (12) in order to estimate Θ is troublesome.
For this reason, we need to revert to the well-known EM algorithm that performs the maximum likelihood estimation of statistical models with missing data. The idea behind the EM algorithm is to estimate the parameter vector Θ in two iterative steps. First, the so-called E-step computes the expected value of the missing data, in our case, an estimation of the actual value of the alignment data. Then, in the so-called M-step, given that we have an estimation of the missing data we can compute Θ, in the case of M1 model, an estimation of the bilingual dictionary. This two-step process is repeated to refine the estimation of the missing data, and then improve the estimation of the parameter vector.
Formally, the E step computes the expected value of the logarithm of the term p(X, A | Y ), given the (incomplete) data samples (X, Y ) and a current estimate of Θ at iteration k, Θ(k). Given that the alignment variables in A are independent from each other, we can compute the E step, with where
N |xn| |yn| Q(Θ | Θ(k)) = X X X a(nkj)i log n=1 j=1 i=0
1 |yn| + 1
+ log p(xnj | yni) a(nkj)i =
p(xnj | yni)(k) P|iy′=n|0 p(xnj | yni′ )(k) .
That is, the expectation of word xnj to be aligned to yni is our current estimation of the probability of xnj to be translated into yni, instead of any other word in yn (including the NULL word).
In the M step, we maximise Eq. (14), in order to obtain the standard update formula for the M1 model, p(u | v)(k+1) =
N (u, v) P N (u′, v) u′∈X
∀u ∈ X , v ∈ Y
N |xn| |yn| N (u, v) = X X X δ(xnj = u) δ(yni = v) a(nkj)i .
n=1 j=1 i=0 The estimation of p(u | v) can be seen as a normalised partial count of how many times the source word u is aligned to the target word v. (14) (15) (16) (17)
In this section we introduce three different natural language tasks which could take benefit from the application of the previously presented M1 probabilistic model. The three tasks –text classification, information retrieval and plagiarism analysis– are considered to be in the crosslingual scenario, i.e., some texts are written in one language, whereas other texts of the same collection are written in another one. The following sections explain into detail the manner we have used the M1 model in each of these tasks. 3.1
The purpose of TC is to convert an unstructured repository of documents into a
structured one by automatically assigning documents to a predefined number of
groups, in the case of text clustering, or to a set of predefined categories, in the
case of text categorisation. Doing so, the task of storing, searching and browsing
documents in these repositories is significantly simplified [
Among the diverse approaches to TC, the well-known naive Bayes
classifier [
The unrealistic assumption of the naive Bayes classifier is one of the main
reasons explaining its comparatively poor results in contrast to other techniques
such as boosting-based classifier committees (boosting) [
Bilingual TC is a novel application strongly characterised by word correlation across languages. This word correlation comes from the fact that the bilingual texts to be classified are mutual parallel translations. Given the latter scenario, we propose two main approaches to tackle bilingual TC. First, we may naively consider that bilingual texts were generated independently and therefore, there is not exist any crosslingual relation between words found in mutual translations. Alternatively, we may realistically assume that an underlying crosslingual word mapping exists and can be exploited to boost the performance of a bilingual classifier. Undoubtedly, the latter approach is significantly more complex than the former, however the crosslingual structure apprehended by the latter is a valuable information that cannot be neglected.
The M1 model in bilingual text classification Formally, our goal is to
classify a bilingual parallel text (x, y) into one of the C supervised categories,
so that we minimise the classification error. According to the optimal Bayes
decision (classification) rule [
c=1,...,C c=1,...,C where
p(x, y | c) = p(y | c) p(x | y, c) can be factorised into a language p.f., p(y | c), and a translation p.f., p(x | y, c).
Given the bilingual classification rule stated in Eqs. (18) and (19), we can derive three different classification rules depending on the assumptions we make: 1. The monolingual rule only considers the contribution of one of the two languages being p(x | c) modelled as a unigram model p(x, y | c) ≈ p(x | c)
|x| p(x | c) := Y p(xj | c).
j=1 (18) (19) (20) (21) 2. The bilingual naive factorisation rule unrealistically assumes that the bilingual parallel texts are independent from each other p(x, y | c) ≈ p(x | c) p(y | c) (22) where p(x | c) and p(y | c) are modelled as source and target unigram models, respectively. This rule incorporates a second source of information into the classifier that leads to believe in its superiority compared to the monolingual rule. 3. The general rule, as presented in Eqs. (18) and (19), models the language p.f., p(y | c), as a target unigram model and the translation p.f., p(x | y, c), as an M1 model. The integration of the M1 model allows to capture word correlation across languages enriching the structure of the bilingual text classifier, being theoretically superior to the monolingual and naive rules.
The maximum likelihood estimation of the source and target models is trivially computed by relative word frequency. The estimation of the M1 model involved in the general rule was already introduced in Section 2. 3.2
In CrossLingual Information Retrieval (CLIR), the usual approach consists of
firstly translating the query into the target language and then retrieving
documents in this language by using a conventional mono-lingual information
retrieval system. The translation system might be of any type, rule-based,
statistical or hybrid. In [
Probabilistic approaches which use parallel corpora in order to translate the
input queries by means of a statistical dictionary in CLIR have been used in
previous work [
text in a certain (source) language, and let y1, y2, . . . , yn be a collection of n web pages in a different (target) language. Given a number k < n, we are interested in finding the k most relevant web pages with respect to the source query x. For this purpose, we have employed a probabilistic approach in which the k most relevant web pages are computed as those most probable ones given x, i.e., Sˆk(x) =
arg max arg min p(y | x)
S⊂{y1,...,yn} y∈S
|S|=k
(23)
In this work, p(y | x) is modelled by using the M1 model. The M1 model assumes
that the order of the words in the query is not important and, therefore, each
position in a document is equally likely to be connected to each position in the
query. Although this assumption is unrealistic in MT, we consider the M1 model
to be particularly well-suited for CLIR.
Plagiarism is the practice of rewriting someone else’s creative work, in whole
or in part, without the adequate credit of the original authorship. Plagiarism
may be carried out in the same language or across different languages (i.e.,
crosslingual plagiarism). In some way, crosslingual plagiarism analysis is related
to the crosslingual information retrieval field [
Whereas some research works have been carried out for the automatic
plagiarism analysis [
from a suspicious document in a given (source) language, and let y1, y2, . . . , yn be a set of original text fragments that may be the source of plagiarised texts in a different (target) language (the reference corpus).
Given the suspicious fragment x, the aim is to find the most probable original text fragment yˆ obtained as a plagiarised translation of x yˆ(x) =
arg max y∈{y1,...,yn} p(y | x) (24) Again, p(y | x) is modelled using the M1 model described in Section 2. 4
In this section we present the results obtained by applying the statistical approach, based on the M1 model, to three different crosslingual natural language tasks. Bilingual text classification is presented first, crosslingual information retrieval follows and, finally, the experiments with crosslingual plagiarism are shown. The three bilingual text classifiers introduced in Section 3.1 were assessed in terms of classification error rate on two categorised parallel corpora. First, we describe these two corpora and then, we present the experimental setting employed to evaluate the proposed monolingual and bilingual text classifiers.
The INTERSECT corpus is a collection of sentence-aligned parallel texts in English, French and German drawn from different subjects. The English-French partition contains extracts coming from the Bible, the Canadian Hansard, fiction books, user manuals, news, scientific-technical reports and official documents from international organisations. These seven subjects constitute the categories in which bilingual parallel sentences are classified. The statistics of this corpus can be found in Table 1.
OPUS [
– European constitution.
These four collections were considered as independent categories in which bilingual parallel sentences had to be classified. Their corresponding joint statistics are presented in Table 1.
For experimental purposes, these corpora were partitioned into three sets, devoting 80% for training, 5% for development and 15% test sets. This partitioning process was randomly carried out 30 times to compute confidence intervals on test error. The parameters of the statistical models proposed were automatically learnt on the training set, additional smoothing parameters were manually
7 OpenOffice.org is an open source office suite. 8 The K Desktop Environment (KDE) is a free graphical desktop environment. 9 Hypertext Preprocessor (PHP) is a widely-used general purpose scripting language. tuned on the development set and the accuracy of the different text classifiers was assessed on the test set.
Table 2 presents the results for the monolingual, naive and general
classifiers on the test sets of the INTERSECT and OPUS corpora. As observed in
both corpora, the monolingual classifier is outperformed by the naive and
general classifiers that incorporate additional information obtained from the second
language. However, remarkably, the general classifier that capture word
correlation across language using the M1 model is superior to the naive classifier in
which each language is modelled independently. This proves the benefits of the
M1 model to improve the accuracy of bilingual text classifiers. These results are
consistent with those presented in [
In Figure 2 it is presented the name of each run together with its MRR. The Average Success At (ASA) different number of documents retrieved (1, 5, 10, 20 and 50) is also shown in this figure. It is quite obvious the improvement that may be obtained when using the presented M1 model instead of traditional ones such as those which represent documents by using the vector space model. The main contribution of the M1 model in CLIR consists of its direct approach (translation and indexing/searching) over crosslingual data. We have carried out some preliminary experiments by selecting five document fragments, y1, · · · , y5, from one author of the information retrieval area (e.g. 10 http://www.clef-campaign.org/ y5: Intrinsic plagiarism analysis deals with the detection of plagiarised sections within a document d, without comparing d to extraneous sources). The aim of this experiment was to obtain an author-based bilingual statistical dictionary which can be used to perform an author-focused CLiPA.
For each original text fragment, we have constructed plagiarised cases by using both, machine and human translators. In the former approach, we have used five popular online translators11, whereas for the latter five different people have “plagiarised” each original fragment written in English to fragments in Italian. In general, the complete corpus is made up of the following text fragments: i Five original fragments written in English by a unique author ii Five human simulated plagiarisms for each original fragment (in Italian) iii Five automatic machine translations for each original fragment (in Italian) iv Five unplagiarised versions for each original fragment (in Italian) obtained by rewriting the same original concept but mostly with other words. iv Twenty unplagiarised (independent) fragments about the plagiarism topic originally written in Italian language
We have splitted the complete corpus into two datasets: training (60%) and test (40%). The training dataset, which is used to construct the statistical bilingual dictionary, is made up of 40 pairs composed of original fragments and their corresponding plagiarised versions. In the test dataset, we employed 10 plagiarised text fragments plus 45 unplagiarised text fragments.
Figure 3(a) shows the performance of the proposed statistical-based system
identifying plagiarized documents at different thresholds. The maximum value
obtained on the basis of the M1 model indicates the correct association between
the original and the corresponding plagiarised text fragment. The obtained
results in Italian-written plagiarisms are consistent with those reported in [
0.75 0.7 0.65 reu 0.6 sea m −F 0.55 0.5
In this paper we have presented the application of the M1 statistical model to the bilingual TC and the crosslingual IR and plagiarism tasks. The M1 translation model has been widely employed in statistical machine translation but still unexplored in many other crosslingual NLP tasks.
The aim of the presented approach is to directly capture word correlation across languages, in contrast to current approaches that ignore or do not take full advantage of multilinguality. The experimental results obtained in different NLP tasks highlight the benefits of the M1 model and the usefulness of learning crosslingual information in multilingual applications.
As a future work, we plan to apply the M1 model for the bilingual TC task by using the challenging JRC-Acquis corpus. Moreover, the extension of the bilingual text classifier to the multilingual case is yet another appealing idea that we would like to study.
It would also be worth exploring superior IBM translation models, like the IBM model 2, that refine the M1 model by learning a crosslingual source-target position mapping. This refinement should be also analysed in other NLP tasks such as summarization, headlines generation and word sense disambiguation.
The authors would like to thank Raphael Salkie of the University of Brighton for providing access to the INTERSECT corpus. This work has been partially supported by the MCyT TIN2006-15265-C06-04, TIN2006-15694-CO2-01 and CSD2007-00018 research projects, the BUAP-701 PROMEP/103.5/05/1536 grant and the FPU fellowship AP2003-0342.