La matemática es el arte de resolver problemas. ¿Nos superarán los ordenadores en esta tarea? Tratamos hoy esta cuestión.
Una polémica en MathOverflow
Dos usuarios de MathOverflow han mantenido recientemente una polémica sobre el tema. Son los usuarios fedja y Iosif Pinelis.
fedja responde en muchas ocasiones a preguntas aparentemente imposibles, demostrando desigualdades increíbles en una forma que lo deja a uno lleno de admiración. No obstante, él sostiene que sus soluciones podrían ser encontradas igualmente por una inteligencia artificial (IA). Para fedja, una solución tiene que ser comprendida por un humano. Un humano con sus capacidades usuales, entre las que no incluye la habilidad de multiplicar números de dos cifras, de manera que no confía en los programas de cálculo simbólico del tipo de Mathematica.
Iosif Pinelis también resuelve problemas que sorprenden por su ingenio, pero no duda, cuando es necesario, en usar Mathematica. Sin embargo, Pinelis duda mucho que una IA sea capaz de imitar las acrobacias de fedja en sus soluciones.
Para fedja la solución de un problema matemático es como jugar una partida de ajedrez. En cada momento tiene una posición y tiene que tratar de mover a una posición más favorable. Uno puede medir si la posición es más favorable por indicadores simples: número de ecuaciones, número de variables, número de ocurrencias de cada variable, capacidad de aplicar teoremas conocidos. Al igual que en el ajedrez uno no ve la posición vencedora hasta que casi llega al final, simplemente trata de conseguir un pequeño avance en cada jugada.
Como en el ajedrez, hay sacrificios, que son aceptables si simplifican y mejoran la situación. Así, si quiero probar \(A<B\), puedo demostrar \(A<C\) y reducir el problema a probar \(C<B\). Sacrificando la ventaja \(C-A\).
Esta comparación con el ajedrez es correcta, pero ya expliqué en otra entrada anterior cuál es la diferencia muy importante para mí. En el ajedrez lo que cuenta es sobre todo tu peor jugada y en cambio en matemática solo cuenta tu mejor jugada.
El caso del ajedrez y la inteligencia artificial
Desde el inicio de los computadores se ha intentado que jugaran al ajedrez. Un éxito fundamental de la Inteligencia Artificial se dio en 1997 cuando Deep Blue ganó al campeón mundial Kasparov. Este programa evaluaba las posiciones utilizando una base de datos con las partidas de los mejores jugadores humanos, cuidadosos pesos construidos por jugadores profesionales y programadores, combinados con una búsqueda en el espacio de jugadas a una velocidad de unos 200 millones de posiciones por segundo. Una estrategia parecida es la que parece proponer fedja, y en sus soluciones trata de exponer algunos de los pesos y criterios para estimar cada posición.
La inteligencia artificial ha dado un salto muy grande desde Deep Blue. En 2017 se presentó AlphaZero. Este programa es capaz de vencer a todos los anteriores, pero su estrategia es muy diferente. Es un algoritmo de propósito general, que aprende desde cero. No necesita input de jugadores humanos. Es capaz de jugar a distintos juegos: ha conseguido jugar mejor que cualquier otro anterior al ajedrez, al go, y también al shogi (el ajedrez japonés, que se juega en un tablero mayor, con más tipos de fichas y capturas que se convierten en fichas del contrario).
AlphaZero usa una red neuronal interna que toma la posición \(s\) como entrada y retorna un vector de probabilidades, asignando una probabilidad a cada jugada posible y un valor \(v\) estimando la esperanza del resultado del juego. AlphaZero estima estas probabilidades por medio de auto-juego. De manera que desde cero avanza mediante juegos simulados consigo mismo hasta una posición de Gran Maestro.
El entrenamiento dura aproximadamente 9 horas en el ajedrez, 12 horas en el shogi y 13 días en el go.
AlphaZero estudia 60000 posiciones por segundo. Mucho menos que su antecesor Deep Blue. AlphaZero se concentra en posiciones más prometedoras. La distancia entre AlphaZero y los anteriores programas es como la de gran maestro a un buen jugador aficionado. No son rivales para AlphaZero. Gana a los programas anteriores aunque solo se le permita usar en cada jugada la décima parte de tiempo que a su oponente.
La característica del juego de AlphaZero es que es más atrevido, sacrificando piezas para obtener ventajas estratégicas a largo plazo. Algunos jugadores humanos piensan que su juego es como el de un extraterrestre con inteligencia superior.
Los creadores de AlphaZero no han intentado aplicar este método a la solución de problemas matemáticos. Ni siquiera a un tipo particular como la demostración de desigualdades. Resolver problemas matemáticos en general es más complicado que resolver problemas en la clase NP, de forma que querer que resuelva cualquier problema matemático posiblemente sea querer demasiado. ¿Qué sería una posición?, ¿qué una jugada válida? Si restringimos el campo a la demostración de desigualdades de algún tipo, por ejemplo que se puedan expresar mediante funciones elementales, integración y sumas, es posible que podamos hacer que un programa del tipo AlphaZero aprenda a resolverlos.
De todos modos, incluso con esa definición restringida, el resultado final se parece mucho a dar la solución de un problema concreto en la clase NP. Si nos dan la prueba, seremos capaces de comprobarla en tiempo polinómico a su longitud. Pero aquí se trata de encontrar la prueba.
Ya lo decía en la entrada anterior (El algoritmo que nadie quiere ver), hay un algoritmo: entrena a un humano. En los próximos años veremos si realmente los ordenadores consiguen superarnos. Yo creo que es probable que lo consigan. Pero es posible que cuando consigamos que un programa sea capaz de resolver problemas matemáticos, no consigamos que resuelva nuestros problemas, porque (el algoritmo) tendrá los suyos propios.
Pólya y la solución de problemas
Pólya cuenta cómo, cuando veía una construcción matemática complicada, se decía a sí mismo: «Sí, la demostración parece correcta, pero ¿cómo ha llegado a ella? ¿Cómo puedo yo hacer algo semejante?» Su libro How to solve it? da directrices generales de cómo resolver problemas. Directrices que se pueden aplicar a cualquier problema: Usar una buena notación, considerar un caso particular, considerar un caso más general, buscar un problema análogo ya resuelto para imitar la solución, resolver un problema análogo más simple, etc. Cada una de esas sugerencias es como un movimiento en el ajedrez.
Pólya hizo un gran trabajo: describir qué debemos entender por un movimiento en la solución de problemas. Esto es esencial a la hora de programar un ordenador para que realice la tarea.
Ejemplo de solución de problemas
Para mostrar la argumentación de fedja debemos recurrir a un ejemplo. Consideraremos una de sus soluciones en MathOverflow y la analizaremos detallando los movimientos y cómo la «posición» se va mejorando. Creo que el ejemplo da mucha fuerza al argumento de fedja.
Varias entradas en MathOverflow pueden servir de ejemplo. Hay una entrada en la que fedja explica sus métodos y por qué piensa que una IA podría hacerlo mejor. Pero en lugar de esta entrada que enlazaré en la última sección y que quizás es demasiado larga, comentaré otra que es la que originó la polémica entre fedja y Iosif Pinelis.
El problema fue planteado por el usuario Vladimir:
Problema. Consideremos la función $$q(t,a)=4\Bigl(1+\frac{t}{x(t,a)}\Bigr)^{-a-1/2}\Bigl(1-\frac{2}{x(t,a)}\Bigr)^{1/2}(x(t,a))^{-3/2}(z(t,a))^{1/4}\Bigl(1+\frac{t}{2}\Bigr)^a,$$ donde \(t>0\), \(0<a<1\), $$x(t,a)=\frac{a-1}{2}t+\frac32+\frac12\sqrt{z(t,a)},$$ y $$z(t,a)=(1-a)^2t^2+2(3-a)t+9.$$ Se pide probar que \(q(t,a)<1\) para todo \(t>0\) y \(0<a<1\). Comprobaciones numéricas sugieren que esto es correcto.
(A) Cambiamos de notación: usaremos \(x\), \(z\) en lugar de \(x(t,a)\) y \(z(t,a)\) y llamaremos \(Q\) a la cantidad que queremos acotar, $$Q:=4\Bigl(1+\frac{t}{x }\Bigr)^{-a-1/2}\Bigl(1-\frac{2}{x }\Bigr)^{1/2}x^{-3/2}z^{1/4}\Bigl(1+\frac{t}{2}\Bigr)^a,$$ hasta la vista descansa escribiéndolo así. Nuestro objetivo es probar \(Q<1\).
(B) Es claro que \(x\) resulta de la solución de una ecuación cuadrática en la que \(z\) es el discriminante. Es fácil escribir la ecuación cuadrática sabiendo quién es \(x\): $$x^2+[(a-1)t+3]x+(2a-3)t=0.$$ Nuestro \(x\) va a verificar esta ecuación y está relacionado con \(z\) mediante $$\sqrt{z}=2x-3-(a-1)t.$$ Por tanto $$Q:=4\Bigl(1+\frac{t}{x }\Bigr)^{-a-1/2}\Bigl(1-\frac{2}{x }\Bigr)^{1/2}x^{-3/2}(2x-3-(a-1)t)^{1/2}\Bigl(1+\frac{t}{2}\Bigr)^a.$$ Es decir, \(0<a<1\) y \(t>0\) se dan arbitrariamente, se determina \(x\) por la ecuación cuadrática (como \(z>0\), se trata de la solución mayor de la ecuación cuadrática) y con esos elementos se determina \(Q\). Hemos eliminado la variable \(z\) y una sola ecuación cuadrática sustituye a las ecuaciones que definían \(x\) y \(z\).
(C) Tomando como nueva variable, en lugar de \(x\), a \(y=x-r\) conseguimos una ecuación en la que el término independiente no depende de \(a\) eligiendo \(r=2\), de manera que hacemos este cambio, tomamos \(y=x+2\) y nuestro problema es acotar $$Q:=4\Bigl(1+\frac{t}{y+2}\Bigr)^{-a-1/2}\Bigl(1-\frac{2}{y+2}\Bigr)^{1/2}(y+2)^{-3/2}(2y+1-(a-1)t)^{1/2}\Bigl(1+\frac{t}{2}\Bigr)^a,$$ siendo \(y\) la mayor solución de $$y^2+[1+(1-a)t]y=2+t.$$
(D) Simplificamos todavía la ecuación cuadrática si cambiamos la variable \(t\) por la \(T\) relacionada mediante $$T=1+(1-a)t,\quad\text{y entonces}\quad 2+t=1+\frac{T-a}{1-a}$$ (luego la restricción \(t>0\) se convierte en \(T>1\)). Con esto, los términos que aparecen en \(Q\) se transforman en $$\frac{t}{2}+1=\frac{y(y+T)}{2},$$ $$t=\frac{(y-1)(y+2)}{1-(1-a)y},$$ así que $$1+\frac{t}{y+2}=\frac{ay}{1-(1-a)y},$$ $$2x-(a-1)t-3=2y+T.$$ Llevando esto a \(Q\) y reordenando algo, $$Q=4\Bigl[\frac{(y+T)(1-(1-a)y)}{2a}\Bigr]^a\Bigl[\frac{(1-(1-a)y)}{ay}\Bigr]^{1/2}\Bigl[\frac{y}{y+2}\Bigr]^{1/2}\frac{1}{(y+2)^{3/2}}(2y+T)^{1/2},$$ $$Q=4\Bigl[\frac{(y+T)(1-(1-a)y)}{2a}\Bigr]^a\Bigl[\frac{(1-(1-a)y)}{a}\Bigr]^{1/2} \frac{1}{(y+2)^2}(2y+T)^{1/2}.$$ Hemos introducido las variables \(y\) y \(T\) en lugar de \(x\) y \(t\), simplificando así \(Q\) y sobre todo la ecuación cuadrática.
(E) el primer factor requiere una atención especial. Notemos que de la ecuación cuadrática y la definición de \(T\) se sigue que $$y(y+T)=1+\frac{T-a}{1-a},$$ $$\Bigl[\frac{(y+T)(1-(1-a)y)}{2a}\Bigr]^a=\Bigl[\frac{y-1+2a}{2a}\Bigr]^a.$$ Luego $$Q=4\Bigl[\frac{y-1+2a}{2a}\Bigr]^a\Bigl[\frac{(1-(1-a)y)}{a}\Bigr]^{1/2} \frac{1}{(y+2)^2}(2y+T)^{1/2}.$$
Hemos simplificado \(Q\).
(F) Notemos que \(\frac{y-1+2a}{2a}>0\) y que la función \(x\mapsto u^x\) es convexa para todo \(u>0\), de forma que por la definición de convexidad $$u^{(1-a)0+a1}\le (1-a)u^0+a u\le 1-a+au.$$ En nuestro caso $$\Bigl[\frac{y-1+2a}{2a}\Bigr]^a\le 1-a+a\frac{y-1+2a}{2a}=\frac{y+1}{2},$$ así que con un pequeño sacrificio nos queda probar $Q_0<1$, donde $$Q_0:=2(y+1)\Bigl[\frac{(1-(1-a)y)}{a}\Bigr]^{1/2}\frac{1}{(y+2)^2}(2y+T)^{1/2},$$ que simplificamos en $$Q_0=\frac{2(y+1)}{(y+2)^2}\Bigl[\frac{(1-(1-a)y)}{a}(2y+T)\Bigr]^{1/2}.$$
(G) Ahora el factor mas complicado nos invita a estudiar la función $$F(T)=\frac{(1-(1-a)y)}{a}(2y+T).$$
Aquí \(a\) es un parámetro, \(T\) es la variable, la dependencia en \(T\) también se hace a través de \(y\), que es función de \(T\) debido a la ecuación cuadrática $$(1-a)y(y+T)=1-2a+T.$$ Estudiemos la derivada logarítmica de \(F(T)\), para estudiar como varía \(F(T)\): $$\frac{d}{dT}\log F(T)=-\frac{(1-a)\dot y}{1-(1-a)y}+\frac{2\dot y+1}{2y+T}.$$ Derivando la ecuación cuadrática obtenemos $$(1-a)(2y+T)\dot y=1-(1-a)y,$$ por tanto (recordando que \(T\ge1\)), $$\frac{d}{dT}\log F(T)=\frac{2\dot y}{2y+T}\le \frac{2\dot y}{2y+1}=\frac{d}{dT}\log (2y+1).$$ Las dos derivadas son iguales cuando \(T=1\). Para \(T=1\), \(t=0\), \(y(y+1)=2\), luego \(y=1\) y entonces \(F(T)=3=2y+1\). Luego en todo caso $$F(T)\le 2y+1.$$ Con lo que, con un nuevo sacrificio, llegamos a $$Q_0\le Q_1:=\frac{2(y+1)}{(y+2)^2}(2y+1)^{1/2}.$$ Probar que \(Q_1<1\) es fácil ya que $$ (y+2)^2-2(y+1)\sqrt{2y+1}=2+(y+1-\sqrt{2y+1})^2>0.$$ De hecho podemos probar sin mucha dificultad que \(Q_1\le \frac13\sqrt{3+2\sqrt{3}}\).
En cada una de las etapas nuestra cantidad \(Q\) se ha transformado, hay una enorme distancia entre la versión original de Vladimir y la expresión de \(Q_1\). La simplificación de estas expresiones ha sido una medida de nuestro progreso.
Después de esta solución, fedja añade:
Lo que hice no va mas allá de las capacidades de la inteligencia artificial (fueron tan solo un conjunto aleatorio de sustituciones y manipulaciones simbólicas). Sin embargo, hasta que no vea una salida como esta permaneceré escéptico. No me inspira mucha confianza el hecho de que una de los órdenes más útiles en Mathematica para un amigo mío, que es un gran fan, resulta ser «Matar el kernel» .
El amigo al que se refiere fedja es Iosif Pinelis y cuando Mathematica entra en un bucle infinito, la única forma de pararlo es «Matar el Kernel».
También hay un intercambio de palabras con Vladimir, el proponente del problema, y Iosif Pinelis:
Iosif Pinelis: dudo que esta demostración esté dentro de las capacidades actuales de la IA.
fedja: Sí, tan solo aplicar manipulaciones simbólicas aleatorias y ver si la complejidad de la fórmula disminuye. Es como un juego de ajedrez con una función de evaluación simple, calculando solo dos pasos por delante antes de escoger.
Vladimir: Hablando honestamente, su demostración me resulta inusual. El uso de la convexidad es muy útil, pero la aparición de \(T\) y \(F(T)\) me resulta bastante impredecible.
fedja: Sí, la parte de la diferenciación no es obvia. El uso de \(T\) no es esencial, puedes mantener la \(t\). Solo hace las fórmulas más cortas. \(F(T)\) es natural: todo lo demás se expresa en términos de \(a\) e \(y\) y tienen tamaño razonable, mientras que esta parte contiene el parámetro \(T\) que puede ser muy grande.
Para saber más
La entrada en MathOverflow donde se inició la polémica es «On some inequality (upper bound) on a function of two variables» y es la que hemos detallado completamente. Posteriormente la polémica continúa con «Is this function concave?». En esta entrada, fedja explica uno de sus trucos preferidos a la hora de probar desigualdades. Pero la mejor entrada, donde explica sus métodos con detalle, es «Ordering preference for two zero mean Gaussian outcomes». Creo que el trabajo de fedja en estas entradas junto con el de Pólya sobre la solución de problemas son un buen principio para explicar a un ordenador qué sería un movimiento en este juego de probar desigualdades.
Los comentarios en todas las entradas anteriores son interesantes. En uno de ellos, Iosif Pinelis pregunta a fedja si cree que una IA puede dar una prueba de la desigualdad propuesta en «An inequality concerning Lagrange’s identity», a la que Iosif Pinelis ha dado una respuesta.
Sobre AlphaZero obtenemos información válida en el Blog de DeepMind sobre AlphaZero. Si queremos más información podemos leer el artículo en Nature explicando AlphaZero. Podemos encontrar información más técnica sobre el programa por ejemplo en Nickcheerla.github.io/deeplearningschool.
Posteriormente los creadores de AlphaZero han tomado como objetivo el juego StarCraft II, que tiene fama de ser de los más complicados que existen. Han tenido éxito en la tarea, tenemos información sobre este éxito en el blog de DeepMind. También podemos ver el Artículo en Nature sobre StarCraft. Pero creo que el objetivo de resolver problemas matemáticos se parece más al ajedrez y sus análogos que a estos juegos.
fedja es un conocido matemático, pero no ha querido desvelar su identidad en MathOverflow, así que mantendré esa voluntad. A propósito de su intervención en MathOverflow, dice:
Uno puede preguntarse si debería aprender a jugar tales juegos [demostrar desigualdades en MathOverflow] en el tiempo que uno puede dedicar a «investigación seria». No creo que haya nada suficientemente «serio» en esta vida que justifique el total abandono del placer de jugar, pero si alguien prefiere ser un «samurai matemático» tampoco veo problema con eso. Dejaré a otros juzgar cuánto (o si) soy capaz de la llamada «investigacion seria». Solo quiero decir que para mí las únicas dos distinciones tangibles entre diferentes problemas matemáticos son si puedo o no entender su enunciado y si puedo o no resolverlos y que empleo en la «investigación seria» aproximadamente las mismas técnicas, como el padre Brown de las novelas de Chesterton, que usaba exactamente los mismos métodos para cazar ladrones que para hablar con los ángeles. Simplemente no puedo explicarlos con ejemplos de ese nivel. Honestamente lo he intentado. El mensaje no se entendió. Veamos si al nivel de la aritmética elemental y desigualdades funcionales entre funciones explícitas lo consigo.
Finalmente quiero dejar aquí constancia del uso de una figura: «Chess is mental torture. – Garry Kasparov» by Francesca Cappa is licensed with CC BY 2.0. To view a copy of this license, visit https://creativecommons.org/licenses/by/2.0/
Dejar una contestacion