Несколько вопросов по эволюционным алгоритмам

[Иван Семенов]

Здравствуйте, уважаемые участники группы!

Некоторое время назад я начал интересоваться
искусственными нейронными сетями.
и пришел к проблеме синтеза структуры сети.

Анализ литературы привел меня на сайт Ю.Р.Цоя (http://qai.narod.ru)
откуда я почерпнул много интересного, в т.ч. обширную библиографию.

В результате анализа я понял, что на Западе
это направление является достаточно популярным,
в то время как в России гораздо меньше работ по нейроэволюции,
точнее, многое является "изобретением велосипеда".

Пользуясь случаем, хочу выразить благодарность
за большой труд по популяризации нейроэволюционного направления
в нашей стране уважаемому Юрию Робертовичу:)

Однако, у меня в голове теперь некоторая каша,
если вас не затруднит, прошу разъяснить мне ряд вопросов.

1. Сложилось такое впечатление, что одновременно
синтезом структуры сети и настройкой весов
более-менее успешно "занимаются"
только эволюционные алгоритмы,
а неэволюционные методы направлены на
решение каждой из двух задач отдельно.

Каскадная корреляция с hill-climbing постепенно усложняет сеть
оптимальное прореживание структуры (OBS, ODS и т.п.) -
вообще оторваны от обучения и являются процедурами,
применяемыми к уже обученной сети.

Подскажите, пожалуйста,
а) какие существуют эффективные неэволюционные методы
для синтеза структур нейронных сетей?
б) какие существуют эффективные неэволюционные методы
для одновременного синтеза структуры сети и настройки весов?

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

3. Вопрос, скорее, по терминологии.

Допустим, я хочу обсудить возможность
применения к какой-либо прикладной задаче ГА,
обсуждая этот вопрос со специалистом, который этой задачей занимается,
я хочу ему объяснить, что я буду использовать ГА/ЭА.
Для этого мне нужно "на пальцах" объяснить "место" ГА
(а в общем случае и ЭА) в той терминологии,
которой этот специалист владеет.

а)
ГА - относятся к классу адаптивных алгоритмов.
ГА - это алгоритмы случайного (стохастического) поиска.
Т.о. ГА = алгоритмы адаптивного локального поиска
(если сформулировать так - меня отсылают к работам Л.А. Растригина)

б)
ГА - это эвристические алгоритмы.
ГА - это разновидность алгоритмов локального поиска
ГА - это разновидность многоагентных алгоритмов
Т.о. ГА = метаэвристические многоагентные алгоритмы глобальной оптимизации
(если сформулировать так - меня отсылают к МГУА Ивахненко)

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

4. Если убрать из генетического алгоритма
операцию кроссовера, чем он фактически становится?
 

[yury...@gmail.com]

Иван, здравствуйте,

Пожалуйста :)

По вопросам:

1. На самом деле есть много алгоритмов, которые одновременно настраивают веса и структуру. Помимо перечисленных есть еще CasPer и его разные вариации, а также можно использовать комитетные методы классификации, типа того же Boosting'a, если в качестве классификаторов применять ИНС (эта идея витает в воздухе, на нее не так давно намекал В.Г. Царегородцев, и есть аналог в лекциях К.В. Воронцова). При этом теоретически boosting должен быть ну очень эффективен, и практически он очень неплох, плюс почитайте про CasPer (это ответ на (1б)). И в принципе можно рассматривать любой комитетный метод обучения, т.к. ИНС по сути -- композиция простых классификаторов-нейронов. К тому же огромное число методов машинного обучения, связанных с аппроксимацией плотности распределения данных для каждого класса, может быть описано в терминах вероятностных нейронных сетей (и наоборот), а там и до машин опорных векторов недалеко. В общем, методов, подходящих под 1б, много, просто в них могут не упоминаться нейронные сети, важно понимать, что в основе все равно лежат примерно одни и те же принципы и подходы.

Еще, в этом году я спрашивал у одного человека, который работал с CasCor, правда ли, что этот алгоритм часто ведет к переобучению, и он сказал, что не встречался с подобным. Так что тут много зависит от данных, задачи, параметров алгоритма обучения.

Что касается 1а, то вот в голову ничего не идет, хотя методик должно быть много. Фактически, почти любой человек, который начинает работать с ИНС придумывает себе какие-то эвристики, которые можно "упаковать" в алгоритм, просто универсального алгоритма не получится. Но дело в том, что по-большому счету подобрать структуру часто не так уж и сложно, проблема больше, на мой взгляд, в адекватном подборе весов. Для достижения хорошего результата часто нужно колдовать с целевой функцией (сумма квадратов, как известно, слишком чувствительна к выбросам), добавлять разные штрафные и регуляризующие слагаемые, обрабатывать данные, использовать априорные знания и т.д.

2. Наверное такие подходы есть. Но проблема в том, что структура ИНС дискретна, а веса -- непрерывны (если не учитывать машинное представление...). Дискретно-непрерывная оптимизация встречается в основном в синтезе систем управления и там нейросетями не пахнет.

3. Здесь проще описать, чем отличаются ЭА от МГУА и от алгоритмов Растригина, и сослаться и на тех и на других :). Плюс, когда будете описывать ГА/ЭА дайте ссылку на хороший источник, который может быть знаком рецензентам и убедит их в вашей правоте (scholarpedia, известные зарубежные и отечественные монографии). Тот же Растригин ссылался на Фогеля, Уолша (и кто-то третий был, не помню :/).

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

Юрий