waashk/dblp huggingface dataset:
finite-state approximation of phrase structure grammars. phrase-structure grammars are an effective representation for important syntactic and semantic aspects of natural languages, but are computationally too demanding for use as language models in real-time speech recognition. an algorithm is described that computes finite-state approximations for context-free grammars and equivalent augmented phrase-structure grammar formalisms. the approximation is exact for certain context-free grammars generating regular languages, including all left-linear and right-linear context-free grammars. the algorithm has been used to construct finite-state language models for limited-domain speech recognition tasks.
using confidence bands for parallel texts alignment. this paper describes a language independent method for alignment of parallel texts that makes use of homograph tokens for each pair of languages. in order to filter out tokens that may cause misalignment, we use confidence bands of linear regression lines instead of heuristics which are not theoretically supported. this method was originally inspired on work done by pascale fung and kathleen mckeown, and melamed, providing the statistical support those authors could not claim.
a procedure for multi-class discrimination and some linguistic applications. the paper describes a novel computational tool for multiple concept learning. unlike previous approaches, whose major goal is prediction on unseen instances rather than the legibility of the output, our mpd (maximally parsimonious discrimination) program emphasizes the conciseness and intelligibility of the resultant class descriptions, using three intuitive simplicity criteria to this end. we illustrate mpd with applications in componential analysis (in lexicology and phonology), language typology, and speech pathology.
mindnet: acquiring and structuring semantic information from text. as a lexical knowledge base constructed automatically from the definitions and example sentences in two machine-readable dictionaries (mrds), mindnet embodies several features that distinguish it from prior work with mrds. it is, however, more than this static resource alone. mindnet represents a general methodology for acquiring, structuring, accessing, and exploiting semantic information from natural language text. this paper provides an overview of the distinguishing characteristics of mindnet, the steps involved in its creation, and its extension beyond dictionary text.
lr recursive transition networks for earley and tomita parsing. efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. in fact, they are readily constructed from straightforward recursive transition networks (rtns). in this paper, we introduce lr-rtns, and then computationally motivate a uniform progression from basic lr parsing, to earley's (chart) parsing, concluding with tomita's parser. these apparently disparate algorithms are unified into a single implementation, which was used to automatically generate all the figures in this paper.
dependency treelet translation: syntactically informed phrasal smt. we describe a novel approach to statistical machine translation that combines syntactic information in the source language with recent advances in phrasal translation. this method requires a source-language dependency parser, target language word segmentation and an unsupervised word alignment component. we align a parallel corpus, project the source dependency parse onto the target sentence, extract dependency treelet translation pairs, and train a tree-based ordering model. we describe an efficient decoder and show that using these tree-based models in combination with conventional smt models provides a promising approach that incorporates the power of phrasal smt with the linguistic generality available in a parser.
from prosodic trees to syntactic trees. this paper describes an ongoing effort to parse the hebrew bible. the parser consults the bracketing information extracted from the cantillation marks of the masoetic text. we first constructed a cantillation treebank which encodes the prosodic structures of the text. it was found that many of the prosodic boundaries in the cantillation trees correspond, directly or indirectly, to the phrase boundaries of the syntactic trees we are trying to build. all the useful boundary information was then extracted to help the parser make syntactic decisions, either serving as hard constraints in rule application or used probabilistically in tree ranking. this has greatly improved the accuracy and efficiency of the parser and reduced the amount of manual work in building a hebrew treebank.
using machine learning to maintain rule-based named-entity recognition and classification systems. this paper presents a method that assists in maintaining a rule-based named-entity recognition and classification system. the underlying idea is to use a separate system, constructed with the use of machine learning, to monitor the performance of the rule-based system. the training data for the second system is generated with the use of the rule-based system, thus avoiding the need for manual tagging. the disagreement of the two systems acts as a signal for updating the rule-based system. the generality of the approach is illustrated by applying it to large corpora in two different languages: greek and french. the results are very encouraging, showing that this alternative use of machine learning can assist significantly in the maintenance of rule-based systems.
using machine learning to explore human multimodal clarification strategies. we investigate the use of machine learning in combination with feature engineering techniques to explore human multimodal clarification strategies and the use of those strategies for dialogue systems. we learn from data collected in a wizard-of-oz study where different wizards could decide whether to ask a clarification request in a multimodal manner or else use speech alone. we show that there is a uniform strategy across wizards which is based on multiple features in the context. these are generic runtime features which can be implemented in dialogue systems. our prediction models achieve a weighted f-score of 85.3% (which is a 25.5% improvement over a one-rule baseline). to assess the effects of models, feature discretisation, and selection, we also conduct a regression analysis. we then interpret and discuss the use of the learnt strategy for dialogue systems. throughout the investigation we discuss the issues arising from using small initial wizard-of-oz data sets, and we show that feature engineering is an essential step when learning from such limited data.
learning accurate, compact, and interpretable tree annotation. we present an automatic approach to tree annotation in which basic nonterminal symbols are alternately split and merged to maximize the likelihood of a training treebank. starting with a simple x-bar grammar, we learn a new grammar whose nonterminals are subsymbols of the original nonterminals. in contrast with previous work, we are able to split various terminals to different degrees, as appropriate to the actual complexity in the data. our grammars automatically learn the kinds of linguistic distinctions exhibited in previous work on manual tree annotation. on the other hand, our grammars are much more compact and substantially more accurate than previous work on automatic annotation. despite its simplicity, our best grammar achieves an f1 of 90.2% on the penn treebank, higher than fully lexicalized systems.
implications for generating clarification requests in task-oriented dialogues. clarification requests (crs) in conversation ensure and maintain mutual understanding and thus play a crucial role in robust dialogue interaction. in this paper, we describe a corpus study of crs in task-oriented dialogue and compare our findings to those reported in two prior studies. we find that cr behavior in task-oriented dialogue differs significantly from that in everyday conversation in a number of ways. moreover, the dialogue type, the modality and the channel quality all influence the decision of when to clarify and at which level of the grounding process. finally we identify form-function correlations which can inform the generation of crs.
learning correlations between linguistic indicators and semantic constraints: reuse of context-dependent decsriptions of entities. this paper presents the results of a study on the semantic constraints imposed on lexical choice by certain contextual indicators. we show how such indicators are computed and how correlations between them and the choice of a noun phrase description of a named entity can be automatically established using supervised learning. based on this correlation, we have developed a technique for automatic lexical choice of descriptions of entities in text generation. we discuss the underlying relationship between the pragmatics of choosing an appropriate description that serves a specific purpose in the automatically generated text and the semantics of the description itself. we present our work in the framework of the more general concept of reuse of linguistic structures that are automatically extracted from large corpora. we present a formal evaluation of our approach and we conclude with some thoughts on potential applications of our method.
verb semantics and lexical selection. this paper will focus on the semantic representation of verbs in computer systems and its impact on lexical selection problems in machine translation (mt). two groups of english and chinese verbs are examined to show that lexical selection must be based on interpretation of the sentences as well as selection restrictions placed on the verb arguments. a novel representation scheme is suggested, and is compared to representations with selection restrictions used in transfer-based mt. we see our approach as closely aligned with knowledge-based mt approaches (kbmt), and as a separate component that could be incorporated into existing systems. examples and experimental results will show that, using this scheme, inexact matches can achieve correct lexical selection.
an eclectic approach to building natural languages interfaces. inka is a natural language interface to facilitate knowledge acquisition during expert system development for electronic instrument trouble-shooting. the expert system design methodology develops a domain definition, called glib, in the form of a semantic grammar. this grammar format enables glib to be used with the inglish interface, which constrains users to create statements within a subset of english. incremental parsing in inglish allows immediate remedial information to be generated if a user deviates from the sublanguage. sentences are translated into production rules using the methodology of lexical-functional grammar. the system is written in smalltalk and, in inka, produces rules for a prolog inference engine.
parsing the wall street journal using a lexical-functional grammar and discriminative estimation techniques. we present a stochastic parsing system consisting of a lexical-functional grammar (lfg), a constraint-based parser and a stochastic disambiguation model. we report on the results of applying this system to parsing the upenn wall street journal (wsj) treebank. the model combines full and partial parsing techniques to reach full grammar coverage on unseen data. the treebank annotations are used to provide partially labeled data for discriminative statistical estimation using exponential models. disambiguation performance is evaluated by measuring matches of predicate-argument relations on two distinct test sets. on a gold standard of manually annotated f-structures for a subset of the wsj treebank, this evaluation reaches 79% f-score. an evaluation on a gold standard of dependency relations for brown corpus data achieves 76% f-score.
factorization of language constraints in speech recognition. integration of language constraints into a large vocabulary speech recognition system often leads to prohibitive complexity. we propose to factor the constraints into two components. the first is characterized by a covering grammar which is small and easily integrated into existing speech recognizers. the recognized string is then decoded by means of an efficient language post-processor in which the full set of constraints is imposed to correct possible errors introduced by the speech recognizer.
fertility models for statistical natural language understanding. several recent efforts in statistical natural language understanding (nlu) have focused on generating clumps of english words from semantic meaning concepts (miller et al., 1995; levin and pieracini, 1995; epstein et al., 1996; epstein, 1996). this paper extends the ibm machine translation group's concept of fertility (brown et al., 1993) to the generation of clumps for natural language understanding. the basic underlying intuition is that a single concept may be expressed in english as many disjoint clump of words. we present two fertility models which attempt to capture this phenomenon. the first is a poisson model which leads to appealing computational simplicity. the second is a general nonparametric fertility model. the general model's parameters are boot-strapped from the poisson model and updated by the em algorithm. these fertility models can be used to impose clump fertility structure on top of preexisting clump generation models. here, we present results for adding fertility structure to unigram, bigram, and headword clump generation models on arpa's air travel information service (atis) domain.
reversible automata and induction of the english auxiliary system. in this paper we apply some recent work of angluin (1982) to the induction of the english auxiliary verb system. in general, the induction of finite automata is computationally intractable. however, angluin shows that restricted finite automata, the k-reversible automata, can be learned by efficient (polynomial time) algoriths. can be learned by efficient (polynomial time) algorithms. we present an explicit computer model demonstrating that the english auxiliary verb system can in fact be learned as a l-reversible automaton, and hence in a computationally feasible amount of time. the entire system can be acquired by looking at only half the possible auxiliary verb sequences, and the pattern of generalization seems compatible with what is known about human acquisition of auxiliaries. we conclude that certain linguistic subsystems may well be learnable by inductive inference methods of this kind, and suggest an extension to context-free languages.
combining unsupervised lexical knowledge methods for word sense disambiguation. this paper presents a method to combine a set of unsupervised algorithms that can accurately disambiguate word senses in a large, completely untagged corpus. although most of the techniques for word sense resolution have been presented as stand-alone, it is our belief that full-fledged lexical ambiguity resolution should combine several information sources and techniques. the set of techniques have been applied in a combined way to disambiguate the genus terms of two machine-readable dictionaries (mrd), enabling us to construct complete taxonomies for spanish and french. texted accuracy is above 80% overall and 95% for two-way ambiguous genus terms, showing that texonomy building is not limited to structured dictionaries such as ldoce.
feature logic for dotted types: a formalism for complex word meanings. in this paper we revisit pustejovsky's proposal to treat ontologically complex word meaning by so-called dotted pairs. we use a higher-order feature logic based on ohori's record &lambda;-calculus to model the semantics of words like book and library, in particular their behavior in the context of quantification and cardinality statements.
transforming syntactic graphs into semantic graphs. in this paper, we present a computational method for transforming a syntactic graph, which represents all syntactic interpretations of a sentence, into a semantic graph which filters out certain interpretations, but also incorporates any remaining ambiguities. we argue that the resulting ambiguous graph, supported by an exclusion matrix, is a useful data structure for question answering and other semantic processing. our research is based on the principle that ambiguity is an inherent aspect of natural language communication.
from information structure to intonation: a phonological interface for concept-to-speech. the paper describes an interface between generator and synthesizer of the german language concept-to-speech system viectos. it discusses phenomena in german intonation that depend on the interaction between grammatical dependencies (projection of information structure into syntax) and prosodic context (performance-related modifications to intonation patterns).phonological processing in our system comprises segmental as well as suprasegmental dimensions such as syllabification, modification of word stress positions, and a symbolic encoding of intonation. phonological phenomena often touch upon more than one of these dimensions, so that mutual accessibility of the data structures on each dimension had to be ensured.we present a linear representation of the multidimensional phonological data based on a straightforward linearization convention, which suffices to bring this conceptually multilinear data set under the scope of the well-known processing techniques for two-level morphology.
computational structure of generative phonology and its relation to language comprehension. we analyze the computational complexity of phonological models as they have developed over the past twenty years. the major results are that generation and recognition are undecidable for segmental models, and that recognition is np-hard for that portion of segmental phonology subsumed by modern autosegmental models. formal restrictions are evaluated.
finding synonyms using automatic word alignment and measures of distributional similarity. there have been many proposals to extract semantically related words using measures of distributional similarity, but these typically are not able to distinguish between synonyms and other types of semantically related words such as antonyms, (co)hyponyms and hypernyms. we present a method based on automatic word alignment of parallel corpora consisting of documents translated into multiple languages and compare our method with a monolingual syntax-based method. the approach that uses aligned multilingual data to extract synonyms shows much higher precision and recall scores for the task of synonym extraction than the monolingual syntax-based approach.
new techniques for context modeling. we introduce three new techniques for statistical language models: extension modeling, nonmonotonic contexts, and the divergence heuristic. together these techniques result in language models that have few states, even fewer parameters, and low message entropies.
speech recognition of czech-inclusion of rare words helps. large vocabulary continuous speech recognition of inflective languages, such as czech, russian or serbo-croatian, is heavily deteriorated by excessive out of vocabulary rate. in this paper, we tackle the problem of vocabulary selection, language modeling and pruning for inflective languages. we show that by explicit reduction of out of vocabulary rate we can achieve significant improvements in recognition accuracy while almost preserving the model size. reported results are on czech speech corpora.
hierarchical non-emitting markov models. we describe a simple variant of the interpolated markov model with non-emitting state transitions and prove that it is strictly more powerful than any markov model. empirical results demonstrate that the non-emitting model outperforms the interpolated model on the brown corpus and on the wall street journal under a wide range of experimental conditions. the non-emitting model is also much less prone to overtraining.
assigning a semantic scope to operations. i propose that the characteristics of the scope disambiguation process observed in the literature can be explained in terms of the way in which the model of the situation described by a sentence is built. the model construction procedure i present builds an event structure by identifying the situations associated with the operators in the sentence and their mutual dependency relations, as well as the relations between these situations and other situations in the context. the procedure takes into account lexical semantics and the result of various discourse interpretation procedures such as definite description interpretation, and does not require a complete disambiguation to take place.
markov parsing: lattice rescoring with a statistical parser. we present a generalization of an incremental statistical parsing algorithm that allows for the re-scoring of lattices of word hypotheses, for use by a speech recognizer. this approach contrasts with other lattice parsing algorithms, which either do not provide scores for strings in the lattice (i.e. they just produce parse trees) or use search techniques (e.g. a-star) to find the best paths through the lattice, without re-scoring every arc. we show that a very large efficiency gain can be had in processing 1000-best lists without reducing word accuracy when the lists are encoded in lattices instead of trees. further, this allows for processing arbitrary lattices without n-best extraction. this can lead to more interesting methods of combination with other models, both acoustic and language, through, for example, adaptation or confusion matrices.
specifying the parameters of centering theory: a corpus-based evaluation using text from application-oriented domains. the definitions of the basic concepts, rules, and constraints of centering theory involve underspecified notions such as 'previous utterance', 'realization', and 'ranking'. we attempted to find the best way of defining each such notion among those that can be annotated reliably, and using a corpus of texts in two domains of practical interest. our main result is that trying to reduce the number of utterances without a backward-looking center (cb) results in an increased number of cases in which some discourse entity, but not the cb, gets pronominalized, and viceversa.
learning to resolve bridging references. we use machine learning techniques to find the best combination of local focus and lexical distance features for identifying the anchor of mereological bridging references. we find that using first mention, utterance distance, and lexical distance computed using either google or wordnet results in an accuracy significantly higher than obtained in previous experiments.
efficient probabilistic top-down and left-corner parsing. this paper examines efficient predictive broad, coverage parsing without dynamic programming. in contrast to bottom-up methods, depth-first top-down parsing produces partial parses that are fully connected trees spanning the entire left context, from which any kind of non-local dependency or partial semantic interpretation can in principle be read. we contrast two predictive parsing approaches, top-down and left-corner parsing, and find both to be viable. in addition, we find that enhancement with non-local information not only improves parser accuracy, but also substantially improves the search efficiency.
an integrated framework for semantic and pragmatic interpretation. we report on a mechanism for semantic and pragmatic interpretation that has been designed to take advantage of the generally compositional nature of semantic analysis, without unduly constraining the order in which pragmatic decisions are made. to achieve this goal, we introduce the idea of a conditional interpretation: one that depends upon a set of assumptions about subsequent pragmatic processing. conditional interpretations are constructed compositionally according to a set of declaratively specified interpretation rules. the mechanism can handle a wide range of pragmatic phenomena and their interactions.