Group Recommender Systems
I worked with Lara Quijano-Sánchez, Belén Díaz-Agudo and Juan A. Recio-García on systems that make recommendations to groups of people. In particluar, we looked at how Case-Based Reasoning can play a role in such systems. Our work shows how CBR can help the cold-start problem (where a user has rated too few items to receive useful recommendations) and also in the aggregation of user preferences
[Quijano-Sánchez et al. 2012a,
Quijano-Sánchez et al. 2012b,
Quijano-Sánchez et al. 2013,
Quijano-Sánchez & Bridge 2013].
Using Recommendation Technology to Enhance Waste Exchange Services
I won funding from the Irish
Environmental Protection Agency
for this STRIVE Programme Project.
The project employed Aidan Waugh.
Our partner was
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 worked 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.
I worked with Nic Wilson and
Walid Trablesi to use different formalisms for representing and reasoning with
the user's inferred preferences
[Trabelsi et al. 2010a,
Trabelsi et al. 2010b,
Trabelsi et al. 2011,
Trabelsi et al. 2013].
Work with Francesco Ricci and Henry Blanco Lores continued, 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].
Explaining Case Base Maintenance
I won funding from
Science Foundation Ireland
for this Research Frontiers Project.
The project employed Lisa Cummins.
Generous support came from Mehmet H. Göker of
PricewaterhouseCoopers, and we enjoyed some
Juan Antonio Recio García
of the Universidad Complutense de Madrid.
We investigated 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.
In particular, we developed a 'committee of experts' approach to case-base
maintenance, which we call the MACE approach
[Cummins and Bridge 2009],
looked at the complexity of datasets before and after case base maintenance
[Cummins and Bridge 2011a],
and evaluated a meta-CBR approach to choosing a maintenance algorithm
[Cummins and Bridge 2011b].
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
James Little and I won funding from
Commercialisation Fund for this Technology Development Project.
For some of the time, the project
has employed Ross Nicholson.
Oskar Manzano and
have also been involved.
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].
Diversity-Enhanced Conversational Collaborative Recommendations
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].
Ant Algorithms for Subset Selection Problems
Finbarr Tarrant and I experimented with
ant algorithms for solving constraint satisfaction problems
[Tarrant & Bridge 2004,
Tarrant & Bridge 2005].
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 & 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 2000b
Ferguson & 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].
Within the framework, we also investigated
the axiomatisation of similarity
[Osborne & Bridge 1997a,
and algebraic equivalences. (The latter might allow
be transformed to forms that are best suited to whatever
evaluation mechanism a particular CBR system provides,
including parallel evaluation strategies
[Osborne & Bridge 1996a,
Osborne & Bridge 1996b,
Osborne & Bridge 1997d,
Campbell et al. 1997,
Campbell et al. 1998].)
Inductive Generalisation in Case-Based Reasoning Systems
Tony Griffiths' prize-winning D.Phil. was successfully completed under my supervision.
Tony provides a careful analysis of case-based learning.
In particular, using worst-case (PAC), average-case and
empirical analyses, he shows the effect of inductive bias
on case-based learning accuracy. Bias is incorporated
through the similarity measure and/or the 'semantics'
ascribed to a case-based system
[Griffiths & Bridge 1995a,
Griffiths & Bridge 1995b,
Griffiths & Bridge 1995c,
Griffiths & Bridge 1996,
Griffiths & Bridge 1997a,
Griffiths & Bridge 1997b,
Griffiths & Bridge 1997c].
Tony was funded by an award from the UK Science and Engineering Research Council.
and I received funding from British Telecom
to investigate the applicability of knowledge-based
systems, especially those that use Case-Based Reasoning,
to British Telecom help desk functions
[Bridge & Dearden 1992a,
Dearden & Bridge 1993].
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
successfully completed his D.Phil. under my supervision.
Miles developed one of the first systems capable of
learning unification-based grammars. The inductive search
space was constrained by a set of linguistic
universals (and, in the implemented system, some
language-specific linguistic constraints)
[Osborne & Bridge 1993a,
Osborne & Bridge 1993b,
Osborne & Bridge 1994b,
Osborne & Bridge 1997e].
Miles was funded by an award from the UK Science and Engineering Research Council.
Logic and Databases: An Object-Oriented Approach
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.