The use of formal models in the design of interactive case m

The use of Formal Models in the Design of Interactive

Case Memory Systems

Andrew Mark Dearden

Submitted for the degree of Doctor of Philosophy

The University of York

The Human Computer Interaction Group,

The Department of Computer Science.

May1995

Abstract

The thesis:generic formal modelling frameworks can be used to encapsulate knowl-edge about human computer interaction with a particular class of system,namely interactive case memories(ICMs).A generic modelling framework can be used to ensure that ICMs developed exhibit desirable interaction properties,and can be re-used for the development of multiple systems.

Some formal modelling frameworks that have been advocated to support the development of interactive systems have aimed to model a very wide class of sys-tems at a highly abstract level.These frameworks are limited in their ability to express important properties that apply to particular systems,and may be open to multiple interpretations when applied to inpidual systems.Other frameworks have emphasised the speci?cation of inpidual systems.Such single speci?cations provide limited re-usability.

In this thesis I develop a generic framework to support the development of ICMs. To develop the framework I propose an abstract framework to describe the way a case memory system(CMS)stores and retrieves cases.This framework views the CMS as a function that takes as input a problem statement and store of cases and returns an ordering over the stored cases.From this viewpoint an ICM can be seen as a system in which the user manipulates the value problem statement and monitors changes to the associated case ordering.By expressing important interaction properties in the context of this generic framework I provide a method of encapsulating knowledge about human-computer interaction with ICMs that can be re-used in the development of multiple systems.Because the framework refers explicitly to the main components of an ICM it is not open to multiple competing interpretations.

i

Contents

1Engineering Interfaces to Interactive Case Memories2

1.1Introduction (2)

1.1.1Interactive case memories (2)

1.1.2Software engineering for human computer interaction (3)

1.1.3Models for designing ICMs (5)

1.2Structure of the Thesis (5)

2Understanding Interactive Case Memories7

2.1Introduction (7)

2.2ICMs in the Context of CBR (8)

2.2.1Case based reasoning and reasoning from cases (8)

2.2.2CBR and case memory systems (11)

2.2.3Interactive case memories (13)

2.3Similarity and Case Retrieval in CMSs and ICMs (13)

2.3.1Similarity and usefulness (14)

2.3.2Case representation and indexing schemes (15)

2.3.3Partial matching of indexing features (16)

2.3.4Combining multiple factors in similarity (19)

2.3.5Similarity and contrast (21)

2.3.6The e?ect of context on similarity (22)

2.4Interaction Issues for Interactive KBS (25)

2.4.1The r?o le of an interactive KBS (25)

2.4.2Problem solving strategy in interactive KBS (27)

2.4.3Initiative in interactive KBS (27)

2.5Analysing Inpidual ICMs (28)

2.5.1CBR Express (28)

2.5.2ReMind (31)

2.5.3PATDEX (33)

2.5.4KATE and CASSYS (34)

2.5.5Observations on current ICM designs (36)

2.6Summary (36)

3Abstract Models for HCI37

3.1Introduction (37)

3.1.1Structure of this chapter (38)

3.2The R?o le of Models in HCI Design (38)

3.2.1Frameworks,models and artifacts (39)

ii

CONTENTS iii

3.2.2Criteria for frameworks to support HCI design (40)

3.3Using Properties in Design (41)

3.3.1The PiE framework (41)

3.3.2Other abstract mathematical models (43)

3.3.3Abstraction and re-usability of general mathematical frame-

works (44)

3.3.4Expressiveness of general mathematical frameworks (44)

3.3.5Ensuring desirable properties (45)

3.3.6Summary (46)

3.4Specifying Interactive Systems (46)

3.4.1Interactor notation (47)

3.4.2Other speci?cation frameworks (50)

3.4.3Abstraction and re-usability of speci?cation models (51)

3.4.4Expressiveness of speci?cation models (53)

3.4.5Ensuring desirable interaction properties using speci?cation

models (53)

3.4.6Summary (53)

3.5A Framework for the Class of ICMs (54)

4A Modelling Framework for Case Memory Systems56

4.1Introduction (56)

4.1.1Structure of this chapter (56)

4.2Previous Models of CMSs and ICMs (57)

4.2.1Existing models of CMSs (57)

4.2.2Models of ICMs (59)

4.2.3The need for a new framework (59)

4.3Background to the Simple Framework (59)

4.3.1Choice of notation (59)

4.3.2Assumptions of the framework (60)

4.4The Basic Framework (63)

4.5Initial Comments on the Model (65)

4.5.1Abstraction and expressiveness (65)

4.5.2Deep versus surface features (66)

4.5.3Combining multiple measures of similarity (66)

4.5.4Similarity and dissimilarity (67)

4.5.5Types of case ordering (68)

4.5.6The e?ect of context on similarity assessment (68)

4.6Demonstrating the Expressiveness of the Model (68)

4.6.1Responding to a reasoner’s goals (68)

4.6.2Responding to other contextual information (69)

4.6.3Responding to historical context (71)

4.6.4History sensitivity (71)

4.6.5Examining inpidual case reports (72)

4.6.6Responding to the rest of the CB (72)

4.6.7Using the domain of the CB (73)

4.6.8Examining the CB mapping (73)

4.6.9Assessing expressiveness (74)

4.7Range and Operationality of the Framework (74)

CONTENTS iv

4.7.1Modelling DataLex (75)

4.7.2Modelling HYPO (78)

4.7.3Modelling CBR Express (80)

4.7.4Modelling CYRUS (82)

4.7.5Summary (88)

4.8Relating Properties to Each Other (90)

4.8.1Relating types of historical context (90)

4.8.2Directability implies attribute interdependence (90)

4.8.3Attribute interdependence without directability (91)

4.8.4Attribute interdependence from report examination (93)

4.8.5Summary (95)

4.9Discussion (95)

5Developing a Framework to Model ICMs97

5.1Introduction (97)

5.1.1Structure of this chapter (98)

5.2Properties of ICMs (99)

5.2.1Reachability (99)

5.2.2Recoverability (100)

5.2.3Initiative (100)

5.3A Framework based on Sufrin and He(1990) (100)

5.3.1Sufrin and He’s framework (100)

5.3.2A framework for ICMs (101)

5.3.3Relating state and behaviour (103)

5.3.4Assessing the framework (107)

5.3.5Summary (108)

5.4A Framework in Object Z (108)

5.4.1Expressing reachability in Object Z (111)

5.4.2Object-Oriented Z (111)

5.4.3Summary (112)

5.5The Agent Language (112)

5.5.1Constraining the behaviour of an ICM Agent (114)

5.5.2Summary (115)

5.6Interactor Notation (115)

5.6.1Constraining behaviour in interactor notation (117)

5.6.2Summary (117)

5.7Discussion (117)

6Flexible Interaction with an ICM119

6.1Introduction (119)

6.1.1Structure of this chapter (119)

6.2The Framework for Modelling ICMs (120)

6.3The Flexibility of an ICM (121)

6.3.1The Ready set of an ICM (121)

6.3.2Comparing the?exibility of ICMs (124)

6.3.3Flexibility,retraction and the framing problem (125)

6.3.4Relations on the set PS (125)

6.3.5Tracking the evolution of a problem (126)

CONTENTS v

6.3.6Summary (126)

6.4Flexibility and Hypothesis Formation (127)

6.4.1An ICM with multiple hypotheses (127)

6.4.2What if Y is not actually true? (130)

6.4.3What-if Y,an observation,is true? (132)

6.4.4What would happen if I did X (133)

6.4.5Summary (133)

6.5An Example ICM Design (134)

6.5.1A navigational interface to an ICM (134)

6.5.2Interaction problems in the helpdesk ICM (138)

6.6An Analysis of the Helpdesk ICM (141)

6.6.1Modelling the set PS (142)

6.6.2Displaying the PS (142)

6.6.3Flexibility of the helpdesk ICM (143)

6.6.4Summary (144)

6.7Summary (144)

7Equal Opportunity for ICMs145

7.1Introduction (145)

7.1.1Structure of this chapter (145)

7.2Equal Opportunity and ICMs (146)

7.3The Focus of Problem Solving (147)

7.3.1De?ning the focus (147)

