7 ms·

Gated Linear Networks

150 points by asparagui 6y ago

The_rationalist 6y ago
Where could this shine? Could it beat SOTA on Nlp tasks?
Immortal333 6y ago
"We show that this architecture gives rise to universal learning capabilities in the limit, with effective model capacity increasing as a function of network size in a manner comparable with deep ReLU networks." What exactly this statement means?
- T-A 6y ago
  Presumably (haven't read the paper yet) that their network provably becomes a universal function approximator in the limit of infinite size. Reading... actually the proof seems to be in https://arxiv.org/abs/1712.01897 https://arxiv.org/abs/1712.01897
- jawarner 6y ago
  As the network size increases, it can learn more complex functions. When the network gets bigger and bigger, it gets closer to being able to learn any arbitrary function.
- fxtentacle 6y ago
  They mean that if you add parameters, the learning capability of their approach grows by a similar amount as if you would add the same number of parameters to a conv+ReLu network (the standard approach). That "universal" is a weird claim in my opinion, but they mean that with enough parameters, this architecture can learn everything.
  - Immortal333 6y ago
    I was able to get the second part of the statement. but I haven't seen the use of "in limit" in a statement like this. Yes, the universal approximation is a strong claim. NN has been proven to have universal approximation theoretically.
    - fxtentacle 6y ago
      "in limit" here means as you approach the edge case of having an unlimited number of parameters.
    - friendly_aixi 6y ago
      The result here is stronger, in the sense that typical NN universality results are statements with respect to just capacity (and not how you optimise them). Here, the result holds with respect to both capacity + a choice of suitable no regret online convex optimisation algorithm (e.g. online gradient descent). Of course, this is just one desirable property of a general purpose learning algorithm.
      - currymj 6y ago
        Do you know of any other kinds of universal function approximators that also have a good regret bound like this, or is yours the first one? global convergence to any arbitrarily weird function at rate O(sqrt(T)) seems amazing, almost too good to be true, and I’m wondering what the catch is. Maybe it’s just a moderately nice property but not extraordinary? Maybe there are some horrible constants hiding in there?
        friendly_aixi 6y ago
        1) It's definitely not the first. Other methods have universal guarantees of some form or other with well quantified rates of convergence, e.g. k-NN would be the best known example. 2) There are some restrictions on the class of density functions it can model, so arbitrarily weird is a bit strong, but the model class is very general. 3) The weights needed to model any function in this class although finite, can be arbitrarily large. The regret of a single neuron has a dependence on the diameter of the convex set your weights reside in, so there is a nasty constant of sorts in there, and this will also carry over when you analyse the regret of a complete network. With such a general statement, it's unavoidable sadly. 4) The universality result on its own is just a nice property. See it as the first stepping stone to a more meaningful analysis. What you really want is for the model class to grow as you add more neurons, using weights within a realistic range, and that the method performs well in practice on some problems people care about -- we provide empirical evidence that the capacity grows on par with deep relu networks with our capacity experiments, and show a bunch of results where the method works, but we don't have a theoretical characterisation of the class of density functions it can model well (i.e. if the function has some nice structural property, then a network of reasonable size is guaranteed to learn a good approximation quickly). Such a result would be extraordinary in my eyes. Because the network is composed of simple and well understood building blocks, I am optimistic that such an analysis will be possible in the future.
