noticias

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Informe del corazón de la máquina

Editor: Jiaqi

La matriz es difícil de entender, pero puede ser diferente si la miras desde otra perspectiva.

Cuando aprendemos matemáticas, a menudo nos sentimos frustrados por la dificultad y la abstracción del conocimiento que aprendemos, pero a veces, simplemente cambiando la perspectiva, podemos encontrar una solución simple e intuitiva al problema; Por ejemplo, cuando éramos niños estábamos aprendiendo la fórmula de suma de cuadrados (a+b)², es posible que no entendamos por qué es igual a a²+2ab+b². Solo sabemos que está escrito así en el. libro y la maestra nos pidió que lo recordáramos así hasta que un día vemos esta imagen animada:

¡De repente nos dimos cuenta de que podemos entenderlo desde una perspectiva geométrica!

Ahora, esta sensación de iluminación vuelve a ocurrir: ¡una matriz no negativa se puede convertir de manera equivalente en el gráfico dirigido correspondiente!

Como se muestra en la figura siguiente, la matriz de 3 × 3 de la izquierda en realidad se puede representar de manera equivalente como un gráfico dirigido que contiene tres nodos a la derecha, y esta representación es muy útil tanto para la teoría de matrices como para la de grafos.

Este ejemplo proviene del matemático Tivadar Danka, quien está comprometido a hacer que las matemáticas sean accesibles para todos. El autoproclamado matemático "bueno caótico" presentó vívidamente esta equivalencia de matrices y gráficos y sus usos en una serie de tweets y publicaciones de blog. Hasta el momento, estos tuits han sido leídos más de 2 millones de veces, recibido más de 3.200 retuits y 9.100 favoritos.

Valencia de matrices y gráficas dirigidas.

Como se muestra en el ejemplo anterior, si tratamos cada fila como un nodo, cada elemento se puede representar como un borde dirigido y ponderado. Por supuesto, se pueden ignorar 0 elementos. Si el elemento está ubicado en la fila i y la columna j, corresponde al borde del nodo i al nodo j.

A primera vista esto puede parecer complicado, pero podemos empezar mirando uno de los nodos.

Como se muestra en la figura, para esta matriz de 3 × 3, la fila 1 corresponde al nodo superior (aquí lo llamamos nodo 1), que contiene 3 elementos pero uno de ellos es 0, por lo que el nodo se extiende hacia los dos lados. El borde amarillo representa el elemento 0,5 en (1,1), por lo que es un borde dirigido que apunta a sí mismo con un peso de 0,5. De la misma forma, la arista azul es la arista que apunta al nodo 2 y tiene un peso de 1.

De esta forma, podemos analizar que la i-ésima columna de la matriz corresponde a todos los bordes que apuntan al i-nodo.

¿De qué sirve esta representación equivalente?

Esta equivalencia entre matrices no negativas y gráficas dirigidas no solo puede ayudarnos a comprender mejor las matrices y sus operaciones, sino que también puede ayudarnos a simplificar algunos procesos de cálculo, lo que también puede ayudarnos a comprender las gráficas desde una nueva perspectiva;

Por ejemplo, las potencias de una matriz corresponden a paseos en el gráfico.

Como se muestra en la figura anterior, para la k-ésima potencia de la matriz cuadrada A n×n, el proceso de suma de cada elemento incluirá todos los posibles recorridos de k-pasos.

Por ejemplo, digamos que queremos elevar al cuadrado la matriz de 3×3 de arriba.

Si usamos la multiplicación de matrices, debemos calcularla así:

Para el primer elemento del resultado de la operación, podemos obtener el resultado = 0,5×0,5+1×0,2+0×1,8 = 0,45. Finalmente, podemos obtener el resultado completo como:

Sin embargo, si utiliza el método de recorrido del gráfico anterior, puede obtener los resultados recorriendo el camino. De manera similar, para el primer elemento de la matriz de resultados, es necesario sumar todos los senderos de 2 pasos que se ajustan a a_{1,l}→a_{l,1}.

Sin embargo, si este gráfico dirigido representa el estado de una cadena de Markov, el cuadrado de su matriz de probabilidad de transición representa esencialmente la probabilidad de que la cadena alcance un cierto estado después de 2 pasos.

No solo eso, representar matrices como una gráfica también puede brindarnos información sobre la estructura de matrices no negativas. Para hacer esto, Danka dijo que primero debemos entender el concepto de "componentes fuertemente conectados".

Componente fuertemente conectado

¿Qué es un componente fuertemente conectado? Para un gráfico dirigido, si se puede llegar a todos los demás nodos del gráfico desde cada nodo, decimos que el gráfico está fuertemente conexo. Como se muestra a continuación.

El componente fuertemente conectado se refiere a la parte/subgrafo del gráfico dirigido que puede lograr una conectividad fuerte. Como se muestra en la figura siguiente, hay un componente fuertemente conectado a la izquierda y a la derecha, mientras que el borde blanco en el medio no pertenece a ningún componente fuertemente conectado.

