  We investigate the generalization properties of a self-training algorithm
with halfspaces. The approach learns a list of halfspaces iteratively from
labeled and unlabeled training data, in which each iteration consists of two
steps: exploration and pruning. In the exploration phase, the halfspace is
found sequentially by maximizing the unsigned-margin among unlabeled examples
and then assigning pseudo-labels to those that have a distance higher than the
current threshold. The pseudo-labeled examples are then added to the training
set, and a new classifier is learned. This process is repeated until no more
unlabeled examples remain for pseudo-labeling. In the pruning phase,
pseudo-labeled samples that have a distance to the last halfspace greater than
the associated unsigned-margin are then discarded. We prove that the
misclassification error of the resulting sequence of classifiers is bounded and
show that the resulting semi-supervised approach never degrades performance
compared to the classifier learned using only the initial labeled training set.
Experiments carried out on a variety of benchmarks demonstrate the efficiency
of the proposed approach compared to state-of-the-art methods.
