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

81–90 of 98 posts

Re: Machine learning leads mathematicians to unsolvable problem

#81

Post by betterunix2 »

niklasd wrote: post #69
foxrob92 wrote: post #63

Earlier quoted context omitted.

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…

This is wrong. NP-hard problems can be solved, they just appear to hard to solve efficiently. NP-hard problems are always decidable, like everything in polynomial hierarchy (P, NP, co-NP, and higher classes that have oracle access to lower classes).

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").

Re: Machine learning leads mathematicians to unsolvable problem

#82

Post by betterunix2 »

fspeech wrote: post #54
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.

Undecidable means there is no logical way to have an answer. Turing’s halting problem is one such.

That is incorrect. The halting problem can be answered -- every Turing Machine either halts or does not halt on a given input. Undecidable only means that we cannot have a single algorithm that outputs the correct answer in every case.

Re: Machine learning leads mathematicians to unsolvable problem

#83

Post by betterunix2 »

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.

PSPACE-complete is an example. EXPSPACE is another.

Re: Machine learning leads mathematicians to unsolvable problem

#84

Post by gus_massa »

mmmmpancakes wrote: post #71
freeone3000 wrote: post #27

Earlier quoted context omitted.

That's enough. ML research is posted on arxiv and presented in open conferences. You can paywall your slide deck but not your paper. If pay-to-play journals get even an inch, they'll try to take everything.

What does “open conferences” mean? 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.

Also, if you live outside USA/Europe, let's go to a important conference may be a few thousand of dollars more expensive that sending an email to the editor with the draft of the paper.

[Hi from Argentina!]

Re: Machine learning leads mathematicians to unsolvable problem

#86

Post by [deleted] »

calf wrote: post #35
joe_the_user wrote: post #19

Earlier quoted context omitted.

As far as I can tell, the article isn't really of any interest either. 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 don't understand your reasoning. Because, you could also "formulate" CH in the "language" of Turing machines. But that is clearly disanalogous to what the article is saying.

[deleted]

Re: Machine learning leads mathematicians to unsolvable problem

#87

Post by lenticular »

eanzenberg wrote: post #38
CuriousCosmic wrote: post #31

Earlier quoted context omitted.

and fees for publishing. 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.

Because being a peer reviewer shouldn’t be done for free? Do you like being paid to work? Because Nature has established themselves as a premier journal over the the past 150 years and are known for their quality? Or maybe I’m just taking crazy pills..

Haha, reviewers getting paid. That's a good one. This journal charges the authors for Pete's sake.

Re: Machine learning leads mathematicians to unsolvable problem

#88

Post by sobellian »

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…

Actually, some undecidable problems are NP hard, like the halting problem. That is, a halting oracle gives a polynomial time algorithm for any NP problem.

Re: Machine learning leads mathematicians to unsolvable problem

#89

Post by chaboud »

Cacti wrote: post #47
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…

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

Read the paper. I have (now).

They’re discussing “learnability” as related to VC dimensionality and compressibility.

It’s absolutely related to aggregability.

Re: Machine learning leads mathematicians to unsolvable problem

#90

Post by chaboud »

zodiac wrote: post #66
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

I did read the paper (now). Their question is of “learnability”, which relates to aggregability/compressibility and dimensionality.

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.

Post reply on HN