6 ms·
Markov Chains Explained Visually (2014)
- rhodysurf 11y agoI like this. Markov chains can be hard to explain without examples.
- deleted 11y ago[deleted]
- ams6110 11y agoIt's a nice demo but when I moved one of the probability sliders from 0.5 to 0.9 my browser essentially locked up for nearly two minutes. (FF 45.0.1). Seems we're still a ways from achieving native browser animation performance that Flash (for all its other problems) had a decade or more ago.
- abiox 11y agoi didn't have any lockups in chrome.
- creed0r 11y agoAm I right in taking from this that markov chains don't necessarily adjust to history? So in the example, if a "sunny day" state has a chance of 0.9 to stay in that state and a 0.1 chance of transitioning to rainy day and I already had 5 sunny days, the 6th day would still have a 0.1 chance to be a rainy day?
- detaro 11y agoYes, the classical Markov chain has no memory. A Markov chain with memory for the last m steps is sometimes called a "Markov chain of order m"
- creed0r 11y agoAlright thanks, so I guess weather as an example works but maybe something else would be a better fit.
- ifdefdebug 11y agoProbability doesn't adjust to history either: if you flip coins, and if you already have 5 heads in a row, your chance for a head the next time you flip is still exactly one half. But weather is not driven by probability so history might matter.
- dasboth 11y agoYes that's right. The reason they're "Markov" chains is that they make the "Markov assumption" which is usually stated as "the future is independent of the past given the present". This just means that the probability of the next timestep depends only on what happened in the current one; it has no memory as such. As detaro says: "A Markov chain with memory for the last m steps is sometimes called a "Markov chain of order m"" So if you wanted it to depend on the last 5 timesteps, you'd create a 5th order Markov chain, and so on.
- skybrian 11y agoYou could count sunny days by encoding the count as different states in a more complicated markov chain: sunny1 -> sunny2 -> sunny3 -> sunny4 -> sunny5. But as with regular expressions, you can't go to arbitrary depth.
- Link-djst 11y agoNice way to learn new things!
- nmaggioni 11y agoLast year I made a pseudo-random text generator based on Markov Chains as a summer project to learn C++: https://github.com/nmaggioni/MarkovText https://github.com/nmaggioni/MarkovText It's in Italian since it just was an hobby project and I didn't spend too much time adapting it for the public domain, but it may be interesting for someone.
- herval 11y agoI have a Twitter bot that makes up book passages combining books from the Gutenberg project: https://twitter.com/markovian_lit https://twitter.com/markovian_lit Code is also on GitHub if it interests anyone - not the prettiest, but it was fun to build :-)
- michaelfeathers 11y agoHere's a Ruby version in 16 lines of code: https://gist.github.com/michaelfeathers/2cf9e1599e06d0563f2e https://gist.github.com/michaelfeathers/2cf9e1599e06d0563f2e
- vc98mvco 11y agoSorry to be off-topic, but the site partially disables my input, i.e. causes high lag. It makes it unusable. I'm using Firefox on a modern PC. Opera seems to run fine, but it maxes out two cores. Uhhh...?
- escobar 11y agoThis has previously appeared on HN in July 2014 :) https://news.ycombinator.com/item?id=8103240 https://news.ycombinator.com/item?id=8103240
- xchaotic 11y agoBut there wasn't enough hype around ML back then. A few Go wins later and it's getting a top spot.
- dang 11y agoCheap shots like this degrade the community, so please don't post them here. The story spent hours at #1 back then, and had three times as many votes as this resubmission (so far).
- kastnerkyle 11y agoFor anyone interested in Markov chains (aimed at language) in Python, and their relationship to the larger world of language modeling (including "modern" RNNLMs and so on) this post by Yoav Goldberg is an excellent introduction, with clear and simple code [1]. Extending the Markov chain even a few steps can give really impressive generated results. Clone/download [2] if you want to run the code yourself. [1] http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/yoavg/d76121dfde2618422139/raw/564dfb8ad396e987c1f1c45ce3c6b942757cdb9e/lm_example http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/... [2] https://gist.github.com/yoavg/d76121dfde2618422139 https://gist.github.com/yoavg/d76121dfde2618422139
- max_ 11y agoThis site is excellent for maths!!!! I recommend it to everyone!!! Thanx sonabinu!!!
- sonabinu 11y agoThanks Max! I think it's a great resource too !!!
- theoh 11y agoFor the case of Markov chains with memory, Dasher is a good learning tool (even though the word Markov is never used). http://www.inference.phy.cam.ac.uk/dasher/ http://www.inference.phy.cam.ac.uk/dasher/ (Actually it seems I mentioned Dasher when this same link was posted in 2014, but it bears repeating.)
- erikpukinskis 11y agoInteresting you mention Dasher. A month or so it occurred to me that some variation on Dasher might be the text input method of choice in VR.
- theoh 11y agoAlong those lines, maybe also something like Fleksy or Swype, which are reportedly usable by blind people -- fleksy in particular is very smart about determining the size and orientation of the invisible "keyboard" the user is typing on.
- justifier 11y agowhen this first hit hn it had an enormous rank of 1070, and the comments are all about the breakthrough importance of markov chains for those who follow.. is this still the case? i feel like i hear less and less about markov chains are they still in research and use? is page rank still the most prominent search algo? does page rank still use markov models? i always felt these probabilistic models were a conflation of correlation and causation
- kastnerkyle 11y agoRNNs (recurrent neural networks) can be seen as generalizations of Markov chains - or as I prefer think of it, Markov chains are very limited RNNs. There is an enormous amount of research happening around these sequential models (and differentiable DAGs (directed acyclic graphs) aka neural networks in general) these days. Markov chains have never (in the work I have seen at least) tried to imply causation - purely correlation/probability. There is other recent research on causality (see the work of Pearl), but just because one thing very likely follows another doesn't mean the preceding event "caused" the next one, as both events could be side effects from the same (unobserved) root cause.
- justifier 11y agobut the difference between neural nets and markov chains is the probabilistic element of nn is the optimal traversal and could be replaced with a perfect algo if one were found to be computationally feasable whereas markov chains start from a place of probability and require it the construction stage of the markov model agrees with your statement: > just because one thing very likely follows another doesn't mean the preceding event "caused" the next one but when in use the current state is the cause of the following state informed by your model nn can simulate a system whereas an mc can only simulate data from a system
- kastnerkyle 11y agoRNNs are optimizing a probability, at least with standard training to maximize likelihood. As you say, with a different training criterion sure it could do something different - but so could a Markov chain if it was built to optimize a different objective (though it wouldn't be a Markov chain anymore I don't think). Look at reinforcement learning - loads of stuff making the Markov assumption and doing quite well on complex tasks, though once again this is quite different than a Markov chain. In theory (at least my opinion on theory) if we had an infinite size "state" it would be possible to just encode all past information in every state, and use Markov rules. It is just not practical, and much easier to extend lookup to multiple timesteps in the past especially with better understanding of optimizing things like RNNs. Choosing the maximum p(X_t+1 | X_t) does not infer causality in any way in my mind - only saying that given the data when X_t happens, some event at X_t+1 is likely to happen. Classic correlation. I don't see where you are seeing causality in that part. I also don't see a distinction in simulating a system and data from a system - to me it is just that NNs can model much more complex systems than typical Markov chains. In general I agree with you, but I find these two concepts are much, much more similar than they are different.
- Mauricio_ 11y agoThose animations are seriously burning my CPU on chrome.
- zactato 11y agoCan we cool it down with the d3 masturbation? The bouncing elastic movement of these illustrations is distracting and resource consuming.
- wodenokoto 11y agoI think it would be much more interesting with a guide to hidden markov models. I'm surprised how much focus there is on regular markov chains without any hidden units on places like hacker news.
- redsummer 11y agoI think I understand the concept. Extrapolating the example of Rainy and Sunny days, how would you model this over a year, where there is seasonal variation? In winter for instance, the rainy days would more likely to continue than sunny days. And what are the recommended methods for creating models from existing data?
- xnzakg 11y agoWoah, spent way too much time making this: http://setosa.io/markov/index.html#%7B%22tm%22%3A%5B%5B0%2C0.9%2C0%2C0%2C0%2C0%2C0%2C0.1%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0.9%2C0%2C0%2C0%2C0.1%2C0%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0.9%2C0%2C0.1%2C0%2C0%2C0%2C0%2C0%2C0%5D%2C%5B0.9%2C0%2C0%2C0%2C0.1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0.1%2C0%2C0%2C0%2C0%2C0%2C0%2C0.9%2C0%5D%2C%5B0%2C0%2C0.1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0.9%5D%2C%5B0%2C0.1%2C0%2C0%2C0%2C0%2C0%2C0%2C0.9%2C0%2C0%2C0%5D%2C%5B0.1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0.9%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0%2C0%2C1%2C0%2C0%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0%2C0%2C0%2C1%2C0%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0%2C0%2C0%2C0%2C1%2C0%2C0%2C0%2C0%5D%2C%5B0%2C0%2C0%2C0%2C1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%5D%5D%7D http://setosa.io/markov/index.html#%7B%22tm%22%3A%5B%5B0%2C0...
- agumonkey 11y agoVery nice lattice.
- vicapow 11y agoFind the source code for this and other explanations at: https://github.com/vicapow/explained-visually/tree/master/client/explanations/markov-chains https://github.com/vicapow/explained-visually/tree/master/cl...
- jokoon 11y agoI don't see how a markov chain has something to do with pagerank. I understand that pagerank use graphs, and a markov chain is some kind of graph, but I don't see anything else.
- pedrosorio 11y agoPageRank assumes your browsing activity is a Markov chain in the graph defined by hyperlinks in the web (assuming 1/n probability for each outgoing link in a page). The rank of a page is the limit #visits to the page/#total visits (which is the eigenvector of the transition matrix for eigenvalue 1)