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

Идея выбирать точки эксперимента по вероятностной модели возникла в 1960-е годы на стыке статистики и теории управления^[1]. Кушнер в 1964 году предложил выбирать следующую точку по вероятности улучшения текущего результата, а Мокус в 1970-е годы развил байесовский подход к глобальной оптимизации и показал его сходимость для широкого класса функций^[1]. В те же годы кригинг — геостатистический метод интерполяции рудных месторождений, родственный регрессионному анализу, — дал вычислительную основу: линейный предсказатель с известной ошибкой^[3].

Обзоры подчёркивают, что ранние работы сформулировали обе главные части будущего метода: модель с мерой неопределённости и правило выбора точки, балансирующее разведку и использование^[2]. Однако вычислительные возможности эпохи ограничивали применение: пересчёт модели после каждого замера был дорог, а задачи имели считанные переменные^[1].

В 1980-е годы кригинг перекочевал в проектирование дорогих вычислительных экспериментов: инженеры строили суррогат по результатам моделирования и искали оптимум уже на нём^[1]. Джонс, Шонау и Велч в 1998 году свели существовавшие схемы в алгоритм эффективной глобальной оптимизации EGO, где критерием выбора точки стало ожидаемое улучшение^[6]. Работа задала стандарт формулировки задачи и показала на инженерных примерах, что десятков проб хватает для близости к оптимуму^[6].

Отдельную линию составили работы Мокуса, оформившие байесовский подход как общий инструмент глобальной оптимизации с мерой информации о функции^[1]. К концу 1990-х годов метод имел ясную постановку, критерии выбора точек и первые программные реализации, но оставался нишевым инструментом инженерного анализа^[6].

Перелом произошёл в 2010-е годы, когда настройка моделей машинного обучения стала массовой дорогой задачей^[1]. Снек, Ларошель и Адамс в 2012 году показали на практике, что байесовская схема подбирает гиперпараметры нейронных сетей лучше случайного поиска при том же бюджете^[4]. Бергстра с соавторами в том же периоде предложили древесные оценки Парзена — альтернативную суррогатную модель, устойчивую к категориальным параметрам^[10].

Теоретический фундамент укрепил анализ доверительных границ: Сринивас с соавторами доказал регретные оценки для гауссовских процессов, показав разумный компромисс разведки и использования^[11]. Дальнейшие работы перенесли метод на параллельные и ограниченные постановки, а библиотеки глубокого обучения сделали его частью повседневного инструментария^[12]. К концу 2010-х годов байесовская оптимизация вошла в системы автоматического машинного обучения как стандартный блок подбора конфигураций^[13].

Основной суррогат — гауссовский процесс: распределение по функциям, в котором любые значения связаны совместным нормальным распределением^[3]. Процесс задаётся средним и ковариационной функцией, а значения в любых точках связаны совместным распределением; ядро кодирует предположение о гладкости целевой функции и определяет, насколько сильно значения в близких точках коррелируют^[3]. Замеры превращают априорное распределение в апостериорное: среднее проходит рядом с наблюдениями, а разброс вне наблюдаемых областей остаётся большим^[3].

При гауссовской модели наблюдений апостериорное предсказание гауссовского процесса вычисляется аналитически. Его неопределённость зависит от выбранного ядра и модели шума^[3]. Стоимость точного обучения гауссовского процесса обычно растёт как ${\displaystyle O(n^{3})}$, где ${\displaystyle n}$ — число наблюдений. При больших наборах данных применяют приближённые методы^[3]. Обзоры рекомендуют процессы для непрерывных пространств небольшой размерности, где предположение гладкости естественно^[1].

Для пространств с категориальными и условными параметрами применяют модели на деревьях решений: ансамбли случайных лесов дают предсказание и разброс по разбросу деревьев, устойчиво обрабатывая разнотипные признаки^[14]. Древесно-структурированная оценка Парзена (TPE) моделирует распределения конфигураций для двух групп результатов. При минимизации потерь это плотности ${\displaystyle l(x)=p(x\mid y<y^{*})}$ и ${\displaystyle g(x)=p(x\mid y\geq y^{*})}$, где ${\displaystyle y^{*}}$ — выбранный квантиль потерь. Кандидаты оцениваются по отношению ${\displaystyle l(x)/g(x)}$^[10]. Такой подход лежит в основе популярных средств настройки и не требует обращения ковариационных матриц^[14].

Выбор суррогата определяется пространством параметров и бюджетом: при выборе суррогата учитывают типы параметров, размерность пространства и бюджет измерений^[14]. Эффективность подхода зависит от соотношения стоимости вычисления целевой функции, обучения суррогата и оптимизации функции приобретения^[1].

Вероятность улучшения измеряет шансы превысить текущий рекорд с учётом неопределённости модели^[1]. Критерий исторически первым появился в работах 1960-х годов, но слабо отличает большие перевесы от малых и тяготеет к мелким шагам около рекорда^[6]. Ожидаемое улучшение исправляет недостаток: усредняется величина превышения, а не сам факт, поэтому точки с потенциалом заметного роста сохраняют привлекательность^[6]. Алгоритм EGO довёл критерий до практической схемы с аналитическим вычислением для гауссовского процесса^[6].

Для максимизации при наблюдениях без шума ожидаемое улучшение определяется как^[2]:

${\displaystyle \mathrm {EI} _{n}(x)=\mathbb {E} \!\left[\max \left(f(x)-f_{n}^{*},0\right)\mid D_{n}\right],\qquad f_{n}^{*}=\max _{1\leq i\leq n}f(x_{i}).}$

Здесь ${\displaystyle D_{n}}$ — накопленные наблюдения, а ожидание берётся по апостериорному распределению. При шумных измерениях необходимы специальные варианты критерия^[2].

Критерий дёшево максимизируется численно: его производные известны, а максимизация по пространству поиска не требует вызовов целевой функции^[2].

Критерий доверительной границы складывает предсказанное среднее и бонус за неопределённость с весовым коэффициентом^[11]:

${\displaystyle \alpha _{\mathrm {UCB} }(x)=\mu (x)+\kappa \,\sigma (x).}$

Прибавка стимулирует разведку: чем меньше данных в области, тем шире интервал и выше оценка^[11]. Коэффициент управляет балансом: при росте параметра схема переходит от жадного использования к систематическому исследованию^[11]. Сринивас и соавторы получили сублинейные оценки накопленного регрета для GP-UCB при заданных предположениях о целевой функции, ядре и шуме, а также специальном выборе изменяющегося коэффициента исследования^[11].

В задачах с ограничениями замер в точке может не просто дать низкое значение, но и оказаться недопустимым: авария прототипа или уход физических параметров за пределы нормы^[7]. Ограниченная схема моделирует допустимость отдельной вероятностной моделью и выбирает точки, где ожидаемое улучшение умножается на вероятность успеха^[7]. Тфаили и соавторы предложили учитывать скрытые ограничения расчётных моделей самолёта с помощью классификаторов, модифицирующих функцию приобретения^[9].

Информационные критерии выбирают точку по ожидаемому приросту знания о положении оптимума, а не по ожидаемому значению функции^[1]. Энтропийные критерии оценивают ожидаемое уменьшение неопределённости относительно положения оптимума^[1]. Выбор критерия зависит от постановки задачи и стоимости его вычисления^[2].

Бюджет задаётся числом замеров, временем или деньгами: цель — максимум качества при заданной цене^[2]. В алгоритме EGO дополнительным критерием остановки служит снижение максимального ожидаемого улучшения ниже выбранного порога^[6].

Классический цикл последовательный: следующая точка зависит от всех предыдущих замеров^[12]. Параллельные схемы выбирают пакет точек: фиксированный или адаптивный, с учётом уже назначенных, но не завершённых проб^[12]. Ван, Кларк, Лю и Фрейзер разработали метод совместной оптимизации пакетного ожидаемого улучшения (q-EI) с помощью стохастических оценок градиента^[12]. Практичные средства допускают десятки одновременных проб на кластере^[15].

Шум замера снижает качество модели: суррогат начинает объяснять случайность вместо структуры^[7]. Схемы с шумом оценивают дисперсию отдельно и учитывают её в предсказаниях, а повторные замеры в одной точке дают независимую оценку погрешности^[7]. В задачах обучения со случайной инициализацией повторные запуски одной конфигурации уменьшают риск выбрать конфигурацию по удачному случаю^[8].

Главная прикладная область — подбор гиперпараметров моделей: скорость обучения, регуляризация, глубина сети, параметры деревьев^[4]. Каждая проба — полное обучение модели на обучающих данных и оценка функции потерь на проверке, поэтому бюджет проб исчисляется десятками и сотнями^[4]. Снек и соавторы показали на наборах задач, что байесовская схема при равном бюджете достигает лучшей точности, чем случайный и сеточный переборы^[4].

Российские исследования развивают направление в двух путях. Смирнова и соавторы объединили априорные знания о похожих задачах с апостериорными данными текущей настройки и получили лучший результат на большинстве задач при том же лимите времени^[8]. Воробьев показал, что автоматизированная настройка компенсирует потерю точности при сокращении объёма данных до половины, а древесные оценки Парзена предпочтительны для ансамблей деревьев^[14].

Открытые средства интегрировали метод в практику: Optuna проводит настройку с древесными оценками Парзена, Hyperopt предлагает несколько суррогатов, а Ax и BoTorch связывают байесовскую схему с современными библиотеками глубокого обучения^[16]. Системы автоматического машинного обучения используют байесовскую схему как ядро подбора конфигураций^[13].

Инженерные применения исторически старше машинного обучения: подбор параметров вычислительных моделей, проектирование конструкций, планирование экспериментов^[6]. Тфаили и соавторы применили ограниченную схему к проектированию летательных аппаратов, где скрытые ограничения проверяются только дорогим расчётом^[9]. Летам и соавторы описали промышленную эксплуатацию метода в социальных сетях: автоматическая настройка систем по результатам шумных онлайн-экспериментов^[7].

В науке метод автоматизирует планирование: подбор условий химических реакций, настройка параметров приборов, поиск конфигураций материалов^[1]. Общая черта — дорогой замер и умеренная размерность, при которой десятки проб дают заметный выигрыш против систематического перебора^[2].

Зоев и соавторы использовали байесовский подход для поиска гиперпараметров моделей U-Net. Полученные при программном обучении весовые коэффициенты затем переносились в систему на кристалле для аппаратной реализации^[17].

Похожие схемы работают в распознавании лиц и обработке изображений, где качество чувствительно к настройкам извлечения признаков^[1].