От классических полиномов к глубокому обучению

Исторически вычислительная математика опиралась на полиномы, сплайны и тригонометрические ряды для аппроксимации сложных функций. Однако в последние годы произошел тектонический сдвиг: искусственные нейронные сети (ИНС) доказали свою эффективность как мощный инструмент вычислительной математики. Теорема Цыбенко (и универсальная теорема аппроксимации) гласит, что нейросеть прямого распространения даже с одним скрытым слоем может аппроксимировать любую непрерывную функцию с наперед заданной точностью, при условии достаточного количества нейронов. Развитие глубокого обучения (Deep Learning) и алгоритмов обратного распространения ошибки позволило настраивать миллионы параметров, создавая невероятно гибкие математические модели.

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

Физически информированные нейросети (PINNs)

Настоящей революцией в численном решении дифференциальных уравнений в частных производных (УЧП) стало появление физически информированных нейронных сетей (Physics-Informed Neural Networks, PINNs). Идея PINN заключается во внедрении физических законов (самих дифференциальных уравнений) непосредственно в функцию потерь (Loss function) нейронной сети во время ее математического обучения.

Алгоритм работает следующим образом. Нейросеть принимает на вход координаты пространства и времени, а на выходе выдает предсказание физической величины (например, скорости потока или давления). Чтобы сеть обучилась правильной физике, функция потерь состоит из двух частей. Первая часть штрафует сеть за несовпадение с заданными граничными и начальными условиями. Вторая, самая главная часть, подставляет выходные данные сети в аналитическое дифференциальное уравнение (например, Навье-Стокса). Производные по координатам вычисляются абсолютно точно и невероятно быстро с помощью графов автоматического дифференцирования (Autograd), встроенных в тензорные процессоры. Если предсказанная функция не удовлетворяет уравнению, возникает невязка, за которую сеть получает огромный штраф. Оптимизатор настраивает веса так, чтобы свести эту невязку к нулю. В результате получается полностью бессеточное аналитическое решение УЧП, способное решать обратные задачи с беспрецедентной легкостью.

Экономия памяти в гигантских системах

В задачах математического моделирования, о которых мы многократно упоминали (метод конечных элементов для прочностных расчетов, метод конечных разностей в гидродинамике, расчет графов в социальных сетях), возникают матрицы колоссальных размеров. Матрица системы из миллиона уравнений содержит триллион элементов. Если попытаться сохранить ее в оперативной памяти компьютера в обычном плотном двумерном формате (каждое число типа double precision занимает 8 байт), потребуется 8 терабайт оперативной памяти! Таких ресурсов нет у обычных серверов.

Однако природа приходит на помощь. Матрицы, возникающие при моделировании физических процессов, являются сверхразреженными. Это означает, что 99,99% элементов в такой матрице — это нули. Каждое уравнение связывает только несколько соседних физических узлов. Хранить миллиарды нулей в памяти и умножать на них (тратя процессорное время впустую) — невероятная глупость. Поэтому в вычислительной линейной алгебре разработаны специализированные форматы упаковки и хранения данных, которые игнорируют нули, радикально сжимая объем требуемой памяти.

Координатный формат (COO)

Самым интуитивно понятным и простым способом сохранения разреженной матрицы является координатный формат (Coordinate format, COO). В этом формате матрица хранится в виде трех одномерных массивов одинаковой длины (равной количеству ненулевых элементов, NNZ). Первый массив хранит сами значения (ненулевые числа). Второй массив хранит индексы строк для этих значений. Третий массив хранит индексы столбцов.

Например, если число 5.4 находится во 2-й строке и 3-м столбце, то в массив значений пишется 5.4, в массив строк — 2, в массив столбцов — 3. Этот формат великолепно подходит для первоначальной сборки матрицы по частям (например, при агрегации конечных элементов), так как в него очень легко добавлять новые числа. Однако для быстрого матричного умножения он не является оптимальным из-за недостаточной структурированности.

Форматы сжатого хранения строк (CSR) и столбцов (CSC)

