Introducción

La inquietud del hombre por comprender el entorno en el que vive le ha permitido avanzar en su forma de enfrentarse a las incógnitas y problemas que el día a día le plantea. Esta necesidad primaria de comprender el funcionamiento de los fenómenos que le rodean le lleva a generar procedimientos de descubrimiento y explicación cada vez más eficientes sobre el funcionamiento de lo que puede percibir a través de los sentidos. Por ejemplo, la enunciación y comprensión de leyes universales de la física le permite enunciar hipótesis sobre las condiciones pasadas de los fenómenos, razonar sobre su relación con el presente que percibe, y predecir la evolución futura de los mismos, adelantándose en el proceso de toma de decisiones de eventos que todavía no han ocurrido. Sin poseer un sistema perfecto de inferencia, sin duda es la capacidad que más le diferencia del resto de seres vivos con los que comparte su existencia.

Sin embargo, de forma reiterada ha de rehacer y ampliar los mecanismos de descubrimiento que utiliza, añadiendo nuevas herramientas que le permitan seguir ampliando las fronteras del conocimiento y modificado aquellas que muestran debilidades. Entre las herramientas diseñadas en el pasado, el Método Científico, y los paradigmas científicos que se establecen por su aplicación, se erigen como grandes referentes, ya que se caracterizan por exigir una justificación racional de los principios que se quieren probar y por rechazar las afirmaciones absolutas a priori asumiendo que cualquiera de ellas es susceptible de ser refutada. Los paradigmas científicos más antiguos son el empírico (validar una hipótesis a través de repetición experimental) y el teórico (probar algo a través de derivaciones lógicas). Posteriormente, madura ya la era de la computación, apareció en escena un nuevo paradigma científico que se ha venido a llamar paradigma computacional (validar algo a través de simulaciones computacionales que complementan las observaciones experimentales). En los últimos años, y como consecuencia también del uso de sistemas informáticos para el tratamiento masivo de datos, ha surgido un nuevo paradigma de inferencia basado en datos, que está dando lugar a una disciplina emergente denominada Ciencia de los Datos que, a pesar de no ser nueva, ha sido en las últimas décadas cuando se ha realizado un esfuerzo por dotarla de fundamentos teóricos sólidos e implementaciones viables, lo que la ha situado en el punto de mira de muchos intereses económicos, sociales y de investigación.

De entre los fenómenos que se pueden abordar con este tipo de paradigmas, son especialmente interesantes aquellos en los que tanto el análisis de los elementos como de las interacciones que se dan entre ellos son importantes, más aún cuando pueden existir diferentes tipos de interacciones o cuando hemos de considerar las propiedades internas que las caracterizan. Las estructuras de datos que permiten expresar este tipo de fenómenos, y que son necesarias para poder manipular después la información almacenada de ellos, deben estar orientadas por tanto a la descripción de sus elementos, a la de las relaciones existentes entre éstos, o presentar una orientación híbrida que permite un nivel de expresividad similar tanto para unos como para otras.

Los métodos más extendidos en Ciencia de los Datos están orientados a trabajar con estructuras que expresan de manera natural las propiedades de los elementos, pero normalmente poseen ciertas limitaciones para expresar sus interacciones de forma natural. Por ejemplo, los vectores o tablas, con los que habitualmente trabajan los algoritmos de aprendizaje automático más comunes, son muy adecuados para describir elementos, pero no así para expresar sus relaciones complejas. Paralelamente, las bases de datos clásicas proporcionan mecanismos para expresar las relaciones complejas entre los elementos, pero las tareas de consulta y modificación disponibles no están optimizadas para trabajar en base a características derivadas de estas relaciones.

La estructura matemática que parece expresar con mayor fidelidad las interacciones entre elementos de un sistema son los grafos, y recientemente han aparecido extensiones de éstos, como los grafos con propiedades, que permiten expresar de manera natural y simultánea todos los componentes que conforman un sistema, sus elementos y las relaciones entre éstos. Basándose en esta estructura conceptual fueron desarrolladas las bases de datos en grafo, que buscan almacenar la información de tal manera que tanto el proceso de almacenamiento como el posterior proceso de consulta sean eficientes cuando se realiza en base a la estructura de grafo que tienen los datos almacenados.

Grafos con Propiedades

