# A Multikernel-Like Learning Algorithm Based on Data Probability Distribution

Authors: Guo Niu; Zhengming Ma; Shuyu Liu
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In the machine learning based on kernel tricks, people often put one variable of a kernel function on the given samples to produce the basic functions of a solution space of learning problem. If the collection of the given samples deviates from the data distribution, the solution space spanned by these basic functions will also deviate from the real solution space of learning problem. In this paper a multikernel-like learning algorithm based on data probability distribution (MKDPD) is proposed, in which the parameters of a kernel function are locally adjusted according to the data probability distribution, and thus produces different kernel functions. These different kernel functions will generate different Reproducing Kernel Hilbert Spaces (RKHS). The direct sum of the subspaces of these RKHS constitutes the solution space of learning problem. Furthermore, based on the proposed MKDPD algorithm, a new algorithm for labeling new coming data is proposed, in which the basic functions are retrained according to the new coming data, while the coefficients of the retrained basic functions remained unchanged to label the new coming data. The experimental results presented in this paper show the effectiveness of the proposed algorithms.


---

## Body

## 1. Introduction

(a) Data Spaces and Data Distributions. Let X represent the data and Ω the data space. In mathematics, the data X can be regarded as a random variable/vector/matrix defined on the data space Ω. There will be different kinds of data on a data space. For example, the data space Ω can be the one consisting of all images of 512
×
512 pixels, while the data X
f represents all face images of 512
×
512 pixels and the data X
l represents all landscape images of 512
×
512 pixels; both of them are defined on the data space Ω but subject to different probability distributions.If the data is regarded as a random variable, the samples of data can be then regarded as the concrete realization of the random variable. In machine learning, the samples of data can be exploited to estimate the probability distribution of data (the probabilistic modeling of data). There are a lots of researches on the probabilistic modeling of data [1–3].(b) Classification/Labels and Classifiers/Label Functions. The classification of the data may be different when the data are used in different applications. For example, let the data be the face images. In the application of identification recognition, the face images of the same person are all grouped into the same class, even though the expressions and postures of these face images may be different. However, in the application of expression recognition, the face images of the same expression are all grouped into the same class, even though these face images belong to different persons.The classifier of data is a machine indicating the class to which a data point belongs. The classifiers of data are trained with the data samples [4, 5]. The classes of data are also called the labels of data and the classifiers of data are also called the label functions of data. In this paper, we adopt the terminology of labels and label functions of data.(c) Kernel Tricks in Machine Learning. The applications of kernel tricks in machine learning can be roughly divided into two categories: the transformation of data spaces and the construction of label functions. In the transformation of data spaces, the kernel functions are used to transform data spaces into other spaces where the data can be linearly separated. The famous Kernel PCA [6] and kernel Fisher discriminant (KFD) [7] belong to this category. In the construction of label functions, the kernel functions are used to serve as the basic functions of label functions. The famous manifold regularization learning [8, 9] belongs to this category. In this paper we address the problems involved in the construction of label functions.In the construction of label functions, the label functions are expressed asf
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
), where k
(
x
,
v
) represents a kernel function, {
x
1
⋯
x
b
} the labeled samples, and {
x
b
+
1
⋯
x
b
+
u
} the unlabeled samples. The coefficients α
→
=
[
α
1
⋯
α
b
+
u
] can be derived from solving the following learning problem:(1)α→∗=argminf∈HX⁡∑i=1bVyi,fxi+κfHX2=argminα→∈Rb+u⁡∑i=1bVyi,∑j=1b+uαikxi,xj+κα→TKXα→.In the above equation, H
X
=
s
p
a
n
{
k
(
x
,
x
i
)
∣
i
=
1
,
…
,
b
+
u
} represents the solution space of the learning problem; {
y
1
⋯
y
b
} represents the labels of the labeled samples {
x
1
⋯
x
b
};(2)KX=kx1,x1⋯kx1,xb+u⋮⋱⋮kxb+u,x1⋯kxb+u,xb+urepresents the kernel matrix; and V
(
y
i
,
f
(
x
i
)
) represents the cost function. We want to find a label function f
(
x
) which will make the cost as small as possible.There are two kinds of properties about the data. The first kind of properties is the natural properties of data. The probability distributions of data are the examples of natural properties of data. The second kind of properties is the semantic properties of data. The data labels are the examples of semantic properties of data. It is clear that, in the framework of learning problem shown in (1), the semantic properties hidden in the data labels have been fully utilized, while the natural properties hidden in data probability distributions seem not to be deeply exploited. At present, the usual way to learn more information other than the data labels is to add various regularization terms to the cost function. For example, in the manifold regularization learning [8–11], a manifold regularization term is added to the cost function:(3)f∗=argminf∈HX⁡∑i=1bVyi,fxi+κfHX2+λfM2,where f
M
2
=
f
→
X
T
L
X
f
→
X is the so-called manifold regularization term, in which f
→
X
=
[
f
(
x
1
)
⋯
f
(
x
b
+
u
)
] and L
X is the Laplacian matrix reflecting the adjacency relations of data samples [12].However, the addition of too many regularization terms to the cost function will make the learning problem complicated and difficult to solve. In this paper, rather than adding regularization terms, an alternative way to exploit the data probability distribution in the learning problem is proposed. For the convenience of description, let us denote the kernel function ask
(
x
,
z
∣
θ
), where θ represents the parameter of the kernel function. In the proposed algorithm, the parameters of the basic functions k
(
x
,
x
i
∣
θ
i
) are adjusted based on the data distribution sample-by-sample; that is, θ
i
=
θ
(
p
(
x
i
)
), where p
(
x
) is the probability distribution of data, i
=
1
,
…
,
b
+
u. These basic functions are then used to span the solution space of the learning problem: H
D
=
s
p
a
n
{
k
(
x
,
x
i
∣
θ
i
)
∣
i
=
1
,
…
,
b
+
u
}. It is clear that the probability distribution of data is integrated into the basic functions.According to the theory of kernel functions, ifθ
i
≠
θ
j, then k
(
x
,
z
∣
θ
i
) and k
(
x
,
z
∣
θ
j
) are two different kernel functions and will generate two different RKHS. Now let H
i denote the RKHS generated by the kernel function k
(
x
,
z
∣
θ
i
), i
=
1
,
…
,
b
+
u; then, theoretically speaking, the solution space H
D can be regarded as a subspace of the direct sum space H
1
⊕
⋯
⊕
H
b
+
u. Therefore, the proposed algorithm can be regarded as a kind of multikernel learning algorithm, but quite different from the commonly used multikernel learning algorithm [13–16]. Therefore, we call the proposed algorithm the multikernel-like learning algorithm based on data probability distribution, referred to as MKDPD algorithm.How to label the new coming data (the out-of-samples)x is the key topic in machine learning [12, 17, 18]. There are two extreme algorithms. One algorithm uses the original label function f
o
l
d to label the new coming data x; that is, the labels of the new coming data x are given by f
o
l
d
(
x
). This algorithm is best in efficiency, but worst in accuracy. Another algorithm regards the new coming data x as the unlabeled samples and mixes the new coming data x with the original samples to retrain a new label function f
n
e
w. The labels of the new coming data x are then given by f
n
e
w
(
x
). This latter algorithm is best in accuracy, but worst in efficiency. Various algorithms for labeling new coming data are the trade-off between these two extreme algorithms. In the proposed MKDPD algorithm, there are two learning processes. In the first learning process, the basic functions of label function are trained. In the second learning process, the weights of basic functions in the label function are solved. Accordingly, a new algorithm for labeling the new coming data is proposed. In the proposed algorithm, the new coming data will be exploited in the first learning process to retrain the basic functions, but the weights of basic functions remained unchanged and combined with the retrained basic functions to label new coming data. The proposed labeling algorithm achieves a better trade-off between the computational efficiency and accuracy.The rest of the paper is arranged as follows: in Section2, the literatures related to our work are reviewed briefly. In Section 3, the main theories of kernel functions and RKHS are introduced. In Section 4, the MKDPD algorithm is proposed. In Section 5, an MKDPD-based algorithm for labeling new coming data is proposed. In Section 6, the experimental results on toy and real-world data are presented to show the performance of the MKDPD algorithms. In Section 7, some conclusions are presented for reference.


## 2. Related Works

Learning from the given data is the main process to machine learning. So how to fully make use of the given samples is the key to the successful learning. In general, supervised learning has sufficient labeled samples and these kinds of algorithms are suitable for classification problems, such as the representative linear discriminant analysis (LDA) [19] and KFD [7]. In practice, a large number of samples are unlabeled, only a small number of samples are labeled. In this case, supervised learning algorithms do not effectively make use of the information hidden in unlabeled samples. To tackle the issue, semisupervised learning [18] is proposed and a wide range of semisupervised learning algorithms have been proposed and widely applied in many areas of machine learning.In recent years, the study of semisupervised learning is not limited to the simple introduction of unlabeled data. Many researchers pay attention to exploit the intrinsic geometry of data and introduce the kernel learning to semisupervised methods. For example, manifold regularization learning proposed by Belkin et al. [8] exploits the underlying data structure by adding a manifold regular term to a general-purpose learner. And following it, a serious of algorithms are proposed. Sindhwani et al. [20] proposed a linear MR (LMR) algorithm, in which a global linear mapping between the samples and their labels is constructed for labeling novel samples. Inspired by Gaussian fields and harmonic functions (GFHF) [21], local and global consistency (LGC) [22], and LMR [20], Nie et al. [23] extended LMR algorithm to flexible manifold embedding algorithm (FMA). FMA relaxes the hard linear constraint in LMR by adding a flexible regression residue. Geng et al. [10] proposed the ensemble manifold regularization (EMR) to deal with the aforementioned problems by learning an optimal graph Laplacian based on a set of given candidate graph Laplacian. With the spare assumption, Fan et al. [24] replaced the manifold regularizer with a sparse regularizer under the MR framework. Luo et al. [11] applied MR framework to solve the problem of multilabel image classification by learning a discriminative subspace.Introducing kernel trick to semisupervised learning methods is an important progress in machine learning. The kernel function [17] is either used to map input sample into a high dimensional kernel space for learning problem nonlinearization, or used to span a RKHS for the learning of label function. Take the MR learning as example, the label function (classifier function) in MR is a linear combination of single kernel function on labeled and unlabeled samples and the performance of MR algorithms strongly depends on this label function.The theory of RKHS plays an important role in kernel methods and RKHS has found a wide range of applications such as minimum variance unbiased estimation of regression coefficients, least squares estimation of random variables, detection of signals in Gaussian noise, problems in optimal approximation [25]. Some RKHS-based learning algorithms appearing recently find applications to online learning with the problem of classification or regression [26–28], while others find applications to the classification of hyperspectral images [29, 30]. Gurram and Kwon [29] achieved the weights for SVM separating hyperplanes by combining both local spectral and spatial information. Gu et al. [30] introduced the conception of Multiple-Kernel Hilbert Space (MKHS) to analyze spectral unmixing problems, and the resultant algorithm performs well in solving nonlinear problems.In theory, RKHS can be generated with some specific functions called kernel functions such as Gaussian, Laplacian, and polynomial [31]. Modifying kernel functions is a way of improving the performance of kernel methods; for example, Wu and Amari [32] extended conformal transformation of kernel functions to improve the performance of Support Vector Machine classifiers, Gurram and Kwon [33] defined a new inner product to warp the RKHS structure to reflect the intrinsic geometry of the given samples, and the literatures [33, 34] obtained the best kernel parameters by calculating the derivatives of objective functions. The application of multiple kernels is hot topic in kernel methods and multikernel learning (MKL) [35] is a successful method, which enhances the interpretability of the classifier with a combination of base kernels and improves the performances of kernel methods. MKL algorithms have been widely investigated [13–16, 35–37] and the reviews of MKL algorithms can be found in [13, 14]. MKL offers a feasible scheme to ensemble multiple kernels, but high computational cost raised by optimization procedure is a bad limitation when it is used to process large-scale data and a number of kernels. Therefore, one main research direction in MKL is how to effectively solve the MKL problem. Lots of MKL algorithms have been proposed; for example, SimpleMKL [36] proposed by Rakotomamonjy et al. is one of the state-of-the-art algorithms used to solve MKL problem which is addressed by a simple subgradient descent method. However, the MKL task is still challenging because it must on one hand learn an optimal combination of multiple kernels and determine the optimal classifier in each iteration and on the other hand make sure that the two optimization procedures are feasible.


## 3. RKHS and Its Application to Machine Learning

### 3.1. RKHS

In machine learning RKHS are often used as the solution spaces of learning problems. The definition of RKHS is as follows.Definition 1.
LetH
=
(
S
(
Ω
)
,
〈
·
,
·
〉
) be a Hilbert space; if there is a function k
:
Ω
×
Ω
→
R, such that(a)
∀
v
∈
Ω, k
(
x
,
v
)
=
k
v
(
x
)
∈
S
(
Ω
);
(b)
∀
f
∈
S
(
Ω
), f
(
x
)
=
〈
f
,
k
x
〉
=
〈
f
(
·
)
,
k
(
·
,
x
)
〉,then, H is said to be a Reproducing Kernel Hilbert Space (RKHS) and the function k
(
x
,
z
) is called the reproducing kernel of H.Note that inH
=
(
S
(
Ω
)
,
〈
·
,
·
〉
), Ω is a data space, S
(
Ω
) is a linear space of functions defined on the data space Ω, and 〈
·
,
·
〉 is an inner product defined on S
(
Ω
). According to the theory of RKHS, RKHS can be generated from a kernel function. The kernel function is defined as follows.Definition 2.
Letk
:
Ω
×
Ω
→
R be a function such that(a)
symmetric:∀
x
,
v
∈
Ω, k
(
x
,
v
)
=
k
(
v
,
x
);
(b)
positive definite: for all the positive integern and all data v
1
,
…
,
v
n
∈
Ω, the following matrix K
∈
R
n
×
n is positive definite:(4)kv1,v1⋯kv1,vn⋮⋱⋮kvn,v1⋯kvn,vn;then the function k
(
x
,
v
) is called a kernel function.A kernel functionk
(
x
,
v
) can be used to generate a RKHS such that the kernel function is the reproducing kernel of RKHS. The generating procedure is as follows.First, a linear space can be generated from the kernel functionk
(
x
,
v
), (5)
S
k
Ω
=
s
p
a
n
k
v
x
∣
k
v
x
=
k
x
,
v
,
v
∈
Ω
=
f
x
∣
f
x
=
∑
i
=
1
n
α
i
k
x
,
v
i
,
α
i
∈
R
,
v
i
∈
Ω
,
i
=
1
,
…
,
n
,
n
∈
N
,where N is the set of all positive integers.Second, an inner product〈
·
,
·
〉
k is defined on S
k
(
Ω
); that is, for all f
,
g
∈
S
k
(
Ω
), since f
(
x
)
=
∑
i
=
1
n
α
i
k
(
x
,
v
i
) and g
(
x
)
=
∑
j
=
1
n
β
j
k
(
x
,
u
j
), the inner product of f and g is then defined as(6)f,gk=∑i=1n∑j=1nαiβjkvi,uj.It is easy to prove that the definition of 〈
·
,
·
〉
k meets the requirements of the inner product and, therefore, H
k
=
(
S
k
(
Ω
)
,
〈
·
,
·
〉
k
) is an inner product space.It is worth noting that for allf
∈
S
k
(
Ω
), since f
(
x
)
=
∑
i
=
1
n
α
i
k
(
x
,
v
i
)
(7)f·,k·,xk=∑i=1nαik·,vi,k·,xk=∑i=1nαik·,vi,k·,xk=∑i=1nαikx,vi=fx.That is to say, the functions in the inner spaceH
k can be reproduced with the kernel function k
(
x
,
v
).Third, the inner spaceH
k can be completed if it is not completed. The completion of H
k, denoted by H
¯
k, is then a RKHS and the kernel function k
(
x
,
v
) is the reproducing kernel of H
¯
k. By the way, it can be seen from the completion that the inner space H
k is dense in the RKHS H
¯
k.


