Текст книги "Верховный алгоритм: как машинное обучение изменит наш мир"

Игра в двадцать вопросов[50]50
  Классическая игра, в которую играют с XIX века. Один человек задумывает объект, а у другого человека есть 20 попыток его отгадать.


[Закрыть]

Другое ограничение обратной дедукции заключается в том, что оно требует большого объема вычислений и из-за этого его трудно применять к масштабным наборам данных. Для решения этой проблемы символисты прибегают к индукции с помощью дерева решений. Деревья решений можно считать ответом на вопрос, что делать, если к какому-то частному случаю применимы правила не одного, а целого ряда понятий. Как в таком случае решить, к какому понятию принадлежит этот случай? Если перед нами частично скрытый предмет с плоской поверхностью и четырьмя ножками, как понять, стол это или стул? Один из вариантов – упорядочить правила, например, в порядке уменьшения точности и выбрать первое подходящее. Другой – дать правилам проголосовать. Деревья решений же априори гарантируют, что к каждому случаю будет подобрано ровно одно правило. Это будет так, если каждая пара правил отличается как минимум в одном тестировании атрибутов и такой набор правил можно выстроить в виде дерева решений. Например, посмотрите на следующий набор:

Если вы за уменьшение налогов и против абортов, вы республиканец.

Если вы против уменьшения налогов, вы демократ.

Если вы за уменьшение налогов, за право на аборт и за свободный оборот оружия, вы независимый кандидат.

Если вы за уменьшение налогов, за право на аборт и против свободного оборота оружия, вы демократ.

Все это можно организовать в виде следующего дерева решений:

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

Согласно дереву решений выше, вы либо республиканец, либо демократ, либо независимый кандидат. Невозможна ситуация, когда этих вариантов больше чем один или ни одного. Наборы понятий, обладающие этим свойством, называют наборами классов, а алгоритмы, которые их определяют, – классификаторами. Каждое понятие косвенно определяет два класса: оно само и его отрицание (например, спам и не-спам). Классификаторы – самая широко распространенная форма машинного обучения.

Обучать деревья решений можно с помощью одного из вариантов алгоритма «разделяй и властвуй». Сначала надо выбрать атрибут, который будет протестирован у корня. Затем мы сосредоточимся на примерах с нисходящих ветвей и выберем для них следующие тесты (например, проверим, за или против абортов сторонники уменьшения налогов). Процесс будет повторяться для каждого нового узла, который мы получим путем индукции, пока все примеры в ветви не будут принадлежать к одному классу. В этот момент мы присвоим этой ветви данный класс.

Напрашивается вопрос: как выбрать лучший атрибут для тестирования в узле? Точность – количество правильно предсказанных примеров – работает не очень хорошо, потому что мы не пытаемся предсказать конкретный класс, а, скорее, стремимся постепенно разделять классы, пока не «очистим» все ветви. Это заставляет вспомнить понятие энтропии[51]51
  Информационная энтропия – мера неопределенности или непредсказуемости информации.


[Закрыть] из теории информации. Энтропия набора предметов – мера его неупорядоченности. Если в группе из 150 человек будет 50 республиканцев, 50 демократов и 50 независимых кандидатов, ее политическая энтропия максимальна. С другой стороны, если в группе одни республиканцы, энтропия будет равна нулю, во всяком случае, в отношении партийной принадлежности. Поэтому, чтобы получить хорошее дерево решений, мы выберем в каждом узле атрибут, который в среднем даст самую низкую энтропию классов по всем ее ветвям, с учетом количества примеров в каждой из ветвей.

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

Иметь отдельную ветвь для каждого значения атрибута неплохо, если они дискретные. А как насчет числовых атрибутов? Если выделять ветвь для каждого значения непрерывной переменной, дерево окажется бесконечно широким. Простое решение – выбрать ряд ключевых порогов на основе энтропии и использовать их. Например, «температура пациента выше или ниже 37,7 ℃?». Для выявления у человека инфекции этой информации в сочетании с другими симптомами может быть достаточно.

Деревья решений находят применение во многих областях. Так, они делают важную работу в психологии. Эрл Хант[52]52
  Эрл Хант (Earl Hunt, род. 1933) – американский психолог, специализирующийся на исследовании искусственного интеллекта.