Como hemos comentado anteriormente, los objetos matemáticos usados habitualmente para modelar las propiedades de los elementos de un sistema suelen poseer cierta linealidad en su estructura y cuentan con buenas implementaciones computacionales (vectores, registros, tablas,...). Para aquellos casos en los que ha sido necesario disponer de herramientas de estructuración menos lineales se han creado implementaciones ad-hoc que han cubierto los requerimientos deseados (XML, RDF,...). En busca de un objeto matemático común que modele este tipo de estructuras de datos, el grafo con propiedades se destaca como un concepto que proporciona un buen equilibrio entre expresar correctamente la descripción de los elementos del sistema y la de sus relaciones. Dicha estructura, que no ha sido definida formalmente hasta hace pocos años, no posee todavía una teoría robusta que lo soporte, a pesar de que, como veremos, una correcta definición puede hacerla contener otras muchas estructuras de datos habituales.

Históricamente, los gafos uni-relacionales (aquellos en los que todas las relaciones son del mismo tipo) constituyeron las bases de la teoría matemática clásica de grafos. Los grafos multi-relacionales (aquellos en los que diferentes relaciones pueden poseer diferentes tipos) se acercan más a la descripción intuitiva de un sistema, aunque siguen mostrando algunas carencias obvias. Son los grafos con propiedades los que permiten que cada elemento (nodo o relación) posea un número indeterminado de propiedades heterogéneas asociadas. Con estas premisas, esta estructura es capaz de contener prácticamente cualquier otra estructura relacional, de tal manera que se puede adaptar al nivel de detalle del sistema que refleja en función de las necesidades de análisis posterior.

Por ello, en este trabajo haremos uso de este tipo de objetos matemáticos como estructura base, tanto en la fase previa de modelado y almacenamiento de la información como en la fase posterior de análisis e inferencia sobre ella.

Aprendizaje Automático en grafos

Una vez seleccionada una estructura matemática adecuada para describir los sistemas que nos interesan, necesitamos herramientas que nos permitan realizar inferencias de manera automática sobre éstos, normalmente con el objetivo de predecir su evolución futura o de manipularlos de manera efectiva. Tradicionalmente, los diversos paradigmas científicos han hecho uso de herramientas basadas en fundamentos lógicos, geométricos, algebraicos, analíticos, etc., y más recientemente hacen un uso extensivo de herramientas algorítmicas.

De igual forma a como, en el método científico, la enunciación de hipótesis tras la observación de fenómenos permite extraer leyes generales a partir de la experiencia, el uso de técnicas computacionales puede ser útil para obtener leyes generales a partir de ejemplos analizados con herramientas algorítmicas. Este proceso se puede hacer a diversos niveles. Podemos hacer uso de las herramientas computacionales como medio de ayuda al proceso de inferencia del investigador, o podemos llevarlo al extremo e intentar que sea el propio algoritmo el que realice la inferencia completa y enuncie leyes de manera automática. En este último caso decimos que estamos tratando con un proceso de aprendizaje automático (del que hablaremos más extensamente en el capítulo 2 de Fundamentos).

En su origen, la mayoría de estas técnicas han sido ideadas para extraer patrones globales en base a una serie de ejemplos aislados, que son descritos a través de un conjunto de propiedades prefijadas, y normalmente expresados en forma de registros o tablas. Esta forma de estructurar los ejemplos coincide con el primer tipo de estructuras presentadas en la sección anterior, aquellas que permiten expresar con facilidad las propiedades de los elementos que conforman un sistema, pero no sus relaciones. Este hecho limita la capacidad de aprendizaje, ya que no considera explícitamente una parte importante del mismo. Si en el fenómeno bajo estudio las interacciones parecen ser determinantes en la comprensión del mismo, parece natural seleccionar una estructura matemática que las refleje correctamente. Sin embargo, los esfuerzos en el desarrollo del aprendizaje automático parecen haber dejado en un segundo plano este tipo de consideraciones.

Diseñar algoritmos que aprendan a partir de datos estructurados en forma de grafos con propiedades permite aprender de manera más natural tanto en base a las propiedades de los elementos de un sistema como a las relaciones existentes entre ellos. Además, aunque siempre se sacrifica información del fenómeno real, la flexibilidad del concepto de grafo permite una adaptación más fiel a la realidad, sin necesidad de realizar transformaciones adicionales que nos alejen en exceso de ella.

