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
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
Þ
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
Search WWH ::




Custom Search