Постепенная оптимизация

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

Описание техники Править

Постепенная оптимизация является улучшением восхождения по выпуклой поверхности^[en], которое позволяет избежать попадания в локальный оптимум. Метод разбивает задачу сложной задачи оптимизации на последовательность оптимизационных задач, из которых первая задача является выпуклой (или почти выпуклой), решение каждой задачи даёт хорошую стартовую точку для следующей задачи в последовательности, а последняя задача в последовательности совпадает с исходной трудной задачи оптимизации, решение которой пытаемся найти. Часто постепенная оптимизация даёт лучший результат по сравнению с простым восхождением по выпуклой поверхности. К тому же, когда выполняются определённые условия, можно показать, что метод найдёт оптимальное решение конечной задачи. Вот эти условия:

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

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

Некоторые примеры Править

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

Постепенная оптимизация может быть использована в изучении многообразий^[5]. Алгоритм моделирования многообразия, например, использует постепенную оптимизацию для поиска вложения многообразия для нелинейной редукции размерности^[6]. Алгоритм постепенно масштабирует переменные дополнительных размерностей, оптимизируя в оставшихся размерностях. Метод может быть использован также для вычисления условий разделения опухолей^[7], для отслеживания объектов в компьютерном зрении^[8] и для других целей.

Доскональное описание метода и его приложения можно найти в статье Мобэхи и Фишера^[3].

Связанные техники оптимизации Править

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

См. также Править

Численное продолжение^[en]

Примечания Править

↑ Thacker, Cootes, 1996.
↑ Blake, Zisserman, 1987.
↑ ¹ ² Mobahi, Fisher III, 2015.
↑ Mobahi, Zitnick, Ma, 2012.
↑ На английском — Manifold Learning. Берштейн А.В. пишет: «В последние годы термин Manifold Learning активно используется в самых разных направлениях математики и Computer Science для обозначения самых разных задач, общее в которых только одно — известно конечное множество точек из многообразия (как правило, известной размерности), вложенного в евклидово пространство большей (возможно, достаточно высокой) размерности, по которому надо что-то сказать о многообразии». Близкий термин — Manifold Sculpting (моделирование многообразия). Широкого распространения в русскоязычной литературе термины пока не получили и перевод терминов не устоялся.
↑ Gashler, Ventura, Martinez, 2008, с. 513–20.
↑ Afanasjev, Akimov, Kozlov, Berkovic, 1989, с. 131–5.
↑ Ming Ye, Haralick, Shapiro, 2003, с. 1625–30.

Литература Править

Neil Thacker, Tim Cootes. Graduated Non-Convexity and Multi-Resolution Optimization Methods // Vision Through Optimization. — 1996.
Andrew Blake, Andrew Zisserman. Visual Reconstruction. — MIT Press, 1987. — ISBN 0-262-02271-0.
Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes. — Springer, 2015. — (Lecture Notes in Computer Science (EMMCVPR 2015)).
Hossein Mobahi, C. Lawrence Zitnick, Yi Ma. Seeing through the Blur. — 2012. — (IEEE Conference on Computer Vision and Pattern Recognition (CVPR),).
Gashler M., Ventura D., Martinez T. Iterative Non-linear Dimensionality Reduction with Manifold Sculpting // Advances in Neural Information Processing Systems 20 / Platt J. C., Koller D., Singer Y., Roweis S.. — Cambridge, MA: MIT Press, 2008. — С. 513–20.
Afanasjev B.P., Akimov A.A., Kozlov A.P., Berkovic A.N. Graduated optimization of fractionation using a 2-component model // Radiobiologia, radiotherapia. — 1989. — Т. 30, вып. 2. — С. 131–5. — PMID 2748803.
Ming Ye, Haralick R.M., Shapiro L.G. Estimating piecewise-smooth optical flow with global matching and graduated optimization // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2003. — Т. 25, вып. 12. — С. 1625–30. — doi:10.1109/TPAMI.2003.1251156.

[_4181c3d0e3a0a4f7-1] Thacker, Cootes, 1996.

[_b700322076dcfcab-2] Blake, Zisserman, 1987.

[_7e4460d68bd9116b-3] ¹ ² Mobahi, Fisher III, 2015.

[_c548875ab43a2ff4-4] Mobahi, Zitnick, Ma, 2012.

[5] На английском — Manifold Learning. Берштейн А.В. пишет: «В последние годы термин Manifold Learning активно используется в самых разных направлениях математики и Computer Science для обозначения самых разных задач, общее в которых только одно — известно конечное множество точек из многообразия (как правило, известной размерности), вложенного в евклидово пространство большей (возможно, достаточно высокой) размерности, по которому надо что-то сказать о многообразии». Близкий термин — Manifold Sculpting (моделирование многообразия). Широкого распространения в русскоязычной литературе термины пока не получили и перевод терминов не устоялся.

[_6d03dc223ad4341a-6] Gashler, Ventura, Martinez, 2008, с. 513–20.

[_ea1b4104f30fe977-7] Afanasjev, Akimov, Kozlov, Berkovic, 1989, с. 131–5.

[_006a9f4a64c444aa-8] Ming Ye, Haralick, Shapiro, 2003, с. 1625–30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]