Proverbs, adages, theorems. Give a few words the ring of truth (or better yet, prove them) and all of a sudden they seem to get pulled out of the bag to support all manner of stances on a subject. And who’s going to challenge them – after all we know they’re true.
You can’t make a horse drink, but you can lead it to water
Recently, in response to the subject of technologies being developed here and elsewhere, a colleague of Algorithm1 – a mathematician – remarked that general-purpose machine learning was a flawed pursuit. There can be no successful general purpose machine learning algorithms, he said, because algorithms must each be tailored to the problem domain, and that tailoring necessarily requires human expertise.
There are at least two noteworthy things going on here. The latter point – about human intervention – belies some unduly pessimistic presumptions regarding both the scope of what constitutes an algorithm, and the upper bounds of what they are capable of. Let’s put that weighty subject on the back-burner for now.
Perhaps more generally, the statement (intentionally or otherwise) embodies a popularly less-than-apt advocation of Wolpert & Macready’s “No Free Lunch” Theorem.
“No Free Lunch” states that for every problem at which a given algorithm excels, there must be a problem at which is peforms abysmally. The oft-quoted corollary being that there can be no single algorithm which is optimal in every case (ergo we must somethow “select” the most appopriate algorithms). This theorem is, by all accounts, mathematically and philosophically sound. However, like many mathematical and philosophical truths, there are fundamental – potentially insurmountable – caveats which must be considered if planning to apply it to the real world. In this case the clanger of a caveat is that “No Free Lunch” considers the space of all conceivable problems.
This would include, for example, the problem of rebuilding the Eiffel Tower using one less girder without destroying its symmetry. Equally, it would include the problem of rebuilding the Eiffel Tower using one less girder without destroying its symmetry, but without applying any of the rules or approaches used by the previous algorithm. It would also include the problem of designing a set of n algorithms which are each able to rebuild the Eiffel Tower using one less girder without destroying its symmetry, such that none of those algorithms share any rules or approaches. And also, for example, the problem of doing the above only in cases where n is the square of a prime number, whilst strictly failing to come up with any solution otherwise, yet without directly testing whether n is a square of a prime. Perhaps that last one isn’t actually possible; in which case let us include the problem of deciding whether it is possible or not. (Repeat ad-infinitum with famous landmarks and arbitrary constraints of your own perverse choosing).
Veritable Loaves and Fishes
The space of all conceivable problems is – lest the point wasn’t sufficiently laboured above – as infintely impractical as it is practically infinite. Starkly on the other hand, the problems that we are likely to wish algorithms to solve in real life, while also perhaps practically infinite, represent a tiny (practically infinitessimal in fact) subset of all conceivable problems. Moreover, it is an infinitessimal subset with strongly unifying characteristics; that is to say that the problems are, on the whole, extremely close together in the space of all conceivable problems. The majority of real world problems are, for example sparse, locally smooth, “Kolmogorov-simple”, and possessed of interesting, decidely non-arbitrary structural qualities such as self-similarity. And where they are not, it seems likely that inherently they are, but that they have crossed the threshold of complexity into chaos. And that is probably a place where no algorithms can follow.
As we cannot contend the No Free Lunch Theorem – which is after all exactly correct within its scope – we may do well to coin another, cheerier one, to offset its undue burden upon the field of Machine Learning. So let’s get that out of the way now…
“For the vast majority of problems relevant to human kind, there exist a practically uncountable number of algorithms which excel, each in subtly different ways, and many which can excel at most.”
The Smörgåsbord Theorem (Washtell et al, 2013)
Now we just need to find them.