An Israeli professor's 'Eureqa' moment
Haifa-born Prof. Hod Lipson and his colleagues have created a computer program that generates mathematical formulas which explain various scientific phenomena. In essence, he argues, it can accelerate the process of scientific discoveries.
The beeping of the mobile phone awoke Prof. Hod Lipson in the middle of the night. "We found the equation!" his research student, Michael Schmidt, announced. The equation Schmidt was referring to has been known to every physicist since the 19th century. It describes the Law of Conservation of Energy - not exactly an earthshaking discovery. Nevertheless, as Prof. Lipson laid his head of disheveled hair back on the pillow, he did so with a smile.
A few days earlier, Lipson and his students at Cornell University had carried out a simple mechanical experiment. They attached two pendulums to one another in a way that generated complex patterns of movement. They then connected that oscillating system to a computer program they have been developing these past five years. The program is intended to take data from different systems - in this case, data concerning the movement of the pendulums - and use it to generate mathematical formulas that describe the mechanisms producing the data. To put it more provocatively - which is how Lipson likes to describe it - this computer program is supposed to identify laws of nature.
The experiment with the pendulums was intended to test the program's capabilities with regard to identifying laws already known to scientists. The result was impressive. Within one day - and without being fed any algorithmic knowledge in physics, geometry, kinematics or from any other area of research - the program was able to come up with one of the most famous equations in the field of science: F=ma, the mathematical representation of Newton's Second Law. A few days later, the program, extrapolating from the data, came up with the equations that describe the Law of Conservation of Momentum and the Law of Conservation of Energy.
The program is named Eureqa, after Archimedes' famous bathtub exclamation (meaning: "I have found it!" ) - invoking the moment of euphoria that accompanies great new discoveries or insights. (The "q" replaces the "k" in "Eureka" as an allusion to the word "equation." )
In April 2009, Lipson and Schmidt published their findings in the Science journal. Alongside their paper - entitled "Distilling free-form natural laws from experimental data" - a research team headed by Ross King from the University of Wales published a paper about a similar program called Adam, which focused on biological experiments. The two papers immediately generated intense media buzz. Although automation of the processes of producing, collecting and storing research data is not unusual, this time the researchers purported to automate the distillation of scientific knowledge. The Guardian newspaper's science correspondent was not alone with his dramatic assertion that, "The work marks a turning point in the way science is done."
Lipson and Schmidt were soon deluged with requests from people who wanted to use the program, and they decided to make it available online for free download. At present, Eureqa is being used by more than 20,000 people - scientists and enthusiasts alike - around the world.
I met with Prof. Hod Lipson late last year at the Weizmann Institute of Science in Rehovot, where he was lecturing on Eureqa during his annual visit home. Haifa-born Lipson, 44, has been in the United States since 1998, after obtaining a Ph.D. in engineering and artificial intelligence from the Technion - Israel Institute of Technology. He first went to the U.S. to pursue his postdoctoral studies, but stayed after getting tenure from Cornell. His prolonged residence in the United States has left a distinct impression on his mannerisms and dress code. He radiates serene vitality and quiet self-confidence, along with open friendliness. Lipson is married to Melba Kurman; they have two sons, Lahav, 14, and Eitan, seven.
Lipson presented Eureqa to me as the next big thing in science, asserting that,"Within less than 20 years, programs like Eureqa will be as commonplace as calculators. In fact, you can already see that today. At the moment people don't give machines credit for discoveries or inventions, but that might have to change."
Randomness and rules
So, how does the program work? Eureqa begins by randomly creating thousands of equations - that is, sequences of familiar mathematical building blocks such as the minus and multiplication signs, sine and so on. The content of these formulas is ordered only by the basic syntax of mathematical formulas. For example, two addition signs cannot appear one after the other. Beyond this basic syntax, the sequences generated by the program are entirely random.
Eureqa must deal with a seemingly impossible task: to transform these raw sequences into polished mathematical formulas that describe the experimental system that is feeding it with data. To this end, the program proceeds in a manner that is not especially intuitive: it enters random changes into the first generation of the formulas it has generated. Using the initial equations, the program generates ten million new formulas per second. It then does the same with every new generation of formulas that is created, randomly changing one of the building blocks in each formula.
Despite the randomness, there is one rule which makes it possible for the program to accomplish its task: After each new generation of formulas, Eureqa is required to make choices to save some of the formulas and get rid of others. The more successful a particular formula is in describing and predicting the data accurately, the higher it is ranked, enabling it to pass the "pruning" stage and survive more generations.
At the outset of the process, none of the formulas approaches an accurate description of the data. However, after a few generations of random variations, Eureqa chooses the best fits and filters out the rest (nearly 90 percent ). The formulas that survive pass on their just-slightly-better sequences to the next generation, and the program introduces more random changes into these formulas, too.
After many generations, in the course of which more than 10 billion formulas are generated, the program is supposed to identify the best formula for describing the data which it is being fed by the experimental system. That formula will describe the fixed relations between invariant parameters in the experimental system.
"It's like the monkey who eventually learns to type out a play by Shakespeare after enough trials," Lipson says about the algorithmic operation. "It's surprising that it works. At first all the models are garbage, but they get better and better. It is very nonintuitive, but that is the way evolution produced the living cell."
Indeed, Eureqa is inspired by evolutionary mechanisms. Random mutations in genes occur in nature, some of which generate traits which are fit for the organism's environment and so are passed on.
In the same way, the random changes in the raw mathematical equations bring them closer to the desirable formulas. Eureqa also includes other techniques for generating intergenerational changes in the formulas, such as genetic recombination, a phenomenon familiar in nature from the process of sexual reproduction, whereby initial formulas intermix to create new ones.
In accordance with the source of inspiration, the research tools used by Eureqa are known overall as evolutionary algorithms - specifically, in the version used by Lipson and Schmidt, genetic algorithms. They have been in use since the 1970s, but have been upgraded with more advanced techniques suited to artificial selection. Lipson and Schmidt started to use genetic algorithms in their research project on evolutionary robotics (see box ) and then decided to apply the same techniques in a program that would serve scientific research.
A case of interpretation
Although Eureqa has drawn considerable media and popular attention, the manner in which the program's initial success is presented has drawn criticism from scientists in the field of artificial intelligence and other realms of research. Prof. Naftali Tishby, director of the Interdisciplinary Center for Neural Computation at the Hebrew University of Jerusalem, who also studies learning systems, voices a common criticism of Eureqa.
"To begin with, there is no such thing as learning without prior assumptions," the professor says, referring to the claim that Eureqa is able to come up with a formula like F=ma without any "background knowledge" of physics or other fields. "The researchers assumed the components of the mathematical formulas they were looking for. The program definitely shows nice results, but they need to be looked at in the right proportions. All we have here is the adjustment of data to a mathematical expression of a predetermined type."
According to Tishby, "What the researchers did is a step in a right and impressive direction in itself, but they have not yet gotten close to the true greatness of physics and mathematics, which is finding or creating the basic concepts, such as mass or force, and not only discovering the laws that are appropriate to the data. So, for Lipson to say that he found Newton's Second Law is not a huge accomplishment, because he already possessed the concepts. He was looking for mathematical connections between concepts or parameters which he predefined, with the basic concepts already present in his syntax."
In other words, Tishby concludes, "Only someone who knows Newton's laws will identify Newton's laws by means of this program. What we have here is a bit of over-marketing."
Similarly, Prof. Sarit Kraus, an expert in artificial intelligence from Bar-Ilan University, says Eureqa's results are highly dependent on the initial input the system receives. "The system did not come from nothing," she notes. "You have a list of basic sentences, through which you create a huge search tree, because from every two sentences you can create a new sentence. The genetic algorithm is actually an intelligent search within a space of possible sentences, but instead of working deterministically, it works randomly."
In response, Lipson points out that most scientists are not engaged in discovering new basic concepts, but "'only' try to create new models with a standard mathematical syntax and existing measurements. So to say that because the software did not come up with new concepts it is not really making discoveries, is pretty damming to the scientific community. It reminds me of the scene in 'I, Robot' where a human challenges the robot by asking it, 'Can a robot write a symphony?' And the robot responds: 'Can you?'"
But Lipson also maintains that his program can in fact generate - at least in a preliminary way - concepts that are new in terms of itself. "As we described in several papers, when we gave Eureqa the data from simple mechanical systems (like pendulums and springs), it was able to discover recurring motifs like potential energy or kinetic energy terms. It called them by name, but also encapsulated them and reused them like new letters in an alphabet."
And he adds, "Having a machine analyze the data and reduce it automatically to a handful of fundamentally meaningful equations is not a trivial task. This accomplishment is not incremental; it has never been done before, though many have tried."
Nevertheless, Lipson is not willing to risk a declaration in the spirit of the usual promises that are practically built into media coverage about artificial intelligence: that computers are going to replace scientists. Lipson recognizes that without the scientists and their theories, Eureqa is not of great value.
"We still need a person to decide which information to collect, which basic components to use and what meaning to impart to the equation that has been discovered," he says.
Eureqa did not include definitions for mass or force, so that the equation that described Newton's Second Law was revealed as such only because of the researchers' interpretation. They received a number of trivial variations; the nontriviality was conferred by Newton. From this perspective, Lipson would appear to agree in part with Tishby and Kraus. "Newton's greatness lay exactly in these matters," he notes, "and not only in finding the equation."
Formula for flapping wings
Eureqa may not yet have come up with revolutionary formulas that merit a Nobel, Lipson admits with a smile. Nevertheless, he notes that the program has a worthy list of achievements and several dozen citations in articles that appear in Google Scholar.
Together with other scientists, Lipson will soon publish a paper describing complex models of flapping wing flight which were produced by Eureqa. "Within a few days," he says, "it rediscovered two models that took two renowned scientists (from Harvard and Cornell) a career to develop. Eureqa then went on to create new models that are even simpler and more accurate."
Lipson also notes that one Master's student used Eureqa to model tire-road interaction. That model is simpler and more accurate than the current industry standard, "and this list is only getting longer," he adds.
Many of those making use of Eureqa are applying it for personal or economic rather than scientific needs. For example, to develop automated investments in the capital market, which is a hot field for similar programs.
"On the one hand," says Lipson, "you have scientists from the Weizmann Institute who are taking information from highly precise experiments and creating models at the cutting edge of science. And, on the other hand, some people are taking data about themselves - people who are trying, say, to find the formula that says that whenever you eat dry cereal you don't sleep well."
Interactions between tires and roads, or the statistical connection between breakfast cereal and sleep may not fire the imagination, but when it comes to the near future, Lipson is certain he is paving the way to creating a revolutionary discovery machine.
Programs like this, he explains, will accelerate "our ability to do science and reach new levels of insight in fields where our intellectual capability is simply not good enough. Just like other industries have resisted automation, experts will argue that they will always be needed. Time will tell if they are correct."
Prof. Tishby, who is skeptical about Eureqa, is also certain that later versions of similar programs have a promising future: "Lipson is simply a little ahead of his time," the professor admits. "The discovery of laws is possible, but demands a significant leap beyond what his program is showing us. What's needed is a program than can identify or invent a new concept that generalizes from specific data to a new phenomenon. I believe that this problem will be solved. When that happens, techniques resembling symbolic learning will be able to help in the scientific work some of us are doing, and to some degree also replace elements of that scientific work.
"In the previous generation," Tishby adds, "we thought that discovering laws with computational assistance was absurd, but today computers are in effect already doing that and even assisting with the mathematical proofs. It turns out that the use of computers or learning systems to discover laws of nature and create new mathematics is already far from being science fiction."
The reason Lipson is convinced Eureqa has a bright future is the dramatic increase he discerns in the quantity of information being collected in various fields of research in recent years - and the concomitant need for new tools to cope with the flood.
"People are now beginning to ask whether there is a limit to what human beings can understand and model, because of the data deluge," Lipson says. "I believe that tools like Eureqa can help us extend the window of insight a bit further, by converting data from complex phenomena into simple mathematical invariants that we might be able to understand."
At the same time, he notes, a program like Eureqa might bring about opposite results in the long term.
"Eventually, as computers become more sophisticated and the phenomena we tackle more complex, we may not be able to keep up," Lipson says. To illustrate, he invokes the Bard again: "It will be like trying to explain Shakespeare to a dog."
'Like chess players'
Is it possible that a next-generation Eureqa program will generate formulas and models that we will not be able to decipher fully, undermining human insight into research?
That question seems premature, but some scientists are already disturbed by the possibility. One of them is mathematician Steven Strogatz, a colleague of Lipson's at Cornell. In November 2010, The New York Times published a special supplement on the subject, called "What's next in science."
Strogatz, one of 10 leading scientists chosen to address the question, wrote about Eureqa: "Automated scientists [like the Eureqa program] may speed up the pace of discovery, but in the process they may change the nature of science itself. For centuries, scientists have solved problems with flashes of insight. But while the equations that automated scientists offer are very good at making predictions, they are often inscrutable to human scientists. We may have to program computers to explain their discoveries to us. Otherwise they will become more like oracles than scientists, handing down mysterious utterances to us mere mortals."
In an article he published in January 2006 on the Edge website about scientific insight, Strogatz wrote, "I worry that insight is becoming impossible, at least at the frontiers of mathematics ... Even when we're able to figure out what's true or false, we're less and less able to understand why."
As an example, Strogatz cited the four-color theorem, that maintains that four colors are enough to use on a map of contiguous territory if one does not want adjacent countries to be demarcated in the same color. The sentence was proved in 1976 by a computer program, but, to this day, no mathematician has succeeded in corroborating the proof.
In fact, in recent decades computer programs have been able to prove dozens of mathematical hypotheses (using techniques different from Eureqa ), and some of the proofs have not been corroborated by human mathematicians. "If this is happening in mathematics, the supposed pinnacle of human reasoning, it seems likely to afflict us in science, too, first in physics and later in biology and the social sciences," Strogatz wrote.
According to Israeli-born mathematician Prof. Doron Zeilberger, from Rutgers University in New Jersey, who is one of the leading figures in computer-assisted mathematics, the transition to the era of computer-generated proofs will undoubtedly lead to the loss of the human understanding of these proofs. But in his view this will actually be an encouraging sign in terms of the discipline's development.
"If someone can understand the proof for the sentence in retrospect, then the sentence is not interesting," he says. "Such proofs will be considered trivial. Just as Groucho Marx said he would not want to be a member of a club that would accept him, my approach holds that if someone can fully understand a mathematical proposition, the mathematics is not deep enough. And in the future mathematics will be a great deal deeper, because of the computer, and at that stage there will be no hope of understanding proofs line by line."
The citation for the Euler Medal, which was awarded to Zeilberger in 2004, described him as "a champion of using computers and algorithms to do mathematics quickly and efficiently." He sometimes credits his computer, which he named Shalosh B. Ekhad (Hebrew for 'three B one, or 3B1,' a compiter model), as coauthor of his articles.
"Maybe 10 percent of mathematicians are expert in the uses of the computer as a symbolic calculator, and maybe 0.1 percent know how to use the computer as a serious tool of research," he says. "I hope that in another 40 years computers will do most of the work. I predict that most proofs will then be made by computer."
Zeilberger admits that his views on this subject are extreme, and suggests that I speak to more mathematicians. One of them, Prof. Gil Kalai, from the Hebrew University, suggests taking his colleague's conjectures about computergenerated math with a pinch of salt.
"The role of computers in helping to prove mathematical problems is significant, but still quite small," Prof. Kilai believes, "and the role of computers in [coming up with] full proofs is still very small."
He adds, "There are many dreams and fantasies in matters that are close to the forefront of science. I am happy that Zeilberger is enthusiastic about what he is developing, but it's very difficult to know what the situation will be in another 10 years."
Kalai agrees that there are already a number of cases in which the computer-generated proof is so complicated that the proof cannot be checked - the results cannot be corroborated.
Kalai recalls the famous conjecture by the 17th-century astronomer Johannes Kepler, dealing with the most economical way to pack spheres in three-dimensional space.
In 1998, the mathematician Thomas Hales succeeded in proving, by computational analysis, that Kepler's proposed solution to the problem was correct. After Hales announced that he had proved the Kepler conjecture, the journal Annals of Mathematics set up a team of 20 leading experts in the field to examine his work.
Members of the team gradually left over the years, until it disbanded in 2004. As a result, the journal's editors decided to publish only the theoretical part of Hales's article. They sent the findings derived by computation to a different journal.
For his part, Prof. Tishby maintains that mathematicians are unjustly suspicious of computational mathematics: "Many mathematicians treat computational proofs with disgust, believing that it will never be possible to make a computer that will replace the creative genius of mathematicians. I regret to say they are wrong.
"They are behaving exactly like chess players," Tishby continues, "who did not believe that a computer would be able to defeat them and even find creative solutions to chess problems. We see here a professional ego that is humanly understandable, but is probably unwarranted."
Like Zeilberger, the mathematician Timothy Gowers - from Cambridge University and a winner of the Fields Medal (often referred to as the Nobel Prize of mathematics ) - is not one of the skeptics mentioned by Tishby. However, he foresees that the development in the realm of computational proofs will come from a very different direction. Gowers notes that the proof of the Kepler conjecture and of the four-colors sentence belong to a certain type of proofs, which mostly exploit the computer's ability to scan a prodigious number of cases.
"I think that these are the kinds of proofs which excite Zeilberger," he says in an email conversation, referring to proofs which human mathematicians can come up with in principle, but not in practice. "I think he places too much emphasis on the kinds of proofs for which [these types] happen to be useful. There is a lot of very interesting mathematics to which that does not apply, which he tends to dismiss as 'trivial' and 'human.'"
As Gowers sees it, the importance of computers in automating mathematical research will not be embodied in methods of "brute force," which makes it possible to solve problems like the four-color sentence. The methods, rather, will be based on human mathematical thought. For example, he believes that in the foreseeable future a computer program will be developed that absorbs and concentrates all the processes of mathematical reasoning which are relatively easy for mathematicians to do. However, because the program will integrate the expertise of mathematicians possessing different abilities and cover a range of research fields, it will have a tremendous advantage over each of them separately. "You would have a tool to spot arguments that humans who weren't in the right area would take a long time to spot," he explains.
In the long term, Gowers believes that computers will be able to bypass human research capabilities in mathematics. "But even I think that day may be some way off," he says.
Most of the scientists I spoke to agreed that there are significant differences between the ability to generate analytical proofs in a field like mathematics, and the creation of formulas and models in other, less exact sciences. Others accepted Strogatz's argument that the computer-generated buds in the field of mathematics will blossom in other areas of research as well. In any case, it seems the problem of the loss of insight is even further away, but Lipson asserts that this phenomenon is already visible in research that is aided by Eureqa. He says that a number of models developed by the program in the realm of biology have not yet been published, because scientists are unable to explain them.
One of the examples he cites refers to a study by the biologist Gurol Suel, from the University of Texas. Suel studied a bacterium called Bacillus subtilis, which under certain conditions becomes a type of spore.
Suel collected a great deal of information about the proteins and other subcellular factors which are responsible for this process, and tried to identify an equation that could model the connections between all the different factors. When he heard about Eureqa, he decided to try his luck.
His first attempt was largely a failure: The program came up with an equation, but it was long, overly complex and packed with variables. Suel and Lipson returned to their respective laboratories to try to solve the riddle. A few months later, they both created, separately, new equations. The equations were similar, but Suel's, which was constructed directly from the biochemical data in his lab, had 16 variables, whereas the Eureqa equation had only seven. Both equations explained the given data well (with a slight advantage to Suel ) and also managed to explain new data.
The problem is that neither Lipson nor Suel can explain why the simpler model works. "We are in the process of figuring out what reduction has occurred in the seven-variable model," Prof. Suel wrote me recently.
Lipson, for his part, views the Eureqa-generated equation as an unexplained success of the program. Maybe, he says, it is a sign of things to come.
How robots learn
Hod Lipson’s main field of research is evolutionary robotics. It was his work there that spawned Eureqa. “The question that challenges me is whether it is possible to make a machine that can make other machines,” he says.
Lipson first gained public exposure in 2007, when he spoke at a TED conference about his work in robotics and presented a starfish-like robot with four legs. The robot was not programmed in advance for locomotion, but “learned” how to move by trial and error, with the help of the genetic algorithms which constituted the basis for Eureqa’s method of operation.
Lipson hopes that bio-inspired robotics will make it possible to create more advanced robots than the ones currently being designed. “Most of the robots that exist in the market are designed by engineers who sit at a desk and sketch the robot and a programmer who works on the controller. They’re based on the idea of intelligent design. But in certain fields evolutionary algorithms are slowly making headway and outdoing what we do manually. I say this cautiously, because it depends how you measure the performance. But there are examples in certain fields of evolutionary processes generating better solutions than a programmer could have.”
The major advantage of evolutionary robots, Lipson adds, lies in their ability to adapt to changing conditions, in contrast to present-day robots, which are limited to the environment for which they were designed.
“We have a robot that learned how to walk, and we removed one of its legs to see what would happen. We simply removed a leg and destroyed the engine,” Lipson explains. “We did not reprogram the robot, we did not ‘say’ that the leg had been removed. But the robot learned quite quickly how to walk with three legs instead of four. That is an example of spontaneous adaptation. I think that if you remove the leg from a conventional robot, it’s game over.”