3
$\begingroup$

I'm struggling to fully understand the stochastic gradient descent algorithm. I know that gradient descent allows you to find the local minimum of a function. What I don't know is what exactly that function IS. More specifically, the algorithm should work by initializing the network with random weights. Then, if I'm not mistaken, it forward-propagates $n$ times (where $n$ is the mini-batch size). At this point, I've no idea about what function should I search for, with over hundreds of neurons each having hundreds of parameters.

$\endgroup$
3
$\begingroup$

Welcome to AI Stack exchange!

You're right, as the network is initialised randomly, the resultant function is essentially impossible to get your head around. This is because most of the time the network has >4 dimensions (4 can be graphed with some effort and a lot of color), and as such is literally beyond human comprehension via graphing.

So what do we do? Well, conveniently, it is possible to find the gradient of segments of a function, without having to know the entirety of the function itself (it's worth noting that it actually is possible to find the resultant function and with a lot of effort find it's derivative. This proves to be much more work than it's worth though, as we don't need the general derivative that tells us what the gradient is for whatever input we give it, we only need the derivative at the specific input we just fed through the network).

This might be hard to understand, but if you're familiar with the chain rule, it might make a bit more sense. The chain rule essentially allows you to split a function into components, and find the gradient of those specific components. By combining all of that, you end up with some nice gradients at each weight/bias with respect to the loss function. Take the negative of the gradient, and you now have the change required to decrease the loss function.

This is obviously quite hard to understand without an example, so here's the best one I've ever found, that helped me very much.

Also, as a side note, the whole mini batch thing is used to minimise catastrophic forgetting (where the network begins to "unlearn" old inputs). To deal with minibatchs, what you do is take input individually, then find the gradient for all weights and bias' for that specific input and remember the changes you want to make. Do that for all inputs in the minibatch, then finally add all the changes together to get the resultant best change for each weight and bias. Only then do you update the weights and bias'.

Let me know if you have any further questions

|improve this answer|||||
$\endgroup$
3
$\begingroup$

I know that gradient descent allows you to find the local minimum of a function. What I don't know is what exactly that function IS.

It's usually called the loss function (and, in general, objective function) and often denoted as $\mathcal{L}$ or $L$ (or something like that, i.e. it is not really important how you denote it). The specific function used as a loss function depends on the problem (ask another question if you want to know the details). For example, in the case of regression, the loss function may be the mean squared error. In classification, the loss function may be the cross-entropy. However, the most important thing to note is that the loss function depends on the parameters of the neural network (NN), so you can differentiate it with respect to the parameters of the NN (i.e. you can take the partial derivative of the loss function with respect to each of the parameters of the NN).

Let's take the example of the mean squared error function, which is defined as

$$ \mathcal{L}(\boldsymbol{\theta}) ={\frac {1}{n}}\sum _{i=1}^{n}(y_i-f_{\boldsymbol{\theta}}(x_i))^{2}. $$ where $n$ is the number of training examples used (the batch size), $y_i$ is the true class (or target) of the input example $x_i$ and $f(x_i)$ is the prediction of the neural network $f_{\boldsymbol{\theta}}$ with parameters (or weights) $\boldsymbol{\theta} = [\theta_i, \dots, \theta_M] \in \mathbb{R}^M$, where $M$ is the number of parameters.

Given the loss function $\mathcal{L}(\boldsymbol{\theta})$, we can now take the derivative of $\mathcal{L}$, with respect to $\boldsymbol{\theta}$, using the famous back-propagation (BP) algorithm, which essentially applies the chain rule of calculus. The BP algorithm produces the gradient of the loss function $\mathcal{L}(\boldsymbol{\theta})$. The gradient can be denoted as $\nabla \mathcal{L}(\boldsymbol{\theta})$ and it contains the partial derivatives of $\mathcal{L}(\boldsymbol{\theta})$ with respect to each parameter $\theta_i$, that is, $\nabla \mathcal{L}(\boldsymbol{\theta}) = \left[ \frac{\partial \mathcal{L}(\boldsymbol{\theta})}{\partial \theta_i}, \dots, \frac{\partial \mathcal{L}(\boldsymbol{\theta})}{\partial \theta_M} \right] \in \mathbb{R}^M$. (If you want to know the details of the back-propagation algorithm, you should ask another question, but make sure you get informed first, because it may not be easy to fully explain it in an answer.)

Afterward, we just apply the gradient descent step

$$ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \gamma \nabla \mathcal{L}(\boldsymbol{\theta}) $$

