новости

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

Отчет о сердце машины

Монтажер: Цзяци

Матрицу сложно понять, но она может быть другой, если посмотреть на нее с другой точки зрения.

Изучая математику, нас часто разочаровывает сложность и абстрактность изучаемых знаний, но иногда, просто изменив точку зрения, мы можем найти простое и интуитивное решение проблемы; Например, когда мы в детстве изучали формулу суммы квадратов (a+b)², мы могли не понимать, почему она равна a²+2ab+b². Мы знаем только, что так написано. книгу, и учитель попросил нас запомнить ее так, пока однажды мы не увидим вот такую ​​анимированную картинку:

Нас внезапно осенило, что мы можем понять это с геометрической точки зрения!

Теперь это прозрение возникает снова: неотрицательную матрицу можно эквивалентным образом преобразовать в соответствующий ориентированный граф!

Как показано на рисунке ниже, матрицу 3×3 слева фактически можно эквивалентно представить как ориентированный граф, содержащий три узла справа, и это представление очень полезно как для теории матриц, так и для теории графов.

Этот пример принадлежит математику Тивадару Данке, который стремится сделать математику доступной для всех. Самопровозглашенный «хаотично-добрый» математик ярко представил эту эквивалентность матриц и графиков и их использование в серии твитов и сообщений в блогах. На данный момент эти твиты были прочитаны более 2 миллионов раз, получили более 3200 ретвитов и 9100 добавлений в избранное.

Валентность матриц и ориентированных графов

Как показано в примере выше, если мы рассматриваем каждую строку как узел, каждый элемент можно представить как направленное и взвешенное ребро. Конечно, 0 элементов можно игнорировать. Если элемент расположен в строке i и столбце j, он соответствует ребру от узла i до узла j.

На первый взгляд это может показаться сложным, но мы можем начать с рассмотрения одного из узлов.

Как показано на рисунке, для этой матрицы 3×3 строка 1 соответствует самому верхнему узлу (здесь мы называем его узлом 1), который содержит 3 элемента, но один из них равен 0, поэтому узел простирается на две стороны. Желтое ребро представляет элемент 0,5 в точке (1,1), поэтому это направленное ребро, направленное на себя, с весом 0,5. Точно так же синее ребро — это ребро, которое указывает на узел 2 и имеет вес 1.

Таким образом, мы можем проанализировать, что i-й столбец матрицы соответствует всем ребрам, указывающим на i-узел.

Какова польза от этого эквивалентного представления?

Эта эквивалентность между неотрицательными матрицами и ориентированными графами может не только помочь нам лучше понять матрицы и их операции, но и, в свою очередь, помочь упростить некоторые процессы вычислений, что, в свою очередь, может помочь нам понять графы с новой точки зрения;

Например, степени матрицы соответствуют блужданиям по графу.

Как показано на рисунке выше, для k-й степени квадратной матрицы A размера n×n процесс суммирования каждого элемента будет включать все возможные k-шаговые обходы.

Например, предположим, что мы хотим возвести в квадрат приведенную выше матрицу 3×3.

Если мы используем матричное умножение, нам нужно вычислить его следующим образом:

Для первого элемента результата операции мы можем получить результат = 0,5×0,5+1×0,2+0×1,8 = 0,45. Наконец, мы можем получить полный результат как:

Однако, если вы используете описанный выше метод обхода графа, вы можете получить результаты с помощью пешеходных дорожек. Аналогично для первого элемента матрицы результатов необходимо просуммировать все двухшаговые пешеходные пути, соответствующие a_{1,l}→a_{l,1}.

Однако если этот ориентированный граф представляет состояние цепи Маркова, квадрат его матрицы вероятности перехода по существу представляет вероятность того, что цепь достигнет определенного состояния после двух шагов.

Мало того, представление матриц в виде графа также может дать нам представление о структуре неотрицательных матриц. Для этого, по словам Данки, нам нужно сначала понять концепцию «сильно связанных компонентов».

Сильно связанный компонент

Что такое сильно связная компонента? Для ориентированного графа, если из любого узла можно добраться до любого другого узла графа, мы говорим, что граф сильно связен. Как показано ниже.

Сильно связный компонент относится к части/подграфу ориентированного графа, которая может обеспечить сильную связность. Как показано на рисунке ниже, слева и справа есть сильно связный компонент, а белый край в середине не принадлежит ни одному сильно связному компоненту.

На рисунке ниже показан еще один пример, где желтая часть является сильно связным компонентом:

Матрица, соответствующая сильно связному графу, является неприводимой матрицей, а все остальные матрицы в неотрицательной матрице являются приводимыми матрицами.

Данька объясняет на примере. (Для простоты объяснения все веса в примере являются единичными весами, но на практике эти значения весов могут быть любыми неотрицательными значениями.)

Далее этот граф, содержащий сильно связные компоненты, но сам не являющийся сильно связным, транскрибируется в соответствующую матричную форму:

И эта матрица является приводимой матрицей.

Видно, что две подматрицы на главной диагонали представляют собой два сильно связных компонента соответственно, в то время как подматрица в правом верхнем углу представляет собой ребро от первого сильно связного компонента ко второму сильно связному компоненту, а нижняя левая представляет собой Представляет ребро от 2-го сильно связного компонента до 1-го сильно связного компонента (поскольку такого ребра нет, все оно равно 0).

Такая форма записи блочной матрицы называется нормальной формой Фробениуса.

Итак, мы, естественно, задаемся вопросом: можем ли мы преобразовать любую неотрицательную матрицу в каноническую матрицу Фробениуса?

Используя ориентированный граф для представления неотрицательной матрицы, мы легко видим, что ответ — да, поскольку любой ориентированный граф, представляющий неотрицательную матрицу, может быть представлен как сильно связанные компоненты, связанные друг с другом. Процесс очень прост:

1. Построить соответствующие ориентированные графы для неотрицательных матриц;
2. Найдите сильно связанные компоненты;
3. Найдите лучший способ обозначить каждый узел.

И все готово!

Используйте графики, чтобы получить стандартную форму Фробениуса.

Итак, что это лучший способ?

На основе приведенного выше примера давайте посмотрим на процесс.

Сначала отдельные сильно связанные компоненты объединяются в единый объект, как показано на рисунке ниже. На данный момент мы можем рассматривать каждый сильносвязанный компонент как черный ящик — нас не волнует его внутренняя структура, а только его внешние связи.

Затем в этом новом графе нам нужно найти компоненты, у которых есть только исходящие ребра, но нет входящих ребер. В этом конкретном примере есть только один, который мы обозначим номером 0:

Следующий шаг более хлопотный: пронумеруйте каждый компонент так, чтобы номер каждого компонента находился как можно дальше от номера 0. Следующий пример иллюстрирует этот момент более наглядно:

Видно, что существует два пути от номера 0 до среднего компонента, поэтому выберите путь, самый дальний от 0, чтобы пронумеровать его. Наконец получил:

По сути, это определяет порядок компонентов. Далее разметьте внутренние узлы каждого компонента:

Если сам граф состоит из матрицы, такой процесс перемаркировки приводит к канонической матрице Фробениуса!

Фактически, этот процесс перемаркировки заключается в использовании матрицы перестановок P для преобразования исходной матрицы, а матрица перестановок состоит из произведения нескольких транспонированных матриц.

Ниже приводится полная форма теоремы:

Конечно, использование графов для представления матриц выходит далеко за рамки этого. Например, мы также можем использовать собственные значения матрицы для определения собственных значений графа. Фактически, этот образ мышления положил начало области исследований теории спектральных графов.

Заключение

Очевидно, что это отношение эквивалентности между матрицами и графами не только полезно для исследований в области теории графов, но и открывает новую перспективу для вычислений и анализа линейной алгебры. Он также имеет некоторые важные практические применения. Например, данные ДНК часто представляются в виде матрицы или графика.

Кроме того, мы все знаем о важности матричных операций для современных больших моделей ИИ, а графы, представленные графами знаний, становятся важной движущей силой современного ИИ благодаря таким технологиям, как поиск с расширенным поиском. Объединение этих двух технологий может привести к новым прорывам в области интерпретации ИИ и построения графиков искусственного интеллекта. По крайней мере, это помогает нам лучше изучать линейную алгебру.

Фактически, приведенное выше содержание взято из книги «Математика машинного обучения», написанной Тивадаром Данкой. Эта книга представит математические знания, связанные с машинным обучением, от простого до глубокого уровня, позволяя читателям по-настоящему понять, что это такое и почему это делается. Данка уверенно заявляет, что это будет «лучший ресурс для изучения машинного обучения». В настоящее время он опубликовал онлайн-превью двух глав. Заинтересованные читатели могут посетить: https://tivadardanka.com/mathematics-of-machine-learning-preview/.