4
$\begingroup$

What is the actual learning algorithm: back-propagation or gradient descent (or, in general, the optimization algorithm)?

I am reading through chapter 8 of Parallel Distributed Processing hand book and the title of the chapter is "Learning internal representation by error propagation" by PDP research Group. https://web.stanford.edu/class/psych209a/ReadingsByDate/02_06/PDPVolIChapter8.pdf

If there are no hidden units, no learning happens. If there are hidden units, they learn internal representation by propagating error back. Does this mean back propagation[delta rule] is the learning rule and gradient descent is an optimization algorithm used to optimize cost function?

$\endgroup$
  • $\begingroup$ See also the discussion here: stackoverflow.com/q/37953585/3924118. $\endgroup$ – nbro Nov 14 '18 at 21:28
  • $\begingroup$ "If there are no hidden units, no learning happens. If there are hidden units, they learn internal representation by propagating error back.", this is a property of the model, not of the learning algorithm. $\endgroup$ – nbro Nov 17 '18 at 12:45
5
$\begingroup$

You can run gradient descent without back propagation, in some cases:

  • Simple structures such as linear or logistic regression, where the gradients can be calculated directly from the inputs and cost function value.

  • In "black box" gradient-based learning algorithms where you don't know how (or don't want to) calculate gradient analytically, so you choose to measure it. This is a slow process, similar to gradient checking of neural networks, i.e. adjust each parameter in turn by a small $+\epsilon$, measure your loss function, and divide difference by $\epsilon$ to get gradient estimate for that parameter.

In those cases, you can calculate the gradient, and then use the optimisation function of your choice - e.g. SGD, Adam, Nesterov Momentum - to make changes to the learned parameters. The model will be changed and should learn its task based on the cost function.

You can also run back propagation without gradient descent. In that case, the model will not change and nothing is learned.

That makes the different flavours of gradient descent technically the "core" learning algorithm in my opinion, and back propagation the preferred method for calculating gradients in neural networks. These gradients are most often estimates of an unknown "true gradient" due to training in batches of small samples of training data.

