Exploiting Monotonicity Constraints in Active Learning for Ordinal Classification

We consider ordinal classication and instance ranking problems where each attribute is
known to have an increasing or decreasing relation with the class label or rank. For example,
it stands to reason that the number of query terms occurring in a document has a positive
in
uence on its relevance to the query. We aim to exploit such monotonicity constraints by
using labeled attribute vectors to draw conclusions about the class labels of order related
unlabeled ones. Assuming we have a pool of unlabeled attribute vectors, and an oracle
that can be queried for class labels, the central problem is to choose a query point whose
label is expected to provide the most information. We evaluate dierent query strategies
by comparing the number of inferred labels after some limited number of queries, as well as
by comparing the prediction errors of models trained on the points whose labels have been
determined so far. We present an ecient algorithm to determine the query point preferred
by the well-known active learning strategy generalized binary search. This algorithm can be
applied to binary classication on incomplete matrix orders. For non-binary classication,
we propose to include attribute vectors in the training set whose class labels have not been
uniquely determined yet. We perform experiments on articial and real data.