Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given the primal objective $$F({\bf a})=L\sum_{i,j}a_{i}a_{j}k(x_i,x_j) + \sum_{i}max(0, 1-y_i \sum_{j}a_jk(x_i,x_j)$$

for the soft margin SVM, where ${\bf a}=(a_1,...,a_N)$, N being the number of training examples. I am trying to get the stochastic gradient descent update for $\textbf{a}$.

Details (could be considered or ignored :-):

I've been trying to read Online Learning with Kernels. While it makes sense for the general case for a general $f$, I don't know how to adapt it here.

More specifically: In the paper we have the general objective $c(x_t, y_t, f(x_t)) + \frac{L}{2}||f||^2$. I understand that by taking the derivative with respect to f, we get to the update $f=(1-Lr)f - rc'(x_t,y_t,f(x_t))k(x_t,.)$.

Now in my case (soft margin/hinge loss kernel SVM) I don't really see how to apply that in order to get the updates for $a_i$. I mean, if I just go ahead and take the derivative of my initial $F({\bf a})$, I get $\frac{d}{da_i}F_n({\bf a})=2LGA - y_nk(x_n,x_i)\text{ right?}$ ($G$ being the gramm matrix) (I have considered the objective $F_n({\bf a})=L\sum_{i,j}a_{i}a_{j}k(x_i,x_j) + max(0, 1-y_n \sum_{j}a_jk(x_n,x_j))$.

But... now what?... :-) Thank you.

share|improve this question
    
You're not going to get nice results trying to find the derivative of a function like $max$, which is not everywhere differentiable. I see two ways out. First, use a conditional in your expression, like equation (12) in your reference. Second, use a differentiable approximation to $max$, like softmax (read the last section of the Wikipedia article on softmax for the approximation I'm thinking about.) –  Carl Feynman Dec 23 '12 at 21:14
    
Thank you. I know that the hinge loss does not have a derivative in 1, but that's fine, I can use a conditional. My questions was, how to get to equation (12) starting from my more concrete for of the loss. Thanks again. –  Jessica Dec 23 '12 at 22:42

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.