Si permitimos que los algoritmos de aprendizaje automático trabajen con grafos como estructura natural de la que aprender, éstos podrán manipular las relaciones de manera explícita de igual manera que lo hacen con las propiedades de los elementos. A este tipo de aprendizaje se le ha venido a llamar aprendizaje relacional (multi-relacional en caso de que existan varios tipos de relaciones entre los datos) y por suerte, y a pesar de que no ha representado un foco de atención, ha obtenido grandes avances y ha sido un área de investigación activo durante muchos años. En la literatura es habitual encontrar el aprendizaje relacional clasificado en tres grandes bloques: (1) Statistical Relational Learning (SRL), dentro del cual se encontrarían desarrollos como las redes lógicas de Markov, que utiliza una codificación de grafos multi-relacionales haciendo uso de modelos probabilísticos; (2) Path Ranking Methods, que de manera explícita exploran el espacio de relaciones a través de caminos aleatorios; y (3) Modelos Basados en Inmersiones, que obtienen una representación vectorial del grafo a través de factorización de matrices/tensores, clusterización bayesiana o redes neuronales. Además de estos tres bloques, aunque menos estudiados, podemos incluir los algoritmos que realizan descubrimiento de patrones relacionales refinando una hipótesis a través de una serie de pasos, en este último bloque podríamos incluir algoritmos como Top-Down Induction of Logical Decision Trees, Multi-Relational Decision Tree Learning o Graph Based Induction Decision Tree, que detallaremos en el capítulo 4 de esta memoria. Aunque, como se puede observar, se han logrado avances en el aprendizaje relacional haciendo uso de árboles de decisión, redes neuronales y modelos probabilísticos, aún queda mucho camino por recorrer. Por ejemplo, hay otros algoritmos que, aún habiendo demostrado gran potencial en el aprendizaje no relacional, como es el caso de Random Forest, todavía no han sido explotados desde esta perspectiva.

Habitualmente, los modelos de aprendizaje automático se clasifican, según diversos criterios en Supervisado frente a No Supervisado (por el tipo de aprendizaje llevado a cabo), Regesión, Calsificación o Ranking (por el tipo de salida esperada), etc. Además, y respecto a la interpretabilidad del modelo resultante por parte de un humano, podemos clasificar los modelos en aquellos que son capaces de ofrecer una explicación que acompaña y justifica el resultado que arrojan (modelos de caja blanca) y aquellos que sacrifican dicha justificación en pos de una mejor eficiencia (modelos de caja negra).

Con respecto a los modelos de caja blanca, uno de los más representativos es el árbol de decisión, que proporciona como resultado una sucesión de tests que explican la predicción de cada uno de los ejemplos. Con respecto a los de caja negra, uno de los modelos más representativos son las redes neuronales que, a pesar de que han demostrado ser muy eficientes en tareas de clasificación y regresión, presentan grandes dificultades a la hora de ofrecer una justificación interpretable por un humano.

Objetivos de la Tesis

Ante el reducido abanico de metodologías para llevar a cabo tareas de aprendizaje automático relacional, el objetivo principal de esta investigación ha sido realizar un análisis de los métodos existentes, modificando u optimizando en la medida de lo posible algunos de ellos, y aportar nuevos métodos que proporcionen nuevas vías para abordar esta difícil tarea. Para ello, y sin nombrar objetivos relacionados con revisiones bibliográficas ni comparativas entre modelos e implementaciones, se plantean una serie de objetivos concretos a ser cubiertos:

1. Definir estructuras flexibles y potentes que permitan modelar fenómenos en base a los elementos que los componen y a las relaciones establecidas entre éstos. Dichas estructuras deben poder expresar de manera natural propiedades complejas (valores continuos o categóricos, vectores, matrices, diccionarios, grafos,...) de los elementos, así como relaciones heterogéneas entre éstos que a su vez puedan poseer el mismo nivel de propiedades complejas. Además, dichas estructuras deben permitir modelar fenómenos en los que las relaciones entre los elementos no siempre se dan de forma binaria (intervienen únicamente dos elementos), sino que puedan intervenir un número cualquiera de ellos.
2. Definir herramientas para construir, manipular y medir dichas estructuras. Por muy potente y flexible que sea una estructura, será de poca utilidad si no se poseen las herramientas adecuadas para manipularla y estudiarla. Estas herramientas deben ser eficientes en su implementación y cubrir labores de construcción y consulta.
3. Desarrollar nuevos algoritmos de aprendizaje automático relacional de caja negra. En aquellas tareas en las que nuestro objetivo no es obtener modelos explicativos, podremos permitirnos utilizar modelos de caja negra, sacrificando la interpretabilidad a favor de una mayor eficiencia computacional.
4. Desarrollar nuevos algoritmos de aprendizaje automático relacional de caja blanca. Cuando estamos interesados en una explicación acerca del funcionamiento de los sistemas que se analizan, buscaremos modelos de aprendizaje automático de caja blanca.
5. Mejorar las herramientas de consulta, análisis y reparación para bases de datos. Algunas de las consultas a larga distancia en bases de datos presentan un coste computacional demasiado alto, lo que impide realizar análisis adecuados en algunos sistemas de información. Además, las bases de datos en grafo carecen de métodos que permitan normalizar o reparar los datos de manera automática o bajo la supervisión de un humano. Es interesante aproximarse al desarrollo de herramientas que lleven a cabo este tipo de tareas aumentando la eficiencia y ofreciendo una nueva capa de consulta y normalización que permita curar los datos para un almacenamiento y una recuperación más óptimos.

Todos los objetivos marcados deben ser desarrollados sobre una base formal sólida, basada normalmente en Teoría de la Información, Teoría del Aprendizaje, Teoría de Redes Neuronales Artificiales o Teoría de Grafos. Esta base debe permitir que los resultados obtenidos sean suficientemente formales como para que los aportes que se realicen puedan ser fácilmente evaluados. También se busca que los modelos abstractos desarrollados sean fácilmente implementables sobre máquinas reales para poder verificar experimentalmente su funcionamiento y poder ofrecer a la comunidad científica soluciones útiles en un corto espacio de tiempo.

Aportaciones realizadas

El trabajo realizado ha supuesto una incursión en la formalización de grafos y el aprendizaje automático relacional y, como se refleja en esta memoria, ha permitido unificar y condensar diferentes perspectivas en dichas áreas. Además, ha permitido desarrollar nuevas técnicas para llevar a cabo este tipo de tareas haciendo uso de formalizaciones más generales y que, por tanto, permiten una mejor adaptación a diferentes contextos, así como haciendo uso de nuevos métodos de aprendizaje que son capaces de trabajar con grafos con propiedades como estructura básica de la que aprender.

Describimos a continuación las aportaciones concretas que se pueden encontrar en este trabajo:

1. Grafo Generalizado, estructura matemática sencilla que generaliza prácticamente todas las definiciones clásicas de grafo, desde grafo uni-relacional hasta hipergrafo con propiedades. En este trabajo se redefinen conceptos pertenecientes a la teoría de grafos desde esta nueva perspectiva y se aporta una base sólida, sencilla y flexible para soportar sistemas en los que puede resultar esencial tanto la descripción de los elementos como la de las relaciones.
2. Extensión de las medidas, existentes para grafos uni-relacionales, al concepto de grafo generalizado. Debido a que esta estructura generaliza la mayor parte del abanico de definiciones para grafos, esta extensión permite realizar mediciones sobre los diferentes tipos de grafo existentes.
3. Property Query Graph, herramienta de consulta para grafos generalizados que permite evaluar estructuras en base a su contenido y al de los elementos con los que está relacionado. Generaliza lenguajes como Cypher y otras herramientas de consulta como los Grafos de Selección. Los PQG se expresan también a través de un grafo generalizado, permitiendo así trabajar con la misma estructura tanto para la fuente de información como para la consulta.
4. PQG-ID3, algoritmo de aprendizaje automático relacional que permite descubrir patrones en estructuras enriquecidas de datos, y construir árboles de decisión para clasificar subgrafos a partir de un conjunto de ejemplos clasificados. Los patrones relacionales extraídos por este algoritmo se expresan a través de un grafo generalizado, permitiendo así su fácil interpretación por parte de cualquier humano/máquina.
5. Metodología para la inmersión de grafos generalizados en espacios vectoriales, manteniendo la semántica original y permitiendo el descubrimiento de nueva información, recuperación de información faltante, clasificación automática de datos y aportando mejoras en otras tareas como son las consultas a larga distancia.
6. Implementaciones de las diversas herramientas desarrolladas a lo largo del trabajo, ofrecidas como librerías Open Source, y que se detallan en al apéndice de Implementación. 

