Математическая оптимизация на шумную функцию

10

Пусть - довольно приятная функция (например, непрерывная, дифференцируемая, не слишком много локальных максимумов, может быть вогнутая и т. Д.). Я хочу найти максимумы : значение которое делает максимально большим.f:RdRfxRdf(x)

Если бы у меня была процедура для точной оценки на любом входе по моему выбору, я мог бы использовать стандартные методы математической оптимизации : восхождение на холм, градиентный спуск (ну, градиентный подъем) и т. Д. Однако в моем приложении у меня нет способ точно оценить . Вместо этого у меня есть способ оценить значение .ff(x)f(x)

В частности, с учетом любого и любого меня есть оракул, который выведет оценку , и ожидаемая ошибка которого составляет приблизительно . Время выполнения этого вызова оракула пропорционально . (Он реализуется посредством своего рода симуляции; точность симуляции увеличивается с квадратным корнем из числа испытаний, и я могу выбрать, сколько испытаний выполнить, чтобы я мог выбрать желаемую точность.) Так что это дает мне способ получить оценку любой точности, которую я желаю, но чем точнее я хочу, чтобы оценка была, тем больше времени это займет у меня.xεf(x)ε1/ε2

Учитывая этот шумный оракул для , существуют ли какие-либо методы для вычисления максимумов настолько эффективно, насколько это возможно? (Или, точнее, нахождение приблизительных максимумов.) Существуют ли варианты альпинизма, градиентного спуска и т. Д., Которые работают в этой модели?ff

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

DW
источник
2
Похоже, очень оптимизация скорости ставок, чтобы оправдать свою собственную область исследования. Как насчет имитации отжига? Можете ли вы адаптировать идеи оттуда - вероятности перехода и температурный график? Там есть связь - когда вы продолжаете падение температуры, и в вашем случае вы хотите, чтобы упал. ϵ
randomsurfer_123
cybersynchronicity, столкнулся именно с этим случаем недавно в программе GA. согласился с rs выше, что имитирующий отжиг, где точность оценки функции примерно соответствует снижению температуры, должен работать. другая идея состоит в том, чтобы просто сделать фиксированное количество выборок в каждой точке и взять среднее значение в качестве оценки. более продвинутая теория может сказать вам только то, что вы не можете получить что-то даром и что нет ярлыков для оценок, которые улучшают оптимизацию.
vzn

Ответы:

4

Точную функцию можно заменить на функцию шумом , где - искусственный параметр, используемый для описания шумовой зависимости, такой что и содержат шум.f(x,p)f(x+Δx,p+Δp)pΔxΔp

  • Некоторые методы, используемые в стохастической оптимизации и надежной оптимизации, могут быть применимы.
  • Поскольку около максимумов, менее опасен, чем .fx0ΔxΔp
  • Иногда можно точно аппроксимировать при оценке . Зачастую это верно только в теории, потому что она не реализована, а некоторые части потребуют особого внимания.fx(x~,p~)f(x~,p~)
  • Желаемая «малость» (и ) является решением «конечного пользователя». Можно предложить эвристику для управления им, но время выполнения, пропорциональное , слишком медленное для полностью автоматической обработки точности.ΔpΔx1/ϵ2
  • Данный компромисс между шумом и временем выполнения - это то, что отличает эту проблему от лучше изученных. Проблемы, когда шум просто неизбежен, встречаются чаще и лучше изучаются.
Томас Климпел
источник
Спасибо за идею. Я изо всех сил пытаюсь понять, что именно будет означать эта замена и как она поможет. Это эквивалентно замене на ? Я не уверен, как понимать : если я правильно понимаю ваше предложение, оно будет исправлено, и я не смогу выбрать его (поэтому без потери общности мы могли бы также установить и впитать любую зависимость в определение ). Стохастическая оптимизация и надежная оптимизация звучат примерно так, как я искал, так что это очень полезно. Спасибо. f(x,p)f(x+Δx,Δp)pp=0f
DW
@DW Да, вы можете установить . Тогда зашумленная версия есть . Как сказано, и содержат шум. Точнее, они не просто содержат шум, это шум. p=0f(x,0)f(x+Δx,Δp)ΔxΔp
Томас Климпел