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

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

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

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

Дилемма изучения–применения

Обратите внимание, насколько генетические алгоритмы отличаются от много­слойных перцептронов. Метод обратного распространения в любой момент времени рассматривает одну гипотезу, и эта гипотеза постепенно меняется, пока не найдет локальный оптимум. Генетические алгоритмы на каждом этапе рассматривают всю популяцию гипотез и благодаря кроссинговеру способны делать большие скачки от одного поколения к другому. После установления небольших произвольных исходных весов обратное распространение действует детерминистски, а в генетических алгоритмах много случайных выборов: какие гипотезы оставить в живых и подвергнуть кроссинговеру (более вероятные кандидаты — лучше приспособленные гипотезы), где скрестить две строки, какие биты мутировать. Процесс обратного распространения получает вес а для заранее определенной архитектуры сети: более густые сети эластичнее, но их сложнее обучать. Генетические алгоритмы не делают априорных допущений об изучаемой структуре, кроме общей формы.

Благодаря этому генетические алгоритмы с намного меньшей вероятностью, чем обратное распространение ошибки, застревают в локальном оптимуме и в принципе более способны прийти к чему-то по-настоящему новому. В то же время их намного сложнее анализировать. Откуда нам знать, что генетический алгоритм получит что-то осмысленное, а не будет, как пьяный, слоняться вокруг да около? Главное здесь — мыслить в категориях кирпичиков. Каждый поднабор битов в строке потенциально кодирует полезный кирпичик, и, если скрестить две строки, кирпичики сольются в более крупный блок, который мы будем использовать в дальнейшем. Иллюстрировать силу кирпичиков Холланд любил с помощью фотороботов. До появления компьютеров полицейские художники умели по показаниям свидетелей быстро рисовать портрет подозреваемого: подбирали бумажную полоску из набора типичных форм рта, потом полоску с глазами, носом, под­бородком и так далее. Система из десяти элементов по десять вариантов каждого позволяла составить 10 миллиардов разных лиц. Это больше, чем людей на планете.

В машинном обучении и вообще в информатике нет ничего лучше, чем сделать комбинаторный взрыв не врагом, а союзником. В генетических алгоритмах интересно то, что каждая строка косвенно содержит экспоненциальное число строительных блоков — схем, — поэтому поиск намного эффективнее, чем кажется. Дело в том, что каждый поднабор битов в строке — это схема, представляющая некую потенциально подходящую комбинацию свойств, а количество поднаборов в строке экспоненциально. Схему можно представить, заменив не входящие в нее биты звездочкой: например, строка 110 содержит схемы ***, **0, *1*, 1**, *10, 11*, 1*0 и 110. Каждый выбор битов дает свою схему, а поскольку для каждого бита у нас есть два варианта действий (включать / не включать в схему), это дает 2 n схем. И наоборот, конкретную схему в популяции могут представлять многие строки, и каждый раз схема неявно оценивается. Представьте, что вероятность выживания и перехода гипотезы в следующее поколение пропорциональна ее приспособленности. Холланд показал, что в таком случае чем более приспособлены представления схемы в одном поколении по сравнению со средним значением, тем с большей вероятностью можно ожидать увидеть их в следующем поколении. Поэтому, хотя генетический алгоритм явно оперирует строками, косвенно он ищет в гораздо более обширном пространстве схем. Со временем в популя­ции начинают доминировать более приспособленные схемы, и, в отличие от пьяно­го, генетические алгоритмы находят дорогу домой.