A Summary Of The Kernel Matrix, And How To Learn It Effectively Using Semidefinite Programming

Kernel-based learning algorithms are widely used in machine learning for problems that make use of the similarity between object pairs. Such algorithms first embed all data points into an alternative space, where the inner product between object pairs specifies their distance in the embedding space. Applying kernel methods to partially labeled datasets is a classical challenge in this regard, requiring that the distances between unlabeled pairs must somehow be learnt using the labeled data. In this independent study, I will summarize the work of G. Lanckriet et al.'s work on"Learning the Kernel Matrix with Semidefinite Programming"used in support vector machines (SVM) algorithms for the transduction problem. Throughout the report, I have provide alternative explanations / derivations / analysis related to this work which is designed to ease the understanding of the original article.

of the embedding space. The importance of this lies in the fact that since kernel-based learning algorithms extract all information needed from inner products of training data points in F, there is no need to learn a kernel function Φ over the entire sample space to specify the embedding of a finite training dataset. Instead, the finite-dimensional kernel matrix (also known as a Gram matrix ) that contains the inner products of training points in F is sufficient. There are, of course, statistical model selection problems to be addressed within this approach; in particular "which projected space efficiently linearly separates the data?" and consequently "which kernel should we use?". The answers to these questions determines the elements of the kernel matrix. While prior knowledge can be used to aid this kernel selection process (to some degree of success), G. Lanckriet et al. propose a method to learning the kernel matrix from data using semidefinite programming (SDP) techniques.
In their report, the main focus is on the problem of transduction -the problem of completing the labeling of a partially labeled dataset. Keep in mind that the unlabeled samples of the dataset for which the algorithm is to find a label, are specified a priori. Once again, this suggests that the algorithm need only to learn a set of entries in the Gram matrix, and not the kernel function itself. This finite-dimensional kernel matrix uses the available labels to learn a good embedding by minimizing an objective function over the space of positive semidefinite kernels. This embedding should exhibit certain properties that aim to entangle the learning of labeled and unlabeled data. The resulting kernel matrix can then be employed as part of any algorithm that uses kernel matrices. One example that the authors discuss in detail is the support vector machine (SVM), where they show this method yields a polynomial time algorithm in the number of test examples, whereas Vapnik's original method for transduction [8] scales exponentially in the number of test examples.
2.1. Statement of Intent. In this paper, I shall summarize a formal proof for G. Lanckriet et al.'s work [1] on "Learning the Kernel Matrix with Semidefinite Programming". In Section 4, I formally define the concepts of kernel-based learning algorithms. In Section 5, we shall review the basics of semidefinite programming along with laying out dual formulations, in Section 6 we look into how SDP is used in finding the optimal kernel matrix. In this section, we also see a specific application of this framework for automatically learning the 2-norm soft margin parameter τ = 1/C. Finally, in Section 7, I shall summarize the works presented findings. I have attempted to prove and or elaborate on some skipped over derivations in the appendices.

Notation
In the derivations below, vectors are represented using bold lower-case notation, e.g, v ∈ R n , and scalar values represented using lower-case italics, e.g., v 1 , v 2 , ..., v n . Matrices are represented using upper-case italics, e.g., X ∈ R m×n . For a square, symmetric matrix X, X 0 means that X is positive semidefinite, while X 0 means that X is positive definite. For a vector v, the notations v ≥ 0 and v > 0 are understood componentwise.

Kernel Methods
Kernel-based learning algorithms [2][3][4] work by taking the data from the input space X and embedding into a feature space F, then searching for linear relations in the resultant space. Kernel-based learning algorithms perform this embedding implicitly, forgoing the need to explicitly specify the function Φ : X → F and instead by requiring that pair-wise distances between each pair of points is specified (as given by their inner product). A primary advantange of this approach is that computing inner products in a feature space F is often much easier than computing the coordinates of the points themselves.
where Φ is a mapping from X to an (inner product) feature space F.
for some x 1 , · · · , x n ∈ X and some kernel function k. The kernel matrix is also known as the Gram marix.
In this paper and in the context of transduction, we are given a finite dataset X , and so the kernel matrix is finite and can specified in the following simple manner Proposition 1 Every positive semidefinite and symmtetric matrix is a kernel matrix. Conversely, every kernel matrix is symmetric and positive semidefinite. 1 Kernel-based algorithms such as Support vector machines seek out solutions that are affine functions in the feature space f (x) = w, Φ(x) + b for some weight vector w ∈ F. As long as the weight vector w can be expressed as a linear combination of the inputs For example in binary classification, a thresholded version of f (x), i.e. sign f (x) is used to classify objects as belonging to one class or another. Note, in the examples and proofs that follow, we assume maximum-margin classifiers are learning the best separating hyperplanes for accurately separating objects from two classes. As for multi-class margins, two prominent 1 Proof: Considering the general case of a kernel matrix, let Furthermore, kernel-based algorithms such as SVMs are so-called maximum margin (γ) classifiers, trying to find the boundary that has the most distance between objects of different classes. In Figure 1 we see various separating boundaries that cleanly divide objects from different classes into their corresponding buckets, but only the margin that has the maximum distance from objects of both class is chosen as the maximum-margin boundary, as it allows for more robustness in the face of new datapoints that may lie too close to the separating boundary. Geometrically, γ corresponds to the distance between the convex hulls of the each of the two classes [9] As is evident from Figure 1, the margin is inversly related to weights vector defining the separating boundary: margin = γ = 2 ||w|| 2 and so maximizing the margin is equivalent to minimizing this weight vector min w,b As discussed above, kernel methods attempt to find a function that is linear in the feature space F accurately separating instances of separate classes onto one or the other side of the function. In order for separating boundary to correctly find a boundary separating all samples, the optimization problem must optimize some criterion over all samples (i.e., each sample should somehow be included as a constraint). Here we look into several such criteria all of which are considered measures of separation of the labeled data. In addition to wanting to maximize the margin between objects of the two classes, kernel methods may allow a tolerance for misclassification. If no tolerance is allowed, the classifier is known as hard margin, whereas soft margin classifiers are those kernel methods that allow for misclassifications as incorporated in their optimization setup. Below we look into 3 criteria corresponding to different mesaures of separation / measures of performance.
Definition 3: Hard Margin Given a set S l = (x 1 , y 1 ), · · · , (x n , y n ) with labeled examples, the hyperplane (w * , b * ) that solves the optimization problem below realizes the maximal margin classifier with geometric margin γ = 1/||w * || 2 (assuming it exists). This margin is called the hard margin.
Primal formulation: Dual formulation 2 : , e is the n-vector of ones, α ∈ R n , and y = [y 1 , · · · , y n ] T . The n constraints in the primal follow straight from the fact that SVM would like to find a separable boundary that correctly (or with some margin of error) places each example on the proper side of the separable boundary; this means that each of the n datapoints must be evaluated against the boundary that the optimzation problem finds.
We observe that the optimization problem finds a solution ω H (K) to the hard margin problem if and only if the data is linearly separable in the transformed feature space F of the transformed datapoints, φ(x i ). As seen in practice, this may not hold, and so we look for an alternative optimization problem that allows for a some error. For this, we define the 1-norm and 2-norm soft margin problems as follows.
Primal formulation: Dual formulation: Intuitively, while the 2-norm loss penalizes outliers more than the 1-norm loss and so has slower convergance rate, it is both convex and smooth and so desirable to be used alongside a range of optimization problems.

4.1.
Generalized Performance Measure. The 3 definitions above have shown various formulations (primal & dual) for finding the optimal separating margin γ. Noting the similarities in the 3 dual formulations above, we define the generalized performance measure as Observe that each of the 3 formulations above are a special case of this general problem: . Given a kernel matrix K, this general optimization problem is able to find optimal parameters (i.e., w * , b * ) that result in the maximum margin γ between the samples, where pair-wise distances in the transformed feature space F are captured in K. As alluded to earlier, in the setting of transduction, we are not given labels for all samples, and so we cannot possibly have an accurate K. We can easily see that to find the maximum margin separator in a transduction setting, we are first required to search over a set K of kernel matrices K, and find the maximum margin for each K. We can alternatively think of this as finding the minimum ω C,τ (K) over all possible K matrices.
In the next sections, we shall describe the assumptions that assist in solving such a meta-/ nested optimization problem. First, we will review semidefinite programs, a partitcular type of optimization problem with special structure for which exists theoretically and emperically efficient interior-point algorithms to solve.

Semidefinite Programming
Semidefinite programming [10][11][12] deals with the optimization of convex functions over the convex cone of symmetric, positive semidefinite matrices P = X ∈ R p×p X = X T , X 0 or affine subsets thereof, characterized by affine or convex constraints on the optimization problem. As mentioned in the previous section, we aim to find an optimal kernel matrix K for the task of transduction, and P (and convex subsets of P) can be viewed as a search space for such possible kernel matrices. The key consideration in this paper is to specify a convex cost function that will enable us to find / learn the optimal kernel matrix using semidefinite programming.
where u ∈ R q is the vector of decision variables, c ∈ R q is the objective vector, and matrices F j i = (F j i ) T ∈ R p×p are given. An important property of each "linear matrix inequality" (LMI) F j (u) is that the set of u satisfying the LMI is a convex set. This property of each LMI constraint, along with the convexity of the affine constraint Au = b leads to the SDPs being a convex optimization problem. This seemingly specialized form of SDPs is important as it arises in a host of applications in optimization problems (either directly in this form, or through casting problems as an SDP using the Schur's Complement Lemma 3 ), and because there exist theoretically and emperically efficient interior-point algorithms to solve SDPs [11]. 3 Lemma 1 (Schur Complement Lemma) Consider the partitioned symmetric matrix where A, C are square and symmetric. If det(A) = 0, we define the schur complement of A in X by the matrix S = C − B T A −1 B. The Schur Complement Lemma states the following: Dual formulation: where Z is a symmetric matrix, of the same size as F (u). Observe that the Lagrangian function L(u, Z) = c T u + trace(ZF (u)) does indeed fullfill the same objective as the primal SDP formulation as we can see that where we have shown the above is a barrier for the primal SDP. As in non-SDP duality, we always have weak duality and can exchange the min and max to get We further have strong duality with a Slater-type condition stating that if the primal SDP is strictly feasible (i.e., ∃ u 0 s.t. F (u 0 ) ≺ 0) then p * = d * . Additionally, if the dual SDP 5 is also strictly feasible (i.e., ∃ Z 0 s.t. c i = −trace(ZF i ) ∀ i ∈ [q]), then both primal and dual optimal values are attained by the same optimal pair (u * , Z * ). 4 In the general case, an SDP with multiple LMI constraints and affine equilities can be reduced to the aforementioned form by elimination of affine constraints, and merging all LMIs into 1 using block matrices. 5 The dual is as follows: which can be re-written as the following problem.
which itself is an SDP. So the dual of a primal SDP is an SDP. We explain why this is important in the text.
We have seen that the primal and dual pair of an SDP are both SDPs, and assuming strict feasibility of both problems, solving the primal minimization problem and maximizing the dual problem are equivalent. This relationship is indeed what algorithms such as SeDuMi [13] exploit to simultaneously solve both the primal and dual, and then use the duality gap p * −d * as a stopping criterion. Equipped with interior-point methods [10] for solving SDPs, these methods have a worst-case complexity of O(q 2 p 2.5 ) where p refers to the dimensionality of F (u) ∈ R p×p and q is the number of block matrices in the reduced LMI. In subsequent sections, we will explain how this bound may be improved assuming certain constraints on the SDP.

Algorithms for Learning Kernels
Working in a transduction setting, we are given data that is partially labeled; the training set S ntr = (x 1 , y 1 ), · · · , (x ntr , y ntr ) is labeled, and the remainder (i.e., test set) T nt = x ntr+1 , · · · , x ntr+nt are unlabeled, and the aim is to predict the labels for the test samples. In such a setting, the optimizing the kernel is equivalent to choosing a kernel matrix of form By setting up the optimization problem to optimize over the "training-data block" K tr , we want to learn the optimal "mixed-data block" K tr,t and "test-data block" K t . What we mean to say is that training and test data blocks must somehow be entangled: tuning the entries in K that correspond to training data (i.e., optimizing their embedding) should automatically tune the test-data entries in some way as well. This can be achieved by constraining the search for optimal kernel to only a certain category of kernels to prevent overfitting the training data, and generalize well to unlabeled test data. For this, the authors consider 3 specific example search spaces K: Example 1: K ∈ K K ⊆ P (convex subset) P: the PSD cone where in examples 2 & 3, the set K = K 1 , · · · , K m are initial "guesses" of the optimal kernel matrix K = Σ m i=1 µ i K i . These initial guesses, i.e., K i s, can be selected from the class of well-known kernel matrices, e.g., linear, Gaussian or polynomial kernels with different kernel parameter values (e.g., slack variables, Gaussian kernel width, polynomial kernel rank, etc.). Elements of K could be chosen as rank-one matrices K i = v i v i T with v i some set of orthogonal vectors, or alternatively K i s can be a diverse set of possibly good Gram matrices using various heterogeneous data sources. In any case, the set of such K i s, i.e., K, lies on the intersection of a low-dimensional linear subspace with the positive semidefinite cone P. Note, the constraints K ⊆ P and K 0 (identical constraints) both arise from Proposition 1 where kernel matrices are positive semidefinite by definition.
Formulating the optimal kernel K as a linear combination of K i s has the interesting consequence that the optimization problem that tries to learn K need only to find optimal mixing parameters µ i ∀ i ∈ [m], instead of fine-tuning the parameters of each of K i using cross-validation. We shall see that restricting the mixing parameters to be non-negative leads to significantly reduced computational complexity for the optimization problem.
6.1. General Optimization Problem. Recall from Section 4.1 where we derived generalized performance measure (i.e., the general dual formulation) for the optimization problem when using any of the kernel methods (i.e., hard margin, 1-norm soft margin or 2-norm soft margin) for transduction. This had the form An important property of the generalized performance measure above is its convexity in K. This can be asserted by considering first that the objective function 2α T e−α T (G(K)+τ I n )α is an affine (and hence convex) function of K. Secondly, ω C,τ (K) is the pointwise maximum of such conex functions, and so is also convex. The remainder of the constraints 0 ≤ α ≤ C and α T y = 0 are obviously convex. Hence the general optimization problem below that minimizes the performance measure over a family K of kernel matrices K is convex.
Recall that in an earlier part of Section 6 (this section), we described 3 examples for how to entangle the learning of the training-data and test-data blocks to learn labels for the unlabeled samples by imposing additional constraints on K. These special forms of K allow us to cast and solve the general optimization problem efficiently as the following SDP 6 General optimization problem: min where λ ∈ R and ν, δ ∈ R ntr . We note that ν ≥ 0 ⇐⇒ diag(ν) 0 which means that contraint is an LMI and a proper SDP constraint; likewise for ν ≥ 0.
We now look into the 3 specific forms of K described above and compare performances and expected outcome.
We notice that if K = K 0 , the optimization problem is indeed an SDP in standard form, however, there are no constraints guaranteeing entanglement of learning training-data and test-data blocks. For example, K t = O where K t is the test-data block and O denotes the zero matrix satisfies all constraints and is a viable solution to the minimization problem, yet it does not carry any meaning in terms of labels for unlabeled data. Below, we look into other kernel families K that can enforce the desired entangled learning.
Solving this optimization problem in its standard SDP form can be done using generalpurpose programs such as SeDuMi [13]. As discussed in Section 5.1, the interior-point methods used to solve SDP problems are polynomial in time, however, have worst case complexity O (m + n tr ) 2 )(n 2 + n 2 tr )(n + n tr ) 0.5 or roughly O (m + n tr ) 2 n 2.5 with the assumptions in example 2. This itself is a major improvement over Vapnik's original method for transduction [8] that scales exponentially in the number of test examples. 6.4. Example 3: K = span K 1 , · · · , K m ∩ K 0 & positive linear combinations. With the additional assumption on Σ m i=1 µ i K i that µ ≥ 0, we can derive the following 7 Optimization problem: min where r inR m and trace(K i ) = r i . This SDP form is more special. In fact, it is a quadratically-constrained quadratic probem (QCQP), itself a type of second-order cone program, which is a special type of SDP [12]. QCQPs can be solve efficiently using either of the SeDuMi [13] Mosek [14] frameworks, which yield worst-case complexity O mn 3 tr . This is a major improvement over the worst-case complexity of the previous example that didn't assume positive linear combinations, and over the general SDP form where K 0. Additionally this constraint results in improved numerical stability -it prevents the algorithm from finding solutions that use large weights µ i with opposite sign that cancel.
Observe that each of the 3 margin criteria (i.e., hard margin, 1-norm soft margin or 2-norm soft margin) is a special case of the generalized performance measure ω C,τ (K tr ): ω H (K) = ω ∞,0 (hard margin), ω S1 (K) = ω C,0 (1-norm soft margin), ω S2 (K) = ω ∞,τ = 1 C (2norm soft margin). These can be used in conjunction with the 3 assumptions on the kernel family K to get appropriate SDP setups for different margins based on the problem at hand. Here we consider 1 example, that was an important open problem at the time G. Lanckriet et al. were publishing their work. 6.5. Learning the 2-norm Soft Margin Parameter. This section shows how the 2-norm soft margin parameter τ = 1/C of SVMs can be learned using SDP or QCQP. For details, please refer to the work of the authors [1] or those of De Bie et al. [15]. Recall the specific form of the 2-norm soft margin problem: Dual formulation: where τ = 1/C. Remember τ = 0 for both the hard margin and 1-norm soft-margin cases. Since in the dual formulation above, the identity matrix induced by the 2-norm appears in exactly the same wasy as other matrices in G(K), we can treat them in the same way and jointly optimize over K and τ to find the optimal dual formulation, i.e., minimize ω S2 (K tr ). Now the joint optimization problem is as follows, and the dual can be restated as the following SDP (similar to derivations in Section 6.1): General optimization problem: min Standard SDP Form: min K,τ,ν,λ,t t subject to trace(K + τ I n ) = c, K ∈ K G(K tr ) + τ I ntr e + ν + λy (e + ν + λy) T t 0 Now we impose assumptions on the family K just as we did in example 2 (Section 6.3) and example 3 (Section 6.4): Notice how example 2 directly reduces to example 3 if K single 0 which means automatically tuning the parameter τ = 1/C for a 2-norm soft margin SVM with a singular kernel K single . This suggests that even if we are not learning the kernel matrix (i.e., K just equals K single and not K = Σ m i=1 µ i K i ), this approach can be used to tune the 2-norm soft margin parameter τ = 1/C automatically, thus solving an important open problem of its time.

Conclusion
In this summary paper, we have described an application of semidefinite programming (SDP) in learning the kernel matrix used for support vector machines (SVM) algorithms. We first reviewed the basics of kernels-based learning algorithms, saw 3 different formulations of SVMs (i.e., hard margin, 1-norm soft margin, and 2-norm soft margin) and derived the a general dual form for all 3 cases which we called the generalized performance measure. Minimizing this generalized performance measure corresponded to maximizing the margin of the SVM classifier. Next we studied the specialized yet commonplace form of SDPs and derived the corresponding dual formulation and saw that it is also an SDP. Using this property, we noted that the primal and dual can be jointly optimized using the same general purpose optimization solver, to more efficiently minimize the duality gap (p * − d * ) used as a stopping criterion. This solver jointly optimized the primal-dual pair with complexity O (m + n tr ) 2 n 2.5 . At this point we had the tools to solve our main optimization problem, which was minimizing the generalized performance measure over a family of kernel matrices K. Here we looked into 3 specific families, and demonstrated that when optimizing over a family of kernels that are strictly a positive linear combination of well-known kernel matrices, possibly from heterogeneous sources, leads to a significant improvement in both the complexity (which was O mn 3 tr ) and numerical stability of the optimal results. Finally, the formulations above were used to propose a method for finding the optimal 2-norm soft margin parameter τ = 1/C, which solved an open problem of its time.

