Верховный алгоритм

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

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

Генетический алгоритм похож на вожака банды профессиональных игроков, которые играют в автоматы сразу во всех казино города. Две схемы конкурируют друг с другом, если включают одни и те же биты, но отличаются по крайней мере одним из них, например *10 и *11, а n конкурирующих схем — как n игровых автоматов. Каждый набор конкурирующих схем — это казино, и генетический алгоритм одновременно определяет автомат-победитель в каждом из них, следуя оптимальной стратегии: игре на самых перспективных машинах с экспоненциально увеличивающейся частотой. Хорошо придумано.

В книге «Автостопом по галактике»77 инопланетная цивилизация строит огромный суперкомпьютер, чтобы ответить на Главный Вопрос, и спустя долгое время компьютер выдает ответ: «42». При этом компьютер добавляет, что инопланетяне не знают, в чем заключается этот вопрос, поэтому те строят еще больший компьютер, чтобы это определить. К сожалению, этот компьютер, известный также как планета Земля, уничтожают, чтобы освободить место для космического шоссе, за несколько минут до завершения вычислений, длившихся много миллионов лет. Теперь можно только гадать, какой это был вопрос, но, наверное, он звучал так: «На каком автомате мне сыграть?»

Выживание самых приспособленных программ