# An Efficient Kernel Learning Algorithm for Semisupervised Regression Problems

Authors: Chao Zhang; Shaogao Lv
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Kernel selection is a central issue in kernel methods of machine learning. In this paper, we investigate the regularized learning schemes based on kernel design methods. Our ideal kernel is derived from a simple iterative procedure using large scale unlabeled data in a semisupervised framework. Compared with most of existing approaches, our algorithm avoids multioptimization in the process of learning kernels and its computation is as efficient as the standard single kernel-based algorithms. Moreover, large amounts of information associated with input space can be exploited, and thus generalization ability is improved accordingly. We provide some theoretical support for the least square cases in our settings; also these advantages are shown by a simulation experiment and a real data analysis.


---

## Body

## 1. Introduction

Kernel-based methods have been proved to be powerful for a wide range of different data analysis problems. Since support vector machine (SVM) was initially proposed by Vapnik [1], many other kernel-based methods have been proposed such as kernel PCA, kernel Fisher discriminant, and kernel CCA. In many cases, the performance of kernel methods greatly depends on the choice of kernel function (for the importance of specifying an appropriate kernel, see Chapter 13 of [2]). To choose an appropriate kernel, many kernel learning algorithms have been proposed in recent years such as [3–5]. Among them, there are two kinds of candidate kernel sets: the first one involves parameter selection from the candidate kernel collection including Gaussian kernels [6]; that is, G
σ
(
x
,
y
)
=
e
x
p
(
-
σ
x
-
y
2
). The others mainly refer to the linear combination of certain prespecified kernels. It is known that the latter one is also called “multiple kernel learning” [4]. Recall that Lanckriet et al. [5] proposed a positive semidefinite programming to search the best linear combination automatically for SVM; however, this approach is time-consuming and only feasible for small sample cases. Sonnenburg et al. [7] relaxed this mentioned optimization problem to a semi-infinite linear program, which is capable of coping with a large spectrum of kernels and samples. However, these multiple kernel learning algorithms do not have better performance than traditional nonweighted kernel K
=
∑
k
K
k in SVM sometimes, and Cortes [8] questioned that “can learning kernels help performance?”. Recently Kloft and Blanchard [9] introduced a multikernel learning with l
q-norm (
q
≥
1
) approach, which has been shown effective in both theory and practice [10, 11]. Essentially, l
q-norm is a kind of minimizing empirical risk algorithm with kernel candidate set {
K
=
∑
k
=
1
M
θ
k
K
k
∣
θ
l
q
≤
1
,
θ
≥
0
}. Kloft and Blanchard [9] provided an excess generation error utilizing local Rademacher complexity of l
q-norm multiple kernel learning. Although these mentioned learning kernel algorithms provide more flexibility than these one-kernel approaches, more complex computational problems induced by multiple kernel learning arise additionally. In addition, these above kernel learning algorithms are considered only under fully supervised learning settings. In practice, labeled instances however are often difficult, expensive, or time-consuming to obtain, as they require the efforts of experienced human annotators. Meanwhile unlabeled data may be relatively east to collect. In the machine learning literature, semisupervised learning addresses this problem by using large amount of unlabeled data, together with the labeled data, to build better learners.In this paper, we pursue the goal of kernel learning algorithms under semisupervised learning framework. For this sake, we resort to find a sequence of candidate kernels using an iterative procedure; then our regularized learning algorithms perform on the corresponding RKHS, which leads to a classical convex optimization program on training data. Finally, we apply the test data to select the optimal kernel function and regularization parameter. It is worth noting that the proposed method consists of two-step estimation stated as above. At the first step, we use large amount of information of unlabeled data to explore underlying data structure. Our optimization problem involved at the second step is as efficient as those classical single kernel approaches. More importantly, we provide sufficient theoretical support for our approach and we demonstrate the effectiveness of the proposed method by experiments.The rest of the paper is organized as follows. In Section2 we introduce some basic notations and our two-step estimation for kernel learning. We present main theoretical results for the proposed approach, which is achieved mainly by using advanced concentration inequalities stated in Section 3. Section 4 contains some proof details such as error decomposition and approximation error. We implement a simulation and a real data experiment in Section 5. Some proofs are relegated to the Appendix.


## 2. The Proposed Algorithm

