5 ms·

That doesn't apply to an ensemble of algorithms where the weights of a given member of the ensemble are adapted based on observations from the given domain. If

That doesn't apply to an ensemble of algorithms where the weights of a given member of the ensemble are adapted based on observations from the given domain. If it did, humans wouldn't be able to choose a good algorithm for specific cases, and obviously we can. Deep neural networks can be thought of as ensembles of smaller neural networks, though of course each member of the ensemble is going to share some degree of algorithmic bias. This suggests that perhaps deep neural networks with heterogeneous activation functions and branching structures will perform better than homogeneous networks.

paulsutter 10y ago
The human brain is exactly such an ensemble of algorithms, and look at all the cognitive biases we have[1]. That our brain was developed for foraging, hunting, and reproducing could explain why the code we write is so buggy. Look I'm just kidding around. Every algorithm has its advocates, and the arguments get tedious after a while. [1] https://en.m.wikipedia.org/wiki/List_of_cognitive_biases https://en.m.wikipedia.org/wiki/List_of_cognitive_biases
IanCal 10y ago
The No Free Lunch theorem doesn't really care how your algorithm does it, and an ensemble of algorithms is just another algorithm. It certainly applies. The reason it's not actually all that useful for real world applications is that problems we value are a subset of "all possible problems" for want of a better explanation. Problems are typically smooth, that is a small change in input variables results in a small change in 'fitness', which already limits how applicable the NFL theorem is. [disclaimer, based on lectures 10 years ago now]
deong 10y ago
> If it did, humans wouldn't be able to choose a good algorithm for specific cases, and obviously we can. This is a surprisingly commonly held fallacy in some AI circles. It's the idea that humans are mathematically perfect. When you phrase it that way, it's fairly obviously false, but you still see a lot of people argue things like "NFL doesn't apply to ensembles because humans..." or "machines can never be as intelligent as humans because...". The reality is that humans are subject to the same mathematical laws as machines. It's far more likely that my brain can't solve an NP-hard problem in polynomial time either. My brain can't beat random search on the set of all possible problems.
- CuriouslyC 10y ago
  It doesn't imply that humans are mathematically perfect, but our brains are basically algorithm generating algorithms - we're not just weighting a set of preexisting solutions. To generalize quite a bit, saying NFL applies to general intelligence ends up implying there are problems for which efficient algorithms exist, but intelligence is literally incapable of discovering. That seems pretty absurd to me.
  - deong 10y ago
    The problem is that if our brains are not "magic" (essentially making this a religious argument), then they're operating via some algorithmic principles. If our brains are "algorithm generating algorithms", then I can in principle write an "algorithm generating algorithm" in silicon that does the same thing. And I know with mathematical certainty that my digital version is subject to NFL. So either my brain is too or we go back to religion to explain what non-physical process is responsible for our super-turing capabilities. The second point is that NFL is often interpreted in a weird way, where we only think about "interesting problems". It is defined on the set of all search or optimization problems. It says if your algorithm is better than exhaustive search over some subset of problems, it must be worse on the complement of that set. What does it mean for an algorithm to be efficient? Well, it's roughly speaking the number of steps it needed to take (assuming each step is the same amount of work, blah blah). OK, so an "efficient" algorithm must, by definition, prioritize some steps over others -- it's picking the "best" steps to take each time it has the choice. OK, so I'll just make up some instances of the problem that are custom-tailored so that what the algorithm thinks are the "best" steps always lead me in the wrong direction. You algorithm will then be worse than exhaustive search on my set of problems, precisely because it's choosing to avoid the steps I know to be good -- I defined the problem to make that happen. That is true of any algorithm you can conceive of. There will be problems for which the bias that makes the algorithm good on the problems you intended it to work on will be exactly the wrong bias. It doesn't matter if you say, "Aha, I'll let my algorithm generate new algorithms! Gotcha!" I'll just design a set of problems for which your algorithm generating algorithm will generate the wrong algorithms. Search is always about bias. Without bias, you have random search -- that's literally the textbook machine learning definition of bias. All NFL says is that if you have to worry about every possible problem, any bias you choose will be worse than random sometimes. There's no escape clause here. Your algorithm generating algorithm is still a search algorithm with its own biases, and it will still be worse than random on some subset of all possible problems.

