Derivación del gradiente de pérdida de la SVM

Question

Esta es la función de pérdida para SVM:

No puedo entender cómo es el gradiente con respecto a w(y(i)):

¿Puede alguien proporcionar la derivación?

Gracias

Answer 1

Empecemos por lo básico. El llamado gradiente no es más que la derivada ordinaria, es decir, la pendiente. Por ejemplo, la pendiente de la función lineal $y=kx+b$ es igual a $k$ por lo que su gradiente con respecto a $x$ es igual a $k$ . Si $x$ y $k$ no son números, sino vectores, entonces el gradiente también es un vector.

Otra buena noticia es que el gradiente es un operador lineal. Esto significa que puedes sumar funciones y multiplicar por constantes antes o después de la diferenciación, no hay ninguna diferencia

Tomemos ahora la definición de la función de pérdida de SVM para un solo $i$ -en la observación. Es

$\mathrm{loss} = \mathrm{max}(0, \mathrm{something} - w_y*x)$

donde $\mathrm{something}=wx+\Delta$ . Por lo tanto, la pérdida es igual a $\mathrm{something}-w_y*x$ si este último es no negativo, y $0$ de lo contrario.

En el primer caso (no negativo) la pérdida $\mathrm{something}-w_y*x$ es lineal en $w_y$ por lo que el gradiente es sólo la pendiente de esta función de $w_y$ es decir.., $-x$ .

En el segundo caso (negativo) la pérdida $0$ es constante, por lo que su derivada es también $0$ .

Para escribir todos estos casos en una ecuación, inventamos una función (se llama indicador) $I(x)$ que es igual a $1$ si $x$ es verdadera, y $0$ de lo contrario. Con esta función, podemos escribir

$\mathrm{derivative} = I(\mathrm{something} - w_y*x > 0) * (-x)$

Si $\mathrm{something} - w_y*x > 0$ el primer multiplicador es igual a 1, y el gradiente es igual a $x$ . De lo contrario, el primer multiplicador es igual a 0, y el gradiente también. Así que reescribí los dos casos en una sola línea.

Ahora pasemos de una sola $i$ -a observación a toda la pérdida. La pérdida es la suma de las pérdidas individuales. Así, como la diferenciación es lineal, el gradiente de una suma es igual a la suma de gradientes, por lo que podemos escribir

$\text{total derivative} = \sum(I(something - w_y*x_i > 0) * (-x_i))$

Ahora, mueve el $-$ multiplicador de $x_i$ al principio de la fórmula, y obtendrás tu expresión.

Answer 2

David ha dado una buena respuesta. Pero me gustaría señalar que la suma() en la respuesta de David:

total_derivative = sum(I(something - w_y*x[i] > 0) * (-x[i]))

es diferente a la de la pregunta original de Nikhil:

$$ \def\w{{\mathbf w}} \nabla_{\w_{y_i}} L_i=-\left[\sum_{j\ne y_i} \mathbf{I}( \w_j^T x_i - \w_{y_i}^T x_i + \Delta >0) \right] x_i $$ La ecuación anterior sigue siendo el gradiente debido a la i-ésima observación, pero para el peso de la clase de verdad básica, es decir $w_{y_i}$ . Existe la suma $\sum_{j \ne y_i}$ porque $w_{y_i}$ está en cada término de la pérdida SVM $L_i$ :

$$ \def\w{{\mathbf w}} L_i = \sum_{j \ne y_i} \max (0, \w_j^T x_i - \w_{y_i}^T x_i + \Delta) $$ Para cada término no nulo, es decir $w^T_j x_i - w^T_{y_i} x_i + \Delta > 0$ se obtendría el gradiente $-x_i$ . En total, el gradiente $\nabla_{w_{y_i}} L_i$ es $numOfNonZeroTerm \times (- x_i)$ , igual que la ecuación anterior.

Gradientes de las observaciones individuales $\nabla L_i$ (calculados anteriormente) se promedian para obtener el gradiente del lote de observaciones $\nabla L$ .