### 3.2. Solution Spaces of Machine Learning Problems

In practice, it is impossible to take the spaceH
k as the solution space of learning problem because it is infinite-dimensional. It is reasonable to require that the solution space be both finite-dimensional and sample-dependent. Thus, for the given samples {
x
1
,
…
,
x
b
,
x
b
+
1
,
…
,
x
b
+
u
}, a linear space can be generated as follows: (8)SXΩ=spankx,xi∣i=1,…,b+u=∑i=1b+uαikx,xi∣αi∈R,i=1,…,b+u.It is clear that S
X
(
Ω
) is both finite-dimensional and sample-dependent. Furthermore, S
X
(
Ω
) is exactly a subspace of S
k
(
Ω
) and therefore H
X
=
(
S
X
(
Ω
)
,
〈
·
,
·
〉
k
) is a subspace of H
k. Since H
X is finite-dimensional, then it is complete; that is, H
X is a Hilbert space. However, H
X is no longer a RKHS.For all functionsf
,
g
∈
S
X
(
Ω
), since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
) and g
(
x
)
=
∑
i
=
1
b
+
u
β
i
k
(
x
,
x
i
), then, according to (6), we have(9)f,gk=∑i=1b+u∑j=1b+uαiβjkxi,xj=α→TKXβ→,where α
→
=
[
α
1
⋯
α
b
+
u
]
T, β
→
=
[
β
1
⋯
β
b
+
u
]
T, and(10)KX=kx1,x1⋯kx1,xb+u⋮⋱⋮kxb+u,x1⋯kxb+u,xb+u.Since the matrix K
X is symmetric and positive definite, the inner product on S
X
(
Ω
) can be defined by itself, not necessarily inherited from 〈
·
,
·
〉
k. In fact, for all f
,
g
∈
S
X
(
Ω
), the inner product can be defined as(11)f,gX=α→TKXβ→.It can be easily proven that the definition of 〈
·
,
·
〉
X meets the requirements of inner product and therefore H
X
=
(
S
X
(
Ω
)
,
〈
·
,
·
〉
X
) is an inner space. Again, since S
X
(
Ω
) is finite-dimensional, H
X is complete. In machine learning, it is the space H
X that is taken as the solution space of learning problem.


## 3.1. RKHS

In machine learning RKHS are often used as the solution spaces of learning problems. The definition of RKHS is as follows.Definition 1.
LetH
=
(
S
(
Ω
)
,
〈
·
,
·
〉
) be a Hilbert space; if there is a function k
:
Ω
×
Ω
→
R, such that(a)
∀
v
∈
Ω, k
(
x
,
v
)
=
k
v
(
x
)
∈
S
(
Ω
);
(b)
∀
f
∈
S
(
Ω
), f
(
x
)
=
〈
f
,
k
x
〉
=
〈
f
(
·
)
,
k
(
·
,
x
)
〉,then, H is said to be a Reproducing Kernel Hilbert Space (RKHS) and the function k
(
x
,
z
) is called the reproducing kernel of H.Note that inH
=
(
S
(
Ω
)
,
〈
·
,
·
〉
), Ω is a data space, S
(
Ω
) is a linear space of functions defined on the data space Ω, and 〈
·
,
·
〉 is an inner product defined on S
(
Ω
). According to the theory of RKHS, RKHS can be generated from a kernel function. The kernel function is defined as follows.Definition 2.
Letk
:
Ω
×
Ω
→
R be a function such that(a)
symmetric:∀
x
,
v
∈
Ω, k
(
x
,
v
)
=
k
(
v
,
x
);
(b)
positive definite: for all the positive integern and all data v
1
,
…
,
v
n
∈
Ω, the following matrix K
∈
R
n
×
n is positive definite:(4)kv1,v1⋯kv1,vn⋮⋱⋮kvn,v1⋯kvn,vn;then the function k
(
x
,
v
) is called a kernel function.A kernel functionk
(
x
,
v
) can be used to generate a RKHS such that the kernel function is the reproducing kernel of RKHS. The generating procedure is as follows.First, a linear space can be generated from the kernel functionk
(
x
,
v
), (5)
S
k
Ω
=
s
p
a
n
k
v
x
∣
k
v
x
=
k
x
,
v
,
v
∈
Ω
=
f
x
∣
f
x
=
∑
i
=
1
n
α
i
k
x
,
v
i
,
α
i
∈
R
,
v
i
∈
Ω
,
i
=
1
,
…
,
n
,
n
∈
N
,where N is the set of all positive integers.Second, an inner product〈
·
,
·
〉
k is defined on S
k
(
Ω
); that is, for all f
,
g
∈
S
k
(
Ω
), since f
(
x
)
=
∑
i
=
1
n
α
i
k
(
x
,
v
i
) and g
(
x
)
=
∑
j
=
1
n
β
j
k
(
x
,
u
j
), the inner product of f and g is then defined as(6)f,gk=∑i=1n∑j=1nαiβjkvi,uj.It is easy to prove that the definition of 〈
·
,
·
〉
k meets the requirements of the inner product and, therefore, H
k
=
(
S
k
(
Ω
)
,
〈
·
,
·
〉
k
) is an inner product space.It is worth noting that for allf
∈
S
k
(
Ω
), since f
(
x
)
=
∑
i
=
1
n
α
i
k
(
x
,
v
i
)
(7)f·,k·,xk=∑i=1nαik·,vi,k·,xk=∑i=1nαik·,vi,k·,xk=∑i=1nαikx,vi=fx.That is to say, the functions in the inner spaceH
k can be reproduced with the kernel function k
(
x
,
v
).Third, the inner spaceH
k can be completed if it is not completed. The completion of H
k, denoted by H
¯
k, is then a RKHS and the kernel function k
(
x
,
v
) is the reproducing kernel of H
¯
k. By the way, it can be seen from the completion that the inner space H
k is dense in the RKHS H
¯
k.


## 3.2. Solution Spaces of Machine Learning Problems

In practice, it is impossible to take the spaceH
k as the solution space of learning problem because it is infinite-dimensional. It is reasonable to require that the solution space be both finite-dimensional and sample-dependent. Thus, for the given samples {
x
1
,
…
,
x
b
,
x
b
+
1
,
…
,
x
b
+
u
}, a linear space can be generated as follows: (8)SXΩ=spankx,xi∣i=1,…,b+u=∑i=1b+uαikx,xi∣αi∈R,i=1,…,b+u.It is clear that S
X
(
Ω
) is both finite-dimensional and sample-dependent. Furthermore, S
X
(
Ω
) is exactly a subspace of S
k
(
Ω
) and therefore H
X
=
(
S
X
(
Ω
)
,
〈
·
,
·
〉
k
) is a subspace of H
k. Since H
X is finite-dimensional, then it is complete; that is, H
X is a Hilbert space. However, H
X is no longer a RKHS.For all functionsf
,
g
∈
S
X
(
Ω
), since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
) and g
(
x
)
=
∑
i
=
1
b
+
u
β
i
k
(
x
,
x
i
), then, according to (6), we have(9)f,gk=∑i=1b+u∑j=1b+uαiβjkxi,xj=α→TKXβ→,where α
→
=
[
α
1
⋯
α
b
+
u
]
T, β
→
=
[
β
1
⋯
β
b
+
u
]
T, and(10)KX=kx1,x1⋯kx1,xb+u⋮⋱⋮kxb+u,x1⋯kxb+u,xb+u.Since the matrix K
X is symmetric and positive definite, the inner product on S
X
(
Ω
) can be defined by itself, not necessarily inherited from 〈
·
,
·
〉
k. In fact, for all f
,
g
∈
S
X
(
Ω
), the inner product can be defined as(11)f,gX=α→TKXβ→.It can be easily proven that the definition of 〈
·
,
·
〉
X meets the requirements of inner product and therefore H
X
=
(
S
X
(
Ω
)
,
〈
·
,
·
〉
X
) is an inner space. Again, since S
X
(
Ω
) is finite-dimensional, H
X is complete. In machine learning, it is the space H
X that is taken as the solution space of learning problem.


## 4. A Multikernel-Like Learning Algorithm Based on Data Probability Distribution MKDPD

### 4.1. Motivation

As shown in (5), the space of label functions is as follows:(12)SXΩ=spankx,xi∣i=1,…,b+u.This means that the functions {
k
(
x
,
x
i
)
∣
i
=
1
,
…
,
b
+
u
} play the role of basic functions of S
X
(
Ω
). Obviously, these basic functions are only dependent on the locations of given samples and seem too simple to adapt to various probability distributions of data. Take Gaussian kernel function k
(
u
,
v
)
=
e
x
p
-
∥
u
-
v
∥
2
/
2
σ
2 as an example, the basic functions {
k
(
x
,
x
i
)
∣
i
=
1
,
…
,
b
+
u
} generated from Gaussian kernel function are identical with each other, only different in the locations of data space. A basic function can be derived from another basic function only by translation in the data space Ω. In fact, if i
≠
j, then(13)kix-xj+xi=exp-∥x-xj+xi-xi∥2/2σ2=kx,xj=kjx.Furthermore, since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
), then for all x
∈
Ω with p
(
x
)
≠
0, f
(
x
) should give the label of x. This means that sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
), where sup
⁡
p
(
p
) is the support of p
(
x
) and sup
⁡
p
(
k
(
·
,
x
i
)
) is the support of k
(
x
,
x
i
); that is, (14)sup⁡pp=x∣x∈Ω,px≠0,sup⁡pk·,xi=x∣x∈Ω,kx,xi≠0.If the relation sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) is not true, there would be x
∈
Ω such that p
(
x
)
≠
0, but f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
)
=
0; that is, f
(
x
) cannot give the label of x.However, the union∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) is dependent on the locations of the given data samples {
x
1
⋯
x
b
+
u
}, not dependent on the data probability distribution p
(
x
). In practice, kernel functions are often compactly supported and the data are not evenly distributed over the data space. In these cases, label function f
(
x
) will be overfitted in the areas where too many data samples are collected, or underfitted in the areas where there are too few data samples collected, or not fitted at all in the area where the union ∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) fails to cover.Based on the above considerations, a learning algorithm based on the data probability distribution is proposed in this paper. In the proposed algorithm, the union is not only dependent on the locations of the given samples, but also dependent on the data probability distribution.


### 4.2. Construction of Solution Spaces

For the convenience of description, letk
(
x
,
v
∣
θ
) denote the kernel function, where θ represents the parameter of the kernel function. Thus, for the given data samples {
x
1
⋯
x
b
+
u
} and data probability distribution p
(
x
), the basic functions of solution space generated from the kernel function k
(
x
,
v
∣
θ
) are expressed as k
(
x
,
x
i
∣
θ
i
), where θ
i
=
θ
p
(
i
), i
=
1
⋯
b
+
u.With these basic functions, we can span a linear spaceS
D
(
Ω
) as follows: (15)SDΩ=spankx,xi∣θi∣i=1,…,b+u=∑i=1b+uαikx,xi∣θi∣i=1,…,b+u.It is clear thatS
D
(
Ω
) is a finite-dimensional linear space. Further, in order to define an inner product on S
D
(
Ω
), we need to define a symmetric and positive definite matrix first:(16)MD=KDTKD+ρI,where ρ, I
∈
R
(
b
+
u
)
×
(
b
+
u
) is a unit matrix and(17)KD=kx1,x1∣θ1⋯kx1,xb+u∣θb+u⋮⋱⋮kxb+u,x1∣θ1⋯kxb+u,xb+u∣θb+u.Note that, since k
(
x
i
,
x
j
∣
θ
j
)
≠
k
(
x
j
,
x
i
∣
θ
i
), i
≠
j, K
D is not symmetric and positive definite. However, M
D is symmetric and definite positive and can be used to define an inner product 〈
·
,
·
〉
D on S
D
(
Ω
): for all f
,
g
∈
S
D
(
Ω
), since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
) and g
(
x
)
=
∑
j
=
1
b
+
u
β
j
k
(
x
,
x
j
∣
θ
j
), then(18)f,gD=α→TMDβ→,where α
→
=
[
α
1
⋯
α
b
+
u
]
T, β
→
=
[
β
1
⋯
β
b
+
u
]
T.It can be easily proven that〈
·
,
·
〉
D meets the requirements of inner product and therefore H
D
=
(
S
D
(
Ω
)
,
〈
·
,
·
〉
D
) is an inner product space. Furthermore, since S
D
(
Ω
) is finite-dimensional, H
D is then complete; that is, H
D is a Hilbert space. However, it is worth noting that H
D is neither a RKHS, nor a subspace of H
k. Recall that although H
X is not RKHS, H
X is a subspace of H
k.In the proposed algorithm,H
D is taken as the solution space of learning problem:(19)f∗=argminf∈HD⁡∑i=1bVyi,fxi+κfHD2+λfM2.Below we explain the rationality of the definition 〈
·
,
·
〉
D:(1)
If〈
·
,
·
〉
D is an inner product of S
D
(
Ω
), according to the linearity of inner product, for all f
,
g
∈
S
D
(
Ω
), we have(20)f,g=∑i=1b+uαik·,xi∣θi,∑j=1b+uβjk·,xj∣θj=∑i=1b+u∑j=1b+uαiβjk·,xi∣θi,k·,xj∣θj.
Usually, the inner product of functional space is often defined as the integral of product of functions; therefore we have(21)k·,xi∣θi,k·,xj∣θj=∫Ωkx,xi∣θikx,xj∣θjdx≈∑h=1b+ukxh,xi∣θikxh,xj∣θj.
Substituting (21) into (20) gives(22)f,g≈∑i=1b+u∑j=1b+u∑h=1b+uαiβjkxh,xi∣θikjxh,xj∣θj=α→TKDTKDβ→.
However the matrixK
D
T
K
D is only positive semidefinite and cannot be used to define an inner product. This problem can be easily solved by adding a regularization term ρ
I, where I
∈
R
(
b
+
u
)
×
(
b
+
u
) is the unit matrix and ρ is the regularization parameter: M
D
=
K
D
T
K
D
+
ρ
I.
The matrixM
D is now symmetric and positive definite and can be used to define an inner product on S
D
(
Ω
): (23)f,gD=α→TMDβ→=α→TKDTKDβ→+ρα→Tβ→≈α→TKDTKDβ→=f,g.
The regularization parameterρ can also alleviate the ill-condition of the matrix K
D
T
K
D and reduce the error stemming from the substitution of integral with summation in (29).
(2)
If the data probability distributionp
(
x
) is uniform, that is, p
(
x
) is constant on the support sup
⁡
p
(
p
), then θ
i
=
θ
(
p
(
x
i
)
), i
=
1
,
…
,
b
+
u. In this case, we have(24)k·,xi∣θi,k·,xj∣θj=kxi,xj∣θ,(25)f,g=f,gX.
Combining (23) and (25) will give the following result: (26)f,gD≈f,g=f,gX.
This means that if the parameterθ of the kernel function k
(
x
,
x
i
∣
θ
) does not adjuste sample by sample, then H
D
=
H
X.


