Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1357
Main Title: Structural Neural Learning Machines
Translated Title: Neuronale Lernverfahren für Graphen
Author(s): Jain, Brijnesh Johannes
Advisor(s): Wysotzki, Fritz
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Zwei aktuelle Herausforderungen beim Lernen auf strukturierten Daten sind 1. die Kombination struktureller und statistischer Mustererkennung; 2. die Integration des symbolischen und subsymbolischen Paradigmas. Die vorliegende Arbeit greift beide Zielstellungen auf und befasst sich mit der Konstruktion von strukturellen neuronalen Lernalgorithmen zur adaptiven Verarbeitung von attributierten Graphen. Die vorliegende Arbeit gliedert sich in zwei Teile. Der erste Teil ist dem Graph Matching Problem gewidmet. Im Kontext von strukturellen neuronalen Netzen tritt das Graph Matching Problem bei der Vorwärtspropagation auf. Nach einer Einführung in die strukturelle Mustererkennung wird eine einheitliche mathematische Beschreibung gängiger Graph Matching Probleme gegeben. Dazu wird das Graph Matching Problem in eine verallgemeinerte Form des Maximum Clique Problems überführt. Das verallgemeinerte Maximum Clique Problem wird als äquivalentes kontinuierliches quadratisches Optimierungsproblem über einen Hyperwürfel formuliert. Dieses Optimierungsproblem wird mit einem Selective Attention Control System (ACS) gelöst. Das ACS garantiert Konvergenz gegen eine zulässige Lösung, benötigt keine heuristische Einstellung der Systemparameter und passt die Systemparameter optimal während des Berechnungsverlauf an. Auf Grundlage des ACS sind die verbleibenen Kapitel des ersten Teils speziellen Techniken des Graph Matching Problems gewidmet. Es werden eine neuronale Lösung für das inexakte Graph Isomorphismus Problem, ein Anytime ACS Verfahren und ein selbstorganisierender Klassifikator für Graphen vorgestellt. Der zweite Teil dieser Arbeit befasst sich mit dem Problem Lernregeln zu formulieren, die strukturelle Fehlerfuntionen als Funktionen von attributierten Gewichtsgraphen minimieren. Ausgangspunkt ist das strukturelle Dot Produkt. Im Gegensatz zum Dot Produkt ist das strukturelle Dot Produkt zwar kein inneres Produkt, besitzt jedoch die gleichen geometrischen Eigenschaften wie das Dot Produkt. Desweiteren erlaubt das strukturelle Dot Produkt Teile der Maschinerie der Differential Analysis auf das Gebiet der attributierten Graphen anzuwenden. Insbesondere wird gezeigt, dass der Gradient einer strukturellen Funktion ein wohldefinierter Graph ist, der in die Richtung des steilsten Anstiegs zeigt. Da das strukturelle Dot Produkt nur fast überall glatt ist, werden Techniken aus der nicht glatten Analysis verwendet, um strukturelle Funktionen auf attributierten Graphen zu optimieren. Der mathematische Unterbau ermöglicht schließlich die Konstruktion und Analyse von strukturellen neuronalen Lernverfahren.
Learning on structural patterns from examples gives rise to two challenging problems: 1. the combination of structural and statistical pattern recognition; 2. the integration of the symbolic and sub-symbolic paradigm. The present work is devoted to the above issues, focusing on the construction of structural neural learning machines for adaptive processing of attributed graphs. The first part of this thesis is concerned with the graph matching problem arising in the feed-forward pass of structural neural learning machines. We start with an introduction to structural pattern recognition from the perspective of the graph matching problem. To provide a generic mathematical framework, we transform all common graph matching problems to a generalized form of the maximum clique problem. Next, we derive an equivalent continuous quadratic program of the generalized clique problem. To minimize the quadratic program, we propose a selective attention control system (ACS) that ensures convergence to feasible solutions, requires no tuning of system parameters, and optimally adapts its system parameters during computation. Based on the proposed ACS, the remainder of the first part deals with advanced techniques for special graph matching problems. We present a two-stage neural network solution to the noisy graph isomorphism problem, an anytime ACS algorithm that can be interrupted at any time and return a result of guaranteed quality, and a self-organizing classifier for graphs combining the principle elimination of competition with concepts from anytime computing. The second part of this thesis focuses on the problem of formulating learning rules to minimize structural error criteria as functions of attributed weight graphs. The starting point is the structural dot product. Though it is not an inner product, we show that the structural dot product of attributed graphs has the same geometrical properties as the standard dot product of vectors. In addition, the structural dot product gives rise to the key result of this contribution: parts of the powerful machinery of differential analysis can be applied to the domain of attributed graphs. In particular, we show that the gradient of a permutation invariant function on attributed graphs is a well-defined graph pointing in the direction of steepest increase. Since the structural dot product is only smooth almost everywhere, we accommodate nonsmooth techniques to minimize structural functions on attributed graphs. Using the mathematical toolkit at hand, we construct structural neural learning machines and analyze their basic principles and mechanisms. The resulting structural neural learning machines constitute a generic framework that directly operates on attributed graphs. As such, they neither have to cope with uncontrollable loss of structural information when transforming graphs to simpler data types, nor with the reconstruction problem.
URI: urn:nbn:de:kobv:83-opus-12779
http://depositonce.tu-berlin.de/handle/11303/1654
http://dx.doi.org/10.14279/depositonce-1357
Exam Date: 14-Jul-2005
Issue Date: 26-May-2006
Date Available: 26-May-2006
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Graph
Graph Matching
Lernverfahren
Neuronale Netze
Graph
Graph Matching
Machine Learning
Neural Networks
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_14.pdf15.93 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.