Active and interactive learning strategies for error-tolerant graph matching

Identifier:  TDX:2406

Handle: https://hdl.handle.net/20.500.11797/TDX2406

Authors:  Cortés Llosa, Xavier

Abstract:
Graphs are data types that can store structural information of objects and are commonly used to represent patterns that because of its nature require this peculiarity, as images, chemical or biological structures, networks, biometric patterns... For more than 30 years, researchers have been focused on how to represent objects through graphs and how to compute the distance between them. The definition of an adequate model for measure the dissimilarity between these representations is a key issue in pattern recognition. This is the Error-Tolerant Graph Matching problem. Graph Edit Distance is a particular approach to the Error-Tolerant Graph Matching problem by means of computing the minimum amount of distortion required to transform one graph into another. The main aim of this thesis is to propose a new model to automatically learn the parameters for Graph Edit Distance and to define different active learning strategies adding interactivity to the problem. Moreover, this thesis explores the definition of different metrics to estimate the dissimilarity between local substructures of two nodes and presents a new model based on metric-trees of Graph-Class Prototypes to store large collections of graphs. Finally, it is proposed to bring the interactivity to a different domain, the problem of matching the points of two images in order to improve the accuracy calculating the relative position between different robots of a fleet working cooperatively.