5 ms·

> In fact, I'd go as far as to say that this is a new kind of Inductive Programming. I wouldn't. Traditional NNs are widely called funciton approximators, or f

> In fact, I'd go as far as to say that this is a new kind of Inductive Programming. I wouldn't. Traditional NNs are widely called funciton approximators, or function induction. That's because they're not Turing-complete, and in this case don't even have memory. This makes them decidedly not programs, just functions. Of course, they could be modified with recurrence (a suggestion of future work), or even more complete memory systems (e.g. equipping a neural controller with a tape), making it Turing-complete. Keep in mind the functional approximation power isn't increased by architecture search alone (there's no restriction from doing weight training). What seems novel here is how significant architecture alone is (I wouldn't guess it being this powerful), and this possibly has implications on the connection with the human brain -- in which my vague impression is that connections themselves are much more tuned than weights; also possibly giving greater emphasis on architecture training.

YeGoblynQueenne 7y ago
>> I wouldn't. Traditional NNs are widely called funciton approximators, or function induction. That's because they're not Turing-complete, and in this case don't even have memory. This makes them decidedly not programs, just functions. But what the article describes is not function approximation anymore. Their system doesn't optimise a set of parameters. The search for an optimal set of parameters has been replaced entirely with a search for an optimal architecture with a single, shared parameter. Note also that you don't need something to be Turing-complete for it to be a program. For instance, a regular automaton is a program, but it's not Turing complete. Turing completeness makes something, well, a Universal Turing Machine, which can compute any program. But a program is just a set of instructions.
- darkmighty 7y ago
  > Note also that you don't need something to be Turing-complete for it to be a program. For instance, a regular automaton is a program, but it's not Turing complete. Turing completeness makes something, well, a Universal Turing Machine, which can compute any program. But a program is just a set of instructions. A regular automaton is a program (and a function is a program), but all programs cannot be expressed as finite (regular) automatons (FAs). So FAs are a subset of programs. If we equate programs with mathematical algorithms, in general they really need the unlimited memory aspect (or at least the capability of abstracting memory, which in practice is always finite of course). To make things clear, an example: a fixed function (or FA) cannot sort a list of numbers of variable size. You can train your function to sort any K numbers, which are the input variables. But because it has no memory, you cannot input variables sequentially (in the FA case you cannot input arbitrarily many variables). You've essentially created a sorting network[1]. Not only that, but for each input growth you need to re-train your architecture. The nice thing about program inference is that it hopefully captures the fundamental algorithm behind a program, which generalizes to arbitrary sizes. It's not that arbitrary sizes are necessary in practice (again computers are always bounded), it's that this abstraction/generalization is extremely useful, saving data and allowing large (arbitrary) variation in input. [1] https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network > a Universal Turing Machine, which can compute any program I feel there's a bit of confusion here. Turing Machines themselves can compute any program (i.e. you can represent any program as a TM) -- that follows essentially from the definition of algorithm (a set of well defined steps given unlimited paper); again languages accepted by FAs are a restricted subset of TMs (the former accepts a regular language while the latter recursively enumerable languages). There are special Turing Machines that simulate arbitrary Turing Machines -- those are called Universal Turing machines. It's a desirable characteristic of any computer, of course (the ability to input arbitrary programs). We refer to program description languages that can describe any Turing Machine as Turing-complete. You could make a Universal Turing machine that accepts this kind of language directly or you could in principle just build a Turing machine that executes the given algorithm (for example using a gate array/FPGA to encode the state automaton, plus some large memory for the tape).
  - YeGoblynQueenne 7y ago
    Yes, sloppy definition of Turing completenes on my part. I apologise unrservedly. But, I still don't understand your objection. You agree that a regular automaton is a program, and that it's not Turing complete. So a program does not need to be Turing complete. I didn't say, nor do I think, that the algorithm described in this article is Turing complete. I think it perfoms program induction. That's as far as I went. I still don't see where Turing completeness comes into it.
