Y. Altun, D. McAllester, M. Belkin
Many real-world classiﬁcation problems involve the prediction of multiple inter-dependent variables forming some structural depen- dency. Recent progress in machine learning has mainly focused on supervised classiﬁcation of such structured variables. In this paper, we investigate structured classiﬁcation in a semi-supervised setting. We present a discriminative approach that utilizes the intrinsic ge- ometry of input patterns revealed by unlabeled data points and we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our for- mulation naturally extends to new test points.