Math for Machine Learning¶

Linear Algebra¶

Kousuke Ariga (kouariga@gmail.com, @kouariga)¶

[v1] January 17, 2018
[v2] January 18, 2019
[v3] April 10, 2019

The latest version is available here.

This notebook is meant to be a quick refresher of linear algebra and a brief introduction of NumPy (Python package for scientific computing), and it is by no means a through review. I assume that you have a prior experience of learning linear algebra such as taking an introductory course a while ago. The goal is to go over some of the important properties of matrices and showcase some of the NumPy methods through practical examples. We consider linear regression and three different solutions: algebraic, analytic, and geometric. I heavily cite and highly recommend Kolter's review notes on linear algebra [2].

Contents¶

1. Introduction
   1.1 Boston house prices dataset
   1.2 Linear regression model
2. Matrices and vectors
   2.1 Matrix
   2.2 Vector
3. Basic operations on matrices and vectors
   3.1 Matrix addition
   3.2 Scalar matrix multiplication
   3.3 Matrix vector multiplication
   3.4 Matrix matrix multiplication
4. Properties of matrices
   4.1 Linear independence
   4.2 Rank
   4.3 Inverse
   4.4 Transpose
   4.5 Span and range
   4.6 Norm
   4.7 Gradient
   4.8 Matrix calculus
   4.9 Dot products
   4.10 Projections
   4.11 Orthogonality
5. Discussion and conclusions

Appendix
A. Linear algebra visualized
B. Transpose and 1-dimensional arrays in NumPy
C. Outer products in NumPy

Reference

1. Introduction¶

Why is linear algebra important in machine learning? Machine learning methods often involves a large amount of data, and linear algebra provides a clever way to analyze and manipulate them. To make the argument concrete, let's take a look at a sample dataset.

1.1 Boston house prices dataset¶

We can load boston dataset from sklearn package, which is a very popular and easy to use machine learning package of Python. It implements many kinds of machine learning algorithms and utility functions. The loaded dataset has the following attributes.

The data and target values are stored in arrays of type numpy.ndarray. In the data array, each row corresponds to a sample, a Boston suburb or town in this example, and each column corresponds to a feature that is described above. Note that numpy.ndarray is not just multi-dimensional array (or list in Python). It implements many useful numeric methods and indexing feature. Refer to the ndarray document and indexing document for the details. Here, I show the first 10 samples, each of which consists of 13 feature values, and some of their statistics by slicing the data array.

The target values are the following. Our task here is to predict the target value, or the "median value of owner-occupied homes in $1000's" in a Boston town, given its feature values such as "per capita crime rate by town" and "average number of rooms per dwelling."

1.2 Linear regression¶

Linear regression is one of the simplest statistical models. It assumes that the target variable $y$ is explained by a weighted sum of feature values $x_1, x_2, \dots, x_n$. In an equation,

$$y_{MEDV} = w_{CRIM}x_{CRIM} + w_{ZN}x_{ZN} + \dots + w_{LSTAT}x_{LSTAT} + b$$

where $b$ is a bias term. Intuitively, $w_*x_*$ terms define the relative up/down from the standard target value. This standard value is what the bias term accounts for. You may wonder if the relationship is really that simple.

"Essentially, all models are wrong, but some are useful."

George Box, 1987

Assuming that the linear regression model is valid and we know all the weights and bias, we can estimate a median house price of a Boston town from its feature values. The bad news is that we don't know the weights... The good news is that we have training samples (a set of features and target pair)! We want to find a set of weights such that the equation holds for the training samples. To this end, we can solve systems of equations.

$$\begin{cases} y_{MEDV}^{(1)} &= w_{CRIM}x_{CRIM}^{(1)} + w_{ZN}x_{ZN}^{(1)} + \dots + w_{LSTAT}x_{LSTAT}^{(1)} + b \\ y_{MEDV}^{(2)} &= w_{CRIM}x_{CRIM}^{(2)} + w_{ZN}x_{ZN}^{(2)} + \dots + w_{LSTAT}x_{LSTAT}^{(2)} + b \\ &\, \vdots \\ y_{MEDV}^{(n)} &= w_{CRIM}x_{CRIM}^{(n)} + w_{ZN}x_{ZN}^{(n)} + \dots + w_{LSTAT}x_{LSTAT}^{(n)} + b \end{cases}$$

Great, we can solve it, ...or can we (more on this later)? Let's rewrite the equations with a better notation.

