13 ms·

Unprovability comes to machine learning

218 points by joker3 8y ago

yters 8y ago
How would this affect the practical nature of the problem? Also, why is this novel? All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem.
- amelius 8y ago
  > All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. I think the argument should be the other way around.
  - deleted 8y ago
    [deleted]
  - deleted 8y ago
    [deleted]
- fredgrott 8y ago
  its the old Godel trick of translating it into a different form..ie what Godel originally did to prove his own theorem was to translate his theorem into symbolics and than negate it,.. In their example they are expressing it in set theory and than operating on it... I probably failed at explaining on a simple level...sorry
  - rs86 8y ago
    Theorems are strings of symbols and can thus be encoded as numbers, and statements about numbers become statements about theorems. That's why the theorem applies to systems at least as strong as arithmetics
- umanwizard 8y ago
  What do you mean by "subject to the halting problem"? There are plenty of Turing machines that can be proven to halt. The halting problem doesn't say "given any Turing machine, no algorithm can determine whether it halts". It says "no algorithm can determine whether any given Turing machine halts".
- yes_man 8y ago
  > All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. Assumption that all learning algorithms can be implemented on a Turing machine cannot hold true, since there are mathematical problems that cannot (take for example https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem). Unless you categorise machine learning problems as problems that can be implemented with a Turing machine, making the statement a tautology. Edit: thinking about my comment maybe I am the one being tautologic. If there is a learning algorithm that can solve Hilbert's problem it would transcend mathematics
  - umanwizard 8y ago
    "X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". Turing machines are just a formalization of the concept of algorithms/computer programs. So problems that can't be implemented as a Turing machine are not "learning algorithms", or any kind of algorithm.
    - deleted 8y ago
      [deleted]
    - __MatrixMan__ 8y ago
      I think that simplifies things a bit too far. A Turing Machine represents the most complete computational toolkit we happen to know of--not the most complete computational toolkit possible. If we discovered a new computational trick tomorrow--one that a Turing Machine can't perform (the ability to solve the halting problem for Turing Machines, for instance), then we would have discovered another--higher--class of computers, and it would be a reasonable linguistic move to refer to their programs as "algorithms" as well.
      - umanwizard 8y ago
        It is probably not possible to discover a new computational trick, by the Church-Turing thesis. The Church-Turing thesis can't be proven, since it is a statement about what is possible in the physical universe, not a statement about mathematics. But the intuitive arguments in favor of it (i.e., that Turing machines capture exactly what we mean by "computation") are, for me, extremely convincing.
- rs86 8y ago
  This is about the possibility of proving certain things about the model, not about properties of any implementation. Properties include for example the relation between the amount and quality of data available for training and the accuracy of the model. If a model is proven to learn too slowly it costs more to train it. And some models might never approximate a target function.
- bnjmn 8y ago
  I suspect the Halting Problem was already an obvious theoretical limitation to machine learning. Just imagine a network trained to classify programs according to whether or not they halt. Then construct a program that runs forever if the network says the program halts, and halts if the network says the program does not halt. No training strategy would ever produce a network that always gives the correct answer in this case. In the Generative Adversarial Network (GAN) framework, this would be the One Weird Trick the generator could pull that would always foil the discriminator. This paper is interesting because it connects learnability to a different kind of undecidability than the Halting Problem: the Continuum Hypothesis. In some ways it's more troubling than the Halting Problem, because at least we can usually figure out whether some actual program halts, using some cleverness, but no one can begin to say whether the Continuum Hypothesis is true or false. The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). That's good news, because it implies the EMX learning model will work: > Their results imply that the finite subsets of the unit interval have monotone-compression schemes, and therefore are learnable in EMX, if and only if the continuum hypothesis is true, which is known to be unprovable. If someone comes along and casts doubt on the Continuum Hypothesis through some mystical but persuasive line of reasoning (news flash: not gonna happen), then there might be some EMX functions that can't be learned, but no one is going to lose sleep over that. There are lots of more immediate reasons why machine learning fails in practice, like not having good training data.
  - baddox 8y ago
    I'm confused. I'm pretty sure that the issue isn't "no one can begin to say whether the Continuum Hypothesis is true or false," but rather that we know it to be independent of the widely-used axiomatic set theories (at least ZFC). Since "truth" is defined in terms of the chosen axioms, and we have proven that the axioms of ZFC can neither prove nor disprove the continuum hypothesis, that means that we already know that you could arbitrarily choose to use "ZFC with CH" or "ZFC with !CH" and either will be consistent (or as consistent as plain old ZFC). > The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). I don't think this is correct. It's very well-accepted that CH is independent of ZFC. Now, you might mean that most mathematicians suspect that adding CH to ZFC is more intuitive/natural/useful than adding !CH to ZFC, but that's a quite different statement. I don't know much about this, but it seems plausible that both extensions of ZFC could be useful for different things, in the same way that using the parallel postulate is useful for some things (Euclidean geometry) and using alternative parallel postulates is useful for other things (non-Euclidean geometries). The P=NP problem, AFAIK, isn't yet proven to be independent of ZFC, although I have heard some seemingly educated people suggest their suspicions that it may be. And now you have me wondering if you win the Millennium Prize if you prove that P=NP is independent of ZFC. Surely you would.
- gowld 8y ago
  It's novel because no one had bothered to prove the result before. It's not an earth-shattering paper, it's a technical curiosity. the OP is a light article about a light paper, to promote a new lightweight journal that launched this week. https://www.nature.com/natmachintell/ https://www.nature.com/natmachintell/
- Sniffnoy 8y ago
  As other commenters have pointed out, this is backwards. The unsolvability of the halting problem says that there is no one algorithm that can tell you whether an arbitrary Turing machine will halt. But for special types of Turing machines, it is often possible to say whether they will halt. So, if you define a special type of Turing machine, and it turns out that the halting problem is unsolveable even for that restricted type, that is noteworthy.
sgt101 8y ago
The idea that machine learning is a subset of mathematics is very dangerous. In the real world the data is never prepped and clean, and the system is complex and interacts with humans and society at many levels.
- yonkshi 8y ago
  ..could you elaborate? Are you saying ML is dangerous because it’s based on mathematics, and math is too clean to handle real world data?
  - cantthinkofone 8y ago
    I think OP means that idealizing ML experiments using contrived data can distort the picture. Real world, ecologically valid results can only be discovered as they emerge when the algorithms are deployed in production. ML algorithms sometimes cook up solutions that can surprise or even disturb their creators. I'm not sure I exactly agree with this premise. If you read about the principles of chaos engineering, (https://principlesofchaos.org/ https://principlesofchaos.org/) it's possible to simulate real world events in testing. And if there's a rigorous mathematical backbone to ML as there clearly is, some determinations about its limitations should be universal for all cases, even if the emergent results in production are unpredictable and could range over intractably many possible outcomes.
  - syn0byte 8y ago
    I think it's just that calling it "maths" tends to give a false sense of certainty where none is warranted. Example: All the really clever math you use to make an encryption algorithm is all 100% correct. Then all the really clever math you use to show that it would take the heat death of the universe to crack your clever encryption is 100% correct. The user uses 'password' as the key; How does your crypto stand up to a brute force? Is that your algorithms fault? Did your difficulty proof lie to you? I know key length is a well understood. In terms of how algorithmically "valid" real world data that can otherwise torpedo entire complex systems, it's as good an example as any.
    - 8y ago
dooglius 8y ago
> Because EMX is a new model in machine learning, we do not yet know its usefulness for developing real-world algorithms. So these results might not turn out to have practical importance. But we do now know that we should be careful when introducing new models of learning. Moreover, we might need to look again at the many subtleties that can come up, even in established learning models. In other words, "Machine Learning" here is a buzzword, without which the paper would probably get less attention.
- logancg 8y ago
  How do you come to the conclusion that ML is a buzzword here? It's natural to publicize interesting new research that grounds a field -- as statisticial learning theory does for machine learning. Historically, Ben-David and co-authors have produced foundational work on the implications of SLT in ML.
  - dooglius 8y ago
    The problem is that the model was invented in this paper itself, and doesn't actually seem to relate to any actual ML algorithm. Admittedly, I didn't read the paper itself so this may be the overreach on the article's part.
    - zwaps 8y ago
      I don't think that can be true. If it was, it were like this: Hey guys, here's an algorithm. Oh by the way, we can not prove that this algorithm does something useful, and their can you. gets published in nature Talk about bang for the buck
jerf 8y ago
It sounds like we can too determine its practical effect, which is zero. No real-world machine learning algorithm can use the real numbers. We can not obtain them to feed them as input, our real-world machines can not process them if we could, and if we got real-number-based answers, we could not use them. Whether the universe itself is or is not based on real numbers, we do not have access to them either way. Our real-world machines only have access to the computable numbers (and only a subset of them, at that). I'm only speaking to the practical impact. It's possible someone will find some way work this down into something practical, but I'd be fairly surprised. Real machine learners get finite data, for which the continuum hypothesis is irrelevant. (I assume the original authors fully understand this.)
- gowld 8y ago
  The press release says "So these results might not turn out to have practical importance." As you state, that's a much weaker statement than the truth: "So these results almost certainly have no practical importance", and as expected, the stronger statement is nowhere in the original paper. The press release, while being careful not to make false statement, commits a pragmatics sin of letting the reader think there is something going on (by saying "maybe" where they should say "almost certainly not", and by even publushing in the first place a pop-science summary of a highly technical result that has no meaning to a popular audience, and so necessarily the (abstract mathematical, unphysical) importance of the reuslt is completely destroyed in translation.
- mike00632 8y ago
  >We can not obtain them to feed them as input, our real-world machines can not process them if we could... I'm not sure about this. We often make calculations with computer representations of real numbers. We can calculate quantities based on algebraic or transcendental numbers with arbitrary precision (optimizations, navigation), or we can use them as a basis (image processing) and represent rational numbers in their terms. Real numbers are all over computer applications.
  - wyattpeak 8y ago
    Arbitrary precision is irrelevant. By it we mean arbitrary finite precision, which leaves us not only with computable numbers, but rationals. Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. Arbitrary precision models reals, it doesn't actually use them.
jcoffland 8y ago
> Because EMX is a new model in machine learning, we do not yet know its usefulness for developing real-world algorithms. So these results might not turn out to have practical importance. I don't think that's the correct conclusion. More likely, all learning models have unprovable problems so the choice of model is not important wrt the existence of unprovable problems. Really, this is not a surprising result. All mathematical systems gave unprovable problems. ML is a mathematical system and no exception.
sampo 8y ago
The actual paper: https://www.nature.com/articles/s42256-018-0002-3 https://www.nature.com/articles/s42256-018-0002-3 (I find the actual research paper easier to understand than the news coverage.)
roywiggins 8y ago
I much prefer Yedidia & Aaronson's paper that explicitly builds a Turing machine whose halting behavior is independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf https://www.scottaaronson.com/busybeaver.pdf
- jeremysalwen 8y ago
  Isn't this an effective argument that ZFC's axioms are "not enough"?
  - roywiggins 8y ago
    I'm pretty confident that no set of axioms could make every Turing machine's halting problem decidable. From the paper: "consider a Turing machine Z that enumerates, one after the other, each of the provable statements in ZFC. To describe how such a machine might be constructed, Z could iterate over the axioms and inference rules of ZFC, applying each in every possible way to each conclusion or pair of conclusions that had been reached so far. We might ask Z to halt if it ever reaches a contradiction; in other words, Z will halt if and only if it finds a proof of 0 = 1. Because this machine will enumerate every provable statement in ZFC, it will run forever if and only if ZFC is consistent. It follows that Z is a Turing machine for which the question of its behavior (whether or not it halts when run indefinitely) is equivalent to the consistency of ZFC. Therefore, just as ZFC cannot prove its own consistency (assuming ZFC is consistent), ZFC also cannot prove that Z will run forever." This argument works for every axiomatic system: there will be a Turing machine whose halting problem cannot be proved in it. If there wasn't, you'd be able to prove that the consistency-checking machine would halt, thereby proving that the system is consistent, which is impossible per Godel incompleteness.
    - IngoBlechschmid 8y ago
      Indeed, precisely that is true. The shocking conclusion of Gödel's incompleteness theorem is that the problem that our logical foundations are incomplete is inherently unfixable; any extended system of axioms will have new statements which are true but which it cannot prove. (That said, there are certain sub-areas of mathematics where we can prove that every true result in one of these sub-areas is actually provable from a certain system of axioms adapted to the given sub-area. But there is no way around Gödel's incompleteness phenomenon if one wants to encompass all of mathematics (and even arithmetic with natural numbers suffices to yield the incompleteness phenomenon).)
nafizh 8y ago
It's funny to note that the first author signed a boycott [0] for publishing research in Nature's new journal (Nature Machine Intelligence) covering AI topics but is one of the first to publish there. [0] https://openaccess.engineering.oregonstate.edu/signatures https://openaccess.engineering.oregonstate.edu/signatures
- BucketSort 8y ago
  Most researchers are not independent and don't have much choice where they publish. Also, prestige plays a huge role in academia. Getting in Nature is a big deal to them. That's one reason I really dislike academia. They are often playing games that are very far from genuine progress. It's all ladder climbing and groveling at their masters feet. Someone please disrupt academia.
  - jvanderbot 8y ago
    You perfectly described all the non academic jobs I've ever had.
  - sn41 8y ago
    I have worked both in academia and in the industry. Academia is heaven when compared to some of the serpentine performance evaluations in the industry. I have even seen people in the same team undermining each other's work because the top 2 in the group would earn a bonus. The real merit of academia is that people can be alone in a corner doing one's work, if they choose to. Industry enforces socialisation, conformity to norms, and shmoozing. Also, the track record of the academic world vis-a-vis disruption is impressive. The oldest western universities are around 900 years old. That said, the article seems to be a fluff piece about a good but not groundbreaking paper. (Nature MI is not Nature, not by a long shot. It does not have any prestige, yet.)
    - SZJX 8y ago
      > The real merit of academia is that people can be alone in a corner doing one's work, if they choose to. Industry enforces socialisation, conformity to norms, and shmoozing. That's a bit dubious. If you don't network in the academia I doubt you can get far at all, while you can very well just comfortably do your job as a technical employee even if you are not really into networking (if you don't have further ambitions). Networking is absolutely essential to would-be professors or anybody who wants long-term stable employment in the academia, and the competition is much fiercer.
goldenkey 8y ago
Though I haven't analyzed the particulars of this article or the paper -- I can say: we already know that compression is incomplete. That is: we cannot know the actual Kolmogorov Complexity of a piece of data due to the halting problem. It shouldn't be surprising then, that programs of a certain schema, Neural Networks, suffer from similar issues. One could suppose that neural networks that are less code-parameterized, and more data-parameterized (weights), would be less prone to having divergences. Well, it's already established that the more data-like NN aren't turing complete, and aren't powerful enough to solve the kind of problems that we really want to solve (AI.) We have to turn to Hopfield Nets, Boltzman Machines, and RNNs for that. The learning/training process for these nets is pretty much encumbered by their capabilities. That is, exploring a field of numbers is one thing. Exploring a field of code? Code<->Data is the one function in the entire universe that is the most non-linear. It is the one function that cannot be described concisely by mathematics. It's like Wolfram terms, "computationally irreducable." The closer a NN reflects an actual space of turing-complete functions, the farther it is from actually being trainable. Alas...we willl figure out middlegrounds as we have already. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- selestify 8y ago
  What do you mean by divergences?
Frenum 8y ago
For me, the interesting conclusion is that there are things that humans are mathematically incapable of knowing.
- Rainymood 8y ago
  >For me, the interesting conclusion is that there are things that humans are mathematically incapable of knowing. Define >mathematically >incapable >knowing These hastily drawn pop-sciency conclusions are part of the problem why ML/AI has garnered so much media attention these days ...
  - Frenum 8y ago
    I probably should have used the word "implication" instead of "conclusion". My thought process was that there are certain input functions that the learning structures within the human neural network can't discern.
hitsthings 8y ago
I bought into this article until "the field of machine learning, although seemingly distant from mathematical logic" and then I sold it all.
hexhex 8y ago
The author puts Gödel's Incompleteness and the Continuum hypothesis on the same level, which is misleading. The continuum hypothesis is unprovable in our current mathematical foundation ZFC, but there are extensions to ZFC that either make the continuum hypothesis true or false. Incompleteness is a property of every sufficiently complex formal system and thus poses a general constraint in logic. That a particular learning problem is not provable in ZFC is not that surprising. Connections between learning and Incompleteness are way more interesting (and there is a lot of pseudo-research going on, "proving" that humans are not simulatable by computer etc.)
alhazen 8y ago
As the authors say in their paper, "[a] closer look reveals that the source of the problem is in defining learnability as the existence of a learning function rather than the existence of a learning algorithm". Algorithmic decision making under uncertainty is NOT the same thing as finding learning functions over infinite domains. Sometimes such a function does not exist. Why should it? Although the authors seem pretty much aware of this fundamental shortcoming in their analysis, they nevertheless go ahead and publish a whole paper about learning functions! This has a name, intellectual fraud.
jeromebaek 8y ago
I'm curious about the applications of this to machine learning in public policy. In papers like Big Data's Disparate Impact (https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2477899 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2477899) we see misguided and underbudgeted policymakers using very sketchy and very opaque ML algorithms to, for example, decide who stays in prison and who does not. If we can prove that the "decision problem" of who stays in prison and who does not is undecidable, invariant of the specific implementations of the ML algorithm, this could make a case for stopping such overreaches of ML.
gromit1987 8y ago
Can someone explain the meaning of the sentence: ``All distributions in this text are finitely supported over the σ-algebra of all subsets of X'' ? On the one hand, it is impossible to define a probability measure on the σ-algebra of all subsets of [0,1]. On the other hand, if a distribution is finitely supported, then there is no point in using a σ-algebra different than what is generated by its support, right?
DiegoDiazEspin 8y ago
Conclusions emphasize on no practical use for machine learning algorithms but in the way learnability is defined and treated while using mathematical models to describe it. Some of this mathematical models could result in undecidable algorithms if the wrong model is chosen

218 points by joker3 8y ago

How would this affect the practical nature of the problem? Also, why is this novel? All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem.

amelius 8y ago
> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. I think the argument should be the other way around.
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
fredgrott 8y ago
its the old Godel trick of translating it into a different form..ie what Godel originally did to prove his own theorem was to translate his theorem into symbolics and than negate it,.. In their example they are expressing it in set theory and than operating on it... I probably failed at explaining on a simple level...sorry
- rs86 8y ago
  Theorems are strings of symbols and can thus be encoded as numbers, and statements about numbers become statements about theorems. That's why the theorem applies to systems at least as strong as arithmetics
umanwizard 8y ago
What do you mean by "subject to the halting problem"? There are plenty of Turing machines that can be proven to halt. The halting problem doesn't say "given any Turing machine, no algorithm can determine whether it halts". It says "no algorithm can determine whether any given Turing machine halts".
yes_man 8y ago
> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. Assumption that all learning algorithms can be implemented on a Turing machine cannot hold true, since there are mathematical problems that cannot (take for example https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem). Unless you categorise machine learning problems as problems that can be implemented with a Turing machine, making the statement a tautology. Edit: thinking about my comment maybe I am the one being tautologic. If there is a learning algorithm that can solve Hilbert's problem it would transcend mathematics
- umanwizard 8y ago
  "X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". Turing machines are just a formalization of the concept of algorithms/computer programs. So problems that can't be implemented as a Turing machine are not "learning algorithms", or any kind of algorithm.
  - deleted 8y ago
    [deleted]
  - __MatrixMan__ 8y ago
    I think that simplifies things a bit too far. A Turing Machine represents the most complete computational toolkit we happen to know of--not the most complete computational toolkit possible. If we discovered a new computational trick tomorrow--one that a Turing Machine can't perform (the ability to solve the halting problem for Turing Machines, for instance), then we would have discovered another--higher--class of computers, and it would be a reasonable linguistic move to refer to their programs as "algorithms" as well.
    - umanwizard 8y ago
      It is probably not possible to discover a new computational trick, by the Church-Turing thesis. The Church-Turing thesis can't be proven, since it is a statement about what is possible in the physical universe, not a statement about mathematics. But the intuitive arguments in favor of it (i.e., that Turing machines capture exactly what we mean by "computation") are, for me, extremely convincing.
rs86 8y ago
This is about the possibility of proving certain things about the model, not about properties of any implementation. Properties include for example the relation between the amount and quality of data available for training and the accuracy of the model. If a model is proven to learn too slowly it costs more to train it. And some models might never approximate a target function.
bnjmn 8y ago
I suspect the Halting Problem was already an obvious theoretical limitation to machine learning. Just imagine a network trained to classify programs according to whether or not they halt. Then construct a program that runs forever if the network says the program halts, and halts if the network says the program does not halt. No training strategy would ever produce a network that always gives the correct answer in this case. In the Generative Adversarial Network (GAN) framework, this would be the One Weird Trick the generator could pull that would always foil the discriminator. This paper is interesting because it connects learnability to a different kind of undecidability than the Halting Problem: the Continuum Hypothesis. In some ways it's more troubling than the Halting Problem, because at least we can usually figure out whether some actual program halts, using some cleverness, but no one can begin to say whether the Continuum Hypothesis is true or false. The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). That's good news, because it implies the EMX learning model will work: > Their results imply that the finite subsets of the unit interval have monotone-compression schemes, and therefore are learnable in EMX, if and only if the continuum hypothesis is true, which is known to be unprovable. If someone comes along and casts doubt on the Continuum Hypothesis through some mystical but persuasive line of reasoning (news flash: not gonna happen), then there might be some EMX functions that can't be learned, but no one is going to lose sleep over that. There are lots of more immediate reasons why machine learning fails in practice, like not having good training data.
- baddox 8y ago
  I'm confused. I'm pretty sure that the issue isn't "no one can begin to say whether the Continuum Hypothesis is true or false," but rather that we know it to be independent of the widely-used axiomatic set theories (at least ZFC). Since "truth" is defined in terms of the chosen axioms, and we have proven that the axioms of ZFC can neither prove nor disprove the continuum hypothesis, that means that we already know that you could arbitrarily choose to use "ZFC with CH" or "ZFC with !CH" and either will be consistent (or as consistent as plain old ZFC). > The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). I don't think this is correct. It's very well-accepted that CH is independent of ZFC. Now, you might mean that most mathematicians suspect that adding CH to ZFC is more intuitive/natural/useful than adding !CH to ZFC, but that's a quite different statement. I don't know much about this, but it seems plausible that both extensions of ZFC could be useful for different things, in the same way that using the parallel postulate is useful for some things (Euclidean geometry) and using alternative parallel postulates is useful for other things (non-Euclidean geometries). The P=NP problem, AFAIK, isn't yet proven to be independent of ZFC, although I have heard some seemingly educated people suggest their suspicions that it may be. And now you have me wondering if you win the Millennium Prize if you prove that P=NP is independent of ZFC. Surely you would.
