Search

As one of the key components, n-gram language model is most frequently used in statistical machine translation. Typically, higher order of the language model leads to better translation performance. However, higher order of the n-gram language model requires much more monolingual training data to avoid data sparseness. Furthermore, the model size increases exponentially when the n-gram order becomes higher and higher. In this paper, we investigate the language model pruning techniques that aim at making the model size as small as possible while keeping the translation quality. According to our investigation, we further propose to replace the higher order n-grams with a low-order cluster-based language model. The extensive experiments show that our method is very effective.

This paper investigates the usefulness of a part of speech language model on the task of automatic speech recognition. The develped model uses part of speech tags as categories in a category-based language model. The constructed model is used to re-score the hypotheses generated by the HTK acoustic module. The probability of a given sequence of words is estimated using n-grams with Witten-Bell backoff. The experiments presented in this paper were carried out for Polish. The best obtained results show that the part-of-speech-only language model trained on a 1-million manually tagged corpus reduces the word error rate by more than 10 percentage points.

Cross language information retrieval (CLIR) is a sub field of information retrieval (IR) which deals with retrieval of content from one language (source language) for a search query expressed in another language (target language) in the Web. Cross Language Information Retrieval evolved as a field due to the fact that majority of the content in the web is in English. Hence there is a need for dynamic translation of web content for a query expressed in the native language. The biggest problem is that of ambiguity of the query expressed in the native language. The ambiguity of languages is typically not a problem for human beings who can infer the appropriate word sense or meaning based on context, but search engines cannot usually overcome these limitations. Hence, methods and mechanisms to provide native languages access to information from the web are needed. There is a need, to not only retrieve the relevant results but also, present the content behind the results in a user understandable manner. The research in the domain has so far focused in terms of techniques that make use support vector machines, suffix tree approach, Boolean models, and iterative results clustering. This research work focuses on a methodology of personalized context based cross language information retrieval using ensemble-learning approach. The source language for this research is taken, as English and the target language is Telugu. The methodology has tested for various queries and the results are shown in this work.

In order to improve the results of automatically recognized handwritten text, information about the language is commonly included in the recognition process. A common approach is to represent a text line as a sequence. It is processed in one direction and the language information via n-grams is directly included in the decoding. This approach, however, only uses context on one side to estimate a word's probability. Therefore, we propose a bidirectional recognition in this paper, using distinct forward and a backward language models. By combining decoding hypotheses from both directions, we achieve a significant increase in recognition accuracy for the off-line writer independent handwriting recognition task. Both language models are of the same type and can be estimated on the same corpus. Hence, the increase in recognition accuracy comes without any additional need for training data or language modeling complexity.

Cross Language Text Categorization (CLTC) is the task of assigning class labels to documents written in a target language (e.g. Chinese) while the system is trained using labeled examples in a source language (e.g. English). With the technique of CLTC, we can build classifiers for multiple languages employing the existing training data in only one language, therefore avoid the cost of preparing training data for each individual language. One challenge for CLTC is the culture differences between languages, which causes the classifier trained on the source language doesn't perform well on the target language. In this paper, we propose an active learning algorithm for CLTC, which takes full advantage of both labeled data in the source language and unlabeled data in the target language. The classifier first learns the classification knowledge from the source language, and then learns the cultural dependent knowledge from the target language. In addition, we extend our algorithm to double viewed form by considering the source and target language as two views of the classification problem. Experiments show that our algorithm can effectively improve the cross language classification performance.

This paper presents the application of morpheme-based and factored language models in an Amharic speech recognition task. Since the use of morphemes in both acoustic and language models often results in performance degradation due to a higher acoustic confusability and since it is problematic to use factored language models in standard word decoders, we applied the models in a lattice rescoring framework. Lattices of 100 best alternatives for each test sentence of the 5k development test set have been generated using a baseline speech recognizer with a word-based backoff bigram language model. The lattices have then been rescored by means of various morpheme-based and factored language models. A slight improvement in word recognition accuracy has been observed with morpheme-based language models while factored language models led to notable improvements in word recognition accuracy.

