Data Mining: The Textbook

n	1	n n
^LD = i=1 ^λi ^−		i=1 j=1 ^λi^λj ^yi^yj ^K(		,		).	(11.1)
			^Xi		^Xj
	2

The number of Lagrangian parameters λ _i (or optimization variables) is equal to the number of training data points n, and the size of the kernel matrix K(X_i , X_j ) is O (n2). As a result, the coefficients of the entire optimization problem cannot even be loaded in main memory for large values of n. The SVMLight approach is designed to address this issue. This approach is mainly based on the following two observations:

1. 
   It is not necessary to solve the entire problem at one time. A subset (or working set) of the variables λ₁ . . . λ_n may be selected for optimization at a given time. Different working sets are selected and optimized iteratively to arrive at the global optimal solution.
   

2. 
   The support vectors for the SVMs correspond to only a small number of training data points. Even if most of the other training data points were removed, it would have no impact on the decision boundary of the SVM. Therefore, the early identification of such data points during the computationally intensive training process is crucial for efficiency maximization.
   

The following observations discuss how each of the aforementioned observations may be leveraged. In the case of the first observation, an iterative approach is used, in which the set of variables of the optimization problem are improved iteratively by fixing the majority of the variables to their current value, and improving only a small working set of the variables. Note that the size of the relevant kernel matrix within each local optimization scales with the square of the size q of the working set S_q, rather than the number n of training points. The SVMLight algorithm repeatedly executes the following two iterative steps until global optimality conditions are satisfied:

1. 
   Select q variables as the active working set S_q, and fix the remaining n − q variables to their current value.
   

2. 
   Solve L_D(S_q), a smaller optimization subproblem, with only q variables.
   

A key issue is how the working set of size q may be identified in each iteration. Ideally, it is desired to select a working set for which the maximum improvement in the objective