Item

Abstract

We consider the classification problem on a finite set of objects.
Some of them are labeled, and the task is to predict the labels of
the remaining unlabeled ones. Such an estimation problem is
generally referred to as transductive inference. It is well-known
that many meaningful inductive or supervised methods can be
derived from a regularization framework, which minimizes a loss
function plus a regularization term. In the same spirit, we
propose a general discrete regularization framework defined on
finite object sets, which can be thought of as the discrete
analogue of classical regularization theory. A family of
transductive inference schemes is then systemically derived from
the framework, including our earlier algorithm for transductive
inference, with which we obtained encouraging results on many
practical classification problems. The discrete regularization
framework is built on the discrete analysis and geometry developed
by ourselves, in which a number of discrete differential operators
of various orders are constructed, which can be thought of as the
discrete analogue of their counterparts in the continuous case.