The considerable interest in ARA techniques and the great diversity of the researchers involved had led to work on ARA being presented at many different venues. Consequently, there was a need to have a single forum where researchers of different backgrounds and disciplines could discuss their work on ARA. As a result, the Symposium on Abstraction, Reformulation, and Approximation (SARA) was established in 1994 after a series of workshops in 1988, 1990, and 1992. The current SARA, held at Lake Arrowhead, California, USA, on July 7-10, 2009, is the eighth in this series, following symposia in 1994, 1995, 1998, 2000, 2002, 2005, and 2007. Following a SARA tradition, this symposium brought together researchers with different backgrounds and facilitated lively discussions during and after the talks. There were 30 researchers from North and South America, Europe, and Australia. Additionally, SARA attendees were able to mingle and have fruitful discussions with members of the collocated Symposium on Combinatorial Search (SoCS). The collocation of SoCS was particularly useful in that many modern techniques in combinatorial search frequently utilize ARA methods. Finally, in addition to the regular and poster talks, there were three invited talks delivered by Jeff Orkin (Massachusetts Institute of Technology), Michael Genesereth (Stanford University), and Robert Holte (University of Alberta).

This article reports on the 2008 Reinforcement Learning Competition,  which began in November 2007 and ended with a workshop at the  International Conference on Machine Learning (ICML) in July 2008 in  Helsinki, Finland.  Researchers from around the world developed  reinforcement learning agents to compete in six problems of various  complexity and difficulty.  The competition employed fundamentally  redesigned evaluation frameworks that, unlike those in previous  competitions, aimed to systematically encourage the submission of  robust learning methods. We describe the unique challenges of  empirical evaluation in reinforcement learning and briefly review  the history of the previous competitions and the evaluation  frameworks they employed.  We also describe the novel frameworks  developed for the 2008 competition as well as the software  infrastructure on which they rely.  Furthermore, we describe the six  competition domains and present a summary of selected competition  results.  Finally, we discuss the implications of these results and  outline ideas for the future of the competition.

The European Conference on Case-Based Reasoning (CBR) in 2008 marked 15 years of international and European CBR conferences where almost seven hundred research papers were published. In this report we review the research themes covered in these papers and identify the topics that are active at the moment. The main mechanism for this analysis is a clustering of the research papers based on both co-citation links and text similarity. It is interesting to note that the core set of papers has attracted citations from almost three thousand papers outside the conference collection so it is clear that the CBR conferences are a sub-part of a much larger whole. It is remarkable that the research themes revealed by this analysis do not map directly to the sub-topics of CBR that might appear in a textbook. Instead they reflect the applications-oriented focus of CBR research, and cover the promising application areas and research challenges that are faced.

Developing intelligent agents and cognitive models is a complex software engineering activity. This article shows how all intelligent agent creation tools can be improved by taking advantage of established software engineering principles such as high-level languages, maintenance-oriented development environments, and software reuse. We describe how these principles have been realized in the Herbal integrated development environment, a collection of tools that allows agent developers to exploit modern software engineering principles.

Process integrated mechanisms (PIM) offer a new approach to the problem of coordinating the activity of physically distributed systems or devices. Current approaches to coordination all have well-recognized strengths and weaknesses. We propose a novel architecture to add to the mix, called the Process Integrated Mechanism (PIM), which enjoys the advantages of having a single controlling authority while avoiding the structural difficulties that have traditionally led to its rejection in many complex settings. In many situations, PIMs improve on previous models with regard to coordination, security, ease of software development, robustness and communication overhead. In the PIM architecture, the components are conceived as parts of a single mechanism, even when they are physically separated and operate asynchronously. The PIM models offers promise as an effective infrastructure for handling tasks that require a high degree of time-sensitive coordination between the components, as well as a clean mechanism for coordinating the high-level goals of loosely coupled systems. PIM models enable coordination without the fragility and high communication overhead of centralized control, but also without the uncertainty associated with the system-level behavior of a MAS.The PIM model provides an ease of programming with advantages over both multi-agent sys-tems and centralized architectures. It has the robustness of a multi-agent system without the significant complexity and overhead required for inter-agent communication and negotiation. In contrast to centralized approaches, it does not require managing the large amounts of data that the coordinating process needs to compute a global view. In a PIM, the process moves to the data and may perform computations on the components where the data is locally available, sharing only the information needed for coordination of the other components. While there are many remaining research issues to be addressed, we believe that PIMs offer an important and novel tech-nique for the control of distributed systems.

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaP2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

We tackle the problem of multi-class relational sequence learning using relevant patterns discovered from a set of labelled sequences. To deal with this problem, firstly each relational sequence is mapped into a feature vector using the result of a feature construction method. Since, the efficacy of sequence learning algorithms strongly depends on the features used to represent the sequences, the second step is to find an optimal subset of the constructed features leading to high classification accuracy. This feature selection task has been solved adopting a wrapper approach that uses a stochastic local search algorithm embedding a naive Bayes classifier. The performance of the proposed method applied to a real-world dataset shows an improvement when compared to other established methods, such as hidden Markov models, Fisher kernels and conditional random fields for relational sequences.

We proposed a learning algorithm for nonparametric estimation and on-line prediction for general stationary ergodic sources. We prepare histograms each of which estimates the probability as a finite distribution, and mixture them with weights to construct an estimator. The whole analysis is based on measure theory. The estimator works whether the source is discrete or continuous. If it is stationary ergodic, then the measure theoretically given Kullback-Leibler information divided by the sequence length $n$ converges to zero as $n$ goes to infinity. In particular, for continuous sources, the method does not require existence of a probability density function.

The major challenge in designing a discriminative learning algorithm for predicting structured data is to address the computational issues arising from the exponential size of the output space. Existing algorithms make different assumptions to ensure efficient, polynomial time estimation of model parameters. For several combinatorial structures, including cycles, partially ordered sets, permutations and other graph classes, these assumptions do not hold. In this thesis, we address the problem of designing learning algorithms for predicting combinatorial structures by introducing two new assumptions: (i) The first assumption is that a particular counting problem can be solved efficiently. The consequence is a generalisation of the classical ridge regression for structured prediction. (ii) The second assumption is that a particular sampling problem can be solved efficiently. The consequence is a new technique for designing and analysing probabilistic structured prediction models. These results can be applied to solve several complex learning problems including but not limited to multi-label classification, multi-category hierarchical classification, and label ranking.

Association rules are among the most widely employed data analysis methods in the field of Data Mining. An association rule is a form of partial implication between two sets of binary variables. In the most common approach, association rules are parameterized by a lower bound on their confidence, which is the empirical conditional probability of their consequent given the antecedent, and/or by some other parameter bounds such as "support" or deviation from independence. We study here notions of redundancy among association rules from a fundamental perspective. We see each transaction in a dataset as an interpretation (or model) in the propositional logic sense, and consider existing notions of redundancy, that is, of logical entailment, among association rules, of the form "any dataset in which this first rule holds must obey also that second rule, therefore the second is redundant". We discuss several existing alternative definitions of redundancy between association rules and provide new characterizations and relationships among them. We show that the main alternatives we discuss correspond actually to just two variants, which differ in the treatment of full-confidence implications. For each of these two notions of redundancy, we provide a sound and complete deduction calculus, and we show how to construct complete bases (that is, axiomatizations) of absolutely minimum size in terms of the number of rules. We explore finally an approach to redundancy with respect to several association rules, and fully characterize its simplest case of two partial premises.