Abstract
Algorithms or models are often measured using a fitness function that calculates total prediction error. While reducing total error is typically the overall objective, examining error as an aggregate value does not provide a thorough understanding of model behaviour. A greater appreciation of behaviour can be obtained through performing a bias-variance decomposition to split error into bias and variance components. This is effective for assessing a deterministic algorithm, such as Classification and Regression Trees (CART). However, splitting the error into bias and variance is not sufficient for non-deterministic algorithms, such as genetic programming (GP), that potentially produce a different model each time they are applied to the same sample.
This thesis presents an extended bias-variance decomposition that decomposes error into bias, external variance (error attributable to limited sampling of the problem), and internal variance (error due to random actions performed as part of the algorithm’s execution). Using this extended decomposition framework provides a greater understanding of the behaviour of an algorithm, and enables more informed choices in algorithm refinement to be enacted. While the extended error decomposition is primarily applied to GP, it can be used to improve the understanding of any non-deterministic algorithm. This is important for interpreting the modelling properties of these types of algorithms, irrespective of their complexity or assumptions regarding their behaviour.
In this thesis, the extended decomposition is used to characterise the behaviour of GP variants in the literature, determining whether they behave as reported in terms of reducing a particular component of error. While the majority of this thesis examines synthetic data sets, methods for decomposition using finite data samples are also examined to determine their suitability for error analysis.
The application of Z-score standardisation (zero mean with unit variance) to GP is rare in the literature. In this thesis, the extended decomposition is applied to a variant of GP using standardisation. It is shown to generally improve the predictive performance of GP by reducing error due to bias. However, it can also be associated with erratic error due to variance (particularly internal variance). This thesis uncovers evidence that this is due to sparse examples of the training data near the boundary intervals of the explanatory variable. A simple solution to this problem is presented, which involves augmenting the training data with observations at the boundaries of these intervals. Cross-validation is used to determine the appropriate number of boundary observations for a number of “real-world” data sets. The results show that standardisation generally improves the predictive performance of GP for these data sets, often without the need for augmentation, demonstrating the importance and reliability of applying standardisation to GP.
This thesis proposes initial steps towards determining how the extended decomposition can be used for algorithm refinement by targeting a reduction of the largest component of error. This is examined for automated algorithm refinement by comparing different combinations of algorithm modules. If these modules have been selected as candidates after characterising them solely using total error (or without characterising them), they may not provide a sufficiently diverse range of behaviours for comparing and combining them effectively. Also, this thesis demonstrates the difficulty in comparing algorithm modules with relatively similar decomposed error when error due to internal variance is unstable. Alternatively, algorithm adaptations with well-understood behaviour in terms of decomposed error are examined for manual algorithm refinement. This highlights the need for automatic machine learning methods that consider a diverse portfolio of modules in terms of targeting the reduction of different components of error for a given problem.