2004 - Technical Reports

Number Report Title
2004/1 A MAXIMUM UNCERTAINTY LDA-BASED APPROACH FOR LIMITED SAMPLE SIZE PROBLEMS - WITH APPLICATION TO FACE RECOGNITION
Carlos E. Thomaz, Duncan F. Gillies, 19pp
2004/2 THE CIFF PROOF PROCEDURE: DEFINITION AND SOUNDNESS RESULTS
Ulle Endriss, Paolo Mancarella, Fariba Sadri, Giacomo Terreni, Francesca Toni, 17pp
2004/3 EXPRESSIVENESS AND COMPLEXITY OF GRAPH LOGIC
Anuj Dawar, Philippa Gardner, Giorgio Ghelli, 21pp
2004/4 MANIPULATING TREES WITH HIDDEN LABELS
Luca Cardelli, Philippa Gardner, Giorgio Ghelli, 42pp
2004/5 OSCP: OPTIMIZATION SERVICE CONNECTIVITY PROTOCOL
Obi C. Ezechukwu, Istvan Maros, 11pp
2004/6 ON MODEL CHECKING MULTIPLE HYBRID VIEWS
Altaf Hussain, Michael Huth, 15pp
2004/7 NOVEL INTELLIGENT WAVELET FILTERING OF EMBOLIC SIGNALS FROM TCD ULTRASOUND
Salman Marvasti, Duncan Gillies, 8pp
2004/8 (C+)++: AN ACTION LANGUAGE FOR REPRESENTING NORMS AND INSTITUTIONS
Marek Sergot, 88pp
2004/9 NATURAL ALGORITHMS FOR OPTIMISATION PROBLEMS
Dorian Gaertner, 143pp
2004/10 LEADER ELECTION IN RINGS OF AMBIENT PROCESSES
Iain Phillips, Maria Grazia Vigliotti, 40pp

A MAXIMUM UNCERTAINTY LDA-BASED APPROACH FOR LIMITED SAMPLE SIZE PROBLEMS - WITH APPLICATION TO FACE RECOGNITION

Carlos E. Thomaz, Duncan F. Gillies, 19pp
Report: 2004/1

Download PDF Download

A critical issue of applying Linear Discriminant Analysis (LDA) is both the singularity and instability of the within-class scatter matrix. In practice, particularly in image recognition applications such as face recognition, there are often a large number of pixels or pre-processed features available, but the total number of training patterns is limited and commonly less than the dimension of the feature space. In this paper, a new LDA-based method is proposed. It is based on a straighforward stabilisation approach for the within-class scatter matrix. In order to evaluate its effectiveness, experiments on face recognition using the well-known ORL and FERET face databases were carried out and compared with other LDA-based methods. The results indicate that our method improves the LDA classification performance when the within-class scatter matrix is not only singular but also poorly estimated, with or without a Principal Component Analysis intermediate step and using less linear discriminant features.


THE CIFF PROOF PROCEDURE: DEFINITION AND SOUNDNESS RESULTS

Ulle Endriss, Paolo Mancarella, Fariba Sadri, Giacomo Terreni, Francesca Toni, 17pp
Report: 2004/2

Download PDF Download

We introduce a new proof procedure for abductive logic programming and prove two soundness results. Our procedure extends that of Fung and Kowalski by integrating abductive reasoning with constraint solving and by relaxing the restrictions on allowed inputs for which the procedure can operate correctly. An implementation of our proof procedure is available and has been applied successfully in the context of multiagent systems.


EXPRESSIVENESS AND COMPLEXITY OF GRAPH LOGIC

Anuj Dawar, Philippa Gardner, Giorgio Ghelli, 21pp
Report: 2004/3

Download PDF Download

We investigate the complexity and expressive power of the spatial logic for querying graphs introduced by Cardelli, Gardner and Ghelli (ICALP 2002). We show that the model-checking complexity of versions of this logic with and without recursion is PSPACE-complete. In terms of expressive power, the version without recursion is a fragment of the monadic second-order logic of graphs and we show that it can express complete problems at every level of the polynomial hierarchy. We also show that it can define all regular languages, when interpretation is restricted to strings. The expressive power of the logic with recursion is much greater as it can express properties that are PSPACE-complete and therefore unlikely to be definable in second-order logic.


MANIPULATING TREES WITH HIDDEN LABELS

Luca Cardelli, Philippa Gardner, Giorgio Ghelli, 42pp
Report: 2004/4

Download PDF Download

We define an operational semantics and a type system for manipulating semistructured data that contains hidden information. The data model is simple labeled trees with a hiding operator. Data manipulation is based on pattern matching, with types that track the use of hidden labels.


OSCP: OPTIMIZATION SERVICE CONNECTIVITY PROTOCOL

