6 ms·

In a data mining / machine learning class I took in university a key point my teacher made was that of the 'No free lunch' theorem. In that class the theorem wa

In a data mining / machine learning class I took in university a key point my teacher made was that of the 'No free lunch' theorem. In that class the theorem was offered on its face and I haven't yet read the original paper (just summaries and recounts) (http://web.archive.org/web/20140111060917/http://engr.case.edu/ray_soumya/eecs440_fall13/lack_of_a_priori_distinctions_wolpert.pdf http://web.archive.org/web/20140111060917/http://engr.case.e...), but the point of the theorem feels very related to the point the author makes. The thesis boils down to: 'not having seen the data, there is no universally superior algorithm'. The author's point of view seems to comport with this theorem. I haven't gone through the paper myself, so I can't argue for or against it. However, in my experience as a professional statistician that has used Random Forests, SVMs, Neural Networks, etc --- finding the right algorithm takes 'feature engineering' (http://blog.kaggle.com/2014/08/01/learning-from-the-best/ http://blog.kaggle.com/2014/08/01/learning-from-the-best/) and close inspection of the data and basis function. Are the data fit well by rectangles? Then you'll want to use decision trees / random forests. Curvy? Give SVM a try. Do the data take intricate patterns? Look into boosting (fitting on residuals recursively). Feature engineering boils down to the old statistical phrase, 'live with the data.' That is, you actually need use your own mind and beliefs to organize inputs prior to feeding them into an algorithm. So in my experience, what seems to be true in Kaggle competitions, and the perspective of this author, it's true --- algorithms are either tightly constrained and perform really well at a specific task, or they perform poorly (but quickly) in a broad sense.

elsewhen 12y ago
if our computing systems continue to get significantly more powerful, won't a brute-force system obviate feature engineering? in other words, can't kaggle eventually be outcompeted by an algo-of-algos that iterates through all known approaches and then settles on the ideal candidate?
- RA_Fisher 12y ago
  Hmm, great question. The caret package made for R might actually make that loop possible: http://caret.r-forge.r-project.org/ http://caret.r-forge.r-project.org/ However, in my experience it's really easy to accidentally ask caret to iterate over a grid of parameters for just one model that would effectively take forever to complete (the useful grids change for each dataset). My bet would be that the algorithm space will expand with more and more computationally intensive methods such that we're always chasing this brute-force method. Even with this great 'caret' abstraction layer today, boy would it be hard to run through even a handful of algorithms in an algorithmic way (not having seen the data ahead of time).
pjscott 12y ago
Where would you categorize human minds in your taxonomy of learning algorithms?
- RA_Fisher 12y ago
  Oh boy, good question. First, I'm not an AI expert, I don't even casually practice AI. I'm not a machine learning expert. I am a statistician that applies machine learning methods a handful of times per year. That to say --- I find Bayes rule to be eerily similar to the way I think a human mind learns. We operate with degrees of belief, we couple those beliefs with new information and update our beliefs. The word taxonomy is heavily loaded, ultimately I'd say if AI were taken to it's logical end it would actually produce a human brain. Let me explain. Consider a map of your city as a model. If that map contained every drain, street lamp, and stop sign --- it wouldn't be a very useful map. It would be so detailed that it would be overwhelming and a poor tool for navigating a city. That's why we use maps, lower-order abstractions. But imagine that a map were your city. That it was your city shrunk down so that you could hold it in your hand. Would it be a model? A map? Would it be your city? Of course this is a fantasy, but the way I see AI is the map. AI researchers are working to convert that map to the actual city with the goal of actually learning about the human mind. So I think rather than giving a glib answer about categorizing the human mind, I'll just say that the category is whatever 'map' AI researchers end up with when we agree that what they've created is a human mind. :-) Edit: for those interested, here are some slides that mention 'no free lunch': http://www.cse.unsw.edu.au/~mike/ml4as/11/l00-2x2.pdf http://www.cse.unsw.edu.au/~mike/ml4as/11/l00-2x2.pdf
  - pjscott 12y ago
    What I was getting at is that any no-free-lunch objection you make to learning algorithms in general also applies to the specific learning algorithm in our heads -- and yet we manage to function well enough to have this conversation.
    - RA_Fisher 12y ago
      Very good point. :-)
TeMPOraL 12y ago
> The thesis boils down to: 'not having seen the data, there is no universally superior algorithm'. We humans apparently found a way around it by a) examining the data, and b) selecting the best algorithm. It's a meta-level algorithm and could AI not do the same? (it's meta-level but there's a closure here; you can apply the same bayesian reasoning to select algorithms as you would do on actual data set)

elsewhen 12y ago

if our computing systems continue to get significantly more powerful, won't a brute-force system obviate feature engineering? in other words, can't kaggle eventually be outcompeted by an algo-of-algos that iterates through all known approaches and then settles on the ideal candidate?

RA_Fisher 12y ago
Hmm, great question. The caret package made for R might actually make that loop possible: http://caret.r-forge.r-project.org/ http://caret.r-forge.r-project.org/ However, in my experience it's really easy to accidentally ask caret to iterate over a grid of parameters for just one model that would effectively take forever to complete (the useful grids change for each dataset). My bet would be that the algorithm space will expand with more and more computationally intensive methods such that we're always chasing this brute-force method. Even with this great 'caret' abstraction layer today, boy would it be hard to run through even a handful of algorithms in an algorithmic way (not having seen the data ahead of time).

pjscott 12y ago

Where would you categorize human minds in your taxonomy of learning algorithms?

RA_Fisher 12y ago
Oh boy, good question. First, I'm not an AI expert, I don't even casually practice AI. I'm not a machine learning expert. I am a statistician that applies machine learning methods a handful of times per year. That to say --- I find Bayes rule to be eerily similar to the way I think a human mind learns. We operate with degrees of belief, we couple those beliefs with new information and update our beliefs. The word taxonomy is heavily loaded, ultimately I'd say if AI were taken to it's logical end it would actually produce a human brain. Let me explain. Consider a map of your city as a model. If that map contained every drain, street lamp, and stop sign --- it wouldn't be a very useful map. It would be so detailed that it would be overwhelming and a poor tool for navigating a city. That's why we use maps, lower-order abstractions. But imagine that a map were your city. That it was your city shrunk down so that you could hold it in your hand. Would it be a model? A map? Would it be your city? Of course this is a fantasy, but the way I see AI is the map. AI researchers are working to convert that map to the actual city with the goal of actually learning about the human mind. So I think rather than giving a glib answer about categorizing the human mind, I'll just say that the category is whatever 'map' AI researchers end up with when we agree that what they've created is a human mind. :-) Edit: for those interested, here are some slides that mention 'no free lunch': http://www.cse.unsw.edu.au/~mike/ml4as/11/l00-2x2.pdf http://www.cse.unsw.edu.au/~mike/ml4as/11/l00-2x2.pdf
- pjscott 12y ago
  What I was getting at is that any no-free-lunch objection you make to learning algorithms in general also applies to the specific learning algorithm in our heads -- and yet we manage to function well enough to have this conversation.
  - RA_Fisher 12y ago
    Very good point. :-)

TeMPOraL 12y ago

> The thesis boils down to: 'not having seen the data, there is no universally superior algorithm'. We humans apparently found a way around it by a) examining the data, and b) selecting the best algorithm. It's a meta-level algorithm and could AI not do the same? (it's meta-level but there's a closure here; you can apply the same bayesian reasoning to select algorithms as you would do on actual data set)