Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Machine learning leads mathematicians to unsolvable problem

nature.com

Post reply on HN
Print view View original

61–70 of 98 posts

Re: Machine learning leads mathematicians to unsolvable problem

#61

Post by adrianN »

miclill wrote: post #56
Cacti wrote: post #47

Earlier quoted context omitted.

NP-hard and undecidability are completely different things. They’re barely on the same planet.

I would argue that for practitioners it is the same planet. But I agree that they are not the same thing.

That strongly depends on the practitioner and the problem. We solve (or approximate) NP hard problems all the time. SAT solvers are really good, so are ILP solvers and a host of other tools that solve a ton of instances of NP-complete problems that arise in practice. If you're into software verification, people solve undecidable problems there every day.

Complexity results are always worst-case results. In practice you can often solve all instances you actually care about.

Re: Machine learning leads mathematicians to unsolvable problem

#62

Post by adrianN »

diegoperini wrote: post #50
foxrob92 wrote: post #40

Earlier quoted context omitted.

I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?

How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.

There are an infinite number of complexity classes that are (probably) harder than NP. Popular ones include PSPACE and EXPTIME. You might want to google for "polynomial hierachy".

Re: Machine learning leads mathematicians to unsolvable problem

#63

Post by foxrob92 »

diegoperini wrote: post #50
foxrob92 wrote: post #40

Earlier quoted context omitted.

I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?

How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.

NP-hard problems can be solved.

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.

Re: Machine learning leads mathematicians to unsolvable problem

#64

Post by dabs »

Question for someone with a more theoretical background: The paper shows that the EMX learnability of some class of functions with respect to some set of probability distributions is undecidable. Does EMX learnability encompass all notions of learnability (or is it equivalent to other notions)? Conversely are there or could there be notions of learnability different from EMX that are not undecidable? Maybe I missed this in the paper but clarification would be appreciated.

Re: Machine learning leads mathematicians to unsolvable problem

#65

Post by threatofrain »

foxrob92 wrote: post #40
chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. 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…

I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?

Aren't some undecidable problems "better" with regards to practical needs because we can achieve arbitrarily precise results more cheaply?

Re: Machine learning leads mathematicians to unsolvable problem

#66

Post by zodiac »

chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. 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…

If you didn't read the paper, at least read the title: "unsolvable" does not mean NP hard

Re: Machine learning leads mathematicians to unsolvable problem

#68

Post by threatofrain »

raverbashing wrote: post #55
chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. 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…

An NP-hard problem is still possible to be solved. Impractical but possible. An undecideable solution cannot be proven true.

A non-computable problem might still be practically "better" because its solution might be approximated precisely and more cheaply, such as the approximation of a real number.

Re: Machine learning leads mathematicians to unsolvable problem

#69

Post by niklasd »

foxrob92 wrote: post #63
diegoperini wrote: post #50

Earlier quoted context omitted.

How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.

NP-hard problems can be solved. 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…

I'm not sure what you mean with "can be solved", but I would spell it out a bit different:

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.

Re: Machine learning leads mathematicians to unsolvable problem

#70

Post by placebo »

"In the latest paper, Yehudayoff and his collaborators define learnability as the ability to make predictions about a large data set by sampling a small number of data points. The link with Cantor’s problem is that there are infinitely many ways of choosing the smaller set, but the size of that infinity is unknown."

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

Post reply on HN