This totally reminds me of SpaceChem on higher levels (puzzle game for programmers).
Show HN: Markov chains explained visually
21–30 of 96 posts
Re: Show HN: Markov chains explained visually
#22Beautiful. 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.
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?
Re: Show HN: Markov chains explained visually
#23"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
#24Earlier 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?
That's indeed one way to implement predictive typing. Looking up the list of possible words is not expensive, you basically step through a small automaton. The challenge is making the models small enough to fit it on a phone. See e.g.:
http://hnk.ffzg.hr/bibl/acl2007/EMNLP-CoNLL2007/pdf/EMNLP-Co...
Re: Show HN: Markov chains explained visually
#25Really cool: well done!
Re: Show HN: Markov chains explained visually
#26Thank 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.
A short overview of using HMMs for speech recognition:
Speech is temporal, a speech sample can be represented as a sequence of data points. Thus, a simple way to compare two speech samples can be an algorithm to compare their corresponding sequences. One such algorithm is DTW, which is an equivalent of the Levenshtein distance algorithm for comparing strings.
So now we have a method of comparing two speech samples. Thus, a simple way to recognize an unknown speech sample can be to keep samples of all possible utterances (phonemes, words, sentences) and just return the best match. That’s not possible - so in speech recognition, they only keep samples of phonemes, and try to find the most likely concatenation of them relative to the unknown sample. The search space is huge, but luckily dynamic programming algorithms exist to make the search fast (they’re called Connected Word Recognition algorithms).
The problem with this approach is that it does not scale. There are tons of variations possible for the same spoken unit (different styles and durations). This is where the Hidden Markov Model comes in. A single HMM can be used to represent all variations of that unit. For example, it can be used to represent multiple speech samples of the word “apple”, or of the phoneme “æ” and so on. There are methods for evaluating the similarity of an HMM and a speech sample, and for training an HMM using multiple samples.
You can also connect phoneme HMMs together to get a big HMM representing words/sentences. The same CWR algorithms as before apply.
Re: Show HN: Markov chains explained visually
#27The one thing to add to this is that usually each state doesn't emit a single token ("I am in state 1" then "I am in state 2") but instead you assume that each state has a range of possible actions and the likelihood of a choice of action varies with state.
So if might not be that your model is sunny versus rainy but instead cold front v warm front. Since rain is more likely during a cold front your observation of rain increases your belief that the system is in the "cold front" state.
Re: Show HN: Markov chains explained visually
#28Good lecture on Markov models:
Re: Show HN: Markov chains explained visually
#29Excellent visualization!
Re: Show HN: Markov chains explained visually
#30Earlier 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?
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 language modeling.
Hidden Markov Models: http://en.wikipedia.org/wiki/Hidden_Markov_model
Kurzweil's Book (He goes into more detail on speech recognition as well as a slew of other topics): http://www.howtocreateamind.com/