notícias

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

Relatório do coração da máquina

Editor: Jiaqi

A matriz é difícil de entender, mas pode ser diferente se você olhar de outra perspectiva.

Ao aprender matemática, muitas vezes ficamos frustrados com a dificuldade e a abstração do conhecimento que aprendemos, mas às vezes, apenas mudando a perspectiva, podemos encontrar uma solução simples e intuitiva para o problema; Por exemplo, quando estávamos aprendendo a fórmula da soma dos quadrados (a+b)² quando éramos crianças, podemos não entender por que ela é igual a a²+2ab+b². Só sabemos que está escrito assim no alfabeto. livro e a professora pediu que lembrássemos assim; até que um dia vimos essa imagem animada:

De repente, percebemos que podemos entendê-lo de uma perspectiva geométrica!

Agora, esta sensação de esclarecimento ocorre novamente: uma matriz não negativa pode ser convertida de forma equivalente no gráfico direcionado correspondente!

Conforme mostrado na figura abaixo, a matriz 3×3 à esquerda pode, na verdade, ser representada de forma equivalente como um gráfico direcionado contendo três nós à direita, e esta representação é muito útil tanto para a teoria de matrizes quanto para a teoria de grafos.

Este exemplo vem do matemático Tivadar Danka, que está empenhado em tornar a matemática acessível a todos. O autoproclamado matemático “caótico e bom” apresentou vividamente essa equivalência de matrizes e gráficos e seus usos em uma série de tweets e postagens em blogs. Até agora, esses tweets foram lidos mais de 2 milhões de vezes, receberam mais de 3.200 retuítes e 9.100 favoritos.

Valência de matrizes e gráficos direcionados

Conforme mostrado no exemplo acima, se tratarmos cada linha como um nó, cada elemento pode ser representado como uma aresta direcionada e ponderada. Claro, 0 elementos podem ser ignorados. Se o elemento estiver localizado na linha i e na coluna j, ele corresponde à aresta do nó i ao nó j.

À primeira vista, isto pode parecer complicado, mas podemos começar observando um dos nós.

Conforme mostrado na figura, para esta matriz 3×3, a linha 1 corresponde ao nó superior (chamamos de nó 1 aqui), que contém 3 elementos, mas um deles é 0, então o nó se estende por dois lados. A aresta amarela representa o elemento 0,5 em (1,1), portanto é uma aresta direcionada apontando para si mesma com peso de 0,5. Da mesma forma, a aresta azul é a aresta que aponta para o nó 2 e tem peso 1.

Desta forma, podemos analisar que a i-ésima coluna da matriz corresponde a todas as arestas apontando para o i-nó.

Qual é a utilidade desta representação equivalente?

Esta equivalência entre matrizes não negativas e gráficos direcionados pode não apenas nos ajudar a entender melhor as matrizes e suas operações, mas também ajudar a simplificar alguns processos de cálculo, o que também pode nos ajudar a entender os gráficos de uma nova perspectiva;

Por exemplo, as potências de uma matriz correspondem a passeios no gráfico.

Conforme mostrado na figura acima, para a k-ésima potência da matriz quadrada n×n A, o processo de soma de cada elemento incluirá todas as caminhadas possíveis em k etapas.

Por exemplo, digamos que queremos elevar ao quadrado a matriz 3×3 acima.

Se estiver usando multiplicação de matrizes, precisamos calculá-la assim:

Para o primeiro elemento do resultado da operação, podemos obter o resultado = 0,5×0,5+1×0,2+0×1,8 = 0,45. Finalmente, podemos obter o resultado completo como:

No entanto, se você usar o método de caminhada no gráfico acima, poderá obter os resultados percorrendo o caminho. Da mesma forma, para o primeiro elemento da matriz de resultados, é necessário somar todos os caminhos de caminhada de 2 passos que estejam em conformidade com a_{1,l}→a_{l,1}.

No entanto, se este gráfico direcionado representa o estado de uma cadeia de Markov, o quadrado da sua matriz de probabilidade de transição representa essencialmente a probabilidade da cadeia atingir um determinado estado após 2 etapas.

Além disso, representar matrizes como um gráfico também pode nos dar uma ideia da estrutura de matrizes não negativas. Para fazer isso, Danka disse que precisamos primeiro entender o conceito de “componentes fortemente conectados”.

Componente fortemente conectado

O que é um componente fortemente conectado? Para um grafo direcionado, se todos os outros nós do grafo puderem ser alcançados a partir de todos os nós, dizemos que o grafo está fortemente conectado. Conforme mostrado abaixo.

O componente fortemente conectado refere-se à parte/subgrafo no grafo direcionado que pode alcançar forte conectividade. Conforme mostrado na figura abaixo, há um componente fortemente conectado à esquerda e à direita, enquanto a borda branca no meio não pertence a nenhum componente fortemente conectado.

A figura abaixo mostra outro exemplo, onde a parte amarela é o componente fortemente conectado:

A matriz correspondente a um gráfico fortemente conectado é uma matriz irredutível, enquanto todas as outras matrizes na matriz não negativa são matrizes redutíveis.

Danka explica com um exemplo. (Para simplificar a explicação, todos os pesos no exemplo são pesos unitários, mas na prática esses valores de peso podem ser quaisquer valores não negativos.)

A seguir, este gráfico, que contém componentes fortemente conectados, mas não é fortemente conectado, é transformado na forma de matriz correspondente:

E esta matriz é uma matriz redutível.

Pode-se ver que as duas submatrizes na diagonal principal representam dois componentes fortemente conectados respectivamente, enquanto a submatriz no canto superior direito representa a aresta do primeiro componente fortemente conectado ao segundo componente fortemente conectado, e a do canto inferior esquerdo representa Representa a aresta do 2º componente fortemente conectado ao 1º componente fortemente conectado (porque não existe tal aresta, é tudo 0).

Esta forma de escrever uma matriz de bloco é chamada de forma normal de Frobenius.

Então, perguntamos naturalmente: Podemos converter qualquer matriz não negativa em uma matriz canônica de Frobenius?

Ao usar um gráfico direcionado para representar uma matriz não negativa, podemos facilmente ver que a resposta é sim, uma vez que qualquer gráfico direcionado representando uma matriz não negativa pode ser representado como componentes fortemente conectados que estão conectados entre si. O processo é muito simples:

1. Construir gráficos direcionados correspondentes para matrizes não negativas;
2. Encontre os componentes fortemente conectados;
3. Encontre uma maneira melhor de rotular cada nó.

E pronto!

Use gráficos para obter o formulário padrão Frobenius

Então, qual é a melhor maneira?

Com base no exemplo acima, vamos dar uma olhada no processo.

Primeiro, os componentes individuais fortemente conectados são fundidos em um único objeto, conforme mostrado na figura abaixo. Neste momento, podemos tratar cada componente fortemente conectado como uma caixa preta - não nos importamos com sua estrutura interna, apenas com suas conexões externas.

Então, neste novo gráfico, precisamos encontrar os componentes que possuem apenas arestas de saída, mas nenhuma aresta de entrada. Há apenas um neste exemplo específico, que rotulamos como número 0:

A próxima etapa é mais problemática: numere cada componente de modo que o número de cada componente esteja à maior distância do número 0. O exemplo a seguir ilustra esse ponto mais claramente:

Pode-se observar que existem dois caminhos do número 0 até o componente do meio, então escolha o caminho mais distante de 0 para numerá-lo. Finalmente consegui:

Na verdade, isso define a ordem dos componentes. A seguir marque os nós internos de cada componente:

Se o próprio gráfico vier de uma matriz, tal processo de renomeação resultará em uma matriz canônica de Frobenius!

Na verdade, esse processo de reetiquetagem consiste em usar uma matriz de permutação P para transformar a matriz original, e a matriz de permutação é composta pelo produto de múltiplas matrizes transpostas.

A seguir está a forma completa do teorema:

É claro que o uso de gráficos para representar matrizes vai muito além disso. Por exemplo, também podemos usar os autovalores da matriz para definir os autovalores do gráfico. Na verdade, essa linha de pensamento deu origem ao campo de pesquisa da teoria dos grafos espectrais.

Conclusão

Obviamente, esta relação de equivalência entre matrizes e gráficos não é apenas útil para a pesquisa em teoria dos grafos, mas também fornece uma nova perspectiva para o cálculo e análise da álgebra linear. Também tem alguns usos práticos importantes. Por exemplo, os dados de DNA são frequentemente representados na forma de uma matriz ou gráfico.

Além disso, todos sabemos a importância das operações matriciais para a IA atual de grandes modelos, e os gráficos representados por gráficos de conhecimento estão se tornando um importante impulsionador da IA ​​atual por meio de tecnologias como a pesquisa aprimorada de recuperação. Vincular os dois pode trazer alguns novos avanços na interpretabilidade da IA ​​e na inteligência artificial gráfica. No mínimo, isso nos ajuda a aprender melhor a álgebra linear.

Na verdade, o conteúdo acima foi extraído do livro "Matemática do Aprendizado de Máquina" que Tivadar Danka está escrevendo. Este livro apresentará o conhecimento matemático relacionado ao aprendizado de máquina do nível simples ao profundo, permitindo que os leitores entendam verdadeiramente o que é e por que é feito. Danka declara com segurança que este será "o melhor recurso para aprender o aprendizado de máquina". Atualmente, ele lançou duas prévias de capítulos online. Os leitores interessados ​​​​podem visitar: https://tivadardanka.com/mathematics-of-machine-learning-preview/.