Algorithms

Innovation inside
read more

XELOPES

prudsys embedded
XELOPES Library

Research & Development

Research drives progress
Scientific Board
Patents
x
Sparse grids

Sparse Grids

prudsys > Technology > Algorithms > Sparse grids

x

Function

The sparse grids method is considered to be one of the most ambitious techniques for the solution of classification and regression problems. It is the first, universal multivariate procedure which is linearly scaleable to the number of data sets and which can therefore be used on extremely large amounts of data.

The basic idea of sparse grids is the solution of classification and regression problems from their operator equations (mostly in the form of differential equations) where the label space is discretized. This formulation has been used for decades, particularly in the form of finite element analysis, to solve physical problems but has until now failed in the data mining area because of the complexity of the calculations needed to deal with exponentially increasing amounts of data (i.e. the curse of dimensionality).

Advantages

  • Sparse grids can perform classification and regression analysis on virtually unlimited numbers of data sets. The method is linearly scaled to the number of data sets and, uncharacteristically, is therefore ideal for our purposes.
  • A further advantage is that sparse grids enable the spectral representation of the regression function. In this way it can be interpreted and can be analysed, compressed and smoothed with the tried and tested signal processing methods.
  • Finally, the universal formulation via sparse grids means that it can be used on completely new operator formulations. While existing methods are tailored for operator equations (e.g. SVMs on regularising networks), sparse grids are a general approximating method for high dimensional integral and differential equations and can therefore be used for the broadest class of operator equations. The explicit integration of prior knowledge is therefore also possible. This opens up completely new possibilities for data mining.

Dr. Michael Thess, Director, Research & Development at prudsys AG:

"The changeover to high discretization methods in general and its predecessor - the sparse grid method - in particular has enabled a revolution in data mining. Behind this there is a simple yet fundamental idea: Replacing the infinite function spaces with finitely dimensioned spaces means that for the first time we can handle most practical challenges without problems. This is comparable to the changeover from the analytical to the numerical solution of differential equations which took place in the fifties or to the analog to digital changeover in computing which took place in the sixties. The sparse grid method not only increases computational speed but also brings with it a completely new standards of quality in data mining"

Partner

prudsys AG develops sparse grid technology for data mining applications in cooperation with Prof. Michael Griebel (University of Bonn) and Dr. Jochen Garcke (Berlin Technical University).

Integration

Sparse grids are a core component of the XELOPES library and therefore also available in the prudsys RDE.

 x
x x x