Low-Rank Approximation and Difusion Maps
Author
Dorado Alfaro, SaraEntity
UAM. Departamento de Ingeniería InformáticaDate
2018-09Subjects
Métodos de aprendizaje de variedades; Mapas de difusión; Método de Nyström; InformáticaEsta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
Abstract
La teoría de la reducción de la dimensionalidad es fundamental para muchos problemas de Aprendizaje Automático. Existen multitud de enfoques, pero este trabajo se centrará en los métodos de aprendizaje de variedades. El punto de partida es asumir que los datos viven en una variedad de dimensión menor que la de partida para lograr entender el fenómeno subyacente que los ha generado. Dentro de este campo, es de especial interés, debido a su fuerte base matemática, el algoritmo conocido como Mapas de Difusión, objeto principal de este trabajo.
Primero realizaremos un estudio de los Mapas de Difusión así como de la teoría matemática necesaria para su correcta comprensión, estudiando conceptos como los Grafos de Semejanza y sus Laplacianos y la Distancia de Difusión. El principal inconveniente de los Mapas de Difusión, así como de otros algoritmos espectrales, es que requiere la diagonalización de una matriz cuadrada cuya dimensión es el número de ejemplos. Por lo tanto, su coste computacional es O(N3), donde N se refiere al número de ejemplos. Es por ello que uno de los objetivos de este trabajo es calcular una aproximación de rango bajo para los Mapas de Difusión mediante el método de Nyström. Además, para evaluar la calidad de la aproximación, propondremos una métrica que se basa en el error de reconstrucción de la matriz de difusión. Por otro lado, existe otro problema cuando se quiere dar la proyección de un ejemplo que no está en la muestra inicial utilizada para el cálculo de la transformación. Es necesario rehacer el análisis espectral de la matriz, lo que es especialmente crítico si las aplicaciones tienen restricciones de funcionamiento en tiempo real. En este trabajo también analizaremos dos propuestas para paliar este coste: aprender el mapeo por medio de redes neuronales para regresión (Redes de Difusión), pudiendo así calcular la proyección para un nuevo ejemplo, y calcular una extensión de la transformación para un nuevo punto con el método de Nyström.
A la hora de mostrar los resultados se van a utilizar tres conjuntos de datos, uno de
los cuales será sintético. Para todos ellos, se calculará la transformación a un espacio de menor dimensión por medio de Mapas de Difusión con el objetivo de extender los mismos a ejemplos fuera de muestra y evaluar la aproximación de rango bajo conseguida por el método de Nyström. Además, se calcularán extensiones para patrones fuera de muestra y se compararán los resultados obtenidos, tanto por las Redes de Difusión como por el método de Nyström, de forma visual.
En resumen, en cuanto a la calidad de la aproximación de rango bajo veremos que,
como cabría esperar, incrementar el número de ejemplos en el conjunto de entrenamiento conlleva una reducción del error de reconstrucción de la matriz de difusión. En cuanto al funcionamiento de los métodos para extender el mapeo a ejemplos fuera de muestra, observaremos que tanto el método de Nyström como las Redes de Difusión obtienen resultados visualmente similares, proyectando ejemplos de la misma clase en las mismas regiones del espacio.
Este trabajo da lugar a nuevas líneas de investigación, ya que como trabajo futuro es de especial interés, entre otros, conseguir comparar la calidad de las extensiones para ejemplos fuera de muestra. The theory of dimensionality reduction is fundamental for many problems of Machine
Learning. There are many approaches, but this work will focus on the methods of Manifold
Learning. The starting point is to assume that data live in a manifold of smaller dimension
than the starting one in order to understand the underlying phenomenon that has generated
them. Within this eld, it is of special interest, due to its strong mathematical foundation,
the algorithm known as Di usion Maps, the main object of this work.
First we will study the theory of Di usion Maps, as well as the mathematical theory
necessary for its correct understanding, studying concepts such as Similarity Graphs and
their Laplacians, and the Di usion Distance. The main drawback of Di usion Maps, as
well as other spectral algorithms, is that they require the diagonalization of a square matrix
whose dimension is the number of examples. Therefore, its computational cost is O(N3),
where N refers to the number of examples. Because of that, one of the main objectives
of this work is to compute a low-rank approximation for Di usion Maps using Nystr om's
method. In addition, in order to evaluate the quality of the approach, we will propose a
metric that is based on the reconstruction error of the di usion matrix. On the other hand,
there is another problem when giving the embedding for examples that were not in the
initial sample used to compute the embedding. It is necessary to redo the spectral analysis
of the matrix, which is especially critical if the applications have operating restrictions in
real time. In this work we will also analyze two proposals to allevaite this cost: to learn
the embedding by means of neural networks for regression (Di usion Nets), being able to
compute the embedding for a new example, and to compute an extension of the embedding
with Nystr om's method.
Regarding the results, three datasets will be used, one of which will be synthetic. For all
of them, we will compute the embedding via Di usion Maps with the objective of extending
it to out-of-sample (OOS) examples and to evaluate the low range approximation achieved
by Nystr om's method. In addition, extensions for OOS patterns will be computed via
Di usion Nets and Nystr om's method.
To sum up, regarding the low-rank approximation quality we will see that increasing
the number of examples in the training set entails a reduction in the reconstruction error of
the di usion matrix, as we could expect. Regarding OOS extensions, we will observe that
both, Nystr om's method and Di usion Nets, obtain visually similar results, embedding
examples of the same class in the same regions of space.
This work gives rise to new lines of research, since as future work it is of special interest,
among others, to be able to compare the quality of the extensions for OOS examples.
Files in this item
Google Scholar:Dorado Alfaro, Sara
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0/
Related items
Showing items related by title, author, creator and subject.
-
Analysis of flow cytometry data with domain-adversarial autoencoders
Dorado Alfaro, Sara
2020-09 -
Análisis e implementación de diferentes medidas de similitud para un algoritmo global de selección de variables
Dorado Alfaro, Sara
2017-05