Adelta: Автоматическое дифференцирование для прерывистых программ

В предыдущем посте мы представили набор новых градиентных правил, представленных в Aδ, которые позволяют автоматически дифференцировать программы с разрывами. Платформа автоматической дифференциации Aδ построена на основе предметно-ориентированного языка (DSL). Одним из ключевых преимуществ Aδ является широкий спектр программ, которые может отображать DSL. В этом посте мы продемонстрируем типы программ, выражаемых Aδ, и сравним их с двумя современными дифференцируемыми фреймворками: Teg² и Diffvg³.

Синтаксис DSL для Aδ

DSL включает основные операторы, такие как ступенчатая функция Хевисайда, сложение, умножение и композиция атомарных функций. Формально минимальный DSL можно выразить с помощью формы Бэкуса-Наура, как показано ниже:

Здесь C представляет постоянное скалярное значение, x представляет любые переменные, связанные с осью выборки (понятие, введенное в предыдущем посте), θпредставляет собой любые параметры, которые мы хотим дифференцировать относительно, а fпредставляет непрерывные атомарные функции, поддерживаемые в DSL (sin, cos, exp , log и pow с постоянным показателем степени).

Обратите внимание, что это минимальный набор операций для DSL, а другие базовые операции можно легко создать с помощью композиции функций. Например, g - h= g +(-1) ⋅ h и g / h= g ⋅(h)⁻¹.

DSL достаточно выразим, чтобы создавать сложные программы, которые можно было бы увидеть в реальной жизни, такие как программы процедурных шейдеров, способные отображать изображения, показанные ниже. Выразительность особенно важна для DSL, потому что, как правило, программисты могут создавать эквивалентные разрывные функции в разных программах, например H(x) и H (x) ⋅ H(x). Фреймворк Aδ выигрывает от выбора дизайна ядра предварительной фильтрации 1D box, поэтому нам не нужно аналитически определять точные прерывистые местоположения (подробности см. Предыдущий пост). Поэтому наша DSL допускает произвольные композиции между ступенчатой функцией Хевисайда и атомарными функциями.

Введение в другие современные дифференцируемые фреймворки

Teg² — это структура, которая систематически различает параметрические разрывы. Их система доказуемо верна для разрывных функций, выражаемых в их DSL. Тег аналитически вычисляет точное местоположение разрыва и на его основе выводит аналитический градиент. Процесс обнаружения разрыва включает в себя инвертирование параметрической функции, управляющей разрывом (т. е. входного аргумента ступенчатой функции Хевисайда), что, как правило, невозможно. Поэтому их DSL обрабатывает только ограниченный набор функций, которые являются дифференцируемыми и обратимыми. Это исключает композиции разрывов и необратимых функций. На рисунке ниже показаны два примера программ, которые можно выразить с помощью Teg. Первый пример — это триангуляция изображений, где разрывы всегда моделируются аффинными преобразованиями. Разрыв во втором примере моделируется билинейной интерполяцией и требует дополнительного преобразования евклидовой координаты в гиперболу перед дифференцированием.

Diffvg³ — это платформа для дифференцированного рендеринга в 2D-векторную графику. Технически это фреймворк для конкретного приложения, и большая часть его выразительности обусловлена огромным количеством параметров, а не сложной структурой программы. Но поскольку его реализация включает множество 2D-примитивов и дает пользователям некоторую свободу построения собственной сцены, мы также кратко обсудим класс функций, к которым можно применить Diffvg.

Дифференцируемая трассировка пути также является активным направлением исследований. Современные фреймворки³⁴⁵ выводят правильные аналитические производные и эффективно выполняют обратное распространение. Поскольку эти конвейеры ориентированы на конкретное приложение (трассировщик пути с треугольной сеткой) и мало адаптируются к другим программам, мы не будем их здесь обсуждать.

Примеры выражаемых функций

Мы будем использовать несколько примеров, чтобы сравнить выразительность Aδ с Teg и Diffvg. Обратите внимание, что для ясной демонстрации фрагмент кода, показанный в этом посте, является просто псевдокодом и не может быть напрямую вызван ни в одной из платформ. Исходный код указан под описанием каждого примера псевдокода. В следующем посте мы обсудим создание реального кода с использованием фреймворка Aδ. Кроме того, обратите внимание, что в приведенном ниже псевдокоде мы используем ветви if/else вместо пошаговых функций Хевисайда для удобочитаемости кода.

Круг: выражается через Aδ, Teg (с ручным усилием) и Diffvg

Мы можем начать с простого шейдера, рисующего круг:

В Aδ мы можем прямо выразить программу в ее евклидовых координатах:

Хотя Teg позволяет выразить шейдер круга аналогично Aδ в прямом проходе, он не может напрямую дифференцировать программу, поскольку выражение круга необратимо. Вместо этого в статье Teg предлагается выполнить дополнительное преобразование евклидовых координат в полярные, прежде чем программа сможет быть дифференцирована фреймворком. У этого есть очевидный недостаток: требуются дополнительные ручные усилия для выбора подходящего преобразования, которого может даже не быть.

В отличие от Aδ и Teg, Diffvg рисует примитив круга через заданный API, где внутренний рендерер заботится о рендеринге и дифференциации. Несмотря на простоту использования, Diffvg обладает ограниченной гибкостью, поскольку использует существующий API для предоставления примитивов и их производных, поэтому каждая новая форма должна быть реализована разработчиком инфраструктуры Diffvg.

Эллипс, не выровненный по оси: выражается через Aδ

Наш второй пример рисует эллипс, не выровненный по оси. В дополнение к параметрам, управляющим положением и радиусом эллипса, существуют параметры, управляющие направлением большой оси и соотношением между большой и малой осями.

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

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

Diffvg также нельзя использовать для удобного выражения этого примера с эллипсом. У него есть API для рисования эллипса, выровненного по оси, но ему не хватает гибкости для расширения на случай, не выровненный по оси. По-прежнему можно использовать Diffvg для аппроксимации произвольной геометрии с использованием многоугольных или сплайновых форм, что требует огромного количества параметров.

Окружности с параметризованным Z-порядком: выражается через Aδ

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

Aδ может гибко использовать прерывистые переменные в качестве входных аргументов для других прерывистых операций, что упрощает разработку шейдера:

Поскольку Teg требует, чтобы разрывы были параметризованы дифференцируемыми и обратимыми функциями, ясно, что приведенная выше программа не может быть реализована в Teg, поскольку она включает в себя композиции разрывов. Однако можно рекурсивно разложить композиции разрывов на умножения разрывов (аналогично переписыванию вложенных ветвей if/else в один гигантский оператор switch). Если далее переписанная программа такова, что каждая непрерывная программа, управляющая каждым разрывом, дифференцируема и обратима, то она будет выражаться в Teg с двумя дополнительными недостатками. Во-первых, для дополнительной перезаписи требуется ручное усилие. Хотя можно реализовать компилятор, который автоматически применяет переписывание, он недоступен, и неясно, может ли переписывание, сгенерированное компилятором, быть оптимизировано так же, как переписывание, созданное человеческим опытом. Во-вторых, поскольку это комбинаторный подход, количество разрывов после перезаписи будет расти экспоненциально. Поскольку временная сложность градиентной программы увеличивается с количеством вводимых разрывов, такая переписывание также будет экспоненциально увеличивать временную сложность градиентной программы.

Diffvg не может выразить приведенный выше пример, потому что его структура допускает только заданный пользователем постоянный порядок Z. Поэтому в приведенном выше примере пользователю нужно указать, что либо синий кружок всегда находится поверх красного, либо наоборот. Но это многоуровневое отношение не может быть параметризовано и дополнительно исследовано оптимизатором.

Ограничения DSL Aδ

Поскольку DSL в рамках Aδ не является полным по Тьюрингу, он не может выражать произвольные программы, которые встречаются в реальном программировании. Например, Aδ не может обрабатывать циклы с неопределенным числом итераций и вместо этого должен разворачивать циклы до максимально возможного числа итераций. Кроме того, в Aδ пока нет механизма обработки операций разброса и сбора. В некоторых простых случаях операция сбора может быть жестко запрограммирована как композиция функций выбора на основе индекса поиска, но в целом такие операции пока не поддерживаются.

Краткое содержание

Мы представили DSL для платформы Aδ. Благодаря нашей структуре дифференциации, которая отбирает разрывы на основе пар выборок, а не точно вычисляет местоположение разрыва, Aδ может гибко выражать широкий спектр программ с шаблонами разрывов, которые представляют такую же сложность, как и программы, созданные программистами.

В отличие от Aδ, Teg больше фокусируется на создании доказуемо правильных градиентных программ и жертвует выразительностью своего DSL. В результате их структура может либо выражать разрывы только с помощью простых обратимых и дифференцируемых функций, таких как аффинные преобразования, либо требует дополнительных ручных усилий по переписыванию программы, либо находит подходящее преобразование координат, позволяющее применить их дифференцирование.

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

Следующим постом будет учебник по использованию кодовой базы Aδ.

Ссылка

[1] Aδ: Autodiff для прерывистой программы — применяется к шейдерам [страница проекта]

[2] Систематическая дифференциация параметрических разрывов [страница проекта]

[3] Дифференцируемая растеризация векторной графики для редактирования и обучения [страница проекта]

[4] Беспристрастная выборка искаженной области для дифференцированного рендеринга [страница проекта]

[5] Перепараметризация разрывных интегралов для дифференцируемого рендеринга [страница проекта]

[6] Дифференцируемый рендеринг в пространстве путей [страница проекта]

Adelta: Автоматическое дифференцирование для прерывистых программ — Часть 2: Объем выражаемых…