Aprendizaje automático clásico
Regresión, árboles, SVM, k-medias, vecinos cercanos
En vez de escribir las reglas, se las extrae de ejemplos. Todo método de aprendizaje es una apuesta sobre cómo generalizar desde lo visto hacia lo no visto.
Intuición
Tienes puntos rojos y azules en un plano, y te traen un punto nuevo. ¿De qué color es? Puedes mirar a sus vecinos (kNN), trazar la recta que mejor separa ambos grupos (regresión logística, SVM) o hacer preguntas sucesivas del tipo «¿ es mayor que 0,4?» (árboles de decisión). Cada estrategia dibuja una frontera de decisión distinta sobre el mismo plano; en el laboratorio las ves literalmente.
Cuando no hay etiquetas, el problema cambia: agrupar (clustering). k-medias busca centros tales que cada punto quede cerca del suyo. Es la forma más simple de descubrir estructura sin supervisión.
El dilema central es el sesgo contra varianza: un modelo demasiado rígido no captura el patrón (subajuste); uno demasiado flexible memoriza el ruido (sobreajuste). Con kNN y la frontera se vuelve una costa fractal; con grande, un trazo suave.
Mecanismo
Mínimos cuadrados (Legendre 1805, Gauss 1809) elige los parámetros que minimizan el error cuadrático; tiene solución cerrada . La regresión logística pasa una combinación lineal por la sigmoide y maximiza la verosimilitud por descenso de gradiente.
La máquina de vectores de soporte (Cortes y Vapnik, 1995) busca el hiperplano con margen máximo; solo los puntos en el borde —los vectores de soporte— determinan la solución. Con el truco del kernel (Boser, Guyon y Vapnik, 1992) se separan datos no lineales proyectándolos implícitamente a espacios de mayor dimensión. En el laboratorio, la SVM usa kernel RBF y se entrena con descenso de subgradiente sobre la pérdida bisagra.
Un árbol de decisión (CART, Breiman et al. 1984; ID3, Quinlan 1986) divide recursivamente el espacio eligiendo en cada nodo el corte que más reduce la impureza de Gini o la entropía. Los bosques aleatorios (Breiman, 2001) y el gradient boosting (Friedman, 2001) combinan cientos de árboles y siguen siendo lo mejor para datos tabulares.
Laboratorio
Cuatro fronteras de decisión
Añade puntos con clic (Mayús para la otra clase) o elige un conjunto. kNN, árbol CART, SVM-RBF y regresión logística se entrenan en vivo sobre los mismos datos.
k-medias paso a paso
Asignación y actualización alternadas del algoritmo de Lloyd, con la inercia medida en cada iteración.
Historia
- 1805
Legendre publica el método de mínimos cuadrados; Gauss reclamará haberlo usado desde 1795.
Legendre (1805), Nouvelles méthodes pour la détermination des orbites des comètes
- 1936
Fisher introduce el análisis discriminante lineal con las flores Iris.
Fisher (1936), Annals of Eugenics 7
- 1967
Cover y Hart prueban que el error de 1-NN es a lo sumo el doble del error de Bayes asintóticamente. MacQueen nombra «k-means».
Cover & Hart (1967), IEEE Trans. Inf. Theory 13; MacQueen (1967), Berkeley Symp.
- 1984
Breiman, Friedman, Olshen y Stone publican CART.
Breiman et al. (1984), Classification and Regression Trees
- 1995
Cortes y Vapnik presentan las redes de vectores de soporte; la teoría VC da garantías de generalización.
Cortes & Vapnik (1995), Machine Learning 20
- 2001
Random forests y gradient boosting: los conjuntos de árboles dominan los datos tabulares.
Breiman (2001), Machine Learning 45; Friedman (2001), Ann. Stat. 29
- 2016
XGBoost populariza el boosting escalable y gana buena parte de las competencias de Kaggle.
Chen & Guestrin (2016), KDD
Límites
Dependen de buenas características: alguien debe decidir qué medir. El aprendizaje profundo nació para aprender también la representación.
Maldición de la dimensionalidad: en muchas dimensiones todas las distancias se parecen y kNN pierde sentido.
Suponen que los datos futuros vienen de la misma distribución que los de entrenamiento (i.i.d.).
¿Qué justifica pasar de los casos observados a una regla general?
Hume planteó en 1739 que ninguna cantidad de observaciones justifica lógicamente la inducción. El teorema no free lunch (Wolpert, 1996) es su versión formal: promediado sobre todos los problemas posibles, ningún algoritmo de aprendizaje es mejor que otro.
Aprender, entonces, siempre supone un sesgo inductivo: una preferencia previa por cierto tipo de mundo (suave, lineal, jerárquico). ¿De dónde sacamos los humanos los nuestros?