8 ms·

I don't think this constitutes a formal proof on any way at all.

JoshCole 4y ago
The formal proofs aren't in a Hacker News comment; just go read game theory research papers. For example, https://www.cs.cmu.edu/~noamb/papers/17-NIPS-Safe.pdf https://www.cs.cmu.edu/~noamb/papers/17-NIPS-Safe.pdf Or go try and solve a moderately complicated anything without allowing yourself abstractions with error. I won't wait on you, because your solutions will never terminate in my lifetime for even things as simple as chess which is a hell of a lot simpler than reality.
JoshCole 4y ago
Take the simplest problem of searching over a continuous range between zero and one exhaustively. Let the value you search for be 0.1. By a diagnolization argument we can realize that even a search carried on for an infinite amount of time and granted an infinite amount of space would not terminate. After all, to find 0.1 you need to make it past 0.01. But to reach that you have to reach 0.001. And so on. Let abstraction map from N to 1 over this space. As N goes up, abstraction error goes up, but the problem is no longer impossible because the diagnolization proof no longer holds. Let b be a branching factor in a game. As b goes to infinity, the game graph becomes continuous. In learning formulations under the game theoretic school of thought you have to search the game graph to get the average of your policies proportional to your counterfactual regret. That implies walking the continuous game graph. In reinforcement learning the bellman equations give you your values. This is also defined in terms of the game graph. So again we fall prey to the problem. We've shown that walking continuous things is impossible even under conditions that are ideal - infinite speed and memory and we've shown that this relates to the learning problem formulations I spoke of. Obviously this only gets worse when we impose reality - we don't actually have infinite space on our computers. They don't compute for an infinite amount of time either. But notice that before we searched for infinite space and time and we failed? When we move down to finite space and finite time we still have the property of completing after full enumeration. We have a finite amount of computing capacity. We have a finite amount of computational storage. Yet the growth rate for unabstracted game trees is exponential. Let c be our constraints. An abstracted game maps n states to one state. So it has log_n(X) where X is your state count. An abstracted game has X states. Since log_n(x) < X we know there exist terminating algorithms for abstraction that are not terminating for unabstracted because log_n(x) < X when X = c. So we get log_n(X) < c when X = c. This is actually much less than the real world gains. Since in learning we get the policy expectations multiple times over the game graph and the convergence guarantees relate to the complexity of the graph you get a much more worthwhile window than just the difference of log_n(X) versus X. For much tighter bounds check out game theory research. They get error bounds on the abstraction error too by choosing clustering solutions with provable properties. So it really has a much stronger formal treatment than you might imagine.
- random314 4y ago
  You are talking about game theory without any precise definition of "abstraction", which it seems like one can define it to be whatever one wants it to be. One abstraction that is very useful is linear algebra which is an abstraction without errors. Same goes for category theory. Grothendiecks work wasn't about tolerating errors in abstractions either. Simple abstractions like generic containers are also not about ignoring errors. Honestly, the random segues to diagonalization arguments, game theory, continuous functions, RL and Bellman equations(WTF!) sound like stream of conciousness random ramblings and an attempt at "out jargoning", much less a "formal proof". Reminds me of this story by Tadelis. https://thecorrespondent.com/100/the-new-dot-com-bubble-is-here-its-called-online-advertising https://thecorrespondent.com/100/the-new-dot-com-bubble-is-h... "We use Lagrange multipliers," one of them said. And for a second, Tadelis was astounded. What? Lagrange multipliers? But Lagrange multipliers don’t have anything to do with ..."Then it hit me," Tadelis recalled. "This guy is trying to out-jargon me!"
  - JoshCole 4y ago
    > One abstraction that is very useful is linear algebra which is an abstraction without errors. Bullshit. Your claim that there is no abstraction error in linear algebra (when run on computers - we're in subdiscussion related to programming) is false. Computers can't represent all numbers [1]. They can only represent the computable numbers in theory and even then only a subset of computable numbers can actually be computed. Therefore, there is abstraction error in linear algebra on computers. This isn't at all a theoretical thing. This regularly has implication on algorithm design. You ought to have known this, because the truth about floating point numbers has been well publicized [2]. > Same goes for category theory. Grothendiecks work wasn't about tolerating errors in abstractions either. Simple abstractions like generic containers are also not about ignoring errors. You're just ignoring that these things when implemented in computers actually do have error, because you find it convenient. You're also apparently not self-aware enough to realize that this agrees with my central premise. Think about your thinking and you'll notice that this failure is indicative of your own minds belief in wrong abstractions being right - otherwise you wouldn't have been able to make this error. > Honestly, the random segues to diagonalization arguments, game theory, continuous functions, RL and Bellman equations(WTF!) sound like stream of conciousness random ramblings and an attempt at "out jargoning", much less a "formal proof". Reminds me of this story by Tadelis. We're talking about learning as it relates to abstraction. If you can't see why a learning problem formulation is relevant to discussion about whether learning an abstraction is appropriate that says a lot more about your reasoning than it does my articulation. As a reminder the OP said: > Teaching people to think about abstractions wrong is not in any way helpful. Everyone I know including myself had to spend years writing bad code before realizing that this way of thinking is counterproductive. I've disagreed with the claim that teaching a bad abstraction that has to be unlearned is bad. I've shown that in learning problems, teaching a bad abstraction can actually be good. I've given proofs to the effect that there are times in which teaching a bad abstraction produces algorithms which terminate in situations where teaching a perfect abstraction doesn't terminate. I've given you links to mathematics showing that given a bad abstraction as a starting point you can produce agents which outcompete something which doesn't use an abstraction. The paper in question takes a bad abstraction and improves upon it after getting it during the challenge of a more specific problem. > "We use Lagrange multipliers," one of them said. Hacker News guidelines call for more thoughtful points, not less thoughtful points, as threads get deeper. It also calls for assumption of good faith. It calls for increasing nuance [3]. What you are doing here - it isn't that. At the risk of starting something painfully obvious, talking about random shit people that aren't me said that you found dumb isn't actually relevant to the discussion. This is a subthread that is on the topic of learning and abstraction. I'm talking about both topics. You aren't. > random ramblings I'm sharing something deeply counterintuitive but true because I think people might find it interesting. Right algorithm + correct data can be worse than right algorithm + wrong data. This is deeply counterintuitive and I find it very fascinating, but it falls out of the formal definitions of utility under multiple different learning frameworks. Something isn't bad because it has abstractions with error in it. Teaching an abstraction with error in it isn't bad either. It isn't even bad when you can find the error - because you're in a more specific situation the learning problem changes, in the general case it was too hard to compute the unabstracted best thing to do, but you can reduce the error in your abstraction when you get more specific because there are less states and so the learning problem becomes more tractable. [1]: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2]: https://floating-point-gui.de/ https://floating-point-gui.de/ A person might try to respond to this point by claiming arbitrary precision numbers exist. That person is lying to themselves. They don't exist. The abstraction error is just in a different place. Go back to the definition of Turing Machines and observe again that not all numbers are computable - we are in an abstraction subject to error and you can't escape this while staying in the Turing framework [1]. [3]: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

The formal proofs aren't in a Hacker News comment; just go read game theory research papers. For example, https://www.cs.cmu.edu/~noamb/papers/17-NIPS-Safe.pdf https://www.cs.cmu.edu/~noamb/papers/17-NIPS-Safe.pdf Or go try and solve a moderately complicated anything without allowing yourself abstractions with error. I won't wait on you, because your solutions will never terminate in my lifetime for even things as simple as chess which is a hell of a lot simpler than reality.

JoshCole 4y ago

Take the simplest problem of searching over a continuous range between zero and one exhaustively. Let the value you search for be 0.1. By a diagnolization argument we can realize that even a search carried on for an infinite amount of time and granted an infinite amount of space would not terminate. After all, to find 0.1 you need to make it past 0.01. But to reach that you have to reach 0.001. And so on. Let abstraction map from N to 1 over this space. As N goes up, abstraction error goes up, but the problem is no longer impossible because the diagnolization proof no longer holds. Let b be a branching factor in a game. As b goes to infinity, the game graph becomes continuous. In learning formulations under the game theoretic school of thought you have to search the game graph to get the average of your policies proportional to your counterfactual regret. That implies walking the continuous game graph. In reinforcement learning the bellman equations give you your values. This is also defined in terms of the game graph. So again we fall prey to the problem. We've shown that walking continuous things is impossible even under conditions that are ideal - infinite speed and memory and we've shown that this relates to the learning problem formulations I spoke of. Obviously this only gets worse when we impose reality - we don't actually have infinite space on our computers. They don't compute for an infinite amount of time either. But notice that before we searched for infinite space and time and we failed? When we move down to finite space and finite time we still have the property of completing after full enumeration. We have a finite amount of computing capacity. We have a finite amount of computational storage. Yet the growth rate for unabstracted game trees is exponential. Let c be our constraints. An abstracted game maps n states to one state. So it has log_n(X) where X is your state count. An abstracted game has X states. Since log_n(x) < X we know there exist terminating algorithms for abstraction that are not terminating for unabstracted because log_n(x) < X when X = c. So we get log_n(X) < c when X = c. This is actually much less than the real world gains. Since in learning we get the policy expectations multiple times over the game graph and the convergence guarantees relate to the complexity of the graph you get a much more worthwhile window than just the difference of log_n(X) versus X. For much tighter bounds check out game theory research. They get error bounds on the abstraction error too by choosing clustering solutions with provable properties. So it really has a much stronger formal treatment than you might imagine.

random314 4y ago
You are talking about game theory without any precise definition of "abstraction", which it seems like one can define it to be whatever one wants it to be. One abstraction that is very useful is linear algebra which is an abstraction without errors. Same goes for category theory. Grothendiecks work wasn't about tolerating errors in abstractions either. Simple abstractions like generic containers are also not about ignoring errors. Honestly, the random segues to diagonalization arguments, game theory, continuous functions, RL and Bellman equations(WTF!) sound like stream of conciousness random ramblings and an attempt at "out jargoning", much less a "formal proof". Reminds me of this story by Tadelis. https://thecorrespondent.com/100/the-new-dot-com-bubble-is-here-its-called-online-advertising https://thecorrespondent.com/100/the-new-dot-com-bubble-is-h... "We use Lagrange multipliers," one of them said. And for a second, Tadelis was astounded. What? Lagrange multipliers? But Lagrange multipliers don’t have anything to do with ..."Then it hit me," Tadelis recalled. "This guy is trying to out-jargon me!"
- JoshCole 4y ago
  > One abstraction that is very useful is linear algebra which is an abstraction without errors. Bullshit. Your claim that there is no abstraction error in linear algebra (when run on computers - we're in subdiscussion related to programming) is false. Computers can't represent all numbers [1]. They can only represent the computable numbers in theory and even then only a subset of computable numbers can actually be computed. Therefore, there is abstraction error in linear algebra on computers. This isn't at all a theoretical thing. This regularly has implication on algorithm design. You ought to have known this, because the truth about floating point numbers has been well publicized [2]. > Same goes for category theory. Grothendiecks work wasn't about tolerating errors in abstractions either. Simple abstractions like generic containers are also not about ignoring errors. You're just ignoring that these things when implemented in computers actually do have error, because you find it convenient. You're also apparently not self-aware enough to realize that this agrees with my central premise. Think about your thinking and you'll notice that this failure is indicative of your own minds belief in wrong abstractions being right - otherwise you wouldn't have been able to make this error. > Honestly, the random segues to diagonalization arguments, game theory, continuous functions, RL and Bellman equations(WTF!) sound like stream of conciousness random ramblings and an attempt at "out jargoning", much less a "formal proof". Reminds me of this story by Tadelis. We're talking about learning as it relates to abstraction. If you can't see why a learning problem formulation is relevant to discussion about whether learning an abstraction is appropriate that says a lot more about your reasoning than it does my articulation. As a reminder the OP said: > Teaching people to think about abstractions wrong is not in any way helpful. Everyone I know including myself had to spend years writing bad code before realizing that this way of thinking is counterproductive. I've disagreed with the claim that teaching a bad abstraction that has to be unlearned is bad. I've shown that in learning problems, teaching a bad abstraction can actually be good. I've given proofs to the effect that there are times in which teaching a bad abstraction produces algorithms which terminate in situations where teaching a perfect abstraction doesn't terminate. I've given you links to mathematics showing that given a bad abstraction as a starting point you can produce agents which outcompete something which doesn't use an abstraction. The paper in question takes a bad abstraction and improves upon it after getting it during the challenge of a more specific problem. > "We use Lagrange multipliers," one of them said. Hacker News guidelines call for more thoughtful points, not less thoughtful points, as threads get deeper. It also calls for assumption of good faith. It calls for increasing nuance [3]. What you are doing here - it isn't that. At the risk of starting something painfully obvious, talking about random shit people that aren't me said that you found dumb isn't actually relevant to the discussion. This is a subthread that is on the topic of learning and abstraction. I'm talking about both topics. You aren't. > random ramblings I'm sharing something deeply counterintuitive but true because I think people might find it interesting. Right algorithm + correct data can be worse than right algorithm + wrong data. This is deeply counterintuitive and I find it very fascinating, but it falls out of the formal definitions of utility under multiple different learning frameworks. Something isn't bad because it has abstractions with error in it. Teaching an abstraction with error in it isn't bad either. It isn't even bad when you can find the error - because you're in a more specific situation the learning problem changes, in the general case it was too hard to compute the unabstracted best thing to do, but you can reduce the error in your abstraction when you get more specific because there are less states and so the learning problem becomes more tractable. [1]: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2]: https://floating-point-gui.de/ https://floating-point-gui.de/ A person might try to respond to this point by claiming arbitrary precision numbers exist. That person is lying to themselves. They don't exist. The abstraction error is just in a different place. Go back to the definition of Turing Machines and observe again that not all numbers are computable - we are in an abstraction subject to error and you can't escape this while staying in the Turing framework [1]. [3]: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html