2
$\begingroup$

Many are now familiar with GBoard, the Google / Android predictive Keyboard. I don't actually know how it works. Obviously it must gather usage data on the device where it is being used, but it probably also includes a database of general usage patterns, downloaded initially and perhaps updated periodically. (Well, that is how I would do it.) In this way, it would be like a spellcheck database that let the user add (and subtract: manger is not too good in a business context) words.

I have long been brushing aside the obvious question of "how does it do that?", but this morning as I was texting, I suddenly recalled the article in [Scientific American* (long ago, can't find it on the web) about Markov Chains and a simple program called Mark V. Shaney that would learn and then output words in a sensible order. That is how it could work. It should be quite easy to store and compress such a simple database.

The particular thing I am focusing on is how GBoard offers three word suggestions as I type, so that I can just pick words instead of typing the words in. The prediction is at the word level, not the letter level. What frustrates me is that it usually does not offer the proper tense for a word, making me type far more letters until the proper word shows up. For example: I want to type "He has started on it" and I type H and choose 'He' from the suggestions, then ha and pick 'has' then type sta and the suggestions are: start starts starting, none of which agree with has. Why doesn't it go right to started?

Has anyone implemented a similar project for analyzing and predicting or even uttering strings of words? It seems dead easy using Markov Chains. Do you think this would make a good project for using things like a 'dictionary' data structure to store words, and some kind of tree to encode the word association weights? Sounds like it would be very interesting to present-day students, already using the product.


The SciAm article mentioned is likely: Dewdney, A.K. (June 1989). "A potpourri of programmed prose and prosody; Computer Recreations; computer-generated commentary". Scientific American. 260 (6): 122–125. doi:10.1038/scientificamerican0689-122.

$\endgroup$
  • 2
    $\begingroup$ Hi Scott, I put the question into the header to make the topicality clearer. If I made a mistake, feel free to revert. $\endgroup$ – Ben I. Jun 13 '18 at 15:07
  • $\begingroup$ @Buffy Thanks for locating the article and putting it in the question! $\endgroup$ – Scott Rowe Jun 13 '18 at 18:36
  • $\begingroup$ You should check out kingjamesprogramming.tumblr.com Which is "Posts generated by a Markov chain trained on the King James Bible, Structure and Interpretation of Computer Programs, and some of Eric S. Raymond's writings Run by Michael Walker (barrucadu)." $\endgroup$ – Adam Jun 13 '18 at 19:32
  • 1
    $\begingroup$ @Adam in the original article, it gave an excerpt of some emitted text, which included something like: " 'The simulacrum is true' -- Ecclesiastes" $\endgroup$ – Scott Rowe Jun 14 '18 at 14:37
2
$\begingroup$

Markov Chains are great for putting out nonsense based on statistical data. However, a predictive keyboard that outputs nonsense isn't very useful. It needs much more context than a Markov Chain can produce. Such a program would base its next output entirely on the most recent entry.

That said, a project to do something like the Mark V. Shaney program might be fun in an Introduction to Data Structures course. However, it is unlikely that students would have previously seen Markov Chains at that point in their studies so some background in that would also need to be incorporated. Markov Chains might be taught in a Discrete Math course, but that usually comes later. Some schools might teach these two courses in tandem, however, making it a bit more feasible.

Such a project would, however, also have the advantage that the statistical basis (the Dictionary) used could introduce concepts of Big Data and how to process it.

You are correct that a predictive keyboard uses past data, but I'm pretty sure that it is based on a much more complex predictive model than could be provided by a Markov Chain. "Predictive Keyboard based on Markov Chains" is probably an oxymoron, though. You can do either or, but likely not both together.

$\endgroup$
  • $\begingroup$ OK, well I might be ignorant about the particulars of Markov Chains, having read about them 30 years ago, so that is fine. But some sort of weighted prediction (more like a tree) is obviously being used to drive the keyboard thing, because I can often type an entire text message just by picking one of the three suggestions for next word on my phone. Pretty good prediction, if you ask me! (Have you used that feature?) The frustrating thing is how the options move position as I type, so I am reaching for the leftmost one and by the time I touch there, it has moved to the center position. Ugh! $\endgroup$ – Scott Rowe Jun 13 '18 at 18:31
  • $\begingroup$ Scott, the same thing happens to me! My fingers aren't fast enough. Usually the data structure used for predictive typing is a TRIE - here's one article on how to do it in Javascript: [link] (medium.com/@dookpham/…) $\endgroup$ – Java Jive Jun 15 '18 at 13:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.