Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-7824
Main Title: Low dimensional visualization and modelling of data using distance-based models
Subtitle: Part I: Visualization of the effects of a changing distance on data using continuous MDS (cMDS); Part II: Inference of the latent space model for network data using expectation propagation
Translated Title: Niedrigdimensionale Visualisierung und Modellierung von Daten mit distanzbasierten Modellen
Translated Subtitle: Teil I: Visualisierung der Auswirkungen einer sich ändernden Distanzmetrik auf die Daten mittels kontinuierlichem MDS (cMDS); Teil II: Ableitung des Latent Space Modells für Netzwerkdaten mittels Expectation-Propagation
Author(s): Grünhage, Gina
Advisor(s): Opper, Manfred
Barthelme, Simon
Referee(s): Opper, Manfred
Barthelme, Simon
Hammer, Barbara
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: This thesis consists of two parts, which seek low-dimensional representations for visualization and analysis of data. Both parts use rather different types of models and inference methods. In both cases, however, the models show inherent invariances, which need to be coped with during the optimization procedures. The first part addresses a fundamental problem in machine learning, namely, the choice of a distance function to describe the similarity of two data points. Often, implicit choices are made, e.g., a spatial scale is chosen to compare images, or features are weighted in a certain way. Unfortunately, different distance functions can yield fundamentally different results since they influence the data structure. Here, a method called continuous multi-dimensional scaling (cMDS) is proposed, which allows to visualize the changes in the data structure in a simple and efficient way as the distance function varies. The algorithm is a variant of dynamical MDS and is based on the Concave-Convex Procedure (CCCP). To address the challenges of MDS which arise due to its invariance to translation and rotation, cMDS uses a smoothing penalty. The algorithm is published as an R package. This work also presents interactive web applications which demonstrate the key features of cMDS. The method is applied to several data sets to show that cMDS can deal with numerous types of hyperparameters and readily reveals important insights and dynamics. The second part of the thesis focusses on modelling and visualizing network data. Network data consists of nodes (e.g., people) and egdes which indicate a relationship (e.g., friendship) between nodes. This work is based on latent space models (LSM), which provide a generative model of network data: Nodes are placed in an auxiliary, low dimensional space, i.e., the latent space. Then, the distance between two nodes is used as a predictor for an edge, such that nodes far apart are unlikely to be linked. Latent space models are usually estimated with MCMC, which is limited with regards to the size of the network, and Variational Bayes, which yields faster but poorer approximations. This work establishes that LSMs can instead be estimated with expectation propagation (EP). Necessary changes to the algorithm and the optimization procedures are shown and the implications of pairwise likelihood sites are thorougly discussed. Comparing EP to other methods of estimation for LSMs (MCMC and Variational Bayes), using a real data set, shows that EP and MCMC yield equivalent results. Thus, it is suggested that EP is the preferable method to estimate latent space models, due to the quality of results, the competitive run time and the potential to use prior knowledge. The results achieved with EP in this work are particularly remarkable in light of the invariances that are inherent to these distance-based models.
Diese Dissertation besteht aus zwei Teilen, die niedrig-dimensionale Repräsentationen zur Visualisierung und Analyse von Daten nutzen. Beide Teile verwenden sehr verschiedene Arten von Modellen und Inferenzmethoden. In beiden Fällen allerdings zeigen die genutzten Modelle Invarianzen, mit welchen während der Optimierung umgegangen werden muss. Der erste Teil behandelt ein fundamentales Problem im Maschinellen Lernen, das darin besteht, eine Distanzfunktion auszuwählen, die die Ähnlichkeit zweier Datenpunkte beschreibt. Oft werden dabei implizite Entscheidungen getroffen: Eine räumliche Skala wird gewählt, um Bilder miteinander zu vergleichen, oder Merkmale werden auf bestimmte Art und Weise gewichtet. Das Problem ist, dass verschiedene Distanzfunktionen zu sehr unterschiedlichen Ergebnissen führen können, da sie maßgeblich die Datenstruktur beeinflussen. Hier wird eine Methode, continuous multi-dimensional scaling (cMDS), vorgestellt, mit der man die Datenstruktur auf einfache und effiziente Art und Weise in Abhängigkeit einer Distanzfunktion darstellen kann. Der Algorithmus ist eine Variante von dynamischem MDS und basiert auf der Concave-Convex Procedure (CCCP). Um die Probleme zu lösen, die durch die Invarianzen von MDS bezüglich Translation und Rotation entstehen, nutzt cMDS eine glättende Regularisierung. Der Algorithmus wurde als R Paket veröffentlicht. In dieser Arbeit werden außerdem noch interaktive Webapplikationen vorgestellt, welche die wichtigsten Funktionen von cMDS demonstrieren. Die Methode wird auf mehrere Datensätze angewandt, um zu zeigen, dass cMDS mit verschiedensten Arten von Hyperparametern umgehen kann und schnell wichtige Erkenntnisse und Einblicke in die Dynamik zulässt. Der zweite Teil der Arbeit beschäftigt sich mit der Modellierung und Visualisierung von Netzwerkdaten. Diese Art von Daten besteht aus Knoten (z.B. Menschen) und Kanten, die eine Beziehung (z.B. Freundschaft) zwischen den Knoten beschreiben. Diese Arbeit basiert auf den latent space Modellen, welche eine generative Erklärung für die Struktur von Netzwerkdaten liefern. In diesen Modellen wird von einem niedrig-dimensionalen Hilfsraum, dem latent space, ausgegangen, in dem die Knoten des Netzwerks platziert werden. Die Distanz zwischen Knoten im latenten Raum wird dann als Prädiktor für Verbindungen zwischen den Knoten genutzt. Knoten, die weit voneinander entfernt sind, haben eher keine Relation und somit keine Verbindung zueinander. Die latent space Modelle können mit MCMC und Variational Bayes abgeschätzt werden. MCMC ist allerdings limitiert in Bezug auf die Größe des Netzwerks, die noch bearbeitet werden kann, während Variational Bayes schnellere, aber ungenauere Abschätzungen liefert. In dieser Arbeit wird gezeigt, dass latent space Modelle stattdessen mit expectation propagation (EP) abgeschätzt werden können. Notwendige Änderungen am Algorithmus und den Optimierungsschritten werden erarbeitet und die Implikationen der paarweisen Likelihood Funktionen werden diskutiert. Ein Vergleich von EP zu anderen Inferenzmethoden für LSMs (MCMC und Variational Bayes) zeigt, dass EP und MCMC für echte Daten äquivalente Ergebnisse liefern. Somit wird gezeigt, dass EP die bevorzugte Methode zur Inferenz von latent space Modellen ist, wegen der Qualität der Ergebnisse, der kurzen Laufzeit und der Möglichkeit, Vorwissen einfließen zu lassen. Die Ergebnisse, die hier mit EP erzielt werden sind wegen der Invarianzen, die inhärent Teil dieser distanzbasierten Modelle sind, besonders bemerkenswert.
URI: https://depositonce.tu-berlin.de//handle/11303/8695
http://dx.doi.org/10.14279/depositonce-7824
Exam Date: 30-May-2018
Issue Date: 2018
Date Available: 13-Dec-2018
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): visualization
dimensionality reduction
machine learning
network modelling
expectation propagation
Visualisierung
Dimensionsreduktion
maschinelles Lernen
Netzwerk-Modelle
Expectation-Propagation
Sponsor/Funder: DFG, GRK 1589/1, Sensory Computation in Neural Systems
License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:FG Modellierung kognitiver Prozesse » Publications

Files in This Item:
File Description SizeFormat 
gruenhage_gina.pdf9.34 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons