Верховный алгоритм. Как машинное обучение изменит наш мир - Педро Домингос

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

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

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

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

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

Одно из последствий применения кроссинговера к программным деревьям вместо битовых строк заключается в том, что получающиеся в результате программы могут быть любого размера и обучение делается более гибким. Однако такие программы имеют тенденцию к разбуханию: по мере эволюции деревья становятся все больше и больше (это еще называют «выживанием толстейших»). Эволюционисты могут утешиться фактом, что программы, написанные человеком, в этом отношении не лучше — Microsoft Windows содержит 45 миллионов строк кода, — к тому же к созданному человеком коду нельзя применить такие простые решения, как прибавление к функции приспособленности штрафа за сложность.

Первым успехом генетического программирования стала в 1995 году разработка электронных схем. Начав с кучи элементов — транзисторов, резисторов и конденсаторов, — система Коза вновь изобрела запатентованный ранее фильтр нижних частот, который можно использовать, например, для усиления басов в танцевальной музыке. С тех пор Коза превратил повторное изобретение запатентованных устройств в своего рода спорт и начал выдавать их дюжинами. Следующей вехой стал патент на разработанную таким образом промышленную систему оптимизации, выданный в 2005 году Ведомством США по патентам и торговым знакам. Если бы тест Тьюринга[79] заключался в обмане патентного эксперта, а не собеседника, 25 января 2005 года вошло бы в учебники истории.

Своей самоуверенностью Коза выделяется даже среди представителей дисциплины, где скромность не в чести. Он видит в генетическом программировании машину для изобретений, Кремниевого Эдисона XXI столетия. Коза и другие эволюционисты верят, что такой алгоритм может получить любую программу, и ставят на него в гонке за Верховным алгоритмом. В 2004 году они учредили ежегодную премию Humies, которую вручают за «соперничающие с человеком» генетические творения. На сегодняшний день присуждено 39 премий.

Несмотря на все успехи и озарения, которые принесли нам генетические алгоритмы в таких вопросах, как градуализм против прерывистого равновесия, одна великая тайна остается неразгаданной: какую роль в эволюции играет половое размножение. Эволюционисты возлагают большие надежды на кроссинговер, однако представители других «племен» считают, что игра не стоит свеч. Ни один из теоретических результатов Холланда не показывает, что кроссинговер полезен: чтобы со временем экспоненциально увеличить частоту наиболее подходящих схем в популяции, достаточно мутаций, а логика «строительных блоков» привлекательна, но быстро сталкивается с проблемами даже при использовании генетического программирования. Когда в ходе эволюции появляются крупные блоки, кроссинговер со все большей вероятностью начинает их разбивать, а если удается вывести очень приспособленную особь, ее потомки, как правило, быстро захватывают популяцию и закрывают собой потенциально более перспективные схемы, содержащиеся в менее приспособленных в целом особях. В результате поиск вариантов сводится к определению чемпиона по приспособленности. Исследователи придумали много приемов сохранения разнообразия в популяции, но результаты пока неубедительны. Инженеры, несомненно, широко используют строительные блоки, но для их правильного соединения нужно, скажем так, много инженерии: сложить их вместе любым старым способом непросто, и неясно, может ли кроссинговер здесь помочь.