FunSearch (abreviación de búsqueda en el espacio de funciones) es un método de inteligencia artificial desarrollado por Google DeepMind para descubrir programas informáticos que resuelven problemas matemáticos y algorítmicos. Combina un gran modelo de lenguaje con un evaluador automatizado y un procedimiento de búsqueda evolutiva, generando programas candidatos, puntuándolos y utilizando programas de alto rendimiento para producir nuevos candidatos. El sistema se anunció en 2023, con un artículo publicado en la revista Nature, y se ha aplicado a problemas de combinatoria extremal y empaquetado en contenedores en línea.
FunSearch representa un cambio en la forma en que se utilizan los grandes modelos de lenguaje para el descubrimiento. En lugar de generar respuestas directamente, plantea un problema como una búsqueda sobre programas informáticos, permitiendo que el modelo proponga código que luego se prueba rigurosamente. Este enfoque aprovecha las capacidades generativas de modelos como los utilizados en Generative AI al tiempo que garantiza que los resultados sean verificables y, a menudo, interpretables por los investigadores.
Método
FunSearch opera generando y evaluando iterativamente programas candidatos. El usuario proporciona una especificación del problema, una función de evaluación y un esqueleto de programa inicial. En cada paso, el sistema muestrea programas existentes de una base de datos, favoreciendo aquellos con puntuaciones más altas, y construye una indicación para un gran modelo de lenguaje preentrenado. El modelo genera un programa modificado, que luego se ejecuta y puntúa mediante el evaluador. Los programas válidos se añaden de nuevo a la base de datos, permitiendo que la búsqueda se base en éxitos previos.
La búsqueda utiliza un método evolutivo basado en islas para mantener la diversidad entre los programas candidatos, reduciendo el riesgo de converger a óptimos locales. Una ventaja clave, como se señala en el artículo original, es que FunSearch produce programas que pueden ser inspeccionados, simplificados e interpretados por los investigadores, en lugar de proporcionar solo una respuesta numérica final o una gran lista de objetos.
Formulación algorítmica
FunSearch puede describirse como una búsqueda sobre un espacio de fragmentos de programa, típicamente funciones incrustadas en un esqueleto fijo. Sea \(\mathcal{F}\) el espacio de funciones candidatas y \(S: \mathcal{F} \to \mathbb{R}\) una puntuación de evaluador obtenida ejecutando un solucionador fijo que llama a la función candidata. Dada una función inicial \(f_0\), FunSearch mantiene una base de datos \(D\) de funciones evaluadas y válidas. Repetidamente muestrea funciones de alta puntuación de \(D\), las utiliza para construir indicaciones para un gran modelo de lenguaje y pide al modelo que genere una nueva función candidata \(f'\). La nueva función se ejecuta dentro del esqueleto específico del problema y se puntúa. Si es válida, se añade a \(D\), permitiendo que indicaciones posteriores se basen en candidatos más fuertes.
El objetivo idealizado es encontrar una función candidata con una alta puntuación de evaluador, \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\), aunque en la práctica FunSearch devuelve la mejor función válida descubierta durante la búsqueda. La implementación original utiliza un proceso evolutivo basado en islas para preservar la diversidad mientras favorece programas con puntuaciones más altas.
Aplicaciones
Problema del conjunto de caps
FunSearch se demostró por primera vez en el problema del conjunto de caps, un problema de combinatoria aditiva sobre el mayor subconjunto posible de \(\mathbb{Z}_3^n\) sin tres puntos en línea. En dimensión 8, FunSearch encontró un conjunto de caps de tamaño 512, mejorando construcciones previamente conocidas. El artículo también reportó cotas inferiores mejoradas para la capacidad del conjunto de caps mediante el descubrimiento de construcciones relacionadas con conjuntos admisibles. Google DeepMind describió el resultado como un ejemplo de uso de grandes modelos de lenguaje para generar conocimiento nuevo y verificable en matemáticas. Un artículo de noticias de Nature reportó que el sistema mejoró los esfuerzos humanos para un problema de combinatoria relacionado con el juego de cartas Set.
Empaquetado en contenedores en línea
FunSearch también se aplicó al problema de empaquetado en contenedores en línea, donde los artículos deben asignarse a contenedores a medida que llegan. En este contexto, FunSearch evolucionó heurísticas programáticas que deciden qué contenedor debe recibir un nuevo artículo. El artículo original reportó que las heurísticas descubiertas superaron las líneas base comunes de mejor ajuste y primer ajuste en datos simulados y en conjuntos de referencia de la OR-Library.
Software
Google DeepMind publicó el software FunSearch en un repositorio público de GitHub, permitiendo a los investigadores reproducir los resultados y aplicar el método a otros problemas. El lanzamiento incluye el código para la búsqueda evolutiva, la interfaz del evaluador y ejemplos para los problemas del conjunto de caps y del empaquetado en contenedores. Esta disponibilidad abierta apoya una mayor experimentación en el campo de Machine learning y Artificial intelligence.
Importancia
FunSearch es notable por su integración de grandes modelos de lenguaje con computación evolutiva, una dirección que ha ganado atención en el campo más amplio de Deep learning. Al producir programas interpretables, ofrece un camino hacia sistemas de IA que no solo resuelven problemas, sino que también proporcionan ideas que los humanos pueden entender y sobre las que pueden construir. El método se ha discutido en el contexto de los esfuerzos más amplios de Google DeepMind para aplicar la IA al descubrimiento científico, junto con otras iniciativas en Generative AI.
Si bien FunSearch ha mostrado promesa en tareas matemáticas y algorítmicas específicas, su aplicabilidad general sigue siendo un área de investigación activa. La dependencia de un modelo de lenguaje preentrenado y la necesidad de un evaluador bien definido son restricciones que pueden limitar su uso en otros dominios. No obstante, el enfoque ha inspirado más trabajo sobre el uso de modelos de lenguaje para la síntesis y optimización de programas, contribuyendo al panorama en evolución de la investigación en IA.