[Закрыть] и его коллеги пользовались деревьями решений в 1960 году для моделирования усвоения человеком новых концепций, а один из магистрантов Ханта, Джон Росс Куинлан, попробовал использовать их в шахматах. Его первоначальная цель была скромной: предсказать результаты эндшпилей «король и ладья против короля и ферзя» на основе ситуации на доске. Теперь же дерево решений, согласно опросам, стало самым широко используемым алгоритмом машинного обучения, что неудивительно: эту методику легко понять и освоить, и обычно она дает довольно точный результат без лишних настроек. Куинлан – самый выдающийся исследователь в школе символистов. Этот невозмутимый прагматичный австралиец год за годом неустанно улучшал деревья решений, сделал их золотым стандартом в области классификации и пишет о них удивительно ясные статьи.

Что бы вы ни хотели предсказать, очень вероятно, что кто-то уже использовал для этого деревья решений. С их помощью разработанный Microsoft игровой контроллер Kinect определяет положение частей тела, получая сигналы от сенсоров глубины, и передает информацию в приставку Xbox. В 2002 году деревья решений обошли группу экспертов, правильно предсказав три из каждых четырех постановлений Верховного суда, в то время как люди дали менее 60 процентов правильных ответов. «Тысячи поклонников деревьев решений не могут ошибаться!» – думаете вы и набрасываете свое дерево, чтобы угадать ответ девушки на ваше приглашение:

Получается, что сегодня вечером она скажет «да». Вы делаете глубокий вдох, достаете телефон и набираете ее номер.

Символисты

Важнейшее убеждение символистов заключается в том, что интеллект можно свести к манипулированию символами. Математик решает уравнения, переставляя символы и заменяя одни другими согласно заранее определенным правилам. Так же поступает логик, когда делает выводы путем дедукции. Согласно этой гипотезе, интеллект не зависит от носителя: можно писать символы мелом на доске, включать и выключать транзисторы, выражать их импульсами между нейронами или с помощью конструктора Tinkertoys. Если у вас есть структура, обладающая мощью универсальной машины Тьюринга, вы сможете сделать все что угодно. Программное обеспечение можно вообще отделить от «железа», и, если вы хотите просто разобраться, как могут учиться машины, вам (к счастью) не надо волноваться о машинах как таковых, за исключением приобретения ПК или циклов на облаке Amazon.

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

Символистское машинное обучение – ответвление инженерии знаний, одной из школ искусственного интеллекта. В 1970‑х у так называемых систем на основе знаний были очень впечатляющие успехи, в 1980‑х они быстро распространились, но потом вымерли. Главная причина – печально известное «узкое горло» приобретения знаний: получать информацию от экспертов и кодировать в виде правил слишком сложное, трудоемкое и подверженное ошибкам занятие, поэтому для большинства проблем такой подход нецелесообразен. Оказалось, что намного легче позволить компьютеру автоматически учиться, скажем, диагностировать заболевания путем просмотра в базах данных симптомов и исходов, чем без конца опрашивать врачей. Внезапно работы таких первопроходцев, как Рышард Михальский, Том Митчелл и Росс Куинлан, приобрели новую значимость, и с тех пор дисциплина непрерывно развивается. (Еще одной важной проблемой систем, основанных на знаниях, было то, что им сложно работать с неопределенностью. Подробнее мы поговорим об этом в главе 6.)

Благодаря своему происхождению и основополагающим принципам символистское машинное обучение ближе к другим областям науки об искусственном интеллекте, чем другие школы машинного обучения. Если информатику представить в виде континента, у символизма будет длинная граница с инженерией знаний. Обмен информацией происходит в обоих направлениях: обучающиеся алгоритмы используют введенное вручную знание, а знание, полученное путем индукции, пополняет базы знаний. Тем не менее вдоль этой границы проходит разлом между рационалистами и эмпириками, и пересечь ее непросто.

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

Но несмотря на популярность деревьев решений, более удобный исходный пункт для поисков Верховного алгоритма – обратная дедукция. У нее есть критически важное качество: в нее легко встраивать знания, а, как нам уже известно, из-за проблемы Юма это существенное преимущество. Кроме того, наборы правил – экспоненциально более компактный способ представления большинства понятий, чем деревья решений. Превратить дерево решений в набор правил несложно: каждый путь от корня к листу становится правилом, и нет никаких подводных камней. С другой стороны, если нужно превратить в дерево решений набор правил, в худшем случае придется разворачивать каждое из них в мини-дерево решений, а затем заменять каждый листок дерева, полученного из правила один, копией дерева для правила два, каждый листок каждой копии правила два копией правила три и так далее, что порождает серьезные проблемы.

Обратная дедукция как сверхученый. Он будет систематически рассматривать доказательства, взвешивать возможные выводы, сопоставлять лучшие и использовать их вместе с другими доказательствами для формулировки дальнейших гипотез, и все это с компьютерной скоростью. Это чисто и изящно, по крайней мере на вкус символиста. С другой стороны, у метода есть ряд серьезных недостатков. Количество возможных выводов очень велико, и, чтобы не заблудиться, приходится не держаться близко к исходному знанию. Обратную дедукцию легко запутать шумом: как разобраться, каких шагов в дедукции не хватает, если предположения или заключения ложны? Еще более серьезно то, что реальные понятия очень часто не определяются сжатым набором правил. Они не черно-белые, а находятся в большой серой зоне между, скажем, спамом и не-спамом, поэтому приходится взвешивать и накапливать слабые доказательства, пока картина не прояснится. В частности, при диагностике заболеваний одним симптомам придается большее значение, чем другим, и неполные доказательства – это нормально. Никто еще не преуспел в обучении набору правил, которое будет определять кошку, глядя на пиксели на картинке, и, наверное, это просто невозможно.

Очень критично по отношению к символистскому обучению настроены коннекционисты. Они считают, что понятия, которые можно определить с помощью логических правил, лишь вершина айсберга, а в глубине есть много такого, что формальные рассуждения просто неспособны увидеть, точно так же как значительная часть работы мозга скрыта в подсознании. Нельзя построить бесплотного автоматического ученого и надеяться, что он сделает что-то полезное: сначала надо одарить его чем-то вроде настоящего мозга, соединенного с настоящими органами чувств, вырастить в реальном мире, возможно, даже ставить ему время от времени подножки. Как же построить такой мозг? Путем обратной инженерии. Если вы решили построить путем обратной инженерии автомобиль, придется заглянуть под капот. Если вы хотите таким же образом создать мозг, надо заглянуть в черепную коробку.

Глава 4
Как учится наш мозг?

С момента своего открытия правило Хебба – краеугольный камень коннекционизма. Своим названием это научное направление обязано представлению, что знания хранятся в соединениях между нейронами. В вышедшей в 1949 году книге The Organization of Behavior («Организация поведения») канадский психолог Дональд Хебб описывал это следующим образом: «Если аксон[53]53
  Нейрит (длинный цилиндрический отросток нервной клетки), по которому передаются исходящие сигналы (нервные импульсы) от тела клетки к иннервируемым органам и другим нервным клеткам.


[Закрыть] клетки A расположен достаточно близко к клетке B и неоднократно или постоянно участвует в ее стимуляции, то в одной или обеих клетках будут иметь место процессы роста или метаболические изменения, которые повышают эффективность возбуждения клеткой A клетки B». Это утверждение часто перефразируют как «нейроны, которые срабатывают вместе, связываются друг с другом».

В правиле Хебба слились идеи психологии, нейробиологии и немалая доля домыслов. Ассоциативное обучение было любимой темой британских эмпириков начиная с Локка, Юма и Джона Стюарта Милля. В Principles of Psychology («Принципы психологии») Уильям Джеймс[54]54
  Уильям Джеймс (William James, 1842–1910) – американский философ и психолог, один из основателей и ведущий представитель прагматизма и функционализма.


[Закрыть] сформулировал общий принцип ассоциации, который замечательно похож на правило Хебба, но вместо нейронов в нем присутствуют процессы в головном мозге, а вместо эффективности стимуляции – распространение возбуждения. Примерно в то же самое время великий испанский нейробиолог Сантьяго Рамон-и-Кахаль провел первые подробные исследования мозга, окрашивая нейроны по недавно изобретенному методу Гольджи[55]55
  Окрашивание по методу Гольджи – техника окрашивания нервной ткани, открытая итальянским физиологом Камилло Гольджи в 1873 году. Самим Гольджи метод был назван «черной реакцией».


[Закрыть], и каталогизировал свои наблюдения, как ботаники классифицируют новые виды деревьев. Ко времени Хебба нейробиологи в общих чертах понимали, как работают нейроны, однако именно он первым предложил механизм, согласно которому нейроны могут кодировать ассоциации.

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

