User input prediction

0001The present invention relates generally to a data input system which comprises a user interface. In particular, the user interface comprises a plurality of targets and is configured to receive user input. The present invention provides a method of modelling a target of a user interface of a system and a method of inputting data into a system in which the targets of a user interface have been so modelled.

0002Previously, work on enhancing user interaction with keyboards of limited size has provided a number of methods based on reduced-size keyboards, which do not cover the full range of characters for a given language. This is the subject of U.S. Pat. No. 6,307,549, which provides a method for disambiguating the output from a reduced keyboard (usually about 3 characters per key). Word-level disambiguation is provided using a selection button which enable a user to cycle through possible matches to the current input. An alternative reduced keyboard layout, based on the common QWERTY layout, is the ‘half qwerty’ layout provided by U.S. Pat. No. 7,083,342, which also uses extra post-input disambiguation.

0003Although reduced keyboards have a reduced error rate, they also quantize the input more roughly, meaning that there is less information content in the input the computer receives from a reduced keyboard than a full keyboard.

0004In theory, with an adequate error-correction system, a full keyboard with error correction should require less disambiguation keystrokes than a reduced keyboard. On a hard keyboard, an input event relates to a user pressing down on a key of the keyboard. For such keyboards, the user can press any location within the boundary of a key; the corresponding input event will be the same for all locations within that boundary. However, with touch-sensitive ‘soft keyboards’, it is possible to use the almost continuous co-ordinates of touches on the soft keyboard.

0005Many existing virtual keyboard systems, e.g. United States patent application publication number 2009/0284471 and predecessors, incorporate mechanisms for automatically ‘correcting’ user input in instances where the system receives a character that is not the one intended by the user. Such systems are based around the idea of associating a pre-specified set of locations, each designated by a set of Cartesian coordinates, with characters available for input by the user. Given a set of coordinates representing an input event, the distances between this event and surrounding pre-specified locations within an ‘auto-correcting region’ are used to construct a weighted set of characters assigned to that event. The auto-correcting region comprises a plurality of characters of the alphabet. During input, the user is presented with a set of ‘objects’ that are considered likely intended character sequences. As the user selects his/her intended input sequences, the (potentially weighted) horizontal and vertical offsets between the input event coordinates and the character coordinates are computed, and the relevant moving average used to calibrate input event coordinates to reflect a user's typing style. The moving average may be a running average where the coordinates of each key are set to the average of all previous input events for that key.

0006The above described existing virtual keyboards model each character as a location specified by a set of coordinates. In contrast, the system and method of the present invention models a user's actual input as he or she targets characters on a virtual keyboard. Thus, the system and method of the present invention models, for a given character, the user's input history for that character.

0007The system and method of the present invention provides a system that adapts to a user and learns the style in which a user inputs text. By modelling the user's historical interaction with the system, the present system is able to more accurately predict which character the user intended to input given an input event. Thus, the present invention provides a system which is capable of providing more accurate and reliable text predictions and thus providing more accurate text input into an electronic device. The increase in accuracy results in less correction, and therefore a system providing more efficient text entry and with a lower processing requirement.

0008In one embodiment, the present invention provides a data input system comprising a user interface comprising a plurality of targets and being configured to receive user input. The system comprises a plurality of models, each of which relates previous user input events corresponding to a target to that target. The system further comprises an input probability generator configured to generate, in association with the plurality of models, a probability that a user input event corresponds to a particular target.

0009The target can represent one or more characters, a key, a symbol or any other item of information which is for user selection.

0010Preferably, the user interface is a virtual keyboard. An input event may correspond to a location on the virtual keyboard and each model is a distribution which models locations of the user's previous input events corresponding to a particular target. This distribution may be a 2D Gaussian. Preferably, the parameters of the 2D Gaussian are learnt using maximum a-posteriori estimation based on the input events corresponding to the target. Preferably, the form of the prior distribution over model parameters is the conjugate prior to the distribution. Where the targets are keys on the virtual keyboard, a prior for each target may be set empirically based on a keyboard layout.

0011The virtual keyboard may comprise multiple sets of target models, each set of target models being tailored to a different user, or usage scenario.

0012The input probability generator in association with the plurality of models may output for a user input event the n most probable targets and their associated probabilities.

0013The system may comprise a map mapping each of the n targets to one or more word fragments with associated probability values. Preferably, each word fragment is tagged in the map with the target to which it corresponds.

0014The system may further comprise a predictor configured to receive the as most probable targets and their associated probabilities and to generate text predictions having probability values. The predictor may be configured to receive the word fragments and their associated probabilities and to generate text predictions having probability values.

0015Upon selection of a prediction, the target(s) of the prediction are matched to the corresponding input event(s). The targets of the prediction may be matched to the corresponding input events by the tagging of the word fragments of the prediction to their corresponding targets. Alternatively, the targets of the prediction may be matched to the corresponding input events by the reverse mapping of the word fragments to their corresponding targets and the pairing of the targets to the input events.

0016The selection of a prediction may comprise the user's selection of the prediction or the automatic selection of the most probable prediction. The selected prediction is preferably input into the data input system as text.

0017The system may also comprise a model updater configured to update a model to reflect mapping of an input event to the target corresponding to that model.

0018An electronic device may comprise the data input system as described above. The electronic device can be a computer, a PDA or a mobile telephone.