We first describe the notations used in this paper. Suppose that our algorithm produces one learnerf
:
X
→
Y from a compact metric space X to the output space Y
⊆
R. Such a learner f yields for each point x the value f
(
x
)
∈
Y, which is a prediction made for x. The goodness of estimation is usually assessed by some specified loss function denoted by ν
:
R
2
→
R
+. The most commonly used loss function is the least square one; that is, ν
(
f
(
x
)
,
y
)
=
(
f
(
x
)
-
y
)
2. Let (
x
,
y
) be the random variable on X
×
Y with the probability distribution ρ. Within statistical learning framework, the target function can be formulated as a minimizer of the following functional optimization: (1)
f
∗
=
a
r
g
min
f
∈
F
⁡
∫
X
×
Y
ν
f
x
,
y
d
ρ
x
×
y
.In particular, in the case of the least square loss, we derive an explicit solution expressed as(2)
f
ρ
x
=
∫
Y
y
d
ρ
y
∣
x
,
x
∈
X
,where ρ
(
y
∣
x
) is conditional probability measure at x induced by ρ. Under fully supervised learning setting, based on available samples S
=
{
(
x
i
,
y
i
)
}
i
=
1
m, the main goal of learning is to design an efficient learning algorithm to obtain one learner f
S, which is capable of well approximating regression function f
∗ on the whole space. These popular regularized learning algorithms within a RKHS can be stated as(3)
inf
f
∈
H
K
⁡
1
m
∑
i
=
1
m
ν
f
x
i
,
y
i
+
λ
f
K
2
,where H
K is a specified RKHS and 0
<
λ
≤
1 is the regularization parameter, controlling empirical error and functional complexity of H
K. Note that λ may rely on sample size; it satisfies l
i
m
m
→
∞
λ
(
m
)
=
0.In the semisupervised learning framework, the firstm samples are labeled as above and followed by n unlabeled samples x
~
=
{
x
m
+
1
,
…
,
x
m
+
n
}. Denote by a weak kernel K
0 as the original kernel. Compared to those standard kernels, a weak kernel here means that its complexity is very large or it is less smooth. A learner with a weak kernel usually leads to overfitting, while it can approximate well more complicated functions and hence reduce estimation bias of the learner. Hence, selecting an appropriate kernel needs to trade off the functional complexity of various H
K. Motivated by this observation, we propose an iterative procedure as our first step for constructing candidate kernels. For the kth step, the next candidate kernel is derived as follows:(4)
K
k
+
1
x
,
u
=
1
m
+
n
∑
i
=
1
m
+
n
K
k
x
,
x
i
K
k
u
,
x
i
,
x
,
u
∈
X
.The labeled samples are divided into training data denoted by D
=
{
(
x
i
,
y
i
)
}
i
=
1
l and test data T
=
S
∖
D, respectively; then we establish our regularized learning algorithm based on the associated H
K
k:(5)
f
z
,
λ
k
≔
a
r
g
min
f
∈
H
K
k
⁡
1
l
∑
i
=
1
l
ν
f
^
x
i
,
y
i
+
λ
f
K
k
2
.Given the total number N of iteration steps, we minimize f
^
(
k
,
λ
) on the test data:(6)
f
z
,
λ
∗
k
∗
=
min
k
∈
1,2
,
…
,
N
,
λ
∈
0,1
⁡
1
m
-
l
∑
x
i
,
y
i
∈
T
f
z
,
λ
k
x
i
-
y
i
2
.Thus, we take f
z
,
λ
∗
k
∗ as our final leaner in semisupervised learning setting. Note that we use the least square loss instead of ν in the final step, since we compute or approximate its solution easily following nice mathematical property of the least square one.Our motivation of designing kernel as (4) is based on the following fact. By the Mercer Theorem [12], any given kernel K
k defined on a compact set can be expressed as K
k
(
x
,
u
)
=
∑
j
=
1
∞
λ
j
e
j
(
x
)
e
j
(
u
), where (
λ
j
,
e
j
) is the corresponding eigenpairs of the integral operator L
K
k, which will be defined in (19) below. In general, the problem of selecting kernel corresponds to a suitable choice of the parameters λ
j, since the eigenvalue λ
j has a close relationship with the functional complexity of H
K
k [13]. In our case, we use an iterative procedure to select an appropriate kernel. To be precise, we define a new candidate kernel by K
k
+
1
(
x
,
u
)
≔
∫
X
K
k
(
x
,
t
)
K
k
(
u
,
t
)
d
ρ
X
(
t
). Based on the observation K
k
+
1
(
x
,
u
)
=
∑
j
=
1
∞
λ
j
2
e
j
(
x
)
e
j
(
u
), it suffices to find an appropriate iteration step. Since ρ
X is often unknown, alternatively, we use an empirical estimator of K
k
+
1 defined as (4) as our candidate kernel. Furthermore, in view of the slow rate with order 1
/
m, by which the empirical kernel in (4) converges to its corresponding population kernel, the large amounts of unlabeled data guarantee a smaller error generated by sampling randomly.It is seen from the proposed program as above that this method avoids multioptimization in the process of learning kernels and its computation is as efficient as the standard single kernel-based algorithms up to some constant. Moreover, large amounts of information associated with input space have been made fully use of, so that some intrinsic data structure may be exploited.


## 3. Main Results

To highlight our idea by presenting more refined theoretical results, in what follows, we are primarily concerned with the least square setting, since the regularized least square algorithm has a closed-form solution. First of all, by the law of large number, with a high probability, we can replace the first step (4) with the following iterative procedure:(7)
K
k
+
1
x
,
u
=
∫
X
K
k
x
,
t
K
k
u
,
t
d
ρ
X
t
,
x
,
u
∈
X
,where ρ
X is the marginal distribution induced by ρ. We denote by f
z
,
λ
N the derived learner of (5) at the Nth iteration. For notational simplicity, we write f
z
=
f
z
,
λ
N. In this paper, we focus on generalization error of the proposed algorithm; that is, (8)
f
z
-
f
ρ
L
ρ
X
2
.A small quantity of f
z
-
f
ρ
L
ρ
X
2 implies a good prediction ability of f
z. Different from those classical literatures under fixed kernel settings such as [13, 14], the main goal of this paper is to indicate some specific advantages theoretically compared with those fixed kernel approaches.To simplify theoretical analysis, we assume that the conditional distributionρ
(
·
∣
x
) has a support on [
-
M
,
M
], and it follows that f
ρ
x
≤
M almost everywhere. To this end, we introduce the projection operator as follows.Definition 1.
Define the projection operatorπ
M on measurable function f
:
X
→
R as (9)
π
M
f
x
=
M
,
if
f
x
>
M
,
f
x
,
if
-
M
≤
f
x
≤
M
,
-
M
,
if
f
x
<
-
M
.Note that the error bound between the projections off
z and f
ρ can be expressed as(10)
π
M
f
z
-
f
ρ
L
ρ
X
2
2
=
E
π
M
f
z
-
E
f
ρ
,where E
(
f
)
=
∫
Z
(
f
(
x
)
-
y
)
2
d
ρ denotes the population error of the function f.Since the regression functionf
ρ may not be found within H
K, the approximation error between H
K and f
ρ is needed. Considering the error induced by sampling and the approximation error, we introduce the following empirical error as (11)
E
z
f
=
1
m
∑
i
=
1
m
f
x
i
-
y
i
2
,and we also introduce an approximation error associated with the joint distribution ρ:(12)
D
λ
=
f
λ
-
f
ρ
L
ρ
X
2
2
+
λ
f
λ
K
N
2
,where f
λ is called the regularization function, given as(13)
f
λ
=
a
r
g
m
i
n
f
∈
H
K
N
f
-
f
ρ
L
ρ
X
2
2
+
λ
f
K
N
2
.Remark 2.
In the literature of learning theory, one usually assumes that there existc
β
>
0 and 0
<
β
≤
1, such that D
(
λ
)
≤
c
β
λ
β. In fact β
=
1 means f
ρ
∈
H
K
N and vice versa [15–17]. Strictly speaking D
(
λ
) is formally discussed in approximation theory.To obtain convergence rates of (10), we decompose the term E
(
π
M
(
f
z
)
)
-
E
(
f
ρ
) into two parts: the approximation error and the sample error; see [14, 15].Proposition 3.
Letf
z be defined by (5); the following inequality holds(14)
E
π
M
f
z
-
E
f
ρ
≤
S
z
,
λ
+
D
λ
,where (15)
S
z
,
λ
=
E
π
M
f
z
-
E
z
π
M
f
z
+
E
z
f
λ
-
E
f
λ
.Proposition3 shows that E
(
π
M
(
f
z
)
)
-
E
(
f
ρ
) is bounded by S
(
z
,
λ
)
+
D
(
λ
). We usually call S
(
z
,
λ
) the sample error, since this quantity mainly involves random sampling and the complexity of H
K.Bounding the sample errorS
(
z
) is a standard technique in learning theory [13, 15, 18]. To this end, we need to introduce the notion of covering number to measure the complexity of H
K.Definition 4.
Assume(
M
,
d
) is a pseudometric space with some metrics d and S
⊂
M. Then, for any ϵ
>
0, we define the covering number N
(
S
,
ϵ
,
d
) referring to ϵ and d as covering number of a ball with radius ϵ: (16)
N
S
,
ϵ
,
d
=
m
i
n
l
∈
N
:
S
⊂
⋃
j
=
1
l
B
s
j
,
ϵ
for  any  sequence
s
j
j
=
1
l
⊂
M
.Recall that a kernel function is called the Mercer kernel, if it is symmetric, positive definite, and continuous. Several properties concerning the Mercer kernel have been established well and can be found in [12, 15]. Suppose that κ
≔
s
u
p
x
∈
X
K
0
(
x
,
x
)
<
∞.Assumption 5.
Suppose that the Mercer kernelK
N has a polynomial complexity with s
>
0
(17)
l
o
g
N
B
1
,
η
≤
C
N
1
η
s
,
∀
η
>
0
,where B
1 is the unit ball of H
K and C
N is some constant. For the Sobolev space H
h on R
p with the order h, it is known in [12] that s
=
2
p
/
h.On the other hand, to quantify the approximation errorD
(
λ
) and characterize the regularity of f
ρ, we need to introduce the notion of fractional integral operator associated with K. Recall that a standard inner product on L
ρ
X
2 is defined as (18)
f
,
g
ρ
X
=
∫
X
f
x
g
x
d
ρ
X
.Then we can define an integral operator L
K on L
ρ
X
2
(
X
):(19)
L
K
f
x
=
∫
X
K
x
,
t
f
t
d
ρ
X
t
.It has been verified in [16] that the integral operator L
K is a compact, self-adjoint, and positive definite operator from L
ρ
X
2
(
X
) to L
ρ
X
2
(
X
). So the fractional operator of L
K is well defined. Moreover, it is easy to check that L
K
k
+
1
=
L
K
k
2 and L
K
N
=
L
K
0
(
2
N
). Lemma 12 below will show that if a weak kernel with respect to the true function is used for learning, the approximation ability cannot be improved even if the true function is sufficiently smooth. This is why we propose the iterative procedure (4) for updating kernels.With these preparations, we can state the main results depending on the capacity ofH
K
N and the smoothness of target function as follows.Theorem 6.
Letf
z be defined by (5) and Assumption 5 holds. If L
K
0
-
r
(
f
ρ
)
∈
L
ρ
X
2
(
X
)
(
r
>
0
), then, for any 0
<
δ
<
1 and m
>
1360
log
⁡
(
1
/
δ
)
/
c
~
(
1
+
s
)
/
s, the following holds:(20)
S
z
,
λ
≤
7
κ
N
λ
min
⁡
r
-
N
/
2
N
,
0
L
K
0
-
r
f
ρ
L
ρ
X
2
+
3
M
2
log
⁡
2
/
δ
3
m
+
1
2
λ
m
i
n
r
/
N
,
2
L
K
0
-
r
f
ρ
L
ρ
X
2
2
+
1
2
E
π
M
f
z
-
E
f
ρ
+
c
~
M
s
/
1
+
s
1
λ
s
/
2
1
+
s
1
m
1
/
1
+
s
,with probability of at least 1
-
δ, where the constant c
~ is given by Proposition 11.From Proposition3, we can deduce that (
1
/
2
)
E
(
π
M
(
f
z
)
)
-
E
(
f
ρ
) in S
(
z
,
λ
) can be ignored by studying the new equivalent sampling error given by S
~
(
z
,
λ
)
=
S
(
z
,
λ
)
-
(
1
/
2
)
E
(
π
M
(
f
z
)
)
-
E
(
f
ρ
). The following corollary provides an asymptotically optimal convergence rate of f
z. The proof can be found in the Appendix.Corollary 7.
Letf
z be defined by (5), and Assumption 5 holds true. If L
K
0
-
r
f
ρ
∈
L
ρ
X
2, then when 1
<
N
<
r
<
2
N, for any 0
<
δ
<
1 and m
>
1360
log
⁡
(
1
/
δ
)
/
c
~
(
1
+
s
)
/
s, the following holds: (21)
S
~
z
,
λ
=
l
o
g
2
δ
O
1
m
2
r
/
2
r
1
+
s
+
s
N
,with probability of at least 1
-
δ, where λ
=
1
/
m
2
N
/
(
2
r
(
1
+
s
)
+
s
N
). Particularly, for K
N
∈
C
∞
(
X
), we have (22)
S
~
z
,
λ
=
l
o
g
2
δ
O
1
m
1
-
ϵ
,where ϵ is an arbitrary positive number.It is seen from Corollary7 that the ideal choice of the regularization parameter λ depends on the two quantities r and s, which are often unknown in advance. Alternatively, cross-validation technique is one of the commonly used tools in practice. It is worth noting that our approach selects the ideal kernel and the regularization parameter simultaneously, which is of significant difference from those classical fixed kernel methods.Next, we compare our rate with existing references. Recently, sharp learning rates have been established by advanced empirical process technique in [14]. Note that we use K
0 to replace the kernel K appearing in algorithm (3), where its covering number has polynomial decay index of p. To be precise, an upper bound of sampling error in [14] was given as(23)
S
z
,
λ
≤
2
D
λ
+
28
κ
D
λ
3
m
λ
l
o
g
2
δ
+
724
M
2
m
l
o
g
2
δ
+
2
C
1
1
m
2
/
2
+
p
1
λ
p
/
2
+
p
.From formula (A.2) in the Appendix, we can achieve that H
K
N
=
L
K
N
1
/
2
(
L
ρ
X
2
)
=
L
K
0
N
(
L
ρ
X
2
)
=
L
K
0
(
N
-
1
/
2
)
(
H
K
0
). Following the equivalent relationship between covering number and the spectrum of L
K (see Theorem 10 [13]), we see that sufficiently large N ensures that s
≪
p. Additionally, when 1
<
N
<
r
<
2
N, λ
m
i
n
{
(
r
-
N
)
/
(
2
N
)
,
0
} in Theorem 6 and D
(
λ
)
/
λ above are both constants and hence it follows that λ
m
i
n
{
r
/
N
,
2
}
=
λ
r
/
N
<
λ
=
c
D
(
λ
) with some constant c, since 0
<
λ
<
1. In summary, our derived sample error is sharper than that in [14]. Thus, if the regression function is smooth sufficiently, that is, which can also be approximated well by H
K
N, we conclude that the corresponding learning rate of Theorem 6 outperforms that in [14]. This shows that if we know the smoothness (
r
) of the target function, we can choose a proper kernel K
N (which requires N
>
r
/
2) to improve the sampling error effectively. This provides us an excellent theoretical basis in choosing kernel function for real problems. Of course, considering noises with the samples in real problems, the chosen kernel also has to be smoother than the target function.


