  The goal of Ordinal Regression is to find a rule that ranks items from a
given set. Several learning algorithms to solve this prediction problem build
an ensemble of binary classifiers. Ranking by Projecting uses interdependent
binary perceptrons. These perceptrons share the same direction vector, but use
different bias values. Similar approaches use independent direction vectors and
biases. To combine the binary predictions, most of them adopt a simple counting
heuristics. Here, we introduce a novel cumulative sum scoring function to
combine the binary predictions. The proposed score value aggregates the
strength of each one of the relevant binary classifications on how large is the
item's rank. We show that our modeling casts ordinal regression as a Structured
Perceptron problem. As a consequence, we simplify its formulation and
description, which results in two simple online learning algorithms. The second
algorithm is a Passive-Aggressive version of the first algorithm. We show that
under some rank separability condition both algorithms converge. Furthermore,
we provide mistake bounds for each one of the two online algorithms. For the
Passive-Aggressive version, we assume the knowledge of a separation margin,
what significantly improves the corresponding mistake bound. Additionally, we
show that Ranking by Projecting is a special case of our prediction algorithm.
From a neural network architecture point of view, our empirical findings
suggest a layer of cusum units for ordinal regression, instead of the usual
softmax layer of multiclass problems.