Statistical language models based on n-gram counts have been shown to successfully replace grammar rules in standard 2-stage (or 'generate-and-select') Natural Language Generation (NLG). In highlyinflected languages, however, the amount of training data required to cope with n-gram sparseness may be simply unobtainable, and the benefits of a statistical approach become less obvious. In this work we address the issue of text generation in a highly-inflected language by making use of factored language models (FLM) that take morphological information into account. We present a number of experiments involving the use of simple FLMs applied to various surface realisation tasks, showing that FLMs may implement 2-stage generation with results that are far superior to standard n-gram models alone.

Automatic speech recognition system is one of the parts of the multimodal dialogue system. It is necessary to create correct vocabulary and to generate suitable language model for this purpose. The main aim of this article is to describe a process of building statistical models of the Slovak language with large vocabulary trained on the text data gathered mainly from Internet sources. Several smoothing techniques for different sizes of vocabulary have been used in order to obtain an optimal model of the Slovak language. We have also employed pruning technique based on relative entropy for size reduction of a language model to find the maximum threshold of pruning with minimum degradation in recognition accuracy. Tests were performed by the decoder based on the HTK Toolkit.

Through out this work we explore different methods to integrate a complex Language Model (a hierarchical Language Model based on classes of phrases) into an Automatic Speech Recognition (ASR) system. The integration is carried out by means of a composition of the different Stochastic Finite State Automata associated to the specific Language Model. This method is based on the same idea employed to integrate the different knowledge sources involved in the recognition process when a classical word-based Language Model is considered. The obtained results show that this integrated architecture provides better ASR system performance than a two-pass decoder where the complex LM is employed to reorder the N-best list.

Our long term goal is to develop systems that can "understand" natural language text. By "understand" we mean that the system can take natural language text as input and answer questions with respect to that text. A key component in building such systems is to be able to translate natural language text into appropriate knowledge representation (KR) languages. Our approach to achieve that is inspired by Montagues path breaking thesis (1970) of viewing English as a formal language and by the research in natural language semantics. Our approach is based on PCCG (Probabilistic Combinatorial Categorial Grammars), λ-calculus and statistical learning of parameters. In an initial work, we start with an initial vocabulary consisting of λ-calculus representations of a small set of words and a training corpus of sentences and their representation in a KR language. We develop a learning based system that learns the λ-calculus representation of words from this corpus and generalizes it to words of the same category. The key and novel aspect in this learning is the development of Inverse Lambda algorithms which when given λ-expressions β and γ can come up with an a such that application of a to β (or β to α) will give us γ. We augment this with learning of weights associated with multiple meanings of words. Our current system produces improved results on standard corpora on natural language interfaces for robot command and control and database queries. In a follow-up work we are able to use patterns to make guesses regarding the initial vocabulary. This together with learning of parameters allow us to develop a fully automated (without any initial vocabulary) way to translate English to designated KR languages. In an on-going work we use Answer Set Programming as the target KR language and focus on (a) solving combinatorial puzzles that are described in English and (b) answering questions with respect to a chapter in a ninth grade biology book. The systems that we are building are good examples of integration of results from multiple sub-fields of AI and computer science, viz.: machine learning, knowledge representation, natural language processing, λ-calculus (functional programming) and ontologies. In this presentation we will describe our approach and our system and elaborate on some of the lessons that we have learned from this effort.

Machine Translation (MT) refers to the use of a machine for performing translation task which converts text or speech in one Natural Language (Source Language (SL)) into another Natural Language (Target Language (TL)). The translation from Arabic to English is difficult task due to the Arabic languages are highly inflectional, rich morphology and relatively free word order. Word ordering plays an important part in the translation process. The paper proposes a transfer-based approach in Arabic to English MT to handle the word ordering problem. Preliminary tested indicate that our system, AE-TBMT is competitive when compared against other approaches from the literature.

We explain why weighted automata are an attractive knowledge representation for natural language problems. We first trace the close historical ties between the two fields, then present two complex real-world problems, transliteration and translation. These problems are usefully decomposed into a pipeline of weighted transducers, and weights can be set to maximize the likelihood of a training corpus using standard algorithms. We additionally describe the representation of language models, critical data sources in natural language processing, as weighted automata. We outline the wide range of work in natural language processing that makes use of weighted string and tree automata and describe current work and challenges.

