Parsing is the task of assigning syntactic or semantic structure to a natural language sentence. This thesis focuses on syntactic parsing with Combinatory Categorial Grammar (CCG; Steedman 2000). CCG allows incremental processing, which is essential for speech recognition and some machine translation models, and it can build semantic structure in tandem with syntactic parsing. Supertagging solves a subset of the parsing task by assigning lexical types to words in a sentence using a sequence model. It has emerged as a way to improve the efficiency of full CCG parsing (Clark and Curran, 2007) by reducing the parser’s search space. This has been very successful and it is the central theme of this thesis. We begin by an analysis of how efficiency is being traded for accuracy in supertagging. Pruning the search space by supertagging is inherently approximate and to contrast this we include A* in our analysis, a classic exact search technique. Interestingly, we find that combining the two methods improves efficiency but we also demonstrate that excessive pruning by a supertagger significantly lowers the upper bound on accuracy of a CCG parser. Inspired by this analysis, we design a single integrated model with both supertagging and parsing features, rather than separating them into distinct models chained together in a pipeline. To overcome the resulting complexity, we experiment with both loopy belief propagation and dual decomposition approaches to inference, the first empirical comparison of these algorithms that we are aware of on a structured natural language processing problem. Finally, we address training the integrated model. We adopt the idea of optimising directly for a task-specific metric such as is common in other areas like statistical machine translation. We demonstrate how a novel dynamic programming algorithm enables us to optimise for F-measure, our task-specific evaluation metric, and experiment with approximations, which prove to be excellent substitutions. Each of the presented methods improves over the state-of-the-art in CCG parsing. Moreover, the improvements are additive, achieving a labelled/unlabelled dependency F-measure on CCGbank of 89.3%/94.0% with gold part-of-speech tags, and 87.2%/92.8% with automatic part-of-speech tags, the best reported results for this task to date. Our techniques are general and we expect them to apply to other parsing problems, including lexicalised tree adjoining grammar and context-free grammar parsing.

Thesis (doctoral)--Université de Paris VII, 1994. / Includes bibliographical references (p. [179]-185). Also issued in print.

Thesis (doctoral)--Université de Paris VII, 1994. / eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (p. [179]-185).

Given a natural language sentence, parsing is the task of assigning it a grammatical structure, according to the rules within a particular grammar formalism. Different grammar formalisms like Dependency Grammar, Phrase Structure Grammar, Combinatory Categorial Grammar, Tree Adjoining Grammar are explored in the literature for parsing. For example, given a sentence like “John ate an apple”, parsers based on the widely used dependency grammars find grammatical relations, such as that ‘John’ is the subject and ‘apple’ is the object of the action ‘ate’. We mainly focus on Combinatory Categorial Grammar (CCG) in this thesis. In this thesis, we present an incremental algorithm for parsing CCG for two diverse languages: English and Hindi. English is a fixed word order, SVO (Subject-Verb- Object), and morphologically simple language, whereas, Hindi, though predominantly a SOV (Subject-Object-Verb) language, is a free word order and morphologically rich language. Developing an incremental parser for Hindi is really challenging since the predicate needed to resolve dependencies comes at the end. As previously available shift-reduce CCG parsers use English CCGbank derivations which are mostly right branching and non-incremental, we design our algorithm based on the dependencies resolved rather than the derivation. Our novel algorithm builds a dependency graph in parallel to the CCG derivation which is used for revealing the unbuilt structure without backtracking. Though we use dependencies for meaning representation and CCG for parsing, our revealing technique can be applied to other meaning representations like lambda expressions and for non-CCG parsing like phrase structure parsing. Any statistical parser requires three major modules: data, parsing algorithm and learning algorithm. This thesis is broadly divided into three parts each dealing with one major module of the statistical parser. In Part I, we design a novel algorithm for converting dependency treebank to CCGbank. We create Hindi CCGbank with a decent coverage of 96% using this algorithm. We also do a cross-formalism experiment where we show that CCG supertags can improve widely used dependency parsers. We experiment with two popular dependency parsers (Malt and MST) for two diverse languages: English and Hindi. For both languages, CCG categories improve the overall accuracy of both parsers by around 0.3-0.5% in all experiments. For both parsers, we see larger improvements specifically on dependencies at which they are known to be weak: long distance dependencies for Malt, and verbal arguments for MST. The result is particularly interesting in the case of the fast greedy parser (Malt), since improving its accuracy without significantly compromising speed is relevant for large scale applications such as parsing the web. We present a novel algorithm for incremental transition-based CCG parsing for English and Hindi, in Part II. Incremental parsers have potential advantages for applications like language modeling for machine translation and speech recognition. We introduce two new actions in the shift-reduce paradigm for revealing the required information during parsing. We also analyze the impact of a beam and look-ahead for parsing. In general, using a beam and/or look-ahead gives better results than not using them. We also show that the incremental CCG parser is more useful than a non-incremental version for predicting relative sentence complexity. Given a pair of sentences from wikipedia and simple wikipedia, we build a classifier which predicts if one sentence is simpler/complex than the other. We show that features from a CCG parser in general and incremental CCG parser in particular are more useful than a chart-based phrase structure parser both in terms of speed and accuracy. In Part III, we develop the first neural network based training algorithm for parsing CCG. We also study the impact of neural network based tagging models, and greedy versus beam-search parsing, by using a structured neural network model. In greedy settings, neural network models give significantly better results than the perceptron models and are also over three times faster. Using a narrow beam, structured neural network model gives consistently better results than the basic neural network model. For English, structured neural network gives similar performance to structured perceptron parser. But for Hindi, structured perceptron is still the winner.

