title: On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms

abstract: We consider the problem of learning a certain type of lexical semantic knowledge that can be expressed as a binary relation between words, such as the so-called sub-categorization of verbs (a verb-noun relation) and the compound noun phrase relation (a noun-noun relation). Specifically, we view this problem as an on-line learning problem in the sense of Littlestone's learning model in which the learner's goal is to minimize the total number of prediction mistakes. In the computational learning theory literature, Goldman, Rivest and Schapire and subsequently Goldman and Warmuth have considered the on-line learning problem for binary relations R : X * Y -> {0, 1} in which one of the domain sets X can be partitioned into a relatively small number of types, namely clusters consisting of behaviorally indistinguishable members of X. In this paper, we extend this model and suppose that both of the sets X, Y can be partitioned into a small number of types, and propose a host of prediction algorithms which are two-dimensional extensions of Goldman and Warmuth's weighted majority type algorithm proposed for the original model. We apply these algorithms to the learning problem for the `compound noun phrase' relation, in which a noun is related to another just in case they can form a noun phrase together. Our experimental results show that all of our algorithms out-perform Goldman and Warmuth's algorithm. We also theoretically analyze the performance of one of our algorithms, in the form of an upper bound on the worst case number of prediction mistakes it makes.


title: Generalizing Case Frames Using a Thesaurus and the MDL Principle

abstract: We address the problem of automatically acquiring case-frame patterns from large corpus data. In particular, we view this problem as the problem of estimating a (conditional) distribution over a partition of words, and propose a new generalization method based on the MDL (Minimum Description Length) principle. In order to assist with the efficiency, our method makes use of an existing thesaurus and restricts its attention on those partitions that are present as `cuts' in the thesaurus tree, thus reducing the generalization problem to that of estimating the `tree cut models' of the thesaurus. We then give an efficient algorithm which provably obtains the optimal tree cut model for the given frequency data, in the sense of MDL. We have used the case-frame patterns obtained using our method to resolve pp-attachment ambiguity.Our experimental results indicate that our method improves upon or is at least as effective as existing methods.


title: A Grammar Formalism and Cross-Serial Dependencies

abstract: First we define a unification grammar formalism called the Tree Homomorphic Feature Structure Grammar. It is based on Lexical Functional Grammar (LFG), but has a strong restriction on the syntax of the equations. We then show that this grammar formalism defines a full abstract family of languages, and that it is capable of describing cross-serial dependencies of the type found in Swiss German.


title: Indexed Languages and Unification Grammars

abstract: Indexed languages are interesting in computational linguistics because they are the least class of languages in the Chomsky hierarchy that has not been shown not to be adequate to describe the string set of natural language sentences. We here define a class of unification grammars that exactly describe the class of indexed languages.


title: Co-Indexing Labelled DRSs to Represent and Reason with Ambiguities

abstract: The paper addresses the problem of representing ambiguities in a way that allows for monotonic disambiguation and for direct deductive computation. The paper focuses on an extension of the formalism of underspecified DRSs to ambiguities introduced by plural NPs. It deals with the collective/distributive distinction, and also with generic and cumulative readings. In addition it provides a systematic account for an underspecified treatment of plural pronoun resolution.


title: Bridging as Coercive Accommodation

abstract: In this paper we discuss the notion of "bridging" in Discourse Representation Theory as a tool to account for discourse referents that have only been established implicitly, through the lexical semantics of other referents. In doing so, we use ideas from Generative Lexicon theory, to introduce antecedents for anaphoric expressions that cannot be "linked" to a proper antecedent, but that do not need to be "accommodated" because they have some connection to the network of discourse referents that is already established.


title: A Compositional Treatment of Polysemous Arguments in Categorial Grammar

abstract: We discuss an extension of the standard logical rules (functional application and abstraction) in Categorial Grammar (CG), in order to deal with some specific cases of polysemy. We borrow from Generative Lexicon theory which proposes the mechanism of {\em coercion}, next to a rich nominal lexical semantic structure called {\em qualia structure}. In a previous paper we introduced coercion into the framework of {\em sign-based} Categorial Grammar and investigated its impact on traditional Fregean compositionality. In this paper we will elaborate on this idea, mostly working towards the introduction of a new semantic dimension. Where in current versions of sign-based Categorial Grammar only two representations are derived: a prosodic one (form) and a logical one (modelling), here we introduce also a more detaled representation of the lexical semantics. This extra knowledge will serve to account for linguistic phenomena like {\em metonymy\/}.


title: A Robust Parsing Algorithm For Link Grammars

abstract: In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by making three dynamic programming passes. In the first pass, the input is parsed using the original algorithm which enforces the constraints on links to ensure grammaticality. In the second pass, the total cost of each substring of words is computed, where cost is determined by the number of null links necessary to parse the substring. The final pass counts the total number of parses with minimal cost. All of the original pruning techniques have natural counterparts in the robust algorithm. When used together with memoization, these techniques enable the algorithm to run efficiently with cubic worst-case complexity. We have implemented these ideas and tested them by parsing the Switchboard corpus of conversational English. This corpus is comprised of approximately three million words of text, corresponding to more than 150 hours of transcribed speech collected from telephone conversations restricted to 70 different topics. Although only a small fraction of the sentences in this corpus are "grammatical" by standard criteria, the robust link grammar parser is able to extract relevant structure for a large portion of the sentences. We present the results of our experiments using this system, including the analyses of selected and random sentences from the corpus.


title: Parsing English with a Link Grammar

abstract: We develop a formal grammatical system called a link grammar, show how English grammar can be encoded in such a system, and give algorithms for efficiently parsing with a link grammar. Although the expressive power of link grammars is equivalent to that of context free grammars, encoding natural language grammars appears to be much easier with the new system. We have written a program for general link parsing and written a link grammar for the English language. The performance of this preliminary system -- both in the breadth of English phenomena that it captures and in the computational resources used -- indicates that the approach may have practical uses as well as linguistic significance. Our program is written in C and may be obtained through the internet.


title: A Matching Technique in Example-Based Machine Translation

abstract: This paper addresses an important problem in Example-Based Machine Translation (EBMT), namely how to measure similarity between a sentence fragment and a set of stored examples. A new method is proposed that measures similarity according to both surface structure and content. A second contribution is the use of clustering to make retrieval of the best matching example from the database more efficient. Results on a large number of test cases from the CELEX database are presented.


title: Bi-Lexical Rules for Multi-Lexeme Translation in Lexicalist MT

abstract: The paper presents a prototype lexicalist Machine Translation system (based on the so-called `Shake-and-Bake' approach of Whitelock (1992) consisting of an analysis component, a dynamic bilingual lexicon, and a generation component, and shows how it is applied to a range of MT problems. Multi-Lexeme translations are handled through bi-lexical rules which map bilingual lexical signs into new bilingual lexical signs. It is argued that much translation can be handled by equating translationally equivalent lists of lexical signs, either directly in the bilingual lexicon, or by deriving them through bi-lexical rules. Lexical semantic information organized as Qualia structures (Pustejovsky 1991) is used as a mechanism for restricting the domain of the rules.


title: A Dynamic Approach to Rhythm in Language: Toward a Temporal Phonology

abstract: It is proposed that the theory of dynamical systems offers appropriate tools to model many phonological aspects of both speech production and perception. A dynamic account of speech rhythm is shown to be useful for description of both Japanese mora timing and English timing in a phrase repetition task. This orientation contrasts fundamentally with the more familiar symbolic approach to phonology, in which time is modeled only with sequentially arrayed symbols. It is proposed that an adaptive oscillator offers a useful model for perceptual entrainment (or `locking in') to the temporal patterns of speech production. This helps to explain why speech is often perceived to be more regular than experimental measurements seem to justify. Because dynamic models deal with real time, they also help us understand how languages can differ in their temporal detail---contributing to foreign accents, for example. The fact that languages differ greatly in their temporal detail suggests that these effects are not mere motor universals, but that dynamical models are intrinsic components of the phonological characterization of language.


title: On Constraint-Based Lambek Calculi

abstract: We explore the consequences of layering a Lambek proof system over an arbitrary (constraint) logic. A simple model-theoretic semantics for our hybrid language is provided for which a particularly simple combination of Lambek's and the proof system of the base logic is complete. Furthermore the proof system for the underlying base logic can be assumed to be a black box. The essential reasoning needed to be performed by the black box is that of {\em entailment checking}. Assuming feature logic as the base logic entailment checking amounts to a {\em subsumption} test which is a well-known quasi-linear time decidable problem.


title: A Labelled Analytic Theorem Proving Environment for Categorial Grammar

abstract: We present a system for the investigation of computational properties of categorial grammar parsing based on a labelled analytic tableaux theorem prover. This proof method allows us to take a modular approach, in which the basic grammar can be kept constant, while a range of categorial calculi can be captured by assigning different properties to the labelling algebra. The theorem proving strategy is particularly well suited to the treatment of categorial grammar, because it allows us to distribute the computational cost between the algorithm which deals with the grammatical types and the algebraic checker which constrains the derivation.


title: Heuristics and Parse Ranking

abstract: There are currently two philosophies for building grammars and parsers -- Statistically induced grammars and Wide-coverage grammars. One way to combine the strengths of both approaches is to have a wide-coverage grammar with a heuristic component which is domain independent but whose contribution is tuned to particular domains. In this paper, we discuss a three-stage approach to disambiguation in the context of a lexicalized grammar, using a variety of domain independent heuristic techniques. We present a training algorithm which uses hand-bracketed treebank parses to set the weights of these heuristics. We compare the performance of our grammar against the performance of the IBM statistical grammar, using both untrained and trained weights for the heuristics.


title: The Use of Knowledge Preconditions in Language Processing

abstract: If an agent does not possess the knowledge needed to perform an action, it may privately plan to obtain the required information on its own, or it may involve another agent in the planning process by engaging it in a dialogue. In this paper, we show how the requirements of knowledge preconditions can be used to account for information-seeking subdialogues in discourse. We first present an axiomatization of knowledge preconditions for the SharedPlan model of collaborative activity (Grosz & Kraus, 1993), and then provide an analysis of information-seeking subdialogues within a general framework for discourse processing. In this framework, SharedPlans and relationships among them are used to model the intentional component of Grosz and Sidner's (1986) theory of discourse structure.


title: A Natural Law of Succession

abstract: Consider the problem of multinomial estimation. You are given an alphabet of k distinct symbols and are told that the i-th symbol occurred exactly n_i times in the past. On the basis of this information alone, you must now estimate the conditional probability that the next symbol will be i. In this report, we present a new solution to this fundamental problem in statistics and demonstrate that our solution outperforms standard approaches, both in theory and in practice.


title: How much is enough?: Data requirements for statistical NLP

abstract: In this paper I explore a number of issues in the analysis of data requirements for statistical NLP systems. A preliminary framework for viewing such systems is proposed and a sample of existing works are compared within this framework. The first steps toward a theory of data requirements are made by establishing some results relevant to bounding the expected error rate of a class of simplified statistical language learners as a function of the volume of training data.


title: Conserving Fuel in Statistical Language Learning: Predicting Data Requirements

abstract: In this paper I address the practical concern of predicting how much training data is sufficient for a statistical language learning system. First, I briefly review earlier results and show how these can be combined to bound the expected accuracy of a mode-based learner as a function of the volume of training data. I then develop a more accurate estimate of the expected accuracy function under the assumption that inputs are uniformly distributed. Since this estimate is expensive to compute, I also give a close but cheaply computable approximation to it. Finally, I report on a series of simulations exploring the effects of inputs that are not uniformly distributed. Although these results are based on simplistic assumptions, they are a tentative step toward a useful theory of data requirements for SLL systems.


title: Cluster Expansions and Iterative Scaling for Maximum Entropy Language Models

abstract: The maximum entropy method has recently been successfully introduced to a variety of natural language applications. In each of these applications, however, the power of the maximum entropy method is achieved at the cost of a considerable increase in computational requirements. In this paper we present a technique, closely related to the classical cluster expansion from statistical mechanics, for reducing the computational demands necessary to calculate conditional maximum entropy language models.


title: The Development and Migration of Concepts from Donor to Borrower Disciplines: Sublanguage Term Use in Hard & Soft Sciences

abstract: Academic disciplines, often divided into hard and soft sciences, may be understood as "donor disciplines" if they produce more concepts than they borrow from other disciplines, or "borrower disciplines" if they import more than they originate. Terms used to describe these concepts can be used to distinguish between hard and soft, donor and borrower, as well as individual discipline-specific sublanguages. Using term frequencies, the birth, growth, death, and migration of concepts and their associated terms are examined.


title: ParseTalk about Textual Ellipsis

abstract: A hybrid methodology for the resolution of text-level ellipsis is presented in this paper. It incorporates conceptual proximity criteria applied to ontologically well-engineered domain knowledge bases and an approach to centering based on functional topic/comment patterns. We state text grammatical predicates for ellipsis and then turn to the procedural aspects of their evaluation within the framework of an actor-based implementation of a lexically distributed parser.


title: POS Tagging Using Relaxation Labelling

abstract: Relaxation labelling is an optimization technique used in many fields to solve constraint satisfaction problems. The algorithm finds a combination of values for a set of variables such that satisfies -to the maximum possible degree- a set of given constraints. This paper describes some experiments performed applying it to POS tagging, and the results obtained. It also ponders the possibility of applying it to word sense disambiguation.


title: Using Chinese Text Processing Technique for the Processing of Sanskrit Based Indian Languages: Maximum Resource Utilization and Maximum Compatibility

abstract: Chinese text processing systems are using Double Byte Coding , while almost all existing Sanskrit Based Indian Languages have been using Single Byte coding for text processing. Through observation, Chinese Information Processing Technique has already achieved great technical development both in east and west. In contrast,Indian Languages are being processed by computer, more or less, for word processing purpose. This paper mainly emphasizes the method of processing Indian languages from a Computational Linguistic point of view. An overall design method is illustrated in this paper.This method concentrated on maximum resource utilization and compatibility: the ultimate goal is to have a Multiplatform Multilingual System. Keywords Text Procrssing, Multilingual Text Processing, Chinese Language Processing, Indian Language Processing, Character Coding.


title: A Proposal for Word Sense Disambiguation using Conceptual Distance

abstract: This paper presents a method for the resolution of lexical ambiguity and its automatic evaluation over the Brown Corpus. The method relies on the use of the wide-coverage noun taxonomy of WordNet and the notion of conceptual distance among concepts, captured by a Conceptual Density formula developed for this purpose. This fully automatic method requires no hand coding of lexical entries, hand tagging of text nor any kind of training process. The results of the experiment have been automatically evaluated against SemCor, the sense-tagged version of the Brown Corpus.


title: Disambiguating bilingual nominal entries against WordNet

abstract: This paper explores the acquisition of conceptual knowledge from bilingual dictionaries (French/English, Spanish/English and English/Spanish) using a pre-existing broad coverage Lexical Knowledge Base (LKB) WordNet. Bilingual nominal entries are disambiguated agains WordNet, therefore linking the bilingual dictionaries to WordNet yielding a multilingual LKB (MLKB). The resulting MLKB has the same structure as WordNet, but some nodes are attached additionally to disambiguated vocabulary of other languages. Two different, complementary approaches are explored. In one of the approaches each entry of the dictionary is taken in turn, exploiting the information in the entry itself. The inferential capability for disambiguating the translation is given by Semantic Density over WordNet. In the other approach, the bilingual dictionary was merged with WordNet, exploiting mainly synonymy relations. Each of the approaches was used in a different dictionary. Both approaches attain high levels of precision on their own, showing that disambiguating bilingual nominal entries, and therefore linking bilingual dictionaries to WordNet is a feasible task.


title: Developing and Evaluating a Probabilistic LR Parser of Part-of-Speech and Punctuation Labels

abstract: We describe an approach to robust domain-independent syntactic parsing of unrestricted naturally-occurring (English) input. The technique involves parsing sequences of part-of-speech and punctuation labels using a unification-based grammar coupled with a probabilistic LR parser. We describe the coverage of several corpora using this grammar and report the results of a parsing experiment using probabilities derived from bracketed training data. We report the first substantial experiments to assess the contribution of punctuation to deriving an accurate syntactic analysis, by parsing identical texts both with and without naturally-occurring punctuation marks.


title: Incorporating Discourse Aspects in English -- Polish MT: Towards Robust Implementation

abstract: The main aim of translation is an accurate transfer of meaning so that the result is not only grammatically and lexically correct but also communicatively adequate. This paper stresses the need for discourse analysis the aim of which is to preserve the communicative meaning in English--Polish machine translation. Unlike English, which is a positional language with word order grammatically determined, Polish displays a strong tendency to order constituents according to their degree of salience, so that the most informationally salient elements are placed towards the end of the clause regardless of their grammatical function. The Centering Theory developed for tracking down given information units in English and the Theory of Functional Sentence Perspective predicting informativeness of subsequent constituents provide theoretical background for this work. The notion of {\em center} is extended to accommodate not only for pronominalisation and exact reiteration but also for definiteness and other center pointing constructs. Center information is additionally graded and applicable to all primary constituents in a given utterance. This information is used to order the post-transfer constituents correctly, relying on statistical regularities and some syntactic clues.


title: Automatic Identification of Support Verbs: A Step Towards a Definition of Semantic Weight

abstract: Current definitions of notions of lexical density and semantic weight are based on the division of words into closed and open classes, and on intuition. This paper develops a computationally tractable definition of semantic weight, concentrating on what it means for a word to be semantically light; the definition involves looking at the frequency of a word in particular syntactic constructions which are indicative of lightness. Verbs such as "make" and "take", when they function as support verbs, are often considered to be semantically light. To test our definition, we carried out an experiment based on that of Grefenstette and Teufel (1995), where we automatically identify light instances of these words in a corpus; this was done by incorporating our frequency-related definition of semantic weight into a statistical approach similar to that of Grefenstette and Teufel. The results show that this is a plausible definition of semantic lightness for verbs, which can possibly be extended to defining semantic lightness for other classes of words.


title: Toward an MT System without Pre-Editing --- Effects of New Methods in ALT-J/E ---

abstract: Recently, several types of Japanese-to-English machine translation systems have been developed, but all of them require an initial process of rewriting the original text into easily translatable Japanese. Therefore these systems are unsuitable for translating information that needs to be speedily disseminated. To overcome this limitation, a Multi-Level Translation Method based on the Constructive Process Theory has been proposed. This paper describes the benefits of using this method in the Japanese-to-English machine translation system ALT-J/E. In comparison with conventional compositional methods, the Multi-Level Translation Method emphasizes the importance of the meaning contained in expression structures as a whole. It is shown to be capable of translating typical written Japanese based on the meaning of the text in its context, with comparative ease. We are now hopeful of carrying out useful machine translation with no manual pre-editing.


title: Countability and Number in Japanese-to-English Machine Translation

abstract: This paper presents a heuristic method that uses information in the Japanese text along with knowledge of English countability and number stored in transfer dictionaries to determine the countability and number of English noun phrases. Incorporating this method into the machine translation system ALT-J/E, helped to raise the percentage of noun phrases generated with correct use of articles and number from 65% to 73%.


title: Letting the Cat out of the Bag: Generation for Shake-and-Bake MT

abstract: Describes an algorithm for the generation phase of a Shake-and-Bake Machine Translation system. Since the problem is NP-complete, it is unlikely that the algorithm will be efficient in all cases, but for the cases tested it offers an improvement over Whitelock's previously published algorithm. The work was carried out while the author was employed at Sharp Laboratories of Europe Ltd.


title: The Effect of Resource Limits and Task Complexity on Collaborative Planning in Dialogue

abstract: This paper shows how agents' choice in communicative action can be designed to mitigate the effect of their resource limits in the context of particular features of a collaborative planning task. I first motivate a number of hypotheses about effective language behavior based on a statistical analysis of a corpus of natural collaborative planning dialogues. These hypotheses are then tested in a dialogue testbed whose design is motivated by the corpus analysis. Experiments in the testbed examine the interaction between (1) agents' resource limits in attentional capacity and inferential capacity; (2) agents' choice in communication; and (3) features of communicative tasks that affect task difficulty such as inferential complexity, degree of belief coordination required, and tolerance for errors. The results show that good algorithms for communication must be defined relative to the agents' resource limits and the features of the task. Algorithms that are inefficient for inferentially simple, low coordination or fault-tolerant tasks are effective when tasks require coordination or complex inferences, or are fault-intolerant. The results provide an explanation for the occurrence of utterances in human dialogues that, prima facie, appear inefficient, and provide the basis for the design of effective algorithms for communicative choice for resource limited agents.


title: An investigation into the correlation of cue phrases, unfilled pauses and the structuring of spoken discourse

abstract: Expectations about the correlation of cue phrases, the duration of unfilled pauses and the structuring of spoken discourse are framed in light of Grosz and Sidner's theory of discourse and are tested for a directions-giving dialogue. The results suggest that cue phrase and discourse structuring tasks may align, and show a correlation for pause length and some of the modifications that speakers can make to discourse structure.


title: Chart-driven Connectionist Categorial Parsing of Spoken Korean

abstract: While most of the speech and natural language systems which were developed for English and other Indo-European languages neglect the morphological processing and integrate speech and natural language at the word level, for the agglutinative languages such as Korean and Japanese, the morphological processing plays a major role in the language processing since these languages have very complex morphological phenomena and relatively simple syntactic functionality. Obviously degenerated morphological processing limits the usable vocabulary size for the system and word-level dictionary results in exponential explosion in the number of dictionary entries. For the agglutinative languages, we need sub-word level integration which leaves rooms for general morphological processing. In this paper, we developed a phoneme-level integration model of speech and linguistic processings through general morphological analysis for agglutinative languages and a efficient parsing scheme for that integration. Korean is modeled lexically based on the categorial grammar formalism with unordered argument and suppressed category extensions, and chart-driven connectionist parsing method is introduced.


title: Disambiguating Noun Groupings with Respect to WordNet Senses

abstract: Word groupings useful for language processing tasks are increasingly available, as thesauri appear on-line, and as distributional word clustering techniques improve. However, for many tasks, one is interested in relationships among word {\em senses}, not words. This paper presents a method for automatic sense disambiguation of nouns appearing within sets of related nouns --- the kind of data one finds in on-line thesauri, or as the output of distributional clustering algorithms. Disambiguation is performed with respect to WordNet senses, which are fairly fine-grained; however, the method also permits the assignment of higher-level WordNet categories rather than sense labels. The method is illustrated primarily by example, though results of a more rigorous evaluation are also presented.


title: Using Information Content to Evaluate Semantic Similarity in a Taxonomy

abstract: This paper presents a new measure of semantic similarity in an IS-A taxonomy, based on the notion of information content. Experimental evaluation suggests that the measure performs encouragingly well (a correlation of r = 0.79 with a benchmark set of human similarity judgments, with an upper bound of r = 0.90 for human subjects performing the same task), and significantly better than the traditional edge counting approach (r = 0.66).


title: Analysis of the Arabic Broken Plural and Diminutive

abstract: This paper demonstrates how the challenging problem of the Arabic broken plural and diminutive can be handled under a multi-tape two-level model, an extension to two-level morphology.


title: The Unsupervised Acquisition of a Lexicon from Continuous Speech

abstract: We present an unsupervised learning algorithm that acquires a natural-language lexicon from raw speech. The algorithm is based on the optimal encoding of symbol sequences in an MDL framework, and uses a hierarchical representation of language that overcomes many of the problems that have stymied previous grammar-induction procedures. The forward mapping from symbol sequences to the speech stream is modeled using features based on articulatory gestures. We present results on the acquisition of lexicons and language models from raw speech, text, and phonetic transcripts, and demonstrate that our algorithm compares very favorably to other reported results with respect to segmentation performance and statistical efficiency.


title: Limited Attention and Discourse Structure

abstract: This squib examines the role of limited attention in a theory of discourse structure and proposes a model of attentional state that relates current hierarchical theories of discourse structure to empirical evidence about human discourse processing capabilities. First, I present examples that are not predicted by Grosz and Sidner's stack model of attentional state. Then I consider an alternative model of attentional state, the cache model, which accounts for the examples, and which makes particular processing predictions. Finally I suggest a number of ways that future research could distinguish the predictions of the cache model and the stack model.


title: Natural language processing: she needs something old and something new (maybe something borrowed and something blue, too)

abstract: Given the present state of work in natural language processing, this address argues first, that advance in both science and applications requires a revival of concern about what language is about, broadly speaking the world; and second, that an attack on the summarising task, which is made ever more important by the growth of electronic text resources and requires an understanding of the role of large-scale discourse structure in marking important text content, is a good way forward.


title: Term Encoding of Typed Feature Structures

abstract: This paper presents an approach to Prolog-style term encoding of typed feature structures. The type feature structures to be encoded are constrained by appropriateness conditions as in Carpenter's ALE system. But unlike ALE, we impose a further independently motivated closed-world assumption. This assumption allows us to apply term encoding in cases that were problematic for previous approaches. In particular, previous approaches have ruled out multiple inheritance and further specification of feature-value declarations on subtypes. In the present approach, these spececial cases can be handled as well, though with some increase in complexity. For grammars without multiple inheritance and specification of feature values, the encoding presented here reduces to that of previous approaches.


title: Automatic Inference of DATR Theories

abstract: This paper presents an approach for the automatic acquisition of linguistic knowledge from unstructured data. The acquired knowledge is represented in the lexical knowledge representation language DATR. A set of transformation rules that establish inheritance relationships and a default-inference algorithm make up the basis components of the system. Since the overall approach is not restricted to a special domain, the heuristic inference strategy uses criteria to evaluate the quality of a DATR theory, where different domains may require different criteria. The system is applied to the linguistic learning task of German noun inflection.


title: Generic rules and non-constituent coordination

abstract: We present a metagrammatical formalism, {\em generic rules}, to give a default interpretation to grammar rules. Our formalism introduces a process of {\em dynamic binding} interfacing the level of pure grammatical knowledge representation and the parsing level. We present an approach to non-constituent coordination within categorial grammars, and reformulate it as a generic rule. This reformulation is context-free parsable and reduces drastically the search space associated to the parsing task for such phenomena.


title: Report of the Study Group on Assessment and Evaluation

abstract: This is an interim report discussing possible guidelines for the assessment and evaluation of projects developing speech and language systems. It was prepared at the request of the European Commission DG XIII by an ad hoc study group, and is now being made available in the form in which it was submitted to the Commission. However, the report is not an official European Commission document, and does not reflect European Commission policy, official or otherwise. After a discussion of terminology, the report focusses on combining user-centred and technology-centred assessment, and on how meaningful comparisons can be made of a variety of systems performing different tasks for different domains. The report outlines the kind of infra-structure that might be required to support comparative assessment and evaluation of heterogenous projects, and also the results of a questionnaire concerning different approaches to evaluation.


title: Similarity between Words Computed by Spreading Activation on an English Dictionary

abstract: This paper proposes a method for measuring semantic similarity between words as a new tool for text analysis. The similarity is measured on a semantic network constructed systematically from a subset of the English dictionary, LDOCE (Longman Dictionary of Contemporary English). Spreading activation on the network can directly compute the similarity between any two words in the Longman Defining Vocabulary, and indirectly the similarity of all the other words in LDOCE. The similarity represents the strength of lexical cohesion or semantic relation, and also provides valuable information about similarity and coherence of texts.


title: Text Segmentation Based on Similarity between Words

abstract: This paper proposes a new indicator of text structure, called the lexical cohesion profile (LCP), which locates segment boundaries in a text. A text segment is a coherent scene; the words in a segment are linked together via lexical cohesion relations. LCP records mutual similarity of words in a sequence of text. The similarity of words, which represents their cohesiveness, is computed using a semantic network. Comparison with the text segments marked by a number of subjects shows that LCP closely correlates with the human judgments. LCP may provide valuable information for resolving anaphora and ellipsis.


title: Possessive Pronouns as Determiners in Japanese-to-English Machine Translation

abstract: Possessive pronouns are used as determiners in English when no equivalent would be used in a Japanese sentence with the same meaning. This paper proposes a heuristic method of generating such possessive pronouns even when there is no equivalent in the Japanese. The method uses information about the use of possessive pronouns in English treated as a lexical property of nouns, in addition to contextual information about noun phrase referentiality and the subject and main verb of the sentence that the noun phrase appears in. The proposed method has been implemented in NTT Communication Science Laboratories' Japanese-to-English machine translation system ALT-J/E. In a test set of 6,200 sentences, the proposed method increased the number of noun phrases with appropriate possessive pronouns generated, by 263 to 609, at the cost of generating 83 noun phrases with inappropriate possessive pronouns.


title: Context-Sensitive Measurement of Word Distance by Adaptive Scaling of a Semantic Space

abstract: The paper proposes a computationally feasible method for measuring context-sensitive semantic distance between words. The distance is computed by adaptive scaling of a semantic space. In the semantic space, each word in the vocabulary V is represented by a multi-dimensional vector which is obtained from an English dictionary through a principal component analysis. Given a word set C which specifies a context for measuring word distance, each dimension of the semantic space is scaled up or down according to the distribution of C in the semantic space. In the space thus transformed, distance between words in V becomes dependent on the context C. An evaluation through a word prediction task shows that the proposed measurement successfully extracts the context of a text.


title: Noun Phrase Reference in Japanese-to-English Machine Translation

abstract: This paper shows the necessity of distinguishing different referential uses of noun phrases in machine translation. We argue that differentiating between the generic, referential and ascriptive uses of noun phrases is the minimum necessary to generate articles and number correctly when translating from Japanese to English. Heuristics for determining these differences are proposed for a Japanese-to-English machine translation system. Finally the results of using the proposed heuristics are shown to have raised the percentage of noun phrases generated with correct use of articles and number in the Japanese-to-English machine translation system ALT-J/E from 65% to 77%.


title: A General Architecture for Language Engineering (GATE) - a new approach to Language Engineering R&D

abstract: This report argues for the provision of a common software infrastructure for NLP systems. Current trends in Language Engineering research are reviewed as motivation for this infrastructure, and relevant recent work discussed. A freely-available system called GATE is described which builds on this work.


title: Parsing with Typed Feature Structures

abstract: In this paper we provide for parsing with respect to grammars expressed in a general TFS-based formalism, a restriction of ALE. Our motivation being the design of an abstract (WAM-like) machine for the formalism, we consider parsing as a computational process and use it as an operational semantics to guide the design of the control structures for the abstract machine. We emphasize the notion of abstract typed feature structures (AFSs) that encode the essential information of TFSs and define unification over AFSs rather than over TFSs. We then introduce an explicit construct of multi-rooted feature structures (MRSs) that naturally extend TFSs and use them to represent phrasal signs as well as grammar rules. We also employ abstractions of MRSs and give the mathematical foundations needed for manipulating them. We then present a simple bottom-up chart parser as a model for computation: grammars written in the TFS-based formalism are executed by the parser. Finally, we show that the parser is correct.


title: Parsing with Typed Feature Structures

abstract: In this paper we provide for parsing with respect to grammars expressed in a general TFS-based formalism, a restriction of ALE. Our motivation being the design of an abstract (WAM-like) machine for the formalism, we consider parsing as a computational process and use it as an operational semantics to guide the design of the control structures for the abstract machine. We emphasize the notion of abstract typed feature structures (AFSs) that encode the essential information of TFSs and define unification over AFSs rather than over TFSs. We then introduce an explicit construct of multi-rooted feature structures (MRSs) that naturally extend TFSs and use them to represent phrasal signs as well as grammar rules. We also employ abstractions of MRSs and give the mathematical foundations needed for manipulating them. We formally define grammars and the languages they generate, and then describe a model for computation that corresponds to bottom-up chart parsing: grammars written in the TFS-based formalism are executed by the parser. We show that the computation is correct with respect to the independent definition. Finally, we discuss the class of grammars for which computations terminate and prove that termination can be guaranteed for off-line parsable grammars.


title: How Part-of-Speech Tags Affect Text Retrieval and Filtering Performance

abstract: Natural language processing (NLP) applied to information retrieval (IR) and filtering problems may assign part-of-speech tags to terms and, more generally, modify queries and documents. Analytic models can predict the performance of a text filtering system as it incorporates changes suggested by NLP, allowing us to make precise statements about the average effect of NLP operations on IR. Here we provide a model of retrieval and tagging that allows us to both compute the performance change due to syntactic parsing and to allow us to understand what factors affect performance and how. In addition to a prediction of performance with tags, upper and lower bounds for retrieval performance are derived, giving the best and worst effects of including part-of-speech tags. Empirical grounds for selecting sets of tags are considered.


title: Situations and Computation: An Overview of Recent Research

abstract: Serious thinking about the computational aspects of situation theory is just starting. There have been some recent proposals in this direction (viz. PROSIT and ASTL), with varying degrees of divergence from the ontology of the theory. We believe that a programming environment incorporating bona fide situation-theoretic constructs is needed and describe our very recent BABY-SIT implementation. A detailed critical account of PROSIT and ASTL is also offered in order to compare our system with these pioneering and influential frameworks.


title: Text Windows and Phrases Differing by Discipline, Location in Document, and Syntactic Structure

abstract: Knowledge of window style, content, location and grammatical structure may be used to classify documents as originating within a particular discipline or may be used to place a document on a theory versus practice spectrum. This distinction is also studied here using the type-token ratio to differentiate between sublanguages. The statistical significance of windows is computed, based on the the presence of terms in titles, abstracts, citations, and section headers, as well as binary independent (BI) and inverse document frequency (IDF) weightings. The characteristics of windows are studied by examining their within window density (WWD) and the S concentration (SC), the concentration of terms from various document fields (e.g. title, abstract) in the fulltext. The rate of window occurrences from the beginning to the end of document fulltext differs between academic fields. Different syntactic structures in sublanguages are examined, and their use is considered for discriminating between specific academic disciplines and, more generally, between theory versus practice or knowledge versus applications oriented documents.


title: Assessing agreement on classification tasks: the kappa statistic

abstract: Currently, computational linguists and cognitive scientists working in the area of discourse and dialogue argue that their subjective judgments are reliable using several different statistics, none of which are easily interpretable or comparable to each other. Meanwhile, researchers in content analysis have already experienced the same difficulties and come up with a solution in the kappa statistic. We discuss what is wrong with reliability measures as they are currently used for discourse and dialogue work in computational linguistics and cognitive science, and argue that we would be better off as a field adopting techniques from content analysis.


title: Speech Recognition by Composition of Weighted Finite Automata

abstract: We present a general framework based on weighted finite automata and weighted finite-state transducers for describing and implementing speech recognizers. The framework allows us to represent uniformly the information sources and data structures used in recognition, including context-dependent units, pronunciation dictionaries, language models and lattices. Furthermore, general but efficient algorithms can used for combining information sources in actual recognizers and for optimizing their application. In particular, a single composition algorithm is used both to combine in advance information sources such as language models and dictionaries, and to combine acoustic observations and information sources dynamically during recognition.


title: Finite-State Approximation of Phrase-Structure Grammars

abstract: Phrase-structure grammars are effective models for important syntactic and semantic aspects of natural languages, but can be computationally too demanding for use as language models in real-time speech recognition. Therefore, finite-state models are used instead, even though they lack expressive power. To reconcile those two alternatives, we designed an algorithm to compute finite-state approximations of context-free grammars and context-free-equivalent augmented phrase-structure grammars. 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 build finite-state language models for limited-domain speech recognition tasks.


title: Attempto Controlled English (ACE)

abstract: Attempto Controlled English (ACE) allows domain specialists to interactively formulate requirements specifications in domain concepts. ACE can be accurately and efficiently processed by a computer, but is expressive enough to allow natural usage. The Attempto system translates specification texts in ACE into discourse representation structures and optionally into Prolog. Translated specification texts are incrementally added to a knowledge base. This knowledge base can be queried in ACE for verification, and it can be executed for simulation, prototyping and validation of the specification.


title: Attempto - From Specifications in Controlled Natural Language towards Executable Specifications

abstract: Deriving formal specifications from informal requirements is difficult since one has to take into account the disparate conceptual worlds of the application domain and of software development. To bridge the conceptual gap we propose controlled natural language as a textual view on formal specifications in logic. The specification language Attempto Controlled English (ACE) is a subset of natural language that can be accurately and efficiently processed by a computer, but is expressive enough to allow natural usage. The Attempto system translates specifications in ACE into discourse representation structures and into Prolog. The resulting knowledge base can be queried in ACE for verification, and it can be executed for simulation, prototyping and validation of the specification.


title: Integrated speech and morphological processing in a connectionist continuous speech understanding for Korean

abstract: A new tightly coupled speech and natural language integration model is presented for a TDNN-based continuous possibly large vocabulary speech recognition system for Korean. Unlike popular n-best techniques developed for integrating mainly HMM-based speech recognition and natural language processing in a {\em word level}, which is obviously inadequate for morphologically complex agglutinative languages, our model constructs a spoken language system based on a {\em morpheme-level} speech and language integration. With this integration scheme, the spoken Korean processing engine (SKOPE) is designed and implemented using a TDNN-based diphone recognition module integrated with a Viterbi-based lexical decoding and symbolic phonological/morphological co-analysis. Our experiment results show that the speaker-dependent continuous {\em eojeol} (Korean word) recognition and integrated morphological analysis can be achieved with over 80.6% success rate directly from speech inputs for the middle-level vocabularies.


title: Extraction of V-N-Collocations from Text Corpora: A Feasibility Study for German

abstract: The usefulness of a statistical approach suggested by Church et al. (1991) is evaluated for the extraction of verb-noun (V-N) collocations from German text corpora. Some problematic issues of that method arising from properties of the German language are discussed and various modifications of the method are considered that might improve extraction results for German. The precision and recall of all variant methods is evaluated for V-N collocations containing support verbs, and the consequences for further work on the extraction of collocations from German corpora are discussed. With a sufficiently large corpus (>= 6 mio. word-tokens), the average error rate of wrong extractions can be reduced to 2.2% (97.8% precision) with the most restrictive method, however with a loss in data of almost 50% compared to a less restrictive method with still 87.6% precision. Depending on the goal to be achieved, emphasis can be put on a high recall for lexicographic purposes or on high precision for automatic lexical acquisition, in each case unfortunately leading to a decrease of the corresponding other variable. Low recall can still be acceptable if very large corpora (i.e. 50 - 100 million words) are available or if corpora for special domains are used in addition to the data found in machine readable (collocation) dictionaries.


title: Combining Hand-crafted Rules and Unsupervised Learning in Constraint-based Morphological Disambiguation

abstract: This paper presents a constraint-based morphological disambiguation approach that is applicable languages with complex morphology--specifically agglutinative languages with productive inflectional and derivational morphological phenomena. In certain respects, our approach has been motivated by Brill's recent work, but with the observation that his transformational approach is not directly applicable to languages like Turkish. Our system combines corpus independent hand-crafted constraint rules, constraint rules that are learned via unsupervised learning from a training corpus, and additional statistical information from the corpus to be morphologically disambiguated. The hand-crafted rules are linguistically motivated and tuned to improve precision without sacrificing recall. The unsupervised learning process produces two sets of rules: (i) choose rules which choose morphological parses of a lexical item satisfying constraint effectively discarding other parses, and (ii) delete rules, which delete parses satisfying a constraint. Our approach also uses a novel approach to unknown word processing by employing a secondary morphological processor which recovers any relevant inflectional and derivational information from a lexical item whose root is unknown. With this approach, well below 1 percent of the tokens remains as unknown in the texts we have experimented with. Our results indicate that by combining these hand-crafted,statistical and learned information sources, we can attain a recall of 96 to 97 percent with a corresponding precision of 93 to 94 percent, and ambiguity of 1.02 to 1.03 parses per token.


title: A Constraint-based Case Frame Lexicon

abstract: We present a constraint-based case frame lexicon architecture for bi-directional mapping between a syntactic case frame and a semantic frame. The lexicon uses a semantic sense as the basic unit and employs a multi-tiered constraint structure for the resolution of syntactic information into the appropriate senses and/or idiomatic usage. Valency changing transformations such as morphologically marked passivized or causativized forms are handled via lexical rules that manipulate case frames templates. The system has been implemented in a typed-feature system and applied to Turkish.


title: Error-tolerant Tree Matching

abstract: This paper presents an efficient algorithm for retrieving from a database of trees, all trees that match a given query tree approximately, that is, within a certain error tolerance. It has natural language processing applications in searching for matches in example-based translation systems, and retrieval from lexical databases containing entries of complex feature structures. The algorithm has been implemented on SparcStations, and for large randomly generated synthetic tree databases (some having tens of thousands of trees) it can associatively search for trees with a small error, in a matter of tenths of a second to few seconds.


title: Apportioning Development Effort in a Probabilistic LR Parsing System through Evaluation

abstract: We describe an implemented system for robust domain-independent syntactic parsing of English, using a unification-based grammar of part-of-speech and punctuation labels coupled with a probabilistic LR parser. We present evaluations of the system's performance along several different dimensions; these enable us to assess the contribution that each individual part is making to the success of the system as a whole, and thus prioritise the effort to be devoted to its further enhancement. Currently, the system is able to parse around 80% of sentences in a substantial corpus of general text containing a number of distinct genres. On a random sample of 250 such sentences the system has a mean crossing bracket rate of 0.71 and recall and precision of 83% and 84% respectively when evaluated against manually-disambiguated analyses.


title: Better Language Models with Model Merging

abstract: This paper investigates model merging, a technique for deriving Markov models from text or speech corpora. Models are derived by starting with a large and specific model and by successively combining states to build smaller and more general models. We present methods to reduce the time complexity of the algorithm and report on experiments on deriving language models for a speech recognition task. The experiments show the advantage of model merging over the standard bigram approach. The merged model assigns a lower perplexity to the test set and uses considerably fewer states.


title: The Role of the Gricean Maxims in the Generation of Referring Expressions

abstract: Grice's maxims of conversation [Grice 1975] are framed as directives to be followed by a speaker of the language. This paper argues that, when considered from the point of view of natural language generation, such a characterisation is rather misleading, and that the desired behaviour falls out quite naturally if we view language generation as a goal-oriented process. We argue this position with particular regard to the generation of referring expressions.


title: Collocational Grammar

abstract: A perspective of statistical language models which emphasizes their collocational aspect is advocated. It is suggested that strings be generalized in terms of classes of relationships instead of classes of objects. The single most important characteristic of such a model is a mechanism for comparing patterns. When patterns are fully generalized a natural definition of syntactic class emerges as a subset of relational class. These collocational syntactic classes should be an unambiguous partition of traditional syntactic classes.


title: Efficient Algorithms for Parsing the DOP Model

abstract: Excellent results have been reported for Data-Oriented Parsing (DOP) of natural language texts (Bod, 1993). Unfortunately, existing algorithms are both computationally intensive and difficult to implement. Previous algorithms are expensive due to two factors: the exponential number of rules that must be generated and the use of a Monte Carlo parsing algorithm. In this paper we solve the first problem by a novel reduction of the DOP model to a small, equivalent probabilistic context-free grammar. We solve the second problem by a novel deterministic parsing strategy that maximizes the expected number of correct constituents, rather than the probability of a correct parse tree. Using the optimizations, experiments yield a 97% crossing brackets rate and 88% zero crossing brackets rate. This differs significantly from the results reported by Bod, and is comparable to results from a duplication of Pereira and Schabes's (1992) experiment on the same data. We show that Bod's results are at least partially due to an extremely fortuitous choice of test data, and partially due to using cleaner data than other researchers.


title: Another Facet of LIG Parsing

abstract: In this paper we present a new parsing algorithm for linear indexed grammars (LIGs) in the same spirit as the one described in (Vijay-Shanker and Weir, 1993) for tree adjoining grammars. For a LIG $L$ and an input string $x$ of length $n$, we build a non ambiguous context-free grammar whose sentences are all (and exclusively) valid derivation sequences in $L$ which lead to $x$. We show that this grammar can be built in ${\cal O}(n^6)$ time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this ${\cal O}(n^6)$ upper bound does not improve over previous results, the average case behaves much better. Moreover, practical parsing times can be decreased by some statically performed computations.


title: Off-line Constraint Propagation for Efficient HPSG Processing

abstract: We investigate the use of a technique developed in the constraint programming community called constraint propagation to automatically make a HPSG theory more specific at those places where linguistically motivated underspecification would lead to inefficient processing. We discuss two concrete HPSG examples showing how off-line constraint propagation helps improve processing efficiency.


title: Multi-level post-processing for Korean character recognition using morphological analysis and linguistic evaluation

abstract: Most of the post-processing methods for character recognition rely on contextual information of character and word-fragment levels. However, due to linguistic characteristics of Korean, such low-level information alone is not sufficient for high-quality character-recognition applications, and we need much higher-level contextual information to improve the recognition results. This paper presents a domain independent post-processing technique that utilizes multi-level morphological, syntactic, and semantic information as well as character-level information. The proposed post-processing system performs three-level processing: candidate character-set selection, candidate eojeol (Korean word) generation through morphological analysis, and final single eojeol-sequence selection by linguistic evaluation. All the required linguistic information and probabilities are automatically acquired from a statistical corpus analysis. Experimental results demonstrate the effectiveness of our method, yielding error correction rate of 80.46%, and improved recognition rate of 95.53% from before-post-processing rate 71.2% for single best-solution selection.


title: SemHe: A Generalised Two-Level System

abstract: This paper presents a generalised two-level implementation which can handle linear and non-linear morphological operations. An algorithm for the interpretation of multi-tape two-level rules is described. In addition, a number of issues which arise when developing non-linear grammars are discussed with examples from Syriac.


title: Syntactic Analyses for Parallel Grammars: Auxiliaries and Genitive NPs

abstract: This paper focuses on two disparate aspects of German syntax from the perspective of parallel grammar development. As part of a cooperative project, we present an innovative approach to auxiliaries and multiple genitive NPs in German. The LFG-based implementation presented here avoids unnessary structural complexity in the representation of auxiliaries by challenging the traditional analysis of auxiliaries as raising verbs. The approach developed for multiple genitive NPs provides a more abstract, language independent representation of genitives associated with nominalized verbs. Taken together, the two approaches represent a step towards providing uniformly applicable treatments for differing languages, thus lightening the burden for machine translation.


title: The importance of being lazy -- using lazy evaluation to process queries to HPSG grammars

abstract: Linguistic theories formulated in the architecture of {\sc hpsg} can be very precise and explicit since {\sc hpsg} provides a formally well-defined setup. However, when querying a faithful implementation of such an explicit theory, the large data structures specified can make it hard to see the relevant aspects of the reply given by the system. Furthermore, the system spends much time applying constraints which can never fail just to be able to enumerate specific answers. In this paper we want to describe lazy evaluation as the result of an off-line compilation technique. This method of evaluation can be used to answer queries to an {\sc hpsg} system so that only the relevant aspects are checked and output.


title: Computing Prosodic Morphology

abstract: This paper establishes a framework under which various aspects of prosodic morphology, such as templatic morphology and infixation, can be handled under two-level theory using an implemented multi-tape two-level model. The paper provides a new computational analysis of root-and-pattern morphology based on prosody.


title: Processing Metonymy: a Domain-Model Heuristic Graph Traversal Approach

abstract: We address here the treatment of metonymic expressions from a knowledge representation perspective, that is, in the context of a text understanding system which aims to build a conceptual representation from texts according to a domain model expressed in a knowledge representation formalism. We focus in this paper on the part of the semantic analyser which deals with semantic composition. We explain how we use the domain model to handle metonymy dynamically, and more generally, to underlie semantic composition, using the knowledge descriptions attached to each concept of our ontology as a kind of concept-level, multiple-role qualia structure. We rely for this on a heuristic path search algorithm that exploits the graphic aspects of the conceptual graphs formalism. The methods described have been implemented and applied on French texts in the medical domain.


title: Fast Parsing using Pruning and Grammar Specialization

abstract: We show how a general grammar may be automatically adapted for fast parsing of utterances from a specific domain by means of constituent pruning and grammar specialization based on explanation-based learning. These methods together give an order of magnitude increase in speed, and the coverage loss entailed by grammar specialization is reduced to approximately half that reported in previous work. Experiments described here suggest that the loss of coverage has been reduced to the point where it no longer causes significant performance degradation in the context of a real application.


title: The Measure of a Model

abstract: This paper describes measures for evaluating the three determinants of how well a probabilistic classifier performs on a given test set. These determinants are the appropriateness, for the test set, of the results of (1) feature selection, (2) formulation of the parametric form of the model, and (3) parameter estimation. These are part of any model formulation procedure, even if not broken out as separate steps, so the tradeoffs explored in this paper are relevant to a wide variety of methods. The measures are demonstrated in a large experiment, in which they are used to analyze the results of roughly 300 classifiers that perform word-sense disambiguation.


title: Magic for Filter Optimization in Dynamic Bottom-up Processing

abstract: Off-line compilation of logic grammars using Magic allows an incorporation of filtering into the logic underlying the grammar. The explicit definite clause characterization of filtering resulting from Magic compilation allows processor independent and logically clean optimizations of dynamic bottom-up processing with respect to goal-directedness. Two filter optimizations based on the program transformation technique of Unfolding are discussed which are of practical and theoretical interest.


title: Translating into Free Word Order Languages

abstract: In this paper, I discuss machine translation of English text into Turkish, a relatively ``free'' word order language. I present algorithms that determine the topic and the focus of each target sentence (using salience (Centering Theory), old vs. new information, and contrastiveness in the discourse model) in order to generate the contextually appropriate word orders in the target language.


title: Extended Dependency Structures and their Formal Interpretation

abstract: We describe two ``semantically-oriented'' dependency-structure formalisms, U-forms and S-forms. U-forms have been previously used in machine translation as interlingual representations, but without being provided with a formal interpretation. S-forms, which we introduce in this paper, are a scoped version of U-forms, and we define a compositional semantics mechanism for them. Two types of semantic composition are basic: complement incorporation and modifier incorporation. Binding of variables is done at the time of incorporation, permitting much flexibility in composition order and a simple account of the semantic effects of permuting several incorporations.


title: Unsupervised Learning of Word-Category Guessing Rules

abstract: Words unknown to the lexicon present a substantial problem to part-of-speech tagging. In this paper we present a technique for fully unsupervised statistical acquisition of rules which guess possible parts-of-speech for unknown words. Three complementary sets of word-guessing rules are induced from the lexicon and a raw corpus: prefix morphological rules, suffix morphological rules and ending-guessing rules. The learning was performed on the Brown Corpus data and rule-sets, with a highly competitive performance, were produced and compared with the state-of-the-art.


title: A Model-Theoretic Framework for Theories of Syntax

abstract: A natural next step in the evolution of constraint-based grammar formalisms from rewriting formalisms is to abstract fully away from the details of the grammar mechanism---to express syntactic theories purely in terms of the properties of the class of structures they license. By focusing on the structural properties of languages rather than on mechanisms for generating or checking structures that exhibit those properties, this model-theoretic approach can offer simpler and significantly clearer expression of theories and can potentially provide a uniform formalization, allowing disparate theories to be compared on the basis of those properties. We discuss $\LKP$, a monadic second-order logical framework for such an approach to syntax that has the distinctive virtue of being superficially expressive---supporting direct statement of most linguistically significant syntactic properties---but having well-defined strong generative capacity---languages are definable in $\LKP$ iff they are strongly context-free. We draw examples from the realms of GPSG and GB.


title: Connectivity in Bag Generation

abstract: This paper presents a pruning technique which can be used to reduce the number of paths searched in rule-based bag generators of the type proposed by \cite{poznanskietal95} and \cite{popowich95}. Pruning the search space in these generators is important given the computational cost of bag generation. The technique relies on a connectivity constraint between the semantic indices associated with each lexical sign in a bag. Testing the algorithm on a range of sentences shows reductions in the generation time and the number of edges constructed.


title: Learning Part-of-Speech Guessing Rules from Lexicon: Extension to Non-Concatenative Operations

abstract: One of the problems in part-of-speech tagging of real-word texts is that of unknown to the lexicon words. In Mikheev (ACL-96 cmp-lg/9604022), a technique for fully unsupervised statistical acquisition of rules which guess possible parts-of-speech for unknown words was proposed. One of the over-simplification assumed by this learning technique was the acquisition of morphological rules which obey only simple concatenative regularities of the main word with an affix. In this paper we extend this technique to the non-concatenative cases of suffixation and assess the gain in the performance.


title: Towards a Workbench for Acquisition of Domain Knowledge from Natural Language

abstract: In this paper we describe an architecture and functionality of main components of a workbench for an acquisition of domain knowledge from large text corpora. The workbench supports an incremental process of corpus analysis starting from a rough automatic extraction and organization of lexico-semantic regularities and ending with a computer supported analysis of extracted data and a semi-automatic refinement of obtained hypotheses. For doing this the workbench employs methods from computational linguistics, information retrieval and knowledge engineering. Although the workbench is currently under implementation some of its components are already implemented and their performance is illustrated with samples from engineering for a medical domain.


title: Compiling a Partition-Based Two-Level Formalism

abstract: This paper describes an algorithm for the compilation of a two (or more) level orthographic or phonological rule notation into finite state transducers. The notation is an alternative to the standard one deriving from Koskenniemi's work: it is believed to have some practical descriptive advantages, and is quite widely used, but has a different interpretation. Efficient interpreters exist for the notation, but until now it has not been clear how to compile to equivalent automata in a transparent way. The present paper shows how to do this, using some of the conceptual tools provided by Kaplan and Kay's regular relations calculus.


title: Building Natural-Language Generation Systems

abstract: This is a very short paper that briefly discusses some of the tasks that NLG systems perform. It is of no research interest, but I have occasionally found it useful as a way of introducing NLG to potential project collaborators who know nothing about the field.


title: Yet Another Paper about Partial Verb Phrase Fronting in German

abstract: I describe a very simple HPSG analysis for partial verb phrase fronting. I will argue that the presented account is more adequate than others made during the past years because it allows the description of constituents in fronted positions with their modifier remaining in the non-fronted part of the sentence. A problem with ill-formed signs that are admitted by all HPSG accounts for partial verb phrase fronting known so far will be explained and a solution will be suggested that uses the difference between combinatoric relations of signs and their representation in word order domains.


title: Higher-Order Coloured Unification and Natural Language Semantics

abstract: In this paper, we show that Higher-Order Coloured Unification - a form of unification developed for automated theorem proving - provides a general theory for modeling the interface between the interpretation process and other sources of linguistic, non semantic information. In particular, it provides the general theory for the Primary Occurrence Restriction which (Dalrymple, Shieber and Pereira, 1991)'s analysis called for.


title: Focus and Higher-Order Unification

abstract: Pulman has shown that Higher--Order Unification (HOU) can be used to model the interpretation of focus. In this paper, we extend the unification--based approach to cases which are often seen as a test--bed for focus theory: utterances with multiple focus operators and second occurrence expressions. We then show that the resulting analysis favourably compares with two prominent theories of focus (namely, Rooth's Alternative Semantics and Krifka's Structured Meanings theory) in that it correctly generates interpretations which these alternative theories cannot yield. Finally, we discuss the formal properties of the approach and argue that even though HOU need not terminate, for the class of unification--problems dealt with in this paper, HOU avoids this shortcoming and is in fact computationally tractable.


title: Active Constraints for a Direct Interpretation of HPSG

abstract: In this paper, we characterize the properties of a direct interpretation of HPSG and present the advantages of this approach. High-level programming languages constitute in this perspective an efficient solution: we show how a multi-paradigm approach, containing in particular constraint logic programming, offers mechanims close to that of the theory and preserves its fundamental properties. We take the example of LIFE and describe the implementation of the main HPSG mechanisms.


title: Resolving Anaphors in Embedded Sentences

abstract: We propose an algorithm to resolve anaphors, tackling mainly the problem of intrasentential antecedents. We base our methodology on the fact that such antecedents are likely to occur in embedded sentences. Sidner's focusing mechanism is used as the basic algorithm in a more complete approach. The proposed algorithm has been tested and implemented as a part of a conceptual analyser, mainly to process pronouns. Details of an evaluation are given.


title: Tactical Generation in a Free Constituent Order Language

abstract: This paper describes tactical generation in Turkish, a free constituent order language, in which the order of the constituents may change according to the information structure of the sentences to be generated. In the absence of any information regarding the information structure of a sentence (i.e., topic, focus, background, etc.), the constituents of the sentence obey a default order, but the order is almost freely changeable, depending on the constraints of the text flow or discourse. We have used a recursively structured finite state machine for handling the changes in constituent order, implemented as a right-linear grammar backbone. Our implementation environment is the GenKit system, developed at Carnegie Mellon University--Center for Machine Translation. Morphological realization has been implemented using an external morphological analysis/generation component which performs concrete morpheme selection and handles morphographemic processes.


title: Learning similarity-based word sense disambiguation from sparse data

abstract: We describe a method for automatic word sense disambiguation using a text corpus and a machine-readable dictionary (MRD). The method is based on word similarity and context similarity measures. Words are considered similar if they appear in similar contexts; contexts are similar if they contain similar words. The circularity of this definition is resolved by an iterative, converging process, in which the system learns from the corpus a set of typical usages for each of the senses of the polysemous word listed in the MRD. A new instance of a polysemous word is assigned the sense associated with the typical usage most similar to its context. Experiments show that this method performs well, and can learn even from very sparse training data.


title: Best-First Surface Realization

abstract: Current work in surface realization concentrates on the use of general, abstract algorithms that interpret large, reversible grammars. Only little attention has been paid so far to the many small and simple applications that require coverage of a small sublanguage at different degrees of sophistication. The system TG/2 described in this paper can be smoothly integrated with deep generation processes, it integrates canned text, templates, and context-free rules into a single formalism, it allows for both textual and tabular output, and it can be parameterized according to linguistic preferences. These features are based on suitably restricted production system techniques and on a generic backtracking regime.


title: Counting Coordination Categorially

abstract: This paper presents a way of reducing the complexity of parsing free coordination. It lives on the Coordinative Count Invariant, a property of derivable sequences in occurrence-sensitive categorial grammar. This invariant can be exploited to cut down deterministically the search space for coordinated sentences to minimal fractions. The invariant is based on inequalities, which is shown to be the best one can get in the presence of coordination without proper parsing. It is implemented in a categorial parser for Dutch. Some results of applying the invariant to the parsing of coordination in this parser are presented.


title: A New Statistical Parser Based on Bigram Lexical Dependencies

abstract: This paper describes a new statistical parser which is based on probabilities of dependencies between head-words in the parse tree. Standard bigram probability estimation techniques are extended to calculate probabilities of dependencies between pairs of words. Tests using Wall Street Journal data show that the method performs at least as well as SPATTER (Magerman 95, Jelinek et al 94), which has the best published results for a statistical parser on this task. The simplicity of the approach means the model trains on 40,000 sentences in under 15 minutes. With a beam search strategy parsing speed can be improved to over 200 sentences a minute with negligible loss in accuracy.


title: Learning Dependencies between Case Frame Slots

abstract: We address the problem of automatically acquiring case frame patterns (selectional patterns) from large corpus data. In particular, we propose a method of learning dependencies between case frame slots. We view the problem of learning case frame patterns as that of learning multi-dimensional discrete joint distributions, where random variables represent case slots. We then formalize the dependencies between case slots as the probabilistic dependencies between these random variables. Since the number of parameters in a multi-dimensional joint distribution is exponential, it is infeasible to accurately estimate them in practice. To overcome this difficulty, we settle with approximating the target joint distribution by the product of low order component distributions, based on corpus data. In particular we propose to employ an efficient learning algorithm based on the MDL principle to realize this task. Our experimental results indicate that for certain classes of verbs, the accuracy achieved in a disambiguation experiment is improved by using the acquired knowledge of dependencies.


title: Clustering Words with the MDL Principle

abstract: We address the problem of automatically constructing a thesaurus (hierarchically clustering words) based on corpus data. We view the problem of clustering words as that of estimating a joint distribution over the Cartesian product of a partition of a set of nouns and a partition of a set of verbs, and propose an estimation algorithm using simulated annealing with an energy function based on the Minimum Description Length (MDL) Principle. We empirically compared the performance of our method based on the MDL Principle against that of one based on the Maximum Likelihood Estimator, and found that the former outperforms the latter. We also evaluated the method by conducting pp-attachment disambiguation experiments using an automatically constructed thesaurus. Our experimental results indicate that we can improve accuracy in disambiguation by using such a thesaurus.


title: Adapting the Core Language Engine to French and Spanish

abstract: We describe how substantial domain-independent language-processing systems for French and Spanish were quickly developed by manually adapting an existing English-language system, the SRI Core Language Engine. We explain the adaptation process in detail, and argue that it provides a fairly general recipe for converting a grammar-based system for English into a corresponding one for a Romance language.


title: Parsing for Semidirectional Lambek Grammar is NP-Complete

abstract: We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call {\em semidirectional}. In semidirectional Lambek calculus $\SDL$ there is an additional non-directional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent's left-hand side, thus permitting non-peripheral extraction. $\SDL$ grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidirectional Lambek Grammar is NP-complete by a reduction of the 3-Partition problem.


title: A Chart Generator for Shake and Bake Machine Translation

abstract: A generation algorithm based on an active chart parsing algorithm is introduced which can be used in conjunction with a Shake and Bake machine translation system. A concise Prolog implementation of the algorithm is provided, and some performance comparisons with a shift-reduce based algorithm are given which show the chart generator is much more efficient for generating all possible sentences from an input specification.


title: Efficient Tabular LR Parsing

abstract: We give a new treatment of tabular LR parsing, which is an alternative to Tomita's generalized LR algorithm. The advantage is twofold. Firstly, our treatment is conceptually more attractive because it uses simpler concepts, such as grammar transformations and standard tabulation techniques also know as chart parsing. Secondly, the static and dynamic complexity of parsing, both in space and time, is significantly reduced.


title: Noun-Phrase Analysis in Unrestricted Text for Information Retrieval

abstract: Information retrieval is an important application area of natural-language processing where one encounters the genuine challenge of processing large quantities of unrestricted natural-language text. This paper reports on the application of a few simple, yet robust and efficient noun-phrase analysis techniques to create better indexing phrases for information retrieval. In particular, we describe a hybrid approach to the extraction of meaningful (continuous or discontinuous) subcompounds from complex noun phrases using both corpus statistics and linguistic heuristics. Results of experiments show that indexing based on such extracted subcompounds improves both recall and precision in an information retrieval system. The noun-phrase analysis techniques are also potentially useful for book indexing and automatic thesaurus extraction.


title: Where Defaults Don't Help: the Case of the German Plural System

abstract: The German plural system has become a focal point for conflicting theories of language, both linguistic and cognitive. We present simulation results with three simple classifiers - an ordinary nearest neighbour algorithm, Nosofsky's `Generalized Context Model' (GCM) and a standard, three-layer backprop network - predicting the plural class from a phonological representation of the singular in German. Though these are absolutely `minimal' models, in terms of architecture and input information, they nevertheless do remarkably well. The nearest neighbour predicts the correct plural class with an accuracy of 72% for a set of 24,640 nouns from the CELEX database. With a subset of 8,598 (non-compound) nouns, the nearest neighbour, the GCM and the network score 71.0%, 75.0% and 83.5%, respectively, on novel items. Furthermore, they outperform a hybrid, `pattern-associator + default rule', model, as proposed by Marcus et al. (1995), on this data set.


title: Functional Centering

abstract: Based on empirical evidence from a free word order language (German) we propose a fundamental revision of the principles guiding the ordering of discourse entities in the forward-looking centers within the centering model. We claim that grammatical role criteria should be replaced by indicators of the functional information structure of the utterances, i.e., the distinction between context-bound and unbound discourse elements. This claim is backed up by an empirical evaluation of functional centering.


title: Processing Complex Sentences in the Centering Framework

abstract: We extend the centering model for the resolution of intra-sentential anaphora and specify how to handle complex sentences. An empirical evaluation indicates that the functional information structure guides the search for an antecedent within the sentence.


title: A Simple Transformation for Offline-Parsable Grammars and its Termination Properties

abstract: We present, in easily reproducible terms, a simple transformation for offline-parsable grammars which results in a provably terminating parsing program directly top-down interpretable in Prolog. The transformation consists in two steps: (1) removal of empty-productions, followed by: (2) left-recursion elimination. It is related both to left-corner parsing (where the grammar is compiled, rather than interpreted through a parsing program, and with the advantage of guaranteed termination in the presence of empty productions) and to the Generalized Greibach Normal Form for DCGs (with the advantage of implementation simplicity).


title: Using Terminological Knowledge Representation Languages to Manage Linguistic Resources

abstract: I examine how terminological languages can be used to manage linguistic data during NL research and development. In particular, I consider the lexical semantics task of characterizing semantic verb classes and show how the language can be extended to flag inconsistencies in verb class definitions, identify the need for new verb classes, and identify appropriate linguistic hypotheses for a new verb's behavior.


title: A Conceptual Reasoning Approach to Textual Ellipsis

abstract: We present a hybrid text understanding methodology for the resolution of textual ellipsis. It integrates conceptual criteria (based on the well-formedness and conceptual strength of role chains in a terminological knowledge base) and functional constraints reflecting the utterances' information structure (based on the distinction between context-bound and unbound discourse elements). The methodological framework for text ellipsis resolution is the centering model that has been adapted to these constraints.


title: Trading off Completeness for Efficiency --- The \textsc{ParseTalk} Performance Grammar Approach to Real-World Text Parsing

abstract: We argue for a performance-based design of natural language grammars and their associated parsers in order to meet the constraints posed by real-world natural language understanding. This approach incorporates declarative and procedural knowledge about language and language use within an object-oriented specification framework. We discuss several message passing protocols for real-world text parsing and provide reasons for sacrificing completeness of the parse in favor of efficiency.


title: Restricted Parallelism in Object-Oriented Lexical Parsing

abstract: We present an approach to parallel natural language parsing which is based on a concurrent, object-oriented model of computation. A depth-first, yet incomplete parsing algorithm for a dependency grammar is specified and several restrictions on the degree of its parallelization are discussed.


title: Towards Understanding Spontaneous Speech: Word Accuracy vs. Concept Accuracy

abstract: In this paper we describe an approach to automatic evaluation of both the speech recognition and understanding capabilities of a spoken dialogue system for train time table information. We use word accuracy for recognition and concept accuracy for understanding performance judgement. Both measures are calculated by comparing these modules' output with a correct reference answer. We report evaluation results for a spontaneous speech corpus with about 10000 utterances. We observed a nearly linear relationship between word accuracy and concept accuracy.


title: Learning Word Association Norms Using Tree Cut Pair Models

abstract: We consider the problem of learning co-occurrence information between two word categories, or more in general between two discrete random variables taking values in a hierarchically classified domain. In particular, we consider the problem of learning the `association norm' defined by A(x,y)=p(x, y)/(p(x)*p(y)), where p(x, y) is the joint distribution for x and y and p(x) and p(y) are marginal distributions induced by p(x, y). We formulate this problem as a sub-task of learning the conditional distribution p(x|y), by exploiting the identity p(x|y) = A(x,y)*p(x). We propose a two-step estimation method based on the MDL principle, which works as follows: It first estimates p(x) as p1 using MDL, and then estimates p(x|y) for a fixed y by applying MDL on the hypothesis class of {A * p1 | A \in B} for some given class B of representations for association norm. The estimation of A is therefore obtained as a side-effect of a near optimal estimation of p(x|y). We then apply this general framework to the problem of acquiring case-frame patterns. We assume that both p(x) and A(x, y) for given y are representable by a model based on a classification that exists within an existing thesaurus tree as a `cut,' and hence p(x|y) is represented as the product of a pair of `tree cut models.' We then devise an efficient algorithm that implements our general strategy. We tested our method by using it to actually acquire case-frame patterns and conducted disambiguation experiments using the acquired knowledge. The experimental results show that our method improves upon existing methods.


title: Incremental Centering and Center Ambiguity

abstract: In this paper, we present a model of anaphor resolution within the framework of the centering model. The consideration of an incremental processing mode introduces the need to manage structural ambiguity at the center level. Hence, the centering framework is further refined to account for local and global parsing ambiguities which propagate up to the level of center representations, yielding moderately adapted data structures for the centering algorithm.


title: Efficient Algorithms for Parsing the DOP Model? A Reply to Joshua Goodman

abstract: This note is a reply to Joshua Goodman's paper "Efficient Algorithms for Parsing the DOP Model" (Goodman, 1996; cmp-lg/9604008). In his paper, Goodman makes a number of claims about (my work on) the Data-Oriented Parsing model (Bod, 1992-1996). This note shows that some of these claims must be mistaken.


title: Synchronous Models of Language

abstract: In synchronous rewriting, the productions of two rewriting systems are paired and applied synchronously in the derivation of a pair of strings. We present a new synchronous rewriting system and argue that it can handle certain phenomena that are not covered by existing synchronous systems. We also prove some interesting formal/computational properties of our system.


title: Notes on LR Parser Design

abstract: The design of an LR parser based on interleaving the atomic symbol processing of a context-free backbone grammar with the full constraints of the underlying unification grammar is described. The parser employs a set of reduced constraints derived from the unification grammar in the LR parsing step. Gap threading is simulated to reduce the applicability of empty productions.


title: Handling Sparse Data by Successive Abstraction

abstract: A general, practical method for handling sparse data that avoids held-out data and iterative reestimation is derived from first principles. It has been tested on a part-of-speech tagging task and outperformed (deleted) interpolation with context-independent weights, even when the latter used a globally optimal parameter setting determined a posteriori.


title: Example-Based Optimization of Surface-Generation Tables

abstract: A method is given that "inverts" a logic grammar and displays it from the point of view of the logical form, rather than from that of the word string. LR-compiling techniques are used to allow a recursive-descent generation algorithm to perform "functor merging" much in the same way as an LR parser performs prefix merging. This is an improvement on the semantic-head-driven generator that results in a much smaller search space. The amount of semantic lookahead can be varied, and appropriate tradeoff points between table size and resulting nondeterminism can be found automatically. This can be done by removing all spurious nondeterminism for input sufficiently close to the examples of a training corpus, and large portions of it for other input, while preserving completeness.


title: Parsing Algorithms and Metrics

abstract: Many different metrics exist for evaluating parsing results, including Viterbi, Crossing Brackets Rate, Zero Crossing Brackets Rate, and several others. However, most parsing algorithms, including the Viterbi algorithm, attempt to optimize the same metric, namely the probability of getting the correct labelled tree. By choosing a parsing algorithm appropriate for the evaluation metric, better performance can be achieved. We present two new algorithms: the ``Labelled Recall Algorithm,'' which maximizes the expected Labelled Recall Rate, and the ``Bracketed Recall Algorithm,'' which maximizes the Bracketed Recall Rate. Experimental results are given, showing that the two new algorithms have improved performance over the Viterbi algorithm on many criteria, especially the ones that they optimize.


title: Combining Trigram-based and Feature-based Methods for Context-Sensitive Spelling Correction

abstract: This paper addresses the problem of correcting spelling errors that result in valid, though unintended words (such as ``peace'' and ``piece'', or ``quiet'' and ``quite'') and also the problem of correcting particular word usage errors (such as ``amount'' and ``number'', or ``among'' and ``between''). Such corrections require contextual information and are not handled by conventional spelling programs such as Unix `spell'. First, we introduce a method called Trigrams that uses part-of-speech trigrams to encode the context. This method uses a small number of parameters compared to previous methods based on word trigrams. However, it is effectively unable to distinguish among words that have the same part of speech. For this case, an alternative feature-based method called Bayes performs better; but Bayes is less effective than Trigrams when the distinction among words depends on syntactic constraints. A hybrid method called Tribayes is then introduced that combines the best of the previous two methods. The improvement in performance of Tribayes over its components is verified experimentally. Tribayes is also compared with the grammar checker in Microsoft Word, and is found to have substantially higher performance.


title: Efficient Normal-Form Parsing for Combinatory Categorial Grammar

abstract: Under categorial grammars that have powerful rules like composition, a simple n-word sentence can have exponentially many parses. Generating all parses is inefficient and obscures whatever true semantic ambiguities are in the input. This paper addresses the problem for a fairly general form of Combinatory Categorial Grammar, by means of an efficient, correct, and easy to implement normal-form parsing technique. The parser is proved to find exactly one parse in each semantic equivalence class of allowable parses; that is, spurious ambiguity (as carefully defined) is shown to be both safely and completely eliminated.