Answers.Body: <p>Welcome to AI Stack exchange!</p>
  
  <p>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.</p>
  
  <p>So what do we do? Well, conveniently, it is possible to find the gradient of <em>segments</em> 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).</p>
  
  <p>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.</p>
  
  <p>This is obviously quite hard to understand without an example, <a href="https://youtu.be/d14TUNcbn1k?t=354" rel="nofollow noreferrer">so here's the best one I've ever found, that helped me very much</a>.</p>
  
  <p>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'.</p>
  
  <p>Let me know if you have any further questions</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-14T23:34:17.723Z
Answers.LastActivityDate: 2020-01-14T23:34:17.723Z
Answers.UserDisplayName: Recessive
Answers.Body: <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>It's usually called the <strong>loss function</strong> (and, in general, <a href="https://en.wikipedia.org/wiki/Loss_function" rel="nofollow noreferrer">objective function</a>) and often denoted as <span class="math-container">$\mathcal{L}$</span> or <span class="math-container">$L$</span> (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 <a href="https://en.wikipedia.org/wiki/Mean_squared_error" rel="nofollow noreferrer">mean squared error</a>. In classification, the loss function may be the <a href="https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_loss_function_and_logistic_regression" rel="nofollow noreferrer">cross-entropy</a>. 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 <a href="https://en.wikipedia.org/wiki/Partial_derivative" rel="nofollow noreferrer">partial derivative</a> of the loss function with respect to each of the parameters of the NN). </p>
  
  <p>Let's take the example of the mean squared error function, which is defined as </p>
  
  <p><span class="math-container">$$
  \mathcal{L}(\boldsymbol{\theta}) ={\frac {1}{n}}\sum _{i=1}^{n}(y_i-f_{\boldsymbol{\theta}}(x_i))^{2}.
  $$</span>
  where <span class="math-container">$n$</span> is the number of training examples used (the batch size), <span class="math-container">$y_i$</span> is the true class (or target) of the input example <span class="math-container">$x_i$</span> and <span class="math-container">$f(x_i)$</span> is the prediction of the neural network <span class="math-container">$f_{\boldsymbol{\theta}}$</span> with parameters (or weights) <span class="math-container">$\boldsymbol{\theta} = [\theta_i, \dots, \theta_M] \in \mathbb{R}^M$</span>, where <span class="math-container">$M$</span> is the number of parameters.</p>
  
  <p>Given the loss function <span class="math-container">$\mathcal{L}(\boldsymbol{\theta})$</span>, we can now take the derivative of <span class="math-container">$\mathcal{L}$</span>, with respect to <span class="math-container">$\boldsymbol{\theta}$</span>, using the famous <a href="https://en.wikipedia.org/wiki/Backpropagation" rel="nofollow noreferrer"><strong>back-propagation</strong></a> (BP) algorithm, which essentially applies the <a href="https://en.wikipedia.org/wiki/Chain_rule" rel="nofollow noreferrer">chain rule of calculus</a>. The BP algorithm produces the <strong>gradient</strong> of the loss function <span class="math-container">$\mathcal{L}(\boldsymbol{\theta})$</span>. The <a href="https://en.wikipedia.org/wiki/Gradient" rel="nofollow noreferrer">gradient</a> can be denoted as <span class="math-container">$\nabla \mathcal{L}(\boldsymbol{\theta})$</span> and it contains the partial derivatives of <span class="math-container">$\mathcal{L}(\boldsymbol{\theta})$</span> with respect to each parameter <span class="math-container">$\theta_i$</span>, that is, <span class="math-container">$\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$</span>. (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.)</p>
  
  <p>Afterward, we just apply the <strong>gradient descent</strong> step</p>
  
  <p><span class="math-container">$$
  \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \gamma \nabla \mathcal{L}(\boldsymbol{\theta})
  $$</span></p>
  
  <p>where <span class="math-container">$\gamma \in \mathbb{R}$</span> is often called the learning rate and is used to weight the contribution of the gradient <span class="math-container">$\nabla \mathcal{L}(\boldsymbol{\theta})$</span> to the new values of the parameters, and <span class="math-container">$\leftarrow$</span> represents an <a href="https://en.wikipedia.org/wiki/Assignment_(computer_science)" rel="nofollow noreferrer">assignment (like in programming)</a>.</p>
  
  <p>It is worth emphasizing that both <span class="math-container">$\boldsymbol{\theta}$</span> and <span class="math-container">$\nabla \mathcal{L}(\boldsymbol{\theta})$</span> are vectors and have the same dimensionality (<span class="math-container">$M$</span>).</p>
  
  <p>Have also a look at <a href="https://ai.stackexchange.com/a/11675/2444">this answer</a> where I explain the difference between gradient descent and stochastic gradient descent. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T13:34:04.087Z
