Hacker News Reader

Comment by jgable | Hacker News Reader

Beautiful. I had seen Markov chains mentioned before, but had not looked them up. Skimming the wikipedia page made sense (it's a state machine with transitions determined by probabilities instead of defined events), but I would not have had an intuitive understanding of why they are useful. The explanation mid-way down about modeling the distribution of sunny and rainy days really made it click for me.

View on HN

The explanation mid-way down about modelling the distribution of sunny and rainy days really made it click for me.

Another very easy to understand is language. Say, I give you a small text. You could create a small state machine containing the possible transitions between words. You could also compute probabilities (estimated from the text) of going from one word to another (e.g the -> text vs. the -> possible, etc), and you'll have a Markov chain.

Of course, this is a very weak model of language, and usually in such models probabilities are modelled on at least the previous two states. But it turns out to be very useful in practice, e.g. you can compute the fluency of different formulations of the same semantics.

Is that how things like Swiftkey or Google Now can predict words so well? If so, how do they do it so quickly?

That's indeed one way to implement predictive typing. Looking up the list of possible words is not expensive, you basically step through a small automaton. The challenge is making the models small enough to fit it on a phone. See e.g.:

http://hnk.ffzg.hr/bibl/acl2007/EMNLP-CoNLL2007/pdf/EMNLP-Co...

Ray Kurzweil, one of the fathers of speech recognition, talks in his book How to Create a Mind about his use of "Hidden Markov Models" as a breakthrough in speech recognition work. I believe Kurzweil used his HMM's to recognize the flow of sounds and speech patterns as words, so it's not exactly the same as what Swiftkey does with word prediction, but it's safe to safe Markov chains have an important place in language modeling.

Hidden Markov Models: http://en.wikipedia.org/wiki/Hidden_Markov_model

Kurzweil's Book (He goes into more detail on speech recognition as well as a slew of other topics): http://www.howtocreateamind.com/

Hidden Markov Models are also an important tool in computational biology - we use them to represent and search for motifs in sequences, such as DNA binding sites, protein domains with a particular function, etc.

Very probably with the Viterbi algorithm: http://en.wikipedia.org/wiki/Viterbi_algorithm

...which is an implementation of a Hidden Markov Model, so, yes.

Viterbi is used for decoding e.g. HMMs, when there are multiple possible state sequences given the observations, and you want to find the most probable. In a normal (non-hidden) Markov model, you can just follow the state transitions and get out a probability (or go to a state and see what the next possibilities are).

An HMM is exactly what you have in both predictive typing and speech recognition, since in both cases you've got some form of sensor noise to deal with.

But predictive typing usually corrects per word. Given a sequence of words, you can give the top suggestions (like Swype and others do) using a non-hidden Markov model. For partially typed words, it's easier to take words from the same suggestion list and rank them by combination of probability and some similarity measure (e.g. edit distance). Possibly complemented by non-suggestions through some other method (e.g. levenshtein automata). If you want to correct

  predctiv tping an spech recgnition

Yes, you you'll want to use a hidden Markov model. If you already have

  predictive typing and speech recgn

then a normal Markov model will serve you fine. And since such predictive keyboards do corrections per word, they are like the latter example and not the former. For speech recognition (e.g. Google Now), you indeed need an HMM.

> Is that how things like Swiftkey or Google Now can predict words so well? If so, how do they do it so quickly?

Yes. It's most definitely an important part of their algorithm.

But why would it be slow? The average person has a vocabulary of max. 50-100k words. Maybe it was even less, I forget. You'd probably do more than fine with just the top 10k anyway.

With a clever data structure, that's peanuts for today's mobile hardware.

In particular (and I dunno if that's how they do it) just the lookup needs to be fast, the storing of new words can be done offline in some lost half-second when the user isn't interacting with the device. With that in mind they can even use really cool data-structures such as tries that can do super-efficient partial prefix matching.

Except they also seem to do fuzzy matching, so there needs to be some Levenshtein distance type of thing in there. That can be costly, but it's also been around for some decades and that part doesn't need to be super-exact, so I bet there's some really clever tricks for that as well. If anyone knows, I'd love to hear about it too :)

Shannon's paper becomes a lot more fun once you've grokked Markov chains.

http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd...

There's a bunch of fun stuff that suddenly becomes possible.

It's gently distressing that by far the most use that Markov chains have seen so far is to generate English-like gibberish text to beat spam filters.

> It's gently distressing that by far the most use that Markov chains have seen so far is to generate English-like gibberish text to beat spam filters.

I don't think that's the most use they've gotten, just the most obvious and visible use.

Reply on news.ycombinator.com