7 ms·

Neural Networks and the Chomsky Hierarchy

164 points by cma 4y ago

ggm 4y ago
I can't say it's totally surprising you need a machine (store, stack, instructions) to handle higher language issues that GPT targets Not to crit the paper: formally stating things is good. But it feels like the outcome was highly predictable. Inferences being drawn from the language model where the language is a real world language and not a restricted subset were always going to hit up against the complexities of real languages. And I'd be mindful that conforming to Chomsky Hierarchies says nothing about the nature of universal language models, or {{GPT or turing machines} and emergent intelligence}. Which again, isn't to lay things on the authors. People have a habit (here, in general) of taking things out of context. I kind of feel thats about it: If the analysis of the classifier architecture shows constructs which map to a machine capable of being the higher Chomsky class, then its likely that reflects the complexity of the languages being analysed.
- cma 4y ago
  Matching braces is part of written natural language and would be beyond the power of regular languages wouldn't it? I thought there was something special with transformers allowing to learn that at least within its context window size in a generalizable way. It also sounds like from the paper transformers are formally proven to capable of it, but the training can't get the weights to make it capable of it, even though there should exist such weights, if I am reading them right.
  - ben_w 4y ago
    I've seen humans mess up matching braces. I've even been that human already this year, only finding out because the compiler told me.
    - randorand0 4y ago
      this may well be the only real skill of programmers who learned C style syntaxes, andor LISPs on the ohter hand, thinking with the parenthesis takes language up to the level of functional-thinking. computable stuff is all about substitution of all things inside a parenthesis for a single thing. and this is the essence of all classic computation
    - cma 4y ago
      But we still generalize it to bigger and bigger without seeing matching brace problems of all sizes we can handle. In the paper I don't think they are looking for perfect, but they show which models can't seem to learn significantly beyond the size of examples they explicitly saw.
      - ben_w 4y ago
        The {specific (number I (messed up was a depth of 3)}. I missed it because it was spaced over a few lines and I was tired.
        cma 4y ago
        But not because you only trained up to examples of two.
        ben_w 4y ago
        I don't know what point you're making, GPT-3 almost certainly has training examples for greater depth. Pattern recognition can fail. Mine does, GPT's does. I count further than I subitize, but from experience my mind may wander and I may lose track after 700 of a thing even if there's literally nothing else to focus on. But I still didn't notice an error at depth 3.
        cma 4y ago
        It seems transformers don't generalize in this class and neural turing machines and neural stack machines do. You get the general rule (in linguistics known as competency) but can't flawlessly do it (performance). Transformers can't seem to get competence here. https://en.m.wikipedia.org/wiki/Linguistic_competence https://en.m.wikipedia.org/wiki/Linguistic_competence
        ben_w 4y ago
        Ah, gotcha. Thanks for the clear explanation and the link! :)
  - charcircuit 4y ago
    If there is a finite input it is regular.
    - smadge 4y ago
      As in you construct a FSM that can recognize all strings of a context free language less than a certain length?
      - deleted 4y ago
        [deleted]
    - Kranar 4y ago
      You might mean something like if you restrict the set of all valid inputs to N characters then the language is regular, but that's a much stronger condition than requiring the input to be finite. Furthermore, such a restriction makes the language non-recursive; it's effectively a trivial language. In standard automata theory, all inputs to automatons are finite.
      - charcircuit 4y ago
        Yes, I was hoping people would understand that from the context.
    - cma 4y ago
      The paper covers that. They only test to a finite size, but the models that fail can't generalize significantly beyond the size of explicit examples they were trained on. Formally transformers should be capable of modeling it with the right weights, but they show good evidence those weights can't be learned with gradient descent. Whereas a neural turing machine or stack machine can learn them with gradient descent.
- ashupadhi01 4y ago
  Can you tell some resources which helped you gain a sound understanding of this domain ?
  - ggm 4y ago
    No, because I regard my understanding as unsound.
    - randorand0 4y ago
      even better, please share. I'm thinkin if your understanding were sound I would have to listen to it, but I rather read about these kinds of things, so whis is why I say unsound is best on the other hand, putting things down into writing is difficult. So while you diminish this paper's accomplishments, you couldn't have done it yourself in spite of easily understanding it.
KhoomeiK 4y ago
ICLR review discussion here: https://openreview.net/forum?id=WbxHAzkeQcn https://openreview.net/forum?id=WbxHAzkeQcn Somewhat relevant work: https://aclanthology.org/2020.emnlp-main.731/ https://aclanthology.org/2020.emnlp-main.731/
albertzeyer 4y ago
The Chomsky hierarchy is all about the type of memory. First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have finite memory, it is always only just as powerful as a FSA. Adding one (infinite) stack will give you pushdown automata complexity, and adding two (or more) (infinite) stacks will get you to Turing machines. Consider that a float in hardware (f32, bf16, or whatever you like), but also in reality (think of the neuronal spike voltage) is not infinite in memory but finite. This is different from mathematics, where you can store infinite memory in a real number. Note that there is an infamous paper, "On the computational power of neural nets", Siegelmann & Sonntag, 1992, which states that RNNs are Turing complete. But this construction assumes that you can store infinite memory in a single neuron activity, which is never true in practice. In practice, a RNN or LSTM has finite memory. However, in practice, also any computer has finite memory. Also the human brain has finite memory. So, it follows, you always only have the complexity of FSAs. But is this right? Wouldn't the intuition say sth different? Maybe the Chomsky hierarchy is not really so relevant? Or the question is somewhat ill posed. What would make a computer Turing complete? You need infinite memory. So, you need to abstract away from a particular computer towards the concept of a computer with infinite memory. The official C language definition calls this an "abstract machine". This abstract machine is Turing complete. How can you apply this to neural networks? How to define an abstract neural network with some explicit memory component, which can grow to infinite sizes? You get to memory-augmented models like the differential neural computer (extended from the neural Turing machine). In theory, you can think of abstract variants of those models with infinite memory, and then you can think about the Chomsky hierarchy. In practice, the memory is always finite though. What they do in the paper is to focus more on the Chomsky hierarchy in practice, i.e. applied to some actual benchmarks. When you limit the length of the input problems, there is some maximum amount of memory which should be sufficient to solve them. Depending on the structure of the neural model, it gives you a clue to what compute complexity it mostly corresponds to when you test it. I have written down some own thoughts on this here: https://stackoverflow.com/questions/2990277/how-useful-is-turing-completeness-are-neural-nets-turing-complete https://stackoverflow.com/questions/2990277/how-useful-is-tu...
- guerrilla 4y ago
YeGoblynQueenne 4y ago
Amazing paper, thanks for posting. That's how you probe the abilities of neural nets! Empirical evaluation done in the context of a theoretical framework. Not just poking models to see what happens [1]. Huh. No wonder Marcus Hutter's name is in the list of authors. _____________ [1] Although poking stuff to see what happens is the root of all science, don't get me wrong.
- wnkrshm 4y ago
  It's often reduction that furthers understanding (e.g. in physics, to try and reduce phenomena to a small set of assumptions/laws).
  - YeGoblynQueenne 4y ago
    Absolutely, but we only understand things in the context of what we already know, and we build up our understanding of new things from that. Besides, a theory can also guide your experiments. For example, in physics, you wouldn't try to calculate the mass of all strawberry icecream in the world because physics doesn't, as a matter of course, consider the properties of strawberry icecream as particularly special or interesting. They're not a concept of physics, that is.
jll29 4y ago
The Chomsky hierarchy is beautiful, and a fundamental result in formal languages and automata theory and complexity that has far-reaching implications for computer science (from compiler design to computability). What I learned only in a theoretical/formal linguistics class is that there exist other hierarchies of languages and associated machines (e.g. A, B, C1, C2, C3 languages) entirely orthogonal to the Chomsky hierarchy's classes, i.e. recursively enumerable, context-sensitive, context-free, and regular classes. The way rules may look like and how they get applied, induce alternative universes of (hierarchies of) formal languages and their automata. Neural networks have come a long way from the Perceptron's inability to compute XOR to the OP's paper. It would be interesting to push that work further so as to include alternative hierarchies.
- nabla9 4y ago
  >is that there exist other hierarchies of languages and associated machines Please explain.
  - kelseyfrog 4y ago
    I believe parent is referring to the LA-grammar hierarchy[1] of formal languages. 1. https://www.lagrammar.net/monographs/1999/slides/pdf/chapter-11.pdf https://www.lagrammar.net/monographs/1999/slides/pdf/chapter... (last slide)
- jameshart 4y ago
  This is a bit of a layman's outsider perspective, so I'd welcome having my perceptions corrected by people who are more up on the way formal grammars are employed in the ML community. To my mind, though, the Chomsky-ish ML focus on 'grammars' always seemed to me to miss some of the power of language. Like, the idea that there is something profound in the fact that "Colorless green ideas sleep furiously" is a grammatical fragment that is semantically meaningless seems to me to miss the fact that it's still a meaningful utterance in a language, even if what it denotes is nonsensical. As is proven by the fact that Chomsky used it in his work on the subject! Its meaninglessness is meaningful - you can use it to illustrate a point. The same is true of ungrammatical sentences, too. Not only do actual humans make ungrammatical utterances all the time, but for example if you are trying to teach someone a lamguage, you might show them an ungrammatical sentence by way of an example of what not to do. So any language that is capable of talking about its own grammar has to admit sentences that are ungrammatical in that language, precisely so you can talk about them! Human language understanding isn't 'parsing', we don't reject utterances because we can't lex the tokens or construct an unambiguous syntax tree or extract semantic meaning. Chomskyish ML researchers seem focused on the problem of making systems that produce grammatical utterances. But I'm honestly more impressed with, for example, GPT's ability to handle and produce the ungrammatical and semantically nonsensical using the same system that it uses to work with grammatical and sensical input and output. That seems much more human-like to me. That a particular neural architecture is incapable of 'rejecting' certain ungrammatical structures doesn't feel like it matters, so long as the architecture is capable of recognizing a more fuzzy analogue degree of 'gramatticalness' of an utterance.
optimalsolver 4y ago
The vindication of Gary Marcus?
theGnuMe 4y ago
I figured this was true. DNNs are differentiable regex basically.
machiaweliczny 4y ago
Does it matter if you can outsource computation to Wolfram Alpha or Python interpreter? I am interested if Transformers can (learn to) reason. They for sure have good statistical model of world.
waynecochran 4y ago
I like the idea of formalizing the computing power of NN by mimicking what we have done with automata theory, but I didn't quite grok how a NN would make use of an "external memory structure." we showed that models interacting with an external memory structure, such as a stack or a finite tape, can climb the Chomsky hierarchy I think of a trained NN as containing a set of weights which control the various perceptrons, convolution kernels, etc... as input data passes thru the network. Exactly how does an external memory source (like a stack or Turing tape) come in to play? Are perceptrons augmented with the ability to record information that changes their behavior? What is a simple example of a NN that makes use of an external memory structure?
- halflings 4y ago
  Examples of such architectures: RETRO (Retrieval-Enhanced Transformer) https://arxiv.org/abs/2112.04426 https://arxiv.org/abs/2112.04426 And much older (2016): Differential Neural Network https://www.deepmind.com/blog/differentiable-neural-computers https://www.deepmind.com/blog/differentiable-neural-computer...
  - lossolo 4y ago
    RETRO has external source of data but is something entirely different to what is discussed in the paper. In simplistic terms, in RETRO architecture you store embeddings in an external database and then use kNN search. It is not an end-to-end model capable of things like those with stack or tape memory (what OP asked about), retrieval models are only good for limited Q/A atm.
