BDS 761: Data Science and Machine Learning I


drawing

Topic 6: Automatic Differentiation II: Matrix Calculus

This topic:¶

  1. Vector function Diagrammatics
  2. Matrix Calculus
  3. Applications
  • "Mathematics for Machine Learning", 2020 https://mml-book.github.io/. note: M4ML writes $\nabla_{\mathbf x} f$ for the row vector (the derivative, or Jacobian). In this lecture (and in pytorch) $\nabla_{\mathbf x} f$ is a column and $\nabla_{\mathbf x} f = \big(\frac{df}{d\mathbf x}\big)^T$.
  • https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf
  • "The Matrix Calculus You Need For Deep Learning" https://arxiv.org/abs/1802.01528

"This paper is an attempt to explain all the matrix calculus you need in order to understand the training of deep neural networks. We assume no math knowledge beyond what you learned in calculus 1...

Example Methods¶

Widely used methods, a few lines each with a modern framework.

  • Linear regression: least squares, solved by setting a gradient to zero
  • Logistic regression: no closed form, but Newton's method with a Jacobian solves it
  • PCA: maximizing a quadratic form
  • Deep learning: gradient descent aplied to wide variety of functions
In [26]:
from sklearn.datasets import load_diabetes
from sklearn.linear_model import LinearRegression

# linear regression: diabetes disease progression from 10 baseline measurements
Xd, yd = load_diabetes(return_X_y=True)
lin = LinearRegression().fit(Xd, yd)
print('R^2:', lin.score(Xd, yd))
R^2: 0.5177484222203499

Logistic regression¶

Malignant vs benign tumor from 30 features

In [27]:
from sklearn.datasets import load_breast_cancer
from sklearn.linear_model import LogisticRegression
from sklearn.preprocessing import StandardScaler

Xb, yb = load_breast_cancer(return_X_y=True)
Xb = StandardScaler().fit_transform(Xb)
logr = LogisticRegression(max_iter=1000).fit(Xb, yb)
print('Accuracy:', logr.score(Xb, yb))
Accuracy: 0.9876977152899824

PCA¶

Project the 30 tumor features onto the 2 directions of largest variance

In [28]:
from sklearn.decomposition import PCA

Z = PCA(n_components=2).fit_transform(Xb)
figure(figsize=(4, 3)); scatter(Z[:, 0], Z[:, 1], c=yb, s=8); xlabel('PC 1'); ylabel('PC 2');

Machine Mearning motivation¶

Optimize an objective function with respect to a set of desired model parameters that control how well a mathematical model explains the data.

Mathematical optimization - typically (ideally) employs gradient-based algorithms

(Jargon: Loss, Architecture, Learning, Training, ...)

drawing

"Mathematics for Machine Learning" fig. 5.2 "mind map".

Vector Functions¶

Functions¶

  • inputs $x \in \mathbb R^D$, the Domain of $f$.
  • targets (function values) $f(x)$, the image/codomain of $f$
\begin{align} f:\mathbb R^n &\rightarrow \mathbb R^m \notag \\ x &\mapsto f(x) \notag \end{align}

This says

  • $f$ is a mapping from $\mathbb R^n$ to $\mathbb R^m$
  • $f$ assigns every input vector $x$ to exactly one output vector $f(x)$

vector x enters box f along a thick arrow and f(x) leaves along a thick arrow

Domain, codomain, and image¶

The domain contains allowed inputs

the codomain specifies the output space

the image contains outputs actually attained

$$ f(\mathbb{R}^n) =\{f(\mathbf{x}):\mathbf{x}\in\mathbb{R}^n\} \subseteq\mathbb{R}^m. $$

Example¶

$$ f(\mathbf{x}) = \mathbf{x}^T\mathbf{x}, \, \mathbf{x} = (x_1,x_2)^T, \; x_i \in \mathbb R $$

What is it doing?

What are domain, codomain, and image?

Univariate function¶

\begin{align} f:\mathbb R &\rightarrow \mathbb R \notag \end{align}

Examples:

  • most functions probably: $\sin,\cos$, $\log,\ln,\exp$, $x^n, \sqrt{x},...$
  • activation functions

f maps a scalar to a scalar

Example: a univariate linear function¶

$$y = f(x) = a\,x$$

y = a x drawn with the weight a on the arrow

Diagram notation used from here on:

  • a number written on an arrow is a weight: it multiplies the value flowing along the arrow

Scalar-valued Function of Vectors¶

A vector argument is a compact notation for describing a multi-variable function.

\begin{align} f:\mathbb R^n &\rightarrow \mathbb R \notag \end{align}$$f(\mathbf x) = f_1(x_1,x_2,...,x_n)$$

f maps n inputs to one output

Example¶

\begin{align} f:\mathbb R^4 &\rightarrow \mathbb R \notag \end{align}$$f(\mathbf x) = x_1 + x_2 - x_4^2$$

What is $n$ and $\mathbf x$?

f maps n inputs to one output

Example: the Sum function¶

$$x_1+x_2+...+x_n$$

What is $\mathbf x$?

the sum function: every input arrow has weight 1

The linear function¶

\begin{align} f:\mathbb R^n &\rightarrow \mathbb R \notag \end{align}$$f(\mathbf x) = f(x_1,x_2,...,x_n) = \mathbf a^T \mathbf x = a_1x_1+a_2x_2+...+a_nx_n$$

Think of $\mathbf x$ as the variable and $\mathbf a$ as a vector of fixed parameters

the linear function a^T x with weights a_i on the arrows

Suppose both $\mathbf x$ and $\mathbf a$ were treated as inputs, what is the domain and codomain of $f(\mathbf x, \mathbf a)$ : $?? \rightarrow ??$

Linearity of linear function¶

$$f(\mathbf x) = f(x_1,x_2,...,x_n) = a^Tx = a_1x_1+a_2x_2+...+a_nx_n$$
  • $f(\mathbf x+\mathbf y) = ?$
  • $f(\alpha \mathbf x) =?$

Linearity of linear function - converse¶

any linear function $\mathbb R^n \rightarrow \mathbb R$ can be described as an inner product

Exercise: prove by using linearity assumption to expand $f(x_1 \mathbf e_1+..+x_n \mathbf e_n)$.

Affine Function¶

\begin{align} f:\mathbb R^n &\rightarrow \mathbb R \notag \\ f(\mathbf x) = \mathbf a^T \mathbf x + b, \, & \mathbf a\in \mathbb R^n, b\in \mathbb R \notag \end{align}

A linear function with an offset

affine function drawn as one linear neuron

Univariate vector-valued function $f(x)$¶

$x$ is a scalar but $f(x)$ is a vector \begin{align} f:\mathbb R &\rightarrow \mathbb R^m \notag \end{align}

$$ f(x) = \begin{pmatrix} f_1(x) \\ f_2(x) \\ \vdots \\ f_m(x) \end{pmatrix} $$

f maps one input to m outputs

Decomposability of function outputs¶

Why can we break up a vector function into scalar functions like this? It didn't work in the other direction (scalar function of vector argument).

Can't separate inputs $$f(\mathbf x) = f(x_1,x_2) = z \ne \text{some combination of } f_1(x_1) \text{ and } f_2(x_2)$$

Can separate outputs $$f(x) = \mathbf z = \begin{pmatrix} z_1 \ z_2

\end{pmatrix}¶

\begin{pmatrix} f_1(x) \\ f_2(x) \\ \end{pmatrix}

$$

Multivariate vector-valued function¶

\begin{align} f:\mathbb R^n &\rightarrow \mathbb R^m \notag \end{align}$$ f(\mathbf x) = \begin{pmatrix} f_1(\mathbf x) \\ f_2(\mathbf x) \\ \vdots \\ f_m(\mathbf x) \end{pmatrix} = \begin{pmatrix} f_1(x_1,x_2,...,x_n) \\ f_2(x_1,x_2,...,x_n) \\ \vdots \\ f_m(x_1,x_2,...,x_n) \end{pmatrix} $$

f maps n inputs to m outputs

Again note we split up the output into component functions

Recap¶

Vector notation collects multiple scalar inputs or outputs: $$ \mathbf{x}= \begin{pmatrix}x_1\\ \vdots\\ x_n\end{pmatrix}, \qquad f(\mathbf{x})= \begin{pmatrix} f_1(x_1,\ldots,x_n)\\ \vdots\\ f_m(x_1,\ldots,x_n) \end{pmatrix}. $$

....................Function type............................................ .....................Mapping........................... ....................Example.......................
Univariate, scalar-valued $\mathbb{R}\to\mathbb{R}$ $f(x)=x^2$
Multivariate, scalar-valued $\mathbb{R}^n\to\mathbb{R}$ $f(\mathbf{x})=\mathbf{a}^T\mathbf{x}$
Univariate, vector-valued $\mathbb{R}\to\mathbb{R}^m$ $f(t)=(\cos t,\sin t)^T$
Multivariate, vector-valued $\mathbb{R}^n\to\mathbb{R}^m$ $f(\mathbf{x})=A\mathbf{x}$, $A\in\mathbb{R}^{m\times n}$

Here $n$ counts input variables and $m$ counts output variables.

Diagram cases¶

the four function types

General case: vectors in, vectors out¶

vector x enters box f along a thick arrow and f(x) leaves along a thick arrow

The arrow describes a whole vector, and the box $f$ stands for all $m$ component functions $f_1,\dots,f_m$.

Deep neural networks are often drawn as chains of such boxes.

Matrix Calculus¶

Scalar function of vector argument¶

The most common vector calculus case in optimization, maximize or minimize the objective:

$$ y = f(\mathbf x) = f(x_1,x_2,...,x_n) $$

Examples: a metric, regression prediction, or classification, of the collective measurement parameters in $\mathbf x$.

This will be the most common situation in machine learning.

Partial differentiation¶

For a multi variable function $f:\mathbb R^n \rightarrow \mathbb R$, i.e. $f(x) = f(x_1,x_2,...,x_n)$,

The $n$ partial derivatives of $f$ are defined as

\begin{align} \dfrac{\partial f}{\partial x_1} &\equiv \lim_{h \rightarrow 0} \dfrac{f(x_1+h,x_2,...,x_n) - f(x_1,x_2,...,x_n)}{h} \notag \\ \vdots \notag \\ \dfrac{\partial f}{\partial x_n} &\equiv \lim_{h \rightarrow 0} \dfrac{f(x_1,x_2,...,x_n+h) - f(x_1,x_2,...,x_n)}{h} \notag \end{align}

Gradient¶

For scalar function $f(\mathbf x) = f(x_1,x_2,...,x_n)$, the gradient is the vector

$$ \nabla f(x_1,x_2,...,x_n) = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{pmatrix} $$

This gives the local slope for each dimension.

Example: if $f(x,y)$ describes the height of the ground. $\nabla f = \left[ \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right]^T$ gives the slope of the ground at every point.

What is the gradient of a function of one variable?

Example:¶

Compute the gradient of $f(x,y)=x^2y + y + 2$ with respect to $x$ and $y$ at the point $(3,4)$

Solve analytically

$$\dfrac{\partial f}{\partial x} = 2xy \;\;\;\;\;\; \dfrac{\partial f}{\partial y} = x^2 + 1$$
$$ \dfrac{\partial f}{\partial x}(3,4) = 24 \;\;\;\;\; \dfrac{\partial f}{\partial y}(3,4) = 10 $$

Example: Compute the gradient of $f(x_1,x_2) = x_1^2 x_2 + x_1 x_2^3$.

Implementing gradients¶

Implement solution manually. Requires working out analytically by hand or symbolicly, then implementing the formula.

In [29]:
def f(x,y):
    return x*x*y + y + 2

def df(x,y):
    return 2*x*y, x*x + 1

df(3, 4)
Out[29]:
(24, 10)

Solve with PyTorch

Make $x$ and $y$ tensors that track gradients, evaluate $f$, and call backward(). Autograd fills in $\partial f/\partial x$ and $\partial f/\partial y$ at the point where $f$ was evaluated.

In [30]:
x = torch.tensor(3.0, requires_grad=True)
y = torch.tensor(4.0, requires_grad=True)

f(x, y).backward()        
df_pytorch = (x.grad, y.grad)     
print(df_pytorch)  
(tensor(24.), tensor(10.))

Alternatively, torch.autograd.grad(output, inputs) returns the gradients directly, one per input, instead of storing them in .grad. The inputs must have requires_grad=True, and output must be a scalar.

In [31]:
df_pytorch = torch.autograd.grad(f(x, y), [x, y])   # same x, y as above
print(df_pytorch)
(tensor(24.), tensor(10.))

Finite-differences

In [32]:
def fd_derivative_x(f, x, y, eps=0.000001):
    df_x = (f(x + eps,y ) - f(x - eps,y))/(2 * eps)  # partial wrt x
    df_y = (f(x, y + eps) - f(x, y - eps))/(2 * eps) # partial wrt y
    return df_x, df_y

fd_derivative_x(f, 3, 4)
Out[32]:
(24.00000000335467, 9.99999999606871)

Note need another finite-difference computation for every variable, so $2n$ total. If $f(\mathbf x)$ slow to compute, this is much slower that manually implemented gradient function $g(\mathbf x) = \nabla f(\mathbf x)$ which is computed 1 time.

Directional derivative¶

The rate of change of a function in any arbitrary direction vector $\mathbf{v}$ (where $\mathbf{v}$ is a unit vector). A scalar:

$$D_{\mathbf{v}} f = \nabla f \cdot \mathbf{v} = |\nabla f| \mathbf u \cdot \mathbf v$$

In 2D case, gives slope of surface in direction $\mathbf v$

For what direction $\mathbf v$ is the directional derivative maximized? minimized?

Notation: $\nabla f$ and $\nabla_{\mathbf x} f(\mathbf x)$ are the same column vector; the subscript only names the variable. The directional derivative is written $D_{\mathbf v} f$.

Total derivative (scalar function case)¶

Direct generalization of derivative to higher dimensions.

\begin{align} \frac{d f(\mathbf x )}{d \mathbf x} = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, ..., \frac{\partial f}{\partial x_n} \right) = \nabla^T_{\mathbf x} f \notag \end{align}

Called total derivative because it is taken with respect to all variables (as opposed to partial derivative).

A.k.a, just "derivative", also denoted as $D f(\mathbf x)$ or $d f(\mathbf x)$, and in some texts (M4ML) $\nabla f(\mathbf x)$; here $\nabla f$ always means the column

Convention in this lecture: the gradient $\nabla_{\mathbf x} f$ is a column, the same shape as $\mathbf x$ (like PyTorch's .grad). The derivative $\dfrac{df}{d\mathbf x} = \nabla_{\mathbf x} f^T$ is a row, like a row of the Jacobian.

Texts differ (M4ML uses $\nabla$ for the row). Always keep in mind whether $f$ and $x$ are vectors or scalars (or matrices).

Hessian Matrix¶

A square matrix containing all second-order partial derivatives of a scalar-valued function. It describes the local curvature of the function's landscape:

$$ H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} $$

Example: $f(x,y)=x^2y + y + 2$

$$ \dfrac{\partial^2 f}{\partial x \partial x} = \dfrac{\partial (2xy)}{\partial x} = 2y $$$$ \dfrac{\partial^2 f}{\partial x \partial y} = \dfrac{\partial (2xy)}{\partial y} = 2x $$$$ \dfrac{\partial^2 f}{\partial y \partial x} = \dfrac{\partial (x^2 + 1)}{\partial x} = 2x $$$$ \dfrac{\partial^2 f}{\partial y \partial y} = \dfrac{\partial (x^2 + 1)}{\partial y} = 0 $$

Manual Implementation

A single matrix-valued function computation

In [35]:
def d2f(x, y):
    return [2*y, 2*x], [2*x, 0]

d2f(3, 4)
Out[35]:
([8, 6], [6, 0])

Higher-order derivatives with pytorch¶

In [36]:
from torch.autograd.functional import jacobian, hessian

x = torch.tensor(3.0, requires_grad=True)
y = torch.tensor(4.0, requires_grad=True)

def f_vec(v):
    x, y = v
    return x*x*y + y + 2

v0 = torch.tensor([3.0, 4.0])
print('gradient:', jacobian(f_vec, v0))   # Jacobian = total deriv in scalar case
print('Hessian:\n', hessian(f_vec, v0))   
gradient: tensor([24., 10.])
Hessian:
 tensor([[8., 6.],
        [6., 0.]])

Differentiate a derivative again in pytorch by keeping its graph

create_graph=True makes the result of torch.autograd.grad differentiable.

In [37]:
x = torch.tensor(5.0, requires_grad=True)
y = x * x

dy_dx, = torch.autograd.grad(y, x, create_graph=True)  # dy/dx = 2x, kept differentiable
d2y_dx2, = torch.autograd.grad(dy_dx, x)               # d2y/dx2 = 2

print(dy_dx, d2y_dx2)
tensor(10., grad_fn=<AddBackward0>) tensor(2.)

Multidimensional Taylor Series¶

For a scalar-valued function of a vector $\mathbf{x}$ evaluated near a point $\mathbf{a}$, the second-order Taylor expansion is $$ f(\mathbf{x}) \approx f(\mathbf{a}) + \nabla f(\mathbf{a})^T (\mathbf{x}-\mathbf{a}) + \frac{1}{2} (\mathbf{x}-\mathbf{a})^T \mathbf{H} (\mathbf{x}-\mathbf{a}) $$ Again the linear approximation is the most commonly used.

Application: Gradient Descent¶

Optimization using local linear approximation. Went from too-trivial-to-cover in optimization classes, to the current state-of-the-art due to massive data sizes and parallel computing (scalability)

To minimize an objective $L:\mathbb R^n\rightarrow\mathbb R$, use the linear Taylor approximation at the current point $\mathbf x^{(k)}$,

$$ L(\mathbf x) \approx L(\mathbf x^{(k)}) + \nabla_{\mathbf x}L(\mathbf x^{(k)})^T(\mathbf x-\mathbf x^{(k)}) $$

The gradient $\nabla_{\mathbf x}L$ is a vector in the same space as $\mathbf x$. It points in the direction of fastest increase. So step the opposite direction:

