Дилемма изучения–применения
Обратите внимание, насколько генетические алгоритмы отличаются от многослойных перцептронов. Метод обратного распространения в любой момент времени рассматривает одну гипотезу, и эта гипотеза постепенно меняется, пока не найдет локальный оптимум. Генетические алгоритмы на каждом этапе рассматривают всю популяцию гипотез и благодаря кроссинговеру способны делать большие скачки от одного поколения к другому. После установления небольших произвольных исходных весов обратное распространение действует детерминистски, а в генетических алгоритмах много случайных выборов: какие гипотезы оставить в живых и подвергнуть кроссинговеру (более вероятные кандидаты — лучше приспособленные гипотезы), где скрестить две строки, какие биты мутировать. Процесс обратного распространения получает веса для заранее определенной архитектуры сети: более густые сети эластичнее, но их сложнее обучать. Генетические алгоритмы не делают априорных допущений об изучаемой структуре, кроме общей формы.
Благодаря этому генетические алгоритмы с намного меньшей вероятностью, чем обратное распространение ошибки, застревают в локальном оптимуме и в принципе более способны прийти к чему-то по-настоящему новому. В то же время их намного сложнее анализировать. Откуда нам знать, что генетический алгоритм получит что-то осмысленное, а не будет, как пьяный, слоняться вокруг да около? Главное здесь — мыслить в категориях кирпичиков. Каждый поднабор битов в строке потенциально кодирует полезный кирпичик, и, если скрестить две строки, кирпичики сольются в более крупный блок, который мы будем использовать в дальнейшем. Иллюстрировать силу кирпичиков Холланд любил с помощью фотороботов. До появления компьютеров полицейские художники умели по показаниям свидетелей быстро рисовать портрет подозреваемого: подбирали бумажную полоску из набора типичных форм рта, потом полоску с глазами, носом, подбородком и так далее. Система из десяти элементов по десять вариантов каждого позволяла составить 10 миллиардов разных лиц. Это больше, чем людей на планете.
В машинном обучении и вообще в информатике нет ничего лучше, чем сделать комбинаторный взрыв не врагом, а союзником. В генетических алгоритмах интересно то, что каждая строка косвенно содержит экспоненциальное число строительных блоков — схем, — поэтому поиск намного эффективнее, чем кажется. Дело в том, что каждый поднабор битов в строке — это схема, представляющая некую потенциально подходящую комбинацию свойств, а количество поднаборов в строке экспоненциально. Схему можно представить, заменив не входящие в нее биты звездочкой: например, строка 110 содержит схемы ***, **0, *1*, 1**, *10, 11*, 1*0 и 110. Каждый выбор битов дает свою схему, а поскольку для каждого бита у нас есть два варианта действий (включать / не включать в схему), это дает 2n схем. И наоборот, конкретную схему в популяции могут представлять многие строки, и каждый раз схема неявно оценивается. Представьте, что вероятность выживания и перехода гипотезы в следующее поколение пропорциональна ее приспособленности. Холланд показал, что в таком случае чем более приспособлены представления схемы в одном поколении по сравнению со средним значением, тем с большей вероятностью можно ожидать увидеть их в следующем поколении. Поэтому, хотя генетический алгоритм явно оперирует строками, косвенно он ищет в гораздо более обширном пространстве схем. Со временем в популяции начинают доминировать более приспособленные схемы, и, в отличие от пьяного, генетические алгоритмы находят дорогу домой.
Одна из самых важных проблем как машинного обучения, так и жизни — дилемма изучения–применения. Если вы нашли что-то работающее, лучше просто это использовать или попытаться поискать дальше, зная, что это может оказаться пустой тратой времени, а может привести к более хорошему решению. Лучше быть ковбоем или фермером? Основать новую компанию или управлять уже существующей? Поддерживать постоянные отношения или непрерывно искать свою половинку? Кризис среднего возраста — тяга к изучению после многих лет применения. Человек срывается с места и летит в Лас-Вегас, полный решимости потратить сбережения всей жизни ради шанса стать миллионером. Он входит в первое попавшееся казино и видит ряд игровых автоматов. Сыграть надо в тот, который даст в среднем лучший выигрыш, но где он стоит — неизвестно. Чтобы разобраться, надо попробовать каждый автомат достаточное количество раз, но, если заниматься этим слишком долго, все деньги уйдут на проигрышные варианты. И наоборот, если перестать пробовать слишком рано и выбрать автомат, который случайно показался удачным в первые несколько раундов, но на самом деле не самый хороший, можно играть на нем остаток ночи и просадить все деньги. В этом суть дилеммы изучения–применения: каждый раз приходится выбирать между повторением хода, принесшего наибольший на данный момент выигрыш, и другими шагами, которые дадут информацию, ведущую, возможно, к еще большему выигрышу. Холланд доказал, что для двух игровых автоматов оптимальная стратегия — каждый раз подбрасывать неправильную монету, которая по мере развития событий становится экспоненциально более неправильной. (Только не подавайте на меня в суд, если этот метод не сработает. Помните, что в конечном счете казино всегда выигрывает.) Чем перспективнее выглядит игровой автомат, тем дольше вы должны в него играть, но нельзя совсем отказываться от второго на случай, если в конце концов он окажется лучшим.
Генетический алгоритм похож на вожака банды профессиональных игроков, которые играют в автоматы сразу во всех казино города. Две схемы конкурируют друг с другом, если включают одни и те же биты, но отличаются по крайней мере одним из них, например *10 и *11, а n конкурирующих схем — как n игровых автоматов. Каждый набор конкурирующих схем — это казино, и генетический алгоритм одновременно определяет автомат-победитель в каждом из них, следуя оптимальной стратегии: игре на самых перспективных машинах с экспоненциально увеличивающейся частотой. Хорошо придумано.
В книге «Автостопом по галактике»
[77] инопланетная цивилизация строит огромный суперкомпьютер, чтобы ответить на Главный Вопрос, и спустя долгое время компьютер выдает ответ: «42». При этом компьютер добавляет, что инопланетяне не знают, в чем заключается этот вопрос, поэтому те строят еще больший компьютер, чтобы это определить. К сожалению, этот компьютер, известный также как планета Земля, уничтожают, чтобы освободить место для космического шоссе, за несколько минут до завершения вычислений, длившихся много миллионов лет. Теперь можно только гадать, какой это был вопрос, но, наверное, он звучал так: «На каком автомате мне сыграть?»
Выживание самых приспособленных программ
Первые несколько десятилетий сообщество, занимавшееся генетическими алгоритмами, состояло в основном из самого Джона Холланда, его студентов и студентов его студентов. Примерно в 1983 году самой большой проблемой, которую умели решать генетические алгоритмы, было обучение управлению системами газопроводов. Но затем, примерно в период второго пришествия нейронных сетей, интерес к эволюционным вычислениям начал набирать обороты. Первая международная конференция по генетическим алгоритмам состоялась в 1985 году в Питтсбурге, а потом произошел кембрийский взрыв разновидностей генетических алгоритмов. Некоторые из них пробовали моделировать эволюцию более точно: в конце концов, базовый генетический алгоритм был только грубым ее приближением. Другие шли в самых разных направлениях, скрещивая эволюционные идеи с концепциями из области информатики, которые смутили бы Дарвина.
