Google continues to push the boundaries in AI development through divisions like DeepMind, which is dedicated to creating innovative AI solutions. Recently, DeepMind’s large language model (LLM) achieved a noteworthy feat by cracking a challenging, nearly impossible mathematical problem.
The breakthrough comes in the form of a technique based on large language models (LLMs), demonstrating that artificial intelligence can assist mathematicians in generating novel solutions.
The AI system, named FunSearch, showcased its capabilities by making advancements in solving Set-inspired problems in combinatorics—a mathematical field focused on understanding the possible arrangements of sets containing a finite number of objects.
According to its creators, the method, outlined in a Nature publication on December 14, has the potential for broader applications across various mathematical and computer science inquiries.
What is FunSearch?
FunSearch operates as a mathematical chatbot, utilising a specially trained large language model (LLM) to formulate requests autonomously.
These requests task the LLM with crafting concise computer programs designed to generate solutions for specific mathematical problems. Following this, the system swiftly evaluates whether the developed solutions surpass existing ones. In cases where improvements are needed, constructive feedback is provided to the LLM, enhancing its performance in subsequent iterations.
Describing the LLM’s role, DeepMind computer scientist Bernardino Romera-Paredes refers to it as a “creativity engine.” He notes that not every program generated by the LLM proves helpful; some are erroneous to the extent that they cannot execute. However, a filtering mechanism efficiently discards the incorrect programs, allowing the system to focus on testing and refining the output of the accurate ones.
FunSearch underwent testing on the ‘cap set problem’ and the ‘bin packing’ problem.
What is the Cap Set Problem?
In exploring the cap set problem, a longstanding and challenging mathematical puzzle that has captivated researchers across diverse fields, renowned mathematician Terence Tao expressed it as his favourite open question.
The essence of the problem lies in the quest to identify the most extensive set of points, referred to as a cap set, within a high-dimensional grid where the unique condition is that no trio of points can align on a single line.
This particular problem assumes importance as it serves as a model for other complexities in extremal combinatorics—a field focused on understanding the potential size variations in collections of numbers, graphs, or similar entities.
Notably, conventional brute-force computing methods prove unfeasible due to the sheer magnitude of possibilities to consider, surpassing even the astronomical count of atoms in the universe.
How did FunSearch solve the problem?
In a collaborative effort with Jordan Ellenberg, a distinguished professor of mathematics at the University of Wisconsin–Madison and a notable contributor to the cap set problem, FunSearch emerged as a key player.
This innovative approach generated solutions in the form of programs that, in specific scenarios, unveiled the most extensive cap sets on record. Notably, this achievement marks the most significant expansion in the size of cap sets witnessed in the past two decades. Furthermore, FunSearch showcased its prowess by surpassing the capabilities of state-of-the-art computational solvers.
What is the ‘Bin Packing’ Problem?
Picture this: different-sized items need to be neatly stowed away, but the catch is that you have a limited number of containers, each with its size limit. The mission? To cleverly arrange these items in a way that uses the least number of containers possible.
This seemingly simple problem has profound implications, impacting tasks from loading shipping containers to managing computing jobs in data centres to cut expenses.
It’s a real-world challenge that mathematicians and tech experts are delving into, aiming to find intelligent solutions for more efficient packing and resource allocation. The bin packing problem, at its core, is about doing more with less, and it’s capturing attention across diverse industries for its potential to streamline operations and reduce costs.
How did FunSearch Solve it?
Regarding the online bin-packing problem, the go-to solutions often involve algorithmic rules of thumb based on human insights and experience. However, tailoring these rules for each unique situation, considering variables like item sizes, timing, and container capacity, poses a considerable challenge.
FunSearch adopted an innovative approach that addressed online bin packing with remarkable ease. The automated program it generated, fine-tuned to the specifics of the data, outperformed established heuristics. This translated to using fewer bins to pack the same number of items, a noteworthy achievement in combinatorial problem-solving.
While other AI approaches, like neural networks and reinforcement learning, have proven effective in tackling challenging problems like online bin packing, they often demand substantial resources for deployment.
FunSearch distinguishes itself by producing code that is not only effective but also easily inspectable and deployable. This means its solutions could seamlessly integrate into various real-world industrial systems, offering swift and tangible benefits.
Why can FunSearch change the game?
FunSearch, an innovative approach to mathematical problem-solving, goes beyond traditional computer search techniques by generating programs that provide solutions and detail the process of reaching them.
Unlike black-box methods, FunSearch’s “show-your-working” approach aligns with scientific practices, enabling researchers to comprehend and learn from the generated programs. The preference for concise programs with low Kolmogorov complexity allows FunSearch to tackle large-scale problems effectively.
Notably, the interpretability of FunSearch’s programs offers actionable insights, fostering a collaborative relationship between humans and the algorithm. Mathematician Jordan Ellenberg emphasises that FunSearch’s solutions are conceptually richer than mere numerical lists, providing a valuable mechanism for developing strategic approaches to complex problems.
Comments 1