VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY HAI-LONG TRIEU BILINGUAL SENTENCE ALIGNMENT BASED ON SENTENCE LENGTH AND WORD TRANSLATION MASTER THESIS OF INFORMATION TECHNOLOGY Hanoi - 2014 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY HAI-LONG TRIEU BILINGUAL SENTENCE ALIGNMENT BASED ON SENTENCE LENGTH AND WORD TRANSLATION Major: Computer science Code: 60 48 01 MASTER THESIS OF INFORMATION TECHNOLOGY SUPERVISOR: PhD. Phuong-Thai Nguyen Hanoi - 2014 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ORIGINALITY STATEMENT „I hereby declare that this submission is my own work and to the best of my knowledge it contains no materials previously published or written by another person, or substantial proportions of material which have been accepted for the award of any other degree or diploma at University of Engineering and Technology (UET) or any other educational institution, except where due acknowledgement is made in the thesis. I also declare that the intellectual content of this thesis is the product of my own work, except to the extent that assistance from others in the project‟s design and conception or in style, presentation and linguistic expression is acknowledged. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Acknowledgements I would like to thank my advisor, PhD Phuong-Thai Nguyen, not only for his supervision but also for his enthusiastic encouragement, right suggestion and knowledge which I have been giving during studying in Master‟s course.
I would also like to show my deep gratitude M.A Phuong-Thao Thi Nguyen from Institute of Information Technology - Vietnam Academy of Science and Technology - who provided valuable data in my evaluating process. I would like to thank PhD Van-Vinh Nguyen for examining and giving some advices to my work, M.A Kim-Anh Nguyen, M.A Truong Van Nguyen for their help along with comments on my work, especially M.A Kim-Anh Nguyen for supporting and checking some issues in my research. In addition, I would like to express my thanks to lectures, professors in Faculty of Information Technology, University of Engineering and Technology (UET), Vietnam University, Hanoi who teach me and helping me whole time I study in UET. Finally, I would like to thank my family and friends for their support, share, and confidence throughout my study.
4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract Sentence alignment plays an important role in machine translation. It is an essential task in processing parallel corpora which are ample and substantial resources for natural language processing. In order to apply these abundant materials into useful applications, parallel corpora first have to be aligned at the sentence level. This process maps sentences in texts of source language to their corresponding units in texts of target language.
Parallel corpora aligned at sentence level become a useful resource for a number of applications in natural language processing including Statistical Machine Translation, word disambiguation, cross language information retrieval. This task also helps to extract structural information and derive statistical parameters from bilingual corpora. There have been a number of algorithms proposed with different approaches for sentence alignment. However, they may be classified into some major categories.
First of all, there are methods based on the similarity of sentence lengths which can be measured by words or characters of sentences. These methods are simple but effective to apply for language pairs that have a high similarity in sentence lengths. The second set of methods is based on word correspondences or lexicon. These methods take into account the lexical information about texts, which is based on matching content in texts or uses cognates.
An external dictionary may be used in these methods, so these methods are more accurate but slower than the first ones. There are also methods based on the hybrids of these first two approaches that combine their advantages, so they obtain quite high quality of alignments. In this thesis, I summarize general issues related to sentence alignment, and I evaluate approaches proposed for this task and focus on the hybrid method, especially the proposal of Moore (2002), an effective method with high performance in term of precision. From analyzing the limits of this method, I propose an algorithm using a new feature, bilingual word clustering, to improve the quality of Moore‟s method.
The baseline method (Moore, 2002) will be introduced based on analyzing of the framework, and I describe advantages as well as weaknesses of this approach. In addition to this, I describe the basis knowledge, algorithm of bilingual word clustering, and the new feature used in sentence alignment. Finally, experiments performed in this research are illustrated as well as evaluations to prove benefits of the proposed method. Keywords: sentence alignment, parallel corpora, natural language processing, word clustering.
5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table of Contents ORIGINALITY STATEMENT. 5 Table of Contents. 6 List of Figures. 9 List of Tables.
10 CHAPTER ONE Introduction. Aligned Parallel Corpora. Types of Alignments. Objectives of the Thesis.
18 CHAPTER TWO Related Works. Overview of Approaches. 19 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Length-based Methods.
Word Correspondences Methods. Some Important Problems. Noise of Texts. Length-based Proposals.
Brown et al. Vanilla: Gale and Church, 1993. Word-based Proposals. Kay and Roscheisen, 1993.
Microsoft’s Bilingual Sentence Aligner: Moore, 2002. Hunalign: Varga et al. Deng et al. Gargantua: Braune and Fraser, 2010.
Fast-Champollion: Li et al. Bleu-align: Sennrich and Volk, 2010. MSVM and HMM: Fattah, 2012. 37 CHAPTER THREE Our Approach.
39 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Evaluation of Moore‟s Approach. 50 CHAPTER FOUR Experiments. Word Clustering Data.
Discussion of Results. 57 CHAPTER FIVE Conclusion and Future Work. Better Word Translation Models. 60 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Figures Figure 1.
A sequence of beads (Brown et al. Equation in dynamic programming (Gale and Church, 1993). A bitext space in Melamed‟s method (Melamed, 1996). The method of Varga et al.
The method of Braune and Fraser, 2010. Sentence Alignment Approaches Review. Framework of sentence alignment in our algorithm. An example of Brown's cluster algorithm.
English word clustering data. Vietnamese word clustering data. Looking up the probability of a word pair. Looking up in a word cluster.
Handling in the case: one word is contained in dictionary. Comparison in Precision. Comparison in Recall. Comparison in F-measure.
57 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Tables Table 1. Frequency of alignments (Gale and Church, 1993). Frequency of beads (Ma, 2006). Frequency of beads (Moore, 2002).
An entry in a probabilistic dictionary (Gale and Church, 1993). Topics in Training data-1. Topics in Training data-2. Input data for training clusters.
Topics for Vietnamese input data to train clusters. Word clustering data sets. 54 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHAPTER ONE Introduction 1. Background Parallel corpora play an important role in a number of tasks such as machine translation, cross language information retrieval, word disambiguation, sense disambiguation, bilingual lexicography, automatic translation verification, automatic acquisition of knowledge about translation, and cross-language information retrieval.
Building a parallel corpus, therefore, helps connecting considered languages [1, 5, 7, 12- 13, 15-16]. Parallel texts, however, are useful only when they have to be sentence-aligned. The parallel corpus first is collected from various resources, which has a very large size of the translated segments forming it. This size is usually of the order of entire documents and causes an ambiguous task in learning word correspondences.
The solution to reduce the ambiguity is first decreasing the size of the segments within each pair, which is known as sentence alignment task. This task is the work of constructing a detailed map of the correspondence between a text and its translation (a bitext map) [14]. This is the first stage for Statistical Machine Translation. With aligned sentences, we can perform further analyses such as phrase and word alignment analysis, bilingual terminology, and collocation extraction analysis as well as other applications [3, 7-9, 17].
Efficient and powerful sentence alignment algorithms, therefore, become increasingly important. A number of sentence alignment algorithms have been proposed [1, 7, 9, 12, 15, 17, 20]. Some of these algorithms are based on sentence length [3, 8, 20]; some use word correspondences [5, 11, 13-14]; some are hybrid of these two approaches [2, 6, 15, 19]. Additionally, there are also some other outstanding methods for this task [7, 17].
For details of these sentence alignment algorithms, see Sections 2. I propose an improvement to an effective hybrid algorithm [15] that is used in sentence alignment. For details of our approach, see Section 3. I also create experiments 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com to illustrate my research.
For details of the corpora used in our experiments, see Section 4. For results and discussions of experiments, see Sections 4. In the rest of this chapter, I describe some issues related to the sentence alignment task. In addition to this, I introduce objectives of the thesis and our contributions.
Finally, I describe the structure of this thesis. Definitions Parallel corpora are a collection of documents which are translations of each other [16]. Aligned parallel corpora are collections of pairs of sentences where one sentence is a translation of the other [1]. Applications Bilingual corpora are an essential resource in multilingual natural language processing systems.
This resource helps to develop data-driven natural language processing approaches. This also contributes to applying machine learning to machine translation [15-16]. Aligned Parallel Corpora Once the parallel text is sentence aligned, it provides the maximum utility [13]. Therefore, this makes the task of aligning parallel corpora of considerable interest, and a number of approaches have been proposed and developed to resolve this issue.
Definition Sentence alignment is the task of extracting pairs of sentences that are translation of one another from parallel corpora. Given a pair of texts, this process maps sentences in the text of the source language to their corresponding units in the text of the target language [3, 8, 13]. Types of Alignments Aligning sentences is to find a sequence of alignments. This section provides some more definitions about “alignment” as well as issues related to it.
Brown et al., 1991, assumed that every parallel corpus can be aligned in terms of a sequence of minimal alignment segments, which they call “beads”, in which sentences align 1-to-1, 1-to-2, 2-to-1, 1-to-0, 0-to-1. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. A sequence of beads (Brown et al. Groups of sentence lengths are circled to show the correct alignment.
Each of the groupings is called a bead, and there is a number to show sentence length of a sentence in the bead.1, “17e” means the sentence length (17 words) of an English sentence, and “19f” means the sentence length (19 words) of a French sentence. There is a sequence of beads as follows: An 𝑒𝑓-bead (one English sentence aligned with one French sentence) followed by An 𝑒𝑓𝑓-bead (one English sentence aligned with two French sentences) followed by An 𝑒-bead (one English sentence) followed by A ¶𝑒¶𝑓 bead (one English paragraph and one French paragraph). An alignment, then, is simply a sequence of beads that accounts for the observed sequences of sentence lengths and paragraph markers [3]. There are quite a number of beads, but it is possible to only consider some of them including 1-to-1 (one sentence of source language aligned with one sentence of target language), 1-to-2 (one sentence of source language aligned with two sentences of target language), etc; Brown et al., 1991 [3] mentioned to beads 1-to-1, 1-to-0, 0-to-1, 1-to-2, 2- to-1, and a bead of paragraphs ( ¶𝑒, ¶𝑓, ¶𝑒𝑓 ) because of considering alignments by paragraphs of this method.