- jsenn 4y ago
  Here's a paper that shows how to augment a recurrent NN with a stack: http://arxiv.org/abs/1503.01007 http://arxiv.org/abs/1503.01007. I'm not an expert, so some or all of this may be wrong, but my understanding of how it works is this. You have a stack memory, which is just a list of numbers (or maybe a list of N-dimensional vectors). You add the contents of the stack at time t-1 to the input of the network at time t. The hidden layer contains a special number that controls whether to push or pop from the stack (or leave it alone). The values in the stack are determined from the values in the hidden layer at the time they were pushed and the special push/pop control parameter. The new value of the stack is passed into the network on the next time step, and so on. The tricky thing is that the stack operations have to be differentiable, otherwise there's no way to optimize the push/pop control and the set of weights that determines how to turn the hidden layer into a stack value. So the special control variable in the hidden layer is a continuous value that controls "how much" push vs. pop to do. The value of the top of the stack is a weighted average of the values in the hidden layer and the current value on the top of the stack. So, if the push vs. pop knob is turned all the way toward pop, then the value of the stack will be whatever the second-from-the-top value is. If it's turned all the way toward push, then the value at the top will be a weighted average of the values in the hidden layer. If it's 50% push and 50% pop, then the value at the top of the stack will be 0.5 * <hidden layer value> + 0.5 * <second-from-top value>, and so on. It's hard to think about what a half push, half pop would actually mean (at least for me), but it apparently works. As a sibling commenter wrote, there are fancier architectures that provide a full differentiable RAM or other types of gadgets for the network to control.
gdelt 4y ago
Author speaking. As many of you pointed out, memory is always finite in practice. The Chomsky hierarchy, however, only makes sense in the infinite memory case, since anything with finite memory will end up in the lowest category, i.e. finite state automatons (recognizing regular languages). So why does it matter ? Because of generalisation, and deep within it, compression. I wrote this paper because I wanted to understand what it really means to generalize. Yes you can reverse strings by creating a massive lookup table of all strings and their associated reverse. You can also do it by hard coding it for all lengths between say 1 and 500 (for length n, take the first token and swap it with the nth, then the second token and swap it with the (n-1)th etc). Both solutions would work in practice. But is it really what we mean by 'reversing a string'? Is it what we want an intelligent system to do? The answer is clearly no. What we want is to do the same thing but using a simple, compressed algorithm (in the reverse string case, push on a stack, then pop from it: near and simple). That's what we mean in general by 'this network generalises well': it has found the most compressed algorithm reproducing the data we fed it. That's really what the Chomsky hierarchy is about: it tells you how to get systems that generalise better. And that's basically what AI is all about.

164 points by cma 4y ago

ggm 4y ago

I can't say it's totally surprising you need a machine (store, stack, instructions) to handle higher language issues that GPT targets Not to crit the paper: formally stating things is good. But it feels like the outcome was highly predictable. Inferences being drawn from the language model where the language is a real world language and not a restricted subset were always going to hit up against the complexities of real languages. And I'd be mindful that conforming to Chomsky Hierarchies says nothing about the nature of universal language models, or {{GPT or turing machines} and emergent intelligence}. Which again, isn't to lay things on the authors. People have a habit (here, in general) of taking things out of context. I kind of feel thats about it: If the analysis of the classifier architecture shows constructs which map to a machine capable of being the higher Chomsky class, then its likely that reflects the complexity of the languages being analysed.

cma 4y ago
Matching braces is part of written natural language and would be beyond the power of regular languages wouldn't it? I thought there was something special with transformers allowing to learn that at least within its context window size in a generalizable way. It also sounds like from the paper transformers are formally proven to capable of it, but the training can't get the weights to make it capable of it, even though there should exist such weights, if I am reading them right.
- ben_w 4y ago
  I've seen humans mess up matching braces. I've even been that human already this year, only finding out because the compiler told me.
  - randorand0 4y ago
    this may well be the only real skill of programmers who learned C style syntaxes, andor LISPs on the ohter hand, thinking with the parenthesis takes language up to the level of functional-thinking. computable stuff is all about substitution of all things inside a parenthesis for a single thing. and this is the essence of all classic computation
  - cma 4y ago
    But we still generalize it to bigger and bigger without seeing matching brace problems of all sizes we can handle. In the paper I don't think they are looking for perfect, but they show which models can't seem to learn significantly beyond the size of examples they explicitly saw.
    - ben_w 4y ago
      The {specific (number I (messed up was a depth of 3)}. I missed it because it was spaced over a few lines and I was tired.
      - cma 4y ago
        But not because you only trained up to examples of two.
        ben_w 4y ago
        I don't know what point you're making, GPT-3 almost certainly has training examples for greater depth. Pattern recognition can fail. Mine does, GPT's does. I count further than I subitize, but from experience my mind may wander and I may lose track after 700 of a thing even if there's literally nothing else to focus on. But I still didn't notice an error at depth 3.
        cma 4y ago
        It seems transformers don't generalize in this class and neural turing machines and neural stack machines do. You get the general rule (in linguistics known as competency) but can't flawlessly do it (performance). Transformers can't seem to get competence here. https://en.m.wikipedia.org/wiki/Linguistic_competence https://en.m.wikipedia.org/wiki/Linguistic_competence
        ben_w 4y ago
        Ah, gotcha. Thanks for the clear explanation and the link! :)
- charcircuit 4y ago
  If there is a finite input it is regular.
  - smadge 4y ago
    As in you construct a FSM that can recognize all strings of a context free language less than a certain length?
    - deleted 4y ago
      [deleted]
  - Kranar 4y ago
    You might mean something like if you restrict the set of all valid inputs to N characters then the language is regular, but that's a much stronger condition than requiring the input to be finite. Furthermore, such a restriction makes the language non-recursive; it's effectively a trivial language. In standard automata theory, all inputs to automatons are finite.
    - charcircuit 4y ago
      Yes, I was hoping people would understand that from the context.
  - cma 4y ago
    The paper covers that. They only test to a finite size, but the models that fail can't generalize significantly beyond the size of explicit examples they were trained on. Formally transformers should be capable of modeling it with the right weights, but they show good evidence those weights can't be learned with gradient descent. Whereas a neural turing machine or stack machine can learn them with gradient descent.
ashupadhi01 4y ago
Can you tell some resources which helped you gain a sound understanding of this domain ?
- ggm 4y ago
  No, because I regard my understanding as unsound.
  - randorand0 4y ago
    even better, please share. I'm thinkin if your understanding were sound I would have to listen to it, but I rather read about these kinds of things, so whis is why I say unsound is best on the other hand, putting things down into writing is difficult. So while you diminish this paper's accomplishments, you couldn't have done it yourself in spite of easily understanding it.

KhoomeiK 4y ago

ICLR review discussion here: https://openreview.net/forum?id=WbxHAzkeQcn https://openreview.net/forum?id=WbxHAzkeQcn Somewhat relevant work: https://aclanthology.org/2020.emnlp-main.731/ https://aclanthology.org/2020.emnlp-main.731/

albertzeyer 4y ago

The Chomsky hierarchy is all about the type of memory. First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have finite memory, it is always only just as powerful as a FSA. Adding one (infinite) stack will give you pushdown automata complexity, and adding two (or more) (infinite) stacks will get you to Turing machines. Consider that a float in hardware (f32, bf16, or whatever you like), but also in reality (think of the neuronal spike voltage) is not infinite in memory but finite. This is different from mathematics, where you can store infinite memory in a real number. Note that there is an infamous paper, "On the computational power of neural nets", Siegelmann & Sonntag, 1992, which states that RNNs are Turing complete. But this construction assumes that you can store infinite memory in a single neuron activity, which is never true in practice. In practice, a RNN or LSTM has finite memory. However, in practice, also any computer has finite memory. Also the human brain has finite memory. So, it follows, you always only have the complexity of FSAs. But is this right? Wouldn't the intuition say sth different? Maybe the Chomsky hierarchy is not really so relevant? Or the question is somewhat ill posed. What would make a computer Turing complete? You need infinite memory. So, you need to abstract away from a particular computer towards the concept of a computer with infinite memory. The official C language definition calls this an "abstract machine". This abstract machine is Turing complete. How can you apply this to neural networks? How to define an abstract neural network with some explicit memory component, which can grow to infinite sizes? You get to memory-augmented models like the differential neural computer (extended from the neural Turing machine). In theory, you can think of abstract variants of those models with infinite memory, and then you can think about the Chomsky hierarchy. In practice, the memory is always finite though. What they do in the paper is to focus more on the Chomsky hierarchy in practice, i.e. applied to some actual benchmarks. When you limit the length of the input problems, there is some maximum amount of memory which should be sufficient to solve them. Depending on the structure of the neural model, it gives you a clue to what compute complexity it mostly corresponds to when you test it. I have written down some own thoughts on this here: https://stackoverflow.com/questions/2990277/how-useful-is-turing-completeness-are-neural-nets-turing-complete https://stackoverflow.com/questions/2990277/how-useful-is-tu...

guerrilla 4y ago

YeGoblynQueenne 4y ago

Amazing paper, thanks for posting. That's how you probe the abilities of neural nets! Empirical evaluation done in the context of a theoretical framework. Not just poking models to see what happens [1]. Huh. No wonder Marcus Hutter's name is in the list of authors. _____________ [1] Although poking stuff to see what happens is the root of all science, don't get me wrong.

wnkrshm 4y ago
It's often reduction that furthers understanding (e.g. in physics, to try and reduce phenomena to a small set of assumptions/laws).
- YeGoblynQueenne 4y ago
  Absolutely, but we only understand things in the context of what we already know, and we build up our understanding of new things from that. Besides, a theory can also guide your experiments. For example, in physics, you wouldn't try to calculate the mass of all strawberry icecream in the world because physics doesn't, as a matter of course, consider the properties of strawberry icecream as particularly special or interesting. They're not a concept of physics, that is.

jll29 4y ago

The Chomsky hierarchy is beautiful, and a fundamental result in formal languages and automata theory and complexity that has far-reaching implications for computer science (from compiler design to computability). What I learned only in a theoretical/formal linguistics class is that there exist other hierarchies of languages and associated machines (e.g. A, B, C1, C2, C3 languages) entirely orthogonal to the Chomsky hierarchy's classes, i.e. recursively enumerable, context-sensitive, context-free, and regular classes. The way rules may look like and how they get applied, induce alternative universes of (hierarchies of) formal languages and their automata. Neural networks have come a long way from the Perceptron's inability to compute XOR to the OP's paper. It would be interesting to push that work further so as to include alternative hierarchies.

nabla9 4y ago
>is that there exist other hierarchies of languages and associated machines Please explain.
- kelseyfrog 4y ago
  I believe parent is referring to the LA-grammar hierarchy[1] of formal languages. 1. https://www.lagrammar.net/monographs/1999/slides/pdf/chapter-11.pdf https://www.lagrammar.net/monographs/1999/slides/pdf/chapter... (last slide)
jameshart 4y ago
This is a bit of a layman's outsider perspective, so I'd welcome having my perceptions corrected by people who are more up on the way formal grammars are employed in the ML community. To my mind, though, the Chomsky-ish ML focus on 'grammars' always seemed to me to miss some of the power of language. Like, the idea that there is something profound in the fact that "Colorless green ideas sleep furiously" is a grammatical fragment that is semantically meaningless seems to me to miss the fact that it's still a meaningful utterance in a language, even if what it denotes is nonsensical. As is proven by the fact that Chomsky used it in his work on the subject! Its meaninglessness is meaningful - you can use it to illustrate a point. The same is true of ungrammatical sentences, too. Not only do actual humans make ungrammatical utterances all the time, but for example if you are trying to teach someone a lamguage, you might show them an ungrammatical sentence by way of an example of what not to do. So any language that is capable of talking about its own grammar has to admit sentences that are ungrammatical in that language, precisely so you can talk about them! Human language understanding isn't 'parsing', we don't reject utterances because we can't lex the tokens or construct an unambiguous syntax tree or extract semantic meaning. Chomskyish ML researchers seem focused on the problem of making systems that produce grammatical utterances. But I'm honestly more impressed with, for example, GPT's ability to handle and produce the ungrammatical and semantically nonsensical using the same system that it uses to work with grammatical and sensical input and output. That seems much more human-like to me. That a particular neural architecture is incapable of 'rejecting' certain ungrammatical structures doesn't feel like it matters, so long as the architecture is capable of recognizing a more fuzzy analogue degree of 'gramatticalness' of an utterance.

optimalsolver 4y ago

The vindication of Gary Marcus?

theGnuMe 4y ago

