Demostrar que la suma de los slacks en SVM es un límite superior en el número de ejemplos mal clasificados

Question

¿Cómo podemos demostrar que la suma de las holguras $\sum \xi_n$ de la función objetivo de la formulación de la SVM con margen suave es un límite superior del número de ejemplos de entrenamiento mal clasificados?

Algunas referencias: https://www.cs.colostate.edu/~asa/pdfs/howto.pdf

Mis conocimientos actuales: El problema de optimización es
minimizar w,b
1/2 $||w||^2$ + C $\sum \xi_i$

con sujeción a $y_i (w^T x_i +b) \ge 1 - \xi_i, \xi_i \ge 0$

Pero utiliza el problema dado por sentado, estoy buscando cómo podemos realmente resolver esto.

Answer 1

En primer lugar, consideremos el caso $y_i = 1$ . Para que se clasifique correctamente, $w^Tx_i + b > 0$ Por lo tanto $0 <y_i(w^Tx_i + b)$ . Para que este número sea $\geq 1 - \xi_i$ , $0 \leq \xi_i < 1$ con $\xi_i = 0$ cuando $y_i(w^Tx_i + b) \geq 1$ .

Ahora supongamos que se ha producido la misma clasificación, de modo que $w^Tx_i + b > 0$ pero de forma incorrecta, es decir, $y_i = -1$ . Como $y_i < 0$ Debe ser que $y_i(w^Tx_i + b) < 0$ . Con el fin de este número a ser $\geq 1 - \xi_i$ Debe ser que $\xi_i > 1$ .

Se puede aplicar una lógica similar para el caso en que $w^Tx_i + b < 0$ . En ambos casos, la clasificación errónea implica que $\xi > 1$ .

Desde $\xi_i > 1$ para todos los casos mal clasificados, se deduce que $\Sigma_{i \in \text{misclassified}}\xi_i > \Sigma_{i \in \text{misclassified}}1$ , que evidentemente es igual al número de casos mal clasificados.

Desde $\xi_i \geq 0$ para todos los casos correctamente clasificados, se deduce que $\Sigma_{i \in \text{correct}}\xi_i \geq 0$ .

Por tanto, la suma de todos los casos debe ser mayor o igual que el número de casos mal clasificados, lo que la convierte en un límite superior del número de casos mal clasificados.