2
$\begingroup$

How it is possible to use automative differentiation (computational graph) on operations like - convolution?

I know that 2d convolution can be represented by matrix multiplication. But what about 3d convolutional or other more complex operations?

$\endgroup$

1 Answer 1

4
$\begingroup$

I will address your question in a roundabout manner, but you will see why.

We can compute a gradient on any convolutional layer, no matter the dimension, because convolution is defined in a similar manner irrespective of dimension.

Convolution Definition

Just to give the formalism, let's consider the rank-2 tensor convolution (rank 2 tensor is a matrix). Given an input $X$ (we can say is of size $k \times k$), a convolution is effectively taking the sum of all of the element-wise products of the kernel $w$ (a matrix of size $m \times n$) onto the submatrices of $X$ of size $m \times n$. Clearly, $m, n \leq k$ for this to make sense. For a convolution, $C$, of stride 1, we can define the convolution operation $C*w$, component-wise, as:

$$C_{i, j} = \sum_{k}\sum_{l}\hat{X}_{i, j, k, l} \cdot w_{k, l}$$

$\hat{X}_{i, j, k, l}$ denotes the $(i, j)$-th submatrix of $X$, and $k, l$ denotes the $(k,l)$-th component of this submatrix. Clearly, you see that we are taking the sum of all component-wise products between the kernel $w$ and the submatrices of $X$ of equivalent dimensions. I have not added the biasing term, but this is not usually included in the mathematical definition of a discrete convolution.

You can see, at its core, this is simply a linear regression with a matrix of weights $w$ (this kernel matrix is the trainable set of parameters in a CNN). Therefore, we can define the gradient $\frac{\partial C}{\partial w_{k, l}}$ for all $k \times l$ parameters in the kernel.

A similar formula holds for a rank-3 tensor convolution, and in fact, I will claim that this holds for a rank-N tensor convolution. If you break it component-wise, it will always, effectively, be a linear regression.

In general...

In principle, autograd only requires that you can compute the partial derivative when you reduce a function on a tensor to its component-wise representation. This is because the autograd will utilize the chain rule, which says that, for the derivative operator $d$, the derivative of a composition of two functions is just the composition of their derivatives:

$$d(f\circ g) = df \circ dg$$

In practice, the gradients for foundational functions (polynomials, $\exp$, $+$, $\times$) are all pre-defined. Since most functions are effectively some composition of these operations/functions, during gradient computation, autograd will be able to compute the gradient for each constituent function, and then it simply has to multiply these gradient values to get the full gradient. To answer your question shortly, no function, as long as it is some composition of "fundamental functions", is too complex for autograd.

Since the simplest function in a convolution is effectively a degree-1 polynomial, performing the gradient computation is trivial for the autograd. The rank of a tensor is handled by appropriately vectorizing the backpropagation.

$\endgroup$
1
  • $\begingroup$ Wow! Considering the convolution operation as a linear regression really simplifies gradient calculations. $\endgroup$
    – Тима
    Apr 18 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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