Patent Publication Number: US-9899019-B2

Title: Systems and methods for structured stem and suffix language models

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to U.S. Provisional Patent Application Ser. No. 62/134,891, filed Mar. 18, 2015, entitled “SYSTEMS AND METHODS FOR STRUCTURED STEM AND SUFFIX LANGUAGE MODELS”. The content of the aforementioned application is hereby incorporated by reference in its entirety for all purposes. 
    
    
     BACKGROUND 
     The present application relates generally to word predictions and, more specifically, to improving the accuracy of word predictions for highly inflected languages. 
     Electronic devices and the ways that users interact with them are evolving rapidly. Changes in size, shape, input mechanisms, feedback mechanisms, functionality, and the like have introduced new challenges and opportunities relating to how a user enters information, such as text. Statistical language modeling may play a central role in input prediction and/or recognition, such as keyboard input prediction and speech (or handwriting) recognition. Effective language modeling may thus play a critical role in the overall quality of an electronic device as perceived by the user. 
     However, to achieve acceptable levels of coverage and robustness, language models may require extensive training on very large text databases. As a result, it may be burdensome or impractical to gather and/or store sufficiently large amounts of training data for use in effectively training the language models. Relatedly, due to the finite size of such databases, many occurrences of word strings may be seen infrequently, yielding unreliable prediction results for all but the smallest word strings. 
     Further, the sizes of resulting language models may exceed what can reasonably be deployed onto portable electronic devices. Though it may be possible to prune training data sets and/or language models to an acceptable size, pruned models may have reduced predictive power and accuracy. Additionally, grammatically incorrect predictions are particularly problematic, as poor predictions often may be more distracting than the lack of a prediction. 
     SUMMARY 
     A compact and robust language model that may provide accurate input prediction and/or input recognition is desirable. Systems, apparatuses, and methods are disclosed for predicting words using structured stem and suffix language models that may take into consideration at least two suffix types (e.g., person and tense) in addition to a stem, and thereby improve word predictions to grammatically valid combinations. 
     In some aspects, the systems and methods may include receiving an input from a user at an electronic device. Using a first n-gram word language model (e.g., a word stem language model), a first probability of a stem may be determined based at least on a first portion previously-input word in the received input. In addition, using a second n-gram language model (e.g., person suffix n-gram language model), a second probability of a first suffix may be determined based at least on a second portion of the previously-input word in the received input. Further, a third probability of a second suffix different from the first suffix may be determined using a third n-gram language model (e.g., tense suffix n-gram language model) based at least on a third portion of the previously-input word in the received input. 
     An integrated or fourth probability of at least one predicted word may be determined based on the probabilities determined by the first n-gram language model, the second n-gram language model, and the third n-gram language model. One or more candidate words—for example, the most probable word, out of multiple predicted words, based on integrated probabilities—may be determined. The one or more candidate words may be provided as an output to the user (e.g., displayed and/or played-back). A graphical user interface may allow the user to select a candidate word without having to manually input the entire word. As such, the efficiency of the user device interaction and the overall user experience may be improved. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example system for determining word predictions based on a structured stem and suffix language model. 
         FIG. 2  illustrates an example method for determining word predictions based on a structured stem and suffix language model. 
         FIG. 3  illustrates a further example method for determining word predictions based on a structured stem and suffix language model. 
         FIG. 4  illustrates a functional block diagram of an electronic device configured to determine word predictions based on a structured stem and suffix language model. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description, reference is made to the accompanying drawings in which it is shown by way of illustration specific examples that can be practiced. It is to be understood that other examples can be used and structural changes can be made without departing from the scope of the various examples. 
     The present aspects generally relate to word predictions for highly inflected languages. It may be beneficial for an electronic device to provide predictive text input based on input already entered by a user. For example, as a user enters text into a draft e-mail message, the electronic device may suggest potential subsequent words for user selection to reduce the amount of manual typing. Based on the user&#39;s previous input, the electronic device may determine possible next words using word n-gram language models, and determine probabilities of different possible next words. One or more of the possible next words—such as a subset having the highest predictions probabilities—can be displayed on-screen for user selection. In this way, the electronic device may permit user entry of one or more words without requiring the user to manually enter each and every character or letter of each word. 
     One of the main drivers affecting coverage of language models, and n-gram language models in particular, may be word inflection. The occurrence of word inflection raises certain challenges in the context of word predictions using word n-gram language models. Word inflection may refer to the modifying of words to encode grammatical information such as, but not limited to, tense, person, number, gender, mood, voice, aspect, and/or case. In many languages, complex verb conjugation and gender declension leads to multiple inflected forms for each lemma. A lemma may be a word that stands at the head of a definition in a dictionary (or citation). For instance, a lemma may be a base word and its inflections. 
     For example, English inflects regular verbs for past tense using the suffix “_ed” (as in “talk”→“talked”). Other languages can exhibit higher levels of word inflection: Romance languages such as French have more overt inflection due to complex verb conjugation and gender declension. Agglutinative languages (e.g., Finnish and Turkish) may be considered highly inflective, as a separate inflected form may be needed for each grammatical category. 
     In n-gram language modeling, word inflection generally increases the size of the underlying vocabulary needed for word prediction, as each inflected form of a word (e.g., “talks”, “talked”, “talking”) may be considered its own word by the language model. Such increase in vocabulary leads to attendant problems such as difficulties in obtaining sufficient training data and resulting language models that are larger than ideal for deployment onto portable electronic devices. For these reasons, a brute force approach to handling words of highly inflected languages, while possible, may not be desirable. 
     In one aspect, to contain the attendant increase in the size of the underlying vocabulary, words may be broken into stem and suffix forms, and using decoupled language models used to train stem data and suffix data for purposes of n-gram language modeling. In general, an inflected word can be broken into a stem and a suffix, and one language model (e.g., a stem language model) may be trained on the stem and suffix data expurgated from all suffixes, while another language model (a “suffix LM”) can be trained based on the stem and suffix data expurgated from all stems. A stem may be a form of a word before any inflectional affixes are added. 
     Further, as the number of suffix morphemes may be limited, this approach may substantially reduce the number of cases where parameter estimation may not be possible. The foregoing approach may be suitable for moderately inflected languages (e.g., German and/or French), yet nonetheless may be difficult to scale up to handle agglutinative languages (e.g., Turkish and/or Finnish), where several suffixes are added to a single stem. 
     For example, consider the Turkish word “geliyorsam”, meaning “If I am coming”. The aforementioned Turkish word may be the result of the agglomeration “gel”, “iyorsa, and “m”, where the first element may be the stem (“gel”), and two standard suffixes may follow to indicate tense (“iyorsa”) and person (“m”), respectively. Thus, the Turkish word “yiyorsam”, meaning “If I am eating” may follow the same agglomeration with a different stem (e.g., “y”, “iyorsa”, and “m”). Thus, the Turkish word “biliyorsam”, meaning “If I am knowing” may follow the same agglomeration with a different stem (e.g., “bil”, “iyorsa”, and “m”). As such, for highly inflected languages including, for example, two or more suffix types, it may be desirable to treat the two or more suffix types separately, as opposed to a single suffix entity as done for low to moderately inflected languages. 
     For such highly inflected languages, considering the two suffix types separately may be beneficial due to conditioning events that tend to differ for tense and person. That is, whereas local context may be adequate to predict an inflection due to the person (e.g., as in “he arrives”, where the presence of “s” directly depends on the pronoun “he”), it may not be as effective to predict an inflection due to tense. The latter may be more likely to depend on the inflection of the previous verb, or a temporal marker possibly far from the present word. Accordingly, the present aspects may address the issue of inaccurate predictions of words of highly inflected languages by using a structured stem and suffix n-gram language model that may separate the suffix into two or more suffix types. 
       FIG. 1  illustrates example system  100  for predicting words using a structured stem and suffix n-gram language model component. Example system  100  includes user device  102  (or multiple user devices  102 ) that can provide a user input interface or environment. User device  102  can include any of a variety of devices, such as a mobile device, cellular telephone (e.g., smartphone), tablet computer, laptop computer, desktop computer, portable media player, wearable digital device (e.g., digital glasses, wristband, wristwatch, brooch, armbands, etc.), television, set top box (e.g., cable box, video player, video streaming device, etc.), gaming system, or the like. User device  102  can have display  116 . Display  116  can be any of a variety of displays, and can also include a touchscreen, buttons, or other interactive elements. In some aspects, display  116  is incorporated within user device  102  (e.g., as in a touchscreen, integrated display, etc.). In other aspects, display  116  is external to—but communicatively coupled to—user device  102  (e.g., as in a television, external monitor, projector, etc.). 
     User device  102  may include or be communicatively coupled to keyboard  118 , which can capture user-entered text (e.g., characters, words, symbols, etc.). Keyboard  118  may include any of a variety of text-entry mechanisms and devices, such as a stand-alone external keyboard, a virtual keyboard, a remote control keyboard, a handwriting recognition system, or the like. For example, keyboard  118  may be a virtual keyboard on a touchscreen capable of receiving text entry from a user (e.g., detecting character selections from touch). In another example, keyboard  118  may be a virtual keyboard shown on a display (e.g., display  116 ), and a pointer or other indicator may be used to indicate character selection (e.g., indicating character selection using a mouse, remote control, pointer, button, gesture, eye tracker, etc.). In yet another example, keyboard  118  may include a touch-sensitive device capable of recognizing handwritten characters. In still other examples, keyboard  118  may include other mechanisms and devices capable of receiving text entry from a user. 
     User device  102  may also include processor  104 , which can receive text entry from a user (e.g., from keyboard  118 ) and interact with other elements of user device  102  as shown. In one example, processor  104  may be configured to perform any of the methods discussed herein, such as predicting words using a structured stem and suffix n-gram language model. In other examples, processor  104  may cause data (e.g., entered text, user data, etc.) to be transmitted to server system  122  through network  120 . Network  120  can include any of a variety of networks, such as a cellular network, WiFi network, wide area network, local area network, the Internet, or the like. Server system  122  may include a server, storage devices, databases, and the like and may be used in conjunction with processor  104  to perform any of the methods discussed herein. For example, processor  104  may cause an interface to be provided to a user for text entry, can receive entered text, can transmit some or all of the entered text to server system  122 , and may cause predicted words to be displayed on display  116 . 
     In some examples, user device  102  can include storage device  106 , memory  108 , word stem n-gram language model  110 , word person suffix n-gram language model  112 , and word tense suffix n-gram language model  114 . In some examples, language models  110 , 112 , and  114  are stored on storage device  106  and can be used to predict words and determine probabilities according to the methods discussed herein. Language models  110 , 112  and  114  may be trained on any of a variety of text data, and can include domain-specific models for use in particular applications. 
     The functions or methods discussed herein can be performed by a system similar or identical to system  100 . It should be appreciated that system  100  can include instructions stored in a non-transitory computer readable storage medium, such as memory  108  or storage device  106 , and executed by processor  104 . The instructions can also be stored and/or transported within any non-transitory computer readable storage medium for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions. In the context of this document, a “non-transitory computer readable storage medium” can be any medium that can contain or store the program for use by or in connection with the instruction execution system, apparatus, or device. The non-transitory computer readable storage medium can include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, a portable computer diskette (magnetic), a read-only memory (ROM), an erasable programmable read-only memory (EPROM), a portable optical disc such as CD, CD-R, CD-RW, DVD, DVD-R, or DVD-RW, or flash memory such as compact flash cards, secured digital cards, USB memory devices, memory sticks, and the like. 
     It should be understood that system  100  is not limited to the components and configuration of  FIG. 1  but can include other or additional components in multiple configurations according to various examples. For example, user device  102  can include a variety of other mechanisms for receiving input from a user, such as a microphone, optical sensor, camera, gesture-recognition sensor, proximity sensor, ambient light sensor, or the like. Additionally, the components of system  100  can be included within a single device or can be distributed among multiple devices. For example, although  FIG. 1  illustrates language models  110 , 112 , and  114  as part of user device  102 , it should be appreciated that, in other examples, the functions of processor  104  can be performed by server system  122 , and/or one or more of entities  110 ,  112 , and  114  can be stored remotely as part of server system  122  (e.g., in a remote storage device). In still other examples, language models and other data can be distributed across multiple storage devices, and many other variations of system  100  are also possible. 
       FIG. 2  illustrates example method and/or process  200  for predicting user input using a structured stem and suffix word n-gram language model. In some aspects, process  200  is executed on processor  104  of system  100  utilizing stem n-gram language model  110  ( FIG. 1 ), person suffix n-gram language model  112  ( FIG. 1 ), and tense suffix n-gram language model  114  ( FIG. 1 ). 
     At block  202  of process  200 , input is received from a user. The input may be received in any of a variety of ways, such as from keyboard  118  in system  100  ( FIG. 1 ), as disclosed herein. The input may also be voice input received through a microphone or a touchscreen of system  100  ( FIG. 1 ). The input may include a single typed character, such as a letter or symbol. The typed input may also include a string of characters, a word, multiple words, multiple sentences, or the like. The input received at block  202  may be directed to various types of interface or environment on an electronic device. For example, such an interface may be configured for typing text messages, emails, web addresses, documents, presentations, search queries, media selections, commands, form data, calendar entries, notes, or the like. 
     The input received at block  202  may be used to predict a word. In some aspects, the input is used to predict one or more of the following:
         a subsequent word likely to be entered following previously-entered words;   the likely completion of a partially-entered word; and/or   a group of words likely to be entered following previously-entered words.       

     Previously-entered characters or words may be considered as observed context that may be used to make predictions. For reference, let:
 
 W   q−n+1   q   =w   q−n+1   w   q−n+2    . . . w   q−1   w   1 ,  (1)
 
denote the entire word history up to and including the current word w q , and assume that some words w i  in the history may be decomposed into a stem s i , a tense suffix f i , and a person suffix p i . In such aspect, a person suffix may be a letter or group of letters added to the end of a word or stem to identify a person. Further, a tense suffix may be a letter or group of letters added to the end of a word or stem to modify its tense. For example, the current word w q  may include or otherwise be represented as w q =s q t q p q . Note that the foregoing decomposition may be extended to any number of specialized suffixes, as language regularity may support. Further, the n words may be one or more words in the received input.
 
     At block  204 , process  200  may determine, using a first n-gram language model, a first probability of a stem based at least on a first portion of a previously-input word in the received input. For example, as described herein, user device  102  ( FIG. 1 ) may execute processor  104  ( FIG. 1 ) to determine, using a first n-gram language model  110  ( FIG. 1 ), a first probability of a stem based at least on a first portion of a previously-input word in the received input. 
     In an aspect, the first n-gram language model may determine the first probability of the stem according to:
 
 Pr ( s   q   |S   q−n+1   q−1 )
 
     In such an aspect, the first n-gram language model may be a word stem n-gram language model. The history of the first n-gram language model, which may be denoted as S q−n+1   q−1 , may be composed of all unstemmed words and/or stems observed in the range [q−n+1, q−1]. As such, the first probability of the stem may be based at least in part on a second stem and an unstemmed word of the previously-input word. In addition, the first n-gram language model may be trained based on a second dataset including stem and suffix data expurgated or removed from all suffixes. 
     Further, at block  206 , process  200  may determine, using a second n-gram language model, a second probability of a first suffix based at least on a second portion of the previously-input word in the received input. In some aspects, the first suffix may be a person suffix. For instance, as described herein, user device  102  ( FIG. 1 ) may execute processor  104  ( FIG. 1 ) to determine, using a second n-gram language model, a second probability of a person suffix based at least on a second portion of the previously input word in the received input. 
     In an aspect, the second n-gram language model may determine the second probability of the person suffix according to:
 
 Pr ( p   q   |P   q−n+1   q−1 )
 
     In such aspect, the second n-gram language model may be a person suffix stem n-gram language model. The history of the second n-gram language model, which may be denoted as P q−n+1   q−1 , may be composed of all unstemmed words and/or person suffixes observed in the range [q−n+1, q−1]. Accordingly, the second probability may be based at least in part on a second person suffix and an unstemmed word of the previously-input word. In addition, the second n-gram language model may be based at least in part on a second dataset including stem and suffix data expurgated from all stems and non-person suffixes. 
     At block  208 , process  200  may determine, using a third n-gram language model, a third probability of a second suffix different from the first suffix based at least on a third portion of the previously-input word in the received input. In some aspects, the second suffix may be a tense suffix. For instance, as described herein, user device  102  ( FIG. 1 ) may execute processor  104  ( FIG. 1 ) to determine, using a third n-gram language model, a third probability of a person suffix based at least on a third portion of the previously input word in the received input. 
     In an aspect, the third n-gram language model may determine the third probability of the person suffix according to:
 
 Pr ( t   q   |T   q−n+1   q−1 )
 
     In such aspect, the third n-gram language model may be a tense suffix stem n-gram language model. The history for the third n-gram language model, which may be denoted as T q−n+1   q−1 , may be composed of tense suffixes and/or unstemmed words that may have a material influence of tense, such as, but not limited to, temporal adverbs. In some aspects, the history may be formed using a part-of-speech analysis of the entire history VV 0   q−1 . Accordingly, in accordance with the n-gram framework, the last n−1 tokens identified in W 0   q−1  are kept in T q−n+1   q−1 . In such aspect, a part-of-speech analysis may be a process of marking up a word in a text as corresponding to a particular part of speech, based on both its definition, as well as its context (e.g., a relationship with adjacent and related words in a phrase, sentence, or paragraph). Hence, block  208  may, in some aspects, include performing a part-of-speech analysis on at least the previously-input word. 
     Further, the third probability of the tense suffix may be determined based at least in part on a second tense suffix of the previously-input word. In addition, the third probability of the tense suffix may be based at least in part on one or more unstemmed words including a temporal adverb. The third n-gram language model may be trained on a first dataset including filtered data expurgated from all stems, non-tense suffixes, and non-information bearing words. For instance, filtered data expurgated or removed from all stems and non-tense suffixes, as well as words deemed non-information bearing, such as, but not limited to, noun phrases and non-temporal adverbs, may be used to train the third n-gram language model. As such, the third n-gram language model may become or otherwise be considered as a long-distance skip n-gram model, informed by a part-of-speech analysis of the input. 
     At block  210 , process  200  may determine a fourth probability of at least one predicted word based on the first probability, the second probability, and the third probability. For instance, as described herein, user device  102  ( FIG. 1 ) may execute processor  104  ( FIG. 1 ), to determine a fourth probability of at least one predicted word based on the first probability, the second probability, and the third probability. In one example, the determination may be a product of the first probability of the stem, the second probability of the person suffix, and the third probability of the tense suffix. 
     In an aspect, the structured stem plus suffix n-gram language model may determine the fourth probability of the person suffix according to:
 
 Pr ( W   0   q−1 )= Pr ( p   q   |P   q−n+1   q−1 )· Pr ( t   q   |T   q−n+1   q−1 )· Pr ( s   q   |S   q−n+1   q−1 )
 
     As shown in the foregoing aspect, the first n-gram language model, the second n-gram language model, and the third n-gram language model may be non-contiguous. The fourth probability may be used to determine at least one predicted word for subsequent output to the user. Specifically, the predicted word may include a stem, a person suffix, and a tense suffix, each determined probabilistically based on its respective n-gram language model, as described herein. In some aspects, multiple words (e.g., two or more) may be used to determine the predicted word. Hence, the fourth probability may be based on the first, second and third probabilities of two or more word in the input. The two or more words may include a string of recently entered words. 
     At block  212 , process  200  may include providing an output of the predicted word to the user, for example, based on the fourth probability determined at block  210 . For instance, user device  102  ( FIG. 1 ) may execute processor  104  ( FIG. 1 ) and/or display  116  ( FIG. 1 ), to provide an output of the predicted word to the user. In other aspects, a speaker may be used to provide an audible output of the predicted word to the user. In some aspects, a predicted word has a non-zero probability as determined at block  210 . In some aspects, block  212  outputs one or more predicted words having the highest prediction probabilities among one or more predicted words. In some aspects, block  212  determines whether the fourth probability for any predicted word w q  exceeds a predetermined threshold probability value. 
     In these aspects, block  212  may output a predicted word w q  if its probability exceeds the threshold, and block  212  may forego output of predicted word(s) if no predicted word w q  exceeds the predetermined threshold. When this is the case, process  200  can return to block  202  to await further input from a user. Blocks  202 ,  204 ,  206 ,  208 , and  210  can be repeated with the addition of each new word entered by a user, and a determination can be made for each new word whether a predicted word should be displayed based on newly determined integrated probabilities of predicted or candidate words. 
     The outputting of the predicted word can include displaying the one or more predicted words. In some aspects, the outputting of a predicted word includes displaying a user-selectable affordance representing the predicted word, such that the word can be selected by the user without the user having to individually and completely enter all the characters of the word. The outputting of the predicted word may include playback of the one or more predicted words. For example, the playback may be an audio or audible playback. In some aspects, outputting a predicted word includes passing the predicted word to an input recognition sub-routine (e.g., a handwriting recognition or voice recognition sub-routine) such that further user output can be provided by the downstream sub-routine. For example, a handwriting recognition sub-routine can display an image of the predicted word that resembles handwriting, based on the word prediction. For example, a voice recognition sub-routine can provide a speech-to-text and/or speech-to-speech output, based on the word prediction. The audio output may be determined with the assistance of a voice-based assistant, such as Siri® by Apple Inc. of Cupertino, Calif. 
     The above-described approach to predicting words, particularly inflected words, combines the benefits of using decoupled stem and suffix language models (e.g., improved size and accuracy) while reducing ungrammatical word predictions based on categorical stem and suffix constraints (e.g., avoiding spurious predictions such as “he speaked fast”). An electronic device employing these techniques for predicting words can permit user input without requiring the user to individually and manually enter each character and/or word associated with an input string, while limiting the occurrence of spurious predictions. In this way, the efficiency of the man-machine interaction and the user&#39;s overall user experience with the electronic device are both improved drastically. 
     Although process  200  includes a first suffix as a person suffix and a second suffix as a tense suffix, it should be understood that the present aspects may include, as the first suffix and the second suffix, other suffix types. For example, the first suffix and/or second suffix may each include or otherwise be one of a plural suffix, a verb form suffix, a characteristic suffix, an action/process suffix, a state suffix, an adjective suffix, a verb suffix, and an adverb suffix. 
       FIG. 3  illustrates example method and/or process  300  for predicting user input using a structured stem and suffix word n-gram language model. In such aspect, process  300  is executed on processor  104  of system  100  utilizing stem n-gram language model  110  ( FIG. 1 ), person suffix n-gram language model  112  ( FIG. 1 ), and tense suffix n-gram language model  114  ( FIG. 1 ). Additionally, in such aspect, the person suffix may be a first suffix and the tense suffix may be a second suffix, as described herein with respect to  FIG. 2 . 
     Process  300  may ensure stem and suffix consistency through the use of categorical stemming, where each category of stems may be associated with a defined or pre-defined set of tense and/or person suffixes. For example, the stem may be associated with a stem category, and the stem category may be associated with one or more suffixes, including a second person suffix and a second tense suffix, to ensure or guarantee stem and suffix consistency. 
     In particular, at block  302 , process  300  may determine whether a person suffix and a tense suffix (e.g., as determined by the second n-gram language model and third n-gram language model, respectively) match the second person suffix and the second tense suffix (e.g., as previously associated with the stem category). Further, at block  304 , method  300  may forego output of the predicted word in response to determining that the person suffix and the tense suffix do not match the second person suffix and the second tense suffix. 
     In another aspect, to ensure word accuracy, process  200  may, at block  306 , determine one or both of a case and an object of the previously-input word. Additionally, at block  308 , process  300  may determine the second probability of the person suffix at block  206  using the second n-gram language model and the third probability of the tense suffix at block  208  using the third n-gram language model may be based on one or both of the case and the object. 
     As an example not to be construed as limiting, the structured stem and suffix n-gram language model may effectively analyze words of languages demonstrating any level of inflection (e.g., highly inflected languages such as Turkish and Finnish) by separating the suffix into two or more suffix types (e.g., person suffix and/or tense suffix), in addition to the stem. As such, the structured stem and suffix n-gram language model may consider at least the stem, person suffix, and tense suffix when determining a predicting word for a particular language. For example, consider the following French sentence: 
     Demain, sans aucun doute, je traverserai la rivière et je camperai de l′autre côte 
     The two stems of the foregoing sentence, “travers_” and “camp_” are conjugated in the first person singular, as can be directly inferred from the pronoun “je” immediately preceding them. However, in both cases the future tense information may not be predictable from the local contexts (“sans”, “aucun”, “doute”, “je”) and (“la”, “rivière”, “et”, “je”). The structured stem and suffix n-gram language model may obtain or otherwise provide an accurate tense prediction by effectively performing long-distance skip contexts such as (“demain”, . . . , “je”) and (“FUTURE_MARKER”, . . . , “je”), respectively, where “FUTURE_MARKER” refers to the fact that the surface form “traverserai” may include a future tense suffix. 
     In another example not to be construed as limiting, consider the following Turkish sentence: 
     geliyorsam ye yiyoruz 
     The structured stem and suffix n-gram language model may train and/or accurately output a predicted word based on the above Turkish sentence by analyzing or otherwise considering the stem, the person suffix, and the tense suffix. For instance, the first (e.g., stem) n-gram language model may include the trigram (“gel_”, “ve”, “y_”), the second (e.g., person suffix) n-gram language model may include the trigram (“_m”, “ve”, “_uz”), and the third (e.g., tense suffix) n-gram language model may include the trigram (“_iyorsa_”, “ve”, “_iyor_”). The structured stem and suffix n-gram language model may account for the above Turkish sentence, even if this particular three-word string was not previously seen in the training data. This ability to, in effect, substitute one stem for another and one suffix for another produces robust predictions while requiring feasible amounts of training data, and translate into language models suitable for deployment, particularly in terms of size. 
     In yet another example not to be construed as limiting, consider the following Turkish sentence: 
     Bakacakum da bulamadik. 
     The structured stem and suffix n-gram language model may train and/or accurately output a predicted word based on the above Turkish sentence by analyzing or otherwise considering the stem, the person suffix, and the tense suffix. The Turkish sentence means, “I was going to look at it but we could not find it.” For instance, the first (e.g., stem) n-gram language model may include the trigram (“bak_”, “da”, “bul_”), the second (e.g., person suffix) n-gram language model may include the trigram (“_m”, “da”, “_k”), and the third (e.g., tense suffix) n-gram language model may include the trigram (“_acaku_”, “da”, “_amadi_”). The structured stem and suffix n-gram language model may account for the above Turkish sentence, even if this particular three-word string was not previously seen in the training data. This ability to, in effect, substitute one stem for another and one suffix for another produces robust predictions while requiring feasible amounts of training data, and translate into language models suitable for deployment, particularly in terms of size. 
       FIG. 4  shows a functional block diagram of example electronic device  400  configured in accordance with the principles of the various described examples. The functional blocks of the device may be implemented by hardware, software, or a combination of hardware and software to carry out the principles of the various described examples, including those described with reference to process  200  of  FIGS. 2 and 3 . It should be understood that the functional blocks described in  FIG. 4  may be combined or separated into sub-blocks to implement the principles of the various described examples. Therefore, the description herein optionally supports any possible combination or separation or further definition of the functional blocks described herein. 
     As shown in  FIG. 4 , example electronic device  400  includes display unit  402  configured to display a word entry interface, and an input receiving unit  404  configured to receive input such as touch input and/or voice input from a user. Input receiving unit  404  can be integrated with display unit  402  (e.g., as in a touchscreen), and display unit  402  may display a virtual keyboard. Electronic device  400  may further include a processing unit  406  coupled to display unit  402  and input receiving unit  404 . Processing unit  406  may include a predicted word determining unit  408 , a stem category unit  410 , and an integrated probability determining unit  412 . 
     Processing unit  406  can be configured to receive input from a user (e.g., from input receiving unit  404 ). First n-gram language model determination unit may be configured to determine, using a first n-gram language model, a first probability of a stem based at least on a first portion of a previously-input word in the received input. Second n-gram language model determination unit may be configured to determine, using a second n-gram language model, a second probability of a person suffix based at least on a second portion of a previously-input word in the received input. Third n-gram language model determination unit may determine, using a third n-gram language model, a third probability of a tense suffix based at least on a third portion of a previously-input word in the received input. Fourth n-gram language model determination unit may be configured to determine a fourth probability of at least one predicted word based on the first probability, the second probability and the third probability. Processing unit  406  may be further configured to cause the predicted word to be displayed (e.g., using display unit  402 ) based on the fourth (integrated) probability. 
     Processing unit  406  may be further configured to determine (e.g., using units  408 ,  410 ,  412 , and  414 ) the probability of the predicted word based on a plurality of words in the typed input. In some examples, the plurality of words comprises a string of recently entered words. For example, recently entered words can include words entered in a current input session (e.g., in a current text message, a current email, a current document, etc.). For predicting words, the recently entered words can include the last n words entered (e.g., the last three words, the last four words, the last five words, or any other number of words). 
     Although examples have been fully described with reference to the accompanying drawings, it is to be noted that various changes and modifications will become apparent to those skilled in the art (e.g., modifying any of the systems or processes discussed herein according to the concepts described in relation to any other system or process discussed herein). Such changes and modifications are to be understood as being included within the scope of the various examples as defined by the appended claims.