Derek Bridge

Research Projects

Overview

Group Recommender Systems

I am working 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 have been looking 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 Macroom-E.

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 Enterprise Ireland 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 product reviews [Healy & Bridge 2010, Bridge & Healy 2010].

Information Recommendation

I am working with Francesco Ricci 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 am working 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].

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].

Explaining Case Base Maintenance

I won funding from Science Foundation Ireland for this Research Frontiers Project. The project employs Lisa Cummins. Generous support has also come from Mehmet H. Göker of PricewaterhouseCoopers, and we have enjoyed some collaboration with Belén Díaz-Agudo and Juan Antonio Recio García of the Universidad Complutense de Madrid.

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

James Little and I won funding from Enterprise Ireland's Commercialisation Fund for this Technology Development Project. For some of the time, the project has employed Ross Nicholson. Nic Wilson, Oskar Manzano and Peter MacHale 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 encouraging [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], he, Pádraig Cunningham, 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 domain expert [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].

Later 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 problems' [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 Eugene Freuder, Brahim Hnich and James Little) 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 performance [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 Enterprise Ireland 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].

Order-Based Retrieval

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 Enterprise Ireland for this Strategic Research Project, with industrial support from Interactive Multimedia Systems (IMS). The project employed Alex Ferguson.

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

Alan Wood 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 CBR systems. 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 similarity. 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 metrics [Osborne & Bridge 1997a, Bridge 1998]. and algebraic equivalences. (The latter might allow metrics to 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.

Help-Desk Support

Andy Dearden, Michael Harrison 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

Miles Osborne 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 level.

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.