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.


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.

  • $\begingroup$ Thank you for your response. My only problem is now understanding how we derive the sum-of-squares error function. Why do we consider the trace and where the constant $\frac{1}{2}$ comes from? $\endgroup$ Oct 27 '18 at 13:00
  • $\begingroup$ What is trace? The constant is just for cancelling the $2$ which comes after taking the derivatives. In optimisation, it does not matter. $\endgroup$
    – Media
    Oct 27 '18 at 13:41
  • $\begingroup$ trace is the sum of the components in the main diagonal of the matrix. $\endgroup$ Oct 28 '18 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.