Введение

Самая ранняя работа по байесовской оптимизации датируется 1964 годом в работе Кушнера¹. Сейчас это очень популярный метод в машинном обучении. При оптимизации целевой функции f(x) без выражения в замкнутой форме и можно получить только наблюдения (возможно, зашумленные) этой функции f(x) при выборочных значениях, метод градиентного спуска не позволяет найти оптимум. Можно численно оценить градиент или использовать поиск по сетке/случайный поиск, когда вычисление f(x) не так дорого. Однако бывают случаи, когда вычисление значений f в заданных точках может быть дорогостоящим. Позвольте мне привести несколько примеров, когда оценка стоит дорого: x — это географические координаты, а f(x) — количество нефти; x — гиперпараметр глубокой нейронной сети, а f — некоторая целевая функция, то вычисление f(x) займет много времени; х - вид лекарства, а f(x) - эффективность против болезни, то это не только трудоемко, затратно по деньгам, но и крысоемко 🙃. В этом случае полезна байесовская оптимизация.

Байесовская оптимизация — это итеративный процесс поиска оптимума, и он очень хорош для поиска глобальных экстремумов с минимальным количеством испытаний, что является преимуществом перед поиском по сетке или случайным поиском. В этой статье мы представим байесовскую оптимизацию в следующем порядке:

  • Что такое байесовская оптимизация?
  • Суррогатная функция: процесс Гаусса (GP) для аппроксимации исходной целевой функции.
  • Функция сбора данных: руководство по выборке позиций
  • Иллюстрация итеративного процесса оптимизации

Что такое байесовская оптимизация?

Байесовская оптимизация — это алгоритм поиска экстремумов целевой функции, особенно когда оценка функции требует больших затрат. Основная идея байесовской оптимизации заключается в том, что сначала используется суррогатная функция для аппроксимации целевой функции f на основе текущих точек выборки. Суррогатная функция должна быть в состоянии моделировать произвольные сложные функции, а также дешева в оценке. Затем найдите функцию приобретения, чтобы оценить прибыль для оптимизации на основе текущей суррогатной модели, а следующая точка выборки — это точка, в которой функция приобретения максимальна.

Он называется байесовским, потому что байесовская оптимизация использует известную «теорему Байеса», в которой говорится, что апостериорная вероятность модели M с учетом данных (или данных, или наблюдений) E пропорциональна вероятности E с учетом M, умноженной на априорную вероятность М:

В байесовской оптимизации априорное P(f) представляет наше мнение о пространстве возможных целевых функций. Вместе с наблюдаемыми данными

получается апостериорное распределение:

Апостериорное распределение отражает наше обновленное представление о неизвестной функции f. Ее также называют суррогатной функцией, которая действует как аппроксимация истинной целевой функции f. Что касается предыдущего, гауссовский процесс (GP) хорошо подходит для большого семейства общих задач оптимизации. Блог² Мартина Крассера — хороший ресурс для Gaussian Process. Гауссовский процесс завершен, заданный его средней функцией и функцией ковариации. Интуиция GP заключается в том, что она аналогична функции, но вместо того, чтобы возвращать скаляр в x, она возвращает нормальную переменную со средним значением, равным f(x). Обратите внимание, что суррогатная функция — это не только детерминированная функция: мы также можем измерить ее неопределенность, когда она используется для аппроксимации истинной целевой функции.

Второй вопрос заключается в том, как эффективно выбрать следующую точку, в которой будет оцениваться функция f. Мы представим своего рода функцию, называемую функция сбора данных, которая используется в качестве подсказки для определения следующего местоположения образца. Он определяется таким образом, что высокий уровень сбора данных соответствует потенциально высоким значениям целевой функции (если цель состоит в том, чтобы найти максимум) либо из-за высокого прогноза, либо из-за большой неопределенности, либо из-за того и другого. Когда поиск ведется в области с высокой неопределенностью, это разведка; когда поиск находится в области с высоким оценочным значением (предположим, что мы ищем максимум целевой функции), это эксплуатация. Следует обратить внимание на компромисс между разведкой и эксплуатацией при определении следующей точки отбора проб. Следующая точка выборки — это место, где сбор данных максимален:

где u — общий символ функции приобретения.

Давайте соберем все вместе.

Байесовская оптимизация

Для t = 1, 2,... делаем

  1. Найдите следующую точку выборки x_t, оптимизировав функцию сбора по гауссовскому процессу.
  2. Попробуйте целевую функцию в x_t.
  3. Увеличьте наблюдение и обновите гауссовский процесс.

конец для цикла.

Суррогатная функция: процесс Гаусса (GP) для аппроксимации исходной целевой функции

Апостериорное распределение по-прежнему является гауссовским процессом из формулы Байеса и предположения о гауссовском априоре². Это приближение к исходной целевой функции с оценкой неопределенности, см. рисунок 1.

Функция сбора данных: руководство по выборке позиций

Существует множество вариантов функции приобретения. Популярными параметрами являются максимальная вероятность улучшения (MPI), ожидаемое улучшение (EI) и верхняя доверительная граница (UCB). Мы представим их один за другим ниже.

Максимальная вероятность улучшения (MPI)

Максимальная вероятность улучшения – это максимальная вероятность того, что суррогатная функция не меньше текущего максимального значения. Поскольку мы знаем, что распределение суррогатной функции в любой точке является нормальным распределением, функция приобретения имеет вид

В приведенной выше формуле f* — текущее максимальное значение целевой функции, а f-hat — суррогатная функция с сигмой стандартного отклонения.

Параметр эпсилон является компромиссным параметром. Без него формула — чистая эксплуатация. Точки, которые с высокой вероятностью будут бесконечно мало больше, чем f*, будут нарисованы поверх точек, дающих больший выигрыш, но меньшую достоверность.

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

Недостаток MPI заключается в том, что он учитывает только вероятность улучшения, не принимая во внимание величину улучшения, которое потенциально может дать точка. EI учитывает и то, и другое. Функция улучшения определяется как

поэтому I(x) является положительной частью того, насколько прогноз выше, чем наилучшее известное значение. Следующей точкой отбора является

Поскольку апостериорное распределение является нормальным со средним значением µ(x) и дисперсией Var(x), можно вычислить математическое ожидание функции улучшения, и оно оказывается следующим:

где

Phi и phi — CDF и PDF стандартного нормального распределения.

Подобно максимальной вероятности улучшения, мы можем включить параметр эпсилон для компромисса между разведкой и эксплуатацией: при исследовании мы должны выбирать точки, где суррогатная дисперсия велика; при эксплуатации мы должны выбирать точки, где суррогатное среднее значение высокое. В приведенной выше формуле все f* заменены на f* + эпсилон.

Верхняя доверительная граница (UCB)

Последней популярной функцией сбора данных является верхняя/нижняя доверительная граница, которая определяется следующим образом:

Пользователи могут свободно настраивать параметр k в функции сбора данных UCB.

Иллюстрация процесса оптимизации

Примечание. Код для создания рисунка 4 принадлежит Мартину Крассеру.

Справочник

[1] Кушнер, Гарольд Дж. «Новый метод определения точки максимума произвольной многопиковой кривой в присутствии шума». Journal of Basic Engineering 86.1 (1964): 97–106.

[2] Мартин Крассер. Гауссовский процесс. http://krasserm.github.io/2018/03/19/gaussian-processes/

[3] Обзор байесовской оптимизации https://soubhikbarari.github.io/blog/2016/09/14/overview-of-bayesian-optimization

[4] Гауссовский процесс https://en.wikipedia.org/wiki/Gaussian_process

[5] Джонс, Д.Р., Шонлау, М. и Уэлч, WJ Journal of Global Optimization (1998) 13: 455. https://doi.org/10.1023/A:1008306431147

[6] Мартин Крассер. https://github.com/krasserm/bayesian-machine-learning