Date: 8th December 2006, 12:15, CS202J Computer Science, Univ. of York (Fri week 9)
Talking with Robots: A Case Study in Architectures for Cognitive Robotics
Dr Jeremy Wyatt, Leverhulme Research Fellow, School of Computer Science, University of Birmingham
In what ways can we integrate multiple types of sensing and action in a robot? This question gets to the heart of deep issues in AI such as the nature and use of representations, and the control of the flow of information in a cognitive architecture. In this talk I will describe some work we are doing on architectures for cognitive robots. I will start by detailing our early work on systems that used and understood utterances about a scene with objects. These experiences led us to design an architecture for developing cognitive robots which we call CAAT. I will describe this, the requirements it is designed to satisfy, its relation to some other architectures, and two early robot systems we have constructed using it.
Date: 10th August 2006, 12:15, CS202J Computer Science, Univ. of York
Title: Evolutionary Computation applied to Sound Synthesis
James McDermott, Dept. of Computer Science and Information Systems, University of Limerick, Ireland.
Sound synthesis is a very powerful technique in the hands of modern musicians, but many beginners and non-technical users have difficulty with the task of understanding a synthesizer's input parameters, and adjusting them to get a desired timbre.
Evolutionary Algorithms, which are based on the ideas of Darwinian natural selection, can provide an alternative method of synthesizer control, in which we evolve a population of timbres, rather than constructing them directly.
This talk will be about our work on both interactive and non-interactive evolution, and about possible future applications of Evolutionary Algorithms to sound and music computing.
Date: 23th June 2006, 12:15, CS202J Computer Science, Univ. of York
Title: Pattern-Based Transformation Approach to Relational Domain Learning Using Dynamic Aggregation for Relational Attributes
Alfred Rayner, University of York
Most standard databases are modelled based on the analysis of functional dependencies (FDs) and this leads to the creation of multiple tables associated through primary and foreign keys. Data representation for data stored in a relational model differs from the traditional feature-vector (single table) representation used in traditional data mining tasks. Data mining tasks for relational database systems are attractive because of the expressive power of relational models and the ability of the learning methods to incorporate relational background knowledge. However, model induction for data extracted from multiple tables requires aggregation of the values of attributes of related entities. The aggregation of the values of related entities into single attributes is an essential component of relational model induction, and has significant impact on generalization performance for domains with important 1-to-n relationships.
I will present a novel transformation-based approach to relational domain learning and describe the transformation process implemented through relational aggregation based on pattern's distances. I will present the prototype of ``Dynamic Aggregation of Relational Attributes'' (hence called DARA) that is capable of mapping one-to-many relationship into one-to-one relationship, while preventing loss of information, in handling classification task in relational domains. I will experimentally show these results in a multi-relational domains and illustrate set of rules extracted using this approach.
Date: 2th June 2006, 12:15, CS103 Computer Science, Univ. of York
Modelling complex (ecological) communities: achievements and challenges
Jim Bown, SIMBIOS Centre, University of Abertay Dundee
Biological systems are inherently complex and exist at, and are interconnected through, a vast range of scales. The ecology and evolution of these systems are driven by interactions and diversity respectively among the individual organisms that comprise these systems. Much research activity in biology generally and ecology in particular strives to relate patterns emergent at the scale of the community, such as productivity and coexistence, with the diversity of processes and physiology manifest at the scale of the individual.
I will, using plant systems as an exemplar, present a conceptual framework that links individual behaviour to community functioning. The fundamental accounting unit of the approach is the individual plant and this is characterised by a series of physiological traits. Importantly, the model parameters are determined by extended feedback. The traits are interrelated by a process-based model. The model successfully predicts the generic log-normal form of the relative abundance curve of individuals together with its dependence on species richness and productivity - a first for individual-based modelling. Further, we have made two clear extensions to this work. First, we have extended the framework to account for memory in the system, in terms of both seed banking and gene flow. Second, we have transported successfully the framework to fungal community dynamics. The results of each will be outlined.
However, we have yet to address two major challenges. First, we need to analyse statistically the spatio-temporal patterns that emerge from this and related models, and we are developing a methodology for this with, among others, researchers at York! Second, and more challenging still, we must link across spatio-temporal scales. This requires a generalisable successive and progressive model abstraction process to bridge more than ten orders of magnitude ... ideas welcome!
Date: 26th May 2006, 12:15, CS202J Computer Science, Univ. of York
Undergraduate project talks
Theatre Staff Rostering for the Edinburgh Festival: A Constraint Programming Approach
Mark Hansed, University of York
We take a constraint programming approach to a real world rostering problem for theatre staff at the annual Edinburgh festival. The staff roster has to take into account several requirements, some of which are mandatory, for example the presence of a first-aider on every shift, others of which are preferences, for example staff working together with friends. The feasibility of constraint programming techniques for solving the theatre staff rostering problem are considered; an analysis of requirements is undertaken, several problem models are proposed, and the problem structure is investigated in an attempt to improve efficiency.
The solution is realised within the constraint programming language ECLiPSe, and tested on several problem instances similar in size to those faced in real life. Although only a subset of the requirements are considered at this stage, rosters are found that meet all of these requirements within a reasonable amount of time. It is expected that the addition of the remaining requirements, alongside more problem inspired heuristics, would also give satisfactory solutions within a reasonable amount of time.
Developing an Automated Testing Tool for the Hyper-Arc Consistency Property of Constraint Propagation Algorithms
Andrew James, University of York
Constraint programming is an emergent software paradigm which has the potential to solve many complex real-life problems, such as scheduling. Constraints simply specify the relationships between objects, such as white cars cannot be produced directly after black cars on a production line. Constraint Propagation Algorithms (CPAs) provide much of the solving power of the underlying implementation by pruning the search space used to find solutions that satisfy all of the constraints for a given problem, but they must be tailored towards each specific constraint.
CPAs are often complex and as constraint programming is applied to different situations, new CPAs are required for the new constraints that have been developed. In this project, an automated testing tool was developed to test if a CPA is sound (no values that could participate in a solution are removed) and complete with respect to hyper-arc consistency (all values that cannot participate in a solution are removed), as well as providing other meaningful statistics to help with error detection or correction.
Date: 23th May 2006, 12:15, CS202J Computer Science, Univ. of York
Estimating probabilities of Induced Control Rules to plan robustly in non-deterministic domains
Sergio Jim�ez, Universidad Carlos III de Madrid - Spain
When planning in probabilistic domains two main approaches are used, Markov Decision Processes and Decision-Theoretic Planning. Both approaches need a domain representation with the exact probabilities of the actions effects. But when planning in realistic domains most of the times these probabilities are unknown or hard to be obtained accurately.
We are developing the LUCK architecture (Learning Uncertainty information as Control Knowledge) to plan in probabilistic domains without knowing a priori these probabilities. This architecture plans to solve problems in probabilistic domains using an initial deterministic domain representation. And learns information about the success of the actions applying Inductive Logic Programming and Parameter Estimation Techniques to generate better plans (in terms of robustness) in the future.
Date: 24th February 2006, 12:15, CS119N Computer Science, Univ. of York
Web Usage Mining for Website Design Improvement
I-Hsien (Derrick) Ting, University of York
To understand users' browsing behaviour is essential for who wants to improve the website's design. In server-side, users' browsing history is recorded in a Clickstream data(logs file), and this is an easier and cheaper way for us to analyse user's browsing behaviour.
In this seminar, an approach about how to use data mining technique to analyse the Clickstream data for website design improvement will be introduced. I will discuss from the format of Clickstream data to data collection, data pre-processing, visualisation, pattern discovery and analysis, how to generate recommendation and how to take action.
An empirical study will also be reported in the end of my presentation to show how a website can use this approach for improving the website's design.
Date: 17th February 2006, 12:15, CS119N Computer Science, Univ. of York
A Study of Concurrency in the Ant Colony System Algorith
Enda Ridge, University of York
This seminar reports the results of a study of a specific type of concurrency in the Ant Colony System (ACS) algorithm. Studies of Cellular Automata (CA) have shown that the update mechanism used can have a dramatic influence on the dynamics of the CA. ACS is usually implemented with a sequential update mechanism.
A new method for controlling the concurrency in a nature-inspired algorithm is introduced. Comprehensive tests on a wide range of problem instances are reported. The study found that concurrency levels had no statistically significant effect on ACS performance.This result is interesting because it contradicts what has been observed in another form of nature-inspired algorithm, namely CAs.
This seminar will give a background of the ACS algorithm, details of the experiments performed, and an analysis of the results obtained.
Date: 10th February 2006, 12:15, CS119N Computer Science, Univ. of York
Undergraduate project talks
Designing a PA Agent
Manik Chakravarti
Aim: The aim of the project is to design and implement.a Personal Assistant (PA), an agent with planning and learning abilities in order to assist its user to manage his/her agenda.
Background: Machine Learning tools, such as the ILP tools Progol and Aleph, can be used to extract rules from a set of observations. These could be applied to model the user's preferences over time and anticipate and automate his/her choices in setting the agenda. <\p>
Objectives and Method: The project wills first develop a simple planner that will schedule events at available times. A GUI may be required to facilitate use and allow the user to enter preferences, such as order of events, the preference for scheduling events at a certain time, etc. Then, an ILP learner will be used to discover the regularities in the data (e.g., daily, weekly, monthly events) and attempt to predict the user's preferences. The evaluation will consist of comparing the planner's output to artificially generated data (entries and modifications in the simulated user's agenda), as well as a subjective evaluation involving a small set of volunteers. If the project is taken by at the M level (MMeng, MMath), and should the time permit, it will also experiment with a multi-agent system of PAs, in which events are proposed, scheduled and re-scheduled automatically by a set of agents.
Building an English Combinatorial Dictionary
Jared Sulem
Aims: The aim of the project is to use available text (or corpus) to discover patterns characteristic of the usage of each of the words in the corpus, which then would be used to assist a non-native speaker with the right choice of words.
Background: When studying a new language, a learner faces three separate challenges in learning (1) the lexicon, mapping concepts on to words, (2) the typical ways in which words are combined into phrases, and (3) the full syntax, which describes what constitutes an acceptable sentence in the language. Of the three tasks, arguably the most difficult to a non-native speaker is the second, as the first and last are limited by the size of the active vocabulary one uses (typically, a couple of thousand words) and the general character of the syntactic rules. On the other hand, the semantics (meaning) of a given word alone is not enough to define the correct syntax of the phrase in which the word is to appear or the best choice of words that would make the phrase they form sound correct and natural. For instance, compare two verbs with similar meaning: to look for <object> and to seek <object>. Also, despite the fact that they express the same meaning, only one of a set of synonyms is expected in some fixed expressions: one is said to draw (rather than pull) a card or a winning ticket. Finally, the same action may be described differently in different languages: in English, one has or takes a shower, while in another language (e.g., Czech), the corresponding phrase may be to give oneself a shower !
Method: A set of syntactic patterns will be defined by the student and used to extract the dictionary entries from the corpus. These then will be linked to the online thesaurus WordNet. A typical example of using the combinatorial dictionary will guide the user from his/her initial guess about the exact choice of words towards the correct phrase, e.g.: (User): knock in the door* -» (Computer) knock on the door ; (U) to seek for the enemy* -» (C) to seek the enemy ; (U) this is the way the biscuit falls apart -» (C) that's the way the cookie crumbles. As shown in the examples, the tool should look for a best match between the input provided and the phrases in the dictionary using the links of synonymy, hypernymy and hyponymy stored in WordNet. Evaluation will be based on a sample of user queries and answers provided by the system.
Spatial aspects of social dynamics
Matthew Hall.
Aim: Multi-agent simulations often focus on the interaction between the behaviour of individual agents, and the system as a whole. This project will study the dynamics of societies, subsets of the multi-agent system that the agent can join or leave at will in order to maximise its reward.
The aim of the project is to assess the role spatial layout plays in the survival of an altruistic community surrounded by selfish individuals. The approach will simulate an environment in which two types of individuals, A and B, are randomly seeking for food, competing for the same food resources. Food consumption will result in increased individual energy level. Falling below a certain energy level would mean death. An encounter of two individuals of the same species results in the creation of offspring if their energy levels are sufficient to pay the one-off price for reproduction. The initial energy level of the offspring is subtracted from that of the parents. The individuals of type A share their energy with all individuals of the same type (community). Individuals of type B never share.
Background: Interactions between agents can be modelled as 'codes of conduct', games (cf. Game Theory) in which each agent chooses from a range of actions and the joint action defines the individual payoff:
| Agent
A \ Agent B |
Action 1 |
Action 2 |
| Action 1 |
(5,5) |
(-3, 2) |
| Action 2 |
(2, -3) |
(0,0) |
Membership in a society can influence the agents' behaviour and the outcome of interactions through the "us vs them" distinction. That is, an agent will, in general, choose different actions towards members and non-members of a society to which s/he belongs. We will assume that each agent can choose between two actions, friendly (F) and hostile (H). In case all societies an agent belongs to recommend action F, it will be carried out, and the best reward prescribed by a shared code of conduct given out. So, an agent would benefit from joining new societies, as that would give him/her a more beneficial treatment from their members. On the other hand, a situation in which the 'code of conduct' (action/reward table) of two societies prescribes two contradicting actions (F vs H), the agent will have to choose and leave either, then play the game as if s/he wasn't a member of the society s/he left.
The size of membership influences the probability of encountering a fellow member, and therefore the overall benefit of being in it. It is expected that this will lead to (highly) non-linear population dynamics, which the project will study.
Objectives and Method: The objective is to design and compare strategies that maximise individual agents' payoff. The project wills first develop a suitable simulation platform, then design a case study of multi-agent interaction (incl. the range of possible societies and related payoffs), run simulations and compare proposed strategies.
Date: 27th January 2006, 12:15, CS119N Computer Science, Univ. of York
Making Automated Decisions on Relatedness
Thimal Jayasooriya, University of York
In our everyday interactions with language, we often need to make decisions on the degree of similarity between two or more disparate concepts. The most obvious example is synonyms - is a broadsheet synonymous with a newspaper ? Can those two terms be used interchangeably in speech or written text ? How about a word pair like coast and shore ? A natural language understanding module would need to make exactly such a determination. To make matters even more complicated, there are other degrees of similarity which explore concepts which aren't synonyms at all. Is the concept of a car related to that of a mechanic ? Is the concept of a doctor related to that of a hospital ?
Semantic distance is one means of determining such relationships without human intervention. In this seminar, I will be describing the major classes of semantic distance algorithms, their characteristics and their performance with a standard test data set. I'll also be explaining a novel hybrid technique which mitigates some of the disadvantages of currently published semantic distance discovery techniques.
Date: 13th January 2006, 13:30, CS119N Computer Science, Univ. of York
What User Modelling can do for Question Answering and Information Retrieval
Silvia Quarteroni, University of York
Most question answering (QA) and information retrieval (IR) systems are insensitive to different users' needs and preferences, and cannot account for multiple, complex or controversial answers.
I will propose the notion of adaptivity in QA and IR by introducing a hybrid QA-IR system based on a user model. The system filters and re-ranks the query results returned by a search engine according to their topics and reading difficulty, thus providing user-tailored answers.