Algorithms and Theory: A research HOWTO

- Determine desired theorem statement
- Design an associated algorithm
- Prove that algorithm satisfies the claims of the theorem
Machine Learning: A research HOWTO

- Determine desired algorithm
- Design associated theorem statement
- Prove that theorem holds for given algorithm

This (slightly tongue-in-cheek) characterization of the ML and Algorithms research cultures does have a bit of truth. If you ask a typical Algorithms person at a conference for a quick summary of his/her result, they'll tell you "we have a $2 + \epsilon$ approximation to the foobar problem". Similarly, if you ask someone at NIPS what their paper is about, they'll say "we have a faster way to do belief propagation for certain graphs" or "we have a modified version of boosting for sparse data". In other words, the former emphasizes the new bound or result, whereas the latter emphasizes the technique.

This has implications for both sides. If you want to know about, say, the known results on approximations for the "sparsest cut problem", an informed approx-algs researcher can quickly give you the known lower-bounds, upper-bounds, and open problems. But if you ask for the methods that achieves the upper bound, you will likely be sent to a 50+ page technical result describing the details. Often, results with only modest improvements on previous work use vastly different methods.

Machine Learning, on the other hand, suffers from quite a different problem. If you ask an ML researcher how to do binary classification, he/she can give you an array of simple and intuitive algorithmic frameworks. But the theoretical results motivating these algorithms are often scattered and incomparable (think Boosting vs SVM).

So, who should be more like the other? What do y'all think?

Hal's recent post on a very similar theme nicely summarised the two styles nicely as: "COMPUTATIONAL statistics" vs. "computational STATISTICS".

ReplyDeleteHow does the old saying go? "The difference between theory and practice is that, in theory, there is no difference between theory and practice but, in practice, there is."

The obvious (and not completely satisfying) answer to who should be more like the other is "Neither. There should be more interaction between these styles so that both camps can build on the other's strengths."

Of course, implementing that answer is another matter... I suspect part of the solution is a cultural one. Posts like this one and Hal's are a good start in telling the community that the different perspectives should be valued. Whether this turns into favourable peer reviews for people working to bridge the gap is another matter.

I think this dichotomy can be mostly explained by the maturity of both fields and by the simple fact that algorithms are purely a mathematical constructs -- so they only need to have internal consistency.

ReplyDeleteI see machine learning as more of a science that needs to be consistency with the world first, and internaly second.

Virtual machines are separated into two major categories, based on their use and degree of correspondence to any real machine. running machine

ReplyDelete