In this article, I shall go over the topic of arriving at the Vectorized Gradient-Descent formulae for the Cost function of the for Matrix form of training-data Equations. And along with that the Fundamentals of Calculus (especially Partial Derivative) and Matrix Derivatives necessary to understand the process.

So our target of this article is to understand the full Mathematics and the flow behind arriving at the below formulae, which is the Vectorized Gradient of the training-data Matrix

First a Refresher on basic Matrix Algebra

A matrix A over a field K or, simply, a matrix A (when K is implicit) is a rectangular array of scalars usually presented in the following form:

The rows of such a matrix A are the m horizontal lists of scalars:

and the columns of A are the n vertical lists of scalars:

A matrix with m rows and n columns is called an m by n matrix, written m*n. The pair of numbers m and n is called the size of the matrix. Two matrices A and B are equal, written A = B, if they have the same size and if corresponding elements are equal. Thus, the equality of two m * n matrices is equivalent to a system of mn equalities, one for each corresponding pair of elements. A matrix with only one row is called a row matrix or row vector, and a matrix with only one column is called a column matrix or column vector. A matrix whose entries are all zero is called a zero matrix and will usually be denoted by 0.

Matrix Multiplication

The below image is taken from Khan Academy’s excellent linear algebra course.

In above, each entry in the product matrix is the dot product of a row in the first matrix and a column in the second matrix

More explanation for higher dimension case — If the product AB = C is defined, where C is denoted by [cij], then the element cij is obtained by multiplying the elements in the ith row of A by the corresponding elements in the jth column of B and adding. Thus, if A has order k * n, and B has order n * p then

There are four simple rules that will help us in multiplying matrices, listed here

1. Firstly, we can only multiply two matrices when the number of columns in

matrix A is equal to the number of rows in matrix B.

2. Secondly, the first row of matrix A multiplied by the first column of matrix B

gives us the first element in the matrix AB, and so on.

3. Thirdly, when multiplying, order matters — specifically, AB ≠ BA.

4. Lastly, the element at row i, column j is the product of the ith row of matrix A and the jth column of matrix B.

The order in which we multiply matters. We must keep the matrices in order, but we do have some flexibility. As we can see in the following equation, the parentheses can be moved:

Implementing a dot production with numpy

this will create integer as array-elements

import numpy as np

A = np.random.randint(10, _size_=(2,3))
B = np.random.randint(10, _size_=(3,2))

This will create 2 Matrices as below e.g.
[[9 0 8] [3 5 5]]

[[5 2]
 [0 7]
 [0 7]
]

print(np.dot(A, B))

# Output
[[45 74]
[15 76]]

The Hadamard Product — Other Kinds of Matrix Multiplication

Hadamard multiplication is defined for matrices of the same shape as the multiplication of each element of one matrix by the corresponding element of the other matrix. Hadamard multiplication is often denoted by as below, for two matrices A(n×m) and B(n×m) we have

So in general Mathematic form for the single independent variable case

Multiple Linear Regression (MLR)

Suppose that the response variable Y and at least one predictor variable xi are quantitative. Then the equation for a specific Y value under the MLR model is

And now in matrix notation, these n sets of equations become

where Y is the vector of the response variable and is an n × 1 vector of dependent variables, X is the matrix of the k independent/explanatory variables (usually the first column is a column of ones for the constant term) and is an n × p matrix of predictors, β is a p × 1 vector of unknown coefficients, and e is an n × 1 vector of unknown errors. Equivalently,

Where Y : is output vector for n training examples. X : is matrix of size n*p where each ith row belongs to ith training set. β : is weight vector of size p for p training features.

Different types of Matrix Differentiation

1-Differentiation with Respect to a Scalar

Differentiation of a structure (vector or matrix, for example) with respect to a scalar is quite simple; it just yields the ordinary derivative of each element of the structure in the same structure. Thus, the derivative of a vector or a matrix with respect to a scalar variable is a vector or a matrix, respectively, of the derivatives of the individual elements.

1.A-Derivatives of Vectors with Respect to Scalars

The derivative of the vector y(x) = (y1 , . . . , yn ) with respect to the scalar x is the vector

The second or higher derivative of a vector with respect to a scalar is likewise a vector of the derivatives of the individual elements; that is, it is an array of higher rank.

1.B-Derivatives of Matrices with Respect to Scalars

The derivative of the matrix Y(x) defined as below

The second or higher derivative of a matrix with respect to a scalar is likewise a matrix of the derivatives of the individual elements.

1.C — Derivatives of Functions with Respect to Scalars

Differentiation of a function of a vector or matrix that is linear in the elements of the vector or matrix involves just the differentiation of the elements, fol- lowed by application of the function. For example, the derivative of a trace of a matrix is just the trace of the derivative of the matrix. On the other hand, the derivative of the determinant of a matrix is not the determinant of the derivative of the matrix

1.D — Higher-Order Derivatives with Respect to Scalars

Because differentiation with respect to a scalar does not change the rank of the object (“rank” here means rank of an array or “shape”), higher-order derivatives

if those derivatives exist. This vector is called the gradient of the scalar-valued function, and is sometimes denoted by ∇f (x)

2.B — Derivatives of Vectors with Respect to Vectors; The Jacobian

The derivative of an m-vector-valued function of an n-vector argument consists of nm scalar derivatives. These derivatives could be put into various structures. Two obvious structures are an n × m matrix and an m × n matrix.

For a function,

if those derivatives exist. This derivative is called the matrix gradient and is denoted by ∇f for the vector-valued function f . (Note that the ∇ symbol can denote either a vector or a matrix, depending on whether the function being differentiated is scalar-valued or vector-valued.)

The m × n matrix is called the Jacobian of f and is denoted by Jf as below

So we have m = n functions and parameters, in this case. Generally speaking, though, the Jacobian matrix is the collection of all m × n possible partial derivatives (m rows and n columns), which is the stack of m gradients with respect to x:

So if we are predicting house-price with the above MLR equation, then _θ_0 will be the basic/base price of a house, then _θ_1 as the price per room, _θ_2 as the price per KM-distance from the nearest Airport.

Using the definition of matrix multiplication, our multivariate hypothesis function can be concisely represented as:

So now the Cost function takes the following form

Where the thetas θ are the weights, and the above partial derivative for any weights wj will be as below

So the Gradient-Descent process for Multivariate case becomes

And that's why we take the transpose of θ to multiply with column-vector x to get the hypothesis (as earlier mentioned in this article)

Refresher — Matrix-Derivative Identities required for the Mathematical Derivation of the Gradient of a Matrix w.r.t. to Vectors

The derivative of a matrix is usually referred to as the gradient and denoted as ∇. Consider a function

---

Matrix Transpose Identities

Because of the associativity of matrix multiplication, this relation can be extended as

Now proceed to find the Gradient of the Cost function.

First a Refresher on the Gradient Descent Algorithm

To implement Gradient Descent, you need to compute the gradient of the cost function with regard to each model parameter θj. In other words, you need to calculate how much the cost function will change if you change θj just a little bit. This is called a partial derivative. It is like asking “What is the slope of the mountain under my feet if I face east?”. and then asking the same question facing north.

Now you would recognize the very well-known cost function

Notice that this formula involves calculations over the full training set X, at each Gradient Descent step! This is why the algorithm is called Batch Gradient Descent: it uses the whole batch of training data at every step.

Once you have the gradient vector, which points uphill, just go in the opposite direction to go downhill. This means subtracting ∇θMSE(θ) from θ. This is where the learning rate η comes into play:5 multiply the gradient vector by η to determine the size of the downhill step

Where Y : is output vector for n training examples. X : is matrix of size n*p where each ith row belongs to ith training set. β : is weight vector of size p for p training features.

Note that β in the above is not a scalar, but a vector.

Now we have the RSS defined as

Then for the following assumption

Then for the whole matrix (i.e. the whole set of training data set or the whole set of Hypothesis Equation ), we will get

Which in the final Vector form

Note, that in the last equality, I had to get the Transpose of X because when doing matrix multiplication — that's a dot product of rows of the first matrix to columns of the second matrix. The number of columns of the 1st matrix must equal the number of rows of the 2nd matrix.

So by transposing the _p-_th column of X ends up being the _p-_th row of the X-Transposed. Thus, when doing a dot product between the p-th row of X-Transposed with (y — Xβ) it will match perfectly as I am using all of the entries of the _p-_th column of X

Alternative-2 — And below is an alternative calculation for arriving at the same Vectorized Gradient formulae for training-data in Matrix form.

Here, I am denoting the coefficients with θ or Theta (instead of β that we used above in our Alternative-1 Gradient Calculation — only to make the presentation differentiable)

Again assume we have our Training Set of data as below

So we can say the below

And now again, we need to use the same vector identity mentioned above, that for a vector z, we have

We have already introduced the trace operator of a Matrix, written as “tr.” Now we need to use a couple of more matrix derivatives Identities (that I am just stating below here, and they all have robust Mathematical proofs, the details of which I am not including here).

So below 2 Matrix Derivative Identities hold true and we need to use them to arrive at the Gradient Calculation.

So now Final Gradient Calculation will be as below

And also the below Matrix Identity

And above is the exact formulae that we will implement in Python/Numpy very soon below.

So now let's go back to the original Cost Function

Compare the above with the Gradient-Descent formulae for the Numerical case

A manual example of the Gradient-Descent implementation

Let's say for simple single variable training dataset we have the following values

x,y1,12,23,34,4

Further, assume,

α (learning rate) = 1

m (number of training examples) =4

Setting _θ_0 to 0 and _θ_1 to 1

So we have the linear equation

at the _i_−th row

Further I denote,

So, regardless of how many times I apply the GD algorithm, the value of θ1 will be constantly equal to 1, since at every iteration we have _θ_0=0 and _θ_1=1

Now extend the above to a multivariable case,

Assume theta values have been picked at random as below

And the GD-Algorithm is,

---

Python/Numpy Implementation

Please refer to the jupyter notebook

First, generate a training dataset in Matrix form

NumPy zeros() function in above — you can create an array that only contains only zeros using the NumPy zeros() function with a specific shape. The shape is row by column format. Its syntax is as below

For example, the code to generate a Matrix of 2 by 3 (2 rows and 3 columns)

import numpy as np

A = np.zeros(shape = (2, 3)) print

Output below

[[0. 0. 0.] [0. 0. 0.]]

Which produces an array like the following:

If I run the above gen_data() function above for a set of 5 training data-set as below with bias and variance of 20 and 10 respectively

gen_data(5, 20, 10)

I will have the following form of output

(array([[1., 0.],
 [1., 1.],
 [1., 2.],
 [1., 3.],
 [1., 4.]]),
 array([22.38023816, 24.18406356, 28.01360908, 26.80051617, 29.30101971])
 )

And now the function for Gradient-Descent implementing the Grdient formulae for a Mactrix that we derived above

The full notebook is here

Reference and Further Reading

Matrix Multiplication — https://en.wikipedia.org/wiki/Matrix_multiplication

Matrix-Calculus — https://en.wikipedia.org/wiki/Matrix_calculus

Vector_Field — https://en.wikipedia.org/wiki/Vector_field

Matrix Transpose Properties -https://en.wikipedia.org/wiki/Transpose#Properties

Matrix Cookbook — https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf

Online Calculation of Matrix Derivative — http://www.matrixcalculus.org/