Factorización de matriz a gran escala en TPU

Factorización de matriz a gran escala en TPU


La factorización matricial es una de las técnicas más antiguas pero aún ampliamente utilizada para aprender a recomendar elementos como canciones o películas a partir de las reseñas de los usuarios. En su forma básica, se aproxima a una matriz grande y escasa (es decir, en su mayoría vacía) de interacciones usuario-elemento con un producto de dos matrices más pequeñas y densas que representan el elemento aprendido y las características del usuario. Estas matrices densas, a su vez, se pueden usar para recomendar elementos a un usuario con los que nunca antes ha interactuado.

A pesar de su simplicidad algorítmica, la factorización de matrices aún puede lograr un rendimiento competitivo en los puntos de referencia de recomendación. La alternancia de mínimos cuadrados (ALS) y en particular su variación implícita es un algoritmo fundamental para aprender los parámetros de factorización de matrices. ALS es conocido por su alta eficiencia, ya que escala linealmente en el número de filas, columnas y valores distintos de cero. Por lo tanto, este algoritmo es muy adecuado para grandes desafíos. Pero para conjuntos de datos de factorización de matrices del mundo real muy grandes, la implementación de una sola máquina no sería suficiente y, por lo tanto, requeriría un gran sistema distribuido. La mayoría de las implementaciones distribuidas de factorización de matrices que usan ALS utilizan dispositivos de CPU estándar, y con razón, dada la naturaleza inherentemente escasa del problema (la matriz de entrada está casi vacía).

Por otro lado, el éxito reciente del aprendizaje profundo, que ha demostrado una capacidad computacional creciente, ha provocado una nueva ola de investigación y avance en los aceleradores de hardware, como las unidades de procesamiento de tensor (TPU). Las TPU ofrecen aceleraciones de hardware específicas del dominio, especialmente para casos de uso como el aprendizaje profundo que implica un gran número de multiplicaciones de matrices densas. En particular, permiten aceleraciones significativas para cargas de trabajo paralelas de datos tradicionales, como B. Entrenamiento de modelos de descenso de gradiente estocástico (SGD) en modo SPMD (Single Program Multiple Data). El enfoque SPMD ha ganado popularidad en cómputos como el entrenamiento de redes neuronales con algoritmos de descenso de gradiente y se puede usar tanto para cómputos de datos paralelos como de modelos paralelos, donde distribuimos los parámetros del modelo entre los dispositivos disponibles. Aunque las TPU han sido tremendamente atractivas para los métodos basados ​​en SGD, no está claro de inmediato si una implementación de ALS de alto rendimiento que requiere una gran cantidad de ALS distribuidas escaso La matriz multiplicada se puede desarrollar para un gran grupo de dispositivos de TPU.

En «ALX: factorización de matriz a gran escala en TPU» examinamos un diseño de ALS distribuido que hace un uso eficiente de la arquitectura de TPU y se adapta bien a los problemas de factorización de matriz del orden de miles de millones de filas y columnas escalando el número de TPU disponibles que se convierten en núcleos. . El enfoque que proponemos utiliza una combinación de modelo y paralelismo de datos, en el que cada núcleo de TPU almacena parte de la tabla de incrustación y entrena en una pieza de datos única, agrupada en mini lotes. Para avanzar en la investigación futura sobre métodos de factorización de matrices a gran escala y para ilustrar las propiedades de escalabilidad de nuestra propia implementación, también creamos y publicamos un conjunto de datos de predicción de enlaces web reales llamado WebGraph.

La figura muestra el flujo de datos y el cálculo del marco ALX en dispositivos TPU. De manera similar a los métodos de entrenamiento basados ​​en SGD, cada núcleo de TPU realiza cálculos idénticos en su propia pila de datos en forma de SPMD, lo que permite el cálculo síncrono en paralelo en múltiples núcleos de TPU. Cada TPU comienza recopilando todas las incrustaciones de elementos relevantes en la etapa Sharded Gather. Estas incrustaciones materializadas se utilizan para buscar incrustaciones de usuarios, que se dispersan en el fragmento apropiado de la tabla de incrustaciones en la etapa de dispersión fragmentada.

