Шрифт:
Идеальный байесовский агент начинается с задания «априорного распределения вероятности», то есть функции, приписывающей определенную вероятность всем «возможным мирам» – иначе говоря, результатам всех сценариев, по которым может меняться мир {31} . Априорное распределение вероятности включает в себя индуктивное смещение, то есть более простым возможным мирам присваивается более высокая вероятность. (Один из способов формально определить простоту возможного мира – использовать показатель колмогоровской сложности, основанный на длине максимально короткой компьютерной программы, генерирующей полное описание этого мира {32} .) При этом в априорном распределении вероятности учитываются любые знания, которые программисты желают передать агенту.
После того как агент получает со своих сенсоров новую информацию, он меняет распределение вероятности, «обусловливая» распределение с учетом этой новой информации в соответствии с теоремой Байеса {33} . Обусловливание – это математическая операция, которая заключается в присвоении нулевых значений вероятности тем мирам, которые не согласуются с полученной информацией, и нормализации распределения вероятности оставшихся возможных миров. Результатом становится «апостериорное распределение вероятности» (которое агент может использовать в качестве априорного на следующем шаге). По мере того как агент проводит свои наблюдения, распределение вероятности концентрируется на все сильнее сжимающемся наборе возможных миров, которые согласуются с полученными свидетельствами; и среди этих возможных миров наибольшую вероятность всегда имеют самые простые.
Образно говоря, вероятность похожа на песок, рассыпанный на большом листе бумаги. Лист разделен на области различного размера, каждая из которых соответствует одному из возможных миров, причем области большей площади эквивалентны более простым мирам. Представьте также слой песка или любого порошка, покрывающего бумагу, – это и есть наше априорное распределение вероятности. Когда проводится наблюдение, в результате которого исключаются какие-то из возможных миров, мы убираем песок из соответствующих областей и распределяем его равномерно по областям, «остающимся в игре». Таким образом, общее количество песка на листе остается неизменным, просто по мере накопления наблюдений он концентрируется во все меньшем количестве областей. Здесь представлено описание обучения в его самом чистом виде. (Чтобы рассчитать вероятность гипотезы, мы просто измеряем количество песка во всех областях, соответствующих возможным мирам, в которых эта гипотеза истинна.)
Итак, мы определили правило обучения. Чтобы получить агента, нам потребуется также правило принятия решений. Для этого мы наделяем агента «функцией полезности», которая присваивает каждому возможному миру определенное число. Это число представляет собой желательность соответствующего мира с точки зрения базовых предпочтений агента {34} . (Чтобы выявить действие с максимальной ожидаемой полезностью, агент мог бы составить список всех возможных действий. А затем рассчитать условное распределение вероятности с учетом каждого действия – то есть распределение вероятности, которое стало бы следствием обусловливания текущего распределения вероятности после наблюдения за результатами этого действия. И наконец, рассчитать ожидаемую ценность действия можно как сумму ценностей всех возможных миров, умноженных на условную вероятность этих миров с учетом осуществления действия {35} .)
Правило обучения и правило принятия решений задают «определение оптимальности» агента. (В сущности такое же определение оптимальности широко используется в искусственном интеллекте, эпистемологии, философии науки, экономике и статистике {36} .) В реальном мире такого агента получить невозможно, поскольку для проведения необходимых расчетов не хватит никаких вычислительных мощностей. Любая попытка сделать это приводит к комбинаторному взрыву вроде описанного нами при обсуждении КИИ. Чтобы представить это, рассмотрим крошечное подмножество всех возможных миров, состоящее из единственного компьютерного монитора, висящего в бесконечном пустом пространстве. Разрешение монитора – 1000 x 1000 пикселей, каждый из которых постоянно или светится, или нет. Даже такое подмножество всех возможных миров невероятно велико: количество возможных состояний монитора, равное 2(1000 x 1000), превосходит объем всех вычислений, которые когда-либо будут выполнены в обозримой Вселенной. То есть мы не можем даже просто пронумеровать возможные миры в этом небольшом подмножестве всех возможных миров, не говоря уже о том, чтобы провести какие-то более сложные расчеты по каждому из них.
Но определение оптимальности может иметь теоретический интерес, даже несмотря на невозможность его физической реализации. Он представляет собой стандарт, с которым можно соотносить эвристические аппроксимации и который иногда позволяет нам судить, как именно поступил бы оптимальный агент в той или иной ситуации. С некоторыми альтернативными определениями оптимальности мы еще встретимся в двенадцатой главе.
31
Мы сознательно опускаем различные технические подробности, чтобы не перегружать повествование. К некоторым из них будет возможность вернуться в главе 12.
32
Программа p генерирует полное описание строки x, если p, запущенная на (некоторой) универсальной машине Тьюринга U, выдает x; это можно записать как U(p) = x. (Здесь строка x представляет любой возможный мир.) Тогда колмогоровская сложность x равна K(x) = minp {l(p): U(p) = x}, где l(p) это длина p в битах. Соломоновская вероятность x определяется как
33
Байесово обусловливание с учетом свидетельства Е дает (вероятность утверждения [например, Е] есть сумма вероятностей возможных миров, в которых это утверждение истинно.)
34
Или случайным образом выбирает одно из возможных действий с максимальной ожидаемой полезностью, если их несколько.
35
Более сжато ожидаемая полезность действия может быть записана как
36
См., например: [Howson, Urbach 1993; Bernardo, Smith 1994; Russell, Norvig 2010].
Одно из преимуществ связи задачи обучения в определенных областях с общей задачей байесовского вывода состоит в том, что эти новые алгоритмы, делающие байесовский вывод более эффективным, немедленно приводят к прогрессу во множестве различных областей. Например, метод Монте-Карло непосредственно применяется в машинном зрении, робототехнике и вычислительной генетике. Еще одно преимущество заключается в том, что исследователям, работающим в различных областях, стало проще объединять результаты своих изысканий. Графовые модели и байесовские статистики представляют собой общий фокус исследований в таких областях, как машинное обучение, статистическая физика, биоинформатика, комбинаторная оптимизация и теория коммуникации {37} . Заметный прогресс в машинном обучении стал следствием использования формальных результатов, изначально полученных в других областях науки. (Конечно, машинное обучение значительно выиграло от появления более быстрых компьютеров и доступности больших наборов данных.)
37
См.: [Wainwright, Jordan 2008]. У байесовских сетей бесчисленное количество областей применения; см., например: [Pourret et al. 2008].
Последние достижения
Во многих областях деятельности уровень искусственного интеллекта уже превосходит уровень человеческого. Появились системы, способные не только вести логические игры, но и одерживать победы над людьми. Приведенная в табл. 1 информация об отдельных игровых программах демонстрирует, как разнообразные виды ИИ побеждают чемпионов многих турниров {38} .
Таблица 1. Игровые программы с искусственным интеллектом
38
Возможно, некоторые читатели, сочтя это направление не слишком серьезным, зададут вопрос: зачем уделять столь пристальное внимание компьютерным играм? Дело в том, что игровые интеллектуальные системы, пожалуй, дают самое наглядное представление о сравнительных возможностях человека и машины.
Шашки. Уровень интеллекта выше человеческого.
Компьютерная игра в шашки, написанная в 1952 году Артуром Самуэлем и усовершенствованная им в 1955 году (версия включала модуль машинного обучения), стала первой интеллектуальной программой, которая в будущем научится играть лучше своего создателя {39} . Программа «Чинук» (CHINOOK), созданная в 1989 году группой Джонатана Шеффера, сумела в 1994 году обыграть действующего чемпиона мира – первый случай, когда машина стала победителем в официальном чемпионате мира. Те же разработчики, использовав алгоритм поиска «альфа-бета отсечение» в базе данных для 39 трлн эндшпилей, представили в 2002 году оптимальную версию игры в шашки – это программа, всегда выбирающая лучший из ходов. Правильные ходы обеих сторон приводят к ничьей {40}
Нарды. Уровень интеллекта выше человеческого.
Компьютерная игра в нарды, созданная в 1970 году Хансом Берлинером и названная им BKG, в 1979 году стала первой интеллектуальной программой, обыгравшей чемпиона мира в показательном матче – хотя впоследствии сам Берлинер приписывал эту победу удачно брошенным костям {41} .
Созданная в 1991 году Джералдом Тезауро программа TD-Gammon уже в 1992 году достигла такого уровня мастерства, что могла сразиться на чемпионате мира. Ради самосовершенствования программа постоянно играла сама с собой, причем Тезауро использовал такую форму укрепляющего обучения, как метод временных различий {42} .
С тех пор программы для игры в нарды по своему уровню в значительной степени превосходили лучших игроков мира {43}
«Эвриско» в космической битве Traveller TCS. Уровень интеллекта выше человеческого в сотрудничестве с самим человеком {44} .
Дугласом Ленатом в 1976 году была создана программа «Эвриско» (Eurisco), представлявшая собой набор эвристических, то есть логических, правил («если – то»). В течение двух лет (1981, 1982) эта экспертная система выигрывала чемпионат США по фантастической игре Traveller TCS (межгалактическое сражение); организаторы даже меняли правила игры, но ничто не могло остановить победного шествия «Эвриско», в результате они приняли решение больше не допускать «Эвриско» к участию в чемпионате {45} . Для построения своего космического флота и сражения с кораблями противника «Эвриско» использовала эвристические правила, которые – в процессе самообучения – корректировала и улучшала при помощи других эвристических правил
Реверси («Отелло»). Уровень интеллекта выше человеческого.
Программа для игры в реверси Logistello выиграла в 1997 году подряд шесть партий у чемпиона мира Такэси Мураками {46}
Шахматы. Уровень интеллекта выше человеческого.
Шахматный суперкомпьютер Deep Blue в 1997 году выиграл у чемпиона мира Гарри Каспарова, Каспаров, хотя и имел претензии к создателям машины, все-таки заметил в ее игре проблески истинного разума и творческого подхода {47} . С тех пор игровые шахматные программы продолжают совершенствоваться {48}
Кроссворды. Профессиональный уровень.
Программа Proverb в 1999 году стала лучшей среди программ для решения кроссвордов среднего уровня {49} .
Созданная в 2012 году Мэттом Гинзбергом программа Dr. Fill вошла в группу лучших участников чемпионата США по кроссвордам. (Показатели программы не были стабильными. Dr. Fill идеально справилась с кроссвордами, считавшимися наиболее сложными среди участников-людей, но оказалась бессильна перед нестандартными, в которых встречались слова, написанные задом наперед, и вопросы, расположенные по диагонали {50} .)
«Скрабл» («Эрудит»). Уровень интеллекта выше человеческого.
По состоянию на 2002 год программы для игры в слова превосходят лучших игроков среди людей {51}
Бридж. Уровень интеллекта не уступает уровню лучших игроков
Программы для игры в бридж «Контракт» к 2005 году достигли уровня профессионализма лучших игроков среди людей {52}
Суперкомпьютер IBM Watson в телепередаче Jeopardy!. Уровень интеллекта выше человеческого.
IBM Watson, созданный в IBM суперкомпьютер с системой ИИ, в 2010 году обыграл Кена Дженнингса и Брэда Раттера – двух рекордсменов Jeopardy! {53} . Jeopardy! – телевизионная игра-викторина с простыми вопросами из области истории, литературы, спорта, географии, массовой культуры, науки и проч. Вопросы задаются в виде подсказок, при этом часто используется игра слов
Покер. Уровень разный.
Игровые программы для покера на сегодняшний день несколько уступают лучшим игрокам в техасский холдем (популярная разновидность покера), но превосходят людей в некоторых других разновидностях игры {54}
Пасьянс «Свободная ячейка» («Солитер»). Уровень интеллекта выше человеческого.
Развитие эвристических алгоритмов привело к созданию программы для пасьянса «Свободная ячейка» (Free Cell), которая оказалась сильнее игроков самого высокого уровня {55} . В своей обобщенной форме эта игровая программа является NP-полной задачей.
Го. Уровень сильного игрока-любителя.
По состоянию на 2012 год серия программ для игры в го «Дзен» (Zen) использовав дерево поиска методом Монте-Карло и технологии машинного обучения – получила шестой дан (разряд) в быстрых играх {56} . Это уровень весьма сильного любителя. В последние годы игровые программы го совершенствуются со скоростью примерно один дан в год. Если этот темп развития сохранится, то, скорее всего, через десять лет они превзойдут чемпиона мира среди людей
39
См.: [Samuel 1959; Schaeffer 1997, ch. 6].
40
См.: [Schaeffer et al. 2007].
41
См.: [Berliner 1980 a; Berliner 1980 b].
42
См.: [Tesauro 1995].
43
В частности, такие программы по игре в нарды, как GNU [Silver 2006] и Snowie [Gammoned.net, 2012].
44
Процессом создания космического флота и битвами руководил сам Дуглас Ленат, написавший по этому поводу: «Итак, победа стала заслугой и Лената, и Eurisco – в пропорции 60: 40. Основной момент тем не менее состоит в том, что в одиночку ни я, ни программа никогда не справились бы» [Lenat 1983, p. 80].
45
См.: [Lenat 1982; Lenat 1983].
46
См.: [Cirasella, Kopec 2006].
47
См.: [Kasparov 1996, p. 55].
48
См.: [Newborn 2011].
49
См.: [Keim et al. 1999].
50
См.: [Armstrong 2012].
51
См.: [Sheppard 2002].
52
См.: [Wikipedia, 2012 a].
53
См.: [Markoff 2011].
54
См.: [Rubin, Watson 2011].
55
См.: [Elyasaf et al. 2011].
56
См.: [KGS, 2012].
Вряд ли сегодня данные факты смогут произвести хоть какое-то впечатление. Но это обусловлено тем, что наши представления о стандартах несколько смещены, поскольку мы уже знакомы с теми выдающимися достижениями, которые появились после описываемых событий. В прежние времена, например, профессиональное умение шахматиста считалось высшим проявлением умственной деятельности человека. Некоторые специалисты конца 1950-х годов считали: «Если когда-нибудь получится создать удачную машину для игры в шахматы, возможно, люди постигнут суть своих интеллектуальных усилий» {57} . В наше время все выглядит иначе. Остается лишь согласиться с Джоном Маккарти, когда-то посетовавшим, что «стоит системе нормально начать работать, как ее сразу перестают называть искусственным интеллектом» {58} .
57
См.: [Newell et al. 1958, p. 320].
58
См.: [Vardi 2012].
Однако появление интеллектуальных шахматных систем не обернулось тем торжеством разума, на которое многие рассчитывали, – и это имело определенное объяснение. По мнению ученых того времени – мнению, наверное, небезосновательному, – компьютер станет играть в шахматы наравне с гроссмейстерами, только когда будет наделен высоким общимуровнем интеллектуального развития {59} . Казалось бы, великий шахматист должен соответствовать немалым требованиям: иметь крепкую теоретическую подготовку; быть способным оперировать абстрактными понятиями; стратегически мыслить и разумно действовать; заранее выстраивать хитроумные комбинации; обладать дедуктивным мышлением и даже уметь моделировать ход мысли противника. Отнюдь. Выяснилось, что достаточно разработать идеальную шахматную программу на основе алгоритма с узкоцелевым назначением {60} . Если программу поставить на быстродействующий процессор – а скоростные компьютеры стали доступны уже в конце XX века, – то она демонстрирует весьма сильную игру. Однако подобный искусственный интеллект слишком однобок. Он ничего другого не умеет, кроме как играть в шахматы {61} .
59
Ирвинг Гуд предполагал в 1976 году:
Появление программного обеспечения, не уступающего по своему потенциалу гроссмейстерскому уровню, будет означать, что мы уже стоим на пороге <создания искусственного сверхразума. – Н. Б.> [Good 1976].
Даглас Хофштадтер писал в 1979 году в книге «Гёдель, Эшер, Бах», за которую в 1980-м он получит Пулитцеровскую премию:
Вопрос: Будут ли такие шахматные программы, которые смогут выиграть у кого угодно?
Возможный ответ: Нет. Могут быть созданы программы, которые смогут обыгрывать кого угодно, но они не будут исключительно шахматными программами. Они будут программами общего разума и, так же как люди, они будут обладать характером. «Хотите сыграть партию в шахматы?» – «Нет, шахматы мне уже надоели. Лучше давайте поговорим о поэзии…» (Даглас Хофштадтер. Гёдель, Эшер, Бах. Эта бесконечная гирлянда / Пер. с англ. М. А. Эскиной. Самара: Издательский дом «Бахрах-М», 2001. С. 635.) [Hofstadter 1999, p. 678].
60
Минимаксный алгоритм поиска с альфа-бета отсечениями использовался совместно со специфической для шахмат функцией эвристической оценки позиций – это дало в сочетании с удачной библиотекой дебютов и эндшпилей, а также другими хитростями, очень сильную шахматную программу.
61
Впрочем, учитывая достижения в изучении оценочной эвристики в ходе моделирования, многие базовые алгоритмы могли бы хорошо проявить себя в большом количестве других игр.
В других случаях изучения и применения искусственного интеллекта выявились проблемы более сложногопорядка, чем ожидалось, поэтому и развитие шло значительно медленнее. Профессор Дональд Кнут, крупнейший специалист в области программирования и вычислительной математики, с удивлением заметил: «Искусственный интеллект, преуспев сегодня во всем, где требуется “разум”, неспособен на те действия, которые люди и животные совершают “бездумно”, – эта задача оказалась гораздо труднее!» {62} Затруднения вызывала, например, разработка системы управления поведением роботов, а также такие их функции, как распознавание зрительных образов и анализ объектов при взаимодействии с окружающей средой. Тем не менее и сделано было немало, и продолжает поныне делаться, причем работа идет не только над развитием программного обеспечения – постоянно совершенствуются аппаратные средства.
62
См.: [Nilsson 2009, p. 318]. Конечно, Кнут несколько преувеличил успехи машинного разума. Все-таки есть еще интеллектуальные задачи, в которых ИИ не преуспел; например, остаются «непродуманными» такие аспекты, как открытие новых направлений в чистой математике, придумывание свежих философских концепций, создание циклов детективных романов, организация военного переворота, разработка очень нужного и инновационного товара широкого потребления.
В один ряд с исследованием инстинктивного поведения можно поставить логику здравого смысла и понимание естественных языков – явления, которые тоже оказались не самыми легкими для систем искусственного интеллекта. Сейчас принято считать, что решение подобных проблем на уровне, сопоставимом с человеческим, является AI-полной задачей [5] – то есть их сложность эквивалентна трудности разработки машин, таких же умных и развитых, как люди {63} . Иными словами, если кто-то добьется успеха в создании ИИ, способного понимать естественный язык так же, как понимает его взрослый человек, то, скорее всего, он или уже создал ИИ, который может делать все, на что способен человеческий разум, или будет находиться в шаге от его создания {64} .
5
AI-полная задача (где AI – artificial intelligence («искусственный интеллект»)) неформальный термин, который применяется в теории ИИ по аналогии с NP-полным классом задач. По существу означает задачу создания искусственного интеллекта человеческого уровня.
63
См.: [Shapiro 1992].
64
Можно только предполагать, почему машине трудно достичь человеческого уровня в восприятии окружающей действительности, регуляции двигательных функций, здравом смысле и понимании языка. Одна из причин заключается в том, что в нашем мозгу имеется специальный механизм, управляющий этими свойствами, – достигшие в процессе эволюции совершенства нейронные структуры. Логическое мышление и навыки вроде игры в шахматы, в отличие от перечисленных выше способностей, не столь естественны, и потому при решении этих задач мы вынуждены полагаться на ограниченные когнитивные ресурсы общего назначения. Возможно, для вычислений и явно выраженных логических рассуждений наш мозг запускает что-то похожее на «виртуальную машину» – медленный и громоздкий психический симулятор универсального компьютера. Если наше предположение верно, то тогда получается забавная вещь: не КИИ моделирует человеческое мышление, а как раз наоборот – логически мыслящий человек симулирует программу ИИ.