where $\gamma \in \mathbb{R}$ is often called the learning rate and is used to weight the contribution of the gradient $\nabla \mathcal{L}(\boldsymbol{\theta})$ to the new values of the parameters, and $\leftarrow$ represents an assignment (like in programming).

It is worth emphasizing that both $\boldsymbol{\theta}$ and $\nabla \mathcal{L}(\boldsymbol{\theta})$ are vectors and have the same dimensionality ($M$).

Have also a look at this answer where I explain the difference between gradient descent and stochastic gradient descent.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ The OP is not actually asking about the loss function, but about the target function. That's a difference in perspective, I don't see anything factually wrong in this answer, but I think it doesn't address the question as phrased (whether that is OP's intent of course is a different matter). The loss function measures the difference at a set of discrete points, between the target function and the current function that the NN produces. If you combine your and Recessive's answers you get the full picture, which may help the OP. $\endgroup$ – Neil Slater Jan 15 at 13:34
  • $\begingroup$ @NeilSlater My answer addresses this sentence "I know that gradient descent allows you to find the local minimum of a function. What I don't know is what exactly that function IS". $\endgroup$ – nbro Jan 15 at 13:35
  • $\begingroup$ Ah, sorry, the OP actually asks about both and is confused. because they also say at this point, I've no idea about what function should I search for. the function that is "searched for" is the target function. I think it would help the OP if you addressed the difference $\endgroup$ – Neil Slater Jan 15 at 13:36
  • $\begingroup$ @NeilSlater Don't worry. Maybe I should have clarified which part of the post I was addressing. I've just edited my answer to do that ;) $\endgroup$ – nbro Jan 15 at 13:43
  • 2
    $\begingroup$ @NeilSlater Actually, this answer really helped me out xD. I was confused because I didn't even know what to look for, since I didn't understand the learning algorithm in general, but guess what, I just got a clear explanation about that! ;D I figured out that the "missing piece" was the backpropagation, wich "connects" the loss function to the actual gradient. Now, I only need to read this answer over, over and over so that it gets stuck in my head forever. Thanks :D $\endgroup$ – Orly Jan 15 at 20:56
0
$\begingroup$

After I've learned a little bit more about the topic, I think I figured out the exact sequence of the algorithm. So, here's my own answer. Please, correct me if I'm wrong.

  1. Give an input, forward-propagate it, and generate an output

  2. For each output neuron: for each weight connected to the neuron: Given the function C = f(w) (which represents the cost in function to the weight value), calculate the derivative of that function at the point where the current weight actually is)

  3. Calculate the actual derivative of all the weights by combining all the partial derivatives in respect to the weight: now you have a gradient of the weights

  4. Repeat this process to calculate the gradient for each of the batch elements. If you have a batch size of 8, then you'll have 8 gradients.

  5. Find the average gradient ((gradient_1+gradient2+gradient3...)/n_gradients)

  6. Move the weights of that gradient

Am I right? How does this apply to deeper layers?

|improve this answer|||||
$\endgroup$
  • $\begingroup$ @nbro I'm asking for your greatness :) $\endgroup$ – Orly Jan 26 at 21:01
  • $\begingroup$ Thanks for the compliment. I also try to do my best :) Your answer seems roughly correct, but I am not sure why you distinguish the weights connected to the output neurons from the other weights. Anyway, if you have a batch of size 8 (or any other number), you will not compute the gradient with respect to each element of the batch, sum these gradients and then divide by 8. $\endgroup$ – nbro Jan 27 at 11:49
  • $\begingroup$ Instead, you'll compute the loss with these 8 elements (see the loss function I defined in my answer), then compute a single gradient (which is often called a "stochastic estimate" of the actual gradient, where, by "actual gradient", I mean a gradient computed with all elements of the dataset). How do you compute it? You just take the derivative of the loss function (I defined in my answer) with respect to each parameter of the network. Try to take the derivative of that loss function with respect to one parameter of the network, for a simple network. You will understand better the process! $\endgroup$ – nbro Jan 27 at 11:55
  • $\begingroup$ Then I suggest you try to implement a basic version of a simple feed-forward neural network (e.g. with 1 or 2 hidden layers), then implement a basic version of back-propagation and gradient descent to train this network. You will understand all the details after having implemented it. See these implementations https://github.com/mnielsen/neural-networks-and-deep-learning. I think they may be useful ;) $\endgroup$ – nbro Jan 27 at 11:55

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.