Method for designing optimal single pointer predictive keyboards and apparatus therefore

• US 6,646,572 B1
• Filed: 02/18/2000
• Issued: 11/11/2003
• Est. Priority Date: 02/18/2000
• Status: Expired due to Term

• Current Assignee: CDN Innovations, LLC (IP Investments Group LLC)
• Original Assignee: Mitsubishi Electric Research Laboratories (Mitsubishi Electric Corporation)
• Inventors: Brand, Matthew
• Primary Examiner(s): Edwards, Timothy
• Application Number:
  US09/506,610
• Time in Patent Office: 1,362 Days
• Field of Search: 341/22, 341/23, 341/34, 345/128, 345/130, 345/169, 345/173, 345/179, 382/230
• US Class Current: 341/22
• CPC Class Codes: G06F 3/0219 Special purpose keyboards
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus

Abstract

Keys are arranged on a keyboard as learned during a training stage. During training, a training corpus of input symbol sequence is provided. Each unique symbol in the corpus has an associated key on the keyboard. A cost function that measures a cost of inputting the symbols of the training corpus is globally minimized. Then, the keys are arranged on the keyboard according to the globally minimized cost function. To reduced the distance a pointer must move, the keys can also be arranged in a hexagonal pattern.

Claims

1. A method for arranging keys on a keyboard:

providing a training corpus of input symbols, each unique input symbol having an associated key on the keyboard;

globally minimizing a cost function that measures a cost of inputting the symbols of the training corpus; and

arranging the keys according to the globally minimized cost function.

2. The method of claim 1 further comprising the steps of:

constructing a model from a training corpus including symbol sequences, the model predicting a set of symbols, each symbol of the set continuing a particular symbol sequence using variable-length subsequences of the particular symbol sequence, a particular length chosen to maximize a probability that the predicting is correct;

highlighting keys on the keyboard, the highlighted keys corresponding to selected symbols of the set of symbols.

3. The method of claim 2 wherein the model is a decision tree.

4. A keyboard wherein keys are arranged according to the method of claim 1, and a predetermined number of predicted keys are highlighted.

5. The keyboard of claim 4 wherein a most likely completion of a particular input symbol sequence is displayed.

6. The method of claim 1 wherein the cost function is expressed as:

$\underset{G}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>d^n<br><br>f+\mathrm{cD}$

where dⁿ is a distance between a subset of G keys on the keyboard raised to an n^th power, and f is a relative frequency with which a corresponding subset of symbols follow each other in the training corpus, and D is secondary work load term having a weight c.

7. The method of claim 6 wherein D is -d_ikf_ijk, where f_ijk is a trigram probability of three successive symbols in the training corpus.

8. The method of claim 6 wherein D is d_ikf_ijk, where f_ijk is a trigram probability of three symbols arranged substantially linearly in the keyboard.

9. The method of claim 1 wherein the cost function is expressed as:

$\underset{G}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>d^n<br><br>f$

where dⁿ is a distance between a subset of G keys on the keyboard raised to an n^th power, and f is a relative frequency with which a corresponding subset of symbols follow each other in the training corpus.

10. The method of claim 9 wherein for n=1, the cost function measures an expected total distance a pointer will travel while inputting the symbols of the training corpus.

11. The method of claim 9 wherein for n>

1, the cost function is biased to reduce the total distance a pointer moves between non-adjacent keys.

12. The method of claim 9 wherein for 0<

n<

1, the cost function is biased to increase a probability that frequently occurring symbol combinations are arranged on adjacent keys.

13. The method of claim 1 further comprising the step of:

annealing while minimizing the cost function.

14. The method of claim 13 wherein the annealing is a deterministic annealing quadratic assignment.

15. The method of claim 13 wherein the annealing is simulated, and the minimizing includes a permutation search.

16. The method of claim 15 wherein a subset of keys are permuted, and wherein the permuted subset of keys is retained when the cost is reduced, and if the cost is increased, then the permuted subset of keys is retained with a probability of e⁻

Δ

C/T, for a cooling positive temperature T.

17. The method of claim 15 wherein the permuting is random.

18. A keyboard wherein keys are arranged according to the method of claim 1.

19. The keyboard of claim 18 wherein each key has a hexagonal shape.

20. The keyboard of claim 18 wherein the keys are movable buttons.

21. The keyboard of claim 18 wherein the size of each key is maximized for a particular number of keys occupying a fixed size area of the keyboard.

22. The keyboard of claim 18 wherein the keys are displayed on a touch sensitive surface.

23. The keyboard of claim 22 wherein the touch sensitive surface includes a first portion for displaying the keys, a second portion for displaying inputted symbols.