Natural language parsing, as one of the central tasks in natural language processing, is widely used in many AI fields. In this paper, we address an issue of parser performance evaluation, particularly its variation across datasets. We propose three simple statistical measures to characterize the datasets and also evaluate their correlation to the parser performance. The results clearly show that different parsers have different performance variation and sensitivity against these measures. The method can be used to guide the choice of natural language parsers for new domain applications, as well as systematic combination for better parsing accuracy.

In automatic sign language translation, one of the main problems is the usage of spatial information in sign language and its proper representation and translation, e.g. the handling of spatial reference points in the signing space. Such locations are encoded at static points in signing space as spatial references for motion events. We present a new approach starting from a large vocabulary speech recognition system which is able to recognize sentences of continuous sign language speaker independently. The manual features obtained from the tracking are passed to the statistical machine translation system to improve its accuracy. On a publicly available benchmark database, we achieve a competitive recognition performance and can similarly improve the translation performance by integrating the tracking features.

Multilingual Automatic Speech Recognition (ASR) systems are of great interest in multilingual environments. We have studied the case of the Comunitat Valenciana because the two official languages are Spanish and Valencian. These two languages share most of their phonemes and their syntax and vocabulary are also quite similar since they have influenced each other for many years. In this work, we present the design of the language and the acoustic models for this bilingual situation. Acoustic models can be separate for each language or shared by both of them, and they can be obtained directly from a training corpus or by adapting a previous set of acoustic models. Language models can be separate for each language (monolingual recognition) or mixed for both languages (bilingual recognition). We performed experiments with a small corpus to determine which option was better for this case.

The process of learning and understand the sign language may be cumbersome to some, and therefore, this paper proposes a solution to this problem by providing a voice (English Language) to sign language translation system using Speech and Image processing technique. Speech processing which includes Speech Recognition is the study of recognizing the words being spoken, regardless of whom the speaker is. This project uses template-based recognition as the main approach in which the V2S system first needs to be trained with speech pattern based on some generic spectral parameter set. These spectral parameter set will then be stored as template in a database. The system will perform the recognition process through matching the parameter set of the input speech with the stored templates to finally display the sign language in video format. Empirical results show that the system has 80.3% recognition rate.

The n-gram model is standard for large vocabulary speech recognizers. Many attempts were made to improve on it. Language models were proposed based on grammatical analysis, artificial neural networks, random forests, etc. While the latter give somewhat better recognition results than the n-gram model, they are not practical, particularly when large training data bases (e.g., from world wide web) are available. So should language model research be abandoned as a hopeless endeavor? This talk will discuss a plan to determine how large a decrease in recognition error rate is conceivable, and propose a game-based method to determine what parameters the ultimate language model should depend on.

Most of state-of-the-art large vocabulary continuous speech recognition systems use word-based n-gram language models. Such models are not optimal solution for inflectional or agglutinative languages. The Polish language is highly inflectional one and requires a very large corpora to create a sufficient language model with the small out-of-vocabulary ratio. We propose a syllable-based language model, which is better suited to highly inflectional language like Polish. In case of lack of resources (i.e. small corpora) syllable-based model outperforms word-based models in terms of number of out-of-vocabulary units (syllables in our model). Such model is an approximation of the morpheme-based model for Polish. In our paper, we show results of evaluation of syllable based model and its usefulness in speech recognition tasks.

This paper presents a language model adaptation framework for highly inflected languages that use sub-word units as basic units in a language model for large vocabulary speech recognition. The proposed adaptation method uses latent semantic analysis based information retrieval to find documents similar to a tiny adaptation corpus. The approach enables to use different language units for modeling document similarity. The method is tested on an Estonian broadcast news transcription task. We compare words, lemmas and morphemes as basic units for similarity modeling. We observe a drop in speech recognition error rate after building adapted language model for each news story. Morpheme-based adaptation is found to give significantly larger improvement than word and lemma-based adaptation.

