Can Gradient Boosting Learn Simple Arithmetic?
mariofilho.com
mariofilho.com
The point to keep in mind here is that addition is a recursive function [2] and as such cannot be learned by learners that cannot model recursion, which is basically all statistical machine learners. The best thing that can be done is to approximate it within some range, at which point you're only memorising which pairs of numbers X and Y map to which third number Z - like the model in the article does. And it doesn't even do it very well, hence the need for noise (which allows it to luck out and cover more XYZ triples).
So let's say that a better title would be "Can GB approximate arithmetic functions over a tiny range of numbers?". Which is not that exiting, for sure [3].
____________________
[1] The only good reason I can think to not validate on a test partition is that you only have a single example. I can think of one use case, trying to learn plans from examples of starting and goal states. But arithmetic? How can you claim to have learned "arithmetic" when you can't show that your model works on even one pair of numbers it hasn't seen in training?
[2] https://en.wikipedia.org/wiki/Peano_axioms#Addition
[3] This is also a good example of the limitations of statistical machine learning, in general. Having "learned" addition, a strong learner should be able to use it to learn the other three functions. Except, statistical machine learners can only learn one concept at a time, and they can't reuse their models as features to learn new concepts.
https://deepmind.com/blog/learning-explanatory-rules-noisy-d...
They have one experiment were they learn the less-than relation between images of digits. Pretty cool stuff.
However- my preference would be a system that combined statistical and symbolic learning. For machine vision specifically, the statistical learner (a CNN most likely) would extract features and these would then become the universe of discourse for the background knowledge of the symbolic learner. This is highly speculative and I haven't done any sort of practical work towards that but I've discussed some of the complications with coleagues and I think that they can be overcome.
Their main contribution seems to be that they have incrementally improved on a symbolic learner. They explicitly tell it to search a predefined set of programmes. They use pretrained MNIST CNN classifiers as inputs into it, which already know that e.g. MNIST has 10 classes.
What I was talking about is symbolic reasoning somehow 'emerging' from a connectionist approach, without being explicitly designed. The cool thing about deep nets is that they are both kind of biologically and evolutionary plausible (except back-propagation, I suppose), and are able to achieve great performance on a bunch of traditionally difficult perception tasks (vision, hearing - again, with some caveats).
But how such a system could develop symbolic reasoning is not at all clear. Are any other biological systems apart from humans capable of symbolic reasoning?
Of course, planes don't flap their wings and so a practical system will probably have a symbolic reasoning engine designed top-down rather than emerging from some neural net. But it is still an interesting question that would give us more insight into how our brains work.
Well, I'm not really the right person to discuss this issue since I can't claim to understand how the brain works. However, I do understand a few things about connectionist methods and it's my understanding that they are not very good models of the way the brain works at all (am I misrepresenting your turn of phrase, of "biologically plausible"?). In that sense, I doubt it's possible that a neural net would develop symbolic reasoning by dint of being in some way similar to a biological brain.
In general, my experience with neural nets and gradient optimistation techniques is that unless a great deal of effort is spent directing their learning, they are prone to learn whatever is convenient, which is very often not what the human users want it to.
For instance, see the following collection of anecdotes of evolutionary algorithms lerning whatever they please, rather than what the researchers were trying to teach them:
https://arxiv.org/abs/1803.03453
Or the descriptions of the difficulties of training Deep Reinforcement Learning models in this article:
https://www.alexirpan.com/2018/02/14/rl-hard.html
Also, while I'm a staunch symbolicist myself, I'm not 100% convinced that symbolic reasoning is "natural". I think it rather took a lot of effort to develop such systems and most people still have a great deal of trouble using them with precision. If you meant to say that symbolic reasoning should arise spontaneously in a neural network, I see that as very unlikely.
This is one of the theories learned by the δILP system for the less-than relation between images of numbers, taken from the pdf version of the paper [1]. Using Prolog as the notation (the transformation from the article is trivial):
target:- image2(X), pred1(X).
pred1(X) :- image1(Y), pred2(Y,X).
pred2(X,Y) :- succ(X,Y).
pred2(X,Y) :- pred2(Z,Y), pred2(X,Z).
a) Y = X+1
b) Y > Z AND X < Z
So, yes, totally, it will generalise to integers with any number of digits.
________________
[1] https://arxiv.org/pdf/1711.04574.pdf
The learned theory is on page 34.
You are correct that this model will not generalize to numbers outside this range.
My goal was just to have a reference when this questions comes up in a discussion about creating feature interactions that are about differences, multiplications, etc.
So I wanted to show that, yes, the model is capable of approximating it. Of course, we would need a sample that covers the necessary range to generalize.
This is a good topic for a future article.
I appreciate your effort to create a point of reference for discussions of this issue, however, that is where precision is needed. There is already much confusion around the power and the limitations of machine learning and experienced practitioners should work to minimise this confusion.
I am looking forward to reading your future article on the topic.
For gradient boosted trees, you first need to grow a single tree. That tree starts with a single leaf and then needs to be split to try and improve performance. But because the data is perfectly antisymmetric, no suitable split can be found. So the growing process terminates. Gradient boosting can't help you, because the residuals to train the next tree on are identical to the original data.
If you add even the slightest amount of imbalance to the data, e.g. by sampling random positions instead of using a grid, the problem disappears.
I opened an issue on Github. This didn't seem obvious to many people that read the article, so it's nice that now we can keep this in mind while using the model:
[1]: https://datascience.stackexchange.com/questions/25024/strang...
I should do it myslef but have no background in applications.