Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Background: This is the costfunction of Mean Regularized Multi Task Learning. This is a typical linear regression learning model, with the only difference being that there's multiple instances of trainings going on at the same time. So X has an additional 3rd dimension and W and Y a 2nd dimension. X is training data, Y is targets, W is weights, m is number of tasks (3rd dimension), d is number of features, n is number of examples.

$X\in R^{n_i\times d \times m}$, $Y\in R^{n_i\times m }$, $W\in R^{d \times m}$

enter image description here

Question: Given the cost function

$$ J =\min_W \frac{1}{2}||XW-Y||_F^2+\lambda\sum_{i=1}^m||W_i-\frac{1}{m}\sum_{s=1}^mW_s||^2_2 $$ What is $\frac{\partial}{\partial W}J$?

I need to calculate the partial derivatives that can be used with steepest gradient descent optimization algorithm. I was thinking of calculating the derivative both with respect to a single weight, and the whole matrix. See my answer for my calculations so far.

share|improve this question
3  
What is $F$? Do you know how to take the partial derivatives of the first term, second term, or neither? –  Douglas Zare Feb 15 '13 at 16:09
1  
@Douglas Zare I dont know either but asked on math math.stackexchange.com/questions/304878/how-to-calculate-v-22 –  siamii Feb 15 '13 at 16:36
    
I don't think $||.||_F$ means the Frobenius norm here, which is what several people guessed on math.stackexchange. Check the link you gave. At least one later slide mentions $F$, but didn't completely specify it. –  Douglas Zare Feb 15 '13 at 18:36
    
@Douglas It looks like the $L^2$ norm on pp 54 and 69 (where it is specifically called that). That's equivalent to the Frobenius norm in those cases (where it appears to be applied to vectors). At the bottom of p. 26 it's clearly the Frobenius norm of a matrix. –  whuber Feb 16 '13 at 12:12
    
@whuber: I assumed that $F$ had something to do with the $F$ on pages 46-48, "$m\times k$ orthogonal cluster indicator matrix." But perhaps that's just a coincidence. –  Douglas Zare Feb 16 '13 at 17:29
show 3 more comments

2 Answers 2

Just some general advice

  • try to limit the indexation where possible, and use matrix algebra

  • As the dimension of $Y_i$ varies with $i$ best not to store as a matrix. Treat $i$ separately.

  • Alternatively, you could define Y as one very long vector $Y=(Y_1^T,\dots,Y_m^T)^T$. Similarly, $X$ would have $\sum_{i=1}^{m}n_i$ rows and $d$ columns. But then $W$ needs to be redefined as the driect sum $W=\oplus_{i=1}^{m}W_i$. But then $W$ now has structural zeros. Too complicated to work with...

  • don't use indices more than once. For example you use $w_{j,k}$ and also use $j,k$ as summation variables. Should use $w_{r,s}$ instead

So I would write your cost function as $$J=\frac{1}{2}\sum_{i=1}^{m}(X_iW_i-Y_i)^T (X_iW_i-Y_i) +\lambda (W_i-\overline{W})^T (W_i-\overline{W})$$ Where $\overline{W}=\frac{1}{m}\sum_{i=1}^{m}W_i$ Now using the chain rule we have $\frac{\partial e^Te}{\partial W_r}= 2\frac{\partial e}{\partial W_r} e$

So you have $$ \frac{\partial J}{\partial W_r} =X_r^T (X_rW_r-Y_r) +2\lambda \sum_{i=1}^{m} \left(\frac{\partial W_i}{\partial W_r}- \frac{\partial \overline{W} }{\partial W_r}\right)(W_i-\overline{W})$$ $$ =X_r^T (X_rW_r-Y_r) +2\lambda (W_r-\overline{W})$$

This is not the answer you have.

update

One way you can re-express the equations is by setting $ X=\oplus_{i=1}^mX_i $ (which has $\sum_{i=1}^mn_i $ rows and $ dm $ colums, and $ w=(W_1^T,\dots, W_m^T)^T $ and $ Y=(Y_1^T,\dots, Y_m^T)^T $. We can also re-express the penalty term as $\sum_{i=1}^m(W_i-\overline {W})^T (W_i-\overline {W})=w^Tw-m\overline {W}^T\overline {W} =w^T (I-m^{-1}G^TG) w $ where $ G$ is the $ d\times md $ matrix which calculates the totals for $ w $. So the $ k $ th row of $ G $ has ones in columns $k, d+k, 2d+k, \dots, (m-1) d+k $ and zeroes everywhere else. We can also write the other factor as $\frac{1}{2}(Y-Xw)^T (Y-Xw) $. Hence an explicit solution is given as

$$\hat {w}=\left [X^TX +2\lambda (I-m^{-1} G^TG)\right]^{-1} X^TY $$

It will probably be more efficient to implement by first use the woodbury matrix identity, as $ X^TX $ is a block- diagonal matrix.

share|improve this answer
    
so you calculated it with respect to Wr, which is one column of W. If you calculate it with respect the whole W you would get my batch gradient result and if you calculate it with respect to a single w element, you would get my online gradient, wouldn't you? I don't see the difference. I might not have been too precise with my notation, i.e. should have used X transpose before, not after in order for it to make mathematical sense. Let me know if you think there would be major differences in our implementations. –  siamii Feb 21 '13 at 10:17
    
anyway, I'll give you the bounty for taking the effort. –  siamii Feb 22 '13 at 13:32
add comment

Okay, so I came to this conclusion. Can anyone verify it please?


Online gradient descent:

$$ \frac{\partial}{\partial w_{j,k}}J =\frac{\partial}{\partial w_{j,k}}\frac{1}{2}||XW-Y||_F^2+\lambda\sum_{i=1}^m||W_i-\frac{1}{m}\sum_{s=1}^mW_s||^2_2 $$ let $ z_{i,k} = \sum_{j=1}^dx_{i,j,k}w_{j,k} - y_{i,k} $ $$ =\frac{\partial}{\partial w_{j,k}}\frac{1}{2}\left(\sqrt{\sum_{k=1}^{m}\sum_{i=1}^{n_{k}}|z_{i,k}|^2}\right)^2+\lambda\sum_{k=1}^m\left(\sqrt{\sum_{j=1}^d|w_{j,k}-\frac{1}{m}\sum_{s=1}^mw_{j,s}|^2}\right)^2 $$ $$ =\frac{\partial}{\partial w_{j,k}}\frac{1}{2}{\sum_{k=1}^{m}\sum_{i=1}^{n_{k}}z_{i,k}^2}+\lambda\sum_{k=1}^m(\sum_{j=1}^d(w_{j,k}-\frac{1}{m}\sum_{s=1}^mw_{j,s})^2) $$

$$ \frac{\partial}{\partial w_{j,k}}J= \sum_{i=1}^{n_{k}}((\sum_{j=1}^dx_{i,j,k}w_{j,k}-y_{i,k}) x_{i,j,k})+\lambda2(w_{j,k}-\frac{1}{m}\sum_{s=1}^mw_{j,s})(1-\frac{1}{m}) $$


Batch gradient descent $$ \frac{\partial}{\partial W}J= (XW-Y)X + 2\lambda\sum_{i=1}^m(W_i-\frac{1}{m}\sum_{s=1}^mW_s) $$

share|improve this answer
    
How did the weights suddenly acquire two subscripts in some places and three in another when in the question they have only one? –  whuber Feb 16 '13 at 12:07
    
@whuber So I was trying to computer the partial derivative with respect one weight. In the original question W was a matrix. Let me update the description –  siamii Feb 16 '13 at 12:09
    
First work it out in the case where all dimensions are $1$, so that $x$, $w$, and $y$ can be considered numbers: that will show you some of the missing pieces and why you don't need the absolute values. –  whuber Feb 16 '13 at 12:36
    
@whuber why would the absolute values disappear? –  siamii Feb 17 '13 at 19:56
    
There are no absolute values to begin with because your function is a sum of squares of things and the derivative of $x^2$ with respect to $x$ is $2x$, not $2|x|$. One mistake you have made is to express these sums of squares in terms of square roots and absolute values, neither of which is differentiable everywhere. –  whuber Feb 17 '13 at 21:39
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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