direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

All Publications

Bayesian transductive classification by maximizing volume in version space
Citation key Graepel1999d
Author Graepel, T. and Herbrich, R., and Obermayer, K.
Title of Book Proceedings of Learning 1999 Conference
Year 1999
Abstract According to Vapnik [1], when solving a given problem one should avoid solving a more general problem as an intermediate step. A direct application of this principle reduces the more general problem of inferring a functional dependency on the whole of input space to the problem of estimating the values of a function at given points (working set), a paradigm referred to as \\\"transductive inference\\\". We consider the case of binary classification by linear discriminant functions. The simplification of the 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 labeling of the working set as the volume of the corresponding polyhedron w.r.t. the apriori distribution in parameter space. Then the maximum aposteriori (MAP) scheme recommends to choose the labeling of maximum volume. In the case of general priors a Monte Carlo sampling of version space leads to estimates of the relevant volumes. Sampling, however, is computationally costly because it is necessary to check one constraint per data point in the training set and the rejection rate grows exponentially with the dimensionality of the input space. We thus suggest to sample the version space using an ergodic billiard, an idea first employed by Rujan [2] for finding the center of mass of version space. Starting from the point corresponding to the Optimal Hyperplane into a randomly selected direction, one follows the trajectory of an ideal billiard ball and determines the largest subvolume in version space as the one, where the ball spends the longest time on its journey. This procedure reduces computational costs because the ball stays by definition always in version space. The success of this method depends on the question if the billard is ergodic, i.e. whether its trajectory eventually covers all of version space uniformly. We present experimental results for the transduction scheme described above and we compare our method with other transduction schemes [3] as well as with the Optimal Hyperplane Classifier [1].
Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions