Freiburg, Leuven, and Friends 2005

Abstracts

Gemma Casas Garriga: Galois connections for mining structured objects [download]

We will revisit, by means of examples, the application of Galois connections for the problem of mining structured objects. Starting from the most basic case, the mining of ordered data, some primary results within the framework will be presented: fromt he identification of plain subsequences called stable, to the extraction of closed partial orders summarizing the data.

Stefan Raeymaekers: Information extraction tool using (k,l)-contextual tree automata

We present a graphical tool for information extraction from web-pages. This tool is based on (k,l)-contextual tree automata, which are an extension of k-contextual string automata. We try to give an intuitive introduction to these languages and give an overview of the inference algorithms used in the tool.

Siegfried Nijssen: On the connections between frequent pattern mining and ROC spaces

On the connections between frequent pattern mining and ROC spaces.

Tadeusz Pietraszek: Optimizing Abstaining Classifiers using ROC Analysis

Classifiers that abstain from classification in certain cases can significantly reduce the misclassification cost. However, the parameters for such abstaining classifiers are often set in an ad-hoc manner. In my talk I will present a method to build a particular type of abstaining binary classifier and to optimize the selection of its parameters using ROC analysis. The method optimizes the selection of parameters in the following three models: cost-based, bounded and expected improvement. To make this method practical I show how it can be used with a ROC building algorithm and cross-validation to effectively reduce misclassification cost in real classification systems, and test it on several UCI KDD datasets. I would also like to briefly introduce "AlertRank" for the last part of the talk. "AlertRank" is a new approach to handling intrusion detection alerts using link mining algorithms.

Andreas Karwath: Learing Chemical Reactions

Toon Calders: NDI: a condensed representation for frequent sets

Recent studies on frequent itemset mining algorithms resulted in significant performance improvements. In the early days, the size of the database and the generation of a reasonable amount of frequent itemsets were considered the most costly aspects of frequent itemset mining, and most energy went into minimizing the number of scans through the database. However, if the minimal support threshold is set too low, or the data is highly correlated, the number of frequent itemsets itself can be prohibitively large. To overcome this problem, recently several proposals have been made to construct a concise representation of the frequent itemsets, instead of mining all frequent itemsets. We present the non-derivable itemsets (NDI) as a condensed representation for the frequent itemsets. The NDI representation is based on a sound and complete deduction mechanism for the support of itemsets that allows for removing redundant itemsets. In my talk I will focus on the deduction rules for support and the NDI representation.

Bjoern Bringmann: Frequent Hypergraph Mining [download]

The problem of frequent hypergraph mining is introduced. It generalizes the mining of frequent item-sets, trees, and graphs in a natural manner. We study the computational properties of various variants of the frequent hypergraph mining problem. In particular, we present practically relevant problem classes for which frequent hypergraph mining can be solved in incremental-polynomial time. For some of these classes we show how frequent hypergraph mining can be mapped onto graph mining and item-set mining problems. Our experimental results in the domain of citation analysis show the potential of the framework on problems that have no natural representation as an ordinary graph.

Daan Fierens: Learning Logical Probability Trees [download]

Several approaches for learning (propositional or relational) probability trees have been proposed in the literature. We empirically investigate the usefulness of the different approaches in a relational context by means of experiments with the first order logical decision tree learner Tilde.

Hendrik Blockeel: Multi-instance decision trees

Several attempts have been made to upgrade decision tree learning to the multi-instance setting. We argue that up till now, none of them are entirely satisfactory. We present a novel approach to multi-instance tree learning that avoids some of the previous approaches' shortcomings.

Bjoern Bringmann and Albrecht Zimmermann: Tree2: Patterns and Decisions

We plan to present some preliminary work on subtree mining for decision tree formation.

Werner Uwents: Relational learning with neural networks

Neural networks are commonly regarded as a propositional learning method. However, many learning problems are relational problems and they can not be represented in a propositional way without loss of information. Using neural networks for learning in this context requires an adaptation of the standard feedforward neural network to process relational information. In this presentation, such an extension of neural networks for relational learning will be proposed and the results of some experiments will be discussed.

Sunna Torge: Towards Learning Stochastic Logic Programs from Proof Banks

Stochastic logic programs (SLP) combine ideas from probabilistic grammars with the expressive power of definite clause logic; as such they can be considered as an extension of probabilistic context-free grammars. Motivated by an analogy with learning tree-bank grammars, we study how to learn stochastic logic programs from proof-trees.

Thomas Gaertner: On Multi-Kernel Methods

The questions of how to best combine different kernels and how to use unlabelled data in kernel methods are two very important questions that have so far not been tackled together. In contrast to other approaches to solve either problem alone, in this presentation I will propose multi-kernel methods as a new class of learning algorithms that combine different kernels and minimise the regularised risk at the same time. For one particular multi-kernel method, so-called co-RLSR, the solution can be found in time O(n2 m) where m>n is the amount of unlabelled data and $n$ is the amount of labelled data.

Tamas Horvath: Cyclic Pattern Kernels Revisited

Abstract: The cyclic pattern kernel (CPK) is a powerful graph kernel based on the patterns formed by the simple cycles of a labeled graph. In a previous work, we proposed a method for computing CPK. This method is restricted to graphs containing polynomial number of simple cycles. In this talk, we present two approaches relaxing this limitation. We first show that for graphs of bounded treewidth, CPK can be computed in time polynomial in the number of cyclic patterns, which in turn can be exponentially smaller than that of simple cyles. We then propose an alternative CPK based on the set of relevant cycles which is known to be enumerable with polynomial delay and its cardinality is typically only cubic in the number of vertices. Empirical results on the NCI-HIV dataset indicate that there is no significant difference in predictive performance between CPK based on simple cycles and that based on relevant cycles.

Koen Deforche: Applying Bayesian network learning to learn HIV resistance pathways

Fabian Guiza: Data Mining for predicting outcome in critically ill patients

Presentation of some first results obtained for the development of predictive models for relevant conditions occurring in critically ill patients (Intensive Care Unit patients). The intention being that the obtain models remain reliable and user-friendly, so that they can be used as a support for good clinical judgment.

Martijn van Otterlo: The Logic behind Dynamic Programming [download]

In recent years some "structured" forms of dynamic programming techniques have appeared in the literature. Although different representational formats are used (e.g. propositional trees, DBNs, continuous hyperplanes and full first-order logic), the underlying mechanisms show strong similarities. One of the main challenges is the efficiency of various data structures and operations needed to do structural Bellman backups.
In this talk we present a general scheme for relational dynamic programming, based on the previously introduced Relational Bellman Backup Operator: ReBel. We identify a number of necessary operations in this general scheme and we show how we can make use of standard techniques from (inductive) logic programming to do computations much more efficiently.
A general question is raised about how much of either dynamic programming techniques or logic programming techniques can be used or are even necessary for relational dynamic programming.

Jan Ramon: Convergence of reinforcement learning using a decision tree learner for function approximation [download]

In this work, we propose conditions under which learning a Q-function using decision trees for function approximation is guaranteed to converge to the optimal policy in the limit, using only a constant more storage space than is needed to store the decision tree. We analyze different factors that influence the efficiency of the proposed algorithm, and in particular study the efficiency of different concept languages. We illustrate the approach with some experiments.

Robby Goetschalckx: Reinforcement Learning with Metric State Aggregation [download]

Even though it has been proven that Q-learning for Markov decision processes (MDP) will converge to the optimal solution, for complicated domains it will take a huge amount of memory and time. State aggregation tries to solve this by treating different states as one aggregate state. However when using state aggregation, the markov property is lost and the proof of convergence to the optimal policy is not valid any more.
In this paper we prove bounds on the error of the policy Q-learning returns when a state aggregation is used, given that certain conditions on a metric on the state space are satisfied. We give some examples and give an outline of a instance-based learning algorithm based on our theorem.

Karl Tuyls: An Evolutionary Game Theoretic Perspective on Multi-Agent Reinforcement

In this talk we tackle Reinforcement Learning in Multi-Agent Systems from an Evolutionary Game Theoretic point of view. Modeling learning agents in the context of Multi-Agent Systems requires an adequate understanding of their dynamic behaviour. Therefore we revise Evolutionary Game Theory.
Evolutionary Game Theory provides a dynamics which describes how strategies evolve over time. Borgers et al. and Tuyls et al. have shown how classical Reinforcement Learning techniques such as Cross learning and Q-learning relate to the Replicator Equations from Evolutionary Game Theory. This provides a better understanding of the learning process. However, we believe Evolutionary Game Theory can do more. In recent work, we showed how this link can be exploited to be used in cooperation with the COllective INtelligence (COIN) framework of Wolpert et al. In this talk we show how this link can explain the added value of COIN and how good parameter values can be predicted from this perspective.

Tom Croonenborghs: On Intelligent Agents in Relational Reinforcement Learning [download]

A common approach to learn the optimal policy in (relational) reinforcement learning is indirectly by learning the value or a quality function to impose an order on the possible actions in a certain state.
In this work, we propose some methods where the learning agent does more than just maximizing his quality function. We would like a really intelligent agent, who can reason about his world and his goals in this world. In our approach partial world models are being learned, which are used to do Bayesian inference or perform a state/value decomposition.