Оптимизация, когда функция стоимости медленна для оценки

59

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

У меня есть то, что мне кажется необычной ситуацией. Каждая оценка моей функции стоимости дорогая. Я пытаюсь найти набор параметров, которые минимизируют трехмерную поверхность относительно наземных истинных поверхностей. Всякий раз, когда я изменяю параметр, мне нужно запускать алгоритм для всей выборочной когорты, чтобы измерить его эффект. Чтобы рассчитать градиент, мне нужно изменить все 15 параметров независимо, то есть мне нужно регенерировать все поверхности и сравнить их с выборочной когортой слишком много раз на градиент и определенно слишком много раз в ходе оптимизации.

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

Поэтому мои вопросы в основном таковы: кто-нибудь знает методы оптимизации функций затрат, выпуклые или нет, когда оценка медленная? Или, во-первых, я делаю что-то глупое, перезапуская алгоритм и сравнивая его с выборочной группой много раз?

Джаред Бексфорт
источник
5
Вы слышали о стохастическом градиентном спуске? Для глубоких нейронных сетей, применяемых к большим обучающим наборам, у вас есть похожая проблема (но аналитический градиент Eval возможен), и стандартное решение состоит в том, чтобы сделать градиентный спуск, основанный только на одной выборке (стохастической) по сравнению со всей когортой (
серией
3
Я только смутно знаком с областью, поэтому это скорее комментарий, чем ответ. Но то, что вы обсуждаете, во многом напоминает тему количественного определения неопределенности, с которой часто сталкиваются инженеры, когда для оценки одной целевой функции потребовались недели (по крайней мере, из-за проблем, с которыми сталкиваются мои коллеги-инженеры). Мое очень ограниченное понимание того, как это обрабатывается, состоит в том, чтобы сделать суррогатное приближение, которое намного легче оценить на основе прошлых оценок и более простых инженерных моделей, а затем использовать эти суррогатные модели для выбора следующей оценки ...
Клифф А.Б.
2
... из более дорогой целевой функции. Ненавижу это говорить, но сейчас я не знаю больше о теме; Мне только кратко рассказали об этом при обсуждении тем исследований с указанными инженерами. Интересно, что это кажется очень сложной областью исследований: я считаю, что хорошие модели требуют как хорошего понимания физики, так и статистики.
Клифф А.Б.
1
@ seanv507 Да, спасибо, но я избежал этого по той же причине. Для запуска одного образца требуется от 30 секунд до минуты. Если у меня есть 15 параметров, я рассчитываю на 8 минут расчета градиента, даже если я использую только один образец. Если пространство большое, это может занять очень много времени. Пожалуйста, поправьте меня, если у вас были другие идеи.
Джаред Бексфорт
5
«что мне кажется необычной ситуацией. Каждая оценка моей функции затрат стоит дорого». Это вообще не необычная ситуация, в общем. Он проявляется повсюду, например, когда когда-либо ваша функция стоимости возникает при запуске симуляции (например, в этом документе: white.ucc.asn.au/publications/White2015PsoTransistorSizing.pdf мы моделируем схему в SPICE, занимающую 10 секунд ). Более экспериментально, в экспериментальной науке оценки могут занимать века. Один из моих друзей, магистров проекта, в основном оптимизирует 5 параметров, чтобы найти лучший способ введения ДНК. Каждая оценка занимает 24 часа.
Линдон Уайт

Ответы:

60

TL; DR

Я рекомендую использовать LIPO. Это достоверно правильно и доказуемо лучше, чем чистый случайный поиск (PRS). Он также чрезвычайно прост в реализации и не имеет гиперпараметров. Я не проводил анализ, который сравнивал бы LIPO с BO, но я ожидаю, что простота и эффективность LIPO подразумевают, что он превзойдет BO.

(См. Также: Каковы некоторые из недостатков байесовской оптимизации гиперпараметров? )

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

Методы байесовского типа оптимизации строят суррогатные модели гауссовского процесса для исследования пространства параметров. Основная идея заключается в том, что кортежи параметров, которые находятся ближе друг к другу, будут иметь одинаковые значения функций, поэтому допущение о структуре дисперсии между точками позволяет алгоритму делать обоснованные предположения о том, какой кортеж с лучшим параметром наиболее целесообразно попробовать в дальнейшем. Эта стратегия помогает сократить количество оценок функций; на самом деле, мотивация методов BO состоит в том, чтобы поддерживать как можно меньшее количество оценок функций, в то же время «используя всего буйвола», чтобы сделать правильные предположения о том, какой смысл проверять дальше. Существуют различные показатели качества (ожидаемое улучшение, ожидаемое улучшение квантилей, вероятность улучшения ...), которые используются для сравнения точек для посещения в следующем.

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

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

С другой стороны, вам нужно будет соответствовать хотя бы одному ГП на каждой итерации (или нескольким, выбирать «лучшие», или усреднять по альтернативам, или полностью байесовские методы). Затем модель используется для создания (возможно, тысяч) прогнозов, обычно в форме многоэтапной локальной оптимизации, с наблюдением, что гораздо дешевле оценить функцию прогнозирования GP, чем оптимизируемую функцию. Но даже с этими вычислительными затратами, как правило, бывает так, что даже невыпуклые функции могут быть оптимизированы с помощью относительно небольшого числа вызовов функций.

По этой теме широко цитируется статья Джоунса и др. «Эффективная глобальная оптимизация дорогостоящих функций черного ящика». Но есть много вариантов этой идеи.

Случайный поиск

Даже когда функция стоимости дорогая для оценки, случайный поиск все еще может быть полезен. Случайный поиск очень прост в реализации. Единственный выбор для исследователя , чтобы сделать это установка вероятности , что вы хотите , чтобы ваши результаты лежат в некотором квантильном ; остальное происходит автоматически, используя результаты из основной вероятности.pд q

Предположим, что ваш квантиль равен и вы хотите вероятность что результаты модели будут в верхних процентов от всех наборов гиперпараметров. Вероятность того, что все попыток кортежей не находятся в этом окне, равна (поскольку они выбираются независимо случайным образом из одного и того же распределения), поэтому вероятность того, что хотя бы один кортеж находится в этой области, составляет . Собрав все вместе, мы имеемq=0.95p=0.95100×(1q)=5nq n = 0,95 n 1 - 0,95 nqn=0.95n10.95n

1qnpnlog(1p)log(q)

который в нашем конкретном случае дает .n59

Это результат того, почему большинство людей рекомендуют попыток кортежей для случайного поиска. Стоит отметить, что сравнимо с количеством экспериментов, необходимых для получения хороших результатов методами, основанными на гауссовском процессе, при умеренном числе параметров. В отличие от гауссовских процессов, число кортежей запросов не изменяется с количеством гиперпараметров для поиска; действительно, для большого числа гиперпараметров метод, основанный на гауссовском процессе, может занять много итераций, чтобы добиться прогресса.n=60n=60

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

ЛИПО и его варианты

Это захватывающее прибытие, которое, если оно не ново , безусловно, ново для меня. Это происходит путем чередования наложения информированных границ на функцию, выборки из наилучшей границы и использования квадратичных приближений. Я все еще прорабатываю все детали, но я думаю, что это очень многообещающе. Это хорошая рецензия на блог , и статья Седрика Малербе и Николаса Ваятиса « Глобальная оптимизация функций Липшица ».

Восстановить Монику
источник
1
Это похоже на современный вариант методов поверхности отклика!
kjetil b halvorsen
1
На самом деле, случайный поиск может работать замечательно: argmin.net/2016/06/20/hypertuning
Tim
1
@ Тим Да, твоя точка зрения хорошо принята. Я не хотел «решать» вопрос о том, что лучше в этом посте, поскольку в BO есть по существу бесконечные перестановки, каждая из которых претендует на звание «лучшего» оптимизатора черного ящика, что делает невозможным быть окончательным. Я согласен, что случайный поиск может работать достаточно хорошо, но я бы порекомендовал LIPO вместо PRS. LIPO доказано правильно и сильно превосходит PRS (в среднем) во всех моих экспериментах. LIPO также имеет минимальную стоимость оценки: если вы можете минимизировать QP, тогда вы можете использовать LIPO, а LIPO имеет нулевые гиперпараметры (в отличие от BO).
Восстановить Монику
Я рад, что проверил этот вопрос еще раз. ЛИПО кажется великолепным.
Джаред Бексфорт
Липо отлично. Когда у меня будет время, я расширю свой ответ, чтобы лучше учесть ЛИПО.
Восстановить Монику
40

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

Я бы сказал, что текущим золотым стандартом для оценки (очень) дорогостоящей функции черного ящика является (глобальная) байесовская оптимизация (BO). Sycorax уже описал некоторые функции BO, поэтому я просто добавляю некоторую информацию, которая может оказаться полезной.

В качестве отправной точки вы можете прочитать этот обзорный документ 1 . Есть и более недавний [2].

В последние годы байесовская оптимизация неуклонно росла как область, с серией специализированных семинаров (например, BayesOpt , и посмотрите эти видео с семинара Шеффилда на BO), так как она имеет очень практические применения в машинном обучении, такие как для оптимизации гиперпараметров алгоритмов ML - см., например, эту статью [3] и соответствующий набор инструментов, SpearMint . Существует множество других пакетов на разных языках, которые реализуют различные алгоритмы байесовской оптимизации.

Как я уже упоминал, основное требование заключается в том, что каждая оценка функции является очень дорогостоящей, так что вычисления, связанные с BO, добавляют незначительные накладные расходы. Чтобы дать пример, BO может быть определенно полезен, если ваша функция оценивается за время порядка минут или более. Вы также можете применить его для более быстрых вычислений (например, десятки секунд), но в зависимости от того, какой алгоритм вы используете, вам может потребоваться принять различные приближения. Если ваша функция оценивается в шкале времени в секундах , я думаю, что вы выходите за границы текущего исследования, и, возможно, другие методы могут стать более полезными. Кроме того, я должен сказать, что BO редко является действительно черным ящиком, и вам часто приходится настраивать алгоритмы, иногда много , чтобы заставить его работать в полную силу с конкретной проблемой реального мира.

Кроме BO, для обзора общих методов оптимизации без производных вы можете взглянуть на этот обзор [4] и проверить алгоритмы, которые имеют хорошие свойства быстрой сходимости. Например, многоуровневый поиск координат (MCS) обычно очень быстро сходится к минимуму окрестности (конечно, не всегда к глобальному минимуму). MCS предназначен для глобальной оптимизации, но вы можете сделать его локальным, установив соответствующие ограничения.

Наконец, вы заинтересованы в BO для целевых функций, которые являются дорогостоящими и шумными , см. Мой ответ на этот вопрос .


Рекомендации:

1 Brochu et al., «Учебник по Байесовской оптимизации функций дорогостоящих затрат с применением к моделированию активного пользователя и обучению иерархическому усилению» (2010).

[2] Шахриари и др., «Извлечение человека из цикла: обзор байесовской оптимизации» (2015).

[3] Snoek и др., «Практическая байесовская оптимизация алгоритмов машинного обучения», NIPS (2012).

[4] Риос и Сахинидис, «Оптимизация без деривативов: обзор алгоритмов и сравнение реализаций программного обеспечения», Журнал глобальной оптимизации (2013).

lacerbi
источник
4
+1 Это отличный ответ. В частности, эти документы являются отличным дополнением к этой теме; действительно, я не знал, что общий метод, который я описал, называется байесовской оптимизацией. Но я обеспокоен тем, что со временем ссылки могут испортиться. Не могли бы вы добавить более полную информацию о цитировании, чтобы будущие пользователи могли получить доступ к этим статьям?
Восстановить Монику
Байесовские статьи по оптимизации весьма полезны. Спасибо, что ответили.
Джаред Бексфорт
1
@ user777: Хороший вопрос. В конце добавлен список явных ссылок, которых должно быть достаточно для восстановления документов.
Lacerbi
6

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

Например, посмотрите на эту статью (Björkman, M. & Holmström, K. «Глобальная оптимизация дорогостоящих невыпуклых функций с использованием радиальных базисных функций». Оптимизация и инженерия (2000) 1: 373. doi: 10.1023 / A: 1011584207202) чье резюме, кажется, указывает, что это именно то, что вы хотите:

В статье рассматривается глобальная оптимизация дорогостоящих целевых функций, т. Е. Проблема поиска глобального минимума, когда существует несколько локальных минимумов и для каждого значения функции требуется значительное время для вычисления ЦП. Такие проблемы часто возникают в промышленных и финансовых приложениях, где значение функции может быть результатом трудоемкого компьютерного моделирования или оптимизации. Производные чаще всего трудно получить, и представленные алгоритмы не используют такую ​​информацию.

Mehrdad
источник
2
Пожалуйста, включите полную информацию о цитировании для связанных документов и других ресурсов. Мы хотим создать надежное хранилище информации, и со временем ссылки, как правило, портятся.
Восстановить Монику
Björkman, M. & Holmström, K. "Глобальная оптимизация дорогостоящих невыпуклых функций с использованием радиальных базисных функций". Оптимизация и инжиниринг (2000) 1: 373. doi: 10.1023 / A: 1011584207202
17
4

Ты не одинок.

Дорогостоящие для оценки системы очень распространены в технике, такие как модели методом конечных элементов (FEM) и модели вычислительной гидродинамики (CFD). Оптимизация этих дорогостоящих компьютерных моделей очень необходима и трудна, потому что для эволюционных алгоритмов часто требуются десятки тысяч оценок проблемы, которая не подходит для дорогостоящих задач. К счастью, существует множество методов (алгоритмов) для решения этой проблемы. Насколько я знаю, большинство из них основаны на суррогатных моделях (метамоделях). Некоторые из них перечислены ниже.

  • Эффективная глобальная оптимизация (EGO) [1]. Алгоритм EGO был упомянут выше и может быть самым известным алгоритмом оптимизации на основе суррогата. Он основан на модели Кригинга и критерии заполнения, называемой функцией ожидаемого улучшения (EI). Пакетами R, включающими алгоритм EGO, являются DiceOptim и DiceKriging.
  • Метод отслеживания мод (MPS) [2]. Алгоритм MPS построен на модели RBF, а для отбора точек-кандидатов используется стратегия выборочного отбора. Код MATLAB публикуется авторами по адресу http://www.sfu.ca/~gwa5/software.html . Алгоритму MPS может потребоваться больше оценок, чтобы получить оптимальное значение, но он может обрабатывать более сложные проблемы, чем алгоритм EGO из моего личного опыта.
  • Ансамбль суррогатных моделей Юлианы Мюллер [3]. Она использовала несколько суррогатов, чтобы улучшить возможности поиска. Набор инструментов MATLAB MATSuMoTo доступен по адресу https://github.com/Piiloblondie/MATSuMoTo .

В целом, эти суррогатные алгоритмы оптимизации пытаются найти глобальный оптимум проблемы, используя как можно меньше оценок. Это достигается за счет полного использования информации, которую предоставляет суррогат (суррогаты). Обзоры по оптимизации вычислительно дорогостоящих задач есть в [4-6].


Ссылка:

  1. Д.Р. Джонс, М. Шонлау и В.Дж. Уэлч, "Эффективная глобальная оптимизация дорогостоящих функций черного ящика", журнал Global Optimization, vol. 13, стр. 455-492, 1998.
  2. Л. Ван, С. Шан, и Г. Г. Ван, "Метод выборки с отслеживанием мод для глобальной оптимизации дорогих функций черного ящика", Engineering Optimization, vol. 36, с. 419-438, 2004.
  3. Дж. Мюллер, "Алгоритмы суррогатной модели для вычислительно дорогостоящих задач глобальной оптимизации" черного ящика ", Технический университет Тампере, 2012.
  4. Г. Г. Ван и С. Шан, "Обзор методов метамоделирования в поддержку оптимизации инженерного проектирования", журнал "Механическое проектирование", вып. 129, с. 370-380, 2007.
  5. А.И. Форрестер и А.Дж. Кин, «Последние достижения в области суррогатной оптимизации», «Прогресс в аэрокосмических науках», вып. 45, с. 50-79, 2009.
  6. FAC Виана, Т. В. Симпсон, В. Балабанов и В. Торопов, «Метамоделирование в междисциплинарной оптимизации дизайна: как далеко мы продвинулись?», AIAA Journal, vol. 52, с. 670-690, 2014/04/01 2014.
Жан Давэй
источник
3

Две простые стратегии, которые я успешно использовал в прошлом:

  1. Если возможно, попытайтесь найти более простую суррогатную функцию, приближающуюся к вашей полной оценке функции стоимости - типичная аналитическая модель, заменяющая симуляцию. Оптимизируйте эту более простую функцию. Затем проверьте и уточните полученное решение с помощью точной функции стоимости.
  2. Если возможно, попытайтесь найти способ оценить точную функцию «дельта-стоимость» - точную, а не приближенную к использованию градиента. То есть из начальной 15-мерной точки, для которой вы оценили полную стоимость, найдите способ определить, как изменится стоимость, внеся небольшое изменение в один (или несколько) из 15 компонентов вашей текущей точки. Вам потребуется использовать свойства локализации небольшого возмущения, если таковые имеются в вашем конкретном случае, и вам, вероятно, потребуется определить, кэшировать и обновить внутреннюю переменную состояния по пути.

Эти стратегии очень специфичны для конкретного случая, я не знаю, могут ли они быть применимы в вашем случае или нет, извините, если они не применимы. Оба могут быть применимы (как это было в моих случаях использования): применить стратегию «дельта-стоимость» к более простой аналитической модели - производительность может улучшиться на несколько порядков.

Другой стратегией было бы использование метода второго порядка, который обычно имеет тенденцию уменьшать количество итераций (но каждая итерация является более сложной) - например, алгоритм Левенберга – Марквардта . Но, учитывая, что у вас, похоже, нет способа напрямую и эффективно оценить градиент, это, вероятно, нереальный вариант в этом случае.

Патрик
источник
3

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

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

Павел
источник
Я предполагаю, что вы первый автор на бумаге - вы, вероятно, должны упомянуть об этом, если это так. В статье отсутствует сравнение с современными методами, такими как байесовская оптимизация или другие суррогатные методы (на самом деле, она вообще не дает никакого эталона). Можете ли вы сказать что-то еще?
Lacerbi
Я не говорю, что модель, используемая там, лучше. Я просто говорю, что люди слишком обеспокоены качеством модели и иногда забывают о параллелизме, который может иметь большое значение, когда задействовано много ядер ..
Пол
Пожалуйста, включите полную информацию о цитировании для связанных документов и других ресурсов. Мы хотим создать надежное хранилище информации, и со временем ссылки, как правило, портятся.
Восстановить Монику
2
Я не уверен, насколько терминология варьируется в зависимости от сообщества, но я обычно здесь использую поверхность ответа, используемую как синоним «полиномиальной суррогатной модели» (обычно квадратичной). Поэтому я склонен думать о суррогатном моделировании как о надмодуле моделирования поверхности отклика. (Это может быть неправильно, хотя.)
GeoMatt22
0

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

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

Как стохастический градиентный спуск может сэкономить время по сравнению со стандартным градиентным спуском?

Как запустить линейную регрессию в параллельном / распределенном режиме для настройки больших данных?

Тот же трюк относится к целевой функции.

Давайте по-прежнему будем использовать линейную регрессию в качестве примера: предположим, что целевой функцией является . Если огромен, скажем, триллион строк, его оценка один раз займет очень много времени. Мы всегда можем использовать подмножество и для аппроксимации целевой функции, которая является квадратом потерь на подмножестве данных.Axb2AAb

Haitao Du
источник