AlphaTensor encuentra nuevas formas de reducir el coste de la multiplicación de matrices

Ulmo

Primero de todo, decir que con los matemáticos que tenemos por el foro, vergüenza me daría que un biólogo tenga que abrir estos temas. Pero entremos en materia.

Parece ser que poniendo a jugar a AlphaTensor con el cálculo de multiplicaciones matriciales ha conseguido descubrir nuevos atajos que nos permitirían hallar la matriz resultante reduciendo el número de operaciones necesarios para llegar a dicho resultado.

La cuestión es que la solución no parece ser universal, sino que encuentra un sistema para cada uno de los tamaños de matrices y dependiendo del tipo de multiplicación el margen de mejora varía:

Left: column (n, m, p) refers to the problem of multiplying n × m with m × p matrices. The complexity is measured by the number of scalar multiplications (or equivalently, the number of terms in the decomposition of the tensor). ‘Best rank known’ refers to the best known upper bound on the tensor rank (before this paper), whereas ‘AlphaTensor rank’ reports the rank upper bounds obtained with our method, in modular arithmetic (ℤ2) and standard arithmetic. In all cases, AlphaTensor discovers algorithms that match or improve over known state of the art (improvements are shown in red). See Extended Data Figs. 1 and 2 for examples of algorithms found with AlphaTensor. Right: results (for arithmetic in ℝ) of applying AlphaTensor-discovered algorithms on larger tensors. Each red dot represents a tensor size, with a subset of them labelled. See Extended Data Table 1 for the results in table form. State-of-the-art results are obtained from the list in ref.

La multiplicación de matrices es uno de los cálculos fundamentales en infinidad de procesos actuales, desde las propias físicas de objetos en animación hasta los propios sistemas de inteligencia artificial que basan su entrenamiento en propagar la información a base de realizar este tipo de multiplicaciones.

a,b, Speed-ups (%) of the AlphaTensor-discovered algorithms tailored for a GPU (a) and a TPU (b), optimized for a matrix multiplication of size 8,192 × 8,192. Speed-ups are measured relative to standard (for example, cuBLAS for the GPU) matrix multiplication on the same hardware. Speed-ups are reported for various matrix sizes (despite optimizing the algorithm only on one matrix size). We also report the speed-up of the Strassen-square algorithm. The median speed-up is reported over 200 runs. The standard deviation over runs is <0.4 percentage points (see Supplementary Information for more details). c, Speed-up of both algorithms (tailored to a GPU and a TPU) benchmarked on both devices.

Si fuera matemático supongo que podría daros más detalles, para los novatillos tenemos artículo en la vanguardia:
https://www.lavanguardia.com/vida/20221007/8557564/ia-deepmind-halla-nueva-forma-multiplicar-matrices-acelerar-calculos.html

Y para los más expertos, el paper original que acaba de publicarse este mismo mes:
https://www.nature.com/articles/s41586-022-05172-4

28
B

Mucha historia... pero le pido que me haga "1 / 0" y seguro que casca...

En serio, muy interesante! las I.A. (dentro de sus posibilidades) van a ser una herramienta tan necesaria como una hoja de excel... en muchas profesiones.

4 1 respuesta
hda

:O

1
Kike_Knoxvil

#2 No debe de quedar mucho para que Excel posea una IA incorporada

Yuke

Mira macho, me siento tontísimo porque si quieres me hago un hit no run en dark souls pero de esto no entiendo ni un 1%.

15 2 respuestas
Ulmo

#5 ¿Pero no entiendes la noticia o no entiendes el estudio? La noticia yo creo que es "sencilla" de entender, lo que ya no lo es tanto (y yo tampoco lo entiendo mucho) es el estudio detallado en sí y cuánto de clickbait hay en él.

Pero el concepto que para multiplicar 2 matrices NxM * MxL se necesitan realizar varias multiplicaciones de números (aquello que nos enseñaron de filas multiplicadas por columnas) yo creo que es bastante intuitivo. Y el hecho de que se pueda obtener el mismo resultado ahorrándote algunas multiplicaciones pues tiene su interés.

Luego está el si se sabe o no para que se usa la multiplicación matricial, que actualmente se usa para prácticamente todo en informática, mucho más con el auge del machine learning e inteligencia artificial que están usando este tipo de cálculo de forma muy intensa.

¿Implicaciones? Hombre, aquí ya podríamos divagar hasta el infinito, incluyendo incluso el impacto medioambiental de ahorrar miles y miles de horas de computación.

2 2 respuestas
Yuke

#6 no entiendo literalmente nada, ya me pasó en su día en bachillerato con las fórmulas.

1 respuesta
wdaoajw

Hay mucha gente que no ha visto una matriz en su vida hulio

1 1 respuesta
Kike_Knoxvil

#7 Quédate con la idea que es almacenar los datos todos juntos de forma ordenada e ir iterando operaciones hasta obtener el resultado. Lo que ha conseguido esta IA es que se requieran menos pasos para llegar a la solución final, lo cual implica menos tiempo de computación (y las impicaciones de esto son infinitas)

1
Danitori

#8 Mis colegas programadores se rien de mi cuando les digo que he hecho una macro en para el wow. ''el dia que toques una matriz vas a flipar''

B

50
Hipnos

Es interesante porque la multiplicación de matrices genéricas es un campo bastante muerto. Por eso actualmente se estudian casos para matrices concretas (matrices dispersas, etc.). No hay mucha mejora respecto a lo actual pero es muy interesante porque indica que podemos usar IAs para eficientar problemas usando este tipo de "gamificación".

Alphazero se volvió buena jugando contra sí misma en un entorno simulado de décadas de partidas. El único problema que queda es simplificar un problema físico o matemático en términos de un juego con "partidas cortas" del cual la IA pueda aprender.

1 respuesta
allmy

La IA ha descubierto algoritmos nuevos. Esto es muy gordo porque ni si quiera hace falta IA para aplicar esos nuevos algoritmos, entiendo. Por lo que entiendo que el siguiente paso será coger esos algoritmos, y aplicarlos en las librerías de cálculo que más se usan y booom! de la noche q la mañana has optimizado un buen trozo de toda la computación a nivel mundial (con su consumo energético, sus ahorros de tiempo, sus ahorros en dinero, etc.)

La duda que tengo es, la optimización no es universal (para cualquier matriz), por lo que ¿Es posible que el ahorro que produzca se lo coma el tener que elegir algoritmo dependiendo del tamaño de la matriz?

3 respuestas
CaNaRy_r00lz

#13 Pero yo entiendo que los algoritmos no son generales, sino especificos a cada matriz, si fueran genericos entonces si seria la leche, pero siendo espeficos no se cuan bueno es, no trabajo con matrices asi que me queda la duda.

2 respuestas
Kike_Knoxvil

#13 No creo que sea tan tan sencillo de aplicar, más aún dentro de programas cerrados como Matlab o cosillas así, me imagino que primero tendrán que hacer un análisis de los casos aplicables, introducirlo a la librería y luego realizar optimizaciones y depuraciones para que los programas no se vuelvan locos. Más bien parece aplicable en un cambio de versión de los programas

De todas maneras no parece que vaya a consumir nada, simplemente tendrá esa opción extra que la elegirá en función de unos valores dados por los programadores, por lo que no debería añadir tiempo extra en la selección. Y aunque lo añadiese, en procesos iterativos largos (que es donde esta optimización va a brillar) se compensaría ya que la elección es una vez (unos nanosegundos) pero la aplicación puede bajar horas de simulaciones

Pero vamos, que lo mio son hacer simulaciones, no soy matemático como para entrar a detalle de que tan bien viene esta optimización

1
Cl0ud7

#14 Segun ha puesto #1 lo que encuentra es un algoritmo para cada tamaño de matriz, entonces si se podria usar entiendo.

Ulmo
#12Hipnos:

Es interesante porque la multiplicación de matrices genéricas es un campo bastante muerto.

¿De donde sacas eso? La programación con redes neuronales es básicamente una matriz que se va multiplicando por varios vectores ya sea para propagar la señal o para hacer el backtracking. Vamos, es que es prácticamente lo único que hacen las redes neuronales que tanto se usan ahora. Todo lo que se renderizado de imágenes, videojuegos, películas etc, más de lo mismo.

Es posiblemente el tipo de cálculo más habitual hoy en día.

#13 #14 Según entiendo ese es el problema, que parece ser que encuentra soluciones diferentes en función al número de filas y columnas que tengan las matrices a multiplicar. De hecho es la primera imagen que he puesto, la primera columna de 3 números : n,m,p es exactamente el tamaño de filas y columnas de las matrices NxM * MxP

Entiendo que desde el punto de vista matemático es interesante porque quiere decir que existe una lógica oculta tras el cálculo que todavía no comprendemos y por eso la IA es capaz de simplificar cálculos que nosotros no.

Para el campo aplicado, bueno, supongo que depende. En programación con redes neuronales al final tú eliges el diseño de tu modelo, si el ahorro de tiempo es notable, podrías forzarlo para ajustarte a matrices de datos más eficientes.

Para resolver los problemas de matemáticas del instituto es evidente que esto no sirve para nada.

¿No hay ningún matemático que nos ilustre?

3 2 respuestas
Rivendel

para algoritmos de calculo de estructuras puede mejorar el rendimiento bastante

1 1 respuesta
Nirfel

Muy interesante, dado que en mi campo estos cálculos son lo básico (Física teórica de la materia condensada).

Luego le hecho un vistazo, pero dudo que sea tan sencillo como sustituir las librerías existentes (BLAS, LAPACK, etc.) Por la que se genere con la IA esta

Taiden

#18 el problema está en lo que dice #17. Cómo las matrices depende del número de elementos esto podría no ser aplicable a menos que puedas lanzar el estudio de esas matrices en particular.

Pero vamos, si tarde o temprano se deriva una expresión general va a aumentar la eficiencia de todos los códigos.

ZurdoK
#5Yuke:

hit no run

Hazlo, no hay cojones

Kaos

Vaya biologo sexy

Hipnos

#17 Pues que no existe ningún avance en ese campo desde hace al menos 50 años. Por eso es un campo muerto.

Otra cosa es que se aplique como todo. Como las sumas. ¿Vas a inventar una suma nueva? No, por eso es un campo muerto.

1 respuesta
Ulmo

#23 A ver, por favor, es un campo que no deja de usarse y estudiarse porque con el boom de las redes neuronales todo se centra en optimizar cálculos vectoriales. Es más, la revolución y arquitectura de las GPUs está hecha expresamente para satisfacer esa gran demanda de calculo vectorial. Que a nivel teórico no hayan habido grandes avances no quita que a nivel práctico hayan habido enormes avances en lo que a calculo matricial se refiere, empezando por las arquitecturas de los computadores.

Pero es que además, ni tan si quiera en lo teórico es un campo muerto, en la propia imagen que pongo primera puedes ver en qué años se lograron versiones más eficientes de cálculos matriciales, y tienes avances en 2013 y 2021.

6
quetzalcube

Gracias por el artículo y la reseña @Ulmo

En cuanto al comentario sobre los matemáticos, ¿qué te hace pensar que este artículo es de matemáticas? Es un artículo sobre algoritmos de computación de matrices, encontrados con un programa. No hay demostraciones, ni nada que explique la razón por la que, en ciertos casos, pueden optimizarse ciertos algoritmos. Supongo que a la gente de cálculo numérico los nuevos algoritmos encontrados les parecerán ejemplos notables a estudiar. Pero vamos, el cálculo numérico está en el borde de lo que uno puede o no llamar matemáticas, y no esta claro de qué lado del borde está! :stuck_out_tongue_winking_eye:

1 2 respuestas
Ulmo

#25 Naaaa, era por meter baza lo de decir matemáticas. De todas formas, no hablamos de una aproximación, hablamos de una formulación que funciona y arroja el resultado correcto, ergo debe haber alguna demostración que se les está escapando a los matemáticos y que debería permitir llegar al resultado simplificado.

¿O crees que pueden haber 2 formulaciones independientes sin ningún nexo de unión que logren satisfacer la misma función? No se, el sentido común me dice que no, pero ni zorra soy biólogo Hulio.

4 respuestas
allmy

#25 #26 una pregunta para los entendidos o más o menos entendidos ¿Cómo puede ser que exista un método diferente que sea válido para un tamaño de matriz pero no para otro? Es decir, ¿Puede haber algo en el tamaño de una matriz que la diferencie fundamentalmente de otra matriz, haciendo que un método valga para una pero no para otra? Esto me parece contra intuitivo. Es como dsi dijéramos que una molécula de agua tiene diferente masa si está rodeada de más moléculas.

1 respuesta
Nirfel

#26 No realmente. Muchas aplicaciones de ML se considera un "black box" porque, aunque puedas mirar paso por paso el que hace el programa, el como funciona no es interpretable.

Por ejemplo, de una charla que dio IBM en mi anterior uni, tienen un grupo trabajando en predicción de reacciones químicas.

Tras entrenar su IA con enormes bases de datos de reacciones químicas, puedes ahora darle un producto final que quieres y un producto de partida y es capaz de decirte todos los reactivos y condiciones que necesitas.

Les pregunté si se es posible estudiar los mecanismos de reacción intermedios y la respuesta fue un rotundo no.

Si intentas interpretar lo que la IA hace, lo único que encuentras son cosas sin sentido.

No sé cómo funcionará en este caso, pero si es parecido a como funciona ML en química, me da a mi que te tienes que conformar con que funciona.

2 1 respuesta
quetzalcube

#26 #27

Yo no soy entendido de este tema, aquí estoy como vosotros: "out of my depth". Como os digo, esto tiene poca relación con las matemáticas o con los temas  habituales que interesan a un matemático.

Si yo he entendido bien el abstract, el programa ha encontrado unos algoritmos para ciertos tipos de matrices. Esos algoritmos son ciertos. Podemos decir que están "demostrados de forma tonta o fea". Quiero decir: sí, están "demostrados" en el sentido de que sabemos con certeza que esos algoritmos son correctos, pero "de forma tonta o fea" porque no tenemos ni idea de por qué esas matrices son especiales o de si hay algoritmos análogos en otros tipos de matrices. En general, una demostración en matemáticas no solo busca "probar" que un resultado es cierto, sino desentrañar por qué es cierto en el sentido de ¿hay otros lugares que puedan tener pruebas similares? ¿cuáles son las condiciones básicas para tener este resultado? ¿hay hipótesis innecesarias? etc... En el caso actual, no tenemos ni idea porque se ha hecho por ordenador.

En cuanto a la pregunta de qué tienen esas matrices que las hacen especiales al resto, eso me recuerda a un fenómeno que, aunque poco frecuente, no es desconocido en matemáticas y siempre es sorprendente. Hay fórmulas, propiedades y teoremas que son específicos de una dimensión y no de otra. Es fácil e intuitivo ver que las "dimensiones pequeñas" (1, 2, 3...) son especiales. Por ejemplo, si quitas un punto a una recta, te quedan dos semirrectas "desconectadas "(no hay ningún camino que vaya de una semirrecta a la otra). Si quitas un punto a un plano no, el complementario está "conectado" porque siempre hay un camino que una cualesquiera dos puntos. Lo mismo ocurre con el espacio. En general, es normal que algo sea cierto "desde 0 hasta cierta dimensión" o "a partir de dimensión n".

Sin embargo también hay cosas que solo son válidas en "ciertas dimensiones" . Por ejemplo, el tensor de Einstein se anula en variedades de dimensión 2. Es decir, para el que sepa, la ecuación

Ricc- rg/2=0

donde Ricc es el tensor de Ricci, r es la curvatura escalar, y g es una métrica solo es cierta en dimensión 2, en general no es cierta. Y así, más en general, hay fórmulas asociadas a una métrica que solo son válidas en ciertas dimensiones. El ejemplo reciente más famoso de un fenómeno así es el del teorema del empaquetamiento por esferas: por alguna razón la dimensiones 8 y 24 son especiales (pinchad ). Uno podría preguntarse si lo que ha encontrado el programita este son ejemplos de fenómenos de este tipo.

1 1 respuesta
Ulmo

#28 Pero esto es diferente, el algoritmo no ha encontrado una "predicción" que es para lo que habitualmente se utiliza el machine learning, ha encontrado un algoritmo que funciona.

No es lo mismo que la máquina sea capaz de hacer predicciones muy precisas y que nosotros no entendamos como lo hace, a que encuentre una fórmula más eficiente que funciona. No necesitamos entender cómo la ha encontrado, porque generalmente lo hace por fuerza bruta, solo el hecho de que la fórmula existe y funciona.

Lo que debemos entender es la fórmula en sí misma y por qué esta funciona, algo que es independiente a cualquier IA.

A mi esto es lo que más me descuadre, que yo desde el campo de la biología computacional (mi especialización) siempre había usado ML para lo que tú dices: predicciones. Y para predecir suelen funcionar bastante bien en campos como la biología donde tienes muchos descriptores como entrada, pero aquí hablamos que no predice nada, encuentra una fórmula como resultado.

Es que no entiendo ni como demonios se programa eso :joy:

Usuarios habituales

  • Nirfel
  • Glumyglu
  • Kike_Knoxvil
  • Ulmo
  • quetzalcube
  • Hipnos
  • Yuke