Database Reference
In-Depth Information
in terms of that of (
7.29
). Concerning the matrix
B
l
, it is obtained by just adding the
new entries of the basis functions in the data points
x
fg
e
i¼
1
to
B
l
. Notice also that the
number of unknown of (
7.29
) only depends on the grid points of the sparse grid and
does not change for an increasing number of data points.
Of course, after adding the new data point
s o
f
S
, we need to solve the complete
equation system (
7.30
) in order to determine
α
l
. However, as stated before, (
7.29
)
has the same dimensionality as (
7.30
), and provided that
S
is not very large, the
system (
7.30
) is very close to (
7.29
). So we can use
α
l
as initial iterate in
the iteration method of (
7.30
), and the solution will require, in general, only a
few iterations.
Notice that there are different ways to assemble and solve the system (
7.26
); we
did not discuss them in detail here. In general, we assemble
G
l
¼ B
l
B
l
and use it
α
l
instead of multiplying with
B
l
and
B
l
directly. Since the
dimension of
G
l
only depends on the number of grid points and, unlike as for
B
l
,not
on the number of d
ata
points
M
, it is especially suited for our adaptive approach.
Therefore, we use
G
l
¼ B
l
B
l
that can be
in
crementally calculated from
G
l
.In
the same way, we define
h
1
¼ B
1
y
and also
h
1
can be easily calculated from
h
l
.
Thus, we rewrite (
7.30
)as
for multiplication with
MC
0
l
þ G
l
λ
α
l
¼ h
l
:
ð
7
:
31
Þ
This way we arrive at the adaptive sparse grid Algorithm 7.3.
Algorithm 7.3: Adaptive computation of sparse grid classifier
g
Input: new training data set
f
ð
x
i
;
y
i
Þ
i¼
1
,
λ
, coefficients
α
l
, vectors
h
l
, matrices
C
0
l
and
G
l
α
l
, updated vectors
h
l
and matrices
G
l
Output: updated coefficients
for
q ¼
0,
,
d
1 do
for
l
1
¼
1,
...
,
n q
do
for
l
2
¼
1,
...
,
n q
(
l
1
1) do
..
for
l
d
1
¼
1,
...
,
n q
(
l
1
1)
...
(
l
d
2
1) do
l
d
¼ n q
(
l
1
1)
...
(
l
d
2
1)
(
l
d
1
1)
update matrix
G
l
from
G
l
and ve
cto
r
h
l
fro
m
h
l
solve the linear system
...
α
l
¼ h
l
starting with
MC
0
l
þ G
l
λ
α
l
end for
...
end for
end for
end for