$$ \mathbf x^{(k+1)} = \mathbf x^{(k)} - \eta\,\nabla_{\mathbf x}L(\mathbf x^{(k)}), \; \eta>0 $$

By the approximation, a small step reduces $L$ by about $\eta\,\|\nabla_{\mathbf x}L\|^2$. At a minimum $\mathbf x^\ast$ the gradient is $\mathbf 0$.

the curve L(x) with tangent lines, the gradient pointing uphill on each side of the minimum, and the iterates stepping down to the minimum

What do we use for the step size $\eta$?

Application: Newton's method¶

Using the second-order Taylor expansion at $\mathbf x^{(k)}$, with gradient $\nabla_{\mathbf x}L$ and Hessian $\mathbf H$ both evaluated at $\mathbf x^{(k)}$:

$$ L(\mathbf x) \approx L(\mathbf x^{(k)}) + \nabla_{\mathbf x}L^T(\mathbf x-\mathbf x^{(k)}) + \frac{1}{2}(\mathbf x-\mathbf x^{(k)})^T\mathbf H(\mathbf x-\mathbf x^{(k)}) $$

Find the minimum of this quadratic approximation by computing its gradient using matrix calculus to get:

$$ \nabla_{\mathbf x}L + \mathbf H(\mathbf x-\mathbf x^{(k)}) $$

set this equal to $\mathbf 0$ to get

$$ \mathbf x^{(k+1)} = \mathbf x^{(k)} - \mathbf H^{-1}\nabla_{\mathbf x}L(\mathbf x^{(k)}) $$

There is no step size to choose. Each step solves an $n\times n$ linear system, which can get very expensive (if not impossible) for large $n$, but it can take far fewer steps than gradient descent.

the curve L(x) with the quadratic model at x0, whose minimum gives x1, and the iterates stepping down to the minimum

Recap: scalar function of vector inputs¶

Using partial derivatives with respect to all inputs gives the gradient - the slope of the function over all dimensions,

Using second detivatives, including pairwise combinations between dimensions, gives the curvature of the function, with respect to all dimensions.

These arise in a local Taylor series approximation to the function.

We make use of the local Taylor series in iterative methods for optimization of a scalar objective function.

Vector function of scalar argument¶

$f:\mathbb R \rightarrow \mathbb R^m $

$$ \mathbf y(t) = \begin{pmatrix} f_1(t) \\ f_2(t) \\ \vdots \\ f_m(t) \end{pmatrix} $$

Examples: a position or velocity vector that changes over time.

$$f'(t) = \dfrac{d f}{d t} = ?$$

back to fundamentals...

$$ f(t) = \begin{pmatrix} f_1(t) \\ f_2(t) \\ \vdots \\ f_n(t) \end{pmatrix} $$\begin{align} \dfrac{d f}{d t} \equiv \lim_{h \rightarrow 0} \dfrac{f(t+h) - f(t)}{h} = ? \end{align}

Derivative of vector-valued function¶

Can view as broadcasting the derivative to all elements: $$ \frac{d}{dt}f(t) = \begin{pmatrix} \frac{d}{dt} f_1(t) \\ \frac{d}{dt} f_2(t) \\ \vdots \\ \frac{d}{dt} f_m(t) \end{pmatrix} $$

Example: $f(t)$ describes position over time in space, while $f'(t)$ describe velocity vector over time.

But note the gradient is also defined as a vector in the prior case with a scalar function of vector argument. Hence we define the total derivative as a row instead. Then we can easily handle the combined case...

Gradient of multivariate vector function¶

$$f(x) = \begin{pmatrix} f_1(x_1,x_2) \\ f_2(x_1,x_2) \\ \end{pmatrix}$$

What is $\dfrac{df}{dx}$?

$$ \dfrac{df}{dx} = \begin{pmatrix} \nabla_x^T f_1 \\ \nabla_x^T f_2 \\ \end{pmatrix} = \begin{pmatrix} \dfrac{\partial f_1}{\partial x_1} & \dfrac{\partial f_1}{\partial x_2} \\ \dfrac{\partial f_2}{\partial x_1} & \dfrac{\partial f_2}{\partial x_2} \\ \end{pmatrix} $$

Jacobian Matrix: for vector-valued function of vector argument¶

As with vector-valued function of scalar argument, we take the derivative of each component function, now in terms of the vector argument $\mathbf x$ instead of $t$.

\begin{align} \frac{d f(\mathbf x )}{d \mathbf x} = \begin{pmatrix}\nabla^T_{\mathbf x} f_1\\ \nabla^T_{\mathbf x} f_2\\ \vdots \\ \nabla^T_{\mathbf x} f_m\end{pmatrix} = \begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & ... & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & ... & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & & \vdots \\ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} & ... & \frac{\partial f_m}{\partial x_n} \end{pmatrix} = \mathbf J \notag \end{align}

Example: vector fields in physics (gravity, electric field), regression model which predicts a location.

Vector Calculus cases¶

$x\in\mathbb{R}^n$, $y\in\mathbb{R}^m$

....Output....... ..........Input..... ..........Derivative... ..................................Example.............................
Scalar Scalar $\dfrac{df}{dx}$ $f(x)=x^2 \implies 2x$
Scalar Vector $\dfrac{df}{d\mathbf x}=\nabla^T f$ $f(\mathbf x)=x_1^2 + x_2^2 \implies \begin{pmatrix}2x_1,& 2x_2\end{pmatrix}$
Vector Scalar $\dfrac{dy}{dt}$ $\mathbf y(t)=\begin{pmatrix}t^2\\3t-t^3\end{pmatrix} \implies \begin{pmatrix}2t\\3-3t^2\end{pmatrix}$
Vector Vector $J_{ij}=\frac{\partial y_i}{\partial x_j}$ $\mathbf y=\begin{pmatrix}x_1^2\\x_1x_2\end{pmatrix} \implies \begin{pmatrix}2x_1 & 0\\ x_2 & x_1\end{pmatrix}$

Note the gradient is a column vector, while the derivative of a scalar-valued function with respect to a vector is a row vector ($\nabla_x f^T$).

Dimensionality of derivative of $f$¶

Basically, the dimensionality of $f$ in rows and the dimensionality of $x$ in columns

drawing
drawing

$\mathbf J = \dfrac{df(\mathbf x)}{d\mathbf x}$: the derivative of a vector function, with row $i$ equal to $\nabla^T f_i$.

Example¶

$$ f(x) = Ax = \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22}\\ \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ \end{pmatrix} $$

What is $\dfrac{df(x)}{dx}$?

General case¶

Matrix-vector product where $A$ is $m \times n$

$$ \frac{d}{d \mathbf x} (\mathbf A \mathbf x) = ? $$

Jacobian in pytorch¶

For a vector valued function $\mathbf y(\mathbf x)$ with elements $y_i(\mathbf x)$, where $\mathbf x$ has elements $x_j$, the Jacobian is a matrix with $J_{ij} = \dfrac{\partial y_i}{\partial x_j}$.

Plan A: We could build it one row at a time with torch.autograd.grad(y[i], x)

Plan B: use torch.autograd.functional.jacobian, which does this for us.

Exercise: Compute the gradient of $\mathbf A \mathbf x$ for a small system with pytorch.

"Linear" Neural-network layer¶

Affine function of inputs. Also called a Dense layer and fully-connected layer.

3x3 linear layer y = Wx + b with all weights and biases labeled

Describe this as a function $f(\mathbf x)$. What is the output vector $\mathbf y$ as a function of $\mathbf x$? What is the Jacobian of $f$?

Suppose you made a linear neural network with the above layer. How would you train it (i.e., chooose $W_{ij}$ and $b_i$)?

linear layer docs

https://docs.pytorch.org/docs/main/nn.html#linear-layers

In [ ]:
import torch

A = torch.tensor([[1., 2., 3.],
                  [4., 5., 6.]]) 
         
x = torch.tensor([1., 0., -1.])           

# nn.Linear(in, out) computes y = x@A^T + b = (A@x + b).T

layer = torch.nn.Linear(3, 2, bias=False) # weight has shape (out, in) = A's shape
with torch.no_grad():
    layer.weight.copy_(A)                 

y = layer(x)

print(y)                                  
print(A @ x)                              
tensor([-2., -2.], grad_fn=<SqueezeBackward4>)
tensor([-2., -2.])

Useful Matrix Calculus Identities¶

drawing

from "The Matrix cookbook" via M4ML

Nonlinear Example: activation function¶

A scalar activation function which is applied elementwise

\begin{align} \boldsymbol{\sigma}(\mathbf x) = \begin{pmatrix}\sigma(x_1)\\ \sigma(x_2)\\ \vdots \\ \sigma(x_n)\end{pmatrix} \end{align}
\begin{align} \frac{\partial \boldsymbol{\sigma}}{\partial \mathbf x} = \begin{pmatrix} \frac{\partial}{\partial x_1}\sigma(x_1) & \frac{\partial}{\partial x_2}\sigma(x_1) & ... & \frac{\partial}{\partial x_n}\sigma(x_1) \\ \frac{\partial}{\partial x_1}\sigma(x_2) & \frac{\partial}{\partial x_2}\sigma(x_2) & ... & \frac{\partial}{\partial x_n}\sigma(x_2) \\ \vdots & \vdots & & \vdots \\ \frac{\partial}{\partial x_1}\sigma(x_n) & \frac{\partial}{\partial x_2}\sigma(x_n) & ... & \frac{\partial}{\partial x_n}\sigma(x_n) \end{pmatrix} = \begin{pmatrix} \sigma^\prime(x_1) & 0 & ... & 0 \\ 0 & \sigma^\prime(x_2) & ... & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & ... & \sigma^\prime(x_n) \end{pmatrix} \end{align}

Ex: Assume $\sigma(x)$ is a basic ReLU()

What is the output $\sigma(\mathbf x)$ and its Jacobian for x=[1, -2, 5]

Nonlinear example: softmax¶

Multiclass classifiers turn a vector of scores $\mathbf z\in\mathbb R^K$ into probabilities

$$p_i = \operatorname{softmax}(\mathbf z)_i = \frac{e^{z_i}}{\sum_{k=1}^K e^{z_k}}$$

Unlike an elementwise activation, every output depends on every input, so the Jacobian is not diagonal:

$$\frac{\partial p_i}{\partial z_j} = p_i(\delta_{ij} - p_j) \quad\Rightarrow\quad \mathbf J = \operatorname{diag}(\mathbf p) - \mathbf p\mathbf p^T$$

Exercise: derive this with the quotient rule, for the cases $i=j$ and $i\ne j$.

In [ ]:
from torch.autograd.functional import jacobian

z = torch.tensor([1.0, 2.0, 0.5])
p = torch.softmax(z, dim=0)

J_autograd = jacobian(lambda z: torch.softmax(z, dim=0), z)
print(J_autograd)


J_formula = torch.diag(p) - torch.outer(p, p)
print('\n',J_formula)
tensor([[ 0.1778, -0.1453, -0.0324],
        [-0.1453,  0.2335, -0.0881],
        [-0.0324, -0.0881,  0.1206]])

 tensor([[ 0.1778, -0.1453, -0.0324],
        [-0.1453,  0.2335, -0.0881],
        [-0.0324, -0.0881,  0.1206]])

Chain Rule¶

Motivation: Deep neural networks¶

A 10-layer network (i.e. pretty small one) will implement a function:

$$f_{9}\Big(f_{8}\big(f_{7}(...f_1(f_0(x)))\big)\Big)$$

We use automated applications of the chain rule to optimize these. We can compute its derivative from the derivatives (Jacobians) of each function individually.

a deep network as a composition of functions followed by a loss

Rules of (multivariate) partial differentiation¶

Scalar rules can be extended if careful. Must maintain order now that we are dealing with vectors, matrix multiplication is not commutative in general.

Product rule $\dfrac{d}{dx}\big(f(x)g(x)\big) = \dfrac{df}{dx}\,g(x)+f(x)\,\dfrac{dg}{dx}$

