History Based Unsupervised Data Oriented Parsing

Proceedings of Recent Advances in Natural Language Processing, pages 453–459, Hissar, Bulgaria, 7-13 September 2013. History Based Unsupervised Data Oriented Parsing Mohsen Mesgar Department of Computer Engineering, Sharif University of technology, Tehran, Iran mmesgar@ce.sharif.ir Gholamreza Ghasem-Sani Department of Computer Engineering, Sharif University of technology, Tehran, Iran sani@sharif.edu Abstract Grammar induction is a basic step in natural language processing. Based on the volume of information that is used by different methods, we can distinguish three types of grammar in- duction method: supervised, unsupervised, and semi-supervised. Supervised and semi- supervised methods require large tree banks, which may not currently exist for many lan- guages. Accordingly, many researchers have focused on unsupervised methods. Unsuper- vised Data Oriented Parsing (UDOP) is cur- rently the state of the art in unsupervised grammar induction. In this paper, we show that the performance of UDOP in free word order languages such as Persian is inferior to that of fixed order languages such as English. We also introduce a novel approach called History-based unsupervised data oriented Parsing, and show that the performance of UDOP can be significantly improved by using some history information, especially in dealing with free word order languages. 1 Introduction Statistical methods of natural language pro- cessing have shown to be very successful in cor- pus based linguistics. One reason is that electron- ic based texts are now available more than ever (Charniak, 1997; Church, 1998). The success of statistical Part Of Speech (POS) tagger systems has caused the trend of research in lexical analy- sis, language modeling, and machine translation to be changed towards using various statistical methods (Feili and Ghassem-Sani, 2004; Charni- ak, 1996). Grammar is an essential tool in many applica- tions of natural language processing (Feili and Ghassem-Sani, 2004). Writing a natural language grammar by hand is not only a time-consuming and difficult task, but also it needs a large amount of skilled efforts. Availability of large parsed corpus such as Penn Treebank (Marcus et al., 1993) has facilitated the development of au- tomatic methods of grammar induction. Based on the level of supervision information that is used by the different grammar induction methods, they are divided in to three major groups (i.e., supervised, semi-supervised, and unsupervised). Supervised and semi-supervised methods require large treebanks, which may not exist for many languages. Therefore, many researchers have focused on unsupervised methods. Unsupervised Data Oriented Parsing (UDOP) is currently the state of the art in unsupervised grammar induc- tion. But in the case of free word order languages such as Persian, its performance is inferior to that of fixed order languages like English. In this paper, we present a novel unsupervised algorithm, named History-Based Unsupervised Data Oriented Parsing (HUDOP), and show, how to improve the performance of UDOP by using history information. In section 2, we discuss about different methods of grammar induction. In section 3, UDOP is explained. In section 4, the details of HUDOP are introduced. Section 5 presents our experi- mental results on English and Persian. Finally, we conclude the paper …

Content truncated to 500 words