March 19th, 2010

humster

Are machines ready to break down language barriers?

EVEN in an era of global networks and cheap travel, international communication still faces one great barrier: we don't all speak the same language. But that gap is narrowing as online translation services advance.

Recently launched website Meedan translates Arabic-language news stories into English, and vice versa, and displays the two versions alongside each other. Comments in either language are instantly translated. A new site for bloggers, called Mojofiti, automatically makes posts available to readers in 27 languages. And Google now has a tool that will eventually allow anyone with a camera-phone to photograph, say, a German restaurant menu, send the image as a multimedia message to Google's servers, and get an English translation sent back to them.

All these services ultimately rely on a technique called statistical machine translation, in which software learns to translate by using brute mathematics to compare large collections of previously translated documents. It then uses the rules it has learned this way to determine the most likely translation in future.

"Whenever there is a possibility of the language barrier preventing someone from doing something there should be the possibility to translate," says Franz Och, who leads machine translation research at Google. His team's Translate service can currently operate between 52 different languages and he is aiming to add more, especially those previously ignored by machine translators. "A speaker of Bengali can only experience a tiny fraction of a per cent of the web," says Och.

Though translation algorithms have improved, some human intervention is still needed to provide a translation that reads well. Meedan's news articles, for example, are machine translated and then tidied up by editors. Google's Toolkit for professional translators produces a machine translation for them to tidy up, in the process providing feedback to the software to improve its translation capabilities.

With the right help even someone that speaks only a single language could produce results as good as those of a professional, says Philipp Koehn of the University of Edinburgh, UK. His service, Caitra, outputs several possible phrases if it is uncertain which one is correct. This lets a monoglot user fix garbled phrases that would otherwise be unfathomable without reading the original.
humster

The predictioneer: Using games to see the future

MY HOROSCOPE this week says that now is the perfect time to relocate, or at least de-clutter. I know it's nonsense, but I can't help wishing there was a genuine way to predict the future.

