7 ms·

How the backpropagation algorithm works

140 points by oskarth 13y ago

oskarth 13y ago
This is chapter two of Michael Nielsen's book on Neural Networks and Deep Learning [1]. If you haven't heard about it before, I highly suggest you check it out. http://neuralnetworksanddeeplearning.com/about.html http://neuralnetworksanddeeplearning.com/about.html
cjauvin 13y ago
This seems like it will be a very interesting book. If anyone is interested, I have written a short and compressed intro to NNs, using very simple Python code: http://cjauvin.blogspot.ca/2013/10/neural-network-101.html http://cjauvin.blogspot.ca/2013/10/neural-network-101.html
agibsonccc 13y ago
This is a great explanation of backpropagation. For those who just want the formulas, my personal favorite has been stanford's ufldl resource: http://ufldl.stanford.edu/wiki/index.php/Backpropagation_Algorithm http://ufldl.stanford.edu/wiki/index.php/Backpropagation_Alg... The general intuition behind backprop is that, taking prediction error in to account (think how many labels it got wrong) How far off were the predictions? Based on that go back and penalize the weights that caused the error by that much. Multi layer perceptrons (as well as multi layer deep nets) have multiple layers whereupon you send the input through the network and make a guess. Then you basically keep updating the weights (iteratively via gradient descent, conjugate gradient, LBFGS,...) till it doesn't change much. It does this by conducting a search navigating using the cost: or objective function. For more in depth, obviously the above book covers this quite in depth. For those who want to just use deep learning, I will be giving talks at both OSCon and Hadoop Summit this year on distributed deep learning using 2 different frameworks I commit to [1] and [2]. Happy to answer questions! [1]: http://deeplearning4j.org/ http://deeplearning4j.org/ [2]: http://github.com/jpatanooga/Metronome/ http://github.com/jpatanooga/Metronome/
plg 13y ago
Nice description of backprop for sure. Aren't people using conjugate gradient descent to optimize NN weights now? Sure you need the partial derivatives but ... that's what GPUs are for, right? :)
- nimish 13y ago
  Backprop lets you calculate the gradient efficiently. What you do with that gradient is up to you (I would try L-BFGS or something akin to a stochastic variation). So you could use conjugate gradient or some other optimization method
dave_sullivan 13y ago
This book is really coming together. It's been a while since I've put together a (100% not comprehensive) list of good places to start if you're looking to learn more and/or use deep learning in your projects. Open source Pylearn2 (used to win kaggle galaxies competition): http://deeplearning.net/software/pylearn2/ http://deeplearning.net/software/pylearn2/ Theano (symbolic math library used by Pylearn2): http://deeplearning.net/software/theano/ http://deeplearning.net/software/theano/ Deep learning tutorials with theano (build your own neural networks): http://www.deeplearning.net/tutorial/ http://www.deeplearning.net/tutorial/ Demos Convnet JS: http://cs.stanford.edu/people/karpathy/convnetjs/ http://cs.stanford.edu/people/karpathy/convnetjs/ Sentiment Analysis: http://nlp.stanford.edu:8080/sentiment/rntnDemo.html http://nlp.stanford.edu:8080/sentiment/rntnDemo.html 3d word cloud (webgl): http://wordcloud.ersatz1.com/ http://wordcloud.ersatz1.com/ Commercial Ersatz (I'm a co-founder, it's a PaaS providing neural network software with cloud GPU servers): http://www.ersatzlabs.com http://www.ersatzlabs.com Good Reading Deep learning of representations: looking forward http://arxiv.org/pdf/1305.0445v2.pdf http://arxiv.org/pdf/1305.0445v2.pdf Zero-Shot Learning Through Cross-Modal Transfer: http://arxiv.org/pdf/1301.3666v2.pdf http://arxiv.org/pdf/1301.3666v2.pdf <-- C'mon, that's pretty amazing... Solution for the Galaxy Zoo challenge: http://benanne.github.io/2014/04/05/galaxy-zoo.html http://benanne.github.io/2014/04/05/galaxy-zoo.html Pylearn2 in practice: http://fastml.com/pylearn2-in-practice/ http://fastml.com/pylearn2-in-practice/
- ma2rten 13y ago
  I while ago I posted a comment here on HN which got number of upvotes but no answer. Could you maybe take stab at it? I've followed the developments in Neural Networks somewhat, but have never applied deep learning so far. This is seems like a good place to ask a couple of question I've been having for a while. 1. When does it make sense to apply deep learning? Could it potentially be applied successful applied to any difficult problem given enough data? Could it also be good at the type of problems that Random Forest, Gradient Boosting Machines are traditionally good at versus the problems that SVMs are traditionally good at (Computer Vision, NLP)? [1] 2. How much data is enough? 3. What degree of tuning is required to make it work? Are we at the point yet where deep learning works more or less out the box? 4. Is it fair to say that dropout and maxout always work better in practice? [2] 5. What is the computational effort? How long e.g. does it take to classify an ImageNet image (on a CPU / GPU)? How long does it take train a model like that? 6. How on earth does this fit into memory? Say in ImageNet your have (256 pixels * 256 pixels) * (10,000 classes) * 4 bytes = 2.4 GB, for a NN without any hidden layers. [1] I am overgeneralizing somewhat, I know. It's my way to avoid overfitting. [2] My lunch today was free.
