TrIK-SVM : an alternative decomposition for kernel methods in Krein spaces
Gaëlle Loosli












TrIK-SVM : an alternative decomposition for kernel methods in Kreĭn spaces
    Gaëlle Loosli^1,2









1- PobRun 

Brioude, France 




2- UCA - LIMOS UMR 6158 CNRS  

Clermont-Ferrand, France


    December 30, 2023
==========================================================================================================================




The proposed work aims at proposing a alternative kernel decomposition in the context of kernel machines with indefinite kernels. The original paper of KSVM (SVM in spaces) uses the eigen-decomposition, our proposition avoids this decompostion. We explain how it can help in designing an algorithm that won't require to compute the full kernel matrix. Finally we illustrate the good behavior of the proposed method compared to KSVM.





§ INTRODUCTION
 

Learning with indefinite kernels is a question that has been treated many times since the introduction of the hyperbolic tangent kernel (tanh) in the libsvm toolbox <cit.>. This particular kernel has never really shown its practical interest, but many other cases of indefinite kernels have been published, such as graph kernels or similarity based kernels <cit.>. In those cases, the need for an indefinite kernel is driven by the application field and the cost of avoiding the indefiniteness can be huge in terms of accuracy <cit.>.
On the theoretical side, <cit.> have shown that learning with an indefinite kernel implies learning in reproducing kernel Kreĭn spaces (RKKS), in which basically the scalar product between a vector and itself can be negative.
In <cit.>, the KSVM algorithm is proven to produce a valid solution in an RKKS, even though the optmization in those spaces is not well defined.

We anchor our work in the same framework, and we propose an upgraded algorithm for KSVM, named TrIK-SVM.









§ ESSENTIALS OF RKKS


A Kreĭn space is a vector space in which the dot product of two identical vectors can provide a negative value. A well-known example of a Kreĭn space is the complex space, in which this property is denoted by i^2 = -1.
In the learning context, it has been shown that trying to optimize a quadratic program (for instance an SVM) using an indefinite kernel matrix is actually a stabilization problem in a Reproducing Kernel Kreĭn space <cit.>.Those spaces are indefinite inner product spaces endowed with a Hilbertian topology without any requirement of positive-definiteness.

definitionspace <cit.>
 An inner product space (, ⟨ . , . ⟩_) is a space if there exists two Hilbert spaces ℋ_+, ℋ_- spanning 𝒦, with f_+∈ℋ_+
  and f_-∈ℋ_-, such that

    |
      [                                      ∀ f ∈𝒦                                f = f_+⊕ f_-;                                    ∀ f,g ∈𝒦 ⟨ f,g⟩_𝒦 =  ⟨ f_+,g_+⟩_ℋ_+ - ⟨ f_-,g_-⟩_ℋ_-;                                             ].


In a nutshell, we provide here the essential facts that can be found in details in the above-cited literature:

  
  * If (,⟨ .,. ⟩) and  (,-⟨ .,. ⟩) are RKHS, =  + is an RKKS.
  
  * There is a representer thoerem in a RKKS, and the decomposition of the reproducing kernel k = k_+ - k_- consists of reproducing kernels in the associated RKHS.
  
  * Any symmetric indefinite kernel can be decomposed in k_+ and k_- and associated to an RKKS
  
  * This decomposition is not unique

Solving a quadratic program in an RKKS () is a stabilization problem that cannot be directly solved. However, it can be reformulated as an equivalent minimization problem <cit.> lying in an associated RKHS () defined as the sum of the positive () and negative () parts of the RKKS. The solution of the minimization problem lies in  and thus needs to be projected back to .

While the original paper shows the interest of KSVM considering the accuracy of the method on a large variety of problems,

 KSVM is not used in practice.
