Ebook: STAIRS 2010

The Fifth Symposium for Artificial Intelligence Researchers (STAIRS 2010) took place in conjunction with the 19th European Conference on Artificial Intelligence (ECAI 2010), as well as the Sixth Conference on Prestigious Applications of Intelligent Systems (PAIS 2010), in Lisbon, Portugal, 16–20 August 2010.

STAIRS is an international meeting intended to support AI researchers from all countries at the beginning of their career: PhD students or those who have held a PhD for less than one year. STAIRS offers doctoral students and young post-doctoral AI fellows a unique and valuable opportunity to gain experience in presenting their work in a supportive scientific environment, where they can obtain constructive feedback on the technical content of their work as well as advice on how to present it, and where they can also establish contacts with the broader European AI research community.

Papers selected by the program committee through a peer-review process were presented at the conference. The topics covered a broad spectrum of subjects in the field of AI: learning and classification, ontologies and the semantic web, agent programming and planning, logic and reasoning, economic approaches, games, dialogue systems, user preferences and recommender systems.

This book contains revised versions of most of the peer-reviewed papers presented at the conference. The final versions of the papers were submitted after the conference, giving the authors an opportunity to take account of any feedback they received during the conference, and improve their contributions accordingly.

I would like to thank the ECAI chairs for supporting STAIRS and for creating a perfect environment for it, as well as the local organisers and the STAIRS participants. Last but not least, I am grateful to the STAIRS program committee for their work in selecting papers and providing feedback to the authors. They were:

Natasha Alechina, Josep Lluis Arcos, Yoram Bachrach, Sylvain Bouveret, Rui Camacho, Hubie Chen, Fabio Gagliardi Cozman, Claudia d'Amato, Eric de la Clergerie, Sarah Jane Delany, Clare Dixon, Esra Erdem, Daan Fierens, Chiara Ghidini, Wojtek Jamroga, Ian Kash, Udo Kruschwitz, Oliver Kutz, Nicolas Lachiche, Nada Lavrac, Francesca Alessandra Lisi, Weiru Liu, Alessio Lomuscio, Peter Lucas, Peter McBurney, Elena Montiel-Ponsoda, Eva Onaindia, Nardine Osman, Hector Palacios, Jeff Z. Pan, Henri Prade, Marta Sabou, David Schlangen, Carles Sierra, Matthijs Spaan, Kostas Stergiou, Heiner Stuckenschmidt, Anni-Yasmin Turhan, Menno van Zaanen, Kalliopi Zervanou, Wamberto Vasconcelos, Stefan Woelfl

Bergen, September 2010,

Thomas Ågotnes

Subgroup discovery is concerned with finding subsets of a population whose class distribution is significantly different from the overall distribution. Previously subgroup discovery has been predominantly investigated under the propositional logic framework. This paper investigates multi-class subgroup discovery in an inductive logic programming setting, where subgroups are defined by conjunctions in first-order logic. We present a new weighted covering algorithm, inspired by the Aleph first-order rule learner, that uses seed examples in order to learn diverse, representative and highly predictive subgroups that capture interesting patterns across multiple classes. Our approach experimentally shows considerable and statistically significant improvement of predictive power, both in terms of accuracy and AUC, and theory construction time, by considering fewer hypotheses.

This paper introduces the notion of prototypicality in Ontology Engineering. Three kinds of prototypicality are considered: a concept can be more or less representative of its super-concept (conceptual prototypicality); a term can be more or less associated to a concept (lexical prototypicality); an instance can be more or less representative of its concept (instance prototypicality). Prototypicalities are modeled as order relations which allow to modulate links between concepts, terms and instances within an ontology. To calculate prototypicality gradients used to quantify these orders, we advocate a specific method which is based on all the components of an ontology (i.e. concepts, properties and instances) and a corpus. This paper also underlines the relevance of prototypicality for improving the efficiency of Ontology Engineering processes, in particular Ontology Personalization and Semantic-based Information Retrieval.

The paper describes a new method that permits a computer to listen to, and follow, live music in real-time, by analysing the incoming audio stream and aligning it to a symbolic representation (e.g, score) of the piece(s) being played. In particular, we present a multi-level music matching and tracking algorithm that, by continually updating and evaluating multiple high-level hypotheses, effectively deals with almost arbitrary deviations of the live performer from the score – omissions, forward and backward jumps, unexpected repetitions, or (re-)starts in the middle of the piece. Also, we show that additional knowledge about the structure of the piece (which can be automatically computed by the system) can be used to further improve the robustness of the tracking process. The resulting system is discussed in the context of an automatic page-turning device for musicians, but it will be of use in a much wider class of scenarios that require reactive and adaptive musical companions.

GOLOG is an agent programming language designed to represent complex actions and procedures in the situation calculus. In this paper we apply relaxation-based heuristics – often used in classical planning – to find (near) optimal executions of a GOLOG program. In doing so we present and utilise a theory of relaxed regression for the approximate interpretation of a GOLOG program. This relaxed interpreter is used to heuristically evaluate the available choices in the search for a program execution. We compare the performance of our heuristic interpreter (in terms of the quality of executions found) with a traditional depth-first search interpreter and one guided by a greedy heuristic without a look-ahead on three domains: spacecraft control, mine operations planning, and task scheduling.

Partially Observable Markov Decision Processes have gained an increasing interest in many research communities, due to sensible improvements of their optimization algorithms and of computers capabilities. Yet, most research focus on optimizing either average accumulated rewards (AI planning) or direct entropy (active perception), whereas none of them matches the rewards actually gathered at execution. Indeed, the first optimization criterion linearly averages over all belief states, so that it does not gain best information from different observations, while the second one totally discards rewards. Thus, motivated by simple demonstrative examples, we study an additive combination of these two criteria to get the best of reward gathering and information acquisition at execution. We then compare our criterion with classical ones, and highlight the need to consider new hybrid non-linear criteria, on a realistic multi-target recognition and tracking mission.

In this paper, we present a generative algorithm to learn Markov Logic Network (MLN) structures automatically, directly from a training dataset. The algorithm follows a bottom-up approach by first heuristically transforming the training dataset into boolean tables, then creating candidate clauses using these boolean tables and finally choosing the best clauses to build the MLN. Comparisons to the state-of-the-art structure learning algorithms for MLNs in two real-world domains show that the proposed algorithm outperforms them in terms of the conditional log likelihood (CLL), and the area under the precision-recall curve (AUC).

We propose an approach to user model-based information retrieval which uses an evolutionary algorithm to learn fuzzy models of user interests and to dynamically track their changes as the user interacts with the system. The system is ontology-based, in the sense that it considers concepts behind terms instead of simple terms.

The approach has been implemented in a real-world prototype newsfeed aggregator with search facilities called IFeed. Experimental results show that our system learns user models effectively. This is proved by both the convergence of the interest degrees contained in the user models population and the increase of the users' activities on the set of proposed documents.

This paper presents a vector space model approach to representing documents and queries, which considers concepts instead of terms and uses WordNet as a light ontology. This representation reduces information redundancy with respect to conventional semantic expansion techniques. Experiments carried out on the MuchMore benchmark and on the TREC-7 and TREC-8 Ad-hoc collections demonstrate the effectiveness of the proposed approach.

Multi-agent simulation provides a way to explore results from social studies and provide hints on how these results scale. One particular class of studies that is interesting to explore are economic-related studies. We developed a multi-agent system that simulates an investment game and incorporates the results from economic-related social studies into the design of the agents. We analyzed how several factors, such as trust and reputation influence the outcome of the agents in terms of distribution of wealth and total generated money.

We present and study a Modal Access Control Logic (M-ACL) to specify and reason about access control policies. We identify canonical properties of well-known access control axioms. We provide a Hilbert-style proof-system and we prove soundness, completeness and decidability of the logic. We present a sound and complete embedding of Modal Access Control Logic into First-Order Logic. We show how to use SPASS theorem prover to reason about access control policies expressed as formulas of Modal Access Control Logic, and we compare our logic with existing ones.

We investigate probabilistic propositional logic as a way of expressing and reasoning about uncertainty. In contrast to Bayesian networks, a logical approach can easily cope with incomplete information like probabilities that are missing or only known to lie in some interval. However, probabilistic propositional logic as described e.g. by Halpern [1], has no way of expressing conditional independence, which is important for compact specification in many cases. We define a logic with conditional independence formulae. We give an axiomatization which we show to be complete for the kind of inferences allowed by Bayesian networks, while still being suitable for reasoning under incomplete information.

Sokoban puzzle is very challenging problem for both humans and computers. It also illustrates differences between human and artificial intelligence – different problems are difficult for humans and for computers. Whereas algorithmic techniques for Sokoban solving have been intensively studied by previous research, factors determining difficulty for humans have not been sufficiently explained so far. We describe two methods for difficulty rating of Sokoban puzzle – a problem decomposition metric and a computational model which simulates human traversal of a state space. We evaluate these metrics on large scale data on human solving (2000 problems solved, 785 hour of problem solving activity).

