5 ms·

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 transition

by jgable 12y ago

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.

danieldk 12y ago
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.
- Orangeair 12y ago
  Is that how things like Swiftkey or Google Now can predict words so well? If so, how do they do it so quickly?
  - danieldk 12y ago
    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-CoNLL200721.pdf http://hnk.ffzg.hr/bibl/acl2007/EMNLP-CoNLL2007/pdf/EMNLP-Co...
  - jzymbaluk 12y ago
    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 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/ http://www.howtocreateamind.com/
    - Blahah 12y ago
      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.
  - regularfry 12y ago
    Very probably with the Viterbi algorithm: http://en.wikipedia.org/wiki/Viterbi_algorithm http://en.wikipedia.org/wiki/Viterbi_algorithm
    - rmrfrmrf 12y ago
      ...which is an implementation of a Hidden Markov Model, so, yes.
    - danieldk 12y ago
      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).
      - regularfry 12y ago
        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.
        danieldk 12y ago
        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.
  - tripzilch 12y ago
    > 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 :)
DanBC 12y ago
Shannon's paper becomes a lot more fun once you've grokked Markov chains. http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf 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.
- dragonwriter 12y ago
  > 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.

by jgable 12y ago

danieldk 12y ago

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.

Orangeair 12y ago
Is that how things like Swiftkey or Google Now can predict words so well? If so, how do they do it so quickly?
- danieldk 12y ago
  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-CoNLL200721.pdf http://hnk.ffzg.hr/bibl/acl2007/EMNLP-CoNLL2007/pdf/EMNLP-Co...
- jzymbaluk 12y ago
  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 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/ http://www.howtocreateamind.com/
  - Blahah 12y ago
    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.
- regularfry 12y ago
  Very probably with the Viterbi algorithm: http://en.wikipedia.org/wiki/Viterbi_algorithm http://en.wikipedia.org/wiki/Viterbi_algorithm
  - rmrfrmrf 12y ago
    ...which is an implementation of a Hidden Markov Model, so, yes.
  - danieldk 12y ago
    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).
    - regularfry 12y ago
      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.
      - danieldk 12y ago
        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.
- tripzilch 12y ago
  > 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 :)

DanBC 12y ago

Shannon's paper becomes a lot more fun once you've grokked Markov chains. http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf 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.

dragonwriter 12y ago
> 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.