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

ГЛАВА 5

ЭВОЛЮЦИЯ: ОБУЧАЮЩИЙСЯ АЛГОРИТМ ПРИРОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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