1. Project Overview

Many software tools and software-based products are used by a very wide variety of users, each with different demands and patterns of use. It is impossible, under these circumstances, for off-the-shelf software to be "optimal" for any particular user. The main form of adaptation that is presently available is "typical user" adaptation, in which the needs and patterns of use of a hypothetical, typical user are defined and the software is fitted to optimize the performance of this typical user. When the set of users is quite varied, or when needs and usage patterns change with time, the needs of a real user will differ from those of the hypothetical typical user. This, in turn, means that the real users' productivity and quality of work have not benefited from the adaptation process, they may even have degraded.

We propose to develop a novel form of software adaptation through learning. The aim is to improve existing software tools with agent-based extensions that dynamically enhance the interactive environment according to each individual user and circumstance of use. A "learning apprentice" observes user interaction with the software and learns how to carry out a particular task. In future interactions, the apprentice may notice a situation in which that task has been successfully performed, and suggest that the same task be performed in the current situation. As an individual's pattern of use changes, the system adapts its function to those changing patterns. Machine learning techniques may be used to acquire effective models of the domain. The apprentice may also learn from an expert about tasks and carry those out or explain them for a more naive user. Adaptive software enhancement is very different from adaptive user interfaces, which essentially tune the level of help and the verbosity of the commands to a predefined level of user's expertise (e.g. novice, expert). We propose to expand the functionality of the software, rather than its appearance.

Adaptive enhancing has potential for extremely broad impact: it applies to virtually all software with extensive functionality, rich application domains, and a broad user community. We expect that development of this technology will influence, e.g., software to access on-line hypermedia repositories (such as a World Wide Web navigation program that infers user interests and automatically directs the user to relevant documents), software tools to build other software (e.g. browsers of program libraries that try guessing what the user may be searching for and suggest the next move towards that uncertain goal), consumer software for the personal computing market (e.g. note-making programs anticipating the next written word), and software embedded in microprocessor-based systems (e.g. intelligent telephones learning frequently used numbers).

The key to making adaptive enhancement practical and cost-effective is to make it as automatic as possible. Because adapting will occur often, any significant cost per adaptation will accumulate to an unacceptably large overall cost. Therefore, the software must automatically infer how to adapt by observing constantly the examples of use of the system. Machine learning - the subfield of AI providing algorithms and techniques for generalizing concepts and procedures from examples - is clearly the approach to adaptation using observations.

2. Performance Tasks

One of the central paradigms of AI is search. We propose to make the related, but different problem of iterative search the performance task for adaptive software enhancement. In iterative search the user, unclear about the exact goal of the search, navigates through a repository. Examples of iterative search include looking for reusable software, looking for an abstract of a paper in an on-line bibliographic data base, or searching for relevant items on the World Wide Web. We propose to focus our work on apprentices that learn from interactive search, for the following reasons:

-- interactive search is ubiquitous in a wide variety of applications. We list below two specific areas in which use of computer systems is a form of search

-- interactive search is a good environment in which to build learning apprentices. as it exhibits most of the features that apprentices must have, and easily supports retro-fitting of apprentices to existing systems.

-- our team has considerable experience in learning apprentices in interactive search, and in the evaluation of the benefits from such apprentices [Duchier 93], [Drummond et al. 93] (note: for publications coauthored by R.C. Holte and S. Matwin see their forms 100).

The two selected interactive search systems for which it is interesting to build apprentices are a World-Wide Web navigation system and a software library browsing system.

The World Wide Web (WWW) continues to gain popularity as the primary method of accessing information and distributed services over the net. As its use and navigation with existing tools is often cumbersome, the present popularity of the Web shows that the value of information it provides must far outweigh the inconvenience of the relatively unfledged access methods. The cognitive overhead involved in deciding where to go, given limited or non-existent foreknowledge, has been recognized as a fundamental issue. The difficulty of maintaining and organizing one's personal information environment has been magnified by the volume and variety of information references that a user is likely to come across and wish to preserve. For example, Mosaic, a WWW browser, introduced the notion of a "hot list" in which a user may accumulate references to distributed documents, thus making them rapidly available. In practice, the hot list rapidly grows in size and it becomes quite difficult to find anything in it since it is a linear, chronological list with no helpful structure or categorization. On the other hand, a learning apprentice may learn user preferences by observing the succession in which documents or information sources are typically accessed by the user. Such adaptive, self-organizing hot list would be a useful enhancement of the Mosaic browser.

A software library browsing system is the second performance task which we want to enhance adaptively by means of a learning apprentice. In browsing the user is searching in a library for the item, or collection of items, that best suits her needs (we use the term browsing to include querying-like actions as well as the associated navigation along links in the library). In our experiments with a learning apprentice for browsing an Object Oriented library of modules we have shown that even a simple prototype often improves the speed and success rate of browsing [Drummond et al. 93]. The apprentice observes the user's normal browsing actions, infers what the user is looking for (the "analogue" of the user's goal), searches the library for the items that best match, and reports them to the user. In our experiments, the learning apprentice identified the target item before it was found by the user 40% of the time.

In both tasks, the user is assumed to have incomplete, imperfect knowledge of the content, organization, and descriptive language of the repository. Because of this, both the browsing and the WWW navigation process are fundamentally uncertain and iterative. Although there might exist a single operation or short sequence of operations that will retrieve the "best" item, the user is, in general, uncertain of which operations are most useful and perhaps even uncertain of which item is "best". We call the user's mental model of the target item the "search goal". The search goal is continually being refined, and perhaps considerably altered, by the user as search proceeds and the user gains knowledge about the repository. A learning apprentice will either make the tentative next search step for the user, or make suggestions about the next step. Consequently, the enhancement can be either at the functional level, when the function of the software is modified, or at the cognitive level, when the user model is being refined by the apprentice and the ensuing suggestions are given.

3. Objectives

As stated in section 1, the overall aim of our research is to develop techniques to enable adaptive enhancement of software with rich functionality, and/or operating in rich domains (contexts). Our fundamental strategy is to retrofit to the software a "learning apprentice" which observes the use of the system, learns the user's current pattern of behaviour, and adapts the system accordingly.

To achieve these aims, it is necessary to solve a number of technical problems. These problems are more fully defined in section 5, where we also describe how we propose to solve them. The purpose of this section is simply to summarize the issues and link them to the overall aim.

1. how to optimize the utility of the apprentice

The benefits of adaptation are, as usual, increased user satisfaction, productivity, quality of work etc. Counterbalancing the potential benefits are two sorts of costs associated with using a learning apprentice: (a) it is fallible and therefore will occasionally wrongly adapt the software and degrade performance (b) any special input or interaction that is required by the apprentice, but not by the underlying software, is a distraction to the user likely to degrade performance. Our objective, naturally, is to optimize this tradeoff, to maximize the net benefit. The corresponding technical issues are

1. suggestion quality

How to maximize the number of high-confidence suggestions/predictions; (see "trading accuracy for coverage")

2. user interaction

How to interact with the user in a form that is both convenient (minimally distracting) and highly informative

In our strategy, the apprentice collects data about the user over a period of time and, when it is confident enough, supplements the software with the enhancements resulting from so inferred model of user's needs. Because the user's needs change from time to time, re-enhancement will be necessary. Such repeated enhancing may involve inference of new features from old features (feature engineering), and generally change of representation. Moreover, the apprentice will be of no benefit if it cannot adapt quickly enough, i.e. if the time taken to do the adaptation exceeds the time for which the adaptation is useful. The corresponding technical issues are

3. coping with context shift
4. feature engineering
5. real-time learning

2. How to retrofit a learning apprentice to existing software.

The basic retrofitting process seems simple: first, give the learning apprentice a copy of the inputs the user gives to the software, and provide access to any of the software's internal "state" variables (e.g. the hypertext document which the user viewed) and databases (e.g. the library in our browsing system). Then let the apprentice change the state-variables, databases, outputs of the software to the user, or even intercept and alter the user's inputs to the software. Retrofitting involves adapting the apprentice to suit the application (e.g. WWW navigation) and the specific software to which it is being retrofit (e.g. Mosaic). The following issue is a necessary condition for a successful retrofit:

for the apprentice to succeed, considerable knowledge is needed about the meaning of its inputs and the effects of its actions, in terms of the task performed by the user. This raises the technical issue of how to acquire this knowledge, and how to use it in the apprentice's learning process. We propose to use machine learning to acquire this knoweldge whenever user feedback about effects of apprentice's suggestions is available.

3. The learning apprentice must maintain a sort of user model

How can this model be represented, what knowledge is needed to infer it? In the browsing task, the user model is called the "search goal analogue". This is probably one of the simplest of user models yet even here, a fairly expressive language is needed, and fairly complex application-specific rules are needed to update it. In fact, our current assumption that the user has just one goal at a time will have to be relaxed. Even more complex representations and inference rules are required for the real situation, where a user's goal is composite (composed of several subgoals).

4. Related Work

Literature on learning apprentices is surprisingly scarce. The very idea of learning apprentices was first proposed by [Mitchell et al. 85]. The circuit design apprentice described by these authors was capturing explainable designs, and generalizing them according to an EBG algorithm. The need of a complete domain theory was a drawback. Newer work [Dent et al 92] from this group overcomes the problem using different forms of inductive learning, including neural networks [Thrun, Mitchell 93], to acquire and incrementally grow the domain knowledge of the apprentice. [Hermens and Schlimmer 93] describe a very simple apprentice, without background knowledge and limited essentially to rote learning. Some of the context drift problems described below manifest themselves in another learning apprentice described by [Schlimmer and Hermens 93].

5. Methodology

1. The Tradeoff between Coverage and Accuracy

By its very nature, a learning apprentice does not degrade the user's performance if it does nothing - the user proceeds normally, without even being aware of any (possible) missed opportunities for improved performance. This observation underlies the strategy for improving the accuracy of a learning apprentice: it is allowed it to cue the user only when there is relative confidence the suggestion is correct. This strategy is called trading coverage for accuracy: the apprentice makes fewer suggestions (lower coverage) but the suggestions it makes are better (more accurate). On the other hand, if an apprentice's suggestion is accepted by the user, this will be interpreted as positive reinforcement of the confidence in the suggestion. [Schlimmer and Hermens,1993] employ a variant of this strategy in which the apprentice informs the user of its confidence. In [Holte et al.,1989] we found that a moderate sacrifice in coverage could produce a relatively large gain in accuracy, a finding which has been confirmed recently by others. Two research questions raised by this strategy are: (1) how can the system decide when to make a suggestion? (2) how can the system maximize both coverage and accuracy? We will look to background knowledge to address these two questions. In [Clark, Matwin, 1993] we used background knowledge to constrain the form of rules induced by a learning system. Assuming that the background knowledge is roughly correct, the rules induced in this way should produce reliable predictions (suggestions) and therefore should be used whenever possible. Purely inductive techniques also may help in answering the two questions. Techniques for question (1) include empirically estimating a suggestion's correctness/utility (see the "small disjuncts" technique we introduced in [Holte et al.,1989]). For question (2), we will investigate inductive biases that maximize the coverage-accuracy tradeoff (so that the least coverage is lost for the amount of accuracy gained).

2. Context shift

Context refers to the user's needs and patterns of behaviour. In any real-world application, these will change with time, sometimes dramatically. For example, the WWW rules will be subject to changes in user's interest, and the interests may shift or become more specialized as the user becomes more expert in a given field. A learning apprentice needs to be able to cope with context in which the user operates. Assume, e.g. that while reading an AI article on Mosaic, the user spots a reference by the author A that interests her, and decides to go to the Science Citation Index to retrieve other papers by A. If there are many authors with the last name A, publishing in different fields, the apprentice might want to narrow this search to AI, which was the topic of the article that initiated the search. The apprentice should also be able to track context "drift", to detect and adapt to abrupt changes., e.g. when the user moves her search from one Web site to another. This issue has recently begun to receive attention [Turney 93], [Widmer 93] in the general machine learning community. As we closely cooperate with Dr. Turney, we expect smooth incorporation of these techniques into our learning apprentice.

