CLASS IMBALANCE AND ACTIVE LEARNING - Imbalanced Learning: Foundations, Algorithms, and Applications - page 109

classes by the largest margin. This hyperplane is obtained by minimizing the
following objective function:

N

1

2 w · w T

min
w ,b,ξ i

+ C ξ i (6.1)

i = 1

subject to ∀ iy i ( w T (x i ) − b) ≥

1 − ξ i

(6.2)

∀ iξ i ≥ 0

where w is the norm of the hyperplane, b is the offset, y i are the labels, ( ) is

the mapping from input space to feature space, and ξ i are the slack variables that
permit the non-separable case by allowing misclassification of training instances.
In practice, the convex quadratic programming (QP) problem in Equation 6.1 is
solved by optimizing the dual cost function. The dual representation of Equation
6.1 is given as

·

N

2
i,j

1

max W(α) ≡ α i − α i α j y i y j K( x i , x j ) (6.3)

i = 1

subject to ∀ i 0 ≤ α i ≤ C (6.4)

i = 1 α i y i = 0

where y i are the labels, ( · ) is the mapping from the input space to the fea-
ture space, K( x i , x j ) = ( x i ), ( x j ) is the kernel matrix, and the α i 's are the

Lagrange multipliers , which are nonzero only for the training instances that fall
in the margin. Those training instances are called support vectors and they define
the position of the hyperplane. After solving the QP problem, the norm of the
hyperplane w can be represented as

n

w = α i (x i ) (6.5)

i = 1

6.3.2 Margin-Based Active Learning with SVMs
Note that in Equation 6.5, only the support vectors affect the SVM solution.
This means that if SVM is retrained with a new set of data that consist of only
those support vectors, the learner will end up finding the same hyperplane. This
emphasizes the fact that not all examples are equally important in training sets.
Then the question becomes how to select the most informative examples for
labeling from the set of unlabeled training examples. This section focuses on a
form of selection strategy called margin-based AL . As was highlighted earlier,
in SVMs, the most informative example is believed to be the closest one to
the hyperplane as it divides the version space into two equal parts. The aim