Implicit bias and recursive grammar structures in estimation of distribution genetic programming

Much recent research in Estimation of Distribution Algorithms (EDA) applied to Genetic Programming has adopted a Stochastic Context Free Grammar(SCFG)-based model formalism. However these methods generate biases which may be indistinguishable from selection bias, resulting in sub-optimal performance. The primary factor generating this bias is the combined effect of recursion in the grammars and depth limitation removing some sample trees from the distribution. Here, we demonstrate the bias and provide exact estimates of its scale (assuming infinite populations and simple recursions). We define a quantity h which determines both whether bias occurs (h > 1) and its scale. We apply this analysis to a number of simple illustrative grammars, and to a range of practically-used GP grammars, showing that this bias is both real and important.