Reduccion de dimensiones

Question 1

Por que es importante estudiar la reduccion de dimensiones?

Answer 1

i) debido a que a medida que va creciendo el tamano de los datos, se requiere cada vez mas poder de computo para poder entrenar algun modelo. Ademas, puede ocurrir que se agregan features que no aportan informacion nueva y por lo tanto no tiene sentido utilizarla para entrenar modelos.
ii) visualizacion de los datos.
iii) cmopresion esde imagenes.
iv) feature engineering.

Question 2

Define ‘maldicion de la dimension’.

Answer 2

Quitar o agregar features conlleva a que un algoritmo funcione mejor o peor y eso dependerá de qué algoritmo se utiliza y de los datos en sı́.

Question 3

Como puede servir la red. de dim. como herramienta de feature eng.?

Answer 3

Los algoritmos de reducción de dimensiones sirven muchas veces para reducir el ruido de un set de datos filtrando los features ruidosos y devolviendo un nuevo set de features con menor cantidad de ruido.

En otros casos es posible reducir las dimensiones de nuestro set de datos a unas pocas columnas y luego agregar estas columnas al set de datos original, este aumento de dimensiones muchas veces agrega features en donde la señal es muy fuerte en relación al ruido y es frecuente que un algoritmo funcione mejor al agregar estos features con respecto a su funcionamiento con el set de datos original.

Question 4

Que tipos de algoritmos existen para manipular la dimensionalidad de los datos?

Answer 4

Existen metodos lineales y no lineales.

Question 5

Mencione algoritmos lineales y no lineales.

Answer 5

Lineales:
SVD y PCA, que son en realidad el mismo algoritmo.

No lineales:
son los denominados algoritmos de Manifold learning.

Question 6

Por que se caracterizan los algoritmos no lineales?

Answer 6

Se destacan porque muchas veces pueden representar muy bien datos no lineales en dos dimensiones.

Un buen algoritmo de Manifold Learning deberı́a mantener a los punto que están cerca en los datos originales como vecinos en su representación bidimensional.

Question 7

Explique SVD.

Answer 7

Sea A una matriz de nxm, se puede demostrar que existen tres matrics U, V y Σ tales que:

A = U ∗ Σ ∗ V T

Donde U es una matriz unitaria en nxn, V es otra matriz unitaria en mxm y Σ es una matriz diagonal en nxm.

A continuación, se muestra un método para obtener dichas matrices:

1. Calcular los autovalores y autovectores de A t A.
2. La matriz Σ se compone de la raiz cuadrada de los autovalores de A t A de forma diagonal y ordenados de forma descendiente.
3. La matriz U se compone con los autovectores normalizados como columnas.
4. La matriz V se puede obtener resolviendo el sistema AV = U Σ sabiendo que V T V es la matriz identidad.

Se ha mencionado anteriormente que U y V son matrices unitarias. Esto quiere decir que U t U = I y que las columnas de U forman una base ortonormal. Esto mismo también vale para V . En definitiva, si a una descomposición en valores singulares la multiplicamos a ambos lados por V se obtiene lo siguiente:

AV = U Σ

Esto quiere decir que si a una base ortogonal le aplico una transformación A entonces el resultado será una segunda base ortogonal donde los vectores que componen dicha base son multiplicados por un escalar.

Question 8

Explique SVD reducida.

Answer 8

Se ha visto que Σ se obtiene a partir de la raı́z cuadrada de la matriz A t A y también se mencionó que estos valores son los que ”estiran” a la base ortogonal compuesta por los vectores U . En determinadas ocasiones, estos valores pueden ser cero y la consecuencia que traen es que anulan ciertas componentes a la hora de realizar el producto matricial y de ahı́ surge el concepto de descomposición en valores singulares reducida. Resumidamente, de los elementos σ 1 , σ 2 …σ n de la matriz Σ se pueden tomar solo aquellos r valores que son positivos de forma tal que σ 1 , σ 2 …σ r son positivos. Teniendo esto en cuenta, serı́a necesario solamente utilizar las primeras r columnas de U y las primeras r columnas de V t . Se puede demostrar que este valor r coincide con el rango de la matriz A.

En resumen, la SVD da a entender que bajo determinados escenarios se podrı́a encontrar una forma más compacta de representar la matriz A y esto da origen a la SVD para el uso de compresión de imágenes.

Question 9

Explique aproximacion de rango k de una matriz.

Answer 9

Se ha visto con la SVD reducida que una matriz A se puede representar de una forma compacta donde utilizábamos aquellos r valores singulares no nulos puesto que eran los únicos que aportaban información y entonces permitı́a también descartar ciertos vectores de U y V .

Dicho de otra forma, se puede pensar que como los valores de la matriz Σ se encuentran ordenados de mayor a menor entonces estos valores representan un grado de importancia de los datos. Esto podrı́a dar a entender que la matriz V es una base en donde los vectores de la base están ordenados por su grado de importancia. En consecuencia, se podrı́a ir más allá de quedarse con los r valores no nulos, es decir, podrı́a ser posible quedarse con los k valores no nulos de Σ (k < r) y aproximar bastante bien a la matriz A. Esto también es conocido como aproximación de rango k.

De la misma forma que se hacı́a con r, en este escenario hay que quedarse con las primeras k columnas de U , las primeras k filas y columnas de Σ y las primeras k columnas de V .

Question 10

Defina energia de una matriz.

Answer 10

Sumatoria de los autovalores.

Question 11

Como se puede definir cual seria un buen k para utilizar la aprox. de rango k de una matriz.

Answer 11

Mediante la energia de la matriz.

Question 12

Como se pueden agregar nuevos datos a una SVD?

Answer 12

Una vez calculada la SVD puede surgir la necesidad de agregar nuevas filas a la matriz A, es decir, agregar nuevos datos en las mismas dimensiones. En consecuencia, es necesario obtener la nueva SVD. La forma trivial de obtenerla es simplemente recalcular la SVD, pero esto puede llegar a ser una tarea muy costosa. La forma no trivial es intentar reutilizar la descomposición que tenemos y realizar ciertos cálculos. Si bien no hay una única forma de recalcular una SVD cuando se agregan datos, la forma más sencilla es pensar cómo se relaciona la matriz U con las demás matrices:

A = U ΣV t

De esta ecuación, se puede despejar U de la siguiente forma:

AV = U ΣV T V = U Σ
AV Σ − 1 = U ΣΣ − 1 = U

Se podrı́a pensar de este despeje que si se agregara una nueva fila a la matriz A entonces se la podrı́a multiplicar por la matriz V y luego por Σ − 1. De esta forma obtenemos su representación dentro de nuestro nuevo espacio, es decir, un nuevo vector que se agregará en la última fila de la matriz U . Si bien este método es sencillo, a medida que se van agregando datos se irá perdiendo la precisión de la SVD calculada originalmente y será necesario recalcular por completo la SVD para recuperar la precisión.

Question 13

Cual es la idea de PCA?

Answer 13

La idea de PCA es encontrar las ”direcciones” principales de los datos, es decir, aquellas direcciones sobre las cuales podemos proyectar los datos reteniendo su variabilidad.

Question 14

Indique los pasos para calcular la PCA.

Answer 14

Una forma sencilla de utilizar este método sobre una matriz A es la siguiente:
1. Para cada elemento de la columna de A i , restarle el promedio de dicha columna. Esto permite centrar los datos en el origen.
2. Para cada elemento de la columna A i , dividirlo por la desviación estándar de dicha columna. Esto permite escalar los datos.
3. Calcular la matriz de covarianza
cov(A) = (1/(n − 1))* At A
4. Calcular los autovalores y autovectores de la matriz de covarianza. Los autovectores conformarán las componentes principales y los autovalores indicarán la importancia de cada componente.

Question 15

SVD vs PCA.

Answer 15

La SVD es en general mas eficiente y numéricamente mas estable que PCA dado que no hace falta construir la matriz de covarianza y es por este motivo que como método genérico lineal para reducción de dimensiones se prefiere siempre usar la SVD.

Question 16

Que problema busca resolver MDS?

Answer 16

El algoritmo multidimensional scaling (MDS) busca resolver el siguiente problema: Dada una matriz con las distancias entre ciudades que se desconocen, se quieren encontrar coordenadas en el plano para estas ciudades de forma tal que las distancias entre las mismas se aproximen lo mas posible a las distancias de nuestra matriz.

Es decir que dada una matriz de distancias entre puntos queremos hallar los puntos en sı́.

Question 17

Explique el algoritmo MDS.

Answer 17

Para poder aplicar el algoritmo, se debe realizar lo siguiente:

1. Elevar la matriz de distancias al cuadrado
2. Centrar la matriz para que las filas y columnas tengan promedio cero
3. Calcular la SVD de la matriz
4. Las primeras q columnas de U da las coordenadas para los puntos que se quieren buscar.

Question 18

Que consideracion hay que tener al usar MDS?

Answer 18

Notar que las coordenadas que devuelve MDS pueden estar espejadas y rotadas con respecto a la realidad ya que las distancias en todos los casos son las mismas.

Question 19

Explique Perceptual mapping.

Answer 19

Perceptual Mapping es una aplicación interesante de MDS para aprender los datos a partir de evaluaciones subjetivas u objetivas de los mismos. Suponer que se tiene un conjunto de autos de diferentes marcas y modelos. Podemos pedirles a los usuarios que indiquen que tan parecidos o diferentes son dos autos en un cuestionario o encuesta. Con la opinión de muchos usuarios sobre todos los pares posibles se puede construir una matriz de distancias. Luego, usando MDS, a partir de las distancias se puede construir una representación vectorial para cada modelo de auto en una cierta cantidad de dimensiones. Lo interesante es que cada una de estas dimensiones va a aportar algún tipo de información sobre los autos, por ejemplo su consumo, seguridad, etc. Se puede ver para cada ”feature” cuál es el valor que toma cada modelo de auto y deducir cual es el ”feature”. Lo que se esta haciendo es una construcción de los datos mismos a partir de las comparaciones entre pares de datos.

Question 20

Casos de uso de ISOMAP.

Answer 20

Puede usarse para visualización de datos, como pre-procesamiento o como features a agregar a los datos mismos.

Question 21

Explique ISOMAP.

Answer 21

El algoritmo consiste en construir un grafo a partir de los datos, calcular las distancias en dicho grafo y luego aplicar MDS para obtener una representación de los datos en pocas dimensiones.

Construcción del Grafo
El primer paso es crear un grafo no-dirigido en donde cada punto del set de datos va a estar conectado a sus k vecinos mas cercanos.Para determinar las distancias se puede usar una métrica a elección. En el grafo dos puntos i y j estarán conectados si j está entre los k vecinos mas cercanos de i o si i está entre los k vecinos mas cercanos de j. Este paso es muy sencillo de completar usando por ejemplo KNN. La matriz del grafo va a tener en cada posición M ij la distancia entre los puntos. El grafo va a ser muy disperso ya que cada punto solo va a tener k vecinos.

Cálculo de Distancias
Una vez obtenida la matriz de distancias, se construye una nueva matriz de distancias de todos los puntos contra todos. Para hacer esto hay que aplicar el algoritmo de Floyd-Warshall que dada una matriz de distancias entre pares de puntos nos devuelve la matriz de distancias mı́nimas de todos contra todos. Floyd-Warshall es O(n 3 ) por lo que hay que tener un poco de cuidado al aplicar ISOMAP a sets de datos masivos.

Aplicación de MDS
Una vez obtenida esta nueva matriz de distancias de todos los puntos contra todos, simplemente se aplica MDS con k = 2 o k = 3 para obtener la representación de nuestros puntos en dos o tres dimensiones respectivamente.

Question 22

Explique Laplacia Eigenmaps.

Answer 22

En este algoritmo también se crea un grafo a partir de los datos pero de una forma diferente a la que se utilizó en ISOMAP. En este algoritmo, la forma en la cual se crea el grafo es compartida por muchos otros como Clustering Espectral y Spectral Hashing.

Construcción del Grafo
Para la construcción del grafo es necesario construir una matriz de adyacencias en donde cada nodo va a estar conectado con sus k vecinos mas cercanos y el peso de las aristas entre nodos vecinos estará dado por la siguiente fórmula: W_ij = exp(-(||x_i - x_j||^2)/(sigma))
El parámetro σ regula el radio alrededor del cual dos puntos se consideran vecinos. Cuando el exponente ||x i − x j || 2 /σ es muy cercano a cero el valor de W ij es muy cercano a 1 mientras que si el exponente se hace mayor a 4 aproximadamente W ij es prácticamente 0. Esto permite regular cuándo se considera que dos puntos son vecinos. Observar que el tomar los k vecinos mas cercanos es en cierta forma equivalente a establecer una condición de corte para la cual se considera que W ij es nulo.

La matriz W es una matriz de adyacencias pero no de distancias. Cuanto mas grande es el valor de W ij mas cercanos son los puntos. En una matriz de adyacencias binaria usamos 1 si los puntos son vecinos y 0 si no. Esto es exactamente lo mismo solo que con valores entre 0 y 1 para determinar el grado de vecindad entre dos puntos.

Construcción del Laplaciano
A partir de un grafo y su matriz de adyacencias se puede calcular la matriz Laplaciana del mismo de la forma:

L = D − W

En donde D es una matriz diagonal con el grado de cada vértice del grafo siendo el grado la sumatoria de todas las aristas que inciden sobre el mismo, osea D_ii = sum(j=1 a n) W_ij.
La matriz resultante L tendrá en su diagonal el valor del grado ya que la diagonal de W es cero. El resto de los elementos de L es igual a la matriz W cambiada de signo ya que todos los elementos de D que no están en la diagonal son cero. Como consecuencia de esto la suma de cualquier fila y columna de L es cero. Siendo L una matriz simétrica sabemos que todos sus autovalores son reales. El último paso del algoritmo es descomponer la matriz L en sus autovalores y autovectores.

Descomposición Espectral del Laplaciano
En una matriz Laplaciana el autovalor mas pequeño en valor absoluto siempre va a ser cero, y su multiplicidad va a ser igual a la cantidad de componentes conexos del grafo. Es decir que en un grafo conexo L va a tener exactamente un autovalor igual a 0. Si se quisiera representar a los datos en k dimensiones entonces hay que tomar los k autovalores mas chicos en valor absoluto ignorando el 0. Los autovectores correspondientes a dichos autovalores son la representación de los datos en k dimensiones.

Question 23

En Laplacian Eigenmaps: se convserva la cercania de los puntos o la distancia de los mismos?

Answer 23

Se conserva la cercania, o sea, los puntos cercanos permanecen cercanos.

Question 24

En que se destaca TSNE?

Answer 24

T-SNE es, al momento de escribir este capı́tulo, el mejor algoritmo para la representación de datos en dos y tres dimensiones. Es, por lo tanto, el algoritmo más usado y el más importante para visualizar datos multidimensionales en el plano o en 3D.

Question 25

En TSNE: se convserva la cercania de los puntos o la distancia de los mismos?

Answer 25

T-SNE, a diferencia de PCA y al igual que en Laplacian Eigenmaps, va a intentar que los puntos que estaban cerca en n dimensiones se mantengan cercanos en k dimensiones. Estas son dos formas radicalmente opuestas de encarar el mismo problema.

Question 26

Enuncie el Teorema fundamental de la dimensionalidad.

Answer 26

No siempre es conveniente reducir la dimensionalidad de un set de datos.

Question 27

Explique utilidad de cada uno de los algoritmos en sus casos de uso.

Answer 27

Cuando se trata de visualización T-SNE suele ser un buen algoritmo para empezar. Cuando los resultados de T-SNE no son buenos se pueden utilizar otros algoritmos como ISOMAP, Laplacian Eigenmaps, LLE, Hessian, MDS, Kernel PCA etc.

Si se trata de reducir las dimensiones por cuestiones de performance o para mejorar el rendimiento de un algoritmo la SVD deberı́a ser la primera opción, teniendo en cuenta la posibilidad de usar algoritmos mas avanzados como Autoencoders.