7.3.2Operations on the focus (150)

7.3.3Analysing the add to focus operation (151)

7.4Supporting manipulation of the focus (152)

7.4.1History sensitivity and the focus (152)

7.4.2Similarity functions that cannot support add to focus (153)

7.4.3Summary (154)

7.5Monotonic ICMs (154)

7.5.1Using monotonicity (155)

7.6A Prototype ICM that Extends Equal Opportunity (156)

7.6.1Case Representation in the Cars ICM (156)

7.6.2A Simple Search with the Cars ICM (158)

7.6.3Manipulating the PS (161)

7.6.4Pursuing a particular case (161)

7.6.5Widening the search (161)

7.6.6Changing the focus (162)

7.6.7Summary (162)

7.7Modelling the Cars ICM (163)

7.7.1Input and representation for the cars ICM (163)

7.7.2Matching constraints in the cars ICM (165)

7.7.3Ordering subsets of features (166)

7.7.4Similarity for the cars ICM (168)

7.8Analysing the cars ICM (169)

7.8.1Monotonicity of the cars ICM (169)

7.8.2Completeness of the cars ICM (170)

7.8.3Implementing change focus (170)

CONTENTS vi

7.8.4Designing an add to focus operation (172)

7.8.5Reachability in the cars ICM (173)

7.9Summary (173)

8Summary and Conclusions175

8.1Summary (175)

8.2Contributions of this thesis (175)

8.2.1Contribution to the design of ICMs (176)

8.2.2Contribution to abstract modelling for HCI (176)

8.2.3Limitations of this thesis (176)

8.2.4Limitations of the modelling framework (177)

8.3Discussion (177)

8.3.1The r?o le of formal models in engineering ICMs (177)

8.3.2Formal frameworks as research tools (178)

8.4Future work (178)

8.4.1Future work on interfaces to ICMs (178)

8.4.2Future work on modelling frameworks for HCI (179)

A A Z Glossary180

B A library of Generic Relations186

C Partial Orders,Pre-orders and Lattices188

C.1Pre-Orders (188)

C.2Partial Orders (189)

C.3Lattices (190)

D Properties of CMS192

E Formal Description of the Helpdesk ICM197

F Monotonicity of the Cars ICM202

F.1Speci?cation of the Cars ICM (202)

F.1.1De?nition of maxsets (202)

F.1.2De?nition of?lex (202)

F.1.3De?nition of order (203)

F.2Proof of Monotonicity (204)

List of Figures

2.1A Flow chart for CBR based on Reisbeck&Schank(1989)[p32] (11)

2.2A Flow chart for a CMS (12)

2.3De?ning a taxonomy of values (17)

2.4An ordinal set of values (17)

2.5Ordering cases with respect to two di?erent factors (19)

2.6Combining di?erent orders by priority (20)

2.7Combining di?erent orders with equal priority (21)

2.8Similarity may depend on the context provided by other cases (24)

2.9Possible roles for interactive KBS (26)

2.10Similarity on a single numeric attribute in CBR Express (30)

3.1The PiE framework (41)

3.2The RED-PiE framework (42)

3.3Di?erent Models of Interactive Systems (55)

4.1A case lattice output by HYPO (79)

4.2A portion of Cyrus’s Case Memory (83)

4.3The Search Procedure for Cyrus (89)

6.1The Ready set is the set of PSs reachable by a single transition (122)

6.2A sequence of PSs and the associated sequence of case orderings (128)

6.3A part of the lattice of descriptions (134)

6.4The interface to the helpdesk ICM (136)

6.5Exploring a Hypothesis (137)

6.6Matching a query(1) (138)

6.7Matching a query(2) (139)

6.8Matching a hypothesis(1) (140)

6.9Matching a hypothesis(2) (141)

7.1Possible sets that satisfy the de?nition of focus (149)

7.2Enquire(Cb1,p) (153)

7.3Enquire(Cb2,p) (153)

7.4An example case from the cars ICM (157)

7.5Searching in the cars ICM:1 (159)

7.6Searching in the cars ICM:2 (159)

7.7Searching in the cars ICM:3 (160)

7.8Altering a Constraint (161)

7.9Focusing on a single case (162)

7.10After Re-anchoring (163)

vii

LIST OF FIGURES viii

C.1An example of a pre-order (188)

C.2An example of a partial order (189)

Acknowledgements

There are a few inpiduals without whose in?uence this thesis might have been about something very di?erent.Particularly I should like to thank Elpida Keravnou at UCL who?red my interest in interactive knowledge-based and expert systems; Rob Davis of BTplc who provided the impetus to study case-based reasoning;and Professor Michael Harrison,my supervisor,who?rst suggested modelling the inter-faces to case-based systems using formal software engineering notations.Both Rob and Michael have been constant sources of encouragement throughout the last3 years.

There are many inpiduals without whose in?uence this thesis might have been much impoverished.I should like to thank all my colleagues in the HCI group at York,especially Alan Dix,Chris Bramwell,Bob Fields and David Duke for so many conversations about the nature of formal models for HCI.I should also like to thank Derek Bridge and Tony Gri?ths of the intelligent systems group at York for the bene?ts I have derived from their knowledge.

I would have been much impoverished without the?nancial support of BTplc and the SERC/EPSRC through a CASE studentship.

There are two inpiduals without whose in?uence this thesis might have looked very di?erent.I must thank Greg Abowd and David Duke for acting as my local L a T E X gurus at di?erent times.

There are a some inpiduals without whom it would not have been as much fun:Robert,Steve,Philippe and Jason,as well as many others.Also thanks to all the Machiavelli players for keeping my mind o?my work.

There is one inpidual without whom this thesis might never have existed.I should like to thank Caroline,my wife,for persuading me to start studying com-puter science,for suggesting that I might enjoy research,and for supporting and encouraging me to?nish.

ix

Dedication

To Alice

x

Declaration

I declare that the work presented in this thesis is my own.

Chapter4is based on a paper written jointly with Michael Harrison which has been submitted for review to the Journal of Intelligent Information Systems. Chapter5is based on a paper co-authored with Michael Harrison and presented at the workshop on Design Speci?cation and Veri?cation of Interactive Systems (Dearden&Harrison,in press).Parts of chapter6are based on a paper,by myself, that is to be included in a collection edited by C.W.Johnson and M.D.Harrison on the subject of the use of formal methods in interactive systems.In all these cases I have exploited only those parts of the work that are directly attributable to me.

xi

A Note on Style

It is accepted practice in the empirical sciences to report the results of experimen-tation in the third person passive voice,i.e.an experiment was conducted.This form is chosen because of the implication that if another experimenter were to fol-low the same procedure then the same results,or results that supported the same conclusions,would be obtained.In practice the experimenter writes him-or herself out of the experimental report.

This form is also used for many theses in computer science and could have been used for this thesis,i.e.a model shall be presented.However,writing the modeller out of a thesis that is primarily concerned with the use of models is not,in my opinion,as simple as writing the experimenter out of a report of an experiment.

In this thesis I shall present a number of mathematical models.It seems unlikely that another computer scientist working on the same problem as I,would create the same models.The question is then:would they obtain models that supported the same conclusions?This question is hard to answer.An alternative question is,if our hypothetical computer scientist were given the models that I have produced, would they reach the same conclusions regarding these models?

My claim is that the models I present support the formal expression of informal concepts that may be important in the design of interactive case memories.I shall not be presenting empirical evidence to support this claim.Indeed it seems that the only way that a judgement can be formed as to whether a formal expression corresponds to an informal concept,is by discovering whether the users of the in-formal concept agree that the representation conforms with their understanding of the term.

An experiment might be conducted in which a group of people who regularly used the concepts were asked to judge the quality of the formal expressions that I present. Who might the subjects of this experiment be?They must be familiar with the use of formal modelling frameworks in the design of interactive systems,they should be familiar with issues in interaction with interactive knowledge based systems,and they should understand the ideas that underly interactive case memories.In short the subjects must be you,the reader,a jury of my academic peers.

1

Chapter1

Engineering Interfaces to Interactive Case Memories

1.1Introduction

This thesis is about software engineering for human-computer interaction.The question that I shall be addressing is how human factors knowledge can be integrated into the design of one particular class of interactive systems.The class of systems that I shall be concerned with may be called Interactive Case Memories(ICMs). My interest in these systems arises from earlier work that I conducted investigating the suitability of various knowledge based systems to support the operations of a computer support help-desk.This work is reported in Bridge and Dearden(1992) and Dearden and Bridge(1993).I introduce ICMs below.

My hypothesis is that human factors knowledge can be integrated into the design of ICMs by using an abstract mathematical modelling framework that supports the expression of important interaction properties.

In this chapter I introduce the main ideas that provide the context for my thesis, namely ICMs,software engineering for human computer interaction(HCI)and the r?o le of models in software engineering for HCI.

1.1.1Interactive case memories

The development of ICMs can be traced back to research in case-based reasoning. Case-based reasoning(CBR)is the process of solving new problems by reference to previous examples(Kolodner,1993).CBR is generally characterised as involving the following steps:

1.analyse the current problem to identify important indexing features;

2.search a store of previous cases to?nd cases which are similar in some way to

the current problem;

3.modify the retrieved solution(or solutions)to solve the new problem.

An essential element of any CBR system is a mechanism for storing and retrieving previous cases.Such a mechanism may be called a Case Memory System(CMS).A CMS does not modify retrieved cases,i.e.it only performs step1and2above.

2

3 Many CMSs assume that all the information about the current problem is avail-able before step1above is conducted.In some applications of CBR this may not be true,i.e.it may be necessary to collect the information about the current problem incrementally.This problem may be solved by using an Interactive Case Memory (ICM).An ICM is a system which interacts with a human user to gather information about a problem,interpret that information and search a store of previous cases to ?nd cases that may be useful in solving the new problem.ICMs can be regarded as a sub-class of Interactive Knowledge Based Systems(KBS).

Clearly,the e?ciency of problem-solving that is supported by an ICM working with a human user will be dependent,not only on the quality of the knowledge represented within the ICM,but also on qualities of the interaction between the human user and the ICM.It is,therefore,important that the designers of new ICMs should be able to apply knowledge made available by research in HCI to ensure that their proposed designs promote desirable interaction qualities.Unfortunately, to date there has been very little research on the human interaction with ICMs (see chapter2).For this reason the main source of HCI knowledge that I shall be applying to ICMs has been derived from studies of the more general class of interactive KBS.

My aim in this thesis is to examine how information about HCI with interactive KBS could be provided in a form that can support the designers of ICMs in analysing proposed designs and in generating alternative designs.I claim that such support can be provided by using a generic formal model of the class of ICMs that is capable of expressing interaction properties that may be desirable.

1.1.2Software engineering for human computer interaction

The general problem of software engineering is the discovery of methods for the design and development of software which can be used to ensure that the software artifacts produced exhibit selected qualities,and that the cost1of producing those artifacts is controlled.

HCI is concerned with the way in which computers can be used to support humans engaged in particular activities.Di?erent designs of interactive software systems may make the task of the human user more or less complex.If the user’s task is made more complex,this may increase the number of errors that the human makes and may reduce the e?ciency with which the human and computer can complete the activity.For example,consider two possible designs for a word processor.In the?rst design,the word processor displays a document to the user using the type faces that will eventually be used in the printed document.In the second design, all the text is presented in one type face.The?rst design reduces the complexity of the user’s task by removing the need for the user to visualise the appearance of the ?nished document.The second design may result in the user printing the document when it is in a state which is not what the user intended.The user may then need to edit the document further to achieve the intended result.Thus the second design may be less e?cient in supporting the production of the document.

1In this thesis I shall use the term cost to refer to the time,e?ort,and materials required to perform some action.Of course such costs translate into?nancial costs for an organisation but I shall not be discussing precise cash costs.

4 The general problem of software engineering for HCI is to develop appropriate methods for the design and development of interactive software systems.The use of appropriate methods should ensure that the software produced exhibits qualities which will enable a human user of the system to perform their activities e?ciently, and that the cost of developing the software can be controlled.

One method that is generally advocated for the development of interactive sys-tems is the use of rapid-prototyping and evaluation(Dix et al.,1993).This approach can be related to the spiral model of software development as described by Boehm (1988).The advocates of this approach suggest that when developing a new system a prototype should be developed as soon as possible.The prototype is then used to elicit HCI knowledge either by means of discussions with the users and clients, or by means of evaluation experiments with users.This approach su?ers from two major disadvantages for the development of interactive KBS.

1.The behaviour of an interactive KBS is highly dependent on the knowledge

modelled within the KBS.Early prototypes will not include all of the knowl-edge that will be included in the completed system.Consequently information gained from the evaluation of early prototypes may not be applicable to the completed system.

2.Early prototypes implicitly encapsulate design decisions.Some of these deci-

sions may be wrong.A phenomenon of‘design inertia’may mean that these decisions are never removed from the design(Dix et al.,1993).Also,in the evaluation process,users may concentrate only on the surface features of the design,i.e.visual appearance and methods of articulating commands,rather than on the deeper issues of organisation and functioning of the interface(Ret-tig,1994).Again this may mean that these deeper design decisions are never corrected.

Thus the prototyping approach alone does not guarantee that the software produced exhibits the interaction qualities that are required.

To compensate for the limitations of the prototyping approach to software en-gineering for HCI,a number of researchers in recent years have advocated the use of abstract mathematical models early in the design process.A range of modelling approaches are reported in Paterno’(in press),Harrison and Thimbleby(1990).The models that have been developed may be used to:

?analyse a detailed design to verify whether general principles which support e?cient human-computer interaction have been adhered to(Dix,1991)[ch1];

?allow the design of the human-computer interface to be integrated with the design of other components of the computer system where formal methods may be used(Duke and Harrison,1993);

?allow HCI concerns to be expressed early in the design process before a work-ing system has been constructed for user testing(Harrison and Thimbleby, 1990)[p2];

The proponents of the use of mathematical models hope to make early design decisions explicit,and therefore open to modi?cation.This hope is based on the ob-servation that,in general,modifying a design is easier than modifying an executable computer program.The formality of the models is intended to ensure that:

5?the consequences of the design decisions can be explored without constructing prototypes;

?that software developed from the models can be guaranteed to exhibit certain qualities exhibited by the models.

Thus the use of such formal models should enable software to be produced that ex-hibits desirable qualities for interaction,and that the cost of producing that software can be controlled2.

1.1.3Models for designing ICMs

The speci?c question that I address in this thesis is:

‘how can existing knowledge about the way that humans interact with

KBS be applied in the design of new ICMs?’.

This question includes two important assumptions:

??rstly,the knowledge to be applied is‘existing knowledge’,i.e.it does not need to be derived from prototypes but is available before any prototype ICMs are constructed;

?secondly,the knowledge is to be applied generally to the design of ICMs(plu-ral)rather than to one speci?c system.

My hypothesis is that this can be achieved through the use of a generic formal model of the class of ICMs.An appropriate model should enable the development of ICMs that exhibit selected interaction qualities that may improve the e?ciency with which a human user of the system can perform their tasks.

The model I present is a generic model that characterises a space of possible designs for ICMs.The model can be used to discuss some design decisions that must be made in the early development of an ICM.The generic nature of the model ensures that it can be re-used in the design of multiple ICMs.A model which can be re-used helps to control the costs of engineering ICMs by spreading the cost of developing the model over the set of ICMs developed.

1.2Structure of the Thesis

In chapter2,I examine case memory systems,ICMs and the concepts of similarity used in CBR and other machine learning methods.From this discussion,I identify a number of properties that a modelling framework to support the design of ICMs should be capable of expressing.

In chapter3,I examine existing abstract mathematical models and modelling frameworks that have been proposed to support the design of interactive systems, and that might be used to support the design of ICMs.I consider a set of criteria by 2It should be noted that the advocates of formal approaches do not necessarily advocate formal modelling as a replacement for prototyping.For a discussion of the relationship between formal models and prototypes see Roast(1993)[ch2]and Dix et al.[chs4,5and9]

6 which such models can be compared.I shall demonstrate that existing models are either:too speci?c to a particular system to support wide re-use;not operational in the sense that they cannot be directly applied by those who are not associated with the construction of the model;or they are too abstract to support the expression of some properties that may be relevant to the usability of ICMs.

In chapter4,I develop a generic modelling framework for case memory systems. The framework concentrates on the design of similarity functions that determine which cases are retrieved in response to a given input.In order to demonstrate that the framework is a suitable starting point for a framework to model ICMs,I explore its expressiveness,operationality and re-usability.The framework does not support reasoning about interaction but is used as a basis for the development of later models.

In chapter5,I examine some properties that a suitable framework for ICMs should be capable of expressing.I then consider how various notations based on Z,which might also support the structuring of a speci?cation as a collection of interconnected units,could be used to model ICMs.I demonstrate that none of these notations are suitable for the expression of some important properties.Consequently I develop a framework based on the work of Sufrin and He(1990).Unfortunately this framework does not support the speci?cation of an ICM as a collection of interconnected units.

In chapter6,I develop the framework examined in chapter5to examine the ?exibility of interaction with an ICM,and enabling an ICM to support a user in exploring their own hypotheses about the current problem.I discuss the design of a prototype ICM which attempts to support?exible hypothesis formation.I show how the framework that I have developed can be used to identify problems with the prototype,and to generate alternative solutions.

In chapter7,I examine a notion of equal opportunity in an ICM by allowing a user to express hypotheses by manipulating the set of cases retrieved from an ICM.I show how the models developed can be used to identify a restricted class of similarity functions which can support this type of interaction.I show how this observation can be used to generate a design for a second prototype ICM which supports a user in manipulating the retrieved cases.

Contribution and further work

In chapter8,I summarise the work that has been presented and indicate further work that needs to be conducted.The contributions of this thesis are:

?the extension of existing work on abstract mathematical models of interactive systems by showing how such models can be used to describe properties that are relevant to a class of interactive KBS,namely ICMs;

?to demonstrate how a generic model of a class of systems can be used to express important properties of those systems without sacri?cing either operationality or re-usability.

Chapter2

Understanding Interactive Case Memories

2.1Introduction

To understand ICMs it is necessary to view them from(at least)two perspectives. The?rst perspective views ICMs within the context of Case-based Reasoning(CBR) and Case Memory Systems(CMS).The second perspective views ICMs as interactive KBS.

Recall that the main steps in CBR were given in chapter1as:

1.analyse the current problem to identify important indexing features;

2.search a store of previous cases to?nd cases which are similar in some way to

the current problem;

3.modify the retrieved solution(or solutions)to solve the new problem.

From the CBR perspective,the primary questions to ask about an ICM are the way that cases are represented and stored,and how similarity is to be judged.A model that aims to support the design of ICMs should allow di?erent approaches to similarity to be compared and contrasted.From the interactive KBS perspective, the main question is how information about the current problem is to be collected and entered,and how the search process is to be guided or controlled by the user.

A model to support the design of ICMs should allow di?erent approaches to this interaction to be compared and contrasted.

In this chapter,I shall review existing work on CBR,the design of CMS,inter-active KBS and ICMs.I shall use the review to explore:

1.the relationship between case based reasoning,case memory systems and other

forms of reasoning that may make use of previous cases in order to clarify the precise scope of the framework developed in this thesis;

2.some of the issues regarding similarity that a suitable model of ICMs should

be capable of expressing;

3.some of the issues in the design of interactive KBS that may be relevant

considerations in a model for ICMs.

7

CHAPTER2.UNDERSTANDING ICMs8 In section2,I place ICMs in the context of case based reasoning and other methods of using cases to solve problems.In section3,I explore some of the issues regarding the assessment of similarity that have been signi?cant topics of research within the CBR community in recent years.In section4,I consider some of the interaction issues that have been identi?ed as signi?cant for interactive KBS in general and that may be important in the design of ICMs and I discuss the design of interfaces to existing ICMs.

2.2ICMs in the Context of CBR

2.2.1Case based reasoning and reasoning from cases

Example based reasoning(Dearden and Bridge,1993)is the process of solving prob-lems by making use of knowledge gained from examples of previous problem solving episodes.There are at least two ways in which examples might be used to guide problem solving.The?rst method may be called‘Domain Model Learning’.The second is CBR.

The domain model learning approach seeks to abstract general knowledge from a set of examples and then apply the general knowledge to solve new problems.The general knowledge generated may be expressed by if-then rules,by decision trees,by detailed descriptions of a particular concept,or by many other types of knowledge representation.The essential di?erence between this approach and CBR is that once the general knowledge has been obtained,the inpidual examples that were used to generate it can be discarded.

This approach to the re-use of examples can be seen in many machine learning systems.Some examples are given below.

?Version Spaces Version space learning algorithms(Mitchell,1982)take as input a set of positive and negative examples of a class and learn a de?nition of the class by conducting a bounded search in a lattice of possible conjunctive descriptions for the class.Version space learning attempts to learn by record-ing at each stage the most general possible descriptions that could apply to a class without including any counter examples,and the most speci?c descrip-tions of the class that include all the positive examples.As more examples are presented,the most speci?c and most general descriptions should converge, the most speci?c descriptions becoming more general whilst the most general descriptions become more speci?c.The output of the algorithm is an explicit conjunctive description of the class that has been learned.

?Decision Tree Learning ID3(Quinlan,1983)and related systems,see Quin-lan(1988),use a set of examples to generate a decision tree that indicates an optimal strategy for gaining information in order to conduct classi?cation.At each node in the tree,ID3computes the average amount of information that could be gained by answering any of the possible questions that could be asked.

The question that is associated with the highest information gain is used to extend the tree at that node.The output of the algorithm is a decision tree that can then be used for solving new problems.

CHAPTER2.UNDERSTANDING ICMs9?Conceptual Clustering Conceptual clustering algorithms learn new con-cepts by grouping sets of objects that are judged to be su?ciently similar,and not too dissimilar(see section2.3.5below for a discussion of the relationship between similarity and dissimilarity).CLUSTER/S(Stepp III and Michalski, 1986)is one such algorithm.CLUSTER/S begins by selecting a subset of the set of training examples to act as seeds for the clusters.It then attempts to include all the training examples in clusters around the seeds.The clusters proposed are evaluated by considering both how similar the examples in the cluster are to each other,and by how much examples within a cluster may di?er.Conceptual clustering systems may learn new categories that are not pre-de?ned by the input.The categories can then be used to classify new examples by measuring the distance between the category and the example.

?Incremental classi?ers Incremental learners,such as EPAM(Feigenbaum, 1963),UNIMEM(Lebowitz,1986),COBWEB(Fisher,1986)and CLASSIT (Genarri et al.,1989),take as input a sequence of examples from a domain de?ned as a conjunction of attribute value pairs.As each example is presented to the system,the system attempts to?t the example into a classi?cation hier-archy.If the system is unable to?t the new example precisely into an existing category,then a new category may be generated.This allows incremental learners to gradually improve the quality of their classi?cation mechanism.

Each concept in the classi?cation hierarchy is de?ned by a conjunction of typ-ical attributes and values,or in the case of CLASSIT,by a set of probability distributions that express the probability that an example is a member of the class given a particular value for each attribute.

?Explanation based learning Explanation based learning(Minton et al., 1989)uses a single example of a concept and a domain theory in order to learn a general description of the concept.This is done by using the domain theory to construct an explanation for the classi?cation of the example as an instance of the concept.The output is thus the general description of the concept.

All the examples in the list above share the assumption that previous examples should be used to learn abstract concepts or abstract knowledge.This method of using examples in problem solving may include the assumption that,once the knowledge has been abstracted,the cases may be discarded.Certainly this would appear to be the case for algorithms such as ID3where a complete problem solving structure is learned.

In contrast to the domain model learning methods above,Case Based Reasoning (CBR)attempts to make use of the information in the previous problem solving episodes directly to solve new problems,rather than using information abstracted from those episodes.In CBR the episodes or examples,are generally referred to as cases.A general outline of the various ways in which a case might be used directly in problem solving is provided by Kolodner et al.(1985).A list of possible uses of cases in problem solving based on Kolodner et al.(1985)is shown below.

?Old cases can be used in interpretation to:

-suggest features that need investigating

本文来源：https://www.bwwdw.com/article/nj4q.html