### 4.3. Analytic Solutions to Learning Problems

#### 4.3.1. Analytic Solutions to Two-Class Learning Problems

In the proposed algorithm, the Hilbert spaceH
D is taken as the solution space of learning problems. Then for all f
∈
H
D, f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
), we have(27)f→D=fx1⋯fxb+uT=KDα→,f
D
2
=
α
→
T
M
α
→, f
M
2
=
α
→
T
K
D
T
L
X
K
D
α
→. Based on the above results, the problem shown in (19) can be simplified as follows: (28)
α
→
∗
=
arg
min
α
→
∈
R
b
+
u
⁡
∑
i
=
1
b
V
y
i
,
∑
i
=
1
b
+
u
α
i
k
x
i
,
x
j
∣
θ
j
+
α
→
T
κ
M
D
+
λ
K
D
T
L
X
K
D
α
→
.Furthermore, if the cost function V
(
y
,
f
(
x
)
) is set to be the square error function, that is, V
(
y
,
f
(
x
)
)
=
(
y
-
f
(
x
)
)
2, we have (29)α→∗=argminα→∈Rb+u⁡y→Ty→-2y→TSKDα→+α→TKDTSTSKD+κMD+λKDTLXKDα→=argminα→∈Rb+u⁡y→Ty→-2b→DTα→+α→TADα→=AD-1b→D,where S is the selection matrix, b
→
D
=
K
D
T
S
T
y
→, and A
D
=
K
D
T
S
T
S
K
D
+
κ
M
D
+
λ
K
D
T
L
X
K
D. Note that the matrix A
D is a symmetric and positive definite matrix.


#### 4.3.2. Analytic Solutions to Multiclass Learning Problems

In principle, the deduction shown above is also suitable for the multiclass learning problems. In fact, for the data samplex
i, its label y
i can take different values to indicate the different classes to which the data sample x
i belongs. However, in practice, the different values of y
i may be too close to facilitate the optimization calculation. Therefore, for the multiclass problems, we adopt another way to indicate the data labels.For the data samplex
i, let its label y
→
i be a C-dimensional vector, where C is the number of classes. If the data sample x
i belongs to the cth class, then the cth component of y
→
i is set to be 1 while the other components of y
→
i are set to zero, where c
=
1
,
…
,
C. Furthermore, a label function f
c
(
x
) is set to describe the probability that the data x belongs to the cth class. Based on these notations, the multiclass problem can be expressed as follows:(30)f∗=argminf⁡∑i=1by→i-g→i2+κ∑c=1Cf→cHD2+λ∑c=1Cf→cTLXf→c,where (31)f=f1,…,fC,g→i=f1xi⋮fCxi,f→c=fcx1⋮fcxl,i=1,…,l.We first calculate the term∑
c
=
1
C
f
→
c
H
D
2. Since f
c
(
x
)
∈
S
D
(
Ω
), then f
c
(
x
)
=
∑
i
=
1
b
+
u
α
i
c
k
(
x
,
x
i
∣
θ
i
) and(32)∑c=1Cf→cHD2=∑c=1Cα→cTMDα→c=TrATMDA,where α
→
c
=
[
α
1
c
,
…
,
α
b
+
u
c
]
T and A
=
[
α
→
1
,
…
,
α
→
C
].Secondly, we calculate the term∑
c
=
1
C
f
→
c
T
L
X
f
→
c. Since f
→
c
=
K
D
α
→
c then(33)∑c=1Cf→cTLXf→c=traceATKDTLXKDA.Thirdly, we calculate the term∑
i
=
1
b
y
→
i
-
g
→
i
2. Let Y
=
[
y
→
1
,
…
,
y
→
b
], G
=
[
g
→
1
,
…
,
g
→
b
], and F
=
[
f
→
1
,
…
,
f
→
C
]
=
K
D
A; then(34)∑i=1by→i-g→i2=Y-G2=traceYTY-2YSKDA+ATKDTSTSKDA.Again, the matrix S is a selection matrix such that G
=
F
T
S
T.At last, substituting (32), (33), and (34) into (30) will give the following result: (35)
A
∗
=
arg
min
A
⁡
t
r
a
c
e
Y
Y
T
-
2
Y
S
K
D
A
+
A
T
K
D
T
S
T
K
D
+
κ
M
D
+
λ
K
D
T
L
K
D
A
=
K
D
T
S
T
S
+
λ
L
+
κ
I
K
D
+
ρ
I
-
1
K
D
T
S
T
Y
T
.


### 4.4. The Framework of Multikernel-Like Learning Algorithms

In the algorithm proposed in this paper, the label functionf
(
x
) is set to be f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
), where the parameter θ
i is adjusted according to the data probability distribution p
(
x
) on the data sample x
i. In general, the data probability distribution is not uniform and therefore the parameter θ
i will be different sample by sample. As a result, the functions k
(
x
,
v
∣
θ
1
)
,
…
,
k
(
x
,
v
∣
θ
b
+
u
) are different kernel functions and will produce different RKHS. In this sense, the algorithm proposed in this paper can be regarded as a kind of multikernel learning algorithms, but quite different from the commonly used multikernel learning algorithm.In the commonly used multikernel learning algorithms, the multikernel function is a linear combination of multiple basic kernel functions:k
M
K
(
x
,
v
)
=
∑
j
=
1
M
β
j
k
j
(
x
,
v
), where the functions k
1
,
…
,
k
M are called basic kernel functions, while the function k
M
K
(
x
,
v
) is called the multikernel function. Since the basic kernel functions are symmetric and positive definite, it can be easily proven that the multikernel function is also symmetric and positive definite. Therefore the label function f
M
K
(
x
) based on the multikernel function can be expressed as (36)fMKx=∑i=1b+uαikMKx,xi=∑i=1b+uαi∑j=1Mβjkjx,xi=∑i=1b+u∑j=1Mαiβjkjx,xi,where the coefficients α
1
,
…
,
α
b
+
u and β
1
,
…
,
β
M are determined through machine learning.If we follow the ideas of the commonly used multikernel learning algorithms and regard the functionsk
(
x
,
v
∣
θ
1
)
,
…
,
k
(
x
,
v
∣
θ
b
+
u
) as the basic kernel functions, then the multikernel function becomes k
M
K
(
x
,
v
)
=
∑
j
=
1
M
β
j
k
(
x
,
v
∣
θ
j
). Thus, according to (36), the label function f
M
K
(
x
) based on the multikernel function becomes (37)fMKx=∑i=1b+uαikMKx,xi=∑i=1b+uαi∑j=1Mβjkx,xi∣θj≠∑i=1b+uαikx,xi∣θi=fx.It can be seen from (37) that, no matter how to adjust the coefficients β
1
,
…
,
β
M, it is impossible to make f
M
K
(
x
)
≠
f
(
x
). From the perspective of solution spaces, in the solution space of f
M
K
(
x
), there are b
+
u functions k
(
x
,
x
i
∣
θ
1
)
,
…
,
k
(
x
,
x
i
∣
θ
b
+
u
) around the data sample x
i, while in the solution space of f
(
x
), there is only one function k
(
x
,
x
i
∣
θ
i
) around the data sample x
i. Therefore the algorithm proposed in this paper is quite different from the commonly used multikernel learning algorithm.Nevertheless, the algorithm proposed in this paper still belongs to the realm of multikernel learning. As stated above, the functionsk
(
x
,
x
i
∣
θ
1
)
,
…
,
k
(
x
,
x
i
∣
θ
b
+
u
) are different kernel functions and can produce different RKHS: H
1
,
…
,
H
b
+
u. Now let V
i
=
{
α
k
(
x
,
x
i
∣
θ
i
)
∣
α
∈
R
}, as stated in Section 3.1; V
i is then a 1-dimensional subspace of H
i. Furthermore, the direct sum of these subspaces turns out to be(38)V=V1⊕⋯⊕Vb+u=∑i=1b+uαix,xi∣θi∣αi∈R.Obviously the direct sum of these subspaces is the solution space H
D.Due to the fact that our algorithm is different from the commonly used multikernel learning algorithm, but still involved in multiple kernel functions, our algorithm is called multikernel-like algorithm.


## 4.1. Motivation

As shown in (5), the space of label functions is as follows:(12)SXΩ=spankx,xi∣i=1,…,b+u.This means that the functions {
k
(
x
,
x
i
)
∣
i
=
1
,
…
,
b
+
u
} play the role of basic functions of S
X
(
Ω
). Obviously, these basic functions are only dependent on the locations of given samples and seem too simple to adapt to various probability distributions of data. Take Gaussian kernel function k
(
u
,
v
)
=
e
x
p
-
∥
u
-
v
∥
2
/
2
σ
2 as an example, the basic functions {
k
(
x
,
x
i
)
∣
i
=
1
,
…
,
b
+
u
} generated from Gaussian kernel function are identical with each other, only different in the locations of data space. A basic function can be derived from another basic function only by translation in the data space Ω. In fact, if i
≠
j, then(13)kix-xj+xi=exp-∥x-xj+xi-xi∥2/2σ2=kx,xj=kjx.Furthermore, since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
), then for all x
∈
Ω with p
(
x
)
≠
0, f
(
x
) should give the label of x. This means that sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
), where sup
⁡
p
(
p
) is the support of p
(
x
) and sup
⁡
p
(
k
(
·
,
x
i
)
) is the support of k
(
x
,
x
i
); that is, (14)sup⁡pp=x∣x∈Ω,px≠0,sup⁡pk·,xi=x∣x∈Ω,kx,xi≠0.If the relation sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) is not true, there would be x
∈
Ω such that p
(
x
)
≠
0, but f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
)
=
0; that is, f
(
x
) cannot give the label of x.However, the union∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) is dependent on the locations of the given data samples {
x
1
⋯
x
b
+
u
}, not dependent on the data probability distribution p
(
x
). In practice, kernel functions are often compactly supported and the data are not evenly distributed over the data space. In these cases, label function f
(
x
) will be overfitted in the areas where too many data samples are collected, or underfitted in the areas where there are too few data samples collected, or not fitted at all in the area where the union ∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
)
) fails to cover.Based on the above considerations, a learning algorithm based on the data probability distribution is proposed in this paper. In the proposed algorithm, the union is not only dependent on the locations of the given samples, but also dependent on the data probability distribution.


## 4.2. Construction of Solution Spaces

For the convenience of description, letk
(
x
,
v
∣
θ
) denote the kernel function, where θ represents the parameter of the kernel function. Thus, for the given data samples {
x
1
⋯
x
b
+
u
} and data probability distribution p
(
x
), the basic functions of solution space generated from the kernel function k
(
x
,
v
∣
θ
) are expressed as k
(
x
,
x
i
∣
θ
i
), where θ
i
=
θ
p
(
i
), i
=
1
⋯
b
+
u.With these basic functions, we can span a linear spaceS
D
(
Ω
) as follows: (15)SDΩ=spankx,xi∣θi∣i=1,…,b+u=∑i=1b+uαikx,xi∣θi∣i=1,…,b+u.It is clear thatS
D
(
Ω
) is a finite-dimensional linear space. Further, in order to define an inner product on S
D
(
Ω
), we need to define a symmetric and positive definite matrix first:(16)MD=KDTKD+ρI,where ρ, I
∈
R
(
b
+
u
)
×
(
b
+
u
) is a unit matrix and(17)KD=kx1,x1∣θ1⋯kx1,xb+u∣θb+u⋮⋱⋮kxb+u,x1∣θ1⋯kxb+u,xb+u∣θb+u.Note that, since k
(
x
i
,
x
j
∣
θ
j
)
≠
k
(
x
j
,
x
i
∣
θ
i
), i
≠
j, K
D is not symmetric and positive definite. However, M
D is symmetric and definite positive and can be used to define an inner product 〈
·
,
·
〉
D on S
D
(
Ω
): for all f
,
g
∈
S
D
(
Ω
), since f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
) and g
(
x
)
=
∑
j
=
1
b
+
u
β
j
k
(
x
,
x
j
∣
θ
j
), then(18)f,gD=α→TMDβ→,where α
→
=
[
α
1
⋯
α
b
+
u
]
T, β
→
=
[
β
1
⋯
β
b
+
u
]
T.It can be easily proven that〈
·
,
·
〉
D meets the requirements of inner product and therefore H
D
=
(
S
D
(
Ω
)
,
〈
·
,
·
〉
D
) is an inner product space. Furthermore, since S
D
(
Ω
) is finite-dimensional, H
D is then complete; that is, H
D is a Hilbert space. However, it is worth noting that H
D is neither a RKHS, nor a subspace of H
k. Recall that although H
X is not RKHS, H
X is a subspace of H
k.In the proposed algorithm,H
D is taken as the solution space of learning problem:(19)f∗=argminf∈HD⁡∑i=1bVyi,fxi+κfHD2+λfM2.Below we explain the rationality of the definition 〈
·
,
·
〉
D:(1)
If〈
·
,
·
〉
D is an inner product of S
D
(
Ω
), according to the linearity of inner product, for all f
,
g
∈
S
D
(
Ω
), we have(20)f,g=∑i=1b+uαik·,xi∣θi,∑j=1b+uβjk·,xj∣θj=∑i=1b+u∑j=1b+uαiβjk·,xi∣θi,k·,xj∣θj.
Usually, the inner product of functional space is often defined as the integral of product of functions; therefore we have(21)k·,xi∣θi,k·,xj∣θj=∫Ωkx,xi∣θikx,xj∣θjdx≈∑h=1b+ukxh,xi∣θikxh,xj∣θj.
Substituting (21) into (20) gives(22)f,g≈∑i=1b+u∑j=1b+u∑h=1b+uαiβjkxh,xi∣θikjxh,xj∣θj=α→TKDTKDβ→.
However the matrixK
D
T
K
D is only positive semidefinite and cannot be used to define an inner product. This problem can be easily solved by adding a regularization term ρ
I, where I
∈
R
(
b
+
u
)
×
(
b
+
u
) is the unit matrix and ρ is the regularization parameter: M
D
=
K
D
T
K
D
+
ρ
I.
The matrixM
D is now symmetric and positive definite and can be used to define an inner product on S
D
(
Ω
): (23)f,gD=α→TMDβ→=α→TKDTKDβ→+ρα→Tβ→≈α→TKDTKDβ→=f,g.
The regularization parameterρ can also alleviate the ill-condition of the matrix K
D
T
K
D and reduce the error stemming from the substitution of integral with summation in (29).
(2)
If the data probability distributionp
(
x
) is uniform, that is, p
(
x
) is constant on the support sup
⁡
p
(
p
), then θ
i
=
θ
(
p
(
x
i
)
), i
=
1
,
…
,
b
+
u. In this case, we have(24)k·,xi∣θi,k·,xj∣θj=kxi,xj∣θ,(25)f,g=f,gX.
Combining (23) and (25) will give the following result: (26)f,gD≈f,g=f,gX.
This means that if the parameterθ of the kernel function k
(
x
,
x
i
∣
θ
) does not adjuste sample by sample, then H
D
=
H
X.


