DeepMind paper published in Nature: A problem that has troubled mathematicians for decades, a large model finds a new solution

As the top technology in the field of artificial intelligence this year, large language models (LLM) are good at combining concepts and helping people solve problems through reading, understanding, writing and coding. But can they discover entirely new knowledge?

Given that LLM has been shown to suffer from the "hallucination" problem, that is, generating information that is inconsistent with the facts, utilizing LLM to make verifiably correct discoveries is a challenging task

Now, a research team from Google DeepMind has proposed a new way to search for solutions to mathematics and computer science problems - FunSearch. FunSearch works by pairing a pre-trained LLM (which provides creative solutions in the form of computer code) with an automatic "evaluator" to prevent hallucinations and wrong ideas. By iterating back and forth between these two components, the initial solution evolves into "new knowledge." A related paper was published in the journal Nature.

Paper address: https://www.nature.com/articles/s41586-023-06924-6

This work is the first to use LLM to make new discoveries on challenging open problems in science or mathematics.

FunSearch unearths new solutions to the cap set problem, an enduring unsolved problem in mathematics. In addition, DeepMind also uses this solution to explore more efficient algorithms to solve the "boxing" problem, which is widely used in many fields, such as improving the efficiency of data centers. Demonstrating the practical application value of FunSearch

The research team believes that FunSearch will become a particularly powerful scientific tool because the programs it outputs reveal how its solutions are constructed, not just is what the solution is. This will stimulate further insights from scientists, creating a virtuous cycle of scientific improvement and discovery.

Drive discovery through the evolution of language models

FunSearch uses an evolutionary algorithm powered by LLM to encourage and drive the highest scoring ideas and ideas. These ideas and ideas can be expressed as computer programs so that they can be automatically run and evaluated

First, the user needs to write the description of the problem in the form of code. This description should include the process of evaluating the program and the seed program used to initialize the program pool

FunSearch is an iterative process. In each iteration, the system selects some programs from the current program pool and passes them to LLM. LLM builds on this foundation and generates new programs, which are then automatically evaluated. The best programs will be added back to the existing library, creating a cycle of self-improvement. FunSearch uses Google's PaLM 2, but is also compatible with other code-trained methods

LLM will retrieve the generated best results from the program database best program and asked to generate a better program.

As we all know, exploring new mathematical knowledge and algorithms in various fields is a very challenging task, which is often beyond the capabilities of the current most advanced artificial intelligence systems. To make FunSearch up to the task, the research team introduced several key components. FunSearch does not start from scratch, but starts from common sense of the problem, and focuses on finding the most critical ideas to achieve new discoveries through an evolutionary process

In addition, FunSearch’s evolutionary process uses a Strategies to increase diversity of ideas to avoid stagnation. Finally, to increase system efficiency, the evolution process is run in parallel.

Opening up new horizons in the field of mathematics

DeepMind said that the first thing they have to solve is the Cap set problem, which is an open problem. It has puzzled mathematicians in multiple research fields for a decade. The famous mathematician Terence Tao once described it as his favorite open problem. DeepMind chose to work with Jordan Ellenberg, a professor of mathematics at the University of Wisconsin-Madison who was an important breakthrough in the Cap set problem.

An important problem is to find the largest set of points (called a "cap set") in a high-dimensional grid such that no three points in it are collinear. The importance of this problem is that it can serve as a model for other problems in extremal combinatorics. Extremal combinatorics studies the minimum or maximum size that collections can have, which can be numbers, graphics, or other objects. Brute force solutions cannot solve this problem - the number of possibilities to consider will soon exceed the number of atoms in the universe

FunSearch Procedurally generated solutions found in some cases The largest cap set in history. This represents the largest increase in cap set size in the past 20 years. Furthermore, FunSearch outperforms state-of-the-art computational solvers because the scale of the problem far exceeds their current capabilities.

The interactive chart shows the evolution from the seed program (top) to the new high-scoring function (bottom). Each circle represents a program and its size is proportional to the score assigned to it. Only the superiors of the bottom program are shown in the figure. The corresponding function generated by FunSearch for each node is shown on the right.

These results show that FunSearch technology can allow humans to go beyond established results on difficult combinatorial problems where it is difficult to build intuition. DeepMind expects this approach to play a role in new discoveries about similar theoretical problems in combinatorics and, in the future, to bring new possibilities to fields such as communication theory.

FunSearch prefers concise, human-understandable programs

Although the discovery of new mathematical knowledge is significant in itself, it is different from traditional computer search techniques. In comparison, the FunSearch method also shows other advantages. This is because FunSearch is not a black box that only generates solutions to problems. Instead, it generates programs that describe how those solutions were arrived at. This kind of "show-your-working" is usually how scientists work, explaining new discoveries or phenomena by describing the processes that gave rise to them.

FunSearch prefers to find solutions with lower Kolmogorov complexity that represent highly compact programs. Kolmogorov complexity refers to the length of the shortest computer program required to output a solution. By using short programs, FunSearch can describe very large objects and thus be able to handle very complex problems. Additionally, this also makes it easier for researchers to understand the program output generated by FunSearch. Ellenberg said: "FunSearch provides a completely new mechanism to develop a strike strategy. The solutions generated through FunSearch are conceptually richer than a simple list of numbers. I learned a few things by studying them."

More importantly, this interpretability of the FunSearch program can provide researchers with actionable insights. For example, while using FunSearch, DeepMind noticed intriguing symmetries in the code of some of its high-scoring outputs. This gave DeepMind a new understanding of the problem, which they used to improve the problem that FunSearch was introduced to find a better solution. DeepMind believes that this is an excellent example of human collaboration with FunSearch on many problems in mathematics.

Left: By inspecting the code generated by FunSearch, DeepMind gained more actionable insights (highlighted). Right: The original "acceptable" set constructed using the (shorter) program on the left.

Solving a well-known computational problem

Inspired by the success of the theoretical cap set problem, DeepMind decided to apply FunSearch to computer science An important practical challenge is the bin packing problem to explore its flexibility. The packing problem concerns how to pack items of different sizes into the minimum number of boxes. It is at the heart of many real-world problems, from shipping containers holding items to distributing computing work in data centers, where costs need to be minimized.

Typically, heuristic algorithm rules based on human experience are used to solve online binning problems. However, developing a set of rules for each specific situation (varying in size, time, or capacity) is very challenging. Although very different from the cap set problem, it is very easy to solve this problem using FunSearch. FunSearch provides an automatically customized program that adapts to the data on a case-by-case basis and is able to use fewer bins to hold the same number of items than existing heuristics.

Example of binning using existing heuristics - the Best-fit heuristic (left) and the heuristic discovered by FunSearch (right).

Complex combinatorial problems like online binning can be solved using other artificial intelligence methods, such as neural networks and reinforcement learning. These methods have also proven effective, but may also require significant resources to deploy. On the other hand, FunSearch outputs code that is easy to inspect and deploy, meaning its solutions have the potential to be applied to a variety of real-world industrial systems, quickly bringing benefits.

DeepMind: Using large models to address scientific challenges will become common practice

FunSearch demonstrates the power of these models if LLMs can be prevented from hallucinating Not only can it be used to generate new mathematical discoveries, but it can also be used to reveal potential solutions to important real-world problems.

DeepMind believes that for many problems in science and industry - both long-standing and new - using LLM-driven methods to generate efficient and tailored algorithms will became common practice.

Actually, this is just the beginning. As LLM continues to make progress, FunSearch will continue to improve. DeepMind said they will also work to expand its capabilities to address a variety of pressing scientific and engineering challenges in society.

The above is the detailed content of DeepMind paper published in Nature: A problem that has troubled mathematicians for decades, a large model finds a new solution. For more information, please follow other related articles on the PHP Chinese website!