Compartir a través de

  • Artículo

Marzo de 2019

Volumen 34, número 3

[C#]

Máquinas de vectores de soporte que usan C#

Por James McCaffrey

Una máquina de vectores de soporte (SVM) es un sistema de software que puede realizar predicciones utilizando datos. El tipo original de SVM se diseñó para realizar una clasificación binaria; por ejemplo, para predecir el género de una persona, en función de su altura, peso e ingresos anuales. También hay variaciones de SVM que pueden realizar una clasificación multiclase (predecir una de tres o más clases) y una regresión (predecir un valor numérico).

En este artículo, presento un completo ejemplo funcional de una SVM que se implementa solo mediante C#, sin ninguna biblioteca externa. Una buena forma de ver el rumbo que tomará este artículo es examinar el programa de demostración que aparece en la Figura 1.

Programa de demostración de SVM en acción
Figura 1 Programa de demostración de SVM en acción

Para empezar, en la demostración se configuran ocho elementos de datos de entrenamiento ficticios. Cada elemento tiene tres valores de predictor seguidos de la clase que se debe predecir con la codificación -1 o +1. Los datos ficticios no representan ningún problema real, por lo que los valores de predictor no tienen ningún significado concreto. En un problema realista de SVM, es importante normalizar los valores de predictor, normalmente aplicando una normalización mínima-máxima para que todos los valores se escalen entre 0,0 y 1,0.

La demostración crea un clasificador de SVM que utiliza una función kernel polinomial. (Explicaré las funciones kernel en breve). El entrenamiento del modelo SVM genera tres vectores de soporte: (4, 5, 7), (7, 4, 2) y (9, 7, 5). Estos son los elementos de datos de entrenamiento [0], [1] y [4]. Cada vector de soporte tiene un valor de ponderación asociado: (-0,000098,-0,000162, 0,000260). Además, un modelo de SVM tiene un valor único denominado sesgo, que es -2,505727 para los datos de demostración.

Los vectores de soporte, ponderaciones y sesgos definen el modelo de SVM entrenado. El programa de demostración usa el modelo para generar los valores de la clase predichos para cada uno de los ocho elementos de entrenamiento. Un valor de decisión negativo se corresponde con una etiqueta de clase predicha de -1, mientras que un valor de decisión positivo se corresponde con una clase predicha de +1. Por lo tanto, el modelo entrenado predice correctamente los ocho elementos de entrenamiento. Esto no es muy sorprendente porque el problema es sencillo.

Para finalizar, la demostración predice la clase de un elemento nuevo y nunca visto con los valores de predictor (3, 5, 7). El valor de decisión calculado es-1,274 y, por tanto, la etiqueta de clase predicha es -1. El cálculo del valor de decisión se explica más adelante en este artículo.

En este artículo se supone que tiene conocimientos intermedios o altos de programación con C#, pero no que sepa algo sobre SVM. El programa de demostración se programa con C#, y, aunque es complicado, debería poder refactorizarlo a otro lenguaje, como Java o Python, si quiere.

El código del programa de demostración es demasiado largo para presentarlo entero en este artículo, pero el código fuente completo está disponible en la descarga de archivos que acompaña a este artículo. Se han eliminado todas las comprobaciones de errores normales para mantener las ideas principales lo más claro posible.

Estructura general del programa

La estructura del programa de demostración se muestra en la figura 2. Toda la lógica de control se incluye en un solo método Main. La clase definida por el programa SupportVectorMachine declara todos los campos de miembro como públicos para que pueda inspeccionarlos más fácilmente mediante programación.

He usado Visual Studio 2017 para crear el programa de demostración, pero no hay dependencias significativas de .NET Framework, por lo que cualquier versión de Visual Studio funcionará bien. Creé una aplicación de consola en C# y la llamé SVM_CSharp. Una vez cargado el código de plantilla en la ventana del editor, quité todo lo innecesario mediante instrucciones y, a continuación, agregué una referencia al ensamblado Collections.Generic. En la ventana Explorador de soluciones, hice clic con el botón derecho en el archivo Program.cs, le cambié el nombre a SVM_Program.cs y permití que Visual Studio cambiase automáticamente el nombre de la clase Program.

Figura 2 Estructura del programa de demostración

using System;
using System.Collections.Generic;
namespace SVM_CSharp
{
  class SVM_Program
  {
    static void Main(string[] args)
    {
      // Set up training data
      // Create SVM object, set parameters
      // Train the SVM
      // Display SVM properties
      // Use trained SVM to make a prediction
    }
  }
  public class SupportVectorMachine
  {
    // All member fields are declared public
    public SupportVectorMachine(string kernelType,
      int seed) . .
    public double PolyKernel(double[] v1, double[] v2) . .
    public double ComputeDecision(double[] input) . .
    public int Train(double[][] X_matrix,
      int[] y_vector, int maxIter) . .
    public double Accuracy(double[][] X_matrix,
      int[] y_vector) . .
    private bool TakeStep(int i1, int i2,
      double[][] X_matrix, int[] y_vector) . .
    private int ExamineExample(int i2, double[][] X_matrix,
      int[] y_vector) . .
    private double ComputeAll(double[] vector,
      double[][] X_matrix, int[] y_vector) . .
  }
}

Uso de la SVM

El programa de demostración configura ocho elementos de entrenamiento codificados de forma rígida:

double[][] train_X = new double[8][] {
  new double[] { 4,5,7 },
  ...
  new double[] { 8,9,10 }  };
int[] train_y = new int[8]{ -1, -1, -1, -1, 1, 1, 1, 1 };

En un escenario que no sea de demostración, debería normalizar los valores de predictor y, probablemente, almacenaría los datos en un archivo de texto. El clasificador de SVM se crea de este modo:

var svm = new SupportVectorMachine("poly", 0);
svm.gamma = 1.0;
svm.coef = 0.0;
svm.degree = 2;

El argumento "poly" es, realmente, un valor ficticio, ya que la SVM está codificada de forma rígida para usar una función kernel polinomial. El argumento 0 es un valor de inicialización para el componente aleatorio del algoritmo de entrenamiento. Los argumentos gamma, coef (también denominado constant) y degree son parámetros para la función kernel polinomial. A continuación, se especifican los parámetros para el algoritmo de entrenamiento:

svm.complexity = 1.0;
svm.epsilon = 0.001;
svm.tolerance = 0.001;
int maxIter = 1000;

Todos estos valores son hiperparámetros que deben determinarse mediante prueba y error. El desafío principal al usar cualquier implementación de una SVM es comprender qué núcleo se debe usar, los parámetros de kernel y los parámetros de entrenamiento. El entrenamiento se realiza mediante una sola instrucción:

int iter = svm.Train(train_X, train_y, maxIter);

Entrenar un clasificador de SVM es un proceso iterativo y el método Train devuelve el número real de iteraciones que se ejecutaron como ayuda para la depuración cuando algo va mal. Después del entrenamiento, el objeto SVM contiene una colección List<double[]> de los vectores de soporte, una matriz que contiene las ponderaciones del modelo (una por cada vector de soporte) y un único valor de sesgo. Se muestran como se indica a continuación:

foreach (double[] vec in svm.supportVectors) {
  for (int i = 0; i < vec.Length; ++i)
    Console.Write(vec[i].ToString("F1") + "  ");
  Console.WriteLine("");
}
for (int i = 0; i < svm.weights.Length; ++i)
  Console.Write(svm.weights[i].ToString("F6") + " ");
Console.WriteLine("");
Console.WriteLine("Bias = " + svm.bias.ToString("F6") + "\n");

Para finalizar, la demostración realiza una predicción:

double[] unknown = new double[] { 3, 5, 7 };
double predDecVal = svm.ComputeDecision(unknown);
Console.WriteLine("Predicted value for (3.0 5.0 7.0) = " +
  predDecVal.ToString("F3"));
int predLabel = Math.Sign(predDecVal);
Console.WriteLine("Predicted label for (3.0 5.0 7.0) = " +
  predLabel);

El valor de decisión es de tipo doble. Si el valor de decisión es negativo, la clase predicha es -1, mientras que si el valor de la decisión es positivo, la clase predicha es +1.

Descripción de las SVM

Las SVM son bastante difíciles de entender y extremadamente difíciles de implementar. Eche un vistazo al gráfico de la Figura 3. El objetivo es crear una regla que distinga entre los datos de color rojo y los de color azul. El gráfico muestra un problema donde los datos tienen solo dos dimensiones (número de variables de predictor) para que se pueda visualizar el problema, pero las SVM pueden trabajar con datos con tres o más dimensiones.

Conceptos básicos de SVM
Figura 3 Conceptos básicos de SVM

Una SVM funciona buscando la pista más ancha posible que separa las dos clases y, a continuación, identifica el punto o puntos de cada clase más cercanos al borde de la pista de separación.

Para clasificar un punto de datos nuevo nunca visto, solo tiene que ver en qué lado de la mitad de la pista se encuentra el nuevo punto. En la figura 3, el punto rojo con un círculo alrededor en (0,3, 0,65) y los puntos azules con un círculo alrededor en (0,5, 0,75) y (0,65, 0,6) se denominan vectores de soporte. Sin embargo, en mi cabeza, pienso en ellos como "puntos de soporte" porque suelo pensar en los vectores como líneas.

Hay tres retos importantes que deben resolverse para implementar una SVM que se pueda usar. En primer lugar, ¿qué debe hacer si los datos no son separables linealmente, como en la figura 3? En segundo lugar, ¿cómo se encuentran los valores de vector, ponderación y sesgo de soporte? En tercer lugar, ¿qué hay que hacer con los puntos de datos de entrenamiento anómalos situados en el lado equivocado de la pista límite?

Como se muestra en este artículo, puede tratar con datos que no sean linealmente separables mediante el uso de las denominadas funciones kernel. Puede determinar los vectores, ponderaciones y sesgos de soporte mediante un algoritmo denominado optimización mínima secuencial (SMO). Y puede gestionar datos de entrenamiento incoherentes con una idea denominada complejidad, que penaliza los datos incorrectos.

Funciones kernel

Hay muchos tipos diferentes de funciones kernel. En pocas palabras, una función kernel toma dos vectores y los combina de alguna forma para generar un único valor escalar. Aunque no es obvio, al usar una función kernel, puede habilitar una SVM para gestionar datos que no sean separables linealmente. Esto se denomina "el truco de kernel".

Suponga que tiene un vector v1 = (3, 5, 2) y un segundo vector v2 = (4, 1, 0). Un kernel muy sencillo se denomina kernel lineal y devuelve la suma de los productos de los elementos del vector:

K(v1, v2) = (3 * 4) + (5 * 1) + (2 * 0) = 17.0

Muchas funciones kernel tienen un factor de escala opcional, a menudo denominado gamma. Para el ejemplo anterior, si gamma se define en 0,5, entonces:

K(v1, v2) = 0.5 * [(3 * 4) + (5 * 1) + (2 * 0)] = 8.5

El programa de demostración usa un kernel polinomial con los valores degree = 2, gamma = 1,0 y constant = 0. En otras palabras, se calcula la suma de los productos, se multiplica por gamma, se agrega el valor de constant y se eleva al valor de degree. Por ejemplo:

K(v1, v2) = [1.0 * ((3*4) + (5*1) + (2*0)) + 0]^2 = (1 * 17 + 0)^2 = 289.0

El programa de demostración implementa el kernel polinomial como se indica a continuación:

public double PolyKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += v1[i] * v2[i];
  double z = this.gamma * sum + this.coef;
  return Math.Pow(z, this.degree);
}

Los valores de gamma, degree y constant (denominado coef para evitar un conflicto de nombre con una palabra clave del lenguaje) son miembros de clase y sus valores se suministran en otro lugar. El programa de demostración codifica de forma rígida la función kernel, de modo que, si quiere experimentar con otra función, tendrá que implementarla por sí mismo.

Una alternativa común al kernel polinomial es el kernel de función de base radial (RBF). En otras palabras, se suman las diferencias cuadradas entre los elementos, se multiplica por el valor negativo de gamma y se eleva a e (número de Euler; aproximadamente, 2.718). En el código, el kernel de RBF podría tener este aspecto:

public double RbfKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += (v1[i] - v2[i]) * (v1[i] - v2[i]);
    return Math.Exp(-this.gamma * sum);
}

Tenga en cuenta que distintas funciones de kernel tienen distintos parámetros. Los kernels lineales y RBF solo necesitan el valor de gamma, pero el kernel polinomial requiere los valores d gamma, degree y constant. La elección de la función kernel que se debe usar y los valores de los parámetros que se aplican a la función kernel que se usa son parámetros libres y se deben determinar mediante prueba y error. Todas las técnicas de clasificación de aprendizaje automático disponen de hiperparámetros, pero las SVM suelen ser especialmente sensibles a sus valores de hiperparámetros.

Algoritmo de optimización mínima secuencial

Existen muchos algoritmos que pueden usarse para determinar los vectores de soporte para un problema de SVM. El algoritmo SMO es el más común. El programa de demostración sigue la explicación original de SMO del artículo de investigación de 1998 "Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines” (Optimización mínima secuencial: un algoritmo rápido para entrenar máquinas de vectores de soporte), disponible en muchos sitios de Internet.

El algoritmo SMO es muy complejo y una explicación completa requeriría unas 200 páginas (lo sé porque una vez revisé un libro entero dedicado a SMO). SMO tiene tres funciones principales: una función de nivel superior "Train" que llama a una función auxiliar ExamineExample, que, a su vez, llama a la función auxiliar TakeStep.

La firma de TakeStep es: private bool TakeStep(int i1, int i2, double[][] X_matrix, int[] y_vector). El parámetro X_matrix contiene los valores de predictor de datos de entrenamiento. El parámetro y_vector contiene los valores de destino de los datos de entrenamiento, que son -1 o +1. Los parámetros i1 e i2 son un primer índice y un segundo índice que apuntan a los datos de entrenamiento. En cada llamada a TakeStep, el algoritmo intenta encontrar una solución mejor y devuelve true si se encuentra una mejora con los dos elementos de datos de entrenamiento; en caso contrario, devuelve false.

La firma de ExamineExample es: private int Examine­Example(nt i2, double[][] X_matrix, int[] y_vector). La función devuelve el número de cambios que se han producido para que TakeStep pueda determinar si ha habido algún progreso.

Tanto TakeStep como ExamineExample utilizan una variable de ámbito de clase denominada complexity. Los valores más altos de complejidad penalizan cada vez más los datos de entrenamiento de valores atípicos y obligan al algoritmo SMO a intentar encontrar una solución para estos, a costa del sobreajuste del modelo. Dado que complexity es un parámetro que usa SMO, siempre estará presente, a diferencia de los parámetros asociados con la función de kernel que se usa, que podría estar presente o ausente.

La función TakeStep usa una variable de ámbito de clase denominada epsilon, y la función ExamineExample usa una variable de ámbito de clase denominada tolerance. Ambos son valores pequeños, establecidos en 0,001 de forma predeterminada en la demostración. Epsilon se usa internamente para determinar cuándo se debe detener la iteración, lo que, a su vez, afecta al número de vectores de soporte que se encuentran. Tolerance se usa para calcular el error. Los valores de epsilon y tolerance son parámetros libres y el efecto de cambiarlos puede variar bastante (de un efecto muy pequeño a uno muy grande) en función del problema en cuestión.

El código para el método Train se presenta en la figura 4. El método es iterativo y devuelve el número de iteraciones que se realizaron. El método acepta un parámetro maxIter para establecer un límite máximo para el número de iteraciones que se realizan. En teoría, el algoritmo SMO siempre converge y la iteración se detiene, pero la teoría no siempre coincide con la práctica con un algoritmo tan complejo como SMO.

Figura 4 El Método de entrenamiento

public int Train(double[][] X_matrix, int[] y_vector, int maxIter)
{
  int N = X_matrix.Length;
  this.alpha = new double[N];
  this.errors = new double[N];
  int numChanged = 0;
  bool examineAll = true;
  int iter = 0;
  while (iter < maxIter && numChanged > 0 || examineAll == true) {
    ++iter;
    numChanged = 0;
    if (examineAll == true) {
      for (int i = 0; i < N; ++i)
        numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    else {
      for (int i = 0; i < N; ++i)
        if (this.alpha[i] != 0 && this.alpha[i] !=
          this.complexity)
          numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    if (examineAll == true)
      examineAll = false;
    else if (numChanged == 0)
      examineAll = true;
  } // While
  List<int> indices = new List<int>();  // support vectors
  for (int i = 0; i < N; ++i) {
    // Only store vectors with Lagrange multipliers > 0
    if (this.alpha[i] > 0) indices.Add(i);
  }
  int num_supp_vectors = indices.Count;
  this.weights = new double[num_supp_vectors];
  for (int i = 0; i < num_supp_vectors; ++i) {
    int j = indices[i];
    this.supportVectors.Add(X_matrix[j]);
    this.weights[i] = this.alpha[j] * y_vector[j];
  }
  this.bias = -1 * this.bias;
  return iter;
}

Además de devolver explícitamente el número de iteraciones que se realizan, Train busca y almacena los índices de los elementos de datos de entrenamiento que son vectores de soporte. Una vez que se conoce el número de vectores de soporte, se puede asignar la matriz que contiene los valores de las ponderaciones. Los valores de ponderación son valores alfa distintos de cero.

El método Train tiene muchos puntos de personalización posibles. Por ejemplo, el código de demostración almacena los vectores de soporte como una colección List<double[]>. Una alternativa es, simplemente, almacenar los índices de los vectores de soporte en una colección List<int> o en un objeto de matriz int[]. Examinar el método Train atentamente es la mejor manera de comenzar a comprender las SVM y el algoritmo SMO.

Comprender el mecanismo de SVM

Si consulta la figura 1, verá que la SVM entrenada tiene tres vectores de soporte: (4, 5, 7), (7, 4, 2) y (9, 7, 5). Y el modelo tiene tres valores de ponderación = (-0,000098, -0,000162, 0,000260) y un sesgo =-2,506. Para calcular el valor de decisión de la entrada (3, 5, 7), se calcula el valor de la función kernel con cada uno de los tres vectores de soporte y, a continuación, se multiplica cada valor de kernel por su correspondiente ponderación, se suma y, luego, se agrega el sesgo:

x = (3, 5, 7)
sv1 = (4, 5, 7)
sv2 = (7, 4, 2)
sv3 = (9, 7, 5)
K(x, sv1) * wt1 = 7396.0 * -0.000098 = -0.725
K(x, sv2) * wt2 = 3025.0 * -0.000162 = -0.490
K(x, sv3) * wt3 = 9409.0 * 0.000260 = 2.446
decision = -0.725 + -0.490 + 2.446 + -2.506 = -1.274
prediction = Sign(decision) = -1

Tenga en cuenta que, si no se normalizan los valores de predictor, como en la demostración, los valores de los kernels pueden ser muy grandes, lo que obliga a los valores de ponderación a ser muy pequeños. Esto podría generar errores aritméticos.

El mecanismo de SVM señala las ventajas y desventajas de la técnica. La SVM se centra únicamente en los vectores de soporte clave y, por tanto, tiende a ser resistente a datos de entrenamiento incorrectos. Cuando el número de vectores de soporte es pequeño, una SVM es, de algún modo, interpretable, lo que supone una ventaja en comparación con muchas otras técnicas. En comparación con muchas otras técnicas de clasificación, en particular, las redes neuronales, las SVM suelen funcionar bien con datos de entrenamiento limitados. Sin embargo, las SVM pueden tener problemas a la hora de gestionar conjuntos de datos de entrenamiento muy grandes. El principal inconveniente de las SVM es que son muy complejas y requieren que especifique el valor de muchos hiperparámetros.

Resumen

Como se muestra en este artículo, la implementación de una máquina de vectores de soporte es algo bastante complejo y difícil. Debido a esto, hay muy pocas implementaciones de biblioteca de SVM disponibles. La mayoría de bibliotecas de SVM se basan en una implementación de C++ denominada LibSVM que creó un grupo de investigadores. Dado que una llamada a C++ suele resultar difícil, hay varias bibliotecas que proporcionan contenedores a través de LibSVM escritos en Python, Java, C# y otros lenguajes.

Al experimentar con el código que se presenta en este artículo, podrá comprender cómo funcionan las SVM, exactamente, y usar una implementación de biblioteca de un modo más eficaz. Dado que el código de este artículo es independiente y está simplificado, podrá explorar funciones kernel alternativas y sus parámetros, además de los parámetros epsilon, tolerance y complexity del algoritmo de entrenamiento SMO.

El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en varios productos clave de Microsoft, como Internet Explorer y Bing. Puede ponerse en contacto con el Dr. McCaffrey en jamccaff@microsoft.com.

Gracias a los siguientes expertos técnicos de Microsoft por revisar este artículo: Yihe Dong, Chris Lee