waashk/dblp huggingface dataset:
fast context-free parsing requires fast boolean matrix multiplication. valiant showed that boolean matrix multiplication (bmm) can be used for cfg parsing. we prove a dual result: cfg parsers running in time o(|g||w|3-e) on a grammar g and a string w can be used to multiply m x m boolean matrices in tmie o(m3-e/3). in the process we also provide a formal definition of parsing motivated by an informal notion due to lang. our result establishes one of the first limitations on general cfg parsing: a fast, practical cfg parser would yield a fast, practical bmm algorithm, which is not believed to exist.
learning stochastic ot grammars: a bayesian approach using data augmentation and gibbs sampling. stochastic optimality theory (boersma, 1997) is a widely-used model in linguistics that did not have a theoretically sound learning method previously. in this paper, a markov chain monte-carlo method is proposed for learning stochastic ot grammars. following a bayesian framework, the goal is finding the posterior distribution of the grammar given the relative frequencies of input-output pairs. the data augmentation algorithm allows one to simulate a joint posterior distribution by iterating two conditional sampling steps. this gibbs sampler constructs a markov chain that converges to the joint distribution, and the target posterior can be derived as its marginal distribution.
parsing with treebank grammars: empirical bounds, theoretical models, and the structure of the penn treebank. this paper presents empirical studies and closely corresponding theoretical models of the performance of a chart parser exhaustively parsing the penn treebank with the treebank's own cfg grammar. we show how performance is dramatically affected by rule representation and tree transformations, but little by top-down vs. bottom-up strategies. we discuss grammatical saturation, including analysis of the strongly connected components of the phrasal nonterminals in the treebank, and model how, as sentence length increases, the effective grammar rule size increases as regions of the grammar are unlocked, yielding super-cubic observed time behavior in some configurations.
measures of distributional similarity. we study distributional similarity measures for the purpose of improving probability estimation for unseen cooccurrences. our contributions are three-fold: an empirical comparison of a broad range of measures; a classification of similarity functions based on the information that they incorporate; and the introduction of a novel function that is superior at evaluating potential proxy distributions.
the role of information retrieval in answering complex questions. this paper explores the role of information retrieval in answering "relationship" questions, a new class complex information needs formally introduced in trec 2005. since information retrieval is often an integral component of many question answering strategies, it is important to understand the impact of different term-based techniques. within a framework of sentence retrieval, we examine three factors that contribute to question answering performance: the use of different retrieval engines, relevance (both at the document and sentence level), and redundancy. results point out the limitations of purely term-based methods to this challenging task. nevertheless, ir-based techniques provide a strong baseline on top of which more sophisticated language processing techniques can be deployed.
a generative constituent-context model for improved grammar induction. we present a generative distributional model for the unsupervised induction of natural language syntax which explicitly models constituent yields and contexts. parameter search with em produces higher quality analyses than previously exhibited by unsupervised systems, giving the best published un-supervised parsing results on the atis corpus. experiments on penn treebank sentences of comparable length show an even higher f1 of 71% on non-trivial brackets. we compare distributionally induced and actual part-of-speech tags as input data, and examine extensions to the basic model. we discuss errors made by the system, compare the system to previous models, and discuss upper bounds, lower bounds, and stability for this task.
accurate unlexicalized parsing. we demonstrate that an unlexicalized pcfg can parse much more accurately than previously shown, by making use of simple, linguistically motivated state splits, which break down false independence assumptions latent in a vanilla treebank grammar. indeed, its performance of 86.36% (lp/lr f1) is better than that of early lexicalized pcfg models, and surprisingly close to the current state-of-the-art. this result has potential uses beyond establishing a strong lower bound on the maximum possible accuracy of unlexicalized models: an unlexicalized pcfg is much more compact, easier to replicate, and easier to interpret than more complex lexical models, and the parsing algorithms are simpler, more widely understood, of lower asymptotic complexity, and easier to optimize.
automatic acquisition of language model based on head-dependent relation between words. language modeling is to associate a sequence of words with a priori probability, which is a key part of many natural language applications such as speech recognition and statistical machine translation. in this paper, we present a language modeling based on a kind of simple dependency grammar. the grammar consists of head-dependent relations between words and can be learned automatically from a raw corpus using the reestimation algorithm which is also introduced in this paper. our experiments show that the proposed model performs better than n-gram models at 11% to 11.5% reductions in test corpus entropy.
corpus-based induction of syntactic structure: models of dependency and constituency. we present a generative model for the unsupervised learning of dependency structures. we also describe the multiplicative combination of this dependency model with a model of linear constituency. the product model outperforms both components on their respective evaluation metrics, giving the best published figures for unsupervised dependency parsing and unsupervised constituency parsing. we also demonstrate that the combined model works and is robust cross-linguistically, being able to exploit either attachment or distributional regularities that are salient in the data.
weakly supervised named entity transliteration and discovery from multilingual comparable corpora. named entity recognition (ner) is an important part of many natural language processing tasks. current approaches often employ machine learning techniques and require supervised data. however, many languages lack such resources. this paper presents an (almost) unsupervised learning algorithm for automatic discovery of named entities (nes) in a resource free language, given a bilingual corpora in which it is weakly temporally aligned with a resource rich language. nes have similar time distributions across such corpora, and often some of the tokens in a multi-word ne are transliterated. we develop an algorithm that exploits both observations iteratively. the algorithm makes use of a new, frequency based, metric for time distributions and a resource free discriminative approach to transliteration. seeded with a small number of transliteration pairs, our algorithm discovers multi-word nes, and takes advantage of a dictionary (if one exists) to account for translated or partially translated nes. we evaluate the algorithm on an english-russian corpus, and show high level of nes discovery in russian.
language model based arabic word segmentation. we approximate arabic's rich morphology by a model that a word consists of a sequence of morphemes in the pattern prefix*-stem-suffix* (* denotes zero or more occurrences of a morpheme). our method is seeded by a small manually segmented arabic corpus and uses it to bootstrap an unsupervised algorithm to build the arabic word segmenter from a large unsegmented arabic corpus. the algorithm uses a trigram language model to determine the most probable morpheme sequence for a given input. the language model is initially estimated from a small manually segmented corpus of about 110,000 words. to improve the segmentation accuracy, we use an unsupervised algorithm for automatically acquiring new stems from a 155 million word unsegmented corpus, and re-estimate the model parameters with the expanded vocabulary and training corpus. the resulting arabic word segmentation system achieves around 97% exact match accuracy on a test corpus containing 28,449 word tokens. we believe this is a state-of-the-art performance and the algorithm can be used for many highly inflected languages provided that one can create a small manually segmented corpus of the language of interest.
machine transliteration. it is challenging to translate names and technical terms across languages with different alphabets and sound inventories. these items are commonly trnasliterated, i.e., replaced with approximate phonetic equivalents. for example, "computer" in english comes out as "konpyuutaa" in japanese. translating such items from japanese back to english is even more challenging, and of practical interest, as transliterated items make up the bulk of text phrases not found in bilingual dictionaries. we describe and evaluate a method for performing backwards transliterations by machine. this method uses a generative model, incorporating several distinct stages in the transliteration process.
a syllable based word recognition model for korean noun extraction. noun extraction is very important for many nlp applications such as information retrieval, automatic text classification, and information extraction. most of the previous korean noun extraction systems use a morphological analyzer or a part-of-speech (pos) tagger. therefore, they require much of the linguistic knowledge such as morpheme dictionaries and rules (e.g. morphosyntactic rules and morphological rules).this paper proposes a new noun extraction method that uses the syllable based word recognition model. it finds the most probable syllable-tag sequence of the input sentence by using automatically acquired statistical information from the pos tagged corpus and extracts nouns by detecting word boundaries. furthermore, it does not require any labor for constructing and maintaining linguistic knowledge. we have performed various experiments with a wide range of variables influencing the performance. the experimental results show that without morphological analysis or pos tagging, the proposed method achieves comparable performance with the previous methods.
two-level, many-path generation. large-scale natural language generation requires the integration of vast amounts of knowledge: lexical, grammatical, and conceptual. a robust generator must be able to operate well even when pieces of knowledge are missing. it must also be robust against incomplete or inaccurate inputs. to attack these problems, we have built a hybrid generator, in which gaps in symbolic knowledge are filled by statistical methods. we describe algorithms and show experimental results. we also discuss how the hybrid generation model can be used to simplify current generators and enhance their portability, even when perfect knowledge is in principle obtainable.
part-of-speech tagging based on hidden markov model assuming joint independence. in this paper we present part-of-speech taggers based on hidden markov models, which adopt a less strict markov assumption to consider rich contexts. in models whose parameters are very specific like lexicalized ones, sparse-data problem is very serious and also conditional probabilities tend to be estimated unreliably. to overcome data-sparseness, a simplified version of the well-known back-off smoothing method is used. to mitigate unreliable estimation problem, our models assume joint independence instead of conditional independence because joint probabilities have the same degree of estimation reliability. in experiments for the brown corpus, models with rich contexts achieve relatively high accuracy and some models assuming joint independence show better results than the corresponding hmms.
unsupervised analysis for decipherment problems. we study a number of natural language decipherment problems using unsupervised learning. these include letter substitution ciphers, character code conversion, phonetic decipherment, and word-based ciphers with relevance to machine translation. straightforward unsupervised learning techniques most often fail on the first try, so we describe techniques for understanding errors and significantly increasing performance.
an expert lexicon approach to identifying english phrasal verbs. phrasal verbs are an important feature of the english language. properly identifying them provides the basis for an english parser to decode the related structures. phrasal verbs have been a challenge to natural language processing (nlp) because they sit at the borderline between lexicon and syntax. traditional nlp frameworks that separate the lexicon module from the parser make it difficult to handle this problem properly. this paper presents a finite state approach that integrates a phrasal verb expert lexicon between shallow parsing and deep parsing to handle morpho-syntactic interaction. with precision/recall combined performance benchmarked consistently at 95.8%-97.5%, the phrasal verb identification problem has basically been solved with the presented method.
hidden markov model-based korean part-of-speech tagging considering high agglutinativity, word-spacing, and lexical correlativity. in this paper we present hidden markov models for korean part-of-speech tagging, which consider korean characteristics such as high agglutinativity, word-spacing, and high lexical correlativity. in order ot consider rich information in contexts, the models adopt a less strict markov assumption. in the models, sparse-data problem is very serious and their parameters tend to be estimated unreliably because they have a large number of parameters. to overcome sparse-data problem, our model uses a simplified version of the well-known back-off smoothing method. to mitigate unreliable estimation problem, our models assume joint independence instead of conditional independence because joint probabilities have the same degree of estimation reliability. experimental results show that models with rich contexts perform even better than standard hmms and that joint independent assumption is effective in some models.
feature-rich statistical translation of noun phrases. we define noun phrase translation as a subtask of machine translation. this enables us to build a dedicated noun phrase translation subsystem that improves over the currently best general statistical machine translation methods by incorporating special modeling and special features. we achieved 65.5% translation accuracy in a german-english translation task vs. 53.2% with ibm model 4.
ambiguity resolution for machine translation of telegraphic messages. telegraphic messages with numerous instances of omission pose a new challenge to parsing in that a sentence with omission causes a higher degree of ambiguity than a sentence without omission. misparsing induced by omissions has a far-reaching consequence in machine translation. namely, a misparse of the input often leads to a translation into the target language which has incoherent meaning in the given context. this is more frequently the case if the structures of the source and target languages are quite different, as in english and korean. thus, the question of how we parse telegraphic messages accurately and efficiently becomes a critical issue in machine translation. in this paper we describe a technical solution for the issue, and present the performance evaluation of a machine translation system on telegraphic messages before and after adopting the proposed solution. the solution lies in a grammar design in which lexicalized grammar rules defined in terms of semantic categories and syntactic rules defined in terms of part-of-speech are utilized together. the proposed grammar achieves a higher parsing coverage without increasing the amount of ambiguity/misparsing when compared with a purely lexicalized semantic grammar, and achieves a lower degree of ambiguity/misparses without decreasing the parsing coverage when compared with a purely syntactic grammar.
learning semantic classes for word sense disambiguation. word sense disambiguation suffers from a long-standing problem of knowledge acquisition bottleneck. although state of the art supervised systems report good accuracies for selected words, they have not been shown to be promising in terms of scalability. in this paper, we present an approach for learning coarser and more general set of concepts from a sense tagged corpus, in order to alleviate the knowledge acquisition bottleneck. we show that these general concepts can be transformed to fine grained word senses using simple heuristics, and applying the technique for recent senseval data sets shows that our approach can yield state of the art performance.
how to cover a grammar. a novel formalism is presented for earley-like parsers. it accommodates the simulation of non-deterministic pushdown automata. in particular, the theory is applied to non-deterministic lr-parsers for rtn grammars.
solving analogies on words: an algorithm. to introduce the algorithm presented in this paper, we take a path that is inverse to the historical development of the idea of analogy (see (hoffman 95)). this is necessary, because a certain incomprehension is faced when speaking about linguistic analogy, i.e., it is generally given a broader and more psychological definition. also, with our proposal being computational, it is impossible to ignore works about analogy in computer science, which has come to mean artificial intelligence.
a polynomial-time fragment of dominance constraints. dominance constraints are logical descriptions of trees that are widely used in computational linguistics. their general satisfiability problem is known to be np-complete. here we identify the natural fragment of normal dominance constraints and show that its satisfiability problem is in deterministic polynomial time.
analysis of conjunctions in a rule-based parser. the aim of the present paper is to show how a rule-based parser for the italian language has been extended to analyze sentences involving conjunctions. the most noticeable fact is the ease with which the required modifications fit in the previous parser structure. in particular, the rules written for analyzing simple sentences (without conjunctions) needed only small changes. on the contrary, more substantial changes were made to the exception-handling rules (called "natural changes") that are used to restructure the tree in case of failure of a syntactic hypothesis. the parser described in the present work constitutes the syntactic component of the fido system (a flexible interface for database operations), an interface allowing an end-user to access a relational database in natural language (italian).
generation as dependency parsing. natural-language generation from flat semantics is an np-complete problem. this makes it necessary to develop algorithms that run with reasonable efficiency in practice despite the high worst-case complexity. we show how to convert tag generation problems into dependency parsing problems, which is useful because optimizations in recent dependency parsers based on constraint programming tackle exactly the combinatorics that make generation hard. indeed, initial experiments display promising runtimes.
the structure and process of talking about doing. people talk about what they do, often at the same time as they are doing. this reporting has an important function in coordinating action between people working together on real everyday problems. it is also an important source of data for social scientists studying people's behavior. in this paper, we report on some studies we are doing on report dialogues. we describe two kinds of phenomena we have identified, outline a preliminary process model that integrates the report generation with the processes that are generating the actions being reported upon, and specify a systematic methodology for extracting relevant evidence bearing on these phenomena from text transcripts of talk about doing to use in evaluating the model.
efficient solving and exploration of scope ambiguities. we present the currently most efficient solver for scope underspecification; it also converts between different underspecification formalisms and counts readings. our tool makes the practical use of large-scale grammars with (underspecified) semantic output more feasible, and can be used in grammar debugging.
characterizing and recognizing spoken corrections in human-computer dialogue. miscommunication in speech recognition systems is unavoidable, but a detailed characterization of user corrections will enable speech systems to identify when a correction is taking place and to more accurately recognize the content of correction utterances. in this paper we investigate the adaptations of users when they encounter recognition errors in interactions with a voice-in/voice-out spoken language system. in analyzing more than 300 pairs of original and repeat correction utterances, matched on speaker and lexical content, we found overall increases in both utterance and pause duration from original to correction. interestingly, corrections of misrecognition erros (cme) exhibited significantly heightened pitch variability, while corrections of rejection errors (cre) showed only a small but significant decrease in pitch minimum. cme's demonstrated much greater increases in measures of duration and pitch variability than cre's. these contrasts allow the development of decision trees which distinguish cme's from cre's and from original inputs at 70--75% accuracy based on duration, pitch, and amplitude features.
an improved redundancy elimination algorithm for underspecified representations. we present an efficient algorithm for the redundancy elimination problem: given an underspecified semantic representation (usr) of a scope ambiguity, compute an usr with fewer mutually equivalent readings. the algorithm operates on underspecified chart representations which are derived from dominance graphs; it can be applied to the usrs computed by large-scale grammars. we evaluate the algorithm on a corpus, and show that it reduces the degree of ambiguity significantly while taking negligible runtime.
is it harder to parse chinese, or the chinese treebank? we present a detailed investigation of the challenges posed when applying parsing models developed against english corpora to chinese. we develop a factored-model statistical parser for the penn chinese treebank, showing the implications of gross statistical differences between wsj and chinese tree-banks for the most general methods of parser adaptation. we then provide a detailed analysis of the major sources of statistical parse errors for this corpus, showing their causes and relative frequencies, and show that while some types of errors are due to difficult ambiguities inherent in chinese grammar, others arise due to treebank annotation practices. we show how each type of error can be addressed with simple, targeted changes to the independence assumptions of the maximum likelihood-estimated pcfg factor of the parsing model, which raises our f1 from 80.7% to 82.6% on our development set, and achieves parse accuracy close to the best published figures for chinese parsing.
generative power of ccgs with generalized type-raised categories. this paper shows that a class of combinatory categorial grammars (ccgs) augmented with a linguistically-motivated form of type raising involving variables is weakly equivalent to the standard ccgs not involving variables. the proof is based on the idea that any instance of such a grammar can be simulated by a standard ccg.