Kernel Regression with Sparse Metric Learning
Rongqing Huang Shiliang Sun
cs.LG stat.ML





R. Huang and S. SunKernel Regression with Sparse Metric Learning

Kernel Regression with Sparse Metric Learning
    Rongqing Huang and Shiliang SunCorresponding author. Tel.: +86 2154345186; fax: +86 2154345119. E-mail address: slsun@cs.ecnu.edu.cn (S. Sun).

Department of Computer Science and Technology, East China Normal University

500 Dongchuan Road, Shanghai 200241, P. R. China
    December 30, 2023
=================================================================================================================================================================================================================================================================================


Kernel regression is a popular non-parametric fitting technique. It aims at learning a function which estimates the targets for test inputs as precise as possible. Generally, the function value for a test input is estimated by a weighted average of the surrounding training examples. The weights are typically computed by a distance-based kernel function and they strongly depend on the distances between examples. In this paper, we first review the latest developments of sparse metric learning and kernel regression. Then a novel kernel regression method involving sparse metric learning, which is called kernel regression with sparse metric learning (KR_SML), is proposed. The sparse kernel regression model is established by enforcing a mixed (2,1)-norm regularization over the metric matrix. It learns a Mahalanobis distance metric by a gradient descent procedure, which can simultaneously conduct dimensionality reduction and lead to good prediction results. Our work is the first to combine kernel regression with sparse metric learning. To verify the effectiveness of the proposed method, it is evaluated on 19 data sets for regression. Furthermore, the new method is also applied to solving practical problems of forecasting short-term traffic flows. In the end, we compare the proposed method with other three related kernel regression methods on all test data sets under two criterions. Experimental results show that the proposed method is much more competitive. 


Keywords: Kernel regression, sparse metric learning, mixed norm regularization, gradient descent algorithm, traffic flow forecasting.




                


§ INTRODUCTION

One of the oldest and most commonly used algorithms for regression is kernel regression. Kernel regression is a non-parametric technique rooting in statistics for estimating the conditional expectation of a random variable. In non-parametric regression, the conditional expectation of a variable 𝐘 given a variable 𝐗 is written as E(𝐘|𝐗)=m(𝐗), where the unknown function m is approximated by a locally weighted average, using a kernel as the weighting function<cit.>. The standard regression task is to estimate an unknown function based merely on a training set of evaluations that are possibly noisy. The target value of a test input is a real number and it is computed using a weighted average of the function values observed at its k nearest neighbors in the training set. The weight of each training point is obtained by a kernel function, which typically decays rapidly with the
distance between itself and the test point. This is also the reason why the target value of a test point has a strong dependence on its nearby training points<cit.>.

The traditional kernel regression (KR) combines the Euclidean metric with Gaussian kernels <cit.>. Using Euclidean as its learning metric, KR is popular for its simplicity. However, there exist two important drawbacks in KR. Firstly, KR adopts Euclidean metric on the input space, which may preclude its usage on some data sets. For example, if a data set whose features represent completely disparate quantities, the Euclidean metric is meaningless to it.
Secondly, Euclidean metric assigns the same weight 1 to all the features. It's known that on most of data sets, some features are possibly irrelevant to the regression task. These features ideally should not contribute to this distance metric at all. Therefore, learning a proper distance metric for kernel regression becomes an important issue.

As a well-established nonlinear regression method being widely used in statistics, kernel regression has attracted much attention from researchers. In 2006, Takeda et al. proposed a novel kernel regression algorithm for image denoising<cit.>. They learn a Mahalanobis matrix from statistics of the local pixel space. However, their algorithm is restricted to specific applications in some sense and cannot be generalized to all cases. At the same year, Keller et al. applied neighborhood component regression to function approximation for reinforcement learning<cit.>. Among all the algorithms related to kernel regression, the most popular one is proposed by Weinberger et al., which they refer to as Metric Learning for Kernel Regression (MLKR)<cit.>. Their work can be interpreted as learning a Mahalanobis matrix for a Gaussian regression kernel via minimization of loss function. However, MLKR just learns a Mahalanobis metric for kernel regression, which does not involve sparse metric learning.  Currently, sparse metric learning is a hot issue in machine learning and data mining. Its objective is to learn a sparse metric which is capable of removing redundancy or noise in data and improving the performance of supervised or
unsupervised learning algorithms<cit.>.  Over the past several years, many sparse metric learning algorithms have been proposed, including sparse metric learning via linear programming,  sparse metric learning via smooth optimization, and so on<cit.>. Unluckily, all the currently published algorithms on sparse metric learning are about classification. Classification refers to an algorithmic procedure for assigning a given piece of input data into one of a given number of categories. The number of categories is finite and the categories are discrete. As to regression, it deals with approximating the probability distribution underlying the data and finding out the most precise target values for the input data. Currently, few sparse metric learning methods are proposed basing on kernel regression issues.

Inspired by the latest innovations on sparse metric learning for classification<cit.>, we propose a novel kernel regression method to learn a sparse metric over the input space. This metric gives rise to an appropriate kernel function with parameters determined completely from the data. In addition to performing regression, our algorithm can also remove redundancy or noise in data leading to dimensionality reduction. We target the objective of sparse metric learning  directly by enforcing a mixed (2,1)-norm regularization over the metric matrix. A Mahalanobis metric is learnt by minimizing the loss function and the metric matrix's mixed (2,1)-norm regularization. Experiments on 19 data sets for regression are performed. The proposed method is also applied to forecast short-term traffic flows to verify its effectiveness. Because KR_SML has the capability of dimensionality reduction, we therefore add another KR model into the comparison. The KR model is referred to as KR_PCA, which first conducts dimensionality reduction on the regressors via principal component analysis (PCA) <cit.> and then runs KR on the leading principal components. Comparisons with three related kernel regression algorithms under two criterions reveal the competitiveness of the proposed method. In addition, our work is the first to combine kernel regression with sparse metric learning.

A preliminary study of the proposed kernel regression method applied to low-dimensional traffic flow forecasting was presented at a conference<cit.>. In this paper, we introduce the detailed framework, provide theoretical justifications, and evaluate the proposed method on more standard regression data sets as well as high-dimensional traffic flow forecasting. The paper is organized as follows. In the next section, some related works about kernel regression are briefly reviewed. The notations establishment and kernel regression problem settings are also presented in this section. In Section 3, we thoroughly introduce the proposed method, namely kernel regression with sparse metric learning(KR_SML). Section 4 reports the experimental results on 19 benchmark data sets for regression, including comparisons with other three related kernel regression methods. In Section 5, the proposed method is applied to forecasting short-time traffic flows. Finally, conclusions and future work are presented in Section 6.





§ KERNEL REGRESSION AND DISTANCE METRIC LEARNING

Our work integrates kernel regression and sparse metric learning. In this section, we will give a brief review on related works including the traditional kernel regression algorithm with the Euclidean metric (KR), Mahalanobis metric learning for kernel regression (MLKR) and latest developments in distance metric learning. In the following subsections, some notations used in this paper will be introduced before presenting these specific techniques.



 §.§ Basic Notations

Let (x⃗, y) represent an example with input x⃗=(x_1, x_2, …, x_d) ∈ R^d and its corresponding target value y. In regression case, the target value y ∈ R and y is continuous. As for a classification issue, y is the label information of an example and it belongs to an integer set (to simplify the classification task, we adopt an integer set to represent the label information). A data set with n examples is denoted by Z={(x⃗_i, y_i)_i=1^n}. The space of symmetric d by d matrices is denoted by S^d. If S ∈ S^d is positive semi-definite, we write it as S≥ 0. The cone of positive semi-definite matrices is denoted by S_+^d and we denote the set of d by d orthonormal matrices by O^d. The trace operation for matrices is denoted by Tr(·), which is the sum of all the diagonal elements of a matrix<cit.>. For any matrix X,Y ∈ R^n× d,  ⟨ X,Y⟩:=Tr(X^TY). In addition, any d by d diagonal matrix is denoted by diag(D_11,D_22,…, D_dd), where D_11,D_22,…, D_dd are the diagonal elements of the matrix.

A Mahalanobis metric is a generalization of the Euclidean metric, in which the squared distance between two examples x⃗_i and x⃗_j is defined as

    d(x⃗_i,x⃗_j)=x⃗_i - x⃗_j^2=(x⃗_i-x⃗_j)^TM(x⃗_i-x⃗_j)
    
    ,

where M can be any symmetric positive semi-definite real matrix. Setting M as the identity matrix, it recovers the standard Euclidean metric.
Actually, the Mahalanobis distance can be expressed as the Euclidean distance after a mapping x⃗→ Ax⃗:

    d(x⃗_i,x⃗_j)=A( x⃗_i - x⃗_j)
    ^2=(x⃗_i-x⃗_j)^TA^TA(x⃗_i-x⃗_j)

Therefore, M can be decomposed as

    M=A^TA
    
    ,

where A is the decomposition of matrix M.
For simplification, we denote the difference of two vectors by x⃗_ij=x⃗_i-x⃗_j.



 §.§ Kernel Regression


Kernel regression is an estimation technique for fitting data <cit.>. Standard kernel regression usually combines the Gaussian kernel function and Euclidean metric. Its task is to estimate an unknown function f:R^d → R based merely on a training set of possibly noisy examples. In kernel regression, the target value of every test input is estimated as

    y_i=f(x⃗_i)+ε
    ,

where ε represents some small noise. 


Nadaraya and Watson proposed to estimate f as a locally weighted average, using a kernel as the weighting function<cit.>.  Therefore, the estimated value ŷ_i  ≈ f(x⃗_i)  is approximated by

    ŷ_i = ∑_j = 1^k y_j K_ij/∑_j = 1^k K_ij
    ,

where k is the number of the test input x⃗_i's nearest neighbors, K_ij is the value of the kernel function based on the distance
between x⃗_i and its corresponding nearest neighbor x⃗_j.



The kernel function K_ij=K(d(x⃗_i,x⃗_j)) is nonnegative. It is formulated as follows


    K(x⃗_i,x⃗_j)= 1/σ√(2π)e^ -
    d(x⃗_i ,x⃗_j )/2σ ^2 
    ,

where d(x⃗_i,x⃗_j) is the Mahalanobis distance
between x⃗_i and x⃗_j with M being the metric matrix. Setting M to be the identity matrix I, it refers to the Euclidean metric.


The quadratic error loss function of kernel regression is generally formulated as L:

    L=∑_i = 1^n (y_i  - ŷ_i )^2 
    ,

