Ebook: STAIRS 2014

These are the proceedings of the 7th European Starting AI Researcher Symposium (STAIRS), held as a satellite event of the 21st European Conference of Artificial Intelligence (ECAI) in Prague, Czech Republic, on 18th and 19th of August 2014. STAIRS is aimed at young researchers in Europe and beyond, particularly PhD students. It provides an opportunity to go through the experience of submitting to and presenting at an international event with a broad scientific scope.

The Call for Papers was soliciting submissions from all areas of AI, ranging from foundations to applications. Topics of interest for STAIRS include autonomous agents and multiagent systems; constraints, satisfiability, and search; knowledge representation, reasoning, and logic; machine learning and data mining; planning and scheduling; uncertainty in AI; natural language processing; as well as robotics, sensing, and vision. That is, the scope of STAIRS is the same as that of the major international conferences in AI. What sets STAIRS apart is that the principal author of every submitted paper must be a young researcher who either does not yet hold a PhD or who has obtained their PhD less than one year before the paper submission deadline.

We received a total of 45 submissions. All of them were carefully reviewed by the STAIRS Programme Committee, consisting of leading European researchers who together cover the depth and breadth of the field of AI. We are very grateful for the great service provided by these colleagues, as well as by the additional reviewers assisting them in their task. In the end, 16 papers were accepted for oral presentation at the symposium, and a further 14 for presentation during a poster session. These 30 accepted papers are included in this volume.

The body of submitted papers together covers the field of AI well, with knowledge representation and reasoning, machine learning, and planning and scheduling being the areas attracting the largest numbers of submissions. The problems tackled range from classical AI themes such as search, all the way to emerging research trends, e.g., at the interface of AI with economics. Also in terms of the foundations/application divide the STAIRS programme covers the full spectrum.

Besides the presentation of contributed papers and posters, the STAIRS programme will feature two keynote talks. On the first day of the symposium, Michael Wooldridge, Professor of Computer Science at the University of Oxford, UK, will offer an introduction to characterisation results for equilibria in repeated games and the significance of such results to multiagent systems. On the second day, Francesca Rossi, Professor of Computer Science at the University of Padova, Italy, will talk about new approaches to sentiment analysis, harnessing modern techniques from AI, such as preference reasoning and computational social choice. We thank both of them for accepting our invitation.

We are looking forward to an exciting two days in Prague, and we hope that readers of this volume will find it as useful as we have in getting an impression of current developments in our field.

June 2014

Ulle Endriss

João Leite

One of the most critical components of Branch & Bound (BnB) solvers for Max-SAT is the estimation of the lower bound. At each node of the search tree, they detect inconsistent subsets (IS) of the formula by unit propagation based methods and apply a treatment to them. The currently best performing Max-SAT BnB solvers perform a very little amount of memorization, thus the same IS may be detected and treated several times during the exploration of the search tree. We address in this paper the problem of increasing the learning performed by BnB solvers. We present new sets of clause patterns which produce unit resolvent clauses when they are transformed by max-resolution. We study experimentally the impact of these transformation' memorization in our solver AHMAXSAT and we discuss their effects on the solver behavior.

We present a local search algorithm exploiting two efficient solvers for SAT. The first one is based on the configuration checking strategy and the second one on an algorithm of the Walksat family. This new solver is dedicated to solve random k-SAT instances, such that k ≥ 4. We have carried tests on the instances of the SAT Challenge 2012. The obtained results confirm the relevance of our approach.

We introduce a framework which is based on probabilistic Description logics (Prob-DL), to represent and solve multi-criteria discrete alternative problems by calculating expected utility. To our knowledge, this is the first ever approach for calculating expected utility using a Description logics based formalism.

In financial markets, market participants need to cope with risk and uncertainty, to forecast possible scenarios, and to constantly analyze and revise their beliefs, expectations, and strategies in the light of the massive amount of economical and financial information they receive. Interestingly, the relevance does not seem to reside in the numbers itself but rather whether they elicit “surprise” for market participants. In this paper we review the presence of the term surprise in economics and finance as well as how it is computed. Then, we present how emotions are defined in cognitive science, provide a formal definition of surprise, and describe the surprise process. Additionally, we present some theories regarding how artificial surprise can be computed. In a case study we compare the two different perspectives on surprise, discussing some similarities and differences. Finally, we present some possible applications of the cognitive science perspective.

This paper presents an approach to repair or improve the quality of plans which make use of temporal and numeric constructs. While current state-of-the-art temporal planners are biased towards minimising makespan, the focus of this approach is to maximise plan quality. Local search is used to explore the neighbourhood of an input seed plan and find valid plans of a better quality with respect to the specified cost function. Experiments show that this algorithm is effective to improve plans generated by other planners, or to perform plan repair when the problem definition changes during the execution of a plan.

This paper describes a new planner, HiPOP (Hierarchical Partial-Order Planner), which is domain-configurable and uses POP techniques to create hierarchical time-flexible plans. HiPOP takes as inputs a description of a domain, a problem, and some optional user-defined search-control knowledge. This additional knowledge takes the form of a set of abstract actions with optional methods to achieve them. HiPOP uses this knowledge to enrich the output by providing a hierarchical time-flexible partial-order plan that follows the given methods. We show in this paper how to use this additional knowledge in a POP algorithm and provide results on a domain with a strong hierarchy of actions. We compare our approach with other temporal planners on this domain.

Relational approaches to represent and solve MDPs exploit structure that is inherent to modelled domains in order to avoid or at least reduce the impact of the curse of dimensionality that propositional representations suffer from. By explicitly reasoning about relational structure, policies that lead to specific goals can be derived on a very general, abstract level; thus, these policies are valid for numerous domain instantiations, regardless of the particular objects participating in it. This paper describes the encoding of relational MDPs as rewrite theories, allowing for highly domain-specific domain encoding and abstraction. Narrowing is employed to solve these relational MDPs symbolically. Resulting symbolic value functions are simplified by Ax-matching abstract state terms. It is shown that relational state representations significantly reduce the size of state space and value function when compared to propositional representations.

There are a lot of measures for selecting interesting itemsets. But which one is better? In this paper we introduce a methodology for evaluating interestingness measures. This methodology relies on supervised classification. It allows us to avoid experts and artificial datasets in the evaluation process. We apply our methodology to evaluate promising measures for itemset selection, such as leverage and stability. We show that although there is no evident winner between them, stability has a slightly better performance.

Modelling preferences has been an active research topic in Artificial Intelligence for more than fifteen years. Existing formalisms are rich and flexible enough to capture the behaviour of complex decision rules. However, for being interesting in practice, it is interesting to learn not a single model, but a probabilistic model that can compactly represent the preferences of a group of users – this model can then be finely tuned to fit one particular user. Even in contexts where a user is not anonymous, her preferences can depend on the value of a non controllable state variable. In such contexts, we would like to be able to answer questions like “What is the probability that o is preferred to o′ by some (unknown) agent?”, or “Which item is most likely to be the preferred one, given some constraints?”

We study in this paper how Probabilistic Conditional Preference networks can be learnt, both in off-line and on-line settings.

We propose a new qualitative spatial logic for reasoning about part-whole relations between geometries (sets of points) represented in different geospatial datasets, in particular crowd-sourced datasets. Since geometries in crowd-sourced data can be less inaccurate or precise, we buffer geometries by a margin of error or level of tolerance σ, and define part-whole relation for buffered geometries. The relations between geometries considered in the logic are: buffered part of (BPT), Near and Far. We provide a sound and complete axiomatisation of the logic with respect to metric models and show that its satisfiability problem is NP-complete.

An attack graph represents all known sequences of actions that compromise a system in form of an and-or graph. We assume that each action in the attack graph has a specified cost and probability of success and propose an algorithm for computing an action selection policy minimizing the expected cost of performing an attack. We model the problem as a finite horizon MDP and use forward search with transposition tables and various pruning techniques based on the structure of the attack graph. We experimentally compare the proposed algorithm to a generic MDP solver and a solver transforming the problem to an Unconstrained Influence Diagram showing a substantial runtime improvement.

