One-row keyboard and approximate typing

[0001] This application claims priority to the U.S. provisional patent application No. 60/601,224, entitled Method and Software for Improved Text Entry, filed on Aug. 13, 2004. The entire contents of that provisional application are incorporated herein by reference.

[0002] It is fascinating to reflect on the great impact of the PC on society. The PC is clearly capable of doing a whole lot more than what we use it for. Essentially, for many the PC became a replacement for the typewriter, and it is still largely a word processor. The other initial application that drove PC adoption was the spreadsheet. Then it also became a presentation creation tool. Over time, email was introduced and, even more recently, Web browsing. Web browsing, in turn, is giving rise to online shopping and replacing encyclopedias as our primary information resource. But, overall, there are still very few uses for these powerful machines by the average user.

[0003] We are now going through a phase where the capabilities of different types of devices are converging. Devices rely on common protocols and are often connected via the Internet, and the services offered are becoming more portable and accessible wherever we are and whenever we need them. We now have PCs, cellphones, TVs, iPods, PDAs, and camera phones relying on the Internet, complemented by communication networks such as the cellular networks, Bluetooth, and Wi-Fi. Services range from unified messaging and VOIP to entertainment.

[0004] With these trends toward greater connectedness and mobility, perhaps the most central roblem is how to make text entry possible on small, portable devices. The success of email, MS, and instant messaging on portable devices and user patterns already established on the PC make an efficient text-entry system a must for broad adoption of smaller, mobile devices.

[0005] In this direction, the RIM pagers (the Blackberry devices) are prime examples of a well-designed portable device. It is simply an excellent email machine, and for many this immediate access to email becomes highly addictive. A great deal of the success of this type of device relies on its small keyboard, which allows for two-thumb typing. This typing is quick and easy to learn since it relies on the same basic organization as the regular typewriter/PC keyboard.

[0006] For cellphones there is the T9 method by Tegic (U.S. Pat. No. 5,818,437 and other pending patents; T9 text input software Copyright 1999-2002; Tegic Communications, Inc.); cf. [22], [23].

[0007] For PDAs, the preferred method for text entry seems to be using a touch screen combined with “graffiti” entered using a stylus or tapping a keyboard with the stylus. Recognition of handwriting is also widely used.

[0008] A solution to the text entry problem for small portable devices should ideally address the following capabilities:

• • [0009] support touch-typing and rapid text entry;
  • [0010] easy-to-learn and consistent with standard keyboards;
  • [0011] easily extensible to include new words and new contexts;
  • [0012] small enough for portability and easy integration with mobile devices;
  • [0013] easy corrections of typos and minor mistakes; and
  • [0014] support auto-completion.

[0015] These goals are addressed by the invention described herein.

[0016] In one aspect, the invention comprises an apparatus for character entry on an electronic device, comprising: a keyboard with one row of keys; and an electronic display device in communication with the keyboard; wherein one or more keys on the keyboard has a correspondence with a plurality of characters, and wherein the correspondence enables QWERTY-based typing.

[0017] In another aspect, the invention comprises an apparatus for character entry on an electronic device, comprising: a keyboard with a plurality of keys; and an electronic display device in communication with the keyboard; wherein one or more keys on the keyboard has a correspondence with a plurality of characters, and wherein, for each of the one or more keys, the plurality of characters comprises: (a) a home row character associated with a particular finger when touch typing; and (b) a non-home-row character associated with the particular finger when touch typing.

[0018] In various embodiments: (1) the apparatus is operable to apply natural language processing and approximate typing algorithms to increase accuracy of recognition and display of typed words and other valid character combinations; (2) the apparatus is operable to apply natural language processing and approximate typing algorithms to reduce average typing ambiguity by more than 5% over T9; (3) the apparatus is operable to identify words and other valid character combinations typed by users based on modeling character and symbol combinations as paths on N-ary trees; (4) the apparatus is operable to identify words and other valid character combinations typed by users based on a dictionary modeled as a set of valid paths on an N-ary tree; (5) the apparatus is operable to identify words and other valid character combinations typed by a user based on a signature dictionary; (6) the apparatus is operable to: receive ambiguous keyboard input; disambiguate the input; and provide predictions based on the input; (7) the predictions are based on identifying a maximum likelihood of a word or other valid character combinations intended to be typed; and (8) the maximum likelihood is identified based on calculating one or more products of probabilities, wherein each of the products comprises: a probability of a character combination, given an intended signature; and a probability for a signature being the intended one, given actual input; (9) the apparatus is operable to display a likely valid character combination based on keystrokes entered by a user; (10) the likely valid character combination is identified based at least in part on parts of speech classification; (11) the likely valid character combination is identified based at least in part on context-based disambiguation; (12) the likely valid character combination is identified based at least in part on natural language processing techniques; (13) the likely valid character combination is identified based at least in part on ordering with respect to one or more cost functions; (14) the likely valid character combination is identified based at least in part on autocompletion and auto-correction software; and (15) the keyboard is a virtual keyboard displayed on the display device.

[0019] In another aspect, the invention comprises an apparatus for character entry on an electronic device, comprising: a keyboard with a plurality of keys; and an electronic display device in communication with the keyboard; wherein each of one or more keys represents an equivalence class of characters, and wherein characters are assigned to equivalence classes according to touch typing assignments to fingers.

[0020] In various embodiments: (1) the apparatus is operable to identify typed words and other valid character combinations based on approximate typing algorithms comprising pattern recognition algorithms; (2) the apparatus is operable to identify typed words and other valid character combinations based on one or more cost functions, similarity measures, probability models, or combinations thereof that measure how well typed character sequences approximate intended character sequences; and (3) at least one cost function is based on an edit distance that provides a coarse model of a user's typing and errors.

[0021] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, and wherein the output signals are determined based on approximate typing algorithms comprising pattern recognition algorithms.

[0022] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, and wherein the output signals are determined based on one or more cost functions, similarity measures, probability models, or combinations thereof that measure how well input character sequences approximate intended character sequences.

[0023] In one embodiment, at least one cost function is based on an edit distance that provides a coarse model of a user's input process and errors.

[0024] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, wherein the output signals include a likely valid character combination, and wherein the likely valid character combination is identified based at least in part on parts of speech classification.

[0025] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, wherein the output signals include a likely valid character combination, and wherein the likely valid character combination is identified based at least in part on context-based disambiguation.

[0026] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, wherein the output signals include a likely valid character combination, and wherein the likely valid character combination is identified based at least in part on natural language processing techniques.

[0027] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, wherein the output signals include a likely valid character combination, and wherein the likely valid character combination is identified based at least in part on ordering with respect to one or more cost functions.

[0028] In another aspect, the invention comprises a method for disambiguation of human input for text entry, comprising: receiving a plurality of discrete input signals; and dynamically mapping the input signals to output signals; wherein one or more of the input signals represents an equivalence class of characters, wherein the output signals include a likely valid character combination, and wherein the likely valid character combination is identified based at least in part on auto-completion and auto-correction software.

[0029] A solution to the text entry problem for small portable devices should ideally address the following capabilities:

• • [0030] support touch-typing and rapid text entry;
  • [0031] easy-to-learn and consistent with standard keyboards;
  • [0032] easily extensible to include new words and new contexts;
  • [0033] small enough for portability and easy integration with mobile devices;
  • [0034] easy corrections of typos and minor mistakes; and
  • [0035] support auto-completion.

[0036] The One-Row Keyboard (ORK) is a solution to this problem. Here are some of the key components of this solution, how each contributes to the solution, and how these are different than the commonly used T9.

• • [0037] 1. The ORK uses a mapping of the standard QWERTY keyboard onto a small set of keys in such a way that the user's previous experience and training with the QWERTY keyboard can be re-used. In particular, this mapping allows for rapid touch-typing of regular text (including both letters and punctuation marks), using all fingers, with virtually no additional training. Difference from T9: T9 requires a slow entry process that is not consistent with the QWERTY keyboard. In particular, the T9 input process is hard to learn, the typing speed is slow, a careful aim must be used for the few fingers utilized, and touch-typing is not supported. Hence, the input process requires considerable attention.
  • [0038] 2. Both ORK and T9 use a smaller set of keys than the regular QWERTY keyboard. Hence, a certain set of keystrokes on either one may not have a unique interpretation in terms of regular letters or words. In such cases, the user may have to choose among alternatives, which requires attention and interrupts typing flow. The ORK is optimized to reduce this ambiguity in several ways:
    • [0039] (a) Without extra optimization, the ORK creates about 2-3 times less ambiguity than T9.
    • [0040] (b) The ORK integrates the punctuation marks into the predictive typing.
    • [0041] (c) Using Natural Language Processing (NLP) techniques, the ambiguity, and hence user attention, is reduced further. (These techniques can also be used to improve T9's performance.)
    • [0042] (d) As data is input, changes occur on the screen. If such changes are not consistent with user expectation, this may cause user distraction. The ORK uses algorithms to smooth the changes on the screen.
    • [0043] (e) The ORK uses a Beginning Of Word (BOW) organization of the dictionary to display the character combinations that will result in little change on the screen.

[0044] Difference from T9: T9 uses a linked tree structure. (These techniques can also be used to improve T9's performance.)

• • • [0045] (f) The ORK also uses cost functions for the display process that increase the cost for changes on the screen. Hence, by minimizing these cost functions, a smoother display results. (These techniques can also be used to improve T9's performance.)
    • [0046] (g) Another reason for interruption of the user's typing flow is the occasional need to add new entries to the dictionary. T9 uses a “spell mode” for this: when a character combination is not recognized, the user is asked to start from the beginning and enter the word unambiguously using multi-tap. This is quite frustrating for the user and is a serious interruption in the entry process. ORK uses a simplified spell mode. This simplification re-uses the information the user has already entered and, hence, only a small amount of extra information is necessary to uniquely identify the new word. The interface for the input of this extra information also requires much less attention on behalf of the user. (These techniques can also be used to improve T9's performance.)
    • [0047] (h) Another significant cause of user interruption is typing errors and other incorrect entries. Because of the ambiguity created by reduced keyboards, such errors are harder to fix. The ORK allows the user to use “approximate typing.” The reduced keyboard entry process is integrated with a correction process, which can either be automatic or designed to minimize user intervention. The correction process is based on statistical techniques used by NLP, voice recognition and speech processing, as well as machine translation. (These techniques can also be used to improve T9's performance.)
  • [0048] 3. The ORK uses both the NLP and approximate typing techniques to improve the auto-completion capability. This allows the user to enter only part of a word or character combination, and when a reasonable prediction of the remaining characters have been obtained, these characters are entered or presented to the user for possible acceptance. (These techniques can also be used to improve T9's performance.)
  • [0049] 4. The ORK also reduces the need for user attention and supports the uninterrupted typing process by allowing a combination of ambiguous and non-ambiguous typing. This allows the entry of symbols and numbers to be integrated with prediction based on the entered letters and punctuation marks.

[0065] 1 A Preferred Embodiment of the Present Invention Comprises the One-row Keyboard.

1.1 The Basic Set-up

[0066] A regular “QWERTY” keyboard consists of the letters of the alphabet in lower case and then an additional set of characters and control keys. To be specific, we shall assume that the “regular” keyboard for touch-typing consists of 30 symbols arranged in three rows:

• [0067] Row 1 qwert yuiop
• [0068] Row 2 asdfg hjkl;
• [0069] Row 3 zxcvb nm,./
  It will be convenient to assign a specific number α, 1≦α≦30, to each of the letters and symbols of this regular keyboard. Starting with the upper left and going row-wise, the letters on the first row obtain numbers α with 1≦α≦10, and so on. For example, the letter v is assigned the number α=α(v)=24. We also assign the space character (used when we reach the end of a word, for instance) the number α=0.

[0070] For the One-Row Keyboard(ORK), we collapse these symbols into one row by grouping three symbols, one from each row, into a single group; see FIG. 1 and FIGS. 15-30. Each one of these groups then corresponds to one key on the One-Row Keyboard: the first key on the One-Row Keyboard corresponds to {qaz}, the second to {wsx}, etc. The One-Row Keyboard thus has ten keys:

• [0071] One-row, left: {qaz}, {wsx}, {edc}, {rfv}, {tgb}
• [0072] One-row, right: {yhn}, {ujm}, {ik, }, {ol.}, {p;/}
  Just as in the case of the regular keyboard, various additional keys, extra symbols, and commands may be added to the One-Row Keyboard. Perhaps the most notable of these is the space bar.

[0073] The One-Row Keyboard still allows the user to touch-type: for each letter of a specific word, the key corresponding to the group of letters containing the letter is typed. In this way, the signature corresponding to the word is typed, rather than the word.

[0074] Suppose we identify each of the keys of the basic One-Row Keyboard with a number σ, 1≦σ≦10, starting from left and going to the right. So, for example, each of the three letters r, f and v corresponds to the number α=σ(r)=α(f)=σ(v)=4. As for regular keys, we also add the space character as σ=0. Now, with this convention, the signature of a word with N letters becomes a sequence of non-zero numbers σ₁σ₂ . . . σ_N.

[0075] Similarly, suppose we identify the row of the regular keyboard to which a letter belongs by a number τ, 1≦τ≦3, starting with the top row. For example, since the letter i belongs to the top row of the regular keyboard, it has τ=τ(i)=1. The dual signature of a word is the sequence of these τ's, one for each letter. A word with N letters thus has a dual signature which is a sequence of numbers τ₁τ₂ . . . τ_N. Again, it is convenient to have τ=0 correspond to the “space” symbol.

[0076] Each specific letter can thus be specified exactly either through the number α or through the pair σ, τ. More generally, an N-letter word w is specified exactly through the sequence
α=α(w)=α₁α₂ . . . α_N,  (1)
or, alternatively, through the signature
σ=σ(w)=σ₁σ₂ . . . σ_N  (2)
and the dual signature
τ=τ(w)=τ₁τ₂ . . . τ_N.  (3)
As we use the One-Row Keyboard to type in the sequence of a word, we lose (exactly) the information in the word's dual signature.

[0077] There is another type of representation of the sequences α,σ, and τ that is also useful. Let us assume that we have a 31-ary infinite tree A=A₃₀, starting from the root and with each node having 31 children. As above, each given word w can be identified with a sequence α=α(w), and now we can identify α in turn with a path α₁α₂ . . . α_N in this tree: starting from the root, the value of α₁ means that on the first level (below the root) the node corresponding to the value α₁ is traversed, and then on the next level, level 2, the node corresponding to the value α₂ is traversed, etc. The path of a N letter word thus has N+1 levels if we count the root level. (Whenever convenient, we may also add a space symbol, or several, to the end of the sequence; in that case, the path involves additional levels.)

[0078] Similarly, the signature σ=σ(w) of word w with N letters can be identified with a path of length N+1 in a 11-ary tree, with 11 choices on each level. The dual signature τ=τ(w) is a path in a 4-ary tree.

[0079] Clearly, very few of the possible paths in these trees correspond to real words, signatures, and dual signatures, respectively.

[0080] The 31-ary tree, used for the words and sequences α, factors precisely into the two trees for the signatures σ and dual signatures τ.

[0081] We can also visualize each sequence a and its corresponding α, τ as a path through the infinite block in FIG. 2 (note that only four levels are shown): on the first level, the unique block with “coordinates” (σ₁, τ₁) is traversed, on the second (σ₂, τ₂), etc. The signatures, and hence what the ten keys of the One-Row Keyboard produce, is obtained by the projection of the α_i's onto the σ_i's and ignoring the τ_i's.

• [0082] Comment 1.1 Both T9 and the ORK are examples of a reduced keyboard. A reduced key-board R is a collection R={Sⁱ}_i of sets (or equivalence classes) of characters Sⁱ={T_jⁱ}_j of letters and symbols. The entire collection {T_jⁱ}_i,j is the alphabet of the keyboard R. With a physical implementation of the reduced keyboard R, we associate each S_i with a key, a location on the screen, or in any other manner through which the user can select the intended set. We have used the notation σ_i to identify this input, and this is the signature corresponding to the equivalence class in question. The dual signature is intended to exactly capture the remaining information necessary to pinpoint a character in the alphabet. If we are given a character T_jⁱ, and we already know that its signature is σ_i (and hence we know S_i), then the dual signature will contain the extra information to obtain T_jⁱ. For example, we may list the elements in the equivalence class Sⁱ, and then, by giving a number to each of the elements in this list, we may identify the exact character T_jⁱ by this number. This is then the dual signature τ_j; the character T_jⁱ, is identified with the pair τ_i, τ_j.

[0083] This representation of an alphabet in terms of signature and dual signature has many benefits. One is a simplified approach to spelling a word or, more generally, identifying a legal character combination for a reduced keyboard; see below. The representation also simplifies the quantitative treatment and analysis of reduced keyboards.

• [0084] Comment 1.2 There is an immediate extension of the “signature, dual signature” representation to higher dimensions: a unique object is identified by the n+1-tuple (τ⁰, τ¹, . . . , τⁿ). (With n=1 and τ⁰=σ, τ¹=τ we are back to the “signature, dual signature”.) If we require that there is a subordination among the tau's, say τ⁰→T¹→ . . . τⁿ, then we have a tree structure. The object corresponding to a specific n+1-tuple (τ₀, τ₁, . . . , τ_n) is identified by the path {τ⁰=τ₀}→{τ¹=τ₁}→ . . . {τⁿ=τ_n}. This points out that in certain circumstances, as in the case of menu systems, the objects in these representations may not be characters (for menus, they are “files” and “folders”).
  1.2 Dictionaries for Words, Signatures, and Dual Signatures

[0085] Most paths α in the global 31-ary word tree do not correspond to valid words in English (if that is the language we are trying to type). This is immediately clear just by looking at the number of possible combinations. Suppose we consider words with at most six letters. Ignoring the “space” symbol at the end of words, there are 30⁶=729 million possible paths using six levels (or seven including the root) in the tree. This number should be compared to the approximately 300 words that correspond to 60 percent of all the printed text or to the approximately 10 words that correspond to 25 percent of the printed text. Hence, we only use one in about 2.4 million of the possible paths 60 percent of the time. Some paths we thus travel often, and most we do not travel at all.

[0086] A dictionary is one way to identify this small subset of valid paths. Initially, this is a useful way to view the dictionary: it is the collection of valid paths. Later we shall worry about the size of the dictionary, and then it becomes of interest to avoid some repetitions and not to include standard modifications of basic words (like adding “s” for the plural of a noun, etc.). We shall use the notation D for the particular dictionary we use. The standard way of organizing D is alphabetically, and when we use this we shall use the subscript w: D_w.

[0087] There are several other views that are useful as well. For example, we may instead consider D as consisting of the sequences α corresponding to valid key combinations. We order these sequences as if the sequences represented a fractional 31-ary expansion, in increasing order. In other words, the word w with α(w)=α₁α₂ . . . thus corresponds to the number 0.α₁α₂ . . . , and these fractional expansions, corresponding to valid words, are entered in ascending order. (With any number of spaces added to the end of the a sequence, we identify the same word and the same fractional expansion.) This view of the dictionary is indicated by the subscript α: D_α. The ordering between the sequences makes it possible to compare two sequences α¹, α²∈D_α: we say that
α¹<_αα²  (4)
if the sequence α¹ comes before α² in D_α, i.e. if
0.α₁¹α₂¹α₃¹ . . . <0.α₁²α₂²α₃²  (5)

[0088] Not all signatures a correspond to words either, and some It's correspond to more than one word. The collection of valid σ's, each entered only once, is called the signature dictionary and is denoted by S. The signature dictionary S can also be viewed in different ways. When we view it in a way analogous to D_α, then we use the notation S_σ. More explicitly, each σ=σ₁σ₂ . . . , corresponding to one or more words, is identified with the 11-ary fractional expansion 0.σ₁σ₂ . . . , and these are entered in an ascending order into S_σ. This ordering is denoted by <_σ. The unique dual signatures are collected in the dual signature dictionary T, and one view of T is T_τ, defined in the obvious, analogous way. The notation for this ordering is <_τ.

[0089] With the orderings <_σ and <_τ in S_τ and T_τ, respectively, we may define several additiona views of D. If we have two words w¹, w²∈D with corresponding signatures and dual signatures (σ¹, τ¹), (σ², τ²), then

[0090] $\begin{array}{cc}\left({\sigma }^1,{\tau }^1\right){<}_{\sigma ,\tau }\left({\sigma }^2,{\tau }^2\right)⟺\{\begin{array}{c}{\sigma }^1{<}_{\sigma }{\sigma }^2\\ {\sigma }^1={\sigma }^2\mathrm{and}{\tau }^1{<}_{\tau }{\tau }^2.\end{array}& \left(6\right)\end{array}$
We shall write D_σ,τ for D with this ordering. We may also write D=S_σ(T_τ) to indicate this ordering. If we switch the two orderings and instead start by ordering with respect to the dual signatures, then we similarly have the ordering <_τ,σ and this gives us the view D_τ,σ=T_τ(S_σ).

[0091] For us probably the view that is most interesting is the following. It is based on interleaving the signature and dual signature sequences. More specifically, if w∈D has the signaure σ=σ₁σ₂ . . . and the dual signature τ=τ₁τ₂ . . . , then we form the expansion 0.σ₁τ₁σ₂τ₂ . . . . This is the basis for the order <_σ×τ: words are identified with their interleaved expansions and entered into D in ascending order. To indicate this view, we write D_σ×τ. Of course, there is similarly an ordering <_τ×σ, and the view using this is D_τ×σ.

[0092] Let us illustrate with a small dictionary.

[0093] Suppose we have a word dictionary D^tiny=D_w^tiny containing the ten words, alphabetically ordered, “and”, “cat”, “do”, “go”, “is”, “it”, “say,” “the”, “to”, and “way”. The corresponding a sequences and signatures and dual signatures are the ones in Table 1. Some of the different orderings of these words are given in Table 2.

[0094] Obviously, the different views of the dictionary do not correspond very closely to how our brains store words. The intent is to make it easier to find the word as we type using the regular keyboard or the One-Row Keyboard. How our brains have the information stored is complicated, but it is probably true that the beginning letter of the word is very important as well as the length of the word; see [18].

[0095]

TABLE 1
Dtiny and associated sequences in alphabetical order.
	Word	α	σ	τ
	and	11 26 13	1 6 3	2 3 2
	cat	23 11 05	3 1 5	3 2 1
	do	13 08	3 9	2 1
	go	15 09	5 9	2 1
	is	08 12	8 2	1 2
	it	08 05	8 5	1 1
	say	12 11 06	2 1 6	2 2 1
	the	05 16 03	5 6 3	1 2 1
	to	05 09	5 9	1 1
	way	02 11 06	2 1 6	1 2 1

[0096]

TABLE 2
Dtiny in increasing <α order (left), increasing <σ,τ
order (center), and increasing <σ×τ order (right).
	Word	α	σ	τ
	way	02 11 06	2 1 6	1 2 1
	to	05 09	5 9	1 1
	the	05 16 03	5 6 3	1 2 1
	it	08 05	8 5	1 1
	is	08 12	8 2	1 2
	and	11 26 13	1 6 3	2 3 2
	say	12 11 06	2 1 6	2 2 1
	do	13 08	3 9	2 1
	go	15 09	5 9	2 1
	cat	23 11 05	3 1 5	3 2 1
	and	11 26 13	1 6 3	2 3 2
	way	02 11 06	2 1 6	1 2 1
	say	12 11 06	2 1 6	2 2 1
	cat	23 11 05	3 1 5	3 2 1
	do	13 08	3 9	2 1
	the	05 16 03	5 6 3	1 2 1
	to	05 09	5 9	1 1
	go	15 09	5 9	2 1
	is	08 12	8 2	1 2
	it	08 05	8 5	1 1
	and	11 26 13	1 6 3	2 3 2
	way	02 11 06	2 1 6	1 2 1
	say	12 11 06	2 1 6	2 2 1
	do	13 08	3 9	2 1
	cat	23 11 05	3 1 5	3 2 1
	the	05 16 03	5 6 3	1 2 1
	to	05 09	5 9	1 1
	go	15 09	5 9	2 1
	is	08 12	8 2	1 2
	it	08 05	8 5	1 1

1.3 Exploiting Sparsity

[0097] Very few paths in the different dictionaries are used, and this sparsity can be exploited in several ways. With the One-Row Keyboard, we only supply the signature of the word; however, in most cases this reduced information is sufficient to uniquely identify not just the exact signature but also the exact word in the dictionary. In relatively few cases, however, there are several words with the same signature.

[0098] This sparsity also means that after a few keystrokes using a regular keyboard, a word can be identified without having to type in the remaining letters. The rest can then be added automatically, without typing. This “auto-completion” can also be taken advantage of when we use the One-Row Keyboard and the signature of the word. Of course, we expect to type more keystrokes before the exact signature has been pinpointed. Very often, however, the great sparsity in the signature dictionary means that we will have identified a unique signature before reaching the signature's end.

[0099] Then, if we decide to use these dictionaries to look up what a typed signature corresponds to, there are several questions that arise. For example:

• • [0100] 1. How do we provide feedback to the user concerning the progress of the typing process?
  • [0101] 2. How do we report and correct typing mistakes?
  • [0102] 3. How do we best resolve ambiguities between words with similar signatures?
  • [0103] 4. How do we best support auto-completion?
  • [0104] 5. How do we automatically fix typos?
  • [0105] 6. How do we quickly look up signatures, dual signatures, and words?
  • [0106] 7. What makes a good dictionary?
  • [0107] 8. How do we add words to a dictionary?
  • [0108] 9. How do we customize dictionaries depending on contexts and on the user?
    We address these in the next discussion below.
    1.4 Reaching Beyond the Dictionaries

[0109] Punctuation marks and other standard symbols form an important part of written text. For a fast and seamless typing experience, it is essential that such characters can be typed in the same manner as letters, without a break in the typing flow. If one needs to bring up a special punctuation/character menu from which the correct mark can be selected, then delays are induced and loss of typing flow results.

[0110] Further, with respect to the QWERTY (or equivalent) keyboards that have common punctuation marks and extra characters adjacent to the letter keys, the experienced user already has an established pattern and existing “wiring” for such keys. To capitalize on the familiarity of this pre-wiring, for improved typing speed and ease of learning, a reduced keyboard may place such characters in more or less the same relative location as the standard QWERTY keyboard. For a preferred embodiment of the ORK, where we collapse the three rows into one, this translates into, for example, placing the period on the same key as O and L (or, more precisely, in the same equivalence class). The disambiguation engine then has to carry out the disambiguation such that an equivalence class may contain both letters used in the dictionary as well as other additional symbols. This can be achieved in several ways. One is to utilize a set of rules to create varied disambiguation results from pre-existing dictionary entries or other intermediate disambiguation results. Note that the application of such rules may be nested.

[0111] Here are a couple of specific instances of such possible rules:

[0112] Append a punctuation (such as : ; , ? ! or .) at the end of an entry so as to generate a match to the complete entered signature. For instance, the signature 6920 may be disambiguated as “How?” (Note how this further uses the Shift key to differentiate among a set of signatures: We use Shift to distinguish ? and ' from each other, just as we use Shift to distinguish ‘H’ from ‘h’. For this example, we have made the assumption that ' replaces/on the QWERTY keyboard.)

[0113] In the same manner, 0069200 may be disambiguated as “how” if we assume that two consecutive instances of a single quote are to be taken as a double quote. Note that the opening and closing double quotes may be disambiguated independently of each other so that the double quotes may apply to words as well as to sentences. (This assumes that ' replaces/on the QWERTY keyboard.)

[0114] As an example of nesting, the sequence 00692000 may be disambiguated as “How?”.

[0115] For reduced keyboards it is thus quite beneficial to support extended character sets. The legal character combinations are then not just those found in dictionaries, but also include combinations of a predefined set of legal combinations (as, for instance, given by a collection of dictionaries) with sets of other symbols. In terms of notations used in Section 1, we may include the extended set of characters as separate dual signatures corresponding to existing signatures, or we may extend the signature set as well. In the former case, we may then end up with keys as in the examples above, where there is a mixture of letters and symbols occuring in the dictionary together with symbols from the extended sets. In the latter case, for those extended characters that are assigned new signature(s), we can identify these as part of the extended character sets, and the treatment of such characters is simpler. For example, the standard solution for including symbols in the context of reduced keyboards is to put the extra symbols on separate keys (i.e., separate signatures) and then require an explicit choice of the symbol (i.e., specifying the dual signature), and then the choice of character is unique. In that particular case, what we add here is only to allow for predictive techniques to be used for symbols outside the set of legal combinations as prescribed by dictionaries.

[0116] Similarly, it is possible to extend the entire class of valid character combinations outside the combinations defined by each dictionary and specific sets of characters. For example, one dictionary may contain the constituent words of character combinations, and legal combinations are obtained by these words combined according to specific rules. If the simple dictionary consists of three words {print, queue, driver}, and it is agreed that words in this dictionary can be combined with the underline symbol ‘_’, and still obtain a legal combination, then we see that combinations like print_queue, print_driver, etc., are valid. In general, a set of dictionaries and a set of character sets can be combined, using specific rules, to obtain an extended set of legal combinations.

[0117] A spell procedure is a standard aspect of a reduced keyboard. If a particular signature sequence is entered, and it cannot be found in the dictionary, the spell procedure allows the user to provide the extra information to identify a new legal character combination (and possibly add this combination to the dictionary). The standard spell procedure, used by T9, for example, is to use a separate process if the signature is not found. In the case of T9, this is usually done through “multitap”: the key corresponding to the equivalance class of letters is typed repeatedly, and each letter in the class is uniquely associated with a specific number of taps. For example, for the standard cellphone implementation of T9, the number “2” corresponds to the letters “abc”, and one press on “2” then identifies “a”, two presses on “2” is “b”, and three is “c”. In terms of the representation using signature and dual signature, we may identify the number of key presses with the dual signature. With this, the letter “c”, say, is given by (2, 3) (sits on the key “2” and requires “3” presses). The “number of key presses” may then be specified independently of the signature, using other keys or in any other manner that allows the user to indicate his choice of the dual signatures. In case the signature has already been entered, for example, only the dual signatures then need to be provided. To spell the word “act”, for instance, we may press the keys “2”, “2”, and “8” to specify the signature. To now identify “act” among all the possible combinations with this signature, we may identify the sequence “1”, “3”, and “1” in some fashion. In this case, we may, for instance, have the keys for dual signatures “1”, “2”, “3”, and “4” separate from the signature keys, and then the dual signatures can be provided at other times during the input process, not just after the signature has been entered.

[0118] More generally, for any reduced keyboard, the dual signatures can be entered independently of the signatures. Hence, if the signatures have been entered, the dual signatures can all be entered by allowing the user to identify the possible dual signatures one by one. If there is only one possibility for the dual signature, then that choice may be omitted. Additionally, the order in which the dual signatures are entered is also flexible; often we assume that the entry process goes in some predetermined order (typically from left to right or the other way around), but this is not necessary.

[0119] Further, different prediction techniques can be used to simplify the required user interaction as the spell process proceeds.

[0120] Notice that the independence of signature and dual signature is what allows the same key to be reused for specifying the dual signature once the signature is given. For example, by overloading “up/down” to pinpoint the dual signature in a list of possible interpretations, for each of the signature entries, is an example of the “signature, dual signature” representation of a character.

• [0121] Comment 1.3 In the following discussion, we will describe various methods of carrying out various operations on a set of dictionary entries, sometimes utilizing the user feedback and input in the process. These methods will have as output possibly a second set of entries and, hence, are equivalent to mapping one set of entries onto another. More importantly, these methods can be used in stages such that the combined output of one or more stages can serve as input for another method. Various arrangements are possible of such combined mappings. For instance, punctuated endings from original dictionary entries may serve as input entries for an approximate typing stage which takes into account user typing errors. Thus, it is important to realize that when we talk of dictionary entries henceforth, these should be understood not only as the original dictionary entries, but also as any permutation and combination of a constructed set of entries arising from any of these methods.

[0122] Similarly, in the following, we will refer to duals of a signature sequence as valid alternatives. It is important to realize that these valid alternatives may actually be a result of an approximate matching process or a rule-based dictionary mapping or for that matter any mapping produced by such a method. Thus, these duals that we refer to may not be exact duals of the entered or dictionary entry signatures, but simply a mapping. A specific instance we will discuss later, is how a set of auto-completion alternatives may be generated for each of the valid duals of an entered signature sequence that is being typed. In that case, the valid dual may actually arise from the approximate matching method and thus may not be an exact dual of the signature entered by the user.

[0123] 2 Approximate Typing

2.1 User Input and Reduced Keyboards

[0124] One of the drawbacks of using a reduced keyboard is the fact that when the user has entered a set of keystrokes and the feedback from the device does not coincide with the user's intentions, it is often hard to identify the underlying reason. Sometimes the unexpected behavior is a consequence of the intended character combination not being in a dictionary. Probably much more frequently, however, the explanation is a typing mistake. It is often hard for the user to decide exactly at what point a mistake was made since the entered key sequence is not in one-to-one correspondence with a character sequence. Rather than trying to understand where the error occurred, the user then often ends up erasing the entire combination and starting again. This is particularly frustrating when the input sequence is long, and, unfortunately, this is also when typing errors frequently occur.

[0125] A similar problem is encountered when the user is not quite sure how to spell a certain word or only knows parts of the word or character combination.With a standard keyboard, one way to handle such a situation is to enter an approximation of the intended word, and the meaning is still likely to be communicated to the reader. With a reduced keyboard, this approach is rarely available since the character combination on the screen is typically quite different than that of the intended word. To remedy this, the user may then try to experiment with different potential spellings to reach the correct one, and, if he fails, he may experience not just a sense of interruption of typing flow, but of actually being stuck. This is a serious drawback of any reduced keyboard and should be addressed.

[0126] In the following, we consider the case when the input from the user is not quite correct or at least the entered signature sequence is not matching that of the word the user intended. The basic assumption we shall make is that the entered signature sequence is approximately correct and, hence, there is a similarity between the intended signature sequence and the one entered.

[0127] The user intends to input a sequence of words (or other character combinations) w_i, i=0, . . . , N, often collected in a sentence s:
s=w₀w₁ . . . w_N.  (7)

[0128] (What constitutes the appropriate delimiter for the different character combinations w_i and for the sentences s is of no real significance for the current discussion.) Using a reduced keyboard R (see Comment 1.1 above), the user provides input to the system, and based on this input, the system provides feedback to the user; see FIG. 3. In the case of a reduced keyboard, the input is typically ambiguous, so part of the task for the system is to disambiguate the different interpretations and provide possible predictions based on the user input. The user can then provide more input to the system by selecting between different possibilities for the character combination wi under consideration.

[0129] The user input is of course assumed to be a reflection of the user's intentions. For a reduced keyboard, the normal assumption is that the signature is the correct one; however, if we add the complication that the user may have mistyped, then the signature sequence may not be the intended or desired one and, hence, the system cannot rely on the accuracy of the signature for its predictions.

[0130] The signature will still serve as an important indication of the user's intent, but the ambiguity may increase if we allow the user to only provide an approximation of the intended input.

[0131] More specifically, in the case of a reduced keyboard, each keystroke by the user represents an equivalence class of unique characters. Hence, with a certain sequence of keystrokes, a unique set of character combinations, consistent with the equivalence classes of each key, is generated. Let us call this set of character combinations the “input set.” The reduced keyboard then works with a disambiguation process to prioritize among the character combinations in the input set in order to provide the user with feedback for possible further interaction.

[0132] In the case of approximate typing on a reduced keyboard, the user's keystrokes generate a larger class of possible character combinations and the disambiguation process operates on this larger class. For example, besides the input set of character combinations corresponding to the exact keystrokes, there may be other possible keystrokes, each with its own set of character combinations, that enter into the disambiguation process, and different rules and methods may be used by the disambiguation process for determining how all of these should be weighed. The regular approach for typing on a reduced keyboard is when only one set of character combinations (the input set) enters into the disambiguation process, and, at the opposite end of the spectrum, we have the situation when the disambiguation process uses all possible keystrokes and weighs these based on the actual user input.

2.2 A Probabilistic Analysis

[0133] To illustrate some of the issues involved and to gain some further insights into effective disambiguation processes for approximate typing on reduced keyboards, we shall consider a maximum likelihood approach.

[0134] Let us for now consider just the single character combination w in isolation and ignore that some of the probabilistic information may be obtained from context and other parts of this or other sentences. It will be convenient to simplify the discussion to a real-time, on-the-fly type of processing where there is a specified order, say left to right. We assume further that the user has in mind the character combination v=c₀ . . . c_I, and, in the process of entering input corresponding to this target, he enters certain keystrokes. The user's actual keystrokes correspond to the signature σ^a=σ₀^a . . . σ_J^a, and his target signature is σ^v=σ₀^v . . . σ_I^v. (Notice, in particular, that the number J+1 of actual keystrokes may not be the same as the the intended number I.)

[0135] From a maximum likelihood point of view, we are interested in finding the best solution
{circumflex over (v)}=arg max_v Prob(v|σ^a),  (8)
where the maximum is takeh over all the intended words v. More generally, we may also consider the N-best solutions
{right arrow over (v)}={right arrow over (v)}^(N)=N-arg max_v Prob(v|σ^a).  (9)

[0136] In order to solve (8) (the same argument applies to (9)), we notice that by the definition of conditional probability and since the keystrokes actually entered do not change, the right-hand side equals

[0137] $\begin{array}{cc}\arg {\max }_{\upsilon }\mathrm{Prob}\left(\upsilon ❘{\sigma }^a\right)=\arg {\max }_{\upsilon }\mathrm{Prob}\left(\upsilon ,{\sigma }^a\right)=\arg {\max }_{\upsilon }\mathrm{Prob}\left(\upsilon ,{\sigma }^{\upsilon },{\sigma }^a\right)=\arg {\max }_u\mathrm{Prob}\left(\upsilon ❘{\sigma }^{\upsilon },{\sigma }^a\right)\mathrm{Prob}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)& \left(10\right)\end{array}$

[0138] It is a reasonable approximation to say that the first factor here, Prob(v|σ^v,σ^a), is independent of σ^a. (In other words, learning the value of σ^a does not provide any additonal information about v once we know σ^v; v and σ^a are conditionally independent given σ^v; cf. [48].) If we accept that, we get
{circumflex over (v)}≈arg max_v Prob(v|σ^v)Prob(σ^v|σ^a)  (11)
(It is easy to come up with examples that suggest that the approximation sometimes is not very precise. Some typing errors are probably more likely to occur for certain specific letter combinations in a group of combinations with the same signature.) This factorization is easy to understand. The first factor corresponds to the maximum likelihood prediction of the regular reduced keyboard, disregarding typing errors. The second factor depends on the probabilities of typing errors as the user keys in a certain signature. For the optimal solution, the product is formed between the probability of a character combination, given an intended signature, and the probability for a signature being the intended one, given the actual input, and then the largest such product is found.

[0139] It is not entirely obvious how to estimate the second factor Prob(σ^v|σ^a) in (11) based on some specific sampling statistics. In contrast, the probability Prob(σ^a|σ^v) is easy to obtain; for example, just start typing the intended word v over and over, and then observe the actual signatures typed. With this in mind, we shall rewrite (11) using Bayes formula:

[0140] $\begin{array}{cc}\mathrm{Prob}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)=\frac{\mathrm{Prob}\left({\sigma }^a❘{\sigma }^{\upsilon }\right)\mathrm{Prob}\left({\sigma }^{\upsilon }\right)}{\mathrm{Prob}\left({\sigma }^a\right)}& \left(12\right)\end{array}$
Inserting this into (11) we find
{circumflex over (v)}≈arg max_v Prob(v|σ^v)Prob(σ^a|σ^v)Prob(σ^v).  (13)

[0141] The signatures of the character combinations “wondr” and “slyer” are the same. Let us call the signature σ^a. Only the latter of these combinations is an English word. Hence, if the user enters this signature σ^a, a disambiguation system based on exact signature entry will display “slyer. ” However, let us look at probabilities:
Prob(wonder)≈6.5·10⁻⁵ Prob(slyer)≦2.7·10⁻⁷  (14)
(These are estimates using Corpus 1 and Corpus 2; there are approximately 240 occurances of “wonder” and no occurrences of “slyer” among the approximately 3.7 million words in these two corpora.) In addition, we notice that it is very easy to misspell “wonder” since the two letters “d” and “e” sit on the same key and the letter “r” is next to them. Hence, the probability is quite high for entering the signature of “wondr”/“slyer” when we intend to enter the signature of “wonder.”

[0142] Let us assume that “wonder” is the only valid character combination corresponding to the signature of that word and similarly for “slyer. ” Then the disambiguation system should favor “wonder” ahead of “slyer” (if it is based on the maximum likelihood estimation and the approximation (11) as long as
Prob(σ^v(1)|σ^a)>Prob(σ^v(2)|σ^a)  (15)
with v⁽¹⁾=wonder and v⁽²⁾=slyer. Equivalently, using (13) instead, this happens exactly when
Prob(σ^a|σ^v(1))Prob(σ^v(1))>Prob(σ^a|σ^v(2))Prob(σ^v(2).  (16)
Since we are assuming that there is only one word with the signature σ^v(1) and one with σ^v(2), by the sampling estimate above we have
Prob(σ^v(1))=Prob(wonder)≈6.5·10⁻⁵ Prob(σ^v(2))=Prob(slyer)≦2.7·10⁻⁷  (17)
Hence, inserting this into the inequality (16), we see that the criterion is essentially
Prob(σ^a|σ^v(1))>Prob(σ^a|σ^v(2))/250.  (18)
In other words, unless the user is approximately 250 times more likely to type the signature of “slyer” correctly compared to his likelihood of entering the signature of “wondr” when he had “wonder” in mind, the disambiguation system should favor “wonder” instead of “slyer”. (In fact, the actual number may be considerably higher than 250 times since there were no occurrences of “slyer” in the corpora while there were 240 occurrences of “wonder”.) For User 1, a small sample experiment indicates that the actual probabilities are
Prob(σ^a|σ^v(1))≈0.05
Prob(σ^a|σ^v(2))≈0.97.  (19)
Hence, we have
Prob(σ^a|σ^v(1))Prob(σ^v(1))≈3.2510⁻⁶
Prob(σ^a|σ^v(2))Prob(σ^v(2))≦2.710⁷.  (20)
So, at least for User 1, it is more than 10 times as likely that he has mistyped “wonder” than intending to type “slyer.”

[0143] This probabilistic analysis makes it clear that we may obtain a significantly better prediction of the user's intentions with an approximate typing system compared with the normal assumption of exact typing. In particular, we may improve the user's overall typing experience. In spite of this, there still may be reasons to assume that the keystrokes exactly reflect the user's intentions. For example, this assumption may result in a lower complexity of the disambiguation system and less expensive searches since the set of valid alternatives is smaller. It may also be hard to find the probabilities for different typing errors: the typing errors may not only be highly dependent on the user, but also the context and the typing speed (transpositions are good examples of errors highly dependent on the speed). And, the user may operate in a mode of making absolutely certain that no typing errors are entered.

[0144] However, a user typing on a reduced keyboard is especially prone to some typing errors. So it may be argued that it is particularly important to allow for approximate typing on these keyboards. If there are drawbacks of an approximate typing system, then there are often different methods to alleviate these. For example, in order to reduce the set of possible interpretations of entered signatures, we may consider a threshold based on probability of occurrence of certain errors or character combinations. A similar thresholding technique is implicitly already built into the typical approaches for “exact typing,” since there is always the possibility that the user enters a character combination that does not correspond to anything generated by the dictionary. (To handle this, the reduced keyboard uses a “spell” mode.)

[0145] There are a number of additional ways to reduce the extra complexity of approximate typing. The disambiguation system may use the basic assumption that the entered signature is correct, and then have an associated set of alternative character combinations consistent with the signature, and then have a second set relying on approximations of the entered signature. This second set can then be used, for instance, if the user indicates with a key press (or some other way) that the first displayed alternatives are insufficient.

[0146] A probabilistic assessment of different alternatives may be unnecessary if we are willing to let the user decide between the alternatives that the disambiguation system generates.

[0147] In other situations, even rather crude estimations are satisfactory for finding character combinations to present to the user. In the case of long words, for example, it is more likely that the entered character combination singles out the intended word with great certainty and that most of the other combinations are quite improbable. Since it is particularly frustrating for the user to enter a large number of characters and then to not obtain the intended word, this case alone means that even a rather crude approximate typing system may have a great impact on the user's experience.

[0148] Approximate typing does not have to rely on probabilistic analysis at all. Fundamentally, approximate typing relies on pattern recognition for its predictions. In this setting, the registered pattern is the actual keystrokes σ^a, and the objective is to find the label σ^v of the intended signature word v. As a consequence there are many different methods that we may use. For example, there are different types of rule-based approaches, neural networks, entropy-based methods, etc., and then combinations of all of these. Next we shall look at a simple way of measuring the similarities of the entered signature with that of other character combinations.

2.3 The Standard Edit Distance

[0149] To measure the similarity between the entered signature and that of other combinations, there are many possible approaches. One is to use different similarity measures. For example, we may introduce a cost function to measure how well the entered sequence approximates the intended sequence. As a special case of this, we may look for different (pseudo-)distance functions with the basic property that an increase in distance corresponds to less similarity. A commonly used distance function or, more precisely, family of distance functions is based on the so-called edit distance.

[0150] The edit distance is typically used with the common alphabet and symbols (including the empty symbol ε); cf. [27], [60], [21]. Here we shall use it with the ORK and with signature sequences. For now, we shall assume that each keystroke on the ORK is identified with a unique number σ=0, . . . 9, and each signature sequence is given by a string
σ=σ₁σ₂ . . . σ_N.  (21)
The empty string is denoted by ε. The basic idea behind the edit distance is to have a set of elementary transformations T={T_i} and a set of costs C={C_i} for applying each one of these. Then the edit distance ed(σ^A,σ^B) from the sequence σ^A to σ^B is the minimal cost of any sequence of transformations, applied one after the other, that transforms σ^A into σ^B. Typically, it is assumed that the overall cost is additive and, hence, is obtained from each of the individual costs by adding them.

[0151] The standard, most basic edit distance uses the transformations insertion (ε→σ, where σ is a symbol in the alphabet used), deletion (σ→ε), and substitution (σ₁→σ₂), and each is assigned a cost of 1. Notice that insertion and deletion are converse to each other, and that insertion has the effect of replacing two consecutive symbols σ₁σ₂ by the triplet σ₁σ₃σ₂ (remember the empty symbol ε is allowed, so this allows us to insert a symbol at the beginning or the end of a string of symbols).

[0152] With the edit distance, the approximate string matching is viewed as an alignment problem. A couple of examples will illustrate this (the examples come from [21]).

[0153] The edit distance from “food” to “money” is at most four. A sequence of transformations is given by
food→mood→mon^d→moned→money
A more instructive way to display this is to put one word on top of the other with a gap in the top one for every insertion and a gap in the bottom one for every deletion. In this way, columns with different symbols correspond to substations, and the number of editing steps and the total editing cost is the number of columns with non-equal entries. For the example above we have

[0154]

	f o o d
	m o n e y

[0155] So, ed(food, money)≦4, and in this case it is not hard to see that it is exactly four. With longer words it is not as clear when we have obtained the optimal set of transformations. For example, here is a more complex situation.

[0156]

	a l g o r i t h m
	a l t r u i s t i c

[0157] Clearly, the ed(algorithm, altruistic)≦6, but it is not obvious whether there is a better set of transformations, with a lower total cost.

[0158] Using the notation from the above example, the key observation in order to efficiently find the optimal set of transformations is the following: if we remove the last column for an optimal set of transformations, the remaining columns must represent the shortest edit sequence for the remaining substrings. Otherwise, if the substrings had a shorter edit sequence, we could just append the last column and get an overall shorter edit sequence.

[0159] Using this observation, it is easy to obtain a recursive algorithm for obtaining the edit distance between two strings. Let us introduce the function E(i,j)=E(i,j,σ^A,σ^B) for i=0, . . . , #σ^A and j=0, . . . , #σ^B defined as the minimal cost (or effort) to transform the subsequence σⁱ of the i first characters in σ^A into the subsequence σ^j of the j first characters in σ^B. Obviously, E(0,0)=0 and E(i,0)=i since the optimal way to convert a sequence with i characters into the empty string is with i deletions. Similarly, E(0,j)=j and the optimal transformations are just j insertions. With this we have the necessary initialization to get the recursion going as long as we find a way to express how to add the last column in the editing process. If both rows of the last column contain a character, then the optimal, last editing step is a substitution and the total cost becomes E(i−1,j−1)+[σ_i^A≠σ_j^B] (where [σ_i^A≠σ_j^B]0 if the i:th character of σ^A is the same as the j:th character of σ^B and 1 otherwise). On the other hand, if the top row contains an empty character and the bottom one a non-empty one, then we have an insertion, and the total cost is E(i,j−1)+1. If we have a non-empty character on the top row and an empty one on the bottom, then the corresponding operation is a deletion and the total cost is E(i−1,j)+1. The optimal choice is the minimum of these three alternatives:
E(i,j)=min{E(i−1,j−1)+[σ_i^A≠σ_j^B], E(i,j−1)+1, E(i−1,j)+1}  (22)
With the initialization
E(0,j)=j  (23)
E(i,0)=i,  (24)
we may recursively go through the equation (22) and obtain the
ed(σ^A,σ^B)=E(m, n) with m=#σ^A and n=#σ^B.  (25)

[0160] More general transformations are often quite easy to add. For example, if we also want to allow for transpositions of adjacent characters, then it is not enough to just consider the last column, since this type of transposition affects two characters. Instead, we have to consider the last two columns. The total cost for the transposition is then E(i−2,j−2)+1+[σ_i−1^A≠σ_j^B]+[σ_i^A≠σ_j−1^B] when i,j≧2) and

[0161] $\begin{array}{cc}E\left(i,j\right)=\min \{\begin{array}{c}E\left(i-1,j-1\right)+\left[{\sigma }_i^A\ne {\sigma }_j^B\right],\\ E\left(i,j-1\right)+1,\\ E\left(i-1,j\right)+1,\\ E\left(i-2,j-2\right)+1+\left[{\sigma }_{i-1}^A\ne {\sigma }_j^B\right]+\left[{\sigma }_i^A\ne {\sigma }_{j-1}^B\right].\end{array}& \left(26\right)\end{array}$
2.4 Some Sample Errors using the ORK

[0162] In this section, we shall start by collecting some hopefully representative typing errors.

[0163]

Some sample typing errors
#	Intended	Signature	Typed	Signature	Last in dict.
1.	catalogue	2040884628	catalbmc	204084628	catal
2.	out	864	oms	861	lux
3.	reference	323232522	reverycc	32323522	revery
4.	while	15782	shille	157882	shille
5.	encyclopedia,	2525288922707	ench.	25258	ench
6.	large	80342	laveb	80324	lave
7.	girls.	473818	give.s	473281	tirel
8.	catalogue.	2040884628	catalombc	204088642	catalo
9.	order	83223	over	8323	over
10.	answer,	0511237	ansccv	051223	ans
11.	which	15725	winkeh	175725	winke
12.	following	388881754	followibh	388881745	followi
13.	idea	7220	kea	720	ke
14.	enjoy	25685	chun.h	256585	chun
15.	suggestions	16442147851	suggestins	1644214751	suggestin
16.	magazines.	6040075218	magazins	60400751	magazin
17.	title	47482	titilc	474782	titil
18.	school	125888	schooi	125887	schoo
19.	chairs.	2507318	chaires.	25073218	chaire
20.	classroom	280113886	classrom	28011386	classro
21.	aim	076	ainm	0756	ain
22.	such	1625	sush	1615	sush
23.	these	45212	byes	4521	thes
24.	conveniently?	2853257254859	confidhc	28537252	confid
25.	bulletin	46882475	gulleybih	468825475	gulley
26.	decide	222722	deceicc	2222722	decei
27.	shelves,	15283217	she.c	15282	shel
28.	letter	824423	lege	8242	lege
29.	labels	804281	labos	80481	labo
30.	something.	1862457548	somethinc.	1862457528	somethin
31.	slogans.	18840518	sobahs.	1840518	sob
32.	giving	473754	biting	474754	biting
33.	thought	4586454	though	458645	though
34.	business	46175211	guishcs	4671521	guis
35.	opposite.	899817428	opposit.	89981748	opposit
36.	these	45212	ther	4523	ther
37.	followed?	388881229	rolls.cc	38881822	rolls
38.	request	3206214	reamsb	320614	reams
39.	expressed	219321122	exprescc	21932122	expres
40.	correct?	28332249	corvet?	2833249	corvet
41.	followed?	388881229	foolsccc?	388812229	foolsc
42.	checking	25227754	endiiihb	25277754	endi
43.	necessary	522211035	neessavh	52211035	nee
44.	which	15725	wien	1725	wien
45.	conservation	285123304785	consera	2851230	conser
46.	holds	58821	nod	582	nod
47.	muddy?	662259	muddch?	6622259	mudd
48.	topic	48972	bloke	48872	booke
49.	language	80546042	languavc	80546032	langua
50.	topic	48972	topicc	489722	topic

[0164] Let us look a little closer at these errors. First of all, the first three signatures are correct for all entries except for errors 2, 11, 13, 21, 22, 32, 34, 44, 46, and 48. The first four signatures are correct except for these errors and, additionally, errors 6, 7, 9, 10, 14, 26, 28, 29, 31, 36, 42, and 43. In many cases, the error causes the signature sequence not to be in the dictionary. Two common errors are transposition and “double-typing” a signature that should only occur once or, vice versa, “single-typing” when it should be “double-typed.” This seems particularly common for signatures 8, 1, and 2. In the next table we have collected various observations. In the column “Leaving dict.” we have recorded whether the error is causing the typed signature not to be in the dictionary; “Desired transf.” is an attempt to see what transformation is needed to correct the error or get the user back on track in typing after an error has occurred, and “Unique compl. before” indicates whether the error could have been avoided by just using a uniqueness-based auto-completion before the error occurred. The underscore in the “Typed signature” column indicates where the signature leaves the dictionary. If we count the relative position of a character with respect to this underscore, letting the first character after the underscore correspond to 0 and the one to the left of the underscore (hence still corresponding to something in the dictionary) be −1, then we may identify the first character to be changed. This then gives us information up to what point the edit distance (in the recursive formulation we just went through) is 0. This location of the first character impacted by the typing error is recorded in the column “1st character loc.”

[0165]

Some observations for sample typing errors
			Unique
	Leaving		compl.
#	dict.	Desired transf.	before	Intended signature	Typed signature	1st character loc.
1.	y	8 → 88	n	2040884628	20408_4628	0
2.	?	1 → 4	n	864	861	—
3.	y	3 → 32	n	323232522	323235_22	−1
4.	y	88 → 8	n	15782	157882 (?)	—
5.	y	8 → 28	n	2525288922707	25258—	−1
6.	y	24 → 42	n	80342	8032_4	−1
7.	y	32 → 3	n	473818	47328_1	−2
8.	y	64 → 46	n	2040884628	204088_642	0
9.	n	2 → 22	n	83223	8323	—
10.	y	2 → 1	n	0511237	051_223	0
11.	y	757 → 57	n	15725	17572_5	−4
12.	y	45 → 54	n	388881754	3888817_45	0
13.	y	2 → 22	n	7220	720	0
14.	y	58 → 85	n	25685	2565_85	0
15.	y	7 → 78	n	16442147851	164421475_1	−1
16.	y	1 → 21	y	6040075218	6040075_1	0
17.	y	7 → ε	n	474827	47478_2	−2
18.	y	87 → 88	y	125888	12588_7	0
19.	y	21 → 1	n	2507318	250732_18	−1
20.	y	8 → 88	y	280113886	2801138_6	0
21.	y	56 → 6	n	076	075_6	−1
22.	y	2 → 1	n	1625	1615—	−2
23.	n	1 → 12	n	45212	4521	?
24.	y	7 → 2	n	2853257254859	285372_52	+1
25.	y	54 → 4	n	46882475	468825_475	−1
26.	y	22 → 2	n	222722	22227_22	−2
27.	y	2 → 32	n	15283217	1528_2	0
28.	y	4 → 44	n	824423	8242_ (?)	−1
29.	y	4 → 42	n	804281	8048_1	−1
30.	y	2 → 4	y	1862457548	18624575_28	0
31.	y	8 → 88	n	18840518	184_0518	−1
32.	n	4 → 3	n	473754	474754	—
33.	n	ε → 4	n	4586454	458645	—
34.	y	71 → 17	n	46175211	4671_521	−2
35.	y	4 → 42	n	899817428	8998174_8	0
36.	n	3 → 1	n	45212	4523	—
37.	y	8 → 88	n	388881229	38881_822	−1
38.	y	1 → 21	n	3206214	32061_4	−1
39.	y	1 → 11	n	219321122	219321_22	0
40.	y	2 → 22	n	28332249	283324_9	−1
41.	y	8 → 88	n	388881229	388812_229	−2
42.	y	27 → 22	n	25227754	2527_7754	−1
43.	y	2 → 22	n	522211035	522_11035	0
44.	n	ε → 5	n	15725	1725	—
45.	y	3 → 33	n	285123304785	285123_0	0
46.	n	8 → 88	n	58821	582	—
47.	y	22 → 2	n	662259	6622_259	0
48.	n	88 → 89	n	48972	48872	—
49.	y	3 → 4	y	80546042	805460_32	0
50.	y	22 → 2	n	48972	48972_2	0

[0166] There seem to be four different types of errors that we may identify in these tables.

• • [0167] 1. Errors with the user continuing to perceived end of the word;
  • [0168] 2. Same as previous but with punctuation marks;
  • [0169] 3. Errors for which the user stopped typing before reaching the end; and
  • [0170] 4. Errors that result in a different legal word.

[0171] For the two first types of errors, the error distance probably provides a good approach. For the third type, a Beginning Of Word (BOW) based edit distance is probably better. Also, for these types of errors, the detection typically happens at the beginning of the word when an intelligent backspace may provide a good solution. The last type seems to require another approach using the alternatives that are presented to the user.

[0172] So, for now let us focus on errors of the first type. First, we consider the complexity of using the edit distance to identify candidate words corresponding to the signature sequence the user has input. We identify candidate sequences by calculating the edit distance (we shall use the edit distance with four basic operations, i.e., include transpositions). To calculate the edit distance, we use dynamic programming and obtain the edit distance by calculating the cost (effort) matrix. Hence, for each candidate sequence, the complexity is proportional to the number of entries in this matrix we have to calculate. This means that if we make the assumption that the four first characters of the input sequence are correct, then the number of entries we need to calculate is significantly reduced. For example, say that the cost matrix is of dimensions 8×8. Then, by the assumption about the first four keystrokes being correct, the resulting number of calculations is reduced from approximately 8×8 to 4×4, i.e, about a quarter. This effect is then further amplified by the fact that the number of candidate words that we have to consider decay essentially exponentially with the number of keystrokes we assume to be correct.

[0173] In addition, we see from the tables above that the typing error typically occurs close to the point of leaving the dictionary. In fact, in most cases the error occurs within two characters of the exit point. In terms of the calculation of the cost matrix, this means that only a submatrix of size 4×4 needs to be considered. However, the overall savings in not having to calculate the cost matrix for each candidate towards the end of the signature sequence is less since there are fewer and fewer words that are candidates towards the end of the input sequence.

[0174] Now, if we use the edit distance to identify candidate words that may correspond to the intended input sequence, it often happens that there are several candidates within, say, an edit distance 1. Then there are several criteria we may use to further refine the selection of such candidates. The simplest is to order these candidates according to probability of use, but there are many other ways as well. For instance, we may introduce different costs for different types of errors. If we choose that approach, transpositions should probably have a low cost (see the tables above) and so should the errors 88→8, 8→88, 22→2 and 2→22. Also, errors that occur close to the exit point compared to errors far from this point (of leaving the dictionary) should have a lower cost. However, these more refined considerations may not be necessary, since the edit distance combined with frequency ordering is remarkably accurate.

[0175]

Candidate words within a small edit distance from typed signature
#	Intended	Signature	Typed	Signature	Candidate	Signature	Edit distance	Rel. frequency
1.	catalogue	2040884628	catalbmc	204084628	catalogue	2040884628	1	2317
3.	reference	323232522	reverycc	32323522	reference	323232522	1	7496
					referred	32323322	1	5834
					referee	3232322	1	1100
					reversed	32323122	1	1096
					reverend	32323252	1	561
					reverted	32323422	1	284
					reverence	323232522	1	248
					revered	3232322	1	183
					fevered	3232322	1	65
					refereed	32323222	1	23
12.	following	388881754	followibh	388881745	following	388881754	1	26288
15.	suggestions	16442147851	suggestins	1644214751	suggesting	1644214754	1	2233
					suggestions	16442147851	1	1899
16.	magazines	604007521	magazins	604007	magazine	60400752	1	4456
					magazines	604007521	1	1589
20.	classroom	280113886	claasrom	28011386	classroom	280113886	1	2111
35.	opposite	89981742	opposit	8998174	opposite	89981742	1	5492
					opposing	89981754	1	913
37.	followed	38888122	rolls.cc	388818	followed	38888122	1	14592
39.	expressed	219321122	exprescc	21932122	expressed	219321122	1	6994
40.	correct	2833224	corvet	283324	correct	2833224	1	6046
					coffee	283322	1	5724
					coffer	283323	1	23
					doffed	283322	1	17
47.	muddy	66225	muddch	662225	muddy	66225	1	603
49.	language	80546042	languavc	80546032	language	80546042	1	17960
50.	topic	48972	topicc	489722	topic	48972	1	2297
					topica	489721	1	1838

2.5 Modifying the Edit Distance

[0176] One of our basic goals in this section is to describe an effective disambiguation system for approximate typing using a reduced keyboard. We have used the maximum likelihood approach to illustrate some of the issues, cf. Subsection 2.2. If we base our design on this approach and equation (11) or (13), then we are faced with the problem of finding estimates for Prob(σ^v|σ^a) (in the case of equation (11)) or Prob(σ^a|σ^v) (in the case of equation (13)). These expressions reflect the probabilities for typing errors, and one possibility is to experimentally go ahead and type a lot and obtain estimates for either of these and then store these approximations. This is in principle quite straightforward, but the storage requirements may easily make this impractical. Another possibility is to instead establish a model for these probabilities, and then use the model to calculate the required conditional probabilities at runtime by comparing the entered signature against valid character combinations. The challenge with this may be the search time. The modelling approach is what we shall consider more closely in this and the next couple of subsections. As a general observation, the problems and challenges are quite similar to those encountered in connection with machine translation from one language to another; cf. [34], p. 219, [31], p. 576, [41], p. 589, [8], and [47].

[0177] The models we shall explore here use the edit distance. The standard edit distance works surprisingly well as a similarity measure in order to identify possible interpretations of the user's intentions based on the actual entered signature. Heuristically, we would expect alternatives with a larger edit distance to be less likely than signatures with a smaller distance. This type of reasoning is often sufficient to order the alternatives for the user to choose from; however, identifying more precise connection between probabilities and the edit distance requires some further analysis.

[0178] We start with a general observation concerning measures of similarity and probabilities. Suppose we have a measure C that measures similarity in such a way that a small value of C(σ^v,σ^a) corresponds to the signatures σ^v and σ^a being similar or close. Suppose the user intends to type the signature σ^v. Suppose further that he sometimes enters σ^a1 and sometimes σ^a2. Now, if the user is more likely to enter σ^a1 than σ^a2, then it seems that, at least for this user,σ^a1 is closer to σ^v. In other words, it seems desirable to require
Prob(σ^a2|σ^v)≧Prob(σ^a1|σ^v)C(σ^v,σ^a2)≧C(σ^v,σ^a1).  (27)
Similarly, it is reasonable to expect that C should satisfy
Prob(σ^v|σ^a2)≦Prob(α^v|σ^a1)C(σ^a1,σ^v)≧C(σ^a1,σ^v).  (28)
Assuming now that C is defined on all pairs of signatures (including those not necessarily corresponding to valid signatures) these two equations (27) and (28) are consequences of the monotonicity property

[0179] $\begin{array}{cc}\frac{1}{\mathrm{Prob}\left({\sigma }^A❘{\sigma }^B\right)}\uparrow \Rightarrow C\left({\sigma }^A{\sigma }^B\right)\uparrow .& \left(29\right)\end{array}$

[0180] In order to guarantee the property (29), we must have access to the actual conditional probabilities. As we noted above, this may sometimes be infeasible and so we are now instead looking for a model of these conditional probabilities. Let us call these model probabilities p(σ^B|σ^A). So, for modelling purposes we may look for similarity measures with the property

[0181] $\begin{array}{cc}\frac{1}{p\left({\sigma }^A❘{\sigma }^B\right)}\uparrow \Rightarrow C\left({\sigma }^A,{\sigma }^B\right)\uparrow .& \left(30\right)\end{array}$

[0182] With this, let us go back to the standard edit distance C=ed based on the four nontrivial transformations substitution, insertion, deletion, and transposition (in addition to the trivial identity); cf. (26). It does not necessarily satisfy (29), and this can be traced back to the cost 1 used for each of the elementary transformations. (Generally speaking, if, say, transpositions are much more likely to occur than any of the other nontrivial transformations, then ed will assign too much distance between a pair of signatures that differ by transpositions for (29) to hold.)

[0183] So, the problem we want to solve is then to find a reasonable class of models and a corresponding set of similarity measures for which the monotonicity property (30) holds.

[0184] Since the costs of the elementary transformations caused the standard edit distance to fail the property (29), we shall go ahead and modify these costs. To simplify the notations a little, we first number the elementary transformations from 0 to 5: T₀ is the trivial identity transformation, T₁ substitution, T₂ insertion, T₃ deletion, and T₄ transposition. We let {right arrow over (T)}={T_i}_i=0⁴. We also introduce the notation ed(σ^A,σ^B, {right arrow over (c)}) for the edit distance based on certain costs {right arrow over (c)}={c_i}_i=0⁴, with one c_i for each of the operations T_i, i=0 . . . 4. In case we choose
c₀=0, c_i=1, i=1, . . . , 4,  (31)
we obtain the standard edit distance (based on the four nontrivial transformations).

[0185] Suppose we let p_i, i=0, . . . , 4, be the actual probabilities of each of the elementary transformations. We then set {right arrow over (c)}*={c_i*}_i with

[0186] $\begin{array}{cc}{c}_i^{*}=\ln \frac{1}{p_i},i=0,\dots ,4,& \left(32\right)\end{array}$
and also
ed*(σ^A,σ^B)=ed(σ^A,σ^B, c*).  (33)

[0187] We can now define a preliminary model for the actual conditional probabilities. We simply let
p*(σ^A|σ^B)=exp(−ed*(σ^A,σ^B))  (34)
Clearly, the monotonicity (30) is built into this definition. We also remark that if we let #T_i=#T_i(σ^B,σ^B) denote the number of times the transform T_i is used in the calculation of ed* when transforming σ^A into σ^B, then (34) can be rewritten as

[0188] $\begin{array}{cc}{p}_{*}\left({\sigma }^A❘{\sigma }^B\right)=\prod _{i=0}^4{p}_i^{\#T_i}& \left(35\right)\end{array}$
Hence, this looks as if the application of each of the different transforms are independent events, each with probability p_i.

[0189] Now, there are several problems with (35). Perhaps most obvious is the fact that the expressions p*(σ^B|σ^B) are not necessarily probability distributions. This can be fixed, however, with an appropriate normalization. Much more seriously, we have not compared and verified these “conditional probabilities” against the experimental data. In the next subsection, we shall carry this out rigorously.

2.6 Maximum Entropy Modeling

[0190] Our objective is to find a model for the probabilities p(σ^v|σ^a),σ^v∈S^v,σ^aÅS^a that we may use in, for instance, the maximum likelihood approach and equation (11). We shall accomplish this in steps, starting in this subsection and then continuing in the next.

[0191] Here is the setup for the more rigorous modeling we are going to consider. We let S^v be the space of labels (of valid signatures) and S^a the space of unlabeled examples (of all possible signatures).

[0192] To establish an appropriate model, we use a training set (σ_l^a,σ_l^v), l=1, . . . , L. To ensure consistency between the observations provided through the training set and the model, we use the expectations of certain features φ_i, i=0, . . , I. We let E_{{tilde over (π)}}[φ_i] represent the expectation of feature φ_i in the training data and E_π[φ_i] be the expectation with respect to the model π being estimated. Here {tilde over (π)} is the observed, empirical distribution over S^α×S^v, and π=π(σ^v|σ^a) is a model distribution over S^a×S^v. Specifically,

[0193] $\begin{array}{cc}{E}_{\tilde{\pi }}\left[{\varphi }_j\right]=\sum _{{\sigma }^{\alpha },{\sigma }^{\upsilon }}\tilde{\pi }\left({\sigma }^a,{\sigma }^{\upsilon }\right){\varphi }_j\left({\sigma }^a,{\sigma }^{\upsilon }\right)=\frac{1}{L}\sum _{l=1}^L{\varphi }_j\left({\sigma }_l^a,{\sigma }_l^{\upsilon }\right)& \left(36\right)\\ E_{\pi }\left[{\varphi }_j\right]=\sum _{{\sigma }^{\alpha }}\tilde{\pi }\left({\sigma }^a\right)\sum _{{\sigma }^{\upsilon }}\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right){\varphi }_j\left({\sigma }^a,{\sigma }^{\upsilon }\right)=\frac{1}{L}\sum _{l=1}^L\sum _{{\sigma }^{\upsilon }}\pi \left({\sigma }^{\upsilon }❘{\sigma }_l^a\right){\varphi }_j\left({\sigma }_l^a,{\sigma }^{\upsilon }\right)& \left(37\right)\end{array}$

[0194] To find the model π(σ^v|σ^a),σ^a,σ^v∈S^a×S^v, we use a maximum entropy approach; cf. [8], [41], [34]. We let H be the average (conditional) entropy given by

[0195] $\begin{array}{cc}H\left(\pi \left(·,{\sigma }^a\right)\right)=\sum _{{\sigma }^{\upsilon }}\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right)\ln \frac{1}{\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right)}& \left(38\right)\end{array}$

[0196] We then look for the solution {circumflex over (π)}(σ^v,σ^a) of the following constrained maximization problem; cf. [36], [8].

[0197] $\begin{array}{cc}{\mathrm{maximize}}_{\pi }\sum _{{\sigma }^a}\tilde{\pi }\left({\sigma }^a\right)H\left(\pi \left(·,{\sigma }^a\right)\right)\mathrm{subject}\mathrm{to}{E}_{\tilde{\pi }}\left[{\varphi }_j\right]=E_{\pi }\left[{\varphi }_j\right]\forall j\sum _{{\sigma }^{\upsilon }}\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right)=1,\forall {\sigma }^a\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right)\ge 0,\forall {\sigma }^{\upsilon },{\sigma }^a& \left(39\right)\end{array}$

[0198] Using Lagrange multipliers, we find that the solution to this constrained maximization problem is of the form

[0199] $\begin{array}{cc}{\pi }_{\overrightarrow{\lambda }}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)=\frac{1}{Z\left({\sigma }^a\right)}\exp \left(\sum _{i=0}^I{\lambda }_i{\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right)\right),\overrightarrow{\lambda }={\left\{{\lambda }_i\right\}}_{i=0}^I,& \left(40\right)\end{array}$
where Z(σ^a)=Z_{{right arrow over (λ)}}(σ^a) is the so-called partition function

[0200] $\begin{array}{cc}Z\left({\sigma }^a\right)=\sum _{{\sigma }^{\upsilon }}\exp \left(\sum _{i=0}^I{\lambda }_i{\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right)\right).& \left(41\right)\end{array}$
In other words, the solution to the maximization problem belongs to a family of loglinear models parameterized by the vector {right arrow over (λ)}of constants.

[0201] The dual objective function ({right arrow over (λ)}) associated with (39) is given by

[0202] $\begin{array}{cc}L\left(\overrightarrow{\lambda }\right)=\sum _{{\sigma }^a,{\sigma }^{\upsilon }}\tilde{\pi }\left({\sigma }^a,{\sigma }^{\upsilon }\right)\ln \frac{1}{{\pi }_{\overrightarrow{\lambda }}\left({\sigma }^a,{\sigma }^{\upsilon }\right)}& \left(42\right)\\ =\frac{1}{L}\left(\sum _{l=1}^L\sum _{i=0}^I{\lambda }_i{\varphi }_i\left({\sigma }_l^a,{\sigma }_l^{\upsilon }\right)-\sum _{l=1}^L\ln \sum _{{\sigma }^{\upsilon }}\exp \left(\sum _{j=0}^I{\lambda }_j{\varphi }_j\left({\sigma }_l^a,{\sigma }^{\upsilon }\right)\right)\right)& \left(43\right)\end{array}$
(see [53], pp. 6-7 for details).

[0203] Solving the maximum entropy problem (39) is then equivalent to maximizing the dual objective function ({right arrow over (λ)}) to find the optimal {right arrow over (λ)}:
{right arrow over (λ)}*=arg max_{{right arrow over (λ)}}({right arrow over (λ)}).  (44)
Once we obtain this vector, then the solution to (39) is the probability distribution π_{{right arrow over (λ)}}*(π^v|σ^a), cf. (40).

[0204] We also remark that the maximization of the dual objective function is equivalent to the maximization of the log-likelihood function

[0205] $\begin{array}{cc}\mathrm{LL}\left(\overrightarrow{\lambda }\right)=\ln \prod _{{\sigma }^a,{\sigma }^{\upsilon }}{{\pi }_{\overrightarrow{\lambda }}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)}^{\tilde{\pi }\left({\sigma }^a,{\sigma }^{\upsilon }\right)};& \left(45\right)\end{array}$
(see [8], p. 47, for details).

