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

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

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

Примечание

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

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

  • Гауссова модель процесса f (x).

  • Байесова процедура обновления для изменения Гауссовой модели процесса при каждой новой оценке f (x).

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

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

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

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

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

  2. Найдите новую точку x, который максимизирует функцию приобретения a (x).

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

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

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

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

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

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

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

Подбирать Гауссову модель регрессии процесса к наблюдениям состоит из нахождения значений для шумового отклонения σ 2 и параметры ядра θ. Этот подбор кривой является в вычислительном отношении интенсивным процессом, выполняемым 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 лучше всего) как самое низкое значение следующего среднего значения.

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

EI(x,Q)=EQ[max(0,μQ(xbest)f(x))].

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

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

PI(x,Q)=PQ(f(x)<μQ(xbest)m).

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

PI=Φ(νQ(x)),

где

νQ(x)=μQ(xbest)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:

LCB=2σQ(x)μQ(x).

В секунду

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

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

EIpS(x)=EIQ(x)μS(x),

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

Плюс

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

σQ 2 (x) = σF 2 (x) + σ 2.

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

σF (x) < σ.

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

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

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

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

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

  2. Для всех алгоритмов, 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.

Смотрите также

|

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте