Sparse Grids

Algorithmen

Innovation inside

XELOPES

prudsys embedded
XELOPES Bibliothek

Forschung & Entwicklung

Forschung bewegt
scientific board
Patente

Sparse Grids | Warenkorb- und Sequenzanalyse | Reinforcement Learning | Disposition und Preisoptimierung

Funktion

Die Sparse Grids Technik (Sparse Grids = Dünne Gitter) gilt als eines der ambitioniertesten Verfahren zur Lösung von Klassifikations- und Regressionsproblemen. Es ist das erste universelle multivariate Verfahren, welches linear mit der Anzahl der Datensätze skaliert und somit auf riesigen Datenmengen eingesetzt werden kann.

Die Grundidee bei Sparse Grids besteht darin, Klassifikations- und Regressionsprobleme über deren Operatorgleichungen - zumeist in Form von Differentialgleichungen - zu lösen, indem der Merkmalsraum diskretisiert wird. Dieser Ansatz, welcher sich für physikalische Probleme - insbesondere in Form der Finite-Elemente-Methode - seit Jahrzehnten bewährt hat, scheiterte im Data-Mining-Bereich bislang an der Rechenkomplexität, welche exponentiell mit der Dimensionszahl ansteigt (Fluch der Dimensionen).

Vorteile

Mittels Sparse Grids können erstmals Klassifikations- und Regressionsaufgaben auf nahezu unbegrenzter Anzahl von Datensätzen gelöst werden. Das Verfahren skaliert linear mit der Zahl der Datensätze und ist diesbezüglich asymptotisch optimal.
Ein weiterer Vorteil ergibt sich aus der spektralen Repräsentation der Regressionsfunktion. Sie ist somit interpretierbar und kann mit den bewährten Methoden der Signalverarbeitung analysiert, komprimiert und geglättet werden.
Schließlich erlaubt der universelle Ansatz über Sparse Grids, diese auf völlig neue Operatorformulierungen anzuwenden. Während derzeitige Verfahren auf fixe Operatorgleichungen zugeschnitten sind, z.B. SVMs auf Regulariserungsnetzwerke, sind Sparse Grids ein generelles Approximationsverfahren für hochdimensionale Integral- und Differentialgleichungen und damit auf weiteste Klassen von Operatorgleichungen anwendbar. Auch der Einbau von aprior-Wissen kann hier explizit erfolgen. Damit erschließen sich völlig neue Aufgabenstellungen für das Data Mining.

Dr. Michael Thess, Leiter Forschung & Entwicklung bei der prudsys AG:

"Der Übergang zu hochdimensionalen Diskretisierungsverfahren im allgemeinen und zu deren Vorreiter - der Dünngittertechnik - im besonderen, stellt eine zentrale Revolution im Data Mining dar. Dahinter steckt eine einfache, aber fundamentale Idee: Indem wir unendlichdimensionale Funktionsräume durch endlichdimensionale ersetzen, werden die meisten praktischen Herausforderungen überhaupt erst sauber handelbar! Vergleichbar dem Übergang von der analytischen zur numerischen Lösung von Differentialgleichungen in den fünfziger Jahren oder von Analog- zu Digitalrechnern in den sechziger Jahren, bedeutet der Übergang zu Dünngitterverfahren nicht nur eine Erhöhung der Rechengeschwindigkeit, sondern stellt insgesamt eine völlig neue Qualität des Data Mining dar".

Partner

Die prudsys AG entwickelt die Dünngittertechnologie für Data-Mining-Applikationen seit zehn Jahren zusammen mit ihren universitären Partnern Uni Bonn (Prof. Michael Griebel) und TU Berlin (Dr. Jochen Garcke).