Statistical pattern recognition has proved to be an interesting framework for machine translation, and stochastic finite-state transducers are adequate models in many language processing areas such as speech translation, computer-assisted translations, etc. The well-known n-gram language models are widely used in this framework for machine translation. One of the application of these n-gram models is to infer stochastic finite-state transducers. However, only simple dependencies can be modelled, but many translations require to take into account strong context and style dependencies. Mixtures of parametric models allow to increase the description power of the statistical models by modelling subclasses of objects. In this work, we propose the use of n-gram mixtures in GIATI, a procedure to infer stochastic finite-state transducers. N-gram mixtures are expected to model topics or writing styles. We present experimental results showing that translation performance can be improved if enough training data is available.

The aim of this work is to integrate segments of words into a category-based Language Model. Two proposals of this kind of models are presented. On the other hand an interpolation of a category-based model with a classical word-based Language Model is studied as well. The models were integrated into an ASR system and evaluated in terms of WER. Experiments on a spontaneous dialogue corpus in Spanish are reported. These experiments show that integrating word segments in a category-based Language Model, a better performance of the model can be achieved.

Half of the world speaks languages that are out of the machine translation and natural language processing technologies mainstream. Then the choice of natural language technology for a given language pair is greatly impacted by technology and resources available. In this paper we describe a hybrid architecture and technology for rapid development of the machine translation system from English to low-density languages. We use state of the art English language processing technologies and resources to transform (compress) the language into the more abstract form. The abstraction level of the transformation is adapted to our knowledge of the low-density (foreign) language. Then statistical machine translation is used to induce translation rules. All tests and implementations have been done on the English --- Lithuanian language pair. Some of the findings of the research can be useful for all, novel and old machine translation language pairs.

In this paper we propose different approaches to the LM integrated in a Continuous Speech Recognition system. All of them are based on classes that are made up of phrases or segments of words. The proposed models were evaluated in terms of Word Error Rate over a spontaneous dialogue corpus in Spanish. The experiments carried out show that better performance of the CSR system can be achieved introducing segments of words into a class-based LM.

Statistical Machine Translation (SMT) is an evolving field where many techniques in Syntactic Pattern Recognition (SPR) are needed and applied. A typical phrase-based SMT system for translating from a T (target) language to an S (source) language contains one or more n-gram language models (LMs) and one or more phrase translation models (TMs). These LMs and TMs have a large memory footprint (up to several gigabytes). This paper describes novel techniques for filtering these models that ensure only relevant patterns in the LMs and TMs are loaded during translation. In experiments on a large Chinese-English task, these techniques yielded significant reductions in the amount of information loaded during translation: up to 58% reduction for LMs, and up to 75% for TMs., 5th International Conference on Computer Recognition Systems CORES 07, Wroclaw, Poland, October 22-25, 2007

Although n-gram models are still the de facto standard in language modeling for speech recognition, it has been shown that more sophisticated models achieve better accuracy by taking additional information, such as syntactic rules, semantic relations or domain knowledge into account Unfortunately, most of the effort in developing such models goes into the implementation of handcrafted inference routines What lacks is a generic mechanism to introduce background knowledge into a language model We propose the use of dynamic Bayesian networks for this purpose Dynamic Bayesian networks can be seen as a generalization of the n-gram models and hmms traditionally used in language modeling and speech recognition Whereas those models use a single random variable to represent state, Bayesian networks can have any number of variables As such they are particularly well-suited for the construction of models that take additional information into account In this paper language modeling with belief networks is discussed Examples of belief network implementations of well-known language models are given and a new model is presented that models dependencies between the content words in a sentence.

In this article we present a syntax-based translation system, called TABL (Translation using Alignment-Based Learning). It translates natural language sentences by mapping grammar rules (which are induced by the Alignment-Based Learning grammatical inference framework) of the source language to those of the target language. By parsing a sentence in the source language, the grammar rules in the derivation are translated using the mapping and subsequently, a derivation in the target language is generated. The initial results are encouraging, illustrating that this is a valid machine translation approach.

In this paper, a natural language interface is presented which consists of the intelligent mechanisms of human identification, speech recognition, word and command recognition, command syntax and result analysis, command safety assessment, technological process supervision as well as human reaction assessment. In this paper, a review is carried out of selected issues with regards to recognition of speech commands in natural language given by the operator of the technological device. A view is offered of the complexity of the recognition process of the operator's words and commands using neural networks made up of a few layers of neurons. The paper presents research results of speech recognition and automatic recognition of commands in natural language using artificial neural networks.

