Information Technology Reference

In-Depth Information

Fig. 2.5

Sum-of-margin

strategy

m
(i)

n

K

−

1

ξ
(i)

1

min
1

ξ
(i)
∗

j,k

2

2

w

+

λ

j,k
+

+

i

=

1

j

=

1

k

=

1

w
T
x
(i)

j

ξ
(i)

if
y
(i)

j

s.t.

−

b
k
≤−

1

+

j,k
,

=

k,

w
T
x
(i)

j

ξ
(i)
∗

j,k

if
y
(i)

j

−

b
k
≥

−

=

+

1

1
,

k

1
,

(2.12)

+

ξ
(i)

ξ
(i)
∗

j,k

j,k
≥

1
≥

0
,

0
,

+

1
,...,m
(i)
,i

j

=

=

1
,...,n,

k

=

1
,...,K

−

1
.

The second strategy is called the
sum-of-margins strategy
. In this strategy, some

additional thresholds
a
k
are introduced, such that for category
k
,
b
k
−
1
is its lower-

bound threshold and
a
k
is its upper-bound threshold. Accordingly, the constraints

become that for documents in category
k
,
w
T
x
(i
j
should exceed threshold
b
k
−
1
but

be smaller than threshold
a
k
, with certain soft margins (i.e., 1

ξ
(i)
∗

j,k

ξ
(i)

j,k
)

respectively. The corresponding learning process can be expressed as follows, from

which we can see that the margin term
k
=
1
(a
k
−

−

1
and 1

−

−

b
k
)
really has the meaning of

“margin” (in Fig.
2.5
,
(b
k
−

+

a
k
)
is exactly the margin between category
k

1 and

category
k
).

m
(i)

K
−

1

n

K
−

1

ξ
(i)

1

ξ
(i)
∗

j,k

min

(a
k
−

b
k
)

+

λ

j,k
+

+

k
=

1

i
=

1

j
=

1

k
=

1

s.t.

a
k
≤

b
k
≤

a
k
+
1
,

w
T
x
(i)

j

ξ
(i)

if
y
(i)

j

≤

a
k
+

j,k
,

=

k,

(2.13)

w
T
x
(i)

j

ξ
(i)
∗

j,k

if
y
(i)

j

≥

b
k
−

1
,

=

k

+

1
,

+

ξ
(i)

ξ
(i)
∗

j,k

2

w

≤

1
,

j,k
≥

0
,

1
≥

0
,

+

1
,...,m
(i)
,i

j

=

=

1
,...,n,

k

=

1
,...,K

−

1
.

Ideally in the above methods, one requires
b
k
(k

=

1
,...,K

−

1
)
to be in an

increasing order (i.e.,
b
k
−
1
≤

b
k
). However, in practice, since there are no clear con-

straints on the thresholds in the optimization problem, the learning process cannot

always guarantee this. To tackle the problem, Chu and Keerthi [
3
] propose adding

explicit or implicit constraints on the thresholds. The explicit constraint simply takes