Descubrir algoritmos de multiplicación de matrices más rápidos con aprendizaje por refuerzo

Área de la Ciencia:

• Ciencias de la computación
• Inteligencia artificial
• Matemáticas computacionales

Sus antecedentes:

• La multiplicación matricial es un cálculo fundamental que afecta a diversos campos como las redes neuronales y la computación científica.
• Descubrir nuevos algoritmos para la multiplicación de matrices es un desafío debido al vasto espacio de búsqueda.
• Los algoritmos existentes, aunque eficientes, pueden no representar la solución óptima.

Objetivo del estudio:

• Desarrollar un enfoque impulsado por la IA para descubrir algoritmos de multiplicación de matrices eficientes y comprobadamente correctos.
• Explorar el potencial del aprendizaje por refuerzo profundo en la automatización del descubrimiento algorítmico.
• Para lograr avances en la complejidad de la multiplicación de matrices más allá de la intuición humana.

Principales métodos:

• Utilizó un agente de aprendizaje de refuerzo profundo, AlphaTensor, inspirado en AlphaZero.
• Entrenó a AlphaTensor para jugar un juego centrado en encontrar descomposiciones tensoriales dentro de un espacio de factores finito.
• Aplicó el agente para descubrir algoritmos para la multiplicación de matrices arbitraria y estructurada.

Principales resultados:

• AlphaTensor descubrió algoritmos que superan la complejidad del estado de la técnica para varias dimensiones de la matriz.
• Un nuevo algoritmo para matrices 4x4 en un campo finito mejora el método de Strassen de 50 años.
• Optimización demostrada para tiempos de ejecución de hardware específicos y multiplicación de matrices estructuradas.

Conclusiones:

• El aprendizaje de refuerzo profundo, ejemplificado por AlphaTensor, puede acelerar el descubrimiento algorítmico.
• El enfoque ofrece un camino para superar los algoritmos diseñados por humanos para tareas computacionales fundamentales.
• AlphaTensor proporciona un marco flexible para optimizar algoritmos basados en diferentes criterios, incluida la complejidad computacional y la eficiencia práctica.