Вероятностные числа

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

Введение

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

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

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

Вероятностные численные методы обещают несколько концептуальных преимуществ по сравнению с классическими методами аппроксимации, основанными на точечных оценках:

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

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

Числовые задачи

Интеграция

Основная статья: байесовская квадратура

Байесовская квадратура с гауссовским процессом, обусловленным $n=0,3,\ {\text{and}}\ 8$ оценки подынтегральной функции (показаны черным цветом). Заштрихованные области в левом столбце иллюстрируют предельные стандартные отклонения. На правом рисунке показан предшествующий ( $n=0$) и задний ( $n=3,8$) Распределение Гаусса по значению интеграла, а также истинное решение.

были разработаны вероятностные численные методы Для решения задач численного интегрирования , наиболее популярный из которых называется байесовской квадратурой .

При численном интегрировании оценки функций $f(x_{1}),\ldots ,f(x_{n})$ в ряде точек $x_{1},\ldots ,x_{n}$ используются для оценки интеграла $\textstyle \int f(x)\nu (dx)$ функции $f$ против какой-то меры $\nu$. Байесовская квадратура состоит из указания предварительного распределения по $f$ и обусловливаем это предварительно $f(x_{1}),\ldots ,f(x_{n})$ чтобы получить апостериорное распределение по $f$, затем вычисляем подразумеваемое апостериорное распределение на $\textstyle \int f(x)\nu (dx)$. Наиболее распространенным выбором априора является гауссов процесс , поскольку он позволяет нам получить апостериорное распределение замкнутой формы для интеграла, которое является одномерным гауссовским распределением. Байесовская квадратура особенно полезна, когда функция $f$ оценить дорого, а размер данных от малого до среднего.

Оптимизация

См. Также: Байесовская оптимизация.

Байесовская оптимизация функции (черный) с гауссовскими процессами (фиолетовый). Внизу показаны три функции сбора данных (синие).

Вероятностные числа также изучались для математической оптимизации , которая заключается в поиске минимума или максимума некоторой целевой функции. $f$ заданные (возможно, зашумленные или косвенные) оценки этой функции в наборе точек.

Возможно, наиболее заметной попыткой в ​​этом направлении является байесовская оптимизация . общий подход к оптимизации, основанный на байесовском выводе. Алгоритмы байесовской оптимизации работают, сохраняя вероятностное представление о $f$ на протяжении всей процедуры оптимизации; это часто принимает форму гауссовского процесса, заранее обусловленного наблюдениями. Это убеждение затем направляет алгоритм при получении наблюдений, которые могут способствовать продвижению процесса оптимизации. Политики байесовской оптимизации обычно реализуются путем преобразования апостериорной целевой функции в недорогую дифференцируемую функцию сбора данных , которая максимизируется для выбора каждого последующего места наблюдения. Одним из известных подходов является моделирование оптимизации с помощью байесовского последовательного экспериментального планирования , стремящегося получить последовательность наблюдений, дающую наибольший прогресс оптимизации, оцениваемый соответствующей функцией полезности . Положительным побочным эффектом этого подхода является то, что неопределенность в целевой функции, измеряемая лежащим в ее основе вероятностным убеждением, может определять политику оптимизации при решении классического компромисса между разведкой и эксплуатацией .

Локальная оптимизация

Вероятностные численные методы были разработаны в контексте стохастической оптимизации для глубокого обучения , в частности, для решения таких основных проблем, как настройка скорости обучения и поиск строк , выбор размера партии, ранняя остановка , обрезка, и направления поиска первого и второго порядка.

В этой ситуации целью оптимизации часто является эмпирический риск в форме $\textstyle L(\theta )={\frac {1}{N}}\sum _{n=1}^{N}\ell (y_{n},f_{\theta }(x_{n}))$ определяется набором данных $\textstyle {\mathcal {D}}=\{(x_{n},y_{n})\}_{n=1}^{N}$, и потеря $\ell (y,f_{\theta }(x))$ это количественно определяет, насколько хорошо прогнозирующая модель $f_{\theta }(x)$ параметризованный $\theta$ выполняет прогнозирование цели $y$ из соответствующего входа $x$ .Эпистемическая неопределенность возникает, когда размер набора данных $N$ велик и не может быть обработан сразу, а это означает, что локальные количества (при наличии некоторых $\theta$), например, функция потерь $L(\theta )$ сам по себе или его градиент $\nabla L(\theta )$ невозможно вычислить за разумное время.Следовательно, обычно мини-пакетная обработка используется для построения оценок этих величин на случайном подмножестве данных. Вероятностные численные методы явно моделируют эту неопределенность и позволяют автоматически принимать решения и настраивать параметры.

Линейная алгебра

Вероятностные численные методы линейной алгебры в первую очередь сосредоточились на решении систем линейных уравнений вида $Ax=b$ и вычисление определителей $|A|$.

Иллюстрация вероятностного линейного решателя на основе матрицы.

Большой класс методов носит итеративный характер и собирает информацию о линейной системе, подлежащей решению, путем многократного умножения матрицы на вектор. $v\mapsto Av$ с системной матрицей $A$ с разными векторами $v$. Такие методы можно грубо разделить на решения: и матричная перспектива, в зависимости от того, выражена ли вера в решение $x$ линейной системы или (псевдо)обратной матрицы $H=A^{\dagger }$. Обновление убеждений использует то, что выведенный объект связан с матричными умножениями. $y=Av$ или $z=A^{\intercal }v$ с помощью $b^{\intercal }z=x^{\intercal }v$ и $v=A^{-1}y$.Методы обычно предполагают распределение Гаусса из-за его замкнутости при линейном наблюдении задачи. Хотя эти два представления концептуально различны, они вычислительно эквивалентны и по своей сути связаны через правую часть через $x=A^{-1}b$.

Вероятностные численные процедуры линейной алгебры успешно применяются для масштабирования гауссовских процессов на большие наборы данных. В частности, они обеспечивают точное распространение ошибки аппроксимации на апостериорную совокупность гауссовского процесса, что количественно определяет неопределенность, возникающую как из-за данных конечного числа наблюдаемых , так и из-за конечного объема затраченных вычислений .

Обыкновенные дифференциальные уравнения

Выборки первой компоненты численного решения системы Лоренца, полученные с помощью вероятностного численного интегратора.

Вероятностно-численные методы для решения обыкновенных дифференциальных уравнений ${\dot {y}}(t)=f(t,y(t))$, разработаны для начальных и краевых задач. Было предложено множество различных вероятностных численных методов, разработанных для обыкновенных дифференциальных уравнений, и их можно в целом сгруппировать в две следующие категории:

• Методы, основанные на рандомизации, определяются посредством случайных возмущений стандартных детерминированных численных методов для обыкновенных дифференциальных уравнений. Например, это было достигнуто за счет добавления гауссовых возмущений к решению одношаговых интеграторов. или путем случайного изменения их временного шага. Это определяет вероятностную меру решения дифференциального уравнения, которое может быть выбрано.
• Методы регрессии гауссовского процесса основаны на постановке задачи решения рассматриваемого дифференциального уравнения как задачи регрессии гауссовского процесса, интерпретируя оценки правой части как данные о производной. Эти методы напоминают байесовскую кубатуру, но используют разные и часто нелинейные модели наблюдения. В зачаточном состоянии этот класс методов был основан на наивной регрессии гауссовского процесса . Позже это было улучшено (с точки зрения эффективных вычислений) в пользу априорных подходов Гаусса – Маркова. моделируется стохастическим дифференциальным уравнением $\mathrm {d} x(t)=Ax(t)\,\mathrm {d} t+B\,\mathrm {d} v(t)$, где $x(t)$ это $\nu$-мерное векторное моделирование первого $\nu$ производные от $y(t)$, и где $v(t)$ это $\nu$-мерное броуновское движение . Таким образом, вывод может быть эффективно реализован с помощью методов, основанных на фильтрации Калмана .

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

Уравнения в частных производных

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

Учимся решать уравнения в частных производных. Предварительный гауссов процесс для конкретной задачи $u$ обусловлено частично известной физикой, заданной неопределенными граничными условиями (BC) и линейным УЧП, а также зашумленными физическими измерениями из эксперимента. Граничные условия и правая часть УЧП неизвестны, но выведены из небольшого набора измерений, искаженных шумом. Сюжеты сопоставляют убеждения $u\mid \cdots$ с истинным решением $u^{\star }$ скрытой краевой задачи.

Вероятностные численные решатели УЧП, основанные на регрессии гауссовского процесса, восстанавливают классические методы на линейных УЧП для определенных априорных значений, в частности методы средневзвешенных остатков , которые включают методы Галеркина , методы конечных элементов , а также спектральные методы .

История и связанные поля

Взаимодействие между численным анализом и вероятностью затрагивается рядом других областей математики, включая в среднем случае анализ численных методов , сложность, основанную на информации , теорию игр и статистическую теорию принятия решений . Предшественники того, что сейчас называют «вероятностными числами», можно найти еще в конце 19-го и начале 20-го века.

Истоки вероятностных чисел можно проследить до обсуждения вероятностных подходов к полиномиальной интерполяции Анри Пуанкаре в его «Исчислении вероятностей» . В современной терминологии Пуанкаре рассматривал априорное распределение Гаусса функции $f\colon \mathbb {R} \to \mathbb {R}$, выраженный в виде формального степенного ряда со случайными коэффициентами, и запрашивал «вероятные значения» $f(x)$ учитывая это до и $n\in \mathbb {N}$ наблюдения $f(a_{i})=B_{i}$ для $i=1,\dots ,n$.

Более поздний плодотворный вклад во взаимодействие численного анализа и вероятности был внесен Альбертом Сульдином в контексте одномерной квадратуры . Статистическая задача, рассматриваемая Сулдиным, заключалась в аппроксимации определенного интеграла $\textstyle \int u(t)\,\mathrm {d} t$ функции $u\colon [a,b]\to \mathbb {R}$, при броуновском движении до $u$, имея доступ к точечной оценке $u$ в узлах $t_{1},\dots ,t_{n}\in [a,b]$. Сульдин показал, что для заданных квадратурных узлов правилом квадратур с минимальной среднеквадратичной ошибкой является правило трапеций ; при этом эта минимальная ошибка пропорциональна сумме кубов межузловых расстояний. В результате правило трапеций с равноотстоящими друг от друга узлами можно рассматривать как в некотором смысле статистически оптимальное — ранний пример в среднем случае анализа численного метода .Точку зрения Сулдина позже расширил Майк Ларкин. Обратите внимание, что броуновское движение Сульдина априорно подынтегральной функции $u$ является гауссовской мерой и что операции интегрирования и точечной оценки $u$ обе линейные карты .Таким образом, определенный интеграл $\textstyle \int u(t)\,\mathrm {d} t$ представляет собой действительную гауссову случайную величину.В частности, после обусловления наблюдаемыми точечными значениями $u$, оно соответствует нормальному распределению со средним значением, равным правилу трапеций, и дисперсией, равной $\textstyle {\frac {1}{12}}\sum _{i=2}^{n}(t_{i}-t_{i-1})^{3}$.Эта точка зрения очень близка к точке зрения байесовской квадратуры , рассматривающей результаты квадратурного метода не просто как точечную оценку, но и как самостоятельную оценку распределения вероятностей.

Как отметил Хоуман Овади и его коллеги, Взаимодействие между числовой аппроксимацией и статистическим выводом также можно проследить до Паласти и Реньи, Сардиния, Кимельдорф и Вахба (о соответствии между байесовской оценкой и сплайновым сглаживанием/интерполяцией) и Ларкин (о соответствии регрессии гауссовского процесса и численной аппроксимации). Хотя подход к моделированию совершенно известной функции как выборки случайного процесса может показаться нелогичным, естественную основу для его понимания можно найти в теории сложности, основанной на информации (IBC). раздел вычислительной сложности, основанный на наблюдении, что численная реализация требует вычислений с частичной информацией и ограниченными ресурсами. В IBC производительность алгоритма, работающего с неполной информацией, может быть проанализирована в наихудшем или среднем случае (рандомизированном) в отношении недостающей информации. Более того, как сказал Паккель Согласно наблюдениям, средний случай можно интерпретировать как смешанную стратегию в состязательной игре, полученную путем поднятия проблемы минмакса (наихудшего случая) до проблемы минмакса над смешанными (рандомизированными) стратегиями. Это наблюдение приводит к естественной связи между численной аппроксимацией и Вальда теорией принятия решений , очевидно, под влиянием фон Неймана теории игр . Чтобы описать эту связь, рассмотрим оптимальную настройку восстановления Микелли и Ривлина. в котором пытаются аппроксимировать неизвестную функцию на основе конечного числа линейных измерений этой функции. Интерпретируя эту задачу оптимального восстановления как игру с нулевой суммой, где Игрок I выбирает неизвестную функцию, а Игрок II выбирает ее аппроксимацию, и используя относительные ошибки в квадратичной норме для определения потерь, возникают гауссовы априорные принципы. в качестве оптимальных смешанных стратегий для таких игр, а ковариационный оператор оптимального гауссовского априора определяется квадратичной нормой, используемой для определения относительной ошибки восстановления.

Программное обеспечение

• ProbNum : вероятностные числа в Python.
• ProbNumDiffEq.jl : Вероятностные численные решатели ОДУ, основанные на фильтрации, реализованной в Julia.
• Emukit : Адаптируемый набор инструментов Python для принятия решений в условиях неопределенности.
• BackPACK : создан на основе PyTorch. Он эффективно вычисляет величины, отличные от градиента.

См. также

• Анализ среднего случая
• Информационная сложность
• Количественная оценка неопределенности