Honorable Mention in the
2009 "Doing Good with Good OR" Competition
won by
Diana Negoescu '09 and Peter Frazier *09
for their paper:
Optimal Learning for Drug Discovery in Ewing's Sarcoma
Faculty adviser: Warren B. Powell
We
are pleased to announce that Diana Negoescu '09 and Peter Frazier *09 received
the honorable mention in the first "Doing Good with Good OR" competition
sponsored by Informs. Their project addressed the problem of sequencing the
testing of different compounds. For example, in the simple molecule below,
there are two sites where we can put any of six substituents (in this case
the substituents are atoms, but more frequently these are small combinations
of atoms).
For larger molecules, there can easily be thousands or tens of thousands of combinations.
The project involved the application of the knowledge gradient (see the page on Optimal Learning) to the problem of how to sequence experiments. Each experiment is used to update a statistical model known in this literature as the Free-Wilson model. The knowledge gradient identifies the compounds from which we will learn the most. After each experiment, we update the Free-Wilson model, which can then be used to predict which compound is the best. Since these experiments are time consuming and expensive, the goal of this research was to run the smallest number of experiments.
The
research used a version of the knowledge gradient which takes advantage of
correlated beliefs - trying one compound teaches us something about other
compounds due to similarities. This makes it possible to sequence a few hundred
experiments, after which we make a recommendation about the best out of 50,000
compounds. The research required modifications to the algorithm for computing
the knowledge gradient with correlated beliefs. The original algorithm could
handle problems with a few thousand choices, while the largest molecule tested
in this research had 87,000 combinations. The new algorithm, which was mathematically
equivalent, reduced the need to store a covariance matrix with 87,000 rows
and columns to one with only about 200 rows and columns, with a dramatic reduction
in execution times.
The figure to the left illustrates the ability of the KGCB algorithm to quickly find the best molecule compared to a random strategy. In this experiment, KGCB reliably found the best compound (out of 10,000 choices) in as little as 20 to 60 experiments, versus 60 to over 120 experiments using an unstructured strategy.
Slide presentation given by Diana Negoescu at Informs for the competition
Optimal Learning for Drug Discovery in Ewing's Sarcoma
Additional readings:
Diana Negoescu, Peter I. Frazier and Warren B. Powell, "The Knowledge-Gradient Algorithm for Sequencing Experiments in Drug Discovery," more complete technical paper describing the algorithmic research in detail.
Frazier, P., W. B. Powell and S. Dayanik, “A Knowledge Gradient Policy for Sequential Information Collection,” SIAM J. on Control and Optimization, Vol. 47, No. 5, pp. 2410-2439 (2008). - This is the original theory paper setting up the knowledge gradient algorithm with independent beliefs.
P. Frazier, W. B. Powell, S. Dayanik, “The Knowledge-Gradient Policy for Correlated Normal Beliefs,” Informs Journal on Computing (to appear). - This paper introduces the knowledge gradient algorithm for correlated beliefs.