where ŷ_i represents the estimator of y_i and is computed by formula (5). L represents the accumulated quadratic leave-one-out regression error
of all test examples.

Metric learning for kernel regression (MLKR) aims at training a Mahalanobis matrix by minimizing the error loss of all training examples:

    L= ∑_i = 1^N_training(y_i  - ŷ_i )^2 
    .

A transformation matrix A, the decomposition of matrix M is learnt by a gradient descent procedure:

    Δ A=-α∂L/∂ A
    ,

where α is an adaptive step-size parameter.
Then the Mahalanobis matrix is obtained by M=A^TA, and it is used to estimate the targets of test inputs.



 §.§ Distance Metric Learning


Metric learning is an important research area in machine learning and data mining. A metric is a distance function on a set of points,
mapping pairs of points into the nonnegative real numbers. The objective of metric learning is to find a proper distance function
to make the distance between similar examples as small as possible while enlarging the distance between dissimilar examples. A proper
metric d(·, ·) obeys four properties<cit.>:






  * Nonnegativity: d(x⃗_i,x⃗_j)≥ 0,




  * Symmetry:  d(x⃗_i, x⃗_j)= d(x⃗_j, x⃗_i),




  * Triangle inequality:  d(x⃗_i, x⃗_j)+ d(x⃗_i, x⃗_k)≥ d(x⃗_j, x⃗_k),




  * Distinguishability: d(x⃗_i, x⃗_j)=0 ⇔x⃗_i = x⃗_j.





For many machine learning algorithms, the choice of a distance metric has a critical influence on their performance. Take the
kNN algorithm as an example<cit.>, most implementations of kNN adopt the simple Euclidean as their distance metrics.
As mentioned in the previous section, Euclidean metric has two important drawbacks, which badly prevents the algorithms from performing well.
Furthermore, it has been revealed that even a simple linear transformation of the input features can lead to significant improvements in kNN classification<cit.>. Distance metric learning has attracted much attention from researchers and a number of improved algorithms have been proposed.
It is already demonstrated that kNN algorithms can be greatly improved by learning an appropriate distance metric from labeled examples<cit.>.

A good distance metric should generally preserve the proximity relationship of the data in the transformed space. That is, the distance between similar examples should be relatively smaller than that between dissimilar examples in the transformed space. In supervised classification, the label information can tell us whether two examples are in the same class (similar) or in different classes (dissimilar). For semi-supervised clustering, the side information conveys the information that a couple of examples are similar or dissimilar to each other <cit.>. Throughout most of the published works on metric learning for classification, they have two points in common.





  * Firstly, triplets containing 3 examples with two kinds of labels are constructed. That is,


T={τ=(i, j, k):i,j, k∈ N,∀(x⃗_i,x⃗_j)∈ S(x⃗_j,x⃗_k)∈ D},

 
where S represents pairs of similar examples and D represents the dissimilar pairs according to the label information.




  * Secondly, the distances between examples should always satisfy some constraints: the distance of similar examples are smaller than that of dissimilar examples.

 A(x⃗_j-x⃗_k)^2≥A(x⃗_i-x⃗_j)^2+1, ∀ (i,j,k)∈ T.







Algorithms of metric learning for classification have strongest dependence on the label information. Among the existing distance metric learning algorithms, distance metric learning for large margin nearest neighbor classification (LMNN)<cit.> is one of the most prominent. LMNN is motivated from the large margin concept. It learns a Mahalanobis metric with the goal that the k-nearest neighbors of the test input always belong to the same class while examples from different classes are separated by a large margin.

Distance metric learning usually attempts to learn a distance function f with a full-rank square metric matrix M from the given data set. However, the observed data are probably contaminated by noise or redundancy,  especially for high-dimensional data sets. If the contaminated data are not pre-processed to remove the irrelevant information in data, the accuracy of related algorithms may be degraded to an extent. Learning a full-rank metric matrix can not suppress the noise and will instead make the learning process time-consuming and expensive. To overcome the drawbacks of existing distance metric learning algorithms, a number of sparse metric learning approaches have been proposed<cit.>. In particular, the latest innovation of metric learning proposes a unified framework for sparse metric learning (GSML)<cit.>. Existing sparse metric learning algorithms are able to learn a good distance metric as well as a sparse or low-dimensional representation. Specifically, GSML directly targets the shortcomings of existing distance metric learning algorithms and has been demonstrated considerable improvement.


GSML bases itself on two principal hypotheses:




  * the distance between similar examples should be relatively smaller than that of dissimilar examples;




  * a good distance metric should have the capability of removing noise in data leading to dimensionality reduction.






Therefore, to meet the first hypothesis, the distances of a triplet in the transformed space should satisfy a constraint condition:

    A(x⃗_j-x⃗_k)^2≥A(x⃗_i-x⃗_j)^2+1,
    ∀ (i,j,k)∈ T,

where A∈ R^d× d is a transformation matrix. For the second hypothesis, any transformation vector x̂⃗̂_i=Ax⃗_i
should have fewer dimensions than the input vector x⃗_i. Let A_i denote the i-th row vector of A, if A_i=0, then
the i-th entry of x⃗_i becomes 0. Thus, to get a sparse solution, we can enforce a L_1-norm regularization across the vector
( A_1, A_2,…, A_d), i.e., ∑_i = 1^d A_i. That is, the sparse representation is realized
by enforcing a mixed (2,1)-norm regularization over the transformation matrix A. Ideally, the principal components of x̂⃗̂_i are
expected to be sparse. Therefore, an extra orthonormal transformation matrix U∈ O^d is introduced and x̂⃗̂_i=AUx⃗_i.

To avoid the situation that there is no solution for equation (10), slack variables ξ are introduced.
After a serials of transformation, the sparse metric learning formulation is proposed<cit.>,


    [             min_U ∈ O^d min_M ∈ S_ + ^d ∑_τξ _τ  + γ M _(2,1); s.t.    1 + x⃗_ij^T U^T MUx⃗_ij≤x⃗_jk^T U^T MUx⃗_jk  + ξ
     _τ,;                                    ξ _τ≥ 0,∀τ  = (i,j,k) ∈ T.;                                                               ]

With reference to <cit.>, problem (11) is equivalent to the following convex optimization problem:

    [                min_M ∈ S_ + ^d ∑_τξ _τ  + γ Tr(M); s.t.    1 + x⃗_ij^TMx⃗_ij≤x⃗_jk^TMx⃗_jk  + ξ
     _τ,;                        ξ _τ≥ 0,∀τ  = (i,j,k) ∈ T.;                                                   ]

By defining the hinge loss [z]_+={[ z      z>0;          0;            ]., the above problem can be transformed into an unconstrained optimization problem:

    min_M≥ 0 ∑_τ[1 +
    x⃗_ij^TMx⃗_ij  -
    x⃗_jk^TMx⃗_jk]_+ + γ Tr(LM)
    
    .

Then the matrix M is obtained by a standard sub-gradient descent procedure.





§ KERNEL REGRESSION WITH SPARSE METRIC LEARNING (KR_SML) 


We aim at learning a low-rank Mahalanobis matrix for kernel regression. Besides preserving the proximity relationship of examples in the transformed space, a good distance metric should be able to effectively remove possible noise in data leading to dimensionality reduction. Therefore, for the purpose of noise suppression, the metric matrix defined by M should be regularized. We will give a detailed explanation on how the metric matrix can be regularized for forcing sparsity. In the end, we introduce the sparse regularization of the metric matrix into the quadratic error loss function of kernel regression to build a sparse metric learning model for kernel regression.

As mentioned in previous sections, existing distance metric learning algorithms usually attempt to learn a distance function f with a full-rank square metric matrix M from the given data set. However, the observed data are probably contaminated by noise, especially for high-dimensional data sets. The noise in the data may prevent the algorithms from performing well if the contaminated data are not pre-processed to remove the noise. Worse still, learning a full-rank metric matrix can not suppress the noise but instead will make the learning process time-consuming and expensive. Therefore, to conquer the drawbacks of existing distance metric learning algorithms, sparse metric learning emerges as required. However, all the existing sparse metric learning algorithms are about classification, none for regression. Therefore, to learn a sparse metric for kernel regression becomes meaningful and necessary.

The Mahalanobis metric is learnt in the transformed space, after the mapping:


x⃗→ Ax⃗,


where A∈ R^d× d is the transformation matrix and the metric matrix M can be obtained by M=A^TA. With the purpose that a good distance metric should be able to remove noise in data leading to dimensionality reduction. Ideally, the principal components of input vector x⃗_i are expected to be sparse. Therefore, any transformation vector x̂⃗̂_i (x̂⃗̂_i=Ax⃗_i )  should have fewer dimensions than its corresponding
input vector x⃗_i. As a 1-norm regularization over a vector can produce a sparse vector, certain columns of A should be expected to become zero vectors. That is the basic motivation of sparse metric learning<cit.>.

Let A_i denote the i-th row vector of A, if A_i=0, then the i-th entry of x⃗_i becomes 0. Thus, enforcing a L_1-norm regularization over the vector ( A_1, A_2,…, A_d), i.e., ∑_i = 1^d A_i, leads to a sparse representation of A. Thereinto, ∑_i = 1^d A_i represents the mixed (2,1)-norm regularization of matrix A. Therefore, the sparse representation can be realized by enforcing a  mixed (2,1)-norm  regularization over the transformation matrix A. On the other hand, the metric matrix M=A^TA=(M_1, M_2,…,M_d). It is obvious that M_i≡ 0 is equivalent to A_i≡0. Motivated by this observation, instead of enforcing a L_1-norm regularization over the vector (A_1,A_2,…,A_d), L_1-norm regularization can be enforced across the vector
( M_1, M_2,…, M_d). The (2,1)-norm regularization over M is denoted by M_(2,1)=∑_i = 1^d M_i.
A similar mixed (2, 1)-norm regularization is used for multi-task learning and multi-class classification to learn the sparse representation shared across different tasks or classes <cit.>.

The task of kernel regression is to estimate the target values for test inputs as precise as possible. In other words, the goal of kernel regression is to make the accumulated quadratic regression error, the concrete form of which is L=∑_i = 1^n (y_i  - ŷ_i )^2, as small as possible. Generally speaking, if a kernel regression algorithm with a specific distance metric performs well on the training data, it often gets a good performance on the test data as well. Therefore, following the idea of MLKR <cit.>, we train a Mahalanobis metric matrix by the training data. Bearing the objective of kernel regression and sparse metric learning in mind, our work would ensure that the error is small and the metric matrix is sparse. Therefore, a Mahalanobis metric matrix is learnt by making the loss function of kernel regression and the  mixed  (2,1)-norm regularization over M to a minimum. That is, the objective function of the proposed kernel regression algorithm (KR_SML) is the minimum of L(M), which is represented as follows


    L(M)=∑_i = 1^N_training(y_i  - ŷ_i )^2 +μM_(2,1)
    .



The mixed (2,1)-norm regularization over M in the objective
function is non-convex and non-differentiable. Actually, the minimum of the mixed (2,1)-norm regularization over M is equivalent to
the trace of M<cit.>, which is presented as Theorem 1.




minM_(2,1)=Tr(M)


Proof. By the eigen-decomposition of M there exists  V∈ O^d such that M=V^Tλ(M)V. Thereinto, the
diagonal matrix λ(M)=diag(λ_1,λ_2,…,λ_d), where λ_i
is the i-th eigen-value of M. Therefore, M_(2,1)=V^Tλ(M)V_(2,1). Observing that


    [ V^T λ (M)V_(2,1)  = ∑_i (∑_j (∑_k V_kiλ _k V_kj )^2  )^1/2;   = ∑_i (∑_k,k'(∑_j V_ki V_k'i )λ _k V_kjλ _k' V_k'j )^1/2;                         = ∑_i (∑_k λ _k ^2  V_ki ^2 )^1/2,;                                                            ]

in the last equality, we use the fact that V∈ O^d, i.e.,
∑_j V_kj V_k^'j=δ_kk^'.
Applying Cauchy-Schwartz's inequality implies that ∑_k
λ _k V_ki ^2 ≤ (∑_k λ _k ^2 V_ki
^2  )^1/2 (∑_k V_ki ^2  )^1/2 =
(∑_k λ _k ^2 V_ki ^2  )^1/2.
Putting this back into equation (15) and the following result is obtained

    M_(2,1)≥∑_i ∑_k λ _k
    V_ki ^2   = ∑_k λ _k   = Tr(M)
    .

If we make V the identity matrix I, then the minimum of
∑_i (∑_k λ _k ^2  V_ki ^2
)^1/2 is equal to Tr(M). That is


    minM_(2,1)= Tr(M)
    .




Therefore, the objective function (14) is equivalent to


    L(M)=∑_i = 1^N_training(y_i  - ŷ_i )^2 + μ Tr(M)
    .



With reference to <cit.> and making use of ∂ Tr(M)/∂
M = I, the gradient of (18) with respect to M can be stated as

    ∂ L(M)/∂ M = 2∑_i = 1^N_training(ŷ_i  - y_i )∑_j = 1^k (ŷ_i  - y_j
    )K_ijx⃗_ijx⃗_ij ^T /∑_j = 1^k
    K_ij + μ I 
    .


After setting the initial value of M, we adjust its subsequent values
using a gradient descent procedure. In each iteration, we have
to keep M positive semi-definite. Let G^t denote the gradient of
the objective function at the t-th iteration, then G^t can be
stated as

    G^t = 2∑_i = 1^N_training(ŷ_i  - y_i
    )∑_j = 1^k (ŷ_i  - y_j )K_ijx⃗_ijx⃗_ij ^T /∑_j = 1^k K_ij + μ I 
    .

At each step, the metric matrix M can be updated by

    M_(t)  = M_(t - 1)  - α G^t
    ,

where α is a small positive step-size constant. We then
project the matrix M_(t) to the cone of positive semi-definite
matrices by the eigen-decomposition of matrix M_(t), i.e.,
M_(t)=P^TΛ P, where P is the eigen-vector matrix, and
Λ is the diagonal matrix with the diagonal elements
λ_i being the eigen-values of M_(t). To keep M_(t)
semi-definite, we set M_(t)=P^TΛ_+ P,
where
Λ_+=diag(max{0,λ_1},max{0,λ_2},…,max{0,λ_d}).

According to the above details, the proposed algorithm is illustrated as
follows.


  * Begin

  * Input Matrix M, step-size α for adapting M, step-size μ for adapting L(M), stop criterion θ, t ←
0.


  * Do t ← t+1

  * Compute the gradient of objective function G^t at the t-th iteration.

  * M_(t)← M_(t - 1)  - α G^t

  * M_(t)← P^TΛ_+ P

  * Compute the value of function L(M_t) at the t-th iteration.

  * Until |L(M_t)-L(M_t-1)| ≤θ.


  * Output M

  * End








§ EXPERIMENTS


The objective of the proposed kernel regression algorithm is to learn a good distance metric for kernel regression and simultaneously remove the noise of data leading to dimensionality reduction. In our experiments, we compare the proposed algorithm with three other competing kernel regression algorithms KR, MLKR, and KR_PCA on 19 standard regression data sets. Information about the data sets, experimental settings and results will be presented in this section in detail.




 §.§ Data Description and Configuration

The first 16 standard regression data sets utilized in our experiments are
from Data for Evaluating Learning in Valid Experiments
(Delve)[Delve: <http://www.cs.toronto.edu/ delve/data/datasets.html>]. They are Kin family of data sets and Pumadyn family of data sets [More information about the specific data set is available at <http://www.cs.toronto.edu/ delve/data/kin/desc.html> and
<http://www.cs.toronto.edu/ delve/data/pumadyn/desc.html>]. They are generated by two synthetic robot arms. Half of the sixteen data sets have 32 dimensions and the other half are of dimension 8. Each data set has already been randomly split into four disjoint training sets of size n=1024 and four corresponding test sets of the same size. As a result, we get four training sets and four test sets. The final result is the mean of the results of the four individual runs. There are other papers that have used the DELVE data sets in assessing model performance <cit.>. The last 3 data sets are from UCI machine learning repository: <http://archive.ics.uci.edu/ml/> for regression. For the last 3 data sets, the final results are given as an average over 10 random splits of the data. The detailed information about the 19 data sets are listed in Table 1, where dataset represents the name of a data set, n represents the size of the data set, and d represents the number of dimensions.

The  target value of a test input is estimated by a locally weighted average of values of its k nearest neighbors in the training set. In our implementation we only considered the k=30 nearest neighbors of each test examples. The trade-off parameter μ in the objective function of our
proposed algorithm and the step-size constant α used in KR_SML
and MLKR are tuned by 10-fold cross-validation on training sets. Specifically, KR_SML consists of setting the initial value of metric matrix M, and then adjusting its values using a gradient descent procedure. In our experiments, we follow <cit.> to initialize it with the identity matrix.





 §.§ Experimental Results


The proposed method has the capability of dimensionality reduction. We provide another KR model with principal component analysis (PCA) <cit.>, one of the most commonly used algorithms for dimensionality reduction, for comparison. The model is referred to as KR_PCA. It first conducts dimensionality reduction on the regressors via principal component analysis and then runs KR on the leading principal components. The other two competing methods are KR and MLKR. To compare the performance of the proposed algorithm with other three related kernel regression algorithms, KR, MLKR, and KR_PCA, two widely-used criterions are adopted to evaluate experimental results. They are root mean squared error (RMSE) and mean absolute relative error (MARE), respectively,
which are formulated as follows

    RMSE=√(1/n∑_i = 1^n (y_i  - ŷ_i )^2 )
    ,

and

    MARE=1/n∑_i = 1^n |y_i  - ŷ_i
    |/y_i 
    .

Besides, we also compare the accumulated quadratic leave-one-out regression error of test examples L=∑_i = 1^n (y_i - ŷ_i )^2,
where ŷ_i is the estimator of y_i and n is the number of test examples. Moreover, we provide the performance in terms of dimensionality reduction as well.










Experimental results based on criterion RMSE of four kernel regression algorithms on 19 data sets are shown in Table 2. The bold number in the
table represents that the kernel regression algorithm in the corresponding column performs best on the data set of the corresponding row. The d column tells the original dimension of each data set. The Rank(M) column reports the rank of the metric matrix M learnt by KR_SML.  The PCA_d column shows the final dimension of each data set learnt by PCA. To give an intuitive comparison, we show the accumulated quadratic leave-one-out regression error of the four kernel regression algorithms in Fig. 1. The final results of four kernel regression algorithms based on comparison criterion MARE are shown in Fig. 2.



 §.§ Discussion

The objective of kernel regression is to estimate the target values for test inputs as precise as possible to minimize the accumulated quadratic regression error. Therefore, the test error L (or RMSE) is treated as the most important comparison  criterion for kernel regression algorithms. As is revealed by the experimental results presented in Table 2 and Fig. 1, the proposed algorithm gets the best performance on all the 19 data sets. As to the comparison criterion MARE, KR_SML also outperforms the other three kernel regression algorithms on most of data sets. In addition, KR_SML is the only kernel regression algorithm that targets the objective of sparse metric learning. According to data in the last three columns of Table 2, the metric matrix M learnt by KR_SML has lower rank than its original dimension on most of data sets. If a sparse or low-rank metric matrix M is learnt, the performance of KR_SML is obviously much better than that of the other three competing kernel regression algorithms. For the data sets puma-32nh and puma-32nm, KR_SML cannot learn a sparse metric matrix M. However, all the three kernel regression algorithms  perform well on the two data sets. It can be explained that the features of the two data sets are all meaningful to the distance metric. That is, if the data are contaminated by noise, KR_SML has the capability of learning a sparse metric matrix leading to dimensionality reduction and the performance of KR is improved a lot. On the other hand, if the data are not contaminated by noise, KR_SML cannot learn a low-rank metric matrix, but it can perform as well as the other two kernel regression algorithms. As to KR_PCA, it also has the ability to reduce dimensionality due to PCA, but it gets the worst performance. This again demonstrates that PCA is easily affected by the scaling of input features and ignores the important information for being totally unsupervised <cit.>. When the noise become the leading PCA principal components, it tends to keep the noise and ignore the signal. Therefore, we can conclude that KR_SML can learn a good distance metric and simultaneously remove noise in data leading to dimensionality reduction. As the first work to combine kernel regression with sparse metric learning, KR_SML is a promising and better algorithm for kernel regression.






§ KR_SML FOR TRAFFIC FLOW FORECASTING


Short-term traffic flow forecasting is one of the most important and
fundamental problems in intelligent transportation systems (ITS). It
contributes a lot to traffic signal control and congestion
avoidance. The benefits of ITS cannot be realized without the
ability to forecast traffic condition in the next time interval, for
example, 5 minutes to half an hour. A good traffic condition
forecasting model will provide this ability and make traffic
management more efficient. There have been a variety of methods proposed for
short-term traffic flow forecasting such as Markov chain models, time series models, Bayesian networks, support vector
machines and kernel regression. In this paper, the proposed kernel regression algorithm KR_SML
is applied to forecasting short-time traffic flow to evaluate its effectiveness.

The problem addressed in this section is to forecast the future
traffic flow rates at given roadway locations from the historical
data on a transportation network. The data are from Beijing's Traffic Management Bureau. From the real urban
traffic map, we select a representative patch to verify the proposed
approach, which is given in Fig. 3 <cit.>. Each circle
in the sketch map denotes a road junction. An arrow shows the
direction of traffic flow, which reaches the corresponding road link
from its upstream link. Paths without arrows are of no traffic flow
records. Vehicular flow rates of discrete time series are recorded
every 15 minutes. The recording period is 25 days (totally 2400
recorded entries) from March, 2002. In our experiment, the raw data
are divided into two sets, 2112 recorded entries of the first 22
days as the training set and the rest recorded entries as the test
set. For evaluation, experiments are performed with multiple
randomly selected roads from Fig. 3.

Let x_1, x_2, x_3, …, x_2400 denote the original 2400
ordered recorded data of a road. First the raw data have to be changed into
examples of vector form. An example is represented as (x⃗,y),
where x⃗∈ R^d and y ∈ R<cit.>. In our experiment, the dimension of x⃗, d, and the number of past flows used to forecast the current flow, k, are empirically set as 45 and 8,
respectively.
















The two criterions used to compare the performance of KR_SML, KR_PCA, MLKR and KR in the above section are also adopted in this section.
Detailed information about the rank of the metric matrix M learnt by KR_SML and the final dimension learnt by PCA for
each data set is presented in Table 3. In addition, performance comparison of the four algorithms based on criterions MARE and RMSE on training sets and test sets are reported in Table 4 and Table 5, respectively. In order to give an intuitive illustration
of the forecasting performance, we draw the forecasting results of
Roadway Gb on the test set using KR, MLKR, KR_PCA and KR_SML, which are shown
in Fig. 4, where blue lines represent real recorded data and red
stars represent forecasted results.
Real traffic flow forecasting results reported in Table 3, Table 4
and Table 5 reveal that MLKR and KR_SML are all superior to the
traditional kernel regression algorithm KR and KR_PCA, which means metric
learning can effectively improve the performance of kernel
regression algorithms. Different from MLKR, the proposed KR_SML is
the first to combine kernel regression with sparse metric learning.
As shown in Table 3, only KR_SML has the capability of learning a
low-rank metric matrix. Furthermore, KR_SML gets much better forecasting results than that of MLKR, KR_PCA, and KR
on almost all the data sets. Therefore, the conclusion can be drawn that the proposed algorithm is better than KR, KR_PCA, and MLKR. It can learn
a good metric and effectively remove noise in data leading to dimensionality
reduction as well.



§ CONCLUSION

In this paper, a new kernel regression algorithm with sparse metric learning, which we refer to
as KR_SML is proposed. KR_SML is realized by introducing a mixed (2,1)-norm regularization over the metric
matrix M into the objective function of kernel regression. By minimizing the regression error function and the metric matrix's mixed (2,1)-norm regularization, a sparse or low-rank metric matrix is learnt through a gradient descent procedure. The proposed algorithm is the first to combine kernel regression with sparse metric learning. KR_SML is evaluated on 19 benchmark data sets for regression. Besides, it is also applied to forecasting short-term traffic flows. For comparison purpose, three related kernel regression algorithms KR, KR_PCA and MLKR are also employed to serve as base lines. Two widely-used criterions including the root mean square error RMSE and mean absolute relative error MARE are adopted to compare the performance of the four kernel regression algorithms. Experimental results of KR_SML on 19 benchmark data sets reveal competitive results. KR_SML gets the best performance on almost all the data sets. Especially when a sparse metric matrix is learnt, KR_SML obviously outperforms the other three kernel regression algorithms. Furthermore, experiments on real data of urban vehicular traffic flows forecasting also indicate excellent results. The promising results demonstrate that KR_SML is an effective and better kernel regression algorithm. It has the capability of learning a good distance metric and simultaneously remove noise in data leading to dimensionality reduction.

KR_SML targets the objective of sparse metric learning directly. It improves the performance of kernel regression by learning a sparse distance metric.
In the future, developing the potential of KR_SML in other domains is our pursuit.



§ ACKNOWLEDGEMENTS


This work is supported in part by the National Natural Science Foundation of China under Project 61075005, and the Fundamental
Research Funds for the Central Universities.

4
1
K. Teknomo, Kernel regression, available at: http://people.revoledu.com/kardi/tutorial/regression/kernel regression, 2007.

2
G. Watson, Smooth regression analysis,  The Indian Journal of Statistics, Series A 26 (1964), 359-372.

3
A. Nadaraya, On estimating regression, Theory of Probability and its Applications 9 (1964), 141-142.

4
K. Weinberger and G. Tesauro, Metric learning for kernel regression, in: Proccedings of the 11th International Conference on
Artificial Intelligence and Statistics, 2007, pp. 608-615.

regression
J. Benedetti, On the nonparametric estimation of regression functions, Journal of the Royal Statistical Society  39 (1977), 248-253.

Takeda
H. Takeda, S. Farsiu and P. Milanfar, Robust kernel regression for restoration and reconstruction of images from sparse noisy data,
  IEEE International Conference on Image Processing, 2006, pp. 1257-1260.

Keller
W. Keller, S. Mannor and D. Precup, Automatic basis function construction for approximate dynamic programming and reinforcement learning,
in: Proceedings of the 23rd International Conference on Machine learning, 2006.

5
K. Weinberger and L. Saul, Distance metric learning for large margin nearest neighbor classification,  Journal of Machine Learning Research  10 (2009), 207-244.

15
K. Weinberger and L. Saul, Fast solvers and efficient implementations for distance metric learning, in: Proceedings of
the 25th International Conference on Machine Learning, 2008, pp. 1160-1167.

26
L. Yang and R. Jin, Distance metric learning: a comprehensive survey, Technical Report, Department of Computer Science and
Engineering, Michigan State University, 2007.

11
R. Rosales and G. Fung, Learning sparse metrics via linear programming,  in: Proceedings of the 12th International
Conference on Knowledge Discovery and Data Mining, 2006, pp. 367-373.

16
K. Huang, Y. Ying and C. Campbell, GSML: A unified framework for sparse metric learning, in: Proceedings of the 9th International
Conference on Data Mining, 2009, pp. 189-198.

17
Y. Ying, K. Huang and C. Campbell, Sparse metric learning via smooth optimization,  Advances in Neural Information Processing Systems, 2009.

rqhuang
R. Huang, S. Sun and Y. Liu, Sparse kernel regression for traffic flow forecasting, Lecture Notes in Computer Science 6676  (2011), 76-84.

18
F. Bach, Consistency of trace norm minimization,  Journal of Machine Learning Research   9 (2008), 1019-1048.

21
T. Graepel, Kernel matrix completion by semidefinite programming, in: Proceedings of the International Conference on Artificial
Neural Networks, 2002, pp. 694-699.

22
G. Obozinski, B. Taskar and M. Jordan, Joint covariate selection and joint subspace selection for multiple classification problems,
 Statistics and Computing 20  (2010), 231-252.


8
A. Argyriou, T. Evgeniou and M. Pontil, Convex multi-task feature learning,  Machine Learning 73 (2008), 243-272.

30
Y. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming 103 (2005), 127-152.

33
R. Duda, P. Hart and D. Stork, Pattern Classification, John Wiley & Sons, New York (2000).


6
E. Xing, A. Ng, M. Jordan and S. Russell, Distance metric learning, with application to clustering with side-information, in: Proccedings of the 15th Annual Conference on Neural Information Processing Systems, 2002, pp. 505-512.

7
I. Tsang, P. Cheung and J. Kwok, Kernel relevant component analysis for distance metric learning, in: Proceedings of the International Joint Conference on Neural Networks, 2005, pp. 954-959.

9
C. Micchelli and M. Pontil, Learning the kernel function via regularization, Journal of Machine Learning Research 6 (2005), 1099-1125.


12
S. Sun and Q. Chen, Kernel regression with a Mahalanobis metric for short-term traffic flow forecasting,  Lecture Notes in Computer Science 5326  (2008), 9-16.


13
G. Fung, O. Mangasarian and A. Smola, Minimal kernel classifiers,  Journal of Machine Learning Research 3 (2002),  303-321.

19
B. Schölkopf, A. Smola and K. Müller, Nonlinear component analysis as a kernel eigenvalue problem,  Neural Computation 10 (1998), 1299-1319.

20
A. Rahimi and B. Recht, Random features for large-scale kernel machines, in: Proccedings of the 20th Annual Conference on Neural Information Processing Systems, 2007.


24
R. Johnson and T. Zhang, Graph-based semi-supervised learning and spectral kernel design, IEEE Transactions on Information Theory  54 (2008), 275-288.

27
G. Baudat and F. Anouar, Generalized discriminant analysis using a kernel approach, Neural Computation 12 (2000), 2385-2404.


29
J. Li and S. Sun, Nonlinear combination of multiple kernels for support vector machines, in: Proceedings of the 20th International Conference on Pattern Recognition, 2010, pp. 2883-2886.


31
T. Hofmann, B. Schölkopf and A. Smola, A review of kernel methods in machine learning, Technical Report, available at:
ftp://ftp.kyb.tuebingen.mpg.de/pub/mpi-memos/pdf/TR-156.pdf, 2006.

32
Y. Zhang and D. Yeung, Semi-supervised multi-task regression, Machine Learning and Knowledge Discovery in Databases 5782 (2009),  617-631.


Sun
S. Sun and C. Zhang, The selective random subspace predictor for traffic flow forecasting, IEEE Transactions on Intelligent Transportation Systems (2007), 367-373.

RN
R. Neal, Assessing relevance determination methods using DELVE, Neural Networks and Machine Learning, Springer-Verlag, 1998.

GP
C. William and C. Rasmussen, Gaussian processes for regression, in: Advances in Neural Information Processing Systems, 1996.

PCA
I. Jolliffe, Principal component analysis, Springer-Verlag, New York, 1986.


