Machine Learning Techniques to Make Computers Easier to Use

1 Introduction

Computers are still not easy to use. The main reason is their ignorance about the user. The user information that is available to an interactive computer system Is lim­ ited, and thus, the user model acquisition is a difficult problem. Classical acquisition methods like user inter­ views, application-specific heuristics, and stereotypical inferences are often not appropriate, and a better auto­ mated method is being sought.

Finding regularities in data is a basis of knowledge acquisition, and extracting behavioral patterns from the user information is one such problem. Each user has a different way of doing the same thing and identifying the information that can characterize the user and be auto­ matically collected is crucial. Once such information is found and if an appropriate machine learning technique can induce regularities in each user's behavior to carry out his/her intended task, we can use them to guide the Kenichi Yoshida Hitachi, Ltd.

Advanced Research Laboratory,

Hatoyama, Saitama 350, Japan

daily work and to do some preprocessing, which may facilitate easiness of usage and increase efficiency.

We discuss three learning tasks, command prediction, script generation and file prefetching in multi task en­ vironments. The scope of user behavior is limited to a sequence of task execution (e.g., editing, formatting, viewing, etc.) using plural application programs.

Most studies that attempted to develop a user­ adaptive interface system only analyzed the sequence of user behaviors, from which to automate the repetitions (See 7) . In this setting, the data can easily be repre­ sented by attribute-value pairs, each attribute denoting the sequence order and its value, the command. Since the command sequence does not necessarily typify the user's behavior, the user model constructed from only the sequence information may not adequately capture the user's behavior. We focused on the process I/0 in­ formation that is also automatically collected along with the command sequence. Since this is dependency infor­ mation and its relationship cannot be fixed in advance, it is not straightforward to represent this by attribute­ value pairs.

We show that graph-based induction [Yoshida and Motoda, 1995] can nicely be applied to the three learning tasks. In this paper, we revisit GBI, show how it can ex­ tract typical patterns from a set of directed graphs and how it can induce classification rules using a similar tech­ nique in the Top Down Decision Tree Induction (TDDT) algorithm. The first and the second learning tasks are implemented as ClipBoard which is a window like UNIX shell [Yoshida and Motoda, 1996], and the third task is implemented as Prefetch daemon that is hidden from the user. The results clearly show that the dependency anal­ ysis of computational processes activated by the user's commands, which is made possible by GBI, is indeed useful. ClipBoard is in daily use and its prediction ac­ curacy and response time are satisfactory. Prefetch dae­ mon works as expected only for I/0 intensive task due to an implementation problem, and thus needs further improvement.

The following section introduces the three learning tasks. Subsequent sections describe the learning method GBI and summarize the results of learning experiments performed to date. The last two sections consider lessons learned from this study and directions for future re­ search.

2 Learning Tasks

Command prediction is a real time task that takes a user's operational history and predicts the next com­ mand. Figure 1 shows, in a simplified form, an example of operational history when a user is making a document using a latex document formatter. The bold arrows show the command sequence. The history includes, in addi­ tion to this, I/ 0 relationships between commands, and thus, takes the form of a directed graph. Each link has a label that corresponds to a file extension. For exam­ ple, the link connecting latex to emacs has a label tex. However, one link is reserved for sequence information. ClipBoard keeps recording and updating the history, and at any point of operation, predicts the next command. The learning task is to induce classification rules from the past history. For each command in the past, a di­ rected graph of a certain depth (number of sequentially connected links) and width (number of sibling links) is taken out 1 . Each directed graph forms a training exam­ ple. Its root is a class and the rests are considered to be nested attributes.

Previous ttpplicati1m

