Personal tools

SC²S Colloquium - January, 8, 2009

From Sccswiki

Jump to: navigation, search
Date: January 8
Room: 02.07.023
Time: 3 pm, s.t.


15:00 Uhr - Evgeniy Zharovsky: Gebietszerlegungsorientierte Dünngitterverfahren (DA)

Seit der Einführung der dünnen Gitter werden diese bei hochdimensionalen Problemen eingesetzt um dem Fluch der Dimensionen zu begegnen. Neben vielen Vorteilen, die diese Gitter bieten, gibt es den Nachteil, dass weder die Massen- noch die Steifigkeitsmatrix dünn besetzt sind. Für iterative Verfahren zur Lösung eines linearen Gleichungssystems wird das Matrix-Vektor-Produkt mit solchen Matrizen benötigt. Es sind Algorithmen entstanden, die dieses Problem durch geschickte Algorithmik mit geringem Speicher- und Operationsaufwand lösen. Zum Teil haben sie sogar linearen Aufwand. Eine oft zitierte Technik dabei ist das unidirektionale Vorgehen.

In meiner Diplomarbeit wird ein anderer Zugang zur Berechnung des Matrix-Vektor-Produktes für die Massenmatrix auf dünnen Gittern untersucht. Der Ansatz dazu basiert auf der Idee der Gebietszerlegung. Dadurch wird die rekursive Struktur der dünnen Gitter ausgenutzt und es entstehen inhärent parallelisierbare Algorithmen, die nach dem devide&conquer-Prinzip arbeiten. In diesem Vortrag möchte ich einen Algorithmus vorstellen, der linearen Aufwand in der Zahl der unbekannten hat und den Kern meiner Diplomarbeit bildet.


15:30 Uhr - Markus Wunsch: Halbüberwachtes (semi-supervised) Lernen mit raumadaptiven dünnen Gittern (DA)

Ziel des Data Minings ist, bislang unbekannte Information aus großen Datenmengen zu extrahieren. Bei Klassifikations- oder Regressionsanwendungen beschränkt sich das Wissen über das Problem meist auf eine Menge Trainingsdaten, für die die Zielgröße (Klassenzugehörigkeit oder Funktionswert) bekannt ist. Die den Daten zugrundeliegende, aber unbekannte Funktion soll rekonstruiert werden.

Oft ist nur für eine kleine Teilmenge der Daten die tatsächliche Klassifikation bekannt; es kann daher nur auf eine Teilmenge der Daten trainiert und von diesen gelernt werden. Halbüberwachtes Lernen versucht, die Daten mit unbekannter Klassifikation mit in den Lernprozess einzubeziehen und die Information, wo potentielle weitere Daten liegen, zu nutzen.

In dieser Arbeit wird die Realisation eines Graph-basierten Ansatzes für Halbüberwachtes Lernen mit adaptiv verfeinerbaren Dünnen Gittern untersucht. Bei diesem Verfahren erfolgt die Regularisierung des Klassifikators nicht nur mittels der bereits aus Supervised-Learning-Verfahren bekannten Glattheitsbedingung bezüglich des Merkmalsraumes, sondern auch mittels einer zweiten Glattheitsbedingung, durch welche eine Regularisierung auf der Mannigfaltigkeit innerhalb des Merkmalsraumes, auf der die Trainingsdaten liegen, angestrebt wird. Da die Gestalt dieser Mannigfaltigkeit im Allgemeinen nicht im Voraus bekannt ist, wird der zugehörige Regularisierungsoperator mit Hilfe von Distanzen zwischen den Trainingsdatenpunkten approximiert, wobei auch die Daten mit unbekannter Klassifikation in die Berechnung einbezogen werden. Die Ergebnisse des Verfahrens hängen somit von der Art der Distanzberechnung ab, welche in einer Graphstruktur über den Trainingsdaten realisiert wird. Neben der euklidischen Distanzmessung werden weitere mannigfaltigkeitsorientierte Verfahren zur Distanzberechnung vorgestellt, wodurch sich die Ergebnisgüte in manchen Fällen steigern lässt. Weiterhin werden Methoden zur mannigfaltigkeitsorientierten Reduktion der Dimensionalität hochdimensionaler Datensätze auf der Basis dieser Distanzmetriken beschrieben. Schließlich werden die vorgestellten Verfahren auf einige Testbeispiele angewandt, wobei auch die Vorteile adaptiver Verfeinerungstechniken dünner Gitter diskutiert werden.