Байесов алгоритм оптимизации

Схема алгоритма

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

Примечание

В течение этого обсуждения D представляет количество компонентов x.

Основные элементы в минимизации:

Гауссова модель процесса f (x).
Байесова процедура обновления для изменения Гауссовой модели процесса при каждой новой оценке f (x).
a acquisition function (x) (на основе Гауссовой модели процесса f), что вы максимизируете, чтобы определить следующий вопрос x для оценки. Для получения дополнительной информации смотрите Типы Функции Приобретения и Максимизацию Функции Приобретения.

Схема алгоритма:

Оцените _yi = f (_xi) для NumSeedPoints точки _xi, взятый наугад в переменных границах. NumSeedPoints bayesopt установка. Если существуют ошибки оценки, берут более случайные точки, пока нет NumSeedPoints успешные оценки. Вероятностное распределение каждого компонента является или универсальной формой или масштабируемый журналом, в зависимости от Transform значение в optimizableVariable.

Затем повторите следующие шаги:

Обновите Гауссову модель процесса f (x), чтобы получить апостериорное распределение по функциям Q (f |_xi, _yi для i = 1..., t). (Внутренне, bayesopt использование fitrgp соответствовать Гауссовой модели процесса к данным.)
Найдите новую точку x, который максимизирует функцию приобретения a (x).

Остановки алгоритма после достижения любого следующего:

Постоянное число итераций (значение по умолчанию 30).
Установленное время (значением по умолчанию не является никакое ограничение по времени).
Останавливающийся критерий, который вы предоставляете в Байесовых Выходных функциях Оптимизации или Байесовых Функциях построения графика Оптимизации.

Для алгоритмических различий параллельно, см. Параллельный Байесов Алгоритм.

Гауссова регрессия процесса для того, чтобы подбирать модель

Базовая вероятностная модель для целевой функции f является Гауссовым процессом, предшествующим с добавленным Гауссовым шумом в наблюдениях. Таким образом, предшествующее распределение на f (x) является Гауссовым процессом со средним μ (x; θ), и ядро ковариации функционируют k (x, x′; θ). Здесь, θ является вектором параметров ядра. Поскольку конкретное ядро функционирует bayesopt использование, смотрите Функцию Ядра.

В немного большем количестве деталей обозначьте набор точек X = _xi со связанными значениями целевой функции F = _fi. Совместное распределение prior значений функции F многомерно нормальный, со средним μ (X) и ковариационная матрица K (X, X), где _Kij = k (_xi, _xj).

Без потери общности предшествующее среднее значение дано как 0.

Кроме того, наблюдения приняты, чтобы добавить Гауссов шум с отклонением σ ². Таким образом, предшествующее распределение имеет ковариацию K (X, X; θ) + σ ²I.

Подбирать Гауссову модель регрессии процесса к наблюдениям состоит из нахождения значений для шумового отклонения σ ² и параметры ядра θ. Этот подбор кривой является в вычислительном отношении интенсивным процессом, выполняемым fitrgp.

Для получения дополнительной информации при подборе кривой Гауссову процессу к наблюдениям, смотрите Гауссову Регрессию Процесса.

Функция ядра

Функция ядра k (x, x′; θ), может значительно влиять на качество Гауссовой регрессии процесса. bayesopt использует ARD Matérn 5/2 ядро, заданное в Ядре (Ковариация) Опции Функции.

См. Snoek, Лэрочелла и Адамса [3].

Типы функции приобретения

Шесть вариантов функций приобретения доступны для bayesopt. Существует три основных типа с expected-improvement также измененный per-second или plus:

'expected-improvement-per-second-plus' (значение по умолчанию)
'expected-improvement'
'expected-improvement-plus'
'expected-improvement-per-second'
'lower-confidence-bound'
'probability-of-improvement'

Функции приобретения оценивают “совершенство” точки x на основе функции апостериорного распределения Q. Когда существуют связанные ограничения, включая Ошибочное ограничение (см. Ошибки Целевой функции), все функции приобретения изменяют свою оценку “совершенства” после предложения Gelbart, Сноека и Адамса [2]. Умножьте “совершенство” на оценку вероятности, что ограничениям удовлетворяют, чтобы прибыть в функцию приобретения.

Ожидаемое улучшение
Вероятность улучшения
Более низкая доверительная граница
В секунду
Плюс

Ожидаемое улучшение

'expected-improvement' семейство функций приобретения оценивает ожидаемый объем улучшения целевой функции, игнорируя значения, которые вызывают увеличение цели. Другими словами, задать

x _{лучше всего} как местоположение самого низкого следующего среднего значения.
_μQ (x _{лучше всего}) как самое низкое значение следующего среднего значения.

Затем ожидаемое улучшение

$E I (x, Q) = E_{Q} [\max (0, μ_{Q} (x_{лучше всего}) - f (x))] .$

