Institute for
Numerical Simulation

Research Group
M. Griebel

• Home
• Publications
• Research
  • Projects
  • Software
  • Computing
  • Conferences
• Teaching
• People
• Miscellany
• Jobs
• Links
• Contact
• Inside

Beschreibung der notwendigen Arbeiten

Im folgenden stellen wir die Methoden, Lösungswege wie auch die Gliederung in Teilaufgaben im Detail vor.

Der geplante Ansatz stützt sich auf folgende variationelle Formulierung der Regularisierungstheorie. Zu minimieren (mit allgemeiner Kostenfunktion $c(x_i,y_i,f_h)$) ist:

$$R_{reg}(f_h) = \frac{1}{l} \sum_{i=1}^l c(x_i,y_i,f_h) + \lambda \Vert \hat P f_h \Vert^2_{L_2}, \quad f_h \in V_h$$ (2)

mit wie vorher $x_i$ den Datenpunkten der Stichprobe und $y_i$ den zugehörigen Labels. Die Funktion $f_h$ stammt aus dem Funktionenraum $V_h$. Speziell soll der Fehler im Quadrat minimiert werden, d.h. $c(x_i,y_i,f_h) = \left(f_h(x_i)-y_i \right)^2$.

Der Klassifikator $f_h$ wird aus den Basisfunktionen von $V_h$ aufgebaut, d.h. $f_h = \sum_{j=1}^n \alpha_j \varphi_j(x)$. Durch Minimierung von (2) bekommen wir für allgemeine Regularisierungsoperatoren für ( $k = 1,\ldots,n$) die Gleichung

$$\sum_{j=1}^n \alpha_j \left[l \lambda (\hat P \varphi_j, \hat P \... ...varphi_j(x_i) \cdot \varphi_k (x_i) \right] = \sum_{i=1}^l y_i \varphi_k (x_i).$$ (3)

Im Gegensatz zu herkömmlichen Data Mining Verfahren, die mit Funktionen auf den Datenpunkten arbeiten, wird in dem hier verfolgten Ansatz ein Punktgitter im Merkmalsraum aufgebaut und auf diesen Gitterpunkten wird der Klassifikator bestimmt. Speziell für $\hat P = \nabla$ als Regularisierungsoperator erhalten wir ein Laplaceproblem mit einem zusätzlichen von den Daten abhängigen Term. Dieses Problem kann nun kosteneffizient mit Dünngittermethoden diskretisiert und gelöst werden.

Unter Ausnutzung dieser variationellen Formulierung gliedert sich die geplante Arbeit in die folgenden Punkte.

• Berechnung des Klassifikators mit Dünnen Gittern

  Mittels der sogenannten Kombinationstechnik [11,12,14] soll eine Variante des Dünngitter-Verfahrens zur Diskretisierung und Lösung von (3) eingesetzt werden. Dabei wird die Dünngitter-Lösung aus der Lösung kleinerer Probleme zusammengesetzt, die unabhängig voneinander berechnet werden können, siehe oben. Hierbei kommen Lösungsbeschleunigungsansätze, wie z.B. Vorkonditionierer oder Mehrgitterverfahren, für die Berechnung der einzelnen Teilprobleme zum Einsatz. Dies erfordert spezielle an die stark anisotropen Gitter angepaßte Mehrgitterverfahren, die insbesondere mit Semivergröberung arbeiten. Diese Konstruktionen sind sowohl für Splines als auch für Wavelets einsetzbar. Es ist vorgesehen, Dünngitter-Löser mit Prewavelet- und Wavelet-Basen zusammen mit der Kombinationstechnik zu implementieren.

• Nachbearbeitung und Auswertung des Klassifikators/Dünngitter Wavelet Kompression

  Multiskalen- und hierarchische Techniken wie die Verwendung von Wavelets, Wavelet packets, und pyramidale Verfahren sind sehr wertvoll, um die Untersuchung des berechneten Klassifikators auf unterschiedlichen Leveln der Auflösung zu ermöglichen. Mit Wavelets kann außerdem mittels z.B. Thresholding die resultierende Funktion weiter geglättet und analysiert werden. Auch kann der Dünngitterklassifikator mit diesen Techniken komprimiert werden um eine schnellere Auswertung in interaktiven Untersuchungen zu ermöglichen. Es sollen entsprechende Kompressionsalgorithmen für Dünngitterdiskretisierungen programmiert werden. Diese basieren auf Tensorprodukt-Wavelets, was erst die Anwendung für höherdimensionale Probleme ermöglicht. Die Eigenschaften der entstehenden Algorithmen sind im Hinblick auf Kompressionseigenschaften der Lösungen zu untersuchen. Spezielles Augenmerk wird dabei auf den Zusammenhang zwischen den speziellen Daten und dem Kompressionseffekt gelegt.

• Parallelisierung

  Bei Daten mit einer größeren Anzahl von Attributen und einer daraus resultierenden höheren Dimensionsanzahl des Variationsproblems sind des weiteren parallele Implementierungen zur schnellen Berechnung des Klassifikators notwendig. Ebenso ist eine parallele Implementierung der Auswertung des Klassifikators für die interaktive Untersuchung der Ergebnisse solcher Anwendungen sinnvoll. Mit der Kombinationstechnik wird dazu von vornherein ein einfach parallelisierbares Verfahren eingesetzt.

• Benchmarking

  Es sind umfangreiche Benchmark-Tests des Verfahrens sowohl anhand praktischer als auch synthetischer Datensätze auszuführen. Zunächst soll die Klassifikationsgüte im Vergleich zu herkömmlichen Klassifikationsverfahren wie Neuronale Netze oder Support-Vektor-Maschinen getestet werden. Da die Verfahren im Wesentlichen auf den gleichen Regularisierungsansätzen beruhen, müssen Dünnegitter-Verfahren vergleichbare Klassifikationsgüten wie die derzeit besten Klassifikationsverfahren aufweisen. Der Schwerpunkt des Benchmarking wird auf dem Test der Rechenzeiten sowohl zur Erstellung von Klassifikatoren (Lernen) als auch der on-line Klassifikation liegen.

  PRUDENTIAL SYSTEMS verfügt über eine umfangreiche Bibliothek von State-of-the-Art Klassifikationsverfahren sowie über eigene Verfahren und Benchmark-Daten aus der Praxis. Außerdem steht ein Generator zur Erzeugung großer Datensätze mit verschiedenen Charakteristiken zur Verfügung, welcher um weitere Komponenten ergänzt werden soll, um spezielle Eigenschaften der Dünngitter-Klassifikation testen zu können.

• Anwendung

  Das Ziel des Projektes ist die Implementierung und Validierung des neuartigen auf dem Tensorprodukt-Ansatz zur Lösung von Variationsproblemen beruhenden Klassifikationsalgorithmus. Dieser soll von den Projektpartnern im Bereich der Finanzmathematik, insbesondere für die Kursprognose auf der Basis untertägiger Tick-Daten (West LB), aber auch in verwandten Bereichen des Data Mining wie dem Direkt-Marketing (PRUDENTIAL SYSTEMS) genutzt und auf diese Weise in die industrielle Anwendung getragen werden. Es soll das Verfahren implementiert und mit Hilfe der Projektpartner an realen Daten getestet und mit den Ergebnissen anderer Verfahren verglichen werden.

  Die Daten auf denen die Tests ausgeführt werden sollen, werden in Abstimmung mit den Projektpartnern (West LB und PRUDENTIAL SYSTEMS) von diesen zur Verfügung gestellt.

Zusammenfassend sind also folgende Arbeiten durchzuführen:

• Implementierung eines parallelen Dünngitterverfahrens zur Lösung des hochdimensionalen Variationsproblems
• Implementierung der Nachbearbeitung des erhaltenen Klassifikators mittels z.B. Tensorprodukt-Wavelet Tresholding
• Implementierung der schnellen parallelen Auswertung des Klassifikators
• Benchmark-Tests des Klassifikationsverfahrens besonders für sehr große Datensätze
• Tests des Verfahrens anhand praktischer Applikationen, insbesondere der Kursprognose untertägiger Tick-Daten (gestellt von West LB) sowie im Bereich Direkt-Mailing (PRUDENTIAL SYSTEMS)