¿Cómo calcular el límite de decisión a partir de los vectores de apoyo?

Question

Quiero obtener el límite de decisión de SVM usando OpenCV 2.4.11, pero parece que no lo devuelve explícitamente, sino que sólo soporta vectores .

¿Cómo podemos calcular el límite de decisión a partir de los vectores de apoyo?

Actualización:

De todos modos parece que a través de la interfaz opencv no puedo obtener el multiplicador de lagrange $\alpha_i$

Answer 1

Una SVM binaria trata de separar a los sujetos que pertenecen a una de dos clases en función de algunas características, la clase se denotará como $y_i \in \{-1,+1\}$ y las características como $x_i$ , observe el $y_i$ es un solo número mientras que $x_i$ es un vector. El índice $i$ identifica al sujeto.

La SVM resuelve un problema de programación cuadrática y encuentra, para cada sujeto un multiplicador de lagrange $\alpha_i$ Muchos de los $\alpha$ son cero. Obsérvese que el $\alpha_i$ son números, por lo que para cada sujeto $i$ usted tiene un número $y_i$ una característica vector $x_i$ y un multiplicador de lagrange $\alpha_i$ (a número ).

También ha elegido un núcleo $K(x,y)$ ( $x$ et $y$ son vectores ) para la que se conoce la forma funcional y se ha elegido un parámetro de capacidad $C$ .

El $x_i$ para el que el correspondiente $\alpha_i$ son distintos de cero son los vectores de apoyo.

Para calcular su límite de decisión, me remito a este artículo . Con la fórmula (61) del artículo mencionado se aprende que el límite de decisión tiene la ecuación $f(x)=0$ , donde $f(x)=\sum_i \alpha_i y_i K(x_i, x) + b$ y como el $\alpha_i$ sólo son distintos de cero para los vectores soporte, esto se convierte en (SV es el conjunto de vectores soporte): $f(x)=\sum_{i \in SV} \alpha_i y_i K(s_i, x) + b$ (donde cambié $x_i$ a $s_i$ como en la fórmula (61) del artículo, para indicar que sólo aparecen vectores de apoyo).

Como se conocen todos los vectores de apoyo, se conoce el $\alpha_i$ el (número) correspondiente $y_i$ y los vectores $s_i$ se puede calcular lo siguiente $f(x)$ si conoce su núcleo $K$ y la constante $b$ .

Así que todavía tenemos que encontrar $b$ : Las ecuaciones (55) y (56) del artículo al que me referí, aprenden que para un $\alpha_i$ con $0 < \alpha_i < C$ (C es un parámetro de su SVM) sostiene que $y_i ( x_i \cdot w + b) = 1$ donde $w$ viene dada por la ecuación (46) del artículo. Así que $b = \frac{1}{y_i} - x_i \cdot w=\frac{1}{y_i} - \sum_{k \in SV} \alpha_k y_k K(x_i, s_k)$ . (el ' $\cdot$ ' es el producto interno que luego será sustituido por el núcleo, ver artículo al que me referí).

Esto último es válido para cualquiera de los $\alpha_i, 0 < \alpha_i < C$ Así que si usted elegir uno de estos un $\alpha_i$ que es menor que $C$ y positivo , entonces se puede calcular $b$ a partir de la observación correspondiente: tomar un $m$ para lo cual $0 < \alpha_m < C$ con esto $m$ corresponde un $x_m$ y un $y_m$ . Por otro lado se conocen todos los vectores de apoyo $s_k$ (que son los vectores $x_k$ con un valor no nulo $\alpha_k$ ver arriba) con sus correspondientes $y_k$ et $\alpha_k$ . Con todo esto se puede calcular $f(x)$ et $f(x)=0$ identifica el límite de decisión, el signo de $f(x)$ determina la clase.

Así que para resumir:

1. Toma las asignaturas $k$ que corresponden a los vectores soporte, es decir, para los que el multiplicador de Lagrange $\alpha_k$ no es cero, para cada uno de esos sujetos se tiene el multiplicador de Lagrange $\alpha_k$ la clase $y_k \in \{-1,+1\}$ y el vector de características $x_k$ (denotado como $s_k$ para dejar claro que son vectores de apoyo);
2. Tomemos un tema para el que el multiplicador de Lagrange es estrictamente menor que $C$ y estrictamente positivo, supongamos que se trata de un objeto $m$ y utilizarlo para calcular $b$ como $b =\frac{1}{y_m} - \sum_{k \in SV} \alpha_k y_k K(x_m, s_k)$ ;
3. La ecuación que identifica el límite de decisión es $f(x)=0$ donde $f(x)=\sum_{k \in SV} \alpha_k y_k K(s_k, x) + b$