Верховный алгоритм - Педро Домингос

Конечно, расчет продолжительности планетарного года — очень простая задача: в ней есть только умножение и квадратный корень. В целом программные деревья могут включать полный спектр элементов программирования, например утверждения «если… то…», циклы и рекурсию. Более показательный пример возможностей генетического программирования — это определение последовательности действий робота для достижения определенной цели. Представьте, что я попросил своего офисного робота принести мне степлер из кладовки. У робота для этого есть большой набор возможных действий: пройти по коридору, открыть дверь, взять предмет и так далее. Каждое из них, в свою очередь, может состоять из различных поддействий: например, протянуть манипулятор к предмету, схватить его в самых разных точках. В зависимости от результатов предыдущих действий новые действия могут выполняться или не выполняться, иногда нужно их повторить некоторое количество раз и так далее. Задача состоит в том, чтобы составить правильную структуру действий и поддействий, а также определить параметры каждого из них, например, как далеко выдвинуть манипулятор. Из «атомарных», мельчайших действий робота и их допустимых комбинаций генетическое программирование может собрать сложное поведение для достижения желаемой цели. Многие ученые таким образом выводили стратегии для роботов-футболистов.

Одно из последствий применения кроссинговера к программным деревьям вместо битовых строк заключается в том, что получающиеся в результате программы могут быть любого размера и обучение делается более гибким. Однако такие программы имеют тенденцию к разбуханию: по мере эволюции деревья становятся все больше и больше (это еще называют «выживанием толстейших»). Эволюционисты могут утешиться фактом, что программы, написанные человеком, в этом отношении не лучше — Microsoft Windows содержит 45 миллионов строк кода, — к тому же к созданному человеком коду нельзя применить такие простые решения, как прибавление к функции приспособленности штрафа за сложность.

Первым успехом генетического программирования стала в 1995 году разработка электронных схем. Начав с кучи элементов — транзисторов, резисторов и конденсаторов, — система Коза вновь изобрела запатентованный ранее фильтр нижних частот, который можно использовать, например, для усиления басов в танцевальной музыке. С тех пор Коза превратил повторное изобретение запатентованных устройств в своего рода спорт и начал выдавать их дюжинами. Следующей вехой стал патент на разработанную таким образом промышленную систему оптимизации, выданный в 2005 году Ведомством США по патентам и торговым знакам. Если бы тест Тьюринга79 заключался в обмане патентного эксперта, а не собеседника, 25 января 2005 года вошло бы в учебники истории.

Своей самоуверенностью Коза выделяется даже среди представителей дисциплины, где скромность не в чести. Он видит в генетическом программировании машину для изобретений, Кремниевого Эдисона XXI столетия. Коза и другие эволюционисты верят, что такой алгоритм может получить любую программу, и ставят на него в гонке за Верховным алгоритмом. В 2004 году они учредили ежегодную премию Humies, которую вручают за «соперничающие с человеком» генетические творения. На сегодняшний день присуждено 39 премий.

Зачем нужен секс?

Несмотря на все успехи и озарения, которые принесли нам генетические алгоритмы в таких вопросах, как градуализм против прерывистого равновесия, одна великая тайна остается неразгаданной: какую роль в эволюции играет половое размножение. Эволюционисты возлагают большие надежды на кроссинговер, однако представители других «племен» считают, что игра не стоит свеч. Ни один из теоретических результатов Холланда не показывает, что кроссинговер полезен: чтобы со временем экспоненциально увеличить частоту наиболее подходящих схем в популяции, достаточно мутаций, а логика «строительных блоков» привлекательна, но быстро сталкивается с проблемами даже при использовании генетического программирования. Когда в ходе эволюции появляются крупные блоки, кроссинговер со все большей вероятностью начинает их разбивать, а если удается вывести очень приспособленную особь, ее потомки, как правило, быстро захватывают популяцию и закрывают собой потенциально более перспективные схемы, содержащиеся в менее приспособленных в целом особях. В результате поиск вариантов сводится к определению чемпиона по приспособленности. Исследователи придумали много приемов сохранения разнообразия в популя­ции, но результаты пока неубедительны. Инженеры, несомненно, широко используют строительные блоки, но для их правильного соединения нужно, скажем так, много инженерии: сложить их вместе любым старым способом непросто, и неясно, может ли кроссинговер здесь помочь.

