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

71–80 of 96 posts

Re: Show HN: Markov chains explained visually

#74

Post by chatmasta »

TazeTSchnitzel wrote: post #61
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.

Yeah, your comment breaks the readability of this comment thread on my mobile (as in, everything is horrible stretched horizontally).

Re: Show HN: Markov chains explained visually

#75

Post by microtonal »

regularfry wrote: post #37
Orangeair wrote: post #22

Earlier quoted context omitted.

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

Viterbi is used for decoding e.g. HMMs, when there are multiple possible state sequences given the observations, and you want to find the most probable. In a normal (non-hidden) Markov model, you can just follow the state transitions and get out a probability (or go to a state and see what the next possibilities are).

Re: Show HN: Markov chains explained visually

#76

Post by chatmasta »

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.

Yeah, same. The first time I ever heard "Markov chains" was when I was a 13-year-old hanging out on black hat SEO forums. Back in the day, software like "YASG" (or something like that, "yet another site generator") made a lot of money with simple PHP scripts for rewriting Wikipedia articles with Markov chains, thus skirting Google's duplicate content algorithms, which were much weaker at the time.

There were actually quite a few vulnerabilities back then. I wrote a script that allowed me to create a Google account with the IP address of a visitor to the website, all without them knowing. All I had to do was open the registration page with a server side script, download the CAPTCHA, display it to the user and ask them to fill it out. When they filled it out, the submitted form targeted the Google registration form in a 1x1 iFrame, then another button targeted the logout form. Google was not checking the referrer of the sign up form, nor was it comparing the IP address that received the CAPTCHA to the one that submitted it.

I had a friend load that script into thousands of generated blogspot blogs, which got long tail google traffic and asked the user to "fill the CAPTCHA to continue." The script ran for ~2 weeks and generated ~60000 Google accounts all from unique IP addresses.

That was around 2007, so obviously it's all patched up by now. I was 15 years old and never did anything with the accounts, so if anyone from google is reading this, keep the lawyers away from me please.

Blackhat SEO actually has a lot of clever tricks. I haven't been part of that space in a while, for a lot of reasons, but I can attribute 99% of my knowledge of marketing to time spent trawling through blackhat SEO forums reading not my about that, but also landing page optimization, conversion tracking, copywriting, etc. It was definitely a worthwhile learning experience for me.

Oops that veered off topic. But yes, Markov chains. Blackhat content generation. :)

Re: Show HN: Markov chains explained visually

#77

Post by girvo »

vicapow wrote: post #73

There was a bug in the playground earlier that I just fixed that allows you to share your Markov chains via the url hash. For example: http://setosa.io/markov/#%7B%22tm%22%3A%5B%5B0.9%2C0.1%2C0%2...

Hey, I think that link is so long it's breaking HN's layout! Reckon you can chuck it in a URL shortener or something? :)

Re: Show HN: Markov chains explained visually

#78

Post by swimfar »

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.

Here's a nice introduction/exercise which is part of a python tutorial.

http://www.greenteapress.com/thinkpython/html/thinkpython014...

Post reply on HN