A Robust Learning-Based Detection and Tracking Algorithm - Technologies and Applications of Artificial Intelligence - page 287

Fig. 3. Flowchart of region-graph algorithm

a given support pattern x i , only the support vector ( x i ,y i ) will have ʲ y i i > 0
and we refers this as positive support vectors, while any other support vectors
( x i ,y ) ,y = y i , will have ʲ y i i < 0 and we refers this as negative support vectors.
The main step in this optimization step is a Sequential Minimal Optimization
(SMO)-style step [16]. SMO is an algorithm that improves Lagrangian dual form
with respect to a pair of coecients ʲ y +
i

and ʲ y −
i

,where ʲ y +

i is positive support
vector and ʲ y i is negative support vector. The coecients must be modified by
opposite amounts, ʲ y +
i

ʲ y +
i

+ ʻ, ʲ y −
i

ʲ y −
i

ʻ because of the constraint
y ʲ i = 0, leading to an one-dimensional maximization in ʻ [1].
TheSMOstepusetooptimizethe( i,y + ,y − ) in this online learning algorithm.
Given the chosen i,y + ,y − , we will define the most ecient search direction with
the highest gradient. This gradient will represent a single coecient of the dual
form.

← ← −

2.4 Budgeting Algorithm

The problem occurs when the number of support vector increase over time. Fur-
thermore, when evaluating discriminant function d ( x, y ) will take a high com-
putational cost because it requires evaluating kernel function for each support
vectors. This means that the storage costs grow linearly with the number of
support vectors.
In this approach, we implement a budget maintenance adapted from [1] which
choose a fixed budget so that the support vectors cannot exceed a specified limit.
If a new support vector need to be added but the budget is already full, this
method will choose an appropriate support vector that need to be kept and
another support vectors that need to be removed.