Information Technology Reference

In-Depth Information

Fig. 2.1
Square loss as a

function of
y
j
−
f(x
j
)

2.2.1 Subset Ranking with Regression

Cossock and Zhang [
5
] solve the problem of ranking by reducing it to regression.

Given
x

m

j

1
, a set of documents associated with training query
q
, and the

ground truth labels
y

={

x
j
}

=

m

j
=

1
of these documents in terms of multiple ordered

categories, suppose a scoring function
f
is used to rank these documents. The loss

function is defined as the following square loss,

={

y
j
}

x
j
,y
j
)
=
y
j
−
f(x
j
)
2
.

L(f

;

(2.1)

The curve of the square loss is as shown in Fig.
2.1
. From the figure one can

see that if and only if the output of the scoring function
f(x
j
)
exactly equals the

label
y
j
, there is no loss. Otherwise the loss increases in a quadratic order. In other

words, for a relevant document, only if the scoring function can exactly output 1,

there will be zero loss. Otherwise if the output is 2 which seems to be an even

stronger prediction of relevance for this document, there will be some loss. This is,

in some sense, not very reasonable.

As an extension of the above method, an importance weighted regression model

is further studied in [
5
]. The weights help the new model focus more on the regres-

sion error on the relevant documents (which are more likely to appear on top of the

ranking result). Furthermore, the introduction of regularization terms to the regres-

sion loss is also investigated, which aims at making the method more generalizable

(i.e., perform better on unseen test data).

In addition to the proposal of the methods, theoretical analysis on the use of the

square loss function is also performed in [
5
]. The basic conclusion is that the square

loss can upper bound the NDCG-based ranking error (see Chap. 5 for more details).

However, according to the above discussions, even if there is a large regression loss,

the corresponding ranking can still be optimal as long as the relative orders between

the predictions
f(x
j
)
(
j

=

1
,...,m
) are in accordance with those defined by the

ground truth label. As a result, we can expect that the square loss is a loose bound

of the NDCG-based ranking error.