Why Ensembles Work

• Why should it be possible to find ensembles of classifiers that make uncorrelated errors?
• Why shouldn't we be able to find a single classifier that performs as well as an ensemble?
• 1) training data might not be sufficient - in 2 class problem need O(log|H|) examples minimum - many equally good hypothesis on the amount of data we have seen
• 2) difficult search problems - smallest decision tree consistent with the data, finding the weights for the smallest possible Neural Network consistent with the training data - NP-hard
• use search heuristics - so even if there is a unique best hypothesis we might not find it - so find suboptimal approximations
• so ensembles combine different suboptimal approximations
• 3) hypothesis space may not contain the true function - weighted combinations of approximations might be able to represent classifiers outside of H
• just complex decision trees but way to large for the available data