Obi C. Ezechukwu, Istvan Maros, 11pp
Report: 2004/5

Download PDF Download

Optimization software e.g. solvers and modelling systems, expose software and vendor specific interfacing mechanisms to client applications e.g. decision support systems, thus introducing close coupling. The ‘Optimization Service Connectivity Protocol’ (OSCP) is an abstraction of the interfaces to optimization software, which is aimed primarily at simplifying the process of integrating optimization systems into software solutions by providing an abstracted, uniform and easy to use interface to such systems, regardless of system or vendor specific requirements. This paper presents a high-level overview of OSCP including descriptions of its main interfaces, and illustrates its use via examples.


ON MODEL CHECKING MULTIPLE HYBRID VIEWS

Altaf Hussain, Michael Huth, 15pp
Report: 2004/6

Download PDF Download

We study consistency, satisfiability, and validity problems for collectively model checking a set of views endowed with labelled transitions, hybrid constraints on states, and atomic propositions. A PTIME algorithm for deciding whether a set of views has a common refinement (consistency) is given. We prove that deciding whether a common refinement satisfies a formula of the hybrid mu-calculus (satisfiability), and its dual (validity), are EXPTIME-complete. We determine two generically generated "summary" views that constitute informative and consistent common refinements and abstractions of a set of views (respectively).


NOVEL INTELLIGENT WAVELET FILTERING OF EMBOLIC SIGNALS FROM TCD ULTRASOUND

Salman Marvasti, Duncan Gillies, 8pp
Report: 2004/7

Download PDF Download

Transcranial Doppler ultrasound can be used to detect emboli in blood flow for predicting stroke. Embolic signals have characteristic transient chirps suitable for wavelet analysis. We have implemented and evaluated the first on-line intelligent wavelet filter to amplify embolic signals building on our previous work in detection. Our intelligent wavelet amplifier uses the matching filter properties of the Daubechies 8th order wavelet to amplify embolic signals. Even the smallest embolic signal is enhanced without affecting the background blood flow signal. We show an increase of over 2db (on average) in embolic signal strength and an improvement in detection of 10-20%.


(C+)++: AN ACTION LANGUAGE FOR REPRESENTING NORMS AND INSTITUTIONS

Marek Sergot, 88pp
Report: 2004/8

Download PDF Download

The action language C+ of Giunchiglia, Lee, Lifschitz, McCain, and Turner is a formalism for specifying and reasoning about the effects of actions and the persistence (`inertia') of facts over time. An `action description' in C+ is a set of C+ laws which define a labelled transition system of a certain kind. (C+)++ is an extended form of C+ designed for representing norms of behaviour and institutional aspects of (human or computer) societies. There are two main extensions. The first is a means of expressing `counts as' relations between actions, also referred to as `conventional generation'. The second is a way of specifying the permitted (acceptable, legal) states of a transition system and its permitted (acceptable, legal) transitions.


NATURAL ALGORITHMS FOR OPTIMISATION PROBLEMS

Dorian Gaertner, 143pp
Report: 2004/9

Download PDF Download

Many computational techniques borrow ideas from nature in one way or another. Neural networks imitate the structure of our human brain, genetic algorithms simulate evolution and swarms of insects inspired algorithms for stochastic combinatorial optimisation. These techniques are characterised by inherent parallelism, adaptivity, positive feedback and some element of randomness.

This report details the investigations into certain features of one such technique: the Ant System meta-heuristic proposed by Dorigo. The algorithm is applied to several variations of the well-known Travelling Salesman Problem, including asymmetric and dynamic ones. Furthermore, different approaches to parallelise the algorithm are investigated.

Good parameters are needed to instantiate the generic algorithm effciently and research to find optimal parameter settings has been conducted in the course of this project. An ontology to classify instances of the TSP is introduced and a thorough analysis of the dependency between parameters and classes of problems is presented. During this analysis, optimal parameters have been found for a given problem instance that led to the discovery of a new shortest tour for this instance.

A novel algorithm, the Genetically Modified Ant System(GMAS), is then proposed that employs ideas from the field of genetic algorithms to eliminate the need to set parameters for a given problem explicitly. An implementation is described and the new system is evaluated with respect to the standard Ant System and also compared to other more specialised heuristics.


LEADER ELECTION IN RINGS OF AMBIENT PROCESSES

Iain Phillips, Maria Grazia Vigliotti, 40pp
Report: 2004/10

Download PDF Download

Palamidessi has shown that the pi-calculus with mixed choice is powerful enough to solve the leader election problem on a symmetric ring of processes. We show that this is also possible in the calculus of Mobile Ambients (MA), without using communication or restriction. Following Palamidessi's methods, we deduce that there is no encoding satisfying certain conditions from MA into CCS. We also show that the calculus of Boxed Ambients is more expressive than its communication-free fragment.