9 ms·

Machine learning leads mathematicians to unsolvable problem

197 points by magoghm 8y ago

min2bro 8y ago
Where is mathematics in ML today? Most of that are happening under the hood and all algorithms are just a black box.
- verroq 8y ago
  The ML field today is all about results. Get the high scores and figure out the math later. Not that there is anything wrong with this, we still at the stage where we're banging rocks together wondering what works and what doesn't, and the theories will come later.
  - byebyetech 8y ago
    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?
    - Eridrus 8y ago
      Yes, there is no need to have a PhD to do ML, either applied or research. Not to say there isn't good research using advanced mathematical/statistical methods, but most of it is not. It's entirely a signaling game.
    - mensetmanusman 8y ago
      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 may be hindered without the training. Likewise with ‘ML experts’ (I hope they get a cool word some day to describe their profession).
      - DoctorOetker 8y ago
        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
    - ngcc_hk 8y ago
      May be Ml is an empirical subject more than a theoretical subject. It is more biology than physics. More astronomy ... even is the subject is created does not meant it follows rules. After all if intelligence comes out artificially, I hope it does not have rule.
      - galaxyLogic 8y ago
        Great point ML takes much of its inspiration from simulating brains. Therefore studying such artificial brains is much like studying biology and thus to a large degree empirical I would assume.
- YjSe2GMQ 8y ago
  There's a very neat and often forgotten piece of math in learning, VC dimension (unrelated to venture capital): https://en.m.wikipedia.org/wiki/Vapnik–Chervonenkis_dimension 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.
  - selimthegrim 8y ago
    It's not very forgotten if it's in the Learning from Data course, to say the least
  - ginnungagap 8y ago
    There are some good combinatorics notes by Chernikov[0, pdf file] talking about VC theory if anyone is interested in learning more [0] http://www.math.ucla.edu/~chernikov/teaching/Combinatorics285N/CombinatoricsNotes.pdf http://www.math.ucla.edu/~chernikov/teaching/Combinatorics28...
- SatvikBeri 8y ago
  It's all around. The math portion just doesn't get as much hype. 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.
thyrsus 8y ago
I don't understand how a result concerning infinities can apply to a finite number of data points represented by finite (bounded - probably by 2^32) integers processed in finite time.
- perfmode 8y ago
  The reals are infinite. Float/double 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.
  - ptd 8y ago
    Can you elaborate on this? Specifically, why isn’t integer size a good counterexample?
  - gubbrora 8y ago
    Float/doubles are finite. They only approximately model the real. And that's key. Because the fact that approximation works for a problem means it must be reasonably smooth, which means everything will be more well behaved and rules out the worst pathologies.
  - repiret 8y ago
    float/double can store a subset of the rationals plus some other values which aren’t found in the reals
    - lern_too_spel 8y ago
      And those other values are finite (NaNs, infinities, unequal zeros). I don't know why you're downvoted. What you said is absolutely correct. 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).
- shoo 8y ago
  i think you're alluding to an interesting question: in what cases does this "undecidability of learnability" result apply? 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.
JayRoni 8y ago
Professor Peter O'Hearn (UCL Computer Science) says latest research findings on 'unsolvable' mathematical problems is “of a rare kind”, and will probably be important for the theory of machine learning.
- deleted 8y ago
  [deleted]
p1esk 8y ago
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.
- fucking_tragedy 8y ago
  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-ai-researchers-boycott-nature-machine-intelligence-journal/#2da5033e5e01 https://www.forbes.com/sites/samshead/2018/04/30/tech-giant-...
  - freeone3000 8y ago
    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.
    - mmmmpancakes 8y ago
      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.
      - gus_massa 8y ago
        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!]
      - msfalcon 8y ago
        The proceedings are freely available online and most sessions are freely casted. Attending the conference in person has surely some cost!
sn41 8y ago
Isn't all this press by the Nature publishing group just about hyping up one of its newer magazines that the larger research community is boycotting? 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 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/at/godel.htm 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. "
- deleted 8y ago
  [deleted]
- cwzwarich 8y ago
  > 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): 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.
fooker 8y ago
Can someone explain why/if this is a big deal? It seems to me that they just rehashed undecidability and logical incompleteness.
chaboud 8y ago
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://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.78.6237%26rep%3Drep1%26type%3Dpdf&ved=2ahUKEwjg3oON9p7gAhXiHDQIHctEBfEQFjAAegQIAxAB&usg=AOvVaw3KFPsAt9iWqBpUqZrEigpu&cshid=1549174909564 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.
- foxrob92 8y ago
  I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?
  - diegoperini 8y ago
    How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.
    - fspeech 8y ago
      Undecidable means there is no logical way to have an answer. Turing’s halting problem is one such.
      - vinceguidry 8y ago
        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.
galaxyLogic 8y ago
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?
- hatsuseno 8y ago
  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.
curiousStarDust 8y ago
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 be solved using standard mathematics."
- elliotec 8y ago
  Yeah, it’s a bit better. Not sure how much, maybe more for non native speakers?
  - curiousStarDust 8y ago
    Thanks! English is my 3rd language, so I do struggle with reading sometimes.
- mikro2nd 8y ago
  To further improve your last sentence, drop the comma after "paradoxes" and add one after "1930s".
dabs 8y ago
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.
sampo 8y ago
Earlier discussion: https://news.ycombinator.com/item?id=18858724 https://news.ycombinator.com/item?id=18858724 (Same research, but different news coverage) The actual research, which I find more understandable than the news coverage: https://www.nature.com/articles/s42256-018-0002-3 https://www.nature.com/articles/s42256-018-0002-3
placebo 8y ago
"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
- pas 8y ago
  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.
- gus_massa 8y ago
  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.
rahuldottech 8y ago
I mean, c'mon we all saw this coming...
madhadron 8y ago
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.
- dltnhic 8y ago
  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?
  - madhadron 8y ago
    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.

197 points by magoghm 8y ago

min2bro 8y ago

Where is mathematics in ML today? Most of that are happening under the hood and all algorithms are just a black box.

verroq 8y ago
The ML field today is all about results. Get the high scores and figure out the math later. Not that there is anything wrong with this, we still at the stage where we're banging rocks together wondering what works and what doesn't, and the theories will come later.
- byebyetech 8y ago
  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?
  - Eridrus 8y ago
    Yes, there is no need to have a PhD to do ML, either applied or research. Not to say there isn't good research using advanced mathematical/statistical methods, but most of it is not. It's entirely a signaling game.
  - mensetmanusman 8y ago
    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 may be hindered without the training. Likewise with ‘ML experts’ (I hope they get a cool word some day to describe their profession).
    - DoctorOetker 8y ago
      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
  - ngcc_hk 8y ago
    May be Ml is an empirical subject more than a theoretical subject. It is more biology than physics. More astronomy ... even is the subject is created does not meant it follows rules. After all if intelligence comes out artificially, I hope it does not have rule.
    - galaxyLogic 8y ago
      Great point ML takes much of its inspiration from simulating brains. Therefore studying such artificial brains is much like studying biology and thus to a large degree empirical I would assume.
YjSe2GMQ 8y ago
There's a very neat and often forgotten piece of math in learning, VC dimension (unrelated to venture capital): https://en.m.wikipedia.org/wiki/Vapnik–Chervonenkis_dimension 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.
- selimthegrim 8y ago
  It's not very forgotten if it's in the Learning from Data course, to say the least
- ginnungagap 8y ago
  There are some good combinatorics notes by Chernikov[0, pdf file] talking about VC theory if anyone is interested in learning more [0] http://www.math.ucla.edu/~chernikov/teaching/Combinatorics285N/CombinatoricsNotes.pdf http://www.math.ucla.edu/~chernikov/teaching/Combinatorics28...
