Бесплатного обеда не бывает

[kaipa]

В аспирантуре я занимался проблемами нелинейной оптимизации. Самый общий и простой метод оптимизации (или поиска экстремума целевой функции, что одно и то же) в нелинейных задачах -- это метод Монте-Карло или просто случайный поиск. К нему можно добавить некоторый статистический аппарат, чтобы оценивать точность оптимизации. Был соблазн попробовать генетические алгоритмы (ГА), в то время они были новы и довольно популярны. Я накупил кучу книжек, которые рассказывали, как здорово некоторые задачи решались при помощи ГА. Реализовал алгоритм, который работал, но не давал каких-то выдающихся результатов по сравнению со случайным поиском. А потом, рецензируя статьи по этой тематике, наткнулся на теорему, осознание которой полностью отвратило меня от всякий экспериментов с ГА, во всяком случае для тех задач, которые тогда ставились. Речь идет о теореме "Бесплатного обеда не бывает" -- No Free Lunch Theorem (NFL). Может быть, на русский это лучше перевести, как "бесплатного сыра не бывает", но название теоремы пришло из одного конкретного примера.

Смысл теоремы в том, что не существует алгоритма (поиска или оптимизации), который "работает" лучше других на всем множестве задач (я намеренно употребляю такие расплывчатые формулировки, но на самом деле условия применимости теоремы весьма широки). Если некоторый алгоритм работает лучше (быстрее, точнее) на одних задачах, значит, на других задачах он будет хуже. Теорема имеет принципиальное значение. Если взять весь класс задач, к которому применим конкретный алгоритм, то он будет не лучше, чем просто случайный поиск. А зачем тогда усложнять? :) Конечно, есть специфические задачи, которые можно решать специфическими алгоритмами, подобранными для этих задач, но обобщить способ "подбора" невозможно.

Интересно, что NFL оказывается тесно связана с Колмогоровской сложностью.

http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization

Comments

[fat-crocodile.livejournal.com]

Результат интересный, но, в общем, довольно логичный.

Если я правильно понял, речь о том, что, методы типа ГА или градиентного спуска используют некоторые закономерности в устройстве функций. Со спуском это более чем очевидно, с ГА это менее очевидно, но скорее всего тоже что-то есть. И, если мы угадали, и функция действительно устроена соответствующим образом, то всё отлично, метод работает лучше, т.к. неявно использует эту дополнительную информацию. А если функция устроена как-то иначе, то он работает плохо.

Ну и т.к. на "всём множестве задач" мы можем встретиться с совсем любыми функциями, то и метода, который одинаково хорошо работает со всеми ними не существует.

[ushastyi.livejournal.com]

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

[fat-crocodile.livejournal.com]

Я далёк от подобных задач, так что может быть глупый вопрос задам.

А можно в процессе работы понять, что наша функция -- плохая, и перейти на Монте-Карло? Или это слишком долго получится?

Ну, т.е., если общего подхода нет, возможно мы можем как-то [автоматически] классифицировать функции и интеллектуально выбирать способ оптимизации.

[ushastyi.livejournal.com]

В общем случае -- нельзя. Что на самом деле можно делать -- это комбинировать случайный поиск и другие алгоритмы.

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