Date Friday 25 January, 2002, 12:30, CS202J
Inductive logic programming: what it is and how to use it
James Cussens
Artificial Intelligence Group
Department of Computer Science
University of York
Abstract: This seminar will introduce inductive logic programming (ILP) focussing on how to apply it. ILP is simply machine learning where a logic program is what gets learnt. Much of the input to an ILP algorithm also takes the form of a logic program, facilitating iterative approaches. Crucially this includes "background knowledge" in the form of facts and rules about the domain of application. Much of the seminar will consist of demos of a particular ILP algorithm: Srinivasan's ALEPH. I will focus on (i) saturation, (ii) refinement search, and (iii) the effect of different evaluation functions. I will also let you in on all those mysterious parameter settings they don't mention in the papers...
Date Friday 1 February, 2002, 12:30, CS202J
Stochastic Simulation of Inherited Kinship-driven Altruism
Heather Turner
Department of Computer Science
University of York
Abstract: A system for simulating population evolution is presented. The hybrid approach combines the personality-driven advantage of the multi-agent system with the scalability of the genetic algorithm. Assuming the existence of a hypothetical kinship-driven altruistic (or selfless) gene, experiments are proposed to investigate the conditions required to achieve its positive selection in the simulated environment. Some theory and motivation will be discussed, along with a description of the test system and proposed experiments.
Modelling the Constraints that Influence Cycle Commuter Choices
Wulf Thannhaeuser
Department of Computer Science
University of York
Abstract: The overall aim of this project is to investigate different ways in which hypotheses can be learned from a given dataset using machine learning techniques. The algorithms discussed in this project are instances of Inductive Logic Programming and Decision Tree algorithms. The dataset that will be analysed is the result of research carried out in the Department of Sociology of the University of York. It is investigating the ways in which different factors affect the people's willingness or ability to cycle to work. We want to extract hypotheses that should be able to accurately predict how often somebody will use a bicycle to commute to work.
Date Friday 8 February, 2002, 12:30, CS202J
Solving Max-XOR-SAT Problems with Stochastic Local Search
Mark Minichiello
Department of Computer Science
University of York
Abstract: Given a set of xor-clauses (a set of literals joined by exclusive-or operators), the Max-XOR-SAT problem is to find a truth assignment that satisfies the maximum number of these clauses. The roots of this problem, in Cryptanalysis, will be discussed, as well as methods for solving it - one of which is a modified version of WalkSAT, a stochastic local search algorithm.
Investigating Noise Parameters in WalkSAT
Peter Nightingale
Department of Computer Science
University of York
Abstract: The propositional satisfiability problem (SAT) can be solved with WalkSAT, a stochastic local search (SLS) solver which takes a noise parameter. This parameter determines the likelihood of making 'wrong' moves when seeking a solution, in order to get the search out of local minima. With the noise parameter set suboptimally, the algorithm performs poorly. This seminar is about assigning a noise parameter not to the whole search, but only to a specific clause type, in the hope that the search can be sped up. As an example, graph colouring can be translated into SAT with two clause types.
Solving Permutation Problems with Stochastic Local Search
Linus Thand
Department of Computer Science
University of York
Abstract: NB-WalkSAT, a stochastic local search procedure for non-Boolean SAT, has been extended to take advantage of the all-different constraints found in some problems by searching a space containing only those assignments that are permutations. This new approach to solving permutation problems with stochastic local search will be discussed and results of experiments presented.
Date Friday 15 February, 2002, 12:30, CS202J
Searching Hidden Markov Models
Nicholas Cook
Department of Computer Science
University of York
and Marconi
Abstract: This talk constitutes my literature review seminar that all research students at York undertake in their first 3 months of registration. As such, it will critically review some of the literature covering hidden Markov modelling with particular emphasis on its exploitation in speech recognition. As is normal in this situation, plans for future research will not be covered.
This talk will provide a gentle introduction to hidden Markov modelling, and then concentrate on strategies used to search these models. These strategies include dynamic programming - Viterbi - and stack based decoding - A*. The talk will include the use of acoustic and language model parameters during the search. Hybrid algorithms will also be discussed.
Date Friday 22 February, 2002, 12:15, CS202J
Integrating Speech Recognition, Natural Language Processing and Character Animation
Andy Coates
Department of Computer Science
University of York
Abstract: An overview of the design and implementation of a prototype system combining technologies from research in SR, NLP and Animation (IBM ViaVoice, Mercury and GTK++). The prototype enables voice control of an animated character within a virtual world, and is extensible in all three dimensions.
More details on the project can be found at: http://www-student.cs.york.ac.uk/~apc105/project/
Date Friday 1 March, 2002, 12:15, CS202J
Reinforcement learning of coordination in cooperative multi-agent systems
Spiros Kapetanakis
Department of Computer Science
University of York
Abstract: We propose a reinforcement learning technique for the learning of coordination in cooperative multi-agent systems that is based on Q-learning and incorporates a novel action selection strategy in the form of a chirp temperature function. This new technique is applicable to scenarios where mutual observation of actions is not possible.
To date, Q-learning approaches for such independent agents did not achieve convergence towards the optimal joint action in scenarios with high miscoordination costs. We improve on previous results by demonstrating that our extension causes the agents to almost always converge to the optimal joint action even in these difficult cases. Furthermore, convergence speed is improved over other existing techniques.
Optimisation of PID Controller Parameters using Genetic Algorithms
Chris Peake
Department of Computer Science
University of York
Abstract: Many learning agents move using discrete actions in a two-dimensional world. By harnessing the continuous and robust features of classical Proportional-Integral-Derivative (PID) controllers, it might be possible to create learning agents that can move in continuous time in a three-dimensional world. However, these controllers must be tuned to produce the desired system (agent) response, and this currently requires a good knowledge of control theory and lots of experience. This project exploits the stochastic, robust nature of genetic algorithm search techniques in an attempt to tune these controllers using machine learning.
Date Wednesday 6 March, 2002, 14:00, CS103
Bayesian Networks for Paternity Testing via DNA
Robert Cowell
Department of Actuarial Science and Statistics
City University
Abstract: In the past couple of years, through work of Dawid and coworkers, it has become possible to formulate complex problems of identity and paternity using DNA samples as probability calculations using probabilistic expert systems (PES). I shall discuss these developments as they relate to a prototype software package I have developed, called FINEX, that enables these calculations to be performed quickly and accurately, overcoming some of the limitations of implementing such problems using current standard PES software.
Date Wednesday 13 March, 2002, 14:00, CS103
Assisting Joint Catalogue Purchases
Daniel Kudenko
Department of Computer Science
University of York
Abstract: To date, online catalogue purchase assistants have mainly been looked at from a single-agent perspective, where only the interests of a single user are taken into account. We extend this scenario and look at cases where more than one user is involved in the purchase, and therefore many (potentially conflicting) interests have to be considered.
In this talk I will present an overview of a system that assists a group of users to reach a joint decision on an online catalogue purchase. This is done by acquiring individual user models and using these models to simulate negotiations that are subsequently presented to the users for further explanation and argumentation. Our research thus combines the areas of user-modeling and multi-agent systems negotiation.
The research is joint work with Mathias Bauer and Dietmar Dengler, DFKI, Germany.
Date Wednesday 1 May, 2002, 14:00 CS103
Understanding Intelligent Agents: A Multi-Paradigm Analysis
John Fox
Cancer Research UK
Abstract: Formal and informal aspects of agent technologies are analysed from several different perspectives, both to inform the development of applications (e.g. in clinical medicine) and to gain a deeper understanding of the concept of an "intelligent" agent . First we discuss the meaning of the "agent" concept with respect to (a) general functional capabilities and (b) the classic BDI model. We then outline the "domino" agent model which has developed out of our experience on developing technologies for clinical applications, and the PROforma toolset for building applications based on this model. The main body of the paper is a review of the PROforma framework from three contrasting viewpoints: logic programming, object-oriented programming and agent-oriented programming. The paper closes with a proposal for an extended agent theory which integrates the three perspectives.
Date Friday 10 May, 2002, 12:15 CS202J
Language Evolution from Iterated Learning
Simon Kirby
Department of Linguistics
University of Edinburgh
Abstract: Understanding the origins of human language is a uniquely challenging scientific problem. A truly explanatory account of the emergence of language must answer a fundamental question: why are languages the way they are and not some other way? The evolutionary linguist aims to answer this by posing a second question: how did language arise from non-language? In this talk I will present a computational approach to language evolution termed the Iterated Learning Model (ILM). In the ILM, individuals are modeled as computational agents that learn by observing the linguistic behaviour of other agents. They then produce behaviour themselves, which in turn forms the input for training new learners. The dynamic properties of languages in an ILM depend on the choice of prior bias for the learning model and the structure of the environment on which the agents' linguistic behaviour is based. I will survey a number of results from the ILM which suggest some surprising conclusions. In particular, biological evolution and communicative function might have less to do with the origins of syntactically structured language than was previously thought. Instead we need to think about human language as an adaptive system in its own right --- one whose structure depends on the pressures that arise from the process of iterated learning.
Date Wednesday 15 May, 2002, 14:00 CS103
Robust Accurate Parsing of Natural Language
Ted Briscoe
Computer Laboratory
University of Cambridge
Abstract: We describe a robust accurate domain-independent approach to statistical parsing incorporated into the new release of the ANLT toolkit and soon to be publically available as a research tool. The system has been used to parse many well known corpora and as a component in an open-domain question answering project. The performance of the system appears competitive with that of statistical parsers utilizing highly lexicalized parse selection models. However, we plan to extend the system to improve parse coverage, depth and accuracy.
Date Friday 17 May, 2002, 12:15 CS202J
Can diagrammatic reasoning be automated?
Mateja Jamnik
Computer Laboratory
University of Cambridge
Abstract: Theorems in automated theorem proving are usually proved by formal logical proofs. However, there is a subset of problems which humans can prove by the use of geometric operations on diagrams, so called diagrammatic proofs. Insight is often more clearly perceived in these proofs than in the corresponding algebraic proofs; they capture an intuitive notion of truthfulness that humans find easy to see and understand. We are investigating and automating such diagrammatic reasoning about mathematical theorems. Concrete, rather than general diagrams are used to prove particular concrete instances of the universally quantified theorem. The diagrammatic proof is captured by the use of geometric operations on the diagram. These operations are the ``inference steps'' of the proof. An abstracted schematic proof of the universally quantified theorem is induced from these proof instances. The constructive omega-rule provides the mathematical basis for this step from schematic proofs to theoremhood. In this way we avoid the difficulty of treating a general case in a diagram. One method of confirming that the abstraction of the schematic proof from the proof instances is sound is proving the correctness of schematic proofs in the meta-theory of diagrams. These ideas have been implemented in the system, called DIAMOND, which is presented here.
Date Friday 24 May, 2002, 12:15 CS202J
The Application of Automated Theory Formation to Machine Learning Tasks
Simon Colton
Division of Informatics/Department of Computer Science
University of Edinburgh/University of York
Abstract: A major machine learning application is classification prediction: given some objects of interest and their classification into a schema, learn a way of classifying a generic object of interest with (hopefully) high accuracy. One way to do this is to learn a (usually small) set of rules which apply to the objects, for instance, a train is going East if and only if it has a small, closed, carriage. This works fine for certain problems where there is a definite answer (I call these IQ-test style problems). However, in other cases, there may not be a set of rules which can be found and used for prediction. An example I'll draw on is finding someone guilty or not guilty, where it is a bad idea to stick to a single rule, or small set of rules, but better to have a "moral theory" and take a more considered approach towards the learning problem. In the talk, I'll describe how the HR program forms such theories and how it uses them for prediction tasks. The two open questions I would like help answering are: (i) is it a good idea to do prediction tasks in this manner and (ii) is it a novel approach.
Date Monday 10 June, 2002, 11:30 CS119N
Extracting coarse domain rules using Self Organizing Maps
Peter Matthews
Engineering Design Centre
Department of Engineering
University of Cambridge
Abstract: The process of designing mechanical artefacts requires the actors (designers) to have a model of the design space. Such models are often tacitly contained in the heads of designers, typically as a result of several years experience in the field, and are difficult to extract. A method is presented, using Self Organizing Maps, that extracts a set of coarse rules (heuristics) from a given distribution of previous design examples. These rules describe relationships between various components in the sample distribution. This method will be illustrated using an artificial design problem, and results from real case studies will be presented. To conclude, a discussion on how this method can be modified and extended to analyse domains other than mechanical design.
Date Thursday 15 August, 2002, 14:00 CS202J
Ethical Constraints in Research
Toby Walsh
Cork Constraint Computation Centre
University College Cork
Cork
Ireland
Abstract: What ethical constraints should we apply during research? Why should we worry? How do ethical constraints affect all parts of the research cycle: hypothesis, experiment, analysis, publication, reviewing, etc.
Date Friday 27 September, 2002, 12:15 CS103
Making Reinforcement Learning Work
Malcolm Strens
Qinetiq
Abstract: Reinforcement learning is a problem description rather than a particular solution method, although the term has been most closely associated with "primitive" (model-free) algorithms such as Q-learning and SARSA. Now there are many parallel strands of research, attempting to solve much more difficult problems than the fully-observable discrete-state ones on which the primitive methods were developed. I will describe 3 classes of solution method: model-based, primitive, and policy search/gradient.
Model-based methods often assume the dynamics of the environment and reward function are known (as an MDP, POMDP or DBN) and can find policies by dynamic programming over these models. If the model is not known, it can be learnt from experience. I will describe Bayesian approaches that address the exploration/exploitation dilemma in the scenario [1].
Primitive RL methods have developed through the use of function approximators to represent the state-action value function, and the introduction of more effective learning rules (e.g. temporal difference learning). More recently, primitive RL has been applied in the partially observable setting by providing a baseline state-action value function to policy search methods, and developing a variant of Q-learning that is robust in a partially-observable setting.
Policy search and policy gradient methods operate in a parameterised space of policies. These methods have the advantage that they are effective in partially-observable settings and can incorporate prior knowledge about effective behaviour. I will focus on direct policy search, the main topic of my recent research [2]. In particular, I'll show that reliable policy search can be obtained even when the evaluation of a policy in a simulation trial is stochastic.
The future of RL probably lies in developing hybrid methods that combine the best characteristics of 2 or more of these approaches. Of particular interest is how to scale RL to operate on problems with high-dimensional state, multiple timescales, and multiple agents. In these settings, we need to go beyond the attribute-value representations used in primitive RL and DP; it is possible that this might be achieved through hybrid symbolic/computational methods. I will use the problem of coordinating a group of Unmanned Airborne Vehicles as an example, and discuss how RL might fit-in with a hierarchical task-execution framework for autonomous systems.
[1] Strens, M. J. A. (2000). A Bayesian framework for reinforcement learning. Proceedings of the Seventeenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann.
[2] Strens, M. J. A. and Moore, A. W. (2001). Direct policy search using paired statistical tests. Proceedings of the Eighteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann.
(Refs [1] & [2] are available from my personal website www.strens.com)
Date Friday 4 October, 2002, 12:15 CS103
Stochastic Constraint Programming
Armagan Tarim
Artificial Intelligence Group
Department of Computer Science
University of York
Abstract:
This talk proposes a new approach, scenario generation incorporated
into the constraint programming framework, to tackle a class of
stochastic optimization problems. Scenario based constraint
programming, SB-CP, is an extension of constraint programming to deal
with a class of models and algorithms in which some of the data may be
subject to uncertainty. Such models are appropriate when data evolve
over time and decisions need to be made prior to observing the entire
data stream. Under such circumstances it pays to develop models in
which plans are evaluated against a variety of future scenarios that
represent alternative outcomes of data. Such models yield plans that
are able to cope with uncertainty. Because of these properties, SB-CP
models have potential applications in areas, such as natural language
processing, financial risk management, production/inventory
management, to mention a few.
Date Wednesday 16 October, 2002, 2:00 CS103
Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning
Ian Miguel
Artificial Intelligence Group
Department of Computer Science
University of York
Abstract: Constraint satisfaction is a fundamental Artificial Intelligence technique for knowledge representation and inference. However, it has become increasingly clear that the classical formulation is insufficient. There are two main areas of weakness: firstly, the inability to deal with flexibility in the problem description in case no `perfect' solution exists, and secondly the inability to deal gracefully with changes to the problem structure. In order to address the first weakness, classical constraint satisfaction has been extended to incorporate different types of flexible constraints. Similarly, the techniques of dynamic constraint satisfaction have been developed to overcome the assumption of a static problem structure.
These two types of extension separately offer significant advances in the range of problems that constraint satisfaction can solve. This talk presents the combination of these two disparate extensions into a single framework: dynamic flexible constraint satisfaction. This framework is able to model changes in a dynamic environment, while retaining the greater expressive power afforded by flexible constraints. As an application, classical AI planning is extended by incorporating preferences into plan operators and goals. This allows a systematic tradeoff between the length of a plan versus the number and severity of the compromises it contains. It is demonstrated that flexible plan synthesis can be reduced to the solution of a hierarchy of dynamic flexible constraint satisfaction problems. This procedure is implemented in the Flexible Graphplan system, which is presented here.
Date Wednesday 23 October, 2002, 2:00 CS103
Toward Mixed-Initiative Recommender Systems
Derek Bridge
Computer Science Department
University College Cork
Abstract: Consumers use Recommender Systems to find products and services. Most typically, customers are invited to articulate their requirements, e.g. using an on-screen form, and these are then matched against a database of product descriptions.
In this talk, I will give a brief, high-level overview of the state of the art in recommender systems. I will argue that many of these systems would be improved if they were to accommodate a wider range of conversational moves within a mixed-initiative dialogue.
I will highlight the importance of dialogue management in systems that support mixed-initiative interaction. I propose an approach that uses a Conversation Policy specified by both a dialogue grammar and a process model.
The dialogue grammar makes explicit the opportunities the user and system have for seizing and ceding the initiative. But it maintains only local dialogue coherence. The process model is used to achieve global dialogue coherence.
The ideas will be illustrated with reference to two systems that I have built.
Date Friday 25 October, 2002, 12:15 CS202J
In the Future Work Series:
Distributed Inductive Learning In The Real World
Daniel Kudenko
Artificial Intelligence Group
Department of Computer Science
University of York
Abstract: In this talk I will argue that current
assumptions made in the applications of inductive machine learning algorithms
are not suitable in realistic agent and multi-agent scenarios, namely where
agents are situated in a real-world, or real-world-like environment and use
limited sensors. Due to these shortcomings there is a need for the evaluation of
(distributed) inductive learning methods under the new set of assumptions,
specifically in a multi-agent learning environment. The results of these
experimental evaluations are expected to lead to novel inductive learning
techniques that are specifically tailored to realistic multi-agent systems.
Date Friday 1 November, 2002, 14:00 CS103
Automatic Reformulation of Constraint Satisfaction Problems
Ian Miguel
Artificial Intelligence Group
Department of Computer Science
University of York
Abstract: Constraint satisfaction is a successful technology for tackling a wide variety of search problems including resource allocation, transportation and scheduling. It is widely recognised that the input model of a constraint satisfaction problem (CSP) has a substantial effect on the ability of a solution procedure to solve it efficiently. Constructing an effective model of a CSP is, however, a challenging task as new users typically lack specialised expertise. This talk will describe how an initial input model can be reformulated automatically into a more effective representation.
Preparatory to reformulation, it is important to establish
patterns of modelling constructs which appear frequently. One common pattern is
that of a matrix of decision variables. A problem often associated with matrices
is the presence of symmetries, which can lead to a large increase in search
effort. An effective means of dealing with these symmetries will be presented.
Automatic reformulation is implemented in the Cgrass system, which captures
common patterns in the hand-transformation of CSPs in transformation rules.
Cgrass' operation will be illustrated via the Golomb ruler, a challenging
problem from combinatorial mathematics. The talk will conclude with a discussion
of directions for future research.
Date Friday 29 November, 2002, 12:15 CS202J
Constraint Technology for the Masses
Alan M Frisch
Artificial Intelligence Group
Department of Computer Science
University of York
Though many companies have problems of vital commercial importance that could be solved with a constraint programming toolkit they do not do so because of a lack of the expertise that is required to model problems as constraint programs. My research aims to bring the proven power of finite domain constraint technology to a wider user base by systematising some of this expertise and, ultimately, to the masses by concealing the technology behind intuitive user interfaces.
I intend to pursue this goal by identifying and studying patterns that arise frequently in constraint programs. Work has begun with one of the most prevalent and powerful patterns--the matrix of decision variables. This talk will focus on initial results in two areas: the systematic reformulation and refinement of problems specified in an abstract language into executable constraint programs that exploit matrices and the breaking of symmetries that arise commonly in matrix formulations. The talk concludes by speculating on how this technology can be made accessible through a spreadsheet interface.
Date Friday 6 December, 2002, 12:15 CS202J
Soft Learning: A Bridge Between Data Mining and Machine Learning
Flaviu Marginean
Artificial Intelligence Group
Department of Computer Science
University of York
It has been felt for some time that, despite employing different formalisms, being served by their own dedicated research communities and addressing distinct issues of practical interest, problems in Data Mining and Machine Learning connect through deep relationships.
We present Soft Learning, a concept designed to describe those problems in Data Mining that can be seen as forms of soft Machine Learning. We explain the significance of the new concept and discuss its relevance to Soft Computing. We give two definitions for Soft Learning, whereof the second is a formal embodiment of the first. We show how this definition unifies many apparently distinct problems and settings in Data Mining and Machine Learning. The relationship between Soft Learning and previous related attempts, such as agnostic, heuristic or robust learning is discussed. As a prerequisite to this analysis, a PAC-learnability analysis for Optimal Soft Learning is outlined. It is shown that agnostic learning or robust learning are forms of Optimal Soft Learning, whilst heuristic learning can be seen as a form of Threshold Soft Learning.