EigenGame traza un nuevo enfoque para resolver problemas fundamentales de ML
Los sistemas modernos de IA abordan tareas como reconocer objetos en imágenes y predecir la estructura 3D de las proteínas como un estudiante diligente se prepararía para un examen. Al entrenarse en muchos problemas de ejemplo, minimizan sus errores con el tiempo hasta lograr el éxito. Pero éste es un esfuerzo solitario y sólo una de las formas conocidas de aprendizaje. El aprendizaje también se produce interactuando y jugando con otros. Es raro que un solo individuo pueda resolver por sí solo problemas extremadamente complejos. Al permitir que la resolución de problemas adquiera estas cualidades similares a las de un juego, esfuerzos anteriores de DeepMind han capacitado a agentes de IA para jugar. Captura la bandera y lograr Nivel de gran maestro en Starcraft. Esto nos hizo preguntarnos si una perspectiva similar basada en la teoría de juegos podría ayudar a resolver otros problemas fundamentales del aprendizaje automático.
Hoy en ICLR 2021 (la Conferencia Internacional sobre Representaciones del Aprendizaje), presentamos “EigenGame: PCA como equilibrio de Nash”, que recibió el premio al artículo destacado. Nuestra investigación exploró un nuevo enfoque para un viejo problema: reformulamos el análisis de componentes principales (PCA), un tipo de problema de valores propios, como juego competitivo de múltiples agentes lo llamamos EigenGame. El PCA suele formularse como un problema de optimización (o problema de agente único); sin embargo, descubrimos que la perspectiva de múltiples agentes nos permitió desarrollar nuevos conocimientos y algoritmos que utilizan los últimos recursos computacionales. Esto nos permitió escalar a conjuntos de datos masivos que anteriormente habrían sido demasiado exigentes desde el punto de vista computacional y ofrece un enfoque alternativo para exploraciones futuras.
PCA como equilibrio de Nash
Descrito por primera vez a principios del siglo XX, PCA Es una técnica de larga data para dar sentido a la estructura de datos de alta dimensión. Este enfoque ahora es omnipresente como primer paso en el proceso de procesamiento de datos y facilita la agrupación y visualización de datos. También puede ser una herramienta útil para aprender representaciones de baja dimensión para regresión y clasificación. Más de un siglo después, todavía existen razones de peso para estudiar el PCA.
En primer lugar, los datos se registraban originalmente a mano en cuadernos de papel y ahora se almacenan en centros de datos del tamaño de almacenes. Como resultado, este análisis familiar se ha convertido en un cuello de botella computacional. Los investigadores han explorado algoritmos aleatorios y otras direcciones para mejorar la forma en que PCA escala, pero descubrimos que estos enfoques tienen dificultades para escalar a conjuntos de datos masivos porque no pueden aprovechar completamente los recientes avances en computación centrados en el aprendizaje profundo, es decir, el acceso a muchas GPU o TPU paralelas.
En segundo lugar, PCA comparte una solución común con muchos problemas importantes de ingeniería y aprendizaje automático, a saber, la valor singular de descomposición (SVD). Al abordar el problema de PCA de la manera correcta, nuestros conocimientos y algoritmos se aplican de manera más amplia en todas las ramas del árbol de ML.
Como ocurre con cualquier juego de mesa, para reinventar el PCA como juego necesitamos un conjunto de reglas y objetivos que los jugadores deben seguir. Hay muchas formas posibles de diseñar un juego de este tipo; sin embargo, ideas importantes provienen del propio PCA: la solución óptima consta de vectores propios que capturan la varianza importante en los datos y son ortogonales entre sí.
En EigenGame cada jugador controla un vector propio. Los jugadores aumentan su puntuación al explicar la variación dentro de los datos, pero son penalizados si están demasiado alineados con otros jugadores. También establecemos una jerarquía: al jugador 1 solo le importa maximizar la variación, mientras que otros jugadores también tienen que preocuparse por minimizar su alineación con los jugadores que están por encima de ellos en la jerarquía. Esta combinación de recompensas y penalizaciones define la utilidad de cada jugador.
Con un diseño adecuado var y Alinear términos, podemos demostrar que:
- Si todos los jugadores juegan de manera óptima, juntos lograrán el equilibrio de Nash del juego, que es la solución PCA.
- Esto se puede lograr si cada jugador maximiza su utilidad de forma independiente y simultánea utilizando el ascenso de gradiente.
Esta propiedad de independencia del ascenso simultáneo es particularmente importante porque permite que el cálculo se distribuya entre docenas de TPU de Google Cloud, lo que permite el paralelismo tanto de datos como de modelos. Esto hace posible que nuestro algoritmo se adapte a datos verdaderamente a gran escala. EigenGame encuentra los componentes principales en cuestión de horas para conjuntos de datos de cien terabytes que comprenden millones de funciones o miles de millones de filas.
Utilidades, actualizaciones y todo lo demás
Al pensar en PCA desde una perspectiva de múltiples agentes, pudimos proponer algoritmos escalables y análisis novedosos. También descubrimos una conexión sorprendente con Aprendizaje hebbiano – o cómo se adaptan las neuronas cuando aprenden. En EigenGame, cada jugador que maximiza sus utilidades da lugar a ecuaciones actualizadas que son similares a actualizar reglas derivado de modelos hebbianos de plasticidad sináptica en el cerebro. Se sabe que las actualizaciones de Hebbian convergen con la solución PCA, pero no se derivan como gradiente de ninguna función de utilidad. La teoría de juegos nos brinda una nueva perspectiva para ver el aprendizaje hebbiano y también sugiere una serie de enfoques para los problemas del aprendizaje automático.
En un extremo del continuo de ML está el camino bien desarrollado de proponer una función objetivo que pueda optimizarse: utilizando la teoría de la optimización convexa y no convexa, los investigadores pueden razonar sobre las propiedades globales de la solución. En el otro extremo, puro conexionista Los métodos y reglas de actualización inspirados en la neurociencia se especifican directamente, pero el análisis de todo el sistema puede ser más difícil, y a menudo requiere el estudio de aspectos complicados. sistemas dinámicos.
Los enfoques de la teoría de juegos como EigenGame se encuentran en algún punto intermedio. Las actualizaciones de los jugadores no están limitadas a ser el gradiente de una función, solo una mejor respuesta a las estrategias actuales de los otros jugadores. Somos libres de diseñar utilidades y actualizaciones con propiedades deseables (por ejemplo, especificando actualizaciones que sean imparciales o aceleradas) mientras garantizamos que la propiedad Nash aún nos permite analizar el sistema en su conjunto.
EigenGame representa un ejemplo concreto de diseño de la solución a un problema de aprendizaje automático como resultado de un gran sistema multiagente. En términos más generales, diseñar problemas de aprendizaje automático como juegos multiagente es un desafío. diseño del mecanismo problema; sin embargo, los investigadores ya han utilizado la clase de dos jugadores, suma cero Juegos para resolver problemas de aprendizaje automático. Lo más notable es el éxito de redes generativas adversarias (GAN) como enfoque del modelado generativo ha despertado el interés en la relación entre la teoría de juegos y el aprendizaje automático.
EigenGame va más allá de esto hacia la configuración más compleja de suma general y muchos jugadores. Esto permite un paralelismo más obvio para una mayor escala y velocidad. También presenta un punto de referencia cuantitativo para que la comunidad pruebe nuevos algoritmos multiagente junto con dominios más ricos, como Diplomacia y Fútbol.
Esperamos que nuestro plan para diseñar utilidades y actualizaciones anime a otros a explorar esta dirección para diseñar nuevos algoritmos, agentes y sistemas. Esperamos ver qué otros problemas se pueden formular como juegos y si los conocimientos que obtengamos mejorarán aún más nuestra comprensión de la naturaleza multiagente de la inteligencia.
Para más detalles vea nuestro artículo. EigenGame: PCA como equilibrio de Nash y nuestro trabajo de seguimiento EigenGame Unloaded: Cuando jugar es mejor que optimizar.