In practice, the two terms back propagation and gradient descent are rarely separated when discussing neural network training. So a lot of people will say that they train a network "using back propagation" or that they are using a gradient descent method without mentioning how they are calculating the gradients using back propagation (because that's pretty much a given). Or they might just say they are "using the Adam optimiser" which in the library they are using automatically runs an NN forward on a mini-batch of data, performs back propagation*, and then changes weight parameters based on the gradients, but heavily adjusted by previous gradient measurements.


* With auto-differentiating frameworks such as TensorFlow, PyTorch etc, it is not really clear that the algorithms are performing "classic back propagation" - although they work using the same chain rule, they may well not perform calculations in the exact same groups that you learned when you studied neural networks and had to write the code for calculating gradients by hand. Instead of back propagating gradients layer-by-layer, they are propagated through an abstract computation graph that includes the learnable parameters.

$\endgroup$
  • $\begingroup$ I think you should add the definition of both backprop and grad descent..Since both have no relation in mathematical terms $\endgroup$ – DuttaA Nov 14 '18 at 13:57
4
$\begingroup$

Gradient descent (GD) is an optimisation algorithm, that is, it is used to find a (local) minimum of a multi-variable and differentiable function $f$. GD is an iterative and numerical optimisation algorithm. It is iterative because it proceeds in iterations. It is numerical because it is not an algorithm which produces an exact solution, due to numerical errors (e.g., round-off errors).

GD is based on the idea that, if a (multi-variable) function $f(\mathbf{x})$ (where $\mathbf{x} \in \mathbb{R}^N$ is a variable representing the input of $f$) is defined and differentiable in a "neighbourhood" of a point $\mathbf{\theta} \in \mathbb{R}^N$, which is a point (in the loose sense of the word "point") in the domain of $f$ (that is, $f(\mathbf{\theta})$ is defined and differentiable), then $f$ decreases fastest if one goes from $\mathbf{\theta}$ in the "direction" of the negative gradient of $f$ at $\mathbf{\theta}$, that is, $-\nabla f(\mathbf {\theta})$. (Do not be scared of the symbol $\theta$, we could have denoted it by $\mathbf{a}$!). Let us break this dense definition down!

Note that here we assume that $f$ is a multi-variable function (that is, a function whose input is not just one real number, but it is a function of $N$ real numbers, which can be grouped in a vector, e.g. $\mathbf{\theta} \in \mathbb{R}^N$), hence $\mathbf{x}$ and $\mathbf{\theta}$ are vectors of real numbers. To emphasize, $\mathbf{\theta}$ is some specific (and "fixed") point in the domain of $f$, whereas $\mathbf{x}$ is a variable that can take any of these specific points.

The basic statement/assignment which is iterated in GD, which captures the definition above, is the following:

$$\mathbf{\theta}_{n+1} \gets \mathbf{\theta}_{n} - \gamma \nabla f(\mathbf{\theta} _{n}) \label{gd-assignment}\tag{1}$$

where the $\gamma$ is a hyper-parameter which represents the "strength" of the step we take in the direction of the negative gradient (i.e., $-\nabla f(\mathbf{\theta} _{n})$). Note the "minus" (i.e., $-$) in front of $\nabla f(\mathbf{\theta}_{n})$, hence the expression "in the direction of the negative gradient". Note also that here "direction" is implemented as a subtraction. The subscript $_n$ represents the current iteration number.

As simple as it looks, the GD algorithm consists in the execution of the assignment \ref{gd-assignment} until some condition is met (e.g., ${\theta}_{n+1}$ is "close enough" to ${\theta}_{n}$). In a nutshell, GD is an iterative algorithm which updates $\theta$ by iterating \ref{gd-assignment} multiple times.

In the context of machine learning (ML), in particular supervised learning, we initially have an untrained model $\mathcal{M}$ (e.g., a neural network), that is, a model whose parameters (sometimes also called "weights") are e.g. randomly initialised. To train $\mathcal{M}$ (i.e., to find the most appropriate parameters of the model with respect to the training data), we first define a so-called "loss function" (which is differentiable), denoted by $\mathcal{L}$, which represents the discrepancy between the current output of $\mathcal{M}$ and the expected output (with respect to the training data) of $\mathcal{M}$. The process of training a model consists in minimising this loss function, that is, it consists in finding the minimum of $\mathcal{L}$.

To do this, as we have just seen above, we can use GD. If you consider the learning process the one of minimising this loss function $\mathcal{L}$, then any algorithm which minimises $\mathcal{L}$ should be called a "learning algorithm". Hence GD should be called a "learning algorithm".

Note that the parameters of the model $\mathcal{M}$, which need to be found during the training process, are often denoted, in ML, by $\theta$. So, the reason why I used the strange symbol $\theta$ in the assignment $\ref{gd-assignment}$ should now be clearer.

Back-propagation (BP) is just an algorithm, proposed by Seppo Linnainmaa in his master's thesis, to compute the derivative of a differentiable (composite) function, which can be represented as a graph.

In ML, back-propagation is often used to compute $\nabla f(\mathbf{\theta}_{n})$ in the assignment \ref{gd-assignment}. So, BP is used as a sub-routine in the GD algorithm (or any other optimization algorithm) to find the parameters of the model $\mathcal{M}$.

Note that, in the context of ML, $\gamma$ in \ref{gd-assignment} is often called the "learning rate". There's a reason for this: GD is the actual learning algorithm. BP is just a sub-routine used to compute the gradient, but we could have used another sub-routine. We could say, in the context of ML (and, in particular, NNs), that the combination of GD and BP is the actual "learning algorithm", but, if by "learning" we mean "optimisation", then the actual "learning algorithm" is GD and not BP, because BP does not optimise anything alone.

$\endgroup$
1
$\begingroup$

Gradient descent is a very general optimization algorithm. Backpropagation is a special case of auto-differenciation combined with gradient descent. So backpropagation is a clever way to do gradient descent.

The idea of Gradient descent is to calculate the gradient (derivative) and use that to descent on the error surface. In 3D, you could imagine 2 parameters (x,y) and the 3rd dimension (z) gives you the training error the model makes with those two parameters. You are at some (random) starting point in this error surface and make a step in downwards direction. Then you calculate the error again and do again a step in downwards direction. Note that I didn't write "downwards" but "in downwards direction" as your step might be too big.

Backpropagation consists of two steps: The forward-pass and the backward-pass. In the forward pass, the output of the network for a given input is calculated. In the backward pass, the gradients are calculated with the chain rule.

See http://cs231n.github.io/optimization-2/ for a good reference for back propagation.

Please note that machine learning is way broader than neural networks. For example, decision trees don't use gradient descent at all to train.

What is the actual learning algorithm: back-propagation or gradient descent?

Gradient descent is the learning algorithm. It is realized in backpropagation in the weight-update of the backward pass.

Notes and References

When I write "backpropagation algorithm", I refer to Tom Mitchells "Machine Learning", Chapter 4.5.2.

To cite Tom Mitchells "Machine Learning":

Algorithms such as BACKPROPAGATION use gradient descent to tune network parameters to best fit a training set of input-output pairs.

[...] gradient descent provides the basis for the BACKPROPAGATION algorithm [...]

[The section 4.5 MULTILAYER NETWORKS AND THE BACKPROPAGATION ALGORITHM] discusses how to learn such multilayer networks using a gradient descent algorithm similar to that discussed in the previous section.

[...]

As shown above, the BACKPROPAGATION algorithm implements a gradient descent search through the space of possible network weights

$\endgroup$
  • 2
    $\begingroup$ This is wrong. Back-prop and gradient descent are two different things. Back-prop is not an implementation of anything. It's a special case of automatic differentiation. $\endgroup$ – nbro Nov 14 '18 at 7:01
  • $\begingroup$ You're nitpicking. Computing the gradient is 99% of the work for gradient descent. For details about the differences: stackoverflow.com/a/37953898/562769 $\endgroup$ – Martin Thoma Nov 14 '18 at 7:39
  • $\begingroup$ nbro is right, and it is an important nit-pick here because the OP is asking about the difference between back prop and gradient descent. A good answer should give a technically accurate answer in that respect. You could add that often people conflate the two because they are used together (as you do here). The linked SO answer has it right $\endgroup$ – Neil Slater Nov 14 '18 at 7:49
  • $\begingroup$ @MartinThoma The answer you cited, stackoverflow.com/a/37953898/3924118, is correct. Your answer is still wrong and I advise you to delete it. Btw, where in the other answer there's something of the kind "Back propagation is a clever implementation of gradient descent."? Also, this question is different. The OP is asking about which of the two algorithms/methods is the "learning algorithm". $\endgroup$ – nbro Nov 14 '18 at 21:26
  • $\begingroup$ "Algorithms such as BACKPROPAGATION use gradient descent to tune network parameters to best fit a training set of input-output pairs." is also wrong. It's the other way around. GD uses BP. You have a lot of wrong statements in this answer. Just delete it or rewrite it completely. But I think that Neil Slater already gave a quite good answer. If you have ever implemented SGD or BP, you will understand what I am talking about. $\endgroup$ – nbro Nov 14 '18 at 21:41
-3
$\begingroup$

Optimization Algorithm just describes the type of algorithm you're trying to use, Back Propagation is a type of Optimization Algorithm, in machine learning you use Back Propagation to Optimize the error function. Also this seems like more of a question for the data science stack exchange.

EDIT: Gradient Descent and Back Propagation are essentially the same thing. Gradient descent is the process of minimizing your error function more and more by making slight changes in the right direction. Back propagation uses partial derivatives to calculate the effect of each variable on the outcome of the error function, and then modifies the weights slightly to move it towards that minimum.

$\endgroup$
  • $\begingroup$ There is nothing silly about the question, IMHO. $\endgroup$ – nbro Nov 14 '18 at 7:04
  • $\begingroup$ @nbro the question has been edited since i posted my answer $\endgroup$ – Jordan LaPrise Nov 14 '18 at 21:09
  • $\begingroup$ Yes, it was edited. I edited it. But I didn't change the meaning of the original question. $\endgroup$ – nbro Nov 14 '18 at 21:22
  • $\begingroup$ Your answer is wrong and you should delete it if you don't want more downvotes. For example, you say "Gradient Descent and Back Propagation are essentially the same thing". This is false/wrong. $\endgroup$ – nbro Nov 14 '18 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.