[0206] To solve (44) and hence find the optimal {right arrow over (λ)}*, we may use standard iterative techniques. In [40], there is a comparison of different numerical methods for maximum entropy problems. Typically, the partial derivatives of ({right arrow over (λ)}) are needed. These are given by

[0207] $\begin{array}{cc}\frac{\partial L}{\partial {\lambda }_i}=E_{\tilde{\pi }}\left[{\varphi }_i\right]-E_{{\pi }_{\overrightarrow{\lambda }}}\left[{\varphi }_i\right]& \left(46\right)\\ =\frac{1}{L}\sum _{l=1}^L\left({\varphi }_i\left({\sigma }_l^a,{\sigma }_l^{\upsilon }\right)-\sum _{{\sigma }^{\upsilon }}{\pi }_{\overrightarrow{\lambda }}\left({\sigma }^{\upsilon }❘{\sigma }_l^a\right){\varphi }_i\left({\sigma }_l^a,{\sigma }^{\upsilon }\right)\right)& \left(47\right)\\ =\frac{1}{L}\sum _{l=1}^L({\varphi }_i\left({\sigma }_l^a,{\sigma }_l^{\upsilon }\right)-E_{{\pi }_{\overrightarrow{\lambda }}\left(·❘{\sigma }_l^a\right)}\left({\varphi }_i\left({\sigma }_l^a,·\right)\right),i=0,\dots ,I.& \left(48\right)\end{array}$
It is also interesting to note that the second derivatives are given by the covariance matrix of the features:

[0208] $\begin{array}{cc}\frac{{\partial }^{2}L}{\partial {\lambda }_j{\lambda }_k}=-\sum _{l=1}^L{\mathrm{cov}}_{{\pi }_{\overrightarrow{\lambda }}\left(·❘{\sigma }_l^a\right)}\left({\varphi }_j\left({\sigma }_l^a,·\right),{\varphi }_k\left({\sigma }_l^a,·\right)\right)& \left(49\right)\end{array}$

[0209] Before applying the maximum entropy modelling to our current situation, we make the following remark. Note that by replacing φ_i(σ^a,σ^v) by −φ_i(σ^a,σ^v), we may always assume that the λ_i*≦0, i=0, . . , I. For any {right arrow over (λ)}≦0 (i.e., λ_i≦0 for each i=0, . . . , I), we define the generalized edit distance ed associated with the features {right arrow over (φ)}(σ^a,σ^v) by

[0210] $\begin{array}{cc}\mathrm{ed}\left({\sigma }^a,{\sigma }^{\upsilon };\overrightarrow{\lambda }\right)=-\sum _{i=0}^I{\lambda }_i{\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right).& \left(50\right)\end{array}$
(We let the associated cost functions {right arrow over (c)} be defined by {right arrow over (c)}=−{right arrow over (λ)}.) The conditional probabilities may then be written as

[0211] $\begin{array}{cc}{\pi }_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)=\frac{1}{Z\left({\sigma }^a\right)}\exp \left(-\mathrm{ed}\left({\sigma }^a,{\sigma }^{\upsilon };{\overrightarrow{\lambda }}_{*}\right)\right).& \left(51\right)\end{array}$

