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