Эволюция: обучающий алгоритм природы

Совместно с издательством «Манн, Иванов и Фербер» мы публикуем отрывок из книги «Верховный алгоритм. Как машинное обучение изменит наш мир» профессора Вашингтонского университета Педро Домингоса, посвященный алгоритму, который сможет выуживать любые знания из данных и решать любые задачи еще до того, как мы их сформулируем.

Перед вами Robotic Park - огромная фабрика по производству роботов. Вокруг нее - тысяча квадратных миль джунглей, каменных и не очень. Джунгли окружает самая высокая и толстая в мире стена, утыканная наблюдательными вышками, прожекторами и орудийными гнездами. У стены две задачи: не пустить на фабрику нарушителей и не выпустить ее обитателей - миллионы роботов, сражающихся за выживание и власть. Роботы победители размножаются путем доступа к программированию 3D-принтеров. Шаг за шагом роботы становятся умнее, быстрее и смертоноснее. Robotic Park принадлежит Армии США и призван путем эволюции вывести совершенного солдата.

Пока такой фабрики не существует, но однажды она может появиться. Несколько лет назад на мастер-классе DARPA я предложил эту идею в рамках мысленного эксперимента, и один из присутствующих в зале высших чинов сухо заметил: «Да, это реализуемо». Его решимость будет выглядеть не такой пугающей, если вспомнить, что для обучения своих подразделений американская армия построила в калифорнийской пустыне полноценный макет афганской деревни вместе с жителями, так что несколько миллиардов долларов - небольшая цена за идеального бойца.

Первые шаги в этом направлении уже сделаны. В лаборатории Creative Machines Lab в Корнелльском университете, которой руководит Ход Липсон, роботы причудливых форм учатся плавать и летать - возможно, прямо сейчас, когда вы читаете эти строки. Один из них похож на ползающую башню из резиновых блоков, другой - на вертолет со стрекозиными крыльями, еще один - на меняющий форму конструктор Tinkertoy. Эти роботы созданы не инженерами, а эволюцией - тем самым процессом, который породил разнообразие жизни на Земле. Изначально роботы эволюционируют внутри компьютерной симуляции, но, как только они становятся достаточно перспективными, чтобы выйти в реальный мир, их автоматически печатают на 3D-принтере. Творения Липсона пока не готовы захватить мир, но они уже далеко ушли от первобытного набора элементов в компьютерной программе, в которой они родились.

Алгоритм, обеспечивший эволюцию этих роботов, изобрел в XIX веке Чарльз Дарвин. В то время он не воспринимал эволюцию как алгоритм, отчасти потому, что в ней недоставало ключевой подпрограммы. Как только Джеймс Уотсон и Фрэнсис Крик в 1953 году открыли ее, все было готово для второго пришествия: эволюция in silico вместо in vivo, происходящая в миллиард раз быстрее. Ее пророком стал Джон Холланд - румяный улыбчивый парень со Среднего Запада.

Алгоритм Дарвина

Как и многие другие ученые, работавшие над ранними этапами машинного обучения, Холланд начинал с нейронных сетей, но, после того как он - тогда еще студент Мичиганского университета - прочитал классический трактат Рональда Фишера The Genetical Theory of Natural Selection, его интересы приобрели другое направление. В своей книге Фишер, который также был основателем современной статистики, сформулировал первую математическую теорию эволюции. Теория Фишера была блестящей, но Холланд чувствовал, что в ней не хватает самой сути эволюции: автор рассматривал каждый ген изолированно, а ведь приспособленность организма - комплексная функция всех его генов. Если бы гены были независимы, частотность их вариантов очень быстро сошлась бы в точку максимальной приспособленности и после этого оставалась бы в равновесии. Но если гены взаимодействуют, эволюция - поиск максимальной приспособленности - становится невообразимо сложнее. Когда в геноме тысяча генов и у каждого два варианта, это даст 21000 возможных состояний: во Вселенной нет такой древней и большой планеты, чтобы все перепробовать. И тем не менее эволюция на Земле сумела создать ряд замечательно приспособленных организмов, и теория естественного отбора Дарвина объясняет, как именно это происходит, по крайней мере качественно, а не количественно. Холланд решил превратить все это в алгоритм.

