 SG++-Doxygen-Documentation
Spatially-Dimension-Adaptive Refinement of ANOVA Components in Python

We compute the sparse grid interpolant of the function $$f(x) = \sin(10x_0)+x_1.$$ We perform spatially-dimension-adaptive refinement of the sparse grid model, which means we refine a particular grid point (locality) only in some dimensions (dimensionality).

For details on spatially-dimension-adaptive refinement see

  V. Khakhutskyy and M. Hegland: Spatially-Dimension-Adaptive Sparse Grids for Online Learning.
Pflüger and J. Garcke (ed.), Sparse Grids and Applications - Stuttgart 2014, Volume 109 of LNCSE, p. 133–162. Springer International Publishing, March 2016.

The example can be found in the file predictiveANOVARefinement.py.

1 # import modules
2 import sys
3 import math
4
5 from pysgpp import *
6 import matplotlib.pyplot as plotter
7 from mpl_toolkits.mplot3d import Axes3D

Spatially-dimension-adaptive refinement uses squared prediction error on a dataset to compute refinement indicators. Hence, here we define a function to compute these squared errors.

1 def calculateError(dataSet,f,grid,alpha,error):
2  print("calculating error")
3  #traverse dataSet
4  vec = DataVector(2)
5  opEval = createOperationEval(grid)
6  for i in range(dataSet.getNrows()):
7  dataSet.getRow(i,vec)
8  error[i] = pow(f(dataSet.get(i,0),dataSet.get(i,1))-opEval.eval(alpha,vec),2)
9  return error

We define the function $$f(x) = \sin(10x_0)+x_1$$ to interpolate.

1 f = lambda x0, x1: math.sin(x0*10)+x1
2

reate a two-dimensional piecewise bi-linear grid

1 dim = 2
2 grid = Grid.createLinearGrid(dim)
3 HashGridStorage = grid.getStorage()
4 print("dimensionality: {}".format(dim))
5
6 # create regular grid, level 3
7 level = 3
8 gridGen = grid.getGenerator()
9 gridGen.regular(level)
10 print("number of initial grid points: {}".format(HashGridStorage.getSize()))
11
12
13 # create coefficient vectors
14 alpha = DataVector(HashGridStorage.getSize())
15 print("length of alpha vector: {}".format(alpha.getSize()))
16

To create a dataset we use points on a regular 2d grid with a step size of 1 / rows and 1 / cols.

1 rows = 100
2 cols = 100
3
4 dataSet = DataMatrix(rows*cols,dim)
5 vals = DataVector(rows*cols)
6
7 for i in range(rows):
8  for j in range(cols):
9  #xcoord
10  dataSet.set(i*cols+j,0,i*1.0/rows)
11  #ycoord
12  dataSet.set(i*cols+j,1,j*1.0/cols)
13  vals[i*cols+j] = f(i*1.0/rows,j*1.0/cols)

We refine adaptively 20 times. In every step we recompute the vector of surpluses alpha, the vector with squared errors on the dataset errorVector, and then call the refinement routines.

1 # create coefficient vectors
2 alpha = DataVector(HashGridStorage.getSize())
3 print("length of alpha vector: {}".format(alpha.getSize()))
4
5 # now refine adaptively 20 times
6
7 for refnum in range(20):

Step 1: calculate the surplus vector alpha. In data mining we do it by solving a regression problem as shown in example Classification Example. Here, the function can be evaluated at any point. Hence. we simply evaluate it at the coordinates of the grid points to obtain the nodal values. Then we use hierarchization to obtain the surplus value.

1  for i in range(HashGridStorage.getSize()):
2  gp = HashGridStorage.getPoint(i)
3  alpha[i] = f(gp.getStandardCoordinate(0), gp.getStandardCoordinate(1))
4
5  # hierarchize

Step 2: calculate squared errors.

1  errorVector = DataVector(dataSet.getNrows())
2  calculateError(dataSet, f, grid, alpha, errorVector)

Step 3: call refinement routines. PredictiveRefinement implements the decorator pattern and extends the functionality of ANOVAHashRefinement. PredictiveRefinement requires a special kind of refinement functor – PredictiveRefinementIndicator that can access the dataset and the error vector. The refinement itself if performed by calling .free_refine() same for normal refinement in ANOVAHashRefinement. ANOVAHashRefinement creates new grid points only in the dimensions where the parent has level greater 1.

1  #refinement stuff
2  refinement = ANOVAHashRefinement()
3  decorator = PredictiveRefinement(refinement)
4  # refine a single grid point each time
5  print("Error over all = %s" % errorVector.sum())
6  indicator = PredictiveRefinementIndicator(grid,dataSet,errorVector,1)
7  decorator.free_refine(HashGridStorage,indicator)
8
9  print("Refinement step %d, new grid size: %d" % (refnum+1, HashGridStorage.getSize()))
10
11
12  # extend alpha vector (new entries uninitialized)
13  alpha.resizeZero(HashGridStorage.getSize())

The output of the program should look like this

 dimensionality:                   2
number of initial grid points:    17
length of alpha vector:           17
length of alpha vector:           17
calculating error
Error over all = 2672.10267813
Refinement step 1, new grid size: 19
calculating error
Error over all = 2014.91978486
Refinement step 2, new grid size: 23
calculating error
Error over all = 1702.72857166
Refinement step 3, new grid size: 27
calculating error
Error over all = 1503.10286769
Refinement step 4, new grid size: 31
calculating error
Error over all = 1315.85714785
Refinement step 5, new grid size: 35
calculating error
Error over all = 1215.70185079
Refinement step 6, new grid size: 39
calculating error
Error over all = 1126.15414566
Refinement step 7, new grid size: 41
calculating error
Error over all = 904.808476363
Refinement step 8, new grid size: 45
calculating error
Error over all = 858.551555544
Refinement step 9, new grid size: 49
calculating error
Error over all = 818.181481584
Refinement step 10, new grid size: 51
calculating error
Error over all = 837.357674149
Refinement step 11, new grid size: 53
calculating error
Error over all = 725.648098963
Refinement step 12, new grid size: 55
calculating error
Error over all = 635.969194416
Refinement step 13, new grid size: 61
calculating error
Error over all = 519.063800091
Refinement step 14, new grid size: 65
calculating error
Error over all = 441.156705522
Refinement step 15, new grid size: 69
calculating error
Error over all = 424.861166023
Refinement step 16, new grid size: 73
calculating error
Error over all = 381.044823939
Refinement step 17, new grid size: 75
calculating error
Error over all = 392.611427824
Refinement step 18, new grid size: 77
calculating error
Error over all = 339.289508891
Refinement step 19, new grid size: 81
calculating error
Error over all = 327.335761311
Refinement step 20, new grid size: 87