Если исключить половое размножение, у эволюционистов в качестве двигателя останутся одни мутации. Когда размер популяции значительно превышает количество генов, есть шанс, что все точечные мутации в ней уже представлены, и тогда поиск становится разновидностью восхождения по выпуклой поверхности: попробуй все возможные шаги, выбери лучший и повтори. (Или выбери несколько лучших вариантов: в таком случае это называется лучевой поиск.) Символисты, например, постоянно используют такой подход для получения наборов правил и не считают его формой эволюции. Чтобы не застрять в локальном максимуме, восхождение можно усилить случайностью (допустить с некоторой вероятностью движение вниз) и случайными пере­запусками (через некоторое время перепрыгнуть в произвольное состояние и продолжать восхождение там). Этого достаточно, чтобы найти удачные решения проблем. Оправдывает ли польза от добавления кроссинговера лишние затраты на вычисления — вопрос открытый.

Никто точно не знает, почему половое размножение так распространено в природе. Было выдвинуто несколько теорий, но ни одна из них не стала общепринятой. Ведущее положение занимает гипотеза Черной Королевы80, популяризированная Мэттом Ридли в книге The Red Queen: Sex and the Evolution of Human Nature («Черная королева. Секс и эволюция человеческой натуры»). Черная Королева говорит Алисе: «Приходится бежать со всех ног, чтобы только остаться на том же месте». Организмы находятся в постоянной гонке с паразитами, и половое размножение помогает популяции быть настолько разнообразной, чтобы ни один микроб не смог заразить ее целиком. Если дело в этом, тогда половое размножение не имеет отношения к машинному обучению, по крайней мере пока полученные путем эволюции программы не начнут соревноваться с компьютерными вирусами за время работы процессора и память. (Что интересно, Дэнни Хиллис81 утверждает, что целенаправленное введение в генетический алгоритм попутно эволюцио­нирующих паразитов может помочь избежать локальных максимумов путем постепенного наращивания сложности, однако пока по этому пути никто не пошел.) Христос Пападимитриу82 и его коллеги показали, что половое размножение оптимизирует не приспособленность, а то, что они назвали смешиваемостью: способность гена в среднем хорошо справляться при соединении с другими генами. Это может пригодиться, если функция приспо­собленности либо неизвестна, либо непостоянна, как в естественном отборе, однако в машинном обучении и оптимизации, как правило, лучше справляется восхождение на выпуклые поверхности.

На этом проблемы генетического программирования не заканчиваются. Получается, что даже его успехи, возможно, совсем не такие «генетические», как хотелось бы эволюционистам. Возьмем разработку электронных схем — знаковый успех генетического программирования. Как правило, даже относительно простые схемы требуют огромного объема поиска, причем неясно, насколько мы обязаны результатами грубой силе, а насколько — генетическому интеллекту. Чтобы ответить растущему хору критиков, Коза включил в свою опубликованную в 1992 году книгу Genetic Programming эксперименты, показывающие, что генетическое программирование превосходит случайно сгенерированных кандидатов в проблеме синтеза булевых схем, но отрыв был небольшой. В 1995 году на Международной конференции по машинному обучению (International Conference on Machine Learning, ICML) в Лейк-Тахо Кевин Лэнг опубликовал статью о том, что восхождение на выпуклые поверхности побеждает генетическое программирование в тех же самых программах, причем часто со значительным перевесом. Коза и другие эволюционисты неоднократно пытались опубликовать свои работы в материалах ICML, ведущем мероприятии в этой области, но, к их растущему разочарованию, их постоянно отклоняли из-за недостаточной эмпирической обоснованности. Коза и так был раздосадован тем, что его не публикуют, поэтому работа Лэнга просто вывела его из равновесия. На скорую руку он написал статью на 23 страницах в два столбца, в которой опровергал выводы Лэнга и обвинял рецензентов ICML в нарушении научной этики, а затем положил по экземпляру на каждое кресло в конференц-зале. Статья Лэнга (а может, и ответ Коза — как посмотреть) стали последней каплей: инцидент в Тахо привел к окончательному расхождению между эволюционистами и остальным сообществом ученых, занимающихся машинным обучением. Эволюционисты хлопнули дверью. Специалисты по генетическому программированию начали проводить собственные конференции, которые впоследствии слились с конференциями по генетическим алгоритмам в GECCO — Genetic and Evolutionary Computing Conference. А мейнстрим машинного обучения во многом просто забыл об их существовании. Печальная развязка, но не первый случай в истории, когда секс приводит к разводу.