So What's LETOR?

Chinese Puzzle by Eugene Mihaesco
June 29th, 2013

In the book The Society of Mind by Marvin Minsky the mind is portrayed as a "society" of agents, each of which is relatively simple. Minsky postulates that despite the simplicity of each agent their interactions give birth to all the complicated, contradictory, and often fully illogical behaviors we associate with being human. A form of emergence. The system has developed to answer users' questions in many ways mirrors Minsky's idea.


Our system consists of many "agents" each of which offers hypotheses to answer the user's question. Each agent, in and of itself, is relatively simple. For example, one agent may know how to extract dates as hypotheses, one may know how to extract numbers as hypotheses, while another may know how to extract place names. Alone, each one of these agents is relatively unspectacular. However, once one creates an ensemble containing a large number of these simple agents, a sort of "intelligence" emerges.

In such a large ensemble one, or more, agent is bound to be able to correctly answer the question at hand. However, by the same token, one, or more of them, is bound to answer the question incorrectly. The problem then becomes: How does one extract the signal from the noise?

Signal to Noise

Each agent tries to help a bit in this task. To each hypothesis it attaches a confidence, the higher the confidence the more likely it thinks its answer is correct. This simple number goes a long way in extracting the signal from the noise. For example, if the majority of agents offer the same hypothesis, each with a high confidence, then it's likely that this hypothesis is correct. However, not all cases are this clear cut.

More often than not there are competing hypotheses. One group of agents thinks that Sultan Kösen is the tallest man on earth

Sultan Kosen

Sultan Kosen

while another group thinks it is Kristain Matsson.

Kristain Matsson

Kristain Matsson

(Strangely enough, both groups are right! Sultan Kösen is taller than any other man on earth and Kristain Matsson is the sole member of the band The Tallest Man on Earth.)

The question is: What to do? One could, and previously we did, weight competing hypotheses according to the number of agents suggesting the hypothesis and the agents' associated confidences. This is simple, effective, and works most of the time. However one can do better.

Agents are Simple, Very Simple

Part of the problem is that each agent is simple, very simple. It can only do two things: pick out a hypothesis and attach a confidence to that hypothesis. It does neither of these particularly well. For some types of questions it picks the wrong answer but yet it's very confidant. For other types of questions it picks the correct answer but it's not at all confident of its answer. The question is: How to fix this?

There are only really two things one can do. First, one can make each of these numerous simple agents "smart" so its confidence estimates are always correct. Second, one can create another "smart" agent whose job it is to revise the confidences of the other simple agents. We took this second path, as it touches less code.

So, What's LETOR?

LETOR is an abbreviation of LEarning TO Rank. It's a catch all term used for techniques that a "smart" agent can use to revise the confidences of other simple agents. Usually these techniques consist of applying various machine learning technologies to the problem of confidence revision.

As the literature attests to its success, we decided to use machine learning techniques when attacking the problem. (In particular SVR). So, we first needed data to learn from. Luckily, we have a repository of about 500K questions. To start with we choose about 5K questions and found their answers through Mechanical Turk. We then ran these 5K questions through our system, keeping track of all agents' hypotheses, all agents' confidences, all documents from which answers were quelled, NLP analysis of these documents, and a lot more information. We then taught the system the mapping from all the saved system data (question, hypothesis, confidences, NLP analysis...) to a number 0 or 1. The mapping was to 0 if the hypothesis was incorrect, 1 if it was correct.

The results are amazing! The single agent implementing our LETOR algorithm lead to a larger increase in system performance than any other agent in the entire system!


Leave a comment: