Ebook: STAIRS 2006

STAIRS 2006 is the third European Starting AI Researcher Symposium, an international meeting aimed at AI researchers, from all countries, at the beginning of their career: PhD students or people holding a PhD for less than one year.

A total of 59 papers were submitted from 22 different countries: Australia, Austria, Brazil, Canada, Czech Republic, France, Germany, Greece, India, Ireland, Italy, Japan, México, Netherlands, Serbia and Montenegro, Scotland, Slovenia, Spain, Sweden, Switzerland, UK, USA.

The areas of the submitted and accepted papers/posters ranges form traditional AI areas, such as Knowledge Representation, Machine Learning, Natural Language Processing, Constraints, Planning and Scheduling, Agents, to AI applications, such as Semantic Web, Data Clustering for medical application, E-learning.

The program committee decided to accept 20 full papers, which amounts to an acceptance rate of 33.8%, and 15 posters.

The STAIRS 2006 best paper award, sponsored by IOS, goes to Giorgos Flouris, Dimitris Plexousakis, and Grigoris Antoniou for their paper:

On Generalizing the AGM Postulate

Congratulations!

The symposium programme includes two invited talks and technical sessions in which the accepted papers and posters will be presented and discussed.

We thank the authors, the PC members and the additional reviewers for making STAIRS 2006 a high-quality scientific event. We would like also to thank EasyChair for the courtesy license of its conference management software.

STAIRS 2006 has benefited from ECAI 2006 in terms of administration support, grants, and sponsorship.

June 2006

Loris Penserini, Pavlos Peppas, Anna Perini

Traditional algorithms of machine learning implemented in cognitive architectures demonstrate lack of autonomous exploration in an unknown environment. However, the latter is one of the most distinctive attributes of cognitive behaviour. The paper proposes an approach of self-reinforcement cognitive learning combining unsupervised goal acquisition, active Markov-based goal attaining and spatial-semantic hierarchical representation within an open-ended system architecture. The novelty of the method consists in division of goals into the classes of parameter goal, invariant goal and context goal. The system exhibits incremental learning in such a manner as to allow effective transferable representation of high-level concepts.

This paper presents a formal definition of Alan. Alan is a programming language that aims to integrate both the agent-oriented and the object-oriented programming. The end is to take advantages from both the paradigms. We define the formal specification of Alan in the rewriting logic language Maude. In this respect, this paper represents the first step towards a complete formal definition of the operational semantics of Alan. This opens us the possibilty of using the wide-spectrum of formal modeling and reasoning supported by Maude: analyzing Alan programs by means of model checking, proving properties of particular Alan programs, and proving general properties of the Alan language.

We present a non-monotonic logic tailored for specifying compact autonomous agent systems. The language is a consistent instantiation of a logic based argumentation system extended with Brooks' subsumption concept and varying degree of belief. Particulary, we present a practical implementation of the language by developing a meta-encoding method that translates logical specifications into compact general logic programs. The language allows n-ary predicate literals with the usual first-order term definitions. We show that the space complexity of the resulting general logic program is linear to the size of the original theory.

In this paper we aim at giving a formal characterization of the notion of responsibility in multi-agent systems. A clearer view of responsibility is critical for regulating multiagent settings: to understand what kinds of responsibility are at stake in a given scenario can help predict system's future behaviour and improve its efficiency. However, although attempts of formal theories of responsibility are increasing, they usually reduce it to causation, while we underline the importance of a theory of responsibility before a damage could ever take place.

We propose an objective notion of responsibility, grounded upon cognitive, social, and material powers. In turn, aversive power - essential to account for antehoc responsibility - will be based on social damage, seen as reduction of one's power. Furthermore, the multiagent dimension of the phenomenon will be addressed: shared versus collective responsibility will be distinguished.

We will apply a modification of the ATEL – R* language (Alternating Time Epistemic Logic with Recall), dealing with goals and past history in order to characterize all the necessary ingredients (goals, ability, powers, awareness of strategies, damage) of multiagent responsibility in several scenarios. System validities will be given and discussed, and a brief discussion of results together with ideas for future work will conclude the paper.

In psychopathological diagnosis, a correct classification of mental retardation level is needed to choose the best treatment for rehabilitation and to assure a quality of life suitable for the patient's specific condition. In order to meet this need this paper presents a new approach that permits performing automatic diagnoses efficiently and reliably, and at the same time is an easy-to-use tool for psychotherapists. The approach is based on a computational intelligence technique that integrates fuzzy logic and genetic algorithms in order to learn from samples a transparent fuzzy rule based on a diagnostic system. Empirical tests on a database of patients with mental retardation and comparisons with established techniques showed the efficiency of the proposed approach, which also gives a great deal of useful information for diagnostic purposes.

This paper presents a tunable content-based music retrieval (CBMR) system suitable for retrieval of music audio clips. Audio clips are represented as extracted feature vectors. The CBMR system is expert-tunable by altering the feature space. The feature space is tuned according to the expert-specified similarity criteria expressed in terms of clusters of similar audio clips. The tuning process utilizes our genetic algorithm that optimizes cluster compactness. The R-tree index for efficient retrieval of audio clips is based on the clustering of feature vectors. For each cluster a minimal bounding rectangle (MBR) is formed, thus providing objects for indexing. Inserting new nodes into the R-tree is efficiently conducted because of the chosen Quadratic Split algorithm. Our CBMR system implements the point query and the n-nearest neighbors query with the O(log n) time complexity. The paper includes experimental results in measuring retrieval performance in terms of precision and recall. Significant improvement in retrieval performance over the untuned feature space is reported.

The amount of business taking place in online marketplaces such as eBay is growing rapidly. At the end of 2005 eBay Inc. reported annual growth rates of 42.5% [3] and in February 2006 received 3 million user feedback comments per day [1]. Now we are faced with the task of using the limited information provided on auction sites to transact with complete strangers with whom we will most likely only interact with once. People will naturally be comfortable with old fashioned “corner store” business practice [14], based on a person to person trust which is lacking in large-scale electronic marketplaces such as eBay and Amazon.com. We analyse reasons why the current feedback scores on eBay and most other online auctions are too positive. We introduce AuctionRules, a trust-mining algorithm which captures subtle indications of negativity from user comments in cases where users have rated a sale as positive but still voiced some grievance in their feedback. We explain how these new trust values can be propagated using a graph-representation of the eBay marketplace to provide personalized trust values for both parties in a potential transaction. Our experimental results show that AuctionRules beats seven benchmark algorithms by up to 21%, achieving up to 97.5% accuracy , with a false negative rate of 0% in comment classification tests compared with up to 8.5% from other algorithms tested.

In this paper we present an intelligent approach for Computer Aided Design, that is capable to learn from its experience in order to speedup the design process. The proposed approach integrates two well known soft-computing techniques, Multi-Objective Genetic Algorithms (MOGAs) and Fuzzy Systems (FSs): MOGA smartly explores the design space, in the meanwhile the FS learn from the experience accumulated during the MOGA evolution, storing knowledge in fuzzy rules. The joined rules build the Knowledge Base through which the integrated system quickly predict the results of complex simulations thus avoiding their long execution times. The methodology is applied to a real case study and evaluated in terms of both efficiency and accuracy, demonstrating the superiority of the intelligent approach against brute force random search.

Today hybrid computing is a popular framework for solving complex problems. If we have knowledge expressed in rules, we can build an Expert System, and if we have data, or can learn from stimulation (training) then we can use Artificial Neural Networks. In this paper we present the FUzzy NEUrule System (FUNEUS) which is a Neuro Fuzzy approach based on fuzzy Adaline neurons and uses Differential Evolution for optimization of membership functions. According to previous Neuro-fuzzy approaches and a well-defined hybrid system HYMES, FUNEUS is an attempt to the direction for integration of neural and fuzzy components with Differential evolution. Despite the fact that it remains difficult to compare neurofuzzy systems conceptually and evaluate their performance, early experimental results proved a promising performance and the need for further evaluation in other application domains.

The automated reasoning research community has grown accustomed to competitive events where a pool of systems is run on a pool of problem instances with the purpose of ranking the systems according to their performances. At the heart of such ranking lies the method used to score the systems, i.e., the procedure used to compute a numerical quantity that should summarize the performances of a system with respect to the other systems and to the pool of problem instances. In this paper we evaluate several scoring methods, including methods used in automated reasoning contests, as well as methods based on voting theory, and a new method that we introduce. Our research aims to establish which of the above methods maximizes the effectiveness measures that we devised to quantify desirable properties of the scoring procedures. Our method is empirical, in that we compare the scoring methods by computing the effectiveness measures using the data from the 2005 comparative evaluation of solvers for quantified Boolean formulas. The results of our experiments give useful indications about the relative strengths and weaknesses of the scoring methods, and allow us to infer also some conclusions that are independent of the specific method adopted.

Credal networks generalize Bayesian networks relaxing numerical parameters. This considerably expands expressivity, but makes belief updating a hard task even on polytrees. Nevertheless, if all the variables are binary, polytree-shaped credal networks can be efficiently updated by the 2U algorithm. In this paper we present a binarization algorithm, that makes it possible to approximate an updating problem in a credal net by a corresponding problem in a credal net over binary variables. The procedure leads to outer bounds for the original problem. The binarized nets are in general multiply connected, but can be updated by the loopy variant of 2U. The quality of the overall approximation is investigated by promising numerical experiments.

The AGM theory is the dominating paradigm in the field of belief change but makes some non-elementary assumptions which disallow its application to certain logics. In this paper, we recast the theory by dropping most such assumptions; we determine necessary and sufficient conditions for a logic to support operators which are compatible with our generalized version of the theory and show that our approach is applicable to a broader class of logics than the one considered by AGM. Moreover, we present a new representation theorem for operators satisfying the AGM postulates and investigate why the AGM postulates are incompatible with the foundational model. Finally, we propose a weakening of the recovery postulate which has several intuitively appealing properties.

We consider a modified version of the situation calculus built using a two-variable fragment of the first-order logic extended with counting quantifiers. We mention several additional groups of axioms that need to be introduced to capture taxonomic reasoning. We show that the regression operator in this framework can be defined similarly to regression in the Reiter's version of the situation calculus. Using this new regression operator, we show that the projection problem (that is the main reasoning task in the situation calculus) is decidable in the modified version. We mention possible applications of this result to formalization of Semantic Web services.

Optimized Recovery (OR) adds belief base optimization to the traditional Recovery postulate—improving Recovery adherence without sacrificing adherence to the more accepted postulates or to the foundations approach. Reconsideration and belief liberation systems both optimize a knowledge base through consolidation of a chain of base beliefs; and recovered base beliefs are returned to the base. The effects match an iterated revision axiom and show benefits for pre-orders, as well. Any system that can resolve an inconsistent belief base can produce these results.

This paper presents a novel unsupervised methodology for automatic disambiguation of nouns found in unrestricted corpora. The proposed method is based on extending the context of a target word by querying the web, and then measuring the overlap of the extended context with the topic signatures of the different senses by using Bayes rule. The algorithm is evaluated on Semcor 2.0. The evaluation showed that the web-based extension of the target word's local context increases the amount of contextual information to perform semantic interpretation, in effect producing a disambiguation methodology, which achieves a result comparable to the performance of the best system in SENSEVAL 3.

