Resumen de Structural similarity: applications to object recognition and clustering
En el desarrollo de esta tesis doctoral, nos centramos en grafos y redes como objetos de estudio, tanto matemática como computacionalmente. Structural Pattern Recognition engloba el desarrollo de representaciones y algoritmos que hacen más tratables algunos problemas estructurales, o que pueden ser representados en términos estructurales (graph matching, graph embedding, graph compression, kernels, graph learning, etc...). En la actualidad, nos encontramos con la existencia de grandes cantidades de información relacionada que debe ser tratada efectiva y eficientemente. Sin embargo, los algoritmos y teoremas propuestos están sujetos a restricciones combinatoriales. Por ello, se han desarrollado paralelamente otras áreas como Spectral Graph Theory y Extremal Graph Theory que pretenden realizar aproximaciones de estos problemas.
Por lo tanto, la principal motivación en los desarrollos incluidos en esta tesis doctoral es la necesidad de avanzar en el procesamiento de datos relacionales de diferentes formas, que son unificadas bajo el concepto de Similitud Estructural.
La Similitud Estructural puede estudiarse tanto a nivel local (nodos) como global (grafos), donde la similitud local se refiere a medir el grado de parecido entre cada par nodos mediante una métrica, o función de similitud. Commute Times (o resistencias efectivas reescaladas) son similitudes estructurales realmente interesantes que sirven, entre otras cosas, para embeber un grafo en un vector donde las distancias topológicas se mantienen (por ejemplo, se usan en triangulaciones de Delaunay). Además, también se pueden usar en medidas de similitud global.
Por otra parte, las técnicas de Graph Matching dependen de funciones de optimización de similitudes globales, siendo las versiones de m mejores soluciones (m-best GM) el estado del arte actual. En este sentido, es interesante determinar la mejor estrategia para abarcar el enorme espacio de búsqueda de soluciones.
Ranking es un tipo de problema de similitud entre nodos que también es de gran interés, donde los métodos basados en la matriz Laplaciana explotan la estructura global del grafo a partir de sus nodos. Sin embargo, los grafos del mundo real suelen ser muy ruidosos. Por ello, es necesario investigar métodos para filtrar el ruido estructural para mejorar el proceso de difusión de cara a obtener un ranking óptimo. Esta problemática de ruido estructural también la tienen los problemas basados en clustering, donde la estimación del Commute Times no es posible en datos de gran tamaño (donde el gap espectral es demasiado grande debido al ruido). Por ello, se necesita una estrategia para densificar el grafo, minimizando el gap espectral, que permita usarse en diversas aplicaciones como compresión de datos usando Extremal Graph Theory. Por último, destacar que la mejora del Commute Times es importante de cara a métodos de Esparsificación.
En esta tesis doctoral hemos contribuido con diferentes aportaciones referentes a medidas de Similitud Estructural, siendo motivadas y justificadas mediante un gran conjunto de experimentos las hipótesis planteadas, siendo las principales conclusiones expuestas a continuación:
1. Se ha desarrollado una arquitectura llamada net4Lap para ranking y re-ranking basado en regularización laplaciana con embeddings neuronales, (a) procesando un grafo kNN de entrada mediante embeddings neuronales, donde SGD infiere una función a partir de características obtenidas a partir de diferentes caminos aleatorios (RW, PARW, MERW y node2vec). En los experimentos comprobamos que la elección del método de caminos aleatorios no es crítica siempre que tenga implementadas probabilidades de retorno (node2vec funciona, en general, mejor que el resto, mientras que MERW pro- duce peores resultados al no tener una política de retorno). Además, se ob- serva que el embedding neuronal no mejora por si solo el estado del arte, sino que tiene que usarse como un método de preprocesado de grafos para ranking.
(b) Con el grafo contextualizado, se realiza un ranking con regularización laplaciana, formulado como un problema de optimización que minimiza la pérdida de armonicidad, (c) donde se introduce una medida de centralidad global (Centralidad de Katz) para modular el proceso de difusión, y se compara con otra medida de centralidad (Centralidad basada en grados). En los experimentos, se com- paran las dos centralidades con diferentes configuraciones de la arquitectura (con y sin embedding neuronal, ranking y re-ranking), obteniendo que la centralidad de Katz mejora la eficiencia en ranking pero, sobre todo, mejora considerablemente al estado del arte en re-ranking, al proporcionar un grafo de entrada acondicionado localmente isotrópico y contextualizado obtenido por ranking. Nuestra arquitectura net4Lap con Katz llega a mejorar al estado del arte incluso un 14%.
2. Se ha propuesto una nueva medida de similitud entre grafos: información mutua entre grafos, donde a) se ha definido un modelo basado en un canal de información estructural, con codificadores basados en embeddings y decodificadores basados en embeddings inversos.
El canal está caracterizado por el alineamiento entrópico de manifolds, usando una transformación global no rígida, que es evaluada con otras transformaciones (rígidas y afines). Los experimentos indican que, en este caso, la transformación rígida da mejores resultados.
Para medir la entropía entre el embedding de entrada y el distorsionado (o transformado), se estima la información mutua multidimensionalmente a partir de la combinación de cópulas (empírica y arquímedea) y estimadores de entropía de Rényi. Los resultados muestran que las cópulas arquímedeas son ligeramente inferiores que las empíricas en la misma dimensión y mejores en dimensiones mayores, aunque la gran diferencia es la complejidad (O(nlogn), frente a O(n2) en empírica), por lo que es mucho más útil usarlas en las situaciones donde hay restricciones de tiempo (como aplicaciones en tiempo real), que reducir la dimensionalidad de las cópulas empíricas. Además, el uso de las cópulas producen grandes mejoras en comparación con SNESV y funciones de asignación cuadrática con PATH.
Finalmente, comparando nuestra medida de similitud con regularización rígida respecto al estado del arte, obtenemos una mejora muy significativa.
3. Se ha realizado una caracterización del espacio de búsqueda de soluciones en problemas de m-best graph matching, transformando un problema MAP a uno para encontrar las m mejores soluciones, combinando estrategias de aproximación y marginalización. Para ello, se han propuesto: (a) Cuatro estrategias para seleccionar la siguiente variable a restringir, de cara a evaluar la siguiente mejor solución (MF, TC, DP y MDP), para demostrar que hay mejores heurísticas que el criterio aleatorio del estado del arte (BP). Los resultados corroboran nuestras hipótesis: Todas nuestras estrategias superan el estado del arte en eficacia, siendo DP la que mejor resultado da (desde un 1% con m=5 hasta un 2% en m=10), sobre todo cuando aumenta el ruido (outliers o valores atípicos).
Además, los experimentos realizados sobre matchings difíciles indican que la mejora alcanza hasta un 4.5%.
Respecto al rendimiento, todas nuestras heurísticas son más rápidas, incluso un 5% de media respecto a BP.
En el análisis de espacio de búsqueda, BP, MF y TC son más sensibles a los errores, mientras que DP y MDP logran un equilibrio entre búsqueda en anchura (diversidad) y profundidad (cuando encuentra un subespacio de soluciones prometedor), que les hace recuperarse mejor ante los errores. Experimentalmente, se comprueba que DP es la heurística más robusta.
Respecto a la rapidez de encontrar la solución óptima, todas nuestras estrategias son mejores que el estado del arte, donde se ha comprobado que DP (la mejor heurística) necesita tan solo en torno a un 37% de soluciones del total usadas en BP m=5 para mejorar su eficacia. En sentido inverso, BP necesita un 45% para superar a DP. Por lo tanto, DP es la mejor heurística respecto a su eficiencia.
4. Se ha desarrollado un densificador de grafos, Dirichlet Densifier, que nos permite acondicionar el grafo de entrada, preservando sus propiedades topológicas, para realizar diversas tareas, aunque en esta tesis nos centramos en la estimación eficiente de medidas de similitud entre nodos, como Commute Times, donde se han realizado diversos experimentos que corroboran las hipótesis planteadas.
(a) Desarrollo de un nuevo densificador llamado Dirichlet Densifier, donde: Primero se ha diseñado un filtro de ruido estructural basado en caminos aleatorios, llamado Return Random Walk, que sirve de proceso de difusión estructural que elimina en gran medida el ruido entre clases. En los experimentos se comprueba que tiene un efecto de suavizado del grafo, eliminando en gran medida el ruido entre clases (en NIST, COIL y LOGO, el ruido es menor del 15% del total de aristas en comparación con otras técnicas del estado del arte). Además, se observa que acondiciona muy bien el grafo de cara al proceso de densificación propuesto. Con el grafo filtrado, se alimenta un proceso de densificación basado en problemas de Dirichlet, siendo un método escalable, robusto, efectivo y totalmente no supervisado, en contraste con densificadores basados en SDP, donde se ha comprobado experimentalmente que no funciona correctamente con grafos de gran tamaño y con ruido estructural. Este proceso está controlado por dos umbrales (que controlan la complejidad y el ruido) y el número de vecinos k, cuyos límites se han acotado experimentalmente para los conjuntos de datos usados (NIST, COIL, LOGO y YALE): k=15 vecinos más cercanos en el grafo kNN de entrada nos permite capturar la estructura del grafo sin introducir excesivo ruido, el umbral δ1=35% del tamaño del grafo de línea nos permite quedarnos con las aristas mas relevantes sin meter demasiado ruido, y el umbral δ2=5% que nos permite inferir inteligentemente un gran número de aristas reduciendo el nivel de densificación. Con esta configuración, en nuestros experimentos hemos obtenido grandes mejoras de eficacia (hasta un 5%) respecto a kNN. iii. Sirve para estimar CT en conjuntos de datos de medio y gran tamaño, minimizando la constante de Cheeger y el gap espectral a valores cercanos a cero, a diferencia de los obtenidos con técnicas del estado del arte, como Anchor Graphs.
(b) Se han formulado las cotas universales de nuestro densificador, donde se reduce a la mitad en la cota inferior del CT y a un cuarto la cota superior respecto a los asociados con los grafos no densificados. Por ello, con- seguimos un buen rendimiento debido a la posibilidad de distinguir mejor entre las aristas dentro de las clases y el ruido.
(c) Además, se ha desarrollado una versión semi-supervisada del densificador, que mejora en eficiencia al método no supervisado (hasta un 10%), incluso con una reducción de la complejidad (O(αn4), donde puede ser bas- tante inferior al obtenido en el método no supervisado (α = 0.35) en los conjuntos de datos estudiados), y nos ha permitido comprobar que el densificador va más allá que añadir aristas o aumentar el volumen del grafo, sino que es posible obtener mejores resultados con un grafo menos denso, puesto que el principio de Dirichlet nos permite una difusión inteligente dentro del grafo. Supera en eficacia al estado del arte y mantiene el gap espectral a valores cercanos a cero.
(d) Se ha aplicado el método de densificación no supervisada en el preprocesado de datos de gran tamaño para acondicionarlos de cara a tareas de compresión y descompresión con Szemerédi regularity lemma, i. encontrando, con experimentos sintéticos y reales, que el régimen ideal de densidad donde este método de compresión es útil y robusto, serían grafos globalmente densos con cierta tolerancia a clases esparsificadas/dispersas. La densificación es útil cuando el grafo es demasiado disperso y, en general, Regularity Lemma puede hacer el papel de un filtro de ruido estructural (válido para densificar en grandes grafos).
ii. Se facilita tratabilidad de datos de gran tamaño mediante compresión y descompresión de grandes grafos (se han evaluado grafos de 10000 nodos), resultando una mejor recomposición de las particiones cuando se usa nuestro densificador.
(e) También se ha aplicado el método de densificación no supervisada en el análisis de las interacciones en las redes formadas por las diferentes regiones del cerebro para detectar precozmente la enfermedad del Alzheimer, donde i. se ha seguido un proceso para acondicionar el grafo dirigido y para representar la conectividad entre regiones del cerebro mediante net4Lap para contextualizar dicho grafo y haciendo uso de los caminos aleatorios de RRW para filtrar el ruido entre regiones y destacar las conexiones más importantes entre regiones. Los resultados indican que el pro- ceso seguido ayuda a distinguir mejor pacientes sanos y pacientes en una fase inicial de la enfermedad, donde el uso de RRW incrementa un 9% la eficacia en la clasificación entre estos pacientes (72.94% frente a 63.64%).
ii. Para la detección de anomalías, se han buscado asimetrías entre las regiones izquierdas y derechas de una misma área respecto a las distribuciones de grados (entrada y salida de grados en cada región). Con ello, se han aislado seis partes de regiones que nos sirven de indicador de la aparición temprana de la enfermedad, que sigue la misma línea de los resultados de estudios clínicos sobre esta enfermedad.
5. Se ha propuesto una forma de simplificar las representaciones de figuras mediante el uso de (a) un método de Graph Sparsification basado en resistencias efectivas, donde la probabilidad de que una arista aparezca en un spanning tree de un grafo es igual a la resistencia efectiva, y (b) el desarrollo de una técnica de resistance sparsification mediante muestreo donde se retienen las aristas que son clave en la preservación de las propiedades topológicas de la figura de entrada, y comparando experimentalmente diferentes representaciones 1-skeleton de triangulaciones y alpha shapes, se observa que se necesitan diferentes valores α para capturar los detalles a baja escala y de la forma global.
(c) Además, conforme aumenta la tolerancia ε, se reduce el número de aristas hasta degradarse, determinando experimentalmente y corroborando las cotas estudiadas para los parámetros α y ε.