Made available in DSpace on 2016-04-27T16:57:34Z (GMT). No. of bitstreams: 1 Eliana Gomes de Oliveira.pdf: 5827772 bytes, checksum: 470346219a8a44a147e1c79e3e337f71 (MD5) Previous issue date: 2014-11-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Research on the teaching and learning of mathematics has shown that in what concerns problems involving the combinatory thought teachers and students commit mistakes that could have been already overcome. For this reason, this dissertation aimed at identifying the operatory invariants teachers working with students of the beginning years of schooling steadily mobilize during the analysis of situations whose content is the Combinatory. The investigation is part of a broader project developed by the research team - PEA-MAT, in the PEPG, Mathematics Education of PUC-SP, in partnership with the group DIMAT, of PUC-Peru. To develop this research the qualitative methodology and the case study were selected. Data were obtained through a questionnaire and a semi-structured interview whose objective was to find the answers for the orienting question of this study, which is: What operatory invariants teachers steadly mobilize when teaching in the beginning years of schooling and during the analysis of situations involving Combinatory? The Theory of Conceptual Fields supported the analysis of the operatory invariants. The Anthropological theory of the Didactic provided subsidies for the analysis of the didactic manuals used by the subjects of this research. Research also investigated the interviewed teachers´ knowledge on Combinatory and Combinatory Literacy. The study revealed that those teachers did not know much about what the official curriculum determined for the Combinatory knowledge. In what concerns the use of didactic manuals teachers were unanimous in agreeing that those books were an essential tool for preparing their classes, even if some of them looked for didactic materials other than books. As to the operatory invariants mobilized by those teachers, analyses demonstrated that they have few concepts on Combinatory because they mobilized the operatory invariant of enumeration of possibilities much more than the means to generalize the multiplication principle. Investigation found out that for situations involving more than two phases and having a greater number of possibilities, invariants were not valid. From those inferences there emerged the urge for a course including the discussion of both didactic and mathematical knowledge (Combinatory), procedures which will surely result in deep reflection on teaching practices / Pesquisas sobre o ensino e a aprendizagem da Matemática têm evidenciado que, em problemas envolvendo raciocínio combinatório, professores e alunos incorrem em erros que já poderiam ter sido superados. Por essa razão, este trabalho objetivou identificar quais invariantes operatórios os professores que lecionam nos anos inicias do Ensino Fundamental mobilizam de forma estável, durante a análise de situações envolvendo combinatória. A investigação se insere em um projeto maior, desenvolvido pelo grupo de pesquisa PEA-MAT, no PEPG Educação Matemática da PUC-SP, em colaboração com o grupo DIMAT, da PUC-Peru. Optou-se pela metodologia qualitativa, adotando-se o estudo de caso. Os dados foram obtidos por meio de questionário e entrevista semiestruturada que visaram a responder à questão norteadora desta pesquisa: Quais invariantes operatórios os professores que lecionam nos anos iniciais do Ensino Fundamental mobilizam de forma estável, durante a análise de situações envolvendo Combinatória? A Teoria dos Campos Conceituais fundamentou as análises dos invariantes operatórios mobilizados. A Teoria Antropológica do Didático embasou a análise dos livros didáticos utilizados pelos sujeitos dessa pesquisa. O trabalho também investigou o conhecimento dos professores-colaboradores sobre Combinatória e Letramento Combinatório. A pesquisa revelou certo desconhecimento dos professores sobre o currículo prescrito do conteúdo de Combinatória. Quanto ao uso do livro didático, os docentes foram unânimes em concordar ser ele um recurso fundamental para suas aulas, mesmo que alguns deles buscassem outras fontes. Quanto aos invariantes operatórios mobilizados pelos docentes, as análises apontaram que eles possuem conceitos restritos sobre Combinatória, porque mobilizaram mais o invariante operatório da enumeração das possibilidades, do que os meios para generalizar o princípio multiplicativo. A investigação apontou que, em situações que envolvam mais de duas etapas, e que tenham um número maior de possibilidades, esse invariante não era válido. Dessas inferências emergiu a necessidade de um curso de formação que contemple a discussão tanto de conhecimentos didáticos quanto m atemáticos (Combinatória), o que deve redundar em reflexão criteriosa sobre prática docente

Wide-coverage parsing is an area that attracts much attention in natural language processing research. This is due to the fact that it is the first step tomany other applications in natural language understanding, such as question answering. Supervised learning using human-labelled data is currently the best performing method. Therefore, there is great demand for annotated data. However, human annotation is very expensive and always, the amount of annotated data is much less than is needed to train well-performing parsers. This is the motivation behind making the best use of data available. Turkish presents a challenge both because syntactically annotated Turkish data is relatively small and Turkish is highly agglutinative, hence unusually sparse at the whole word level. METU-Sabancı Treebank is a dependency treebank of 5620 sentences with surface dependency relations and morphological analyses for words. We show that including even the crudest forms of morphological information extracted from the data boosts the performance of both generative and discriminative parsers, contrary to received opinion concerning English. We induce word-based and morpheme-based CCG grammars from Turkish dependency treebank. We use these grammars to train a state-of-the-art CCG parser that predicts long-distance dependencies in addition to the ones that other parsers are capable of predicting. We also use the correct CCG categories as simple features in a graph-based dependency parser and show that this improves the parsing results. We show that a morpheme-based CCG lexicon for Turkish is able to solve many problems such as conflicts of semantic scope, recovering long-range dependencies, and obtaining smoother statistics from the models. CCG handles linguistic phenomena i.e. local and long-range dependencies more naturally and effectively than other linguistic theories while potentially supporting semantic interpretation in parallel. Using morphological information and a morpheme-cluster based lexicon improve the performance both quantitatively and qualitatively for Turkish. We also provide an improved version of the treebank which will be released by kind permission of METU and Sabancı.

Segundo o pensamento de Mario Praz, Umberto Eco, Anatol Rosenfeld e muitos outros, as estruturas da obra de arte refletem as estruturas epistemológicas de uma época, acompanhando a evolução das formas de organização sócio-históricas e revelando uma superestrutura de pensamento subjacente a tais formas de organização. No caso de Calvino e de Lins, embora haja inúmeras e enormes diferenças conceituais e estilísticas, é muito clara a passagem de uma visão de mundo (e consequentemente uma resultante forma estética) em que o presente (anos 40-50), embora complexo, é representável como continuidade histórica, a uma nova forma mentis em que a História do presente (anos 60-70), relativizada e desrealizada pelas mudanças técnicas, científicas, culturais, sócio-epistemológicas, é percebida como mosaico de eventos e discursos e, como tal, é representável esteticamente. Percebe-se que as estruturas convencionais (contos e romances), unitárias, íntegras até meados dos anos 60, dão lugar, a partir de 1965 (Calvino) e 1966 (Lins), a uma preferência pelas formas fragmentadas, modulares, recombináveis, hipertextuais, em que os módulos podem ser manipulados pelo leitor para multiplicar as narrativas. Nessa fase da literatura combinatória surgirão obras-primas como Le città invisibili ou Pentágono de Hahn. Essa forma modular combinatória dos anos sessenta evoluirá, nos anos setenta, para uma forma mais complexa: o hiper-romance, cuja estrutura será ainda fortemente amparada na matemática e na geometria. Mas o hiper-romance, além dos elementos combinatórios articuladores da arquitetura romanesca, traz em seu cerne outros elementos fundamentais: a metanarrativa, a busca de um sentido para a representação (do amor e da morte, dos conflitos) e como representação dessa busca; a configuração narrativa do conhecimento como multiplicidade de temas e discursos; a forma da representação como multiplicidade de narrativas realizadas, realizáveis e potenciais; a busca da unidade dos fragmentos na compreensão de uma única Unidade possível: a do mosaico como resposta possível ao labirinto. / According to many authors, especially Mario Praz, Umberto Eco and Anatol Rosenfeld, the structures of a work of art reflect the epistemological structures of a certain period in time, following the evolution of socio-historical organization and revealing a superstructure of thought that comes together with such ways of organization. As far as Calvino and Lins are concerned, notwithstanding the so many conceptual and stylistic differences, their texts of fiction show very clearly the passage from a point of view (and respective esthetic form) in which the present (1940s and 1950s), though complex, can be represented as a historical continuity, to a new point of view in which the History of the present (1960s and 1970s) is understood as relative and fragmented. It is clear that conventional, uniform, whole structures such as short stories and novels, had a unified structure until the mid-sixties, but after 1965 (Calvino) and 1966 (Lins), these structures give place to a fragmented hypertext structures divided into mobile parts that the reader can manipulate and recombine in order to multiply the stories. From this period are masterpieces such as Le città invisivili and Pentágono de Hahn. This combinatory fragmented form from the sixties will evolve, in the seventies, to a more complex form: the hypernovel. The structure of the hypernovel will be strongly based on mathematics and geometry, and it also emphasizes metanarrative, the search for a sense of representation (love and death, for example) and the representation of the search itself. It also seeks to represent knowledge as multiplicity of themes and discourses, combined in fictional stories written and potentially writable. Both authors consider the structure of the novel as important as the story itself, for the structure is their search for the only possible unity: a mosaic, as a possible answer to the labyrinth.

This study investigates the problem of quantifier scope ambiguity in natural languages and the various ways with which it has been accounted for, some of which are problematic for monotonic theories of grammar like Combinatory Categorial Grammar (CCG) which strive for solutions that avoid non-monotonic functional application, and assume complete transparency between the syntax and the semantics interface of a language. Another purpose of this thesis is to explore these proposals on examples from Turkish and to try to account for the meaning differences that may be caused by word order and see how the observations from Turkish fit within the framework of CCG.

This paper presents and evaluates an algorithm to translate a dependency treebank into a Combinatory Categorial Grammar (CCG) lexicon. The dependency relations between a head and a child in a dependency tree are exploited to determine how CCG categories should be derived by making a functional distinction between adjunct and argument relations. Derivations for an English (CoNLL08 shared task treebank) and for an Italian (Turin University Treebank) dependency treebank are performed, each requiring a number of preprocessing steps. In order to determine the adequacy of the lexicons, dubbed DepEngCCG and DepItCCG, they are compared via two methods to preexisting CCG lexicons derived from similar or equivalent sources (CCGbank and TutCCG). First, a number of metrics are used to compare the state of the lexicon, including category complexity and category growth. Second, to measures the potential applicability of the lexicons in NLP tasks, the derived English CCG lexicon and CCGbank are compared in a sentiment analysis task. While the numeric measurements show promising results for the quality of the lexicons, the sentiment analysis task fails to generate a usable comparison. / text

This thesis addresses the complexities in the design of System of Systems, by providing a flexible, case independent method to analyse and rank the alternatives that are capable of performing the desired missions or operations assigned by decision makers. Although its methods involve only low-fidelity models, these proved to be the best choice as the design space created and, consequently, the number of analysis grow explosively with the increase of available options to perform the required tasks. This is due to the combinatory approach used in the generation of the design space. Another goal is to provide a demonstration of possible improvements with the addition of ontologies to the early stages of design, especially when complex solutions are expected. This also diminishes the probability of human error by decreasing the amount of work demanded when adding alternatives or changing their characteristics, displaying again the feasible application of knowledge based and automated solutions to the engineering design process. With these advantages, the flexibility of altering the set of inputs is enhanced, adding to the resilience of the framework, as it can be attached to any available compatible ontology and perform in that specific domain without hindrance. Due to the lack of techniques and the probable cost of these once made available, the evaluation of emergence is not considered in this work, and is not reccomended to be directly done once ready for use, at least not on the full result array. Moreover, the modular implementation of the framework makes the exchange of functions a rather simple task, enabling users to adapt it to their own needs. Some immediate implementations are mentioned to greatly improve the general performance and relevance of results provided.