Perhaps there is. One self-styled "predictioneer" believes he has found the answer. Bruce Bueno de Mesquita is a professor of politics at New York University and a senior fellow at the Hoover Institution at Stanford University in California. In his new book, The Predictioneer (The Predictioneer's Game in the US), he describes a computer model based on game theory which he - and others - claim can predict the future with remarkable accuracy.

Over the past 30 years, Bueno de Mesquita has made thousands of predictions about hundreds of issues from geopolitics to personal problems. Overall, he claims, his hit rate is about 90 per cent. So how does he do it?

Bueno de Mesquita's "predictioneering" began in 1979 when he was on a Guggenheim fellowship writing a book about the conditions that lead to war. He had designed a mathematical model to examine the choices people could make and the probability that their actions would result in either diplomacy or war. Like any model, he needed data to test it.

A good opportunity arose when the US State Department asked his opinion about an ongoing political crisis in India. The ruling coalition had become unstable and it was clear that Prime Minister Morarji Desai would be forced to stand down and a new prime minister chosen from within the coalition.

Since his PhD thesis had been on Indian politics, and data on politics didn't seem a million miles from data on war, Bueno de Mesquita agreed to help. He compiled a list of all the people who would try to influence the appointment of the next prime minister, what their preference was and how much clout they had. He fed this information into his computer programme, asked it to predict how the negotiations would play out and left it to run overnight. His own hunch was that the deputy prime minister, Jagjivan Ram, would take over. Many other experts on Indian politics thought the same thing.

The following morning, he checked the computer and found to his surprise that it was predicting a politician called Chaudhary Charan Singh would be the next prime minister. It also predicted that he would be unable to build a working coalition and so would quickly fall.

Strange result

When Bueno de Mesquita reported the result to an official at the State Department, he was taken aback. The official said no one else was saying Singh and the result was strange, at best. "When I told him I'd used a computer programme I was designing, he just laughed and urged me not to repeat that to anyone," says Bueno de Mesquita. A few weeks later, Singh became prime minister. Six months on his government collapsed. "The model had come up with the right answer and I hadn't," says Bueno de Mesquita. "Clearly there were two possibilities: the model was just lucky, or I was on to something."

Three decades later, it is clear that Bueno de Mesquita is on to something. The model has been used by Bueno de Mesquita, his students and clients (including the US government) to make thousands of predictions published in hundreds of peer-reviewed publications. These include whether or not North Korea's supreme leader, Kim Jong II, would dismantle his nation's nuclear arsenal, how a land-for-peace formula could work in the Israeli-Palestinian conflict, and which clients of a risk-management group were likely to commit fraud. According to research by the CIA, Bueno de Mesquita's model is more than 90 per cent accurate (British Journal of Political Science, vol 26, p 441). He now spends a considerable proportion of his time running a consultancy firm based in New York.

How is such accuracy possible? What Bueno de Mesquita is not doing is predicting random events such as lottery draws. Nor does he claim to be able to forecast the movement of stock markets, the outcome of general elections or the onset of financial crises - events where millions of people have a small influence, but none is able to move the market on their own.

Rather, he confines himself to "strategic situations" where relatively small numbers of people are haggling over a contentious decision. "I can predict events and decisions that involve negotiation or coercion, cooperation or bullying," he says. That includes domestic politics, foreign policy, conflicts, business decisions and social interactions.
His main tool is game theory, which uses mathematics to predict what people will do in a situation where the outcome also depends on other people's decisions. "It's a fancy label for a pretty simple idea: that people do what they believe is in their best interest," says Bueno de Mesquita.
Invented in the 1940s by John von Neumann and Oskar Morgenstern, the original formulation was based on games where players tried to anticipate other players' moves or countermoves but essentially all participants were cooperative and truthful. In the 1950s, mathematician John Nash, subject of the film A Beautiful Mind, created a more realistic formulation in which players are out for themselves and can bully, lie, bluff or renege on their word to achieve their desired outcome. The classic example is the prisoner's dilemma (see "Game theory in action"). Bueno de Mesquita uses Nash's assumptions: players are motivated by self-interest and will do whatever they can to get what they want - or at least to block an undesired outcome.

In its simplest form the model works like this. First, Bueno de Mesquita decides what question to ask - for example, will Iran build a nuclear warhead. He then compiles a list of everybody who might influence that decision, and assigns each of them a value from 1 to an arbitrary number, say 100, in each of four categories: what outcome they want; how important they think the issue is; how determined they are to reach agreement; and how much influence they have.

At that point, the "negotiations" begin. Say there are five players, A, B, C, D and E. To arrive at a result, every player is paired with every other and their positions compared. When A is paired with B, for example, A must decide whether to support or resist the central proposal ("Iran should build a nuclear weapon") or offer a counter-proposal, taking into account B's position and the likelihood of getting C, D or E's support. B either agrees, negotiates or bullies in return, all the while taking the positions of the other three players into account. Once every possible combination has been played out, each player sorts through the various proposals or demands they received, and evaluates the credibility of any threats made against them. Players may then shift position accordingly. At the end, the model calculates the group's overall position as a number between 1 and 100. This is taken to be the "result".

When five players are involved there are 120 possible interactions - every player's interaction with every other, in both directions (5 × 4), multiplied by the other three players' positions (3 × 2). But the complexity soon skyrockets. If you jump to 10 players there are 3.6 million potential interactions. A typical predictioneer problem involves 30 to 40 players, although Bueno de Mesquita has tackled problems with more than 200.

Game theory aside, one of the key determinants of the model's success is the quality of the original data: garbage in leads to garbage out. To obtain good quality data, Bueno de Mesquita consults widely with experts in the field.

According to political scientist Nolan McCarty of Princeton University, this is the real strength of the approach. "I suspect the model's success is largely due to the fact that Bueno de Mesquita is very good on the input side; he's a very knowledgeable person and a widely respected political scientist. I'm sceptical that the modelling apparatus adds as much predictive power as he says it does."

McCarty's Princeton colleague, economist Avinash Dixit agrees, but adds a word of warning. "Experts can be wrong, as we have seen in a different context recently, namely the financial crisis."

Dixit has another problem with the data produced by the model. "There's ambiguity about what the final number means. For example, if the prediction is whether Iran acquires nuclear weapons, and the answer is graded on the scale from 0 to 200, what would 120 mean? There's going to be a bomb or there will be no bomb? That is not so clear. I think the seemingly precise answers are deceptive, and game theorists should be more humble and more open about the uncertainty that is unavoidable in their calculations and results."

Bueno de Mesquita accepts that the results require expert interpretation, but says there is no ambiguity. "The issue scales are not just whether a bomb will be built or not," he says. "Rather they define points in between; 120 on the Iran nuclear scale refers to Iran developing weapons-grade fuel but not building a bomb."

Bueno de Mesquita is now working on a new and more complex model using Bayesian game theory, which also takes into account players' beliefs about other players and also allows for scenarios with imperfect or incomplete information.

"The old model - essentially a sophisticated version of the one I used in 1979 - was accurate 90 per cent of the time," he says. "This new model blows the old one out of the water in terms of the result and the accuracy of the path leading up to the outcome." In February he presented a paper at a meeting of the International Studies Association detailing the difference in performance between the two models.
So how good is the new model? Bueno de Mesquita recently used it to make a prediction on the political situation in Pakistan. Working with a group of students, he asked how willing the Pakistani government would be to pursue Al-Qaida and Taliban militants in its territory, and how the US government could exert influence on their decision.

Targeting terror

In January 2008 the students fed in data on all the players, including the US, Pakistan's then president Pervez Musharraf and other leading Pakistani politicans. Their assumption was that the US would offer foreign aid to persuade Pakistan's leaders to target the terrorists, and Pakistan would try to extract the maximum amount of aid possible from the US.

The model predicted that to get maximum cooperation from Pakistan, the US would need to donate at least $1.5 billion in 2009, double the projected 2008 figure. In return for this Pakistan would pursue the terrorists on a scale of 80 out of 100, but no more. In other words, the leadership would make considerable effort to reduce the terrorist threat but not to completely eliminate it. "The Pakistani government are no fools," explains Bueno de Mesquita. "They know that the money will dry up if Al-Qaida and the Taliban are destroyed. So they will rein the threat in and reduce it, but not utterly destroy it."

The Pakistani government are no fools. They know the money will dry up if the militants are destroyed
The outcome? According to Bueno de Mesquita, the US government authorised $1.5 billion in foreign aid to Pakistan in 2009, and the Pakistani leadership sustained pursuit of the militants at that level. "We have done very well," says Bueno de Mesquita.

With such a powerful tool at your disposal, it must be tempting to use it for yourself. Bueno de Mesquita admits that he has received a few shady offers. In 1997, representatives of Mobutu Sese Seko, the recently deposed president of Zaire (now the Democratic Republic of the Congo), asked him to calculate how to salvage control of the country in return for 10 per cent of Mobutu's substantial wealth. Bueno de Mesquita alerted the US government.

He has, however, used his model to help friends and also to assist the San Francisco Opera when it was having financial difficulties.

So what of the future? Another of Bueno de Mesquita's recent predictions addresses the future of climate change negotiations up to 2050. Depressingly, he predicts that although the world will negotiate tougher greenhouse gas reductions than in the Kyoto protocol, in practise these are likely to be abandoned as Brazil, India and China rise in power in relation to the European Union and the US.

The predictioneer has also been spectacularly wrong, though. In 1992, he was asked to predict which bills would be likely to get through the US Congress after Bill Clinton was elected president. It was well known that Clinton was planning to push through a healthcare bill, but all 27 of Bueno de Mesquita's predictions of what was likely to be in it and which elements would be passed by Congress turned out to be incorrect.

Where did it all go wrong? The problem was with the inputs. Bueno de Mesquita had assumed that an influential congressman, Daniel Rostenkowski, would be the key to getting healthcare reform through. But just as Clinton began to push through the plan, Rostenkowski came under investigation for corruption and was eventually forced to resign from office. Bueno de Mesquita was unhappy at the time, but now shrugs it off: "I have been willing to put my reputation on the line and publish before events happened. So far I've not been too embarrassed."