- janosett 6y ago
  > "We show that this architecture" They are demonstrating a new technique, Gated Linear Networks. > gives rise to universal learning capabilities in the limit they claim to show that with an unbounded amount of time and memory (network size / # params) this architecture can be used to learn/approximate any function > with effective model capacity increasing as a function of network size Model capacity here refers to the ability to memorize a mapping between inputs and outputs. They show that a network with more layers/weights will "memorize" more. > in a manner comparable with deep ReLU networks "Deep ReLU networks" are referring to commonly used modern deep neural network architectures. ReLU is a popular activation function: https://en.wikipedia.org/wiki/Rectifier_(neural_networks) https://en.wikipedia.org/wiki/Rectifier_(neural_networks)
fxtentacle 6y ago
That is an amazing paper, a great result and new neutral architectures are long overdue. But I don't believe that this has any significance in practice. GPU memory is the limiting factor for most current AI approaches. And that's where the typical convolutional architectures shine, because they effectively compress the input data, then work on the compressed representation, then decompress the results. With gated linear networks, I'm required to always work on the full input data, because it's a one step prediction. As the result, I'll run out of GPU memory before I reach a learning capacity that is comparable to conv nets.
- BrokrnAlgorithm 6y ago
  What about findings w. R. T. Online learning? I find continuous learning quality of algorithms to be a topic which often seems to be more of a side-concern, although it carries a lot of relevance in applied settings.
  - fxtentacle 6y ago
    I believe that to be a red herring. Their approach cannot learn any features that provide a lower-dimensional approximation of the input data. As the result, there is no intermediate representation which could change and thereby negatively affect previously learned classifiers. But if I train 10 independent traditional networks, I also won't have newly learned data affect old performance. So in effect they give up the possibility to do transfer learning in exchange for avoiding the disadvantages of transfer learning. But that's a bad tradeoff. With their approach you always train from scratch, which brings with it the need for huge training data sets. So I can train a bird classifier on the traditional architecture with 500 labeled images and a pretrained resnet. Our I use a million bird images and this approach.
    - friendly_aixi 6y ago
      1) Indeed, GLNs don't learn features... but I would claim they do learn some notion of an intermediate representation, it's just different from the DL mainstream -- in particular its closely related to the inverse Radon transform in medical imaging. 2) Inputs which are similar in terms of cosine similarity will map to similar (data dependent) products of weight matrices, and thus behave similarly, which of course can affect performance in both good and bad ways. With the results we show on permuted MNIST, its well... just not particularly likely that they will interfere. This is a good thing -- why should completely different data distributions interfere with one another? The point is the method is resiliant to catastrophic forgetting when the cosine similarity between data items from different tasks is small. This highlights the different kind of inductive bias a halfspace gated GLN has compared to a Deep ReLu network. 3) Re bird example, that's slightly unfair. I am sure one could easily make use of the pre-trained resnet to provide informative features to a GLN -- it's early days for this method, hybrid systems haven't been investigated, so I don't know whether it would work better than current SOTA methods for image classification. But I would be pretty confident that some simple combination would work better than chopping the head off a pretrained network and fitting an SVM on top. This is all speculation on my part though. :)
caretak3r 6y ago
As a relative neophyte in this realm, this is fascniating to read. Comparing this to the the models/methods to derive said properties, is good education for me.
nl 6y ago
I didn't realise Hutter was on leave from ANU at DeepMind.

150 points by asparagui 6y ago

Where could this shine? Could it beat SOTA on Nlp tasks?

"We show that this architecture gives rise to universal learning capabilities in the limit, with effective model capacity increasing as a function of network size in a manner comparable with deep ReLU networks." What exactly this statement means?

T-A 6y ago
Presumably (haven't read the paper yet) that their network provably becomes a universal function approximator in the limit of infinite size. Reading... actually the proof seems to be in https://arxiv.org/abs/1712.01897 https://arxiv.org/abs/1712.01897
jawarner 6y ago
As the network size increases, it can learn more complex functions. When the network gets bigger and bigger, it gets closer to being able to learn any arbitrary function.
fxtentacle 6y ago
They mean that if you add parameters, the learning capability of their approach grows by a similar amount as if you would add the same number of parameters to a conv+ReLu network (the standard approach). That "universal" is a weird claim in my opinion, but they mean that with enough parameters, this architecture can learn everything.
- Immortal333 6y ago
  I was able to get the second part of the statement. but I haven't seen the use of "in limit" in a statement like this. Yes, the universal approximation is a strong claim. NN has been proven to have universal approximation theoretically.
  - fxtentacle 6y ago
    "in limit" here means as you approach the edge case of having an unlimited number of parameters.
  - friendly_aixi 6y ago
    The result here is stronger, in the sense that typical NN universality results are statements with respect to just capacity (and not how you optimise them). Here, the result holds with respect to both capacity + a choice of suitable no regret online convex optimisation algorithm (e.g. online gradient descent). Of course, this is just one desirable property of a general purpose learning algorithm.
    - currymj 6y ago
      Do you know of any other kinds of universal function approximators that also have a good regret bound like this, or is yours the first one? global convergence to any arbitrarily weird function at rate O(sqrt(T)) seems amazing, almost too good to be true, and I’m wondering what the catch is. Maybe it’s just a moderately nice property but not extraordinary? Maybe there are some horrible constants hiding in there?
      - friendly_aixi 6y ago
        1) It's definitely not the first. Other methods have universal guarantees of some form or other with well quantified rates of convergence, e.g. k-NN would be the best known example. 2) There are some restrictions on the class of density functions it can model, so arbitrarily weird is a bit strong, but the model class is very general. 3) The weights needed to model any function in this class although finite, can be arbitrarily large. The regret of a single neuron has a dependence on the diameter of the convex set your weights reside in, so there is a nasty constant of sorts in there, and this will also carry over when you analyse the regret of a complete network. With such a general statement, it's unavoidable sadly. 4) The universality result on its own is just a nice property. See it as the first stepping stone to a more meaningful analysis. What you really want is for the model class to grow as you add more neurons, using weights within a realistic range, and that the method performs well in practice on some problems people care about -- we provide empirical evidence that the capacity grows on par with deep relu networks with our capacity experiments, and show a bunch of results where the method works, but we don't have a theoretical characterisation of the class of density functions it can model well (i.e. if the function has some nice structural property, then a network of reasonable size is guaranteed to learn a good approximation quickly). Such a result would be extraordinary in my eyes. Because the network is composed of simple and well understood building blocks, I am optimistic that such an analysis will be possible in the future.
