Бесплатного обеда не бывает
May. 25th, 2010 11:44 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipaВ аспирантуре я занимался проблемами нелинейной оптимизации. Самый общий и простой метод оптимизации (или поиска экстремума целевой функции, что одно и то же) в нелинейных задачах -- это метод Монте-Карло или просто случайный поиск. К нему можно добавить некоторый статистический аппарат, чтобы оценивать точность оптимизации. Был соблазн попробовать генетические алгоритмы (ГА), в то время они были новы и довольно популярны. Я накупил кучу книжек, которые рассказывали, как здорово некоторые задачи решались при помощи ГА. Реализовал алгоритм, который работал, но не давал каких-то выдающихся результатов по сравнению со случайным поиском. А потом, рецензируя статьи по этой тематике, наткнулся на теорему, осознание которой полностью отвратило меня от всякий экспериментов с ГА, во всяком случае для тех задач, которые тогда ставились. Речь идет о теореме "Бесплатного обеда не бывает" -- No Free Lunch Theorem (NFL). Может быть, на русский это лучше перевести, как "бесплатного сыра не бывает", но название теоремы пришло из одного конкретного примера.
Смысл теоремы в том, что не существует алгоритма (поиска или оптимизации), который "работает" лучше других на всем множестве задач (я намеренно употребляю такие расплывчатые формулировки, но на самом деле условия применимости теоремы весьма широки). Если некоторый алгоритм работает лучше (быстрее, точнее) на одних задачах, значит, на других задачах он будет хуже. Теорема имеет принципиальное значение. Если взять весь класс задач, к которому применим конкретный алгоритм, то он будет не лучше, чем просто случайный поиск. А зачем тогда усложнять? :) Конечно, есть специфические задачи, которые можно решать специфическими алгоритмами, подобранными для этих задач, но обобщить способ "подбора" невозможно.
Интересно, что NFL оказывается тесно связана с Колмогоровской сложностью.
http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
Смысл теоремы в том, что не существует алгоритма (поиска или оптимизации), который "работает" лучше других на всем множестве задач (я намеренно употребляю такие расплывчатые формулировки, но на самом деле условия применимости теоремы весьма широки). Если некоторый алгоритм работает лучше (быстрее, точнее) на одних задачах, значит, на других задачах он будет хуже. Теорема имеет принципиальное значение. Если взять весь класс задач, к которому применим конкретный алгоритм, то он будет не лучше, чем просто случайный поиск. А зачем тогда усложнять? :) Конечно, есть специфические задачи, которые можно решать специфическими алгоритмами, подобранными для этих задач, но обобщить способ "подбора" невозможно.
Интересно, что NFL оказывается тесно связана с Колмогоровской сложностью.
http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-05-26 07:12 am (UTC)Если я правильно понял, речь о том, что, методы типа ГА или градиентного спуска используют некоторые закономерности в устройстве функций. Со спуском это более чем очевидно, с ГА это менее очевидно, но скорее всего тоже что-то есть. И, если мы угадали, и функция действительно устроена соответствующим образом, то всё отлично, метод работает лучше, т.к. неявно использует эту дополнительную информацию. А если функция устроена как-то иначе, то он работает плохо.
Ну и т.к. на "всём множестве задач" мы можем встретиться с совсем любыми функциями, то и метода, который одинаково хорошо работает со всеми ними не существует.
no subject
Date: 2010-05-26 07:30 am (UTC)no subject
Date: 2010-05-26 09:18 am (UTC)А можно в процессе работы понять, что наша функция -- плохая, и перейти на Монте-Карло? Или это слишком долго получится?
Ну, т.е., если общего подхода нет, возможно мы можем как-то [автоматически] классифицировать функции и интеллектуально выбирать способ оптимизации.
no subject
Date: 2010-05-26 10:11 am (UTC)Например, выбирать случайным образом точку старта градиентного спуска. Для достаточно хороших функций это может дать неплохой результат, особенно если число локальных экстремумов не очень велико. Однако, градиентный спуск тоже недешев, потому что требует довольно большого количества вычислений для определения градиента. А поскольку заранее неизвестно, в правильную ли яму идет спуск, эти вычисления, возможно, идут вхолостую. А можно было бы потратить на случайный поиск.
создание жизни
Date: 2010-05-28 08:07 pm (UTC)К чему это я? А к тому, что самые сложные организмы получены не случайным поиском, а методами ГА. Случайным способом созданы вирусы, бактерии - те, что не используют половое размножение и развиваются (почти исключительно) мутациям. Хотя, как выясняется, и у бактерий и у вирусов есть возможность обмена генетической информацией между разными особями. Так что можно сказать, что всё живое, что мы видим - результат ГА.
Это что касается задач "вообще", "про жизнь".
А если взять конкретные задачи и способы их решения, то (видимо) следуют вспомнить эволюционные методы. Ведь, по сути, любой ученик усваивает нечто подобное - от простого к сложному. Методом комбинирования простого, мы строим нечто более сложное. На этом и математика, и химия, и физика и многое другое построено. Получается и тут мы имеем дело не с простым поиском, а со скрещиванием идей и отбором получившихся гипотез.
Re: создание жизни
Date: 2010-05-28 09:47 pm (UTC)Методы ГА -- это лишь попытка сэмулировать мутации и скрещивания генов, и попытка довольно далекая от реальности. Например, сейчас уже известно, что ДНК достаточно устойчива к мутациям. Большие изменения приводят как правило к гибели организмов, а не их изменению, а малые "лечатся" за счет избыточности информации и некоторых не совсем еще понятных механизмов самовосстановления. Несколько лет назад я читал очень интересную статью на тему эволюции, которая избавляет от "наивного" школьного взгляда на этот процесс: http://elementy.ru/lib/430413 Так что ответ на вопрос о роли мутаций в эволюции далеко не однозначен.
Насчет эволюции идей -- не совсем понял Вашу мысль. Конечно же эволюция знаний -- это эволюция. Спорить тут не о чем. Эволюция в широком смысле -- это плавное изменение. Но никакой аналогии с ГА я тут не вижу. ГА -- это хорошо формализуемый алгоритм, в котором есть четкие формальные определения: что есть популяция, как кодируется "ген", каковы правила скрещивания и мутации, и, главное, какая целевая функция. Науку формализовать таким способом невозможно.
Re: создание жизни
Date: 2010-05-29 07:13 am (UTC)Про мутации при делении сказано тут http://www.natural-selection.ru/?p=8 "Это означает, что на геном человека, состоящий приблизительно из 3 • 10^12 пар нуклеотидов, при каждом делении клеток происходит примерно три мутации." Из этого нужно сказать: "мутаций мало, но они есть". (Кстати, число мутаций, по моему, занижено и последнее число следует повысить на несколько порядков.) Я ведь не спорю, что при большом числе мутаций организм будет нежизнеспособный. Но без мутаций не будет материала для улучшения приспособленности. Кстати опыты селекционеров подтверждают - при облучении (т.е. при увеличении уровня мутаций) семян из них могут появиться новые, с новыми интересными свойствами, растения. "В Японии при помощи радиации создан весьма устойчивый к неблагоприятным воздействиям сорт риса «Реи Меи» — самый высокоурожайный из выращиваемых здесь. Мутант сои «Райден», также полученный в Японии, созревает на 25 дней быстрее, чем сорт «Жемаси-рацу», из которого он выведен; новый сорт более стоек и дает такие же урожаи".
> "ГА -- это хорошо формализуемый алгоритм"
на самом деле это группа алгоритмов. Есть разные виды отбора родителей, разные механизмы кодирования генов, разные механизмы мутации. Т.е. "ГА" это не какой-то один алгоритм (типа стандарта, который описывает сжатие фильмов на DVD), а группа, которая может расширяться.
Когда ученому (или ученику в школе) дают задачу он начинает создавать в уме различные гипотезы. Он начинает из уже наработанных знаний о мире выбирать отдельные факты и комбинировать их вместе. При этом он оценивает результат, т.е. считает функцию приспособленности. Конечно я упрощаю в 10000 раз. Думаю ты согласишься, что ученик при решении математической задачи перебирает известные ему теоремы и формулы, пытается комбинировать (скрещивание) их по определенным правилам в поисках решения. Т.е. это некий вид ГА, в котором очень большое число хромосом, и очень сложная функция приспособленности.
К чему это я веду: аналоги ГА работают в нашем мире не только на компьютерах. И они доказали право на существование.
Что касается "Бесплатного обеда не бывает" - да, алгоритм (не важно как полученный и каких затрат стоивший) специально разработанный для какой-то задачи будет справляться с задачей быстрее и лучше, чем некий "универсальный алгоритм". В этом случае ГА (как "универсальный алгоритм") проигрывают сильно.
А вот если мы начнем считать общее время потраченное на создание алгоритма, его реализацию и время счета (особенно для задач, которые нужно решить один раз), то ГА могут победить в большом числе случаев (даже с учетом подстройки коэффициентов ГА).
Re: создание жизни
Date: 2010-05-30 06:42 am (UTC)Это почему Вы так решили?
Во-первых, буду придираться. Если Вы пишете "создание", то это слово предполагает, что есть кто-то, кто создает. Бог?
Во-вторых, и создание, и возникновение, никак не объясняется и не может быть объяснено приспособленностью к размножению. Возникновению жизни предшествовало появление аминокислот, которые не обладают способностью к размножению.
В-третих, если Вы имели ввиду "развитие" жизни, то самые устойчивые живые существа -- это вирусы и бактерии, которым миллионы лет. У них потрясающая способность к рамножению и выживанию. По Вашей логике, развитие жизни на бактериях и вирусах должно было бы завершиться, однако, оно двигалось по пути постоянного усложнения. Причем, более сложные организмы куда менее приспособлены к размножению, чем простые.
Поэтому Ваша функция "Жизни" не подходит.
Продолжаю не соглашаться.
Date: 2010-05-30 05:40 pm (UTC)Вы занимались этой проблемой как биолог, чтобы иметь собственное мнение, да еще на несколько порядков отличающееся от данных официальной науки, которые сами же приводите?
И пусть мутации есть, ученые смогли выделить хотя бы одну мутацию генома человека, которая улучшила его приспособляемость? Те мутации, что приведены в статье -- это болезни.
Принимаю уточнение, хотя я как раз и указал, что свойства ГА зависят очень сильно от способов кодирования, скрещивания, мутации и т.п. Общий только принцип.
Процессы мышления человека при решении какой-то задачи -- это вообще темный лес. Часто решение приходит во сне :)
При решении задачи, ученик отнюдь не перебирает известные ему теоремы и формулы. Это больше похоже на поиск пути в графе, где вершины -- это промежуточные результаты, а ребра -- рассуждения (применения теорем) или формулы. Оценить же результат он вообще не может, поскольку не знает ответ на задачу. Это может сделать только учитель. Аналогии с ГА, на мой взгляд, никакой.
Вообще, если следовать Вашей логике, то действие человека, у которого есть цель, но нет однозначного решения -- это реализация генетического алгоритма, потому что надо выбирать из нескольких альтернатив.
Нет ничего проще случайного поиска (Монте-Карло), о чем Вы? И таки Вы не верите, что бесплатного обеда не бывает? :)
Re: Продолжаю не соглашаться.
Date: 2010-05-30 06:34 pm (UTC)К примеру 10 тысяч лет назад взрослые люди не могли усваивать молоко. Однако позже в геноме людей (в разных племенах в разное время) произошли мутации, которые позволили взрослым усваивать молоко. http://www.membrana.ru/print.html?1166028720 С тех пор эти мутированные гены встречаются часто, потому что закрепились в геноме как полезные.
Процессы принятия решений у людей мне, действительно, не очень известны. Вполне возможно это ближе к обходу графа.
> Нет ничего проще случайного поиска
Я не о простоте, а о скорости нахождения минимума (пусть и не глобального, а просто "хорошего").
Дадим одинаковое время разным людям: "найти самое маленькое значение у функции f(x)=....". При этом функцию подберем довольно сложную, да еще с ограничениями (как это часто бывает в жизни). Это может быть и поиск молекулы-катализатора химической реакции или нахождение формы манипулятора робота, который работает в быстром течении жидкости. Программист может выбирать любой метод решения задачи. Выиграет тот, кто за (к примеру) неделю выдаст наиболее хорошее решение.
Какой твой прогноз - кто выиграет? 1. Любитель Монте-карло. 2. Любитель ГА. 3. Любитель аналитических решений.
отдельно упомянем вариант "Программист, выбравший симбиоз методов A и B".
Мой прогноз:
a) при высокой сложности задачи аналитик почти не имеет шанса;
б) Монте-карло получит среднее(посредственное) решение, которое можно будет легко улучшить градиентным спуском
в) ГА получит хорошее решение
в случае, если программист сможет быстро(!) аналитически решить хоть часть задачи, то (вместе с ГА) он может получить отличное решение.
Твой прогноз, скорее всего, будет другой.
Что касается метода симуляции отжига, то я его пробовал. На сложных задачах он хуже.
Ты так и не сказал, на каких задачах получил лучший результат у Монте-Карло и более плохой у ГА.
Какой метод ты предпочитаешь, когда аналитически не можешь разобрать (решить) функцию?
Re: Продолжаю не соглашаться.
Date: 2010-05-30 08:41 pm (UTC)Аналитические решения не рассматриваем. Реальные нелинейные задачи с десятками, а то и сотнями размерностей аналитически не решаются.
В соответствии с теоремой о бесплатном обеде (с чего мы и начали), у 1 и 2 равные шансы при одинаковом времени работы (временем здесь является количество вычислений целевой функции). Но так как запрограммировать Монте-Карло гораздо проще и быстрее, чем ГА, то за неделю можно перебрать куда большее количество случайных вариантов и найти наименьший, чем с ГА, для которого придется писать программу (или использовать библиотеку) и подбирать коэффициенты. То есть Монте-Карло выиграет. Ведь казино выигрывает всегда :)
И это не прогноз, а научно доказанный факт. О чем и был мой пост.
Re: Продолжаю не соглашаться.
Date: 2010-05-31 12:53 pm (UTC)result:=14;
for I := 0 to 22 do if (x[i]<0) or (x[i]>1) then
x[i]:=random;
for I := 0 to 22-3 do begin
result:=result+sin(x[i]*i+x[i+1]+2*x[i+2])*sqr(x[i]);
end;
в моем случае методами ГА значение <0.3 найдено 4 раза из 10 запусков. ГА я специально под эту задачу не настраивал. Взял (несколько доработанный) компонент (библиотеку) для Дельфи.
Ради хохмы попробовал метод Монте-Карло. Делал 1 200 000 итераций (т.е. в 6 раз больше, нежели в ГА). Типичное "лучшее" решение было от 6.0 до 6.9. Это намного больше решения, которое было найдено методами ГА (ГА нашел решение <0.3)
И ты после этого будешь продолжать настаивать на том, что случайный поиск самый эффективный из общих методов поиска?
Re: Продолжаю не соглашаться.
Date: 2010-05-31 01:09 pm (UTC)Я настаиваю лишь на том (и не я, а ученые, доказавшие теорему), что на всем классе допустимых задач поиска экстремума ГА будет лучше Монте-Карло примерно в половине случаев, а в другой половине -- наоборот. Возможно, Ваш пример -- именно тот, где ГА хорошо работает. Даже если это и так, то это доказывает лишь то, что существуют функции, для которых ГА более эффективен, чем Монте-Карло. В соответствии с теоремой, существуют функции, где ГА так же и менее эффективен.
Кстати, немаловажно, что в случае с Монте-Карло довольно нетрудно оценить статистически с какой точностью и надежностью найден минимум (через порядковые статистики), то есть иметь оценку вроде "экстремум лежит в интервале (m1, m2) с вероятностью 0.99". С ГА это сделать гораздо сложнее. Нет никой зацепки насколько хорошо или плохо найденное решение.
будем рассматривать реальные задачи
Date: 2010-05-31 02:46 pm (UTC)> на всем классе допустимых задач поиска экстремума
это, видимо, главная ошибка. Сейчас, к примеру, большинство вычислений с плавающей запятой делаются с 19-20 значащих цифр. И мало кого волнуют, что можно делать вычисления с 1000 значащими цифрами. Так и тут: нужно рассматривать типичные, наиболее часто встречающиеся в жизни задачи, а не рассматривать "сферического коня в ваакууме". Да, не все задачи оптимально решать методами ГА. Какие неоптимально - а черт его знает. Может часть комбинаторных, может часть задач, которые можно реализовать только целочисленно. Но и чисто случайный поиск ничего хорошего не принесет. Лучше все-таки даже на таких задачах запускать ГА, просто регулировать уровень мутаций (ставить повыше). А с уровнем мутаций 100% ГА вообще в Монте-Карло превращаются :)
Re: будем рассматривать реальные задачи
Date: 2010-05-31 03:11 pm (UTC)Про значащие цифры -- это не имеет значения. Применимость теоремы о бесплатном обеде реально высокая. Посмотрите условия, в википедии есть.
Настоящая проблема в том, что когда появляется реальная нелинейная задача, то часто вообще неизвестно, как она себя ведет. И применяя ГА "вслепую", можно уехать совсем не туда, и даже об этом не догадываться. Преимущество случайного поиска в том, что он дает гарантированный результат, для которого можно гарантированно посчитать точность и надежность поиска. Для любой задачи.
И я не спорю, что для некоторого заранее известного частого случая или типа можно сделать ГА, который будет очень хорошо работать. Ключевые слова здесь -- "заранее известного".
no subject
Date: 2010-05-30 08:13 am (UTC)можете, только отвечать скучно на это
> однако, оно двигалось по пути постоянного усложнения. Причем, более сложные организмы куда менее приспособлены к размножению
Перефразируем мое высказывание. Кто может решать более сложные задачи - бактерия, созданная (родившаяся, образованная - как угодно) в результате мутаций или улитка (продукт полового размножения)?
Мы ведь заинтересованы узнать, какой метод монте-карло или ГА лучше подходят для решения "широкого круга задач". Моя аналогия бактерия-улитка не дает однозначного ответа, но это косвенное подтверждение того, что методами ГА можно находить минимум сложной функции быстрее, нежели методами чисто случайного поиска. Вы против такого высказывания?
Кстати, на какого рода функциях (задачах) вы получили преимущество при использовании метода Монте-Карло?
no subject
Date: 2010-05-30 05:25 pm (UTC)Только Вы не подумайте, что я издеваюсь. Я задаю вопросы, на которые я не знаю ответа. И, наверное, никто не знает. И ГА тут совершенно не причем.
По поводу преимущества метода Монте-Карло. В функциях с большим количеством локальных экстремумов (ям). Особенно если они близки к глобальному. Нет никакой стратегии, чтобы отличить локальную яму от глобальной, не спустившись до низу. При этом нельзя гарантировать, что были найдены все локальные ямы. Для такого рода задач неплохой должно подходить http://en.wikipedia.org/wiki/Simulated_annealing , но я не проводил таких исследований.