How to derive the sum-of squares error function formula?

Question

I'm attending a Machine Learning course and I'm studying linear models for classification right now. Slides present approaches to learn linear discriminants (Least squares, Fisher's linear discriminant, Perceptron and SVM), more specifically, how to compute the weight matrix $\tilde{\textbf{W}}$ to determine the discriminant function:

\begin{equation}y = \tilde{\textbf{W}}^T \tilde{\textbf{x}} + w_0. \end{equation}

My problem is about least squares: I don't understand how the minimization of sum-of-squares error function:

\begin{equation}E(\tilde{\textbf{W}}) = \frac{1}{2} Tr\Bigl\{(\tilde{\textbf{X}}\tilde{\textbf{W}} - \textbf{T})^T(\tilde{\textbf{X}}\tilde{\textbf{W}} - \textbf{T})\Bigr\} \end{equation} (where $Tr$ is the trace).

is derived and how it is possible to reach the closed formula solution:

\begin{equation}\tilde{\textbf{W}} = (\tilde{\textbf{X}}^T\tilde{\textbf{X}})^{-1}\tilde{\textbf{X}}^T\textbf{T}\end{equation}

Can someone explain me the main steps in the simplest and clearest possible way to make sense of these formulas? I'm a beginner.

P.S. These formulas come from C.Bishop. Pattern Recognition and Machine Learning.

Answer 1

There are two interpretations of this formula that I explain one of them.

\begin{equation} Xw = y \end{equation}

\begin{equation} X^tXw = X^ty \end{equation}

The above is for making sure that you make a square matrix that it has an inverse. It is possible that $X^tX$ does not have any inverse but its chance for linear regression problems is not that much. The reason is that you have a matrix $X$ which belongs to $R^{m \times n}$ which $m$ represents the number of samples and $n$ represents the number of features. Usually, the number of samples is much more than the number of features. Next,

\begin{equation}(X^tX)^{-1}(X^tX)w = (X^tX)^{-1}X^ty\end{equation}

\begin{equation}w = (X^tX)^{-1}X^ty\end{equation}

Consequently, you have found a closed form for the $w$ linear regression problem which can be generalised to non-linear regression.

Be aware that $(X^tX)^{-1}X^t$ is called the pseudo-inverse of the matrix $X$. The reason is that $X$ is not a square matrix and it does not have inverse but by the mentioned formula you can find its pseudo-inverse. Just multiply it by $X$ and you will get Identity matrix.

There is another interpretation of this. You can find here.