Además, de los puntos indicados, se han realizado aportes no menos importantes como son: un primer paso hacia una herramienta para la normalización de datos estructurados en forma de grafo a través del análisis de las estructuras vectoriales obtenidas a partir de una inmersión; una primera familia de refinamientos que permiten manipular automáticamente predicados complejos sobre grafos; y otros aportes conceptuales y técnicos de menor envergadura que no han sido nombrados en esta sección.

Estructura de la memoria

A continuación se describe el contenido de esta memoria, describiendo los diversos capítulos de que consta y que pretenden cubrir los objetivos marcados anteriormente.

En el capítulo 2, Fundamentos, se introducen las teorías fundamentales que sirven de eje transversal a todo el trabajo realizado y se presentan las estructuras comunes a los diferentes capítulos de esta memoria. Se presenta un marco para grafos que unifica definiciones como grafo uni-relacional o grafo con propiedades a través del concepto de grafo generalizado, redefiniendo conceptos pertenecientes a la Teoría de Grafos en un marco unificado. Además, se realiza una introducción al área del aprendizaje automático y se presentan, de manera breve, los modelos que serán utilizados a lo largo de la memoria.

En el capítulo 3, Consulta de patrones en grafos con propiedades, se realiza un estudio acerca de la evaluación y extracción de información en estructuras relacionales, presentando una revisión de las tecnologías y fundamentos que han abordado esta tarea. Además, se presentan los Property Query Graphs (PQG), nuestra propuesta para evaluar estructuras inmersas en un grafo con propiedades, y que funcionan como predicados sobre subgrafos, de tal manera que son ideales como base en tareas de descubrimiento. El capítulo concluye mostrando algunos ejemplos concretos de PQG.

Posteriormente, el capítulo 4, Árboles de decisión para grafos con propiedades, plantea el problema de construir automáticamente árboles clasificadores de subgrafos en grafos con propiedades. Se comienza repasando el funcionamiento de los algoritmos de construcción de árboles de decisión, desde aquellos que aprenden árboles clasificadores de objetos (descritos a través de un conjunto de propiedades), hasta aquellos que aprenden a clasificar registros de una base de datos relacional teniendo en cuenta sus relaciones. La parte central del capítulo presenta el algoritmo PQG-ID3, nuestra propuesta para construir árboles de decisión multi-relacionales basada en consultas PQG. Terminamos mostrando una colección de ejemplos de árboles construidos usando esta herramienta y analizando los patrones semánticos resultantes.

A continuación, el capítulo 5, Inmersión semántica de grafos con propiedades, realiza una aproximación diferente al aprendizaje multi-relacional, esta vez haciendo uso de redes neuronales para aprender una codificación vectorial de un grafo con propiedades. Esta codificación permite hacer uso de los métodos de aprendizaje automático habituales diseñados para trabajar de manera natural con objetos descritos vectorialmente. Se realiza un repaso por los métodos de aprendizaje que hacen uso de redes neuronales, y se analizan métodos que han sido utilizados para realizar codificaciones de otros tipos de estructuras. Se presenta una metodología que hace uso de codificadores neuronales para llevar a cabo inmersiones de grafos con propiedades en espacios vectoriales, y se realizan experimentos sobre datos reales para verificar que la proyección obtenida permite capturar propiedades presentes en el grafo original. Además, se demuestra empíricamente que la metodología de inmersión propuesta permite llevar a cabo de manera exitosa tareas habituales de clasificación automática, extracción de información, recuperación de información faltante y consultas a larga distancia.

Por último, en Conclusiones y trabajo futuro presentamos las conclusiones obtenidas del proceso de investigación estructuradas de manera acorde a los diferentes bloques de esta memoria, así como las conclusiones obtenidas globalmente y de manera transversal a todo el trabajo. En este último capítulo también presentamos las líneas de trabajo futuro que se abren con esta investigación y que están relacionadas con la formalización de grafos, el aprendizaje relacional, la consulta de patrones en grafos y procedimientos de descubrimiento en bases de datos.

Trabajos Publicados

• P. Almagro Blanco; F. Sancho Caparrini. Generalized Graph Pattern Matching. arXiv:1708.03734 
• P. Almagro Blanco; F. Sancho Caparrini. Semantic Preserving Embeddings for Generalized Graphs. arXiv:1709.02759 
• P. Almagro Blanco; F. Sancho Caparrini . Induction of Decision Trees based on Generalized Graph Queries.  arXiv:1708.05563