Descubrir algoritmos más rápidos para la multiplicación de matriz sigue siendo una búsqueda clave en informática y álgebra lineal numérica. Desde las contribuciones pioneras de Strassen y Winograd a fines de la década de 1960, que mostraron que los productos de matriz general podrían calcularse con menos multiplicaciones de lo que se creía anteriormente, han surgido varias estrategias. Estos incluyen métodos basados en gradiente, técnicas heurísticas, marcos teóricos grupales, caminatas aleatorias basadas en gráficos y aprendizaje de refuerzo profundo. Sin embargo, se ha colocado significativamente menos enfoque en los productos de matriz con una estructura inherente, como cuando la segunda matriz es la transposición o idéntica a la primera, o cuando las matrices poseen dispersión o simetría. Esta supervisión es notable, dado que las expresiones como AA^t aparecen con frecuencia en dominios como estadísticas, aprendizaje profundo y comunicaciones, que representan construcciones críticas como las matrices de gram y covarianza. Además, xx^t es repetitivo en modelo de lenguaje grande Algoritmos de entrenamiento como Muon y Shampoo.
Estudios anteriores han explorado la multiplicación de matriz estructurada utilizando varios métodos teóricos y de aprendizaje automático basados en el aprendizaje. La teoría de la representación y el marco Cohn -Umans se han empleado para diseñar esquemas de multiplicación eficientes para matrices estructuradas. El aprendizaje de refuerzo también ha demostrado ser prometedor: los modelos han aprendido a descubrir o redescubrir algoritmos conocidos como los de Strassen. El trabajo reciente se ha centrado en optimizar el cálculo de XX^t sobre campos finitos y dominios complejos. Entre estos, el método conocido más eficiente para el algoritmo de Strassen es el algoritmo de Strassen, que aplica el algoritmo de Strassen de manera recursiva en las matrices de bloque 2 × 2, traduciendo efectivamente el problema estructurado en el dominio de la multiplicación general de matriz.
Investigadores de la Universidad China y el Instituto de Investigación Shenzhen de Big Data han desarrollado RXTX, un algoritmo para calcular eficientemente xx^t donde X pertenece a R^n*m. RXTX reduce el número de operaciones requeridas (multiplicaciones y adiciones) en aproximadamente un 5% en comparación con los métodos principales actuales. A diferencia de muchos algoritmos que solo muestran beneficios para matrices grandes, RXTX ofrece mejoras incluso para tamaños pequeños (por ejemplo, n = 4). El algoritmo se descubrió a través de la búsqueda basada en el aprendizaje automático y la optimización combinatoria, aprovechando la estructura específica de xx^t para la aceleración de factores constantes.
El algoritmo RXTX mejora la multiplicación de la matriz al reducir el número de operaciones en comparación con métodos anteriores como Strassen y Strassen-Winogrado recursivo. Utiliza 26 multiplicaciones de matriz general y esquemas de adición optimizados, lo que resulta en menos operaciones totales. El análisis teórico muestra que RXTX realiza menos multiplicaciones y operaciones combinadas, especialmente para matrices más grandes. Las pruebas prácticas en 6144 × 6144 matrices que usan una CPU de un solo hilo show rxtx son aproximadamente 9% más rápido que las rutinas BLAS estándar, con aceleraciones observadas en el 99% de las ejecuciones. Estos resultados destacan la eficiencia de RXTX para productos de matriz simétrica a gran escala y su ventaja sobre los algoritmos recursivos tradicionales y de última generación.
La metodología propuesta integra RL con una tubería de programación lineal entera mixta de dos niveles (MILP) para descubrir algoritmos de multiplicación de matriz eficientes, particularmente para calcular xx^t. La gran búsqueda del vecindario guiado por RL genera un gran conjunto de productos bilineales de Rank-1 potenciales, que son expresiones candidatas. MILP-A explora todas las combinaciones lineales de estos productos para expresar las salidas objetivo, mientras que MILP-B identifica el subconjunto más pequeño que puede representar todos los objetivos. Esta configuración refleja el enfoque alfatensor, pero lo simplifica al reducir significativamente el espacio de acción, centrándose en productos de tensor de baja dimensión y aprovechando solucionadores MILP como GUROBI para un cálculo rápido.
Por ejemplo, para calcular xx^t para una matriz 2 × 2 x, el objetivo es derivar expresiones como x_1^2 + x_2^2 o x_1x_3 + x_2x_4. La política rl randoMlY muestras miles de productos bilineales usando coeficientes de {−1, 0, +1}. MILP-A encuentra combinaciones de estos productos que coinciden con las expresiones deseadas, y MILP-B selecciona la menor cantidad necesaria para cubrir todos los objetivos. Este marco permitió el descubrimiento de RXTX, un algoritmo que realiza un 5% menos multiplicaciones y operaciones generales que los métodos anteriores. RXTX es eficiente para matrices grandes y pequeñas y demuestra una fusión exitosa de búsqueda basada en ML y optimización combinatoria.
Mira el Papel. Todo el crédito por esta investigación va a los investigadores de este proyecto. Además, siéntete libre de seguirnos Gorjeo Y no olvides unirte a nuestro 95k+ ml de subreddit y suscribirse a Nuestro boletín.
Sana Hassan, una pasante de consultoría en MarktechPost y estudiante de doble grado en IIT Madras, le apasiona aplicar tecnología e IA para abordar los desafíos del mundo real. Con un gran interés en resolver problemas prácticos, aporta una nueva perspectiva a la intersección de la IA y las soluciones de la vida real.
