Практические руководства

Первая алгоритмическая выборка ребенка из раздачи: доступные методы и способы их использования

Медленное и доступное введение в выборку и аппроксимацию сложных распределений

TL;DR

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

Отбор проб как концепция

Здесь мы называем выборки xᵢ из распределения p (x) одиночными реализациями, распределение вероятностей которых равно p (x). Это отличается от некоторых других мест в статистике, где образец x может относиться к набору реализаций.

Монте-Карло

Методы Монте-Карло преследуют 2 цели: (1) создать выборки из заданного распределения с хорошим охватом этого распределения; и (2) оценить математическое ожидание функций при некотором заданном распределении. Если мы будем использовать методы Монте-Карло для выборки (т.е. решения нашей первой проблемы), мы также сможем предоставить несмещенную оценку для решения нашей второй проблемы - хорошая выборка покрытия позволит нам аппроксимировать интеграл в выражении математического ожидания для x ~ P (X):

Eₓ = E[ f(x) ] = ∫ f(x) p(x) dx

Итак, основная вычислительная проблема, о которой мы должны подумать, - это как лучше всего взять эти образцы. Здесь мы обсуждаем один алгоритмический подход для взятия этих выборок в соответствии с подходами Монте-Карло и Маркова, а также некоторые соображения по улучшению времени для вычисления этого единственного метода Монте-Карло цепи Маркова: алгоритм выборки Метрополиса Гастингса

Марковское свойство / процесс

Короткое, но важное замечание: здесь мы обсуждаем не цепь Маркова, которая является типом вероятностной модели, которая включает идеи из марковского процесса. Методы сортировки марковского процесса работают в предположении, что во временном ряду случайных величин (RV) каждая RV не зависит от всех остальных RV, кроме той, которая ему предшествует . Это переводится в правило цепочки вероятностей, применяемое к совместному распределению вероятностей серии выборок, таким образом:

P( X₁ , … , Xₙ ) = P( X₁ ) P( X₂ | X₁ ) … P( Xₙ | Xₙ₋₁ )

Методы Монте-Карло

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

Методы Монте-Карло (МК) - это итерационные методы исследования (выборки с хорошим охватом) доменного пространства. Эти методы делятся на две общие категории: простые и цепи Маркова.

Простая выборка

Здесь каждая итерация независима, потому что каждая выполняется вслепую (без знания предыдущего результата выборки). Simple MC использует простое для выборки (четко определенное) распределение. Хотя мы не будем здесь подробно обсуждать это, простая выборка MC подразделяется на следующие подкатегории:

Выборка по важности:

Приближает математическое ожидание сложной (не простой для выборки) функции по области с помощью простого для выборки распределения.

Выборка отклонения:

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

Наша объективная оценка ожидаемого интереса (E [P (x)]) может быть затем вычислена через среднее значение по всем нашим выборкам {x} ∈ S . Это беспристрастно, потому что мы приближаемся к истинному значению ожидаемого распределения интересов по мере того, как размер нашей выборки приближается к размеру домена. Кроме того, при увеличении количества элементов S (т. Е. Путем взятия большего количества выборок) дисперсия нашей оценки будет уменьшаться со скоростью, пропорциональной 1 / R. . Доказательство этих двух свойств, общих для всех оценок Монте-Карло, можно увидеть здесь:

Как видно из приведенного выше выражения вычисления оценщика, это очень простое вычисление, которое нужно включить в вычисление функции Evidence Lower Bound (ELBO) для обучающих моделей. И по мере того, как вы увеличиваете размер обучающей выборки или количество мини-пакетов, используемых для обучения, вы все больше приближаетесь к реальному ожиданию вашей вероятностной неразрешимой функции потерь.

Выборка цепи Маркова