Dosificación densa para mejorar la eficiencia
Diseñamos ALX específicamente para TPU aprovechando las propiedades únicas de la arquitectura de TPU y superando algunas limitaciones interesantes. Por ejemplo, cada núcleo de TPU tiene una memoria limitada y restringe todos los tensores a una forma estática, pero cada ejemplo en una minipila puede tener una gran variedad de elementos (es decir, las entradas pueden ser largas y escasas). Para resolver esto, dividimos ejemplos excesivamente largos en múltiples ejemplos más pequeños de la misma forma, un proceso llamado formación de lotes densos. Consulte nuestro artículo para obtener más detalles sobre el apilamiento denso.

Ejemplo ilustrativo de cómo se compactan lotes dispersos para aumentar la eficiencia en las TPU.

Fragmentación uniforme de tablas de incrustación
Con el problema de procesamiento por lotes resuelto, a continuación queremos factorizar una matriz dispersa en dos matrices de incrustación densas (por ejemplo, incrustaciones de usuarios y artículos) de modo que el producto escalar resultante de las incrustaciones esté cerca de la matriz dispersa original; esto nos ayuda a hacer predicciones para derivar todo las posiciones de la matriz original, incluidas las que estaban vacías, que se pueden usar para recomendar artículos con los que los usuarios no han interactuado. Ambas tablas de incrustación resultantes (ancho y alto en la figura a continuación) pueden ser potencialmente demasiado grandes para caber en un solo núcleo de TPU, lo que requiere una configuración de capacitación distribuida para la mayoría de los casos de uso a gran escala.

La mayoría de los intentos anteriores de factorización de matrices distribuidas utilizan una arquitectura de servidor de parámetros, donde los parámetros del modelo se almacenan en servidores de alta disponibilidad y los datos de entrenamiento son procesados ​​en paralelo por trabajadores que son los únicos responsables de la tarea de aprendizaje. Dado que, en nuestro caso, cada núcleo de TPU tiene una potencia de procesamiento y una memoria idénticas, es un desperdicio usar solo la memoria para almacenar los parámetros del modelo o la potencia de procesamiento para el entrenamiento. Así que diseñamos nuestro sistema para usar cada núcleo para ambos.

Ejemplo ilustrativo de la factorización de una matriz dispersa Y en dos matrices de inclusión densa W y H.

En ALX, compartimos ambas tablas de incrustación de manera uniforme, aprovechando al máximo tanto la cantidad de memoria distribuida disponible como los enlaces dedicados de baja latencia entre las TPU. Esto es muy eficiente para tablas incrustadas muy grandes y da como resultado un buen rendimiento para operaciones de recopilación y dispersión distribuidas.

Fragmentación uniforme de ambas tablas de inclusión (B y H) sobre núcleos de TPU (en azul).

gráfico web
Debido a que las aplicaciones potenciales pueden abarcar conjuntos de datos muy grandes, la escalabilidad puede ser una oportunidad importante para los avances en la factorización de matrices. Para este propósito, también publicamos un gran conjunto de datos de predicción de enlaces web del mundo real llamado WebGraph. Este conjunto de datos se puede modelar fácilmente como un problema de factorización matricial, donde las filas y las columnas son enlaces de origen y de destino, respectivamente, y la tarea es predecir los enlaces de destino de cada enlace de origen. Usamos WebGraph para ilustrar las propiedades de escala de ALX.

El conjunto de datos de WebGraph se generó a partir de un solo rastreo realizado por CommonCrawl en 2021, donde eliminamos todo y solo conservamos los datos de Enlace-> Enlaces externos. Debido a que el rendimiento de un método de factorización depende de las propiedades del gráfico subyacente, creamos seis versiones de WebGraph, cada una con un patrón de escasez y una configuración regional diferentes, para examinar qué tan bien funciona ALS para cada una.

  • Para examinar los gráficos específicos de la configuración regional, filtramos en función de dos dominios de nivel superior: «de» e «in», cada uno de los cuales produce un gráfico con un orden de magnitud menos nodos.
  • Estos gráficos aún pueden exhibir patrones aleatorios de escasez y enlaces colgantes. Por lo tanto, filtramos aún más los nodos en cada gráfico para tener al menos 10 o 50 enlaces entrantes y salientes.

Para facilitar el acceso, los hemos puesto a disposición como un paquete de conjunto de datos de Tensorflow. Como referencia, la versión más grande, WebGraph-sparse, tiene más de 365 millones de nodos y 30 mil millones de bordes. Creamos y publicamos divisiones de entrenamiento y prueba con fines de evaluación.

Resultados
Ajustamos cuidadosamente el sistema y los parámetros de calidad de ALX. Basado en nuestras observaciones con respecto a la precisión y elección de solucionadores lineales. Descubrimos que al elegir cuidadosamente la precisión para almacenar las tablas de incrustación (bfloat16) y para ingresar a los solucionadores lineales (float32), podíamos reducir a la mitad la memoria requerida para las incrustaciones y aún así evitar problemas debido a valores de precisión más bajos durante la solución. fase. Para nuestros solucionadores lineales, elegimos gradientes conjugados, que han demostrado consistentemente ser los más rápidos en TPU. Usamos incrustaciones de dimensión 128 y entrenamos el modelo para 16 épocas. En nuestra experiencia, el ajuste de hiperparámetros a través de la penalización de la norma (λ) y el peso no observado (α) fue esencial para obtener buenas métricas de recuperación, como se muestra en la siguiente tabla.

Resultados obtenidos al ejecutar ALX en todas las versiones del conjunto de datos de WebGraph. Las puntuaciones de recuerdo de 1,0 significan un recuerdo perfecto.

análisis de escala
Dado que los datos de entrada se procesan en paralelo en los núcleos de TPU, aumentar la cantidad de núcleos reduce el tiempo de entrenamiento, idealmente de forma lineal. Sin embargo, al mismo tiempo, una mayor cantidad de núcleos requiere más comunicación de red (debido a las tablas de incrustación fragmentadas). Gracias a las interconexiones de alta velocidad, esta sobrecarga puede ser insignificante para una pequeña cantidad de núcleos, pero a medida que aumenta la cantidad de núcleos, la sobrecarga eventualmente ralentiza el escalado lineal ideal.

Para confirmar nuestra hipótesis, analizamos las propiedades de escala de las cuatro variantes de WebGraph más grandes en términos de tiempo de entrenamiento a medida que aumentamos la cantidad de núcleos de TPU disponibles. Incluso empíricamente, como se muestra a continuación, observamos la disminución lineal predicha en el tiempo de entrenamiento hasta un punto óptimo, después del cual la sobrecarga de la red ralentiza la disminución.

Análisis de escalado del tiempo de ejecución a medida que aumenta el número de núcleos de TPU. Cada figura muestra el tiempo que se tarda en entrenar para una época en segundos.

Conclusión
Para facilitar el acceso y la reproducibilidad, el código ALX es de código abierto y se ejecuta sin problemas en Google Cloud. De hecho, demostramos que una matriz dispersa como WebGraph-dense con un tamaño de 135M x 135M (con bordes de 22B) se puede factorizar en menos de un día en un colab conectado a 8 núcleos de TPU. Diseñamos el marco ALX con la escalabilidad en mente. Con 256 núcleos de TPU, una época de la variante de WebGraph más grande, WebGraph-sparse (matriz dispersa de 365M x 365M), tarda unos 20 minutos (5,5 horas para la ejecución de entrenamiento completa). El modelo final tiene alrededor de 100 parámetros B. Esperamos que ALX y WebGraph sean útiles tanto para los investigadores como para los profesionales que trabajan en estos campos. ¡Puedes encontrar el código para ALX aquí en github!

Gracias
El equipo central incluye a Steffen Rendle, Walid Krichene y Li Zhang. Agradecemos a muchos colegas de Google por su ayuda en varias fases de este proyecto. En particular, estamos agradecidos con el equipo de JAX por las numerosas discusiones, particularmente con James Bradbury y Skye Wanderman-Milne; Blake Hechtman por su ayuda con XLA y Rasmus Larsen por discusiones útiles sobre el rendimiento de los solucionadores lineales en TPU. Finalmente, también agradecemos a Nicolás Mayoraz y John Anderson por sus útiles comentarios.

Related post

Google quiere proporcionar AR a escala mundial con Google Maps

Google quiere proporcionar AR a escala mundial con Google…

Google Maps está recibiendo una actualización importante. Mientras Google es por 2 horas E/S 2022 En el evento de la semana…
Este enorme juego de bicicletas VR parece un gran momento para pasar un buen rato.

Este enorme juego de bicicletas VR parece un gran…

Para dar vida a la experiencia, QValem desarrolló su propia pista de carreras virtual y la superpuso al mundo real. en…
Este desarrollador creó un gran juego de carreras de realidad virtual en una pista de carreras

Este desarrollador creó un gran juego de carreras de…

Un nuevo juego de búsqueda experimental permite a su creador subirse a una bicicleta real y montarla en una pista de…

Leave a Reply

Tu dirección de correo electrónico no será publicada.