Information Technology Reference
In-Depth Information
4.2.2 Bound Optimization
4.2.2.1 SVM
map
SVM
map
[
36
] uses the framework of structured SVM [
17
,
29
] to optimize the eval-
uation measure AP.
Suppose
x
m
j
={
x
j
}
represents all the documents associated with the training
=
1
m
j
query
q
,
y
={
y
j
}
(
y
j
=
1, if document
x
j
is labeled as relevant;
y
j
=
0, other-
=
1
wise) represents the corresponding ground truth label, and
y
c
represents any incor-
rect label. Then SVM
map
is formulated as follows:
n
min
1
λ
n
2
ξ
(i)
2
w
+
i
=
1
y
c(i)
y
(i)
,
s.t.
∀
=
(4.15)
w
T
Ψ
y
(i)
,
x
(i)
≥
w
T
Ψ
y
c
(i)
,
x
(i)
+
AP
y
c
(i)
,
y
(i)
−
ξ
(i)
.
1
−
Here
Ψ
is called the joint feature map, whose definition is given as
Ψ(
y
,
x
)
=
(x
u
−
x
v
),
(4.16)
u,v
:
y
u
=
1
,y
v
=
0
Ψ
y
c
,
x
=
y
u
−
y
v
(x
u
−
x
v
).
(4.17)
u,v
:
y
u
=
1
,y
v
=
0
It has been proven that the sum of slacks in SVM
map
AP) from
above. Therefore, if we can effectively solve the above optimization problem, AP
will be correspondingly maximized. However, there are an exponential number of
incorrect labels for the documents, and thus the optimization problem has an ex-
ponential number of constraints for each query. Therefore, it is a big challenge to
directly solve such an optimization problem. To tackle the challenge, the active set
method is used in [
36
]. That is, a working set is maintained, which only contains
those constraints with the largest violations (defined below), and the optimization is
performed only with respect to this working set.
can bound (1
−
AP
y
c
,
y
+
w
T
Ψ
y
c
,
x
.
Violation
1
−
(4.18)
Then the problem becomes efficiently finding the most violated constraints for a
given scoring function
f(x)
w
T
x
. To this end, the property of AP is considered.
That is, if the relevance at each position is fixed, AP will be the same no matter
which document appears at that position. Accordingly, an efficient strategy to find
the most violated constraint can be designed [
36
], whose time complexity is only
O(m
log
m)
, where
m
is the number of documents associated with query
q
.
In [
5
,
6
,
19
], SVM
map
is further extended to optimize other evaluation measures.
Specifically, when the target evaluation measures are NDCG and MRR, the resultant
=