Вероятность улучшения

'probability-of-improvement' функция приобретения делает подобное, но более простое, вычисление как 'expected-improvement'. В обоих случаях, bayesopt сначала вычисляет x _{лучше всего} и _μQ (x _{лучше всего}). Затем для 'probability-of-improvement', bayesopt вычисляет вероятность PI, который новая точка x приводит к лучшему значению целевой функции, измененному “граничным” параметром m:

$P I (x, Q) = P_{Q} (f (x) < μ_{Q} (x_{лучше всего}) - m) .$

bayesopt берет m в качестве предполагаемого шумового стандартного отклонения. bayesopt оценивает эту вероятность как

$P I = Φ (ν_{Q} (x)),$

где

$ν_{Q} (x) = \frac{μ_{Q} (x_{лучше всего}) - m - μ_{Q} (x)}{σ_{Q} (x)} .$

Здесь Φ (·) модуль нормальный CDF, и _σQ является следующим стандартным отклонением Гауссова процесса в x.

Более низкая доверительная граница

'lower-confidence-bound' функция приобретения смотрит на кривую G два стандартных отклонения ниже следующего среднего значения в каждой точке:

$G (x) = μ_{Q} (x) - 2 σ_{Q} (x) .$

G (x) 2_σQ более низкий конверт уверенности модели целевой функции. bayesopt затем максимизирует отрицание G:

$L C B = 2 σ_{Q} (x) - μ_{Q} (x) .$

В секунду

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

Эти функции приобретения работают можно следующим образом. Во время оценок целевой функции, bayesopt обеспечивает другую модель Bayesian времени оценки целевой функции как функция положения x. Ожидаемое улучшение в секунду, которое использование функции приобретения

$E I p S (x) = \frac{E I_{Q} (x)}{μ_{S} (x)},$

где _μS (x) является следующим средним значением синхронизирующей Гауссовой модели процесса.

Плюс

Чтобы выйти из локального минимума целевой функции, приобретение функционирует с plus на их имена изменяют их поведение, когда они оценивают, что они - overexploiting область. Чтобы изучить сверхиспользование, позвольте _σF (x) быть стандартным отклонением следующей целевой функции при x. Позвольте σ быть следующим стандартным отклонением аддитивного шума, так, чтобы

_σQ ² (x) = _σF ² (x) + σ ².

Задайте _tσ, чтобы быть значением ExplorationRatio опция, положительное число. bayesopt plus функции приобретения, после каждой итерации, оценивают, удовлетворяет ли следующий вопрос x

_σF (x) <_tσ σ.

Если так, алгоритм объявляет, что x сверхиспользует. Затем функция приобретения изменяет свою Функцию Ядра путем умножения θ на количество итераций, как предложил Бык [1]. Эта модификация повышает отклонение _σQ для точек промежуточные наблюдения. Это затем генерирует новую точку на основе новой подходящей функции ядра. Если новая точка, которую x снова сверхиспользует, функция приобретения, умножает θ на дополнительный фактор 10 и попробовала еще раз. Это продолжается таким образом до пяти раз, пытаясь сгенерировать точку x, который не сверхиспользует. Алгоритм принимает новый x как следующий вопрос.

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

Максимизация функции приобретения

Внутренне, bayesopt максимизирует функцию приобретения использование выполняющих общих шагов:

Для алгоритмов начиная с 'expected-improvement' и для 'probability-of-improvement', bayesopt оценивает самое маленькое выполнимое среднее значение апостериорного распределения _μQ (x _{лучше всего}) путем выборки нескольких тысяч точек в переменных границах, взятия нескольких из лучших (низкое среднее значение) допустимые точки и улучшения их использующий локальный поиск, чтобы найти очевидную лучшую допустимую точку. Выполнимый означает, что точка удовлетворяет ограничениям (см. Ограничения в Байесовой Оптимизации).
Для всех алгоритмов, bayesopt выборки несколько тысяч точек в переменных границах, берет несколько из лучших (высокая функция приобретения) допустимые точки и улучшает их использующий локальный поиск, чтобы найти очевидную лучшую допустимую точку. Значение функции приобретения зависит от смоделированного апостериорного распределения, не выборки целевой функции, и таким образом, это может быть вычислено быстро.

Ссылки

[1] Бык, A. D. Уровни сходимости эффективных глобальных алгоритмов оптимизации. https://arxiv.org/abs/1101.3501v3, 2011.

[2] Gelbart, M., Дж. Сноек, Р. П. Адамс. Байесова оптимизация с неизвестными ограничениями. https://arxiv.org/abs/1403.5607, 2014.

[3] Snoek, J., Х. Лэрочелл, Р. П. Адамс. Практическая байесова оптимизация алгоритмов машинного обучения. https://arxiv.org/abs/1206.2944, 2012.

Документация