Индустриальным стандартом для быстрых вычислений (решения СЛАУ и умножения матрицы на вектор) стал Формат Сжатого Хранения Строк (Compressed Sparse Row, CSR). Этот формат также использует три одномерных массива, но упаковывает индексы строк гораздо умнее, чем COO. Массив значений и массив индексов столбцов остаются такими же (хранятся элементы, перебираемые слева направо и сверху вниз). Но массив строк заменяется на массив «указателей на начало строк» (row_ptr).

Массив row_ptr имеет размер, равный количеству строк в матрице плюс один. Каждый элемент этого массива показывает, на каком индексе в массиве значений начинается новая строка матрицы. Вычисляя разность между соседними элементами массива row_ptr, компьютер мгновенно узнает, сколько ненулевых элементов содержится в конкретной строке. Это обеспечивает феноменально быстрый доступ к элементам при умножении. Абсолютно симметричным является Формат Сжатого Хранения Столбцов (Compressed Sparse Column, CSC), где сжимаются индексы столбцов, а элементы записываются сверху вниз и слева направо. CSR оптимизирован для умножения y = A*x, а CSC — для y = A^T*x. Все современные библиотеки линейной алгебры (Intel MKL, SciPy.sparse, cuSPARSE на видеокартах) построены на глубокой аппаратной оптимизации этих форматов упаковки.

Проблема нестационарности в цифровой обработке сигналов

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

Однако большинство реальных сигналов в природе и технике являются нестационарными. Мелодия состоит из нот, которые звучат последовательно. Человеческая речь — это чередование согласных и гласных звуков с разным спектром. Землетрясение имеет четкое начало, фазу максимальных разрушений и затухание. Если мы применим классическое преобразование Фурье к 10-секундной аудиозаписи песни, мы получим один усредненный спектр. Этот спектр покажет нам все ноты, которые присутствовали в песне, но он абсолютно ничего не скажет о том, когда именно была сыграна каждая нота. Мы теряем информацию о времени. Для решения этой фундаментальной проблемы было изобретено Оконное преобразование Фурье (Short-Time Fourier Transform, STFT).

Скользящее окно: компромисс между временем и частотой

Идея оконного преобразования Фурье логична и проста. Вместо того чтобы анализировать весь сигнал целиком от минус бесконечности до плюс бесконечности, мы разрезаем его на короткие временные сегменты (кадры). Для этого исходный сигнал умножается на специальную функцию, называемую окном (window function), которая не равна нулю только на небольшом отрезке времени.

Затем к этому вырезанному кусочку сигнала применяется стандартное преобразование Фурье. Мы получаем спектр для этого конкретного момента времени. Затем окно сдвигается немного вправо (часто с перекрытием предыдущего кадра, чтобы избежать артефактов на краях), и процедура повторяется. В результате вместо одномерного графика спектра мы получаем двумерный массив чисел (или трехмерный график). По одной оси откладывается время, по другой — частота, а цвет или высота точки обозначает амплитуду (мощность) сигнала. Такое визуальное представление называется спектрограммой, и оно является главным инструментом фонетиков, радиотехников и звукорежиссеров.

Весовые окна и предел Габора (принцип неопределенности)

На практике просто грубо обрезать сигнал (прямоугольное окно) нельзя. Это порождает резкие скачки на краях кадра, что по законам математики приводит к размазыванию спектра (эффект спектральной утечки — spectral leakage). Поэтому инженеры используют гладкие весовые окна (окна Ханна, Хэмминга, Блэкмана), которые плавно сводят амплитуду сигнала к нулю на краях кадра, минимизируя искажения.

Однако оконное преобразование Фурье имеет жесткое физико-математическое ограничение, аналогичное квантовому принципу неопределенности Гейзенберга. Оно известно как предел Габора. Суть его в том, что мы не можем одновременно получить идеальное разрешение и по времени, и по частоте. Если мы возьмем короткое временное окно, мы будем точно знать, когда произошло событие, но спектр станет размытым (плохое частотное разрешение). Если мы возьмем длинное окно, мы получим идеальное разрешение по частоте (точно отличим близкие ноты), но размоем сигнал во времени (потеряем резкость быстрых ударов барабана). Инженеру всегда приходится искать компромисс, подбирая размер окна под конкретную задачу, что и послужило стимулом для дальнейшего развития вейвлет-анализа.