$$\begin{bmatrix} y_{MEDV}^{(1)} \\ y_{MEDV}^{(2)} \\ \vdots \\ y_{MEDV}^{(n)} \end{bmatrix} = \begin{bmatrix} x_{CRIM}^{(1)} & x_{ZN}^{(1)} & \dots & x_{LSTAT}^{(1)} & 1 \\ x_{CRIM}^{(2)} & x_{ZN}^{(2)} & \dots & x_{LSTAT}^{(2)} & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{CRIM}^{(n)} & x_{ZN}^{(n)} & \dots & x_{LSTAT}^{(n)} & 1 \end{bmatrix} \begin{bmatrix} w_{CRIM} \\ w_{ZN} \\ \vdots \\ w_{LSTAT} \\ b \end{bmatrix}$$

More simply,

$$\begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(n)} \end{bmatrix} = \begin{bmatrix} \boldsymbol{x}^{(1)} \\ \boldsymbol{x}^{(2)} \\ \vdots \\ \boldsymbol{x}^{(n)} \end{bmatrix} \boldsymbol{w}$$

or even...

$$\boldsymbol{y} = X\boldsymbol{w}$$

Yes, this is beautiful. This notation is used in linear algebra, and it is a very powerful tool given to us to tackle machine learing problems. The objective here is to find a set of weights $\boldsymbol{w}$ that solves this equation. We call this process to learn from data.

2. Matrices and vectors¶

2.1 Matrix¶

