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

Контур алгоритма

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

Примечание

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

Ключевыми элементами минимизации являются:

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

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

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

Контур алгоритма:

  • Вычислите yi = f (xi) для NumSeedPoints xi точки, взятые случайным образом в пределах границ переменной. NumSeedPoints является 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. Совместное распределение априорных значений функции 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, заданное в Kernel (Covariation) Function Options.

См. Снук, Ларошель и Адамс [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. Когда существуют связанные ограничения, включая ограничение Ошибки (см. Ошибки целевой функции), все функции обретения изменяют свою оценку «качества», следуя предложению Гельбарта, Снука и Адамса [2]. Умножьте «качество» на оценку вероятности того, что ограничения удовлетворены, чтобы прийти к функции приобретения.

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

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

  • x лучше всего как место наименьшего апостериорного среднего.

  • μQ (x лучшее) как самое низкое значение апостериорного среднего.

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

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

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

The 'probability-of-improvement' Функция acquisition делает аналогичное, но более простое вычисление как 'expected-improvement'. В обоих случаях, bayesopt сначала вычисляет x лучшее и μQ (x лучшее). Затем для 'probability-of-improvement', bayesopt вычисляет PI вероятности, что новая x точек приводит к лучшему значению целевой функции, измененному параметром «margin» 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.

Нижняя доверительная граница

The '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 поддерживает другую байесовскую модель целевого вычисления функции времени как функцию от x положения. Ожидаемое улучшение в секунду, которое использует функция приобретения,

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

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

Плюс

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

σQ2(<reservedrangesplaceholder1>) = σF2(<reservedrangesplaceholder1>) + σ2.

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

σF (<reservedrangesplaceholder2>) <<reservedrangesplaceholder1> <reservedrangesplaceholder0>.

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

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

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

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

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

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

Ссылки

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

[2] Gelbart, M., J. Snoek, R. P. Adams. Байесовская оптимизация с неизвестными ограничениями. https://arxiv.org/abs/1403.5607, 2014.

[3] Snoek, J., H. Larochelle, R. P. Adams. Практическая байесовская оптимизация алгоритмов машинного обучения. https://arxiv.org/abs/1206.2944, 2012.

См. также

|

Похожие темы

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