We present four new feature selection methods for ordinal regression and test them against four di erent baselines on two large datasets of product reviews.
In (text) classi cation, feature selection (FS) consists in identifying a subset S T of the original feature set T such that jSj jT j ( = jSj=jT j being called the reduction level ) and such that S reaches the best compromise between (a) the e ectiveness of the resulting classi ers and (b) the e ciency of the learning process and of the classi ers. While feature selection has been extensively investigated for standard classi cation, it has not for a related and important learning task, namely, ordinal classi cation (OC { aka ordinal regression). OC consists in estimating a target function : D ! R mapping each object di 2 D into exactly one of an ordered sequence R = hr1 : : : rni of ranks, by means of a function ^ called the classi er.
We here address the problem of feature selection for OC.
We use a \ lter" approach, in which a scoring function Score
is applied to each feature tk 2 T in order to measure the
predicted utility of tk for the classi cation task (the higher
the value of Score, the higher the predicted utility), after
which only the jSj top-scoring features are retained. We
have designed four novel feature scoring functions for OC,
and tested them on two datasets of product review data,
using as baselines the only three feature scoring functions for
OC previously proposed in the literature, i.e., the probability
redistribution procedure (PRP) function proposed in [
FEATURE SELECTION FOR OC
Our rst method, V ar IDF , is a variant of the V ar method
described in [
V ar(tk) (IDF (tk))a (1) where IDF is the standard inverse document frequency and a is a parameter (to be optimized on a validation set) that allows to ne-tune the relative contributions of variance and IDF to the product. Given that V ar(tk) = 0 implies that Score(tk) = 0, we smooth V ar(tk) by adding to it a small value = 0:1 prior to multiplying it by IDF (tk).
Our second method, RR(V ar IDF ), is a variant of V ar IDF meant to prevent it from exclusively catering for a certain rank and disregarding the others. It consists in (i) provisionally \assigning" each feature tk to the rank closest to the mean of its distribution across the ranks; (ii) sorting, for each rank rj , the features provisionally assigned to rj in decreasing order of their value of the Score function of Equation 1; and (iii) enforcing a \round robin" policy in which the n ranks take turns, for nx rounds, in picking their favourite features from the top-most elements of their rankspeci c orderings.
Our third method, RR(IGOR), is based on the idea of viewing ordinal classi cation on R = hr1 : : : rni as the generation of (n 1) binary classi ers j , each of which is in charge of separating Rj = fr1; : : : ; rj g from Rj = frj+1; : : : ; rng, for j = 1; : : : ; (n 1). For each feature tk we thus compute (n 1) di erent values of IG(tk; cj ) (the classic information gain function of binary classi cation), by taking cj = r1 [ : : : [ rj and cj = rj+1 [ : : : [ rn, for j = 1; : : : ; (n 1). Similarly to RR(V ar IDF ), we (i) sort, for each of the (n 1) binary classi ers j , the features in decreasing order of IG(tk; cj ) value, and (ii) enforce a roundrobin policy in which the (n 1) classi ers j take turns, for nx 1 rounds, in picking their favourite features from the top-most elements of their classi er-speci c orderings.
Our fourth method, RR(N C IDF ), directly optimizes the chosen error measure E. Let us de ne the negative correlation of tk with rj in the training set T r as X
E( ~ j ; di) N CT r(tk; rj ) = fdi2T r j tk2dig
jfdi 2 T r j tk 2 digj where ~ j is the \trivial" classi er that assigns all di 2 D to rj and E( ^ ; di) represents the error that ^ makes in classifying di. Let the rank R(tk) associated to a feature tk be R(tk) = arg min N CT r(tk; rj ) rj2R 1.8 1.6 0.8
Amazon-83713
FFS Triv
Var RR(Var)
PRP RRIGOR
Var*IDF RR(Var*IDF) RR(NC*IDF) 0 20 80
100 40
60
Reduction Level where the a parameter serves the same purpose as in Equation 1. Similarly to the 2nd and 3rd methods, to select the best x features we apply a round-robin policy in which each rj is allowed to pick, among the features such that R(tk) = rj, the nx features with the best Score.
More details on these methods can be found in [
We have tested the proposed measures on two di erent datasets,
TripAdvisor-15763 and Amazon-83713, whose
characteristics are summarized in Table 1. Both datasets consist of
product reviews scored on a scale of one to ve \stars", and
(as shown by Table 1) are highly imbalanced. See [
As the evaluation measure we use the macroaveraged mean
absolute error (M AEM ), proposed in [
X j ^ (di) where T ej denotes the set of test documents whose true rank is rj and the \M" superscript indicates \macroaveraging".
We compare our methods with the three baselines mentioned at the end of Section 1 and with the \trivial baseline" that consists in scoring all test documents as 3 stars.
As a learning device we use -support vector regression
( -SVR) [
The results of our tests are displayed in Figure 1, in which
e ectiveness is plotted as a function of the tested
reduction level. For reasons of space only the Amazon-83713
results are displayed (see [