What is the high-level algorithm followed by contemporary packages for the calculation of gradient?

Question

Most of the neural network models in contemporary deep learning packages are trained based on gradients.

Let $f: \mathbb{R}^m \rightarrow \mathbb{R}^n$ be a function for which we want to find a gradient, then the gradient is generally represented by a Jacobian matrix that looks like below

$$J = \begin{bmatrix} \dfrac{\partial y_1}{\partial x_1} & \dfrac{\partial y_1}{\partial x_2} & \dfrac{\partial y_1}{\partial x_3} &\dots & \dfrac{\partial y_1}{\partial x_m} \\ \dfrac{\partial y_2}{\partial x_1} & \dfrac{\partial y_2}{\partial x_2} & \dfrac{\partial y_2}{\partial x_3} &\dots & \dfrac{\partial y_2}{\partial x_m} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \dfrac{\partial y_n}{\partial x_1} & \dfrac{\partial y_n}{\partial x_2} & \dfrac{\partial y_n}{\partial x_3} &\dots & \dfrac{\partial y_n}{\partial x_m} \\ \end{bmatrix} $$

For example: If $f(x_1, x_2) = \begin{bmatrix} x_1 + x_2 \\ x_1x_2 \end{bmatrix}$ then $J = \begin{bmatrix} 1 & 1 \\ x_2 & x_1 \end{bmatrix}$

After calculating the Jacobian matrix, we can substitute the co-ordinate values of a particular point so that we can obtain a real matrix which is a gradient at a particular point.

$$ J_{(4, 5)} = \begin{bmatrix} 1 & 1 \\ 5 & 4 \end{bmatrix} $$

In order to perform the gradient of a function at a point, the algorithm I know is as follows:

1. Write each output of the function in the analytical form in terms of input;
2. Apply partial derivative on each output w.r.t each input;
3. Substitute the values of the input point at which we want to find the gradient.

Thus, finally, we will get the gradient.

Do the popular packages like PyTorch, Tensorflow, Keras, etc., use this or a variant of this algorithm to find the gradients at a particular point?

If yes, will those packages be able to write the analytical forms of all the output variables in terms of input variables?

If not, what is the high-level algorithm for calculating gradients? Is it based on geometrical slope version of gradient?

Answer 1

Does the popular packages like PyTorch, Tensorflow, Keras, etc., use this or a variant of this algorithm to find the gradients at a particular point?

Yes. This is effectively what back-propagation is. However, there are a couple of important details:

• Using a loss function flattens the matrix form you have to a vector, because with a loss function the dimension of the output $n=1$. This is important, since it is not possible to directly search for a maximum or minimum value for multi-dimensional output.

• Back-propagation is resolved as follows:

  • Set up by constructing a computation graph that composes multiple functions. Some libraries set this graph up directly e.g. TensorFlow, whilst others like PyTorch can resolve it dynamically at run time from requested computations (this is convenient and easier to write, but there is a performance cost).
  • Gradients are calculated numerically by resolving function composition in reverse using the chain rule.
  • There is an implied analytic form for the forward calculation, but it never used directly.

If yes, will those packages be able to write the analytical forms of all the output variables in terms of input variables?

In theory, yes, as the data to do so is in the computational graphs that are used to run neural networks forward, and is the same data that is used to resolve back propagation. In practice I have not seen this done. There may be an add-on or library that could print out the analytic forms of neural network outputs at any layer, or for the loss function. If there is not one, it would not be too hard to write one.

However, other than as a teaching aid for very small networks, then the analytical view of the outputs or loss function are not a practical or useful description of what is going on. The graph view showing how the linear algebra and non-linear activations are composed into a sequence of computations (and reversed step-by-step for gradient calculations) is much easier to comprehend. Many neural network libraries can generate views of this compuational graph.

One important take-away though, is that despite the apparent complexity of back-propagation, it is doing exactly what you expect in the question: Calculating the gradient components in a Jacobian.