2024-08-19
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
기계 심장 보고서
편집자: Jiaqi
매트릭스는 이해하기 어렵지만, 다른 관점에서 보면 다를 수도 있다.
수학을 배울 때, 우리는 배우는 지식의 난이도와 추상성으로 인해 좌절감을 느끼는 경우가 많습니다. 그러나 때로는 관점을 바꾸는 것만으로도 문제에 대한 간단하고 직관적인 해결책을 찾을 수 있습니다. 예를 들어, 우리가 어렸을 때 제곱합 (a+b)² 공식을 배울 때 그것이 왜 a²+2ab+b²와 같은지 이해하지 못할 수도 있습니다. 책을 읽고 선생님은 언젠가 우리가 이 애니메이션 사진을 볼 때까지 이것을 이렇게 기억하라고 했습니다.
기하학적 관점에서 그것을 이해할 수 있다는 사실이 갑자기 우리에게 떠올랐습니다!
이제 이러한 깨달음이 다시 일어납니다. 음수가 아닌 행렬은 상응하는 유향 그래프로 동등하게 변환될 수 있습니다!
아래 그림에서 볼 수 있듯이 왼쪽의 3×3 행렬은 실제로 오른쪽의 3개 노드를 포함하는 방향성 그래프와 등가적으로 표현될 수 있으며, 이러한 표현은 행렬 이론과 그래프 이론 모두에 매우 유용합니다.
이 예는 모든 사람이 수학에 접근할 수 있도록 노력하는 수학자 Tivadar Danka의 작품입니다. 자칭 "혼돈의 선" 수학자인 그는 일련의 트윗과 블로그 게시물을 통해 행렬과 그래프의 동등성과 그 사용법을 생생하게 소개했습니다. 지금까지 이 트윗은 200만 번 이상 읽혔고, 3,200개 이상의 리트윗과 9,100개 이상의 즐겨찾기를 받았습니다.
행렬과 유향 그래프의 원자가
위의 예에서 볼 수 있듯이 각 행을 노드로 처리하면 각 요소는 방향이 있고 가중치가 부여된 가장자리로 표시될 수 있습니다. 물론 0개의 요소는 무시될 수 있습니다. 요소가 i행과 j열에 있으면 노드 i에서 노드 j까지의 가장자리에 해당합니다.
언뜻 보면 복잡해 보일 수 있지만 노드 중 하나를 살펴보는 것부터 시작할 수 있습니다.
그림에 표시된 대로 이 3×3 행렬의 경우 행 1은 3개의 요소를 포함하지만 그 중 하나가 0이므로 노드가 두 측면으로 확장되는 최상위 노드(여기서는 노드 1이라고 함)에 해당합니다. 노란색 가장자리는 (1,1)의 요소 0.5를 나타내므로 가중치가 0.5인 자신을 가리키는 방향이 있는 가장자리입니다. 마찬가지로 파란색 가장자리는 노드 2를 가리키는 가장자리이며 가중치는 1입니다.
이런 방식으로 행렬의 i번째 열이 i-노드를 가리키는 모든 모서리에 해당함을 분석할 수 있습니다.
이 동등한 표현의 용도는 무엇입니까?
음이 아닌 행렬과 방향성 그래프 간의 이러한 동등성은 행렬과 해당 연산을 더 잘 이해하는 데 도움이 될 뿐만 아니라 일부 계산 프로세스를 단순화하는 데도 도움이 되며 새로운 관점에서 그래프를 이해하는 데도 도움이 됩니다.
예를 들어, 행렬의 거듭제곱은 그래프의 보행에 해당합니다.
위 그림에 표시된 것처럼 n×n 정사각 행렬 A의 k승에 대해 각 요소의 합산 프로세스에는 가능한 모든 k-단계 이동이 포함됩니다.
예를 들어 위의 3×3 행렬을 제곱한다고 가정해 보겠습니다.
행렬 곱셈을 사용하는 경우 다음과 같이 계산해야 합니다.
연산 결과의 첫 번째 요소에 대해 결과 = 0.5×0.5+1×0.2+0×1.8 = 0.45를 얻을 수 있습니다. 마지막으로 다음과 같은 완전한 결과를 얻을 수 있습니다.
그러나 위의 그래프 걷기 방법을 사용하면 경로를 걷는 것으로 결과를 얻을 수 있습니다. 마찬가지로 결과 행렬의 첫 번째 요소에 대해서는 a_{1,l}→a_{l,1}을 준수하는 2단계 보행 경로를 모두 합산해야 합니다.
그러나 이 방향 그래프가 마르코프 체인의 상태를 나타내는 경우 전이 확률 행렬의 제곱은 본질적으로 체인이 2단계 후에 특정 상태에 도달할 확률을 나타냅니다.
뿐만 아니라 행렬을 그래프로 표현하면 음이 아닌 행렬의 구조에 대한 통찰력을 얻을 수도 있습니다. 이를 위해서는 먼저 "강하게 연결된 구성요소"라는 개념을 이해해야 한다고 Danka는 말했습니다.
강하게 연결된 구성 요소
강력하게 연결된 구성요소란 무엇입니까? 유향 그래프의 경우 그래프의 다른 모든 노드가 모든 노드에서 도달할 수 있으면 그래프가 강력하게 연결되어 있다고 말합니다. 아래 그림과 같습니다.
강한 연결 구성 요소는 강력한 연결을 달성할 수 있는 유향 그래프의 부분/하위 그래프를 나타냅니다. 아래 그림과 같이 왼쪽과 오른쪽에는 강하게 연결된 구성 요소가 있고 가운데 흰색 가장자리는 강하게 연결된 구성 요소에 속하지 않습니다.
아래 그림은 노란색 부분이 강하게 연결된 구성요소인 또 다른 예를 보여줍니다.
강하게 연결된 그래프에 해당하는 행렬은 기약 행렬이고, 음수가 아닌 행렬의 다른 모든 행렬은 기약 행렬입니다.
Danka는 예를 들어 설명합니다. (설명의 편의를 위해 예시에서 모든 가중치는 단위중량이지만, 실제로 이러한 가중치 값은 음수가 아닌 어떤 값이라도 가능합니다.)
다음으로, 강하게 연결된 구성요소를 포함하지만 그 자체로는 강하게 연결되지 않은 이 그래프는 해당 행렬 형식으로 변환됩니다.
그리고 이 행렬은 환원가능한 행렬이다.
주대각선의 두 부분행렬은 각각 두 개의 강한 연결성분을 나타내고, 오른쪽 위 부분행렬은 첫 번째 강한 연결성분에서 두 번째 강한 연결성분까지의 간선을 나타내고, 왼쪽 아래 부분행렬은 두 번째 강한 연결 성분에서 첫 번째 강한 연결 성분까지의 간선을 나타냅니다(해당 간선이 없으므로 모두 0입니다).
이러한 블록 행렬 작성 형식을 Frobenius 정규 형식이라고 합니다.
따라서 우리는 자연스럽게 질문합니다. 음수가 아닌 행렬을 Frobenius 정규 행렬로 변환할 수 있습니까?
음이 아닌 행렬을 나타내는 유향 그래프를 사용하면 대답이 '예'라는 것을 쉽게 알 수 있습니다. 음이 아닌 행렬을 나타내는 유향 그래프는 서로 연결된 강력하게 연결된 구성요소로 표현될 수 있기 때문입니다. 과정은 매우 간단합니다.
이제 끝났습니다!
그래프를 사용하여 Frobenius 표준 형식 얻기
그렇다면 이것이 더 좋은 방법은 무엇입니까?
위의 예를 바탕으로 프로세스를 살펴보겠습니다.
먼저, 아래 그림과 같이 강력하게 연결된 개별 구성 요소가 단일 개체로 융합됩니다. 이때 우리는 강력하게 연결된 각 구성요소를 블랙박스로 처리할 수 있습니다. 내부 구조에는 관심이 없고 외부 연결에만 관심이 있습니다.
그런 다음 이 새 그래프에서 나가는 가장자리만 있고 들어오는 가장자리가 없는 구성 요소를 찾아야 합니다. 이 특정 예에는 숫자 0으로 라벨을 붙인 하나만 있습니다.
다음 단계는 더 까다롭습니다. 각 구성 요소의 번호가 숫자 0에서 가장 먼 거리에 있도록 각 구성 요소에 번호를 매깁니다. 다음 예는 이 점을 더 명확하게 보여줍니다.
숫자 0에서 중간 구성 요소까지 두 개의 경로가 있음을 알 수 있으므로 0에서 가장 먼 경로를 선택하여 번호를 매깁니다. 마침내 얻었습니다 :
실제로 이는 구성 요소의 순서를 정의합니다. 다음으로 각 구성 요소의 내부 노드를 표시합니다.
그래프 자체가 행렬에서 나온 경우 이러한 레이블 재지정 프로세스로 인해 Frobenius 표준 행렬이 생성됩니다!
실제로 이러한 재라벨링 과정은 순열 행렬 P를 사용하여 원래 행렬을 변환하는 것이며, 순열 행렬은 여러 전치 행렬의 곱으로 구성됩니다.
다음은 정리의 완전한 형태입니다.
물론, 행렬을 표현하기 위해 그래프를 사용하는 것은 이보다 훨씬 더 뛰어납니다. 예를 들어, 행렬의 고유값을 사용하여 그래프의 고유값을 정의할 수도 있습니다. 실제로 이러한 사고 방식이 스펙트럼 그래프 이론이라는 연구 분야를 탄생시켰습니다.
결론
분명히, 행렬과 그래프 사이의 이러한 등가 관계는 그래프 이론 연구에 도움이 될 뿐만 아니라 선형 대수학의 계산 및 분석에 대한 새로운 관점을 제공합니다. 또한 몇 가지 중요한 실제 용도가 있습니다. 예를 들어, DNA 데이터는 종종 행렬이나 그래프 형태로 표현됩니다.
또한, 우리 모두는 현재 대형 모델 AI에서 행렬 연산의 중요성을 알고 있으며, 지식 그래프로 표현되는 그래프는 검색 강화 검색 등의 기술을 통해 현재 AI의 중요한 동인이 되고 있습니다. 이 둘을 연결하면 AI 해석 가능성과 그래프 인공 지능에 새로운 돌파구가 생길 수 있습니다. 최소한 이것은 우리가 선형 대수학을 더 잘 배우는 데 도움이 됩니다.
실제로 위 내용은 티바다르 단카(Tivadar Danka)가 집필하고 있는 책 '기계학습의 수학(Mathematics of Machine Learning)'에서 발췌한 내용이다. 이 책은 머신러닝과 관련된 수학적 지식을 단순한 수준부터 심층적인 수준까지 소개하여 독자들이 그것이 무엇인지, 왜 이루어지는지 진정으로 이해할 수 있도록 해줄 것이며, 단카는 이 책이 “머신러닝 학습을 위한 최고의 리소스”가 될 것이라고 자신있게 선언합니다. 현재 그는 온라인으로 두 장의 미리보기를 공개했습니다. 관심 있는 독자는 https://tivadardanka.com/mathematics-of-machine-learning-preview/를 방문하세요.
