I would not "require" people to know Markov chains but I am usually surprised how many programmers have no idea what it is and how it works and how it can be used. It is a very powerful tool to model queues which is something most distributed systems deal with :).
Show HN: Markov chains explained visually
31–40 of 96 posts
Re: Show HN: Markov chains explained visually
#32I'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.
Re: Show HN: Markov chains explained visually
#33I created a Markov chain generator: https://gist.github.com/grant/561834963dc526495c45
var numNodes=10;var roundNum=100;var a=[];for(var i=0;iroundNum)/roundNum;connections[j]=randNum;sum+=randNum}connections=connections.map(function(e){var t=e(1/sum);t=Math.round(troundNum)/roundNum;return t});sum=connections.reduce(function(e,t){return e+t});connections[numNodes-1]+=1-sum;connections[numNodes-1]=Math.round(connections[numNodes-1]roundNum)/roundNum;a[i]=connections}console.log(JSON.stringify(a))
Copy and paste the output into the side bar.
Re: Show HN: Markov chains explained visually
#34Markov chain circle generator: https://gist.github.com/grant/29afaa91349b1928b05e
Re: Show HN: Markov chains explained visually
#35I'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 playing game NPC.
Re: Show HN: Markov chains explained visually
#36I'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.
Usually, you'd have a row and column per word in your dictionary. Rows would represent the current word, and the columns would represent the next word in the sentence, with the transition probability of each cell in the matrix being determined by counting the frequency of occurence of each word pair in some body of text.
Re: Show HN: Markov chains explained visually
#37Earlier 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?
Very probably with the Viterbi algorithm: http://en.wikipedia.org/wiki/Viterbi_algorithm
Re: Show HN: Markov chains explained visually
#38This 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 mastered some basics I would enjoy it. Any recommendations will help.
Re: Show HN: Markov chains explained visually
#39I'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 ".", and only selecting a following node that is not a period, since sentences don't tend to start with punctuation. From there, use a random number generator to pick a following node based on your probability matrix, rinse, repeat.
If you'll notice, there's no guarantee that it will be grammatically correct. There's just some statistical likelihood that it will be.
Re: Show HN: Markov chains explained visually
#40That's pretty cool. The markov chain diagrams seem very similar (identical?) to deterministic finite automota. Would it be correct or incorrect to say that a Markov Chain can be thought of as a DFA where the changes in state are determined by probability?