- PVSM.RU - https://www.pvsm.ru -
Теория вероятности никогда не переставала меня удивлять, начиная ещё с того момента, как я впервые с ней столкнулся, и до сих пор. В разное время в разной степени меня настигали, назовём их «вау-эффекты», шоковые удары в мозжечок, от которых меня накрывало эффектом третьего ока, и мир навсегда переставал быть прежним.
И она верна. Вот только, если — это не случайный процесс. Адовая смесь из свойств нормального распределения и «почти наверное» доказывает, что в обратном случае эта формула в общем случае неверна. Томик мат.анализа с решениями обыкновенных дифференциальных уравнений теперь можно выкинуть в топку. Люди в теме тихо хихикают, остальные нетерпеливо листают статьи в Вики с исчислениями Ито.
Но совсем недавно я испытал и четвёртый, так называемый, «вау-эффект». Это не какой-то отдельно взятый факт, а целая теория, которую я собираюсь поведать в серии из нескольких статей. И если предыдущие финты теории вероятности вас уже не удивляют, то прошу милости под кат (знаю, вы и так уже здесь).
Начнем с обыкновенной алгебры — определим «вероятностные» (они немного отличаются от «физических») полиномы Эрмита:
Значения первых полиномов:
Полиномы Эрмита обладают следующими свойствами:
Последнее соотношение поможет нам в вычислении -ых полиномов Эрмита для заданного . Программироваться мы будем на Haskell, ибо он позволяет математикам выражаться на привычном им языке — Haskell чист, строг и прекрасен как сама математика.
hermite :: (Enum a, Num a) => a -> [a]
hermite x = s
where s@(_:ts) = 1 : x : zipWith3 (hn2 hn1 n1 -> x * hn1 - n1 * hn2) s ts [1..]
Функция hermite принимает на вход параметр , а на выходе даёт бесконечный лист из -ых полиномов для Кто не знаком с концепцией ленивых вычислений, очень советую ознакомиться. Для тех же, кто эту концепцию знает, но ещё не до конца может в функциональное программирование: что здесь происходит? Представьте, что у нас уже есть бесконечный лист со всеми значениями Эрмитовых полиномов:
s = [1, x, x^2-1, x^3-3x, x^4-6x^2+3, ... ]
Хвост этого листа (без первого элемента):
ts = [x, x^2-1, x^3-3x, x^4-6x^2+3, ... ]
Вдогонку мы возьмем ещё лист с натуральными числами:
[1, 2, 3, ... ]
Функция zipWith3 комбинирует последние три листа, используя данный ему оператор:
x * [ x, x^2-1, x^3-3x, ... ]
- [ 1*1, 2*x, 3*(x^2-1), ... ]
= [x^2-1, x^3-3x, x^4-6x^2+3, ... ]
Добавляем впереди 1 и x, и получаем полный набор Эрмитовых полиномов. Иными словами, мы достали лист со значениями полиномов, используя лист с этими значениями, то есть, лист, который мы и пытаемся достать. Поговаривают, что полное осознание красоты и мощи ФП сродни умению заглянуть себе в ухо.
Проверим: первые 6 значений для :
Prelude> take 6 (hermite 1)
[1,1,0,-2,-2,6]
Что мы и ожидали увидеть.
Двинемся немного в другую степь — вспомним определение пространства Гильберта. Говоря научным языком, это полное метрическое линейное пространство с заданным на нём скалярным произведением На этом пространстве каждому элементу соответствует вещественное число, именуемое нормой и равное
Ничего сверхъестественного. Когда я пытаюсь представить Гильбертово пространство, я начинаю от простого и постепенно прихожу к сложному.
Это пространство можно расширить до пространства комплексных векторов: , для которого скалярное произведение будет
(верхняя черта обозначает комплексное сопряжение).
Обычно под множеством подразумевается интервал , а под мерой — равномерная мера (мера Лебега), т.е. . И тогда скалярное произведение записывается в виде обыкновенного интеграла Лебега
Если же мы думаем в терминах теории вероятностей, то — это пространство элементарных событий, и — случайные величины, а — вероятностная мера. У каждой такой меры есть своя функция плотности распределения , которая может быть отличной от константы, тогда и скалярное произведение совпадает с математическим ожиданием:
Настало время внести в наши размышления элемент случайности. Пусть у нас имеется гильбертово пространство . Тогда мы назовем (изонормальным) Гауссовским процессом, если
По своей математической сути — это отображение из одного гильбертова пространства в другое, из некоторого в — вероятностное пространство из случайных величин с конечной дисперсией, заданного триплетом (множество элементарных событий), (сигма-алгебра) и (вероятностная мера). Несложно показать, что это отображение линейно:
(в смысле равенства «почти наверное», привет «вау-эффект» #2)
Пример. Пусть , где — равномерная мера (Лебега). Скалярное произведение на нём
Пусть — единичная функция на интервале . Тогда и
не что иное, как Броуновское движение (или Винеровский процесс). Более того,
называется интегралом Ито от функции относительно .
Для того, чтобы реализовать Гауссовский процесс я воспользуюсь пакетами, которые благородные люди уже написали за нас.
import Data.Random.Distribution.Normal
import Numeric.LinearAlgebra.HMatrix as H
gaussianProcess :: Seed -> Int -> Int -> ((Int, Int) -> Double) -> Matrix Double
gaussianProcess seed nSamples dim dotProducts = gaussianSample seed nSamples mean cov_matrix
where mean = vector (replicate dim 0)
cov_matrix = H.sym $ matrix dim (map (i -> dotProducts (i `quot` dim, i `rem` dim)) $ take (dim * dim) [0, 1..])
Функция gaussianProcess принимает параметр seed (стандартная штука для генераторов), nSamples — размер выборки, dim — размерность вектора , dotProducts — функцию, принимающую на вход , индекс матрицы ковариации и возвращающую соответствующее этому индексу скалярное произведение . На выход gaussianProcess выдает вектор .
Уже подходит время объединить все полученные нами знания вместе. Но прежде, стоит упомянуть об одном полезном свойстве эрмитовых полиномов и нормального распределения в совокупности. Пусть Тогда, используя разложение Тейлора,
Возьмем — две стандартные нормально распределенные случайные величины. Через производящую функцию нормального распределения мы можем вытащить следующее соотношение:
Берем -ую частную производную , приравниваем по обе стороны уравнения сверху и получаем
О чем это нам говорит? Во-первых, мы получили норму для , а, во-вторых, мы теперь знаем, что разные эрмитовы полиномы от нормальных случайных величин ортогональны друг другу. Вот сейчас мы готовы к осознанию нечто большего.
Пусть — n-й Винеровский хаос. Тогда
Воу-воу, палехче! Давайте разложим эту теорему о разложении по кусочкам и переведём с математического на человеческий. Мы не будем сильно вдаваться в детали, а лишь интуитивно поясним о чем тут речь. Значок обозначает линейную оболочку подмножества гильбертова пространства — пересечение всех подпространств , содержащих . Говоря проще, это множество всех линейных комбинаций элементов из . Черта сверху над обозначает замыкание множества. Если , то называется полным множеством (грубо говоря, " плотно в "). Следовательно, — замыкание линейной оболочки полиномов Эрмита от Гауссовского процесса на единичной гиперсфере.
С нотацией вроде разобрались. Теперь о том, что такое Винеровский хаос. Идем от простого: содержит все линейные комбинации Эрмитовых полиномов со степенью 0, то есть различные комбинации чисел , то есть всё пространство вещественных чисел. Следовательно, . Идем дальше. Несложно увидеть, что , то есть пространство, составленное из Гауссовских процессов. Получается, что все центрированные нормальные величины принадлежат . Если мы добавим еще , то к ним присоединятся и остальные нормальные случайные величины, чье математическое ожидание отлично от нуля. Дальнейшие множества уже оперируют с n-ми степенями .
Пример. Пусть и — квадрат Броуновского движения. Тогда
Первое слагаемое принадлежит , второе — . Это и называется разложением в Винеровский хаос.
Мы показали ранее, что для . Теорема о разложении гласит о том, что эти множества не только ортогональны друг другу, но также формируют полную систему в . Что это означает на практике? Это значит, что любая случайная величина с конечной дисперсией может быть аппроксимирована полиномиальной функцией от нормально распределенной случайной величины.
очень схожа с определением полинома Эрмита
Если же распределение далеко от Гаусса, то можно попробовать и другие ортогональные полиномы. Например, плотность Гамма-распределения:
Ничего не напоминает? Да это же полиномы Лагерра
Равномерному распределению соответствуют полиномы Лежандра, биномиальному распределению — полиномы Кравчука, и т.п. Теория, развивающая идею разложения вероятностного пространства на ортогональные полиномы именуется в англоязычной литературе как «Polynomial chaos expansion».
Пример. Давайте теперь возьмем , функцию и зададим случайную величину , такую что
где . По теореме о разложении мы можем представить её в виде взвешенной суммы из полиномов Эрмита
где коэффициенты задаются формулой
Эти значения мы получили следующим образом:
Поздравляю! Теперь, если у вас есть функция от стандартной нормально распределенной случайной величины, вы сможете её разложить по базису из Эрмитовых полиномов. Например, подбрасывание честной монетки 0-1 мы можем представить в виде
Немного поколдовав с математикой (подсчет несложных интегралов мы оставим читателю), мы получаем разложение:
Заметьте, что каждый второй элемент в разложении по базису равен нулю.
second (x:y:xs) = y : second xs
second _ = []
coinTossExpansion :: Int -> Double -> Double
coinTossExpansion n xi = sum (take n $ 0.5 : zipWith (*) fn (second $ hermite xi))
where fn = 1.0 / (sqrt $ 2 * pi) : zipWith ( fn1 k -> -fn1 * k / ((k + 1) * (k + 2)) ) fn [1, 3..]
Функция coinTossExpansion возвращает сумму, полученную разложением случайной монетки в винеровский хаос, для данного от до . На графике показана постепенная сходимость для выбранных случайным образом с возрастанием .
Судя по этому графику, где-то после мы можем обрезать сумму, округлить и вернуть в качестве .
coinTossSequence :: Seed -> Int -> [Int]
coinTossSequence seed n = map (round.coinTossExpansion 100) (toList nvec)
where nvec = (toColumns $ gaussianProcess seed n 1 ((i,j)->1) ) !! 0
Проверим, как будет выглядеть последовательность из 20 подбрасываний.
Prelude> coinTossSequence 42 20
[0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1]
Теперь, когда вас попросят сгенерировать подбрасывания монетки, вы знаете, что им показать.
Ну а без шуток, мы что-то посчитали и что-то разложили, а какой в этом всем толк, спросите вы. Не спешите чувствовать себя обманутыми. В последующих статьях мы покажем, как это разложение позволяет брать производную от случайной величины (в некотором смысле), расширим стохастическое интегрирование (и ваше сознание), и найдем всему этому практическое применение в машинном обучении.
Автор: The_Freeman
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/270181
Ссылки в тексте:
[1] мозг: http://www.braintools.ru
[2] Источник: https://habrahabr.ru/post/343148/?utm_campaign=343148
Нажмите здесь для печати.