La maldición de la dimensión v.s. máquinas de soporte vectorial
Alfonso Ruiz
La Ciencia de los Datos es un dominio reciente que combina ideas matemáticas de otras disciplinas como la teoría de la computación, la estadística y la optimización; el desarrollo de computadoras más veloces ha generado problemas desde el punto de vista teórico pues los resultados empíricos no están sustentados matemáticamente.
En este artículo vamos a hablar de por qué la estadística clásica no puede explicar teóricamente los resultados empíricos de muchos algoritmos y de un caso particular en el que sí existe un sustento matemático teórico que para aquello que los científicos de datos ven en la práctica.
El artículo está dividido de la siguiente manera:
- La maldición de la dimensión
- Teoría del aprendizaje estadístico
- Máquinas de soporte vectorial (SVM)
- Teoremas de concentración de la medida
También hemos creado unas notas que pueden descargar desde nuestro sitio así como un repositorio con el código en Python de algunos de los experimentos para ejemplificar lo expuesto.
La maldición de la dimensión
Las variables explicativas de una base de datos están encargadas de caracterizar a nuestras observaciones, por ejemplo la edad de nuestros clientes, el número de empleados de una compañía, las palabras utilizadas en un texto, el color de los píxeles de una imagen, etc.
En este texto denotaremos a las variables por una letra equis con un índice que las numera:
La maldición de la dimensión es el fenómeno desafortunado que le ocurre a un algoritmo durante el entrenamiento y que está ocasionado por tener una cantidad gigantesca de variables explicativas. Para evitar ambigüedades sobre qué significa gigantesco, es suficiente con suponer que el número de variables excede al número de observaciones al que llamaremos N.
La primera persona en llamarle Maldición de la Dimensión a este fenómeno fue Richard Bellman quien notó que la dimensión del espacio de estados en un problema de Aprendizaje por Refuerzo ocasiona terribles consecuencias en el proceso de optimización. En la actualidad este problema se resuelve sobretodo utilizando redes neuronales profundas como en el caso de AlphaGo en el que un modelo logró vencer al mejor jugador del mundo.
En este curso hablaremos sobre cómo el algoritmo de Máquinas de Soporte Vectorial es capaz de vencer a la maldición de la dimensión y cuál es el sustento matemático detrás.
Máquinas de soporte vectorial
El algoritmo de máquinas de soporte vectorial que presentaremos en esta sección busca construir un hiperplano utilizando una base de datos de clasificación supervisada. Para fijar ideas proponemos imaginar que deseamos clasificar los productos que a mi tienda le conviene comprar. La etiqueta en este caso será +1 me conviene o -1 cuando no me convenga, las características de los productos pueden incluir su precio, el histórico de nuestras ventas, si es un producto perecedero, etc.
A continuación explicamos las ideas generales del algoritmo de Máquinas de Soporte Vectorial (SVM):
- Utilizando una base de datos supervisada como la descrita, el algoritmo construye un hiperplano. Un hiperplano es una combinación lineal de las características, es decir:
- El algoritmo busca un hiperplano que clasifique correctamente a todos los elementos de la base de datos (esta hipótesis puede parecer restrictiva pero bien podríamos pedirle que clasifique cierto porcentaje correctamente). Notemos que en general habrá más de un hiperplano que satisfaga esta propiedad.
- Dentro de las opciones de hiperplanos que cumplen el inciso anterior, elegiremos aquel que maximice la distancia con el punto más cercano dentro de la base de datos. Esta idea se puede entender como la creación de una región de seguridad entre el hiperplano y los datos.
Teoría del aprendizaje estadístico
La teoría del aprendizaje estadístico es el área matemática que busca explicar la relación matemática que existe entre las siguientes cantidades:
- El número de datos N con los que entreno mi modelo.
- El número de variables d que contiene mi base de datos.
- El error esperado E en el conjunto de test.
El teorema más general del Aprendizaje Estadístico dice lo siguiente:
Si entrenamos un modelo lineal mediante cualquier algoritmo (podría no ser SVM) entonces el error E ≅ d / N
Notemos que este resultado es bastante débil pues si estamos en el régimen de la maldición de la dimensión entonces d será mucho mayor a N y por lo tanto la predicción del error es vacía desde un punto de vista práctico.
Utilizando las medidas de concentración de las que hablaremos en la siguiente sección, es posible mejorar el resultado de la siguiente manera:
Si entrenamos un modelo lineal mediante Máquinas de Soporte Vectorial entonces el error E ≅ 1 / N
Este resultado es verdaderamente sorprendente pues anula la dependencia del algoritmo y la dimensión en la que viven los datos, prácticamente no existe ningún otro algoritmo con una propiedad similar, por lo menos demostrada matemáticamente hasta el momento.
Los teoremas de concentración de la medida
El teorema más importante de la estadística clásica es la Ley de los Grandes Números y afirma que el promedio completo de una población puede ser aproximado por los promedios empíricos de un muestreo siempre y cuando garanticemos que son independientes e idénticamente distribuidos.
Para encontrar la relación entre la ley de los grandes números y la teoría del aprendizaje podemos pensar que nuestra población son todos los posibles errores en test (al entrenar el modelo con distintas bases de datos), de esta manera el error esperado que denotamos anteriormente por E es precisamente el promedio completo de esta población, mientras que los promedios empíricos son tan pequeñas como el error en el conjunto de train (el cual estamos suponiendo nulo).
El segundo teorema en importancia es el Teorema Límite Central que garantiza que los errores de aproximación cometidos por la Ley de los grandes números (es decir la diferencia entre el promedio de la población y el promedio empírico) siguen en el límite una distribución gaussiana.
Desafortunadamente estos dos resultados son límites y solo garantizan cierto comportamiento cuando el número de observaciones N es arbitrariamente grande. El tercer teorema más importante de la Teoría de la Probabilidad es la desigualdad de Hoeffding (otras versiones son de Chernoff, Bernstein, Azuma, Talagrand, McDiarmind, etc). Esta desigualdad dice lo siguiente:
La probabilidad de un error grande entre el promedio empírico y el promedio de toda la población decrece exponencialmente.
Gracias a este resultado podemos demostrar que SVM no es afectado por la maldición de la dimensión. En fórmula lo podemos escribir de la siguiente manera:
¿Dónde aprender más?
En el Colegio de Matemáticas Bourbaki ofrecemos cursos para capacitar a los estudiantes que deseen comenzar sus estudios o profundizar en la comprensión de los modelos matemáticos como por ejemplo las Máquinas de Soporte Vectorial y las bases estadísticas para comprender mejor los temas que revisamos en este post.
Estamos orgullosos por ofrecer el mejor contenido de hispanoamérica sobre estos temas, muchas gracias a todos nuestros ex-alumnos por permitirnos mejorar diariamente el contenido que ofrecemos.
Nuestros cursos incluyen casos de uso reales implementados en Python o en R, cada semana se trabaja con una base de datos distinta y el curso incluye las explicaciones matemáticas de los modelos.
Oferta académica
- Track de Ciencia de Datos. (49 semanas).
- Machine Learning & AI for the Working Analyst ( 12 semanas).
- Matemáticas para Ciencia de Datos ( 24 semanas).
- Especialización en Deep Learning. (12 semanas).
- Track de Finanzas Cuantitativas (49 semanas)
- Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
- Las matemáticas de los mercados financieros (24 semanas).
- Deep Learning for Finance (12 semanas).