This paper presents a method that uses gene ontologiestogether with the paradigm of relational subgroup discovery, to help find description of groups of genes differentially expressed in specific cancers. The descriptions are represented by means of relational features, extracted from publicly available gene ontology information, and are straightforwardly interpretable by the medical experts. We applied the proposed method to two known data sets: (i) acute lymphoblastic leukemia (ALL) vs. acute myeloid leukemia (AML) and (ii) classification of fourteen types of cancer. Significant number of discovered groups of genes had a description, confirmed by the medical expert, which highlighted the underlying biological process that is responsible for distinguishing one class from the other classes. We view our methodology not just as a prototypical example of applying more sophisticated machine learning algorithms to gene expression analysis, but also as a motivation for developing increasingly more sophisticated functional annotations and ontologies, that can be processed by such learning algorithms.

From a set of a partially ordered tasks, one goal of the project scheduling problem is to compute earliest starting dates, latest starting dates and floats of the different tasks, and to identify critical tasks. When durations of tasks are not precisely known, the problem is much trickier. Recently we provided polynomial algorithms to compute upper bound of activity floats in the interval-valued model. The aim of this paper is to extend those new algorithms to the fuzzy-valued problem. To this end, we use the new notion of gradual numbers [7], that represents soft boundaries of a fuzzy interval. We show that algorithms in the interval–valued case can be adapted to fuzzy intervals considering them as crisp intervals of gradual numbers.

The intrinsic and pervasive uncertainty of the real world causes unforeseen disturbances during the execution of plans. The continuous adaptation of existing schedules is necessary in response to the corresponding disruptions. Affected Operations Rescheduling (AOR) and Matchup Scheduling (MUP) have proven to be efficient techniques for this purpose, as they take only a subset of future activities into account. However, these approaches have mainly been investigated for the job shop scheduling problem, which is too restrictive for many practical scheduling problems outside the shop floor. Thus, this paper analyzes and describes how the respective concepts can be extended for the more generic problem class of the Resource-Constrained Project Scheduling Problem (RCPSP). The conducted evaluation reveals that particularly our generalized version of AOR (GAOR) can yield significant performance improvements in comparison to the strategy of rescheduling all future activities.

Web service technology allows access to advertised services despite of their location and implementation platform. However, considerable differences on structural, semantical and technical levels along with the growing number of available web services makes their discovery a significant challenge. Keyword-based matchmaking methods can help users to locate quickly the set of potentially useful services, but they are insufficient for automatic retrieval. On the other hand, the high cost of formal ontology-based methods alienates service designers from their use in practice. Several information retrieval approaches to assess the similarity of web services have been proposed. In this paper we proceed with such a study. In particular, we examine advantages of using Vector-Space Model, WordNet and semantic similarity metrics for this purpose. A matching algorithm relying on the above techniques is presented and an experimental study to choose the most effective approach is provided.

The increasing number of Web services and thus of possible combinations is particularly hard to accord with the dynamic and versatile feature of the Web. Indeed, in general, complex Web services may frequently happen not to fit the situation encountered. To avoid composing a new Web service “from scratch”, we search a practical way of repairing failed ones. This paper presents a Web service repairing heuristic based on a semantic modeling approach. Modeling Web services is triggered with an OWL-S fragment. Repairing is based on our previous work which allows organizing a collection of Web services into hierarchies. A NEXPTIME complexity upper bound is shown for a reparation which doesn't change the internal structure of the complex Web service.

Based on the use of location and available car seats, Car sharing systems allowed a substantial number of people to share car rides.This paper proposes the initial phase of Smart Ride Seeker (SRS), which is a Car Pooling-like technique for distributing resources among a community. This paper develops the SRS technique through a mobile-based application that allows the mapping of ride seekers' locations along with the locations of available cars on a graphical interface/map, giving the possibility to calculate the optimal path for both the ride giver and seeker to fulfill their demands.

The great number and variety of learning-based spam filters proposed during the last years cause the need in many-sided evaluation of them. This paper is dedicated to the evaluation of the dependence of filtering accuracy on the temporal distribution of training data. Such evaluation may be useful for organizing effective training of the filter.