Date: 16th December 2005, 12:15, Room CS202J, Computer Science, Univ. of York
Persuasion and Dialogue
Pierre Andrews, University of York
Techniques for effective argumentation and persuasion have been developed by philosophers since the III century B.C. They have been effectively integrated in multiple media, and used for instance in advertising.
However, persuasive technology is a recent field of development in computer science and has yet to be explored in all its different aspects. Captology, for example, is currently developing new HCI techniques to integrate persuasive communication theories. Health care, legal and natural argumentation are other fields of interest where much of the effort is being developed.
In this seminar, I will introduce the different techniques developed in Natural Language Processing and Artificial Intelligence for argumentative systems. I will then discuss my current object of research which consists in trying to integrate these techniques to implement persuasive dialogue for health-care advice
Date: 2nd December 2005, 12:15, Room CS119N, Computer Science, Univ. of York
Parallel Reinforcement Learning
Matthew Grounds, University of York
Abstract: Reinforcement learning (RL) is a family of learning methods that can be used by an agent to learn from experience, given a reward signal which defines the utility of a state of the agent's environment. As with many machine learning methods, reinforcement learning suffers from the "curse of dimensionality" - as more learning features are added, computational requirements exhibit exponential growth. In this context, a technique which can reduce these requirements and allow us to "scale up" to ever larger problems would be extremely useful.
While computation time remains large for even relatively simple RL problems, it is reasonable to ask whether parallel computation can be used to find solutions more quickly. There has been very little research in this area, which is surprising when technologies such as hyper-threading, multi-core processors and grid computing are moving rapidly into the mainstream. Researchers in multi-agent learning have traditionally been more concerned with topics such as role learning and specialisation, emergent system properties and learning cooperative behaviours.
In this seminar, I will briefly talk about the different approaches to single-agent reinforcement learning. I will then move on to discuss the opportunities for parallelization of these algorithms, and present some results on specific algorithms that I have developed based on these ideas.
Date: 27th October 2005, 13:15, Room M023, Biology M-block, Univ. of York
Bayesian inference via Markov chain Monte Carlo for Phylogeny, Classification Trees and Pedigrees
James Cussens, University of York
The Bayesian approach to using data to infer models is appealingly simple. Starting from a prior probability distribution [P(M)] over all models considered possible, data [D] is used to compute a posterior distribution [P(M|D)]. For each model M, P(M|D) states the probability that M is the true model in light of the data. P(M|D) can be used, for example, to return the most likely model. Unfortunately, computing or even representing P(M|D) exactly is often computationally impossible. Markov chain Monte Carlo (MCMC) is a way of approximately getting to P(M|D). In this talk I will explain the basic ideas behind MCMC and show how it can be used in Bayesian approaches to phylogeny, classification trees and pedigrees.
Joint seminar with Bioinformatics Lunch Club
Date: 8th June 2005, 14:00, Room CS103, Computer Science Building, Univ. of York
Steps towards Cognitive Vision
Tony Cohn University of Leeds
In this talk I will present some results from a recent EU project on Cognitive Vision. Our main goal was to build a system which could take perceptual inputs (both visual and auditory) turn them into symbols, reason about the behaviour being observed and then demonstrate the understanding by having the computer perform actions in the world. Moreover, our aim was for the system to learn all this autonomously, simply by observing the world. I will discuss a system which achieves this in a simple table top game world, watching two players, and then taking over the part of one of the players using a talking head. The behavioural descriptions are learned through inductive logic programming (Progol). We are also able to learn mathematical principles such as equivalence and transitivity of orderings. I will also discuss how we were able to improving classification by reasoning about spatio-temporal continuity.
Date: 13th May 2005, 12:15, Alcuin EW/104
Collective Intelligence in Ants: the Example of Brood Sorting
Ana Sendova-Franks, School of Mathematical Sciences, Faculty of Computing Engineering and Mathematical Sciences, University of the West of England
Abstract: Anthropocentric definitions of intelligence ignore the problem-solving abilities of many animal species and insects in particular. This hinders our understanding of the evolution of intelligence and related developments in AI. The phenomenon that best illustrates this is collective intelligence or the ability of a group to solve problems that are beyond the scope of an individualÃÆs overview. Insect societies are capable of tremendous feats of collective intelligence. Decision-making during nest choice in ants and bees, improvement in collective performance with experience in ants and building in wasps and termites are just a few examples.
Social insects are complex distributed systems honed by millions of years of natural selection. Understanding their problem-solving abilities requires an interdisciplinary approach at the interface between biology, computer science, mathematics and statistics.
The relatively small societies of temperate ants living in flat crevices in rocks are an ideal model system for studying collective intelligence in social insects. The living space of these ants can be approximated to two dimensions and we can follow the behaviour of all individuals all the time under controlled conditions.
A classic example of collective intelligence in these rock ants is their ability to sort the brood in concentric annuli (semi-annuli or bands) of items at different stages of development. The smallest items are in the middle and the largest on the periphery. Ants can re-establish this pattern within 48 h after an emigration to a new nest site. The question is: how do ants do that? I will talk about the latest results from biological experiments aiming to answer this question. Our current understanding of the mechanisms underlying brood sorting can be summarised by a process consisting of two phases. An initial phase of clustering all items is followed by a phase of spacing them out. During this second phase, the differential diffusion of items of different type leads to the sorted pattern.
Further understanding of this process requires individual-based computer modelling. The underlying algorithms of individual behaviour could inform AI algorithms for distributed sorting. Computer modelling in turn could inform analytical models. The general principles of such mathematical models are likely to be applicable to a wide range of biological sorting phenomena, from cell movement during morphogenesis to the behaviour of individuals in animal groups, as well as to the behaviour of AI sorting algorithms.
Refs
Date: 4th March 2005, 12:15 CS119N
Numerical Constraint Solving: Contributions and Application to Virtual Camera Control
Marc Christie, LINA, Laboratoire d'Informatique de Nantes Atlantique, UniversitȨ de Nantes, Nantes, France
Abstract: This talk will present some contributions to numerical constraint solving their application to virtual camera control.
Many industrial real-life problems can be expressed as a set of linear or non-linear equations or inequalities on numerical variables. Recent numerical techniques such as hull and box local consistencies provide an efficient and reliable answer based on interval arithmetics. These techniques offer estimable guaranteed properties such as contractance, monotonicity and completeness. Whereas completeness gives rise to an outer-approximation (an approximation that encloses a possible solution to the problem), some applications in robotics, civil engineering or computer graphics require the computation of an inner-approximation (all points of the approximation are solutions). We first propose a technique to compute inner-approximations of a set of inequalities via constraint negation and extend this technique to manage a universally quantified variable.
In the second part of the talk, we present how these techniques are integrated in a virtual camera control tool. Virtual camera control consists in positioning and animating a camera in a virtual world, such that the resulting images satisfy a set of visual cinematographic properties. Current 3D modellers surprisingly lack tools to assist the user, despite the fact that cinema has provided a rich grammar that allows a director to clearly describe shots. Modellers are based on complex mathematical notions (spline curves, velocity graphs) more or less hidden by high-level manipulators. Manipulators allow positioning and animating the camera, but lack correlation with well established cinematographic notions relative to camera composition (object framing, distance shot specification, relative viewing angles, occlusions) and camera movement (travelling, panoramic, arcing). We propose to rely on this grammar to provide a high-level approach to camera control. The description of the user is translated into numerical constraints on both the parameters of the camera and the path. We introduce the hypertube paradigm as a model for the camera path and as an incremental solving procedure. Experimental results illustrate this approach.
We finally conclude the talk with our on-going work on semantic space-partitioning for virtual camera composition and numerical local search techniques.
Date: 23th February 2005, 14:00 CS103
Proactive Exploitation of Symmetry in Planning
Maria Fox (Univ. of Strathclyde)
Abstract: Automated Planning is the problem of finding partially ordered sequences of activities to achieve specified sets of goals. These sequences are called plans. Planning has been applied to a variety of real world problems of interest, including the control of a spacecraft (NASA's Deep Space 1 project), the generation of power plant start-up routines, the development of delivery schedules in both military and civilian logistics contexts, and so on. The domain of a planning problem can be very complex, giving rise to astronomically-sized, or infinite, search spaces. Finding plans efficiently therefore relies on the exploitation of powerful heuristics and search control strategies.
Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that, in domains with obvious symmetric structure, the exploitation of symmetry can dramatically reduce the size of the search space and the time taken to find a solution. Researchers have considered how to exploit symmetry-breaking to prune symmetric parts of the search space in Constraint Satisfaction Problems (CSPs), Model Checking, Formal Verification and in Planning.
Unfortunately, the symmetry in a problem is not always apparent but may be hidden in the structure of the problem. Applying an appropriate abstraction to the problem domain can reveal hidden symmetries and make them available for search control. However, symmetries of the abstracted problem are not necessarily symmetries of the original problem, so they cannot be used for pruning the search space without risking the loss of completeness. In the work described here we present an alternative approach: instead of using such symmetries for pruning we use them in a proactive way to guide choices during search. We show that this approach is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerful alternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of Almost Symmetry is defined and results are presented showing that proactive exploitation of almost symmetry leads to statistically significant improvements in the performance of a heuristic forward search planner.
Date: 11th February 2005, 12:15 CS119N
Existing approaches to Ontology Learning
Klapaftis Ioannis
Abstract: Semantic web aims to increase the comprehensibility of web documents both by machines and humans and their transportability. The development of such a web has made the role of ontology engineering increasingly crucial. Ontology learning is concerned with methods and techniques that enable the automatic, error-free, time saving and low cost acquisition of the knowledge required to build ontologies. This presentation provides an overview of the systems developed and the methodologies used in order to accomplish the task of ontology construction with particular emphasis on learning.
Title: An Overview of Knowledge Discovery: Information Extraction and Multi-Relational Data Mining
Alfred Rayner
Abstract: Knowledge discovery in databases (KDD) was initially defined as the "non-trivial extraction of implicit, previously unknown, and potentially useful information from data". Information Extraction (IE) and Data mining (DM) are two of the main steps in the KDD process. The information extraction finds useful information about the domain and encodes the information in a structured form, suitable for populating database. On the other hand, Data Mining (DM) concerned with applying computational techniques to actually find patterns in the database. However, most existing data mining approaches are propositional and look for patterns in a single data table. Multi-relational data mining (MRDM) approaches, many of which based on Inductive Logic Programming (ILP), look for patterns that involve multiple tables (relations) from a relational database. Multi-relational data mining (MRDM) has a key to play in the growth of KDD. This presentation briefly surveys some of the main drivers, prospects and challenges in Knowledge Discovery's fields of Information Extraction and Relational Data Mining.
Date: 28th January 2005, 12:15 CS119N
Title: Gate: an open-source infrastructure for natural language processing - overview and example applications
Kalina Bontcheva and Hamish Cunningham, Natural Language Processing Group, Department of Computer Science, University of Sheffield.
Abstract: In this talk I will present GATE, an open-source framework and graphical development environment which enables users to customise, develop, and deploy language processing tools in a robust fashion. We will also discuss how the GATE architecture has enabled us to develop a number of successful applications for various language processing tasks, with a focus on Information Extraction. I will also discuss how the system can be applied in combination with machine learning techniques. A brief demo will be available.