My main area of interest is the subfield of intelligent user interfaces known as programming by demonstration (PBD) or programming by example (PBE). The purpose of PBD is to have the user demonstrate the result of a computation, from which the system is able to construct a generalized program which is able to accomplish the user's task. A special case of PBD is macros, such as those found in GNU Emacs or Microsoft Office. Macros allow the user to record a sequence of fixed actions, and replay these actions using a single mouse click. Macros may be considered to be a simple straight-line program consisting of fixed actions with constant parameters. By constrast, PBD aims to learn more expressive programs, which may contain conditional constructs, variables, and iteration. By having the user construct programs using only the interface she is already familiar with, PBD hopes to combine the ease of use of macros with the expressiveness of programming.
My thesis work formalized programming by demonstration as a machine learning problem in the domain of repetitive text editing. Users create training examples for an ML algorithm by performing editing tasks. The goal is to automate repetitive editing tasks by learning a program which is able to perform the user's task, by watching as the user demonstrates the correct behavior of the program. Our system, SMARTedit, embodies a robust machine learning algorithm called Version Space Algebra to learn complex programs in a small number of training examples.
In addition to automating repetitive tasks, PBD might also solve the naming problem. With a proliferation of commands and associated names by which to invoke them, PBD may allow the user to demonstrate the beginning of a long, complex command sequence, and have the system recognize the sequence based on the demonstrated prefix.
My previous work has considered PBD in the email domain. My IUI paper discussed applying two standard machine learning algorithms to learn short programs for processing email. We contrasted Mitchell's version space algorithm and Quinlan's FOIL inductive rule learner on their abilities to learn more and less expressive programs given small numbers of training examples.
Macros are one example of a PBD system available in current text editing programs. Typically, one tells the system to begin recording, performs some actions, and then stops the recording. These actions may then be played back by invoking the macro.
The benefits to macros are that users don't need to learn special programming skills in order to automate long sequences of actions. Most, if not all, of the features of the user interface that the user is accustomed to are available for use in the macro. So macros could be an easy way for users to automate simple, repetitive tasks.
However, macros have their drawbacks. Since they only replay a fixed sequence of keystrokes, they're difficult to use for simple tasks such as numbering lines. Users need to think far enough in advance to realize that they are about to start performing a repetitive task, and start the macro recorder at the appropriate time. Also, users may find it difficult to construct macros that work in a wide enough variety of conditions, because constructing the macro requires forethought as to the kinds of conditions under which the macro is going to operate. For example, if a user wishes to delete the first word of a line, one way to do this is by moving the cursor to the beginning of the line, then typing the DELETE key as many times as there are letters in the word. However, if the next situation involves a word of a different length, this macro will fail to accomplish the desired task, and will delete the wrong number of characters. One solution is to use a different command, such as delete-to-end-of-word, which is guaranteed to work in a larger number of situations. However, the extra effort required to choose the right command for each situation makes macros difficult to construct. Finally, macros are difficult to debug; if the macro is in error, a user must either re-record it from scratch or drop down into the programming language representation of the macro (e.g. elisp) to repair it.
My thesis work formalized PBD as the machine learning problem of learning complex functions from examples of their input and output behavior. We modeled each text-editing action as a function that maps from one application state to another. For instance, moving the cursor from one location to another causes the application state to change to reflect the new cursor position. Given such state pairs, we infer the function (e.g. move to the next line) that explains each state change in the demonstration.
The canonical PBD web site is Henry Lieberman's Programming by Example page. The canonical reference textbooks are Allen Cypher's Watch What I Do and Henry Lieberman's Your Wish is My Command.
Several conferences occasionally attract papers and researchers working in the field of PBD: