4
$\begingroup$

In ordinary least squared there is this equation (Kevin Murphy book page 221, latest edition)

$$NLL(w)=\frac{1}{2}({y-Xw})^T(y-Xw)=\frac{1}{2}w^T(X^TX)w-w^T(X^T)y$$

I am not sure how the RHS equals the LHS. Maybe my linear algebra is weak but I can't figure out how this happens. Can somebody point out how this happens. This is related to deriving the Ordinary Least squares equation where $\hat{w}_{OLS}=(X^TX)^{-1}X^Ty$

NLL - stands for negative loglikelihood.

I am attaching the screen shots of the relevant section. My equation is in the 1st image(page 221). I actually bought the book so I am hoping that showing 2 pages is not a copyright infringement. source (Kevin Murphy, Machine Learning, A probabilistic perspective)

enter image description here enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are you missing a $y^Ty$ term or does it somehow get dropped? $\endgroup$
    – user95564
    Dec 11, 2015 at 5:08
  • $\begingroup$ Could you tell us what NLL stands for? $\endgroup$
    – user95564
    Dec 11, 2015 at 5:08
  • 1
    $\begingroup$ Can you give the full reference? Note that $\frac12({y-Xw})^T(y-Xw)\neq \frac12w^T(X^TX)w-w^T(X^T)y$ but the different between them is not a function of $w$ -- so their argmin is in the same place. $\endgroup$
    – Glen_b
    Dec 11, 2015 at 7:28
  • 1
    $\begingroup$ It does not. There is an extra term $(1/2)y^Ty$ but this term is omitted since it does not depend explicitly on $w$ and it's value has no effect on the value of $w$ that minimizes $NLL(w)$. $\endgroup$
    – CTNT
    Dec 11, 2015 at 8:13

1 Answer 1

Reset to default
10
$\begingroup$

The sum of squares expands to:

$$ \begin{align*} \frac{1}{2}({y-Xw})^T(y-Xw) &= \frac{1}{2}\left( y^\top y - y^\top Xw - \left( X w \right) ^\top y + \left( X w \right)^\top X w \right) \\ &= \frac{1}{2}\left( y^\top y - y^\top Xw - w^\top X^\top y + w^\top X^\top X w \right) \\ &= \frac{1}{2}\left(y^{\top}y - 2 y^\top X w + w^\top X^\top X w \right) \end{align*} $$

Note that $y^\top X w$ is a 1 by 1 matrix (i.e. scalar) hence it is always symmetric and $y^\top X w = w^\top X^\top y$.

Observe that the minimization problem: $$ \text{minimize(over $w$) } \quad \frac{1}{2}y^{\top}y - y^\top X w + \frac{1}{2} w^\top X^\top X w $$ Has an equivalent solution for $w$ as: $$ \text{minimize(over $w$) } \quad \frac{1}{2}w^\top X^\top X w - y^\top X w $$ This is because the scalar $y^\top y$ doesn't affect the optimal choice of $w$. Also observe that objective is a convex function of w, hence the first order conditions are both necessary and sufficient conditions for an optimum. The first order condition is: $$ \frac{\partial \mathcal{L}}{\partial w} = \frac{1}{2}\left(X^\top X + (X^\top X)^\top \right)w - X^\top y = 0 $$ $$ X^\top X w = X^\top y$$

If $X^\top X $ is full rank (i.e. the columns of $X$ are linearly independent), $X^\top X$ can be inverted to obtain the unique solution:

$$ w = \left( X^\top X \right)^{-1} X^\top y$$

Note: For reference, matrix calculus rules for taking the partial derivative with respect $w$ can be found on Wikipedia here. Or as rightskewed pointed out, there's the classic matrix cookbook.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hmm the step that goes from the minimization equation to the partial derivative equation needs some heavy linear algebra manipulation (I thought it was a simple partial derivative but it isnt!)....Had to go through this video to figure out that step youtube.com/… $\endgroup$
    – mathopt
    Dec 12, 2015 at 0:17
  • 1
    $\begingroup$ @user1467929 This wikipedia page on matrix calculus is somewhat long and convoluted but actually a great reference. For notation purposes, the two approaches are numerator layout or denominator layout. In numerator layout: $\frac{\partial Aw}{\partial w^\top} = A$ while in denominator layout $\frac{\partial Aw}{\partial w} = A^\top$. I remember being endlessly confused by different notation back when first learning. Sometimes it's easier to write everything out as disgusting sum and then find the compact matrix notation. $\endgroup$
    – Matthew Gunn
    Dec 12, 2015 at 0:25
  • 2
    $\begingroup$ I keep this comprehensive cookbook handy $\endgroup$
    – rightskewed
    Dec 12, 2015 at 0:40
  • $\begingroup$ @rightskewed that's a classic! $\endgroup$
    – Matthew Gunn
    Dec 12, 2015 at 0:43

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.