## 4. Error Analysis

The sampling errorS
(
z
,
λ
) is analyzed according to empirical process technique. The initial study on sampling error mainly applies the McDiarmid inequality without considering the conception of “space complexity.” However, the McDiarmid inequality is not able to show the variance message of random variables. Afterwards, VC dimension was originally introduced into the literature and some other conceptions such as covering numbers formed in the Bernstein-type probability inequality significantly reduce the sampling error; see [19] for an explicit overview. To bound sample error, we split it into two parts again: (24)
S
z
,
λ
=
E
z
f
λ
-
E
z
f
ρ
-
E
f
λ
-
E
f
ρ
+
E
π
M
f
z
-
E
f
ρ
-
E
z
π
M
f
z
-
E
z
f
ρ
≔
S
1
z
,
λ
+
S
2
z
,
λ
.Note that S
1
(
z
,
λ
) does not involve any functional complexity, which in turn can be estimated easily by the following one-side Bernstein probability inequality.Lemma 8.
Defineξ as a random variable on the probability space Z, and there exists a constant M
ξ and it holds ξ
-
E
ξ
≤
M
ξ. Define the variance of ξ by σ
2; then, for any 0
<
δ
<
1, the following holds: (25)
1
m
∑
i
=
1
m
ξ
z
i
-
E
ξ
≤
2
M
ξ
log
⁡
1
/
δ
3
m
+
2
σ
2
log
⁡
1
/
δ
m
,with probability of at least 1
-
δ.Proposition 9.
Define random variableξ
1
(
z
)
=
(
f
λ
(
x
)
-
y
)
2
-
(
f
ρ
(
x
)
-
y
)
2. For any 0
<
δ
<
1 the following holds: (26)
S
1
z
,
λ
=
1
m
∑
i
=
1
m
ξ
1
z
i
-
E
ξ
1
≤
7
f
λ
∞
+
3
M
2
log
⁡
2
δ
3
m
+
1
2
f
λ
-
f
ρ
ρ
2
,with probability of at least 1
-
δ
/
2.Proof.
Notice that(27)
ξ
1
z
=
f
λ
x
-
f
ρ
x
f
λ
x
+
f
ρ
x
-
2
y
.Since f
ρ
x
≤
M is true almost everywhere, thus (28)
ξ
1
≤
c
≔
f
λ
∞
+
M
f
λ
∞
+
3
M
.This yields that ξ
2
-
E
ξ
2
≤
M
ξ
2
≔
2
c.
Additionally, notice thatE
(
ξ
1
)
2 satisfies (29)
E
f
λ
x
-
f
ρ
x
2
f
λ
x
+
f
ρ
x
-
2
y
2
≤
f
λ
∞
+
3
M
2
f
λ
-
f
ρ
ρ
2
,which implies that σ
2
(
ξ
1
)
≤
E
(
ξ
1
2
)
≤
c
f
λ
-
f
ρ
ρ
2.
By Lemma8 and the basic inequality a
b
≤
(
a
+
b
)
/
2 (a
,
b
≥
0), we obtain (30)
1
m
∑
i
=
1
m
ξ
1
z
i
-
E
ξ
1
≤
7
c
log
⁡
2
/
δ
3
m
+
1
2
f
λ
-
f
ρ
ρ
2with probability of at least 1
-
δ
/
2.Bounding the sampling errorS
2
(
z
,
λ
) is more involved, since the estimator f
z will vary with the random sample. To handle it, some advanced uniform concentration inequality is required [14].Lemma 10.
DefineG as a function set on Z. If there exists a constant c
ρ, then g
-
E
g
≤
B almost everywhere and E
(
g
2
)
≤
c
ρ
E
(
g
). Then for any positive number ɛ and 0
<
α
≤
1, (31)
P
r
o
b
z
∈
Z
m
s
u
p
g
∈
G
E
g
-
1
/
m
∑
i
=
1
m
g
z
i
E
g
+
ɛ
≥
4
α
ɛ
≤
N
G
,
α
ɛ
exp
⁡
-
α
2
m
ɛ
2
c
ρ
+
2
/
3
B
.Proposition 11.
Givenf
z defined by (5), suppose that Assumption 5 holds. When m
>
1360
log
⁡
(
1
/
δ
)
/
c
~
(
1
+
s
)
/
s, then, for any 0
<
δ
<
1, (32)
S
2
z
,
λ
≤
1
2
E
π
M
f
z
-
E
f
ρ
+
c
~
M
s
/
1
+
s
1
λ
s
/
2
1
+
s
1
m
1
/
1
+
swith probability of at least 1
-
δ, where c
~
=
(
1360
C
N
(
16
)
s
M
2
+
s
)
1
/
1
+
s.Proof.
Introduce a function setF
R defined by Proposition 9: (33)
F
R
=
π
M
f
x
-
y
2
-
f
ρ
x
-
y
2
:
f
∈
B
R
.Each function in F
R can be denoted as g
(
z
)
=
(
π
M
(
f
)
(
x
)
-
y
)
2
-
(
f
ρ
(
x
)
-
y
)
2, where f
∈
B
R. It follows that E
(
g
)
=
E
(
π
M
(
f
)
)
-
E
(
f
ρ
)
≥
0, (
1
/
m
)
∑
i
=
1
m
g
(
z
i
)
=
E
z
(
π
M
(
f
)
)
-
E
z
(
f
ρ
), and (34)
g
z
=
π
M
f
x
-
f
ρ
x
π
M
f
x
+
f
ρ
x
-
2
y
.
Also note thatπ
M
(
f
)
∞
≤
M and f
ρ
≤
M almost everywhere; we have (35)
g
z
≤
8
M
2
.This implies that (36)
g
-
E
g
≤
B
≔
16
M
2
.
Additionally notice that(37)
E
g
2
=
∫
X
π
M
f
x
-
f
ρ
x
2
π
M
f
x
+
f
ρ
x
-
2
y
2
≤
16
M
2
π
M
f
-
f
ρ
ρ
2
=
16
M
2
E
g
.By Lemma 10 with B
=
c
ρ
=
16
M
2 and α
=
1
/
4, we obtain(38)
E
π
M
f
-
E
f
ρ
-
E
z
π
M
f
-
E
z
f
ρ
E
π
M
f
-
E
f
ρ
+
ɛ
≤
ɛ
,with probability at least (39)
1
-
N
F
R
,
1
4
ɛ
exp
⁡
-
m
ɛ
16
2
c
ρ
+
2
/
3
B
≥
1
-
N
F
R
,
1
4
ɛ
e
x
p
-
m
ɛ
680
M
2
.Now we need to estimate covering number N
(
F
R
,
(
1
/
4
)
ɛ
).
For arbitraryg
1
,
g
2
∈
F
R, we obtain (40)
g
1
z
-
g
2
z
≤
f
1
x
-
f
2
x
π
M
f
1
x
+
π
M
f
2
x
-
2
y
.
Sinceπ
M
f
x
≤
M is true for any x
∈
X and π
M is contraction mapping, we have (41)
g
1
z
-
g
2
z
≤
4
M
f
1
x
-
f
2
x
,
∀
f
1
,
f
2
∈
B
R
.
Hence(42)
N
F
R
,
1
4
ɛ
≤
N
B
R
,
ɛ
16
M
≤
N
B
1
,
ɛ
16
M
B
.
According to Assumption5, suppose that (43)
C
N
16
M
B
s
1
ɛ
s
-
m
ɛ
680
M
2
=
log
⁡
δ
,where b
=
C
N
(
16
M
B
)
s and a
=
m
/
680
M
2. Then it can be written as (44)
ɛ
1
+
s
-
l
o
g
1
/
δ
a
ɛ
s
-
b
a
=
0
.
According to Lemma 7 given in [16] (45)
ɛ
≤
m
a
x
2
log
⁡
1
/
δ
a
,
2
b
a
1
/
1
+
s
.Substituting it into (38) and noticing that E
π
M
f
-
E
f
ρ
+
ɛ
(
ɛ
)
≤
(
1
/
2
)
E
(
π
M
(
f
)
)
-
E
(
f
ρ
)
+
ɛ, we further see that E
(
π
M
(
f
)
)
-
E
(
f
ρ
)
-
(
E
z
(
π
M
(
f
)
)
-
E
z
(
f
ρ
)
) can be bounded by (46)
1
2
E
π
M
f
-
E
f
ρ
+
m
a
x
1360
log
⁡
1
/
δ
m
,
c
~
B
s
/
1
+
s
1
m
1
/
1
+
s
.
Based on Lemma 4.1 given in [14], for each z
∈
Z
m we have (47)
f
z
K
N
≤
M
λ
.
Hence, if(48)
m
>
1360
log
⁡
1
/
δ
c
~
1
+
s
/
s
,we have (49)
1360
log
⁡
1
/
δ
m
≤
c
~
B
s
/
1
+
s
1
m
1
/
1
+
s
.Proposition 11 is completed by taking B
=
M
/
λ.According to the conclusion of Proposition9, two important quantities f
λ
∞ and f
λ
-
f
ρ
ρ
2 involved in S
1
(
z
,
λ
) need to be bounded.Lemma 12.
Letf
λ be defined as (13). If L
K
0
-
r
f
ρ
∈
L
ρ
X
2, the following holds: (50)
f
λ
K
N
≤
λ
m
i
n
r
-
N
/
2
N
,
0
L
K
0
-
r
f
ρ
L
ρ
X
2
,
f
λ
-
f
ρ
L
ρ
X
≤
λ
m
i
n
r
/
2
N
,
1
L
K
0
-
r
f
ρ
L
ρ
X
2
.It makes sense that the estimation off
λ is extended from Lemma  4.3 in [18], where K
0 takes place of K
N. Now we discuss the second quantity. In the classical algorithm (3), when r
>
1, the increase of smoothness of f
ρ is not able to improve the error f
λ
-
f
ρ
L
ρ
X, which is called the “saturation” phenomenon in the literature of inverse problems. While, for the algorithm we study, only when r
>
2
N, the saturation will happen. This shows specific advantages of using K
N instead of the original K
0 from the perspective of approximation theory.Proof of Lemma12.
According to [17], f
λ
=
(
λ
I
+
L
K
N
)
-
1
L
K
N
f
ρ. Notice that (51)
L
K
N
=
L
K
0
2
N
,and this yields (52)
f
λ
=
λ
I
+
L
K
0
2
N
-
1
L
K
0
2
N
f
ρ
=
λ
I
+
L
K
0
2
N
-
1
L
K
0
2
N
L
K
0
r
L
K
0
-
r
f
ρ
=
∑
k
=
1
∞
λ
k
2
N
+
r
λ
+
λ
k
2
N
L
K
0
-
r
f
ρ
,
e
k
L
ρ
X
2
e
k
,where {
λ
k
,
e
k
}
k is the corresponding spectrum of the integral operator L
K
0. Thus (53)
f
λ
K
N
2
=
∑
k
=
1
∞
λ
k
2
N
+
2
r
λ
+
λ
k
2
N
2
L
K
0
-
r
f
ρ
,
e
k
L
ρ
X
2
2
≤
λ
m
i
n
r
-
N
/
N
,
0
L
K
0
-
r
f
ρ
L
ρ
X
2
.
On the other hand, noting the fact thatf
λ
-
f
ρ
=
λ
(
λ
I
+
L
K
N
)
-
1
f
ρ and the assumption L
K
0
-
r
f
ρ
∈
L
ρ
X
2, we have (54)
f
λ
-
f
ρ
L
ρ
X
2
=
λ
λ
I
+
L
K
0
2
N
-
1
L
K
0
r
L
K
0
-
r
f
ρ
L
ρ
X
2
=
λ
∑
k
=
1
∞
α
k
λ
k
r
λ
k
2
N
+
λ
e
k
L
ρ
X
2
≤
λ
m
i
n
r
/
2
N
,
1
L
K
0
-
r
f
ρ
L
ρ
X
2
where  we  used  the  fact  that
α
l
2
=
L
K
0
-
r
f
ρ
L
ρ
X
2
.This is the end of proving Lemma 12.Together with Propositions9 and 11, Lemma 12, and the fact that f
λ
∞
≤
κ
N
f
λ
K
N, Theorem 6 is proved easily.


## 5. Numerical Experiments

### 5.1. Simulated Example

Although this paper mainly focuses on theoretical analysis, we can take some experiments to show its efficiency in practice. A simulated example is considered, where the true regression is an additive model. That is,(55)
f
∗
x
i
=
5
f
1
x
i
1
+
3
f
2
x
i
2
+
4
f
3
x
i
3
+
6
f
4
x
i
4with f
1
(
u
)
=
2
e
x
p
(
-
0.1
u
), f
2
(
u
)
=
(
2
u
-
1
)
2, f
3
(
u
)
=
s
i
n
(
π
u
)
/
(
2
-
s
i
n
π
u
), and f
4
(
u
)
=
0.2
s
i
n
(
π
u
)+0.1
c
o
s
(
π
u
)
+
0.3
s
i
n
2
(
π
u
)
+
0.5
c
o
s
3
(
π
u
)
+
0.5
s
i
n
3
(
π
u
). Firstly, generate x
i
j which are independent from U
(
-
0.5,0.5
); then generate y
i by y
i
=
f
∗
(
x
i
)
+
ϵ
i with ϵ
i
~
N
(
0,0.1
).For the above example, different scenarios are taken into account, with(
m
=
200
,
n
=
30
), (
m
=
400
,
n
=
100
), and (
m
=
500
,
n
=
120
), and each scenario is repeated 50 times. We here use the widely used Gaussian kernel, K
σ
(
x
,
u
)
=
e
x
p
(
-
x
-
u
2
/
σ
2
), where parameter σ will be specified by conducted 10-fold cross-validation on each data set. Besides, as we mentioned before, we start with a weak kernel K and search a better one somehow iteratively. A standard weak kernel is defined as follows: K
w
e
a
k
(
x
,
y
)
=
e
-
λ
x
-
y, where λ is an adjustable parameter, where we specify it as λ
=
0.1.The performance of various methods is measured by the MSE, where MSE represents the relative mean squared error for each kernel-based regression. The averaged performance measures are summarized in Table1. Note that SKM represents the single kernel method with the Gaussian kernel, UKM represents the proposed method without using any unlabeled data, and SEKM represents the proposed method with using all the unlabeled data.Table 1
Performance obtained using various kernel-based methods.
Method/sample Size
(m = 200, n = 30)
(m = 400, n = 100)
(m = 500, n = 120)
SKM
0.090 ± 0.032
0.093 ± 0.022
0.095 ± 0.018
UKM
0.085 ± 0.052
0.082 ± 0.037
0.080 ± 0.041
SEKM
0.080
±
0.062
0.077 ± 0.042
0.075 ± 0.036From Table1 we find that using the proposed kernel learning method on the data sets generates better prediction accuracy than using a single kernel. Probably, the true function is more complicated, and in this case the Gaussian kernel has a limited learning ability. Thus, learning to start with a weak kernel implies that the hypothesis space is much larger than that induced by the Gaussian kernel, so that the true function can be learnt well by our algorithm. Moreover, from the last row of Table 1, we see that using the unlabeled data by our algorithm can further reduce the prediction error, as we expect in theory.


