Boosting Support Vector Machines

Máquinas de vectores de soporte

En este articulo, se presenta un algoritmo de clasificación binaria basado en Support Vector Machines (Maquinas de Vectores de Soporte) que combinado apropiadamente con técnicas de Boosting consigue un mejor desempeño en cuanto a tiempo de entrenamiento y conserva características similares de generalización con un modelo de igual complejidad pero de representación mas compacta.

INTRODUCCIÓN

Las máquinas de vectores de soporte (SVM por sus siglas en inglés) han sido, en los últimos años, una técnica ampliamente aplicada a problemas de clasificación y regresión [1]. Desde el punto de vista de aprendizaje estadístico, una de las razones de su éxito es que para ciertas funciones kernel se ha demostrado que SVM es un aprendiz fuerte [2], es decir que puede alcanzar un error de generalización arbitrariamente cercano al error de Bayes con un conjunto de entrenamiento lo suficientemente grande. La principal desventaja de SVM es la complejidad temporal del algoritmo. Siendo m el número de elementos del conjunto de entrenamiento, SVM resuelve un problema de programación cuadrática que implica inicialmente complejidad O(m³). Múltiples investigaciones han propuesto métodos para mejorar esta complejidad [3] [6] llegando a que sea O(m²).

Por otra parte, algoritmos como Adaboost [7] encuentran una buena hipótesis combinando adecuadamente hipótesis dadas por un aprendiz débil, es decir un algoritmo que retorna una hipótesis cuyo desempeño es mejor que adivinar. Sin embargo, usar un algoritmo fuerte como clasificador base de Adaboost no representa gran ventaja desde el punto de vista de la generalización. Wickramaratna, Holden y Buxton han usado SVM como clasificador base de Adaboost, pero el desempeño del clasificador resultante se degrada con el aumento del número de rondas [8]. Por esta razón puede ser útil hacer de SVM un algoritmo débil para aprovechar las ventajas de Adaboost.

Adicionalmente, el debilitar SVM trae otras ventajas ya que puede utilizarse para reducir el conjunto de entrenamiento con el fin de simplificar la representación de SVM [9], lo que se conoce como algoritmo de editing.

A continuación, en la sección II se revisan los conceptos básicos de clasificación, así como los fundamentos de los algoritmos de Boosting y SVM. La sección III presenta el algoritmo propuesto de Boosting Support Vector Machines (BSVM). La sección IV muestra el análisis de los experimentos realizados y finalmente la sección V presenta las conclusiones.

PRELIMINARES

Sea Ξ un espacio de entrada, Ψ un espacio de etiquetas y Δ una distribución sobre Ξ. Dada una secuencia S = {(x_i,y_i)}^m_i=1 = de ejemplos etiquetados donde cada x_i ∈ Ξ es independiente e idénticamente distribuido de acuerdo a Δ, se asigna cada y_i ∈ Ψ de acuerdo a una regla posiblemente estocástica. En el caso de clasificación binaria se restringe Ψ = {-1,+1}.