Database Reference
In-Depth Information
L
2
,
Here
C
is
the
N N
matrix with the entries
C
j
,
k
¼ M
P
φ
j
,
P
φ
k
j
,
k ¼
1,
...
,
N
, and
B
is a rectangular
N M
matrix with entries
B
j
,
i
¼ φ
j
(x
i
),
i ¼
1,
...
,
M
,
j ¼
1,
...
,
N
. The vector
y
contains the data labels
y
i
and has length
M
. The unknown vector
α
j
and has length
N
.
Depending on the regularization operator, we obtain different minimization
problems in
V
N
. For example, if we use the gradient
α
contains the degrees of freedom
2
L
2
in the
regularization expression in (
7.1
), we obtain a Poisson problem with an additional
term which resembles the interpolation problem. The natural boundary conditions
for such a partial differential equation are Neumann conditions. The discretization
(
7.2
) gives us then the linear system (
7.7
) where
C
corresponds to a discrete
Laplacian. To obtain the classifier
f
N
, we now have to solve this system.
Φ
f ðÞ¼∇
f kk
7.2.2 Grid-Based Discrete Approximation
Up to now we have not yet been specific what finite-dimensional subspace
V
N
and
what type of basis functions {
φ
j
}
j¼
1
N
we want to use. In contrast to conventional
data mining approaches like radial basis approaches or SVMs, which work with
ansatz functions associated to data points, we now use a certain grid in the attribute
space to determine the classifier with the help of these grid points. This is similar to
the numerical treatment of partial differential equations.
For reasons of simplicity, here and in the reminder of this chapter, we restrict
ourselves to the case x
i
¼
[0,1]
d
. This situation can always be reached by
proper rescaling of the data space. A conventional finite element discretization
would now employ an equidistant grid
Ω
n
with mesh size
h
n
¼
2
n
for each
coordinate direction, where
n
is the refinement
level. In the following we
always use the gradient
P ¼ ∇
in the regularization expression (
7.3
). Let
j denote the multi-index (
j
1
,
...
,
j
d
)
∈
N
d
. We now use piecewise
d
-linear,
test and trial functions
φ
n
,j
(x)ongrid
Ω
n
. Each basis function
ϕ
n
,j
(x)isthereby
1 at grid point j and 0 at all other points of grid
Ω
n
. A finite element method on
grid
Ω
n
now would give
Þf
n
ðÞ¼
X
2
n
X
2
n
ð
f
N
ðÞ¼
...
α
n
,
j
ϕ
n
,
j
ðÞ:
j
1
j
d
And the variational procedure (
7.4
), (
7.5
), and (
7.6
) would result in the discrete
linear system
C
n
þ B
n
B
n
λ
α
n
¼ B
n
y
ð
7
:
8
Þ
with the discrete (2
n
+1)
d
(2
n
+1)
d
Laplacian