Еще одно отличие между символистским и коннекционистским обучением заключается в том, что первое – последовательное, а второе – параллельное. В случае обратной дедукции мы шаг за шагом разбираемся, какое правило необходимо ввести, чтобы от посылок прийти к желаемым выводам. В коннекционистской модели все нейроны учатся одновременно, согласно правилу Хебба. В этом нашли отражение различия между компьютерами и мозгом. Компьютеры даже совершенно обычные операции – например, сложение двух чисел или переключение выключателя – делают маленькими шажочками, поэтому им нужно много этапов. При этом шаги могут быть очень быстрыми, потому что транзисторы способны включаться и выключаться миллиарды раз в секунду. Мозг же умеет выполнять большое количество вычислений параллельно благодаря одновременной работе миллиардов нейронов. При этом нейроны могут стимулироваться в лучшем случае тысячу раз в секунду, и каждое из этих вычислений медленное.

Количество транзисторов в компьютере приближается к количеству нейронов в головном мозге человека, однако мозг безусловно выигрывает в количестве соединений. Типичный транзистор в микропроцессоре непосредственно связан лишь с немногими другими, и применяемая технология планарных полупроводников жестко ограничивает потенциал совершенствования работы компьютера. А у нейрона – тысячи синапсов. Если вы идете по улице и увидели знакомую, вам понадобится лишь десятая доля секунды, чтобы ее узнать. Учитывая скорость переключения нейронов, этого времени едва хватило бы для сотни шагов обработки информации, но за эти сотни шагов мозг способен просканировать всю память, найти в ней самое подходящее и адаптировать найденное к новому контексту (другая одежда, другое освещение и так далее). Каждый шаг обработки может быть очень сложным и включать большой объем информации.

Это не значит, что с помощью компьютера нельзя симулировать работу мозга: в конце концов, именно это делают коннекционистские алгоритмы. Поскольку компьютер – универсальная машина Тьюринга, он может выполнять вычисления, происходящие в мозге, как и любые другие, при условии, что у него есть достаточно памяти и времени. В частности, недостаток связности можно компенсировать скоростью: использовать одно и то же соединение тысячу раз, чтобы имитировать тысячу соединений. На самом деле сегодня главный недостаток компьютеров заключается в том, что в отличие от мозга они потребляют энергию: ваш мозг использует примерно столько мощности, сколько маленькая лампочка, в то время как электричеством, питающим компьютер Watson, о котором мы рассказывали выше, можно осветить целый бизнес-центр.

Тем не менее для имитации работы мозга одного правила Хебба мало: сначала надо разобраться с устройством головного мозга. Каждый нейрон напоминает крохотное деревце с огромной корневой системой из дендритов[56]56
  Дихотомически ветвящийся отросток нервной клетки, воспринимающий сигналы от других нейронов, рецепторных клеток или непосредственно от внешних раздражителей. Проводит нервные импульсы к телу нейрона.


[Закрыть] и тонким волнистым стволом – аксоном. Мозг в целом похож на лес из миллиардов таких деревьев, однако лес этот необычный: ветви деревьев соединены в нем с корнями тысяч других деревьев (такие соединения называются синапсами), образуя колоссальное, невиданное хитросплетение. У одних нейронов аксоны короткие, у других – чрезвычайно длинные, простирающиеся от одного конца мозга к другому. Если расположить аксоны мозга друг за другом, они займут расстояние от Земли до Луны.

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

Во времена Хебба еще не умели измерять силу синапсов и ее изменения, не говоря уже о том, чтобы разбираться в молекулярной биологии синаптических процессов. Сегодня мы знаем, что синапсы возникают и развиваются, когда вскоре после пресинаптических нейронов возбуждаются постсинаптические. Как и во всех других клетках, концентрация ионов внутри и за пределами нейрона отличается, и из-за этого на клеточной мембране имеется электрическое напряжение. Когда пресинаптический нейрон возбуждается, в синаптическую щель выделяются крохотные пузырьки с молекулами нейротрансмиттеров. Они заставляют открыться каналы в мембране постсинаптического нейрона, из которых выходят ионы калия и натрия, меняющие напряжение на мембране. Если одновременно возбуждается достаточное количество близко расположенных пресинаптических нейронов, напряжение подскакивает и по аксону постсинаптического нейрона проходит потенциал действия. Благодаря этому ионные каналы становятся восприимчивее, а также появляются новые, усиливающие синапс каналы. Насколько нам известно, нейроны учатся именно так.

Следующий шаг – превратить все это в алгоритм.