Gibbs Algorithm

Why can't we just use the Bayes optimal classifier every time?

An alternative to the Bayes optimal classifier is a slightly less optimal procedure known as the Gibbs Algorightm.

1.

Choose a hypothesis h from H at random according to the posterior distribution over H.

2.

use h to predict the classification of the next instance x.

The misclassification error for the Gibbs algorithm is at most twice the expected error of the Bayes optimal classifier!

Read Opper and Haussler (1991) and Haussler et al. (1994) which will be given.