[0212] The maximum entropy approach is quite general in nature. To apply it to our particular situation, we need to define a set of features. We shall base these features on the edit distance ed(σ^A,σ^B,{right arrow over (c)}) for some given cost functions {right arrow over (c)}={c_i}_i=0⁴. We let
φ_i(σ^v,σ^a)=#T_i, i=0, . . . , 4,  (52)
where #T_i denotes the number of occurrences of the ith transformation T_i in the (optimal) calculation of the edit distance ed(σ^a,σ^v, {right arrow over (c)}). These features φ_i(σ^v,σ^a) obviously may depend on the particular choice of the cost functions {right arrow over (c)}.

[0213] Suppose then that we have obtained the solution {right arrow over (λ)}*={λ_i*}_i=0⁴ and let
Λ_i*=exp λ_i*.  (53)
According to (40), the corresponding model probabilities are given by

[0214] $\begin{array}{cc}{\pi }_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{\upsilon }❘{\sigma }^a\right)=\frac{1}{Z\left({\sigma }^a\right)}\exp \left(\sum _{i=0}^4{\lambda }_i^{*}{\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right)\right),& \left(54\right)\\ =\frac{1}{Z\left({\sigma }^a\right)}\prod _{i=0}^4{\left({\Lambda }_i^{*}\right)}^{{\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right)}& \left(55\right)\\ & \left(56\right)\end{array}$

[0215] Notice that at least for these features given by (52), our notations here are somewhat misleading: We have defined the φ_i:s with respect to an edit distance with a starting cost function {right arrow over (c)}. We then obtain a new (generalized) edit distance via the equation (50), associated with the optimal {right arrow over (λ)}*. This new edit distance now potentially results in different choices of the number of elementary transformations #T_i=#T_i(σ^a,σ^v) and a new optimal {right arrow over (λ)}*. And this can then be repeated forever unless the iteration process converges (i.e., the numbers #T_i stabilize from iteration to iteration).

[0216] We also experimented with a “normalized” set of features

[0217] $\begin{array}{cc}{\varphi }_i={\varphi }_i\left({\sigma }^a,{\sigma }^{\upsilon }\right)=\frac{\#T_i}{\sum _{j=0}^I\#T_j}.& \left(57\right)\end{array}$

[0218] The edit distance, with the appropriate cost functions, provides a coarse model of a user's typing and errors. By introducing more transforms, this model can be refined. For example, we have seen in the Subsection 2.4 that certain insertions and deletions are particularly common. Hence, we may introduce insertion and deletion transforms depending on neighboring characters.

[0219] Based on several users' typing errors, it seems that the following transforms may provide a better explanation of their typing than the standard set:

[0220]

	in22	insertion of extra 2
	in88	insertion of extra 8
	inss	insertion of extra symbol after same symbol
		(where symbol is not 2 or 8)
	ins	insertion of symbol without resulting duplication
	de22	deletion of extra 2
	de88	deletion of extra 8
	dess	deletion of extra symbol in a duplication
		(where symbol is not 2 or 8)
	des	deletion of symbol not from a duplication

Transposition tr, identity id, and substition su as before.
2.7 The Resulting Bayesian Model

[0221] Let us now see how we can establish a model that we can use in equations (11) and (13) in Subsection 2.2. First, we observe that the maximum entropy models from the previous Subsection are not exactly what we need. The reason is the following.

[0222] The probability distributions p_{{right arrow over (λ)}}(σ^v,σ^a) we obtained are defined in terms of the appropriate edit distance in such a way that if two signatures σ₁^v and σ₂^v have the same edit distance from the typed σ^a, then p_{{right arrow over (λ)}}(σ^v1|σ^a)=p_{{right arrow over (λ)}}(σ^v2|σ^a). If one of these two intended signatures σ_i^v, i=1, 2, is much more common than the other, then it seems that we should favor this signature instead of the other in, say, (11). But clearly our model distributions p_{{right arrow over (λ)}}(σ^v1|σ^a) will not form the basis for such assessments, at least not directly, since they only depend on the edit distance. (And this, of course, also means that the analysis in an example like Example 2.1 is out of reach.)

[0223] We can of course go back to the maximum entropy models and instead model p_{{right arrow over (λ)}}(σ^a|σ^v) using those techniques. If we do that in a straighforward manner, we are likely to end up with a partition function Z that depends on v, Z(v). This is problematic from a complexity point of view since it is expensive to calculate it, and it does not vanish when we want to compare several different v:s.

[0224] Another possibility is to introduce more constraints in the basic maximization (39). For example, we may add a constraint for each σ^v so that we guarantee through this constraint that the probability (obtained from a standard corpus perhaps) of each σ^v ends up being the right one. The calculations necessary for this do not appear to be easy, or at least from a complexity point of view it does not seem that they can be used in our setting.

[0225] A third possibility is to introduce more features into the definition of the edit distance so that the modified edit distance becomes more sensitive. With carefully chosen features, it may be possible to make the edit distance reflect the probability of the different σ^v. If we succeed in that, then on the other hand the modified edit distance probably will not accurately reflect the user's typing patterns.

[0226] The problems we are encountering here are due to the fact that we are mixing the impact from two different sources on our data. On one hand, we have the user's intended distribution of character combinations; and then, on the other hand, we have his typing and typing errors, cf. FIG. 3.

[0227] To sort this out, let us consider the input process as consisting of two parts: one process corresponding to units of characters at (like signatures corresponding to words) followed by another process corresponding to the user's typing and outputting a σ^a for each σ^v. Let us for simplicity also assume that the first of these processes is 0th order and can be described by the distribution of the o^v:s and that the second outputs a σ^a according to another distribution after each σ^v. (Neither of these assumptions is really necessary, but they make the discussion simpler.) In other words, suppose the user's context of character combinations is described by the probability distribution P(σ^v),σ^v∈S^v (for instance, P may be the probabilities of words in a big corpus), and that there are probability distributions π(σ^a|σ^v) for the data entered σ^a∈S^a given each intended σ^v∈S^v. Together these distributions determine a joint distribution p(σ^v,σ^a) on S^v×S^a defined by
p(σ^v,σ^a)=P(σ^v)π(σ^a|σ^v),σ^v∈S^v,σ^a∈S^a.  (58)
So, p(σ^v,σ^a) describes the probability that σ^v is the intended signature when σ^a is entered. This is then the basic description of the combined input system. We remark that we are thus led to a description that follows a path widely used in image analysis and pattern recognition to handle prior knowledge and empirical data, see [26], [58], [27].

[0228] Both P(σ^v) and the family π(σ^a|σ^v) may easily be recovered from the joint distribution p(σ^v,σ^a). To see this, we note that we clearly have

[0229] $\begin{array}{cc}P\left({\sigma }^{\upsilon }\right)=\sum _{{\sigma }^{\alpha }}p\left({\sigma }^{\upsilon },{\sigma }^a\right).& \left(59\right)\end{array}$
Further, by using the definition of conditional probability and the definition (58), we see that

[0230] $\begin{array}{cc}p\left({\sigma }^a❘{\sigma }^{\upsilon }\right)=\frac{p\left({\sigma }^{\upsilon },{\sigma }^a\right)}{P\left({\sigma }^{\upsilon }\right)}=\frac{P\left({\sigma }^{\upsilon }\right)\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right)}{P\left({\sigma }^{\upsilon }\right)}=\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right).& \left(60\right)\end{array}$
Hence, we may recover π(σ^a|σ^v) by first obtaining P from the joint distibution and then use the joint distribution again to get p(l atIv). This also tells us that the conditional probabilities p(σ^a|σ^v) of the combined input system only depend on the conditional probabilities describing the user's typing and have nothing to do with the distribution of the intended signatures σ^v.

[0231] We introduce the notation Q(σ^a),σ^a∈S^a, for the other marginal distribution associated with the joint distribution p(σ^v,σ^a):

[0232] $\begin{array}{cc}Q\left({\sigma }^a\right)=\sum _{{\sigma }^{\upsilon }\in S^{\upsilon }}p\left({\sigma }^{\upsilon },{\sigma }^a\right)=\sum _{{\sigma }^{\upsilon }\in S^{\upsilon }}P\left({\sigma }^{\upsilon }\right)\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right),{\sigma }^a\in S^a.& \left(61\right)\end{array}$

[0233] Assume now that we are given the typed σ^a and are asking for the distribution of the σ^v:s. Once again, simply by using the definition of conditional probability we get

[0234] $\begin{array}{cc}p\left({\sigma }^{\upsilon }❘{\sigma }^a\right)=\frac{p\left({\sigma }^{\upsilon },{\sigma }^a\right)}{P\left({\sigma }^{\upsilon }\in S^{\upsilon },{\sigma }^a\right)}=\frac{P\left({\sigma }^{\upsilon }\right)\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right)}{Q\left({\sigma }^a\right)},& \left(62\right)\end{array}$
where we of course assume that the denominator Q(σ^a) does not vanish. One way to interpret this relationship is like this: We started with a distribution P(σ^v) of the signatures σ^v∈S^v. Once we obtain the σ^a, then this distribution is adjusted and modified by the factor

