Feature Selection and Kernel Design via Linear Programming

1 Introduction and RelatedWork

The definition of a distance or a similarity function over the input or data space is fundamental in the performance of machine learning algorithms, both in terms of accuracy and efficiency. This can be easily verified by looking at the role that the distance or similarity plays in common algorithms (e.g., k-means, nearest neighbors, support vector machines or any other kernel method, etc.). However, since the concept of similarity depends on the task of interest (objects can be similar or dissimilar in many ways depending on the application), a similarity function that is appropriate for one task may not be appropriate for another. This task dependency has been noted in a number of approaches that seek to build these functions for a particular classification or regression model given some training data (e.g., [Cohen et al., 1998; Xing et al., 2002; Schultz and Joachims, 2003; Lanckriet et al., 2004; Athitsos et al., 2004]).

In this paper, we are interested in automatically finding good similarity functions after some basic information about the task of interest has been provided (e.g., by an expert user). Unlike approaches that rely on class labels (e.g., [Lanckriet et al., 2004]) or on building sets of points that are globally similar (or dissimilar) [Xing et al., 2002; Wagstaff et al., 2001], here we explore a simpler-to-specify form of user supervision: that provided by statements like object i is more similar to object j than to object k1 . We remark that we are not only interested on building functions that are consistent with this information provided by the user, but we are also interested in obtaining functions that are efficient to compute. Thus, in addition we focus on functions that can be evaluated by looking only at part of the features or input dimensions; therefore, implying some form of feature selection.

More formally, let us represent the objects of interest as points xk in a D-dimensional space ℜD , with k = {1, 2, ...,N}. We would like to obtain a function K : ℜD × ℜD → ℜ that satisfies the above similarity comparisons and that in addition can be well approximated by ˜K : ℜd × ℜd → ℜ which only uses d < D components of xk. For this we will rely on (Mercer) Kernel representations [Cristianini and Shawe-Taylor, 2000] and define K (similarly for ˜K) as a kernel K(x, y) = ∑j αjKj (x, y) where α ∈ ℜ; thus, K is a mixture of kernel functions 2 . Throughout this paper, we will work with this representation of similarity functions, define convex problems for obtaining K, and later extend this idea to focus on ˜K. Some of the motivation for the framework in this paper is related to earlier work in metric learning [Rosales and Fung, 2006]; however, here the focus is on a different problem, kernel design.

1 Example objects of interest include database records, user opinions, product characteristics, etc.

2 Note that K is any affine combination of kernels not just a convex combination. Also, we are not restricting Kj to be itself a kernel.

In this paper, we first show how relative constraints, involving triples of points of the form, K(xi, xj) > K(xi, xk) can be used to learn K. One can think of this first formulation as parallel to other approaches for learning K that rely on supervised learning with class labels (and, unlike the one presented here, are classification-algorithm dependent). These formulations involve solving a semidefinite programming problem (SDP) [Graepel, 2002; Lanckriet et al., 2004], but we show how a different Linear Programming formulation, introduced in this paper, is also sufficient in practice and much more efficient computationally (e.g., it can be use to solve much larger problems, faster). In addition, we extend this formulation to consider the issue of representation/evaluation efficiency based on a form of feature selection. This formulation leads to a linear programming approach for solving the kernel design problem that also optimizes for succinct feature representations.

1.1 Kernel Design

In recent years the idea of kernel design for learning algorithms has received considerable attention in the machine learning community. Traditionally, an appropriate kernel is found by choosing a parametric family of well-known kernels, e.g., Gaussian or polynomial, and then learning a generally sub-optimal set of parameters by a tuning procedure. This procedure, although effective in most cases, suffers from important drawbacks: (1) calculating kernel matrices for a large range of parameters may become computationally prohibitive, especially when the training data is large and (2) very little (to none) prior knowledge about the desired similarity can be easily incorporated into the kernel learning procedure.

