Градиентный спуск и многие другие методы полезны для нахождения локальных минимумов в функциях стоимости. Они могут быть эффективными, когда функцию стоимости можно быстро оценить в каждой точке, численно или аналитически.
У меня есть то, что мне кажется необычной ситуацией. Каждая оценка моей функции стоимости дорогая. Я пытаюсь найти набор параметров, которые минимизируют трехмерную поверхность относительно наземных истинных поверхностей. Всякий раз, когда я изменяю параметр, мне нужно запускать алгоритм для всей выборочной когорты, чтобы измерить его эффект. Чтобы рассчитать градиент, мне нужно изменить все 15 параметров независимо, то есть мне нужно регенерировать все поверхности и сравнить их с выборочной когортой слишком много раз на градиент и определенно слишком много раз в ходе оптимизации.
Я разработал метод, позволяющий обойти эту проблему, и в настоящее время оцениваю его, но меня удивляет, что я не нашел много литературы, касающейся дорогих оценок функции стоимости. Это заставляет меня задуматься, не усугубляю ли я проблему сложнее, чем она есть, и, возможно, уже есть лучший способ.
Поэтому мои вопросы в основном таковы: кто-нибудь знает методы оптимизации функций затрат, выпуклые или нет, когда оценка медленная? Или, во-первых, я делаю что-то глупое, перезапуская алгоритм и сравнивая его с выборочной группой много раз?
источник
Ответы:
TL; DR
Я рекомендую использовать LIPO. Это достоверно правильно и доказуемо лучше, чем чистый случайный поиск (PRS). Он также чрезвычайно прост в реализации и не имеет гиперпараметров. Я не проводил анализ, который сравнивал бы LIPO с BO, но я ожидаю, что простота и эффективность LIPO подразумевают, что он превзойдет BO.
(См. Также: Каковы некоторые из недостатков байесовской оптимизации гиперпараметров? )
Байесовская оптимизация
Методы байесовского типа оптимизации строят суррогатные модели гауссовского процесса для исследования пространства параметров. Основная идея заключается в том, что кортежи параметров, которые находятся ближе друг к другу, будут иметь одинаковые значения функций, поэтому допущение о структуре дисперсии между точками позволяет алгоритму делать обоснованные предположения о том, какой кортеж с лучшим параметром наиболее целесообразно попробовать в дальнейшем. Эта стратегия помогает сократить количество оценок функций; на самом деле, мотивация методов BO состоит в том, чтобы поддерживать как можно меньшее количество оценок функций, в то же время «используя всего буйвола», чтобы сделать правильные предположения о том, какой смысл проверять дальше. Существуют различные показатели качества (ожидаемое улучшение, ожидаемое улучшение квантилей, вероятность улучшения ...), которые используются для сравнения точек для посещения в следующем.
Сравните это с чем-то вроде поиска по сетке, который никогда не будет использовать информацию из своих предыдущих оценок функций, чтобы сообщить, куда идти дальше.
Кстати, это также мощный метод глобальной оптимизации, и поэтому он не делает никаких предположений о выпуклости поверхности. Кроме того, если функция является стохастической (скажем, оценки имеют некоторый собственный случайный шум), это может быть непосредственно учтено в модели GP.
С другой стороны, вам нужно будет соответствовать хотя бы одному ГП на каждой итерации (или нескольким, выбирать «лучшие», или усреднять по альтернативам, или полностью байесовские методы). Затем модель используется для создания (возможно, тысяч) прогнозов, обычно в форме многоэтапной локальной оптимизации, с наблюдением, что гораздо дешевле оценить функцию прогнозирования GP, чем оптимизируемую функцию. Но даже с этими вычислительными затратами, как правило, бывает так, что даже невыпуклые функции могут быть оптимизированы с помощью относительно небольшого числа вызовов функций.
По этой теме широко цитируется статья Джоунса и др. «Эффективная глобальная оптимизация дорогостоящих функций черного ящика». Но есть много вариантов этой идеи.
Случайный поиск
Даже когда функция стоимости дорогая для оценки, случайный поиск все еще может быть полезен. Случайный поиск очень прост в реализации. Единственный выбор для исследователя , чтобы сделать это установка вероятности , что вы хотите , чтобы ваши результаты лежат в некотором квантильном ; остальное происходит автоматически, используя результаты из основной вероятности.p д q
Предположим, что ваш квантиль равен и вы хотите вероятность что результаты модели будут в верхних процентов от всех наборов гиперпараметров. Вероятность того, что все попыток кортежей не находятся в этом окне, равна (поскольку они выбираются независимо случайным образом из одного и того же распределения), поэтому вероятность того, что хотя бы один кортеж находится в этой области, составляет . Собрав все вместе, мы имеемq=0.95 p=0.95 100×(1−q)=5 n q n = 0,95 n 1 - 0,95 nqn=0.95n 1−0.95n
который в нашем конкретном случае дает .n≥59
Это результат того, почему большинство людей рекомендуют попыток кортежей для случайного поиска. Стоит отметить, что сравнимо с количеством экспериментов, необходимых для получения хороших результатов методами, основанными на гауссовском процессе, при умеренном числе параметров. В отличие от гауссовских процессов, число кортежей запросов не изменяется с количеством гиперпараметров для поиска; действительно, для большого числа гиперпараметров метод, основанный на гауссовском процессе, может занять много итераций, чтобы добиться прогресса.n=60 n=60
Поскольку у вас есть вероятностная характеристика того, насколько хороши результаты, этот результат может стать убедительным инструментом, чтобы убедить вашего босса в том, что проведение дополнительных экспериментов приведет к уменьшению предельной прибыли.
ЛИПО и его варианты
Это захватывающее прибытие, которое, если оно не ново , безусловно, ново для меня. Это происходит путем чередования наложения информированных границ на функцию, выборки из наилучшей границы и использования квадратичных приближений. Я все еще прорабатываю все детали, но я думаю, что это очень многообещающе. Это хорошая рецензия на блог , и статья Седрика Малербе и Николаса Ваятиса « Глобальная оптимизация функций Липшица ».
источник
Литература по оценке дорогостоящей функции черного ящика довольно обширна и, как отмечали другие люди, обычно основывается на методах суррогатной модели. Черный ящик здесь означает, что мало что известно о базовой функции, единственное, что вы можете сделать, это оценить в выбранной точке (градиенты обычно недоступны).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).
источник
Я сам не знаю алгоритмы, но я полагаю, что тип алгоритма оптимизации, который вы ищете, это оптимизация без производных , которая используется, когда цель дорогая или шумная .
Например, посмотрите на эту статью (Björkman, M. & Holmström, K. «Глобальная оптимизация дорогостоящих невыпуклых функций с использованием радиальных базисных функций». Оптимизация и инженерия (2000) 1: 373. doi: 10.1023 / A: 1011584207202) чье резюме, кажется, указывает, что это именно то, что вы хотите:
источник
Ты не одинок.
Дорогостоящие для оценки системы очень распространены в технике, такие как модели методом конечных элементов (FEM) и модели вычислительной гидродинамики (CFD). Оптимизация этих дорогостоящих компьютерных моделей очень необходима и трудна, потому что для эволюционных алгоритмов часто требуются десятки тысяч оценок проблемы, которая не подходит для дорогостоящих задач. К счастью, существует множество методов (алгоритмов) для решения этой проблемы. Насколько я знаю, большинство из них основаны на суррогатных моделях (метамоделях). Некоторые из них перечислены ниже.
В целом, эти суррогатные алгоритмы оптимизации пытаются найти глобальный оптимум проблемы, используя как можно меньше оценок. Это достигается за счет полного использования информации, которую предоставляет суррогат (суррогаты). Обзоры по оптимизации вычислительно дорогостоящих задач есть в [4-6].
Ссылка:
источник
Две простые стратегии, которые я успешно использовал в прошлом:
Эти стратегии очень специфичны для конкретного случая, я не знаю, могут ли они быть применимы в вашем случае или нет, извините, если они не применимы. Оба могут быть применимы (как это было в моих случаях использования): применить стратегию «дельта-стоимость» к более простой аналитической модели - производительность может улучшиться на несколько порядков.
Другой стратегией было бы использование метода второго порядка, который обычно имеет тенденцию уменьшать количество итераций (но каждая итерация является более сложной) - например, алгоритм Левенберга – Марквардта . Но, учитывая, что у вас, похоже, нет способа напрямую и эффективно оценить градиент, это, вероятно, нереальный вариант в этом случае.
источник
Как упоминали другие люди, суррогатная модель (также называемая поверхностью отклика) является мощным подходом. По моему мнению, одна важная вещь, которую забывают люди, - это то, что вы можете выполнять несколько функций параллельно , если используете многоядерные процессоры.
Я бы посоветовал взглянуть на этот код , он использует простую модель ответа, но масштабируется на многоядерных процессорах, что дает ускорение, равное количеству используемых ядер. Математика позади метода описана в этой статье .
источник
Есть много приемов, используемых в стохастическом градиентном спуске, которые также могут быть применены к оценке целевой функции. Общая идея состоит в том, чтобы попытаться приблизить целевую функцию, используя подмножество данных .
Мои ответы в этих двух постах обсуждают, почему работает стохастический градиентный спуск: интуиция за ним заключается в том, чтобы приблизить градиент, используя подмножество данных.
Как стохастический градиентный спуск может сэкономить время по сравнению со стандартным градиентным спуском?
Как запустить линейную регрессию в параллельном / распределенном режиме для настройки больших данных?
Тот же трюк относится к целевой функции.
Давайте по-прежнему будем использовать линейную регрессию в качестве примера: предположим, что целевой функцией является . Если огромен, скажем, триллион строк, его оценка один раз займет очень много времени. Мы всегда можем использовать подмножество и для аппроксимации целевой функции, которая является квадратом потерь на подмножестве данных.∥Ax−b∥2 A A b
источник