Machine learning leads mathematicians to unsolvable problem
nature.com
nature.com
Reflects poorly on the authors, regardless of the actual merits of their finding.
[1] https://www.forbes.com/sites/samshead/2018/04/30/tech-giant-...
Last time I checked, fees for participating in ML related conferences are very high (compared to registration fees for conferences in academic fields with less hype). This makes them less open because cost is a financial barrier to participation.
[Hi from Argentina!]
Formulating a proposition that is independent of standard axioms is simple. Formulating it in the language of machine learn is an exercise. The main thing is the authors didn't provide any motivation for this to matter to the overall enterprise of machine learning, because there isn't motivation for this. It's just a novelty.
i.e. Why should people have to pay to view the results of what is often publicly funded research? Even more so why should researchers have to pay to publish work that the publishers profit off of but the researchers don't.
Or maybe I’m just taking crazy pills..
There will always be someone who defends publishers based on not knowing anything about how scientific publishing works.
I would even venture to say that most researchers will be against the idea of paid reviews, just like Amazon found out that paid product reviews are a very bad idea.
You are. Where did you ever get the idea that nature pays for reviews?
Aggregability is NP-Hard: https://www.google.com/url?sa=t&source=web&rct=j&url=http://...
That is, even for linear systems, determining whether or not macrovariables (e.g. complete eigenvector sets, complete embeddings) exist for a given space is an NP-Hard problem. With linear systems serving as, effectively, a lower bound for ML problems (because, otherwise, why are you even ML'ing the thing?), whether or not a problem is "learnable" is, unsurprisingly, probably NP-Hard. Aggregability and learnability look staggeringly similar to me.
Demonstrating otherwise would be a huge result. Writing a paper confirming Kreinovich and Shpak in a slightly different domain is basically a "Water is Wet" paper.
Having not yet read the paper, I'm unaware of any new ground here.
Disclaimer: I'm really noob, not asking it sarcastically.
It's just impossible to write a general-purpose algorithm to solve it in all cases.
The Continuum Hypothesis [0] (which the authors are saying the learning problem is isomorphic [1] to) is not provable from the axioms of set theory. You can add "The Continuum Hypothesis is true" OR "The Continuum Hypothesis is false" to the axioms, and still have consistent mathematics.
[0] Continuum hypothesis is that the set of Integers (0, -1, 1, -2, 2, ...) is infinite but smaller than the set of Reals (Integers + Rationals + Irrationals), and there are no infinite sets with size smaller than the Reals, but larger than the Integers.
[1] not sure of correct term here - the point is that they have shown the problems are the same.
There are NP-hard problems that are undecidable, that means, there is no algorithm that can decide the question for every input. However, in some instances we are able to solve these problems (even quite easy). For example we know that an algorithm like "while TRUE DO (nothing) END" will never terminate, even though the halting problem is undecidable.
However, if a NP-hard problem is also in NP, than it can be solvend. But it will take exponential time in the worst case. That, too, does not mean that in some instance we are able to solve them in reasonable time.
Undecidable problems e.g. the Halting problem cannot generally be solved using an algorithm (so it has to be solved on a case-by-case basis and requires "creativity").
I think you might confuse NP-hard with NP-complete. There are problems that are NP-hard, not in NP and unsolvable. If a problem is NP-hard _and_ in NP, then they can always be solved.
or, given enough effort / luck / redefining the problem, sometimes extra structure can be found for the particular problem instances that you want to solve, meaning that they actually belong to an easier problem class that can be solved in practise -- e.g. you've got extra information or constraints that you're not actually using, so you don't need to solve the NP-hard problem in general, just solve the specific problem you've got.
i'll willing to change my position if someone can argue it is similar for undecidable problems.
I guess the parent meant something like this.
Of course the concepts are totally dissimilar but the practical consequences are less apart.
Complexity results are always worst-case results. In practice you can often solve all instances you actually care about.
They’re discussing “learnability” as related to VC dimensionality and compressibility.
It’s absolutely related to aggregability.
An undecideable solution cannot be proven true.
So, unless there is an infinity encoded in the exact problem somehow, you can always solve it by simple brute force enumeration.
Look at the busy beaver, it's completely possible theoretically to simply enumerate all the possible states of a tape for a given N, and play the corresponding Turing machines. Even if calculating this is physically impossible, and proven to be impossible to generalize for any N. (That is the BB functions are uncomputable, but of course not exact values.)
There's nothing to calculate there. It's a proof by construction for Godel's incompleteness theorem.
This stuff is all in the same ballpark.
Having read their paper, I do appreciate the formulation and approach. I just don’t find the result “surprising” in the slightest.
One of the first things you see in a graduate course on real analysis that covers measure theory is the construction of an unmeasurable set using the axiom of choice (equivalent to the continuum hypothesis). Then you say, "that's useless," and restrict the subsets you work with to those that don't depend on this problem, or you go work with intuitionist, finitist, ultrafinitist, or some other logic, which gives basically the same effect. Then you build all of probability theory and machine learning in this actually useful world.
The unmeasurable set construction that everyone uses is to consider all subsets of [0,1] of the form {x + r : x in [0,1], r is rational}. Since there are uncountably many irrational numbers, you end up with an uncountable number of these subsets, and then use the axiom of choice to select an element of each.
For their probability distributions with finite support, consider the sets of points that form the support of the distributions. I can form a sequence of such sets that heads towards that unmeasurable set, and a corresponding sequence of probability distributions. They completely ignore whether their set of distributions is complete (that is, contains all limits of sequences—hint, it isn't), but they're taking suprema, so they effectively are working in the closure anyway, where the limits are included.
So basically they have found an obscure way of showing the first result taught in measure theory and dressed it up in the clothes of machine learning, even though no machine learning work ever conducted or that will ever be conducted with work on this mathematical structure because of this exact reason.
The actual research, which I find more understandable than the news coverage: https://www.nature.com/articles/s42256-018-0002-3
By the way, Paul Cohen, who proved the independence of the Continuum Hypothesis, says that Godel did not express much interest in independence results (I think Godel believed in Platonism):
https://www.youtube.com/watch?v=VBFLWk7k1Zo
An article by Godel, taking a philosophical viewpoint about set theory and independence, is "The modern development of the foundations of mathematics in the light of philosophy":
http://www.marxists.org/reference/subject/philosophy/works/a...
Godel believed that for well-defined areas of mathematics, we can add more _intuitive_ axioms to make the theory decidable: The appropriate quote from the article: "I would like to point out that this intuitive grasping of ever newer axioms that are logically independent from the earlier ones, which is necessary for the solvability of all problems even within a very limited domain, agrees in principle with the Kantian conception of mathematics. "
Gödel proved the other direction of the independence of CH (and the Axiom of Choice), and had been trying to prove independence some years after that. He had actually succeeded in proving the independence of AC by 1943, and later said in an interview with Hao Wang that his methods could have probably been extended to prove the independence of CH by 1950, but he stopped working on it because he developed a distaste for the subject. In retrospect, Gödel wished that he had continued his work so that set theory progressed faster.
The article The Origins of Forcing by G. H. Moore in the proceedings of the 1986 Logic Colloquium is a good discussion of the relevant history.
> Godel believed that for well-defined areas of mathematics, we can add more _intuitive_ axioms to make the theory decidable: The appropriate quote from the article: "I would like to point out that this intuitive grasping of ever newer axioms that are logically independent from the earlier ones, which is necessary for the solvability of all problems even within a very limited domain, agrees in principle with the Kantian conception of mathematics. "
This line of research hasn't gone very well in practice since Gödel's time. It has produced a lot of interesting set theory, but has not really impacted mathematics at large.
> This line of research hasn't gone very well in practice since Gödel's time. It has produced a lot of interesting set theory, but has not really impacted mathematics at large.
What about Hugh Woodin's work? I agree that it has not had impact yet, but do you think it might lead along this suggested line?
Reading this got me wondering about more philosophical aspects, such as the relation of this conclusion to to the process of human learning and prediction (which obviously works) and whether it's somehow tied in some way to the problem of induction. Could be nonsense, but I'll be putting some more thought into the meaning of this
Sure, you can the start to ask what are the good upper bounds. How many epochs to use for training, start to quantify the training set quality, and then ask how good that must be to get a good enough model. Etc. But all of these then can be limited by estimation.
People learn, but sometimes learn with mistakes. For example:
* Is this mushroom edible?
It's much easier to make a good enough classifier than a perfect classifier, if you allow a broad definition of good enough.
"A team of researchers has stumbled on a question that is mathematically unanswerable. It is linked to logical paradoxes, that were discovered by Austrian mathematician Kurt Gödel in the 1930s and it can’t be solved using standard mathematics."
So, while I think your question is interesting and good, I don’t think integer size is a strong counterexample in support of a different conclusion.
It's an absurd thing for GP to say integers aren't infinite (apparently talking about fixed width integer types) and then turn around and say float/double are infinite (talking about single precision and double precision floating point types).
the paper seems to talk about binary classifiers `h : X --> {0, 1}`, where each classifier h belongs to some family `F` of functions subseteq `{h : X --> {0, 1}}`, and where observed samples are drawn from some unknown distribution P over X.
so, it probably depends upon the choice of `X` and `F`, but i dont have enough of a handle on the theory to understand this.
I.e. in many materials or chemistry fields where you start operating with over 100 variables, you begin to develop a dark arts of understanding because what is being attempted is beyond the ability of computers to model.
You can do chemistry without a PhD, but your ability to systematically try to address the complexity may be hindered without the training. Likewise with ‘ML experts’ (I hope they get a cool word some day to describe their profession).
If we have a function f(x1, x2, ...) of 100 variables and you wonder about the gradient, theres multiple ways of calculating it.
Theres symbolic differentiation, but due to the chain rule, the number of terms grows rapidly and the expression can not be stored.
Then theres the finite difference method, whereby you calculate for each of 100 variables x_i:
f(x1, x2, ..., (x_i +epsilon), ..., x100) - f(x1, ..., x100)
the term on the right is the same constant so in total you need 100+1 forward function evaluations. And theres the issue of precision for small differences (mantissa).
One of the main reasons machine learning took off is because of the mathematical realization (Automatic/Algorithmic Differentiation) on how a 1 forward and 1 backward pass is more mathematically rigorous (calculates gradient vs finite differences) and much more efficient.
With the blackboxing of the algorithms, many endusers of the ML libraries end up using ML when they don't know the functional form of a map, but will refuse to apply automatic differentiation of a known complex function with large number of parameters. In contrast those endusers that made sure to understand Automatic Differentiation as a tool orthogonal to arbitrary function approximation (i.e. everyone who realizes the math part of ML is very important) will be able to apply AD (or any other tricks learnt through a mathematical perspective) in situatins where there is no need for arbitrary function approximation...
EDIT: woops I thought you were arguing for blackboxing, against mathematical interpretation upvoted
After all if intelligence comes out artificially, I hope it does not have rule.
https://en.m.wikipedia.org/wiki/Vapnik–Chervonenkis_dimensio...
Also, the reason why black box methods are such a big deal now is precisely because controlled/engineered methods turned out to be inferior (obvious example: image recognition; look no further than into the story of the dropout method and Alex Krizhevsky).
Edit: s/basically forgotten/often forgotten/ in the first sentence.
[0] http://www.math.ucla.edu/~chernikov/teaching/Combinatorics28...
For example, Goodfellow and Bengio's book on Deep Learning talks a lot about connections to Bayesian Inference, Classical Statistics, Information Theory, and a bit about Topology.
Christopher Oolah's blog gives plenty of great explanations of mathematical topics.
Personally, I use Math in my work all the time. Thinking in terms of Information Theory has let me quantify and compare algorithms that seemed difficult to evaluate at first. And several times, I've seen a business make the wrong decision due to lack of Math/Stats background.
I don't mean to be a Math snob – you can absolutely do a lot of valuable work treating algorithms as black boxes. But the Math is there, and it is being used.