Figure 1: cat ions) I/ 0 relationships between commands (appli-

Script generation is a batch task that extracts fre­ quently occurring patterns from a large graph represent­ ing a history of order of days, generalizes the arguments and generates shell scripts to execute a sequence of oper­ ations by a single command. Figure 2 shows an example of the generated scripts when a user repeatedly calls up emacs, latex and xdvi.

File prcfctching is a real time task that predicts files to be used in the immediate future and prefetches them into the cache. Unlike the command prediction, prefetching must predict a few steps ahead and thus more than one file. The learning task is done in a batch mode using a large directed graph. The task is to extract frequently occurring patterns first like script generation, from each of which a prefetch rule is generated and then to merge them into a single trie structure (example shown in Fig. 10). The prefetching is made in real time based on this trie. Since prefetching is automatic, this task is invisible.

1 In the experiments described in 4.1, the depth was set 5 and the width 128 (this is maximum and automatically adjusted).

3 Graph-based Induction

3.1 Finding Regularities in a Directed Graph

GBI was originally intended to find interesting concepts from inference patterns by extracting frequently appear­ ing patterns in the inference trace. In [Yoshida and Mo­ toda, 1995], it is shown that GBI was able to discover the notion of NOT and NOR from the simulation traces of an electric circuit. In this application, the original in­ puts are causal relations of voltage and current between various nodes of the circuit; there is no notion of logical operation. However, by finding regularities in the input traces, it was able to lift up the abstraction level and find more abstract concepts. Later, we showed that the same idea can be applied to other types of learning (speed up learning and classification rule learning) [Yoshida et al., 1994] .

The original GBI was so formulated to minimize the graph size by replacing each found pattern with one node that it repeatedly contracted the graph. The graph size definition reflected the sizes of extracted patterns as well as the size of contracted graph. This prevented the al­ gorithm from continually contracting, which meant the graph never became a single node. Because finding a subgraph is known to be NP-hard, the ordering of links is constrained to be identical if the two subgraphs are to match, and an opportunistic beam search simi lar to genetic algorithm was used to arrive at suboptimal solu­ tions. In this algorithm, the primitive operation at each step in the search was to find a good set of linked pair nodes to chunk (pairwise chunking).

Because the search is local and stepwise, we can adopt an indirect index rather than a direct estimate of the graph size to find the promising pairs. On the basis of this notion, we generalize the original GBI, and further extend it to cope with the classification problem. The idea of pairwise chunking is given in Fig. 3, and the gen­ eral algorithm in Fig. 4.

The selection criterion of the pair nodes should be such that its use can find interesting patterns (e. g., patterns occurring more frequently than others or patterns more GBI(G)

Selection of pair nodes ( Ak, f; , Bj)

Chunk the pair nodes into one node: c

C:=CU{c}

Gc := contracted graph of G

While termination condition not reached

C := CuGBI(Gc)

end_while

Output C

Figure 4: Generalized algorithm of GBI

easily identifiable than others). Proper termination con­ dition must be used in accordance with the selection cri­ terion (e.g., iteration number, chunk size, change rate of selection indexes, etc.). Examples of such indexes are information gain [Quinlan, 1986], information gain ra­ tio [Quinlan, 1993] and gini index [Breiman et al., 1984].

We use information gain as an index here, but the other indexes can be used in the same way. Unlike de­ cision tree building where the index is used for selectino­ an attribute, here we have to select linked pair nodes~ Each node has a value (color) and each link has a la­ bel. We can interpret the triplet (Ak, fi , B 1 ) as saying that the value of the i-th attribute fi of the parent Ak is Bj or when the i-th attribute fi takes the value B 0 its immediate result is Ak. The problem is which (i,j, f) to select to chunk. A natural way is to focus on one of ~he t~ree elements, and select the best remaining two to tdenttfy the chosen element. Three alternatives exist: a) focus on k, b) focus on i and c) focus on j. Case a) tries to find the attribute and its value pair that best char­ a~terizes the chosen immediate result . Likewise, case b) tnes to find the result and the attribute value pair that best characterizes the chosen attribute, and case c) tries to find the attribute and its result pair that best charac­ terizes the chosen attribute value. Which one to adopt depends on what the directed graph represents in terms of the original problem description. The default is to choose a).