avaku 13y ago
Can I come up with a bit of criticism? This book does provide a great description of the details of the algorithm inner workings (very cute demons too). However, after reading this chapter (sorry I haven't looked at the other ones), there is still a feel of a bit of mystery about why it works, and even more why it might not work. Possibly is is covered in other parts of the book, so I apologise if this criticism is not justified. I am personally a big fan of Christopher Bishop's book Pattern Recognition and Machine Learning, where backprop is described as an architecture for efficient computation of multiple stochastic gradient descents... I was involved with NNs before, but only after understanding where the algorithm for individual neurons comes from, I could properly appreciate the benefits of backprop (and understand the drawbacks).
argc 13y ago
Or "Why I wish I was better at math."
j2kun 13y ago
Can someone explain to me why NN's are always in layers?
- walrus 13y ago
  Feedforward neural networks are acyclic; recurrent neural networks are cyclic. Recurrent NNs are harder to train in general.
  - j2kun 13y ago
    Layered is much more specific than acyclic. I can come up with an example that is not layered by still acyclic. Just connect nodes across two or more layers.
    - walrus 13y ago
      Functionally, layered and acyclic NNs are the same thing. An arbitrary acyclic NN acts the same as a layered NN with some of the weights fixed at 1 or 0. (Replace any edge crossing n layers in a non-layered acyclic NN with a chain of n nodes to get a layered NN that responds to input the same as the original non-layered NN.) I suppose there may be some cases where the extra speed you get by omitting the intermediate nodes pays off. However, I can't imagine a situation where you'd know enough about the problem in advance that you could design the NN's graph in that level of detail.
      - j2kun 13y ago
        Usually the adjacency between layers is complete, so your modification isn't quite without loss of generality. I also cannot imagine a situation in which you'd know that much detail, but using a general network would allow one to, for example, dynamically modify the topology of the graph (as real neural networks do regularly). EDIT: I guess what I'm asking for is a rigorous proof that the two models are equivalent with as little overhead as you say there should be.
- _ikke_ 13y ago
  From the first chapter of this book, it is described that each layer adds more abstraction. The first layer (input) works on individual pixels, the next layer on a part of the image. Each deeper layer can make more high-level decissions.
jey 13y ago
What are some problems where Deep Learning shines? Does it outperform other algorithms on those problems? Is there an understanding of why? Context: I have some background in statistical sorts of machine learning algorithms and am genuinely puzzled by this "deep learning" phenomenon and why it's catching on.
- ma2rten 13y ago
  Deep learning can expose hidden non-linear relationships in the data. It's state-of-the-art in applications such as object recognition from images and voice recognition. There have also been promising results in the natural language processing field. What all of these have in common is that they are "real" artificial intelligence, i.e. teaching computers things that they have been historically bad at compared to humans. Search for a talk by Geoffrey Hinton if you are genuinely interested.
- Houshalter 13y ago
  Deep learning is the state of the art on image and sound data. It's taking over natural language processing as well. Neural networks work well because they can learn complicated functions from the data. With image, sound and maybe text, the data has structure that can be exploited by NNs. Convolutional neural networks take advantage of this. So instead of learning "pixel 4,773 correlates with the output", we can look at a smaller number of image patches and learn "features" from each patch that correlate with the output. We can go further and create multiple layers of these. Each small image patch extracts some features which are used by the layer above it, and so on to the final output.
turbolent 13y ago
There's a really nice explanation at http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html
zackmorris 13y ago
I can't emphasize enough how great it is the he actually provides CODE right from chapter one that implements a network with an arbitrary number of neurons at each layer using NumPy. I've read (arguably) better explanations of how neural networks function, but the code was always either archaic or nonexistent. To me, the ability to learn artificial intelligence concepts but also pass them on to others in a way that they can be tinkered with signals a tipping point in the field. I would like to see all of the basic building blocks of AI (such as Bayes classifiers, genetic algorithms, etc) packaged up this way into an API that is as approachable as OpenGL. Then I would like to see multiprocessing libraries like OpenCL/CUDA incorporated internally so that training can happen in milliseconds instead of minutes or hours. With enough eyeballs looking at these things, we might be able to get from heuristics and rules of thumb for training values to something more concrete. It seems like every time I learn a new paradigm it devolves into wishy-washiness because there are just not enough years in a researcher's life to discover the subtle rules at work behind the scenes. The progression seems to always be the same: failure to achieve success over 50%, then reaching 95% after some hours/days of tinkering, then finding the model hits a maximum of 99% and another model must be learned. Rinse, repeat. If that changes, and we’re able to link up various models without having to choose arbitrary constants, machine learning will have arrived IMHO. We could throw hardware at it and let an array of agents evolve in parallel without human intervention until we see which arrangements work best. Eventually that could lead to a theory of mind that actually works because it could learn anything a human could learn, for the most part unsupervised. I’ve learned just enough about this stuff to wonder about the endgame. I have a hunch that it will involve something akin to version control, so that an AI can try different approaches until it finds a solution, but with the ability to roll back in case it goes off the rails. Does anyone have a starting point for things like imagination in AI, or trial runs that happen in simulation before the AI acts in real life? And maybe how to merge new solutions into existing ones?
- michael_nielsen 13y ago
  Author here. I'd love if you could give me pointers to your favourite explanations of how neural networks function (even better, if you can say what you particularly liked about them). (I really enjoyed reading the remainder of your comment.)

140 points by oskarth 13y ago

This is chapter two of Michael Nielsen's book on Neural Networks and Deep Learning [1]. If you haven't heard about it before, I highly suggest you check it out. http://neuralnetworksanddeeplearning.com/about.html http://neuralnetworksanddeeplearning.com/about.html

cjauvin 13y ago

This seems like it will be a very interesting book. If anyone is interested, I have written a short and compressed intro to NNs, using very simple Python code: http://cjauvin.blogspot.ca/2013/10/neural-network-101.html http://cjauvin.blogspot.ca/2013/10/neural-network-101.html

agibsonccc 13y ago

This is a great explanation of backpropagation. For those who just want the formulas, my personal favorite has been stanford's ufldl resource: http://ufldl.stanford.edu/wiki/index.php/Backpropagation_Algorithm http://ufldl.stanford.edu/wiki/index.php/Backpropagation_Alg... The general intuition behind backprop is that, taking prediction error in to account (think how many labels it got wrong) How far off were the predictions? Based on that go back and penalize the weights that caused the error by that much. Multi layer perceptrons (as well as multi layer deep nets) have multiple layers whereupon you send the input through the network and make a guess. Then you basically keep updating the weights (iteratively via gradient descent, conjugate gradient, LBFGS,...) till it doesn't change much. It does this by conducting a search navigating using the cost: or objective function. For more in depth, obviously the above book covers this quite in depth. For those who want to just use deep learning, I will be giving talks at both OSCon and Hadoop Summit this year on distributed deep learning using 2 different frameworks I commit to [1] and [2]. Happy to answer questions! [1]: http://deeplearning4j.org/ http://deeplearning4j.org/ [2]: http://github.com/jpatanooga/Metronome/ http://github.com/jpatanooga/Metronome/

plg 13y ago

Nice description of backprop for sure. Aren't people using conjugate gradient descent to optimize NN weights now? Sure you need the partial derivatives but ... that's what GPUs are for, right? :)

