algorithm

We propose a new evolutionary method of extracting user preferences from examples shown to an automatic graph layout system. Using stochastic methods such as simulated annealing and genetic algorithms, automatic layout systems can find a good layout using an evaluation function which can calculate how good a given layout is. However, the evaluation function is usually not known beforehand, and it might vary from user to user. In our system, users show the system several pairs of good and bad layout examples, and the system infers the evaluation function from the examples using genetic programming technique. After the evaluation function evolves to reflect the preferences of the user, it is used as a general evaluation function for laying out graphs. The same technique can be used for a wide range of adaptive user interface systems.

Recent work is beginning to reveal the potential of numerical optimization as an approach to generating interfaces and displays. Optimization-based approaches can often allow a mix of independent goals and constraints to be blended in ways that would be difficult to describe algorithmically. While optimization-based techniques appear to offer several potential advantages, further research in this area is hampered by the lack of appropriate tools. This paper presents GADGET, an experimental toolkit to support optimization for interface and display generation. GADGET provides convenient abstractions of many optimization concepts. GADGET also provides mechanisms to help programmers quickly create optimizations, including an efficient lazy evaluation framework, a powerful and configurable optimization structure, and a library of reusable components. Together these facilities provide an appropriate tool to enable exploration of a new class of interface and display generation techniques.

Standard telephone keypads are labeled with letters of the alphabet, enabling users to enter textual data for a variety of possible applications. However, the overloading of three letters on a single key creates a potential ambiguity as to which character was intended, which must be resolved for unambiguous text entry. Existing systems all use pairs of keypresses to spell out single key letters, but are extremely cumbersome and frustrating to use.

Instead, we propose single-stroke text entry on telephone keypads, with the ambiguity resolved by exploiting information-theoretic constraints. We develop algorithms capable of correctly identifying up to 99% of the characters in typical English text, sufficient for such applications as telephones for the hearing impaired, E-mail without a terminal, and advanced voice-response systems.