Machine learning is easier than it looks
I'd like to chime in here as a mathematician.<p>Many people here express their feelings that math or computer science papers are very difficult to read. Some even suggest that they're deliberately written this way. The truth is that yes, they in fact are deliberately written this way, but the reason is actually opposite of many HNers impression: authors want to make the papers <i>easier</i> to understand, and not more difficult.<p>Take for example a page from a paper that's linked in this article. Someone here on HN complains that the paper talks about "p being absolutely continuous with respect to the Lebesque measure on En", hundreds of subscripts and superscripts, and unintuitively named variables, and that it makes paper very difficult to understand, especially without doing multiple passes.<p>For non-mathematicians, it's very easy to identify with this sentiment. After all, what does it even mean for a measure to be absolutely continuous with respect to Lebesgue measure. Some of these words, like "measure" or "continuous" make some intuitive sense, but how can "measure" be "continuous" with respect to some other measure, and what the hell is Lebesgue measure anyway?<p>Now, if you're a mathematician, you know that Lebesgue measure in simple cases is just a natural notion of area or volume, but you also know that it's very useful to be able to measure much more complicated sets than just rectangles, polyhedrals, balls, and other similar regular shapes. You know Greeks successfully approximated areas of curved shapes (like a disk) by polygons, so you try to define such measure by inscribing or circumscribing a nice, regular shapes for which the measure is easy to define, but you see it only works for very simple and regular shapes, and is very hard to work with in practice. You learned that Henri Lebesgue constructed a measure that assigns a volume to most sensible sets you can think of (indeed, it's hard to even come up with an example of a non-Lebesgue-measurable set), you've seen the construction of that measure, and you know that it's indeed a cunning and nontrivial work. You also know that any measure on Euclidean space satisfying some natural conditions (like measure of rectangle with sides a, b is equal to product ab, and if you move a set around without changing its shape, its measure shouldn't change) must already be Lebesgue measure. You also worked a lot with Lebesgue measure, it being an arguably most important measure of them all. You have an intimate knowledge of Lebesgue measure. Thus, you see a reason to honor Lebesgue by naming measure constructed by him with his name. Because of all of this, whenever you read or hear about Lebesgue measure, you know precisely what you're dealing with.<p>You know that a measure p is absolutely continuous with respect to q, if whenever q(S) is zero for some set S, p(S) is also zero. You also know that if you tried to express the concept defined in a previous sentence, but without using names for measures involved, and a notation for a value a measure assigns to some set, the sentence would come out awkward and complicated, because you would have to say that a measure is absolutely continuous with respect to some other measure, if whenever that other measure assigns a zero value to some set, the value assigned to that set by the first measure must be zero as well. You also know, that since you're not a native English speaker (and I am not), your chance of making grammatical error in a sentence riddled with prepositions and conjunctions are very high, and it would make this sentence even more awkward. Your programmer friend suggested that you should use more intuitive and expressive names for your objects, but p and q are just any measures, and apart from the property you're just now trying to define, they don't have any additional interesting properties that would help you find names more sensible than SomeMeasure and SomeOtherMeasure.<p>But you not only know the definition of absolute continuity of measures: in fact, if that was the only thing you knew about it was the definition, you'd have forgotten it long ago. You know that absolute continuity is important because of a Radon-Nikodym theorem, which states that if p is absolutely continuous with respect to q, then p(A) is in fact integral over A of some function g with respect to measure q (that is, p(A) = int_A g dq). You know that it's important, because it can help you reduce many questions about measure p to the questions about behaviour of function g with respect to measure q (which in our machine learning case is a measure we know very, very well, the Lebesgue measure).<p>You also know why the hell it's called absolutely continuous: if you think about it for a while, the function g we just mentioned is kind of like a derivative of a measure of measure p with respect to measure q, kind of like dp/dq. Now, if you write p(A) = int_A (dp/dq) dq = int_A p'(q) dq, even though none of the symbols dp/dq or p'(q) make sense, it seems to mean that p is an "integral of its derivative", and you recall that there's a class of real valued functions for which it is true as well, guess what, the class of absolutely continuous functions. If you think about these concepts even harder, you'll see that the latter concept is a special case of our absolutely continuous measures, so all of this makes perfectly sense.<p>So anyway, you read that "p is absolutely continuous with respect to Lebesgue measure", and instantly tons of associations light up in your memory, you know what they are working with, you have some ideas why they might need it, because you remember doing similar assumption in some similar context to obtain some result (and as you're reading the paper further, you realize you were right). All of what you're reading makes perfect sense, because you are very familiar with the concepts author introduces, with methods of working with them, and with known results about them. Every sentence you read is a clear consequence of the previous one. You feel you're home.<p><i>...</i><p>Now, in alternate reality, a nonmathematician-you also tries to read the same paper. As the alternate-you haven't spent months and years internalizing these concept to become vis second nature, ve has to look up every other word, digress into Wikipedia to use DFS to find a connected component containing a concept you just don't yet understand. You spend hours, and after them you feel you learned nothing. You wonder if the mathematicians deliberately try to make everything complicated.<p>Then you read a blog post which expresses the idea behind this paper very clearly. Wow, you think, these assholes mathematicians are really trying to keep their knowledge in an ivory tower of obscurity. But, since you only made it through the few paragraphs of the paper, you missed an intuitive explanation that's right there on that page from an paper reproduced by that blog post:<p><i>Stated informally, the k-means procedure consists of simply starting with k groups each of which consists of a single random point, and thereafter adding each new point to the group whose mean the new point is nearest. After a point is added to a group, the mean of that groups is adjusted in order to take account of that new point</i><p>Hey, so there was an intuitive explanation in that paper after all! So, what was all that bullshit about measures and absolute continuity all about?<p>You try to implement an algorithm from the blog post, and, as you finish, one sentence from blog post catches your attention:<p><i>Repeat steps 3-4. Until documents’ assignments stop changing.</i><p>You wonder, but when that actually happens? How can you be sure that they will stop at all at some point? The blog post doesn't mention that. So you grab that paper again...