Но сначала ему надо было окончить университет. Он благоразумно выбрал более традиционную тему - булевы схемы с циклами - и в 1959 году защитил первую в мире диссертацию по информатике. Научный руководитель Холланда Артур Бёркс поощрял интерес к эволюционным вычислениям: помог ему устроиться по совместительству на работу в Мичиганском университете и защищал его от нападок старших коллег, которые вообще не считали эту тему информатикой. Сам Бёркс был таким открытым для новых идей, потому что тесно сотрудничал с Джоном фон Нейманом, доказавшим принципиальную возможность существования самовоспроизводящихся машин. Бёрксу выпало завершить эту работу после того, как в 1957 году фон Нейман умер от рака. То, что фон Нейману удалось доказать возможность существования таких машин, - замечательное достижение, учитывая примитивное состояние генетики и информатики в то время, однако его автомат просто делал точные копии самого себя: эволюционирующие автоматы ждали Холланда.

Ключевой вход генетического алгоритма, как назвали творение Холланда, - функция приспособленности. Если имеется программа-кандидат и некая цель, которую эта программа должна выполнить, функция приспособленности присваивает программе баллы, показывающие, насколько хорошо она справилась с задачей. Можно ли так интерпретировать приспособленность в естественном отборе - большой вопрос: приспособленность крыла к полету интуитивно понятна, однако цель эволюции как таковой неизвестна. Тем не менее в машинном обучении необходимость чего-то похожего на функцию приспособленности не вызывает никаких сомнений. Если нам нужно поставить диагноз, то программа, которая дает правильный результат у 60 процентов пациентов в нашей базе данных, будет лучше, чем та, что попадает в точку только в 55 процентах случаев, и здесь возможной функцией приспособленности станет доля правильно диагностированных случаев.

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

Функция приспособленности воплощает роль человека в этом процессе, но более тонкий аспект - это роль природы. Начав с популяции не очень подходящих кандидатов - возможно, совершенно случайных, - генетический алгоритм должен прийти к вариантам, которые затем можно будет отобрать на основе приспособленности. Как это делает природа? Дарвин этого не знал. Здесь в игру вступает генетическая часть алгоритма. Точно так же как ДНК кодирует организм в последовательности пар азотистых оснований, программу можно закодировать в строке битов. Вместо нулей и единиц алфавит ДНК состоит из четырех символов - аденина, тимина, гуанина и цитозина. Но различие лишь поверхностное. Вариативность последовательности ДНК, или строки битов, можно получить несколькими способами. Самый простой подход - это точечная мутация, смена значения произвольного бита в строке или изменение одного основания в спирали ДНК. Но Холланд видел настоящую мощь генетических алгоритмов в более сложном процессе: половом размножении.

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

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

Представьте, например, что нам нужно вывести правило для фильтрации спама. Если в обучающих данных десять тысяч разных слов, каждое правило-кандидат можно представить в виде строки из 20 тысяч битов, по два для каждого слова. Первый бит для слова «бесплатно» будет равен единице, если письмам, содержащим слово «бесплатно», разрешено соответствовать правилу, и нулю, если не разрешено. Второй бит противоположен: один, если письма, не содержащие слова «бесплатно», соответствуют правилу, и ноль - если не соответствуют. Если единице равны оба бита, письмо будет соответствовать правилу вне зависимости от того, содержит оно слово «бесплатно» или нет, то есть правило, по сути, не содержит условий для этого слова. С другой стороны, если оба бита равны нулю, правилу не будут соответствовать никакие письма, поскольку либо один, либо другой бит всегда ошибается и такой фильтр пропустит любые письма (ой!). В целом письмо соответствует правилу, только если оно разрешает весь паттерн содержащихся и отсутствующих в нем слов. Приспособленностью правила может быть, например, процент писем, который оно правильно классифицирует. Начиная с популяции произвольных строк, каждая из которых представляет собой правило с произвольными условиями, генетический алгоритм будет выводить все более хорошие правила путем повторяющегося кроссинговера и мутаций самых подходящих строк в каждом поколении. Например, если в текущей популяции есть правило «Если письмо содержит слово -бесплатный- - это спам» и «Если письмо содержит слово -легко- - это спам», перекрещивание их даст, вероятно, более подходящее правило «Если письмо содержит слова -бесплатный- и -легко- - это спам», при условии, что перекрест не придется между двумя битами, соответствующими одному из этих слов. Кроссинговер также породит правило «Все письма - спам», которое появится в результате отбрасывания обоих условий. Но у этого правила вряд ли будет много потомков в следующем поколении.

Поскольку наша цель - создать лучший спам-фильтр из всех возможных, мы не обязаны честно симулировать настоящий естественный отбор и можем свободно хитрить, подгоняя алгоритм под свои нужды. Одна из частых уловок - допущение бессмертия (жаль, что в реальной жизни его нет): хорошо подходящая особь будет конкурировать за размножение не только в своем поколении, но и с детьми, внуками, правнуками и так далее - до тех пор пока остается одной из самых приспособленных в популяции. В реальном мире все не так. Лучшее, что может сделать очень приспособленная особь, - передать половину своих генов многочисленным детям, каждый из которых будет, вероятно, менее приспособлен, так как другую половину генов унаследует от второго родителя. Бессмертие позволяет избежать отката назад, и при некотором везении алгоритм быстрее достигнет желаемой приспособленности. Конечно, если оценивать по количеству потомков, самые приспособленные индивидуумы в истории были похожи на Чингисхана - предка одного из двух сотен живущих сегодня людей. Так что, наверное, не так плохо, что в реальной жизни бессмертие не дозволено.

Если мы хотим вывести не одно, а целый набор правил фильтрации спама, можно представить набор - кандидат из n правил в виде строки n - 20 000 битов (20 тысяч для каждого правила, если в данных, как раньше, 10 тысяч разных слов). Правила, содержащие для каких-то слов 00, выпадают из набора, поскольку они, как мы видели выше, не подходят ни к каким письмам. Если письмо подходит к любому правилу в наборе, оно классифицируется как спам. В противном случае оно допустимо. Мы по-прежнему можем сформулировать приспособленность как процент правильно классифицированных писем, но для борьбы с переобучением, вероятно, будет целесообразно вычитать из результата штраф, пропорциональный сумме активных условий в наборе правил.

Мы поступим еще изящнее, если разрешим выводить правила для промежуточных концепций, а затем выстраивать цепочки из этих правил в процессе работы. Например, мы можем получить правила «Если письмо содержит слово -кредит- - это мошенничество» и «Если письмо - мошенничество, значит, это письмо - спам». Поскольку теперь следствие из правила не всегда «спам», требуется ввести в строки правил дополнительные биты, чтобы представить эти следствия. Конечно, компьютер не использует слово «мошенничество» буквально: он просто выдает некую строку битов, представляющую это понятие, но для наших целей этого вполне достаточно. Такие наборы правил Холланд называет системами классификации. Они «рабочие лошадки» эволюционистов - основанного им племени машинного обучения. Как и многослойные перцептроны, системы классификации сталкиваются с проблемой присвоения коэффициентов доверия - какова приспособленность правил к промежуточным понятиям? - и для ее решения Холланд разработал так называемый алгоритм пожарной цепочки. Тем не менее системы классификации используются намного реже, чем многослойные перцептроны.

По сравнению с простой моделью, описанной в книге Фишера, генетические алгоритмы - довольно большой скачок. Дарвин жаловался, что ему не хватает математических способностей, но, живи он на столетие позже, то, вероятно, горевал бы из-за неумения программировать. Поймать естественный отбор в серии уравнений действительно крайне сложно, однако выразить его в виде алгоритма - совсем другое дело, и это могло бы пролить свет на многие мучающие человечество вопросы. Почему виды появляются в палеонтологической летописи внезапно? Где доказательства, что они постепенно эволюционировали из более ранних видов? В 1972 году Нильс Элдридж и Стивен Джей Гулд предположили, что эволюция состоит из ряда «прерывистых равновесий»: перемежающихся длинных периодов застоя и коротких всплесков быстрых изменений, одним из которых стал кембрийский взрыв. Эта теория породила жаркие дебаты: критики прозвали ее «дерганной эволюцией». На это Элдридж и Гулд отвечали, что постепенную эволюцию можно назвать «ползучей». Эксперименты с генетическими алгоритмами говорят в пользу скачков. Если запустить такой алгоритм на 100 тысяч поколений и понаблюдать за популяцией в тысячепоколенных отрезках, график зависимости приспособленности от времени будет, вероятно, похож на неровную лестницу с внезапными скачками улучшений, за которыми идут плоские периоды затишья, со временем длящиеся все дольше. Несложно догадаться, почему так происходит: когда алгоритм достигнет локального максимума - пика на ландшафте приспособленности, - он будет оставаться там до тех пор, пока в результате счастливой мутации или кроссинговера какая-то особь не окажется на склоне более высокого пика: в этот момент такая особь начнет размножаться и с каждым поколением взбираться по склону все выше. Чем выше текущий пик, тем дольше приходится ждать такого события. Конечно, в природе эволюция сложнее: во-первых, среда может меняться - как физически, так и потому, что другие организмы тоже эволюционируют, и особь на пике приспособленности вдруг может почувствовать давление и будет вынуждена эволюционировать снова. Так что текущие генетические алгоритмы полезны, но конец пути еще очень далеко.

Источник: postnauka.ru

Комментарии: