  In multiclass semi-supervised learning (SSL), it is sometimes the case that
the number of classes present in the data is not known, and hence no labeled
examples are provided for some classes. In this paper we present variants of
well-known semi-supervised multiclass learning methods that are robust when the
data contains an unknown number of classes. In particular, we present an
"exploratory" extension of expectation-maximization (EM) that explores
different numbers of classes while learning. "Exploratory" SSL greatly improves
performance on three datasets in terms of F1 on the classes with seed examples
i.e., the classes which are expected to be in the data. Our Exploratory EM
algorithm also outperforms a SSL method based non-parametric Bayesian
clustering.
