[deleted]
Show HN: Markov chains explained visually
11–20 of 96 posts
Re: Show HN: Markov chains explained visually
#12This is really nice. Minor nit #1: https://www.dropbox.com/s/2meqa8hhen9ztba/Screenshot%202014-... Seems like the graph visualization is sticking to the wrong coordinates (dragging it to the left doesn't help; it moves back to the center) Minor nit #2. I'd love to see a visualization of the "probability mixing" interpretation of markov chains and stationary distributions, which is what PageRank is really about. That…
One way to get at what you're saying in #2 is to have a counter that accumulates the number of epochs spent in state 1, state 2, state 3, for one of these examples. Have a way to reset this counter, and compute the relative frequency (by normalizing the counts-in-each-epoch by the number of epochs so far).
Come to think of it, you could even calculate the first eigenvector of the transition matrix, and show this eigenvector next to the relative frequency mentioned above.
In fact, you could then plot an L1 distance of the relative frequency (above) to the eigenvector, with one point for each epoch. This distance would decrease (non-monotonically) towards zero as the number of epochs increases. I believe it is (in the expectation sense) exponentially fast, but with an exponent that depends on the transition matrix. (Typical transition matrices would exhibit fast mixing, http://en.wikipedia.org/wiki/Markov_chain_mixing_time).
Re: Show HN: Markov chains explained visually
#13"For example, the algorithm Google uses to determine the order of search results, called PageRank, is a type of Markov chain."
I had to research that to understand it: http://en.wikipedia.org/wiki/PageRank
Here is some key text from Wikipedia:
Google recalculates PageRank scores each time it crawls the Web and rebuilds its index. As Google increases the number of documents in its collection, the initial approximation of PageRank decreases for all documents.
The formula uses a model of a random surfer who gets bored after several clicks and switches to a random page. The PageRank value of a page reflects the chance that the random surfer will land on that page by clicking on a link. It can be understood as a Markov chain in which the states are pages, and the transitions, which are all equally probable, are the links between pages.
If a page has no links to other pages, it becomes a sink and therefore terminates the random surfing process. If the random surfer arrives at a sink page, it picks another URL at random and continues surfing again.
Re: Show HN: Markov chains explained visually
#14Now look up Hidden Markov models,
http://en.wikipedia.org/wiki/Hidden_Markov_model
How they can be calibrated in the finite case http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm
And how they can be evaluated for arbitrary models http://en.wikipedia.org/wiki/Particle_filter
Re: Show HN: Markov chains explained visually
#15Thank 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.
Re: Show HN: Markov chains explained visually
#16can I fork these?
Re: Show HN: Markov chains explained visually
#17Thank 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 state, but there is some uncertainty.
Re: Show HN: Markov chains explained visually
#18"For example, the algorithm Google uses to determine the order of search results, called PageRank, is a type of Markov chain." I had to research that to understand it: http://en.wikipedia.org/wiki/PageRank Here is some key text from Wikipedia: Google recalculates PageRank scores each time it crawls the Web and rebuilds its index. As Google increases the number of documents in its collection, the initial approximation…
That's increadibly easy (it is!)
I can't understand why Google owns it.
Especially today ("~15 years later") and with a lot of good open source software available.
Re: Show HN: Markov chains explained visually
#19Very cool. Would love to see this generalized to an interactive visualization of Markov Decision Processes (MDPs).
Re: Show HN: Markov chains explained visually
#20This 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?