Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Markov chains explained visually

setosa.io

Post reply on HN
Print view View original

81–90 of 96 posts

Re: Show HN: Markov chains explained visually

#81

Post by regularfry »

microtonal wrote: post #75
regularfry wrote: post #37

Earlier quoted context omitted.

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

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.

Re: Show HN: Markov chains explained visually

#82

Post by matthewcanty »

I'm outta control on this page!

[ [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1] ]

Re: Show HN: Markov chains explained visually

#83

Post by microtonal »

regularfry wrote: post #81
microtonal wrote: post #75

Earlier quoted context omitted.

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.

Re: Show HN: Markov chains explained visually

#84

Post by michaelcampbell »

girvo wrote: post #77
vicapow wrote: post #73

There was a bug in the playground earlier that I just fixed that allows you to share your Markov chains via the url hash. For example: http://setosa.io/markov/#%7B%22tm%22%3A%5B%5B0.9%2C0.1%2C0%2...

Hey, I think that link is so long it's breaking HN's layout! Reckon you can chuck it in a URL shortener or something? :)

Verboten on HN.

Re: Show HN: Markov chains explained visually

#85

Post by scott_s »

ddt wrote: post #39
devindotcom wrote: post #32

I've seen Markov chains applied to language generation - producing sentences that make sense grammatically but not literally. Anyone know what the connection is here? I think I have an idea but would like to see if it gets independently verified by someone else.

There are complicated ways of doing this, but the naïve way is as follows: First you need a corpus of text that's grammatically correct Each node in the chain is a word or piece of punctuation. Each word has a certain probability of being followed by every other word in the corpus, including itself. There are a few different ways to start the sentence. One approach is to start from the node for the punctuation mark "…

If you'll notice, there's no guarantee that it will be grammatically correct. There's just some statistical likelihood that it will be.

Which is also true for human speakers.

Re: Show HN: Markov chains explained visually

#87

Post by sitk »

This is an absolutely magical and intuitive (not to mention beautiful) way to imagine the complex mathematical concept of a Markov Chain. This is the exact sort of pedagogical tools that MOOCs and other educational software platforms need to build and adopt to bring education into the 21st Century and finally replace traditional teaching methods. How does this compare to what even the best teacher could draw on a whiteboard? Teachers will still play an essential role in the emotional and social development of students, and they can then focus their energy on these things which software probably will struggle to ever replace.

Re: Show HN: Markov chains explained visually

#89

Post by tripzilch »

Orangeair wrote: post #22
microtonal wrote: post #7

Earlier quoted context omitted.

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),…

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

> 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 :)

Re: Show HN: Markov chains explained visually

#90

Post by notduncansmith »

tdaltonc wrote: post #17
beenpoor wrote: post #15

Thank you! I understood what Markov Chains are now. Nicely done and in a simple understandable fashion. I am also trying to understand what they call Hidden Markov Model (specifically, I just cannot wrap my head around how it gets used in speech. They just look like entirely different things). Would be awesome to see an update with the Hidden MM.

To understand an HMM: Start with a MM with two states. In state "A" we always observe "X" in state "B" we always observe "Y". That's a basic MM. Now lets change it to a HMM. Now, in state "A" we observe "X" 90% of the time and "Y" 10% of the time, and in state B we observe "Y" 90% of the time and "X" 10%. The observations don't tell us exactly what state we're in. The state is "hidden." We still get a clue about the…

This is an excellent explanation, thanks!
Post reply on HN