gowld 8y ago
It's novel because no one had bothered to prove the result before. It's not an earth-shattering paper, it's a technical curiosity. the OP is a light article about a light paper, to promote a new lightweight journal that launched this week. https://www.nature.com/natmachintell/ https://www.nature.com/natmachintell/
Sniffnoy 8y ago
As other commenters have pointed out, this is backwards. The unsolvability of the halting problem says that there is no one algorithm that can tell you whether an arbitrary Turing machine will halt. But for special types of Turing machines, it is often possible to say whether they will halt. So, if you define a special type of Turing machine, and it turns out that the halting problem is unsolveable even for that restricted type, that is noteworthy.

sgt101 8y ago

The idea that machine learning is a subset of mathematics is very dangerous. In the real world the data is never prepped and clean, and the system is complex and interacts with humans and society at many levels.

yonkshi 8y ago
..could you elaborate? Are you saying ML is dangerous because it’s based on mathematics, and math is too clean to handle real world data?
- cantthinkofone 8y ago
  I think OP means that idealizing ML experiments using contrived data can distort the picture. Real world, ecologically valid results can only be discovered as they emerge when the algorithms are deployed in production. ML algorithms sometimes cook up solutions that can surprise or even disturb their creators. I'm not sure I exactly agree with this premise. If you read about the principles of chaos engineering, (https://principlesofchaos.org/ https://principlesofchaos.org/) it's possible to simulate real world events in testing. And if there's a rigorous mathematical backbone to ML as there clearly is, some determinations about its limitations should be universal for all cases, even if the emergent results in production are unpredictable and could range over intractably many possible outcomes.
- syn0byte 8y ago
  I think it's just that calling it "maths" tends to give a false sense of certainty where none is warranted. Example: All the really clever math you use to make an encryption algorithm is all 100% correct. Then all the really clever math you use to show that it would take the heat death of the universe to crack your clever encryption is 100% correct. The user uses 'password' as the key; How does your crypto stand up to a brute force? Is that your algorithms fault? Did your difficulty proof lie to you? I know key length is a well understood. In terms of how algorithmically "valid" real world data that can otherwise torpedo entire complex systems, it's as good an example as any.
  - 8y ago

dooglius 8y ago

> Because EMX is a new model in machine learning, we do not yet know its usefulness for developing real-world algorithms. So these results might not turn out to have practical importance. But we do now know that we should be careful when introducing new models of learning. Moreover, we might need to look again at the many subtleties that can come up, even in established learning models. In other words, "Machine Learning" here is a buzzword, without which the paper would probably get less attention.

logancg 8y ago
How do you come to the conclusion that ML is a buzzword here? It's natural to publicize interesting new research that grounds a field -- as statisticial learning theory does for machine learning. Historically, Ben-David and co-authors have produced foundational work on the implications of SLT in ML.
- dooglius 8y ago
  The problem is that the model was invented in this paper itself, and doesn't actually seem to relate to any actual ML algorithm. Admittedly, I didn't read the paper itself so this may be the overreach on the article's part.
  - zwaps 8y ago
    I don't think that can be true. If it was, it were like this: Hey guys, here's an algorithm. Oh by the way, we can not prove that this algorithm does something useful, and their can you. gets published in nature Talk about bang for the buck

jerf 8y ago

It sounds like we can too determine its practical effect, which is zero. No real-world machine learning algorithm can use the real numbers. We can not obtain them to feed them as input, our real-world machines can not process them if we could, and if we got real-number-based answers, we could not use them. Whether the universe itself is or is not based on real numbers, we do not have access to them either way. Our real-world machines only have access to the computable numbers (and only a subset of them, at that). I'm only speaking to the practical impact. It's possible someone will find some way work this down into something practical, but I'd be fairly surprised. Real machine learners get finite data, for which the continuum hypothesis is irrelevant. (I assume the original authors fully understand this.)