In this paper, we present an empirical study that utilizes morph-syntactical information to improve translation quality. With three kinds of language pairs matched according to morph-syntactical similarity or difference, we investigate the effects of various morpho-syntactical information, such as base form, part-of-speech, and the relative positional information of a word in a statistical machine translation framework. We learn not only translation models but also word-based/class-based language models by manipulating morphological and relative positional information. And we integrate the models into a log-linear model. Experiments on multilingual translations showed that such morphological information as part-of-speech and base form are effective for improving performance in morphologically rich language pairs and that the relative positional features in a word group are useful for reordering the local word orders. Moreover, the use of a class-based n-gram language model improves performance by alleviating the data sparseness problem in a word-based language model.

A new method for information retrieval based on relative entropy with different smoothing methods has been presented in this paper. The method builds a query language model and document language models respectively for the query and the documents. We rank the documents according to the relative entropies of the estimated document language models with respect to the estimated query language model. While estimating a document language, the efficiency of the smoothing method is considered, we select three popular and relatively efficient methods to smooth the document language model. The feedback documents are used to estimate a query model by the approach that we assume that the feedback documents are generated by a combined model in which one component is the feedback document language model and the other is the collection language model. Experimental results show that the method is effective and performs better than the basic language modeling approach.

Over the past 10-15 years, the influence of methods from machine learning has transformed the way that research is done in the field of natural language processing. This talk will begin by covering the history of this transformation. In particular, learning methods have proved successful in producing stand-alone text-processing components to handle a number of linguistic tasks. Moreover, these components can be combined to produce systems that exhibit shallow text-understanding capabilities: they can, for example, extract key facts from unrestricted documents in limited domains or find answers to general-purpose questions from open-domain document collections. I will briefly describe the state of the art for these practical text-processing applications, focusing on the important role that machine learning methods have played in their development. The second part of the talk will explore the role that natural language processing might play in machine learning research. Here, I will explain the kinds of text-based features that are relatively easy to incorporate into machine learning data sets. In addition, I'll outline some problems from natural language processing that require, or could at least benefit from, new machine learning algorithms.

A new method for information retrieval which is on the basis of language model with relative entropy and feedback is presented in this paper. The method builds a query language model and document language models respectively for the query and the documents. We rank the documents according to the relative entropies of the estimated document language models with respect to the estimated query language model. The feedback documents are used to estimate a query model by the approach that we assume that the feedback documents are generated by a combined model in which one component is the feedback document language model and the other is the collection language model. Experimental results show that the method is effective for feedback documents and performs better than the basic language modeling approach. The results also indicate that the performance of the method is sensitive to both the smoothing parameters and the interpolation coefficients used to estimate the values of the language models.

In language engineering, language models are employed in order to improve system performance. These language models are usually N-gram models which are estimated from large text databases using the occurrence frequencies of these N-grams. An alternative to conventional frequency-based estimation of N-gram probabilities consists on using neural networks to this end. In this paper, an approach to language modeling with a hybrid language model is presented as a linear combination of a connectionist N-gram model, which is used to represent the global relations between certain linguistic categories, and a stochastic model of word distribution into such categories. The hybrid language model is tested on the corpus of the Wall Street journal processed in the Penn Treebank project.

Even if n-grams were proved to be very powerful and robust in various tasks involving language models, they have a certain handicap that the dependency is limited to very short local context because of the Markov assumption. This article presents an improved cache based approach to Chinese statistical language modeling. We extend this model by introducing the Chinese concept lexicon into it. The cache of the extended language model contains not only the words occurred recently but also the semantically related words. Experiments have shown that the performance of the adaptive model has been improved greatly.

In the probabilistic model of text categorization, we assume that terms are characterized by their statistical distribution of tf-idf metrics. However, we feel that classical tf-idf metrics may not be the best method solution for information retrieval and text categorization. We explored a language modeling approach with term-specific weighting method to improve the performance of text categorization system. To make our method comparable to the previous approaches, we performed an experiment and compared it to basic models. Term-specific language modeling approach to text categorization problem significantly outperformed the baseline model on each point of the evaluation.