Answers.Text: 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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T13:35:23.943Z
Answers.Text: @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"_.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T13:36:52.480Z
Answers.Text: 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
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T13:43:19.280Z
Answers.Text: @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 ;)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T20:56:57.077Z
Answers.Text: @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
Answers.UserDisplayName: Orly
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-14T23:48:43.667Z
Answers.LastActivityDate: 2020-01-15T13:42:43.287Z
Answers.LastEditDate: 2020-01-15T13:42:43.287Z
Answers.UserDisplayName: nbro
Answers.Body: <p>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.</p>
  
  <ol>
  <li><p>Give an input, forward-propagate it, and generate an output</p></li>
  <li><p>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)</p></li>
  <li><p>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</p></li>
  <li><p>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.</p></li>
  <li><p>Find the average gradient ((gradient_1+gradient2+gradient3...)/n_gradients)</p></li>
  <li><p>Move the weights of that gradient</p></li>
  </ol>
  
  <p>Am I right? How does this apply to deeper layers?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-26T21:01:05.270Z
Answers.Text: @nbro I'm asking for your greatness :)
Answers.UserDisplayName: Orly
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-27T11:49:00.900Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-27T11:55:05.740Z
Answers.Text: 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!
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-27T11:55:09.897Z
Answers.Text: 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](https://github.com/mnielsen/neural-networks-and-deep-learning). I think they may be useful ;)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-26T20:58:17.610Z
Answers.LastActivityDate: 2020-01-27T11:40:02.817Z
Answers.LastEditDate: 2020-01-27T11:40:02.817Z
Answers.UserDisplayName: Orly
Body: <p>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 <span class="math-container">$n$</span> times (where <span class="math-container">$n$</span> 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.</p>
  
Tags: <neural-networks><deep-learning><backpropagation><objective-functions><gradient-descent>
Title: What's the function that SGD takes to calculate the gradient?
UserDisplayName: Orly
ThreadText: # What's the function that SGD takes to calculate the gradient?
  
  (Asked by: username_0 on 2020-01-14)
  
  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.
  
  **Tags:** neural-networks, deep-learning, backpropagation, objective-functions, gradient-descent
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2020-01-14. Score: 3
  
  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](https://youtu.be/d14TUNcbn1k?t=354).
  
  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
  
  
  ---
  
  ### Answer by username_2 on 2020-01-14. Score: 3
  
  > 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](https://en.wikipedia.org/wiki/Loss_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](https://en.wikipedia.org/wiki/Mean_squared_error). In classification, the loss function may be the [cross-entropy](https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_loss_function_and_logistic_regression). 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](https://en.wikipedia.org/wiki/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**](https://en.wikipedia.org/wiki/Backpropagation) (BP) algorithm, which essentially applies the [chain rule of calculus](https://en.wikipedia.org/wiki/Chain_rule). The BP algorithm produces the **gradient** of the loss function $\mathcal{L}(\boldsymbol{\theta})$. The [gradient](https://en.wikipedia.org/wiki/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)](https://en.wikipedia.org/wiki/Assignment_(computer_science)).
  
  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](https://ai.stackexchange.com/a/11675/2444) where I explain the difference between gradient descent and stochastic gradient descent.
  
  > **Comments:**
  > **username_3**: 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.  
  > **username_2**: @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"_.  
  > **username_3**: 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  
  > **username_2**: @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 ;)  
  > **username_0**: @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  
  
  ---
  
  ### Answer by username_0 on 2020-01-26. Score: 0
  
  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?
  
  > **Comments:**
  > **username_0**: @nbro I'm asking for your greatness :)  
  > **username_2**: 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.  
  > **username_2**: 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!  
  > **username_2**: 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](https://github.com/mnielsen/neural-networks-and-deep-learning). I think they may be useful ;)  
  
  ---
  
  