La siguiente figura muestra otro ejemplo, donde la parte amarilla es el componente fuertemente conectado:

La matriz correspondiente a un gráfico fuertemente conexo es una matriz irreducible, mientras que todas las demás matrices de la matriz no negativa son matrices reducibles.

Danka lo explica con un ejemplo. (Para simplificar la explicación, todos los pesos del ejemplo son pesos unitarios, pero en la práctica estos valores de peso pueden ser cualquier valor no negativo).

A continuación, este gráfico, que contiene componentes fuertemente conectados pero que en sí mismo no está fuertemente conectado, se transforma a la forma matricial correspondiente:

Y esta matriz es una matriz reducible.

Se puede ver que las dos submatrices en la diagonal principal representan dos componentes fuertemente conectados respectivamente, mientras que la submatriz en la parte superior derecha representa el borde desde el primer componente fuertemente conectado al segundo componente fuertemente conectado, y la de la parte inferior izquierda representa Representa el borde desde el segundo componente fuertemente conectado hasta el primer componente fuertemente conectado (debido a que no existe tal borde, todo es 0).

Esta forma de escribir una matriz de bloques se llama forma normal de Frobenius.

Entonces, naturalmente nos preguntamos: ¿Podemos convertir cualquier matriz no negativa en una matriz canónica de Frobenius?

Al usar un gráfico dirigido para representar una matriz no negativa, podemos ver fácilmente que la respuesta es sí, ya que cualquier gráfico dirigido que represente una matriz no negativa se puede representar como componentes fuertemente conectados que están conectados entre sí. El proceso es muy sencillo:

1. Construir gráficos dirigidos correspondientes para matrices no negativas;
2. Encuentre los componentes fuertemente conectados;
3. Encuentre una mejor manera de etiquetar cada nodo.

¡Y ya está!

Utilice gráficos para obtener la forma estándar de Frobenius

Entonces, ¿cuál es esta mejor manera?

Según el ejemplo anterior, echemos un vistazo al proceso.

Primero, los componentes individuales fuertemente conectados se fusionan en un solo objeto, como se muestra en la siguiente figura. En este momento, podemos tratar cada componente fuertemente conectado como una caja negra: no nos importa su estructura interna, solo sus conexiones externas.

Luego, en este nuevo gráfico, necesitamos encontrar los componentes que solo tienen bordes salientes pero no entrantes. Solo hay uno en este ejemplo específico, al que etiquetamos con el número 0:

El siguiente paso es más problemático: numerar cada componente de modo que el número de cada componente esté a la mayor distancia del número 0. El siguiente ejemplo ilustra este punto más claramente:

Se puede ver que hay dos caminos desde el número 0 hasta el componente central, así que elija el camino más alejado de 0 para numerarlo. Finalmente obtuve:

En efecto, esto define el orden de los componentes. A continuación marque los nodos internos de cada componente:

Si el gráfico en sí proviene de una matriz, ¡tal proceso de reetiquetado da como resultado una matriz canónica de Frobenius!

De hecho, este proceso de reetiquetado consiste en utilizar una matriz de permutación P para transformar la matriz original, y la matriz de permutación se compone del producto de múltiples matrices transpuestas.

La siguiente es la forma completa del teorema:

Por supuesto, el uso de gráficos para representar matrices va mucho más allá de esto. Por ejemplo, también podemos usar los valores propios de la matriz para definir los valores propios del gráfico. De hecho, esta línea de pensamiento dio origen al campo de investigación de la teoría de grafos espectrales.

Conclusión

Obviamente, esta relación de equivalencia entre matrices y gráficas no sólo es útil para la investigación de la teoría de grafos, sino que también proporciona una nueva perspectiva para el cálculo y análisis del álgebra lineal. También tiene algunos usos prácticos importantes. Por ejemplo, los datos de ADN a menudo se representan en forma de matriz o gráfico.

Además, todos conocemos la importancia de las operaciones matriciales para los grandes modelos de IA actuales, y los gráficos representados por gráficos de conocimiento se están convirtiendo en un importante impulsor de la IA actual a través de tecnologías como la búsqueda mejorada por recuperación. La vinculación de ambos puede generar nuevos avances en la interpretabilidad de la IA y la inteligencia artificial gráfica. Como mínimo, esto nos ayuda a aprender mejor el álgebra lineal.

De hecho, el contenido anterior está extraído del libro "Matemáticas del aprendizaje automático" que está escribiendo Tivadar Danka. Este libro presentará el conocimiento matemático relacionado con el aprendizaje automático desde un nivel simple hasta un nivel profundo, permitiendo a los lectores comprender realmente qué es y por qué se hace. Danka declara con confianza que este será "el mejor recurso para aprender el aprendizaje automático". Actualmente, ha publicado dos avances de capítulos en línea. Los lectores interesados ​​pueden visitar: https://tivadardanka.com/mathematics-of-machine-learning-preview/.