Posted on

Online Learning as the Mathematics of Accountability

Accountability is a social problem. When someone screws up, do you fire them? Or do you accept the error and let them continue? This is a very difficult problem and we all know of stories where the wrong decision was made.

Online learning (as meant here), is a subfield of learning theory which analyzes the online learning model.

In the online learning model, there are a set of hypotheses or “experts”. On any instantance x, each expert makes a prediction y. A master algorithm A uses these predictions to form it’s own prediction yA and then learns the correct prediction y*. This process repeats.

The goal of online learning is to find a master algorithm A which uses the advice of the experts to make good predictions. In particular, we typically want to guarantee that the master algorithm performs almost as well as the best expert. If L(e) is the loss of expert e and L(A) is the loss of the master algorithm, it is often possible to prove:

L(A) less than mine L(e) + log(number of experts)

over all sequences.

In particular, there is no assumption of independent samples and there is no assumption that the experts perform well (or can perform well). This is not a high probability statement: it simply always holds. These assumption-free qualities are very important for application to the accountability problem, because the experts really can be adversarial.

In any situation where we have a set of human experts giving advice on the same subject, we can hope to apply online learning algorithms to better distill collective advice into single prediction. Examples include:

  1. stock picking Many of the big stocks have ‘analysts’ who predict whether they will go up or down. For an example, look here.
  2. surveys It is common to see things like “A gain of 1.4 percent was expected, based on the median estimate in a Bloomberg survey of 53 economists” in news articles. Presumably, these economists are reused frequently implying they have a record to which an online algorithm could be applied.

This application of online learning isn’t trivial. Even for the above examples, it isn’t clear how to handle issues like:

  1. A new expert starts making predictions. There are some reasonable ad-hoc mechanisms for coping with this in the context of particular algorithms.
  2. An expert declines to make a prediction. The modified “sleeping experts” setting handles this, but the results are not quite as tight.
  3. The loss associated with individual predictions is highly variable rather than something simple like “0/1-loss” or “squared error loss”. One approach to this is to combine regret minimizing learning reductions with online learning algorithms (drawback: the reduced predictions may not be of intuitive things). Another approach is simply trying to make very flexible master algorithms (drawback: flexibility often comes with a weakening in the theoretical guarantees).
  4. In the real world, we may not have feedback about a prediction until after the next 10 predictions (or more) need to be made.
  5. In the real world, there may be uncertainty about the measured truth. Quantifying GDP growth requires a lot of work and has some fundamental uncertainty associated with it, especially when immediate feedback is required.
Posted on

Site Update

I tweaked the site in a number of ways today, including:

  1. Updating to WordPress 1.5.
  2. Installing and heavily tweaking the Geekniche theme. Update: I switched back to a tweaked version of the old theme.
  3. Adding the Customizable Post Listings plugin.
  4. Installing the StatTraq plugin.
  5. Updating some of the links. I particularly recommend looking at the computer research policy blog.
  6. Adding threaded comments. This doesn’t thread old comments obviously, but the extra structure may be helpful for new ones.

Overall, I think this is an improvement, and it addresses a few of my earlier problems. If you have any difficulties or anything seems “not quite right”, please speak up. A few other tweaks to the site may happen in the near future.

Posted on

Science in the Government

I found the article on “Political Science” at the New York Times interesting. Essentially the article is about allegations that the US government has been systematically distorting scientific views. With a petition by some 7000+ scientists alleging such behavior this is clearly a significant concern.

One thing not mentioned explicitly in this discussion is that there are fundamental cultural differences between academic research and the rest of the world. In academic research, careful, clear thought is valued. This value is achieved by both formal and informal mechanisms. One example of a formal mechanism is peer review.

In contrast, in the land of politics, the basic value is agreement. It is only with some amount of agreement that a new law can be passed or other actions can be taken. Since Science (with a capitol ‘S’) has accomplished many things, it can be a significant tool in persuading people. This makes it compelling for a politician to use science as a mechanism for pushing agreement on their viewpoint.

Most scientists would not mind if their research is used in a public debate. The difficulty arises when the use of science is not representative of the beliefs of scientists. This can happen in many ways. For example, agreement is uncommon in research which implies that it is almost always possible, by carefully picking and choosing, to find one scientist who supports almost any viewpoint.

Such misrepresentations of scientific beliefs about the world violate the fundamental value of “careful, clear thought”, so they are regarded as fundamentally dangerous to the process of research. Naturally, fundamentally dangerous things are sensitive issues which can easily lead to large petitions.

This combination of mismatched values is what appears to be happening. It is less clear what should be done about it.

One response has been (as the article title suggests) politicization of science and scientists. For example the Union of Concerned Scientists (which organized the petition) has a viewpoint and is pushing it. As another example, anecdotal evidence suggests a strong majority of scientists in the US voted against Bush in the last presidential election.

I would prefer a different approach, which is essentially a separation of responsibilities. Given a sufficient separation of powers, scientists should be the most reliable source for describing and predicting the outcomes of some courses of action and the impact of new technologies. What is done with such information is up to the rest of the world. This style of “sharply defined well-separated powers” has worked fairly well elsewhere. Supreme court judges (who specialize in interpretation of law) are, by design, relatively unaffectable by the rest of politics. A newer example is the federal reserve board who have been relatively unaffected by changes in politics, even though it is easy to imagine their powers could dramatically effect election outcomes. This last example is a matter of custom rather than constitutional law.

Neither of the above examples are perfect—the separation of powers has failed on multiple occasions. Nevertheless, it seems to be a useful ideal.

Posted on

(Dis)similarities between academia and open source programmers

Martin Pool and I recently discussed the similarities and differences between academia and open source programming.

Similarities:

  1. Cost profile Research and programming share approximately the same cost profile: A large upfront effort is required to produce something useful, and then “anyone” can use it. (The “anyone” is not quite right for either group because only sufficiently technical people could use it.)
  2. Wealth profile A “wealthy” academic or open source programmer is someone who has contributed a lot to other people in research or programs. Much of academia is a “gift culture”: whoever gives the most is most respected.
  3. Problems Both academia and open source programming suffer from similar problems.
    1. Whether or not (and which) open source program is used are perhaps too-often personality driven rather than driven by capability or usefulness. Similar phenomena can happen in academia with respect to directions of research.
    2. Funding is often a problem for both groups. Academics often invest many hours in writing grants while open source programmers simply often are not paid.
  4. Both groups of people work in a mixed competitive/collaborative environment.
  5. Both groups use conferences as a significant mechanism of communication.

Given the similarities, it is not too surprising that there is significant cooperation between academia and open source programming, and it is relatively common to crossover from one to the other.

The differences are perhaps more interesting to examine because they may point out where one group can learn from the other.

  1. A few open source projects have achieved significantly larger scales than academia as far as coordination amongst many people over a long time. Big project examples include linux, apache, and mozilla. Groups of people of this scale in academia are typically things like “the ICML community”, or “people working on Bayesian learning”, which are significantly less tightly coupled than any of the above projects. This suggests it may be possible to achieve significantly larger close collaborations in academia.
  2. Academia has managed to secure significantly more funding than open source programmers. Funding typically comes from a mixture of student tuition and government grants. Part of the reason for better funding in academia is that it has been around longer and so been able to accomplish more. Perhaps governments will start funding open source programming more seriously if they produce an equivalent (with respect to societal impact) of the atom bomb.
  3. Academia has a relatively standard career path: grade school education, undergraduate education, graduate education, then apply for a job as a professor at a university. In contrast the closest thing to a career path for open source programmers is something like “do a bunch of open source projects and become so wildly succesful that some company hires you to do the same thing”. This is a difficult path but perhaps it is slowly becoming easier and there is still much room for improvement.
  4. Open source programmers take significantly more advantage of modern tools for communication. As an example of this, Martin mentioned that perhaps half the people working on Ubuntu have blogs. In academia, they are still a rarity.
  5. Open source programmers have considerably more freedom of location. Academic research is almost always tied to a particular university or lab, while many people who work on open source projects can choose to live esssentially anywhere with reasonable internet access.