El matemático convertido en político

Nicolás de Condorcet fue un matemático, filósofo y político francés (1743-1794). Fue pionero en la aplicación de las matemáticas a las ciencias sociales y escribió un ensayo que, a 235 años de su publicación, sigue siendo una referencia para el estudio de los sistemas de votación.

Condorcet publicó su primer artículo académico a los 22 años y a los 25 fue admitido en la Real Academia de Ciencias. Tuvo una destacada trayectoria como servidor público, en la que promovió reformas políticas, económicas y administrativas. Formó parte del ala moderada de la revolución francesa, donde abogó por la educación laica y el voto de la mujer. Cuando el ala radical de los jacobinos tomó el control del gobierno fue perseguido y encarcelado. Murió en prisión sin que estén claras las circunstancias.

Imagen publicada en Wikipedia.

La obra más conocida de Condorcet, el “Ensayo sobre la aplicación del análisis a la probabilidad de las decisiones sometidas a la pluralidad de voces”, describe las condiciones para que una votación refleje las preferencias de la mayoría, lo que no siempre se logra en un sistema en el que se escoge una de las opciones. Además, se demuestra matemáticamente que, si los participantes tienen información para elegir sólo un poquito mejor que escogiendo al azar, la probabilidad de que una decisión por mayoría sea correcta aumenta con el número de participantes.

Pues resulta que esta idea inspira algunos de los algoritmos más poderosos de la Inteligencia Artificial (IA), conocidos como ensambles. Todo empezó en 1994, cuando el Dr. Leo Breiman, de la Universidad de California en Berkeley, propuso una técnica para hacer predicciones combinando los pronósticos de varios modelos en una especie de votación. El error de las predicciones obtenidas era hasta 40% menor al error promedio de los modelos individuales. Este algoritmo inició una línea de innovación que hasta hoy sigue dando grandes resultados.

Los métodos de ensamble

Los ensambles de algoritmos se utilizan para mejorar la exactitud de modelos de lo que se conoce como aprendizaje supervisado. Estos modelos, a partir de muchos ejemplos con uno o varios atributos, así como una categoría o valor asociado a cada ejemplo, encuentran los parámetros con mayor probabilidad de predecir el valor o categoría de un ejemplo no visto antes.

El método de ensamble creado por Breiman, que llamó Bagging como abreviatura de Bootsrap Aggregation (agregación de muestreos), consiste en generar varios modelos predictivos a partir del mismo grupo de ejemplos. Para predecir la categoría de un nuevo ejemplo, se obtiene la predicción de cada modelo y el valor definitivo es el que aparece más veces, si la categoría es un número entero, o el promedio, si es un número no entero.

Para generar modelos diferentes con un mismo conjunto de ejemplos se utilizan muestreos. Si tenemos un número n de ejemplos, se toman muestras de n ejemplos al azar (aunque se repitan), una para cada modelo. Esto produce grupos en los que algunos ejemplos aparecerán varias veces y otros no estarán. Con estos grupos se generan los modelos individuales (fase de entrenamiento).

La ilustración de abajo muestra la aplicación del Bagging a un conjunto de 9 ejemplos. Se toman 5 muestras, de 9 ejemplos cada una, y se “entrenan” 5 modelos. Luego se obtienen las predicciones de cada modelo para un nuevo ejemplo. La predicción definitiva es el valor mayoritario (0 en este caso).

El siguiente paso en la evolución de los métodos de ensamble fue en 1996, con una técnica llamada Boosting (impulso). En esta técnica ya no hay un espíritu muy democrático, pues la predicción de cada modelo recibe un peso diferente, de acuerdo con los errores que tuvo en la fase de entrenamiento. Esta técnica logró reducir aún más el error en las predicciones.

En el Boosting, cada modelo se “entrena” con el mismo grupo de ejemplos, pero cada ejemplo tiene un peso asignado (w_i), el cual se actualiza de modelo a modelo. El primer modelo se genera con todos los ejemplos con el mismo peso. Al terminar, se calcula el error total y se obtiene el peso que tendrá el modelo en la votación (α_m). Con esta información se actualizan los pesos de los ejemplos (w_i), dando mayor importancia a aquéllos en los que la predicción del modelo fue equivocada.

El siguiente modelo se “entrena” utilizando los pesos actualizados de los ejemplos. Este proceso continúa hasta generar los modelos deseados. La predicción definitiva es la suma de las predicciones de cada modelo, multiplicadas por el peso de cada uno (α_m).

La figura de abajo muestra la aplicación de la técnica a un grupo de 9 ejemplos.

El algoritmo publicado en 1996, llamado AdaBoost como abreviatura de Adaptive Boosting (impulso adaptable), es muy poderoso y sigue siendo muy utilizado. Sin embargo, la evolución de los métodos de ensamble continuó, ahora en la búsqueda de mejores procedimientos para actualizar los pesos de los ejemplos y de métodos para reducir los tiempos de cálculo.

De esta forma, entre 1999 y 2001 se publicó el algoritmo Gradient Boosting (impulso del gradiente) que actualiza los pesos de acuerdo con el impacto que el cambio tendría en el error total. En 2016 se dio a conocer un algoritmo de ensamble de árboles de decisión llamado XGBoost, como abreviatura de Extreme Gradient Boosting (Impulso extremo del gradiente), el cual aprovecha el potencial del procesamiento paralelo.

Finalmente, en 2017 se anunció otro algoritmo de ensamble de árboles de decisión llamado LightGBM, como abreviatura de Light Gradient Boosting Machine (Máquina de impulso ligero del gradiente), que implementa técnicas para ahorrar cálculos que le permiten reducir hasta en 20 veces el tiempo de proceso sin perder exactitud.

El espíritu de Condorcet

Los ensambles de algoritmos son una de las herramientas más avanzadas para desarrollar sistemas que descubren patrones en conjuntos de datos estructurados, como los de una tabla. Se utilizan en muy diversas áreas e industrias para crear herramientas muy poderosas, capaces de hacer predicciones de una gran exactitud, a partir de modelos sencillos. Una solución eficiente y elegante.

La idea formalizada por Condorcet de que, bajo ciertas condiciones, las decisiones colectivas se vuelven más acertadas entre más participantes hay encontró un fructífero campo de aplicación en un área inesperada, la Inteligencia Artificial. Ojalá y esto sirva para recordarnos que la democracia tiene fundamento, aunque haya que trabajar mucho para generar las condiciones y procedimientos para que funcione bien.

Luis Gerardo Fonseca Guzmán

blog@inteligenciafutura.mx