## 4.3. Analytic Solutions to Learning Problems

### 4.3.1. Analytic Solutions to Two-Class Learning Problems

In the proposed algorithm, the Hilbert spaceH
D is taken as the solution space of learning problems. Then for all f
∈
H
D, f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
), we have(27)f→D=fx1⋯fxb+uT=KDα→,f
D
2
=
α
→
T
M
α
→, f
M
2
=
α
→
T
K
D
T
L
X
K
D
α
→. Based on the above results, the problem shown in (19) can be simplified as follows: (28)
α
→
∗
=
arg
min
α
→
∈
R
b
+
u
⁡
∑
i
=
1
b
V
y
i
,
∑
i
=
1
b
+
u
α
i
k
x
i
,
x
j
∣
θ
j
+
α
→
T
κ
M
D
+
λ
K
D
T
L
X
K
D
α
→
.Furthermore, if the cost function V
(
y
,
f
(
x
)
) is set to be the square error function, that is, V
(
y
,
f
(
x
)
)
=
(
y
-
f
(
x
)
)
2, we have (29)α→∗=argminα→∈Rb+u⁡y→Ty→-2y→TSKDα→+α→TKDTSTSKD+κMD+λKDTLXKDα→=argminα→∈Rb+u⁡y→Ty→-2b→DTα→+α→TADα→=AD-1b→D,where S is the selection matrix, b
→
D
=
K
D
T
S
T
y
→, and A
D
=
K
D
T
S
T
S
K
D
+
κ
M
D
+
λ
K
D
T
L
X
K
D. Note that the matrix A
D is a symmetric and positive definite matrix.


### 4.3.2. Analytic Solutions to Multiclass Learning Problems

In principle, the deduction shown above is also suitable for the multiclass learning problems. In fact, for the data samplex
i, its label y
i can take different values to indicate the different classes to which the data sample x
i belongs. However, in practice, the different values of y
i may be too close to facilitate the optimization calculation. Therefore, for the multiclass problems, we adopt another way to indicate the data labels.For the data samplex
i, let its label y
→
i be a C-dimensional vector, where C is the number of classes. If the data sample x
i belongs to the cth class, then the cth component of y
→
i is set to be 1 while the other components of y
→
i are set to zero, where c
=
1
,
…
,
C. Furthermore, a label function f
c
(
x
) is set to describe the probability that the data x belongs to the cth class. Based on these notations, the multiclass problem can be expressed as follows:(30)f∗=argminf⁡∑i=1by→i-g→i2+κ∑c=1Cf→cHD2+λ∑c=1Cf→cTLXf→c,where (31)f=f1,…,fC,g→i=f1xi⋮fCxi,f→c=fcx1⋮fcxl,i=1,…,l.We first calculate the term∑
c
=
1
C
f
→
c
H
D
2. Since f
c
(
x
)
∈
S
D
(
Ω
), then f
c
(
x
)
=
∑
i
=
1
b
+
u
α
i
c
k
(
x
,
x
i
∣
θ
i
) and(32)∑c=1Cf→cHD2=∑c=1Cα→cTMDα→c=TrATMDA,where α
→
c
=
[
α
1
c
,
…
,
α
b
+
u
c
]
T and A
=
[
α
→
1
,
…
,
α
→
C
].Secondly, we calculate the term∑
c
=
1
C
f
→
c
T
L
X
f
→
c. Since f
→
c
=
K
D
α
→
c then(33)∑c=1Cf→cTLXf→c=traceATKDTLXKDA.Thirdly, we calculate the term∑
i
=
1
b
y
→
i
-
g
→
i
2. Let Y
=
[
y
→
1
,
…
,
y
→
b
], G
=
[
g
→
1
,
…
,
g
→
b
], and F
=
[
f
→
1
,
…
,
f
→
C
]
=
K
D
A; then(34)∑i=1by→i-g→i2=Y-G2=traceYTY-2YSKDA+ATKDTSTSKDA.Again, the matrix S is a selection matrix such that G
=
F
T
S
T.At last, substituting (32), (33), and (34) into (30) will give the following result: (35)
A
∗
=
arg
min
A
⁡
t
r
a
c
e
Y
Y
T
-
2
Y
S
K
D
A
+
A
T
K
D
T
S
T
K
D
+
κ
M
D
+
λ
K
D
T
L
K
D
A
=
K
D
T
S
T
S
+
λ
L
+
κ
I
K
D
+
ρ
I
-
1
K
D
T
S
T
Y
T
.


## 4.3.1. Analytic Solutions to Two-Class Learning Problems

In the proposed algorithm, the Hilbert spaceH
D is taken as the solution space of learning problems. Then for all f
∈
H
D, f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
), we have(27)f→D=fx1⋯fxb+uT=KDα→,f
D
2
=
α
→
T
M
α
→, f
M
2
=
α
→
T
K
D
T
L
X
K
D
α
→. Based on the above results, the problem shown in (19) can be simplified as follows: (28)
α
→
∗
=
arg
min
α
→
∈
R
b
+
u
⁡
∑
i
=
1
b
V
y
i
,
∑
i
=
1
b
+
u
α
i
k
x
i
,
x
j
∣
θ
j
+
α
→
T
κ
M
D
+
λ
K
D
T
L
X
K
D
α
→
.Furthermore, if the cost function V
(
y
,
f
(
x
)
) is set to be the square error function, that is, V
(
y
,
f
(
x
)
)
=
(
y
-
f
(
x
)
)
2, we have (29)α→∗=argminα→∈Rb+u⁡y→Ty→-2y→TSKDα→+α→TKDTSTSKD+κMD+λKDTLXKDα→=argminα→∈Rb+u⁡y→Ty→-2b→DTα→+α→TADα→=AD-1b→D,where S is the selection matrix, b
→
D
=
K
D
T
S
T
y
→, and A
D
=
K
D
T
S
T
S
K
D
+
κ
M
D
+
λ
K
D
T
L
X
K
D. Note that the matrix A
D is a symmetric and positive definite matrix.


## 4.3.2. Analytic Solutions to Multiclass Learning Problems

In principle, the deduction shown above is also suitable for the multiclass learning problems. In fact, for the data samplex
i, its label y
i can take different values to indicate the different classes to which the data sample x
i belongs. However, in practice, the different values of y
i may be too close to facilitate the optimization calculation. Therefore, for the multiclass problems, we adopt another way to indicate the data labels.For the data samplex
i, let its label y
→
i be a C-dimensional vector, where C is the number of classes. If the data sample x
i belongs to the cth class, then the cth component of y
→
i is set to be 1 while the other components of y
→
i are set to zero, where c
=
1
,
…
,
C. Furthermore, a label function f
c
(
x
) is set to describe the probability that the data x belongs to the cth class. Based on these notations, the multiclass problem can be expressed as follows:(30)f∗=argminf⁡∑i=1by→i-g→i2+κ∑c=1Cf→cHD2+λ∑c=1Cf→cTLXf→c,where (31)f=f1,…,fC,g→i=f1xi⋮fCxi,f→c=fcx1⋮fcxl,i=1,…,l.We first calculate the term∑
c
=
1
C
f
→
c
H
D
2. Since f
c
(
x
)
∈
S
D
(
Ω
), then f
c
(
x
)
=
∑
i
=
1
b
+
u
α
i
c
k
(
x
,
x
i
∣
θ
i
) and(32)∑c=1Cf→cHD2=∑c=1Cα→cTMDα→c=TrATMDA,where α
→
c
=
[
α
1
c
,
…
,
α
b
+
u
c
]
T and A
=
[
α
→
1
,
…
,
α
→
C
].Secondly, we calculate the term∑
c
=
1
C
f
→
c
T
L
X
f
→
c. Since f
→
c
=
K
D
α
→
c then(33)∑c=1Cf→cTLXf→c=traceATKDTLXKDA.Thirdly, we calculate the term∑
i
=
1
b
y
→
i
-
g
→
i
2. Let Y
=
[
y
→
1
,
…
,
y
→
b
], G
=
[
g
→
1
,
…
,
g
→
b
], and F
=
[
f
→
1
,
…
,
f
→
C
]
=
K
D
A; then(34)∑i=1by→i-g→i2=Y-G2=traceYTY-2YSKDA+ATKDTSTSKDA.Again, the matrix S is a selection matrix such that G
=
F
T
S
T.At last, substituting (32), (33), and (34) into (30) will give the following result: (35)
A
∗
=
arg
min
A
⁡
t
r
a
c
e
Y
Y
T
-
2
Y
S
K
D
A
+
A
T
K
D
T
S
T
K
D
+
κ
M
D
+
λ
K
D
T
L
K
D
A
=
K
D
T
S
T
S
+
λ
L
+
κ
I
K
D
+
ρ
I
-
1
K
D
T
S
T
Y
T
.


## 4.4. The Framework of Multikernel-Like Learning Algorithms

In the algorithm proposed in this paper, the label functionf
(
x
) is set to be f
(
x
)
=
∑
i
=
1
b
+
u
α
i
k
(
x
,
x
i
∣
θ
i
), where the parameter θ
i is adjusted according to the data probability distribution p
(
x
) on the data sample x
i. In general, the data probability distribution is not uniform and therefore the parameter θ
i will be different sample by sample. As a result, the functions k
(
x
,
v
∣
θ
1
)
,
…
,
k
(
x
,
v
∣
θ
b
+
u
) are different kernel functions and will produce different RKHS. In this sense, the algorithm proposed in this paper can be regarded as a kind of multikernel learning algorithms, but quite different from the commonly used multikernel learning algorithm.In the commonly used multikernel learning algorithms, the multikernel function is a linear combination of multiple basic kernel functions:k
M
K
(
x
,
v
)
=
∑
j
=
1
M
β
j
k
j
(
x
,
v
), where the functions k
1
,
…
,
k
M are called basic kernel functions, while the function k
M
K
(
x
,
v
) is called the multikernel function. Since the basic kernel functions are symmetric and positive definite, it can be easily proven that the multikernel function is also symmetric and positive definite. Therefore the label function f
M
K
(
x
) based on the multikernel function can be expressed as (36)fMKx=∑i=1b+uαikMKx,xi=∑i=1b+uαi∑j=1Mβjkjx,xi=∑i=1b+u∑j=1Mαiβjkjx,xi,where the coefficients α
1
,
…
,
α
b
+
u and β
1
,
…
,
β
M are determined through machine learning.If we follow the ideas of the commonly used multikernel learning algorithms and regard the functionsk
(
x
,
v
∣
θ
1
)
,
…
,
k
(
x
,
v
∣
θ
b
+
u
) as the basic kernel functions, then the multikernel function becomes k
M
K
(
x
,
v
)
=
∑
j
=
1
M
β
j
k
(
x
,
v
∣
θ
j
). Thus, according to (36), the label function f
M
K
(
x
) based on the multikernel function becomes (37)fMKx=∑i=1b+uαikMKx,xi=∑i=1b+uαi∑j=1Mβjkx,xi∣θj≠∑i=1b+uαikx,xi∣θi=fx.It can be seen from (37) that, no matter how to adjust the coefficients β
1
,
…
,
β
M, it is impossible to make f
M
K
(
x
)
≠
f
(
x
). From the perspective of solution spaces, in the solution space of f
M
K
(
x
), there are b
+
u functions k
(
x
,
x
i
∣
θ
1
)
,
…
,
k
(
x
,
x
i
∣
θ
b
+
u
) around the data sample x
i, while in the solution space of f
(
x
), there is only one function k
(
x
,
x
i
∣
θ
i
) around the data sample x
i. Therefore the algorithm proposed in this paper is quite different from the commonly used multikernel learning algorithm.Nevertheless, the algorithm proposed in this paper still belongs to the realm of multikernel learning. As stated above, the functionsk
(
x
,
x
i
∣
θ
1
)
,
…
,
k
(
x
,
x
i
∣
θ
b
+
u
) are different kernel functions and can produce different RKHS: H
1
,
…
,
H
b
+
u. Now let V
i
=
{
α
k
(
x
,
x
i
∣
θ
i
)
∣
α
∈
R
}, as stated in Section 3.1; V
i is then a 1-dimensional subspace of H
i. Furthermore, the direct sum of these subspaces turns out to be(38)V=V1⊕⋯⊕Vb+u=∑i=1b+uαix,xi∣θi∣αi∈R.Obviously the direct sum of these subspaces is the solution space H
D.Due to the fact that our algorithm is different from the commonly used multikernel learning algorithm, but still involved in multiple kernel functions, our algorithm is called multikernel-like algorithm.


## 5. An MKDPD-Based Algorithm for Labeling New Coming Data

### 5.1. Problems

How to label new coming data{
x
1
n
e
w
,
…
,
x
n
n
e
w
} has been a hot topic in machine learning, where n
≥
1 represents the number of new coming data. Generally speaking, there are two extreme methods for labeling new coming data: relearning methods and unlearning methods.The relearning methods regard the new coming data as unlabeled data samples and mixe them with the original data samples to form new data samples:{
x
1
,
…
,
x
b
+
u
,
x
b
+
u
+
1
,
…
,
x
b
+
u
+
n
}, where x
b
+
u
+
j
=
x
j
n
e
w, j
=
1
,
…
,
n. Based on these new data samples, the methods relearn the new coefficients {
α
1
n
e
w
,
…
,
α
b
+
u
+
n
n
e
w
} of the label function f. The label of the new coming data x
j
n
e
w is then given by f
M
R
r
e
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
+
n
α
i
n
e
w
k
(
x
j
n
e
w
,
x
i
).The unlearning methods make use of the original coefficients{
α
1
o
l
d
,
…
,
α
b
+
u
o
l
d
} of label function f to label new coming data: f
M
R
u
n
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
).Obviously, in terms of accuracy, the relearning methods perform best, whiles the unlearning methods perform worst. In terms of efficiency, the unlearning methods perform best, while the relearning methods perform worst. For years the researchers have been hovering between these two extreme methods and try to find the trade-offs between accuracy and efficiency.


### 5.2. A MKDPD-Based Algorithm for Labeling New Coming Data

As stated in Section4, there are two times of learning in the MKDPD algorithm. In the first time of learning, the MKDPD algorithm has to adjust the parameters of kernel functions according to data probability distribution. In the second time of learning, the MKDPD algorithm has to determine the coefficients of label functions. Therefore, in the framework of the MKDPD algorithm, there are at least three ways to label new coming data:(1)
The MKDPD-based relearning method:f
M
K
D
P
D
r
e
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
+
n
α
i
n
e
w
k
(
x
j
n
e
w
,
x
i
∣
θ
i
n
e
w
), j
=
1
,
…
,
n. Obviously, the MKDPD-based relearning method can achieve the best accuracy but perform worst in efficiency because the MKDPD-based relearning method has to calculate both the parameters θ
n
e
w and coefficients α
n
e
w.
(2)
The MKDPD-based unlearning method:f
M
K
D
P
D
u
n
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
∣
θ
i
o
l
d
). Obviously, the MKDPD-based unlearning method can achieve the best efficiency but perform worst in accuracy because the unlearning method does not calculate the parameters θ
n
e
w and coefficients α
n
e
w either.
(3)
The MKDPD-based semilearning method:f
M
K
D
P
D
s
e
m
i
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
∣
θ
i
n
e
w
). The MKDPD-based semilearning method regards the new coming data as unlabeled data samples and mixes them with the original data samples to retrain the new parameters θ
n
e
w of kernel functions. However, the coefficients α
o
l
d remained unchanged and combined with the retrained kernel functions to label the new coming data. The MKDPD-based semilearning method takes full advantage of two times of learning in the MKDPD algorithm and achieves a better trade-off between computational accuracy and efficiency.


### 5.3. Error and Efficiency Analysis

#### 5.3.1. Experimental Data and Experimental Settings

We test our algorithm in the framework of manifold regularization and therefore the experimental data are downloaded from the website of manifold regularization (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). There are a total of 400 sets of data collected from two half-moons, 200 sets of data from one half-moon, and another 200 sets of data from another half-moon.We randomly take 1 set of datum as labeled sample and 99 sets of data as unlabeled samples from each half-moon. The remaining 200 sets of data are taken as new coming data for labeling.In order to alleviate the effect of random sampling on the objectivity of the experimental results, the random sampling has been done forN times and each random sampling will produce an experimental result. The average of N experimental results is taken as the end result. N is set to be 30, 50, 70, and 90, respectively (Table 1).Table 1
Average error rates (%) of four algorithms on testing samples with different number of tests.
Algorithm
Train times
N
=
30
N
=
50
N
=
70
N
=
90
f
M
R
u
n
0.8500
0.8800
0.7286
1.0167
f
M
K
D
P
D
u
n
0.2333
0.2700
0.2786
0.2722
f
M
K
D
P
D
s
e
m
i
0.1667
0.2200
0.19297
0.2000
f
M
K
D
P
D
r
e
0
0
0
0.0333


#### 5.3.2. Error Analysis

Table1 lists the error rates of various algorithms for labeling new coming data. Not surprisingly, the order of error rates is f
M
K
D
P
D
r
e
≤
f
M
K
D
P
D
s
e
m
i
≤
f
M
K
D
P
D
u
n. This order coincides with the amount of information exploited by these algorithms from the new coming data.In addition, the error rate off
M
K
D
P
D
u
n is smaller than that of f
M
R
u
n, where f
M
K
D
P
D
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
∣
θ
i
o
l
d
) and f
M
R
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
). It can be seen from the formulae of f
M
K
D
P
D
u
n and f
M
R
u
n that the basic functions k
(
x
,
x
i
∣
θ
i
o
l
d
) of f
M
K
D
P
D
u
n exploit not only the locations of samples, but also the probabilities of data on the samples, while the basic functions k
(
x
,
x
i
) of f
M
R
u
n exploit only the locations of samples.Figure1(a) shows the error rates of various algorithms change along with the number of new coming data. Again, the error rate of f
M
K
D
P
D
s
e
m
i is between those of f
M
K
D
P
D
u
n and f
M
K
D
P
D
r
e.Figure 1
(a) shows the error rates of the four algorithms (f
M
R
u
n, f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
K
D
P
D
r
e) on the testing set, and the number of new coming samples is 50, 100, 150, and 200, respectively. (b) reports the computation time of the four algorithms with the increasing of the new coming sample (from 50 to 200).
(a)
(b)


#### 5.3.3. Efficiency Analysis

Figure1(b) shows the runtime of various algorithms in labeling the new coming data. It can be seen from Figure 1(b) that the runtime of f
M
K
D
P
D
r
e increases exponentially along with the number of new coming data, while the runtime of f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
R
u
n almost remains unchanged.Since bothf
M
K
D
P
D
u
n and f
M
R
u
n make use of the original parameters θ
o
l
d and α
o
l
d to label the new coming data, the runtime of f
M
K
D
P
D
u
n and f
M
R
u
n will not change no matter how many new coming data are coming. However, in the proposed algorithm f
M
K
D
P
D
s
e
m
i, although the parameters θ are retrained from θ
o
l
d to θ
n
e
w according to the new coming data, the runtime of f
M
K
D
P
D
s
e
m
i almost remains unchanged along with the number of new coming data. The means that f
M
K
D
P
D
s
e
m
i achieves a certain amount of accuracy without increasing its runtime.


## 5.1. Problems

How to label new coming data{
x
1
n
e
w
,
…
,
x
n
n
e
w
} has been a hot topic in machine learning, where n
≥
1 represents the number of new coming data. Generally speaking, there are two extreme methods for labeling new coming data: relearning methods and unlearning methods.The relearning methods regard the new coming data as unlabeled data samples and mixe them with the original data samples to form new data samples:{
x
1
,
…
,
x
b
+
u
,
x
b
+
u
+
1
,
…
,
x
b
+
u
+
n
}, where x
b
+
u
+
j
=
x
j
n
e
w, j
=
1
,
…
,
n. Based on these new data samples, the methods relearn the new coefficients {
α
1
n
e
w
,
…
,
α
b
+
u
+
n
n
e
w
} of the label function f. The label of the new coming data x
j
n
e
w is then given by f
M
R
r
e
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
+
n
α
i
n
e
w
k
(
x
j
n
e
w
,
x
i
).The unlearning methods make use of the original coefficients{
α
1
o
l
d
,
…
,
α
b
+
u
o
l
d
} of label function f to label new coming data: f
M
R
u
n
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
).Obviously, in terms of accuracy, the relearning methods perform best, whiles the unlearning methods perform worst. In terms of efficiency, the unlearning methods perform best, while the relearning methods perform worst. For years the researchers have been hovering between these two extreme methods and try to find the trade-offs between accuracy and efficiency.


## 5.2. A MKDPD-Based Algorithm for Labeling New Coming Data

As stated in Section4, there are two times of learning in the MKDPD algorithm. In the first time of learning, the MKDPD algorithm has to adjust the parameters of kernel functions according to data probability distribution. In the second time of learning, the MKDPD algorithm has to determine the coefficients of label functions. Therefore, in the framework of the MKDPD algorithm, there are at least three ways to label new coming data:(1)
The MKDPD-based relearning method:f
M
K
D
P
D
r
e
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
+
n
α
i
n
e
w
k
(
x
j
n
e
w
,
x
i
∣
θ
i
n
e
w
), j
=
1
,
…
,
n. Obviously, the MKDPD-based relearning method can achieve the best accuracy but perform worst in efficiency because the MKDPD-based relearning method has to calculate both the parameters θ
n
e
w and coefficients α
n
e
w.
(2)
The MKDPD-based unlearning method:f
M
K
D
P
D
u
n
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
∣
θ
i
o
l
d
). Obviously, the MKDPD-based unlearning method can achieve the best efficiency but perform worst in accuracy because the unlearning method does not calculate the parameters θ
n
e
w and coefficients α
n
e
w either.
(3)
The MKDPD-based semilearning method:f
M
K
D
P
D
s
e
m
i
(
x
j
n
e
w
)
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
j
n
e
w
,
x
i
∣
θ
i
n
e
w
). The MKDPD-based semilearning method regards the new coming data as unlabeled data samples and mixes them with the original data samples to retrain the new parameters θ
n
e
w of kernel functions. However, the coefficients α
o
l
d remained unchanged and combined with the retrained kernel functions to label the new coming data. The MKDPD-based semilearning method takes full advantage of two times of learning in the MKDPD algorithm and achieves a better trade-off between computational accuracy and efficiency.


## 5.3. Error and Efficiency Analysis

### 5.3.1. Experimental Data and Experimental Settings

We test our algorithm in the framework of manifold regularization and therefore the experimental data are downloaded from the website of manifold regularization (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). There are a total of 400 sets of data collected from two half-moons, 200 sets of data from one half-moon, and another 200 sets of data from another half-moon.We randomly take 1 set of datum as labeled sample and 99 sets of data as unlabeled samples from each half-moon. The remaining 200 sets of data are taken as new coming data for labeling.In order to alleviate the effect of random sampling on the objectivity of the experimental results, the random sampling has been done forN times and each random sampling will produce an experimental result. The average of N experimental results is taken as the end result. N is set to be 30, 50, 70, and 90, respectively (Table 1).Table 1
Average error rates (%) of four algorithms on testing samples with different number of tests.
Algorithm
Train times
N
=
30
N
=
50
N
=
70
N
=
90
f
M
R
u
n
0.8500
0.8800
0.7286
1.0167
f
M
K
D
P
D
u
n
0.2333
0.2700
0.2786
0.2722
f
M
K
D
P
D
s
e
m
i
0.1667
0.2200
0.19297
0.2000
f
M
K
D
P
D
r
e
0
0
0
0.0333


### 5.3.2. Error Analysis

Table1 lists the error rates of various algorithms for labeling new coming data. Not surprisingly, the order of error rates is f
M
K
D
P
D
r
e
≤
f
M
K
D
P
D
s
e
m
i
≤
f
M
K
D
P
D
u
n. This order coincides with the amount of information exploited by these algorithms from the new coming data.In addition, the error rate off
M
K
D
P
D
u
n is smaller than that of f
M
R
u
n, where f
M
K
D
P
D
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
∣
θ
i
o
l
d
) and f
M
R
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
). It can be seen from the formulae of f
M
K
D
P
D
u
n and f
M
R
u
n that the basic functions k
(
x
,
x
i
∣
θ
i
o
l
d
) of f
M
K
D
P
D
u
n exploit not only the locations of samples, but also the probabilities of data on the samples, while the basic functions k
(
x
,
x
i
) of f
M
R
u
n exploit only the locations of samples.Figure1(a) shows the error rates of various algorithms change along with the number of new coming data. Again, the error rate of f
M
K
D
P
D
s
e
m
i is between those of f
M
K
D
P
D
u
n and f
M
K
D
P
D
r
e.Figure 1
(a) shows the error rates of the four algorithms (f
M
R
u
n, f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
K
D
P
D
r
e) on the testing set, and the number of new coming samples is 50, 100, 150, and 200, respectively. (b) reports the computation time of the four algorithms with the increasing of the new coming sample (from 50 to 200).
(a)
(b)


### 5.3.3. Efficiency Analysis

Figure1(b) shows the runtime of various algorithms in labeling the new coming data. It can be seen from Figure 1(b) that the runtime of f
M
K
D
P
D
r
e increases exponentially along with the number of new coming data, while the runtime of f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
R
u
n almost remains unchanged.Since bothf
M
K
D
P
D
u
n and f
M
R
u
n make use of the original parameters θ
o
l
d and α
o
l
d to label the new coming data, the runtime of f
M
K
D
P
D
u
n and f
M
R
u
n will not change no matter how many new coming data are coming. However, in the proposed algorithm f
M
K
D
P
D
s
e
m
i, although the parameters θ are retrained from θ
o
l
d to θ
n
e
w according to the new coming data, the runtime of f
M
K
D
P
D
s
e
m
i almost remains unchanged along with the number of new coming data. The means that f
M
K
D
P
D
s
e
m
i achieves a certain amount of accuracy without increasing its runtime.


## 5.3.1. Experimental Data and Experimental Settings

We test our algorithm in the framework of manifold regularization and therefore the experimental data are downloaded from the website of manifold regularization (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). There are a total of 400 sets of data collected from two half-moons, 200 sets of data from one half-moon, and another 200 sets of data from another half-moon.We randomly take 1 set of datum as labeled sample and 99 sets of data as unlabeled samples from each half-moon. The remaining 200 sets of data are taken as new coming data for labeling.In order to alleviate the effect of random sampling on the objectivity of the experimental results, the random sampling has been done forN times and each random sampling will produce an experimental result. The average of N experimental results is taken as the end result. N is set to be 30, 50, 70, and 90, respectively (Table 1).Table 1
Average error rates (%) of four algorithms on testing samples with different number of tests.
Algorithm
Train times
N
=
30
N
=
50
N
=
70
N
=
90
f
M
R
u
n
0.8500
0.8800
0.7286
1.0167
f
M
K
D
P
D
u
n
0.2333
0.2700
0.2786
0.2722
f
M
K
D
P
D
s
e
m
i
0.1667
0.2200
0.19297
0.2000
f
M
K
D
P
D
r
e
0
0
0
0.0333


## 5.3.2. Error Analysis

Table1 lists the error rates of various algorithms for labeling new coming data. Not surprisingly, the order of error rates is f
M
K
D
P
D
r
e
≤
f
M
K
D
P
D
s
e
m
i
≤
f
M
K
D
P
D
u
n. This order coincides with the amount of information exploited by these algorithms from the new coming data.In addition, the error rate off
M
K
D
P
D
u
n is smaller than that of f
M
R
u
n, where f
M
K
D
P
D
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
∣
θ
i
o
l
d
) and f
M
R
u
n
=
∑
i
=
1
b
+
u
α
i
o
l
d
k
(
x
,
x
i
). It can be seen from the formulae of f
M
K
D
P
D
u
n and f
M
R
u
n that the basic functions k
(
x
,
x
i
∣
θ
i
o
l
d
) of f
M
K
D
P
D
u
n exploit not only the locations of samples, but also the probabilities of data on the samples, while the basic functions k
(
x
,
x
i
) of f
M
R
u
n exploit only the locations of samples.Figure1(a) shows the error rates of various algorithms change along with the number of new coming data. Again, the error rate of f
M
K
D
P
D
s
e
m
i is between those of f
M
K
D
P
D
u
n and f
M
K
D
P
D
r
e.Figure 1
(a) shows the error rates of the four algorithms (f
M
R
u
n, f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
K
D
P
D
r
e) on the testing set, and the number of new coming samples is 50, 100, 150, and 200, respectively. (b) reports the computation time of the four algorithms with the increasing of the new coming sample (from 50 to 200).
(a)
(b)


## 5.3.3. Efficiency Analysis

Figure1(b) shows the runtime of various algorithms in labeling the new coming data. It can be seen from Figure 1(b) that the runtime of f
M
K
D
P
D
r
e increases exponentially along with the number of new coming data, while the runtime of f
M
K
D
P
D
u
n, f
M
K
D
P
D
s
e
m
i, and f
M
R
u
n almost remains unchanged.Since bothf
M
K
D
P
D
u
n and f
M
R
u
n make use of the original parameters θ
o
l
d and α
o
l
d to label the new coming data, the runtime of f
M
K
D
P
D
u
n and f
M
R
u
n will not change no matter how many new coming data are coming. However, in the proposed algorithm f
M
K
D
P
D
s
e
m
i, although the parameters θ are retrained from θ
o
l
d to θ
n
e
w according to the new coming data, the runtime of f
M
K
D
P
D
s
e
m
i almost remains unchanged along with the number of new coming data. The means that f
M
K
D
P
D
s
e
m
i achieves a certain amount of accuracy without increasing its runtime.


## 6. Experiments

### 6.1. Adjustment of Parameters of Kernel Functions

In the proposed MKDPD algorithm, the basic functions of label functionf
(
x
) are set to be k
(
x
,
x
i
∣
θ
i
), where θ
i
=
θ
(
p
(
x
i
)
), i
=
1
,
…
,
b
+
u. The schemes of how to adjust the parameters θ
i are open. People can adopt various schemes according to their specific applications. No matter how to adjust the parameters θ
i, the structures of analytic solutions shown in (19) will not change in the framework of the proposed MKDPD algorithm. In the experiments presented in this paper, the scheme of adjusting the parameters is based on the following considerations;(1)
The parametersθ
i should be adjusted so as to make sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). In this way, for all x
∈
Ω with p
(
x
)
≠
0, the label function f
(
x
) can give the label of x.
(2)
If the value ofp
(
x
i
) is large, the number of samples gathering in the neighborhood of x
i will be large too because they are more likely to be collected. In order to prevent data overfitting in the area, it is reasonable to adjust the parameter θ
i to reduce the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). Conversely, if the value of p
(
x
i
) is small, the number of samples will be small too because they are more unlikely to be collected. In order to prevent data underfitting in the area, it is reasonable to adjust the parameter to expand the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). This means that the probability p
(
x
i
) is inversely proportional to the scope of the support.
(3)
In the following experiments, we adopt Gaussian kernel functionsk
(
x
,
x
i
∣
θ
i
)
=
e
x
p
-
∥
x
-
x
i
∥
2
/
2
θ
i
2. The Gaussian kernel function can be regarded as a compactly support function, the sample x
i is its center, and 3
θ
i is often regarded as its effective radius. Therefore, the parameter θ
i is proportional to the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
), or inversely proportional to the probability p
(
x
i
); that is, θ
i
=
η
i
/
p
(
x
i
), where η
i is an adjustable parameter. In our experiments, the probability p
(
x
i
) of sample x
i is set to p
(
x
i
)
=
p
i
(
x
i
)
/
∑
i
p
i
(
x
i
), where p
i
(
x
i
)
=
ε
(
x
i
)
/
b
+
u and ε
(
x
i
) is the number of neighbors of x
i.


### 6.2. Experiments on Synthetic Dataset (Two Moons Dataset)

The synthetic dataset is the Two Moons Dataset, which has already been used in the experiments in Section5.The Two Moons dataset contains 400 sets of data nonevenly collected from two half-moons, where 200 sets of data are collected from one half-moon and the other 200 sets of data are collected from the other half-moon. We randomly take 100 sets of data from each half-moon as samples, where 1 sample is labeled and the other samples are unlabelled. The remaining 200 sets of data in the Two Moons dataset are taken as the test data (i.e., new coming data in Section5).Figure2 shows the experimental results of the proposed MKDPD algorithm and MR algorithm. In Figures 2(a) and 2(b), although the labeled sample in the upper half-moon is badly located, the proposed MKDPD algorithm can still separate the upper half-moon from the lower half-moon, while MR algorithm fails at the one corner of the upper half-moon. In Figures 2(c) and 2(d), the labeled sample in the upper half-moon is located much near the center of the upper half-moon and accordingly the performance of MR algorithm becomes much better. However, the proposed MKDPD algorithm still outperforms MR algorithm in this circumstance.Figure 2
Two Moons Dataset: separating planes of MKDPD (see (a) and (c)) and MR (see (b) and (d)); the red and blue color points are labeled samples; the rest of the points are unlabeled samples.
(a)
(b)
(c)
(d)The labeled samples are randomly taken forN times and each time will produce an experimental result. The average of experimental results is listed in Table 2. It can be seen from Table 2 that the proposed MKDPD algorithm outperforms MR algorithm under all circumstances.Table 2
Average error rates (%) of MKDPD and MR on unlabeled samples of two moons set with different number of tests.
Algorithm
Train times
N
=
30
N
=
50
N
=
70
N
=
90
MKDPD
0
0
0
0.0112
MR
0.8586
0.9293
0.7720
1.0325There are two regularization terms in the proposed MKDPD algorithm and MR algorithm: manifold regularizationλ
f
M
2 and function regularization κ
f
H
2, where H
=
H
D in MKDPD or H
=
H
X in MR. We keep λ unchanged, while letting κ change from 0 to 0.2 and comparing their performances (see Figure 3). As shown in Figure 3, the error rates of the proposed MKDPD algorithm and MR algorithm decrease where the parameter κ decreases, but the error rate of the proposed MKDPD decreases much faster than that of MR algorithm.Figure 3
Error rates (%) of MKDPD and MR on unlabeled and testing samples of two moons set with the regular parameter κ varied from 0 to 0.2.
(a)
(b)


### 6.3. Recognition of Handwritten Digits

#### 6.3.1. USPS and MNIST Datasets

USPS (United States Postal) Dataset (http://www.cs.nyu.edu/~roweis/data.html) is a very popular dataset of handwritten digits, which contains 10 handwritten digits from “0” to “9”; each digit has 1100 images and each image is sized as 16
×
16 and can be converted into a 256-dimensional vector. We take the first 400 images of each digit as the samples and the remaining images as the test data (new coming data).The MNIST (http://yann.lecun.com/exdb/mnist/) is another popular handwritten digits dataset, which contains a training set of 60000 images and a test set of 10000 images. Each image in MNIST is of size 28
×
28 and can be converted into a 784-dimensional vector. We select 400 sets of data from the training set as the samples for each digit and all data in the test set as the test data (new coming data).


#### 6.3.2. The Two-Class Experiments

We randomly select two different digits from the ten digits to construct a binary classification problem, and then there is a total of 45 classification problems. For each binary classification problem, a sample is taken as the labeled sample for each digit and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the labeled samples are randomly selected for ten times and each time will produce an experimental result. The average of ten experimental results is presented as the final experiment result.The experimental results of the proposed MKDPD algorithm and MR algorithm are presented in Figure4. In Figures 4(a), 4(b), 4(c), and 4(d), the x-axis represents the 45 binary classification problems, and the y-axis represents the error rates. The error rates on the unlabeled samples are shown in Figures 4(a) and 4(c), and the error rates on the test data are shown in Figures 4(b) and 4(d). As can be seen, the error rates of the proposed MKDPD algorithm are lower than those of the MR algorithm. Furthermore, the averages of the results of 45 binary classifications are listed in Table 3. It can be seen from Table 3 that the proposed MKDPD algorithm outperforms the MR algorithm.Table 3
Average error rates (%) of the two-class experiments on USPS, MNIST, and ISOLET datasets.
Dataset
Algorithm
Unlabeled samples
Testing samples
USPS
MKDPD
2.5494
2.4723
MR
3.1541
3.5774
MNIST
MKDPD
5.4213
6.0654
MR
6.8557
8.1182
ISOLET
MKDPD
15.4067
17.7037
MR
17.6039
24.9947Figure 4
Two-class problem experiments: in (a, b, c, and d), (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the USPS set, respectively, and (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the MNIST set, respectively, where the y-axis is the 45 binary classification problems; in (e, f, g, and h), we report the scatter plots of error rate on unlabeled samples versus test samples. (e) and (g) are the scatter plots of error rates of MKDPD on USPS and MNIST, respectively, and (f) and (h) are the scatter plots of error rates of MR on USPS and MNIST, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)In Figures4(e), 4(f), 4(g), and 4(h), the x-axis represents the error rates of labeling the unlabeled samples and the y-axis represents the error rates of labeling the test data. For a good learning algorithm, its error rates on the unlabeled samples and on the test data should be close to each other; that is, the scatter points in Figures 4(e), 4(f), 4(g), and 4(h) should be close to the diagonal line. Again, in this respect, the proposed MKDPD algorithm performs the MR algorithm better.


#### 6.3.3. The Multiclass Experiments

In the multiclass experiments, there are 10 classes and each class corresponds to a digit. The labeled samples of each digit are randomly selected from its samples for 10 times and each time will produce an experimental result. The average of 10 experimental results is taken as the final result and listed in the first and second column of Table5. The number of labeled samples is set to be 1, 3, and 5, respectively. It can be seen from Table 5 that the proposed MKDPD algorithm outperforms the MR algorithm.


### 6.4. Recognition of Spoken Letters

#### 6.4.1. ISOLET Dataset

ISOLET is a dataset of spoken letters and can be downloaded from UCI machine learning repository. ISOLET contains the utterances of 150 speakers who spoke 26 English letters twice, and then each speaker has 52 utterances. In the experiment, two subsets of ISOLET, whose names are ISOLET1 and ISOLET5 respectively, are directly download from (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). Each subset contains the utterances of 30 speakers. We take the data in ISOLET1 as the samples and the data in ISOLET5 as the test data (new coming data).


#### 6.4.2. The Two-Class Experiments

In the two-class experiments, the utterances of the first 13 English letters are classified as one class and the utterances of the last 13 English letters are classified as another class. We take the 52 utterances of one speaker from ISOLET1 as the labels samples and the utterances of the other speakers in ISOLET1 as the unlabeled samples. Since there are 30 speakers in ISOLET1, we can construct 30 two-class experiments this way and the 30 experimental results are presented in Figure5. As can be seen from Figure 5, the proposed MKDPD algorithm outperforms the MR algorithm. The averages of 30 experimental results experiments are listed in Table 4, which also shows that the proposed MKDPD performs better than the MR algorithm.Table 4
Average error rates (%) of the two-class experiments on Yale-B and CMU-PIE datasets with different number of labeled samples.
Dataset
Algorithm
3 labeled samples
5 labeled samples
7 labeled samples
Unlabeled
Test
Unlabeled
Test
Unlabeled
Test
Yale-B
MKDPD
35.2279
31.4955
30.4664
25.1786
27.3871
20.7087
MR
36.7658
32.7455
31.7899
26.8136
28.8743
22.7087
CMU-PIE
MKDPD
23.9889
20.4167
13.6962
10.1042
8.5904
5.5754
MR
26.0776
22.9712
15.9315
12.3611
10.0515
6.8452Table 5
Error rates (%) of the multiclass problem experiments on five datasets: USPS, MNIST, ISOLET, Yale-B, and CMU-PIE, where the value in bracket is the number of labeled sample in each class.
Dataset
Algorithm
Unlabeled (labeled samples)
Test (labeled samples)
USPS
MKDPD
19.8241 (
1
)
12.7056 (
3
)
10.3949 (
5
)
18.1100 (
1
)
10.9359 (
3
)
8.5658 (
5
)
MR
23.5377 (1)
14.5279 (3)
11.2359 (5)
21.2428 (1)
13.3242 (3)
10.2856 (5)
MNIST
MKDPD
31.8342 (
1
)
20.5939 (
3
)
16.0872 (
5
)
38.5650 (
1
)
27.2950 (
3
)
23.0300 (
5
)
MR
35.1206 (1)
21.2741 (3)
17.9026 (5)
44.6050 (1)
31.3800 (3)
26.7300 (5)
ISOLET
MKDPD
18.5743 (
2
)
12.7060 (
4
)
10.3704 (
6
)
29.9469 (
2
)
24.4297 (
4
)
21.7241 (
6
)
MR
20.6300 (2)
15.1305 (4)
13.0057 (6)
30.1790 (2)
25.4111 (4)
22.4801 (6)
Yale-B
MKDPD
36.4440 (
3
)
26.6991 (
5
)
18.4750 (
7
)
35.3516 (
3
)
26.8203 (
5
)
17.2070 (
7
)
MR
45.5172 (3)
36.9676 (5)
31.3500 (7)
41.9531 (3)
36.1406 (5)
25.5078 (7)
CMU-PIE
MKDPD
23.9773 (
3
)
11.5591 (
5
)
5.6034 (
7
)
20.1968 (
3
)
9.3056 (
5
)
4.1551 (
7
)
MR
25.2904 (3)
12.2715 (5)
6.3793 (7)
21.0532 (3)
11.0069 (5)
5.7292 (7)Figure 5
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of ISOLET set, where the y-axis is the 30 binary classification problems; (b) is the error rates of MKDPD and MR on test samples of ISOLET set.
(a)
(b)


#### 6.4.3. The Multiclass Experiments

In the multiclass experiments, the utterances of each English letter are classified as a class, and then there are 26 classes. We randomly selectN speakers from ISOLET1 and take their utterances as the labeled samples. The utterances of the other speakers in ISOLET1 are then taken as the unlabeled samples. In order to alleviate the effect of randomness, the selection of N speakers is performed for 10 times and each time will produce an experimental result. The averages of 10 experimental results are taken as the final results and listed in the third column of Table 5. It can be observed from Table 5 that the proposed MKDPD algorithm achieves about 1%~3% improvements over the MR algorithm.


### 6.5. Face Recognition

#### 6.5.1. YALE-B and CMU-PIE Datasets

YALE-B (http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html) is a dataset of face images which consists of the face images of 10 persons; each person is photographed under 9 poses and 64 illuminations. In the experiment, we select the face images of 8 persons of 64 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. For each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data). CMU-PIE [38] is another dataset of face images which consists of more than 40000 images of 68 persons; each person is photographed under 4 expressions, 24 Illuminations, and 13 poses. In the experiment, we select the face images of 8 persons of 3 poses and 24 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. Again, for each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data).


#### 6.5.2. The Two-Class Experiments

We select the face images of two persons to construct a binary classification problem and then there are a total of 28 binary classification problems. For each binary classification problem,N samples of each person are taken as the labeled samples and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the N samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final results (see Figures 6 and 7), where the number of labeled samples is set to be N
=
3,5, and 7, respectively. The average of 28 binary classification results is listed in Table 4. It can be seen that, compared with the MR algorithm, the proposed MKDPD algorithm achieves about 1%~5% improvements.Figure 6
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the Yale-B set; (b) is the error rates (%) of MKDPD and MR on test samples of the Yale-B set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled samples in each class.
(a)
(b)Figure 7
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the CMU-PIE set; (b) is the error rates (%) of MKDPD and MR on test samples of the CMU-PIE set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled sample in each class.
(a)
(b)


#### 6.5.3. The Multiclass Experiments

In the multiclassification experiments, we take the face images of a person as one class and then there are 8 classes.N samples of each person are taken as the labeled samples and the remaining samples as the unlabeled samples. Again, the N labeled samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final result and listed in the last four columns of Table 5, where the number of labeled samples is set to be N
=
3,5, and 7, respectively. As can be seen, the proposed MKDPD algorithm achieves about 1%~12% improvements to the MR algorithm.


## 6.1. Adjustment of Parameters of Kernel Functions

In the proposed MKDPD algorithm, the basic functions of label functionf
(
x
) are set to be k
(
x
,
x
i
∣
θ
i
), where θ
i
=
θ
(
p
(
x
i
)
), i
=
1
,
…
,
b
+
u. The schemes of how to adjust the parameters θ
i are open. People can adopt various schemes according to their specific applications. No matter how to adjust the parameters θ
i, the structures of analytic solutions shown in (19) will not change in the framework of the proposed MKDPD algorithm. In the experiments presented in this paper, the scheme of adjusting the parameters is based on the following considerations;(1)
The parametersθ
i should be adjusted so as to make sup
⁡
p
(
p
)
⊆
∪
i
=
1
b
+
u
sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). In this way, for all x
∈
Ω with p
(
x
)
≠
0, the label function f
(
x
) can give the label of x.
(2)
If the value ofp
(
x
i
) is large, the number of samples gathering in the neighborhood of x
i will be large too because they are more likely to be collected. In order to prevent data overfitting in the area, it is reasonable to adjust the parameter θ
i to reduce the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). Conversely, if the value of p
(
x
i
) is small, the number of samples will be small too because they are more unlikely to be collected. In order to prevent data underfitting in the area, it is reasonable to adjust the parameter to expand the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
). This means that the probability p
(
x
i
) is inversely proportional to the scope of the support.
(3)
In the following experiments, we adopt Gaussian kernel functionsk
(
x
,
x
i
∣
θ
i
)
=
e
x
p
-
∥
x
-
x
i
∥
2
/
2
θ
i
2. The Gaussian kernel function can be regarded as a compactly support function, the sample x
i is its center, and 3
θ
i is often regarded as its effective radius. Therefore, the parameter θ
i is proportional to the scope of the support sup
⁡
p
(
k
(
·
,
x
i
∣
θ
i
)
), or inversely proportional to the probability p
(
x
i
); that is, θ
i
=
η
i
/
p
(
x
i
), where η
i is an adjustable parameter. In our experiments, the probability p
(
x
i
) of sample x
i is set to p
(
x
i
)
=
p
i
(
x
i
)
/
∑
i
p
i
(
x
i
), where p
i
(
x
i
)
=
ε
(
x
i
)
/
b
+
u and ε
(
x
i
) is the number of neighbors of x
i.


