Maximum a Posteriori Transduction

Transduction deals with the problem of estimating the values of a function at given points (called working samples) by a set of training samples. This paper proposes a maximum a posteriori (MAP) scheme for the transduction. The probability measure defined for the estimation is induced by the code length of the prediction error and the model with respect to some coding system. The ideal MAP transduction is essentially to minimize the so-called stochastic complexity. Approximations to the ideal MAP transduction are also addressed, where one or multiple models of the function are estimated as well as the values at the working sample. This work investigates, for both pattern classification and regression, that under what condition the approximated MAP transduction is better than the traditional induction, which learns models from the training samples and then computes the value at the given points. Analysis on whether the working samples compress the description length of the model is also presented. For some coding system it does, for some others it doesn’t. For fairness, a universal coding system should be adopted, but it involves the problem of not recursively computable. Keywords: Transduction; maximum a posteriori; minimum description length; stochastic complexity 1