In this paper we look at regular path temporal logic, RPTL, a modal logic which combines the ability to quantify over (finite) paths described by regular expressions (a property which characterises PDL) with the addition of temporal operators. The formulation of RPTL was inspired by agent programming verification considerations. In this paper we prove the decidabilty of RPTL and establish complexity bounds on the satisfiability problem for RPTL by translating it into the theory of alternating tree automata on infinite trees.

Combining term rewriting and modal logics, this paper addresses confluence and termination of rewrite systems introduced for only-knowing logics. The rewrite systems contain a rule scheme that gives rise to an infinite number of critical pairs, hence we cannot check the joinability of every critical pair directly, in order to establish local confluence. We investigate conditions that are sufficient for confluence and identify a set of rewrite rules that satisfy these conditions; however, the general confluence result makes it easier to check confluence also of stronger systems should one want additional rules. The results provide a firm logical basis for implementation of procedures that compute autoepistemic expansions.

In the area of qualitative spatial reasoning, the LR calculus (a refinement of Ligozat's flip-flop calculus) is a quite simple constraint calculus that forms the core of several orientation calculi like the Dipole calculi and the OPRA₁ calculus by introducing the left-right-dichotomy.

For many qualitative spatial calculi, algebraic closure is applied as the standard polynomial time “decision” procedure. For a long time it was believed that this can decide the consistency of scenarios of the LR calculus. However, in [8] it was shown that algebraic closure is a bad approximation of consistency for LR scenarios: scenarios in the base relations “Left” and “Right” are always algebraically closed, no matter if those scenarios are consistent or not. So algebraic closure is completely useless here. Furthermore, in [15] it was proved that the consistency problem for any calculus with relative orientation containing the relations “Left” and “Right” is NP-hard.

In this paper we propose a new and better polynomial time approximation procedure for this NP-hard problem. It is based on the angles of triangles in the Euclidean plane. LR scenarios are translated to sets of linear inequalities over the real numbers. We evaluate the quality of this procedure by comparing it bot to the old approximation using algebraic closure and to the (exact but exponential time) Buchberger algorithm for Gröbner bases (used as a decision method).

Auctions have been used to deal with resource allocation in multi-agent systems. In some environments like service-oriented electronic markets, it is advisable to use recurrent auctions since resources are perishable and auctions are repeated over time with the same or a very similar set of agents. Recurrent auctions are a series of auctions of any kind where the result of one auction may influence the following one. As a drawback some problems do appear that could cause the market to collapse at mid-long term. Previous works have dealt with these problems by adding fairness to the auction outcomes. Those works dealt with multi-unit auctions, in which several units of an item are sold, and they do not assure that agents cannot manipulate the auctions for their own benefit. In this paper, we present new fair mechanisms that goes further. First we focus on combinatorial auctions, in which different items, and several units per item are sold in each auction, which poses additional challenges when they are recurrent. And second, the mechanisms are shown to prevent some agents' manipulation of the auction outcomes.

This ongoing research presents an alternative to the manual creation of lexical resources and proposes an approach towards the automatic construction of a lexical ontology for Portuguese. Textual sources are exploited in order to obtain a lexical network based on terms and, after clustering and mapping, a wordnet-like lexical ontology is created. At the end of the paper, current results are shown.

In this work we address the problem of monitoring the evolution of clusters, which became an important research issue in recent years due to our ability to collect and store data that evolves over time. The evolution is traced through the detection and categorization of transitions undergone by clusters' structures computed at different points in time. We adopt two main strategies for cluster characterization – representation by enumeration and representation by comprehension -, and propose the MEC (Monitor of the Evolution of Clusters) framework, which was developed along the lines of the change mining paradigm. MEC includes a taxonomy of various types of clusters' transitions, a tracking mechanism that depends on cluster representation, and a transition detection algorithm. Our tracking mechanism can be subdivided in two methods, devised to monitor clusters' transitions: one based on graph transitions, and another based on clusters' overlap. To demonstrate the feasibility and applicability of MEC we present real world case studies, using datasets from different knowledge areas, such as Economy and Education.

Usually, in argumentation, the proof-standards that are used are fixed a priori by the procedure. However decision-aiding is a context where these may be modified dynamically during the process, depending on the responses of the client. The expert indeed needs to adapt and refine its choice of an appropriate method of aggregation, so that it fits the preference model inferred from the interaction. In this paper we examine how this aspect can be handled in an argumentation-based decision-aiding framework. The first contribution of the paper is conceptual: the notion of a concept lattice based on simple properties and allowing to navigate among the different proof-standards is put forward. We then show how this can be integrated within the Carneades model while still preserving its essential properties; and illustrates our proposal with a detailed example.

Goal recognition is generally considered to follow plan recognition. The plan recognition problem is typically defined to be that of identifying which plan in a given library of plans is being executed, given a sequence of observed actions. Once a plan has been identified, the goal of the plan can be assumed to follow. In this work, we address the problem of goal recognition directly, without assuming a plan library. Instead, we start with a domain description, just as is used for plan construction, and a sequence of action observations. The task, then, is to identify which possible goal state is the ultimate destination of the trajectory being observed.

We present a formalisation of the problem and motivate its interest, before describing some simplifying assumptions we have made to arrive at a first implementation of a goal recognition system, AUTOGRAPH. We discuss the techniques employed in AUTOGRAPH to arrive at a tractable approximation of the goal recognition problem and show results for the system we have implemented.

Constraint Satisfaction Problems (CSPs) are well known models used in Artificial Intelligence. In order to represent real world systems, CSPs have been extended to Dynamic CSPs (DCSPs), which support adding and removing constraints at runtime. Some approaches to the NP-complete problem of solving CSPs use filtering techniques such as arc consistency, which also have been adapted to handle DCSPs with binary constraints. However, there exists only one algorithm targeting non-binary DCSPs (DnGAC4). In this paper we present a new algorithm DnSTR for maintaining arc consistency in DCSPs with non-binary constraints. Our algorithm is based on Simple Tabular Reduction for Table Constraints, a technique that dynamically maintains the tables of supports within the constraints. Initial results show that our algorithm outperforms DnGAC4 both for addition and removal of constraints.

It is generally assumed that all users in a dataset are equally adversely affected by data sparsity and hence addressing this problem should result in improved performance. However, although all users may be members of a sparse dataset, they do not all suffer equally from the data sparsity problem. This indicates that there is some ambiguity as to which users should be identified as suffering from data sparsity, referred to as sparse users throughout this paper, and targeted with new recommendation improvement strategies. This paper defines sparsity in terms of number of item ratings and average similarity with nearest neighbours and then goes on to look at the impact of sparsity so defined on performance. Counterintuitively, it is found that in top-N recommendations sparse users actually perform better than some other categories of users when a standard approach is used. These results are explained, and empirically verified, in terms of a bias towards users with a low number of ratings. The link between sparsity and performance is also considered in the case of predictions rather than top-N recommendations. This work provides the motivation for targeting improvement approaches towards distinct groups of users as opposed to the entire dataset.

The Banzhaf power index is a prominent measure of a player's influence for coalition formation in weighted voting games, an important class of simple coalitional games that are fully expressive but compactly representable. For the normalized Banzhaf index, Aziz and Paterson [1] show that it is NP-hard to decide whether merging any coalition of players is beneficial, and that in unanimity games, merging is always disadvantageous, whereas splitting is always advantageous. We show that for the probabilistic Banzhaf index (which is considered more natural than the normalized Banzhaf index), the merging problem is in P for coalitions of size two, and is NP-hard for coalitions of size at least three. We also prove a corresponding result for the splitting problem. In unanimity games and for the probabilistic Banzhaf index (in strong contrast with the results for the normalized Banzhaf index), we show that splitting is always disadvantageous or neutral, whereas merging is neutral for size-two coalitions, yet advantageous for coalitions of size at least three. In addition, we study the merging and splitting problems for threshold network flow games [3,4] on hypergraphs.

Microarray technology facilitates the monitoring of the expression profile of a large number of genes across different experimental conditions or tissue samples simultaneously. Microarray technology is being utilized in cancer diagnosis through the classification of the tissue samples. In this article, we have presented an integrated unsupervised technique for cancer classification. The proposed method is based on multiobjective differential fuzzy clustering of the tissue samples. In this regard, real coded encoding of the cluster centres is used and two fuzzy cluster validity indices are simultaneously optimized. The resultant set of near-Pareto-optimal solutions contains a number of non-dominated solutions. Each such solution has been improved by a novel technique based on Support Vector Machine (SVM) classification. Thereafter, the final clustering solution is produced by majority voting ensemble technique of all improved solutions. The performance of the proposed multiobjective clustering method has been compared to several other microarray clustering algorithms for three publicly available benchmark cancer data sets, viz., leukemia, Colon cancer and Lymphoma data to establish its superiority. Also statistical significance tests have been conducted to establish the statistical superiority of the proposed clustering method.