MDL transduction

Transduction takes a set of training samples and aims at estimating class labels of given examples in one step as opposed to the traditional induction, which involves an intermediate learning step. The background philosophy of transduction is that one should not reduce an easier task (estimating labels of given examples) to a substantially more complex problem (learning a model). This paper proposes a new scheme for transductive inference, which we call MDL transduction. It labels the given examples so that the stochastic complexity of the whole data is minimized. In the sense of minimum description length, MDL transduction outperforms induction in both generative and discriminative methods. A key property of MDL transduction is that it learns nothing about the model. This highly agrees with the afore-mentioned philosophy. Relation to Transductive SVM (TSVM) is also discussed. We show that TSVM is an approximation of MDL transduction with discriminant models.