16.3: Máquinas vectoriales de soporte de clasificación

En la sección anterior se analizó el uso de modelos probabilísticos (o generativos) para la clasificación, esta sección analiza el uso de técnicas discriminativas en esencia, ¿podemos ejecutar nuestros datos a través de una función para determinar su estructura? Tales técnicas discriminativas evitan el costo inherente que implica los modelos generativos que podrían requerir más información de la que realmente es necesaria.

Las técnicas de máquina vectorial de soporte implican esencialmente dibujar un vector que es perpendicular a la línea (hiperplano) que separa los datos de entrenamiento. El enfoque es que observamos los datos de entrenamiento para obtener un hiperplano de separación para que dos clases de datos se encuentren en diferentes lados del hiperplano. Hay, en general, muchos hiperplanos que pueden separar los datos, por lo que queremos dibujar el hiperplano que más separa los datos -deseamos elegir la línea que maximice la distancia desde el hiperplano a cualquier punto de datos. En otras palabras, el SVM es un clasificador de margen máximo. Se puede pensar que el hiperplano está rodeado con márgenes de igual tamaño a cada lado de la línea, sin puntos de datos dentro del margen en ninguno de los lados. Queremos trazar la línea que nos permita trazar el margen más grande. Tenga en cuenta que una vez que se determine la línea de separación y el margen, algunos puntos de datos estarán justo en el límite del margen. Estos son los puntos de datos que nos evitan ampliar más el margen, y así determinar la línea/margen. Tales puntos se llaman los vectores de soporte. Si agregamos nuevos puntos de datos fuera del margen o eliminamos puntos que no son vectores de soporte, no cambiaremos el margen máximo que podamos lograr con cualquier hiperplano.

Supongamos que el vector perpendicular al hiperplano es w, y que el hiperplano pasa por el punto\(\left(\frac{b}{|w|}\right)\). Entonces un punto x se clasifica como estar en la clase positiva si w ∗ x es mayor que b, y negativo en caso contrario. Se puede demostrar que el w óptimo, es decir, el hiperplano que logra el margen máximo, puede escribirse realmente como una combinación lineal de los vectores de datos σa _i ∗ x _i. Entonces, para clasificar un nuevo punto de datos x, necesitamos tomar el producto punto de w con x para llegar a un escalar. Observe que este escalar, σa _i ∗ (x _i ∗ x) solo depende del producto punto entre x y los vectores de entrenamiento x _i s. Además, se puede demostrar que encontrar el hiperplano de margen máximo para un conjunto de puntos (de entrenamiento) equivale a maximizar un programa lineal donde el función objetiva solo depende del producto punto de los puntos de entrenamiento entre sí. Esto es bueno porque nos dice que la complejidad de resolver ese programa lineal es independiente de la dimensión de los puntos de datos. Si precalculamos los productos de puntos por pares de los vectores de entrenamiento, entonces no importa cuál es la dimensionalidad de los datos con respecto al tiempo de ejecución de resolver el programa lineal.

Núcleos

Vemos que los SVM dependen únicamente del producto punto de los vectores. Entonces, si llamamos a nuestra transformación φ (v), para dos vectores solo nos importa el valor de φ (v ₁) ·φ (v ₂) El truco para usar kernels es darnos cuenta de que para ciertas transformaciones φ, existe una función K (v ₁, v ₂), tal que:

K (v ₁, v ₂) = φ (v ₁) · φ (v ₂)

En la relación anterior, el lado derecho es el producto punto de vectores con dimensión muy alta, pero el lado izquierdo es función de dos vectores con dimensión inferior. En nuestro ejemplo anterior de mapeo x → (x, y = x ²), obtenemos

K (x ₁, x ₂) = (x ₁ x ² ₁) · (x ₂, x ^₂) = x ₁ x ₂ + (x ₁ x ₂^{) 2}
Ahora no aplicamos realmente la transformación φ, podemos hacer todos nuestros cálculos en el espacio dimensional inferior, pero obtenemos todo el poder de usar una dimensión superior.

Los núcleos de ejemplo son los siguientes:

1. Núcleo lineal: K (v ₁, v ₂) = v ₁ · v ₂ que representa el mapeo trivial de φ (x) = x
2. Núcleo polinómico: K (v ₁, v ₂) = (1 + v ₁ · v ₂) ⁿ el cual se utilizó en el ejemplo anterior con n = 2.
3. Núcleo de base radial: K (v1, v2) = exp (−β|v1 −v2| ²) Esta transformación es en realidad de un punto v1 a una función (que puede pensarse como un punto en el espacio Hilbert) en un espacio infinito-dimensional. Entonces, lo que realmente estábamos haciendo es transformar nuestro conjunto de entrenamiento en funciones, y combinar el para obtener un límite de decisión. Las funciones son gaussianas centradas en los puntos de entrada.
4. Núcleo sigmoide: K (v1, v2) = tanh [β (v ₁ ^T v ₂ + r)] Los núcleos sigmoides han sido populares para su uso en SVM debido a su origen en redes neuronales (por ejemplo, las funciones del núcleo sigmoide son equivalentes a redes neuronales perceptrón de dos niveles). Se ha señalado en trabajos anteriores (Vapnik 1995) que la matriz del núcleo puede no ser positiva semidefinida para ciertos valores de los parámetros μ y r. Sin embargo, el núcleo sigmoide se ha utilizado en aplicaciones prácticas [2].

Aquí hay un ejemplo específico de una función del kernel. Considere las dos clases de datos unidimensionales:

{−5, −4, −3, 3, 4, 5} y {−2, −1, 0, 1, 2}

Estos datos claramente no son separables linealmente, y el mejor límite de separación que podemos encontrar podría ser x > −2.5. Ahora considere aplicar la transformación. Los datos ahora se pueden escribir como nuevos pares,

{−5, −4, −3, 3, 4, 5} → {(−5, 25), (−4, 16), (−3, 9), (3, 9), (4, 16), (5, 25)}

y

{−2, −1, 0, 1, 2} → {(−2, −4), (−1, 1), (0, 0), (1, 1), (2, 4)}

Estos datos son separables por la regla y > 6.5, y en general entre más dimensiones transformamos los datos, más separables se vuelven.

Una forma alternativa de pensar sobre este problema es transformar el clasificador de nuevo en el espacio original de baja dimensión. En este ejemplo en particular, obtendríamos la regla x ^₂ < 6.5, que biseccionaría la recta numérica en dos puntos. En general, a mayor dimensionalidad del espacio en el que nos transformamos, más complicado es un clasificador que obtenemos cuando nos transformamos de nuevo al espacio original.

Una de las advertencias de transformar los datos de entrada usando un kernel es el riesgo de sobreajustar (o sobreclasificar) los datos. De manera más general, el SVM puede generar tantas dimensiones de vectores de características que no generaliza bien a otros datos. Para evitar el sobreajuste, la validación cruzada se utiliza normalmente para evaluar el ajuste proporcionado por cada conjunto de parámetros probado durante el proceso de búsqueda de cuadrícula o patrón. En el kernel de base radial, puede aumentar esencialmente el valor de β hasta que cada punto esté dentro de su propia región de clasificación (con lo que se derrotó el proceso de clasificación por completo). Los SVM generalmente evitan este problema de sobreajuste debido a que maximizan los márgenes entre puntos de datos.

Cuando se utilizan conjuntos de entrenamiento difíciles de separar, los SVM pueden incorporar un parámetro de costo C, para permitir cierta flexibilidad en la separación de las categorías. Este parámetro controla la compensación entre permitir errores de entrenamiento y forzar márgenes rígidos. De esta manera, puede crear un margen blando que permita algunas clasificaciones erróneas. Al aumentar el valor de C se incrementa el costo de clasificar erróneamente los puntos y se fuerza la creación de un modelo más preciso que puede no generalizarse bien.

¿Podemos usar cualquier función como nuestro kernel? La respuesta a esto es proporcionada por Mercers Condition que nos proporciona un criterio analítico para elegir un kernel aceptable. Mercers Condition establece que un kernel K (x, y) es un kernel válido si y solo si se mantiene lo siguiente Para cualquier g (x) tal que\( \int g(x)^{2} dx \) sea finito, tenemos:

\[\iint K(x, y) g(x) g(y) d x d y \geq 0 \nonumber [3] \]

En total, hemos definido discriminadores SVM y mostrado cómo realizar la clasificación con funciones de mapeo de kernel adecuadas que permiten realizar cálculos en menor dimensión mientras se está para capturar toda la información disponible en dimensiones más altas. En la siguiente sección se describe la aplicación de las SVM a la clasificación de tumores para el diagnóstico de cáncer.