Gradient Descent

Computation graphs are visual representations of mathematical operations that go from inputs to outputs. They're particularly useful in deep learning to organize calculations. For example, consider the function:

In this function, we have intermediate variables:

And the final output:

We can represent this as:

Derivatives with a Computation Graph

In a computation graph, we often want to calculate how changes in inputs affect the outputs. This is where the chain rule is key. It states that for two functions $f$ and $g$, the derivative of heir composition $(f \circ g)(x) = f(g(x))$ with respect to $x$ is:

In terms of variables, if $y = f(u)$ and $u = g(x)$, then the derivative of $y$ with respect to $x$ is given by:

Here, $\frac{dy}{du}$ is evaluated at the point $u = g(x)$.

In the context of a computation graph, we calculate derivatives from the output back to the inputs. This ight-to-left pass that's more natural for computing derivatives is known as backpropagation in machine learning. The notation $d\text{var}$ represents the derivative of the final output with respect to various intermediate quantities.

Backpropagation Example

Take the visual representation of a computation graph with forward pass above. For the backward pass, we want to compute the derivatives of the final output $J$ with respect to the inputs $a, b, c$ and along the way we will need it in terms of the intermediate quantities $u, v$.

1. Compute intermediates $dJ/dv$ and $dJ/du$, which is the derivative of the final output $J$ with respect to $u$ and $v$.

2. Compute $dJ/da$, which is the derivative of the final output $J$ with respect to $a$.

3. Compute $dJ/db$, which is the derivative of the final output $J$ with respect to $b$.

4. Compute $dJ/dc$, which is the derivative of the final output $J$ with respect to $c$.

We compute these derivatives going from right to left, applying the chain rule at each step.These gradients tell us how much a change in a certain variable affects the final output. This is crucial for algorithms like gradient descent, where we need to adjust parameters to minimize a cost function.

Logistic Regression Gradient Descent

Similarly take the derivatives of gradient descent example for one sample with two features:

• $z$ is the linear combination of inputs and weights plus the bias.
• $a$ is the activation computed using the sigmoid function $\sigma(z)$.
• $\mathcal{L}(a, y)$ is the loss function, which is the binary cross-entropy.
• The derivatives $\frac{d\mathcal{L}}{dw_1}$, $\frac{d\mathcal{L}}{dw_2}$, and $\frac{d\mathcal{L}}{db}$ describe how the loss function changes with respect to each parameter.
• The update rules define how to adjust the parameters $w_1$, $w_2$, and $b$ in the direction that minimizes the loss, using a learning rate $\alpha$

The derivatives for the Backward pass. First the derivative of the binary cross-entropy loss function:

For the derivative of the sigmoid function

For $z$ we have:

Now for the partial derivatives with respect to weights and bias:

And now the update rules for weights and bias

Gradient Descent on $m$ Examples

Take the cost function $J$ for logistic regression which is the average of the binary cross-entropy loss over all $m$ training examples:

We can also calculate the average gradient across all examples. The derivative of $J$ with respect to $w_j$ is:

Once you've computed the derivatives of the cost function $J$ with respect to each parameter, we update the parameters $w$ and $b$ to minimize the cost function $J$.