Probabilistic techniques for program generation

Program optimization with linkage estimation (POLE), employs a
Bayesian network as the probabilistic model and is based on a
prototype-tree. A prototype tree is a single complete n-ary tree (where n is the maximum arity of the non-terminals) that represents a program. Each node in the tree is mapped to a random variable with its support corresponding to the discrete values for the choice set it can take. Programs are formed by sampling from this probabilistic model. More efficient programs are then used to re-estimate the distribution and then re-sample. Each iteration of this loop helps us to capture better and more efficient programs.

A Matlab and Java implementation of POLE is provided for simple problems. The project will involve development of probabilistic models for capturing important parts of the program. Effects of sample size will be studied. Another question that needs to be addressed is: how to estimate the probabilistic model robustly from small sample sizes. You will closely work with two post-doctoral associates.

The student must demonstrate excellent programming skills. Experience
in machine learning and data mining is a plus.

Please send a CV to Kalyan Veeramachaneni (