[en] 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.

[es] 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.