The last few years have witnessed some remarkable success of the state-of-the art unsupervised knowledge extraction systems like NELL and REVERB. These systems are gifted with typically web-scale coverage but are often plagued with ambiguity due to lack of proper schema or unique identifiers for the instances. This classifies them apart from extraction systems like DBPEDIA, YAGO or FREE-BASE which have precise information content but have smaller coverage. In this work we bring together the former to enrich the later with high precision novel facts and present a statistical approach to discover new knowledge. In particular, we semantify NELL triples using DBPEDIA.

Tracking and understanding moving pedestrian behaviors is of major concern for a growing number of applications. Classical approaches either consider the two problems separately or treat them simultaneously while relying on limited context-based graphical models. In this paper, we present an approach to tackle both the problems conjointly based on richer contextual information issued from agent-based behavioral simulators which aim to realistically reproduce human behaviors within complex environments. We focus on the special case of a single target and experimentally show that the proposed approach manages to track a single pedestrian with complex behavior even in case of long periods of occlusion.

Current spoken dialogue systems (SDS) often behave inappropriately as they do not feature the same capabilities to detect speech recognition errors and handle them adequately as is achieved in human conversation. Adopting human abilities to identify perception problems and strategies to recover from them would enable SDS to show more constructive and naturalistic behavior.

We investigated human error detection and error handling strategies within the context of a SDS for pedestrian assistance. The human behavior serves as a model for future algorithms that could yield reduced error rates in speech processing.

The results contribute to a better understanding which knowledge humans employ to build up interpretations from perceived words and establish their confidence in perception and interpretation. The findings provide useful input for SDS developers and enable researchers to estimate the potential benefit of future research avenues.

We propose a new parallel search algorithm – A! – based on cooperating A* search agents, concurrency and a secondary tiebreaking heuristic. The search agents in A! share information asynchronously and trade some of their independence for additional search focus and a more global view of the search task. A! is inherently nondeterministic due to the implicit randomness of instruction scheduling, but given a consistent primary heuristic, it still finds optimal solutions for the single-source shortest path problem (SSSP). A! combines into a single cooperative search algorithm the breadth available in parallel execution and the depth-first orientation of both locally and globally informed search.

We experimentally show that A! outperforms both vanilla A* and an explicitly randomized, noncooperative parallel A* variant. We present an empirical study on cooperation benefits and scalability in the classic 15-puzzle context. The results imply that cooperation and concurrency can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.

Autonomous underwater vehicle (AUV) missions are challenging due to limited or no communication with the vehicle and uncertainty about what may be encountered during the mission. The vehicle has limited battery power and memory to store datasets and does not know how much of these resources its actions will consume. Managing the uncertainty by building contingency plans (as in previous work) is infeasible owing to the large number of contingencies. Purely online planning is also difficult because of restricted computation. We propose a mixture of off-line planning and on-line plan repair, presenting an approach for deleting parts of a plan when resources are tight, or stitching new plan fragments into an existing plan when additional resources are available. We discuss this novel approach using a simulated AUV mission domain.

We make a link between a specialized context free language expressing the rules of variety of card games, called CGDL, and the most known general-purpose game description language GDL-II. We present a systematic translation from CGDL to GDL-II, prove that the translation is correct, and analyze the complexity of resulting code in both theoretical and empirical way.

The predominant learning strategy for H(S)MMs is local search heuristics, of which the Baum-Welch/ expectation maximization (EM) algorithm is mostly used. It is an iterative learning procedure starting with a predefined topology and randomly-chosen initial parameters. However, state-of-the-art approaches based on arbitrarily defined state numbers and parameters can cause the risk of falling into a local optima and a low convergence speed with enormous number of iterations in learning which is computationally expensive. For models with persistent states, i.e. states with high self-transition probabilities, we propose a segmentation-based identification approach used as a pre-identification step to approximately estimate parameters based on segmentation and clustering techniques. The identified parameters serve as input of the Baum-Welch algorithm. Moreover, the proposed approach identifies automatically the state numbers. Experimental results conducted on both synthetic and real data show that the segmentation-based identification approach can identify H(S)MMs more accurately and faster than the current Baum-Welch algorithm.

This paper presents a supervised algorithm for separating speech from background non-stationary noise (piano music) in single-channel recordings. The proposed algorithm, based on a nonnegative matrix factorization (NMF) approach, is able to extract speech sounds from isolated or chords piano sounds learning the set of spectral patterns generated by independent syllables and piano notes. Moreover, a sparsity constraint is used to improve the quality of the separated signals. Our proposal was tested using several audio mixtures composed of real-world piano recordings and Spanish speech showing promising results.

The preferential approach to nonmonotonic reasoning was consolidated in depth by Krause, Lehmann and Magidor (KLM) for propositional logic in the early 90's. In recent years, there have been efforts to extend their framework to Description Logics (DLs) and a solid (though preliminary) theoretical foundation has already been established towards this aim. Despite this foundation, the generalisation of the propositional framework to DLs is not yet complete and there are multiple proposals for entailment in this context with no formal system for deciding between these. In addition, there are virtually no existing preferential reasoning implementations to speak of for DL-based ontologies. The goals of this PhD are: to place the preferential approach in context w.r.t. the alternative nonmonotonic reasoning proposals, to provide a complete generalisation of the preferential framework of KLM to the DL ALC, provide a formal understanding of the relationships between the multiple proposals for entailment in this context, and finally, to develop an accompanying defeasible reasoning system for DL-based ontologies with performance that is suitable for use in existing ontology development settings.

Temporal data abstraction (TA) is a set of techniques aiming to abstract time-points into higher-level interval concepts and to detect significant trends in both low-level data and abstract concepts. Dynamic Bayesian networks (DBNs) are temporal probabilistic graphical models that model temporal processes, temporal relationships between events and state changes through time. In this paper, we propose the integration of TA methods with DBNs in the context of medical decision-support systems, by presenting an extended DBN model. More specifically, we demonstrate the derivation of temporal abstractions which are used for building the network structure. We also apply machine learning algorithms to learn the parameters of the model through data. The model is applied for diagnosis of coronary heart disease using as testbed a longitudinal dataset. The classification accuracy of our model evaluated using the evaluation metrics of Precision, Recall and F1-score, shows the effectiveness of our proposed system.

Inprocessing is to apply clause simplification techniques during search and is a very attractive idea since it allows to apply computationally expensive techniques. In this paper we present the search space decomposition formalism SSD that models parallel SAT solvers with clause sharing and inprocessing. The main result of this paper is that the sharing model SSD is sound. In the formalism, we combine clause addition and clause elimination techniques, and it covers many SAT solvers such as PaSAT, PaMira, PMSat, MiraXT and ccc. Inprocessing is not used in these solvers, and we therefore propose a novel way how to combine clause sharing, search space decomposition and inprocessing.

Accuracy and comprehensibility are two important classifier properties, however they are typically conflicting. Research in the past years has shown that Pareto-based multi-objective approach for solving this problem is preferred to the traditional single-objective approach. Multi-objective learning can be represented as search that starts either from an accurate classifier and modifies it in order to produce more comprehensible classifiers (e.g. extracting rules from ANNs) or the other way around: starts from a comprehensible classifier and modifies it to produce more accurate classifiers. This paper presents a case study of applying a recent algorithm for multi-objective learning of hybrid trees MOLHC in human activity recognition domain. Advantages of MOLHC for the user and limitations of the algorithm are discussed on a number of datasets from the UCI repository.

This paper focuses on predicting player behaviour in two-player games with microtransactions. Typically the games are for free and companies generate their revenue by selling in-game goods. We show creation of a users behaviour model, which are then used in a recommendation system increasing in-game goods purchases. We focus on learning techniques in a novel way, predicting the time of purchases rather than the most likely product to be purchased. The player model is based on in-game signals, such as players success, curiosity, social interactions etc. We had access to a Pool Live Tour game dataset made by Geewa. We report promising results in predicting the purchase events.