7
$\begingroup$

I am a little confused when trying to find the gradient for the multiclass hinge loss:

$$l(y) = \max( 0, 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i - W_{y_i} \cdot x_i)$$

Where $W^{k \times n}$ is the matrix holding in each row the corresponding classifier of each class.

Unless my math is wrong, the gradient of the function is: \begin{equation} \frac{\partial l}{\partial w} = \begin{cases} 0, & W_{y_i}\cdot x_i > 1 + W_r \cdot x_i \\ 0 + 0 - x_i, & \text{otherwise} \end{cases} \end{equation}

Is this ok?

So if I would like to find the $W$ which minimizes the function using the stochastic gradient descend I would need to do: \begin{equation} W_y^{(t+1)} = W_y^{(t)} - \eta x_i \end{equation}

with $\eta$ the learning rate.

Is this a valid procedure to optimize the $l(y)$ function?

$\endgroup$
4
  • $\begingroup$ What is $w$? And since in definition $l$ depends on $y$, shouldn't then $\frac{\partial l}{\partial w}=0$? $\endgroup$
    – mpiktas
    Jun 2, 2015 at 6:20
  • $\begingroup$ $\omega$ is the same as $W_{y_i}$. $l$ is also dependent on $W$ and $x_i$. I wrote it that way because that's how I saw it in another places. $\endgroup$ Jun 2, 2015 at 6:27
  • $\begingroup$ And what is $W_{y_i}$? If you define all the quantities in the formula you might get answers from people who are not aware what is a multiclass hinge loss. Derivatives is a part of calculus, and much more people know calculus. $\endgroup$
    – mpiktas
    Jun 2, 2015 at 6:31
  • $\begingroup$ $W_{y_i}$ is the row y of the matrix $W$. I think you are right and I might be confusing some concepts. What I would like to know is if there is a straight-forward solution to the multiclass problem or if the solution is to treat them in a one vs. all style. $\endgroup$ Jun 2, 2015 at 6:41

2 Answers 2

8
$\begingroup$

Let's use the example of the SVM loss function for a single datapoint:

$L_i = \sum_{j\neq y_i} \left[ \max(0, w_j^Tx_i - w_{y_i}^Tx_i + \Delta) \right]$

Where $\Delta$ is the desired margin.

We can differentiate the function with respect to the weights. For example, taking the gradient with respect to $w_{yi}$ we obtain:

$\nabla_{w_{y_i}} L_i = - \left( \sum_{j\neq y_i} \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) \right) x_i$

Where 1 is the indicator function that is one if the condition inside is true or zero otherwise. While the expression may look scary when it is written out, when you're implementing this in code you'd simply count the number of classes that didn't meet the desired margin (and hence contributed to the loss function) and then the data vector $x_i$ scaled by this number is the gradient. Notice that this is the gradient only with respect to the row of $W$ that corresponds to the correct class. For the other rows where $j≠{{y}_{i}}$ the gradient is:

$\nabla_{w_j} L_i = \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) x_i$

Once you derive the expression for the gradient it is straight-forward to implement the expressions and use them to perform the gradient update.

Taken from Stanford CS231N optimization notes posted on github.

$\endgroup$
2
  • 1
    $\begingroup$ Can you send me your code at [email protected]? $\endgroup$
    – CKM
    Sep 22, 2016 at 8:32
  • $\begingroup$ "We can differentiate the function with respect to the weights" - Can you please explain how you developed that formula from the Loss function? as in what are the steps / derivation rules used... I can't figure this one out. And... why do you do it w.r.t Wj AND Wyi? Thanks $\endgroup$ Mar 29, 2017 at 8:16
0
$\begingroup$

First of all, note that multi-class hinge loss function is a function of $W_r$. \begin{equation} l(W_r) = \max( 0, 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i - W_{y_i} \cdot x_i) \end{equation} Next, max function is non-differentiable at $0$. So, we need to calculate the subgradient of it. \begin{equation} \frac{\partial l(W_r)}{\partial W_r} = \begin{cases} \{0\}, & W_{y_i}\cdot x_i > 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i \\ \{x_i\}, & W_{y_i}\cdot x_i < 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i\\ \{\alpha x_i\}, & \alpha \in [0,1], W_{y_i}\cdot x_i = 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i \end{cases} \end{equation} In the second case, $W_{y_i}$ is independent of $W_r$. Above definition of subgradient of multi-class hinge loss is similar to subgradient of binary class hinge loss.

$\endgroup$
8
  • $\begingroup$ Could you please clarify what alpha is? Thank you! $\endgroup$
    – Ramalho
    Feb 15, 2016 at 18:14
  • $\begingroup$ $\alpha$ is some real number in the given interval. $\endgroup$
    – CKM
    Feb 16, 2016 at 3:41
  • $\begingroup$ That I understood, but why do we need it? I understand that max is not differentiable by it self, but why multiply by some alpha?! I hope to understand. You are also missing the gradient with respect to $W_{yi}$. $\endgroup$
    – Ramalho
    Feb 17, 2016 at 10:23
  • $\begingroup$ Please look at the subgradient of binary class hinge loss here. $W_{y_i}$ is fixed; Not a variable since it is indexed by known class label. $r$ is the row/label that you choose; its variable. $\endgroup$
    – CKM
    Feb 18, 2016 at 5:07
  • $\begingroup$ P.S. If you think $W_{y_i}$ is variable, if you easily modify the above differentiation. $\endgroup$
    – CKM
    Feb 18, 2016 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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