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

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

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

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

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

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

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

Одним из самых выдающихся студентов Холланда был Джон Коза78. В 1987 году он возвращался на самолете в Калифорнию с конференции в Италии, и его озарило: почему бы не получать путем эволюции полноценные компьютерные программы, а не сравнительно простые вещи вроде правил «Если…, то…» и контроллеров газопроводов? А если поставить себе такую цель, зачем держаться за битовые строки как их представление? Программа на самом деле — дерево обращений к подпрограммам, поэтому лучше непосредственно скрещивать эти поддеревья, а не втискивать их в битовые строки и рисковать разрушить отличные подпрограммы, перекрещивая их в произвольной точке.

Например, представьте, что вы хотите вывести программу, вычисля­ющую длину года на некой планете (T) на основе ее расстояния от солнца (D). По третьему закону Кеплера, T — это квадратный корень из D в кубе, умноженный на постоянную C, которая зависит от используемых единиц времени и расстояния. Генетический алгоритм должен уметь работать на основе данных Тихо Браге о планетарных движениях, как когда-то сам Кеплер работал. В подходе Коза D и C — это листья программного дерева, а операции, которые их соединяют, например умножение и извлечение квадратного корня, — это внутренние узлы. Вот программное дерево, которое правильно вычисляет T:

В генетическом программировании, как Коза назвал свой метод, мы скрещиваем два программных дерева, произвольно меняя местами два их поддерева. Например, одним из результатов кроссинговера деревьев на рисунке ниже, проведенного в выделенных узлах, будет правильная программа для вычисления T:

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

Конечно, расчет продолжительности планетарного года — очень простая задача: в ней есть только умножение и квадратный корень. В целом программные деревья могут включать полный спектр элементов программирования, например утверждения «если… то…», циклы и рекурсию. Более показательный пример возможностей генетического программирования — это определение последовательности действий робота для достижения определенной цели. Представьте, что я попросил своего офисного робота принести мне степлер из кладовки. У робота для этого есть большой набор возможных действий: пройти по коридору, открыть дверь, взять предмет и так далее. Каждое из них, в свою очередь, может состоять из различных поддействий: например, протянуть манипулятор к предмету, схватить его в самых разных точках. В зависимости от результатов предыдущих действий новые действия могут выполняться или не выполняться, иногда нужно их повторить некоторое количество раз и так далее. Задача состоит в том, чтобы составить правильную структуру действий и поддействий, а также определить параметры каждого из них, например, как далеко выдвинуть манипулятор. Из «атомарных», мельчайших действий робота и их допустимых комбинаций генетическое программирование может собрать сложное поведение для достижения желаемой цели. Многие ученые таким образом выводили стратегии для роботов-футболистов.