Natural language understanding is a sub-field of natural language processing, which builds automated systems to understand natural language. It is such an ambitious task that it sometimes is referred to as an AI-complete problem, implying that its difficulty is equivalent to solving the central artificial intelligence problem -- making computers as intelligent as people. Despite its complexity, natural language understanding continues to be a fundamental problem in natural language processing in terms of its theoretical and empirical importance. In recent years, startling progress has been made at different levels of natural language processing tasks, which provides great opportunity for deeper natural language understanding. In this thesis, we focus on the task of semantic parsing, which maps a natural language sentence into a complete, formal meaning representation in a meaning representation language. We present two novel state-of-the-art learned syntax-based semantic parsers using statistical syntactic parsing techniques, motivated by the following two reasons. First, the syntax-based semantic parsing is theoretically well-founded in computational semantics. Second, adopting a syntax-based approach allows us to directly leverage the enormous progress made in statistical syntactic parsing. The first semantic parser, Scissor, adopts an integrated syntactic-semantic parsing approach, in which a statistical syntactic parser is augmented with semantic parameters to produce a semantically-augmented parse tree (SAPT). This integrated approach allows both syntactic and semantic information to be available during parsing time to obtain an accurate combined syntactic-semantic analysis. The performance of Scissor is further improved by using discriminative reranking for incorporating non-local features. The second semantic parser, SynSem, exploits an existing syntactic parser to produce disambiguated parse trees that drive the compositional semantic interpretation. This pipeline approach allows semantic parsing to conveniently leverage the most recent progress in statistical syntactic parsing. We report experimental results on two real applications: an interpreter for coaching instructions in robotic soccer and a natural-language database interface, showing that the improvement of Scissor and SynSem over other systems is mainly on long sentences, where the knowledge of syntax given in the form of annotated SAPTs or syntactic parses from an existing parser helps semantic composition. SynSem also significantly improves results with limited training data, and is shown to be robust to syntactic errors. / text

The process of determining the structural relationships between words in both natural and machine languages is known as parsing. Parsers are used as core components in a number of Natural Language Processing (NLP) applications such as online tutoring applications, dialogue-based systems and textual entailment systems. They have been used widely in the development of machine languages. In order to understand the way parsers work, we will investigate and describe a number of widely used parsing algorithms. These algorithms have been utilised in a range of different contexts such as dependency frameworks and phrase structure frameworks. We will investigate and describe some of the fundamental aspects of each of these frameworks, which can function in various ways including grammar-driven approaches and data-driven approaches. Grammar-driven approaches use a set of grammatical rules for determining the syntactic structures of sentences during parsing. Data-driven approaches use a set of parsed data to generate a parse model which is used for guiding the parser during the processing of new sentences. A number of state-of-the-art parsers have been developed that use such frameworks and approaches. We will briefly highlight some of these in this thesis. There are three specific important features that it is important to integrate into the development of parsers. These are efficiency, accuracy, and robustness. Efficiency is concerned with the use of as little time and computing resources as possible when processing natural language text. Accuracy involves maximising the correctness of the analyses that a parser produces. Robustness is a measure of a parser’s ability to cope with grammatically complex sentences and produce analyses of a large proportion of a set of sentences. In this thesis, we present a parser that can efficiently, accurately, and robustly parse a set of natural language sentences. Additionally, the implementation of the parser presented here allows for some trading-off between different levels of parsing performance. For example, some NLP applications may emphasise efficiency/robustness over accuracy while some other NLP systems may require a greater focus on accuracy. In dialogue-based systems, it may be preferable to produce a correct grammatical analysis of a question, rather than incorrectly analysing the grammatical structure of a question or quickly producing a grammatically incorrect answer for a question. Alternatively, it may be desirable that document translation systems translate a document into a different language quickly but less accurately, rather than slowly but highly accurately, because users may be able to correct grammatically incorrect sentences manually if necessary. The parser presented here is based on data-driven approaches but we will allow for the application of constraint rules to it in order to improve its performance.

No description available.

Proefschrift Universiteit van Amsterdam. / Met lit. opg. - Met samenvatting in het Nederlands.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1971. / Typescript. Vita. Includes bibliographical references.

Proponents of generalized phrase structure grammar (GPSG) cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. Since context-free languages (CFLs) can be parsed in time proportional to the cube of the sentence length, and GPSGs only generate CFLs, it seems plausible the GPSGs can also be parsed in cubic time. This longstanding, widely assumed GPSG "efficient parsability" result in misleading: parsing the sentences of an arbitrary GPSG is likely to be intractable, because a reduction from 3SAT proves that the universal recognition problem for the GPSGs of Gazdar (1981) is NP-hard. Crucially, the time to parse a sentence of a CFL can be the product of sentence length cubed and context-free grammar size squared, and the GPSG grammar can result in an exponentially large set of derived context-free rules. A central object in the 1981 GPSG theory, the metarule, inherently results in an intractable parsing problem, even when severely constrained. The implications for linguistics and natural language parsing are discussed.

This thesis deals with automatic syntactic analysis of natural languagetext, also known as parsing. The parsing approach is data-driven, whichmeans that parsers are constructed by means of machine learning, lookingat training data in the form of annotated natural language sentences. The syntactic framework used in the thesis is dependency-based. Robustness is one of the characteristics of the data-driven approaches investigated here.The overall aim of this thesis is to maintain robustness while increasing accuracy.The content of the thesis falls naturally into two tracks, a transformation track and a combination track. The  rst type of transformation investigatedis called pseudo-projective, because it enables strictly projective dependency parsers to recover non-projective dependency relations. Informally,a non-projective dependency tree contains crossing binary directed relations, when drawn above the sentence. Experimental results show that pseudo-projective transformations can improve accuracy significantly for a range of languages. The second type of transformation aims to facilitate the processing of specific linguistic constructions such as coordination and verb groups. Experimental results again show a positive effect on parsing accuracy for several languages, often greater than for the pseudo-projective transformations. However, the improvement of the transformations dependson the internal structure of the base parser, which is not the case for thepseudo-projective transformations. The combination track compares various approaches for combining data driven dependency parsers, again as a means of improving accuracy. As different parsers have different strengths and weaknesses, making parsers collaborate in order to  nd one single syntactic analysis may result in higher accuracy than any of the syntactic analyzers can produce by itself. The experimental results show that accuracy improves across languages, giventhat appropriate parsers are combined. The thesis ends with an attempt to combine the two tracks, showing that combining parsers with different tree transformations also increases accuracy. Moreover, this experiment indicates that high diversity among a small set of parsers is much more important than a large number of parsers with low diversity.

No description available.

The aim of my thesis is to show that some properties of rightward movement constructions (a cover term referring to sentences where an element appears to be “displaced” to the right) may be derived from syntactic principles and interface conditions within the framework of the minimalist program, and also to claim that properties which have up to now been dealt with purely in syntax receive a better account in terms of language processing. I develop a nonmovement approach to the Japanese Post-Verbal Construction (JPVC) by claiming that a postverbal phrase is adjoined to an element by External Merge, and that it is permitted as a syntactic object by a licensing condition which allows it to be construed as an argument or a modifier by interpretive rules at the interface level (SEM/LF). Many syntactic properties of the JPVC are accounted for in terms of independently motivated interface conditions and syntactic principles. I assume that the parser is a system that can make use of UG principles as well as language particular rules, and that the parser should be universal. The interaction of syntactic principles with parsing strategies makes it possible to cope with elusive problems concerning scope ambiguity as well as locality effects observed in the JPVC. This interaction may also account for the Right Roof Constraint effect displayed by the rightward movement constructions in English (i.e., Heavy "P Shift (H"PS), Extraposition from "P, and Right Dislocation). Furthermore, it predicts that languages fall into three types with respect to the possibility of the HNPS construction: (i) both subjects and objects can appear in postverbal position (e.g., Italian, Japanese, Turkish); (ii) subjects cannot do so (e.g., English); (iii) neither subjects nor objects can appear in postverbal position (e.g., Dutch, German). The claim that there is a parsing strategy relating to linear distance is supported by an experiment designed as a test for the effect of the length of intervening elements on acceptability of the JPVC, with the data obtained using Magnitude Estimation, a technique used in psychophysics to measure judgements of sensory stimuli.

Most of the recent efficient algorithms for dependency parsing work by factoring the dependency trees. In most of these approaches, the parser loses much of the contextual information during the process of factorization. There have been approaches to build higher order dependency parsers - second order, [Carreras2007] and third order [Koo and Collins2010]. In the thesis, the approach by Koo and Collins should be further exploited in one or more ways. Possible directions of further exploitation include but are not limited to: investigating possibilities of extension of the approach to non-projective parsing; integrating labeled parsing; joining word-senses during the parsing phase [Eisner2000]