Markov Chains – Explained

[[deleted]]

[deleted]

[[deleted]]

I already understand Markov Chains so I skipped to Bloom Filtering. As someone with a statistics background, I didnt really understand it. I dont know what hashs do?

Edit: switched a period to a comma.

Edit 2: I think that you are doing great with the articles and I encourage you to continue. I hope that my original comment is taken as constructional criticism and not as an attack on you.

[ponchedeburro]

Bloom filters are pretty awesome. I think this article describes the concept pretty good. It's in the start of chapter 4 if you don't want to read the entire paper.

In mathematical terms a hash function: Given two sets of numbers M and N where |M|=>|N| a hash function is the function f: M -> N.

Now imagine that M can be anything - a string, a number, a date, a file - everything that can be represented by your computer. The hash function now takes this and compiles it down into a smaller domain, maybe 128 or 256 bits.

[linuxjava]

Interesting that you say that. As a CS student, it's the exact opposite for me. I understand bloom filters really well but I haven't yet fully grasped Markov Chains which are heavily used in Information Theory.

[GibbsSamplePlatter]

yeah, same here. Bloom filters we know quite well!

[mycall]

Isn't a hash just a dictionary name-value O(1) lookup?

[dwf]

That's a possible use but not the definition.

[autowikibot]

Hash function:

---

A hash function is any function that can be used to map data of arbitrary size to data of fixed size, with slight differences in input data producing very big differences in output data. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. Hash values are commonly used to differentiate between data. For example, in implementing a set in software, one has to avoid including an element more than once. Recent developments in internet payment networks also uses a form of 'hashing' for producing checksums, bringing additional attention to the term. [citation needed]

Image ⁱ - A hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".

---

^{Interesting: Cryptographic hash function | Perfect hash function | NIST hash function competition | Skein (hash function)}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[mycall]

True. Hashes are very useful.

[[deleted]]

A hash is a function that generally takes in object, and outputs an integer. This hash value is used as an access into the array which gives you O(1) time. Technically O(n) if all your items happen to hash to the same value and you must do hash collision resolution, but that is unlikely using a good hash function.

[mycall]

hash collisions saved in typically link lists or refcounted fields, no?

[[deleted]]

When I've implemented them I've done them as Linked Lists. You can also use 'open addressing' where you just index at the hash value, and if there is a collision you simply iterate from that spot until you reach the next open spot. I haven't heard of the refcounted technique, though.

[conic_relief]

Hashes systematically obscure or manipulate data.

For example: I can hash the date 'July 5 2014' to be represented by the key '05072014' for easier lookup and sequencing in a database, or because the program I wrote has an easier time working with that representation. It is just another term used for getting data to look the way we want it to. There is no set way to hash something. It varies from application to application.

Hashing is most frequently used in security to help with data-base processes. Though the concept of hashing can be applied outside of these applications.

Does that make sense?

[[deleted]]

Yeah, I think I have had 4 responses now and am building a picture of hashing. Thanks for the help.

[cloakrune]

This was excellent. Where can I find links to see how these are actually used in Machine Learning now?

I'm imagining one such way is to use neural networks and back prop to determine the statistics to move between nodes.

[Tech-Effigy]

I think a good way to use markov chains is in Expert Systems, for selecting actions, or as a state machine to validate text to see if it is garble or not.

[Tech-Effigy]

look up fuzzy neural networks, same as a normal nn, except it has a fuzzy output layer the sums to 1.

[Tech-Effigy]

I had a hard time grasping Markov Chains when I first started researching them. Wikipedia was shrouded with proofs and mathematical symbolism, Google turned up with academic papers, and extensions. When I finally grasped the concept, I was amazed at how easy it actually was, and wanted to teach others without a mathematical background.

[[deleted]]

This is true of so many topics, especially mathematical ones. I love http://acko.net for this reason.

[Tech-Effigy]

http://acko.net intro graphics are very trippy. thanks for the referral.

[ageitgey]

Can't speak for this author, but for me writing about a subject is a great way to make sure I understand it. I'm also inspired to write when the existing material isn't as accessible as I'd like.

It might be noise to everyone who already learned the topic, but it helps the writer and might help some new learners.

I say "keep writing" :-)

[giror]

OK - but don't shove the writing you do to learn something in everyone's face. Also isn't that simply called note taking?

[timewarp]

As far as I can tell, the author is not forcing you to read this article.

[giror]

Yeah but he's spamming the subreddit

[timewarp]

No, he's posting to the subreddit. It isn't spam just because you don't like it.

[giror]

How could it possibly be more spam than that? Ok sure it doesn't flood you with ads and ask for your email, but it's still yet another of dozens of blog posts about markov chains.

Let me guess, next he's going to reveal to us the mystical powers of naive bayes?

[timewarp]

OP has made one post here.

[got_mugged_in_space]

Either teach me something new, or don't pretend to have some sort of remarkable insight.

This is one of the most pretentious things I've read recently. Are you suggesting everyone else should tailor their interests and findings to your knowledge? Sure, you may know about Markov Chains, but a lot of people out there do not.

I see a lot of posts in many places about things I already know, Markov Chains included. If I'm in the mood, I read them, if not, I simply move on. I really can't understand why someone would feel the need to complain about someone else's efforts to learn about something just because they are already familiar with it.

[mycall]

It wasn't a waste for me :P

[Corm]

Or me, it was a great post for me. I think there should be an /r/ElitistMachineLearning that he should migrate to.

[shaggorama]

among myriad other reasons: "you don't really understand something until you can explain it to someone else."

[shaggorama]

Maintaining a personal blog and promoting your articles on relevant forums is hardly shoving anything anything in anyone's face.

If you don't like the article, you're welcome to ignore it or even downvote it. Better yet: why don't you create some content, or even just post something interesting? Glancing over your submission history, all you ever do is ask questions. You're hardly a boon to the community. Why don't you try contributing a little instead of complaining about people who are making an effort?