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

51–60 of 96 posts

Re: Show HN: Markov chains explained visually

#51

Post by dragonwriter »

DanBC wrote: post #50
jgable wrote: post #4

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.

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.

Re: Show HN: Markov chains explained visually

#52

Post by rmrfrmrf »

regularfry wrote: post #37
Orangeair wrote: post #22

Earlier quoted context omitted.

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

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

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

Re: Show HN: Markov chains explained visually

#54

Post by enjalot »

nabeelahmed13 wrote: post #38

This is at a tangent, but I'm a fresh CS undergrad and this simple explanation really hooked me. So my question is, where can I find more of this stuff? MOOCs are tough to manage with university, but if I wanted to learn more about these mathematical concepts presented in an interesting way, where should I start looking? I'm a tad bit indecisive about how good I am with CS theory but I know if I took the leap and mas…

the other visualizations on setosa.io are pretty great. There really aren't enough of these around if you ask me. another set of good tutorials that are at this level is Red Blob Games: http://www.redblobgames.com/ focused on games but introduces math/coding concepts very intuitively and in a practical manner.

Re: Show HN: Markov chains explained visually

#56

Post by theoh »

nabeelahmed13 wrote: post #38

This is at a tangent, but I'm a fresh CS undergrad and this simple explanation really hooked me. So my question is, where can I find more of this stuff? MOOCs are tough to manage with university, but if I wanted to learn more about these mathematical concepts presented in an interesting way, where should I start looking? I'm a tad bit indecisive about how good I am with CS theory but I know if I took the leap and mas…

Dasher http://www.inference.phy.cam.ac.uk/dasher/ takes some of the Markov chain ideas to the next level. If you are a visual thinker it is a good way to get a feel for probabilistic compression techniques, specifically PPM and arithmetic coding.

Also good is the Viterbi Workshop (EDIT: unfortunately the URL below leads to a broken version of the applet.) http://www.alantro.com/viterbi/workshop.htm It used to have animated Java illustrations of the Viterbi algorithm, mentioned in other comments on this post. There are other working applets out there, e.g. http://www.wirelesscommunication.nl/reference/chaptr05/recei...

The general field is called "algorithm animation" but it seems be out of fashion. The old SRC Modula-3 distribution used to contain a cool package for creating animations of algorithms. Here is a video made by the authors: http://www.youtube.com/watch?v=zIgu9q0vVc0

Re: Show HN: Markov chains explained visually

#57

Post by Pinn2 »

The problem with Markov chains is that they are named after a person, which makes math seem more like a "private club". For instance, why use "abelian group", when "commutative group" will do? The reasons for wanting to be a member of an exclusive group are psychological.

Re: Show HN: Markov chains explained visually

#58

Post by Blahah »

jzymbaluk wrote: post #30
Orangeair wrote: post #22

Earlier quoted context omitted.

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

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 languag…

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.

Re: Show HN: Markov chains explained visually

#60

Post by Terr_ »

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.

Suppose the Markov "state" is what word a user just intended to speak. You can use a non-hidden Markov Model to generate sentences.

But for speech-recognition, you don't know what the user said (that's your goal) and you're guessing based on audio sensor data. This means the true state is "hidden" from you, and you're trying to make educated guesses.

Using a Hidden Markov Model allows you to combine your imperfect indicators (audio samples that sound like certain words) with statistical knowledge (how likely certain words are to follow other words) to improve your guesses.

Post reply on HN