SatvikBeri 8y ago
It's all around. The math portion just doesn't get as much hype. 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.

thyrsus 8y ago

I don't understand how a result concerning infinities can apply to a finite number of data points represented by finite (bounded - probably by 2^32) integers processed in finite time.

perfmode 8y ago
The reals are infinite. Float/double 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.
- ptd 8y ago
  Can you elaborate on this? Specifically, why isn’t integer size a good counterexample?
- gubbrora 8y ago
  Float/doubles are finite. They only approximately model the real. And that's key. Because the fact that approximation works for a problem means it must be reasonably smooth, which means everything will be more well behaved and rules out the worst pathologies.
- repiret 8y ago
  float/double can store a subset of the rationals plus some other values which aren’t found in the reals
  - lern_too_spel 8y ago
    And those other values are finite (NaNs, infinities, unequal zeros). I don't know why you're downvoted. What you said is absolutely correct. 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).
shoo 8y ago
i think you're alluding to an interesting question: in what cases does this "undecidability of learnability" result apply? 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.

JayRoni 8y ago

Professor Peter O'Hearn (UCL Computer Science) says latest research findings on 'unsolvable' mathematical problems is “of a rare kind”, and will probably be important for the theory of machine learning.

deleted 8y ago
[deleted]

p1esk 8y ago

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.

fucking_tragedy 8y ago
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-ai-researchers-boycott-nature-machine-intelligence-journal/#2da5033e5e01 https://www.forbes.com/sites/samshead/2018/04/30/tech-giant-...
- freeone3000 8y ago
  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.
  - mmmmpancakes 8y ago
    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.
    - gus_massa 8y ago
      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!]
    - msfalcon 8y ago
      The proceedings are freely available online and most sessions are freely casted. Attending the conference in person has surely some cost!

sn41 8y ago

Isn't all this press by the Nature publishing group just about hyping up one of its newer magazines that the larger research community is boycotting? 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 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/at/godel.htm 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. "

deleted 8y ago
[deleted]
cwzwarich 8y ago
> 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): 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.

fooker 8y ago

Can someone explain why/if this is a big deal? It seems to me that they just rehashed undecidability and logical incompleteness.

chaboud 8y ago

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://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.78.6237%26rep%3Drep1%26type%3Dpdf&ved=2ahUKEwjg3oON9p7gAhXiHDQIHctEBfEQFjAAegQIAxAB&usg=AOvVaw3KFPsAt9iWqBpUqZrEigpu&cshid=1549174909564 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.

foxrob92 8y ago
I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?
- diegoperini 8y ago
  How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.
  - fspeech 8y ago
    Undecidable means there is no logical way to have an answer. Turing’s halting problem is one such.
    - vinceguidry 8y ago
      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.

galaxyLogic 8y ago

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?

hatsuseno 8y ago
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.

curiousStarDust 8y ago

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 be solved using standard mathematics."

elliotec 8y ago
Yeah, it’s a bit better. Not sure how much, maybe more for non native speakers?
- curiousStarDust 8y ago
  Thanks! English is my 3rd language, so I do struggle with reading sometimes.
mikro2nd 8y ago
To further improve your last sentence, drop the comma after "paradoxes" and add one after "1930s".

dabs 8y ago

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.

sampo 8y ago

Earlier discussion: https://news.ycombinator.com/item?id=18858724 https://news.ycombinator.com/item?id=18858724 (Same research, but different news coverage) The actual research, which I find more understandable than the news coverage: https://www.nature.com/articles/s42256-018-0002-3 https://www.nature.com/articles/s42256-018-0002-3

placebo 8y ago

"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

pas 8y ago
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.
gus_massa 8y ago
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.

rahuldottech 8y ago

I mean, c'mon we all saw this coming...

madhadron 8y ago

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.

dltnhic 8y ago
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?
- madhadron 8y ago
  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.