Нейросеть превзошла математиков, найдя неизвестный алгоритм умножения
Исследователи из Google DeepMind показали, что ИИ может находить более быстрые алгоритмы для решения задачи умножения матриц, чем до сих пор нашли математики. Задача перемножения матриц — одна из самых трудоемких вычислительных проблем ИИ. Для поиска алгоритма умножения задача была переформулирована в игру и превзошла математиков.
Владимир Губайловский
Нейросети учатся ускорять свою работу
Матрица — это прямоугольная таблица чисел. Первые алгоритмы работы с матрицами были разработаны в древнем Китае 4 тысячи лет назад. Активное использование матриц для решения систем линейных уравнений началось в XVII — XVIII веках. Эта техника удобна, но для больших числовых таблиц очень трудоемка, и любое ускорение критически важно для вычислительной математики, в том числе для работы нейросетей.
Группа исследователей из Google DeepMind в Лондоне обнаружила, что ИИ может найти более быстрые алгоритмы для решения задачи умножения матриц.
Матрицы
Математика постоянно используется в компьютерных вычислениях, как средство формального описания реального мира. Например, матрицы используются для представления пикселей на экране компьютера, погодных условий или узлов нейросети. Одним из основных алгоритмов в таких случаях является выполнение вычислений над матрицами. Например, при программировании игр матрицы описывают возможные варианты движения. Для реализации таких движений матрицы часто перемножаются или складываются. Это требует большой вычислительной мощности, и чем больше матрицы — тем труднее с ними работать. Математики тратят много времени и энергии на разработку все более и более эффективных алгоритмов матричных вычислений.
В 1969 году математик Фолькер Штрассен нашел способ перемножать две матрицы 2×2, используя всего семь операций умножения вместо восьми, которые были стандартом.
Поскольку перемножение любых матриц можно свести к перемножению блоков 2×2, этот алгоритм на сегодня является основным вычислительным средством, которое используется в компьютерной математике.ИИ ускоряет ИИ
В этой новой работе исследователи из DeepMind задались вопросом, можно ли использовать систему искусственного интеллекта, основанную на обучении с подкреплением, для создания новых алгоритмов с меньшим количеством шагов, чем те, которые используются сейчас. Чтобы выяснить это, они обратились к игровым системам. Команда сосредоточилась на поиске по дереву, который обычно используется в программировании игр. Это средство, с помощью которого система может перебирать различные сценарии в поисках наилучшего. Такой подход дал отличный результат. Преобразование системы искусственного интеллекта в игру позволило отыскать более эффективный способ для перемножения матриц, чем до сих пор нашли математики. А ведь математики работают с матрицами очень давно и всегда хотели сделать работу с матрицами более быстрой.
Исследователи DeepMind позволили своей системе искать, просматривать и затем использовать существующие алгоритмы, используя вознаграждения за более короткие и быстрые способы перемножения. В результате система нашла факторы, влияющие на эффективность матричного умножения. Затем исследователи позволили системе создать собственный алгоритм. И она создала. Во многих случаях алгоритмы, выбранные системой, были лучше, чем те, которые были созданы математиками.
Теперь эту систему можно использовать для поиска самых разных быстрых алгоритмов во многих областях вычислительной математики.
Пушмит Кохли, соавтор работы сказал журналу Nature о работе нейросети: «У нее потрясающая интуиция, когда она играет в эти игры. Это не интуиция человека, и в некотором смысле ИИ должен создавать свои собственные знания о проблеме с нуля».
Построение и анализ вычислительных алгоритмов
Построение и анализ вычислительных алгоритмов
ОглавлениеПРЕДИСЛОВИЕМОДЕЛИ ВЫЧИСЛЕНИЙ 1.1. АЛГОРИТМЫ И ИХ СЛОЖНОСТИ 1.2. МАШИНЫ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ К ПАМЯТИ 1.3. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ РАМ-ПРОГРАММ 1.4. МОДЕЛЬ С ХРАНИМОЙ ПРОГРАММОЙ 1.  5. МОДИФИКАЦИЯ РАМ1.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА 1.7. СВЯЗЬ МАШИН ТЬЮРИНГА И РАМ 1.8. ЯЗЫК ВЫСОКОГО УРОВНЯ — УПРОЩЕННЫЙ АЛГОЛ 2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ 2.1. СТРУКТУРЫ ДАННЫХ: СПИСКИ, ОЧЕРЕДИ И СТЕКИ 2.2. ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ 2.3. ГРАФЫ 2.4. ДЕРЕВЬЯ 2.5. РЕКУРСИЯ 2.6. РАЗДЕЛЯЙ И ВЛАСТВУЙ 2.7. БАЛАНСИРОВКА 2.8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 2.9. ЭПИЛОГ 3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ 3.1. ЗАДАЧА СОРТИРОВКИ 3.2. ЦИФРОВАЯ СОРТИРОВКА 3.3. СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ 3.4. СОРТДЕРЕВОМ — УПОРЯДОЧЕНИЕ С ПОМОЩЬЮ O(n log n) СРАВНЕНИЙ 3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ O(n log n) 3.6. ПОРЯДКОВЫЕ СТАТИСТИКИ 3.7. СРЕДНЕЕ ВРЕМЯ ДЛЯ ПОРЯДКОВЫХ СТАТИСТИК 4. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ 4.2. МЕТОД РАССТАНОВКИ 4.3. ДВОИЧНЫЙ ПОИСК 4.4. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА 4.5. ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА 4.6. ПРОСТОЙ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ ОБЪЕДИНЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ МНОЖЕСТВ  7. ДРЕВОВИДНЫЕ СТРУКТУРЫ ДЛЯ ЗАДАЧИ ОБЪЕДИНИТЬ — НАЙТИ4.8. ПРИЛОЖЕНИЯ И ОБОБЩЕНИЯ АЛГОРИТМА ОБЪЕДИНИТЬ — НАЙТИ 4.9. СХЕМЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ 4.10. СЛОВАРИ И ОЧЕРЕДИ С ПРИОРИТЕТАМИ 4.11. СЛИВАЕМЫЕ ДЕРЕВЬЯ 4.12. СЦЕПЛЯЕМЫЕ ОЧЕРЕДИ 4.13. РАЗБИЕНИЕ 4.14. РЕЗЮМЕ 5. АЛГОРИТМЫ НА ГРАФАХ 5.1. ОСТОВНОЕ ДЕРЕВО НАИМЕНЬШЕЙ СТОИМОСТИ 5.2. МЕТОД ПОИСКА В ГЛУБИНУ 5.3. ДВУСВЯЗНОСТЬ 5.4. ПОИСК В ГЛУБИНУ В ОРИЕНТИРОВАННОМ ГРАФЕ 5.5. СИЛЬНАЯ СВЯЗНОСТЬ 5.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ 5.7. АЛГОРИТМ ТРАНЗИТИВНОГО ЗАМЫКАНИЯ 5.8. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ 5.9. ЗАДАЧИ О ПУТЯХ И УМНОЖЕНИЕ МАТРИЦ 5.10. ЗАДАЧИ С ОДНИМ ИСТОЧНИКОМ 5.11. ДОМИНАТОРЫ В ОРИЕНТИРОВАННЫХ АЦИКЛИЧЕСКИХ ГРАФАХ: КОМБИНИРОВАНИЕ ПОНЯТИЙ 6. УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ 6.2. АЛГОРИТМ ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ 6.3. ОБРАЩЕНИЕ МАТРИЦ 6.4. НВП-РАЗЛОЖЕНИЕ МАТРИЦЫ 6.5. ПРИЛОЖЕНИЯ НВП-РАЗЛОЖЕНИЯ 6.6. УМНОЖЕНИЕ БУЛЕВЫХ МАТРИЦ 7.  БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ7.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 7.3. БПФ ПРИ ИСПОЛЬЗОВАНИИ БИТОВЫХ ОПЕРАЦИЙ 7.4. ПРОИЗВЕДЕНИЕ ПОЛИНОМОВ 7.5. АЛГОРИТМ ШЕНХАГЕ — ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ 8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ 8.1. АНАЛОГИИ МЕЖДУ ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ 8.2. УМНОЖЕНИЕ И ДЕЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ 8.3. УМНОЖЕНИЕ И ДЕЛЕНИЕ ПОЛИНОМОВ 8.4. МОДУЛЬНАЯ АРИФМЕТИКА 8.5. МОДУЛЬНАЯ АРИФМЕТИКА ПОЛИНОМОВ И ВЫЧИСЛЕНИЕ ИХ ЗНАЧЕНИЙ 8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ 8.7. КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ И ИНТЕРПОЛЯЦИЯ ПОЛИНОМОВ 8.8. НАИБОЛЬШИЕ ОБЩИЕ ДЕЛИТЕЛИ И АЛГОРИТМ ЕВКЛИДА 8.10. НОД ЦЕЛЫХ ЧИСЕЛ 8.11. ЕЩЕ РАЗ О ПРИМЕНЕНИИ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ 8.12. РАЗРЕЖЕННЫЕ ПОЛИНОМЫ 9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ 9.1. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 9.2. РАСПОЗНАВАНИЕ ОБРАЗОВ, ЗАДАВАЕМЫХ РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ 9.  3. РАСПОЗНАВАНИЕ ПОДЦЕПОЧЕК9.4. ДВУСТОРОННИЙ ДЕТЕРМИНИРОВАННЫЙ МАГАЗИННЫЙ АВТОМАТ 9.5. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ И ИДЕНТИФИКАТОРЫ ПОЗИЦИЙ 10. NP-ПОЛНЫЕ ЗАДАЧИ 10.1. НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА 10.2. КЛАССЫ … 10.3. ЯЗЫКИ И ЗАДАЧИ 10.4. NP-ПОЛНОТА ЗАДАЧИ ВЫПОЛНИМОСТИ 10.5. ЕЩЕ НЕСКОЛЬКО NP-ПОЛНЫХ ЗАДАЧ 10.6. ЗАДАЧИ С ПОЛИНОМИАЛЬНО ОГРАНИЧЕННОЙ ПАМЯТЬЮ 11. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ 11.2. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН ТЬЮРИНГА 11.3. ЗАДАЧА, ТРЕБУЮЩАЯ ЭКСПОНЕНЦИАЛЬНЫХ ВРЕМЕНИ И ПАМЯТИ 11.4. НЕЭЛЕМЕНТАРНАЯ ЗАДАЧА 12. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ 12.2. ЕЩЕ РАЗ О НЕВЕТВЯЩИХСЯ ПРОГРАММАХ 12.3. МАТРИЧНАЯ ФОРМУЛИРОВКА ЗАДАЧ 12.4. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТРОКАМ 12.5. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТОЛБЦАМ 12.6. ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАССМОТРЕНИЕМ СТРОК И СТОЛБЦОВ 12.7. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА |
Построение и анализ вычислительных алгоритмов. Изд-во «Мир», М., 1979 г.
Алгоритм умножения матриц Время Сложность
1.
ОбзорУмножение матриц — важная операция в математике. Это базовый инструмент линейной алгебры, который имеет широкий спектр приложений в нескольких областях, таких как физика, инженерия и экономика.
В этом уроке мы обсудим два популярных алгоритма умножения матриц: наивное умножение матриц и алгоритм Солве-Штрассена. Мы также представим анализ временной сложности каждого алгоритма.
2. Введение в умножение матриц
Берем две матрицы и порядка и . Посмотрим на матрицы:
,
Теперь, когда мы умножаем матрицу на матрицу, мы получаем другую матрицу — назовем ее. Порядок матрицы будет .
Давайте теперь рассмотрим элементы матрицы:
.
Каждая запись в матрице может быть вычислена из записей матрицы и путем нахождения попарного суммирования:
3. Свойства умножения матриц
Позвольте , и быть три матрицы одинаковых размеров.
По ассоциативности при умножении можно написать . Это свойство указывает, что мы можем изменить группировку, окружающую умножение матриц, и это не повлияет на результат умножения матриц.
Мы можем распределить матрицы так же, как мы распределяем действительные числа. Используя распределительное свойство при умножении, мы можем написать: .
Существуют специальные матрицы, называемые единичными матрицами или единичными матрицами, которые имеют на главной диагонали и в других местах. Некоторые примеры матриц идентичности:
, ,
Умножение матриц имеет очень интересное свойство. Когда матрица умножается справа на единичную матрицу , выходная матрица будет такой же, как матрица . Это свойство называется мультипликативной идентичностью. Например:
Важно отметить, что умножение матриц не является коммутативным. Допустим, мы умножаем две матрицы и того же порядка тогда .
Это общий случай. Но если и обе являются диагональными матрицами и имеют одинаковые размеры, они обладают свойством коммутативности.
4. Наивный алгоритм умножения матриц
4.1. Псевдокод
Давайте сначала посмотрим на псевдокод наивного алгоритма умножения матриц, а затем обсудим шаги алгоритма:
Алгоритм перебирает все элементы и , и самый внешний цикл заполняет результирующую матрицу .
Чтобы найти его реализацию, мы можем посетить нашу статью о умножении матриц в Java.
4.2. Анализ временной сложности
Наивный алгоритм умножения матриц содержит три вложенных цикла. Для каждой итерации внешнего цикла общее количество прогонов внутренних циклов будет эквивалентно длине матрицы. Здесь целочисленные операции требуют времени. В общем, если длина матрицы , общая временная сложность будет .
Теперь вопрос в том, можем ли мы улучшить временную сложность матричного умножения? Мы обсудим улучшенный алгоритм умножения матриц в следующем разделе.
5. Алгоритм Солве Штрассена
5.1. Алгоритм
В 1969 году Фолькер Штрассен добился значительного прогресса, доказав, что сложность не является оптимальной, выпустив новый алгоритм, названный в его честь.
Там, где наивный метод использует исчерпывающий подход, алгоритм Стассена использует стратегию «разделяй и властвуй» вместе с хорошим математическим трюком для решения задачи умножения матриц с минимальными вычислениями.
Возьмем две входные матрицы и порядка . В общем, размер входных матриц будет:
,
Первым шагом является разделение каждой входной матрицы на четыре подматрицы порядка :
Следующим шагом является выполнение 10 операции сложения/вычитания:
Третий шаг алгоритма состоит в том, чтобы вычислить 7 операций умножения рекурсивно, используя предыдущие результаты.
Здесь каждый имеет размер:
Наконец, желаемые подматрицы результирующей матрицы могут быть вычислены путем сложения и вычитания различных комбинаций подматриц :
Теперь соберем все вместе в матричной форме:
Итак, как мы видим, этот алгоритм должен выполнять операции умножения, в отличие от простого алгоритма, который требует операций умножения.
Важно отметить, что этот алгоритм работает только на квадратных матрицах одинаковой размерности.
5.2. Анализ временной сложности
Это решение основано на рекурсии. На первом этапе мы делим входные матрицы на подматрицы размера . Этот шаг может быть выполнен в раз.
На шаге мы вычисляем операции сложения/вычитания, что требует времени.
На шаге мы делаем рекурсивные вызовы для вычисления . Результатом этого шага будет матрица порядка. Этот шаг требует времени.
Наконец, путем сложения и вычитания подматриц , мы получаем результирующую матрицу . Временная сложность этого шага будет .
Следовательно, общая временная сложность этого алгоритма будет:
6. Сравнение двух алгоритмов
Давайте суммируем два алгоритма умножения матриц в этом разделе и сведем ключевые моменты в таблицу:
7. Заключение
В этом руководстве мы подробно обсудили два алгоритма умножения матриц: наивный метод и алгоритм Солве-Штрассена.
Мы также представили сравнение, включая ключевые моменты этих двух алгоритмов.
Алгоритм Штрассена для умножения матриц
спросил
Изменено 10 лет, 1 месяц назад
Просмотрено 26 тысяч раз
Может ли кто-нибудь объяснить алгоритм Штрассена для умножения матриц интуитивно понятным способом? Я прошел (ну, попытался пройти) объяснение в книге и вики, но это не щелкает наверху.
Любые ссылки в Интернете, которые используют много английского языка, а не формальной нотации и т. Д., Также будут полезны. Есть ли какие-то аналогии, которые могли бы помочь мне построить этот алгоритм с нуля, не запоминая его?
- алгоритм
- матрица
- умножение
- штрассен
2
Рассмотрим перемножение двух матриц 2×2 следующим образом:
A B * E F = AE+BG AF+BH C D G H CE+DG CF+DH
Очевидный способ вычислить правую часть — просто выполнить 8 умножений и 4 сложения. Но представьте, что умножения намного дороже, чем сложения, поэтому мы хотим уменьшить количество умножений, если это вообще возможно. Штрассен использует трюк, чтобы вычислить правую часть с одним меньшим умножением и гораздо большим количеством сложений (и некоторых вычитаний).
Вот 7 умножений:
M1 = (A + D) * (E + H) = AE + AH + DE + DH М2 = (А + В) * Н = АХ + ВН M3 = (C + D) * E = CE + DE M4 = A * (F - H) = AF - AH M5 = D * (G - E) = DG - DE M6 = (C - A) * (E + F) = CE + CF - AE - AF M7 = (B - D) * (G + H) = BG + BH - DG - DH
Таким образом, чтобы вычислить AE+BG, начните с M1+M7 (что дает нам термины AE и BG), затем добавьте/вычтите некоторые другие M, пока не останется только AE+BG.
Чудесным образом M выбраны так, что работают M1+M7-M2+M5. То же самое с другими 3 требуемыми результатами.
Теперь поймите, что это работает не только для матриц 2×2, но и для матриц любого (четного) размера, где A..H являются подматрицами.
1
На мой взгляд, есть 3 идеи, которые вам нужно получить:
Вы можете разбить матрицу на блоки и работать с полученной матрицей блоков так же, как с матрицей чисел. В частности, вы можете перемножить две такие блочные матрицы (конечно, если количество блочных строк в одной совпадает с количеством блочных столбцов в другой) и получить тот же результат, что и при умножении исходных матриц чисел.
Блоки, необходимые для выражения результата умножения блочной матрицы 2×2, имеют достаточно общих множителей, чтобы их можно было вычислить за меньшее число умножений, чем предполагает исходная формула. Это трюк, описанный в ответе Тони.
Рекурсия.
