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

c0b4c #31 Oct '22

#29quetzalcube:

Podemos decir que están "demostrados de forma tonta o fea".

Creo intuir que no es el caso. Simplemente han encontrado algoritmos que son más eficientes que los conocidos para determinados tipos de matrices, pero no han demostrado que esos algoritmos sean los óptimos. Y el motivo es que para encontrar dichos algoritmos tienen que discretizar el conjunto de coeficientes (creo que es algo así como el espacio de optimización). Y, tampoco han demostrado que los algoritmos encontrados sean los óptimos para cada conjunto. Es posible que la optimización estuvise cayendo en un mínimo local, por ejemplo. Pero me temo que de momento no hay forma de comprobarlo, porque la demostración de estas cosas se hace de forma analítica, o con derivadas.

RPV: Han encontrado algoritmos que son más eficientes que los conocidos, pero no han demostrado que estos sean los óptimos (i.e., es posible que existan algoritmos más eficientes incluso).

2 1 respuesta

DelToro #32 Oct '22

Entonces la policia sabia que los de asuntos internos les habian tendido una trampa?

2

quetzalcube #33 Oct '22 Papa Frank TrumpChomsky

#31 gracias pero… yo no he dicho que hayan probado que fuesen óptimos sólo que han probado que son algoritmos que, efectivamente, son válidos para esas matrices y más eficientes que los conocidos. No he dicho que fuesen óptimos

pardier #34 Oct '22

necesitas una calculadora cientifica

Glumyglu #35 Oct '22

#26Ulmo:
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.

La demostración es que arroja el resultado correcto (teóricamente). De este tema no sé mucho, pero leyendo el paper original en el que se describe el algoritmo de Strassen, el anterior algoritmo más rápido para multiplicar matrices, básicamente exponen el algoritmo, prueban que da el resultado correcto y que "reduce" el número de operaciones.

En el paper de AlphaTensor formulan la multiplicación de matrices como un tensor, ¿puede que haya una relación más profunda y que estas mejoras de los algoritmos se deduzcan de propidades de los tensores? Poder puede ser, supongo, pero parece que no se han puesto con ello. Yo como ni siquiera sé lo que es un tensor (xd) poco más puedo decir.

Esto ya no va dirigido a ti sino al hilo en general. Sobre las implementaciones, tiene sus problemas. Por lo que he leído todo algoritmo que mejore la complejidad del estándar va a tener como consecuencia una pérdida de la estabilidad numérica. Es decir, que arroje el resultado correcto solo ocurre en la teoría cuando se trabaja con aritmética exacta, pero en la vida real eso no ocurre. De hecho, excepto el de Strassen, no se suelen implementar los otros algoritmos, e incluso el de Strassen no se encuentra en algunas de las librerías más famosas de álgebra lineal (BLAS). Para situaciones donde no tienes este problema (cuerpos finitos, que creo que es precisamente el caso que se asume en el paper dde AlphaTensor) es una ventaja, para implementaciones reales esta pérdida de estabilidad es más dramática... No sé hasta qué punto el algoritmo nuevo se comportará respecto a este tema porque leyendo el paper por encima no parecen considerarlo, pero sin un estudio de ello nadie lo va a implementar.

2 respuestas

Kike_Knoxvil #36 Oct '22

#35 No estoy 100% seguro pero un tensor es una ordenación de un espacio: un vector por ejemplo. En mi caso he tenido que trabajar hasta la saciedad con el tensor de tensiones para la resistencia de materiales pero nunca nos han entrado a explicar que cojones es de forma exacta y matemática.

En cuanto a lo de la implementación, precisamente es útil para trabajar con elementos finitos que es la base de las simulaciones: discretizar el problema, resolver cada "cachito" y calcular el siguiente en función a este y repetir cálculos hasta llegar a una aproximación aceptable de la solución. Como dije en otro comentario, reducir el número de pasos para calcular una solución en un proceso iterativo largo puede significar una reducción considerable del tiempo de computación; y sinceramente a mi me parece que las simulaciones son una implementación bastante real donde pueden despuntar.

Al menos en mi opinión, claro

1 respuesta

Glumyglu #37 Oct '22

#36 El problema es que sigues trabajando con floating-point numbers y, por lo poco que he estado leyendo sobre el tema, estos algoritmos para multiplicar de forma rápida son más susceptibles a las pérdidas de precisión ocasionadas por esto. Que un algoritmo requiera un menor número de operaciones no significa, a priori, que vaya a ser mejor.

1 respuesta

Kike_Knoxvil #38 Oct '22

#37 En realidad sí, precisamente porque al no ser preciso lo que se hace es acotar un error en el proceso iterativo: si la diferencia entre el resultado y la semilla inicial es inferior a X, se considera correcto; por tanto dar menos pasos quiere decir que se llega antes a ese valor inferior entre semilla y resultado final

1 respuesta

R

Rinkes #39 Oct '22

Seguid así... con cosas de estas la red igual vuelve a valer de algo.

Vi0LaToR #40 Oct '22

Os acordáis?

B

[Borrado] #41 Oct '22

Osea que si ha reducido el número de cálculos necesarios para multiplicar matrices quiere decir que la IA ha desarrollado/descubierto un método nuevo para multiplicar matrices ¿no?

1 respuesta

ReEpER #42 Oct '22 Gafe

#6 weno weno, tampoco se hancian filasxcolumanas solo en multipicacion de matrices eh xD no vayamos ahora a simplificar.

1 respuesta

Ulmo #43 Oct '22 Moderador

#42ReEpER:
weno weno, tampoco se hancian filasxcolumanas solo en multipicacion de matrices eh xD no vayamos ahora a simplificar.

La verdad es que desconocía los otros algoritmos, pero ya puse una imagen en #1 donde se ven alternativas más eficientes, lo de filas x columnas era solo a modo de ejemplo.

EnderFX #44 Oct '22

#41 Un nuevo método para multiplicar matrices de determinadas dimensiones.

Para mí la importancia de esto puede venir más en la dirección de lo que dice #35. Si somos capaces de conocer el algoritmo utilizado para esos tamaños, obviamente se pueden introducir en librerías de cálculo y para esos casos aumentar un poco el rendimiento.

Sin embargo, lo que me gustaría saber, y parece, es que estos algoritmos más eficientes pueden ser el síntoma de alguna propiedad desconocida, ya sea para tamaños específicos o algo generalizable a todas las matrices. Y eso sí que sería la repanocha

1

Glumyglu #45 Oct '22

#38 No entiendo bien a qué te refieres exactamente, lo siento. Pero si lo que entiendo no está muy desencaminado, precisamente la situación que ocurriría es que esa diferencia jamás va a ser inferior a X (con un valor realista de X), sino que crecerá indefinidamente o te convergerá a otra cosa que no es. Como ejemplo de algoritmo no estable está Gramm-Schmidt para ortonormalizar un conjunto de vectores. Teóricamente debería arrojar el resultado correcto siempre, pero, en la práctica no lo hace porque es muy sensible al uso de la aritmética de precisión finita. Por eso en la práctica se usan otros métodos que, si bien téoricamente equivalentes y más costosos, te dan el resultado correcto.

Este algoritmo (Lanczos) intenta aproximar los valores propios de una matriz A. En cierto proceso se necesita ortonormalizar un conjunto de vectores y se usa Gramm-Schmidt, se puede ver que el error global no tiende a 0, por lo que el resultado es correcto (en este caso parece ser que se disponían de los valores propios reales para compararlos). Este algoritmo tiene coste O(kn) con n las filas de la matriz y k el número de pasos, su contra parte (que arroja un resultado bastante mejor) es O(k²n), bastante mayor. Sin embargo, arroja un resultado más sensato.

Perdona la chapa. Solo quería dejar claro que (y a todo el hilo, no a ti en particular), si bien un método puede ser rápido (o mucho más rápido) que otro, hay muchas más cosas a considerar. Si llega rapidísimo a un resultado que es una mierda, pues no te sirve de nada. Toca sospesar hasta qué punto puedes perder precisión por ganar velocidad. Y si el anterior más rápido, Strassen, no parece usarse demasiado en la práctica por estos problemas, hasta que no se analice la estabilidad de este método habría que ser bastante cautos.

1 respuesta

Kike_Knoxvil #46 Oct '22

#45 En el caso de este estudio se tendrá el resultado final que se considera correcto (no creo que se lancen a mirar solo si es rápido a ciegas); por lo que estaría alcanzando el mismo valor que el resto de métodos pero en menos pasos.
Yo simplemente te lo comento para los procesos iterativos en sistemas discretizados del mundo real: Si por ejemplo estás calculando la resistencia de una viga de un metro con un millon de elementos el proceso igual te lleva 15 minutos con los algoritmos de siempre, si con este se llega al mismo resultado en 10, eso que ganas. Si además, al dejarlo el mismo tiempo llega a una solución más refinada, pues mejor pero no es realmente el objetivo.

Si a lo que tienes miedo es de que a partir de cierto paso el valor empiece a diverger por la imprecisión numérica... Bueno, eso también se puede medir (tu mismo has puesto un ejemplo donde en teoría se ve a partir de que momento el valor del error empieza a aumentar en lugar de reducirse); pero una cosa te digo: en la inmensa mayor parte de las aplicaciones de las simulaciones, que el error aumente estando en el orden de nanos (10^-9) es insignificante. Donde más se va a notar es en procesos de investigación, pero para procedimientos industriales de cálculo donde la precisión no importa tanto pero sí el tiempo que está simulando es donde mejor van a destacar.

Pero vaya, que a mi me parece de cajón que para este estudio una de las primeras formas de filtrar los resultados es que lleguen a las respuestas correctas en varias pruebas

1 respuesta

Glumyglu #47 Oct '22

#46Kike_Knoxvil:
Si además, al dejarlo el mismo tiempo llega a una solución más refinada, pues mejor pero no es realmente el objetivo

No se trata de llegar a una solución más refinada o no, se trata de que no llegas a la solución.

#46Kike_Knoxvil:
se ve a partir de que momento el valor del error empieza a aumentar en lugar de reducirse

Se ve porque para ese ejemplo se tienen los valores propios reales de la matriz, si no los tuvieses no lo podrías saber. De hecho en la gráfica aparece la cota teórica sobre el error y cómo, a efectos prácticos, no sirve de nada por los problemas de estabilidad numérica.

#46Kike_Knoxvil:
el error aumente estando en el orden de nanos (10-9) es insignificante

Me parece aventurado decir que es insignificante si, en principio, no sabes cuánto error vas a poder arrastrar.

No entiendo muy bien a dónde quieres llegar. ¿Has usado alguna vez en alguno de tus proyectos/trabajo el algoritmo de Strassen para multiplicar matrices?

1 respuesta

c0b4c #48 Oct '22

https://arxiv.org/abs/2210.04045

XD

Kike_Knoxvil #49 Oct '22

#47 No entiendo: si en la validación se llega a la misma respuesta que los demás algoritmos que se sabe que dan la solución correcta dentro de una cota, ¿como puede no llegar a la solución? No le veo lógica a esa afirmación

Un error de nanos es insignificante en la vida real, por ejemplo en el diseño de un tanque a presión: te da igual que el resultado sea de 1000000000 Pa que 1000000001 Pa porque vas a tener otros problemas y errores a la hora de fabricarlo que van a ser más críticos, además de un coeficiente de seguridad para porsiacaso

Personalmente no, no he trabajado con el algoritmo de Strassen, a lo sumo elegir el orden de RK para la resolución iterativa de simulaciones pero a nivel interno era cosa de Matlab/ANSYS como manejar esas matrices

3 respuestas

Glumyglu #50 Oct '22

#49 Pues no sé qué validación habrán hecho, pero que en los casos que hayan usado dé un resultado válido no significa que lo vaya a hacer siempre, por varios motivos. Y, precisamente lo que digo es que el error no tiene que reducirse a un error de nanos, ejemplo (aunque no en una aplicación industrial): el accidente con el misil Patriot. Y lo que sé es que en el propio paper mencionan (si no lo he entendido mal) que no han tenido en cuenta esas cuestiones.

Matlab usa las rutinas dadas por BLAS para multiplicar matrices. Por lo que en caso de ser matrices sin ninguna estructura especial, usa la multiplicación convencional. El algoritmo de Strassen ofrece mejoras de velocidad (según este mismo paper) mayores sobre la multiplicación de matrices convencional que las que este nuevo algoritmo ofrece sobre Strassen y se lleva conociendo durante más de 50 años. Aun así no parece utilizarse en la mayoría de implementaciones porque no merece la pena lidiar con esas pérdidas de estabilidad, ¿qué te hace pensar que no van a ser importantes en este caso? Luego además, hay que tener en cuenta que en muchos casos reales las matrices que surgen tienen estructura "especial" que permiten un algoritmo propio de multiplicación más rápido que el convencional.

Que ojo, no digo que luego se haga un análisis de esto y salga favorecido respecto a Strassen, pero se trata precisamente de eso. de que hay que hacerlo antes de implementar nada.