## 6.2. Experiments on Synthetic Dataset (Two Moons Dataset)

The synthetic dataset is the Two Moons Dataset, which has already been used in the experiments in Section5.The Two Moons dataset contains 400 sets of data nonevenly collected from two half-moons, where 200 sets of data are collected from one half-moon and the other 200 sets of data are collected from the other half-moon. We randomly take 100 sets of data from each half-moon as samples, where 1 sample is labeled and the other samples are unlabelled. The remaining 200 sets of data in the Two Moons dataset are taken as the test data (i.e., new coming data in Section5).Figure2 shows the experimental results of the proposed MKDPD algorithm and MR algorithm. In Figures 2(a) and 2(b), although the labeled sample in the upper half-moon is badly located, the proposed MKDPD algorithm can still separate the upper half-moon from the lower half-moon, while MR algorithm fails at the one corner of the upper half-moon. In Figures 2(c) and 2(d), the labeled sample in the upper half-moon is located much near the center of the upper half-moon and accordingly the performance of MR algorithm becomes much better. However, the proposed MKDPD algorithm still outperforms MR algorithm in this circumstance.Figure 2
Two Moons Dataset: separating planes of MKDPD (see (a) and (c)) and MR (see (b) and (d)); the red and blue color points are labeled samples; the rest of the points are unlabeled samples.
(a)
(b)
(c)
(d)The labeled samples are randomly taken forN times and each time will produce an experimental result. The average of experimental results is listed in Table 2. It can be seen from Table 2 that the proposed MKDPD algorithm outperforms MR algorithm under all circumstances.Table 2
Average error rates (%) of MKDPD and MR on unlabeled samples of two moons set with different number of tests.
Algorithm
Train times
N
=
30
N
=
50
N
=
70
N
=
90
MKDPD
0
0
0
0.0112
MR
0.8586
0.9293
0.7720
1.0325There are two regularization terms in the proposed MKDPD algorithm and MR algorithm: manifold regularizationλ
f
M
2 and function regularization κ
f
H
2, where H
=
H
D in MKDPD or H
=
H
X in MR. We keep λ unchanged, while letting κ change from 0 to 0.2 and comparing their performances (see Figure 3). As shown in Figure 3, the error rates of the proposed MKDPD algorithm and MR algorithm decrease where the parameter κ decreases, but the error rate of the proposed MKDPD decreases much faster than that of MR algorithm.Figure 3
Error rates (%) of MKDPD and MR on unlabeled and testing samples of two moons set with the regular parameter κ varied from 0 to 0.2.
(a)
(b)


## 6.3. Recognition of Handwritten Digits

### 6.3.1. USPS and MNIST Datasets

