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

71–80 of 98 posts

Re: Machine learning leads mathematicians to unsolvable problem

#71

Post by mmmmpancakes »

freeone3000 wrote: post #27
fucking_tragedy wrote: post #18

Earlier quoted context omitted.

As someone who isn't in the know, I found this[1] Forbes article about the journal. Forbes portrays the opposition as opposing the fact that it's a closed access journal, but are there other points of contention that weren't reported in the article? [1] https://www.forbes.com/sites/samshead/2018/04/30/tech-giant-...

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.

Re: Machine learning leads mathematicians to unsolvable problem

#72

Post by pas »

pfortuny wrote: post #60
raverbashing wrote: post #55

Earlier quoted context omitted.

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

Yes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general statement about “equations”).

Are there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken.

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

Re: Machine learning leads mathematicians to unsolvable problem

#73

Post by pas »

placebo wrote: post #70

"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 conclusio…

The problem with these papers is, that if you want to do practical ML, you can simply fix some upper bounds on various numbers that arise during the analysis of the problem, and thus make it mathematically finite, and trivial. Not easy, of course, but this frees you from the infinite regress that's the problem of induction.

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.

Re: Machine learning leads mathematicians to unsolvable problem

#74

Post by pfortuny »

pas wrote: post #72
pfortuny wrote: post #60

Earlier quoted context omitted.

Yes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general statement about “equations”).

Are there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken. 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 i…

Gödel’s sentence comes to mind. Yes, it is not “practical” but it is undecidable.

Re: Machine learning leads mathematicians to unsolvable problem

#75

Post by pas »

pfortuny wrote: post #74
pas wrote: post #72

Earlier quoted context omitted.

Are there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken. 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 i…

Gödel’s sentence comes to mind. Yes, it is not “practical” but it is undecidable.

Godel's sentence is not an exact problem. It's a big number representing a claim (a theorem) about Godel numbers and the sentence itself.

There's nothing to calculate there. It's a proof by construction for Godel's incompleteness theorem.

Re: Machine learning leads mathematicians to unsolvable problem

#76

Post by svat »

hannob wrote: post #42
eanzenberg wrote: post #38

Earlier quoted context omitted.

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

There's a strange thing, there seems to be a universal rule of Open Access discussions: There will always be someone who defends publishers based on not knowing anything about how scientific publishing works.

My favourite article about open access, about the Journal of Machine Learning Research, and really the ultimate smackdown, all done very politely: https://blogs.harvard.edu/pamphlet/2012/03/06/an-efficient-j...

Re: Machine learning leads mathematicians to unsolvable problem

#77

Post by hatsuseno »

galaxyLogic wrote: post #45

If I understood the article correctly (and I think I didn't) it says learnability of a given data-set is like the halting problem, there is no general algorithm for deciding whether an arbitrary data-set is learnable. Am I close?

This was my takeaway from the article as well. Even though I have no academic knowledge on the subject, can't say I was surprised to learn this. To me it seems obvious in hindsight, though might be Dunning-Kruger.

Re: Machine learning leads mathematicians to unsolvable problem

#78

Post by gus_massa »

placebo wrote: post #70

"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 conclusio…

Don't read too in this result. This is about perfect classifiers, if it is enough to train a perfect classifier using only a finite amount of samples of the set.

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.

Re: Machine learning leads mathematicians to unsolvable problem

#79

Post by mikro2nd »

curiousStarDust wrote: post #46

Not completely on the subject, but I had to read the first sentence 5 times, before I was able to understand its meaning. Then I realized it was too long, so modified it to following version. Is it better or worse? "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…

To further improve your last sentence, drop the comma after "paradoxes" and add one after "1930s".

Re: Machine learning leads mathematicians to unsolvable problem

#80

Post by plaidfuji »

p1esk wrote: post #17

This work was published in “Nature Machine Intelligence“, the journal boycotted by pretty much everyone who matters in ML. Reflects poorly on the authors, regardless of the actual merits of their finding.

Which would also explain why Nature wrote this publicity piece on it. I can only hope that ML researchers show the rest of academia the way out of publishers' hands.
Post reply on HN