### 5.2.  Real Example

The proposed method is also applied to a real example, the Boston housing data, which is publicly available. The Boston housing data concerns the median value of owner-occupied homes in each of the 506 census tracts in the Boston Standard Metropolitan Statistical Area in 1970. It consists of 13 variables, including per capita crime rate by town (CRIM), proportion of residential land zoned for lots over 25,000 square feet (ZN), proportion of nonretail business acres per town (INDUS), Charles River dummy variable (CHAS), nitric oxides concentration (NOX), average number of rooms per dwelling (RM), proportion of owner-occupied units built prior to 1940 (AGE), weighted distances to five Boston employment centers (DIS), index of accessibility to radial highways (RAD), full-value property-tax rate per $10000 (TAX), pupil-teacher ratio by town (PTRATIO), the proportion of blacks by town (B), and lower status of the population (LSTAT), which may affect the housing price.In our analysis, all the variables are standardized. To compute the averaged prediction error, each dataset is randomly split into two parts: training data and testing data with the number30. To show the performance our method compared with a single kernel method, we split the training data with three different scenarios with (
m
=
300
,
n
=
30
), (
m
=
350
,
n
=
40
), and (
m
=
426
,
n
=
50
), and each scenario is repeated 50 times. Besides, parameter σ will be specified by conducted 10-fold cross-validation on each data set. The prediction performance of the single kernel method via the proposed method is summarized in Table 2.Table 2
On test set obtaining best accuracy for Boston housing.
Method/sample Size
(m = 300, n = 30)
(m = 350, n = 40)
(m = 426, n = 50)
SKM
1.774 ± 0.0931
1.712 ± 0.0835
1.675 ± 0.0733
UKM
1.785 ± 0.851
1.684 ± 0.737
1.633 ± 0.841
SEKM
1.764 ± 0.851
1.705 ± 0.752
1.625 ± 0.804As shown in the table, the proposed method is significant in terms of prediction accuracy, except that one of six results in Table2 is of poor performance compared to the single kernel method. This practical result may be acceptable, since we do not know the underlying rule for this real data, and it is hard to ensure a perfect performance in various settings. Totally, to some extent, the proposed method is a simple but efficient kernel learning method in the family of kernel methods.


## 5.1. Simulated Example

Although this paper mainly focuses on theoretical analysis, we can take some experiments to show its efficiency in practice. A simulated example is considered, where the true regression is an additive model. That is,(55)
f
∗
x
i
=
5
f
1
x
i
1
+
3
f
2
x
i
2
+
4
f
3
x
i
3
+
6
f
4
x
i
4with f
1
(
u
)
=
2
e
x
p
(
-
0.1
u
), f
2
(
u
)
=
(
2
u
-
1
)
2, f
3
(
u
)
=
s
i
n
(
π
u
)
/
(
2
-
s
i
n
π
u
), and f
4
(
u
)
=
0.2
s
i
n
(
π
u
)+0.1
c
o
s
(
π
u
)
+
0.3
s
i
n
2
(
π
u
)
+
0.5
c
o
s
3
(
π
u
)
+
0.5
s
i
n
3
(
π
u
). Firstly, generate x
i
j which are independent from U
(
-
0.5,0.5
); then generate y
i by y
i
=
f
∗
(
x
i
)
+
ϵ
i with ϵ
i
~
N
(
0,0.1
).For the above example, different scenarios are taken into account, with(
m
=
200
,
n
=
30
), (
m
=
400
,
n
=
100
), and (
m
=
500
,
n
=
120
), and each scenario is repeated 50 times. We here use the widely used Gaussian kernel, K
σ
(
x
,
u
)
=
e
x
p
(
-
x
-
u
2
/
σ
2
), where parameter σ will be specified by conducted 10-fold cross-validation on each data set. Besides, as we mentioned before, we start with a weak kernel K and search a better one somehow iteratively. A standard weak kernel is defined as follows: K
w
e
a
k
(
x
,
y
)
=
e
-
λ
x
-
y, where λ is an adjustable parameter, where we specify it as λ
=
0.1.The performance of various methods is measured by the MSE, where MSE represents the relative mean squared error for each kernel-based regression. The averaged performance measures are summarized in Table1. Note that SKM represents the single kernel method with the Gaussian kernel, UKM represents the proposed method without using any unlabeled data, and SEKM represents the proposed method with using all the unlabeled data.Table 1
Performance obtained using various kernel-based methods.
Method/sample Size
(m = 200, n = 30)
(m = 400, n = 100)
(m = 500, n = 120)
SKM
0.090 ± 0.032
0.093 ± 0.022
0.095 ± 0.018
UKM
0.085 ± 0.052
0.082 ± 0.037
0.080 ± 0.041
SEKM
0.080
±
0.062
0.077 ± 0.042
0.075 ± 0.036From Table1 we find that using the proposed kernel learning method on the data sets generates better prediction accuracy than using a single kernel. Probably, the true function is more complicated, and in this case the Gaussian kernel has a limited learning ability. Thus, learning to start with a weak kernel implies that the hypothesis space is much larger than that induced by the Gaussian kernel, so that the true function can be learnt well by our algorithm. Moreover, from the last row of Table 1, we see that using the unlabeled data by our algorithm can further reduce the prediction error, as we expect in theory.