In what follows , only case a) is described. The other two are obtained by permutating the subscripts. Let the underline in th~ subscript mean its complement (e.g., i means the attnbutes other than the i-th.), the overline in the variable mean a vector for the unspecified sub­ script(s) (e.g., nk means {n; ,1} for a k), and the super­ script yes and no mean the result of the division by test . The amount of information that is required to identify k before selecting the triplet is

where Nk is the number of nodes that have value Ak and nk,i,j is the number of the triplets (Ak, fi, B1) (i.e., the number of nodes that have value Ak and their i-th attributes have value B1.).

The amount of the same information after the selec­ tion is

The best attribute and its value for each k to select is

Thus, the best triplet is determined to be

This is recursively repeated until a termination condi­ tion is satisfied.

3.2 Inducing Classification Rules

In case of the classification problem, we interpret the root node as a class node and the links attached to it as the primary attributes. The node at the other end of each link is the value of the attribute, which has sec­ ondary attributes. Thus, each attribute can have its own attributes recursively, and the graph (i.e., each instance of the data) becomes a directed tree. In this case, the pairwise chunking must start at the root node and a-o b backwards following the links. Here, we have to select the attribute and its value pair that best characterizes the class. So the selection index is slightly different from the normal GBI described above.

The amount of information before the selection is

where nk is the number of nodes that have class value Ak(k = 1, K) , and N = Lk nk. The amount of informa­ tion after the test by the attribute fi whose value is B 0 0 1

IS

2 Note that the triplets that go into the yes branch are all identical, implying l(nykes ) = 0. ,t, )

Thus, the best attribute fi and its value B 1 to select for testing is

This is recursively repeated until each subgroup, after testing, contains a single class value or some stopping condition is satisfied.

4 ClipBoard Interface

Figure 5 shows the system configuration for ClipBoard Interface and Prefetch Daemon. The process I/ 0 recorder is a part of the operating system and records all the 1/0 operations of each command issued. This information is represented together with the command sequence by a directed graph as operation history. GEl program runs on this graph and generates prediction (classification) rules and typical patterns. The mouse­ based command controller uses these to 1) select the next command, and to 2) create UNIX shell scripts. The prefetch daemon uses the typical patterns to generate prefetch rules and merges them into a trie structure to 3) prefetch files.

Figure 6 displays the screen images of ClipBoard dur­ ing a simple document processing task. When ClipBoard starts without any information, the screen lists only file names (Fig. 6 (a)) . At this stage, after selecting a file to be processed, t he dialogue box appears so that the user can specify the command (Fig. 6 (b)). If the user specifies emacs, it treats emacs as the default for the file with the extension tex. ClipBoard tries to learn the appropriate command for each file extension, and rec­ ommends t he command by icons (Fig. 6 (c)). ClipBoard never asks the user for information. The user can always override ClipBoard's recommendation, which triggers the learning task. Icons for the same files change over time reflecting context changes.

Currently, ClipBoard interface is written by Tcl/Tk. The GBI program has both C and Lisp versions. The prefetch daemon is written by Java.

r:z~··:.r·j~~ ···· ··· ·· · ...... ··· ·· ·· · · ~i ·i ·;·;·:.;· ~~· ······· .............................. ±l?~

Figure 6: Screen image of ClipBoard

4.1 Command Prediction

1/0 Information Analysis

Consider an operation history in Table 1. As shown in steps (A), (B), and (C), the file paper.dvi is processed by three different commands: xtex, xdvi and dvi2ps. Fig­ ure 7 shows the corresponding directed graphs that are inputs to GBI. The algorithm described in 3.2 first chooses the dvi attribute (fi) and its value latex (Bj) for testing, and chunks the triplets (xdvi , dvi, latex) in (B) and (dvi2ps, dvi , latex) in (C) . The No branch con­ tains only one instance, (A), and the Yes branch contains two instances, (B) and (C). Next, the algorithm chooses the sequential attribute and its value xdvi for testing and chunks the triplet ((dvi2ps, dvi, latex), seq., xdvi) This separates (C) from (B) and the induction stops 3 . The shaded parts in Fig. 7 are the typical patterns. Figure 8 is the interpretation of the extracted patterns.