USPS (United States Postal) Dataset (http://www.cs.nyu.edu/~roweis/data.html) is a very popular dataset of handwritten digits, which contains 10 handwritten digits from “0” to “9”; each digit has 1100 images and each image is sized as 16
×
16 and can be converted into a 256-dimensional vector. We take the first 400 images of each digit as the samples and the remaining images as the test data (new coming data).The MNIST (http://yann.lecun.com/exdb/mnist/) is another popular handwritten digits dataset, which contains a training set of 60000 images and a test set of 10000 images. Each image in MNIST is of size 28
×
28 and can be converted into a 784-dimensional vector. We select 400 sets of data from the training set as the samples for each digit and all data in the test set as the test data (new coming data).


### 6.3.2. The Two-Class Experiments

We randomly select two different digits from the ten digits to construct a binary classification problem, and then there is a total of 45 classification problems. For each binary classification problem, a sample is taken as the labeled sample for each digit and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the labeled samples are randomly selected for ten times and each time will produce an experimental result. The average of ten experimental results is presented as the final experiment result.The experimental results of the proposed MKDPD algorithm and MR algorithm are presented in Figure4. In Figures 4(a), 4(b), 4(c), and 4(d), the x-axis represents the 45 binary classification problems, and the y-axis represents the error rates. The error rates on the unlabeled samples are shown in Figures 4(a) and 4(c), and the error rates on the test data are shown in Figures 4(b) and 4(d). As can be seen, the error rates of the proposed MKDPD algorithm are lower than those of the MR algorithm. Furthermore, the averages of the results of 45 binary classifications are listed in Table 3. It can be seen from Table 3 that the proposed MKDPD algorithm outperforms the MR algorithm.Table 3
Average error rates (%) of the two-class experiments on USPS, MNIST, and ISOLET datasets.
Dataset
Algorithm
Unlabeled samples
Testing samples
USPS
MKDPD
2.5494
2.4723
MR
3.1541
3.5774
MNIST
MKDPD
5.4213
6.0654
MR
6.8557
8.1182
ISOLET
MKDPD
15.4067
17.7037
MR
17.6039
24.9947Figure 4
Two-class problem experiments: in (a, b, c, and d), (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the USPS set, respectively, and (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the MNIST set, respectively, where the y-axis is the 45 binary classification problems; in (e, f, g, and h), we report the scatter plots of error rate on unlabeled samples versus test samples. (e) and (g) are the scatter plots of error rates of MKDPD on USPS and MNIST, respectively, and (f) and (h) are the scatter plots of error rates of MR on USPS and MNIST, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)In Figures4(e), 4(f), 4(g), and 4(h), the x-axis represents the error rates of labeling the unlabeled samples and the y-axis represents the error rates of labeling the test data. For a good learning algorithm, its error rates on the unlabeled samples and on the test data should be close to each other; that is, the scatter points in Figures 4(e), 4(f), 4(g), and 4(h) should be close to the diagonal line. Again, in this respect, the proposed MKDPD algorithm performs the MR algorithm better.


### 6.3.3. The Multiclass Experiments

In the multiclass experiments, there are 10 classes and each class corresponds to a digit. The labeled samples of each digit are randomly selected from its samples for 10 times and each time will produce an experimental result. The average of 10 experimental results is taken as the final result and listed in the first and second column of Table5. The number of labeled samples is set to be 1, 3, and 5, respectively. It can be seen from Table 5 that the proposed MKDPD algorithm outperforms the MR algorithm.


## 6.3.1. USPS and MNIST Datasets

USPS (United States Postal) Dataset (http://www.cs.nyu.edu/~roweis/data.html) is a very popular dataset of handwritten digits, which contains 10 handwritten digits from “0” to “9”; each digit has 1100 images and each image is sized as 16
×
16 and can be converted into a 256-dimensional vector. We take the first 400 images of each digit as the samples and the remaining images as the test data (new coming data).The MNIST (http://yann.lecun.com/exdb/mnist/) is another popular handwritten digits dataset, which contains a training set of 60000 images and a test set of 10000 images. Each image in MNIST is of size 28
×
28 and can be converted into a 784-dimensional vector. We select 400 sets of data from the training set as the samples for each digit and all data in the test set as the test data (new coming data).


## 6.3.2. The Two-Class Experiments

We randomly select two different digits from the ten digits to construct a binary classification problem, and then there is a total of 45 classification problems. For each binary classification problem, a sample is taken as the labeled sample for each digit and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the labeled samples are randomly selected for ten times and each time will produce an experimental result. The average of ten experimental results is presented as the final experiment result.The experimental results of the proposed MKDPD algorithm and MR algorithm are presented in Figure4. In Figures 4(a), 4(b), 4(c), and 4(d), the x-axis represents the 45 binary classification problems, and the y-axis represents the error rates. The error rates on the unlabeled samples are shown in Figures 4(a) and 4(c), and the error rates on the test data are shown in Figures 4(b) and 4(d). As can be seen, the error rates of the proposed MKDPD algorithm are lower than those of the MR algorithm. Furthermore, the averages of the results of 45 binary classifications are listed in Table 3. It can be seen from Table 3 that the proposed MKDPD algorithm outperforms the MR algorithm.Table 3
Average error rates (%) of the two-class experiments on USPS, MNIST, and ISOLET datasets.
Dataset
Algorithm
Unlabeled samples
Testing samples
USPS
MKDPD
2.5494
2.4723
MR
3.1541
3.5774
MNIST
MKDPD
5.4213
6.0654
MR
6.8557
8.1182
ISOLET
MKDPD
15.4067
17.7037
MR
17.6039
24.9947Figure 4
Two-class problem experiments: in (a, b, c, and d), (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the USPS set, respectively, and (a) and (b) report the error rates (%) of MKDPD and MR on unlabeled and test samples of the MNIST set, respectively, where the y-axis is the 45 binary classification problems; in (e, f, g, and h), we report the scatter plots of error rate on unlabeled samples versus test samples. (e) and (g) are the scatter plots of error rates of MKDPD on USPS and MNIST, respectively, and (f) and (h) are the scatter plots of error rates of MR on USPS and MNIST, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)In Figures4(e), 4(f), 4(g), and 4(h), the x-axis represents the error rates of labeling the unlabeled samples and the y-axis represents the error rates of labeling the test data. For a good learning algorithm, its error rates on the unlabeled samples and on the test data should be close to each other; that is, the scatter points in Figures 4(e), 4(f), 4(g), and 4(h) should be close to the diagonal line. Again, in this respect, the proposed MKDPD algorithm performs the MR algorithm better.


## 6.3.3. The Multiclass Experiments

In the multiclass experiments, there are 10 classes and each class corresponds to a digit. The labeled samples of each digit are randomly selected from its samples for 10 times and each time will produce an experimental result. The average of 10 experimental results is taken as the final result and listed in the first and second column of Table5. The number of labeled samples is set to be 1, 3, and 5, respectively. It can be seen from Table 5 that the proposed MKDPD algorithm outperforms the MR algorithm.


## 6.4. Recognition of Spoken Letters

### 6.4.1. ISOLET Dataset

ISOLET is a dataset of spoken letters and can be downloaded from UCI machine learning repository. ISOLET contains the utterances of 150 speakers who spoke 26 English letters twice, and then each speaker has 52 utterances. In the experiment, two subsets of ISOLET, whose names are ISOLET1 and ISOLET5 respectively, are directly download from (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). Each subset contains the utterances of 30 speakers. We take the data in ISOLET1 as the samples and the data in ISOLET5 as the test data (new coming data).


### 6.4.2. The Two-Class Experiments

In the two-class experiments, the utterances of the first 13 English letters are classified as one class and the utterances of the last 13 English letters are classified as another class. We take the 52 utterances of one speaker from ISOLET1 as the labels samples and the utterances of the other speakers in ISOLET1 as the unlabeled samples. Since there are 30 speakers in ISOLET1, we can construct 30 two-class experiments this way and the 30 experimental results are presented in Figure5. As can be seen from Figure 5, the proposed MKDPD algorithm outperforms the MR algorithm. The averages of 30 experimental results experiments are listed in Table 4, which also shows that the proposed MKDPD performs better than the MR algorithm.Table 4
Average error rates (%) of the two-class experiments on Yale-B and CMU-PIE datasets with different number of labeled samples.
Dataset
Algorithm
3 labeled samples
5 labeled samples
7 labeled samples
Unlabeled
Test
Unlabeled
Test
Unlabeled
Test
Yale-B
MKDPD
35.2279
31.4955
30.4664
25.1786
27.3871
20.7087
MR
36.7658
32.7455
31.7899
26.8136
28.8743
22.7087
CMU-PIE
MKDPD
23.9889
20.4167
13.6962
10.1042
8.5904
5.5754
MR
26.0776
22.9712
15.9315
12.3611
10.0515
6.8452Table 5
Error rates (%) of the multiclass problem experiments on five datasets: USPS, MNIST, ISOLET, Yale-B, and CMU-PIE, where the value in bracket is the number of labeled sample in each class.
Dataset
Algorithm
Unlabeled (labeled samples)
Test (labeled samples)
USPS
MKDPD
19.8241 (
1
)
12.7056 (
3
)
10.3949 (
5
)
18.1100 (
1
)
10.9359 (
3
)
8.5658 (
5
)
MR
23.5377 (1)
14.5279 (3)
11.2359 (5)
21.2428 (1)
13.3242 (3)
10.2856 (5)
MNIST
MKDPD
31.8342 (
1
)
20.5939 (
3
)
16.0872 (
5
)
38.5650 (
1
)
27.2950 (
3
)
23.0300 (
5
)
MR
35.1206 (1)
21.2741 (3)
17.9026 (5)
44.6050 (1)
31.3800 (3)
26.7300 (5)
ISOLET
MKDPD
18.5743 (
2
)
12.7060 (
4
)
10.3704 (
6
)
29.9469 (
2
)
24.4297 (
4
)
21.7241 (
6
)
MR
20.6300 (2)
15.1305 (4)
13.0057 (6)
30.1790 (2)
25.4111 (4)
22.4801 (6)
Yale-B
MKDPD
36.4440 (
3
)
26.6991 (
5
)
18.4750 (
7
)
35.3516 (
3
)
26.8203 (
5
)
17.2070 (
7
)
MR
45.5172 (3)
36.9676 (5)
31.3500 (7)
41.9531 (3)
36.1406 (5)
25.5078 (7)
CMU-PIE
MKDPD
23.9773 (
3
)
11.5591 (
5
)
5.6034 (
7
)
20.1968 (
3
)
9.3056 (
5
)
4.1551 (
7
)
MR
25.2904 (3)
12.2715 (5)
6.3793 (7)
21.0532 (3)
11.0069 (5)
5.7292 (7)Figure 5
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of ISOLET set, where the y-axis is the 30 binary classification problems; (b) is the error rates of MKDPD and MR on test samples of ISOLET set.
(a)
(b)


### 6.4.3. The Multiclass Experiments

In the multiclass experiments, the utterances of each English letter are classified as a class, and then there are 26 classes. We randomly selectN speakers from ISOLET1 and take their utterances as the labeled samples. The utterances of the other speakers in ISOLET1 are then taken as the unlabeled samples. In order to alleviate the effect of randomness, the selection of N speakers is performed for 10 times and each time will produce an experimental result. The averages of 10 experimental results are taken as the final results and listed in the third column of Table 5. It can be observed from Table 5 that the proposed MKDPD algorithm achieves about 1%~3% improvements over the MR algorithm.


## 6.4.1. ISOLET Dataset

ISOLET is a dataset of spoken letters and can be downloaded from UCI machine learning repository. ISOLET contains the utterances of 150 speakers who spoke 26 English letters twice, and then each speaker has 52 utterances. In the experiment, two subsets of ISOLET, whose names are ISOLET1 and ISOLET5 respectively, are directly download from (http://manifold.cs.uchicago.edu/manifold_regularization/manifold.html). Each subset contains the utterances of 30 speakers. We take the data in ISOLET1 as the samples and the data in ISOLET5 as the test data (new coming data).


## 6.4.2. The Two-Class Experiments

In the two-class experiments, the utterances of the first 13 English letters are classified as one class and the utterances of the last 13 English letters are classified as another class. We take the 52 utterances of one speaker from ISOLET1 as the labels samples and the utterances of the other speakers in ISOLET1 as the unlabeled samples. Since there are 30 speakers in ISOLET1, we can construct 30 two-class experiments this way and the 30 experimental results are presented in Figure5. As can be seen from Figure 5, the proposed MKDPD algorithm outperforms the MR algorithm. The averages of 30 experimental results experiments are listed in Table 4, which also shows that the proposed MKDPD performs better than the MR algorithm.Table 4
Average error rates (%) of the two-class experiments on Yale-B and CMU-PIE datasets with different number of labeled samples.
Dataset
Algorithm
3 labeled samples
5 labeled samples
7 labeled samples
Unlabeled
Test
Unlabeled
Test
Unlabeled
Test
Yale-B
MKDPD
35.2279
31.4955
30.4664
25.1786
27.3871
20.7087
MR
36.7658
32.7455
31.7899
26.8136
28.8743
22.7087
CMU-PIE
MKDPD
23.9889
20.4167
13.6962
10.1042
8.5904
5.5754
MR
26.0776
22.9712
15.9315
12.3611
10.0515
6.8452Table 5
Error rates (%) of the multiclass problem experiments on five datasets: USPS, MNIST, ISOLET, Yale-B, and CMU-PIE, where the value in bracket is the number of labeled sample in each class.
Dataset
Algorithm
Unlabeled (labeled samples)
Test (labeled samples)
USPS
MKDPD
19.8241 (
1
)
12.7056 (
3
)
10.3949 (
5
)
18.1100 (
1
)
10.9359 (
3
)
8.5658 (
5
)
MR
23.5377 (1)
14.5279 (3)
11.2359 (5)
21.2428 (1)
13.3242 (3)
10.2856 (5)
MNIST
MKDPD
31.8342 (
1
)
20.5939 (
3
)
16.0872 (
5
)
38.5650 (
1
)
27.2950 (
3
)
23.0300 (
5
)
MR
35.1206 (1)
21.2741 (3)
17.9026 (5)
44.6050 (1)
31.3800 (3)
26.7300 (5)
ISOLET
MKDPD
18.5743 (
2
)
12.7060 (
4
)
10.3704 (
6
)
29.9469 (
2
)
24.4297 (
4
)
21.7241 (
6
)
MR
20.6300 (2)
15.1305 (4)
13.0057 (6)
30.1790 (2)
25.4111 (4)
22.4801 (6)
Yale-B
MKDPD
36.4440 (
3
)
26.6991 (
5
)
18.4750 (
7
)
35.3516 (
3
)
26.8203 (
5
)
17.2070 (
7
)
MR
45.5172 (3)
36.9676 (5)
31.3500 (7)
41.9531 (3)
36.1406 (5)
25.5078 (7)
CMU-PIE
MKDPD
23.9773 (
3
)
11.5591 (
5
)
5.6034 (
7
)
20.1968 (
3
)
9.3056 (
5
)
4.1551 (
7
)
MR
25.2904 (3)
12.2715 (5)
6.3793 (7)
21.0532 (3)
11.0069 (5)
5.7292 (7)Figure 5
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of ISOLET set, where the y-axis is the 30 binary classification problems; (b) is the error rates of MKDPD and MR on test samples of ISOLET set.
(a)
(b)


## 6.4.3. The Multiclass Experiments

In the multiclass experiments, the utterances of each English letter are classified as a class, and then there are 26 classes. We randomly selectN speakers from ISOLET1 and take their utterances as the labeled samples. The utterances of the other speakers in ISOLET1 are then taken as the unlabeled samples. In order to alleviate the effect of randomness, the selection of N speakers is performed for 10 times and each time will produce an experimental result. The averages of 10 experimental results are taken as the final results and listed in the third column of Table 5. It can be observed from Table 5 that the proposed MKDPD algorithm achieves about 1%~3% improvements over the MR algorithm.


## 6.5. Face Recognition

### 6.5.1. YALE-B and CMU-PIE Datasets

YALE-B (http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html) is a dataset of face images which consists of the face images of 10 persons; each person is photographed under 9 poses and 64 illuminations. In the experiment, we select the face images of 8 persons of 64 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. For each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data). CMU-PIE [38] is another dataset of face images which consists of more than 40000 images of 68 persons; each person is photographed under 4 expressions, 24 Illuminations, and 13 poses. In the experiment, we select the face images of 8 persons of 3 poses and 24 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. Again, for each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data).


### 6.5.2. The Two-Class Experiments

We select the face images of two persons to construct a binary classification problem and then there are a total of 28 binary classification problems. For each binary classification problem,N samples of each person are taken as the labeled samples and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the N samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final results (see Figures 6 and 7), where the number of labeled samples is set to be N
=
3,5, and 7, respectively. The average of 28 binary classification results is listed in Table 4. It can be seen that, compared with the MR algorithm, the proposed MKDPD algorithm achieves about 1%~5% improvements.Figure 6
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the Yale-B set; (b) is the error rates (%) of MKDPD and MR on test samples of the Yale-B set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled samples in each class.
(a)
(b)Figure 7
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the CMU-PIE set; (b) is the error rates (%) of MKDPD and MR on test samples of the CMU-PIE set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled sample in each class.
(a)
(b)


### 6.5.3. The Multiclass Experiments

In the multiclassification experiments, we take the face images of a person as one class and then there are 8 classes.N samples of each person are taken as the labeled samples and the remaining samples as the unlabeled samples. Again, the N labeled samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final result and listed in the last four columns of Table 5, where the number of labeled samples is set to be N
=
3,5, and 7, respectively. As can be seen, the proposed MKDPD algorithm achieves about 1%~12% improvements to the MR algorithm.


## 6.5.1. YALE-B and CMU-PIE Datasets

YALE-B (http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html) is a dataset of face images which consists of the face images of 10 persons; each person is photographed under 9 poses and 64 illuminations. In the experiment, we select the face images of 8 persons of 64 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. For each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data). CMU-PIE [38] is another dataset of face images which consists of more than 40000 images of 68 persons; each person is photographed under 4 expressions, 24 Illuminations, and 13 poses. In the experiment, we select the face images of 8 persons of 3 poses and 24 illuminations as the experimental dataset. Each image is cropped and resized to an image of 32
×
32 pixels. Again, for each person, 50% of his face images are taken as the samples, while his other face images are taken as the test data (new coming data).


## 6.5.2. The Two-Class Experiments

We select the face images of two persons to construct a binary classification problem and then there are a total of 28 binary classification problems. For each binary classification problem,N samples of each person are taken as the labeled samples and the remaining samples are taken as the unlabeled samples. To avoid the randomness, the N samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final results (see Figures 6 and 7), where the number of labeled samples is set to be N
=
3,5, and 7, respectively. The average of 28 binary classification results is listed in Table 4. It can be seen that, compared with the MR algorithm, the proposed MKDPD algorithm achieves about 1%~5% improvements.Figure 6
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the Yale-B set; (b) is the error rates (%) of MKDPD and MR on test samples of the Yale-B set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled samples in each class.
(a)
(b)Figure 7
Two-class problem experiments: (a) is the error rates (%) of MKDPD and MR on unlabeled samples of the CMU-PIE set; (b) is the error rates (%) of MKDPD and MR on test samples of the CMU-PIE set. And the y-axis of each figure is the 28 binary classification problems and the value in bracket is the number of labeled sample in each class.
(a)
(b)


## 6.5.3. The Multiclass Experiments

In the multiclassification experiments, we take the face images of a person as one class and then there are 8 classes.N samples of each person are taken as the labeled samples and the remaining samples as the unlabeled samples. Again, the N labeled samples are randomly taken for 10 times and each time will produce an experimental result. The average of 10 experimental results is presented as the final result and listed in the last four columns of Table 5, where the number of labeled samples is set to be N
=
3,5, and 7, respectively. As can be seen, the proposed MKDPD algorithm achieves about 1%~12% improvements to the MR algorithm.


## 7. Conclusion

In machine learning, one variable of a kernel function is often anchored on each given sample and thus derives a number of basic functions of the label function. The weights of basic functions in the label function are then trained by exploiting the labels of labeled samples. The basic functions derived this way are the same in shape, only different in the positions of data space. Obviously, these basic functions seem too simple to adapt to the changes of data distribution. For example, if the given samples are distributed unevenly, then in the area where there are too many samples are given, there will be too many basic functions located in this area and maybe overlapped too much, while in the area where there are too few samples given, there will be too few basic functions located in this region and maybe overlapped too little or not overlapped at all.In the MKDPD algorithm proposed in this paper, we adjust the basic functions according to the probabilities of data on the given samples. If the probability of data on a sample is large, then the number of samples in the vicinity of the sample will be large too and we can reduce the support of the basic function located on the sample accordingly to avoid overlapping too much with other basic functions. Likewise, if the probability of data on a sample is small, the number of samples in the vicinity of the sample will be small too and we can expand the support of the basic function located on the sample accordingly to avoid overlapping too little with other basic functions. The experimental results justify the proposed MKDPD algorithm.From the perspective of the applications of data classification, the aim of machine learning is to label the new coming data. Usually, there are three methods: unlearning, relearning, and semilearning. In the MKDPD algorithm proposed in this paper, there are two learning processes: learning the basic functions and learning the weights of basic functions. In this paper we propose a semilearning method based on the MKDPD algorithm. The proposed semilearning method regards the new coming data as unlabeled samples and mixes them with the original samples to relearn the basic functions, but still the original weights to combine the new basic functions to label the new coming data. The proposed MKDPD-based method for labeling new coming data achieves a better trade-off between the computational accuracy and efficiency.



---

*Source: 5927306-2016-06-23.xml*