YeGoblynQueenne 7y ago
[sorry- splitting this off 'cause it's getting a bit large and to make the whole thing easier to read] >> What seems novel here is how significant architecture alone is (I wouldn't guess it being this powerful), and this possibly has implications on the connection with the human brain -- in which my vague impression is that connections themselves are much more tuned than weights; also possibly giving greater emphasis on architecture training. You are surprised by how significant architecture is. I am not surprised at all. I think it's been very clear for a while now that the success of deep neural networks is entirely due to their architectures that are fine-tuned to specific tasks. On the one hand, it's obvious that this is the case if you look at the two major successes of deep learning: CNNs for vision and LSTMs (and variants) for sequence learning. Both are extremely precise, extremely intricate architectures with an intense focus one one kind of task, and that kind of task, alone. On the other hand, the vast majority of neural net publications are specifically about new architectures, or, rather, tweaks to existing architectures. In fact, in my boldest moments I'd go as far as to suggest that weight training with gradient optimisation has kept deep neural nets back. Gradient optimisation gets stuck in local minima, and it will always get stuck in local minima, and therefore always be dumb as bricks. Which is evident in the way deep neural nets overfit and are incapable of extrapolating outside their training datasets.
- darkmighty 7y ago
  > Gradient optimisation gets stuck in local minima, and it will always get stuck in local minima, and therefore always be dumb as bricks. Which is evident in the way deep neural nets overfit and are incapable of extrapolating outside their training datasets. This seems extremely harsh, given the vast successes of deep neural nets calling them 'dumb as bricks' (there are too many examples of extrapolation outside datasets to count[1]). They have proven generalization capability when care is taken against over fitting (almost any model has this ability). Also there are results showing getting stuck in local minima is unlikely in highly-dimensional parameter spaces (the curvature in a large number of directions needs to coincide), and in any case rarely you're seeking the global minimum because of said over-fitting issues. [1] It should be self-evident because they would hardly be of any use if unable to extrapolate at all. See GANs (https://www.thispersondoesnotexist.com/ https://www.thispersondoesnotexist.com/), AlphaGo (https://en.wikipedia.org/wiki/AlphaGo https://en.wikipedia.org/wiki/AlphaGo), etc.

YeGoblynQueenne 7y ago

>> I wouldn't. Traditional NNs are widely called funciton approximators, or function induction. That's because they're not Turing-complete, and in this case don't even have memory. This makes them decidedly not programs, just functions. But what the article describes is not function approximation anymore. Their system doesn't optimise a set of parameters. The search for an optimal set of parameters has been replaced entirely with a search for an optimal architecture with a single, shared parameter. Note also that you don't need something to be Turing-complete for it to be a program. For instance, a regular automaton is a program, but it's not Turing complete. Turing completeness makes something, well, a Universal Turing Machine, which can compute any program. But a program is just a set of instructions.

darkmighty 7y ago
> Note also that you don't need something to be Turing-complete for it to be a program. For instance, a regular automaton is a program, but it's not Turing complete. Turing completeness makes something, well, a Universal Turing Machine, which can compute any program. But a program is just a set of instructions. A regular automaton is a program (and a function is a program), but all programs cannot be expressed as finite (regular) automatons (FAs). So FAs are a subset of programs. If we equate programs with mathematical algorithms, in general they really need the unlimited memory aspect (or at least the capability of abstracting memory, which in practice is always finite of course). To make things clear, an example: a fixed function (or FA) cannot sort a list of numbers of variable size. You can train your function to sort any K numbers, which are the input variables. But because it has no memory, you cannot input variables sequentially (in the FA case you cannot input arbitrarily many variables). You've essentially created a sorting network[1]. Not only that, but for each input growth you need to re-train your architecture. The nice thing about program inference is that it hopefully captures the fundamental algorithm behind a program, which generalizes to arbitrary sizes. It's not that arbitrary sizes are necessary in practice (again computers are always bounded), it's that this abstraction/generalization is extremely useful, saving data and allowing large (arbitrary) variation in input. [1] https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network > a Universal Turing Machine, which can compute any program I feel there's a bit of confusion here. Turing Machines themselves can compute any program (i.e. you can represent any program as a TM) -- that follows essentially from the definition of algorithm (a set of well defined steps given unlimited paper); again languages accepted by FAs are a restricted subset of TMs (the former accepts a regular language while the latter recursively enumerable languages). There are special Turing Machines that simulate arbitrary Turing Machines -- those are called Universal Turing machines. It's a desirable characteristic of any computer, of course (the ability to input arbitrary programs). We refer to program description languages that can describe any Turing Machine as Turing-complete. You could make a Universal Turing machine that accepts this kind of language directly or you could in principle just build a Turing machine that executes the given algorithm (for example using a gate array/FPGA to encode the state automaton, plus some large memory for the tape).
- YeGoblynQueenne 7y ago
  Yes, sloppy definition of Turing completenes on my part. I apologise unrservedly. But, I still don't understand your objection. You agree that a regular automaton is a program, and that it's not Turing complete. So a program does not need to be Turing complete. I didn't say, nor do I think, that the algorithm described in this article is Turing complete. I think it perfoms program induction. That's as far as I went. I still don't see where Turing completeness comes into it.

YeGoblynQueenne 7y ago

[sorry- splitting this off 'cause it's getting a bit large and to make the whole thing easier to read] >> What seems novel here is how significant architecture alone is (I wouldn't guess it being this powerful), and this possibly has implications on the connection with the human brain -- in which my vague impression is that connections themselves are much more tuned than weights; also possibly giving greater emphasis on architecture training. You are surprised by how significant architecture is. I am not surprised at all. I think it's been very clear for a while now that the success of deep neural networks is entirely due to their architectures that are fine-tuned to specific tasks. On the one hand, it's obvious that this is the case if you look at the two major successes of deep learning: CNNs for vision and LSTMs (and variants) for sequence learning. Both are extremely precise, extremely intricate architectures with an intense focus one one kind of task, and that kind of task, alone. On the other hand, the vast majority of neural net publications are specifically about new architectures, or, rather, tweaks to existing architectures. In fact, in my boldest moments I'd go as far as to suggest that weight training with gradient optimisation has kept deep neural nets back. Gradient optimisation gets stuck in local minima, and it will always get stuck in local minima, and therefore always be dumb as bricks. Which is evident in the way deep neural nets overfit and are incapable of extrapolating outside their training datasets.

darkmighty 7y ago
> Gradient optimisation gets stuck in local minima, and it will always get stuck in local minima, and therefore always be dumb as bricks. Which is evident in the way deep neural nets overfit and are incapable of extrapolating outside their training datasets. This seems extremely harsh, given the vast successes of deep neural nets calling them 'dumb as bricks' (there are too many examples of extrapolation outside datasets to count[1]). They have proven generalization capability when care is taken against over fitting (almost any model has this ability). Also there are results showing getting stuck in local minima is unlikely in highly-dimensional parameter spaces (the curvature in a large number of directions needs to coincide), and in any case rarely you're seeking the global minimum because of said over-fitting issues. [1] It should be self-evident because they would hardly be of any use if unable to extrapolate at all. See GANs (https://www.thispersondoesnotexist.com/ https://www.thispersondoesnotexist.com/), AlphaGo (https://en.wikipedia.org/wiki/AlphaGo https://en.wikipedia.org/wiki/AlphaGo), etc.