3. Feature/bias engineering

Successful learning requires the appropriate background knowledge as well as the right features used to describe examples and rules. For instance, the WWW agent could categorize the documents viewed by the user according to domain knowledge, and then use its model of the user to rearrange references to them according to their relevance.

Collectively, the explicit background knowledge, the hypothesis language and the representation of the examples are referred to as the bias. In the ideal situation, the bias provides just the features and syntax needed to identify a highly accurate rule on the basis of a few training examples. The features and background knowledge that naturally occur in the operating environment of a learning apprentice will almost never be an adequate bias. For the apprentice to succeed, new features and/or background must be engineered, i.e. invented and incorporated into the apprentice.

We will examine the possibility of automating or assisting aspects of the bias engineering by using various empirical and knowledge-based techniques for bias selection and constructive induction (feature invention), such as [Ling et al. 93] and [Clark and Matwin 93]. The browsing apprentice could, e.g., benefit from ontologies to classify software components while assisting the user browsing, and such ontologies could be learned from examples. In our current learning apprentice for browsing we use an extremely simple representation for the search analogue, but experience has shown that this representational bias is not entirely appropriate, and a richer representation is needed. We will investigate several alternative representations, including neural nets for their robustness and noise-resistance, and first-order logic (FOL) for its expressive power. Our expertise in learning FOL concepts will be useful in addressing this objective.

6. Role of Research Personnel

Rob Holte will be responsible for the work on coverage vs. accuracy. Stan Matwin will be responsible for the feature engineering work. Both investigators will be working jointly on the context shift problems, as well as on the issues related to the retrofitting of the apprentices. Denys Duchier, a postdoctoral fellow, has been with our group for the last two years. Dr. Duchier has considerable experience in the development of software for interactive search in the GARNET Graphical Toolkit library. Dr. Duchier is also the leading expert in the access and use of WWW in Ottawa. Chris Drummond has written the early browsing apprentice. Currently a Ph.D. student, Chris is interested in pursuing the research on learning and search as his Ph. D. topic. John Ng is working on a Master thesis in which a browsing learner will assist the users of a Smalltalk library. If funding was available, his work could be extended into a Ph.D. project. Several other graduate students at both Ph.D. and Masters level expressed interest in our project.

Our team has a considerable experience in getting students involved in Strategic Grant research. The team presented in the preceding paragraph has already worked on a previous grant for more than two years. We have a solid record of cooperation, both between the investigators, and with the postdoctoral fellows and graduate students. We hold weekly team meetings, in which we evaluate current progress and discuss in a more substantial manner a selected problem of importance at the given stage of work. Graduate students are also actively involved in user workshops (see the section on Promotion of Results to the User Sector), writing papers, external presentations, conferences and so on.

7. References

Dent, L., Boticario, J., McDermott, J., Mitchell, T.M, Zabowski, D., "A Personal Learning Apprentice", Procs. of AAAI-92, pp. 96-103, 1992.

Duchier, D., "Concrete Browsing Of A Graphical Toolkit Library", Procs. 5th International Conference On Tools With AI, Boston 1993.

Hermens, L., Schlimmer, J. C.,"A Machine-learning Apprentice for the Completion of Repetitive Forms", Procs. of the 9th CAIA, pp. 164-170, 1993

Mitchell, T. M., Mahadevan, S., Steinberg, L., "LEAP: A Learning Apprentice for VLSI Design", Procs. of the 9th IJCAI, pp. 573-580, 1985.

Thrun, S.B., Mitchell, T.M., "Integrating Inductive Neural Network Learning and Explanation Based Learning", Procs. of the 13th IJCAI, pp. 930-935, 1993.

Schlimmer, J.C., and Hermens, L., "Software Agents: Completing Patterns and Constructing User Interfaces", Journal of AI Resaerch, vol. 1, pp. 61-89, 1993.

Turney, P., "Exploiting Context When Learning to Classify", Procs. of ECML-93, pp. 402-407, 1993.

Widmer, G. Kubat, M., "Effective Learning in Dynamic Environments by Explicit Context Tracking", Procs. of ECML-93, pp. 227-243, 1993.