More recently, several authors [Bennett et al., 2002; Lanckriet et al., 2004; Fung et al., 2004] have considered the use of a linear combination of kernels that belong to a family or superset of different kernel functions and parameters; this transforms the problem of choosing a kernel model into one of finding an optimal linear combination of the members of the kernel family. Using this approach there is no need to predefine a kernel; instead, a final kernel is constructed according to the specific classification problem to be solved. In this paper we also use a mixture model representation 3 ; however, our approach does not depend on and is not attached to any specific machine learning algorithm (for classification, regression, inference, etc). Instead, inspired by the fact that most kernels can be seen as similarity functions, we rely on explicit conditions on similarity values among subset of points in the original training dataset; this is, our formulation allows the user to explicitly ask for conditions that have to be satisfied or reflected in the desired kernel function to be learned.

1.2 Relative Similarity Constraints

As explained above, we concentrate on examples of proximity comparisons among triples of objects of the type object i is more like object j than object k. In choosing this type of relative relationships, we were inspired primarily by [Athitsos et al., 2004; Cohen et al., 1998; Schultz and Joachims, 2003; Rosales and Fung, 2006], where these relationships are defined with respect to distances or rankings. The use of relative similarity constraints of this form for kernel design offers different challenges. Note that we are not interested in preserving absolute similarities, which are in general much more difficult to obtain (absolute similarities imply relative similarities, but the converse is not true).

3 But note that the elements of the mixture could be functions that are not kernels.

One important observation for kernel design is that the kernel conditions implied by these relationships are linear relationships among individual kernel entries in the kernel matrix (defined over the points of interest) and can be expressed as linear constraints. In addition to this, unlike any of the methods referred to above, by restricting the kernel family to have only kernels that depend in one original feature at the time, we are able to learn kernels that depend on a minimal set of the original features. This can be seen as implicitly performing feature selection with respect to the original data space. In combination with the benefits of a new linear programming approach, the formulation proposed in this paper has a unique set of attributes with significant advantages over recent approaches for kernel design.

1.3 Notation and background

In the following, vectors will be assumed to be column vectors unless transposed to a row vector by a superscript ⊤. The scalar (inner) product of two vectors x and y in the ddimensional real space ℜd will be denoted by x⊤y. The 2norm and 1-norm of x will be denoted by ‖x‖2 and ‖x‖1 respectively. A column vector of ones of arbitrary dimension will be denoted by ⃗e, and one of zeros will be denoted by ⃗0. A kernel matrix for a given set of points will be denoted by K, individual components by Kij, and kernel functions by K() or simply K.

2 A Linear programming formulation for kernel design

2.1 Using a linear combination of Kernels

Let us say we are given a set of points xk ∈ ℜD with k = {1, ..., N} for which an appropriate similarity function is unknown or expensive to compute. In addition we are given information about a few relative similarity comparisons. Formally, we are given a set T = {(i, j, k)|K(xi, xj) > K(xi, xk)} for some kernel function K. The kernel K is not known explicitly, instead a user may only be able to provide these similarity relationships sparsely or by example. We are interested in finding a kernel function K() that satisfies these relationships.

For the rest of the paper, let us suppose that instead of the kernel K being defined by a single kernel mapping (e.g., Gaussian, polynomial, etc.), the kernel K is instead composed of a linear combination of kernel functions Kj, j = {1, . . . , k}, as below:

As pointed out in [Lanckriet et al., 2004], the set Ω = {K1(x, y), . . . , Kk(x, y)} can be seen as a predefined set of initial guesses of the kernel matrix. Note that the set Ω could contain very different kernel matrix models, all with different parameter values. The goal is then to find a kernel function Kα that satisfies relative kernel value constraints (specified by the user as a set T ). A general formulation for achieving this is given by:

