Las matrices dispersas son solo una representación de matrices reales. Sin embargo, ¿por qué los necesitamos?
Consideremos el gráfico de la web. (¡No te preocupes, intentaré no ser muy técnico!)
Podemos definir el gráfico anterior de la siguiente manera:
- Una página web es un nodo o un punto en este gráfico.
- Un hipervínculo o un enlace es lo que relaciona una página web con otra.
Ahora que definimos nuestro gráfico. Te preguntas, ¿qué tiene que ver con matrices dispersas?
- Aproximadamente, ¿cuántas personas en el mundo conocen el álgebra lineal?
- Probabilidad (estadísticas): supongamos que tenemos una matriz de bits de tamaño NXM. ¿Cuál es el número estimado de filas en la matriz que tienen un número distinto de 1 en ellas?
- ¿Por qué la velocidad de convergencia del descenso del gradiente depende de los valores propios máximos y mínimos de A para resolver AX = b a través de mínimos cuadrados?
- ¿Cuáles son las diferencias básicas entre SVD (Descomposición de valor singular) y EVD (Descomposición de valor de Eigen)?
- ¿Abandonamos el orden de las operaciones al resolver problemas de álgebra de dos pasos?
Las páginas web que definimos anteriormente serán las filas y columnas en una matriz normal normal. En nuestro caso, el número de filas y columnas es el mismo.
Ok, ahora llenemos nuestra matriz. Para cada enlace entre dos páginas web, pondremos un valor en la fila y columna asociadas a ambas páginas web.
Ejemplo: si tenemos un enlace desde la página de inicio de Amazon a Quora, hipotéticamente, el valor de la celda en (row_amazon, column_quora) es igual a 1.
Y así sucesivamente para cada página web en la red. Terminaremos con el siguiente gráfico
[Ref. SNAP / web-BerkStan matriz dispersa]
En este gráfico, los enlaces (o valores) están representados pero son puntos. Observamos que en realidad hay mucha escasez en ese gráfico.
Por lo tanto, la representación de esta matriz en su forma tradicional es inútil ya que la densidad de esta matriz es de aproximadamente 1/3 (no es un número exacto) y guardar todos los valores de los elementos cero tomará mucho espacio.
Pero el espacio en disco (complejidad del espacio para expertos) es un factor importante en la construcción de un sistema computacional, que también conduce a mejores operaciones computacionales. Y esta es la razón:
La multiplicación matricial del libro escolar debe realizar N veces N veces N operaciones para obtener los resultados finales de salida porque seremos necesarios para tener en cuenta esos valores cero inútiles que no agregarán nada a nuestra multiplicación. Y eso es mucho incluso para una computadora cuando pasa una cierta cantidad de N (número de páginas web en nuestro caso).
Volvamos a nuestro gráfico, que ahora preferiríamos tener en una representación escasa. La multiplicación de matriz dispersa realiza una cantidad de operaciones proporcionales a la cantidad de valores n-cero. (1/3 veces N: número de elementos distintos de cero)
K / 3 N << N x N x N
¡Espero que todos estemos de acuerdo en eso!
También puede leer la entrada de Wikipedia sobre ese tema Matriz dispersa.
Entonces, ahora que sabemos para qué se utilizan las matrices dispersas. Podemos avanzar rápidamente en su aplicación en Machine Learning.
No estoy seguro de su experiencia en ML, por lo que tomaré un ejemplo sencillo sobre el análisis de componentes principales y la reducción de la dimensionalidad.
Los métodos enumerados anteriormente se logran a través de una multiplicación matricial más compleja y sin entrar en muchos detalles, esto resultará en aún más operaciones de las que podría tomar la multiplicación matricial escolar utilizada anteriormente. ¡Eso puede llevar algo de tiempo y no queremos eso!
Entonces, en este caso, queremos realizar nuestro cálculo rápidamente porque necesitamos esos resultados para aplicar otros algoritmos de ML como KNN.
Espero que esto responda tu pregunta y gracias por leer!