3 ms·

I suspect the Halting Problem was already an obvious theoretical limitation to machine learning. Just imagine a network trained to classify programs according t

by 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.
- IngoBlechschmid 8y ago
  Indeed, unlike the axiom of choice, which is routinely used by most working mathematicians, the continuum hypothesis is not. (In fact, most working mathematicians can probably not even state this hypothesis precisely, as they're concerned with different areas of mathematics and haven't received the necessary training in logics or set theory; and among set theorists, consequences of CH are explored just as often as consequences of !CH are. (CH does simplify several things, such as arithmetic with infinite cardinal numbers, but the point still stands.)) Yes, the P=NP problem is not yet proven to be independent of ZFC. It's certainly a possibility, and to be honest a quite intriguing and fun one, but we shouldn't make the mistake to think that any hard open problem is independent of ZFC. (I know that you didn't state that, I'm just writing this for the record.) Sometimes hard open problems are simply hard open problems.
  - baddox 8y ago
    I agree on your last point, but I will say the P=NP feels like a particularly good candidate for being independent of ZFC, not only because it seems to be very difficult, but because it feels so adjacent to things like the halting problem and incompleteness theorems. :)
- bnjmn 8y ago
  > 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 guess I'm a constructivist about this. You can't just wave your hands and take !CH as an axiom. Remember what that means: you reject that there is no set with cardinality between the integers and the reals, so you're implying there is such a set. I realize not all mathematicians share this point of view, but if you can't somehow construct the intermediate set you're claiming exists, or show that it can be constructed, then you don't really have any grounds for taking !CH to be true. Without a positive reason for believing such a set exists, I have a hard time pretending that !CH could possibly be a "useful" (your word) axiom to add to ZFC. By contrast, imagining that CH might be true is easy. You don't have to construct any never-before-seen mathematical objects to make your point. You just presume, without fear of being contradicted by ZFC, that the integers are countably infinite, and the reals are uncountably infinite but only sort of "minimally" so (there are higher orders of uncountable infinity, but none lower). You may never be able to prove CH (certainly not with ZFC, and almost certainly not with any other logical system), but at least the model makes sense: there's no cardinality in between that of the integers and the reals. Which is not to say that CH is particularly useful! In fact, maybe the most interesting thing about the paper is the idea that the CH could be meaningfully connected to anything in an applied form of math like machine learning. Does that weird connection between CH and ML have any practical consequences for ML in general, or the EMX learning algorithm in particular? Probably not, especially since assuming CH is true just implies EMX should work, so it's fine to keep using it to solve learning problems. In other words, if you wanted to convince an ML practitioner that their learning algorithms might be unreliable because the Continuum Hypothesis might be false, I think they would be within their rights to request you show them an actual set with cardinality between the integers and the reals. When you couldn't, they would then be within their rights to ignore your objection.
ginnungagap 8y ago
Most mathematicians don't care at all about CH and among those who do not all believe that ZFC+CH is more intuitive than ZFC+not CH (really it makes no sense to believe whether it is true or not unless you believe in some platonic universe of sets, but I do maths, not philosophy), for example Gödel himself thought that the continuum could be aleph_2, Woodin's Omega logic argued the same (but this is somewhat controversial) and the proper forcing axiom also implies that the continuum is aleph_2
- bnjmn 8y ago
  Please see my reply to @baddox. You say you do math and not philosophy, but the whole CH independence proof kinda moves this discussion out of the realm of (ZFC-based) math, doesn't it? If you don't want to consider philosophy here, there's not much more to say.
  - ginnungagap 8y ago
    Plenty of math is done outside of ZFC, a lot of modern set theory for example, but that doesn't make it philosophy. Even Grothendieck's EGA has a couple of arguments that cannot be carried out in ZFC in the generality he presents them in, but I wouldn't call EGA a philosophy treatise nor an algebraic geometer a philosopher

by bnjmn 8y ago

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.

IngoBlechschmid 8y ago
Indeed, unlike the axiom of choice, which is routinely used by most working mathematicians, the continuum hypothesis is not. (In fact, most working mathematicians can probably not even state this hypothesis precisely, as they're concerned with different areas of mathematics and haven't received the necessary training in logics or set theory; and among set theorists, consequences of CH are explored just as often as consequences of !CH are. (CH does simplify several things, such as arithmetic with infinite cardinal numbers, but the point still stands.)) Yes, the P=NP problem is not yet proven to be independent of ZFC. It's certainly a possibility, and to be honest a quite intriguing and fun one, but we shouldn't make the mistake to think that any hard open problem is independent of ZFC. (I know that you didn't state that, I'm just writing this for the record.) Sometimes hard open problems are simply hard open problems.
- baddox 8y ago
  I agree on your last point, but I will say the P=NP feels like a particularly good candidate for being independent of ZFC, not only because it seems to be very difficult, but because it feels so adjacent to things like the halting problem and incompleteness theorems. :)
bnjmn 8y ago
> 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 guess I'm a constructivist about this. You can't just wave your hands and take !CH as an axiom. Remember what that means: you reject that there is no set with cardinality between the integers and the reals, so you're implying there is such a set. I realize not all mathematicians share this point of view, but if you can't somehow construct the intermediate set you're claiming exists, or show that it can be constructed, then you don't really have any grounds for taking !CH to be true. Without a positive reason for believing such a set exists, I have a hard time pretending that !CH could possibly be a "useful" (your word) axiom to add to ZFC. By contrast, imagining that CH might be true is easy. You don't have to construct any never-before-seen mathematical objects to make your point. You just presume, without fear of being contradicted by ZFC, that the integers are countably infinite, and the reals are uncountably infinite but only sort of "minimally" so (there are higher orders of uncountable infinity, but none lower). You may never be able to prove CH (certainly not with ZFC, and almost certainly not with any other logical system), but at least the model makes sense: there's no cardinality in between that of the integers and the reals. Which is not to say that CH is particularly useful! In fact, maybe the most interesting thing about the paper is the idea that the CH could be meaningfully connected to anything in an applied form of math like machine learning. Does that weird connection between CH and ML have any practical consequences for ML in general, or the EMX learning algorithm in particular? Probably not, especially since assuming CH is true just implies EMX should work, so it's fine to keep using it to solve learning problems. In other words, if you wanted to convince an ML practitioner that their learning algorithms might be unreliable because the Continuum Hypothesis might be false, I think they would be within their rights to request you show them an actual set with cardinality between the integers and the reals. When you couldn't, they would then be within their rights to ignore your objection.

ginnungagap 8y ago

Most mathematicians don't care at all about CH and among those who do not all believe that ZFC+CH is more intuitive than ZFC+not CH (really it makes no sense to believe whether it is true or not unless you believe in some platonic universe of sets, but I do maths, not philosophy), for example Gödel himself thought that the continuum could be aleph_2, Woodin's Omega logic argued the same (but this is somewhat controversial) and the proper forcing axiom also implies that the continuum is aleph_2

bnjmn 8y ago
Please see my reply to @baddox. You say you do math and not philosophy, but the whole CH independence proof kinda moves this discussion out of the realm of (ZFC-based) math, doesn't it? If you don't want to consider philosophy here, there's not much more to say.
- ginnungagap 8y ago
  Plenty of math is done outside of ZFC, a lot of modern set theory for example, but that doesn't make it philosophy. Even Grothendieck's EGA has a couple of arguments that cannot be carried out in ZFC in the generality he presents them in, but I wouldn't call EGA a philosophy treatise nor an algebraic geometer a philosopher