Learning on Relational Data: Prototype-Based Classification of Attributed Graphs
| dc.contributor.advisor | Obermayer, Klaus | en |
| dc.contributor.author | Srinivasan, Shankar Deepak | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik | en |
| dc.date.accepted | 2011-08-19 | |
| dc.date.accessioned | 2015-11-20T20:49:22Z | |
| dc.date.available | 2011-11-01T12:00:00Z | |
| dc.date.issued | 2011-11-01 | |
| dc.date.submitted | 2011-11-01 | |
| dc.description.abstract | In der strukturellen Mustererkennung haben sich Graphen mit Attributen als nützliche Methode zur Repräsentation von Mustern erwiesen. Sie verfügen über viele Vorteile gegenüber Vektorräumen, wie etwa der Möglichkeit, Relationen zwischen verschiedenen Komponenten eines Musters zu repräsentieren. Es fehlt jedoch ein Repertoire an Methoden für alltägliche Aufgaben wie Klassifikation oder Clusterverfahren. Der wesentliche Grund dafür ist das Fehlen von erweiterten mathematischen Strukturen auf Graphenräumen, wie sie für Vektorräume existieren. Selbst die elementarsten Konzepte, wie die Addition von Graphen und der Mittelwert von Graphen, sind nicht definiert. Bei einer Methode, die vorgeschlagen wurde, wird in Strukturräumen gearbeitet. Hier werden mit Hilfe einer Zugehörigkeitsfunktion alle äquivalenten Strukturen mit Vektorrepräsentationen assoziiert. Im Fall von Graphen würden dabei Elemente der selben Äquivalenzklasse als Vektoren repräsentiert, welche zu allen Graphen korrespondieren würden, die man über Permutationen ihrer Knoten erhalten kann. Eine solche Einbettung von Graphen ermöglicht die Definition von Metriken und (Sub-)Gradienten. Mit Hilfe dieser Definitionen können prinzipielle Lernalgorithmen für relationale Daten entwickelt werden. Learning Graph Quantization (LGQ) ist ein Algorithmus zur Konstruktion eines Klassifikators, der Graphen auf Klassenbezeichner einer endlichen Menge abbildet. Der Klassifikator ist parametrisiert durch eine Menge von Prototypen mit Klassenbezeichnern. Der Klassenbezeichner eines neuen Graphen wird ermittelt, indem er dem Klassenbezeichner des nächstgelegenen Prototypen mit Hilfe einer Nächstgelegener Nachbar-Regel zugeordnet wird. Das Ziel des Lernens ist es, eine Menge von Prototypen zu finden, die die Klassenbezeichner der Graphen am besten aus der zugrundeliegenden Verteilung ermitteln. Mit den definierten Konzepten der Metrik und Subgradienten wird eine neue Klasse von Algorithmen eingeführt, um die Prototypen durch ein Subgradientenabstiegsverfahren zu ermitteln, wie es auch bei dem Learning Vector Quantization Verfahren auf Vektorräume angewandt wird. Prototyp-basierte Methoden in der strukturellen Mustererkennung können ebenfalls verwendet werden, um Graphen in Vektorräume einzubetten. Die Unähnlichkeit zwischen den Graphen und jedem Prototypen wird als Merkmal in einem (Merkmals-) Vektorraum verstanden. Bei dieser Sichtweise generieren die Prototypen einen Kern, der wiederum Merkmale zur Klassifizierung generiert. Es wird gezeigt, dass die durch die Klasse der LGQ Algorithmen ermittelten Prototypen Merkmale generieren, die sehr gut zur Klassifizierung geeignet sind. In Experimenten mit mehreren Datensätzen verbessern sie die Ergebnisse von Methoden, die dem aktuellen Stand der Technik entsprechen. Außerdem wird die Qualität der Prototypen für die Einbettung evaluiert, indem Schranken aus der statistischen Lerntheorie angewendet werden. Im dritten Teil der Arbeit wird eine Klasse von probabilistischen Verfahren eingeführt, um Graphen mit Attributen zu klassifizieren. Für Zufallsgraphen mit Attributen schlagen wir einen Online-Algorithmus zur Parameterschätzung vor, der auf Konzepten der Informationsgeometrie basiert. Der resultierende Zufallsgraph wird dabei als Prototyp ausgewählt. Zudem wird eine Formel zur Definition der Likelihood eingeführt, die über geeignete Unabhängigkeitsannahmen verfügt. Die Menge der Graphen wird in einen Merkmalsraum eingebettet (definiert über die Log-Likelihood), in dem dann Klassifikatoren trainiert werden. Es wird demonstriert, dass die Likelihood ein geeignetes Merkmal zur Klassifizierung ist. | de |
| dc.description.abstract | In structural pattern recognition, attributed graphs are a very useful means to represent patterns. They enjoy many advantages over feature vectors, such as their ability to support relations between different components of a pattern which results in higher representative and descriptive power. However, in many potential applications, they are encumbered by a lack of repertoire of techniques to accomplish standard tasks such as classification and clustering. This is primarily because the “space of graphs” has no rich mathematical structure like vector spaces. Even the most elementary concepts such as addition of graphs, mean of a set of graphs is not defined. A method has been proposed on working in the "space of structures", which associates all equivalent structures with vector representations through a membership function. In the case of graphs, elements of the same equivalence class would be vectors corresponding to all graphs obtained by all possible permutations of the nodes. Such an embedding of graphs enables the definition of metric and (sub)gradient, thus allowing the development of principled learning algorithms in the domain of relational data. Learning Graph Quantization (LGQ) is an algorithm for constructing a classifier that maps graphs to class labels from a finite set. The classifiers are parametrized by a set of prototypes with class labels. The class label of a new graph is predicted by assigning it to the class label of the nearest prototype (NPC) according to the nearest neighbor rule. The goal of learning is to find a set of prototypes that best predicts the class labels of graphs from the underlying distribution. With the notion of metric and subgradient defined, a novel class of algorithms are proposed to learn the prototypes using a subgradient descent procedure analogous to Learning Vector Quantization in the domain of feature vectors. Prototype based methods in structural pattern recognition can also be used to embed the graphs into a vector space. Consider the dissimilarity of the graphs to each prototype as a feature in a (feature) vector space. In such a view, the prototypes generate a kernel, which in turn generate features for classification. We demonstrate that the prototypes learnt by the class of LGQ algorithms generate features that are well suited for classification. In experiments, they improve the state-of-the art performance on multiple datasets. We also evaluate the quality of prototypes for embedding, using bounds from statistical learning theory. In the third part, a class of probabilistic methods is proposed for classifying attributed graphs. Within the framework of attributed random graphs, we propose an online algorithm to estimate the parameters, using concepts from Information geometry. The resulting random graph is chosen as a prototype and a formula for defining likelihood is proposed with suitable independence assumptions. The graph set is embedded into a feature space (defined by log-likelihood), where classifiers are trained. It is demonstrated that likelihood is a feature for classification. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-32974 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/3294 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-2997 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | en |
| dc.subject.other | Graphen mit Attributen | de |
| dc.subject.other | Klassifikation | de |
| dc.subject.other | Merkmalsraum Einbettung | de |
| dc.subject.other | Prototyp-basierte Methoden | de |
| dc.subject.other | Zufalllsgraph-Modelle | de |
| dc.subject.other | Attributed graphs | en |
| dc.subject.other | Classification | en |
| dc.subject.other | Feature space embedding | en |
| dc.subject.other | Prototype based methods | en |
| dc.subject.other | Random models | en |
| dc.title | Learning on Relational Data: Prototype-Based Classification of Attributed Graphs | en |
| dc.title.translated | Lernen auf Relationalen Daten: Prototyp-basierte Klassifikation von Graphen mit Attributen | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.institute | Inst. Softwaretechnik und Theoretische Informatik | de |
| tub.identifier.opus3 | 3297 | |
| tub.identifier.opus4 | 3112 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1