paulsutter 10y ago

The human brain is exactly such an ensemble of algorithms, and look at all the cognitive biases we have[1]. That our brain was developed for foraging, hunting, and reproducing could explain why the code we write is so buggy. Look I'm just kidding around. Every algorithm has its advocates, and the arguments get tedious after a while. [1] https://en.m.wikipedia.org/wiki/List_of_cognitive_biases https://en.m.wikipedia.org/wiki/List_of_cognitive_biases

IanCal 10y ago

The No Free Lunch theorem doesn't really care how your algorithm does it, and an ensemble of algorithms is just another algorithm. It certainly applies. The reason it's not actually all that useful for real world applications is that problems we value are a subset of "all possible problems" for want of a better explanation. Problems are typically smooth, that is a small change in input variables results in a small change in 'fitness', which already limits how applicable the NFL theorem is. [disclaimer, based on lectures 10 years ago now]

deong 10y ago

> If it did, humans wouldn't be able to choose a good algorithm for specific cases, and obviously we can. This is a surprisingly commonly held fallacy in some AI circles. It's the idea that humans are mathematically perfect. When you phrase it that way, it's fairly obviously false, but you still see a lot of people argue things like "NFL doesn't apply to ensembles because humans..." or "machines can never be as intelligent as humans because...". The reality is that humans are subject to the same mathematical laws as machines. It's far more likely that my brain can't solve an NP-hard problem in polynomial time either. My brain can't beat random search on the set of all possible problems.

CuriouslyC 10y ago
It doesn't imply that humans are mathematically perfect, but our brains are basically algorithm generating algorithms - we're not just weighting a set of preexisting solutions. To generalize quite a bit, saying NFL applies to general intelligence ends up implying there are problems for which efficient algorithms exist, but intelligence is literally incapable of discovering. That seems pretty absurd to me.
- deong 10y ago
  The problem is that if our brains are not "magic" (essentially making this a religious argument), then they're operating via some algorithmic principles. If our brains are "algorithm generating algorithms", then I can in principle write an "algorithm generating algorithm" in silicon that does the same thing. And I know with mathematical certainty that my digital version is subject to NFL. So either my brain is too or we go back to religion to explain what non-physical process is responsible for our super-turing capabilities. The second point is that NFL is often interpreted in a weird way, where we only think about "interesting problems". It is defined on the set of all search or optimization problems. It says if your algorithm is better than exhaustive search over some subset of problems, it must be worse on the complement of that set. What does it mean for an algorithm to be efficient? Well, it's roughly speaking the number of steps it needed to take (assuming each step is the same amount of work, blah blah). OK, so an "efficient" algorithm must, by definition, prioritize some steps over others -- it's picking the "best" steps to take each time it has the choice. OK, so I'll just make up some instances of the problem that are custom-tailored so that what the algorithm thinks are the "best" steps always lead me in the wrong direction. You algorithm will then be worse than exhaustive search on my set of problems, precisely because it's choosing to avoid the steps I know to be good -- I defined the problem to make that happen. That is true of any algorithm you can conceive of. There will be problems for which the bias that makes the algorithm good on the problems you intended it to work on will be exactly the wrong bias. It doesn't matter if you say, "Aha, I'll let my algorithm generate new algorithms! Gotcha!" I'll just design a set of problems for which your algorithm generating algorithm will generate the wrong algorithms. Search is always about bias. Without bias, you have random search -- that's literally the textbook machine learning definition of bias. All NFL says is that if you have to worry about every possible problem, any bias you choose will be worse than random sometimes. There's no escape clause here. Your algorithm generating algorithm is still a search algorithm with its own biases, and it will still be worse than random on some subset of all possible problems.