gowld 8y ago
The press release says "So these results might not turn out to have practical importance." As you state, that's a much weaker statement than the truth: "So these results almost certainly have no practical importance", and as expected, the stronger statement is nowhere in the original paper. The press release, while being careful not to make false statement, commits a pragmatics sin of letting the reader think there is something going on (by saying "maybe" where they should say "almost certainly not", and by even publushing in the first place a pop-science summary of a highly technical result that has no meaning to a popular audience, and so necessarily the (abstract mathematical, unphysical) importance of the reuslt is completely destroyed in translation.
mike00632 8y ago
>We can not obtain them to feed them as input, our real-world machines can not process them if we could... I'm not sure about this. We often make calculations with computer representations of real numbers. We can calculate quantities based on algebraic or transcendental numbers with arbitrary precision (optimizations, navigation), or we can use them as a basis (image processing) and represent rational numbers in their terms. Real numbers are all over computer applications.
- wyattpeak 8y ago
  Arbitrary precision is irrelevant. By it we mean arbitrary finite precision, which leaves us not only with computable numbers, but rationals. Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals. Arbitrary precision models reals, it doesn't actually use them.

jcoffland 8y ago

> Because EMX is a new model in machine learning, we do not yet know its usefulness for developing real-world algorithms. So these results might not turn out to have practical importance. I don't think that's the correct conclusion. More likely, all learning models have unprovable problems so the choice of model is not important wrt the existence of unprovable problems. Really, this is not a surprising result. All mathematical systems gave unprovable problems. ML is a mathematical system and no exception.

sampo 8y ago

The actual paper: https://www.nature.com/articles/s42256-018-0002-3 https://www.nature.com/articles/s42256-018-0002-3 (I find the actual research paper easier to understand than the news coverage.)

roywiggins 8y ago

I much prefer Yedidia & Aaronson's paper that explicitly builds a Turing machine whose halting behavior is independent of ZFC: https://www.scottaaronson.com/busybeaver.pdf https://www.scottaaronson.com/busybeaver.pdf

jeremysalwen 8y ago
Isn't this an effective argument that ZFC's axioms are "not enough"?
- roywiggins 8y ago
  I'm pretty confident that no set of axioms could make every Turing machine's halting problem decidable. From the paper: "consider a Turing machine Z that enumerates, one after the other, each of the provable statements in ZFC. To describe how such a machine might be constructed, Z could iterate over the axioms and inference rules of ZFC, applying each in every possible way to each conclusion or pair of conclusions that had been reached so far. We might ask Z to halt if it ever reaches a contradiction; in other words, Z will halt if and only if it finds a proof of 0 = 1. Because this machine will enumerate every provable statement in ZFC, it will run forever if and only if ZFC is consistent. It follows that Z is a Turing machine for which the question of its behavior (whether or not it halts when run indefinitely) is equivalent to the consistency of ZFC. Therefore, just as ZFC cannot prove its own consistency (assuming ZFC is consistent), ZFC also cannot prove that Z will run forever." This argument works for every axiomatic system: there will be a Turing machine whose halting problem cannot be proved in it. If there wasn't, you'd be able to prove that the consistency-checking machine would halt, thereby proving that the system is consistent, which is impossible per Godel incompleteness.
  - IngoBlechschmid 8y ago
    Indeed, precisely that is true. The shocking conclusion of Gödel's incompleteness theorem is that the problem that our logical foundations are incomplete is inherently unfixable; any extended system of axioms will have new statements which are true but which it cannot prove. (That said, there are certain sub-areas of mathematics where we can prove that every true result in one of these sub-areas is actually provable from a certain system of axioms adapted to the given sub-area. But there is no way around Gödel's incompleteness phenomenon if one wants to encompass all of mathematics (and even arithmetic with natural numbers suffices to yield the incompleteness phenomenon).)

nafizh 8y ago

It's funny to note that the first author signed a boycott [0] for publishing research in Nature's new journal (Nature Machine Intelligence) covering AI topics but is one of the first to publish there. [0] https://openaccess.engineering.oregonstate.edu/signatures https://openaccess.engineering.oregonstate.edu/signatures

BucketSort 8y ago
Most researchers are not independent and don't have much choice where they publish. Also, prestige plays a huge role in academia. Getting in Nature is a big deal to them. That's one reason I really dislike academia. They are often playing games that are very far from genuine progress. It's all ladder climbing and groveling at their masters feet. Someone please disrupt academia.
- jvanderbot 8y ago
  You perfectly described all the non academic jobs I've ever had.
- sn41 8y ago
  I have worked both in academia and in the industry. Academia is heaven when compared to some of the serpentine performance evaluations in the industry. I have even seen people in the same team undermining each other's work because the top 2 in the group would earn a bonus. The real merit of academia is that people can be alone in a corner doing one's work, if they choose to. Industry enforces socialisation, conformity to norms, and shmoozing. Also, the track record of the academic world vis-a-vis disruption is impressive. The oldest western universities are around 900 years old. That said, the article seems to be a fluff piece about a good but not groundbreaking paper. (Nature MI is not Nature, not by a long shot. It does not have any prestige, yet.)
  - SZJX 8y ago
    > The real merit of academia is that people can be alone in a corner doing one's work, if they choose to. Industry enforces socialisation, conformity to norms, and shmoozing. That's a bit dubious. If you don't network in the academia I doubt you can get far at all, while you can very well just comfortably do your job as a technical employee even if you are not really into networking (if you don't have further ambitions). Networking is absolutely essential to would-be professors or anybody who wants long-term stable employment in the academia, and the competition is much fiercer.

goldenkey 8y ago

Though I haven't analyzed the particulars of this article or the paper -- I can say: we already know that compression is incomplete. That is: we cannot know the actual Kolmogorov Complexity of a piece of data due to the halting problem. It shouldn't be surprising then, that programs of a certain schema, Neural Networks, suffer from similar issues. One could suppose that neural networks that are less code-parameterized, and more data-parameterized (weights), would be less prone to having divergences. Well, it's already established that the more data-like NN aren't turing complete, and aren't powerful enough to solve the kind of problems that we really want to solve (AI.) We have to turn to Hopfield Nets, Boltzman Machines, and RNNs for that. The learning/training process for these nets is pretty much encumbered by their capabilities. That is, exploring a field of numbers is one thing. Exploring a field of code? Code<->Data is the one function in the entire universe that is the most non-linear. It is the one function that cannot be described concisely by mathematics. It's like Wolfram terms, "computationally irreducable." The closer a NN reflects an actual space of turing-complete functions, the farther it is from actually being trainable. Alas...we willl figure out middlegrounds as we have already. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

selestify 8y ago
What do you mean by divergences?

Frenum 8y ago

For me, the interesting conclusion is that there are things that humans are mathematically incapable of knowing.

Rainymood 8y ago
>For me, the interesting conclusion is that there are things that humans are mathematically incapable of knowing. Define >mathematically >incapable >knowing These hastily drawn pop-sciency conclusions are part of the problem why ML/AI has garnered so much media attention these days ...
- Frenum 8y ago
  I probably should have used the word "implication" instead of "conclusion". My thought process was that there are certain input functions that the learning structures within the human neural network can't discern.

hitsthings 8y ago

I bought into this article until "the field of machine learning, although seemingly distant from mathematical logic" and then I sold it all.

hexhex 8y ago

The author puts Gödel's Incompleteness and the Continuum hypothesis on the same level, which is misleading. The continuum hypothesis is unprovable in our current mathematical foundation ZFC, but there are extensions to ZFC that either make the continuum hypothesis true or false. Incompleteness is a property of every sufficiently complex formal system and thus poses a general constraint in logic. That a particular learning problem is not provable in ZFC is not that surprising. Connections between learning and Incompleteness are way more interesting (and there is a lot of pseudo-research going on, "proving" that humans are not simulatable by computer etc.)

alhazen 8y ago

As the authors say in their paper, "[a] closer look reveals that the source of the problem is in defining learnability as the existence of a learning function rather than the existence of a learning algorithm". Algorithmic decision making under uncertainty is NOT the same thing as finding learning functions over infinite domains. Sometimes such a function does not exist. Why should it? Although the authors seem pretty much aware of this fundamental shortcoming in their analysis, they nevertheless go ahead and publish a whole paper about learning functions! This has a name, intellectual fraud.

jeromebaek 8y ago

I'm curious about the applications of this to machine learning in public policy. In papers like Big Data's Disparate Impact (https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2477899 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2477899) we see misguided and underbudgeted policymakers using very sketchy and very opaque ML algorithms to, for example, decide who stays in prison and who does not. If we can prove that the "decision problem" of who stays in prison and who does not is undecidable, invariant of the specific implementations of the ML algorithm, this could make a case for stopping such overreaches of ML.

gromit1987 8y ago

Can someone explain the meaning of the sentence: ``All distributions in this text are finitely supported over the σ-algebra of all subsets of X'' ? On the one hand, it is impossible to define a probability measure on the σ-algebra of all subsets of [0,1]. On the other hand, if a distribution is finitely supported, then there is no point in using a σ-algebra different than what is generated by its support, right?

DiegoDiazEspin 8y ago

Conclusions emphasize on no practical use for machine learning algorithms but in the way learnability is defined and treated while using mathematical models to describe it. Some of this mathematical models could result in undecidable algorithms if the wrong model is chosen