0019In a second embodiment, the present invention provides a method of modelling a target of a user interface comprising a plurality of targets and being configured to receive input, the method comprising modelling for each target user input events which correspond to that target.

0020Where the user interface is a virtual keyboard and an input event corresponds to a location on the virtual keyboard, the method may further comprise modelling each target as a distribution which describes the locations of the user's previous input events corresponding to the target. The distribution may be a 2D Gaussian. Each model must also comprise a prior, which may be conjugate to the distribution. Preferably, the parameters of the 2D Gaussian are learnt using maximum a-posteriori estimation based on the input events corresponding to the target. The targets are keys on the virtual keyboard and a prior for each target is set empirically based on a keyboard layout.

0021In a third embodiment there is provided a method of inputting data into a system comprising a user interface having a plurality of targets and being configured to receive input, the method comprising generating using an input probability generator in association with a plurality of models, each model relating previous input events corresponding to a target to that target, a probability that a user input event corresponds to a particular target.

0022Preferably, the method comprises outputting from the input probability generator for a user input event the n most probable targets and their associated probabilities. The method may also include mapping with a map each of the n targets to one or more word fragments with associated probability values. Preferably, the method comprises tagging with the map each of the one or more word fragments with the target from which it was mapped.

0023The method may comprise generating using a predictor configured to receive the n most probable targets and their associated probabilities text predictions having probability values. Preferably, the method comprises generating using a predictor configured to receive the word fragments and their associated probabilities text predictions having probability values. The method may comprise selecting a text prediction and matching using the predictor the target(s) of the text prediction to the corresponding input event(s). The matching of the target(s) of the text prediction to the corresponding input event(s) may comprise pairing the targets which are tagged to the word fragments with the input events. Alternatively, the matching of the target(s) of the text prediction to the corresponding input event(s) may comprise reverse mapping the word fragments to their targets and pairing the targets with the input events.

0024The method may further comprise updating a model using a model updater when an input event has been matched to a target.

0025The present invention will now be described in detail with reference to the accompanying drawing, in which:

0026<figref idref="DRAWINGS">FIG. 1</figref> is a schematic of a system architecture according to the invention.

0027The invention provides a system and method that utilises machine learning to model user interactions on a virtual keyboard. The three major activities of the system, in conjunction with a predictor, are evaluation, inference, and learning, and the system is structured around an iterative application of those activities. The system of the present invention can be incorporated into an electronic device, for example a PDA, a mobile phone or a computer.

0028Elements of the system will now be described with reference to <figref idref="DRAWINGS">FIG. 1</figref>.

0029The system of the present invention provides a user interface comprising a plurality of targets and being configured to receive user input. In the example provided in <figref idref="DRAWINGS">FIG. 1</figref>, the user interface comprises a virtual keyboard <b>1</b>, e.g. a keyboard on a softscreen. The system is configured to interpret the user input as either an input event <b>10</b> or a selection event <b>20</b>. An input event <b>10</b> is an event in which a user selects (e.g. by ‘touch’ or ‘click’) a location in 2D space on the virtual keyboard, this event being detected by the virtual keyboard <b>1</b> and represented as Cartesian coordinates. A selection event <b>20</b> is the selection by a user of a prediction <b>18</b> from a set of predictions displayed to the user. The virtual keyboard <b>1</b> may have input event regions and selection event regions to distinguish between an input event <b>10</b> and a selection event <b>20</b>. However, there are other ways to interpret the user input as selection or input events, e.g. a selection event <b>20</b> may correspond to a different gesture on the keyboard (such as a swipe across the screen) to an input event <b>10</b> (which could correspond to, for example, a touch of the screen).

0030An input event <b>10</b> is not limited to being represented by Cartesian coordinates, but can also be represented by other variables such as time since the last key press, key press pressure, gesture information (the path traced by a touch on a softscreen keyboard), accelerometer readings etc.

0031For a soft keyboard, a selection event <b>20</b> relates to a user selecting the intended prediction by touching/clicking an area on the keyboard which displays that prediction, thus entering the prediction into the system. A selection event <b>20</b> may also relate to the automatic selection by the system of the most probable prediction when the user ‘hits’ ‘space’ to complete a word. There are other mechanisms for user selection of a prediction, for example a gesture on a soft keyboard such as a swipe-right across the screen can be a mechanism for inserting the most probable prediction. The selected prediction <b>20</b> corresponds to the character sequence a user intended to enter through the input events <b>10</b>. Thus, by entering a selection event <b>20</b>, the input events <b>10</b> entered by a user can be matched to their intended targets, as will be explained in more detail below.

0032The only requirement for the virtual keyboard <b>1</b> is that there are distinct ‘target points’ for the user, which correspond to intended input. The target points could be, but are not limited to, character keys (i.e. a grid of virtual or physical keys, as in normal qwerty keyboards); an arrangement of letter glyphs, e.g. as a grid with no visible key boundaries; or a linear letter line, A-Z. Thus, each target of the virtual keyboard <b>1</b> can represent single or multiple characters, or any other item of information for user selection. For the following examples, the focus is on text entry into a system. However, the system and method is not limited to the entry of text and is applicable to the entry of non-text data, where quanta of data are represented by target points on a user interface.

