FunSearch: nuevos descubrimientos en matemáticas y ciencias usando LLM

 (deepmind.google)
1 puntos por GN⁺ 2023-12-15 | 1 comentarios | Compartir por WhatsApp
  • FunSearch de Google DeepMind combina un LLM preentrenado con un evaluador automático para explorar nuevas soluciones verificables en problemas de matemáticas y ciencias de la computación en forma de código
  • El LLM crea nuevos programas, el evaluador automático les asigna una puntuación, y luego los programas con mejores resultados vuelven al conjunto en una iteración evolutiva que mejora las soluciones
  • En el cap set problem, encontró los cap sets más grandes descubiertos hasta ahora en algunas configuraciones, y mostró rendimiento incluso en escalas difíciles de manejar para los solucionadores computacionales de vanguardia existentes
  • El mismo enfoque también se aplicó a online bin packing, donde programas ajustados a las características de los datos colocaron la misma cantidad de ítems en menos bins que las heurísticas existentes
  • Como el resultado son programas cortos que las personas pueden leer, los investigadores pueden revisar la estructura de la solución y usarla en una colaboración humano-IA para mejorar la formulación del problema

La idea básica de FunSearch

  • FunSearch explora funciones escritas como código de computadora para encontrar nuevas soluciones en matemáticas y ciencias de la computación
  • Su nombre proviene de que busca funciones (functions)
  • Como los LLM pueden generar información incorrecta, FunSearch combina al LLM, que propone ideas creativas, con un evaluador automático para filtrar las ideas erróneas
  • Corresponde al primer caso en que un LLM produjo nuevos descubrimientos en problemas científicos y matemáticos abiertos y difíciles

Estructura de iteración evolutiva

  • Primero, el usuario escribe la descripción del problema en forma de código
    • Incluye un procedimiento para evaluar el programa
    • También se prepara un programa semilla para inicializar el conjunto de programas
  • En cada iteración, una parte del conjunto actual de programas se entrega al LLM
    • El LLM genera nuevos programas a partir de los programas existentes
    • Los nuevos programas se ejecutan y evalúan automáticamente
    • Los programas con alta puntuación se agregan de nuevo a la base de datos de programas
  • El usuario puede recuperar en cualquier momento el programa con la mejor puntuación encontrado hasta ese momento
  • FunSearch utilizó Google PaLM 2, pero también es compatible con otros LLM entrenados con código
  • La estructura de búsqueda también se reforzó para enfrentar problemas combinatorios difíciles
    • Parte de conocimiento general sobre el problema y se concentra en las ideas clave necesarias para nuevos descubrimientos
    • Aumenta la diversidad de ideas para evitar el estancamiento
    • Ejecuta el proceso evolutivo en paralelo para mejorar la eficiencia

Resultados en el Cap set problem

  • El primer objetivo de aplicación fue el cap set problem, que durante décadas ha complicado a matemáticos de varias áreas de investigación
  • Este problema consiste en encontrar el tamaño máximo de un conjunto de puntos en una retícula de alta dimensión donde no haya tres puntos sobre una misma línea recta; es decir, un cap set
  • También funciona como modelo para otros problemas de combinatoria extremal (extremal combinatorics)
  • Como el número de casos posibles crece rápidamente hasta superar la cantidad de átomos del universo, el cálculo por fuerza bruta no funciona
  • FunSearch generó soluciones en forma de programas y encontró, en algunas configuraciones, los cap sets más grandes descubiertos hasta ahora
  • Este resultado representa el mayor aumento en el tamaño de cap set de los últimos 20 años, y mostró mejor rendimiento incluso en regiones donde la escala del problema supera la capacidad actual de los solucionadores computacionales de vanguardia
  • Demostró que puede superar resultados existentes en problemas combinatorios donde es difícil construir intuición, y podría extenderse en el futuro a problemas teóricos similares en combinatoria y a áreas como la teoría de las comunicaciones

Programas cortos que las personas pueden interpretar

  • FunSearch no es una caja negra que solo entrega una lista de respuestas, sino que genera programas que muestran cómo está construida la solución
  • Esto también conecta con la forma general de la ciencia de explicar nuevos descubrimientos o fenómenos a través del proceso que los genera
  • FunSearch favorece soluciones expresadas como programas compactos con baja Kolmogorov complexity
    • La complejidad de Kolmogórov es la longitud del programa de computadora más corto que produce la solución
    • Los programas cortos pueden describir objetos muy grandes, lo que ayuda a escalar a problemas masivos tipo búsqueda de aguja en un pajar
    • La salida del programa es fácil de entender para los investigadores
  • En parte del código de salida con puntuaciones altas se observaron simetrías interesantes, y a partir de ellas se refinó la formulación del problema para obtener mejores soluciones
  • Jordan Ellenberg dijo que FunSearch ofrece “un mecanismo completamente nuevo para desarrollar estrategias de ataque”, y que las soluciones generadas son conceptualmente mucho más ricas que una lista de números

Aplicación a Online bin packing

  • FunSearch también se aplicó a bin packing, un problema práctico de ciencias de la computación
  • Bin packing consiste en colocar ítems de distintos tamaños en la menor cantidad posible de bins
  • Algunos ejemplos reales incluyen la carga de contenedores y la asignación de trabajos de cómputo en centros de datos para reducir costos
  • El online bin packing suele abordarse con heurísticas basadas en la experiencia humana
    • Puede ser difícil encontrar un conjunto de reglas para cada situación específica con distintos tamaños, tiempos y capacidades
  • Aunque es un problema muy diferente del cap set problem, FunSearch se configuró con facilidad y creó programas ajustados automáticamente a las características de los datos
  • Los programas generados colocaron la misma cantidad de ítems en menos bins que las heurísticas existentes
  • Otros enfoques de IA, como redes neuronales o aprendizaje por refuerzo, también pueden ser eficaces para problemas combinatorios difíciles, pero pueden requerir recursos considerables para desplegarse
  • Como FunSearch produce código fácil de inspeccionar y desplegar, puede generar soluciones con una forma apta para incorporarse en distintos sistemas industriales reales

Actualización y expansión en 2024

  • Un reporte en arXiv publicado en diciembre de 2024 mostró que el enfoque de FunSearch puede usarse para amplificar el rendimiento humano en programación competitiva combinatoria
  • Las competencias de programación tradicionales como Codeforces exigen soluciones completas a problemas clásicos de algoritmos bajo restricciones de tiempo y memoria
  • Las competencias combinatorias tratan problemas complejos en los que no se busca una única respuesta correcta, sino la mejor solución aproximada posible
  • Este enfoque puede producir soluciones mejores que las encontradas por participantes ubicados en los percentiles más altos
  • Utiliza una estructura de colaboración en la que el programador humano escribe el backbone del código de la solución y el LLM hace evolucionar creativamente las funciones que lo controlan
  • A medida que mejoraron los LLM generales, dejó de ser necesario un modelo especializado en código, y puede usarse con base en Gemini 1.5 Flash
  • Además de la programación competitiva, FunSearch también se usó para encontrar mejores formas de optimizar funciones dentro de marcos de optimización bayesiana

La dirección de los descubrimientos basados en LLM

  • FunSearch muestra que, si se incorporan mecanismos para evitar las alucinaciones de los LLM, estos pueden usarse no solo para nuevos descubrimientos matemáticos sino también para generar soluciones potenciales a problemas reales importantes
  • En problemas antiguos o nuevos de la ciencia y la industria, podría volverse común generar algoritmos eficaces y personalizados con enfoques basados en LLM
  • FunSearch puede mejorar junto con el avance general de los LLM, y está previsto que amplíe sus capacidades hacia diversos problemas científicos y de ingeniería

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-12-15
Opiniones de Hacker News

  • Me pregunto qué tan necesario es un LLM aquí.
    A simple vista, parece que el rol del LLM es generar algo plausible, como una función de Python que siga una firma de tipos dada.
    Pero incluso sin un LLM, debería ser posible crear funciones de Python aleatorias y correctas que satisfagan una firma de tipos dada. Sería como el ejercicio de [1], pero dirigido a un lenguaje mucho más complejo, y quizá un lenguaje restringido sería más fácil de usar. Me pregunto si también sería posible algo como PushGP [2].
    Las preguntas son: (1) cuál es el valor agregado del LLM aquí, si reduce de forma significativa la cantidad de evaluaciones necesarias para converger y, si es así, cómo; (2) si otras técnicas de programación genética son menos competitivas en el mismo problema y producen soluciones con menor aptitud; y (3) si, en caso de que una programación genética más tradicional alcance una aptitud similar, hay una diferencia en el costo computacional al incluir también el costo de entrenar el LLM.
    [1] http://www.davidmontana.net/papers/stgp.pdf
    [2] https://faculty.hampshire.edu/lspector/push.html

    • El espacio de estados de los programas ejecutables es muchísimo más grande que el de los programas útiles.
      No alcanza con monos y máquinas de escribir; la razón para usar Palm2 aquí es que los candidatos no deben ser aleatorios, sino plausibles. La idea es no perder tiempo con programas sin sentido.
      Además, los algoritmos genéticos basados en la generación de programas aleatorios tienen un problema enorme de arranque en frío. Si la aptitud de todos los candidatos es 0, al principio —y probablemente hasta el final— es muy posible que no haya progreso.
    • La función descubierta está aquí: https://github.com/google-deepmind/funsearch/blob/main/cap_s...
      No estoy muy familiarizado con los algoritmos genéticos, pero no me parece que algo de este nivel sea imposible de encontrar para un algoritmo genético. Aunque me sorprendería si alguien ya lo hubiera intentado mucho en la práctica.
      Por otro lado, como se ve en el apéndice A.2 del paper, un enfoque genético sin LLM probablemente requeriría mucho más diseño manual que el enfoque con LLM.
    • Los algoritmos genéticos, incluso con restricciones, terminan creando muchos programas sin sentido. Con suficiente esfuerzo, probablemente se puede lograr que la mayoría sean sintácticamente correctos, pero nada más.
      La diferencia que aporta el LLM aquí es que restringe el espacio de mutaciones posibles, en general, a programas semánticamente plausibles.
      Sobre el punto 3: un LLM entrenado es útil para muchísimos propósitos, así que si se amortiza el costo de entrenarlo desde cero, no es tan grande. Puede haber un costo adicional de ajuste fino para adaptarlo al framework FunSearch, pero el costo del ajuste fino es bastante pequeño. Usarlo en este framework probablemente sea ventajoso frente a usar solo programación genética.
    • La síntesis inductiva de programas estuvo prácticamente estancada durante décadas porque el espacio de búsqueda era demasiado grande. Era difícil ir más allá de programas muy triviales.
      Los LLM reducen mucho el espacio de búsqueda y, aunque por supuesto muchas veces lo reducen de forma incorrecta, después se puede aplicar síntesis inductiva de programas para ajustar y probar. Sin LLM, hasta donde sé, este enfoque hoy es imposible. Incluso en casos triviales, terminarías probando miles de millones de programas completamente absurdos.
    • Pensaba que el descenso de gradiente estocástico y los LLM convergen muchísimo más rápido que la programación genética. Sin duda, mucho más rápido que una búsqueda aleatoria.

  • El contexto importante es que este descubrimiento mostró que cierto número de combinatoria, que el año pasado se sabía que estaba en el rango de 2.218~2.756, ahora está entre 2.2202~2.756.
    La mejora se logró encontrando secuencias específicas con ciertas propiedades especiales, más que mediante una prueba matemática centrada en la lógica. Eso no significa que no sea rigurosa.
    Es una forma interesante y probablemente útil de generar ejemplos y, en la práctica, se parece más a un algoritmo genético con LLM incluido.

  • Comentario de Subbarao sobre el “juego contra sí mismo”: https://twitter.com/rao2z/status/1728121216479949048
    Según el texto, FunSearch usa un método evolutivo impulsado por un LLM para promover y desarrollar ideas con puntajes altos. Estas ideas tienen forma de programas de computadora, por lo que pueden ejecutarse y evaluarse automáticamente.
    El usuario escribe la descripción del problema en forma de código. Esta descripción incluye un procedimiento para evaluar los programas y un programa semilla para inicializar el conjunto de programas.
    En cada iteración, FunSearch selecciona algunos programas del conjunto actual, el LLM los expande de forma creativa para crear nuevos programas, y los nuevos programas se evalúan automáticamente. Los mejores se agregan de nuevo al conjunto existente, creando un bucle de automejora.
    En búsquedas web, se usa pplx.ai y phind.com de manera similar como evaluadores. Se hace una pregunta, se observa qué referencias y enlaces web traen, y luego se refina la pregunta o se hacen preguntas de seguimiento para que extraigan material más profundo o distinto. Funciona mejor para encontrar joyas ocultas que revisar reddit o Google.
    También hay mucho contenido excelente en Tech Twitter, así que, ahora que Grok está disponible para todos, espero que se use para investigación.

  • https://twitter.com/gfodor/status/1735348301812383906
    Hay quien dice: “Si DeepMind demostró de forma concluyente que las redes neuronales pueden generar conocimiento verdaderamente nuevo, es el descubrimiento más importante desde el fuego”.
    Si eso es realmente así, me pregunto por qué no todo el mundo está hablando de esto. Es impresionante que lo hayan logrado con PaLM 2, menos avanzado que GPT-4 o Gemini. Parece enorme pensar en lo que podrán hacer las próximas generaciones de modelos si aprovechan este tipo de método.

    • Aquí el trabajo difícil lo está haciendo el algoritmo evolutivo.
      El LLM básicamente reemplaza al operador de mutación aleatoria y recibe una petición del tipo “sugiere una modificación razonable para estas 20 líneas de Python”. Atribuirle el mérito de la generación de conocimiento a la red neuronal se siente como una evaluación generosa.
      Además, más allá de requerir una estructura donde “crear sea difícil y evaluar sea fácil”, depende mucho de la naturaleza del problema. La parte que se quiere evolucionar tiene que poder descomponerse en una función de Python muy corta.
    • Dije “¡wow!” en voz alta.
      Que un LLM pueda descubrir una nueva solución en geometría de alta dimensión, donde no había avances desde hace 20 años, va mucho más allá de simplemente pegar de forma convincente fragmentos plagiados de datos de entrenamiento.
      Sugiere que hay una profundidad oculta en las capacidades de los LLM, siempre que sepamos cómo hacer los prompts y evaluar correctamente.
      Es un resultado que rompió mis expectativas por completo. Uno no sabe qué descubrimiento puede estar escondido detrás del siguiente prompt y una semilla aleatoria.
    • Las redes neuronales pueden generar “conocimiento nuevo” desde hace mucho tiempo.
      Lo mismo aplica a los LLM: https://www.nature.com/articles/s41587-022-01618-2
    • Según el paper, actualmente FunSearch funciona mejor en problemas con las siguientes características:
      a) existe un evaluador eficiente, b) hay retroalimentación de puntaje rica que cuantifica el grado de mejora, es decir, no es una señal binaria, c) se puede proporcionar un esqueleto con una parte aislada para evolucionar.
      Por ejemplo, la generación de demostraciones de teoremas queda fuera de este alcance, porque no está claro cómo proporcionar una señal de puntaje suficientemente rica.
    • Este ejemplo se siente relativamente limitado a encontrar nuevos algoritmos o funciones.
      Es un gran logro, pero comparado con el descubrimiento del fuego, o con muchísimas cosas intermedias como la electricidad, no parece estar al mismo nivel.

  • En resumen, dado un template/esqueleto de programa y una función de aptitud, generan una población de programas con un LLM y usan un prompt que crea un programa nuevo a partir de otras k versiones; encontraron que k=2 funciona bien. Es algo biológico. Luego ejecutan los programas sobre entradas y los califican con la función de aptitud, usando un modelo de islas para la evolución.
    En principio, el prompt debe sentirse más o menos así:
    def foo_v1(a, b): ...
    def foo_v2(a, b): ...
    # Usa foo_v1 y foo_v2 para crear una nueva función. Solo puedes cambiar lo que está dentro de llaves dobles, como {{ THIS }}
    def foo(a, b): return a + {{}}
    Si solo hicieron alrededor de 1e6 llamadas al LLM para obtener nuevos resultados, es un número sorprendentemente bajo. También dicen que la evaluación/calificación tarda unos minutos.
    Aquí vale la pena pensar en el compromiso entre profundidad y amplitud. Está relacionado con la latencia y el throughput al calificar programas individuales y poblaciones. ¿Qué pasaría si se aplicara memoización a todos los programas? Me pregunto si, manteniendo la función de pérdida en varias dimensiones, con una dimensión por entrada o por bucket de entradas, primero se podrían encontrar poblaciones de programas que funcionen bien en regiones distintas y combinarlas después.
    También me pregunto si ya tenían conocimiento previo sobre qué tan raros son los cap sets. Me da curiosidad si antes hubo intentos computacionales sin resultados, pero en cualquier caso es genial.

  • Parafraseando el post de Twitter / X: de aquí en adelante, esto solo va a mejorar.
    Es decir, las capacidades de la IA aumentan de forma monótona, y lo han hecho durante décadas; en este caso, además, la capacidad se mejora a sí misma de forma recursiva. Ya estoy viendo mejoras personales de productividad al programar de alrededor de 20 a 30% gracias al autocompletado con IA, la refactorización asistida por IA y los diffs de code review generados automáticamente por IA en los comentarios.
    Se siente como si la IA hubiera entrado en una etapa parecida a Intel en los 90. Si querías que tu código corriera 2 veces más rápido, solo tenías que esperar la siguiente revisión de los CPU de Intel. Ahora los modelos de IA cumplen ese papel. Si conectas partes de flujos de negocio, como programación, soporte al cliente o clasificación de bugs, a sistemas con LLM, la “mejora” del sistema pasa a ser casi solo cambiar el nombre del modelo.
    Después de la integración inicial, con un esfuerzo mínimo, podemos esperar que durante los próximos años “todo mejore mágicamente un poco” de forma continua.

    • A mi parecer, nada de eso aparece en el post del blog ni en el paper enlazado.
      En particular, no compararon resultados con y sin LLM. Según lo entiendo, este paper muestra resultados de programación genética donde se usa un LLM para generar funciones kernel en Python que probablemente respetan una firma de tipo dada. Para esta tarea no es estrictamente necesario un LLM.
      Por lo tanto, sigue siendo una pregunta abierta si aquí el LLM está haciendo algo especialmente particular.

  • Uno de los problemas que abordaron fue el problema del cap set.
    https://en.m.wikipedia.org/wiki/Cap_set
    Este problema consiste en encontrar el conjunto más grande de puntos en una grilla de alta dimensión donde no haya tres puntos en una misma línea; es decir, un cap set. Es importante porque funciona como modelo para otros problemas de combinatoria extremal. La combinatoria extremal estudia qué tan grandes o pequeñas pueden ser colecciones de números, grafos u otros objetos. En este problema, el cálculo por fuerza bruta no funciona, porque la cantidad de posibilidades a considerar supera rápidamente el número de átomos del universo.
    FunSearch generó soluciones en forma de programas y, en algunas configuraciones, encontró los cap sets más grandes descubiertos hasta ahora. Esto representa el mayor aumento en el tamaño de cap sets en los últimos 20 años. Además, como el problema crece a una escala muy superior a la capacidad de los solvers computacionales de estado del arte actuales, FunSearch superó a esos solvers.

  • Me pregunto cómo integrar el razonamiento simbólico con los LLM, o si siquiera es posible.

    • Eso es precisamente lo que estamos haciendo. No solo es posible; creemos que es necesario para aplicaciones que vayan más allá de la generación por prueba y error.
    • También parece tener cierto paralelo con las ideas neuro-simbólicas que explora Lab V2 de ASU.
    • LEAN

  • El reciente paper de FunSearch de DeepMind destacó que usó modelos de lenguaje grandes preentrenados para generar mejoras de código.
    Curiosamente, aunque el LLM principal era Codey, basado en la familia de modelos PaLM2, en el material complementario también se menciona StarCoder, un LLM de código abierto.
    Sin embargo, el repositorio de GitHub de FunSearch no incluye esta implementación de LLM. Por ejemplo, sampler.py contiene código como el siguiente:

    class LLM:  
"""Language model that predicts continuation of provided source code."""

def __init__(self, samples_per_prompt: int) -> None:  
self._samples_per_prompt = samples_per_prompt

def _draw_sample(self, prompt: str) -> str:  
"""Returns a predicted continuation of `prompt`."""  
raise NotImplementedError('Must provide a language model.')

    Este código muestra que se necesita una implementación externa de LLM. Si usaron StarCoder con éxito, sorprende que no haya una guía de integración ni una implementación básica para ese modelo o para algún LLM de código abierto similar. Si hubieran incluido algo así, la reproducibilidad y la accesibilidad de la investigación habrían mejorado mucho.

  • Independientemente de si esto constituye nuevo conocimiento verificable, es un caso de estudio interesante al pensar en el problema de restringir el acceso a la IA mediante el tamaño del modelo u otros mecanismos regulatorios.
    Esas restricciones dan una ventaja injusta a las empresas que pueden descubrir nuevo conocimiento o leyes naturales y monetizarlos sin compartirlos.