$$A= \begin{bmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \end{bmatrix} \quad A \in \mathbb{R}^{2\times3}$$

A matrix is a rectangular array of numbers. The dimension of matrix is number of rows by number of columns. $A_{ij}$ is the $i, j$ entry of $A$, which is in the $i$ th row and the $j$ th column.

2.2 Vector¶

$$\boldsymbol{y} = \begin{bmatrix} 0 \\ 2 \\ 4 \\ 6 \end{bmatrix} \quad \boldsymbol{y} \in \mathbb{R}^4$$

A vector is a $n\times 1$ matrix. Here $\boldsymbol{y}$ is said to be a 4-dimensional vector because it has 4 elements in it. $\boldsymbol{y}_i$ denotes the $i$ th element of $\boldsymbol{y}$.

3. Basic operations on matrices and vectors¶

3. 1 Matrix addition¶

$$\begin{bmatrix} 1 & 0 \\ 2 & 5 \\ 3 & 1 \end{bmatrix} + \begin{bmatrix} 4 & 0.5 \\ 2 & 5 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 0.5 \\ 4 & 10 \\ 3 & 2 \end{bmatrix}$$

The shapes have to be the same.

3.2 Scalar matrix multiplication¶

$$3\begin{bmatrix} 1 & 0 \\ 2 & 5 \\ 3 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 0 \\ 6 & 15 \\ 9 & 3 \end{bmatrix}$$

3.3 Matrix vector multiplication¶

$$A\boldsymbol{x} = \boldsymbol{y}$$

$A: m \times n$ matrix (m rows, n columns)

$\boldsymbol{x}: n \times 1$ matrix (n-dimensional vector)

$\boldsymbol{y}: m \times 1$ matrix (m-dimensional vector)

To get $y_i$, multiply $A$'s ith row with vector $x$ element-wise, then add them up.

$$\begin{bmatrix} 1 & 2 & 1 & 5 \\ 0 & 3 & 0 & 4 \\ -1 & -2 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 2 \\ 1 \end{bmatrix} = \,?$$

Hint: $\mathbb{R}^{3\times4} \times \mathbb{R}^{4\times1} = \mathbb{R}^{3\times1}$

3.4 Matrix matrix multiplication¶

$$AB = C$$

$A := l \times m$ matrix (l rows, m columns matrix)

$B := m \times n$ matrix (m rows, n columns matrix)

$C := l \times n$ matrix (l rows, n columns matrix)

$$\begin{bmatrix} 1 & 4 \\ 5 & 3 \\ 2 & 6 \end{bmatrix} \begin{bmatrix} 1 & 8 & 7 & 4 \\ 5 & 6 & 2 & 3 \end{bmatrix} = \,?$$

Hint: $\mathbb{R}^{3\times2} \times \mathbb{R}^{2\times4} = \mathbb{R}^{3\times4}$

Note $AB$ and $BA$ are not the same, i.e. matrix multiplication is NOT commutative. Actually, the latter is not necessarily defined. Check dimension.

4. Properties of matrices¶

Is linear algebra all about saving papers? Definitely NO! Do you remember terminologies such as linear independence, rank, span, etc that you learned in the linear algebra course? Did you get the ideas? Being able to calculate them is important, but understanding the concept is more (at least as) important for the purpose of this course (we can use computers for calculation after all). Let's review the properties of matrices while solving the linear regression of Boston house price. The goal is to solve the following equation.

$$\boldsymbol{y} = X\boldsymbol{w}$$

where $X\in \mathbb{R}^{m\times n}$ and $m>n$. $m$ is greater than $n$ because there are more samples than the number of features (remember rows are samples). In other words, $X$ is a vertically long matrix.

4.1 Linear independence¶

Here, let's assume that all the features (columns of $X$) are linearly independent.

A set of vectors $\{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n\}\in\mathbb{R}^m$ is said to be (linearly) independent if no vector can be represented as a linear combination of the remaining vectors. [2]

Otherwise, it is linearly dependent. For example, if we have temperature in Fahrenheit and in Celsius as two different features, the latter is represented in terms of the first as

$$F = \frac{9}{5}C + 32.$$

Such features are linearly dependent. For another example, if we have categorical features like gender, we could have two columns one for male and the other for female. For male samples we have ones in the male column and zeros in the female column, and the opposite for female samples. Did you notice that we have a linear dependence here because these features can be represented in the form

$$F = - M + 1.$$

4.2 Rank¶

For a matrix $A \in \mathbb{R}^{m\times n}$ where $m>n$, if its columns are linearly independent, it is said to be full rank. Formally,

The column rank of a matrix $A \in \mathbb{R}^{m\times n}$ is the size of the largest subset of columns of $A$ that constitute a linearly independent set. With some abuse of terminology, this is often referred to simply as the number of linearly independent columns of $A$. In the same way, the row rank is the largest number of rows of $A$ that constitute a linearly independent set.

For any matrix $A \in \mathbb{R}^{m\times n}$, it turns out that the column rank of $A$ is equal to the row rank of $A$ (though we will not prove this), and so both quantities are referred to collectively as the rank of $A$, denoted as $rank(A)$.

For $A \in \mathbb{R}^{m\times n}$, $rank(A) \leq \min(m, n)$. If $rank(A) = \min(m, n)$, then $A$ is said to be full rank. [2]

Therefore, the first statement holds.

4.3 Inverse¶

The inverse of a square matrix $A\in\mathbb{R}^{n\times n}$ is denoted $A^{-1}$, and is the unique matrix such that

$$A^{-1}A=I=AA^{-1}.$$

Note that not all matrices have inverses. Non-square matrices, for example, do not have inverses by definition. However, for some square matrices $A$, it may still be the case that $A^{-1}$ may not exist. In particular, we say that $A$ is invertible or non-singular if $A^{-1}$ exists and non-invertible or singular otherwise. In order for a square matrix $A$ to have an inverse $A^{-1}$, then $A$ must be full rank. [2]

So, again, let's assume that the columns of $X$ are linearly independent, i.e. $X$ is full rank. Here's our first attempt to solve the equation for $\boldsymbol{w}$.

The first approach (wrong)¶

$$\begin{align*} \boldsymbol{y} &= X\boldsymbol{w} \\ \boldsymbol{w} &= X^{-1}\boldsymbol{y} \end{align*}$$

Can we do this?

Remember that our $X$ is a vertically long matrix i.e. non-square, and cannot be inverted by definition.

Therefore, we can't do $\boldsymbol{w} = X^{-1}\boldsymbol{y}$.

4.4 Transpose¶

By convention, an n-dimensional vector is often thought of as a matrix with n rows and 1 column, known as a column vector. If we want to explicitly represent a row vector — a matrix with 1 row and n columns — we typically write $\boldsymbol{x}^T$. (2)

$$\boldsymbol{y} = \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \end{bmatrix} \quad\boldsymbol{y}^T = \begin{bmatrix} 0 & 1 & 2 & 3 \end{bmatrix}$$

The transpose can be generalized to matrices.

The transpose of a matrix results from "flipping" the rows and columns. Given a matrix $A\in\mathbb{R}^{m\times n}$, its transpose, written $A^T\in\mathbb{R}^{n\times m}$, is the $n\times m$ matrix whose entries are given by

$$(A^T)_{ij} = A_{ji}.$$

(2)

$$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix} \quad A^T = \begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \end{bmatrix}$$

What is the dimension of $A^TA$?

$A^TA$ is always a square matrix ($\mathbb{R}^{n\times m}\mathbb{R}^{m\times n} = \mathbb{R}^{n\times n}$). If $A$ is full rank, $A^TA$ is also invertible.

The second approach (algebraic)¶

$$\begin{align*} \boldsymbol{y} &= X\boldsymbol{w} \\ X^{T}\boldsymbol{y} &= X^{T}X\boldsymbol{w} \\ \boldsymbol{w} &= {(X^{T}X)}^{-1}X^{T}\boldsymbol{y} \end{align*}$$

