waashk/dblp huggingface dataset:
directed replacement. this paper introduces to the finite-state calculus a family of directed replace operators. in contrast to the simple replace expression, upper &larr; lower, defined in karttunen (1995), the new directed version, upper @&larr; lower, yields an unambiguous transducer if the lower language consists of a single string. it transduces the input string from left to right, making only the longest possible replacement at each point.a new type of replacement expression, upper @&larr; prefix ... suffix, yields a transducer that inserts text around strings that are instances of upper. the symbol ... denotes the matching part of the input which itself remains unchanged. prefix and suffix are regular expressions describing the insertions.expressions of the type upper @&larr; prefix ... suffix may be used to compose a deterministic parser for a "local grammar" in the sense of gross (1989). other useful applications of directed replacement include tokenization and filtering of text streams.
fast methods for kernel-based text analysis. kernel-based learning (e.g., support vector machines) has been successfully applied to many hard problems in natural language processing (nlp). in nlp, although feature combinations are crucial to improving performance, they are heuristically selected. kernel methods change this situation. the merit of the kernel methods is that effective feature combination is implicitly expanded without loss of generality and increasing the computational costs. kernel-based text analysis shows an excellent performance in terms in accuracy; however, these methods are usually too slow to apply to large-scale text analysis. in this paper, we extend a basket mining algorithm to convert a kernel-based classifier into a simple and fast linear classifier. experimental results on english basenp chunking, japanese word segmentation and japanese dependency parsing show that our new classifiers are about 30 to 300 times faster than the standard kernel-based classifiers.
conditional descriptions in functional unification grammar. a grammatical description often applies to a linguistic object only when that object has certain features. such conditional descriptions can be indirectly modeled in kay's functional unification grammar (fug) using functional descriptions that are embedded within disjunctive alternatives. an extension to fug is proposed that allows for a direct representation of conditional descriptions. this extension has been used to model the input conditions on the systems of systemic grammar. conditional descriptions are formally defined in terms of logical implication and negation. this formal definition enables the use of conditional descriptions as a general notational extension to any of the unification-based grammar representation systems currently used in computational linguistics.
homonymy and polysemy in information retrieval. this paper discusses research on distinguishing word meanings in the context of information retrieval systems. we conducted experiments with three sources of evidence for making these distinctions: morphology, part-of-speech, and phrases. we have focused on the distinction between homonymy and polysemy (unrelated vs. related meanings). our results support the need to distinguish homonymy and polysemy. we found: 1) grouping morphological variants makes a significant improvement in retrieval performance, 2) that more than half of all words in a dictionary that differ in part-of-speech are related in meaning, and 3) that it is crucial to assign credit to the component words of a phrase. these experiments provide better understanding of word-based methods, and suggest where natural language processing can provide further improvements in retrieval performance.
know when to hold 'em: shuffling deterministically in a parser for nonconcatenative grammars. nonconcatenative constraints, such as the shuffle relation, are frequently employed in grammatical analyses of languages that have more flexible ordering of constituents than english. we show how it is possible to avoid searching the large space of permutations that results from a nondeterministic application of shuffle constraints. the results of our implementation demonstrate that deterministic application of shuffle constraints yields a dramatic improvement in the overall performance of a head-corner parser for german using an hpsg-style grammar.
incorporating compositional evidence in memory-based partial parsing. in this paper, a memory-based parsing method is extended for handling compositional structures. the method is oriented for learning to parse any selected subset of target syntactic structures. it is local, yet can handle also compositional structures. parts of speech as well as embedded instances are being used simultaneously. the output is a partial parse in which instances of the target structures are marked.
charting the depths of robust speech parsing. we describe a novel method for coping with ungrammatical input based on the use of chart-like data structures, which permit anytime processing. priority is given to deep syntactic analysis. should this fail, the best partial analyses are selected, according to a shortest-paths algorithm, and assembled in a robust processing phase. the method has been applied in a speech translation project with large hpsg grammars.
from chunks to function-argument structure: a similarity-based approach. chunk parsing has focused on the recognition of partial constituent structures at the level of individual chunks. little attention has been paid to the question of how such partial analyses can be combined into larger structures for complete utterances. such larger structures are not only desirable for a deeper syntactic analysis. they also constitute a necessary prerequisite for assigning function-argument structure.the present paper offers a similarity-based algorithm for assigning functional labels such as subject, object, head, complement, etc. to complete syntactic structures on the basis of prechunked input.the evaluation of the algorithm has concentrated on measuring the quality of functional labels. it was performed on a german and an english treebank using two different annotation schemes at the level of function-argument structure. the results of 89.73 % correct functional labels for german and 90.40 % for english validate the general approach.
compilation of hpsg to tag. we present an implemented compilation algorithm that translates hpsg into lexicalized feature-based tag, relating concepts of the two theories. while hpsg has a more elaborated principle-based theory of possible phrase structures, tag provides the means to represent lexicalized structures more explicitly. our objectives are met by giving clear definitions that determine the projection of structures from the lexicon, and identify "maximal" projections, auxiliary trees and foot nodes.
boosting-based parse reranking with subtree features. this paper introduces a new application of boosting for parse reranking. several parsers have been proposed that utilize the all-subtrees representation (e.g., tree kernel and data oriented parsing). this paper argues that such an all-subtrees representation is extremely redundant and a comparable accuracy can be achieved using just a small set of subtrees. we show how the boosting algorithm can be applied to the all-subtrees representation and how it selects a small and relevant feature set efficiently. two experiments on parse reranking show that our method achieves comparable or even better performance than kernel methods and also improves the testing efficiency.
using string-kernels for learning semantic parsers. we present a new approach for mapping natural language sentences to their formal meaning representations using string-kernel-based classifiers. our system learns these classifiers for every production in the formal language grammar. meaning representations for novel natural language sentences are obtained by finding the most probable semantic parse using these string classifiers. our experiments on two real-world data sets show that this approach compares favorably to other existing systems and is particularly robust to noise.
mildly non-projective dependency structures. syntactic parsing requires a fine balance between expressivity and complexity, so that naturally occurring structures can be accurately parsed without compromising efficiency. in dependency-based parsing, several constraints have been proposed that restrict the class of permissible structures, such as projectivity, planarity, multi-planarity, well-nestedness, gap degree, and edge degree. while projectivity is generally taken to be too restrictive for natural language syntax, it is not clear which of the other proposals strikes the best balance between expressivity and complexity. in this paper, we review and compare the different constraints theoretically, and provide an experimental evaluation using data from two treebanks, investigating how large a proportion of the structures found in the treebanks are permitted under different constraints. the results indicate that a combination of the well-nestedness constraint and a parametric constraint on discontinuity gives a very good fit with the linguistic data.
extraposition via complex domain formation. we propose a novel approach to extraposition in german within an alternative conception of syntax in which syntactic structure and linear order are mediated not via encodings of hierarchical relations but instead via order domains. at the heart of our proposal is a new kind of domain formation which affords analyses of extraposition constructions that are linguistically more adequate than those previously suggested in the literature.
processing optimality-theoretic syntax by interleaved chart parsing and generation. the earley deduction algorithm is extended for the processing of ot syntax based on feature grammars. due to faithfulness violations, infinitely many candidates must be compared. with the (reasonable) assumptions (i) that ot constraints are descriptions denoting bounded structures and (ii) that every rule recursion in the base grammar incurs some constraint violation, a chart algorithm can be devised. interleaving parsing and generation permits the application of generation-based optimization even in the parsing task, i.e., for a string input.
cohesion and collocation: using context vectors in text segmentation. collocational word similarity is considered a source of text cohesion that is hard to measure and quantify. the work presented here explores the use of information from a training corpus in measuring word similarity and evaluates the method in the text segmentation task. an implementation, the <b>vectile</b> system, produces similarity curves over texts using pre-compiled vector representations of the contextual behavior of words. the performance of this system is shown to improve over that of the purely string-based <b>texttiling algorithm</b> (hearst, 1997).
ot syntax - decidability of generation-based optimization. in optimality-theoretic syntax, optimization with unrestricted expressive power on the side of the ot constraints is undecidable. this paper provides a proof for the decidability of optimization based on constraints expressed with reference to local subtrees (which is in the spirit of ot theory). the proof builds on kaplan and wedekind's (2000) construction showing that lfg generation produces context-free languages.
transitivity and foregrounding in news articles: experiments in information retrieval and automatic summarising. this paper describes an on-going study which applies the concept of transitivity to news discourse for text processing tasks. the complex notion of transitivity is defined and the relatioship between transitivity and information foregrounding is explained. a sample corpus of news articles has been coded for transitivity. the corpus is being used in two text processing experiments.
compounding and derivational morphology in a finite-state setting. this paper proposes the application of finite-state approximation techniques on a unification-based grammar of word formation for a language like german. a refinement of an rtn-based approximation algorithm is proposed, which extends the state space of the automaton by selectively adding distinctions based on the parsing history at the point of entering a context-free rule. the selection of history items exploits the specific linguistic nature of word formation. as experiments show, this algorithm avoids an explosion of the size of the automaton in the approximation construction.
experiments in parallel-text based grammar induction. this paper discusses the use of statistical word alignment over multiple parallel texts for the identification of string spans that cannot be constituents in one of the languages. this information is exploited in monolingual pcfg grammar induction for that language, within an augmented version of the inside-outside algorithm. besides the aligned corpus, no other resources are required. we discuss an implemented system and present experimental results with an evaluation against the penn tree-bank.
the effect of establishing coherence in ellipsis and anaphora resolution. this paper presents a new model of anaphoric processing that utilizes the establishment of coherence relations between clauses in a discourse. we survey data that comprises a currently stalemated argument over whether vp-ellipsis is an inherently syntactic or inherently semantic phenomenon, and show that the data can be handled within a uniform discourse processing architecture. this architecture, which revises the dichotomy between ellipsis vs. model interpretive anaphora given by sag and hankamer (1984), is also able to accommodate divergent theories and data for pronominal reference resolution. the resulting architecture serves as a baseline system for modeling the role of cohesive devices in natural language.
common topics and coherent situations: interpreting ellipsis in the context of discourse inference. it is claimed that a variety of facts concerning ellipsis, event reference, and interclausal coherence can be explained by two features of the linguistic form in question: (1) whether the form leaves behind an empty constituent in the syntax, and (2) whether the form is anaphoric in the semantics. it is proposed that these features interact with one of two types of discourse inference, namely common topic inference and coherent situation inference. the differing ways in which these types of inference utilize syntactic and semantic representations predicts phenomena for which it is otherwise difficult to account.
using higher-order logic programming for semantic interpretation of coordinate constructs. many theories of semantic interpretation use &lambda;-term manipulation to compositionally compute the meaning of a sentence. these theories are usually implemented in a language such as prolog that can simulate &lambda;-term operations with first-order unification. however, for some interesting cases, such as a combinatory categorial grammar account of coordination constructs, this can only be done by obscuring the underlying linguistic theory with the "tricks" needed for implementation. this paper shows how the use of abstract syntax permitted by higher-order logic programming allows an elegant implementation of the semantics of combinatory categorial grammar, including its handling of coordination constructs.
temporal relations reference or discourse coherence? the temporal relations that hold between events described by successive utterances are often left implicit or underspecified. we address the role of two phenomena with respect to the recovery of these relations: (1) the referential properties of tense, and (2) the role of temporal constraints imposed by coherence relations. we account for several facets of the identification of temporal relations through an integration of these.
unsupervised discrimination and labeling of ambiguous names. this paper describes adaptations of unsupervised word sense discrimination techniques to the problem of name discrimination. these methods cluster the contexts containing an ambiguous name, such that each cluster refers to a unique underlying person or place. we also present new techniques to assign meaningful labels to the discovered clusters.
atn grammar modeling in applied linguistics. augmented transition network grammars have significant areas of unexplored application as a simulation tool for grammar designers. the intent of this paper is to discuss some current efforts in developing a grammar testing tool for the specialist in linguistics. the scope of the system under discussion is to display structures based on the modeled grammar. full language definition with facilitation of semantic interpretation is not within the scope of the systems described in this paper. application of grammar testing to an applied linguistics research enviroment is emphasized. extensions to the teaching of linguistics principles and to refinement of the primitive atn functions are also considered.
senseclusters: unsupervised clustering and labeling of similar contexts. senseclusters is a freely available system that identifies similar contexts in text. it relies on lexical features to build first and second order representations of contexts, which are then clustered using unsupervised methods. it was originally developed to discriminate among contexts centered around a given target word, but can now be applied more generally. it also supports methods that create descriptive and discriminating labels for the discovered clusters.
incremental generation of spatial referring expressions in situated dialog. this paper presents an approach to incrementally generating locative expressions. it addresses the issue of combinatorial explosion inherent in the construction of relational context models by: (a) contextually defining the set of objects in the context that may function as a landmark, and (b) sequencing the order in which spatial relations are considered using a cognitively motivated hierarchy of relations, and visual and discourse salience.
learning transliteration lexicons from the web. this paper presents an adaptive learning framework for phonetic similarity modeling (psm) that supports the automatic construction of transliteration lexicons. the learning algorithm starts with minimum prior knowledge about machine transliteration, and acquires knowledge iteratively from the web. we study the active learning and the unsupervised learning strategies that minimize human supervision in terms of data labeling. the learning process refines the psm and constructs a transliteration lexicon at the same time. we evaluate the proposed psm and its learning algorithm through a series of systematic experiments, which show that the proposed framework is reliably effective on two independent databases.
proximity in context: an empirically grounded computational model of proximity for processing topological spatial expressions. the paper presents a new model for context dependent interpretation of linguistic expressions about spatial proximity between objects in a natural scene. the paper discusses novel psycholinguistic experimental data that tests and verifies the model. the model has been implemented, and enables a conversational robot to identify objects in a scene through topological spatial relations (e.g. "x near y"). the model can help motivate the choice between topological and projective prepositions.
an algorithm for finding noun phrase correspondences in bilingual corpora. the paper describes an algorithm that employs english and french text taggers to associate noun phrases in an aligned bilingual corpus. the taggers provide part-of-speech categories which are used by finite-state recognizers to extract simple noun phrases for both languages. noun phrases are then mapped to each other using an iterative re-estimation algorithm that bears similarities to the baum-welch algorithm which is used for training the taggers. the algorithm provides an alternative to other approaches for finding word correspondences, with the advantage that linguistic structure is incorporated. improvements to the basic algorithm are described, which enable context to be accounted for when constructing the noun phrase mappings.
datr theories and datr models. evans and gazdar (evans and gazdar, 1989a; evans and gazdar, 1989b) introduced datr as a simple, non-monotonic language for representing natural language lexicons. although a number of implementations of datr exist, the full language has until now lacked an explicit, declarative semantics. this paper rectifies the situation by providing a mathematical semantics for datr. we present a view of datr as a language for defining certain kins of partial functions by cases. the formal model provides a transparent treatment of datr's notion of global context. it is shown that datr's default mechanism can be accounted for by interpreting value descriptors as families of values indexed by paths.
semantic analysis of japanese noun phrases - a new approach to dictionary-based understanding. this paper presents a new method of analyzing japanese noun phrases of the form <i>n</i><sub>1</sub> no n<sub>2</sub>. the japanese postposition <i>no</i> roughly corresponds to <i>of</i>, but it has much broader usage. the method exploits a definition of <i>n<sub>2</sub></i> in a dictionary. for example, <i>rugby no coach</i> can be interpreted as <i>a person who teaches technique in rugby</i>. we illustrate the effectiveness of the method by the analysis of 300 test noun phrases.
finite state transducers approximating hidden markov models. this paper describes the conversion of a hidden markov model into a sequential transducer that closely approximates the behavior of the stochastic model. this transformation is especially advantageous for part-of-speech tagging because the resulting transducer can be composed with other transducers that encode correction rules for the most frequent tagging errors. the speed of tagging is also improved. the described methods have been implemented and successfully tested on six languages.
automatic detection of text genre. as the text databases available to users become larger and more heterogeneous, genre becomes increasingly important for computational linguistics as a complement to topical and structural principles of classification. we propose a theory of genres as bundles of facets, which correlate with various surface cues, and argue that genre detection based on surface cues is as successful as detection based on deeper structural properties.
bridging the gap between dictionary and thesaurus. this paper presents an algorithm to integrate different lexical resources, through which we hope to overcome the individual inadequacy of the resources, and thus obtain some enriched lexical semantic information for applications such as word sense disambiguation. we used wordnet as a mediator between a conventional dictionary and a thesaurus. preliminary results support our hypothesised structural relationship, which enables the integration, of the resources. these results also suggest that we can combine the resources to achieve an overall balanced degree of sense discrimination.
integration of speech to computer-assisted translation using finite-state automata. state-of-the-art computer-assisted translation engines are based on a statistical prediction engine, which interactively provides completions to what a human translator types. the integration of human speech into a computer-assisted system is also a challenging area and is the aim of this paper. so far, only a few methods for integrating statistical machine translation (mt) models with automatic speech recognition (asr) models have been studied. they were mainly based on n-best rescoring approach. n-best rescoring is not an appropriate search method for building a real-time prediction engine. in this paper, we study the incorporation of mt models and asr models using finite-state automata. we also propose some transducers based on mt models for rescoring the asr word graphs.