3 In reality, there are many occasions in history where dvi files are used by the same command that has different de-

• (C) If and Then dvi file was made from latex, the previous command was xdvi, Next Application is dvi2ps.
• (B) If and Then dvi file was made from latex, the previous command was latex, Next Application is xdvi.
• (A) If Then None of the above, Next Application is xtex.

Figure 8: Interpretation as prediction rules

GBI assumes the existence of a strong correlation be­ tween the linked attributes. As described in 3.2, the algorithm follows the standard TDDT induction, but the attributes to be selected are dynamically modified in the process. Note that it is impractical to represent the graph structure by a single table of attribute-value pairs.

Evaluation

The above algorithm for the classification problem was implemented and tested for the command prediction problem using both artificially generated and real op­ eration data.

Artificial data were generated approximating user's behavior by a Markov model that comprises five differ­ ent tasks. The model used is shown in Fig. 9. About

pendency, in which case the chunking process becomes more complicated.

2000 different sequences were generated, in which com­ mands that were not in the model (e.g., ls, df, etc.) were added as noise. Three fold cross validation was used to evaluate the prediction accuracy. The results are shown in Table 2. This table includes the results obtained by other methods for comparison.

Def.: Default value for most frequently used command

LD: Linear Discrimination Method

GB/1: W~ithout de . penden.cv info. for the root node comman~d to predJtt;

GB/2 : ith dependency info. for the root node

There are two cases for GBI. GBI1 is the case where dependency information is used only for the commands (nodes) preceding the root node. In other words , no de­ pendency information is used for the root node. This re­ flects the fact that the argument is not known in advance to predict the next command. GBI2 is the case where the dependency information for the root node (command to predict) is also used. This corresponds to a case where the file to process is specified, and this is exactly what the current ClipBoard Interface does 4 . In [Yoshida and Motoda, 1996] the former is called command prediction and the latter, application selection.

Default is the simplest way of prediction that al­ ways assumes the most frequently used command to be the next command. LD is a linear discrimination method [James, 1984], which gave the same answer as the default and did not improve the accuracy. The best result by the conventional method was achieved by the decision-tree learning method CART [Breiman et al., 1984]. LD and CART use only sequential informa­ tion because these methods cannot deal with information having a graph structure. From these results, it is clear that the I/ 0 dependency information (in particular, the one immediately before the command to predict) plays an important role in increasing the accuracy of predic­ tion.

4 This is not a strong restriction because files associated with a given task are generally known and the prediction of the command for each of these files can be made with this method.

The same algorithm was tested against the real data that had been taken from the log of daily usage over three months of a single user. The data include about 2000 kinds of commands. Two-thirds of them was used as a training data set and the rest as a test data set. The result is shown in Table 3. It is clear that GBI outperforms the other methods. Interestingly GBh is much better than CART in real data. This is probably because the number of commands actually used is much larger than the artificial data case and the noise level is also higher. Unfortunately the value for GB/2 is not available for the same data set. It is instead estimated by the daily usage when the performance approached the steady state. Once again, the role of I/0 dependency is clear.

The non-essential commands such as ls and df can be naturally ignored by a mouse-based interface system. If we ignore these effects and focus on the important com­ mands, we obtain the results shown in Table 4, which is by far better. While evaluation of ClipBoard is still ongoing, most of the important commands predicted by ClipBoard is quite adequate, and the user does not feel any burden in using it.

4.2 Script Generation

I/0 Information Analysis

To be precise, the I/0 recorder keeps track of 1) all pro­ cess creations in the operating system, and 2) all I/0 operations (open system calls). Thus, even in a multi­ window and/or a multi-task environments, it is possi­ ble to extract relationships between commands that may have been issued across the different shells. We use the whole graph to extract patterns. The extracted pat­ terns are frequently appearing ones in the history, and we convert them to shell scripts. The input file name is changed to the argument of the script with extensions retained (See Fig. 2).

Evaluation

Table 5 lists the scripts generated from the sample his­ tory, which involves about 10,000 process creations and about 130,000 I/0 operations. The number of processes includes system programs that were not invoked by the user (e.g. , telnet daemon, line printer spooler daemon, etc.) , some user commands (e.g., shell scripts), and cre­ ated child processes. The number of the actual com­ mands invoked by the user was approximately 2000.

Since the algorithm only considers the frequency or its equivalent as measured by the index, evaluation of the usefulness or importance of the generated scripts must be rendered to the user. Unlike the case for command prediction, there is no direct feedback from the user. The scripts in Table 5 have clear meanings except script 3. Without having knowledge about the C compiler, Clip­ Board could generate scripts 4 and 6. ClipBoard did not use any pre-specified knowledge about latex and related commands in generating script 5. Script 1 is a unique script for this particular user. Without ClipBoard the user has to write this by him or herself.

5 Prefetch Daemon

I/0 Information Analysis

In a multi-task environment different users work on the same machine for different tasks (e.g., editing and pro­ gramming). Even though the I/0 operation sequence of each task has regularity, the overall I/0 sequence is af­ fected by the subtle timing of each task progress. The graph structure can encode the correct information even in a multi-task environment. Just like in the case of script generation, GBI analyzes the process data and represents them by a set of directed graphs, from which it extracts typical patterns. Each of the patterns repre­ sents an aspect of the user (we call it user model for con­ venience). Figure 10 shows how these patterns are used to prefetch files. First, each of the patterns is converted into a prefetch rule. Unlike the command predictions, the point here is not to predict the root node from the rest, but to predict from the bottom (first) node in the sequence how certain files are going to be used along the subsequent command execution. Each rule consists of a sequence of events, i.e., command executions and 1/0 operations, with a list of files to be prefetched. Next, each rule is merged into a single trie structure. The sys­ tem checks the common event sequences in the rules and merges the same parts into a single structure. For ex­ ample, in Fig. 10, the first nodes of the two user models, A and B, are the same and are thus merged. In order to improve the prefetch accuracy, the frequency informa­ tion in the log is used to prune files 5 . The generation of trie structure is performed as a batch process.

Evaluation

After the batch process constructs the trie structure, the prefetch daemon uses this trie structure to prefetch files. The daemon maintains the status information for each process. If a new process is act ivated, the prefetch dae­ mon creates a new pointer which points the root node of the trie structure. If the process executes command emacs (i.e., the program memorized in the succeedino­ trie node), the daemon prefetches program files mak~ and bzbtex and updates the pointer. In Fig. 10 process (a) shows the position of the pointer after it executed ~macs and then bibtex. Each time it updates the pointer, Jt also looks for the same command from the root (i.e., the command just below the root node) as if a new pro­ cess with this command was initiated. When it finds the command, it also prefetches the associated files. This is recursive. If the actual events of the process exhibit a different sequence from the trie, all the pointers for this process are removed and the prefetch daemon io·nores · b the process until a new process is initiated.

The above prefetch mechanism was tested for the daily usage data (the length of the log was about 38,000). The prefetch cache size was automatically adjusted by OS. The trie had approximately 1000 nodes. Although fur­ ther experiments are necessary, the preliminary experi­ ments show that the trie structure has high prediction accuracy. For the experiment we conducted, the hit rate was almost 100%.

Unfortunately, even with the high hit rate, the current implementation slows down the CPU intensive tasks due to the CPU resources used by the prefetch daemon. We could only speed up l/0 intensive tasks. It could indeed speed up the invocation of a large program such as X­ wmdows and mule to the extent that we did not feel we had waited. The process switching overhead and the JAVA byte code interpretation are the sources of the problem. A kernel embedded file prefetcher that is coded by C and assembler would solve the problem.

5 There are many patterns that partially overlap and/or are subpatterns of the others. A threshold can be set to the number of occurences of the files for them to be prefetched.

6 Discussion

6.1 Learning Semantics from Syntax

Alt~ough ~h.at GBI does is simply extracting the syn­ tacttc/stattsttcal nature of what a user has done in the past, it is still possible to extract useful semantics of the user's behavior. The user never tells the start of his/ her task to ClipBoard, but the scripts generated by GBI does capture a piece of meaningful tasks. Most cru­ cial is the information source. The surface form of the user's input (i.e., command sequence) was not enouo-h. Other information that is hidden and invisible (i.e., p~o­ cess l / 0) contributed much. Standard techniques (e .g., index based on information theory, cross validation, etc.) that statisticians have developed are also important fac­ tors.

6.2 Information to Capture User Behavior

[Piernot, 1993] addresses the importance of the context in an interface system. File extensions we used in our analysis to capture the I/0 information helped provide rich context. Other information that may help capture the user's behavior is command exit status and time of execution. For example, if the user fails to compile a program because of a simple syntactic error, the next step tends to be an editing task. If s/he succeeds, it tends to be a test run. Thus, the exit status seems to be informative. Since most users tend to check e-mail in the morning, the time of day also seems to be informative. Experiments using ClipBoard utilizing such information are currently under investigation.

The method of encoding information is also important. We encoded the I/0 information from how a file was made by application program. The experimental results suggest the adequacy of this encoding, but this is not the only way to use the l / 0 information. For example, how a file was used by application program is another way of encoding. Figure 11 shows a graph format that was designed to emphasize this aspect. We confirmed the usefulness of this encoding with a version of ClipBoard that uses this as an alternative to the sequence infor­ mation. Note that this encoding has a noise-tolerant nature. User errors, such as mistyping and wrong com­ mand selection, and unexpected interrupts, such as new mail arrival, sometimes cause noise in sequence informa­ tion. The replaced I/ 0 information is less affected by such noise.

6.3 Method of Analyzing User Behavior

If the user is always logical and consistent, the analyti­ cal methods, such as explanation-based learning, are ad-

(C) is the directed graph of the history information at Step (C) in Figure 1. The shaded part indicates that paper. dvi was previously used by xdvi. (C)' is the reconstructed graph. The dvi node is removed for brevity and the (used by) xdvi node replaces the sequence information.

Figure 11: Graph encoding the knowledge of how a file was used.

equate in making the user behavior model. Unfortu­ nately, the user is sometimes illogical and inconsistent, and capriciousness makes it difficult to apply analyti­ cal methods to the interface problem. The statistical methods, such as linear discrimination and k-nearest­ neighbor [James, 1984], and empirical learning methods, such as [Quinlan, 1986], seem to be more adequate. The errors, i.e., mistyping and wrong command selection, are naturally ignored as noises in these methods. However, these methods are not suited to handle structural data as was the case for this study.

If we set the maximum width (number of input files) per command and the maximum depth (number of chains of I/ 0 relationship), it is possible to design a table of attributes and values that can record all the necessary information. If we take the maximum width as 50 and the maximum depth as 5, a table with :::::: 50 5 attributes is created 6 . This is only for one instance. If the analysis requires 1000 cases, the table size becomes huge.

Inductive logic programming (ILP) [Quinlan, 1990; Muggleton and Feng, 1992; Pazzani and Kibler, 1992], on the other hand, is more expressive and captures the relations most naturally in first-order logic. It can also handle noise [Quinlan, 1990; Pazzani and Kibler, 1992]. To explore the potential of this approach, we tried to use FOCL, one of the most efficient ILP systems, to analyze the real data used in Section ·4.1. However, FOCL took more than 4 hours to find the first test condition of the first rule; therefore we had to give up this approach 7 .

