Dr. Arturo Berrones Santos

El Dr. Arturo Berrones es Lic. en Física por la Facultad de Ciencias Físico Matemáticas de la UANL. Estudió el Doctorado en Ciencias (Física) en la Universidad Autónoma del Estado de Morelos, graduándose con una tesis desarrollada en el Instituto de Ciencias Físicas de la UNAM dentro del campo de la Mecánica Estadística. El Dr. Arturo es miembro del Sistema Nacional de Investigadores en el nivel 1. Sus intereses son las interrelaciones entre las ciencias computacionales, la física estadística y las matemáticas aplicadas.

   

Formulación de la optimización no-lineal y del aprendizaje de máquina como sistemas desordenados

 26/feb/2021  Seminario PISIS-UANL 2021      Asistencia : 29

Introducción

En esta ocasión el Dr. Berrones nos habla acerca de la combinación del aprendizaje automático y la programación matemática. El objetivo de esta charla se centra en introducir al auditorio el concepto de los sistema desordenado y la interrelación entre la física estadística y la optimización combinatoria para esto se presenta el problema de la mochila cuadrática y un problema de máquinas de boltzmann. El Dr. Arturo nos comenta sobre la falta de integración de herramientas utilizadas en la investigación de sistemas desordenados en el campo de la investigación de operaciones y como puede ser de gran ayuda para la solución de problemas. Uno de los aportes más destacados de su investigación consiste en la capacidad de resolver problemas de optimización no lineal considerando la física estadística avanzada, en particular, la distribución de probabilidad de las soluciones.

Resumen

En la charla el Dr. Arturo nos presenta dos artículos de investigación científica que nos muestran la relación entre la física estadística y la investigación de operaciones. Para el primer artículo basado en el problema de la mochila cuadrática, se utiliza la física estadística para inferir el comportamiento de los coeficientes de conectividad, que establecen la relación entre las variables de decisión, por lo cual, se analiza a profundidad la estructura estadística de las instancias logrando incluso saber qué instancias serán difíciles para este problema. Mientras que para el segundo artículo presentado se busca generar un modelo de programación entero-mixto para el aprendizaje no supervisado a través de las máquinas de Boltzmann.

Los principales inconvenientes que se encontraron en esta investigación fueron que al aplicar al problema de la mochila cuadrática los coeficientes de acoplamiento negativos, se tiene una función objetivo no convexa en el modelo de Isin haciéndose un problema muy difícil de resolver de manera exacta. Para el problema de muestreo, el principal inconveniente es en las zonas de convergencia (por ejemplo: máximos de una función objetivo) que quedan separadas y estos métodos se quedan “atorados” en una región de máximos locales por mucho tiempo. Por último, se indica que el uso de modelos de aprendizaje-máquina es recomendable ya que al conocer la estructura de los datos presenta buenos resultados de estos problemas complejos.

Conclusiones

De acuerdo con los métodos de solución presentados, el problema de la mochila cuadrada logra incrementar la calidad de la solución y se cree que podría generar soluciones iniciales de alta calidad para procedimientos de búsqueda local. Una de las principales aportaciones es exponer diversas formas de integrar la física estadística y la optimización combinatoria. Actualmente, se continúa desarrollando un modelo entero-mixto para una máquina de Boltzmann enteramente conectada, el cual proporciona una estadística correcta de los patrones que se le enseñan al algoritmo.

Fe de erratas: A solicitud del doctor Arturo Berrones se aclaran los siguientes puntos: sobre el comentario de “basta con que haya elementos de signo negativo en la matriz de interacciones de la mochila cuadrática para tener un problema no convexo” (en general eso es cierto pero no necesariamente), lo correcto es que la matriz de interacciones debe ser positiva definida para que la mochila cuadrática sea convexa. Además, aclara que: “probar un algoritmo sobre un conjunto de instancias muestreadas como variables aleatorias independientes es como probar siempre la misma instancia”. Eso es cierto si los intervalos para los distintos coeficientes son siempre los mismos. Puede influir mucho en la dificultad de la instancia cambiar los intervalos de existencia de los coeficientes aunque estos sigan siendo independientes. Para más detalles, ver el paper: Where are the hard knapsack problems?

Enlaces relevantes

Reseñas anteriores