Поэтапная оптимизация
Поэтапная оптимизация — это метод глобальной оптимизации , который пытается решить сложную задачу оптимизации путем первоначального решения значительно упрощенной задачи и постепенного преобразования этой проблемы (во время оптимизации) до тех пор, пока она не станет эквивалентной сложной задаче оптимизации. [1] [2] [3]
Описание техники
[ редактировать ] |
Поэтапная оптимизация — это усовершенствование восхождения на холм , которое позволяет альпинисту избежать достижения локального оптимума. [4] Он разбивает сложную задачу оптимизации на последовательность задач оптимизации, причем первая задача в последовательности является выпуклой (или почти выпуклой), решение каждой проблемы дает хорошую отправную точку для следующей задачи в последовательности, а последняя Проблема в последовательности — это сложная задача оптимизации, которую она в конечном итоге пытается решить. Часто поэтапная оптимизация дает лучшие результаты, чем простое восхождение в гору. Далее, при наличии определенных условий можно показать, что можно найти оптимальное решение конечной задачи последовательности. Эти условия таковы:
- Первую задачу оптимизации в последовательности можно решить, зная начальную отправную точку.
- Локально выпуклая область вокруг глобального оптимума каждой задачи в последовательности включает точку, соответствующую глобальному оптимуму предыдущей задачи в последовательности.
Индуктивно можно показать, что если эти условия соблюдены, то альпинист придет к глобальному оптимуму решения сложной задачи. К сожалению, может быть сложно найти последовательность задач оптимизации, удовлетворяющую этим условиям. Часто градуированная оптимизация дает хорошие результаты, даже если невозможно доказать, что последовательность задач строго соответствует всем этим условиям.
Некоторые примеры
[ редактировать ]Поэтапная оптимизация обычно используется при обработке изображений для поиска объектов на большом изображении. Эту задачу можно сделать более выпуклой , размыв изображения. Таким образом, объекты можно найти, сначала выполняя поиск по наиболее размытому изображению, затем начиная с этой точки и осуществляя поиск в менее размытом изображении и продолжая таким образом до тех пор, пока объект не будет точно расположен на исходном четком изображении. Правильный выбор оператора размытия зависит от геометрического преобразования, связывающего объект на одном изображении с другим. [5]
Поэтапную оптимизацию можно использовать в многообразном обучении. Например, алгоритм Manifold Sculpting использует градуированную оптимизацию для поиска вложения многообразия для нелинейного уменьшения размерности . [6] Он постепенно масштабирует дисперсию дополнительных измерений в наборе данных, одновременно оптимизируя остальные измерения. Его также использовали для расчета условий фракционирования опухолей. [7] для отслеживания объектов в компьютерном зрении, [8] и другие цели.
Подробный обзор метода и его применения можно найти в . [3]
Сопутствующие методы оптимизации
[ редактировать ]Имитация отжига тесно связана с постепенной оптимизацией. Вместо сглаживания функции, по которой выполняется оптимизация, имитация отжига случайным образом искажает текущее решение на затухающую величину, что может иметь аналогичный эффект. [ нужна ссылка ] Однако, поскольку при моделировании отжига для поиска улучшений используется случайная выборка, сложность его вычислений экспоненциально зависит от количества оптимизируемых измерений. [ нужна ссылка ] Напротив, градуированная оптимизация сглаживает оптимизируемую функцию, поэтому по-прежнему можно использовать методы локальной оптимизации, которые эффективны в многомерном пространстве (например, методы на основе градиента, альпинисты и т. д.).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Такер, Нил; Кутс, Тим (1996). «Градуированные методы невыпуклости и многоразрешной оптимизации» . Видение через оптимизацию .
- ^ Блейк, Эндрю; Зиссерман, Эндрю (1987). Визуальная реконструкция . МТИ Пресс. ISBN 0-262-02271-0 . [ нужна страница ]
- ^ Jump up to: а б Хосейн Мобахи, Джон В. Фишер III. О связи между гауссовским гомотопическим продолжением и выпуклыми оболочками , в конспектах лекций по информатике (EMMCVPR 2015), Springer, 2015.
- ^ Халс, Дэниел; Тумер, Каган; Хойл, Кристофер; Тумер, Ирем (февраль 2019 г.). «Моделирование междисциплинарного проектирования с помощью мультиагентного обучения» . АЙ ЭДАМ . Том. 33. С. 85–99. дои : 10.1017/S0890060418000161 .
- ^ Хоссейн Мобахи, К. Лоуренс Зитник, Йи Ма. Видя сквозь размытие , конференция IEEE по компьютерному зрению и распознаванию образов (CVPR), июнь 2012 г.
- ^ Гашлер, М.; Вентура, Д.; Мартинес, Т. (2008). «Итеративное нелинейное уменьшение размерности с помощью многообразия» (PDF) . В Платте, JC; Коллер, Д.; Сингер, Ю.; и др. (ред.). Достижения в области нейронных систем обработки информации 20 . Кембридж, Массачусетс: MIT Press. стр. 513–20.
- ^ Афанасьев, Б.П.; Акимов А.А.; Козлов А.П.; Беркович, А.Н. (1989). «Поэтапная оптимизация фракционирования с использованием двухкомпонентной модели». Радиобиология, Радиотерапия . 30 (2): 131–5. ПМИД 2748803 .
- ^ Мин Е; Харалик, РМ; Шапиро, Л.Г. (2003). «Оценка кусочно-гладкого оптического потока с помощью глобального сопоставления и постепенной оптимизации». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 25 (12): 1625–30. CiteSeerX 10.1.1.707.7843 . дои : 10.1109/TPAMI.2003.1251156 .