This paper describes development of a large vocabulary continuous speaker independent speech recognition system for Estonian. Estonian is an agglutinative language and the number of different word forms is very large, in addition, the word order is relatively unconstrained. To achieve a good language coverage, we use pseudo-morphemes as basic units in a statistical trigram language model. To improve language model robustness, we automatically find morpheme classes and interpolate the morpheme model with the class-based model. The language model is trained on a newspaper corpus of 15 million word forms. Clustered triphones with multiple Gaussian mixture components are used for acoustic modeling. The system with interpolated morpheme language model is found to perform significantly better than the baseline word form trigram system in all areas. The word error rate of the best system is 27.7% which is a 10.0% absolute improvement over the baseline system.

An essential element of any speech recognition system is the language model. A language model attempts to identify and make use of the regularities in natural language to better define language syntax for easier recognition. One major obstacle in speech recognition is the variability and uncertainty of message content. This coupled with inherent noise distortion and losses that occur in speech emphasize the need for a good language model. This paper describes the work done in generation of language model for Tamil speech recognition system. From the study the performance of Morpheme based Language model is better compared to other models tried for Tamil speech recognizer.

In this work we obtain robust category-based language models to be integrated into speech recognition systems. Deductive rules are used to select linguistic categories and to match words with categories. Statistical techniques are then used to build n-gram Language Models based on lexicons that consist of sets of categories. The categorization procedure and the language model evaluation were carried out on a task-oriented Spanish corpus. The cooperation between deductive and inductive approaches has proved efficient in building small, reliable language models for speech understanding purposes.

This paper describes the work developed in the creation of language models for a continuous speech recognition system for the Portuguese language. First we discuss the process we use to create and update a text corpus based on newspaper editions collected from the Web from which we were able to generate N-gram language models. We also present the procedure we use to improve those models for a Broadcast News (BN) recognition task by interpolating them with a BN transcriptions based language model. Finally the paper details a method used to generate morpheme-based language models.

We present a new type of language model -- variable length language model (VLLM) whose length is non-deterministic on the base of 5-gram combined model brought forward previously. Its main advantage lies in that it captures the function of 5-gram combined model and reflects the structural feature of every line in test text as well. Compared to previous language model, the VLLM makes use of current result to determine which kind of language model should be used next and realizes the automatic choice of language model that is always constant before. VLLM also resolves the problem when punctuation marks appear. Based on those improvements, we make experiments and get encouraging result.

Sign language is the language used by the deaf, which is a comparatively steadier expressive system composed of signs corresponding to postures and motions assisted by facial expression. The objective of sign language recognition research is to "see" the language of deaf. The integration of sign language recognition and sign language synthesis jointly comprise a "human-computer sign language interpreter", which facilitates the interaction between deaf and their surroundings. Considering the speed and performance of the recognition system, Cyberglove is selected as gesture input device in our sign language recognition system, Semi-Continuous Dynamic Gaussian Mixture Model (SCDGMM) is used as recognition technique, and a search scheme based on relative entropy is proposed and is applied to SCDGMM-based sign word recognition. Comparing with SCDGMM recognizer without searching scheme, the recognition time of SCDGMM recognizer with searching scheme reduces almost 15 times.

The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.

This paper describes the development of a video-based continuous sign language recognition system using Hidden Markov Models (HMM). The system aims for automatic signer dependent recognition of sign language sentences, based on a lexicon of 52 signs of German Sign Language. A single colour video camera is used for image recording. The recognition is based on Hidden Markov Models concentrating on manual sign parameters. As an additional component, a stochastic language model is utilised, which considers uni- and bigram probabilities of single and successive signs. The system achieves an accuracy of 95% using a bigram language model.

High accuracy speech recognition requires a language model, to specify what word sequences are possible or at least likely. Standard n-gram language models for speech recognition ignore linguistic structures, but more linguistically sophisticated language models are possible. Unification grammars are widely used in natural languageand these can be compiled into non-left-recursive context-free grammars that can then be used in realtime speech recognizers by dynamically expanding them into state-transition networks. A hybrid language model incorporating both a unification grammar and n-gram statistics has been shown to increase speech recognition accuracy. Probabilistic context-free grammars and probabilistic unification grammars are also possible.