I figured this was true. DNNs are differentiable regex basically.

machiaweliczny 4y ago

Does it matter if you can outsource computation to Wolfram Alpha or Python interpreter? I am interested if Transformers can (learn to) reason. They for sure have good statistical model of world.

waynecochran 4y ago

I like the idea of formalizing the computing power of NN by mimicking what we have done with automata theory, but I didn't quite grok how a NN would make use of an "external memory structure." we showed that models interacting with an external memory structure, such as a stack or a finite tape, can climb the Chomsky hierarchy I think of a trained NN as containing a set of weights which control the various perceptrons, convolution kernels, etc... as input data passes thru the network. Exactly how does an external memory source (like a stack or Turing tape) come in to play? Are perceptrons augmented with the ability to record information that changes their behavior? What is a simple example of a NN that makes use of an external memory structure?

halflings 4y ago
Examples of such architectures: RETRO (Retrieval-Enhanced Transformer) https://arxiv.org/abs/2112.04426 https://arxiv.org/abs/2112.04426 And much older (2016): Differential Neural Network https://www.deepmind.com/blog/differentiable-neural-computers https://www.deepmind.com/blog/differentiable-neural-computer...
- lossolo 4y ago
  RETRO has external source of data but is something entirely different to what is discussed in the paper. In simplistic terms, in RETRO architecture you store embeddings in an external database and then use kNN search. It is not an end-to-end model capable of things like those with stack or tape memory (what OP asked about), retrieval models are only good for limited Q/A atm.
jsenn 4y ago
Here's a paper that shows how to augment a recurrent NN with a stack: http://arxiv.org/abs/1503.01007 http://arxiv.org/abs/1503.01007. I'm not an expert, so some or all of this may be wrong, but my understanding of how it works is this. You have a stack memory, which is just a list of numbers (or maybe a list of N-dimensional vectors). You add the contents of the stack at time t-1 to the input of the network at time t. The hidden layer contains a special number that controls whether to push or pop from the stack (or leave it alone). The values in the stack are determined from the values in the hidden layer at the time they were pushed and the special push/pop control parameter. The new value of the stack is passed into the network on the next time step, and so on. The tricky thing is that the stack operations have to be differentiable, otherwise there's no way to optimize the push/pop control and the set of weights that determines how to turn the hidden layer into a stack value. So the special control variable in the hidden layer is a continuous value that controls "how much" push vs. pop to do. The value of the top of the stack is a weighted average of the values in the hidden layer and the current value on the top of the stack. So, if the push vs. pop knob is turned all the way toward pop, then the value of the stack will be whatever the second-from-the-top value is. If it's turned all the way toward push, then the value at the top will be a weighted average of the values in the hidden layer. If it's 50% push and 50% pop, then the value at the top of the stack will be 0.5 * <hidden layer value> + 0.5 * <second-from-top value>, and so on. It's hard to think about what a half push, half pop would actually mean (at least for me), but it apparently works. As a sibling commenter wrote, there are fancier architectures that provide a full differentiable RAM or other types of gadgets for the network to control.

gdelt 4y ago

Author speaking. As many of you pointed out, memory is always finite in practice. The Chomsky hierarchy, however, only makes sense in the infinite memory case, since anything with finite memory will end up in the lowest category, i.e. finite state automatons (recognizing regular languages). So why does it matter ? Because of generalisation, and deep within it, compression. I wrote this paper because I wanted to understand what it really means to generalize. Yes you can reverse strings by creating a massive lookup table of all strings and their associated reverse. You can also do it by hard coding it for all lengths between say 1 and 500 (for length n, take the first token and swap it with the nth, then the second token and swap it with the (n-1)th etc). Both solutions would work in practice. But is it really what we mean by 'reversing a string'? Is it what we want an intelligent system to do? The answer is clearly no. What we want is to do the same thing but using a simple, compressed algorithm (in the reverse string case, push on a stack, then pop from it: near and simple). That's what we mean in general by 'this network generalises well': it has found the most compressed algorithm reproducing the data we fed it. That's really what the Chomsky hierarchy is about: it tells you how to get systems that generalise better. And that's basically what AI is all about.