0033To generate predictions for presentation to a user, the system comprises a plurality of models <b>6</b> which model the user's previous input events for each of the plurality of targets; an input probability generator <b>2</b> which queries the plurality of models <b>6</b> with a given input event <b>10</b> and generates one or more likely targets and their probabilities; and a predictor <b>4</b> which generates text predictions <b>18</b> from the likely targets and their probabilities. In a preferred example, the system further comprises a word fragment map <b>3</b> which maps the likely targets to word fragments which are used by the predictor <b>4</b> to generate text predictions.

0034The input probability generator <b>2</b> receives an input event <b>10</b> and generates or updates a Target Sequence intention Structure <b>12</b>. The Target Sequence Intention Structure <b>12</b> contains one or more targets and for each target the probability that the user had intended to select that target through the input event <b>10</b>. The Target Sequence Intention Structure <b>12</b> contains a correspondence between the input event <b>10</b> and the targets corresponding to that input event <b>10</b>, for example by tagging the targets with the input event <b>10</b>. The Target Sequence Intention Structure <b>12</b> can contain all of the targets of the system or it can contain only the targets which have an associated probability higher than a certain threshold probability value. The threshold value is a system parameter, that can be set empirically to a pre-defined level (e.g. 10⁻⁴). Alternatively, the threshold level might be determined by experiments with the user. As discussed in more detail below, to generate a probability of observing an input event <b>10</b> for a target, the input probability generator <b>2</b> queries a model set <b>6</b> with an input event <b>10</b>, and evaluates for each target a probability value, which can be represented as a per-event probability vector. To reduce the computation, small values can be filtered out of the per-event probability vector. These per-event probability vectors are concatenated to form the Target Sequence Intention Structure <b>14</b>, which forms the input to the next stage: target mapping <b>3</b>.

0035The model set <b>6</b> comprises a plurality of trained models representing the plurality of targets (which may be characters) of the system. A target is modelled as a distribution which models the user's actual input if he was ‘targeting’ that target. The distribution that is being modelled is p(x|c), where x is an input event position vector, and c is a label identifying a single target (a target identifies a set of possible intended characters).

0036In a preferred embodiment, this distribution is modelled as a multivariate Gaussian, p(x|c,<img file="US2014108994A1_D0001.tif" />)=G (x;μ_g,Σ_c), where <img file="US2014108994A1_D0002.tif" /> is the assumed model (encompassing all assumptions and parameters and G(x;μ,Σ) is shorthand for the Gaussian probability density function, mean μ, covariance Σ, evaluated at x. The model parameters are μ_c, and Σ_cfor each target c. The model parameters are learnt using maximum a-posteriori (MAP) estimation based on historical interaction with the keyboard. However, other learning mechanisms can be used, some of which are discussed later.

0037Rather than using a 2D Gaussian, the user's input can be modelled by independently distributing the x and y co-ordinates of the user's input events with a Laplace distribution. Alternatively, the user input can be modelled with a Gamma distribution. Laplace and Gamma distributions may be more appropriate than a Gaussian distribution because the distributions are more heavy-tailed, with the probability density decaying more slowly than that of a Gaussian as the input event (e.g. touch location) moves away from a target. Such heavy-tailed distributions may reflect the user's actual writing style more accurately, thus providing, potentially, better error correction performance. Other suitable modelling techniques can also be applied.

0038In order to obtain the MAP estimate for μ_c,Σ_c, a prior distribution of those parameters must be specified. Where the targets relate to keys on a virtual keyboard, the priors (mean and covariance) can be set empirically based on a keyboard layout, a convenient choice for which is the normal inverse Wishart distribution, NIWD, as this is the conjugate prior of a Gaussian with unknown mean and covariance. Other prior distributions can be used, some of which are discussed later. The definition of conjugate priors states that if the prior is conjugate to the likelihood, the posterior is the same form of distribution as the prior (potentially with different parameters). The parameters of the conjugate distribution (both prior &amp; posterior) are then termed hyperparameters (as they parameterize the distribution of the model's actual parameters), and MAP learning can be made into a relatively simple hyperparameter recalculation.

0039Thus, in an embodiment, learning simply entails recalculating the four NIWD parameters, an algorithm that is easily made incremental. The prior is therefore:

0000<br /><i>p</i>(μ_c,Σ_c|<img file="US2014108994A1_D0003.tif" />)=NIWD(μ_c,Σ_c;α_c^prior,β_c^prior,{circumflex over (μ)}_c^prior,{circumflex over (Σ)}_c^prior),

0000and the posterior is:

0000<br /><i>p</i>(μ_c,Σ_c<i>|{x</i>_i}_{i=1 . . . t},<img file="US2014108994A1_D0004.tif" />)=NIWD(μ_c,Σ_c;α_c^(t),β_c^(t),{circumflex over (μ)}_c^(t),{circumflex over (Σ)}_c^(t)),

0000where α_cand β_care degrees-of-freedom hyperparameters for the mean and covariance respectively (a large degrees-of-freedom value means that the prior is strong, and learning is slow), and {circumflex over (μ)}_c,{circumflex over (Σ)}_care the modal values of the mean and covariance respectively. α_c^(t)is the posterior value of the hyperparameter α_c, after t observations, {x_i}_{i=1 . . . t}, therefore α_c⁽⁰≡α_c^prior.

0040Working through the known hyperparameter update relations for the NIWD distribution, the general update rules for this parameterization are:

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mfrac><mrow><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mover><mi>x</mi><mi>_</mi></mover></mrow><mo>+</mo><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo></mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mrow><mrow><mi>n</mi><mo>+</mo><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mfrac></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><msubsup><mover><mi>Σ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mfrac><mrow><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mrow><mi>X</mi><mo>+</mo><mover><mi>X</mi><mi>_</mi></mover></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo></mo><msubsup><mover><mi>Σ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mrow><mrow><mi>n</mi><mo>+</mo><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mfrac></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mi>where</mi><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mi>X</mi><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><mrow><mrow><mo>(</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>-</mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mo></mo><msup><mrow><mo>(</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>-</mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mi>T</mi></msup></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mover><mi>X</mi><mi>_</mi></mover><mo>=</mo><mrow><mfrac><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi></mrow></mfrac><mo></mo><mrow><mo>(</mo><mrow><mover><mi>x</mi><mi>_</mi></mover><mo>-</mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mo></mo><msup><mrow><mo>(</mo><mrow><mover><mi>x</mi><mi>_</mi></mover><mo>-</mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow><mo>)</mo></mrow><mi>T</mi></msup></mrow></mrow><mo>,</mo></mrow></math></maths>

0000where there are n observations, {x_i}_{i=1 . . . n}, with mean <o ostyle="single">x</o>. When applied to the prior, using all observations, this provides a batch-learning algorithm. An incremental learning algorithm can be formed by setting n=1, and reapplying the update formula to the posterior, i.e. α_c^(t+1)=α_c^(t)+1.

0041As the mode of the NIWD is ({circumflex over (μ)},{circumflex over (Σ)}), the MAP estimate of the parameters after t observations is simply: μ_c={circumflex over (μ)}_c^(t), Σ_c={circumflex over (Σ)}_c^(t).

0042The NIWD is convenient because it is conjugate of the multivariate Gaussian, which gives simple and incremental learning rules. As an alternative, it is possible to use a uniform (uninformative) prior. A prior can be specified where the position and convariance are independent, e.g. the prior for position could be a Gaussian or uniform, and that for covariance could be the ‘matrix normal distribution’.

0043The present example uses batch-mode and incremental learning algorithms, which compute the posterior in a single update from the prior, and by adding one observation at a time respectively. One of these learning algorithms runs when the user ‘selects’ a prediction by matching the locations of input events to the locations of characters which make up the selected prediction.

0044If a Laplace/Gamma distribution is chosen instead of a Gaussian distribution, the same process is followed as for the Gaussian: a prior is chosen (for example the conjugate prior) and learning rules are derived for the MAP learning goal.

0045As an alternative to MAP, Maximum Likelihood (ML) estimation is another choice for a learning mechanism, where the prior does not come into it, and the parameters are chosen such that the likelihood of observing the training data under the model is maximised. A further possibility would be to use a true Bayesian estimator (neither the ML nor MAP approaches are truly Bayesian because they both make point estimates), in which an integral is computed over all possible values of the posterior and the mean or median used for inference decisions. Disadvantageously these estimates are relatively costly to compute, and therefore currently less attractive for constrained resource environments. Examples of Bayesian estimators are Variational Bayes and Gibbs sampling.

0046The above described learning algorithm is a learning algorithm that accounts for each datapoint equally, whether recent or old, with a prior which is (intentionally) overwhelmed once a certain number of datapoints have been observed. In order to add a basic form of recency into the model, and some outlier tolerance by continually reinforcing the prior, two alterations can be made:

0047The first is simply to limit the degrees-of-freedom parameters α_c, β_c, which has the effect of ‘forgetting’ old observations, and limiting how ‘rigid’ the model becomes (a ‘rigid’ model has such a high degrees-of-freedom value that new datapoints have very little effect). The limit is applied by not updating them if they would exceed the limit (an action which Should not compromise the action of the other hyperparameter updates).

0048The second is to feed the other prior hyperparameters, {circumflex over (μ)}_c^priorand {circumflex over (Σ)}_c^prior, back into the update equations, such that they continue to have an effect even after many datapoints have been observed. This can be done relatively simply as the update equations are simply weighted averages of a few quantities, so it is reasonable to ‘add in’ some quantity of the prior, as follows:

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mi>min</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi></mrow><mo>,</mo><msub><mi>α</mi><mi>cmax</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><mi>min</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi></mrow><mo>,</mo><msub><mi>β</mi><mi>cmax</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mfrac><mrow><mrow><mi>n</mi><mo></mo><mrow><mo>[</mo><mrow><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mi>δ</mi></mrow><mo>)</mo></mrow><mo></mo><mover><mi>x</mi><mi>_</mi></mover></mrow><mo>+</mo><mrow><mi>δ</mi><mo></mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mi>prior</mi></msubsup></mrow></mrow><mo>]</mo></mrow></mrow><mo>+</mo><mrow><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo></mo><msubsup><mover><mi>μ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mrow><mrow><mi>n</mi><mo>+</mo><msubsup><mi>α</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mfrac></mrow></mrow></math></maths><maths id="MATH-US-00002-2" num="00002.2"><math overflow="scroll"><mrow><mrow><msubsup><mover><mi>Σ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mrow><mi>t</mi><mo>+</mo><mi>n</mi></mrow><mo>)</mo></mrow></msubsup><mo>=</mo><mfrac><mrow><mrow><mi>n</mi><mo></mo><mrow><mo>[</mo><mrow><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mi>ɛ</mi></mrow><mo>)</mo></mrow><mo></mo><mrow><mo>(</mo><mrow><mi>X</mi><mo>+</mo><mover><mi>X</mi><mi>_</mi></mover></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>ɛ</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msubsup><mover><mi>Σ</mi><mo>^</mo></mover><mi>c</mi><mi>prior</mi></msubsup></mrow></mrow><mo>]</mo></mrow></mrow><mo>+</mo><mrow><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup><mo></mo><msubsup><mover><mi>Σ</mi><mo>^</mo></mover><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mrow><mrow><mi>n</mi><mo>+</mo><msubsup><mi>β</mi><mi>c</mi><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msubsup></mrow></mfrac></mrow><mo>,</mo></mrow></math></maths>

0049The additional parameters α_cmax, β_cmax, δ and ε may be set empirically, as required. They control the ‘asymptotic strength’ of the prior, and the rate at which past observations are forgotten.

0050A single virtual keyboard <b>1</b> may need to maintain multiple separate target model sets <b>6</b>, for example if a single system may be used by different users, or if the form factor of the virtual keyboard is variable. In some cases (e.g. a form factor change), the system may have sufficient information to explicitly choose a different input model, but in the case of multiple users, the appropriate model choice may not be obvious. In this situation, an element of model selection can assist.

0051A robust way to perform model selection, is to evaluate the data likelihood over a number of samples. This can be achieved as follows, where data likelihood is expressed as:

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>ℒ</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mrow><mo>{</mo><msub><mi>x</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mrow><mn>1</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>n</mi></mrow></mrow></msub><mo>|</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>|</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths>

0000where <img file="US2014108994A1_D0005.tif" />(D|<img file="US2014108994A1_D0006.tif" />) is the likelihood of observing the data D under the model <img file="US2014108994A1_D0007.tif" />. This can be written as,

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>ℒ</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mrow><mo>{</mo><msub><mi>x</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mrow><mn>1</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>n</mi></mrow></mrow></msub><mo>|</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><mrow><mi>log</mi><mo></mo><mrow><munder><mo>∑</mo><mi>j</mi></munder><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>,</mo><mrow><msub><mi>c</mi><mi>j</mi></msub><mo>|</mo><mi>ℳ</mi></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>ℒ</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mrow><mo>{</mo><msub><mi>x</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mrow><mn>1</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>n</mi></mrow></mrow></msub><mo>|</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><mi>const</mi><mo>+</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><mrow><mi>log</mi><mo></mo><mrow><munder><mo>∑</mo><mi>j</mi></munder><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>|</mo><msub><mi>c</mi><mi>j</mi></msub></mrow><mo>,</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths>

0000where the prior over targets, p(c|<img file="US2014108994A1_D0008.tif" />), may be extracted into a constant if we assume it is uniform.

0052This log-likelihood statistic can be computed by querying multiple models at the Input probability generator stage at once, summing the output over all targets, and selecting the model for which the calculated log-likelihood of some ‘seed input’ is highest.

0053The model presented up to this point has incorporated the assumption that each key-press in a sequence is independent of all others, an assumption that is clearly inaccurate (the distribution of input for a certain key is probably quite strongly dependant on the last character entered). A first-order Markov assumption might be more appropriate: that the current character input is conditionally independent of all previous characters, given just the last character entered. The probability of an entire input sequence would then be:

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mrow><mo>{</mo><msub><mi>x</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mrow><mn>1</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>t</mi></mrow></mrow></msub><mo>|</mo><msub><mrow><mo>{</mo><msub><mi>c</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mrow><mn>1</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>t</mi></mrow></mrow></msub></mrow><mo>,</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>x</mi><mn>1</mn></msub><mo>|</mo><msub><mi>c</mi><mn>1</mn></msub></mrow><mo>,</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>2</mn></mrow><mi>n</mi></munderover><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>|</mo><msub><mi>c</mi><mi>i</mi></msub></mrow><mo>,</mo><msub><mi>x</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>ℳ</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths>

0000where all tens are as previously described above. A critical modelling decision is then to assume a form for the conditional probability of a touch location, p(x_i|c_i,x_i-1, <img file="US2014108994A1_D0009.tif" />). One choice of distribution would first classify the previous touch location, x, with a separate Gaussian for each target and class of previous input location. Another possible choice would be to use the distance traveled, d=∥x_i−x_i-1∥, to control the variance of the per-target input distribution. The form of this distribution should be chosen to model typical data collected from virtual keyboard users.

0054A model set <b>6</b> can be i) queried by the input probability generator <b>2</b> to return the current MAP estimate of the model parameters; and ii) trained by an input model updater <b>5</b> in order to update the models in response to a selection event.

0055Model parameters may be stored on a per-key basis, or (in the case of covariance), shared among multiple keys. In the example described, each key/target has a position and covariance value. The alternative is to provide each key with a location, but force keys to share a covariance—when any of the keys are trained, the same covariance is trained. The exact representation of the parameters is flexible; it may be, for example, more convenient to store the precision matrix rather than the covariance, as this does not require a matrix inversion during probability generation, but does require an inversion in the less frequent case of model training.

0056Thus, given an input event <b>10</b>, the input probability generator <b>2</b> generates a probability p(x|c, <img file="US2014108994A1_D0010.tif" />), for each target c, that the user had intended to select that target by the input event <b>10</b>. To generate the probability value for a given target, the input probability generator <b>2</b> queries the model for that target to return the current MAP estimate of the model parameters, μ_c,Σ_c. The input probability generator <b>2</b> then uses the model parameters to calculate the value of the Gaussian probability density function, G(x;μ,Σ), evaluated at the input location x. The calculated probability value can be represented as a per-event probability vector, which can be concatenated to form part of the Target Sequence Intention Structure <b>14</b>.

0057In a preferred embodiment, the system further comprises a target mapping stage <b>3</b>. The target mapping stage <b>3</b> comprises a word fragment map which provides a mapping from target inputs to word fragments (usually one or two characters) that can be used to build predictions. This mapping is applied independently to each element in the Target Sequence Intention Structure <b>12</b> in order to convert it into an Input Sequence Intention Structure <b>16</b>. The word fragment map maintains a mapping from a target (a location on a keyboard, an abstraction of a key) to one or more word fragments (portions of a word that the user wants to enter). In the simplest case, each target refers to a single word fragment (e.g. when typing English on a full qwerty keyboard). Where there are alternative characters associated with each key (e.g. French accented characters or where each key represents multiple characters), those characters may be added as additional word fragments. The probabilities corresponding to each target may additionally be discounted by some factor for each alternative word fragment. The sets of possible word fragments and probabilities for each event in the sequence are then assembled into an Input Sequence Intention Structure <b>16</b>.

0058The target mapping stage <b>3</b> also maps the word fragments of a selected prediction <b>20</b> back to their corresponding target events. In a preferred embodiment, each of the word fragments is tagged with the target from which it came to allow the pairing by a predictor <b>4</b> of a target to its touch location when a selection event has occurred. This can be achieved by tagging each word fragment with its corresponding target and input event. Thus, to un-map is a trivial pairing of touch-locations and targets. However, instead of tagging the word fragments, the system can use other mechanisms to map the word fragments of a selected prediction <b>20</b> back to their corresponding target events. For example, in an alternative embodiment, the target mapping stage <b>3</b> comprises a reverse mapping of the word fragments of a selected prediction back to their corresponding targets. To achieve the reverse mapping the selected prediction <b>20</b> and the corresponding string of input events are passed to a splitting mechanism. The splitting mechanism may split the prediction <b>20</b> into word fragments by evaluating the combination of word fragments with the highest probability for that selected prediction <b>20</b>. The word fragments are then reverse mapped at the target mapping stage <b>3</b> to their targets and paired with the string of input events. In the simplest implementation of such a mechanism, the word fragments comprise single characters and the splitting mechanism splits the prediction into single characters to be mapped back to the targets. In this situation, the splitting may be carried out by the predictor <b>4</b>.

0059To generate text (or similar) predictions <b>18</b>, the system comprises a predictor <b>4</b>. A predictor <b>4</b> is a device which, given some input, which in this case comprises an Input Sequence Intention Structure <b>16</b> containing a sequence of sets of ‘word fragments’ and probabilities, generates a set of predictions <b>18</b>. Each prediction <b>18</b> consists of a text string, i.e. a term or phrase (denoted by s_i) and a probability value, denoted by p_i. The set of predictions is therefore of the form {(s_—1, p_—1), (s_—2, p_—2) . . . (s_n, p_n)}, where there are n predictions in a set.

0060As one skilled in the art will understand, any type of predictor <b>4</b> and any number of predictors <b>4</b> can be used to generate text predictions in a text prediction system. Preferably, the predictor <b>4</b> generates text predictions <b>18</b> based on the context of the user inputted text, i.e. the predictor <b>4</b> generates text predictions <b>18</b> for the nth term, based on up to n−1 terms of context. Here, “context” denotes both the terms that have occurred previously in the sequence, as well as any knowledge the system has about the current term (e.g. the likely word fragments contributing to the term). Given a particular context, the system predicts the words that are most likely to follow by using estimates of probabilities. The predictions <b>18</b> can be generated by a multi-language model as well as a single language model predictor.

0061A thorough description of the use of a predictor (single and multi-language model) to generate text predictions is presented in international patent application publication number WO2010/112841, “System and method for inputting text into electronic devices”, which is incorporated herein by reference in its entirety. Furthermore, a thorough description of the use of an adaptive predictor (single and multi-language model) to generate category-weighted text predictions is presented in international patent application number PCT/GB2010/001898, “System and method for inputting text into electronic devices”, which is incorporated herein by reference in its entirety.

0062The predictor <b>4</b> of the system receives as its input an input Sequence Intention Structure <b>16</b> containing a sequence of sets of ‘word fragments’ and probabilities, and generates a set of predictions <b>18</b> which are displayed to the user. The predictor <b>4</b> may be configured to return matches for which the Input Sequence intention Structure <b>16</b> completes an entire word or return likely words of which the Input Sequence Intention Structure <b>16</b> is a prefix, e.g. in the case where the Input Sequence Intention Structure comprises the word fragments t and o and the word may be predicted as ‘to’ (completing the word) or ‘together’ (the word fragments are a prefix for the word). The Input Sequence Intention Structure <b>16</b> need only be used as a guide; it may, for example, add additional characters as if the user has missed some or ignore characters as if the user has entered extra characters. A single path through the Input Sequence Intention Structure <b>16</b> must be identified by each prediction <b>18</b>, so that an association can be made between input events and targets. Each target has already been mapped by the word fragment map at the target mapping stage <b>3</b> to one or more word fragments, depending on language, which are unique. Furthermore, in the preferred embodiment, the Input Sequence Intention Structure <b>16</b> stores the tagging of the word fragments to their targets and input events. Thus, the selection of a prediction provides a correspondence between input events <b>10</b> and targets, because the predictor <b>4</b> tracks the targets used to compose the prediction, via the tagging of the word fragments with their corresponding targets. In an embodiment in which the unmapping comprises a reverse mapping, a splitting mechanism splits the selected prediction <b>20</b> into a combination of word fragments and the word fragment map is used to provide a reverse mapping of the word fragments to their corresponding targets. Each target is then paired with its respective input event <b>10</b>.

0063The system also comprises an input model updater <b>5</b>. The input model updater <b>5</b> receives input event to target correspondences <b>14</b> in response to a selection event <b>20</b>. The selection event <b>20</b> identifies the targets which the user had intended to input and thus allows the predictor <b>4</b> to match the targets to the input events <b>10</b>. The input model updater <b>5</b> updates the appropriate models, preferably (for memory usage and efficiency) using the incremental variant of the learning algorithm. The input model updater <b>5</b> applies the incremental learning update rules to the plurality of models in response to each selection event <b>20</b> on the virtual keyboard <b>1</b>. The input is a set of input locations paired with targets {(x_i, c_i)}_{i=1 . . . k}, each of which can be used as a single training point, x_i, for a single target, c_i. The prior hyperparameters and learning parameters are all set to fixed values—these set the initial target positions and expected accuracy, as well as controlling the speed at which learning takes place. Each model can be considered in isolation. By doing so, the training data is required to be labelled, i.e. input events require association with target labels. The labelling is not provided in the data, which is a stream of input events <b>10</b> and targets, so must be inferred from selection events <b>20</b>. As described previously, one way of associating input events <b>10</b> with targets is to tag the word fragments with their targets and input events <b>10</b> in the Input Sequence Intention Structure <b>16</b>. Once a prediction is selected, the word fragments making up the prediction are known. Thus, the targets tagged to the word fragments can be paired to the input events, providing labelled training data. Alternatively, the targets of a selected prediction can be determined by reverse mapping word fragments to their targets at the target mapping stage <b>3</b>. The targets so determined can then be paired to the input events <b>10</b>.

0064Thus, the present invention provides a system which models user input events for a plurality of targets and updates those models with user input, to provide a system which is able to more accurately predict which character the user intends to input given an input event and thus provide more accurate text predictions.

0065The use of the present system will now be described by way of a non-limiting example. A user interacts with a continuous coordinate system of a virtual keyboard <b>1</b> by entering input, for example by touching a location on a touch-sensitive keyboard <b>1</b>. The user touches a location on the keyboard <b>1</b> with the intent of entering a target displayed on the keyboard <b>1</b>. The keyboard <b>1</b> builds up a stream of input events <b>10</b> (which in the present example are Cartesian coordinates representing the locations of the touches on the keyboard) which is passed to an input probability generator <b>2</b>.

0066The input probability generator <b>2</b> generates or updates a Target Sequence Intention Structure <b>12</b>. In the instance where the targets of the keyboard represent characters, the Target Sequence Intention Structure <b>12</b> contains one or more characters corresponding to the most likely characters the user had intended to input when the touched the screen. Associated with each of the characters is a probability that the user had intended to enter that character When he touched the screen at the location and a tag to the input event <b>10</b>. To generate the Target Sequence Intention Structure <b>12</b> the input probability generator <b>2</b> calculates the probability that the user had intended to enter each of the one or more characters by querying the associated model for each character with the input event <b>10</b>. As discussed above, each model models the user's historical interaction with the keyboard for that character, i.e. it models the user's previous input events for that character. The input probability generator <b>2</b> then, preferably, retains the characters with an associated probability above a threshold probability value, where the threshold value is set empirically to a pre-defined level (e.g. 10⁻⁴) or is determined by experiments with the user.

0067The Target Sequence Intention Structure <b>12</b> is passed to a word fragment map which maps each character of the Target Sequence Intention Structure <b>12</b> to one or more word fragments with associated probabilities, thus generating an Input Sequence Intention Structure <b>16</b>. Each character of the one or more characters is independently mapped to one or more word fragments, where the word fragments are tagged with the characters from which they came. The probabilities associated with the word fragments need not be the same as the probability associated with the character. For example, when mapping, the probability associated with a character may be multiplied by an additional factor dependent on the word fragment. The word fragment map may be a fixed map stored in a memory of the system. The map varies with the language used, e.g. the punctuation will differ with the chosen language and accented characters, umlauts etc. may feature in the word fragments dependent on the chosen language of the system.

0068Preferably, the word fragment map comprises targets mapped to word fragments, where the word fragments are tagged with the targets from which they came.

0069The Input Sequence Intention Structure <b>16</b> contains the word fragments, preferably tagged to the characters and input events from which they came, and probabilities corresponding to a sequence of input events <b>10</b>. From the Input Sequence Intention Structure <b>16</b>, the predictor <b>4</b> generates a number of predictions <b>18</b> by identifying a single path through the Input Sequence Intention Structure <b>16</b> for each prediction <b>18</b>, i.e. by passing through the word fragments and generating a prediction sequence comprising a single word fragment for each of the input events <b>10</b>. By identifying a single path through the Input Sequence Intention Structure <b>16</b>, an association <b>14</b> can be made between input events <b>10</b> and targets. The predictor considers a number of the most probable paths through the Input Sequence Intention Structure <b>16</b>, optionally also considering all words for which that path is a prefix. This is then fed into an n-gram language model to give an ordering of prediction candidates. An implementation of this process is described in international patent application publication number WO2010/112841, which is hereby incorporated by reference in its entirety.

0070The virtual keyboard <b>1</b> may be configured to display the predictions generated by the predictor. The selection <b>20</b> of the correct prediction can be achieved by either user selection of a given prediction displayed to the user or auto-accepting by the system of the most probable prediction. The predictor <b>4</b> is configured to track via the Input Sequence Intention Structure <b>16</b> which word fragments are used to compose a prediction, so that, upon user selection <b>20</b>, the input events <b>10</b> are matched <b>14</b> to their targets. If the Input Sequence Intention Structure <b>16</b> comprises the word fragments tagged with their targets, the predictor <b>4</b> is configured to track the target tags, such that matching input events <b>10</b> to their targets comprises pairing the input events <b>10</b> to their targets. Alternatively, the word fragments are first matched to their corresponding targets by reverse mapping at the target mapping stage <b>3</b>, before these targets are paired with the input events <b>10</b>. The input events <b>10</b> paired with their targets are forwarded to the input model updater <b>5</b>, which updates the relevant models of the set of models <b>6</b>.

0071An example is now discussed, to illustrate the functioning of the system. In the example, a user is trying to enter the word “it's” on a virtual keyboard <b>1</b> (qwerty layout).

0072The user touches the screen very near to the first character T. The virtual keyboard <b>1</b> generates an input event <b>10</b> (e.g. Cartesian coordinates) representing that location, and sends it to the input probability generator <b>2</b>.

0073The input probability generator <b>2</b> evaluates all of the target models <b>6</b>, computing how likely they are to correspond to this input event. The input probability generator filters out low-probability targets by retaining only those with a probability above a predetermined threshold (which is set empirically or through experiment with the user). In the present example, the resulting Target Sequence Intention Structure <b>12</b> is [(@I, 1.0), (@O, 0.2), (@U, 0.2), (@K, 0.15), (@J, 0.1)], where @I is the target corresponding to the character ‘i’.

0074The target mapping stage <b>3</b> transforms each target into a number of alternative word fragments, e.g. @I→i, ï, ′i. The target mapping stage <b>3</b> maps targets to word fragments and tags each word fragment with the target from which it came. The resulting Input Sequence Intention Structure <b>16</b> is: [(i, 1.0; @I), (ï, 1.0; @I), (′i, 1.0; @I), (o, 0.2; @O), (′o, 0.2; @O), (ö, 0.2; @O), (ó, 0.2; @O), . . . ]

0075The predictor <b>4</b> then uses this, and any available word context, to generate predictions <b>18</b> to be fed back to the user. The predictor <b>4</b> might, for example, predict: [“I”, “I'm”, “in”].

0076The user then makes a second touch event, quite far from the second character ‘t’, actually closer to ‘r’. The virtual keyboard <b>1</b> sends both touch events <b>10</b> (‘i’ &amp; ‘t’) to the input probability generator <b>2</b>.

0077The input probability generator <b>2</b> now generates a sequence of probability vectors: {[(@I, 1.0), (@O, 0.2), . . . ], [(@R, 0.8), (@T, 0.6), (@E, 0.1), . . . ]}

0078The target mapping stage <b>3</b> is applied to each event in the sequence independently, with the word fragments tagged to their targets: {[(i, 1.0; @I), (ï, 1.0; @I), . . . ], [(r, 0.8; @R), (′r, 0.8; @R), (t, 0.6; @T), . . . ]}

0079The predictor <b>4</b> makes predictions <b>18</b>: [“it”, “it's”, “or”] which are displayed to the user. The predictions may be displayed by the virtual keyboard. The user selects the prediction “it's”. The virtual keyboard <b>1</b> creates a selection event <b>20</b> and the predictor matches the two touch events <b>10</b> to the targets of the prediction <b>18</b>. The un-mapping stage is a trivial pairing of touch-locations and targets, because the system keeps track of the list of targets and input events that make up each prediction via the tagging of the word fragments with their targets and input events.

0080The predictor <b>4</b> pairs the locations at which the user touched the screen to their targets (touch-1→@I), (touch-2→T). The input model updater <b>5</b> then updates the model for @I, which will likely be tightened (as the first touch event was very accurate), and the model for @T, which will likely be loosened (as the second touch event was not as accurate).

0081The above example relates to a target representing a single character. However, a target may represent multiple characters. If a target represents multiple characters e.g. A/B/C, the model for that target models the user input events corresponding to the target A/B/C. Where the selected prediction <b>18</b> comprises A, B or C, the target A/B/C is mapped back to the input event.

0082By modelling a user's historical interaction with a virtual keyboard, the present method is able to accurately predict the characters which the user had intended to enter when touching the screen.

0083It will be appreciated that this description is by way of example only; alterations and modifications may be made to the described embodiment without departing from the scope of the invention as defined in the claims.