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

61–70 of 96 posts

Re: Show HN: Markov chains explained visually

#61

Post by TazeTSchnitzel »

granttimmerman wrote: post #33

I created a Markov chain generator: https://gist.github.com/grant/561834963dc526495c45 var numNodes=10;var roundNum=100;var a=[];for(var i=0;i roundNum)/roundNum;connections[j]=randNum;sum+=randNum}connections=connections.map(function(e){var t=e (1/sum);t=Math.round(t roundNum)/roundNum;return t});sum=connections.reduce(function(e,t){return e+t});connections[numNodes-1]+=1-sum;connections[numNodes-1]=Math.round(conne…

Please indent each line with a double space so it's properly monospace formatted.

Re: Show HN: Markov chains explained visually

#62

Post by TazeTSchnitzel »

kephra wrote: post #35
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.

Markov chains work well for artificial language and name generations. One of my first programs in 1979, when I was a 13yr old kid, was to sum up the occurrence of characters following other characters in text files, and to roll dice on this table to generate names for role playing games. I later learned that I reinvented Markov this way. I still have those printouts, and use them when ever I need a name for a role pl…

Someone made a Twitter account to generate baby names with markov chains, actually: https://twitter.com/markovbaby

Re: Show HN: Markov chains explained visually

#63

Post by tel »

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.

Imagine that you've got a markov model just like what this article suggests. Now imagine that in each round your markov model emits a state and then sends that state to a noise box which converts that state into some kind of sound.

As a simple model, say S1 leads to a rising C, S2 leads to a falling F, S3 leads to a stable Bb.

In a more complex model, this sound box is actually plays two or three sounds all at once. As a further complexity, many output sounds overlap between states.

If you're a scientist observing just the sounds being made then you're talking about an HMM (because the markov model is "hidden" behind the sound box). We model speech this way by assuming (sort of) that speech is composed of phonemes (each state) which might sort of overlap in their actual sound.

So a scientist using an HMM tries to reverse the process—listen to the sounds and figure out the phonemes that generated it by knowing something about how people make transitions between phonemes in, say, English words.

Re: Show HN: Markov chains explained visually

#64

Post by sitkack »

lobotryas wrote: post #55

Has anyone thought about or attempted to model game AI with Markov Chains instead of decision trees? Ex: NPCs, wildlife or enemies that use Markov Chains to react to their surroundings.

Just a decision tree with a probability of transitioning to a branch?

Re: Show HN: Markov chains explained visually

#66

Post by thetwiceler »

aet wrote: post #20
dnautics wrote: post #9

This is really great, but could you put in a bit how some transition matrices aren't markov (e.g. [0 1; 1 0]) and the convergence criterion where you can take M^n n->infinity and get the occupancy of the states?

Why isn't your example Markov?

It is in fact Markov; Markov just means that the probability distribution of the future depends only on the present, and so the past adds no additional information in conjunction with the present. That's certainly the case here.

This is an example of a Markov chain that is not aperiodic; what that means is that, given a starting node, at any point in time in the future, it will always be the case that it is impossible to be at a certain node. This ends up meaning that the Markov chain never ends up reaching a steady state; rather, its behavior is periodic!

Re: Show HN: Markov chains explained visually

#68

Post by tdaltonc »

bunkat wrote: post #65
_nullandnull_ wrote: post #45

Beautiful. What did you use to create the graphics?

I'd be interested in this as well. Is it D3?

From browsing the source, it looks like the graphics are rendered in D3 and the sliders are connected to the graphics using Angular.

Re: Show HN: Markov chains explained visually

#69

Post by moron4hire »

richcuteguy34 wrote: post #53

Nice Here's a model of chutes and ladder using Markov http://www.datagenetics.com/blog/november12011/index.html And another for Candyland http://www.datagenetics.com/blog/december12011/index.html

Nice. These articles are great. Very much appreciated.

Re: Show HN: Markov chains explained visually

#70

Post by un_publishable »

lobotryas wrote: post #55

Has anyone thought about or attempted to model game AI with Markov Chains instead of decision trees? Ex: NPCs, wildlife or enemies that use Markov Chains to react to their surroundings.

Not sure about individual-scale models, but Markov Chains are common in Mathematical Ecology. You can do quite a lot in animal group modeling with transition matrices and basic probability theory. This is a good book if you can get it cheap (like most monograph textbooks): http://www.amazon.com/Introduction-Stochastic-Processes-Biol...

Also, props to submission author Victor Powell. Those force-directed graphs are visually interesting, add to the article, and are even responsive (try changing the window size).

Post reply on HN