Information Technology Reference
In-Depth Information
Fig. 3.1
Loss function
in [ 12 ]
and x v associated with a training query q , the loss function is defined below,
= |
y u,v
h(x u ,x v )
|
L(h
;
x u ,x v ,y u,v )
,
(3.1)
2
where the hypothesis is defined as h(x u ,x v ) = t w t h t (x u ,x v ) and h t (x u ,x v ) is
called the base preference function.
Suppose h(x u ,x v ) takes a value from
, where a positive value indicates
that document x u is ranked before x v , and a negative value indicates the opposite.
According to the above loss function, we can easily find that if the ground truth label
indicates that document x u should be ranked before document x v (i.e., y u,v =
[−
1 , +
1
]
1)
but h(x u ,x v )
1, there will be a loss for this pair of documents. Similarly, if the
ground truth label indicates that document x u should be ranked after document x v
(i.e., y u,v =−
=
1) but h(x u ,x v )
= −
1, there will also be a loss. The curve of the above
loss function is shown in Fig. 3.1 .
With the above loss function, the weighted majority algorithm, e.g., the Hedge
algorithm, is used to learn the parameters in the hypothesis h . Note that the hypoth-
esis h is actually a preference function, which cannot directly output the ranked list
of the documents. In this case, an additional step is needed to convert the pairwise
preference between any two documents to the total order of these documents. To
this end, one needs to find the ranked list σ , which has the largest agreement with
the pairwise preferences. This process is described by
=
σ
max
π
h(x π 1 (u) ,x π 1 (v) ).
(3.2)
u<v
As we know, this is a typical problem, called rank aggregation. It has been proven
NP-hard to find the optimal solution to the above optimization problem. To tackle
the challenge, a greedy ordering algorithm is used in [ 12 ], which can be much more
efficient, and its agreement with the pairwise preferences is at least half the agree-
ment of the optimal algorithm.
One may have noticed a problem in the above formulation. When defining the
loss function for learning, attention is paid to the preference function. However,
Search WWH ::




Custom Search