Часть I. ВВЕДЕНИЕ

Глава 1. ОБЛАСТЬ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

1.0. Существует ли она?

В университетах США действуют более 100 учебных программ в области вычислительных наук. По существу каждая из них включает курс под названием искусственный интеллект. Фактически, как оказалось, методами программирования, предназначенными для исследований по искусственному интеллекту, занимается больше людей, чем методами обработки коммерческих данных (Эллиот,

1968). Эти учебные программы отражают соотношение между соответствующими объемами проводимых научных исследований. Издается журнал под названием Artificial Intelligence („Искусственный интеллект") и серия отчетов о научных конференциях по машинному разуму. Что же дает начало этой бурной деятельности?

Если бы физики или химики взялись дать абстрактные определения своих областей знания, то вы скорее всего не нашли бы разногласий ни среди тех, ни среди других. Вряд ли бы обнаружилось такое единодушие, если бы пришлось собрать вместе разных ученых, занимающихся искусственным интеллектом. Интересно, однако, что, познакомившись детально с учебными курсами, которые они читают, и исследованиями, которые они проводят, вы, вероятно, нашли бы у них много общего. Рекомендованная Ассоциацией по вычислительной технике (АВТ) программа по вычислительным наукам содержит основу для курса А9, Искусственный интеллект, в которой перечисляются: доказательство теорем, игры, распознавание образов, решение задач, адаптивное программирование, принятие решений, сочинение музыки вычислительной машиной, обучающиеся сети, обработка данных на естественном языке, а также вербальное и концептуальное обучение в качестве подходящих для изучения тем (Комитет по учебным программам АВТ, 1968). Подобные направления отражены и в научной литературе. Таким образом,

нет сомнений в факте существования этой области научной деятельности. Но какова степень ее значимости?

В одном из тестов, предназначенных для проверки жизненности научного направления, предлагается ответить на вопрос: „Влияет ли данное научное направление на области знания, тесно связанные с ним?“. По этому критерию искусственный интеллект оценивается достаточно высоко. Методы программирования, развитые для исследований по искусственному интеллекту, широко распространились в области программирования для ЭВМ вообще. Многие концепции искусственного интеллекта, несомненно, повлияли на развитие психологии в ряде ее областей (Хант, 1968; Фридзида, 1972; Лоэлин, 1968; Миллер, Галантер и Прибрам, 1960; Вейсстейн, 1969). В химии методы искусственного интеллекта были применены к анализу данных масс-спектроскопии (Ледерберг и Фейгенбаум, 1968) и при планировании синтеза органических молекул (Кори и Випке, 1969).

Оказалось, что существует содержательная область знаний, общие принципы которой трудно выделить. Проблема, по-видимому, заключается в определении понятия интеллекта. Психологи, которые некоторое время занимались проблемой определения интеллекта, приняли прагматический подход, состоящий в том, что интеллект — это то, что измеряется в интеллектуальных тестах. Также поступлю и я. Для первых 90% этой книги „искусственный интеллект" будет означать просто набор дисциплин, изучаемых в соответствующих курсах по искусственному интеллекту. Я выделю группу тем, для меня наиболее интересных или важных, и буду говорить о них достаточно подробно. Принимая этот подход, я откладываю рассмотрение таких нерешенных общих философских вопросов, как „Может ли машина думать?" и „Можно ли говорить, что машина понимает?", до тех пор, пока не будет установлена общая основа фактического знания. С этой целью книга разделена на четыре части. Первая содержит обзор различных направлений искусственного интеллекта (гл. 1) и попытку соединить проблемы искусственного интеллекта с некоторыми нашими представлениями о вычислимости и абстрактных вычислительных устройствах (гл. 2). Я не буду пытаться дать исчерпывающую историю вопроса, но подобная книга должна содержать некоторый обзор и по крайней мере несколько замечаний об историческом развитии области. Кроме того, глава об абстрактных вычислениях будет не строгим введением в эту проблему, а скорее очерком общего понятия вычислимости с акцентом на взаимосвязи между теорией вычислимости и искусственным интеллектом.

Остальные главы делятся на разделы, посвященные трем независимым направлениям исследований, являющимся основой всего искусственного интеллекта: распознаванию образов, решению задач и машинному восприятию и пониманию. Я не пытался дать подробный

обзор литературы (по этому вопросу опубликовано более 1500 статей). Моя цель — детально объяснить подходы и принципы, наиболее перспективные в каждой из обсуждаемых областей. Таким образом, полнота изложения здесь приносится в жертву; многие исследования просто не упоминаются.

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

В последней главе я обратился к философским вопросам, которых до сих пор избегал. Мой ответ на вопрос „Может ли машина думать?, возможно, не удовлетворит приверженцев двух крайних точек зрения.

1.1. Решение задач

Термин „решение задач" имеет довольно ограниченное значение в лексиконе искусственного интеллекта. Задача считается поставленной, когда известны текущее состояние, описание характеристик целевого состояния и операции, с помощью которых можно переходить от одного состояния к другому. При этом возможны ограничения, учитывающие, что на пути решения в определенные состояния приходить не следует. Эта формулировка известна как подход в пространстве состояний. Несколько следующих примеров показывают, насколько широко он применим.

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

При доказательстве теорем заданы множество истинных утверждений (посылки) и утверждение, истинность которого неизвестна

(теорема, подлежащая доказательству). Используя последовательность допустимых операцийг, таких, как правила вывода в алгебре или тригонометрии, расширяем множество истинных утверждений так, чтобы включить в него теорему. Состояния определяются проверенными к текущему моменту утверждениями; операторы задаются правилами вывода.

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

Было отмечено (Фейгенбаум, 1968), что современные исследования по искусственному интеллекту начались с попыток Аллена Ньюэлла, Герберта Саймона и Дж. Шоу написать программы, решающие задачи. Их исследования проводились совместно в корпорации РЭНД и Технологическом институте Карнеги (теперь Университет Карнеги-Мелон). С идейной точки зрения работа РЭНД — Карнеги была важна как сама по себе, так и потому, что она задала тон многим другим исследованиям. Методы же программирования, развитые в ходе этих работ, стали широко использоваться в вычислительных науках вообще.

Ньюэлл и его коллеги (1957) сначала создали программу Логик-Теоретик (ЛТ), предназначенную для доказательства теорем в исчислении высказываний. С помощью ЛТ были успешно доказаны 38 из 52 теорем гл. 2 книги Уайтхеда и Рассела „Principia Mathematical Поскольку „Principia" считается одной из фундаментальных работ, устанавливающих логические основания математики, достижения ЛТ непременно должны были вызвать интерес. Нетрудно преувеличить или, наоборот, неоправданно уменьшить значение успеха ЛТ в воспроизведении результатов „Principia" (ссылки здесь намеренно опущены), так что полезно было бы иметь точное представление о том, что же было сделано.

Доказательства теорем из гл. 2 книги Уайтхеда и Рассела не произведут на математика впечатления большой глубины. Способные студенты университета, как правило, могут выполнить большинство из них. Яркость достижения Уайтхеда и Рассела состоит не в доказательстве самих теорем, а в осознании того, что их доказательство может служить основой построения, ведущего от логики к математике. Это было большим творческим актом, который Ньюэлл, Саймон и Шоу и не пытались имитировать на вычислительной машине. С другой стороны, задачи гл. 2 не вполне тривиальны. Эти

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

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

Ньюэлл, Саймон и Шоу назвали эту процедуру алгоритмом Британского музея, так как она казалась им столь же разумной, как посадить за пишущие машинки обезьян для того, чтобы заново написать все книги, имеющиеся в Британском музее. Они предложили вместо нее следующий эвристический подход — термин, заимствованный у Пойа (1954, 1957), который считал, что большинство математических доказательств производится на основе догадки о характере решения и затем проверки того, что догадка правильна. Пойа противопоставлял это алгоритмическому способу — механическому осуществлению всех шагов, которые в конце концов обязаны привести к правильному ответу. Алгоритм Британского музея является, очевидно, алгоритмическим. То, что было сделано Ньюэллом и его коллегами, заключалось в написании ряда правил (т. е. программы) для порождения догадок и затем проверки их правильности. Эта идея быстро привилась, и сегодня об „эвристическом программировании" говорят уважительно и до некоторой степени таинственно как о передовом способе программирования, хотя оно

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

При написании программы Логик — Теоретик Ньюэлл, Саймон и Шоу столкнулись с задачами, которые заставили их разработать новый важный прием программирования, обработку списков. Это метод организации памяти ЭВМ так, чтобы основными операндами были упорядоченные множества (списки), а не переменные. Техника обработки списков нашла широкое применение в вычислительных науках (Кнут, 1969). Можно также привести доводы в пользу того, что при обработке сложной информации весьма удобен язык для оперирования списками, так как обработка списков — очень важный инструмент во многих приложениях, использующих в основном символьную, а не численную обработку.

Характерным для подхода РЭНД — Карнеги к решению задач был большой интерес к тому, каким образом люди решают задачи. Программа для ЭВМ представляет собой точно определенное множество правил для работы с данным классом задач. Допустим, что удалось установить разумное соответствие между входом и выходом некоторой программы и стимулами и реакциями, наблюдаемыми в лаборатории психолога. Тогда можно сказать, что на уровне обработки информации эта программа является моделью человека (Ньюэлл, Саймон и Шоу, 1958; Ньюэлл и Саймон, 1961, 1972). Однако моделирование человеческого мышления и создание хорошего решателя задач не одно и то же, так как лишь в одном из этих случаев критерий успеха состоит в получении хорошего решения задач. Ньюэлл и Саймон (1961) не считали эти цели несовместимыми и, очевидно, использовали знание процесса решения задач человеком, чтобы предложить структуру эвристических программ, и обратно. Интуитивно это можно оправдать тем, что люди — это наиболее способные решатели задач; поэтому, если мы хотим построить искусственный разум, нам следовало бы изучить сначала, как работает естественный.

Слабость довода о том, что программирование должно подражать человеческому интеллекту, обнаруживается, когда вы занимаетесь решением задач в специализированной области, для которой методы, не свойственные человеку, могут оказаться достаточно хорошими. Работа Ньюэлла и др. по математическому доказательству теорем подвергалась критике на основании того, что существуют более эффективные, чем алгоритм Британского музея, методы полного перебора, и что использование более совершенных из них может дать лучшие результаты (Уэнг, I960). Эта критика в некотором отношении несостоятельна, поскольку Ньюэлл с коллегами больше интересовались поисками достаточно общих методов, чем собственно результатами доказательства теорем. По этой же причине для Ньюэлла и др. было удобно изучать в качестве примера общего

класса задач теоремы из ,,Principia“, хотя в теории групп могли бы найтись проблемы, более интересные для математика.

Скептик возразит, что умения решать задачи вообще, без связи с какой-либо содержательной областью, не может быть. Следующий проект Ньюэлла с сотрудниками, программа „Универсальный решатель задач" (GPS )) содержит попытку показать, что (а) такое умение существует и (б) оно может обсуждаться на очень конкретном уровне программирования для ЭВМ. В то время как в программу ЛT были явно встроены операции, использованные в формализации Уайтхеда и Рассела для исчисления высказываний, GPS был про граммой для работы с операторами и состояниями на абстрактном уровне. Чтобы применить GPS при решении конкретной задачи, надо задать структуру характерных состояний и операторов (например, размещение миссионеров и людоедов и передвижение лодки) в этой программе. Такая процедура спецификации была названа описанием проблемной среды. Программа GPS пригодна для любой задачи, допускающей преобразование в удобную проблемную среду. Целью исследований GPS было показать, что правильно конкретизированные универсально применимые процедуры (т. е. программы) приводят к решениям, которые, будучи получены людьми, оцениваются как весьма разумные. Список задач, с которыми работали GPS и сходные программы, включает элементарную логику, шахматы, выраженные словами школьные алгебраические задачи и ответы на вопросы, заданные на несколько нечетком английском языке, но относящиеся к очень ограниченной базе данных. В одном из наиболее обширных исследований программа GPS употреблялась для решения десяти разных небольших задач в областях от интегрирования неопределенных интегралов до головоломки о миссионерах и людоедах (Эрнст и Ньюэлл, 1969).

Для нескольких случаев Ньюэлл и Саймон привели в качестве довода, подтверждающего, что их программа моделирует человеческое мышление, сравнение записей доказательства теорем программами с записями комментариев „думающего вслух" человека. В 1972 г. они опубликовали много таких данных и предложили общую методику составления программ, предназначенных для моделирования мышления (Ньюэлл и Саймон, 1972).

Примерно в то же время, когда работы группы РЭНД — Карнеги стали привлекать к себе внимание, в Массачусетском технологическом институте (МТИ) сформировалась тесно с ней связанная и такая же активная группа под руководством Марвина Минского и Джона Мак-Карти. Впоследствии Мак-Карти и Фейгенбаум, член группы Карнеги, вдвоем ушли в Станфордский университет, который вместе со Станфордским исследовательским институтом также стал ведущим центром в занятиях искусственным интеллектом.

И непосредственно через исследования членов групп, и косвенно, вследствие того, что был вовлечен престиж соответствующих институтов и университетов, группы МТИ и Станфорда оказали сильное влияние на американские работы по решению задач на ЭВМ.

В противоположность ранним исследованиям Карнеги — РЭНД исследования в МТИ больше относились к формальным математическим представлениям. Среди типичных разрабатывавшихся проблем были интегрирование неопределенных интегралов (Слейгл, 1963), вопросно-ответные системы с использованием простых баз данных (Рафаэль, 1964), объединение дедуктивных рассуждений с информационным поиском (Мак-Карта, 1959; Слейгл, 1965; Грин, 1969) и неувядаемая проблема игры ЭВМ в шахматы (Гринблатт и др., 1968). Казалось, что Мак-Карти, Минский и их коллеги рассматривали искусственный интеллект скорее как расширение математики и символической логики, чем как дисциплину, параллельную психологии. Они были крайне аккуратны в формализации вычислительных процедур и соотношении их с математикой в более традиционном понимании, в частности с теорией рекурсивных функций (Мак-Карти, 1961; Беркли и Бобров, 1964). Заслуживают рассмотрения также попытки Амареля (1968) и Бенерджи (1969) формализовать процессы решения задачи, поскольку они представляют собой независимые усилия, направленные к той же цели. Стремление к формализации имеет большую потенциальную ценность, ибо для построения точной и жизнеспособной теории процесса решения задач нужен адекватный формализм. С другой стороны, такой теории сейчас нет, и мы чувствуем, что для многих частных проектов искусственного интеллекта неформальный подход типа подхода Ньюэлла и Саймона будет столь же удовлетворительным, как и отпугивающие зачастую формализмы, которые предлагались.

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

где А — условие задачи, в В — нужное заключение, истинно. Предположим теперь, что А и В — множества утверждений. Если бы мы хотели доказать истинность утверждения (1) с помощью подхода Ньюэлла и Саймона, мы начали бы с множества аксиом и применили бы некоторые правила вывода для получения нового множества аксиом и утверждений-следствий. Затем применили бы какие-то правила вывода к для получения множества и далее третьего множества, четвертого и т. д., пока не обнаружилось бы, что некоторое множество А,- содержит в качестве своего подмножества В, т. е. множество утверждений, подлежащих доказательству.

Другой способ доказательства истинности утверждения (1) состоит в том, чтобы показать, что его отрицание

ложно. Это можно осуществить, показав, что одновременная истинность А и 1 В приводит к противоречию. Робинсон предложил применять для этого всего одно правило вывода, называемое резолюцией. Продемонстируем его идею на простом примере. Рассмотрим известную ситуацию из водевиля:

„Если эта дама приходится Чарли тетей, то она должна прийти с Чарли. Но ее никогда не видели вместе с Чарли

Сделаем довольно очевидный перевод на язык математической логики:

Пусть А обозначает Предложения (3) представляют собой аксиомы задачи. Гипотезой здесь является то, что дама не приходится Чарли тетей 2), и это записывается как Для доказательства этого с помощью резолюции мы должны взять отрицание нашей гипотезы (т. е. ) и добавить к аксиомам полученные в результате предложения. Тогда, переписав предложение в дизъюнктивной форме, получим предложения

Исследуем теперь второй этап вывода по методу Робинсона. Пусть два предложения имеют форму и Тогда

Вывод такого рода называют резолюцией предложений, стоящих слева от знака а предложение справа — резольвентой. Если объединяются два предложения вида и то приходим к противоречию. Формально можно считать резольвентой двух таких предложений пустое предложение Вывод пустого предложения показывает, что исходное множество содержало противоречие (возможно, имплицированное).

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

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

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