Note that the second line multiplies both sides by the transpose of $X$ from the left. Then, we can solve for $\boldsymbol{w}$ because $X^TX$ is invertible.

This is a valid algebraic approach.

Why don't we get the intuition behind the solution. Consider the linear system

$$\boldsymbol{y} = X\boldsymbol{w}$$

where

$$\boldsymbol{y} = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} \quad X = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \quad \boldsymbol{w} = \begin{bmatrix} w_{1} \\ w_{2} \end{bmatrix}.$$

This equation is saying that $\boldsymbol{y}$ is a linear combination of column vectors of $X$.

$$\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} = w_1\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + w_2\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$$

However, there are no such weights.

4.5 Span¶

With linear algebra's terminology, $\boldsymbol{y}$ doesn't lie in the column space of $X$, or the space that column vectors of $X$ spans. Formally,

The span of a set of vectors $\{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n\}$ is the set of all vectors that can be expressed as a linear combination of $\{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_n\}$. That is,

$$\text{span}(\{\boldsymbol{x}_1, \dots, \boldsymbol{x}_n\}) = \Big\{\boldsymbol{v}:\boldsymbol{v}=\sum_{i=1}^{n}\alpha_{i}\boldsymbol{x}_{i}, \alpha_{i}\in\mathbb{R}\Big\}.$$

(2)

Especially, when $\boldsymbol{x}$'s are the columns of a matrix $X$, their span is said to be the range or the column space of $X$ and denoted $\mathcal{R}(X)$.

Back to the equation, although the target vector $\boldsymbol{y}$ is 3-dimensional, there are only two column vectors that span the space, i.e. the range of $X$ is just a 2-dimensional plane. Therefore, there certainly exists 3-dimensional vectors that don't lie on this plane, like the $\boldsymbol{y}$ above. Visually, it looks something like below.

But we want to represent $\boldsymbol{y}$ in terms of $\boldsymbol{x}_i$'s. The best we can do is to find a vector that lies in the range of $X$, but is also as close to $\boldsymbol{y}$ as possible.

4.6 Norm¶

This objective can be formulated by using norm by saying to find $\boldsymbol{w}$ that minimizes $||y - X\boldsymbol{w}||_2$.

A norm of a vector $\Vert x\Vert$ is informally a measure of the “length” of the vector. For example, we have the commonly-used Euclidean or $\ell_2$ norm,

$$\Vert\boldsymbol{x}\Vert_2 = \sqrt{\sum_{i=1}^nx_i^2}.$$

Note that $\Vert \boldsymbol{x}\Vert_2^2 = \boldsymbol{x}^T\boldsymbol{x}$. (2)

If you take the norm of difference of vectors, it is a measure of distance between them. There are several types of norms, but another popular one is $\ell_1$ norm. Given a vector $\boldsymbol{x}\in\mathbb{R}^n$,

$${\Vert\boldsymbol{x}\Vert}_1 = \sum_{i=0}^{n}|x_i|$$

Let's use $\ell_2$ norm as a measure of distance for now. For convinience, we can minimize the square of $\ell_2$ norm without loss of generality. To find weights that minimizes $\Vert\boldsymbol{y} - X\boldsymbol{w}\Vert_2^2$, we can take its derivative with respect to $\boldsymbol{w}$ and set to zero. Easy, right?

4.7 Gradient¶

To this end, the notion of gradient, which is a natural extension of partial derivatives to a vector setting, comes in handy.

Suppose that $f:\mathbb{R}^{m\times n} \rightarrow \mathbb{R}$ is a function that takes as input a matrix $A$ of size $m\times n$ and returns a real value. Then the gradient of $f$ (with respect to $A\in\mathbb{R}^{m\times n}$) is the matrix of partial derivatives, defined as:

$$\nabla_{A}f(A)\in\mathbb{R}^{m\times n} = \begin{bmatrix} \frac{\partial f(A)}{\partial A_{11}} & \frac{\partial f(A)}{\partial A_{12}} & \dots & \frac{\partial f(A)}{\partial A_{1n}} \\ \frac{\partial f(A)}{\partial A_{21}} & \frac{\partial f(A)}{\partial A_{22}} & \dots & \frac{\partial f(A)}{\partial A_{2n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f(A)}{\partial A_{m1}} & \frac{\partial f(A)}{\partial A_{m2}} & \dots & \frac{\partial f(A)}{\partial A_{mn}} \end{bmatrix}$$

i.e., an $m\times n$ matrix with

(∇Af(A))ij=∂f(A)