Resolver ARC-AGI sin preentrenamiento
(iliao2345.github.io)- En problemas como ARC-AGI, donde hay que encontrar reglas a partir de pocos ejemplos, CompressARC encuentra soluciones usando solo aprendizaje en tiempo de inferencia por rompecabezas, sin preentrenamiento, datasets externos ni búsqueda a gran escala
- La idea central es un experimento sobre si puede emerger un comportamiento inteligente al optimizar el objetivo de compresión de información sin pérdida para que la representación del rompecabezas, incluida la respuesta, se vuelva más corta
- Usando unos 20 minutos por rompecabezas en una RTX 4070, registró 34.75% en el conjunto de entrenamiento y 20% en el conjunto de evaluación, y se distingue por ser un enfoque con redes neuronales que usa como datos de entrenamiento solo el rompecabezas objetivo
- La arquitectura está diseñada alrededor de la equivarianza respecto al orden de los ejemplos, las permutaciones de color y las rotaciones y reflexiones, y usa una representación de multitensor que agrupa tensores de varios rangos
- Muestra fortalezas en mapeo color-procedimiento, rellenado, recorte, conexión de puntos y movimientos cortos, pero contar, extender patrones a larga distancia, rotar/copiar/redimensionar y la planificación de agentes siguen siendo cuellos de botella
Experimento: si se puede resolver ARC-AGI solo con compresión
- La pregunta central es si la compresión de información sin pérdida por sí sola puede producir comportamiento inteligente
- CompressARC es un método para rompecabezas ARC-AGI que funciona únicamente con una función objetivo basada en compresión
- Plantea tres restricciones
- Sin preentrenamiento: el modelo se inicializa al azar y se entrena en tiempo de inferencia
- Sin dataset: cada modelo aprende solo un rompecabezas ARC-AGI objetivo y produce una sola respuesta
- Sin búsqueda: usa descenso por gradiente casi sin búsqueda en el sentido habitual
- Los resultados fueron 34.75% en entrenamiento y 20% en evaluación, y cada rompecabezas tarda aproximadamente 20 minutos en una RTX 4070
- Se presenta como el primer método neuronal para ARC-AGI que usa solo el rompecabezas objetivo como datos de entrenamiento
Configuración del problema ARC-AGI
- ARC-AGI es un benchmark de IA presentado en 2019 que pone a prueba la capacidad de inferir y generalizar reglas abstractas a partir de pocos ejemplos
- Cada rompecabezas proporciona varios ejemplos de entrada-salida y una entrada de prueba, y el sistema debe acertar la cuadrícula de salida de prueba
- Se permiten dos intentos por rompecabezas, y si uno de los dos es correcto se obtiene 1 punto
- Se puede cambiar el tamaño de la cuadrícula de salida y elegir el color de todos los píxeles
- Los rompecabezas están diseñados para que una persona razonable pueda resolverlos, pero resulten más difíciles para máquinas
- El humano promedio resuelve 76.2% del conjunto de entrenamiento
- Los expertos humanos resuelven 98.5%
- Los 400 rompecabezas de entrenamiento son más fáciles que el resto y buscan enseñar los siguientes patrones
- Objetualidad: los objetos no aparecen ni desaparecen sin razón
- Orientación a objetivos: algunos objetos actúan como agentes con intención
- Números y conteo: se usan cantidad de objetos, alineación, comparación, suma y resta básicas
- Geometría y topología: incluye reflexión, rotación, traslación, transformación, combinación, repetición y diferencias de distancia de figuras
- La competencia reciente de Kaggle de ARC Prize tuvo premios de hasta más de 1 millón de dólares, y el premio principal estaba asignado a un método que lograra 85% en 100 problemas ocultos con 12 horas de cómputo en un entorno restringido
Cómo funciona CompressARC
- En CompressARC, una representación que se comprime a menos bits se asocia con una respuesta más correcta del rompecabezas
- El sistema busca una representación comprimida que convierta un rompecabezas incompleto en uno completo, de modo que al descomprimir esa representación se reconstruyan el rompecabezas y la respuesta
- La red neuronal cumple el papel de decodificador
- No hay una red neuronal codificadora separada
- La codificación se implementa entrenando el decodificador en tiempo de inferencia mediante descenso por gradiente
- Los pesos optimizados y la configuración de la distribución de entrada cumplen el papel de representación comprimida en bits del rompecabezas y la respuesta
- En términos estándar de machine learning, el procedimiento es el siguiente
- Se recibe un rompecabezas ARC-AGI
- Se construye una red neuronal
facorde al número de ejemplos del rompecabezas y al número de colores observados - Toma una entrada normal aleatoria
z ~ N(μ, Σ)y produce logits de color por píxel para todas las cuadrículas - Minimiza la suma de entropía cruzada sobre las cuadrículas conocidas e ignora la cuadrícula de respuesta
- Añade una penalización por divergencia KL para que
N(μ, Σ)se acerque aN(0,1) - Guarda las cuadrículas de respuesta generadas durante el entrenamiento y elige como predicción final la respuesta que más se repite
fθestá diseñado para ser equivariante ante aumentos comunes como cambiar el orden de los pares entrada-salida, permutar colores y aplicar rotaciones o reflexiones espaciales
Derivación desde la perspectiva de compresión
- La compresión sin pérdida consiste en representar información con la menor cantidad posible de bits, pudiendo reconstruir exactamente el original a partir de esa representación
- En ARC-AGI, en principio habría que comprimir el símbolo completo formado por el rompecabezas y su respuesta, pero en la práctica la respuesta no está en la entrada del codificador y tampoco se conoce la distribución generadora de rompecabezas
- Se asume que existe un sistema de compresión eficiente en bits y factible de implementar para el dataset ARC-AGI
- Incluso sin conocer la distribución
p, se puede pensar en un compresor universal que minimice la longitudlen(f)+len(s)de un programafy una entradas- El decodificador ejecuta
f(s)para reconstruir el original - En teoría de la información algorítmica, solo puede ser menos eficiente que el compresor original por la longitud de
f - En la práctica, un codificador que explore el espacio de programas no es viable
- El decodificador ejecuta
- CompressARC elige un forward pass de una red neuronal como programa fijo en lugar de explorar el espacio de programas
sestá compuesto por los pesosθ, la entradazy una corrección de salidaεθyzcalculan longitud de código desde la perspectiva de Relative Entropy Coding (REC), yεdesde la perspectiva de arithmetic coding- La longitud de código de corrección de salida se vuelve igual a la entropía cruzada total de las cuadrículas conocidas
- La longitud de código de
zpasa a serKL(pz || qz), conqz = N(0,I)
- La longitud total de código toma la misma forma que la pérdida de un VAE
- error de reconstrucción
- KL sobre
z - regularización del decodificador
- La implementación de CompressARC incluye modificaciones sobre esa derivación relacionadas con parte de la regularización, la equivarianza y la independencia entre rompecabezas
Arquitectura: multitensor y equivarianza
- La característica más importante de la arquitectura es la equivarianza
- Si la entrada
zse transforma, la salida del rompecabezas ARC-AGI también debe transformarse de la misma manera - Los ejemplos incluyen reordenamiento de pares entrada-salida, mezcla de colores y volteos, rotaciones y reflexiones de la cuadrícula
- Si la entrada
- El diseño parte de una arquitectura base completamente simétrica y luego agrega capas asimétricas que introducen las capacidades no equivariantes necesarias, rompiendo una a una las simetrías innecesarias
- Los datos internos fluyen en un formato llamado multitensor
- Es un conjunto de tensores con distintos rangos y shapes
- Sus dimensiones se componen de subconjuntos de hasta
[n_examples, n_colors, n_directions, height, width, n_channels] - La dimensión
channelsiempre se conserva - Aplicando reglas se reduce a 18 la cantidad de tensores válidos dentro del multitensor
- Un rompecabezas puede representarse como un tensor
[examples, colors, height, width, channel]channelse usa para seleccionar la cuadrícula de entrada o de salidawidthyheightrepresentan la posición de los píxeles- La dimensión
colorcontiene una codificación one-hot del color de cada píxel
- La arquitectura completa sigue este flujo
- comienza con los parámetros de la distribución de
z - Decoding Layer
- repite 4 veces Multitensor Communication, Softmax, Directional Cummax, Directional Shift, Directional Communication, Nonlinear y Normalization
- Linear Heads para producir la distribución del rompecabezas ARC-AGI
- comienza con los parámetros de la distribución de
Resultados de rendimiento
- El entrenamiento se realizó con Adam durante 2000 iterations
- tasa de aprendizaje
0.01 β1 = 0.5,β2 = 0.9
- tasa de aprendizaje
- Resultados en el conjunto de entrenamiento
- 100 iteration: Pass@2 2.25%
- 500 iteration: Pass@2 27.5%
- 1000 iteration: Pass@2 31.75%
- 2000 iteration: Pass@2 34.75%
- Pass@1000 en 2000 iteration: 52.75%
- Resultados en el conjunto de evaluación
- 100 iteration: Pass@2 1.25%
- 500 iteration: Pass@2 15%
- 1000 iteration: Pass@2 19.25%
- 2000 iteration: Pass@2 20%
- Pass@1000 en 2000 iteration: 33.75%
- Como la evaluación de ARC-AGI permite dos intentos, el resultado clave del texto se mide con Pass@2
Rompecabezas que puede resolver y los que se le dificultan
- CompressARC identifica reglas hasta donde se lo permiten sus capacidades, pero se topa con cuellos de botella en habilidades que su arquitectura no tiene
- Ejemplos de tareas posibles
- asignar colores individuales a procedimientos individuales
- rellenar
- recortar
- conectar puntos, incluidas diagonales de 45 grados
- detectar el mismo color
- identificar adyacencia de píxeles
- asignar colores por ejemplo
- identificar partes de una figura
- movimientos a corta distancia
- También quedan claras las tareas difíciles
- hacer corresponder dos colores entre sí
- repetir la misma operación varias veces seguidas
- mover, rotar, reflejar, redimensionar y copiar imágenes
- detectar propiedades topológicas como conectividad
- planificar y simular comportamiento de agentes
- extender patrones a larga distancia
- En el rompecabezas de entrenamiento 28e73c20 hay que extender un patrón desde los bordes hacia el centro, pero CompressARC solo extiende a corta distancia y cerca del centro depende de conjeturas
Caso: Color the Boxes
- En la solución humana se identifica que la entrada está dividida en cajas y que en la salida esas cajas quedan coloreadas
- las esquinas siempre son negras
- el centro siempre es magenta
- las cajas de los lados se colorean según la dirección: arriba rojo, abajo azul, derecha verde, izquierda amarillo
- El progreso de entrenamiento de CompressARC cambia por etapas
- 50 step: refleja que las filas y columnas celestes de la entrada también corresponden en la salida
- 150 step: muestra una forma de salida donde los píxeles cercanos tienden a tener colores parecidos
- 200 step: imita bloques de color más grandes recortados por bordes celestes y bloques de esquinas negras
- 350 step: acierta en general los colores de las cajas según la dirección respecto al centro
- 1500 step: la salida queda casi refinada, aunque en las muestras todavía aparecen errores raros
- El análisis de la distribución aprendida de
zmuestra que codifica una tabla de correspondencia color-dirección y la posición de las líneas divisorias de filas y columnas - Solo cuatro tensores conservan información
(examples, height, channel): contiene la posición de las filas celestes de cada ejemplo(examples, width, channel): contiene la posición de las columnas celestes de cada ejemplo(direction, color, channel): contiene la correspondencia entre dirección y color(color, channel): distingue el papel especial del magenta y del celeste
Casos adicionales y análisis de representaciones
-
Bounding Box rompecabezas 6d75e8bb
- La solución humana consiste en dibujar la caja celeste más pequeña que encierra la figura roja
- CompressARC muestra señales de haber identificado la bounding box común en 100 step, y en 150 step encuentra la respuesta para luego refinarla con más entrenamiento
- Los tensores principales que sobreviven son
(examples, height, channel),(examples, width, channel)y(color, channel) - Los tensores de filas y columnas indican las filas y columnas con muchos píxeles celestes, pero no está claro cómo conoce la posición de los bordes
-
Center Cross rompecabezas 41e4d17e
- Desde el centro de la burbuja azul de la entrada, hay que dibujar rayos magenta hacia arriba, abajo, izquierda y derecha, y el color de la burbuja debe quedar por encima de esos rayos
- CompressARC copia primero la entrada, luego aparecen filas y columnas magenta y gradualmente se estabilizan en la posición correcta
- No muestra el error típico de la solución humana de dibujar mal los rayos por encima de la burbuja
- Los tensores que sobreviven son
(examples, height, width, channel)y(color, channel) (examples, height, width, channel)codifica el centro de la burbuja
Ideas de mejora
- En vez de comprimir cada rompecabezas por separado, comprimir en conjunto todo el dataset ARC-AGI podría compartir cómputo entre rompecabezas y aportar un mejor sesgo inductivo
- Se considera usar los mismos pesos de red para todos los rompecabezas y aplicar perturbaciones limitadas por rompecabezas
- También se propone un enfoque de hypernetwork que aprenda embeddings de alta dimensión por rompecabezas y una proyección lineal desde esos embeddings hacia los pesos de la red
- No se intentó porque esa dirección podría ralentizar el ciclo de iteración de investigación
- Para tareas de copiado de figuras podrían servir capas del tipo convolution
- Si una cuadrícula almacena la figura y otra marca la posición de copia, una convolution podría producir el resultado copiado
- La convolution común tenía el problema de amplificar más el ruido que la señal
- La tropical convolution funcionó bien en rompecabezas de juguete, pero no fue suficiente para los rompecabezas de entrenamiento de ARC-AGI
- También se consideró usar un KL floor para aliviar el posterior collapse
- Se observó que cuando el KL de tensores importantes cae a 0, luego ya no logra recuperarse
- Mantener el KL por encima de 0 durante un tiempo podría hacer que la red aprenda a usar esa información
- Se implementó, pero no se vieron casos donde los tensores se recuperaran, y probablemente haga falta otro diseño del schedule del KL floor
- La regularización no se usa en la implementación
- En la formulación del problema es el elemento que mide la complejidad de
fy forma parte de la derivación de CompressARC - Se considera algo temerario haberla omitido en la implementación
- En la formulación del problema es el elemento que mide la complejidad de
Trabajo relacionado y posición dentro de la investigación
- La idea de la equivalencia entre compresión e inteligencia está inspirada en el Hutter Prize
- El Hutter Prize premia al sistema que mejor comprime un archivo de texto de Wikipedia y vincula la capacidad de compresión con la inteligencia
- El trasfondo teórico incluye Solomonoff Induction, Kolmogorov Complexity y Minimum Description Length
- Desde la perspectiva de teoría de la información, Relative Entropy Coding es clave
- Se plantea que, si se puede acotar la divergencia KL, entonces se puede construir un algoritmo de compresión, abstrayendo el problema de implementar códigos binarios reales
- Desde la perspectiva VAE, el decodificador cumple el papel de algoritmo de descompresión
- También podrían considerarse neural Turing machine con capacidades más generales, pero como no se adaptan bien a la optimización por descenso por gradiente se optó por el enfoque VAE
- Reponderar la pérdida de reconstrucción al estilo beta-VAE funciona bien en este caso
- Los métodos previos para ARC-AGI suelen usar LLM, aumento de datos, datasets alternativos, aprendizaje en tiempo de prueba y búsqueda de programas basada en lenguajes específicos del dominio
- CompressARC enfatiza que usa deep learning sin preentrenamiento externo ni búsqueda a gran escala
- El código del proyecto está publicado en GitHub
1 comentarios
Comentarios de Hacker News
El preentrenamiento a gran escala parece ir en contra del propósito de la generalidad.
Si se creó una máquina general capaz de sintetizar un programa que, viendo solo 3 ejemplos, predice el cuarto, entonces en la práctica se resolvió la síntesis de oráculos.
En cambio, si se entrenó una red con todo el conocimiento humano, incluida la creación de acertijos, luego se hizo ajuste fino con el 99% del dataset y se le permitió intentar varias veces con el 1% restante, eso se parece más a haber creado un compresor caro que comprime la psicología de quien diseña el examen.
Presupone que existe un ámbito platónico de lógica y razón al que una AGI solo tendría que conectarse, pero sin contexto no puede haber significado, ni inferencia, ni lógica.
Para reconocer patrones de figuras se necesita el concepto de figura, lo que presupone el concepto de relaciones espaciales, que a su vez presupone el concepto de espacio 2D o 3D.
Estas cosas parecen obvias e implícitas porque están profundamente incorporadas en el entorno que la mente humana evolucionó durante cientos de millones de años para interpretar, y en el entorno que ha consumido y procesado durante décadas.
La verdadera prueba para una AGI es la capacidad de asimilar información diversa en una visión coherente del mundo, y el preentrenamiento en realidad hace justamente eso.
Incluso una inteligencia con esa capacidad probablemente necesite tener “precargadas” suposiciones estructurales sobre el mundo en el que se ubicará. Algo parecido a las áreas del cerebro especializadas en relaciones espaciales, lenguaje e interpretación sensorial.
Los humanos también, cuando queremos mejorar en algo, descubrimos cómo practicar esa tarea y aprendemos de una forma que efectivamente nos hace mejorar.
Por eso hay quienes creen que no habrá AGI por un buen tiempo: https://www.lycee.ai/blog/why-no-agi-openai
No veo por qué deberíamos esperar que una máquina generalice bien sin conocimiento de fondo.
Me hizo pensar en el podcast de Lex Fridman con Marcus Hutter.
Joshua Bach también definió la inteligencia como la capacidad de modelar la realidad con precisión, y me pregunto si la compresión sin pérdida en sí misma es inteligencia, o si es el modelo de ajuste óptimo. ¿Hay alguna diferencia entre ambas?
https://www.youtube.com/watch?v=E1AxVXt2Gv4
Por lo tanto, hay que mirar cuatro ejes: simplicidad, precisión, latencia y complejidad de la realidad; la inteligencia artificial ocupará alguna región dentro de ese espacio.
De hecho, hay una prueba simple para distinguir la inteligencia: si puede leer código de una función en C y decir cómo los cambios en la entrada afectan la salida.
En algoritmos complejos hay que construir un modelo interno. Si no, ¿cómo ejecutarías mentalmente cómo funciona qsort con un millón de elementos?
También se puede distinguir del mismo modo si un estudiante solo finge entender o si realmente entendió.
Una prueba más difícil es la inversa: crear un algoritmo viendo solo algunos ejemplos de entrada y salida.
[1] http://prize.hutter1.net/
Estoy tratando de destilar la esencia de este enfoque, pero parece estar oculta detrás de detalles no esenciales como la elección de un método de compresión específico o una distribución previa
La innovación central parece estar en construir un “modelo” que pueda optimizarse con descenso de gradiente, y hacer que su punto óptimo sea el modelo más “simple” que recuerde la relación entrada-salida
Aquí, “simpleza” concretamente significa “que se puede comprimir de manera eficiente”, pero en términos más generales probablemente se acerque a que la complejidad del modelo sea lo más baja posible
Esto contrasta claramente con el aprendizaje automático estándar. Normalmente primero se elige la estructura del modelo y varios parámetros de complejidad para fijar un presupuesto de complejidad, y luego se entrena con datos para encontrar una solución que recuerde bien la relación de entrada y salida
Este nuevo método invierte el aprendizaje automático. Sigue recordando los pares de entrada-salida, pero optimiza para reducir al máximo la complejidad del modelo
Que pueda generalizar con solo 2 ejemplos de entrenamiento es realmente sorprendente, y creo que sugiere con fuerza una dirección correcta para abordar la generalización
El camino por el que los autores llegaron a esta estructura fue la teoría de la información, pero no estoy seguro de que eso sea lo esencial
La clave parece estar más bien en darse cuenta de que, en lugar de buscar el mejor modelo dentro de un presupuesto de complejidad fijo, se puede buscar el modelo de mínima complejidad posible
A la función objetivo de pérdida en optimización se le suele agregar un término de regularización, y esa regularización a menudo puede interpretarse como una penalización a la complejidad
Gracias a la dualidad, la misma función objetivo puede verse de varias maneras: minimizar una suma ponderada del error en los datos y la complejidad, minimizar la complejidad manteniendo el error en los datos por debajo de un límite, o minimizar el error en los datos manteniendo la complejidad por debajo de un límite
Esta regularización clásica parece haber pasado de moda últimamente
No creo que desempeñe un papel importante en la mayoría de las arquitecturas Transformer, pero sería interesante si volviera de alguna forma
Además de eso, este enfoque tiene tantos elementos nuevos que es difícil distinguir qué es lo que realmente impulsa el rendimiento
Por ejemplo, la propia arquitectura de la red neuronal también parece haber sido ajustada con bastante cuidado para maximizar el rendimiento en tareas tipo ARC-AGI, y no queda claro cómo generalizará más allá de eso
Cada rompecabezas tiene un formato similar, y los datos que varían dentro de cada uno coinciden casi exactamente con la información necesaria para inferir la regla
Si se reduce la cantidad de información necesaria para describir la regla, para minimizar la pérdida de información el códec casi no tiene alternativa más que reducirse a hacer lo que hace la regla misma
Si cada rompecabezas tuviera más ruido o datos arbitrarios, no creo que esta técnica hubiera funcionado
Por supuesto, a partir de cierto punto el rompecabezas no debería convertirse en “encontrar dónde está el rompecabezas”, pero aquí funciona porque cada ejemplo contiene información pura sobre el propio rompecabezas
Interesante. Cada vez pienso más que el futuro del aprendizaje automático podría ir hacia tener menos “aprendizaje automático” en el sentido al que estamos acostumbrados
Menos preentrenamiento, datos y búsqueda, y más representación directa, procesamiento simbólico, satisfacción de restricciones y metaaprendizaje
Las cosas que serán menos necesarias —preentrenamiento, datos, etc.— son desordenadas, indiscriminadas y accidentales
Si dependes de ellas, siempre quedas subordinado a la calidad de los datos, lo cual está bien si el objetivo es hacer minería de datos, pero no encaja si el objetivo es modelar las causas fundamentales de los datos
Según entiendo, esto se acerca a intentar revelar la representación mínima del espacio de soluciones/problemas
Mediante equivarianza, están siguiendo la estructura real del problema y derivando algo cercano a la representación subyacente real del rompecabezas y a cómo resolverlo, en lugar de esperar capturarlo por casualidad a partir de muchos ejemplos resueltos
Excelente documentación y explicación. Me alegra porque coincide con mi propia introspección
Veo la “inteligencia como comprimir información en una representación irreducible”
https://en.wikipedia.org/wiki/Kolmogorov_complexity
https://en.wikipedia.org/wiki/Solomonoff%27s_theory_of_induc...
https://en.wikipedia.org/wiki/Minimum_description_length
Parece estar relacionado con estos conceptos, así que pienso profundizar más
https://en.wikipedia.org/wiki/Wigner%27s_classification
Si ARC-AGI es un benchmark que prueba la capacidad de inferir reglas abstractas a partir de ejemplos mínimos y generalizar, entonces en última instancia está definiendo la inteligencia como la capacidad de comprimir información en un conjunto de reglas
En ese caso, tiene sentido decir que la compresión hace ese trabajo
Me pregunto si alguna vez intentaste resolver problemas de ARC-AGI directamente
Los problemas son bastante sutiles y ponen a prueba una amplia gama de conceptos abstractos
Como referencia, o1-preview obtuvo 21% en la evaluación pública, y el enfoque del artículo original alcanza 34%
Un paper de Schmidhuber algo relacionado: https://arxiv.org/abs/0812.4360
Si la frase es “procesar cada rompecabezas en una RTX 4070 durante unos 20 minutos”, eso parece significar que el desafío de 100 problemas tomaría 33.3 horas
Eso supera el objetivo del desafío, que es 12 horas, pero el enfoque en sí es bastante genial
Esto parece casi un enfoque estándar de deep learning bayesiano, salvo por el hecho de que diseñaron la estructura con mucho cuidado