Постепенная оптимизация - Graduated optimization - Wikipedia

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

Описание техники

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

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

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

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

Несколько примеров

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

Постепенная оптимизация может использоваться во множественном обучении. Например, алгоритм Manifold Sculpting использует постепенную оптимизацию для поиска вложения многообразия для нелинейного уменьшения размерности.[5] Он постепенно масштабирует дисперсию дополнительных измерений в наборе данных при оптимизации остальных измерений. Его также использовали для расчета условий фракционирования с опухолями,[6] для отслеживания объектов в компьютерном зрении,[7] и другие цели.

Подробный обзор метода и его приложений можно найти в.[3]

Связанные методы оптимизации

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

Смотрите также

использованная литература

  1. ^ Такер, Нил; Кутс, Тим (1996). «Методы постепенной невыпуклости и оптимизации с несколькими разрешениями». Видение через оптимизацию.
  2. ^ Блейк, Эндрю; Зиссерман, Эндрю (1987). Визуальная реконструкция. MIT Press. ISBN  0-262-02271-0.[страница нужна ]
  3. ^ а б Хоссейн Мобахи, Джон В. Фишер III. О связи между продолжением гауссовских гомотопий и выпуклыми оболочками, В конспектах лекций по информатике (EMMCVPR 2015), Springer, 2015.
  4. ^ Хоссейн Мобахи, К. Лоуренс Зитник, Йи Ма. Видя сквозь размытие, Конференция IEEE по компьютерному зрению и распознаванию образов (CVPR), июнь 2012 г.
  5. ^ Gashler, M .; Ventura, D .; Мартинес, Т. (2008). «Итеративное уменьшение нелинейной размерности с помощью моделирования многообразия» (PDF). In Platt, J.C .; Коллер, Д .; Певица Ю.А. и другие. (ред.). Достижения в системах обработки нейронной информации 20. Кембридж, Массачусетс: MIT Press. С. 513–20.
  6. ^ Афанасьев, БП; Акимов А.А.; Козлов, А.П .; Беркович, АН (1989). «Постепенная оптимизация фракционирования с использованием 2-компонентной модели». Радиобиология, радиотерапия. 30 (2): 131–5. PMID  2748803.
  7. ^ Мин Е; Haralick, R.M .; Шапиро, Л. (2003). «Оценка кусочно-гладкого оптического потока с глобальным согласованием и постепенной оптимизацией». IEEE Transactions по анализу шаблонов и машинному анализу. 25 (12): 1625–30. Дои:10.1109 / TPAMI.2003.1251156.