Indeed, it suffers from several major practical drawbacks: it requires to compute the eigen-decompostion of the matrix (computation time and stability issues) and the final solution is full (the sparsity is lost during the projection) back to the RKKS.
Recently, several papers dealing with indefinite matrices have noted those drawbacks and proposed alternative methods. Essentially, some paper are proposing minimization methods that ignore the stabilization problem <cit.> and others rely on using kernel as features, which is a way to embed the RKKS in an RKHS <cit.>. The first category of methods are likely to provide an admissible but not optimal solution in the RKKS. The second category usually works pretty well but might hide some information from the negative part. One can note a major improvement over KSVM in terms of computational complexity, brought in <cit.> in the form of a carefully approximated version, based on kernel approximation, partial eigen-decomposition and CVM algorithm. The final solution is also approximated in order to be sparser <cit.>.




  
The stabilization problem
We recall here the stabilization problems in both RKKS and RKHS to exhibit the place of the kernel decomposition that will be discussed later.
Let { x_i ∈𝒳, y_i ∈ [-1,1], ∀ i ∈ [1,…,ℓ] } be a binary training set, and τ an hyper-parameter for error penalization, the following problem aims at finding coefficients α_i (∀ i ∈ [1,…,ℓ])  and a bias b such
that the decision function D(x) = sign(f(x) + b) with f(x)= ∑_i=1^ℓα_i y_i k(x_i ,x).
The equivalent minimization problem is formulated by replacing f by , such that
⟨,⟩ = ⟨,⟩_ + ⟨,⟩_ and =  +.
Then the equivalent minimization problem to eq.<ref> becomes:




    [ {[             f ∈, b ∈           1/2⟨ f,f⟩_;                             ∑_i=1^ℓmax(0,;                      (1-y_i(f(x_i)+b)))≤τ ]. {[               ∈, b ∈              1/2⟨,⟩_;                             ∑_i=1^ℓmax(0,;                      (1-y_i((x_i)+b))) ≤τ ]. ]

The dual can be calculated as a usual SVM and it lets the modified kernel matrix =  + appear :

    {[                           -1/2^⊤Y( + )Y + ^⊤1;                                       ^⊤y = 0;                        0≤_i ≤ C   ∀ i ∈ [1…ℓ] ].

Y is the diagonal matrix of labels y. This problem provides a solution that needs to be projected in the space and all the previous computations are independent of the choice of the decomposition.





§ TRIK-SVM


Our new algorithm aims at solving eq.<ref> in a more efficient way than KSVM. First let's detail the KSVM decomposition <cit.>, which is naturally based on the eigen-decomposition of the kernel matrix. Then we give the new decomposition.




  
KSVM "flip" Decomposition
Let U and D be respectively the eigenvectors and the diagonal matrix containing the eigenvalues ok the kernel matrix K, such that K = U^⊤DU.
The modified semi-definite positive (SDP) kernel associated to K is defined as = U|D|U^⊤ where |U| contains the absolute values of U. In this case, = U max(D, 0)U^⊤ and = -U min(D, 0)U^⊤.




  
TrIK-SVM "shift" Decomposition
Admitting we know the most negative eigenvalue of the kernel matrix, denoted λ:

    K = (K - λ I) + λ I

with I the identity matrix. Checking that = K - λ I and = -λ I are both SDP matrices is straight forward. Then the modified SDP
kernel becomes = K - 2λ I.





  
Transition matrices
Transition matrices are used to project either the kernel matrix or the solution back and forth between the RKKS and the RKHS.

    [                                                                                                               KSVM                                                                                                           TrIK-SVM;                  [  = U_+ U_+^⊤ =  U_- U_-^⊤;       P =  -             ;      = USU^⊤  S = sign(D);              ] [ = (K-λ I)K^-1 = I - λ K^-1;                   = λ K^-1;     P =  -  = I - 2 λ K^-1;                            ] ]






  
Algorithm
Based on the transition matrix, the algorithm of KSVM is very simple, it consists in projecting the indefinite kernel matrix K into the RKHS (), solve a regular SVM and project the obtained solution  back to the RKKS (α).
The most straight forward way to use the proposed decomposition is to apply it directly, similarely to the KSVM algorithm. However doing so suffers from severe numerical unstabilities.
Instead we observe that the proposed decomposition can be applied in a rank-one fashion. This features makes it possible to design a solver that can compute the kernel elements on the fly and produce directly a solution in the RKKS.





 §.§ TrIK-SVM algorithm



We propose here a dedicated solver that computes at each step both the solution in a RKHS and in the
RKKS, so that gradient steps are performed in the minimization setting and optimality conditions are
checked in the RKKS. The algorithm is based on a active set method <cit.>.
The algorithm iteratively checks dual or primal constraints and updates the solution after each modification of the support vector set.
The dual checking deals with bounds on : in case of a bound violation, the corresponding point
is removed from the set of support vectors. The primal checking deals with the good classification
constraint: in case of a violation, it means that there remains some misclassified training examples
and one is picked to be added to the set of support vectors.
Algorithm <ref> gives the global scheme in which we insert the indefiniteness treatment. Steps [1.] and
[3.] are modified while step [2.] will not.
In the following, we present in parallel the hard-margin case (HM) and the soft-margin case (SM).


Bounded support vectors are subscripted (bsv) and free support vectors are subscripted (sv).
Matrices  and  are the labeled versions of  and  (G = Y  Y).





Step [1.] The idea is to compute at each step both  (already done) and α. Originally, this step, restricted to examples that are in the
set of current support vectors, consists in computing b (see <cit.> for details) and .
Introducing our kernel decomposition, and noting that only diagonal terms are different between  and , we obtain that α_sv = (I - 2λ^-1_sv,sv)_sv.




    [                                            (HM)                                            (SM);                        _sv,sv_sv+ b y_sv = 1_sv       _sv,sv_sv + C _sv,bsv1_bsv+ b y_sv = 1_sv;                            = ^-1(1_sv - b y_sv)                 = ^-1(1_sv - C_sv,bsv - b y_sv);                _sv,sv P_sv,sv_sv+ b y_sv = 1_sv _sv,svP_sv,sv_sv+ C _sv,bsv1_bsv+ b y_sv = 1_sv;                                α_sv= P_sv,sv_sv                                α_sv= P_sv,sv_sv ]



Step [2.] This step aims at checking the dual admissibility, ie. checking that all _i ≥ 0 and
projecting the solution in the admissible set if it is not. Since in the RKKS α is not constrained <cit.>, this step can only be
performed in the RKHS.

Step [3.] This last step is performed once the current set of support vector gives an admissible
solution in the dual. Its goal is to check the optimality in the primal by verifying that all non support
vectors are well classified, which has to be true in the RKKS.

Using the modified steps in the original algorithm, we can compute values for  and  on the fly, or
use a cache strategy for more efficiency. Since both solutions are computed on the SV set at each
step, the output α can be sparse.






 §.§ Experimental evaluation of TrIK-SVM



KSVM has already proven its interest, so the goal of the presented experiments is to check that TrIK-SVM behaves at least as well as KSVM.
We took randomly generated dataset (based on ake_blobs in scikit-learn) in
dimension 5 with 4 centers (2 are assigned to class -1, 2 are assigned to class 1, at random). Resulting
problems may be almost separable and others very overlapping.






  
Sensitivity to λ
The first point to check about our decomposition is linked to the fact that we claim
that any value under the least eigenvalue of the spectrum will produce a valid decomposition. If it’s
true on the paper, one might wonder on the numerical effect. Figures <ref> illustrate the stability of the
solution in the RKKS independently of λ. We run TrIK-SVM on one randomly picked dataset, with
different values of λ, starting from the true least eigenvalue up to 20 times this value. We report the α
and  values for each λ.










  
TrIKSVM vs KSVM
The instabilities due to the eigen-decomposition in KSVM are
more easily observed for datasets with many similar training points. In our experiments, it happens
more often than for real datasets, since all training point are picked in a restricted space.
Figure <ref> present an illustrative result of the accuracy performance of TrIK-SVM and KSVM. We
observe that TrIK-SVM is competitive over KSVM, which suffers from numerical instabilities. We
also plot on figure <ref> the corresponding training time for each, on loglog axis. At first sight the advantage of TrIK-
SVM is not obvious, but we need to mention that here, KSVM is internally using libsvm which is
fully optimized, while the current TrIK-SVM implementation is fully implemented in Python without
any trick and pre-computes the complete kernel, so there’s space for improvement.






















§ CONCLUSION



This paper introduces a novel algorithm called TrIK-SVM that solves most of the KSVM limitations:
it provides a sparse solution, that can be computed without pre-computing the full kernel matrix
and thus that can benefit from advanced cache strategies. Since the hyper-parameter λ does not
influence the quality of the solution neither the computation time, given that it is sufficiently negative,
TrIK-SVM comes without additional parameter to tune compared to a classical SVM.
Future work includes application to problems others than binary classification, including Multiple Kernel Setting, and a more efficient implementation of the proposed algorithm.











unsrt








