Machine learning leads mathematicians to unsolvable problem • Hacker News Board

Re: Machine learning leads mathematicians to unsolvable problem

#91

Post by fspeech » Sun, Feb 03, 2019, 5:05 PM UTC

betterunix2 wrote: post #82

fspeech wrote: post #54

Earlier quoted context omitted.

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.

This is the first paragraph from the Wikipedia article on undecidable problems: “In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.” https://en.m.wikipedia.org/wiki/Undecidable_problem

Re: Machine learning leads mathematicians to unsolvable problem

#92

Post by fspeech » Sun, Feb 03, 2019, 5:23 PM UTC

vinceguidry wrote: post #58

fspeech wrote: post #54

Earlier quoted context omitted.

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

There's got to be more to it than that. The halting problem itself isn't some on-off switch, it can be studied and broken down into different problem classes, some of which are indeed decidable. It's just impossible to write a general-purpose algorithm to solve it in all cases.

“It's just impossible to write a general-purpose algorithm to solve it in all cases.” That is the definition of an undecidable problem. Independence, as in Euclid’s fifth postulate, is not what we typically think of as undecidability, though can be referred to as such.

Re: Machine learning leads mathematicians to unsolvable problem

#93

Post by madhadron » Sun, Feb 03, 2019, 5:32 PM UTC

The theorem is proved for only for probability distributions with support at a finite number of points on [0,1], and the sigma-algebra of all subsets of [0,1]. This is an utterly bizarre choice and makes the whole thing basically uninteresting.

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.

Re: Machine learning leads mathematicians to unsolvable problem

#94

Post by DoctorOetker » Sun, Feb 03, 2019, 6:06 PM UTC

mensetmanusman wrote: post #15

byebyetech wrote: post #4

Earlier quoted context omitted.

So what is the meaning of "ML experts" if all they do is trial and loss experiments! Is Math PhD just used for hiring signal rather than actual requirements to do ML projects?

It’s an exciting time because the field is getting to the point where ‘complexity is unbounded’ 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 ma…

the example you gave is unfortunately a counterexample!

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

Re: Machine learning leads mathematicians to unsolvable problem

#95

Post by dltnhic » Sun, Feb 03, 2019, 6:56 PM UTC

madhadron wrote: post #93

The theorem is proved for only for probability distributions with support at a finite number of points on [0,1], and the sigma-algebra of all subsets of [0,1]. This is an utterly bizarre choice and makes the whole thing basically uninteresting. 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 (equivale…

This is not adding to the conversation. Your comment was my impediment in moving past the second page of the paper. Problem is, I never got to study foundations of measure theory, and presumed I could be wrong. Do you have any self-study recommendations, paper or concise books?

Re: Machine learning leads mathematicians to unsolvable problem

#96

Post by msfalcon » Sun, Feb 03, 2019, 7:00 PM UTC

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.

The proceedings are freely available online and most sessions are freely casted. Attending the conference in person has surely some cost!

Re: Machine learning leads mathematicians to unsolvable problem

#97

Post by madhadron » Sun, Feb 03, 2019, 8:27 PM UTC

dltnhic wrote: post #95

madhadron wrote: post #93

The theorem is proved for only for probability distributions with support at a finite number of points on [0,1], and the sigma-algebra of all subsets of [0,1]. This is an utterly bizarre choice and makes the whole thing basically uninteresting. 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 (equivale…

This is not adding to the conversation. Your comment was my impediment in moving past the second page of the paper. Problem is, I never got to study foundations of measure theory, and presumed I could be wrong. Do you have any self-study recommendations, paper or concise books?

I really don't have a good recommendation. :( I learned it from a person, not a book, and the textbook he was assigning exercises from (Folland) is essentially useless for self study to my mind.

Re: Machine learning leads mathematicians to unsolvable problem

#98

Post by niklasd » Sun, Feb 03, 2019, 9:05 PM UTC

betterunix2 wrote: post #81

niklasd wrote: post #69

Earlier quoted context omitted.

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

Sorry, but you are flat out wrong. For example, the halting problem is NP-hard and undecidable [1]

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.

[1] https://en.wikipedia.org/wiki/NP-hardness