nimish 13y ago
Backprop lets you calculate the gradient efficiently. What you do with that gradient is up to you (I would try L-BFGS or something akin to a stochastic variation). So you could use conjugate gradient or some other optimization method

dave_sullivan 13y ago

This book is really coming together. It's been a while since I've put together a (100% not comprehensive) list of good places to start if you're looking to learn more and/or use deep learning in your projects. Open source Pylearn2 (used to win kaggle galaxies competition): http://deeplearning.net/software/pylearn2/ http://deeplearning.net/software/pylearn2/ Theano (symbolic math library used by Pylearn2): http://deeplearning.net/software/theano/ http://deeplearning.net/software/theano/ Deep learning tutorials with theano (build your own neural networks): http://www.deeplearning.net/tutorial/ http://www.deeplearning.net/tutorial/ Demos Convnet JS: http://cs.stanford.edu/people/karpathy/convnetjs/ http://cs.stanford.edu/people/karpathy/convnetjs/ Sentiment Analysis: http://nlp.stanford.edu:8080/sentiment/rntnDemo.html http://nlp.stanford.edu:8080/sentiment/rntnDemo.html 3d word cloud (webgl): http://wordcloud.ersatz1.com/ http://wordcloud.ersatz1.com/ Commercial Ersatz (I'm a co-founder, it's a PaaS providing neural network software with cloud GPU servers): http://www.ersatzlabs.com http://www.ersatzlabs.com Good Reading Deep learning of representations: looking forward http://arxiv.org/pdf/1305.0445v2.pdf http://arxiv.org/pdf/1305.0445v2.pdf Zero-Shot Learning Through Cross-Modal Transfer: http://arxiv.org/pdf/1301.3666v2.pdf http://arxiv.org/pdf/1301.3666v2.pdf <-- C'mon, that's pretty amazing... Solution for the Galaxy Zoo challenge: http://benanne.github.io/2014/04/05/galaxy-zoo.html http://benanne.github.io/2014/04/05/galaxy-zoo.html Pylearn2 in practice: http://fastml.com/pylearn2-in-practice/ http://fastml.com/pylearn2-in-practice/

ma2rten 13y ago
I while ago I posted a comment here on HN which got number of upvotes but no answer. Could you maybe take stab at it? I've followed the developments in Neural Networks somewhat, but have never applied deep learning so far. This is seems like a good place to ask a couple of question I've been having for a while. 1. When does it make sense to apply deep learning? Could it potentially be applied successful applied to any difficult problem given enough data? Could it also be good at the type of problems that Random Forest, Gradient Boosting Machines are traditionally good at versus the problems that SVMs are traditionally good at (Computer Vision, NLP)? [1] 2. How much data is enough? 3. What degree of tuning is required to make it work? Are we at the point yet where deep learning works more or less out the box? 4. Is it fair to say that dropout and maxout always work better in practice? [2] 5. What is the computational effort? How long e.g. does it take to classify an ImageNet image (on a CPU / GPU)? How long does it take train a model like that? 6. How on earth does this fit into memory? Say in ImageNet your have (256 pixels * 256 pixels) * (10,000 classes) * 4 bytes = 2.4 GB, for a NN without any hidden layers. [1] I am overgeneralizing somewhat, I know. It's my way to avoid overfitting. [2] My lunch today was free.

avaku 13y ago

Can I come up with a bit of criticism? This book does provide a great description of the details of the algorithm inner workings (very cute demons too). However, after reading this chapter (sorry I haven't looked at the other ones), there is still a feel of a bit of mystery about why it works, and even more why it might not work. Possibly is is covered in other parts of the book, so I apologise if this criticism is not justified. I am personally a big fan of Christopher Bishop's book Pattern Recognition and Machine Learning, where backprop is described as an architecture for efficient computation of multiple stochastic gradient descents... I was involved with NNs before, but only after understanding where the algorithm for individual neurons comes from, I could properly appreciate the benefits of backprop (and understand the drawbacks).

argc 13y ago

Or "Why I wish I was better at math."

j2kun 13y ago

Can someone explain to me why NN's are always in layers?

walrus 13y ago
Feedforward neural networks are acyclic; recurrent neural networks are cyclic. Recurrent NNs are harder to train in general.
- j2kun 13y ago
  Layered is much more specific than acyclic. I can come up with an example that is not layered by still acyclic. Just connect nodes across two or more layers.
  - walrus 13y ago
    Functionally, layered and acyclic NNs are the same thing. An arbitrary acyclic NN acts the same as a layered NN with some of the weights fixed at 1 or 0. (Replace any edge crossing n layers in a non-layered acyclic NN with a chain of n nodes to get a layered NN that responds to input the same as the original non-layered NN.) I suppose there may be some cases where the extra speed you get by omitting the intermediate nodes pays off. However, I can't imagine a situation where you'd know enough about the problem in advance that you could design the NN's graph in that level of detail.
    - j2kun 13y ago
      Usually the adjacency between layers is complete, so your modification isn't quite without loss of generality. I also cannot imagine a situation in which you'd know that much detail, but using a general network would allow one to, for example, dynamically modify the topology of the graph (as real neural networks do regularly). EDIT: I guess what I'm asking for is a rigorous proof that the two models are equivalent with as little overhead as you say there should be.
_ikke_ 13y ago
From the first chapter of this book, it is described that each layer adds more abstraction. The first layer (input) works on individual pixels, the next layer on a part of the image. Each deeper layer can make more high-level decissions.

jey 13y ago

What are some problems where Deep Learning shines? Does it outperform other algorithms on those problems? Is there an understanding of why? Context: I have some background in statistical sorts of machine learning algorithms and am genuinely puzzled by this "deep learning" phenomenon and why it's catching on.

ma2rten 13y ago
Deep learning can expose hidden non-linear relationships in the data. It's state-of-the-art in applications such as object recognition from images and voice recognition. There have also been promising results in the natural language processing field. What all of these have in common is that they are "real" artificial intelligence, i.e. teaching computers things that they have been historically bad at compared to humans. Search for a talk by Geoffrey Hinton if you are genuinely interested.
Houshalter 13y ago
Deep learning is the state of the art on image and sound data. It's taking over natural language processing as well. Neural networks work well because they can learn complicated functions from the data. With image, sound and maybe text, the data has structure that can be exploited by NNs. Convolutional neural networks take advantage of this. So instead of learning "pixel 4,773 correlates with the output", we can look at a smaller number of image patches and learn "features" from each patch that correlate with the output. We can go further and create multiple layers of these. Each small image patch extracts some features which are used by the layer above it, and so on to the final output.

turbolent 13y ago

There's a really nice explanation at http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html

zackmorris 13y ago

I can't emphasize enough how great it is the he actually provides CODE right from chapter one that implements a network with an arbitrary number of neurons at each layer using NumPy. I've read (arguably) better explanations of how neural networks function, but the code was always either archaic or nonexistent. To me, the ability to learn artificial intelligence concepts but also pass them on to others in a way that they can be tinkered with signals a tipping point in the field. I would like to see all of the basic building blocks of AI (such as Bayes classifiers, genetic algorithms, etc) packaged up this way into an API that is as approachable as OpenGL. Then I would like to see multiprocessing libraries like OpenCL/CUDA incorporated internally so that training can happen in milliseconds instead of minutes or hours. With enough eyeballs looking at these things, we might be able to get from heuristics and rules of thumb for training values to something more concrete. It seems like every time I learn a new paradigm it devolves into wishy-washiness because there are just not enough years in a researcher's life to discover the subtle rules at work behind the scenes. The progression seems to always be the same: failure to achieve success over 50%, then reaching 95% after some hours/days of tinkering, then finding the model hits a maximum of 99% and another model must be learned. Rinse, repeat. If that changes, and we’re able to link up various models without having to choose arbitrary constants, machine learning will have arrived IMHO. We could throw hardware at it and let an array of agents evolve in parallel without human intervention until we see which arrangements work best. Eventually that could lead to a theory of mind that actually works because it could learn anything a human could learn, for the most part unsupervised. I’ve learned just enough about this stuff to wonder about the endgame. I have a hunch that it will involve something akin to version control, so that an AI can try different approaches until it finds a solution, but with the ability to roll back in case it goes off the rails. Does anyone have a starting point for things like imagination in AI, or trial runs that happen in simulation before the AI acts in real life? And maybe how to merge new solutions into existing ones?

michael_nielsen 13y ago
Author here. I'd love if you could give me pointers to your favourite explanations of how neural networks function (even better, if you can say what you particularly liked about them). (I really enjoyed reading the remainder of your comment.)