Appendix A -Hard Margin Dual Formulation
We start with: min and derive: max where the constraints can be re-written in the proper form for deriving the dual formulation: Finally to simplify notation, we define z i = y i Φ(x i ) and Z = [z 1 ; · · · ; z n ] T and write the n constraints and write them together in the form and this can be done because by Slater's condition we can see that the original minimization problem is strictly feasible. Alternative, we can see that the objective function is convex in w and concave in α and so the switching of min and max is justified. After swapping max and min, we can solve the inner optimization problem by taking derivative and setting to 0: Plugging back into the inner optimization function (the min problem), we get note that we still have the conditions α ≥ 0 and α T y = 0 that are conditions for the outer optimization function (the max problem). So now the overall optimization problem becomes: note that we can re-write α T 1 − α T ZZ T α 2 as 1α T 1 − α T ZZ T α without affect the maximizer of the optimization problem. Furthermore, note that ZZ T = y i y j k(x i , x j ) which is what we defined to be G(K). So the final formulation becomes: which is what we set out to get as the derived dual formulation.
The same process above can extended to derive the dual derivation of the 1-norm and 2-norm soft margins with slack variables.

Appendix B -SDP Formulation for General Optimization Problem
Assuming K 0, K = m i=1 µ i K i,tr , µ ≥ 0 We begin by substituting ω C,τ (K tr ) into the general optimization problem to get min K max α:0≤α≤C,α T y=0 2α T e − α T G(K tr ) + τ I ntr α subject to trace(K) = c K 0 where the second constraint K 0 can be omitted as it is implied by the last two constraints.
Recall that r inR m and trace(K i ) = r i . So the above can be re-written as: 2α T e − τ α T α − max i c r i α T G(K i,tr )α with reasoning: • r1: interchanging the min & max is justified because the objective is linear in µ (hence convex) and concave in α • r2: G(K i,tr ) = diag(y)K i,tr diag(y) from definitin where G(K) is defined by G ij (K) = y i y j [K] ij = y i y j k(x i , x j ) This can finally be fomulated as: