Algorithm efficiency comes from problem information
stochasticlifestyle.com
stochasticlifestyle.com
When one wants to use the best ML model "in production" (after all the exploration is done and dusted), or when there is a "domain expert" who can specify the right biases to encode into the algorithm (i.e. problem information), the point made in the post is very valid.
Often, however, the point of using ML is to tease out some property that is not apparent previously. In that case, the hope is to use some class of algorithms (eg: neural networks) with the right general biases (eg: convolutional layers and RELU activations, or share the first few layers of VGG) so that it can pull out the appropriate aspects from the problem specification that you did not know to ask for.
From this perspective, the challenge lies in the 'No Free Lunch' theorem which implies that unless you known enough about the problem to indirectly encode the correct biases (eg: In the case of image classification -- choosing neural networks, convolutions, etc. rather than a decision tree) you can never win the game.
No free lunch isn't about choosing the right biases, it says that a single model cannot solve every problem. And in fact any solver will have accuracy equivalent to chance when averaged across all problems. Here's an example:
There are four possible one bit to one bit functions, I and ~ (the identity and inverse functions), as well as T and F (True and False). If you create a truth table for all four of those functions:
func input output
I 0 | 0
I 1 | 1
~ 0 | 1
~ 1 | 0
T 0 | 1
T 1 | 1
F 0 | 0
F 1 | 0
That's what the No Free Lunch theorem states: that across all possible functions in your space, you can do no better than chance, because for any function F that you approximate exactly, I can define a function "!F" (or in a non-binary space, a family of functions) which you are exactly 0% accurate on. This is true no matter the algorithm or assumptions you choose.
Similarly, I can define a classification algorithm that has no implicit assumptions about what I am classifying, other than that it can be classified, but still achieves 100% accuracy on any specific problem I apply it to:
For every possible input in your function space, get the ground truth label from some external function, throw those all into a mapping (a very, very large mapping) and then just look up the input in the mapping when requested.
For image classification, this means a mapping of all possible NxN images to a boolean: "Contains dog". You might even, as an optimization make this more space efficient by picking certain pixels that are more impactful and looking at them first, so that you don't have to store every image. That sounds an awful lot like a decision tree ;)
Tl'dr: 'No Free Lunch' has nothing to do with the efficiency of the encoding, but instead with the ability to have a perfect agent that can solve every problem.
Sure but I think the failure of neural nets to solve PDAs was significant as a negative. You'd like a machine learning algorithm to get information you didn't think of but at this point it seems like they succeed only in certain circumstance. Describing the instances would help characterize the limits of present ML and how it can go further.
I’ve phrased the same idea as “what regularity of the problem space is my algorithm exploiting?” A good first question to demistify any purported fast algorithm.
I like your phrase too, as there are classes of knowledge about a problem that don't necessarily reduce the domain, depending on how you look at it, but can still be exploited.
I think neural nets and deep learning systems are misunderstood so profoundly because humans are bad at many kinds of reasoning and the explanation of the neural net being "smart" is so psychologically appealing.
Where did the author get this idea? It can be done more efficiently than that: https://mathoverflow.net/a/52557/40272
So no, the article is wrong.
http://theory.epfl.ch/vishnoi/CargeseLectures.pdf
Still, the point stands that you'd never want to actually solve a large system "the generic way" unless you really have to (i.e. you cannot identify a structure for which you have a faster algorithm).
The best currently known exponent for square matrix multiplication is around 2.3728; Wikipedia's page on matrix multiplication has a reference.
No wonder I never heard about these. I updated it for correctness (and fixed the link, ugh) but yeah, these are details I'd hope to not dwell on in the post since for all intents and purposes you'd still never want to do the worst fallback unless you have to.
The outermost, most -general, and least-tractable problem being "Do what's needed for whatever."
No, I don't think this is even close for most problems. Neural networks, maybe, but they're an unusually simple case where everyone uses similar, largely GPU accelerated code.
If you're looking to make your machine learning software faster, writing a new piece of fundamental GPU code to beat cuDNN could possibly be faster but probably won't get you very far. But changing your model to better match the data could make the problem orders of magnitude easier.
BLAS libraries are all within the range of each other because they all store memory in basically the same way, do indirection in basically the same way, care for the cache in basically the same way and do SIMD in basically the same way.
As soon as you step out of those prebuilt blocks and build your own function over squares of numbers, you're going to be losing far more than a factor of 3 until you understand how to handle these issues.
I think he said the exact opposite. He's basically saying algorithmic time complexity matters (and therefore identifying your problem class matters, since you might get a more efficient algorithm out of it) since you can only get so far with the generic algorithm, however good your implementation is.
Both the broad-strokes algorithm and the fine details are responsible for huge performance differences.
The same high-level algorithm might be implemented inside an old, highly optimised FORTRAN program and then get transliterated into a use-once MATLAB script which runs 100 times slower because the vectorisation voodoo wasn't quite right.
In the latter case, people might not bother fixing it because the hour it would take is longer than the run-time. Or maybe the run-time cost is weeks, but the people doing it are scientists and understanding computers isn't their job.