Sum rule $\dfrac{d}{dx}\big(f(x)+g(x)\big) = \dfrac{df}{dx}+\dfrac{dg}{dx}$

Chain rule $\dfrac{d}{dx}\, g\big(f(x)\big) = \dfrac{dg}{df}\,\dfrac{df}{dx}$

When the derivatives are vectors or matrices, the product is a matrix product, taken in the order of the composition. In gradient (column) form the chain rule reads in reverse, as in transposing a product $\nabla_x\, g\big(f(x)\big) = \big(\frac{df}{dx}\big)^T\nabla_f\, g$.

Example¶

Chain rule for $f(x(t))$, where $x \in \mathbb R^2$ and $t \in \mathbb R$

$f(x(t)) = f(x_1(t),x_2(t))$

  • Chain rule $\dfrac{d}{dt}\, f\big(x(t)\big) = \dfrac{df}{dx}\,\dfrac{dx}{dt}$

Key question, what kind of function is "$x(t)$" here, $\mathbb R^? \rightarrow \mathbb R^?$

Answer: a vector function with a scalar argument. $$x(t) = \begin{pmatrix} x_1(t) \\ x_2(t) \\ \end{pmatrix} $$

Therefore, for first term in $\dfrac{df}{dx}\,\dfrac{dx}{dt}$,

$$\dfrac{df}{dx} =?$$
$$\dfrac{df}{dx} = \left[\dfrac{\partial f}{\partial x_1},\dfrac{\partial f}{\partial x_2}\right] = \nabla_x^T f$$

For second term in $\dfrac{df}{dx}\,\dfrac{dx}{dt}$, we have

$$\dfrac{dx}{dt}=?$$
$$ \dfrac{dx}{dt} = \begin{pmatrix} \dfrac{d x_1(t)}{dt} \\ \dfrac{d x_2(t)}{dt} \\ \end{pmatrix} $$

Finally, what is the net result $\dfrac{df}{dx}\,\dfrac{dx}{dt}$?

$$\left[\dfrac{\partial f}{\partial x_1},\dfrac{\partial f}{\partial x_2}\right] \begin{pmatrix} \dfrac{d x_1(t)}{dt} \\ \dfrac{d x_2(t)}{dt} \\ \end{pmatrix} = \dfrac{\partial f}{\partial x_1}\dfrac{d x_1}{dt} + \dfrac{\partial f}{\partial x_2}\dfrac{d x_2}{dt}$$

Example¶

  • $f(x_1,x_2) = x_1^2+2x_2$
  • $x_1 = \sin t$
  • $x_2 = \cos t$

Compute derivative of $f$ wrt $t$ at the point $t = 0$

Composition of multivariate vector function¶

Consider $f(x(s))$, where $x(s) = \begin{pmatrix} x_1(s) \\ x_2(s) \\ \end{pmatrix} $, and $s = \begin{pmatrix} s_1 \\ s_2 \\ \end{pmatrix}$

$$\dfrac{df}{ds} = \dfrac{df}{dx}\,\dfrac{dx}{ds} =?$$

$\dfrac{df}{ds} = \dfrac{df}{dx}\,\dfrac{dx}{ds} =?$

Easy part: $\dfrac{df}{dx} = ?$

($f$ is a scalar function)

$\dfrac{df}{ds} = \dfrac{df}{dx}\,\dfrac{dx}{ds} =?$

Hard part: $\dfrac{dx}{ds}=?$

(Both $x$ and $s$ are 2D vectors).

Putting it together...¶

$$\dfrac{df}{ds} = \dfrac{df}{dx}\,\dfrac{dx}{ds} =?$$

Example¶

$$f(x) = \exp(x_1x_2^2)$$$$x(t) = \begin{pmatrix} x_1(t) \\ x_2(t) \\ \end{pmatrix} = \begin{pmatrix} t \cos t \\ t \sin t \\ \end{pmatrix} $$

Example: composition of two linear layers¶

Two linear layers in sequence, with no activation in between ($\mathbf W_1$ is $h\times n$, $\mathbf W_2$ is $m\times h$): $$ \mathbf z = \mathbf W_1\mathbf x + \mathbf b_1, \qquad \mathbf y = \mathbf W_2\mathbf z + \mathbf b_2 $$

Chain rule: the Jacobian of the composition is the product of the Jacobians, in composition order, $$ \frac{d\mathbf y}{d\mathbf x} = \frac{d\mathbf y}{d\mathbf z}\,\frac{d\mathbf z}{d\mathbf x} = \mathbf W_2\,\mathbf W_1 $$ Note sizes work out $(m\times h)(h\times n) = m\times n$

Substituting $\mathbf z$ into $\mathbf y$

$$ \mathbf y = (\mathbf W_2\mathbf W_1)\,\mathbf x + (\mathbf W_2\mathbf b_1 + \mathbf b_2) = \mathbf W'\mathbf x + \mathbf b' $$

There is no functional benefit from a deep network of purely linear layers.

In [79]:
from torch.autograd.functional import jacobian

torch.manual_seed(0)
layer1 = torch.nn.Linear(3, 4)
layer2 = torch.nn.Linear(4, 2)

def f(x):
    y = layer2(layer1(x))  # y = W2 (W1 x + b1) + b2
    return y

x = torch.randn(3)
J = jacobian(f, x)
print(J, '\n\n', layer2.weight @ layer1.weight)
tensor([[-0.1577, -0.1227, -0.0054],
        [-0.1189, -0.1485, -0.0592]]) 

 tensor([[-0.1577, -0.1227, -0.0054],
        [-0.1189, -0.1485, -0.0592]], grad_fn=<MmBackward0>)

Example: a single layer with activation¶

A linear layer followed by an activation function $\sigma$ applied element-wise to each output: $$ \mathbf z = \mathbf W\mathbf x + \mathbf b, \qquad \mathbf y = \boldsymbol\sigma(\mathbf z) $$

3x3 nonlinear layer: the linear layer's sums z_i each pass through an activation node sigma to give y_i

The layer is a composition, so its Jacobian is the product of the two Jacobians we already have, in composition order: $$ \frac{d\mathbf y}{d\mathbf x} = \frac{d\mathbf y}{d\mathbf z}\,\frac{d\mathbf z}{d\mathbf x} = \underbrace{\begin{pmatrix}\sigma'(z_1) & 0 & 0\\ 0 & \sigma'(z_2) & 0\\ 0 & 0 & \sigma'(z_3)\end{pmatrix}}_{\text{activation}}\ \underbrace{\mathbf W}_{\text{linear}}, \qquad \frac{\partial y_i}{\partial x_j} = \sigma'(z_i)\,W_{ij} $$

Later: For a scalar $L$ computed from $\mathbf y$, the gradient is the transpose, so the order reverses: first the activation Jacobian, then the linear one, $$ \nabla_{\mathbf x}L = \Big(\frac{d\mathbf y}{d\mathbf x}\Big)^T\nabla_{\mathbf y}L = \mathbf W^T\,\mathrm{diag}\big(\sigma'(\mathbf z)\big)\,\nabla_{\mathbf y}L $$ Working backward from $L$ one layer at a time like this is backpropagation.

Applications¶

Least Squares Linear regression¶

Take the derivative of the least-squares "loss" and set it equal to zero

\begin{align} L(\boldsymbol\beta) &= \Vert\mathbf y - \mathbf X\boldsymbol\beta\Vert_2^2 \notag \\ & = (\mathbf y - \mathbf X\boldsymbol\beta)^T(\mathbf y - \mathbf X\boldsymbol\beta) \notag \\ &= \mathbf y^T \mathbf y + \boldsymbol\beta^T \mathbf X^T \mathbf X \boldsymbol\beta -2 \boldsymbol\beta ^T \mathbf X \mathbf y \notag \\ \end{align}

Compute the gradient using matrix calculus

$$\nabla_{\boldsymbol\beta} L = -2\mathbf X^T(\mathbf y - \mathbf X\boldsymbol\beta)$$

Setting the gradient to zero gives the normal equations $$ \mathbf X^T\mathbf X\boldsymbol\beta = \mathbf X^T\mathbf y $$

Solving directly gives the pseudoinverse.

In [80]:
from sklearn.datasets import load_diabetes
from sklearn.linear_model import LinearRegression

X, y = load_diabetes(return_X_y=True)
X1 = np.column_stack([np.ones(len(X)), X])     # column of ones for the intercept

beta = np.linalg.solve(X1.T @ X1, X1.T @ y)    # normal equations

lin = LinearRegression().fit(X, y)
print('intercept:', beta[0], lin.intercept_, '  coefficients:', beta[1:], lin.coef_)
intercept: 152.13348416289597 152.13348416289597   coefficients: [ -10.0098663  -239.81564367  519.84592005  324.3846455  -792.17563855
  476.73902101  101.04326794  177.06323767  751.27369956   67.62669218] [ -10.0098663  -239.81564367  519.84592005  324.3846455  -792.17563855
  476.73902101  101.04326794  177.06323767  751.27369956   67.62669218]

PCA¶

Data $\mathbf X$ ($N$ patients $\times$ $D$ features), centered so each column has mean zero. Summarize each patient by one number, a linear score of the features with weights $\mathbf w\in\mathbb R^D$:

$$s_i = \mathbf x_i^T\mathbf w = w_1 x_{i1} + \cdots + w_D x_{iD}, \qquad \mathbf s = \mathbf X\mathbf w$$

A score that is nearly the same for every patient tells us nothing; a good one should spread the patients out.

Choose $\mathbf w$ to maximize the variance of the scores.

Because the features are centered, so are the scores

$$ \bar s = \bar{\mathbf x}^T\mathbf w = \mathbf 0^T \mathbf w = 0 $$

So the variance is the mean square:

$$\operatorname{Var}(s) = \frac1N\sum_i s_i^2 = \frac1N\,\mathbf s^T\mathbf s = \frac1N(\mathbf X\mathbf w)^T(\mathbf X\mathbf w) = \mathbf w^T\Big(\underbrace{\tfrac1N\mathbf X^T\mathbf X}_{\boldsymbol\Sigma}\Big)\mathbf w$$

$\boldsymbol\Sigma$ is the covariance matrix of the features. The variance of the score is a quadratic form in $\mathbf w$

PCA (cont)¶

The first principal direction is the unit vector that captures the most variance:

$$\max_{\mathbf w}\; \mathbf w^T\boldsymbol\Sigma\mathbf w \quad\text{subject to}\quad \mathbf w^T\mathbf w = 1$$

The scale of $\mathbf w$ is meaningless (the relative contribution of features is what matters), so we chose $\Vert\mathbf w\Vert = 1$

Lagrangian: $$\mathcal L(\mathbf w,\lambda) = \mathbf w^T\boldsymbol\Sigma\mathbf w - \lambda(\mathbf w^T\mathbf w - 1)$$

Using $\nabla_{\mathbf w}(\mathbf w^T\mathbf A\mathbf w) = (\mathbf A + \mathbf A^T)\mathbf w$ from matrix calculus, plus the symmetry of $\boldsymbol\Sigma$:

$$\nabla_{\mathbf w}\mathcal L = 2\boldsymbol\Sigma\mathbf w - 2\lambda\mathbf w = 0 \quad\Rightarrow\quad \boldsymbol\Sigma\mathbf w = \lambda\mathbf w$$

So $\mathbf w$ is an eigenvector of $\boldsymbol\Sigma$. The variance it captures is $\mathbf w^T\boldsymbol\Sigma\mathbf w = \lambda\,\mathbf w^T\mathbf w = \lambda$, largest for the top eigenvalue. The second principal direction maximizes the same variance among unit vectors orthogonal to the first, and so on down the eigenvalues.

In [47]:
from sklearn.datasets import load_breast_cancer
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA

X = StandardScaler().fit_transform(load_breast_cancer().data)   # centered (and scaled)
Sigma = X.T @ X / X.shape[0]

evals, evecs = np.linalg.eigh(Sigma)   # eigenvalues in ascending order
w = evecs[:, -1]                       # eigenvector of the largest eigenvalue

pc1 = PCA(n_components=1).fit(X).components_[0]
#print(abs(w @ pc1))
print('variance captured:', w @ Sigma @ w, '  top eigenvalue:', evals[-1])
variance captured: 13.281607682257905   top eigenvalue: 13.281607682257917

Ridge regression¶

Add the penalty $\lambda\Vert\boldsymbol\beta\Vert_2^2$. The gradient gains a $2\lambda\boldsymbol\beta$ term, so

$$(\mathbf X^T\mathbf X + \lambda\mathbf I)\boldsymbol\beta = \mathbf X^T\mathbf y$$

scikit-learn does not penalize the intercept, so center $\mathbf X$ and $\mathbf y$ and leave the intercept out of the penalized system.

Logistic regression¶

logistic regression as an affine function followed by the sigmoid

An affine function followed by the sigmoid, $\mathbb R^n\to\mathbb R\to(0,1)$. It is a composition, so the chain rule gives how $p$ changes with $\mathbf w$.

Fitting logistic regression: observed = expected¶

Each patient gets a predicted probability $p_i = \sigma(\mathbf x_i^T\mathbf w)$ of the outcome (here, a malignant tumor), and we observe $y_i\in\{0,1\}$.

A practical requirement, the same observed-versus-expected check used for any clinical risk score: the model should predict as many cases as were observed, in total and weighted by each feature,

$$\mathbf u(\mathbf w) = \mathbf X^T(\mathbf y - \mathbf p) = \mathbf 0$$

one equation per column of $\mathbf X$. The column of ones gives $\sum_i y_i = \sum_i p_i$: total observed cases = total expected cases.

Solving with Newton's method¶

$\mathbf u$ is a vector-valued function of $\mathbf w$, and nonlinear because of $\sigma$, so there is no closed form. Linearize with its Jacobian and solve for the step: $\mathbf u(\mathbf w+\boldsymbol\Delta)\approx\mathbf u(\mathbf w)+\mathbf J\boldsymbol\Delta=\mathbf 0$.

By the chain rule, with the diagonal Jacobian of the elementwise sigmoid,

$$\mathbf J = \frac{\partial\mathbf u}{\partial\mathbf w} = -\mathbf X^T\frac{\partial\mathbf p}{\partial\mathbf w} = -\mathbf X^T\mathbf S\mathbf X,\qquad \mathbf S = \operatorname{diag}\big(p_i(1-p_i)\big)$$$$\mathbf w \leftarrow \mathbf w + (\mathbf X^T\mathbf S\mathbf X)^{-1}\mathbf X^T(\mathbf y-\mathbf p)$$

Each step is a weighted least-squares solve, so statisticians call this iteratively reweighted least squares (IRLS). The weight $p_i(1-p_i)$ is the variance of patient $i$'s 0/1 outcome: patients whose outcome is least certain ($p_i$ near 0.5) count the most.

In [ ]:
from sklearn.datasets import load_breast_cancer
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression

Xb, yb = load_breast_cancer(return_X_y=True)
ym = 1 - yb                                      # 1 = malignant (scikit-learn codes benign as 1)
Xb = StandardScaler().fit_transform(Xb)[:, :5]   # 5 features: all 30 nearly separate the classes and the fit diverges
X1 = np.column_stack([np.ones(len(Xb)), Xb])

sigmoid = lambda z: 1 / (1 + np.exp(-z))

w = np.zeros(X1.shape[1])
for it in range(10):                             # Newton's method on u(w) = X^T (y - p) = 0
    p = sigmoid(X1 @ w)
    u = X1.T @ (ym - p)                          # observed minus expected, one entry per column of X
    XtSX = X1.T @ (X1 * (p * (1 - p))[:, None])  # -Jacobian of u, without forming the N x N matrix S
    w = w + np.linalg.solve(XtSX, u)
    print(it, f'observed cases {ym.sum()}, expected {p.sum():.2f}, |u| = {np.linalg.norm(u):.2e}')

logr = LogisticRegression(penalty=None).fit(Xb, ym) # scikit learn version
w, np.r_[logr.intercept_, logr.coef_[0]]
0 observed cases 212, expected 284.50, |u| = 3.85e+02
1 observed cases 212, expected 226.59, |u| = 1.11e+02
2 observed cases 212, expected 215.64, |u| = 4.26e+01
3 observed cases 212, expected 211.94, |u| = 1.62e+01
4 observed cases 212, expected 211.07, |u| = 6.13e+00
5 observed cases 212, expected 211.52, |u| = 2.06e+00
6 observed cases 212, expected 211.94, |u| = 2.87e-01
7 observed cases 212, expected 212.00, |u| = 5.79e-03
8 observed cases 212, expected 212.00, |u| = 2.39e-06
9 observed cases 212, expected 212.00, |u| = 3.90e-13
/opt/venv/lib/python3.12/site-packages/sklearn/linear_model/_logistic.py:1381: FutureWarning: 'penalty' was deprecated in version 1.8 and will be removed in 1.10. To avoid this warning, leave 'penalty' set to its default value and use 'l1_ratio' or 'C' instead. Use l1_ratio=0 instead of penalty='l2', l1_ratio=1 instead of penalty='l1', l1_ratio set to a float between 0 and 1 instead of penalty='elasticnet', and C=np.inf instead of penalty=None.
  warnings.warn(
Out[ ]:
(array([  0.45924555, -22.09485226,   1.56463237,  14.7403169 ,
         14.68921315,   1.66460148]),
 array([  0.46112047, -22.09209605,   1.56528365,  14.72348074,
         14.70887019,   1.66571615]))

Recap¶

  • The gradient $\nabla_{\mathbf x} f$ of a scalar function is a column, the same shape as $\mathbf x$; it points in the direction of fastest increase
  • The derivative $\dfrac{df}{d\mathbf x}$ is a row; for a vector function it is the Jacobian, with rows for the output functions and columns for the input variables
  • Chain rule: multiply the derivatives (Jacobians) in the order of the composition; the gradient is the transpose of the derivative

Backpropagation and Automatic Differentiation¶

see also

  • http://timvieira.github.io/blog/post/2017/08/18/backprop-is-not-just-the-chain-rule/
  • https://people.cs.umass.edu/~domke/courses/sml2011/08autodiff_nnets.pdf