В алгоритмах выборки цепей Маркова существует распределение, генерирующее кандидатов. Q - выбор, сделанный разработчиком. Кандидат в Φᵢ может напрямую зависеть или не зависеть от Φᵢ-₁, но всегда будет каким-то образом зависеть от предыдущей итерации, что позволяет учитывать характеристики марковских свойств (как определено выше). Альтернативой тому, чтобы Φᵢ напрямую зависеть от Φᵢ-₁, является сохранение того же распределения q (Φ) с той же параметризацией, а затем привязать зависимость к некоторому другому свойству, относящемуся к Φᵢ-₁ итерации. Тогда q (Φᵢ) должно быть похоже на наше целевое распределение, чтобы обеспечить хорошее приближение к нему.

Алгоритм выборки Метрополиса-Гастингса

В алгоритмах Metropolis существует простое для выборки распределение кандидатов (или предложений), обусловленное значением выборки предыдущей итерации, Φᵢ-₁. Мы используем это предложение-кандидат как средство для выборки из сложного распределения интересов, P * (X).

Если мы выберем распределение кандидатов как семейство гауссианов с одной константой 𝝈, но зависящей от итераций 𝝁, например, мы упростим вычисление значения 𝞪 из-за симметрии, которую эта зависимость вводит, как q (Φᵢ-₁ | Φ *) = q (Φ * | Φᵢ-₁). Значение 𝝈 в таких случаях также называется размером шага, который является гиперпараметром, который необходимо тщательно учитывать, поскольку он влияет на время, необходимое для исследования пространства выборки с помощью достаточное покрытие, а значит, и время работы алгоритма. Такой симметричный выбор функции предложения и определяет алгоритм Metropolis. Расширение Гастингса происходит, когда вычисление альфа-значения алгоритма обобщается для принятия необязательно симметричного предложения. Метод Метрополис-Гастингс основан на подходе Метрополис с использованием идей, полученных на основе выборки по важности: он взвешивает как новую, так и старую выборки по распределению кандидатов.

Обратите внимание, что как в альфа-вычислении Метрополис, так и в альфа-вычислении Метрополис-Гастингс, термин P * (X) появляется как в числителе, так и в знаменателе - умный способ отменить любые коэффициенты нормализации, которые не зависят от X, но, тем не менее, трудноразрешимы, например, те, которые присутствуют в моделях, основанных на энергии.

На случайной прогулке по мегаполису (RWM)

В RWM, таком как Metropolis Hastings, у нас есть зависимость текущего образца кандидата от предыдущей итерации. Обычно в RWM кандидат Φᵢ может напрямую зависеть или не зависеть от Φᵢ-₁, но всегда будет каким-то образом зависеть от предыдущей итерации, тем самым используя марковское свойство. При использовании этого семейства алгоритмов у нас есть два важных выбора: распределение кандидатов и размер шага. Размер шага напрямую влияет на скорость, с которой мы принимаем образцы: слишком высокая скорость (слишком маленький размер шага) приведет к очень медленному исследованию области; слишком низкая скорость (слишком большой размер шага) приведет к неполному охвату домена. Есть одна статья, которая предполагает, что подходящий размер шага для установки для реализации Metropolis в большинстве случаев составляет 𝝈 = 2,38. Одна предлагаемая эвристика для соответствующей степени принятия составляет 23–50% выборок, и в любом случае распределение кандидатов должно иметь более высокую дисперсию, чем
P * (X) (распределение представляет интерес для приближения).

Источники

1. Ghojogh, Nekoei, Ghojogh, et. al. Алгоритмы выборки, от выборки при опросе до методов Монте-Карло: учебное пособие и обзор литературы. Ноябрь 2020 г .: https://arxiv.org/pdf/2011.00901.pdf

2. Георгий. Университет Торонто, CSC412 Зима 2020, лекция 5: https://probmlcourse.github.io/csc412/lectures/week_6/

3. Георгий. Университет Торонто, CSC412 Зима 2020, лекция 7: https://probmlcourse.github.io/csc412/lectures/week_10/#optimizing-the-elbo

4. Понимание алгоритма Метрополиса-Гастингса. Машинное обучение TV (Калифорнийский университет в Санта-Круз). Февраль 2020 г .: https://www.youtube.com/watch?v=0lpT-yveuIA

5. Розенталь. Оптимизация и адаптация алгоритма мегаполиса. Февраль 2013: http://probability.ca/jeff/ftpdir/lawlessart.pdf