waashk/dblp huggingface dataset:
restrictions on tree adjoining languages. several methods are known for parsing languages generated by tree adjoining grammars (tags) in o(n6) worst case running time. in this paper we investigate which restrictions on tags and tag derivations are needed in order to lower this o(n6) time complexity, without introducing large runtime constants, and without losing any of the generative power needed to capture the syntactic constructions in natural language that can be handled by unrestricted tags. in particular, we describe an algorithm for parsing a strict subcalss of tag in o(n5), and attempt to show that this subclass retains enough generative power to make it useful in the general case.
an application of automated language understanding techniques to the generation of data base elements. this paper defines a methodology for automatically analyzing textual reports of events and synthesizing event data elements from the reports for automated input to a data base. the long-term goal of the work described is to develop a support technology for specific analytical functions related to the evaluation of daily message traffic in a military environment. the approach taken leans heavily on theoretical advances in several disciplines, including linguistics, computational linguistics, artificial intelligence, and cognitive psychology. the aim is to model the cognitive activities of the human analyst as he reads and understands message text, distilling its contents into information items of interest to him, and building a conceptual model of the information conveyed by the message. this methodology, although developed on the basis of a restricted subject domain, is presumed to be general, and extensible to other domains.our approach is centered around the notion of "event", and utilizes two major knowledge sources: (1) a model of the sublanguage for event reporting which characterizes the message traffic, and (2), a model of the analyst-user's conceptualization of the world (i.e., a model of the entities and relations characteristic of his world).
minimalist parsing of subjects displaced from embedded clauses in free word order languages. in sayeed and szpakowicz (2004), we proposed a parser inspired by some aspects of the minimalist program. this incremental parser was designed specifically to handle discontinuous constituency phenomena for nps in latin. we take a look at the application of this parser to a specific kind of apparent island violation in latin involving the extraction of constituents, including subjects, from tensed embedded clauses. we make use of ideas about the left periphery from rizzi (1997) to modify our parser in order to handle apparently violated subject islands and similar phenomena.
tree-gram parsing: lexical dependencies and structural relations. this paper explores the kinds of probabilistic relations that are important in syntactic disambiguation. it proposes that two widely used kinds of relations, lexical dependencies and structural relations, have complementary disambiguation capabilities. it presents a new model based on structural relations, the tree-gram model, and reports experiments showing that structural relations should benefit from enrichment by lexical dependencies.
multi-level plurals and distributivity. we present a computational treatment of the semantics of plural noun phrases which extends an earlier approach presented by scha [7] to be able to deal with multiple-level plurals ("the boys and the girls", "the juries and the committees", etc.), we argue that the arbitrary depth to which such plural structures can be nested creates a correspondingly arbitrary ambiguity in the possibilities for the distribution of verbs over such nps. we present a recursive translation rule scheme which accounts for this ambiguity, and in particular show how it allows for the option of "partial distributivity" that collective verbs have when applied to such plural noun phrases.
polynomial time and space shift-reduce parsing of arbitrary context-free grammars. we introduce an algorithm for designing a predictive left to right shift-reduce non-determinisic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. the performance of the resulting parser is formally proven to be superior to earley's parser (1970).the technique employed consists in constructing before run-time a parsing table that encodes a non-deterministic machine in the which the predictive behavior has been compiled out. at run time, the machine is driven in pseudo-parallel with the help of a chart.the recognizer behaves in the worst case in o(|g|2n3)-time and o(|g|n2)-space. however in practice it is always superior to earley's parser since the prediction steps have been compiled before run-time.finally, we explain how other more efficient variants of the basic parser can be obtained by determinizing portions of the basic non-deterministic push-down machine while still using the same pseudo-parallel driver.
the acquisition and application of context sensitive grammar for english. a system is described for acquiring a context-sensitive, phrase structure grammar which is applied by a best-path, bottom-up, deterministic parser. the grammar was based on english news stories and a high degree of success in parsing in reported. overall, this research concludes that csg is a computationally and conceptually tractable approach to the construction of phrase structure grammar for news story text.
an earley-type parsing algorithm for tree adjoining grammars. we will describe an earley-type parser for tree adjoining grammars (tags). although a cky-type parser for tags has been developed earlier (vijay-shanker and joshi, 1985), this is the first practical parser for tags because as is well known for cfgs, the average behavior of earley-type parsers is superior to that of cky-type parsers. the core of the algorithm is described. then we discuss modifications of the parsing algorithm that can parse extensions of tags such as constraints on adjunction, substitution, and feature structures for tags. we show how with the use of substitution in tags the system is able to parse directly cfgs and tags. the system parses unification formalisms that have a cfg skeleton and also those with a tag skeleton. thus it also allows us to embed the essential aspects of patr-ii.
an alternative conception of tree-adjoining derivation. the precise formulation of derivation for tree-adjoining grammars has important ramifications for a wide variety of uses of the formalism, from syntactic analysis to semantic interpretation and statistical language modeling. we argue that the definition of tree-adjoining derivation must be reformulated in order to manifest the proper linguistic dependencies in derivations. the particular proposal is both precisely characterizable, through a compilation to linear indexed grammars, and computationally operational, by virtue of an efficient algorithm for recognition and parsing.
morphological richness offsets resource demand - experiences in constructing a pos tagger for hindi. in this paper we report our work on building a pos tagger for a morphologically rich language- hindi. the theme of the research is to vindicate the stand that- if morphology is strong and harnessable, then lack of training corpora is not debilitating. we establish a methodology of pos tagging which the resource disadvantaged (lacking annotated corpora) languages can make use of. the methodology makes use of locally annotated modestly-sized corpora (15,562 words), exhaustive morpohological analysis backed by high-coverage lexicon and a decision tree based learning algorithm (cn2). the evaluation of the system was done with 4-fold cross validation of the corpora in the news domain (www.bbc.co.uk/hindi). the current accuracy of pos tagging is 93.45% and can be further improved.
deterministic left to right parsing of tree adjoining languages. we define a set of deterministic bottom-up left to right parsers which analyze a subset of tree adjoining languages. the lr parsing strategy for context free grammars is extended to tree adjoining grammars (tags). we use a machine, called bottom-up embedded push down automation (bepda), that recognizes in a bottom-up fashion the set of tree adjoining languages (and exactly this set). each parser consists of a finite state control that drives the moves of a bottom-up embedded pushdown automaton. the parsers handle deterministically some context-sensitive tree adjoining languages. in this paper, we informally describe the bepda then given a parsing table, we explain the lr parsing algorithm. we then show how to construct an lr(0) parsing table (no lookahead). an example of a context-sensitive language recognized deterministically is given. then, we explain informally the construction of slr(1) parsing tables for bepda. we conclude with a discussion of our parsing method and current work.
acquiring core meanings of words, represented as jackendoff-style conceptual structures, from correlated streams of linguistic and non-linguistic input. this paper describes an operational system which can acquire the core meanings of words without any prior knowledge of either the category or meaning of any words it encounters. the system is given as input, a description of sequences of scenes along with sentences which describe the [events] taking place as those scenes unfold, and produces as output, a lexicon consisting of the category and meaning of each word in the input, that allows the sentences to describe the [events]. it is argued, that each of the three main components of the system, the parser, the linker and the inference component, make only linguistically and cognitively plausible assumptions about the innate knowledge needed to support tractable learning. the paper discusses the theory underlying the system, the representations and algorithms used in the implementation, the semantic constraints which support the heuristics necessary to achieve tractable learning, the limitations of the current theory and the implications of this work for language acquisition research.
lexicalized context-free grammars. lexicalized context-free grammar(lcfg) is an attractive compromise between the parsing efficiency of context-free grammar (cfg) and the elegance and lexical sensitivity of lexicalized tree adjoining grammar (ltag). lcfg is a restricted form of ltag that can only generate context-free languages and can be parsed in cubic time. however, lcfg supports much of the elegance of ltag's analysis of english and shares with ltag the ability to lexicalize cfgs without changing the trees generated.
guiding an hpsg parser using semantic and pragmatic expectations. efficient natural language generation has been successfully demonstrated using highly compiled knowledge about speech acts and their related social actions. a design and prototype implementation of a parser which utilizes this same pragmatic knowledge to efficiently guide parsing is presented. such guidance is shown to prune the search space and thus avoid needless processing of pragmatically unlikely constituent structures.
metaphor comprehension - a special mode of language processing? the paper addresses the question of whether a complete language understanding system requires special procedures in order to comprehend metaphorical language. to answer this question it is necessary to delineate the processes involved in metaphor comprehension and to determine the uniqueness of such processes in the context of existing language understanding systems.
ellipsis resolution with underspecified scope. the paper presents an approach to ellipsis resolution in a framework of scope underspecification (underspecified discourse representation theory). it is argued that the approach improves on previous proposals to integrate ellipsis resolution and scope underspecification (crouch, 1995; egg et al., 2001) in that application processes like anaphora resolution do not require full disambiguation but can work directly on the underspecified representation. furthermore it is shown that the approach presented can cope with the examples discussed by dalrymple et al. (1991) as well as a problem noted recently by erk and koller (2001).
combining deep and shallow approaches in parsing german. the paper describes two parsing schemes: a shallow approach based on machine learning and a cascaded finite-state parser with a hand-crafted grammar. it discusses several ways to combine them and presents evaluation results for the two individual approaches and their combination. an underspecification scheme for the output of the finite-state parser is introduced and shown to improve performance.
learning tense translation from bilingual corpora. this paper studies and evaluates disambiguation strategies for the translation of tense between german and english, using a bilingual corpus of appointment scheduling dialogues. it describes a scheme to detect complex verb predicates based on verb form subcategorization and grammatical knowledge. the extracted verb and tense information is presented and the role of different context factors is discussed.
from n-grams to collocations: an evaluation of xtract. in previous papers we presented methods for retrieving collocations from large samples of texts. we described a tool, xtract, that implements these methods and able to retrieve a wide range of collocations in a two stage process. these methods as well as other related methods however have some limitations. mainly, the produced collocations do not include any kind of functional information and many of them are invalid. in this paper we introduce methods that address these issues. these methods are implemented in an added third stage to xtract that examines the set of collocations retrieved during the previous two stages to both filter out a number of invalid collocations and add useful syntactic information to the retained ones. by combining parsing and statistical techniques the addition of this third stage has raised the overall precision level of xtract from 40% to 80% with a precision of 94%. in the paper we describe the methods and the evaluation experiments.
producing biographical summaries: combining linguistic knowledge with corpus statistics. we describe a biographical multi-document summarizer that summarizes information about people described in the news. the summarizer uses corpus statistics along with linguistic knowledge to select and merge descriptions of people from a document collection, removing redundant descriptions. the summarization components have been extensively evaluated for coherence, accuracy, and non-redundancy of the descriptions produced.
automatically extracting and representing collocations for language generation. collocational knowledge is necessary for language generation. the problem is that collocations come in a large variety of forms. they can involve two, three or more words, these words can be of different syntactic categories and they can be involved in more or less rigid ways. this leads to two main difficulties: collocational knowledge has to be acquired and it must be represented flexibly so that it can be used for language generation. we address both problems in this paper, focusing on the acquisition problem. we describe a program, xtract, that automatically acquires a range of collocations from large textual corpora and we describe how they can be represented in a flexible lexicon using a unification based formalism.
aspect and discourse structure: is a neutral viewpoint required? we apply smith's theory of aspect (1991) to german - a language without any aspectual markers. in particular, we try to shed more light on the effects aspect can have on discourse structure and show how english and german behave differently in this respect. we furthermore describe how smith's notion of a neutral viewpoint can be helpful for the analysis of discourse in german. it turned out that proposals claiming that the german preterite covers the progressive as well as the simple aspect can not sufficiently explain the data presented in this paper (b&auml;uerle, 1988). finally we give a situation-theoretic approach to formalize smith's intuitions following glasbey (1994) incorporating allen's interval-calculus (allen, 1984).
word expert parsing. this paper describes an approach to conceptual analysis and understanding of natural language in which linguistic knowledge centers on individual words, and the analysis mechanisms consist of interactions among distributed procedural experts representing that knowledge. each word expert models the process of diagnosing the intended usage of a particular word in context. the word expert parser performs conceptual analysis through the interactions of the individual experts, which ask questions and exchange information in converging on a single mutually acceptable sentence meaning. the word expert theory is advanced as a better cognitive model of natural language understanding than the traditional rule-based approaches. the word expert parser models parts of the theory, and the important issues of control and representation that arise in developing such a model from the basis of the technical discussion. an example from the prototype lisp implementation helps explain the theoretical results presented.
a cognitive model of coherence-driven story comprehension. current models of story comprehension have three major deficiencies: (1) lack of experimental support for the inference processes they involve (e.g. reliance on prediction); (2) indifference to 'kinds' of coherence (e.g. local and global); and (3) inability to find interpretations at variable depths. i propose that comprehension is driven by the need to find a representation that reaches a 'coherence threshold'. variable inference processes are a reflection of different thresholds, and the skepticism of an individual inference process determines how thresholds are reached.
towards finding and fixing fragments-using ml to identify non-sentential utterances and their antecedents in multi-party dialogue. non-sentential utterances (e.g., short-answers as in "who came to the party?"--- "peter.") are pervasive in dialogue. as with other forms of ellipsis, the elided material is typically present in the context (e.g., the question that a short answer answers). we present a machine learning approach to the novel task of identifying fragments and their antecedents in multiparty dialogue. we compare the performance of several learning algorithms, using a mixture of structural and lexical features, and show that the task of identifying antecedents given a fragment can be learnt successfully (f(0.5) = .76); we discuss why the task of identifying fragments is harder (f(0.5) = .41) and finally report on a combined task (f(0.5) = .38).
logarithmic opinion pools for conditional random fields. recent work on conditional random fields (crfs) has demonstrated the need for regularisation to counter the tendency of these models to overfit. the standard approach to regularising crfs involves a prior distribution over the model parameters, typically requiring search over a hyperparameter space. in this paper we address the overfitting problem from a different perspective, by factoring the crf distribution into a weighted product of individual "expert" crf distributions. we call this model a logarithmic opinion pool (lop) of crfs (lop-crfs). we apply the lop-crf to two sequencing tasks. our results show that unregularised expert crfs with an unregularised crf under a lop can outperform the unregularised crf, and attain a performance level close to the regularised crf. lop-crfs therefore provide a viable alternative to crf regularisation without the need for hyperparameter search.
trace prediction and recovery with unlexicalized pcfgs and slash features. this paper describes a parser which generates parse trees with empty elements in which traces and fillers are co-indexed. the parser is an unlexicalized pcfg parser which is guaranteed to return the most probable parse. the grammar is extracted from a version of the penn treebank which was automatically annotated with features in the style of klein and manning (2003). the annotation includes gpsg-style slash features which link traces and fillers, and other features which improve the general parsing accuracy. in an evaluation on the penn treebank (marcus et al., 1993), the parser outperformed other unlexicalized pcfg parsers in terms of labeled bracketing f-score. its results for the empty category prediction task and the trace-filler co-indexation task exceed all previously reported results with 84.1% and 77.4% f-score, respectively.
annealing techniques for unsupervised statistical language learning. exploiting unannotated natural language data is hard largely because unsupervised parameter estimation is hard. we describe deterministic annealing (rose et al., 1990) as an appealing alternative to the expectation-maximization algorithm (dempster et al., 1977). seeking to avoid search error, da begins by globally maximizing an easy concave function and maintains a local maximum as it gradually morphs the function into the desired non-concave likelihood function. applying da to parsing and tagging models is shown to be straightforward; significant improvements over em are shown on a part-of-speech tagging task. we describe a variant, skewed da, which can incorporate a good initializer when it is available, and show significant improvements over em on a grammar induction task.
parse forest computation of expected governors. in a headed tree, each terminal word can be uniquely labeled with a governing word and grammatical relation. this labeling is a summary of a syntactic analysis which eliminates detail, reflects aspects of semantics, and for some grammatical relations (such as subject of finite verb) is nearly uncontroversial. we define a notion of expected governor markup, which sums vectors indexed by governors and scaled by probabilistic tree weights. the quantity is computed in a parse forest representation of the set of tree analyses for a given sentence, using vector sums and scaling by inside probability and flow.
incremental construction of compact acyclic nfas. this paper presents and analyzes an incremental algorithm for the construction of acyclic non-deterministic finite-state automata (nfa). automata of this type are quite useful in computational linguistics, especially for storing lexicons. the proposed algorithm produces compact nfas, i.e. nfas that do not contain equivalent states. unlike deterministic finite-state automata (dfa), this property is not sufficient to ensure minimality, but still the resulting nfas are considerably smaller than the minimal dfas for the same languages.
synonymous collocation extraction using translation information. automatically acquiring synonymous collocation pairs such as <turn on, obj, light> and <switch on, obj, light> from corpora is a challenging task. for this task, we can, in general, have a large monolingual corpus and/or a very limited bilingual corpus. methods that use monolingual corpora alone or use bilingual corpora alone are apparently inadequate because of low precision or low coverage. in this paper, we propose a method that uses both these resources to get an optimal compromise of precision and coverage. this method first gets candidates of synonymous collocation pairs based on a monolingual corpus and a word thesaurus, and then selects the appropriate pairs from the candidates using their translations in a second language. the translations of the candidates are obtained with a statistical translation model which is trained with a small bilingual corpus and a large monolingual corpus. the translation information is proved as effective to select synonymous collocation pairs. experimental results indicate that the average precision and recall of our approach are 74% and 64% respectively, which outperform those methods that only use monolingual corpora and those that only use bilingual corpora.