The interest in using Finite-State Models in a large variety of applications is recently growing as more powerful techniques for learning them from examples have been developed. Language Understanding can be approached this way as a problem of language translation in which the target language is a formal language rather than a natural one. Finite-state transducers are used to model the translation process, and are automatically learned from training data consisting of pairs of natural-language/formal-language sentences. The need for training data is dramatically reduced by performing a two-level learning process based on lexical/phrase categorization. Successful experiments are presented on a task consisting in the “understanding” of Spanish natural-language sentences describing dates and times, where the target formal language is the one used in the popular Unix command “at”.

Identification of the language of documents has traditionally been accomplished using dictionaries or other such language sources. This paper presents a novel algorithm for identifying the language of documents using much less information about the language than traditional methods. In addition, if no information about the language of incoming documents is known, the algorithm groups the documents into language groups, despite the deficit of language knowledge. The algorithm is based on the vector space model of information retrieval and uses a matrix projection operator and the singular value decomposition to identify terms that distinguish between languages. Experimental results show that the algorithm works reasonably well.

The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses constructive ordinals to bound the number of mind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate of the number of mind changes it will make before converging to a correct hypothesis for languages in the class being learned. Recently, this measure, which also suggests the difficulty of learning a class of languages, has been used to analyze the learnability of rich classes of languages. Jain and Sharma have shown that the ordinal mind change complexity for identification from positive data of languages formed by unions of up to n pattern languages is ωn. They have also shown that this bound is essential. Similar results were also established for classes definable by length-bounded elementary formal systems with up to n clauses. These later results translate to learnability of certain classes of logic programs.

In this paper, we study selection criteria for the use of word trigger pairs in statistical language modeling. A word trigger pair is defined as a long-distance word pair. To select the most significant trigger pairs, we need suitable criteria which are the topics of this paper. We extend a baseline language model by a single word trigger pair and use the perplexity of this extended language model as selection criterion. This extension is applied to all possible trigger pairs, the number of which is the square of the vocabulary size. When a unigram language model is applied as baseline model, this approach produces the mutual information criterion used in [7, 11]. The more interesting case is to use this criterion in the context of a more powerful model such as a bigram/trigram model with a cache. We study different variants of including word trigger pairs into such a language model. This approach produced better word trigger pairs than the conventional mutual information criterion. When used on the Wall Street Journal corpus, the trigger pairs selected reduced the perplexity of a trigram/cache language model from 138 to 128 for a 5-million word training set and from 92 to 87 for a 38-million word training set.

Many corpus-based methods for natural language processing are based on supervised training, requiring expensive manual annotation of training corpora. This paper investigates reducing annotation cost by sample selection. In this approach, the learner examines many unlabeled examples and selects for labeling only those that are most informative at each stage of training. In this way it is possible to avoid redundantly annotating examples that contribute little new information. The paper first analyzes the issues that need to be addressed when constructing a sample selection algorithm, arguing for the attractiveness of committee-based selection methods. We then focus on selection for training probabilistic classifiers, which are commonly applied to problems in statistical natural language processing. We report experimental results of applying a specific type of committee-based selection during training of a stochastic part-of-speech tagger, and demonstrate substantially improved learning rates over complete training using all of the text.

This paper introduces the notion of characteristic examples and shows that the notion contributes to language learning in polynomial time. A characteristic example of a language L is an element of L which includes, in a sense, sufficient information to represent L. Every context-free language can be divided into a finite number of languages each of which has a characteristic example and it is decidable whether or not a context-free language has a characteristic example. We present an algorithm that learns parenthesis languages using membership queries and characteristic examples. Our algorithm runs in time polynomial in the number of production rules of a minimal parenthesis grammar and in the length of the longest characteristic example.

Higher-order assembly language (HOAL) generalizes combinator-based target languages by allowing free variables in terms to play the role of registers. We introduce a machine model for which HOAL is the assembly language, and prove the correctness of a compiler from a tiny language into HOAL. We introduce the notion of a λ-representation, which is an abstract binding operation, show how some common representations of procedures and continuations can be expressed as λ-representations. Last, we prove the correctness of a typical procedure-calling convention in this framework.