# How does “linear algebraic” weight training function work?

This answer shows that linear and polynomial function weights can be trained using this matrix operation:

$w = (X^TX)^{-1}X^Ty$

Therefore, algorithms such as gradient descent are not necessary for these functions. By my understanding, gradient descent for linear regression model finds perfect derivative for each weight so that cost function is minimal.

Before asking for connections between gradient descent and equation above, let's separate the equation in smaller steps:

$X = [1,2,3,4,5,6,7,8,9,10,11,12]$

$y=[2.3,2.33,2.29,2.3,2.36,2.4,2.46,2.5,2.48,2.43,2.38,2.35]$

Let's turn $X$ vector to matrix by adding column of 1's which will be used to train the bias value:

\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1 \\ 5 & 1 \\ 6 & 1 \\ 7 & 1 \\ 8 & 1 \\ 9 & 1 \\ 10 & 1 \\ 11 & 1 \\ 12 & 1 \end{bmatrix}

1. Transpose: $X^T$:

\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 9 & 10 & 11 & 12 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}

2. Matrix multiplication $X^TX$:

\begin{bmatrix} 650 & 78 \\ 78 & 12 \end{bmatrix}

3. Inverse matrix operation $(X^TX)^{-1}$:

\begin{bmatrix} 0.00699301 & -0.04545455 \\ -0.04545455 & 0.37878788 \end{bmatrix}

4. Matrix multiplication $(X^TX)^{-1}X^T$:

array([[-0.03846154, -0.03146853, -0.02447552, -0.01748252, -0.01048951,
-0.0034965 ,  0.0034965 ,  0.01048951,  0.01748252,  0.02447552,
0.03146853,  0.03846154],
[ 0.33333333,  0.28787879,  0.24242424,  0.1969697 ,  0.15151515,
0.10606061,  0.06060606,  0.01515152, -0.03030303, -0.07575758,
-0.12121212, -0.16666667]])

1. Matrix vector multiplication $(X^TX)^{-1}X^Ty$:

\begin{bmatrix} 0.01174825 & 2.30530303 \end{bmatrix}

This seems to be the perfect slope for minimizing cost. But I'm unable to understand how does it exactly work.

It seems like that the algorithm such as gradient descent would've took extremely large amount of iterations to estimate perfect slope and bias value.

How/why does this equation exactly work? Is it somehow related to differentiation? Could it be compared to algorithms such as gradient descent? If so, how? Is it possible to use this equation with sigmoid functions?

Your goal is to find a $w$ such that

$$Xw \approx y$$

and way to model this problem is to minimize the objective function:

$$\min_w\|Xw-y\|^2.$$

Differentiating with respect to $w$ and equate it to zero gives us

$$2X^T(Xw-y)=0$$

$$X^TXw-X^Ty=0$$

$$X^TXw=X^Ty$$

if $X^TX$ is invertible, then we have

$$w=(X^TX)^{-1}(X^Ty)$$

Remark:

We tend to avoid computing inverse and prefer gradient-based method. Complexity of the normal equation method is cubic.

• Thank you for your response. My apologies, I couldn't exactly understand the part where we equated to zero. Is there some specific rule that i'm not aware of? It seems like Euclidean norm. – ShellRox Mar 26 '18 at 7:46
• Yes, the norm that I used are just Euclidean norm. I just apply chain rule. – Siong Thye Goh Mar 26 '18 at 15:44
• Reference for matrix calculus – Siong Thye Goh Mar 26 '18 at 16:08
• Thank you! I guess I need to study more about multivariable differentiation. – ShellRox Mar 26 '18 at 19:29
• @SiongThyeGoh I've searched alot but didn't find any valid solution. I aware that the complexity of gradient based methods are $O(n^2)$. Is there any proven approach for showing that? – Media Oct 27 '18 at 17:53

First of all, gradient descent cannot find the global optimum. If your function has just one extremum, it can find it but if it has lots of them there is no guarantee that it finds the best one. If you are familiar with derivative and slope of functions, the Normal equation, tries to find the point which all the derivative is equal to zero for all directions, variables. It is the result of the derivatives.

You are somehow right, mathematically we know the optimal solution of all ML problems but in practice, normal equations do not work. The reason is that if you increase the number of features, you will have a matrix which gets larger and larger. Most problems are not linearly separable. Consequently, you have to add high order polynomials and the point is that you don't know which polynomial to use. If you use just the second order polynomial you will get a matrix that won't be located in your computer's memory because of being so much large. suppose that you have 100 features. If you just add the combination of multiplication of two variables, compute how many entries your matrix will have. And if you do that you can be sure that it does not add too much complexity to your model, because you've not added complex higher order polynomials whilst you need them. ML algorithms like deep-nets try to learn so many complicated functions using the smaller number of entries.

How/why does this equation exactly work? Could it be compared to algorithms such as gradient descent? If so, how? Is it possible to use this for more complex activation functions such as hyperbolic tangent?

It is the result of taking the multivariable derivative, gradient. Yes the goal of them is to find the local minima, but they have a different approach. Gradient descent tries to go downhill whilst normal equation tries to find the location by finding where the derivative is zero for all features.