Tutorial del Algoritmo DVS en Python
El algoritmo de Descomposición en Valores Singulares (DVS) es una aproximación a la descomposición de una matriz, lo cual nos ayuda en la reducción de esta mediante la generalización de la descomposición propia — también conocida como descomposición espectral — de una matriz cuadrada a cualquier otro tipo de matriz. Esto ayudará a simplificar los cálculos cuando se trabaja con matrices.
Si no tienes claro los conceptos de una descomposición propia, te invito a leer mi artículo anterior sobre el Algoritmo de Análisis de Componentes Principales, específicamente la sección 3: “Calcular la Descomposición Propia de la Matriz de Covarianza” (Tutorial del Algoritmo ACP en Python | by Anthony Barrios | LatinXinAI | Medium). Será de gran ayuda debido a que el algoritmo de Descomposición en Valores Singulares tiene un enfoque similar al algoritmo de Análisis de Componentes Principales (ACP). Mientras que este último hace una suposición de la matriz cuadrada que se recibe como entrada, el algoritmo DVS evita esto.
De manera general, cuando trabajamos con matrices de números reales, la fórmula a utilizar en la Descomposición en Valores Singulares es la siguiente:
Se destaca previamente que una matriz singular se refiere a las matrices cuyo determinante es cero, lo cual indica que no tiene entonces un inverso multiplicativo.
Sabiendo esto, volviendo a la fórmula, notamos entonces que M sería la matriz m x n que deseamos descomponer, U es la matriz singular izquierda — en este caso su dimensión es m x m — que contiene a los vectores propios de la matriz
La letra griega Sigma representa una matriz diagonal que contiene las raíces cuadradas de los valores propios de las matrices MM* o M*M, ordenadas en orden descendente; mientras que V es la matriz singular derecha de tamaño n x n, esta posee los vectores propios de la matriz
Para un entendimiento simple de la función de cada matriz, podemos decir que las matrices U y V* causan una rotación en la matriz, mientras que la matriz Sigma ocasiona un escalamiento.
Tutorial en Python
¡Eso es! Ahora veremos un ejemplo básico de este algoritmo en Python. Antes de ello, cabe destacar que estaremos usando la Distribución Anaconda para Python. En caso que no la tengas instalada, probablemente deberás instalar algunos pip’s (instaladores de paquetes para Python) a través del siguiente comando:
Hecho esto, sigamos con el tutorial. Consideraremos la siguiente matriz para nuestra demostración.
La cosa con Python y algunas librerías, es que podemos realizar el Algoritmo DVS simplemente llamando a una función, pero eso le quitaría la diversión a este tutorial. Podemos recrear este algoritmo y ver el proceso que se realiza en el paso a paso. Lo primero que haremos es importar las librerías a utilizar, en este caso usaremos NumPy y SciPy. SciPy es una librería de código abierto de Python, es usada con bastante frecuencia para resolver problemas en el área de matemáticas, ciencias, ingeniería y tecnología. Permite al usuario alterar y ver los datos utilizando una variedad de comandos de alto nivel de Python. Cabe destacar que es una extensión de la librería NumPy que también va a ser de gran uso. Puede seguirlo en este Jupyter Notebook.
Ahora, vamos a crear algunas funciones que hagan los cálculos respectivos, están todos comentados en caso de que no se entienda qué es lo que hacen a simple vista.
Creamos luego nuestra matriz, a la que llamaremos como “A”.
Ahora le asignaremos valores a nuestras variables mediante los llamados a las funciones que creamos en el primer paso.
Cuando imprimimos nuestras variables, obtenemos la siguiente salida:
Y eso es básicamente todo. Ahora, Python nos permite llamar a la función que automatiza todo este proceso, la cual como previamente se dijo es importada de la librería SciPy. Esto nos permite hacer los cálculos más simples y sin algún margen de error.
Como podemos ver, los valores son casi iguales, exceptuando algunos signos que cambian en los valores. Dicho esto, cada investigador al momento de realizar su trabajo busca trabajar de manera rápida y eficiente, así que se recomienda trabajar con esta función de la librería SciPy.
Aplicaciones del Algoritmo
Ahora que sabemos lo básico, no siempre queremos utilizar el algoritmo DVS para una simple descomposición de matriz. Hay muchas aplicaciones que podemos realizar.
Este algoritmo puede ser utilizado para calcular la pseudoinversa de una matriz, la cual es una extensión de la inversa de una matriz cuadrada a las que no son cuadradas. Es de bastante ayuda cuando queremos recuperar información perdida de las matrices que no poseen una inversa. El algoritmo DVS es capaz de calcular la pseudoinversa de la matriz para poder trabajar con esa información.
Pero también conocemos que este algoritmo es utilizado ampliamente como un método de Reducción de Dimensionalidad, específicamente en la compresión de imágenes. Dicho esto, veamos un ejemplo en Python sobre compresión de imágenes utilizando el algoritmo DVS.
Compresión de Imágenes en Python utilizando el Algoritmo DVS.
Cuando queremos comprimir un archivo, siempre buscamos el acercamiento más eficiente con la menor cantidad de datos innecesarios. Mientras más pequeña sea la imagen, menor será el costo de almacenamiento y transmisión. El algoritmo de Descomposición en Valores Singulares ayuda en la descomposición de una matriz dada (en este caso, una imagen es una matriz con diferentes valores que representan a los colores mostrados) en tres matrices, para finalmente mostrar a la misma imagen, pero con una cantidad reducida de valores.
De esta forma, la compresión de imágenes será alcanzada mientras se guardan las características más importantes que forman a la foto principal.
Para comenzar a trabajar con este algoritmo, escogeremos los primeros k elementos de cada matriz. En el siguiente ejemplo, utilizaremos este método y mostraremos algunas variaciones correspondientes al número de elementos con los que trabajaremos. Para la demostración utilizaremos la siguiente foto de un gato.
Lo primero que haremos es importar nuestras librerías
A este punto ya estamos familiarizados con NumPy. Agregaremos otras librerías como Matplotlib, una librería de gráficos para Python que a su vez es una extensión de NumPy. Matplotlib contiene a la librería image, que soporta la carga de imágenes, su re-escalado y acciones que permiten cambiar la forma de visualizarlas. Específicamente contiene imread, una función que permite leer la imagen como un arreglo.
Además, hemos importado la interfaz pyplot, que nos otorga formas de graficar implícitas muy parecidas a los métodos que utiliza MATLAB. Finalmente, la librería os. Esta tiene funciones para crear y eliminar directorios, es decir carpetas, recuperando su contenido, actualizando e identificando el directorio actual.
Ahora, vamos a ajustar el tamaño del gráfico, leer nuestra imagen y convertirla en una imagen a escala de grises, de esta forma se hará un poco más sencillo ver las diferencias entre los resultados que nos muestre este algoritmo.
Cuando llamamos a la función plt.show, nos muestra entonces nuestra nueva fotografía en una escala de grises.
En este momento comienza la magia. Vamos a calcular el algoritmo DVS usando la función importada de NumPy o SciPy.
En primera instancia, puede ser un poco confuso de ver, pero lo que estamos haciendo es extraer las entradas diagonales de la matriz Sigma y ordenándose de manera descendiente. Luego, de forma iterativa se procede a seleccionar los primeros k valores de cada matriz, seleccionándolos de las columnas de la matriz U y las filas de la matriz V transpuesta. Con este aporte, veremos el mejor método para aproximarnos a la imagen original.
Cuando llamamos a la última función, nos mostrará tres diferentes salidas con los valores de k dados.
La primera salida no nos dará nada claro, pero podemos suponer que la imagen nos muestra a un gato por sus orejas puntiagudas.
En la siguiente imagen claramente podemos ver a un gato, pero obviamente la imagen se ve borrosa, así que no podemos apreciar los detalles que la imagen original tiene.
La imagen final tiene el mayor número de k valores que le dimos en este caso, lo cual nos permite ver una imagen más clara. Por supuesto que tiene algunos detalles que se pierden de la foto original, pero podemos notar que este valor de k es ideal para una buena comprensión en donde obtengamos la menor cantidad de datos posibles para dar un mensaje claro. Esta imagen puede ser de gran uso en un proyecto futuro en el que podemos trabajar, tal vez en un álbum de gatos o en una página de una veterinaria.
En conclusión
El algoritmo de Descomposición en Valores Singulares es una herramienta poderosa para la reducción de dimensionalidades. En este artículo, fuimos capaz de hacer un repaso a algunos términos matemáticos que permitieron entender el funcionamiento de este algoritmo y en cómo puede ser aplicado en campos importantes como la compresión de imágenes.
En este caso, siendo de gran ayuda debido a la reducción de transmisión y almacenamiento, notamos que el simple uso de este algoritmo es alcanzado mediante la selección adecuada de k elementos. Mientras este número incrementó, la matriz con la que trabajamos llegaba a ser reconstruida casi como la imagen original. De esta forma, se puede decir que este es un algoritmo bastante simple ya que tiene una complejidad computacional elevada.
Pero la compresión de imágenes no es la única área en la que se destaca este algoritmo, sino que también funciona en compresión de base de datos o videos. Te animo a seguir leyendo y practicando con el algoritmo en que trabajamos en las secciones de los tutoriales con Python. ¡Éxitos en tu código!
Do you identify as Latinx and are working in artificial intelligence or know someone who is Latinx and is working in artificial intelligence?
- Get listed on our directory and become a member of our member’s forum: https://lxai.app/
- Become a writer for the LatinX in AI Publication: http://bit.ly/LXAI-Volunteer
- Learn more on our website: http://www.latinxinai.org/
Don’t forget to hit the 👏 below to help support our community — it means a lot! Thank you :)
Referencias:
- Pillow, J. (2018). Statistical Modeling and Analysis of Neural Data, Spring 2018. Pillow Lab @ Princeton. Retrieved August 12, 2022, from http://pillowlab.princeton.edu/teaching/statneuro2018/
- Serrano.Academy. (2020). Singular Value Decomposition (SVD) and Image Compression [Video]. YouTube. https://www.youtube.com/watch?v=DG7YTlGnCEo&t=33s&ab_channel=Serrano.Academy
- Swathi, H. R., Sohini, S., Surbhi, & Gopichand, G. (2017). Image compression using singular value decomposition. IOP Conference Series: Materials Science and Engineering, 263, 042082. https://doi.org/10.1088/1757-899x/263/4/042082
