Bayesian Transductive Classification by Maximizing Volume in Version Space

We consider the case of binary classification by linear discriminant functions. The simplification of the transduction problem results from the fact that the infinite number of linear discriminants is boiled down to a finite number of equivalence classes on the working set. The number of equivalence classes is bounded from above by the growth function. Each equivalence class corresponds to a polyhedron in parameter space. In a PAC style setting we consider only the region of parameter space with zero training error, often referred to as the version space. From a Bayesian point of view, we suggest to measure the prior probability of a labelling of the working set as the volume of the corresponding polyhedron w.r.t. the a-priori distribution in parameter space. Then the maximum a-posterior (MAP) scheme recommends to choose the labelling of maximum volume.

References

• Thore Graepel, Ralf Herbrich, and Klaus Obermayer. Bayesian Transductive Classification by Maximizing Volume in Version Space to be presented at Snowbird1999.
• Thore Graepel, Ralf Herbrich, and Klaus Obermayer. Bayesian Transduction. . In Advances in Neural Information System Processing 12, pages 456-462, 2000. (Gzipped PostScript).
• Thore Graepel and Ralf Herbrich. The Kernel Gibbs Sampler. . In Advances in Neural Information System Processing 13, 2001. in press. (Gzipped PostScript).
• NIPS*99 Workshop