A waste exchange service connects people who produce waste with
people who can reuse or recycle the waste. We are applying
recommender systems ideas to Macroom-E's web-based waste
exchange service, with the goal or making more and better
matches. A major research challenge is that people are reluctant
to describe the waste they have or want in sufficient detail
to enable good matches to be made.
We proposed the ideas of smart search and smart suggestions as ways of
heping users to find items and helping users to author descriptions of
items respectively. Aidan wrote up this work for his Research Masters,
with the smart suggestions work published in
[Bridge & Waugh 2009,
Waugh & Bridge 2010].
Subsequently, Macroom-e won an
Innovation Voucher, which they spent with us to bring these
ideas into their WasteMatchers live service.
The smart suggestions idea is implemented in a family of systems, which
we call GhostWriter systems. For example, following on from Aidan's GhostWriter
system for waste exchange services, Paul Healy and I developed the
GhostWriter-2.0 system to enable
amazon.com users to write more useful
[Healy & Bridge 2010,
Bridge & Healy 2010].
I am working with
on advice-giving in conversational recommender systems.
We have shown how such a system can infer some of its user's
preferences by observing the user's queries, and then
give advice about next possible actions based on what it has
inferred. We are able to show that a user can find the
item s/he wants more quickly if advice is given, and we
are able to show that this advice is shorter if it is based
on what has been inferred about the user
[Bridge & Ricci 2007]. Both the Free University of Bozen-Bolzano
and the Center for Scientific and Technological Research
(ITC-irst) in Trento have supported me with travel funding.
Work with Francesco Ricci and Henry Blanco Lores continues with an investigation of the case where the system has only a finite set of possible user profiles and must infer whcih subset of these is consistent with the user's actions. This results in shorter dialogs, faster processing and hardly any reduction in advice quality
[Blanco et al. 2012a,
Blanoc et al. 2012b].
We are investigating algorithms for maintenance of case bases.
These algorithms propose the deletion of noisy or redundant cases,
with a view to increasing retrieval efficiency while doing as little
damage as possible or even increasing reasoning accuracy.
Our work tries to make these algorithms better suited to use in
real-world settings by: making them incremental; seeking more
than one source of support for candidate deletions to enhance
user confidence; and explaining the effects of candidate deletions.
In particular, we have developd a 'committee of experts' approach to case-base
maintenance, which we call the MACE approach
[Cummins and Bridge 2009].
Case Based Reasoning in Forest Management
Conor Nugent and I developed Case-Based Reasoning methods for predicting the product yield of the trees
in a managed forest
[Nugent et al 2009].
TalkingShop: Conversational Recommenders for Configurable Products
In the project, we developed a compact graphical data structure
into which case bases or product catalogs can be compiled. The data
structure is flexible enough to support a variety of forms of retrieval
(e.g. exact-matching and inexact-matching), and does so in a way that is
generally faster than conventional retrieval algorithms
[Nicholson et al. 2006].
Feature-Based and Feature-Free Textual CBR for Spam Filtering
Sarah Jane Delany
and I investigated textual Case-Based Reasoning (CBR) for
spam filtering. We compared a feature-based approach that Sarah Jane had
developed in her Ph.D. research with a feature-free approach, that used
text compression in its similarity measure. Accuracy results were very
[Delany & Bridge 2006a,
Delany & Bridge 2006b].
We went on to test the robustness of both approaches, in particular in
dealing with the fact that spam is a moving target, i..e we are faced with
what machine learning
researchers would call 'concept drift'. Again, results with the feature-free
approach are extremely encouraging: we can preserve accuracy over time,
with low-effort maintenance of the case base
[Delany & Bridge 2007].
John Paul Kelly and I investigated ways of building conversational
collaborative recommenders, in which user feedback over the course of
a multi-step interaction guides the recommender so that it makes
recommendations that satisfy the user's short-term, ephemeral interests.
We also showed how to enhance the diversity of recommendations made by
a collaborative recommender, which is useful in the conversational
scenario described above. Our major contribution was to show diversity
can be enhanced using only the knowledge already contained in the ratings matrix
[Bridge & Kelly 2005,
Bridge & Kelly 2006,
Kelly & Bridge 2006].
John Paul received some support from the Adaptive Information
Cluster, funded by Science Foundation Ireland.
Efficient Collaborative Recommendations using Formal Concept Analysis
Patrick du Boucher-Ryan and I applied Formal Concept Analysis to the
ratings matrix used by a collaborative recommender. We showed how the
concept lattice that this produces can be used as an index to rapidly find
candidate neighbours for making predictions and recommendations.
Although the concept lattice is large, we saved in excess of 90% of the
time taken by the conventional user-based nearest neighbours algorithm
[du Boucher-Ryan & Bridge 2005,
du Boucher-Ryan & Bridge 2006].
Pat wrote up this work for his Research Masters. He was supported by an award made by
the Boole Centre for Research in Informatics,
which was funded by the Higher Education Authority’s Programme for Research in Third Level Institutions Cycle 3.
Knowledge-Lite Explanation-Oriented Retrieval
The conventional wisdom in case-based classification is that the
system can explain its conclusion by showing the user the
case or cases that are closest to the new problem (i.e. the nearest
neighbours). Dónal Doyle challenged this in his Ph.D. research, and in
[Doyle et al 2004],
Yusof Rahman and I showed how a case-based
system could retrieve 'marginal' cases that better explain why the
new problem has been classified the way that it has.
Lisa Cummins and I later generalised this work and made it more knowledge lite,
i.e. so that it requires less effort on the part of the knowledge engineer and
[Bridge & Cummins 2005,
Cummins and Bridge 2006].
Dr. Christine Solnon
and I generalised the work: we used ant algorithms for
solving a whole class of problems that we refer to as 'subset selection
[Solnon & Bridge 2006].
This class includes constraint satisfaction problems but also
maximum clique problems and multi-dimensional knapsack problems.
Using CBR to Select Solution Strategies in Constraint Programming
Cormac Gebruers and I (with
Brahim Hnich and
experimented with case-based classification
techniques for two of the phases of constraint programming. The first
phase is how best to model a problem using constraints; the second is
choosing the best solution strategy (search algorithm, heuristics, etc.)
for finding solutions
[Little et al. 2002,
Gebruers et al. 2005].
Using Clustering to Build Scalable Collaborative Filtering Systems
Jerome Kelleher and I applied clustering techniques to the ratings matrices
used by collaborative recommenders. We then predicted the
active user's rating for a product that s/he has not yet rated
from the clusters. We found that using neighbourhood-based
methods on the clustered data gave disappointing
[Bridge & Kelleher 2002].
But, if we make less personalised predictions
from summary information about the clusters, we obtain
surprisingly good accuracy at tremendous speed
[Kelleher & Bridge 2003,
Kelleher & Bridge 2004].
Supporting Reuse in the Software Development Cycle
I won funding from
for this Strategic Research Project.
The project employed Markus Grabert.
We built a Case-Based Reasoning system for improving software
reuse. In particular, the case base contains what we called Java
'examplets', i.e. snippets that demonstrate Java usage of the kind
you might find in a how-to FAQ list. We defined two retrieval
mechanisms, one based on text retrieval, the other based on
spreading activation over a graph-based representation of the
examplet token stream. We showed that combining both types of
retrieval gave the best results
[Grabert & Bridge 2003c].
With Alex Ferguson,
I devised a query language that builds on the best
aspects of similarity-based retrieval, while offering
a number of new operators that give greater
expressiveness. We called the approach
Order-Based Retrieval (OBR). We showed that, not only is OBR expresssive,
but it gives
a natural way of obtaining a diverse set of retrieved items.
We applied the ideas to case-based recommender systems
[Bridge 2001,Bridge & Ferguson 2002a,
Bridge & Ferguson 2002b].
WWW Shopping using Refinable Similarity Measures
I won funding from
for this Strategic Research Project, with industrial support from
Interactive Multimedia Systems (IMS).
The project employed
We defined a new way of combining similarity measures
[Ferguson & Bridge 1999b]
and we investigated the range of ways in which users
can interact with case-retrieval systems
[Ferguson & Bridge 2000c].
This work relies on a notion
of indifference between degrees of similarity. We have
argued that, for on-line shopping, our framework,
deploying this notion of indifference between degrees
of similarity, avoids a level of spurious precision
which plagues systems that are based on conventional
numeric-valued similarity measures
[Ferguson & Bridge 2000a].
We have also looked at more closely
reconciling our ways of combining similarity metrics
with more conventional
numeric weighted averages
[Ferguson & Bridge 2000bFerguson & Bridge 2001].
In an interesting spin-off of this work, we have applied
the idea of using a pair of weight vectors to define
similarity measures for case-based classification systems
that can report their classification confidence
[Bridge & Ferguson 2001].
Concurrent Architectures for Heterogeneous Knowledge Manipulation Systems
and I won funding under the U.K. Department of Trade and Industry/Engineering and
Physical Sciences Research Council's
Architectures for Integrated Knowledge-Manipulation Systems (AIKMS)
programme. The industrial partner was
Transtech Parallel Systems.
The project employed Hugh Osborne,
Duncan Campbell and Andy Johnson.
The most important outcome from this project was a
generalised framework for measuring similarity in
In our new framework, similarity is measured by functions
whose result types are
partial orders. This both subsumes and extends many existing
numeric-valued and non-numeric-valued ways of measuring
We use the phrase 'similarity metric' to refer to our
generalised similarity measures.
Within our new framework, we defined operators for
combining similarity metrics. These
operators make use of ways of combining partial orders.
Strikingly, this means that in our framework different
similarity metrics (e.g. set-valued and numeric-valued) can
be combined, without inter-conversion
[Osborne & Bridge 1997a,
Osborne & Bridge 1997b,
Osborne & Bridge 1997c].
Assessment of Knowledge-Based Systems Applications in Social Policy
Funded by the University of York, with support from the UK Department
of Social Security, Michael Hirst and I
applied Case-Based Reasoning (CBR) techniques to Department of Social Security
Disability Living Allowance data. Early results showed CBR
better predicting mobility awards than care awards.
Our report [Hirst & Bridge 1996]
offers possible explanations for this.
Formal Justification in Requirements Engineering
Simon Smith successfully completed a D.Phil., partly under
my supervision, in which he
developed a way of structuring formal specifications to
allow incremental re-proof of previously established
properties following changes to the specification.
Learning Unification-Based Natural Language Grammars
Chris Higgins successfully completed a D.Phil., partly under
my supervision, in which he
formalised object-oriented databases. He used a logic
programming formalisation: objects are theories, and
inter-object communication operates at a metalogical
A Process-Oriented Approach to Configuration Management for Communications Software
Shem Ochuodho successfully completed a D.Phil., partly
under my supervision, in which he
developed both a new data model and a new process model for
supporting configurations management, with particular
applications to telecoms software.
Computing Presuppositions in an Incremental Natural Language Processing System
My Ph.D. was completed under the supervision of the late Karen
Spärck Jones, Computer Laboratory, University of Cambridge.
The Ph.D. gives a partial solution to the presupposition projection
problem. The solution distinguishes two types of
presuppositions failure: where a presupposition is not
satisfied by the discourse model, and where a presupposition
is false. An incremental natural language processing system
was shown to be especially well-suited to computing
presuppositions of compound sentences.