Introducción
Los matemáticos aman un buen rompecabezas. Incluso algo tan abstracto como multiplicar matrices (tablas numéricas bidimensionales) puede sentirse como un juego cuando tratas de encontrar la forma más eficiente de hacerlo. Es un poco como tratar de resolver un Cubo de Rubik en la menor cantidad de movimientos posible: desafiante, pero atractivo. Excepto que para un Cubo de Rubik, el número de movimientos posibles en cada paso es 18; para la multiplicación de matrices, incluso en casos relativamente simples, cada paso puede presentar más de 1012 .
Durante los últimos 50 años, los investigadores han abordado este problema de muchas maneras, todas basadas en búsquedas informáticas con la ayuda de la intuición humana. El mes pasado, un equipo de la empresa de inteligencia artificial DeepMind mostró cómo abordar el problema desde una nueva dirección, informando en un in Naturaleza que habían entrenado con éxito una red neuronal para descubrir nuevos algoritmos rápidos para la multiplicación de matrices. Era como si la IA hubiera encontrado una estrategia desconocida para resolver un Cubo de Rubik monstruosamente complejo.
“Es un resultado muy bueno”, dijo jose alman, científico informático de la Universidad de Columbia. Pero él y otros especialistas en multiplicación de matrices también enfatizaron que dicha asistencia de IA complementará en lugar de reemplazar los métodos existentes, al menos en el corto plazo. “Es como una prueba de concepto de algo que podría convertirse en un gran avance”, dijo Alman. El resultado simplemente ayudará a los investigadores en su búsqueda.
Como para probar el punto, tres días después de la Naturaleza Cuando salió el artículo, un par de investigadores austriacos ilustraron cómo los métodos nuevos y antiguos podrían complementarse entre sí. Utilizaron una búsqueda convencional asistida por computadora para mejorar aún más uno de los algoritmos que la red neuronal había descubierto.
Los resultados sugieren que, al igual que el proceso de resolver un Cubo de Rubik, el camino hacia mejores algoritmos estará lleno de giros y vueltas.
multiplicando matrices
La multiplicación de matrices es una de las operaciones más fundamentales y omnipresentes en todas las matemáticas. Para multiplicar un par de n-Por-n matrices, cada una con n2 elementos, se multiplican y se suman estos elementos en combinaciones particulares para generar el producto, un tercero n-Por-n matriz. La receta estándar para multiplicar dos n-Por-n matrices requiere n3 operaciones de multiplicación, por lo que una matriz de 2 por 2, por ejemplo, requiere ocho multiplicaciones.
Para matrices más grandes, con miles de filas y columnas, este proceso se vuelve engorroso rápidamente. Pero en 1969, el matemático Volker Strassen descubrió un procedimiento para multiplicar un par de matrices de 2 por 2 usando siete en lugar de ocho pasos de multiplicación, a costa de introducir más pasos de suma.
El algoritmo de Strassen es innecesariamente complicado si solo desea multiplicar un par de matrices de 2 por 2. Pero se dio cuenta de que también funcionaría para matrices más grandes. Eso es porque los elementos de una matriz pueden ser ellos mismos matrices. Por ejemplo, una matriz con 20,000 20,000 filas y 2 2 columnas se puede volver a imaginar como una matriz de 10,000 por 10,000 cuyos cuatro elementos son matrices de 5,000 5,000 por 2 2 cada uno. Cada una de estas matrices se puede subdividir en cuatro bloques de XNUMX por XNUMX, y así sucesivamente. Strassen podría aplicar su método para multiplicar matrices de XNUMX por XNUMX en cada nivel de esta jerarquía anidada. A medida que aumenta el tamaño de la matriz, crece el ahorro de menos multiplicaciones.
El descubrimiento de Strassen condujo a la búsqueda de algoritmos eficientes para la multiplicación de matrices, que desde entonces ha inspirado dos subcampos distintos. Uno se enfoca en una cuestión de principio: si imaginas multiplicar dos n-Por-n matrices y dejar n correr hacia el infinito, ¿cómo se escala el número de pasos de multiplicación en el algoritmo más rápido posible con n? los registro actual para la mejor escala, n2.3728596, pertenece a Alman y Virginia Vassilevska Williams, científico informático del Instituto Tecnológico de Massachusetts. (Un reciente inédito preprint informó una pequeña mejora usando una nueva técnica.) Pero estos algoritmos son de interés puramente teórico, superando métodos como el de Strassen solo para matrices absurdamente grandes.
El segundo subcampo piensa en una escala menor. Poco después del trabajo de Strassen, el informático estadounidense israelí Shmuel Winograd mostró que Strassen había llegado a un límite teórico: no es posible multiplicar matrices de 2 por 2 con menos de siete pasos de multiplicación. Pero para todos los demás tamaños de matriz, el número mínimo de multiplicaciones requeridas sigue siendo una pregunta abierta. Y los algoritmos rápidos para matrices pequeñas podrían tener un impacto enorme, ya que las iteraciones repetidas de dicho algoritmo podrían vencer al algoritmo de Strassen cuando se multiplican matrices de tamaño razonable.
Desafortunadamente, la gran cantidad de posibilidades es enorme. Incluso para matrices de 3 por 3, "la cantidad de algoritmos posibles excede la cantidad de átomos en el universo", dijo Alhussein Fawzi, un investigador de DeepMind y uno de los líderes del nuevo trabajo.
Enfrentados a este vertiginoso menú de opciones, los investigadores han progresado al transformar la multiplicación de matrices en lo que parece ser un problema matemático totalmente diferente, uno que es más fácil de manejar para las computadoras. Es posible representar la tarea abstracta de multiplicar dos matrices como un tipo específico de objeto matemático: una matriz tridimensional de números llamada tensor. Luego, los investigadores pueden dividir este tensor en una suma de componentes elementales, llamados tensores de "rango 1"; cada uno de estos representará un paso diferente en el correspondiente algoritmo de multiplicación de matrices. Eso significa que encontrar un algoritmo de multiplicación eficiente equivale a minimizar la cantidad de términos en una descomposición de tensor: cuantos menos términos, menos pasos involucrados.
De esta manera, los investigadores han descubierto nuevos algoritmos que se multiplican n-Por-n matrices usando menos que el estándar n3 pasos de multiplicación para muchos tamaños de matriz pequeños. Pero los algoritmos que superan no solo el estándar, sino también el algoritmo de Strassen para matrices pequeñas han permanecido fuera del alcance, hasta ahora.
Game On
El equipo de DeepMind abordó el problema convirtiendo la descomposición de tensores en un juego para un solo jugador. Comenzaron con un algoritmo de aprendizaje profundo descendiente de AlphaGo, otra IA de DeepMind que en 2016 aprendió a jugar el juego de mesa Go lo suficientemente bien como para vencer a los mejores jugadores humanos.
Todos los algoritmos de aprendizaje profundo se construyen alrededor de redes neuronales: redes de neuronas artificiales ordenadas en capas, con conexiones que pueden variar en fuerza que representan cuánto influye cada neurona en las de la siguiente capa. La fuerza de estas conexiones se modifica en muchas iteraciones de un procedimiento de entrenamiento, durante el cual la red neuronal aprende a transformar cada entrada que recibe en una salida que ayuda al algoritmo a lograr su objetivo general.
En el nuevo algoritmo de DeepMind, denominado AlphaTensor, las entradas representan pasos en el camino hacia un esquema válido de multiplicación de matrices. La primera entrada a la red neuronal es el tensor de multiplicación de matriz original, y su salida es el tensor de rango 1 que AlphaTensor ha elegido para su primer movimiento. El algoritmo resta este tensor de rango 1 de la entrada inicial, lo que genera un tensor actualizado que se retroalimenta a la red como una nueva entrada. El proceso se repite hasta que finalmente todos los elementos del tensor inicial se han reducido a cero, lo que significa que no hay más tensores de rango 1 para eliminar.
En ese momento, la red neuronal ha descubierto una descomposición de tensores válida, ya que se garantiza matemáticamente que la suma de todos los tensores de rango 1 es exactamente igual al tensor inicial. Y los pasos que tomó para llegar allí se pueden traducir de nuevo en pasos del algoritmo de multiplicación de matrices correspondiente.
Aquí está el juego: AlphaTensor descompone repetidamente un tensor en un conjunto de componentes de rango 1. Cada vez, AlphaTensor recibe una recompensa si encuentra una forma de reducir el número de pasos. Pero los atajos a la victoria no son para nada intuitivos, al igual que a veces debes codificar una cara perfectamente ordenada en un cubo de Rubik antes de poder resolverlo todo.
El equipo ahora tenía un algoritmo que, en teoría, podría resolver su problema. Solo tenían que entrenarlo primero.
Nuevos Caminos
Como todas las redes neuronales, AlphaTensor necesita una gran cantidad de datos para entrenar, pero la descomposición de tensores es un problema notoriamente difícil. Hubo pocos ejemplos de descomposiciones eficientes que los investigadores pudieran alimentar a la red. En cambio, ayudaron a que el algoritmo comenzara a entrenarlo en el problema inverso mucho más fácil: sumar un montón de tensores de rango 1 generados aleatoriamente.
“Están usando el problema fácil para producir más datos para el problema difícil”, dijo Michael littman, científico informático de la Universidad de Brown. La combinación de este procedimiento de entrenamiento hacia atrás con el aprendizaje por refuerzo, en el que AlphaTensor generó sus propios datos de entrenamiento mientras buscaba descomposiciones eficientes, funcionó mucho mejor que cualquier método de entrenamiento por sí solo.
El equipo de DeepMind entrenó a AlphaTensor para descomponer tensores que representan la multiplicación de matrices hasta 12 por 12. Buscó algoritmos rápidos para multiplicar matrices de números reales ordinarios y también algoritmos específicos para una configuración más restringida conocida como aritmética de módulo 2. (Esto es matemática basada en solo dos números, por lo que los elementos de la matriz solo pueden ser 0 o 1, y 1 + 1 = 0). trabajar con matrices de números reales.
Después del entrenamiento, AlphaTensor redescubrió el algoritmo de Strassen en cuestión de minutos. Luego descubrió hasta miles de nuevos algoritmos rápidos para cada tamaño de matriz. Estos eran diferentes de los algoritmos más conocidos pero tenían el mismo número de pasos de multiplicación.
En algunos casos, AlphaTensor incluso batió récords existentes. Sus descubrimientos más sorprendentes ocurrieron en la aritmética del módulo 2, donde encontró un nuevo algoritmo para multiplicar matrices de 4 por 4 en 47 pasos de multiplicación, una mejora sobre los 49 pasos requeridos para dos iteraciones del algoritmo de Strassen. También superó el algoritmo más conocido para matrices de módulo 5 de 5 por 2, reduciendo el número de multiplicaciones requeridas del récord anterior de 98 a 96. (Pero este nuevo récord aún está por detrás de los 91 pasos que se requerirían para algoritmo de Strassen usando matrices de 5 por 5).
El nuevo resultado de alto perfil creó mucha emoción, con algunos investigadores colmando de elogios a la mejora basada en la IA en el status quo. Pero no todos en la comunidad de multiplicación de matrices quedaron tan impresionados. “Sentí que estaba un poco exagerado”, dijo Vassilevska Williams. “Es otra herramienta. No es como, 'Oh, las computadoras vencen a los humanos', ¿sabes?
Los investigadores también enfatizaron que las aplicaciones inmediatas del algoritmo récord 4 por 4 serían limitadas: no solo es válido solo en aritmética de módulo 2, sino que en la vida real hay consideraciones importantes además de la velocidad.
Fawzi estuvo de acuerdo en que, en realidad, esto es solo el comienzo. “Hay mucho espacio para la mejora y la investigación, y eso es algo bueno”, dijo.
Un giro final
La mayor fortaleza de AlphaTensor en relación con los métodos de búsqueda por computadora bien establecidos es también su mayor debilidad: no está limitado por la intuición humana sobre cómo se ven los buenos algoritmos, por lo que no puede explicar sus opciones. Eso dificulta que los investigadores aprendan de sus logros.
Pero esto puede no ser un inconveniente tan grande como parece. Unos días después del resultado de AlphaTensor, el matemático manuel kauers y su estudiante de posgrado jakob moosbauer, ambos de la Universidad Johannes Kepler de Linz en Austria, informaron otro paso adelante.
Introducción
Cuando salió el artículo de DeepMind, Kauers y Moosbauer estaban en el proceso de buscar nuevos algoritmos de multiplicación utilizando una búsqueda convencional asistida por computadora. Pero a diferencia de la mayoría de estas búsquedas, que comienzan de nuevo con un nuevo principio rector, su método funciona modificando repetidamente un algoritmo existente con la esperanza de obtener más ahorros de multiplicación. Tomando el algoritmo de AlphaTensor para matrices módulo 5 de 5 por 2 como punto de partida, se sorprendieron al descubrir que su método redujo el número de pasos de multiplicación de 96 a 95 después de solo unos segundos de cálculo.
AlphaTensor también les ayudó a hacer otra mejora indirectamente. Anteriormente, Kauers y Moosbauer no se habían molestado en explorar el espacio de las matrices de 4 por 4, creyendo que no sería posible superar dos iteraciones del algoritmo de Strassen. El resultado de AlphaTensor los llevó a reconsiderarlo, y después de una semana de tiempo de cálculo comenzando desde cero, su método arrojó otro algoritmo de 47 pasos no relacionado con el que AlphaTensor había descubierto. “Si alguien nos hubiera dicho que hay algo que descubrir para 4 por 4, podríamos haberlo hecho antes”, dijo Kauers. “Pero está bien, bueno, así es como funciona”.
Littman espera más sorpresas de este tipo, comparando la situación con la primera vez que un corredor termina una milla en menos de cuatro minutos, una hazaña que en general se consideraba imposible. “La gente decía, 'Oh, espera, podemos hacer esto', y ahora mucha gente puede hacerlo”, dijo.
De cara al futuro, Fawzi espera generalizar AlphaTensor para abordar una gama más amplia de tareas matemáticas y computacionales, al igual que su antepasado AlphaGo finalmente se expandió a otros juegos.
Kauers ve esto como la verdadera prueba de fuego para la aplicación del aprendizaje automático para descubrir nuevos algoritmos. Señala que la búsqueda de algoritmos rápidos de multiplicación de matrices es un problema combinatorio para el cual las búsquedas por computadora, con o sin asistencia humana, son muy adecuadas. Pero no todos los problemas matemáticos son tan fáciles de precisar. Si el aprendizaje automático puede descubrir una idea algorítmica cualitativamente nueva, dijo, "esto sería un cambio de juego".
