I’ve been mainly working on my graduate studies, but as a side project I’ve been working on developing a more efficient way of doing Solomonoff induction. The idea is that Solomonoff induction requires some language over which to construct programs. But most ‘formal’ languages we know of—such as Turing machines—do not fit well with observed reality, in that you wind up requiring a very large additive constant complexity to the complexity of your programs. So the goal is to find some computational substrate that will not require such large additive complexity. The most obvious solution to this would be probabilistic graphical networks (such as Bayesian networks), but searching through Bayesian networks is extremely hard because there are a huge number of possible network topologies. So my idea is to restrict the network topologies. It is known that ANNs are able to, in principle, simulate any function, but I suspect most ANNs are too crude. Instead, I’ve been working on combining ANN approaches with hierarchical bayesian networks. I suspect the resulting structure has enough power to produce most sequences found in real life while also being very easy to optimize over due to the recursive structure and the fact that good learning algorithms for ANNs are known. My initial experiments in this direction have been positive; the main goal now is to derive a more efficient learning algorithm and to prove bounds on time- and space-complexity.
Are artificial neural networks really Turing-complete? Yep, they are [Siegelman, Sontag 91]. Amount of neurons in the paper is 105, with rational edge weights, so it’s really Kolmogorov-complex. This, however, doesn’t say if we can build good machines for specific purposes.
Let’s figure out how to sort a dozen numbers with λ-calculus and sorting networks. It must stand to notice, that lambda-expression is O(1), whereas sorter network is O(n (log n)^2) in size.
Batcher’s odd–even mergesort would be O(log n) levels deep, and given one neuron is used to implement comparator, would result in O(n!) possible connections (around 229 per level). That we need 200 bits of insight to sort a dozen of numbers with that specific method does not mean that there is no cheaper way to do that, but sets a reasonable upper bound.
Apparently, I cannot do good lambda-calculus, but seems like we can do merge sorting of Church-encoded numerals in less than a hundred lambda-terms which is about the same amount of bits as sorting networks.
On a second note: how are Bayesian networks different from preceptrons, except fro having no thresholds?
I’ve been mainly working on my graduate studies, but as a side project I’ve been working on developing a more efficient way of doing Solomonoff induction. The idea is that Solomonoff induction requires some language over which to construct programs. But most ‘formal’ languages we know of—such as Turing machines—do not fit well with observed reality, in that you wind up requiring a very large additive constant complexity to the complexity of your programs. So the goal is to find some computational substrate that will not require such large additive complexity. The most obvious solution to this would be probabilistic graphical networks (such as Bayesian networks), but searching through Bayesian networks is extremely hard because there are a huge number of possible network topologies. So my idea is to restrict the network topologies. It is known that ANNs are able to, in principle, simulate any function, but I suspect most ANNs are too crude. Instead, I’ve been working on combining ANN approaches with hierarchical bayesian networks. I suspect the resulting structure has enough power to produce most sequences found in real life while also being very easy to optimize over due to the recursive structure and the fact that good learning algorithms for ANNs are known. My initial experiments in this direction have been positive; the main goal now is to derive a more efficient learning algorithm and to prove bounds on time- and space-complexity.
Are artificial neural networks really Turing-complete? Yep, they are [Siegelman, Sontag 91]. Amount of neurons in the paper is 105, with rational edge weights, so it’s really Kolmogorov-complex. This, however, doesn’t say if we can build good machines for specific purposes.
Let’s figure out how to sort a dozen numbers with λ-calculus and sorting networks. It must stand to notice, that lambda-expression is O(1), whereas sorter network is O(n (log n)^2) in size.
Batcher’s odd–even mergesort would be O(log n) levels deep, and given one neuron is used to implement comparator, would result in O(n!) possible connections (around 229 per level). That we need 200 bits of insight to sort a dozen of numbers with that specific method does not mean that there is no cheaper way to do that, but sets a reasonable upper bound.
Apparently, I cannot do good lambda-calculus, but seems like we can do merge sorting of Church-encoded numerals in less than a hundred lambda-terms which is about the same amount of bits as sorting networks.
On a second note: how are Bayesian networks different from preceptrons, except fro having no thresholds?