janosett 6y ago
> "We show that this architecture" They are demonstrating a new technique, Gated Linear Networks. > gives rise to universal learning capabilities in the limit they claim to show that with an unbounded amount of time and memory (network size / # params) this architecture can be used to learn/approximate any function > with effective model capacity increasing as a function of network size Model capacity here refers to the ability to memorize a mapping between inputs and outputs. They show that a network with more layers/weights will "memorize" more. > in a manner comparable with deep ReLU networks "Deep ReLU networks" are referring to commonly used modern deep neural network architectures. ReLU is a popular activation function: https://en.wikipedia.org/wiki/Rectifier_(neural_networks) https://en.wikipedia.org/wiki/Rectifier_(neural_networks)

fxtentacle 6y ago

That is an amazing paper, a great result and new neutral architectures are long overdue. But I don't believe that this has any significance in practice. GPU memory is the limiting factor for most current AI approaches. And that's where the typical convolutional architectures shine, because they effectively compress the input data, then work on the compressed representation, then decompress the results. With gated linear networks, I'm required to always work on the full input data, because it's a one step prediction. As the result, I'll run out of GPU memory before I reach a learning capacity that is comparable to conv nets.

BrokrnAlgorithm 6y ago
What about findings w. R. T. Online learning? I find continuous learning quality of algorithms to be a topic which often seems to be more of a side-concern, although it carries a lot of relevance in applied settings.
- fxtentacle 6y ago
  I believe that to be a red herring. Their approach cannot learn any features that provide a lower-dimensional approximation of the input data. As the result, there is no intermediate representation which could change and thereby negatively affect previously learned classifiers. But if I train 10 independent traditional networks, I also won't have newly learned data affect old performance. So in effect they give up the possibility to do transfer learning in exchange for avoiding the disadvantages of transfer learning. But that's a bad tradeoff. With their approach you always train from scratch, which brings with it the need for huge training data sets. So I can train a bird classifier on the traditional architecture with 500 labeled images and a pretrained resnet. Our I use a million bird images and this approach.
  - friendly_aixi 6y ago
    1) Indeed, GLNs don't learn features... but I would claim they do learn some notion of an intermediate representation, it's just different from the DL mainstream -- in particular its closely related to the inverse Radon transform in medical imaging. 2) Inputs which are similar in terms of cosine similarity will map to similar (data dependent) products of weight matrices, and thus behave similarly, which of course can affect performance in both good and bad ways. With the results we show on permuted MNIST, its well... just not particularly likely that they will interfere. This is a good thing -- why should completely different data distributions interfere with one another? The point is the method is resiliant to catastrophic forgetting when the cosine similarity between data items from different tasks is small. This highlights the different kind of inductive bias a halfspace gated GLN has compared to a Deep ReLu network. 3) Re bird example, that's slightly unfair. I am sure one could easily make use of the pre-trained resnet to provide informative features to a GLN -- it's early days for this method, hybrid systems haven't been investigated, so I don't know whether it would work better than current SOTA methods for image classification. But I would be pretty confident that some simple combination would work better than chopping the head off a pretrained network and fitting an SVM on top. This is all speculation on my part though. :)

caretak3r 6y ago

As a relative neophyte in this realm, this is fascniating to read. Comparing this to the the models/methods to derive said properties, is good education for me.

nl 6y ago

I didn't realise Hutter was on leave from ANU at DeepMind.