The tutorials will be held at the University of Edinburgh.
Tutorial Chair: Robert Givan
Click on the tutorial titles below to see details.
(Saturday 30 July - morning)
The field of grammar induction is concerned with inferring grammatical models of the generative structure underlying sequential data. Both the theory and practice of grammar induction are well-developed and have found applications in a wide variety of domains: in bio-informatics, context-free grammars capture the hierarchical structure of the nucleotide sequences that comprise proteins; in natural language processing and speech recognition, stochastic grammars are used for language modeling. Other applications include wrapper induction for information extraction from documents marked up with XML, recognition and generation of musical scores, and inductive logic programming. This tutorial will provide an introduction to the theory, practice, and open problems in grammar induction. Among the topics that will be covered are models of learnability, inference of finite state automata and context-free grammars, learning from trees and structured data, stochastic finite automata and grammars, inference techniques, positive and negative learnability results, and applications.
(Saturday 30 July - morning)
In the last fifteen years the area of automated reasoning in first-order logic witnessed several exciting developments. A new theory of inference systems with redundancy has been developed. New implementation techniques and heuristics have evolved. Systems based on the new theory and implementation techniques outperform the previous generation systems, often by orders of magnitude. New applications appeared in connection with the rapid growth in the use and acceptance of formal methods and development of ontologies and knowledge bases.
The tutorial is intended to overview the state-of-the-art automated reasoning, including theory, implementation, applications, and the use of theorem provers. Presentation will be accompanied by demos of the theorem prover Vampire, the winner of several world cups in theorem proving. For example, we will show how the modern theory influenced the design of Vampire and options available in it and how Vampire can be used for answering queries to large knowledge bases.
(Saturday 30 July - morning)
Branch-and-bound is a search paradigm which uses bounds to prune large portions of a search space without compromising optimality. This paradigm is heavily utilized in AI, prompting substantial research of the derivation of bounds. We reflect on the history of the use of bounds and observe that, until recently, the focus has been on bounds derived from relaxations of constraints. We demonstrate how overlooked bounds can be systematically derived by tightening constraints, adding/removing variables, and modifying the objective function. Then a formalization of the use of bounds as a two-step procedure is presented. The use of this framework is conducive to eliciting methods that go beyond search-tree pruning. We demonstrate the use of this technique for devising novel search strategies and apply these strategies to several optimization problems.
This tutorial is aimed at the general AI audience. Familiarity with basic concepts of combinatorial optimization is desirable but not essential.
(Saturday 30 July - morning)
Reductions allow us to reuse classification algorithms in new settings such as multiclass classification, cost sensitive classification, and reinforcement learning. This approach to solving prediction problems can often yield comparable or superior performance with minimal (human) effort. We present several algorithms exhibiting this design pattern along with the mathematical tools used to analyze and develop new reduction algorithms.
At the end of this tutorial, you should understand several reduction algorithms, how to use them and how to analyze and optimize them.
(Saturday 30 July - afternoon)
This tutorial will provide participants with a firm understanding of the essential techniques for constraint processing. Presenters will summarize the huge amount of results published in the last years in a few lines of research, allowing attenders to get a clear and structured view of the field. The presentation will be focused on the algorithmic methods for constraint processing, without forgetting theoretical aspects and successful constraint applications. Algorithms will be described in terms of search, inference and hybrids.
The tutorial will cover both types of constraint processing: hard constraints (classical constraint satisfaction) and soft constraints (constrained optimization). Modelling guidelines and environments for constraint processing will be discussed. To know more after the tutorial, a detailed list of references will be presented.
(Saturday 30 July - afternoon)
Recently there has been a surge of interest in methods which combine first-order and relational languages with probabilistic models. In this tutorial, we will survey several recent approaches. We will describe logic and rule-based approaches (such as Probabilistic Logic Programming, Bayesian Logic Programs, and Stochastic Logic Programs), frame and object-oriented approaches (such as Probabilistic Relational Models, Markov Relational Networks and Probabilistic Entity Relationship Models), and methods based on functional programming (such as Stochastic Lambda Calculus and IBAL).
We will describe the representations and representational issues, beginning with attribute uncertainty, and then describing more complex types of uncertainty such as structural uncertainty and identity uncertainty. We will describe several inference algorithms and learning techniques, including statistical approaches to parameter and structure learning and inductive logic programming approaches. We will conclude by discussing a number of application areas that can be modeled, for instance collaborative filtering, entity resolution, information extraction, social network analysis, and web mining.
(Saturday 30 July - afternoon)
During the last decade a number of breakthroughs have lifted the efficiency of domain-independent planning to a level required in many challenging applications. The tutorial presents the most important approaches to state space traversal as applied in algorithms for classical (deterministic) planning and in implementations of algorithms for more general forms of planning, including techniques based on propositional satisfiability testing, heuristic state-space search, and on logic-based data structures like binary decision diagrams.
The presentation is based on general and uniform concepts that allow the description of the most central notions concisely and makes the essential differences and similarities between the different approaches more apparent. Unlike in most research papers which use restricted STRIPS operators, the presentation is based on an expressive language similar to ADL/PDDL used by many recent planner implementations.
(Saturday 30 July - afternoon)
Explicit preference modelling provides declarative means for choosing among alternatives, including alternative solutions of problems to solve, answers of data-base queries, decisions of a computational agent, or plans of a robot. Explicit preference models allow finer-grained control over computation and new ways of interactivity, and therefore provide more satisfactory results and outcomes than other choice mechanisms.
The tutorial addresses a broad AI audience, giving an overview on preferences in four parts starting with traditional decision theory and ending with highly advanced issues:
(Sunday 31 July - all day)
Most of the AI techniques that have been found useful in a wide range of areas including Search, Planning, SAT, Constraints, Bayesian Neworks, and Markov Decision Processes, can be understood along a few dimensions, and are expressions of a small core of concepts and principles. In this tutorial, we articulate this basic core of ideas aiming at a coherent, comprehensive, and modern view of AI Problem Solving.
We focus on optimal problem solving over various state and variable-based (graphical) models used in AI, and classify current techniques in two classes: those based on search and inference, and those based on pure inference and no search. In the former class, we analyze the notions of branching and pruning (either with lower bounds or constraint propagation), along with the notions of learning (in both SAT/CSPs and State Models), decomposition, and caching. In the latter class, we consider the concepts of variable elimination, join tree decomposition, and compilation. We also analyze the relation among these notions, their time and space complexity, and how they are currently used for solving various tasks of interest in AI.
(Sunday 31 July - morning)
The information age has made it easy to store large amounts of data. The proliferation of documents available on the Web, on corporate intranets, on news wires, and elsewhere is overwhelming. However, while the amount of data available to us is constantly increasing, our ability to absorb and process this information remains constant. Search engines only exacerbate the problem by making more and more documents available in a matter of a few key strokes. Text Analytics is a new and exciting research area that tries to solve the information overload problem by using techniques from data mining, machine learning, NLP, IR and knowledge management. Text analytics involves the preprocessing of document collections (text categorization, information extraction, term extraction), the storage of the intermediate representations, the techniques to analyze these intermediate representations (distribution analysis, clustering, trend analysis, association rules etc) and visualization of the results.
In this tutorial we will present the general theory of Text analytics and will demonstrate several systems that use these principles to enable interactive exploration of large textual collections. We will present a general architecture for text analytics and will outline the algorithms and data structures behind the systems. Special emphasis will be given to efficient algorithms for very large document collections, tools for visualizing such document collections, the use of intelligent agents to perform text analytics on the internet, and the use information extraction to better capture the major themes of the documents. The tutorial will cover the state of the art in this rapidly growing area of research. Several real world applications of text analytics will be presented.
(Sunday 31 July - morning)
Multiagent planning is concerned with planning by (and for) multiple agents. It can involve agents planning for a common goal, an agent coordinating the plans or planning of others, or agents refining their own plans while negotiating over tasks or resources. Distributed continual planning addresses these problems when further complicated with interleaved execution. More than ever industry, space, and the military are seeking systems that can solve these problems.
This tutorial will describe variations of the multiagent planning problem, discuss issues in the applicability and design of multiagent planning systems, and describe some real-world multiagent planning problems. We will also review the history of research contributions to this sub-field and describe frameworks and systems such as Distributed NOAH, GPGP, DSIPE, and SHAC. In addition, we will describe open research issues in multiagent planning and its overlap and relation to other fields, such as market-based AI and game theory.
(Sunday 31 July - morning)
In many areas of human reasoning, such as law, ethics, medicine, the social sciences, proof is not possible, and so instead rationality must be based on some more or less persuasive argument. Argumentation has long been of interest to informal logicians, but increasingly attempts are being made to make the notions involved sufficiently precise to be amenable to embodiment in computer systems. Additionally, argumentation can be modelled as a dialogue between supporters and opponents of the proposition under consideration. Both practical reasoning and dialogue have particular significance for multi-agent systems.
In this tutorial we will look at the characteristics of argument that distinguish it from proof; at ways in which a formal framework for reasoning about systems of argument can be provided; at dialogues based on such frameworks; at representations of the structure of individual arguments; and at some example applications of these
(Sunday 31 July - afternoon)
Collaborative agent systems are critical in a vast range of applications, in virtual environments for training and education, in improving human-computer interaction and organizational productivity, in applications in disaster rescue, space, military, and other spheres. Such collaborative systems are within reach thanks to progress in our understanding of rationality, both collective and individual. This tutorial will describe the major theoretical advances that can support principled designs and analyses of such systems as well as describe implementations based on those theories. The tutorial will begin with an overview of rationality: what it means for an agent to be rational and how this can be reflected in agent designs. This will include a brief review of models of mental state as well as rational agent architectures, emphasizing considerations of resource-boundedness and the ways this affects formalizations and system designs.
(Sunday 31 July - afternoon)
Evolutionary Linguistics is a new and rapidly growing field that has emerged from the field of artificial intelligence and that is concerned with modelling the origins and evolution of language. It addresses questions such as the origins of grammar, the prerequisites for human language, and origins of symbolic communication. This tutorial offers an introduction for artificial intelligence researchers who are new to evolutionary linguistics and is aimed at understanding the field and helping them set up computational experiments that address open issues. We do this by presenting a thorough overview of the field and by discussing how established AI techniques can be used to investigate the evolution of language. To illustrate this we present a number of case studies. In addition, we aim to provide suggestions of how to disseminate the research to a multidisciplinary audience, which often include linguists, anthropologists, archeologists, psychologists and biologists.
(Sunday 31 July - afternoon)
Markets are important mechanisms for allocating goods, services, tasks, and resources among multiple agents, be they human or software. The market clearing problem is that of deciding how to allocate the items among the agents. The last four years have witnessed a leap of improvement in market clearing algorithms both for traditional market designs and entirely new market designs enabled by advanced clearing technology. This tutorial covers the computational implications of different market designs and presents algorithms for clearing markets optimally and approximately. Auctions (one seller, multiple buyers), reverse auctions (one buyer, multiple sellers), and exchanges (multiple buyers and multiple sellers) are covered. Both theoretical and experimental results are presented. Multi-item and multi-unit markets will be a key focus. Computational implications of different classes of side constraints will be presented. Bid types covered include price-quantity bids, different shapes of supply/demand curves, and package bids. Methods for selective incremental preference elicitation for combinatorial markets are presented, with which the market can be cleared optimally using only a small portion of the agents' preferences as input.
A basic understanding of algorithms, search, and NP-completeness is necessary. No background on markets is assumed.
(Sunday 31 July - afternoon)
We can expect that some software agents would work on our behalf, representing our interests and defending our privacy. A principled approach to the achievement of this dream is proposed by the Distributed Constraint Reasoning community which offers a general framework and powerful competitive techniques to approach these important applications. We will introduce the two major approach families, secure multi-party computations and search-based algorithms. This tutorial will provide an unified view on Distributed Constraint Reasoning, introducing distributed constraint reasoning systems as semi-cooperative multi-agent systems and concentrating on the privacy, communication and organization requirements of such systems. The general ideas behind the known distributed constraint reasoning systems are presented within this multi-agent framework. For each approach, the requirements, limitations, advantages and disadvantages of the different categories will be discussed.
(Saturday 30 July & Sunday 31 July - 2 days)
A two day advanced tutorial supported by the European Commission's Cognitive Systems initiative, at which tutorials will be presented by seven leading researchers on problems of learning and representation in integrated natural and artificial systems combining multiple functions using different forms of representation and learning. The presentations will illustrate the state of the art and unsolved problems. The tutorial will end with a two hour panel discussion on what the major unsolved problems are and how we can make progress towards solving them.
Please send inquiries regarding the IJCAI-05 tutorial programme to:
Bob Givan
School of Electrical and Computer Engineering
Purdue University, West Lafayette, Indiana 47907
tutorials05@ijcai.org
Information for Tutorial Organisers (was: call for proposals)