[0235] $\frac{\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right)}{Q\left({\sigma }^a\right)}.$
We refer to P(σ^v) as the prior distribution and p(σ^v|σ^a) as the posterior distribution of σ^v given σ^a.

[0236] Note that to describe the joint distribution p(σ^v,σ^a) and the input process, we only need the “transition” probability distributions π(·|σ^v) as far as the typing goes. Sometimes it will be convenient to have access to a joint distribution, so we shall go ahead and define π(σ^v,σ^a) on S^v×S^a. We let

[0237] $\begin{array}{cc}\pi \left({\sigma }^{\upsilon },{\sigma }^a\right)=\frac{\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right)}{\#S^{\upsilon }}& \left(63\right)\end{array}$
where #S^v is the number of signatures in S^v (which we assume is finite). We then have two corresponding marginal distributions:

[0238] $\begin{array}{cc}\prod \left({\sigma }^a\right)=\sum _{{\sigma }^{\upsilon }\in S^{\upsilon }}\pi \left({\sigma }^{\upsilon },{\sigma }^a\right)=\frac{1}{\#S^{\upsilon }}\sum _{{\sigma }^{\upsilon }\in S^{\upsilon }}\pi \left({\sigma }^a❘{\sigma }^{\upsilon }\right),{\sigma }^a\in S^a\mathrm{and}& \left(64\right)\\ \Omega \left({\sigma }^{\upsilon }\right)=\frac{1}{\#S^{\upsilon }},{\sigma }^{\upsilon }\in S^{\upsilon }.& \left(65\right)\end{array}$
(Equivalently, we may have defined π(σ^v,σ^a) by first picking the uniform distribution Ω(σ^v), S^v, and then requiring π(σ^v,σ^a)=Ω(σ^v)π(σ^a|σ^v).)

[0239] For our purposes, we typically want to compare different σ^v:s given the same user input σ^a. With this in mind, we observe that by (60) and (62)

[0240] $\begin{array}{cc}\frac{p\left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{p\left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}=\frac{P\left({\sigma }^{{\upsilon }_1}\right)p\left({\sigma }^a❘{\sigma }^{{\upsilon }_1}\right)}{P\left({\sigma }^{{\upsilon }_2}\right)p\left({\sigma }^a❘{\sigma }^{{\upsilon }_2}\right)}.& \left(66\right)\end{array}$
Similarly, using the definition (63),

[0241] $\begin{array}{cc}\frac{\pi \left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{\pi \left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}=\frac{\pi \left({\sigma }^a❘{\sigma }^{{\upsilon }_1}\right)}{\pi \left({\sigma }^a❘{\sigma }^{{\upsilon }_2}\right)}.& \left(67\right)\end{array}$
Combining these equations (66) and (67) and once again using (60), we find that

[0242] $\begin{array}{cc}\frac{p\left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{p\left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}=\frac{P\left({\sigma }^{{\upsilon }_1}\right)\pi \left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{P\left({\sigma }^{{\upsilon }_2}\right)\pi \left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}.& \left(68\right)\end{array}$

[0243] So if we model P(σ^v) and π(σ^a|σ^v), then through (58) we obtain a corresponding model for the joint distribution p(σ^v,σ^a). In particular, let us use the maximum entropy model π_{{right arrow over (λ)}}*(σ^v|σ^a) from the previous subsection to model π(σ^v|σ^a). Let us also use some reasonable approximation P₀(σ^v) of the distribution P(σ^v) (for instance, the probabilities generated from a large corpus of some kind). Then we obtain a corresponding model
p_{{right arrow over (λ)}}*(σ^v,σ^a)=P₀(σ^v)π_{{right arrow over (λ)}}*(σ^a|σ^v),σ^v∈S^v,σ^a∈S^a.  (69)
For this model, the various identities above are valid. For example, equation (68) now reads

[0244] $\begin{array}{cc}\frac{p_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{p_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}=\frac{P_0\left({\sigma }^{{\upsilon }_1}\right){\pi }_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{P_0\left({\sigma }^{{\upsilon }_2}\right){\pi }_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}.& \left(70\right)\end{array}$
Using the explicit description of π_{{right arrow over (λ)}}* given by (51), we may equivalently write

[0245] $\begin{array}{cc}\frac{p_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_1}❘{\sigma }^a\right)}{p_{{\overrightarrow{\lambda }}_{*}}\left({\sigma }^{{\upsilon }_2}❘{\sigma }^a\right)}=\frac{P_0\left({\sigma }^{{\upsilon }_1}\right)}{P_0\left({\sigma }^{{\upsilon }_2}\right)}\exp \left(\mathrm{ed}\left({\sigma }^a,{\sigma }^{{\upsilon }_2};{\overrightarrow{\lambda }}_{*}\right)-\mathrm{ed}\left({\sigma }^a,{\sigma }^{{\upsilon }_1};{\overrightarrow{\lambda }}_{*}\right)\right).& \left(71\right)\end{array}$
2.8 Another Typing Model

[0246] Let us once again go back to the basic model (58). With it, we are treating the typing model for a user (or set of users) as “noise” on top of the exact entry of the intended units of characters (“words”). To establish such a typing model, we have used maximum entropy modeling. The equation (35) can also serve as inspiration for another approach, and this is what we shall go through in this subsection.

[0247] One possibility is to view the typed characters as outcomes of an appropriate stochastic process. For example, if the typed character coincides with that of the intended signature, then we may record that as “no error”; and if an error occurs, we may characterize this by recording what transform is required to adjust the intended keystroke to coincide with the typed one. For the error/no-error process, we may then use a Poisson-type process, and, in addition, use a separate distribution to characterize the possible outcomes when an error occurs; cf. [30]. This is similar to what we shall study here.

[0248] Let us consider a fixed unit σ^v of intended character combinations (a “word”) with individual characters σ_n^v:
σ^v=σ₁^v . . . σ_N−1^v,  (72)
where N=#σ^v is the length of σ^v. (We note that we are using a left-to-right ordering, but the particular ordering is not important.) Each unit σ^v is input by the user, resulting in the signature σ^v with characters σ_m^a:
σ^a=σ₁^a . . . σ_M−1^a,  (73)
where M=#σ^a. It will be convenient to set
σ_n^v=b, n≦0  (74)
σ_n^v=e, n≧N,  (75)
and, similarly,
σ_m^a=b, m≦0  (76)
σ_m^a=e, m≧M,  (77)
(78)
to take care of the beginning and the end of these units. The typing model we shall study here uses a sequence of transforms τ==T(σ^v,σ^a)={T_k} to explain the typed entries σ^a given the intended ones σ^v. Each transform acts on a set of characters in the intended signature and outputs some characters in the typed signature, and the transforms are ordered sequentially, just as the input process, so we shall also write
T= . . . T₋₁T₀T₁  (79)
as well as
Tσ^v=σ^a.  (80)
Each of the transforms T_k acts on a character σ_nk^v and outputs either the empty character or a character in σ^a. The idea is to choose the transforms so that the probability Prob(T) becomes an approximation of the typing model π(σ^a|σ^v).

[0249] Let us illustrate the procedure in terms of the family of five basic transforms (including the identity) used for the standard edit distance {id, in, de, su, tr}, cf. Subsection 2.3 as well as Example 2.3 in Subsection 2.6. We shall view each of the transforms T_k as being chosen independently from the family of transforms {id, in, de, su, tr} and assume that the particular transform is drawn from the family of transforms with a probability that only depends on the current position that the transform is acting upon, the position before the current position (for a first-order model), what particular transform that is picked, and what output symbol it must generate to match the typed signature. So, the action of each transform T_k can be completely characterized by the character curr=σ_ik^v at the current position, the previous character prev=σ_ik−1^v, the type type of the transform, and the output character out. So, we may in general describe T_k by the input-output relationship (prev,curr)→(type,out). We note that sometimes a different choice of relevant context (here the position before the current one) is more appropriate. For example, a user inserting an extra “s” onto nouns is probably quite common. In that case, a better context for the insertion transform may be the character after the current position so that the end of the unit will be recognized.

[0250] Suppose the intended signature is σ^v=1234 and the typed signature is σ^a=5512334. A reasonable guess as to what happened during the user's input process is given by the sequence of transforms T={in, in, id, id, id, in, id}. In more detail, we have the following sequence of transforms:
(b,b)→(in,5)(b,b)→(in,5)(b,1)→(id,1)(1,2)→(id,2)(2,3)→(id,3)(2,3)→(in,3)(3,4)→(id,4).  (81)
Similarly, let us assume the intended signature is σ^v=12234 and the typed signature is σ^a=1243. Then the typos may possibly be explained by the sequence T={id, id, de, id, tr}, or, more precisely, by the sequence
(b,1)→(id,1)(1,2)→(id,2)(2,2)→(de,ε)(2,3)→(id,3)(3,4)→(tr,(4,3)).  (82)
(Obviously, there is redundancy in the notation here; for example, the transpose of (3,4) is clearly known without specifying (4,3).)

[0251] Once we have the sequence of transforms in place or, equivalently, the input-output relationships, and if the transforms are picked independently with probabilities depending on the two input parameters, then the following is a reasonable approximation of a typing model:

[0252] $\begin{array}{cc}\pi \left({\sigma }^{\upsilon }❘{\sigma }^a\right)\approx \prod _k\mathrm{Prob}\left(T_k\right)=\prod _k\mathrm{Prob}\left(\left({\mathrm{prev}}_k,{\mathrm{curr}}_k\right)\to \left({\mathrm{type}}_k,{\mathrm{out}}_k\right)\right).& \left(83\right)\end{array}$
The transition probabilities Prob((prev_k, curr_k)→(type_k, out_k)) can be estimated from sample data (for a given user or a set of users). Since each of the labels (prev, curr) and (type, out) only take finitely many values, it is convenient to collect all these probabilities in a transition matrix with, say, a row corresponding to a specific input label (prev, curr) and each column to a specific output label (type, out).

[0253] Let us make two comments related to the estimation of this transition matrix. In our example with the small set of basic transforms, there are not very many entries in the matrix, and still there may be entries that are very infrequently visited as the user types. This sparsity of data makes it harder to obtain reliable estimates for some of the entries. There are many techniques for other applications that have been developed to address this (cf. [34], [31], [41]). For example, sometimes we may omit the dependency on the prev label and collect all the samples corresponding to a certain curr, type, out in a larger bin, and then assume that the distribution over the prev label is uniform (so called “back-off” from a first order model to a 0:th one). More generally, we may define other equivalence classes of labels that we expect to behave similarly as far as typing error, and then distribute the frequency counts evenly over the equivalence class.

[0254] The other comment relates to finding the appropriate transform sequences. Since the typing model is intended to explain the typical typing process, including common errors, the transform sequence should reflect these explanations. The assignment of the appropriate transforms to obtain the approximation of the transition matrix from samples at first seems to require a careful, case-by-case choice; however, it turns out that the transforms obtained from the calculation of the edit distance in most instances work quite well and few special cases need “hand-coding.”

2.9 Reducing Search Complexity

[0255] The edit distance can be calculated very quickly even for general cost functions and larger sets of basic transforms. For instance, we do not need to calculate the entire cost matrix E(i,j) in the dynamic programming approach (26). In Subsection 2.4, we have mentioned that by making the assumption that a certain number of the initial characters are entered correctly, we obtain a signficant reduction in complexity. In addition, there are several well-known techniques to reduce the complexity of the distance calculation. Suppose, for example, that we are only interested in edit distances smaller than a certain value. Then we may stop the calculation when we get too far off the diagonal in the cost matrix since we know that the cost will only increase after that. There are techniques for carrying out the distance calculations in parallel. We refer to [33] and [44] for recent references and related approaches (the trick to only consider elements in the cost matrix close to the diagonal goes back to [39], [57]).

[0256] Our goal in this Subsection is to find techniques that allow us to expand the collection of possible typing errors that we may consider within a reasonable response time. The assumption that the first four characters are correctly entered is often much too restrictive. For example, in Table 3 we have collected the probability of up to the first four characters being typed correctly for signatures of length at least 5 that contain errors. This data relies on statistics from eight users as they typed about 6,800 words.

[0257] There are at least two basic approaches to reduce the search complexity to quickly find the potential signatures we need to consider. The first approach is to improve how we predict the signature that the user probably had intended. The second approach is to find a better indexing structure for the dictionary. In [6], [7], and [16] the indexing is based on the metric structure of the edit distance.

[0258] The exact typing model of a user depends on the system within which the typing occurs.

[0259]

TABLE 3
The error probability for the initial characters
among errors by three users for character combinations
of length 5 and more.
First i
characters correct	User 1 prob. %	User 2 prob. %	User 3 prob.%
1	95.2	91.9	98.6
2	85.7	83.2	89.9
3	78.6	63.4	77.0
4	61.9	41.0	60.4

[0260] In other words, the cabilities of the typing environment will impact the user's typing habits. As we mentioned earlier, it is probably particularly important for the user if longer words do not have to be retyped or edited. On the other hand, shorter words are typically more frequent, and it is easier to erase a few characters and to keep track of what has already been emtered, etc. Hence, we may expect that an accurate typing model will distinguish between different lengths of signatures entered.

[0261] To approximate this difference in the dependence of the user's experience and typing model on the length of the signatures entered, we shall separate signatures of length, say, four or less, from those longer than four.

[0262] For character combinations that are four characters long or less, it is more feasible to obtain an approximation of the typing model directly from experimental data. For now, we shall simply incorporate a few specific transforms for these combinations. For example, from our experimental data it seems that transpositions at the end of combinations are particularly common. For these shorter combinations, it is also easier to establish a look-up table for combinations that are particularly prone to certain errors and then list the appropriate corrections for these.

[0263] Here we shall now focus on character combinations that are at least five characters long. There are several considerations to keep in mind: response time, storage, typing order, user characteristics, etc. In order to reduce search time, we may use different prediction techniques, taking into account the particular data structure of the stored information. These predicitions may use a number of features. For example, the approximate length of a character combination seems to be quite stable under the entry process. With a storage premium, we may also add word endings and other shorter combinations.

[0264] The following will illustrate some of the issues involved. If we assume that the four initial characters are correct, then we have significantly narrowed down the number of potential signatures we have to consider. However, as we have seen in Table 3, this assumption is quite restrictive and removes a significant portion of the intended signatures. We can improve the situation by relaxing the assumption and only assume that the first three characters are correct. To avoid increasing the search space too much, we can then use these three to predict a fourth character and let these predicted four-character combinations form the basis for our search of potential, additional alternatives to present to the user. (These are in addition to the alternatives obtained using the default assumption that all four are correct.) One such prediction method is to use the maximum likelihood prediction for the fourth entry based on the probability of all legal combinations of length four with the given, initial three characters. These predictions can be established off line and stored in a small table for quick retrieval.

[0265] We may also add different models for the typing to improve the prediction accuracy. For example, as we mentioned in Subsection 2.6 (see Example 2.3) it is easy to type too few of the character 8 on the ORK, and hence it makes sense to incorporate these types of facts when predicting likely errors and intended entries.

[0266] To illlustrate this, let us consider the ORK as the entry device and let us further make the assumption that only the first two out of the initial four characters are correct, and that we want to use all four characters for our initial search of likely alternatives (as before). Hence, this leaves us with having to predict the two remaining characters. So, there are potentially one hundred possibilities for each one of the ten thousand possible initial σ^a:s with four characters (since we are assuming that the first two characters are correct). So, if we decide to use a maximum likelihood approach, we are interested in ordering the probabilities Prob(σ^v|σ^a) for each one of the σ^a:s. The σ^v:s we are considering here correspond to legal combinations of length four that are part of the character combinations of length at least five. Instead of experimentally estimating these, we go back to the basic Bayesian model (58) in Subsection 2.7. For the ordering, we may then use equation (68). The factor P(σ^v) can be estimated from sample data (like a large corpus or dynamically). This means that as soon as we have a typing model π(σ^v|σ^a), then we have the basis for selecting the most likely four combinations σ^v:s for each fixed σ^a.

[0267] In the next example, we shall compare the performance of the two approaches outlined above. The first uses the assumption that the first three characters entered are correct and then predicts three possible choices for the fourth character based on the frequency of occurrence derived from a standard corpus. The second uses the typing model described in Subsection 2.8. For this approach, we shall only assume that the first two characters are correct.

[0268] In this example, we shall compare the two prediction methods described above. For the first prediction method, we assume that the first three characters entered are correct. As a consequence, the highest percentages we can reach are 78.6%, 63.4%, and 77.0% for the three users, cf. Table 3.

[0269]

TABLE 4
The probability of having the first four characters among
the top 2 and 3 alternatives, respectively,
for the prediction method without typing model. (Using
character combinations of length 5 and more.)
Among i
top alternatives	User 1 prob. %	User 2 prob. %	User 3 prob. %
2	71.4	52.8	68.3
3	78.6	59.0	74.1

For the second prediction method, we only assume that the first two characters entered are correct. Hence, the highest percentages we can reach now are 87.7%, 81.3%, and 80.5% for the three users, cf. Table 3.

[0270]

TABLE 5
The probability of having the first four characters among
the top 2 and 3 alternatives, respectively,
for the prediction method with typing model. (Using
character combinations of length 5 and more.)
Among i
top alternatives	User 1 prob. %	User 2 prob. %	User 3 prob. %
2	76.3	64.0	73.9
3	79.1	68.3	76.2

Let us also record the percentage of the error signatures whose first four or five characters are among the top 3 alternatives when we only assume that the first character is correct.

[0271]

TABLE 6
The probability of having the first four or five
characters among the top 3 alternatives, respectively, for
the prediction method with typing model under the assumption the
first character is correct. (Using character
combinations of length 5 and more.)
	First j characters of top 3 alternatives	Overall % of all errors
	4	67.6
	5	11.5

[0272] 3 NLP-based Considerations

3.1 The Substitution Test

[0273] To explain the basic underlying idea in this section, let us start by considering some groups of words with the same signature, see Table 7. With the objective of reducing the collisions, we observe that the words in each of the groups are often of very different in nature, some are nouns, some are verbs and adjectives, etc. This means that although they have the same signature, they often play different roles in building a sentence.

[0274]

TABLE 7
Groups of words with the same signature and
corresponding frequencies
#	Words	Frequencies
1	to	2332410
	go	59270
2	sixth	2128
	sixty	1304
3	slang	174
	slant	124
4	safe	6541
	save	6209
	wave	3407
	ward	3323
	ware	225
5	basis	13464
	tasks	3598
	taxis	284
	basks	16
	gawks	0
6	show	24459
	snow	3263
7	signs	4724
	sighs	203
8	sorry	6968
	worry	4516
9	sold	7820
	wood	6792
	sole	2358
	wold	83
	sloe	7
	now	108301
	how	81957
	nos	185
	yow	77
	hos	0

[0275] To further elaborate on this, let us consider a couple of sample sentences (in this case from Alice In Wonderland).

• • [0276] 1. ‘I'm very sorry you've been annoyed,’ said Alice, who was beginning to see its meaning.
  • [0277] 2. How puzzling all these changes are!
  • [0278] 3. Mind Now!
  • [0279] 4. So she set the little creature down, and felt quite relieved to see it trot away quietly into the wood.
    If we substitute the word “sorry” with “worry”, the other word in the same collision group, then sentence 1 no longer makes sense. It is certainly grammatically incorrect. Similarly, in sentence 2, none of the other words in the same collision group work as a substitute for “now”; grammatically, the resulting sentence would be incorrect. Sentence 3 is a little more challenging: “how” can be substituted for “now” and we still have a meaningful sentence. Perhaps it is a little more unusual, but it is grammatically correct. In sentence 4, the word “wood” can be replaced by the noun “sole”, but not when this word is used as an adjective. Hence, in that case, we need to refine the frequency information about this particular word to incorporate the counts when the word is used a noun and when it is used as an adjective. So, after such a such a refinement, we have been able to reduce the number of colliding words of any real consequence to two (“wood” and “sole”), and we have also been able to adjust the probabilities to more accurately reflect the situtation.

[0280] One way to consider the input of characters and the feedback is as a communication process between the user and the device. The device is attempting to extract the intended words and sentences. As the substitution test indicates, the meaning of the words and the sentence is an important component for the understanding of spoken, as well as written, language between two users, and it seems to be a potentially powerful mechanism to help determine the best choices of words with the same signature.

[0281] To find the exact meaning of a word and a sentence is difficult, since it is hard to even quantify the problem and the terms involved. The meaning of a word is, for example, highly context sensitive. In general, the problem of automatically extracting the meaning from words and sentences is related to a number of interesting and very active research areas in Natural Language Processing (NLP), cf. [46], [4], [41], [32], [20].

[0282] However, it is possible to carry out a substitution test, similar to the one above, in any sentence by inserting each of the words corresponding to a given signature and decide which ones can be discarded on grammatical and syntactical grounds. In this section, we discuss how such a substitution test can be automated and how it can be used to improve the user's experience using the One-Row Keyboard and similar reduced keyboards.

3.2 Some Statistics

[0283] Let us start by looking at some statistics related to the effectiveness of the input process, without the support of syntactical information or any other way of utilizing the meaning of the sentence being created. In Table 8 below, we have collected some statistics from the following texts:

• [0284] Book 1 Alice in Wonderland (by Lewis Carroll)
• [0285] Book 2 Memoirs of Aaron Burr (by Matthew L. Davis)
• [0286] Book 3 Crime and Punishment (by Fyodor Dostojevsky)
• [0287] Book 4 Edison, his life and inventions (by Frank Lewis Dyer)
• [0288] Book 5 Complete Poems of Emily Dickinson
• [0289] Book 6 The Forgotten King (by Jonathan Dunn)
• [0290] Articles Sampling of articles from recent editions of Time
  In particular, we notice that the signature is ambiguous for about 30% of the words, but that about 90% of those are in fact displayed correctly. This results in approximately 96-98% of all words being displayed correctly “the first time” on the display. (We have assumed that word initially displayed is simply the most probable word for a given signature, i.e., we have used the path-frequency ordering.)

[0291] So there are approximately 3% of words that are incorrectly displayed the first time they are displayed. Although this number seems to be quite low, it is helpful to keep in mind that the average number of words in a sentence is quite large. For example, in The Wall Street Journal corpus (cf. [51], [1], [42]), the average sentence length is approximately 23 words. Hence, if we were typing The Wall Street Journal with the One-Row Keyboard, we would

[0292]

TABLE 8
Collision statistics for sample texts.
Item	Book 1	Book 2	Book 3	Book 4	Book 5	Book 6	Articles
# words	26686	283057	207084	261462	94299	155997	17837
# collisions	7557	90685	66809	89011	28796	36268	3013
% collisions	28.3	32.0	32.3	34.0	30.5	23.2	16.9
% correct display	96.86	97.54	97.33	97.83	96.04	97.81	97.95

expect to have to change one word on the screen at least once in about 70% of the sentences (since 23×0.03˜0.7).

[0293] Let us then investigate a little further where the problems are originating. The ten most frequent collision groups account for about 60% of the collisions, and the 50 most frequent ones represent about 90%, cf. Table 9.

[0294]

TABLE 9
The percentage of the collisions in the most
frequently occuring collision groups.
% of Collisions
# most frequent groups	Book 1	Book 2	Book 3	Book 4	Book 5	Book 6	Articles
10	65.1	52.6	58.6	66.1	54.7	52.7	63.5
25	83.7	74.7	77.0	78.7	70.4	72.3	83.2
50	94.5	86.3	88.6	86.2	80.6	84.2	93.7
100	99.8	94.2	95.5	92.5	89.0	93.1	100

[0295] As we noted, in most cases the right word is initially displayed on the screen. Hence, to measure the problematic collisions it is interesting to look at what signatures are the ones causing most of the incorrectly displayed words. Rather than doing that exactly, we have collected in Table 10 how much of the approximately 3% of the incorrectly displayed words we could avoid if we were able to correctly handle the two most frequent words in certain specific collision groups. These specific groups are selected based on the frequency of the first alternative. Assuming that we correctly resolve the two words in ten of the collision groups, we reduce the 3% to approximately 1.4%. And if we take care of 25 groups and the coresponding two words of the highest frequency in each of those, then as a result approximately 0.7% of the words are being incorrectly displayed. Assuming that the average sentence is about 23 words long, we would then expect to find only one incorrectly displayed word in one out of six or seven sentences (23×0.007=0.161).

[0296]

TABLE 10
The effect of resolving the two
most frequent words in specific sets of collision groups.
% Correctly Displayed
#
groups	Book	Book	Book	Book	Book	Book
fixed	1	2	3	4	5	6	Articles
10	98.78	98.95	98.87	98.83	97.81	98.84	99.01
25	99.35	99.30	99.33	99.14	98.39	99.18	99.36
50	99.67	99.5	99.55	99.38	98.76	99.45	99.63
100	99.91	99.67	99.72	99.56	99.12	99.67	99.89

[0297] On the other hand, if we could resolve all the words in some specific collision groups, not just the two most frequent, then the effect would be slightly different. In that case, we should select the collision groups based on the total frequency of all the alternatives (thus not counting the frequency of the displayed words). This is what we have in Table 11, assuming that we display all the words in the specific collision groups exactly when they should be.

[0298] As we see, when we completely resolve ten collision groups, the collision probability goes down to approximately 1.2%. If we handle 50 groups perfectly, then only about 0.5% of the words would be incorrectly displayed. This means that on average only one word would be incorrect in a little more than nine sentences.

[0299] The words that make up these groups are quite consistent across the different sample texts. For example, in Table 12 are some of the details about the ten groups used in Table 11 for Book 1, Book 2, and Articles.

[0300]

TABLE 11
The effect of resolving the entire group for a
specific number of collision groups.
% Correctly Displayed
#
groups	Book	Book	Book	Book	Book	Book
fixed	1	2	3	4	5	6	Articles
10	98.82	98.99	98.87	98.89	97.84	98.84	99.07
25	99.40	99.36	99.39	99.25	98.53	99.21	99.44
50	99.73	99.58	99.63	99.51	98.96	99.51	99.74
100	99.97	99.77	99.81	99.72	99.36	99.74	100

[0301]

TABLE 12
The percent of the collisions in the most
frequently occuring collisions groups for sample texts.
#	Word	% of Collisions
Book 1
1	they	1.733
	then	1.244
2	of	6.802
	or	1.019
3	how	0.900
	now	0.794
4	way	0.741
	say	0.675
5	to	9.647
	go	0.662
6	on	2.554
	oh	0.595
7	just	0.688
	must	0.582
8	have	1.059
	hare	0.410
	hard	0.106
	yard	0.013
9	round	0.543
	found	0.423
10	can	0.463
	day	0.384
Book 2
1	of	12.478
	or	1.595
2	by	1.967
	th	0.815
3	can	0.475
	day	0.471
4	they	0.850
	then	0.346
5	now	0.455
	how	0.288
6	may	0.810
	man	0.214
	jay	0.033
7	year	0.160
	hear	0.120
	near	0.087
8	c	0.223
	d	0.190
	e	0.009
9	to	10.761
	go	0.195
10	say	0.193
	way	0.179
	wan	0.001
Articles
1	of	15.267
	or	2.124
2	they	3.485
	then	0.797
3	say	0.664
	way	0.597
	san	0.199
4	how	1.162
	now	0.730
5	have	3.186
	hard	0.498
	yard	0.033
6	to	17.624
	go	0.465
7	can	1.228
	day	0.365
8	good	0.398
	told	0.199
	gold	0.066
	bold	0.066
9	just	1.128
	must	0.266
10	may	0.697
	man	0.199
	jan	0.033
	jay	0.033

3.3 Modeling the User—Device Interaction