Information Technology Reference
In-Depth Information
-
Initialize latent variables
X
=(
x
1
,...
x
N
)
(often employing spectral methods like
LLE), and
-
minimize
E
(
X
)
w.r.t. DSRE employing an optimization scheme.
A typical example is unsupervised kernel regression, analyzed by Klanke and Rit-
ter [16], but further methods can also be employed. Klanke and Ritter [16] introduced
an optimization scheme based on LLE, PCA, and leave-one-out cross-validation (LOO-
CV) for UKR. Various extension of UKR have been proposed, e.g., a feature space vari-
ant (employing Mercer kernels), and the use of landmark points to reduce the
non-parametric training set. Carreira-Perpinan and Lu [5] argue that training of non-
parametric unsupervised regression approaches is quite expensive, i.e.,
(
N
3
)
in
O
(
N
2
)
in memory. Parametric methods can accelerate learning, e.g., un-
supervised regression based on radial basis function networks (RBFs) [26], Gaussian
processes [19], and neural networks [27].
time, and
O
2.2
Nearest Neighbor Regression
In the following, we give a short introduction to K-nearest neighbor regression that
is basis of the UNN approach. KNN is a technique with a long tradition. It was first
mentioned by Fix and Hodges [8] in the fifties in an unpublished US Air Force School of
Aviation Medicine report as non-parametric classification technique. Cover and Hart [3]
investigated the approach experimentally in the sixties. Interesting properties have been
found, e.g., that for
K
=1
,and
N
, KNN is bound by the Bayes error rate.
The problem in regression is to predict output values
y
∈
IR
→∞
d
of given input values
q
based on sets of
N
input-output examples
((
x
1
,
y
1
)
,...,
(
x
N
,
y
N
))
. The goal
is to learn a function
f
:
x
→
y
known as regression function. For a novel pattern
x
KNN regression computes the mean of the function values of its K-nearest neighbors:
x
∈
IR
f
KNN
(
x
):=
1
K
y
i
(2)
i∈N
K
(
x
)
N
K
(
x
)
containing the indices of the
K
-nearest neighbors of
x
.Theidea
of KNN is based on the assumption of locality in data space: In local neighborhoods
of a pattern
x
near patterns are expected to have similar labels
y
. Consequently, for
an unknown
x
the label must be similar to the labels of the closest patterns, which
is modeled by the average of the output value of the
K
nearest samples. KNN has
been proven well in various applications, e.g., in the detection of quasars based on
spectroscopic data [10].
with set
3
Unsupervised Nearest Neighbor Regression
In this section we introduce an iterative strategy for UNN regression [17,18] that is
based on minimization of the data space reconstruction error (DSRE).
