Un algoritmo de aprendizaje automático halla construcciones que se creían imposibles en la teoría de grafos
Una inteligencia artificial ha refutado cinco conjeturas matemáticas -teoremas no probados- en combinatoria extrema y teoría de grafos sin ayuda humana, sin ningún entrenamiento ni información previa sobre el tema.
Adam Zsolt Wagner, postdoctorado de la Universidad de Tel Aviv en Israel e investigador especializado en aprendizaje automático, combinatoria y teoría de grafos, utilizó un algoritmo de aprendizaje automático para buscar ejemplos que refutaran una serie de conjeturas que llevan tiempo asentadas en la teoría de grafos, un área de las matemáticas que implica el estudio de objetos configurados por una serie de puntos (los vértices) conectados por líneas (las aristas).
Los matemáticos pensaban que estas conjeturas eran ciertas, aunque sin haber podido probarlas, porque no habían encontrado una construcción que demostrase que son falsas.
La ‘creatividad’ de las máquinas
“Los matemáticos tienen muchas técnicas para encontrar tales construcciones, pero a veces el contraejemplo de una conjetura tiene una estructura muy extraña, y los humanos carecemos de creatividad para encontrarlos; por suerte, los ordenadores no están sujetos a los mismos límites de creatividad que nosotros, ya que piensan de forma diferente, y de ahí que mi programa haya encontrado contraejemplos a cinco conjeturas”, explica Wagner en una entrevista online con La Vanguardia .
“A veces el contraejemplo de una conjetura tiene una estructura muy extraña y los humanos carecemos de creatividad para encontrarlo
Para hacerlo posible, utilizó un algoritmo de aprendizaje por refuerzo, un programa similar a los que aprenden juegos partiendo solo de las reglas y practicando por su cuenta, como el famoso AlphaZero de Deepmind, que alcanzó por si solo un nivel de ajedrez sobrehumano. “Mi programa es mucho menos sofisticado, pero aún así fue lo suficientemente bueno para encontrar contraejemplos”, apunta Wagner.
El método
Aprender jugando
Y explica que el funcionamiento de su inteligencia artificial es sencillo. “Formula una conjetura como un juego; un jugador construye una gráfica y recibe una puntuación en función de lo cerca que esté de ser un contraejemplo; luego construye otra nueva figura y recibe una nueva puntuación; y así juega sucesivamente, mejorando sus construcciones y, si tenemos suerte, tras uno o dos días de aprendizaje ha encontrado una construcción que es mejor de lo que los humamos pensaban que era posible y, por tanto, hemos refutado la conjetura”, detalla.
Y añade que “lo divertido de este método es que el programa empieza sin saber nada: solo ingresamos la conjetura que tiene que refutar y dejamos que la magia del aprendizaje reforzado resuelva el resto; esto significa que no tuve que pensar en nada: una vez que el programa funcionó, solo metí alrededor de cien conjeturas y en el transcurso de unos meses se las arregló para refutar estas cinco”.
Lo divertido de este método es que el programa empieza sin saber nada
Entre las conjeturas desmontadas se encuentran una pregunta de Brualdi y Cao sobre la maximización de permanentes de patrones evitando matrices, y varios problemas relacionados con los valores propios de adyacencia y distancia de los gráficos.
El matemático Timothy Gowers, director de investigación en Cambridge, ha asegurado en Twitter que el programa de Wagner puede resultar gran ayuda para los investigadores matemáticos al permitirles comprobar de manera sencilla sus conjeturas antes de seguir adelante en sus formulaciones y cálculos.