5 ms·

Can someone correct me, if I'm wrong, but statistics doesn't allow Turing-complete models, right? Machine learning certainly allows that (for example an RNN).

taeric 7y ago
Depends what you mean. At the least, you can easily use statistics to talk about how well an rnn works. It may be that we can reduce an rnn to a distribution, someday. It does seem true that statistics are more suited to describe analytical models. But, that seems as much a quirk of history than a foregone conclusion. As an easy example, I can give you the statistics of my bike ride. Such that you can get a pretty solid understanding of what my next week's worth of rides will be like, per the parameters used in the description. This does basically nothing to help you build a bike. Or make the ride yourself. So too, would a statistical model of an rnn be. And indeed, this is no different than a statistical model for how often humans will make mistakes see any process. Or a model for how many students will successfully learn a topic.
mturmon 7y ago
This is kind of a fun question because it places the notion of “computational” computability (classical CS) alongside that of classical computability (finding a model by, say, minimizing an error which in turn boils down to calculus or linear system solution). Long story short, because of the power of real numbers — with each one encoding an infinite sequence of bits — it’s not clear that even “simple” computations important to elementary statistical models, like exponentiating, have low computational complexity. Computing, say, “e” can be done by a Turing machine, but it’s nontrivial. Another observation along the same lines is that some simple statistical models turn out to really complex — like “find a such that the model y = sin (a x) fits sample data (x1, y1),..., where abs(y) < 1”. This simple model class is well known to have infinite VC dimension, because a can be arbitrarily large. Another way to say it may be that Turing completeness is not a very sharp tool to separate model classes. I found this helpful: http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf

taeric 7y ago

Depends what you mean. At the least, you can easily use statistics to talk about how well an rnn works. It may be that we can reduce an rnn to a distribution, someday. It does seem true that statistics are more suited to describe analytical models. But, that seems as much a quirk of history than a foregone conclusion. As an easy example, I can give you the statistics of my bike ride. Such that you can get a pretty solid understanding of what my next week's worth of rides will be like, per the parameters used in the description. This does basically nothing to help you build a bike. Or make the ride yourself. So too, would a statistical model of an rnn be. And indeed, this is no different than a statistical model for how often humans will make mistakes see any process. Or a model for how many students will successfully learn a topic.

mturmon 7y ago

This is kind of a fun question because it places the notion of “computational” computability (classical CS) alongside that of classical computability (finding a model by, say, minimizing an error which in turn boils down to calculus or linear system solution). Long story short, because of the power of real numbers — with each one encoding an infinite sequence of bits — it’s not clear that even “simple” computations important to elementary statistical models, like exponentiating, have low computational complexity. Computing, say, “e” can be done by a Turing machine, but it’s nontrivial. Another observation along the same lines is that some simple statistical models turn out to really complex — like “find a such that the model y = sin (a x) fits sample data (x1, y1),..., where abs(y) < 1”. This simple model class is well known to have infinite VC dimension, because a can be arbitrarily large. Another way to say it may be that Turing completeness is not a very sharp tool to separate model classes. I found this helpful: http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf