Active and interactive learning strategies for error-tolerant graph matching

Author

Cortés Llosa, Xavier

Director

Serratosa Casenelles, Francesc

Date of defense

2016-07-15

Pages

189 p.



Department/Institute

Universitat Rovira i Virgili. Departament d'Enginyeria Informàtica i Matemàtiques

Abstract

Els grafs, són un tipus de dades que ens permet emmagatzemar la informació estructural d’un objecte conferint-nos la possibilitat de representar patrons que degut a la seva pròpia naturalesa requereixen d’aquesta particularitat, ja siguin imatges, estructures químiques o biològiques, xarxes, patrons biomètrics... Des de fa més de 30 anys, la recerca enfocada a com representar objectes mitjançant grafs i el posterior còmput de la distància entre aquestes representacions ha ocupat el treball de molts investigadors. La definició d’un model adequat per mesurar la dissimilitud entre dues d’aquestes representacions, és una qüestió clau en el camp del reconeixement de patrons. A aquest problema se l’ha anomenat “Error-Tolerant Graph Matching”. La “Graph Edit Distance” és una aproximació particular al problema de “l’Error-Tolerant Graph Matching” a partir del còmput de la mínima distorsió necessària per transformar un graf en un altre. El principal objectiu d’aquesta tesi, és el de proposar un nou model per aprendre automàticament els paràmetres de la “Graph Edit Distance” i definir diferents estratègies actives d’aprenentatge per afegir interactivitat al problema. Aquesta tesi, també explora la definició de diferents mètriques per calcular la dissimilitud entre sub-estructures locals corresponents a dos nodes i presenta un nou model basat en “metric-trees” de “Graph Class Prototypes” per guardar col•leccions de grafs. Finalment, es proposa portar el concepte d’interactivitat a un altre domini, el problema de relacionar els punts entre dues imatges per tal de millorar la precisió en el càlcul de la posició correlativa entre robots pertanyents a una mateixa flota que treballa de forma cooperativa.


Los grafos, son un tipo de datos que nos permite almacenar la información estructural de un objeto confiriéndole la posibilidad de representar patrones que debido a su propia naturaleza requieren de esta particularidad, ya sean imágenes, estructuras químicas o biológicas, redes , patrones biométricos ... Desde hace más de 30 años, la investigación enfocada a cómo representar objetos mediante grafos y el posterior cómputo de la distancia entre estas representaciones ha ocupado el trabajo de muchos investigadores. La definición de un modelo adecuado para medir la disimilitud entre dos de estas representaciones, es una cuestión clave en el campo del reconocimiento de patrones. A este problema se le ha llamado "Error-Tolerant Graph Matching". La "Graph Edit Distance" es una aproximación particular al problema del "Error-Tolerant Graph Matching " a partir del cómputo de la mínima distorsión necesaria para transformar un grafo en otro. El principal objetivo de esta tesis, es el de proponer un nuevo modelo para aprender automáticamente los parámetros de la "Graph Edit Distance" y definir diferentes estrategias activas de aprendizaje para añadir interactividad al problema. Esta tesis, también explora la definición de diferentes métricas para calcular la disimilitud entre sub-estructuras locales correspondientes a dos nodos y presenta un nuevo modelo basado en "metric-trees" de "Graph Class Prototypes" para guardar colecciones de grafos. Finalmente, se propone llevar el concepto de interactividad a otro dominio, el problema de relacionar los puntos entre dos imágenes para mejorar la precisión en el cálculo de la posición correlativa entre robots pertenecientes a una misma flota que trabaja de forma cooperativa.


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.

Keywords

Teoria de grafs; Aprenentatge automàtic; Reconoxeiment de patrons; Teoría de grafos; Aprendizaje automático; Reconocimiento de patrones; Graphs theory; Machine learning; Pattern recognition

Subjects

004 - Computer science and technology. Computing. Data processing; 51 - Mathematics

Knowledge Area

Enginyeria i Arquitectura

Documents

TESI.pdf

8.222Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)