## 5.2.  Real Example

The proposed method is also applied to a real example, the Boston housing data, which is publicly available. The Boston housing data concerns the median value of owner-occupied homes in each of the 506 census tracts in the Boston Standard Metropolitan Statistical Area in 1970. It consists of 13 variables, including per capita crime rate by town (CRIM), proportion of residential land zoned for lots over 25,000 square feet (ZN), proportion of nonretail business acres per town (INDUS), Charles River dummy variable (CHAS), nitric oxides concentration (NOX), average number of rooms per dwelling (RM), proportion of owner-occupied units built prior to 1940 (AGE), weighted distances to five Boston employment centers (DIS), index of accessibility to radial highways (RAD), full-value property-tax rate per $10000 (TAX), pupil-teacher ratio by town (PTRATIO), the proportion of blacks by town (B), and lower status of the population (LSTAT), which may affect the housing price.In our analysis, all the variables are standardized. To compute the averaged prediction error, each dataset is randomly split into two parts: training data and testing data with the number30. To show the performance our method compared with a single kernel method, we split the training data with three different scenarios with (
m
=
300
,
n
=
30
), (
m
=
350
,
n
=
40
), and (
m
=
426
,
n
=
50
), and each scenario is repeated 50 times. Besides, parameter σ will be specified by conducted 10-fold cross-validation on each data set. The prediction performance of the single kernel method via the proposed method is summarized in Table 2.Table 2
On test set obtaining best accuracy for Boston housing.
Method/sample Size
(m = 300, n = 30)
(m = 350, n = 40)
(m = 426, n = 50)
SKM
1.774 ± 0.0931
1.712 ± 0.0835
1.675 ± 0.0733
UKM
1.785 ± 0.851
1.684 ± 0.737
1.633 ± 0.841
SEKM
1.764 ± 0.851
1.705 ± 0.752
1.625 ± 0.804As shown in the table, the proposed method is significant in terms of prediction accuracy, except that one of six results in Table2 is of poor performance compared to the single kernel method. This practical result may be acceptable, since we do not know the underlying rule for this real data, and it is hard to ensure a perfect performance in various settings. Totally, to some extent, the proposed method is a simple but efficient kernel learning method in the family of kernel methods.


## 6. Conclusions and Discussions

This paper mainly discussed the kernel learning problems within semisupervised learning setting. Our candidate kernel sequence is generated by a simple iterative procedure using large amounts of unlabeled data. Under mild assumptions on target function, it is shown that we can match a kernel theoretically to outperform efficiently the sample error induced by one-kernel learning. This also shows that the learning kernel function outperforms traditional kernel-based learning algorithms in our case. Moreover, a simulation example and a real data experiment are implemented, respectively, to show the effectiveness of our proposed method.We note that the space complexity of function space in the paper is described by covering number, which was a straightaway conception. Yet it is not a perfect choice theoretically. Combining with the way in which the kernel function was formed in the text, we can replace Assumption5 with the eigenvalue asymptotic behavior assumption on the integration operator L
K
0. Based on its relationship among entropy and the Rademacher complexity, a better theoretical results may be achieved. This will be our subsequent work in the future. We attempt to explore some intrinsic structure of input space by selecting an appropriate kernel. Perhaps, there are other more effective ways to explore these underlying structures.



---

*Source: 451947-2015-09-08.xml*