where ϵt are slacks variables, t indexes T , the function h(Kα) is a regularizer on the kernel matrix Kα (or alternatively the kernel function Kα) for capacity control, and the parameter γ ≥ 0 controls the trade-off between constraint satisfaction and regularization strength (usually obtained by tuning). Note that this formulation seems sufficient, we can optimize the set of values αi in order to obtain a positive semidefinite (PSD) linear combination Kα(x, y) = ∑kj=1 αjKj(x, y) suitable for the specific task at hand. This formulation, however requires solving a relatively expensive semidefinite program (SDP). Enforcing αi ≥ 0, ∀i, [Fung et al., 2004; Lanckriet et al., 2004] and moreover restricting all the kernels in the set Ω to be PSD results in Kα being PSD. However this strongly limits the space of attainable kernel functions Kα.

Instead of using these restrictions, we explore an alternative, general definition that allows us to consider any kernel function in Ω and any αk ∈ ℜ without compromising computational efficiency (e.g., without requiring us to solve a SDP). For this we will explicitly focus on a well characterized subfamily of the PSD matrices: the set of diagonal dominant matrices. In order to provide a better understanding of the motivation for our next formulation we present the following theorem as stated in [Golub and Van Loan, 1996]:

Theorem 1 Diagonal Dominance Theorem Suppose that M ∈ ℜD×D is symmetric and that for each i = 1, . . . , n , we have:

then M is positive semi-definite (PSD). Furthermore, if the inequalities above are all strict, then M is positive definite.

Based on the diagonal dominance theorem (for matrices with positive diagonal elements) above, by simplifying the notation letting Kα ij ≡ Kα(xi, xj), we arrive to the following alternative formulation:

where Kα ij = ∑Ki∈Ω αiKi(xi, xj) and S is a set of training points (e.g., those points used to define the triples in T ). Finally, defining auxiliary variables rij ∈ ℜ+, γ1 ≥ 0, and γ2 ≥ 0, formulation (3) can be rewritten as a linear programming problem in the following way:

where s ∈ ℜk (same dimensionality as α) and sj ≥ 0. Note that to simplify notation we have overloaded the variables i, j, k (but their meaning should be clear from the context).

In order to better understand the motivation for formulation (4) it is important to note that:

• (i) Minimizing ∑i Kα ii is equivalent to minimizing ∑ j j̸=i rij since Kα ii ≥ ∑kj=1 j̸=i rij, ∀i.
• (ii) Since we are implicitly minimizing∑ j j̸=i rij, at the optimal solution {α∗ , r∗ , ϵ∗, s∗} to problem (4), we have that:

• (iii) Combining (i) and (ii) we obtain:

which implies that Kα∗ is diagonal dominant and hence positive semidefinite.

2.2 Learning kernels that depend on fewer input features ( ˜K)

Next, we will modify formulation (4) in order to learn kernels that depend in a small subset of the original input features. As far as we know, all of the existing direct objective optimization methods for feature selection with kernels perform feature selection in the implicit feature space induced by the kernel and not with respect to the original feature space. Doing this using traditional kernels, leads to nonlinear, nonconvex optimization problems that are difficult to solve due to the nonlinearity relations among the original features introduced by the kernel mappings.

In order to overcome this difficulty we propose a simple but effective idea. Instead of using kernels that depend on all the features we will only consider a set ¯Ω comprised of weak kernels that depend on only one feature at a time. For example, if xi = (x1i , . . . , xfi , . . . , xDi ) and xj = (x1j , . . . , xfj , . . . , xDj ) are two vectors on ℜD , then a weak Gaussian kernel only depending on feature f is defined by:

Let us denote by If the set of indices i of kernels Ki ∈ ¯Ω that only depend on feature f for f ∈ {1, . . . ,D}. Then, any linear combination of weak kernels in ¯Ω can be written as:

Note that if αp = 0, ∀p ∈ If for a given f, this implies that Kα ij does not depend on the original feature f . This motivates our next formulation for feature selection that uses weak onedimensional kernels:

where now s is indexed by the feature number f rather than the kernel number alone. It is interesting to note that for each feature f, formulation (7) is minimizing Mf = max {|αp| /p ∈ If }. This is appropriate since:

3 Numerical Evaluation

For our experimental evaluation we used a collection of nine publicly available datasets, part of the UCI repository 4 . A summary of these datasets is shown in Table 1. These datasets are commonly used in machine learning as a benchmark for performance evaluation. Our choice of datasets is motivated primarily by their use in evaluating a competing approach [Xing et al., 2002] aimed to learn distance functions.

We evaluate our approach against single kernels by comparing against the standard Gaussian (at various widths), linear, and polynomial kernels. These kernels are also the ones used as the basis for our mixture kernel design; thus it is a reasonable baseline comparison. We compare both of our formulations. One formulation attempts to perform implicit feature selection by defining weak kernels, while the other uses full kernel matrices (that depend on all input dimensions).

We have also chosen to compare our formulation against that proposed in [Xing et al., 2002]. This obeys various reasons. In addition to being a state-of-the-art method, the primary reason for our choice is that it uses a similar (but not identical) type of supervision, as explained below. Unlike other related approaches, computer code and data has been made public for this method 5 . In addition, this method outperformed a constrained version of K-means [Wagstaff et al., 2001] in the task of finding good clusterings.

4 http://www.ics.uci.edu/∼mlearn/MLRepository.html.

5 Data for all experiments and code for [Xing et al., 2002] was downloaded from http://www.cs.cmu.edu/∼epxing/papers/. The class for dataset 1 was obtained by thresholding the median value attribute to 25K.

3.1 Evaluation Settings

The datasets employed in these experiments are generally used for classification since class labels are available. However, the various methods to be compared here do not require explicit class labels. The method introduced in this paper requires relative similarity information among a subset of points (clearly class labels provide more information). We use the available class labels to generate a set of triples with similarity comparisons that respect the classes. More explicitly, given a randomly chosen set of three points (from the training set), if two of these belong to the same class and a third belongs to a different class, then we place this triple in our set T (i.e., i and j are the points in the same class, k is the remaining point). For the case of [Xing et al., 2002], the supervision is in the form of two sets, one called a similar set and the other a dissimilar set. In order to identify these sets, we can again use the class labels, now to build a similar set of pairs (likewise for a dissimilar set of pairs). Given this level of supervision, this method attempts to find an optimal Mahalanobis distance matrix to have same-class points closer to each other than different-class points (see [Xing et al., 2002] for details).

For every triple (i, j, k) ∈ T used in our approach for learning, we use (i, j) ∈ S and (i, k) ∈ D for learning in [Xing et al., 2002]; where S and D are the similar and dissimilar sets. We believe this provides a fair level of supervision for both algorithms since roughly the same information is provided. It is possible to obtain a superset of T from S and D, and by construction S and D can be obtained from T .

In order to evaluate performance for the various methods, we use a 0.85/0.15 split of the data into training and testing (for the methods where training is required). From the training portion, we generate 1500 triples, as explained above, for actual training. This information is provided, in the appropriate representation, to both algorithms. For testing, we repeatedly choose three points at random, and if their class labels imply that any two points are more similar to each other than to a third (i.e., again if two points have the same class and a third has a different class label), then we check that the correct relationships were learned. That is, whether the two points in the same class are more similar (or closer) to each other than any of these points (chosen at random) to the third point. This same measure is used for all algorithms. Thus, we define the percentage correct simply as the proportion of points from the test set (sampled at random) that respect the class-implied similarity or distance relationship.

Our method requires setting two balancing parameters. We set them by using cross validation by splitting the training set in two halves. The values tested (for both parameters) were {10-4, 10-2, 10-1, 1, 10, 102}. These parameters have an effect on the number of dimensions employed since a higher value for γ1 favors using fewer kernels (or dimensions). Likewise, larger values for γ2 favors kernel matrices with a smaller trace.

3.2 Discussion and Results

Fig. 1 shows the performance of our approach compared against various Gaussian and polynomial kernels. A linear kernel performed almost identically to the polynomial kernel of degree two and it is omitted in the graph. The mean and standard deviation (of the performance measure) for each individual kernel was computed from 10 random samplings of the dataset. In order to be consistent across approaches, the number of samples used for testing was set to 1000 triples.

One could expect an optimal mixture of kernels to provide a higher performance in both cases (full and weak kernel mixtures) when compared with single kernels. This is generally the case. It can be seen in the figure that in most cases single predetermined kernels are suboptimal. In the case of weak kernels, the performance is always better than single kernels. However, for the case of mixtures of full kernels there are cases where a single kernel provides a higher performance in average. This can be at least due to two reasons: (1) simply unlucky selection (sampling) of test points. In datasets 1, 3, and 9, the standard deviation is large enough to justify this possibility. A much more interesting reason is (2) the imposed restrictions on the solution space of the mixture kernel (e.g., dataset 6). Recall that we concentrated our solution on a subspace of the PSD matrices, that of diagonal dominant matrices. If the full cone of PSD matrices were to be incorporated as solution space, the kernel mixture could perform as good as any base kernel (since a mixture of a single kernel is a valid solution). Note however that, although this is possible, one would be required to pay much higher computational costs (e.g., for large datasets or number of constraints).

Interestingly, the performance for the mixture of weak kernels is superior. This can be due to the larger number of degrees of freedom (the number of α mixing parameters is larger) or also a feature selection effect on overfitting. However, even though this is the case for the datasets considered in this paper (and results suggest that this may often be the case), we remark that this result is not theoretically guaranteed since non-linear interactions among multiple dimensions or features may not be representable using a linear combination of single features.

Fig. 2 shows the average optimal number of dimensions found by this process in a 10-fold cross validation experiment and the corresponding one-standard-deviation error bars. The number of dimensions was identified by counting the number of α's larger than 0.01. This automatic choice of dimensionality was done using cross-validation as explained above and is a valuable property of the method presented. Note that the method effectively reduces the number of features for all but one dataset.

Fig. 3 shows the comparison of the present formulation (using weak kernels) against [Xing et al., 2002]. We show percentage correct averaged over 10 random splits of the data along with one-standard-deviation bars. For each of the 10 splits, 1000 triples from the test set are randomly chosen. When comparing the performance of both methods, we note that, except for dataset 5, our method clearly outperforms the competing approach. Interestingly, this dataset was the same for which the optimal number of dimensions was determined to always be equal to the original dimensionality.

In addition to the implicit non-linear representations implied by the kernels employed, we believe that a key reason for the superior performance of the mixture of weak kernels is the automatic identification of relevant dimensions. This reduction in dimensionality appears to provide an important advantage at the time of generalization. It is generally accepted that a simpler representation is preferable (e.g., [Blumer et al., 1987]) and it can reduce overfitting in practice.

From a computational efficiency perspective at test time, being able to represent the original data more succinctly is especially advantageous. In particular, when similarities can be calculated directly using a low-dimensional representation, computational time savings can be significant for on-line applications. The projection step in this approach can be precomputed off-line. In retrieval applications (e.g., query-byexample), the objects can be stored in their low-dimensional representation. From a conceptual point of view, this formulation also has the advantage of providing a more effective tool for understanding the data since it can identify whether variables (dimensions) are of high or low relevance for a task of interest.

4 Conclusions and Future Work

We presented a novel formulation for learning kernel functions from relative similarity information. Our general formulation consisted of a convex optimization problem requiring semidefinite programming to be solved. We designed a practical approximate problem, requiring linear programming instead. In particular, we showed how the diagonal dominance constraint on the kernel matrix leads to a general problem that can be solved very efficiently. In addition to this, we have shown how to extend the formulation to allow for implicit feature selection using a combination of kernels. Experiments indicated that our weak kernel formulation outperforms a state-of-the-art approach that uses similar information to learn a distance (rather than a similarity function).

Although relative similarity constraints are used in this paper, other constraints could potentially be imposed. For example, we could have sign or magnitude restrictions on certain kernel components, we can impose local isometry constraints (similar to [Weinberger et al., 2004]), or we can request the kernel to preserve local distances.

We believe this paper has potential implications in other problems. Our results suggest that the SDP problem could, in some cases, be replaced by a linear programming problem. We suggested one way to achieve this goal; this has the potential to be applied to other problems whose solution involves SDP.