Classification with probability density estimation on sparse grids

Benjamin Peherstorfer, Fabian Franzelin, Dirk Pflüger, Hans Joachim Bungartz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a novel method to tackle the multi-class classification problem with sparse grids and show how the computational procedure can be split into an Offline phase (pre-processing) and a very rapid Online phase. For each class of the training data the underlying probability density function is estimated on a sparse grid. The class of a new data point is determined by the values of the density functions at this point. Our classification method can deal with more than two classes in a natural way and it provides a stochastically motivated confidence value which indicates how to rate the respond to a new point. Furthermore, the underlying density estimation method allows us to pre-compute the system matrix and store it in an appropriate format. This so-called Offline/Online splitting of the computational procedure allows an Online phase where only a few matrix vector products are necessary to learn a new, previously unseen training data set. In particular, we do not have to solve a system of linear equations anymore. We show that speed ups by a factor of several hundred are possible. A typical application for such an Offline/Online splitting is cross validation. We present the algorithm and the computational procedure for our classification method, report on the employed density estimation method on sparse grids and show by means of artificial and real world data sets that we obtain competitive results compared to the classical sparse grid classification method based on regression.

Original languageEnglish (US)
Title of host publicationSparse Grids and Applications - Munich 2012
EditorsJochen Garcke, Dirk Pfluger
PublisherSpringer Verlag
Pages255-270
Number of pages16
ISBN (Electronic)9783319045368
DOIs
StatePublished - 2014
Event2nd Workshop on Sparse Grids and Applications, SGA 2012 - Gammarth, Tunisia
Duration: Jul 2 2012Jul 6 2012

Publication series

NameLecture Notes in Computational Science and Engineering
Volume97
ISSN (Print)1439-7358
ISSN (Electronic)2197-7100

Other

Other2nd Workshop on Sparse Grids and Applications, SGA 2012
CountryTunisia
CityGammarth
Period7/2/127/6/12

ASJC Scopus subject areas

  • Modeling and Simulation
  • Engineering(all)
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Classification with probability density estimation on sparse grids'. Together they form a unique fingerprint.

Cite this