GBI's expressiveness lies in between the attribute­ value pairs and the first-order logic. It is a limited form of propositional calculus. Its learning potential is much weaker than that of ILP, but stronger than that of the attribute-value representations and yet as efficient. We demonstrated that command prediction we addressed in this paper is a class of the problem that GBI's framework fits well.

6.4 Other Applications

The idea of ClipBoard seems to be useful in designing interface systems of other kinds such as automatic chart format selection in spread sheet and data base, naive­ user guidance and installation guidance-and-diagnosis systems. The last two are meant to apply the knowl­ edge learned from expert behavior to non-expert users. During the development of ClipBoard, we were able to use the I/ 0 information itself, i.e., the raw history data, for debugging purposes. A good display system of this information seems to be beneficial even for an expert user.

6 Note that a typical (not maximum) single run of the latex command receives 50 input files (e.g., .tex, .aug, . sty . . bbl, .eps, . tfm, .fmt, etc).

7 We have not taken advantage of the search strategy used in GBI.

We are aware of some minor things that could improve ClipBoard's ease of use. For example, we could improve ClipBoard's selection function by highlighting the second suggestion shown in the dialog box (See Fig. 6 (b)) when the user wants to override ClipBoard's first suggestion (which is displayed by icon).

One promising application that goes beyond those within a single machine is dynamic World Wide Web caching. The rapid growth of information gathering through WWW causes a heavy network overload, and the resulting slow response is causing a problem. Dis­ tributed caching is a promising approach. Our prelimi­ nary study [Yoshida, 1997] by GBI shows that it is pos­ sible to reduce the overload by extracting frequent oc­ curring data transmission patterns from the wide area network flow and using this to allocate distribute cache storage. The simulation assumed the situation where 32,000 WWW servers are accessed simultaneously by 16 clients. Each client and router had a 32 MB cache capac­ ity. The data were taken from the access log of our proxy server that included 2.3 million data transfers (18. 7 GB in size). Figure 12 shows how the traffic changes with the time of day with and without cache, from which we observe 26% reduction of traffic between 10 am and 8 pm. The traffic reduction at the peak time amounts to 100MB.

7 Related Work

Intellectual assistance by computers has attracted many people, and various attempts have been undertaken with different approaches and for different tasks. There are many terms that characterize these approaches such as learning apprentice, software agent, learning agent, in­ terface agent, programming by example or demonstra­ tion, personal knowledge based system, etc. What is common to many of them is that they observe repetition or regularity in the user's behavior and use them for au­ tomation, prediction and customization in one way or another.

The amount of knowledge that has to be provided in advance varies among the approaches. General remarks are that making the user program everything requires too much insight, understanding and effort from the user, and having to encode a lot of domain-specific background knowledge about the task and the user also requires a huge amount of work from the knowledge engineer. Both have fixed competence, and are hard to customize to individual user differences or changes of habits. Some sort of automatic knowledge acquisition that can capture each user's habits is needed.

EAGER [Cypher, 1991] is an example of program by demonstration (PBD), which is a HyperText system that keeps watching a user's actions, detects an iteration and offers to run the iterative procedure to completion by generalizing the repetitions and making macros. My­ ers 's demonstrational formatter [Myers, 1991] is also an example of PBD. It does not focus on the repetition, but generalizes a single example to create a template for later use, which enables the formatting of headers, itemized lists, tables, references, etc. Another example is Gold [Myers et al., 1994] which is a business charted­ itor. It is given the knowledge of properties of the data and the typical graphics in business charts to generalize a single, or a very few examples, by interpreting them as a combination of primitives.

[Greenberg and Witten, 1988] analyzes repetitive pat­ terns in the UNIX command histories and observes some regularities. [Masui and Nakayama, 1994] also uses the repetitive nature for a predictive user interface. When a user types a repeat key after doing repetitive operations, an editing sequence corresponding to one iteration is de­ tected, defined as a macro, and executed at the same time. Although being simple, it covers a wide range which had to formerly be covered by keyboard macro.

All of the above approaches do not use machine learn­ ing techniques although they do guess and generalize. The Interface agent of [Maes and Kozierok, 1993] takes a machine learning approach. They address the problem of self-customizing software at a much more task inde­ pendent level. The core is to learn by observing the user , i.e., by find reguralities in the user's behavior and using them for prediction. They also adapt two other learning modes: learning from user feedback and learning by be­ ing told. They used memory-based learning (k-nearest neighbor) which is good for explanation. Situations in the user are described in terms of a set of attributes which are hand-coded. The tasks that they applied are a calendar management agent and an electronic mail clerk.

The personal learning apprentice CAP [Dent et al. ,

1992] is similar to the above. It is an interactive assis­ tance that learns continually from the user to predict de­ fault values. Their application is a calendar management apprentice which learns preferences as a knowledgeable secretary might do. Two competing leaning methods are used: decision tree learning and backpropagation neural net. The attribute value representation suffices for this purpose. Another related system addresses the task of form-filling [Hermens and Schlimmer, 1993]. They use decision tree learning to predict default values for each field on the form by referring to values observed on other fields and the previous form copy.

[Schlimmer and Hermens, 1993]'s pen-based interac­ tive note taking system is a self-customizing. software to eliminate the need for user customization. It starts with partially-specified software and applies a machine learn­ ing technique to complete any remaining customizat ion. The system learns a finite state machine to character­ ize the syntax of user's notes and learns decision tree to generate predictions. Letizia [Lieberman, 1995] is an in­ terface agent that assists a user browsing the WWW. It tracks user behavior and attempts to anticipate items of interest by doing concurrent, autonomous exploration of links from the user's current positions. Intelligent agent for information browsing is a hot area and many sys­ tems are being pursued (e.g., [Etzioni94 and Weld, 1994; Perkowits and Etzioni, 1995].

The research on prefetching is carried out by a sep­ arate community. The standard Least Recently Used (LRU) based caching offers some assistance, but ignoring any relationships that exist between file system events fails to make full use of available information. The clos­ est work that uses the relationship would be [Kroeger and Long, 1994]. They use trie structure to memo­ rize previous 1/0 sequence but no explicit learning is performed. Their results indicate that the predictive caching gains on the average 15% more cache hits than the LRU based caching. However, since they are using only sequential information, their method does not work well in a multi-task environment.

All of the applications that use machine learning tech­ niques do not require relational representations. The data are represented by a set of features . Analysis of se­ quential information is enough for the selected applica­ tions. Some require additional task specific knowledge. We showed in this paper that there are other applica­ tions that this success cannot be easily generalized, and proposed the GBI as a general induction mechanism for this type of applications.

8 Conclusion

We have modeled a user adaptive interface that can pre­ dict next command, generate scripts and prefetch files in a multi-task environment. The analysis of behavioral data indicated that the directly observable sequential records are not enough to capture the behavior, and that simultaneous use of process 1/0 information that is hid­ den from the user is beneficial. An efficient induction algorithm that can handle relational data was needed and a technique called graph-based induction was ap­ plied. It can find frequently occurring patterns from a graph representation. It also induces classification rules from structured data that have intra-relationship. Pair­ wise chunking, which is the heart of the algorithm, does not guarantee an optimal solution by any means, but empirical study shows that use of statistical measure re­ sults in a good solution. It is efficient and can run in real time. The command prediction module is in daily usc. Shell script generation works as expected but is less used. Prefetching daemon still needs a better implemen­ tation to enjoy the real benefit.

Acknowledgments

Much of the work was conducted while the first au­ thor was at ARL, Hitachi, Ltd. Authors are grate­ ful to Shojiro Asai and Katsumi Miyauchi of ARL for their generous support of this work. They extend their thanks to Takashi Washio, Tadashi Horiuchi and Toshi­ hiro Kayama of Osaka University for the discussions.