Program

Location

Room R6
Building R
Tilburg University

A hybrid evolutionary algorithm for inductive logic programming

Federico Divina
Computational Linguistics and AI
Tilburg University

Learning from examples in First Order Logic (FOL), also known as inductive Logic Programming (ILP) constitutes a central topic in Machine Learning, with relevant applications to problems in complex domain, like natural language and molecular computational biology. Learning can be viewed as a search problem in the space of all possible hypotheses. Given a FOL description language used to express possible hypotheses, background knowledge, a set of positive examples and a set of negative examples, one has to find a hypothesis which covers all positive examples and none of the negative ones. This problem is NP-hard, even if the language to represent hypotheses is propositional logic. When FOL hypotheses are used the complexity of searching is combined with the complexity of evaluating hypotheses.

Learning first-order hypotheses is a hard task, due to the huge search space one has to deal with. The approach used by the majority of ILP systems tries to overcome this problem by using specialized search strategies, like the top-down and the inverse resolution mechanism. However, the greedy selection strategies adopted for reducing the computational effort, render techniques based on this approach often incapable of escaping from local optima. An alternative approach is offered by Evolutionary Algorithms (EAs). EAs have proved to be successful in solving comparatively hard optimization problems, as well as problems like ICL.

The stochastic operators used by EAs render them capable of escaping from local optima, giving them greater exploration power than standard approaches to ILP. However this latter characteristic of EAs is also responsible for their rather poor performance on learning tasks which are easy to tackle by algorithms that use specialized search strategies. These observations suggest that the two approaches above described, i.e., standard ILP strategies and EAs, are applicable to partly complementary classes of learning problems. More important, they indicate that a system incorporating features from both approaches could profit from the different bents of the approaches.

In this talk I will present the ECL system. ECL is a hybrid EA for solving ILP problems. ECL evolves hypotheses by optimizing a single fitness function that takes into consideration the accuracy of the hypotheses being evolved. ECL uses domain knowledge in some operators and for this reason is a hybrid EA. ECL has been proved successfully in solving many ILP problems.

Memory-based Classification of Proper Names in Norwegian

Anders Nøklestad
Department of Linguistics
University of Oslo

Automatic classification of proper names into semantic categories (Named Entity Recognition, or NER) is an important task, because it provides valuable information to other language technology tasks such as information extraction and machine translation.

In my talk, I will present a Named Entity recogniser for Norwegian that uses memory-based learning with TiMBL for classification (but not for identification) of proper names. The recogniser has been developed as part of a Scandinavian NER project called Nomen Nescio, which has produced NE recognisers for Danish and Swedish in addition to Norwegian. The recognisers classify proper names into one of the categories Person, Organisation, Location, Event, Work of Art, or Other (miscellaneous).

In my work, I have tested the effect of various features, ranging from simple pattern matching features to linguistically informed features such as syntactic relationships between a name and other words in the sentence. I have run the classifier with the different feature weighting schemes provided by TiMBL, and with various values of k for the k-nearest neighbour classifier. Regardless of parameter settings, the MBL-based classifier outperforms both a rule-based classifier and a (non-optimised) maximum entropy-based classifier that has been trained on the same feature set.

The best parameter setting yields classification accuracies of 83.2% using cross-validation and 90.1% using leave-one-out testing. I will suggest an explanation for the large difference between these numbers, indicating that leave-one-out testing might not be appropriate for this task. I will also have a look at an interesting relationship between the number of features used and the optimal value of k.

A computational model of sentence and story comprehension

Stefan Frank
NICI
Katholieke Universiteit Nijmegen

When an event or situation is experienced, a mental representation of the event may be formed in the mind of the experiencer. Such a representation will not have a linguistic or propositional form. Several recent experiments have shown that reading a sentence that describes an event eventually leads to a similar, non-linguistic mental representation. In fact, the successful construction of such a representation can be viewed as the hallmark of comprehension.

Nevertheless, most models of sentence and text comprehension are only concerned with linguistic or propositional forms. In this talk, I shall first argue that such models are not models of comprehension at all. Next, I present the Distributed Situation Space model, which simulates the process of inferencing during story comprehension. The input representations used by this model are "situational" instead of "propositional", that is, they encode a story statement's relation to the model's experience with the world, instead of the statement's propositional structure. Finally, I will discuss the possibility of designing a model that simulates sentence comprehension. Such a model would take linguistic input (a word sequence) and convert it into a representation of the described event. A combination of the two models could read a story's words and construct an interpretation of the story.

Learning coreference resolution

Veronique Hoste
CNTS - Language Technology Group
University of Antwerp

We provide a thorough empirical study of the behaviour of two well-known machine learning techniques, viz. memory-based learning and rule induction on the task of coreference resolution. Applied to this specific task, we determine which factors contribute to the success or failure of a machine learning experiment. We consider the effect of algorithm bias, feature selection, algorithm parameter optimization, the combined variation of both and the effect of sample selection on the performance of both learning techniques. On the basis of results on the MUC-6 coreference resolution data sets, we show that the initial differences between the two learning techniques are easily outruled, or even reversed, when taking into account all these factors.

We also introduce the first coreferentially annotated corpus of Dutch texts.

How efficient is speech?

Rob van Son
Institute of Phonetic Sciences/ACLC, University of Amsterdam

Speech is considered an efficient communication channel. This implies that the organization of utterances is such that more speaking effort is directed towards important parts than towards redundant parts. Based on a model of incremental word recognition, the importance of a segment is defined as its contribution to word-disambiguation. This importance is measured as the segmental information content, in bits. On a labeled Dutch speech corpus it is then shown that crucial aspects of the information structure of utterances partition the segmental information content and explain 90% of the variance. Two measures of acoustical reduction, duration and spectral center of gravity, are correlated with the segmental information content in such a way that more important phonemes are less reduced. It is concluded that the organization of reduction according to conventional information structure does indeed increase efficiency.

Augmentative and Alternative Communication for Dysarthric Speakers

Maria Wolters
University of Newcastle-upon-Tyne and Queen Margaret University College, Edinburgh

As the population ages, degenerative diseases of the nervous system such as Parkinson's Disease (PD) become more and more common. These diseases affect not only the movement of the limbs, but also speech. As Parkinson's Disease progresses, the patients become dysarthric: They have problems with executing the movements of the articulators (tongue, lips, jaw). The challenge for speech technologists, computer scientists, and engineers is: How can we help people afflicted by such a disease to communicate successfully? This is the key issue that will be explored in the talk. We will concentrate on three questions:

1. What problems do dysarthric people with a degenerative diseases of the nervous system face when they try to communicate?
2. How can augmentative and alternative communication strategies help?
3. How can speech technology help?

Arabic morphology generation: A two-step strategy

Abdelhadi Soudi
ENIM, Morocco / DFKI, Germany

The non-concatenative morphology typical of Arabic has spurred the development of sophisticated formalisms and computational engines, as well as produced brute force approaches. In this talk, we present a computational model that handles Arabic morphology generation using a two-step strategy that separates the infixation changes undergone by an Arabic stem from the processes of prefixation and suffixation. Our model is based on discrimination trees and transformational rules. The Lexeme-based Morphology framework provides a theoretical justification for our representation of Arabic morphology, which focuses on stems in contrast to the root+pattern+vocalism approaches followed by other researchers. The current implementation has been tested on verbal morphology including weak verbs and various types of strong verbs and nouns including nouns with a broken plural pattern and sound nouns. The Arabic morphology generation system has also been interfaced with the KANT Interlingua-based MT system, developed at Carnegie Mellon's LTI.

Lambda Grammars

Reinhard Muskens
Computational Linguistics and AI
Tilburg University

The example grammar I will consider has 3 dimensions: 1) dominance and precedence, 2) semantics, and 3) features. A *sign* will be a triple of lambda terms, one for each dimension. I will show how in dimension 1) the modalities of the multimodal Lambek Calculus can be obtained. (The lambda terms in dimension 1) are close to Curry's 1961 `functors'.) Dimension 2) will be a streamlined form of Montague semantics; and dimension 3) will consist of lambda terms over Johnson's simple first-order feature language. A grammar in its simplest form will consist of a set of lexical signs and a specification of a set of combinators. Combinators combine signs by a process of `pointwise application.'

In the talk I will also point out some obvious affinities with Lexical-Functional Grammar.

Sentence Summarization for Automatic Subtitling

Erik F. Tjong Kim Sang
CNTS - Language Technology Group
University of Antwerp

We will describe three approaches for sentence summarization: a learning approach based on parallel corpora, a method which relies on hand-made deletion rules and method for automatically extracting paraphrases from raw text. We will evaluate the results of the first two methods applied to a summarization task and discuss how they can be improved.

Machine Learning for Shallow Interpretation of User Utterances in Spoken Dialogue Systems

Piroska Lendvai
ILK Research Group
Tilburg University

In recent years there has been an increased interest in using statistical and machine learning approaches for the processing of user utterances in spoken dialogue systems. Dialogue act classification is an example for which this approach has been relatively successful. The purpose of this task is to determine what the underlying intention of a user utterance is (e.g., suggest, request, reject, etc.).

Another task for which such approaches have been applied is automatic problem detection. Given that current speech recognizers may still make recognition errors, it is important to detect these problems as soon as possible. Various researchers have shown that users signal problems when they become aware of them and that it is possible to detect communications problems with a high accuracy on the basis of such user signals.

Finally, for processing and understanding spoken user utterances, statistical techniques have also proven their usefulness, either in combination with rule-based grammars or without them.

We investigate to what extent automatic learning techniques can be used for shallow interpretation of user utterances in spoken dialogue systems when the task involves simultaneous dialogue act classification, shallow understanding and problem detection. For this purpose we train both a rule-induction and a memory-based learning algorithm on a large set of surface features obtained by affordable means from an annotated corpus of Dutch human-machine dialogues. Using a pseudo-exhaustive search, the parameters of both algorithms are optimized.

The shallow interpretation task turns out to be a difficult one, partly since there are 96 types of user answers. Exact results on algorithm performances will be reported in the talk.

Piroska Lendvai has been an AiO at Tilburg University for the past two years, working on her project "Learning to Communicate: Machine Learning of Dialogue Strategies". The talk illustrates the latest research direction her project has taken, co-operating with her two project leaders Antal van den Bosch and Emiel Krahmer.

Last update: March 26 2003