2
$\begingroup$

This is in a similar vein to a recent question I asked, however I feel that it is sufficiently different to warrant another question. Again, this is from Andrew Ng's excellent freely available machine learning class.

This question asks for the conversion from index notation to matrix vector notation of the cost function of the multivariate least squares given as:

$$ \begin{align} J(\theta) = \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^p \Big( (\theta^T x^{(i)})_j - y^{(i)}_j \Big)^2 \end{align} $$

where $\theta \in \mathbb{R}^{n \times p}$, $X \in \mathbb{R}^{m \times n}$, $Y \in \mathbb{R}^{m \times p}$. Rewriting this as:

$$ \begin{align} J(\theta) = \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^p \Big( u^{(i)}_j - y^{(i)}_j \Big)^2 \end{align} $$

where $u^{(i)}_j = (\theta^T x^{(i)})_j$, I can then convert the inner sum to a dot product:

$$ \begin{align} J(\theta) = \frac{1}{2} \sum_{i=1}^m \big( u^{(i)} - y^{(i)} \big)^T \big( u^{(i)} - y^{(i)} \big) \end{align} $$

From here it seems that the next step would be to conclude that this is equivalent to:

$$ \begin{align} J(\theta) &= \frac{1}{2} tr \Big( \big( U - Y \big)^T \big( U - Y \big) \Big) \\ &= \frac{1}{2} tr \Big( \big( X \theta - Y\big)^T \big( X \theta - Y \big) \Big) \end{align} $$

However I am missing the leap from reducing the outer summation. Again, I appreciate all the help.

$\endgroup$
2
$\begingroup$

Understanding $u^{(i)}-y^{(i)}$ as a column vector corresponding to the difference between the vector of predicted values of the DV of example $i$ and the vector of actual values, the squared of the difference is encapsulated in:

\begin{align} \big( u^{(i)} - y^{(i)} \big)^T \big( u^{(i)} - y^{(i)} \big) \end{align}

Now the batch calculation of the cost is not just one single example, but rather the summation of all these squared residuals across all $m$ examples (the $1/2$ being just a "trick" to get nicer derivatives):

\begin{align} \sum_{i=1}^m \big( u^{(i)} - y^{(i)} \big)^T \big( u^{(i)} - y^{(i)} \big) \end{align}

However, the OP explicitly posits a multivariate multiple regression model, or, in other words, the $j$ indexation of the dependent variables, which range from $1$ to $p$ needs to be addressed. The "independent variable" $Y$ is a matrix of the form:

$$\underset{m\times p}Y=\begin{bmatrix} y^{(1)}_1 & y^{(1)}_2 & \cdots & y^{(1)}_p\\ y^{(2)}_1 & y^{(2)}_2 & \cdots & y^{(2)}_p\\ \vdots & \ddots & \vdots\\ y^{(m)}_1 & y^{(m)}_2 & \cdots & y^{(m)}_p\\ \end{bmatrix}= \begin{bmatrix} \mathbf y^{(1)\top}\\ \mathbf y^{(2)\top}\\ \vdots\\ \mathbf y^{(m)\top} \end{bmatrix}$$

where the super-scripted indexes in parenthesis denote individual examples, while the sub-scripted indexes denote each one of the $j = \{1,\dots,p\}$, independent variables in the model.

The loss function would result in a $p\times p$ matrix as follows:

$$\begin{align} &\underset{\color{brown}{p\times m}}{(X\Theta-Y)^\top}\underset{\color{brown}{m\times p}}{(X\Theta-Y)} \\[2ex]= &\begin{bmatrix} \color{red}{\small\underset{\color{brown}{1\times m}}{\left(\mathbf u_1 - \mathbf y_1 \right)^\top}\underset{\color{brown}{m\times 1}}{ \left(\mathbf u_1 - \mathbf y_1 \right)}} & \small\left(\mathbf u_1 - \mathbf y_1 \right)^\top \left(\mathbf u_2 - \mathbf y_2 \right) &\cdots & \small\left(\mathbf u_1 - \mathbf y_1 \right)^\top \left(\mathbf u_p - \mathbf y_p \right)\\ \small\left(\mathbf u_2 - \mathbf y_2 \right)^\top \left(\mathbf u_1 - \mathbf y_1 \right) & \color{red}{\small\left(\mathbf u_2 - \mathbf y_2 \right)^\top \left(\mathbf u_2 - \mathbf y_2 \right)} &\cdots & \small\left(\mathbf u_2 - \mathbf y_2 \right)^\top \left(\mathbf u_p - \mathbf y_p \right)\\ \vdots&\vdots&\ddots&\vdots\\ \small\left(\mathbf u_p - \mathbf y_p \right)^\top \left(\mathbf u_1 - \mathbf y_1 \right) & \small\left(\mathbf u_p - \mathbf y_p \right)^\top \left(\mathbf u_2 - \mathbf y_2 \right) &\cdots & \color{red}{\small\left(\mathbf u_p - \mathbf y_p \right)^\top \left(\mathbf u_p - \mathbf y_p \right)} \end{bmatrix} \end{align} $$

We only care about dot products where all the sub-indices are identical: $j$ for $j=1$ to $j=p.$ These are located in the diagonal of the matrix $(X\Theta-Y)^\top(X\Theta-Y)$, and the sum of the diagonal values is by definition the trace.

$\endgroup$
  • $\begingroup$ I could be wrong, and this has been tripping me up for a while, but aren't the indices of the matrix you describe off? Isn't $(X \Theta - Y)^T (X \Theta - Y)$ a $p \times p$ rather than an $m \times m$ matrix? $\endgroup$ – oort Jun 25 '17 at 3:04
  • 1
    $\begingroup$ The multivariate nature of the model is now addressed in the edited answer. $\endgroup$ – Antoni Parellada Jul 9 '17 at 19:41

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.