Представьте, например, что нам нужно вывести правило для фильтрации спама. Если в обучающих данных десять тысяч разных слов, каждое правило-кандидат можно представить в виде строки из 20 тысяч битов, по два для каждого слова. Первый бит для слова «бесплатно» будет равен единице, если письмам, содержащим слово «бесплатно», разрешено соответствовать правилу, и нулю, если не разрешено. Второй бит противоположен: один, если письма, не содержащие слова «бесплатно», соответствуют правилу, и ноль — если не соответствуют. Если единице равны оба бита, письмо будет соответствовать правилу вне зависимости от того, содержит оно слово «бесплатно» или нет, то есть правило, по сути, не содержит условий для этого слова. С другой стороны, если оба бита равны нулю, правилу не будут соответствовать никакие письма, поскольку либо один, либо другой бит всегда ошибается и такой фильтр пропустит любые письма (ой!). В целом письмо соответствует правилу, только если оно разрешает весь паттерн содержащихся и отсутствующих в нем слов. Приспособленностью правила может быть, например, процент писем, который оно правильно классифицирует. Начиная с популяции произвольных строк, каждая из которых представляет собой правило с произвольными условиями, генетический алгоритм будет выводить все более хорошие правила путем повторяющегося кроссинговера и мутаций самых подходящих строк в каждом поколении. Например, если в текущей популяции есть правило «Если письмо содержит слово “бесплатный” — это спам» и «Если письмо содержит слово “легко” — это спам», перекрещивание их даст, вероятно, более подходящее правило «Если письмо содержит слова “бесплатный” и “легко” — это спам», при условии, что перекрест не придется между двумя битами, соответствующими одному из этих слов. Кроссинговер также породит правило «Все письма — спам», которое появится в результате отбрасывания обоих условий. Но у этого правила вряд ли будет много потомков в следующем поколении.
Поскольку наша цель — создать лучший спам-фильтр из всех возможных, мы не обязаны честно симулировать настоящий естественный отбор и можем свободно хитрить, подгоняя алгоритм под свои нужды. Одна из частых уловок — допущение бессмертия (жаль, что в реальной жизни его нет): хорошо подходящая особь будет конкурировать за размножение не только в своем поколении, но и с детьми, внуками, правнуками и так далее — до тех пор пока остается одной из самых приспособленных в популяции. В реальном мире все не так. Лучшее, что может сделать очень приспособленная особь, — передать половину своих генов многочисленным детям, каждый из которых будет, вероятно, менее приспособлен, так как другую половину генов унаследует от второго родителя. Бессмертие позволяет избежать отката назад, и при некотором везении алгоритм быстрее достигнет желаемой приспособленности. Конечно, если оценивать по количеству потомков, самые приспособленные индивидуумы в истории были похожи на Чингисхана — предка одного из двух сотен живущих сегодня людей. Так что, наверное, не так плохо, что в реальной жизни бессмертие не дозволено.
Если мы хотим вывести не одно, а целый набор правил фильтрации спама, можно представить набор — кандидат из n правил в виде строки n × 20 000 битов (20 тысяч для каждого правила, если в данных, как раньше, 10 тысяч разных слов). Правила, содержащие для каких-то слов 00, выпадают из набора, поскольку они, как мы видели выше, не подходят ни к каким письмам. Если письмо подходит к любому правилу в наборе, оно классифицируется как спам. В противном случае оно допустимо. Мы по-прежнему можем сформулировать приспособленность как процент правильно классифицированных писем, но для борьбы с переобучением, вероятно, будет целесообразно вычитать из результата штраф, пропорциональный сумме активных условий в наборе правил.
Мы поступим еще изящнее, если разрешим выводить правила для промежуточных концепций, а затем выстраивать цепочки из этих правил в процессе работы. Например, мы можем получить правила «Если письмо содержит слово “кредит” — это мошенничество» и «Если письмо — мошенничество, значит, это письмо — спам». Поскольку теперь следствие из правила не всегда «спам», требуется ввести в строки правил дополнительные биты, чтобы представить эти следствия. Конечно, компьютер не использует слово «мошенничество» буквально: он просто выдает некую строку битов, представляющую это понятие, но для наших целей этого вполне достаточно. Такие наборы правил Холланд называет системами классификации. Они «рабочие лошадки» эволюционистов — основанного им племени машинного обучения. Как и многослойные перцептроны, системы классификации сталкиваются с проблемой присвоения коэффициентов доверия — какова приспособленность правил к промежуточным понятиям? — и для ее решения Холланд разработал так называемый алгоритм пожарной цепочки. Тем не менее системы классификации используются намного реже, чем многослойные перцептроны.
По сравнению с простой моделью, описанной в книге Фишера, генетические алгоритмы — довольно большой скачок. Дарвин жаловался, что ему не хватает математических способностей, но, живи он на столетие позже, то, вероятно, горевал бы из-за неумения программировать. Поймать естественный отбор в серии уравнений действительно крайне сложно, однако выразить его в виде алгоритма — совсем другое дело, и это могло бы пролить свет на многие мучающие человечество вопросы. Почему виды появляются в палеонтологической летописи внезапно? Где доказательства, что они постепенно эволюционировали из более ранних видов? В 1972 году Нильс Элдридж и Стивен Джей Гулд75 предположили, что эволюция состоит из ряда «прерывистых равновесий»: перемежающихся длинных периодов застоя и коротких всплесков быстрых изменений, одним из которых стал кембрийский взрыв76. Эта теория породила жаркие дебаты: критики прозвали ее «дерганной эволюцией». На это Элдридж и Гулд отвечали, что постепенную эволюцию можно назвать «ползучей». Эксперименты с генетическими алгоритмами говорят в пользу скачков. Если запустить такой алгоритм на 100 тысяч поколений и понаблюдать за популяцией в тысячепоколенных отрезках, график зависимости приспособленности от времени будет, вероятно, похож на неровную лестницу с внезапными скачками улучшений, за которыми идут плоские периоды затишья, со временем длящиеся все дольше. Несложно догадаться, почему так происходит: когда алгоритм достигнет локального максимума — пика на ландшафте приспособленности, — он будет оставаться там до тех пор, пока в результате счастливой мутации или кроссинговера какая-то особь не окажется на склоне более высокого пика: в этот момент такая особь начнет размножаться и с каждым поколением взбираться по склону все выше. Чем выше текущий пик, тем дольше приходится ждать такого события. Конечно, в природе эволюция сложнее: во-первых, среда может меняться — как физически, так и потому, что другие организмы тоже эволюционируют, и особь на пике приспособленности вдруг может почувствовать давление и будет вынуждена эволюционировать снова. Так что текущие генетические алгоритмы полезны, но конец пути еще очень далеко.
Дилемма изучения–применения
Обратите внимание, насколько генетические алгоритмы отличаются от многослойных перцептронов. Метод обратного распространения в любой момент времени рассматривает одну гипотезу, и эта гипотеза постепенно меняется, пока не найдет локальный оптимум. Генетические алгоритмы на каждом этапе рассматривают всю популяцию гипотез и благодаря кроссинговеру способны делать большие скачки от одного поколения к другому. После установления небольших произвольных исходных весов обратное распространение действует детерминистски, а в генетических алгоритмах много случайных выборов: какие гипотезы оставить в живых и подвергнуть кроссинговеру (более вероятные кандидаты — лучше приспособленные гипотезы), где скрестить две строки, какие биты мутировать. Процесс обратного распространения получает веса для заранее определенной архитектуры сети: более густые сети эластичнее, но их сложнее обучать. Генетические алгоритмы не делают априорных допущений об изучаемой структуре, кроме общей формы.
Благодаря этому генетические алгоритмы с намного меньшей вероятностью, чем обратное распространение ошибки, застревают в локальном оптимуме и в принципе более способны прийти к чему-то по-настоящему новому. В то же время их намного сложнее анализировать. Откуда нам знать, что генетический алгоритм получит что-то осмысленное, а не будет, как пьяный, слоняться вокруг да около? Главное здесь — мыслить в категориях кирпичиков. Каждый поднабор битов в строке потенциально кодирует полезный кирпичик, и, если скрестить две строки, кирпичики сольются в более крупный блок, который мы будем использовать в дальнейшем. Иллюстрировать силу кирпичиков Холланд любил с помощью фотороботов. До появления компьютеров полицейские художники умели по показаниям свидетелей быстро рисовать портрет подозреваемого: подбирали бумажную полоску из набора типичных форм рта, потом полоску с глазами, носом, подбородком и так далее. Система из десяти элементов по десять вариантов каждого позволяла составить 10 миллиардов разных лиц. Это больше, чем людей на планете.
