Искусственный интеллект

 

ОТ РЕДАКТОРА ПЕРЕВОДА 

Последняя Международная конференция по проблемам искус-ственного интеллекта, прошедшая в США в августе 1977 г., с оче-видностью показала, что это направление переживает сейчас бурный расцвет. Большие успехи за последнее время достигнуты в области создания систем для общения с ЭВМ на естественном языке, пред-ставления и приобретения знаний, эффективных автоматических помощников, облегчающих работу программиста, систем принятия решений и эвристического поиска, доказательства теорем, машинного зрения и роботоподобных устройств.

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

Неустойчивость словосочетания «искусственный интеллект» отчасти объясняется тем, что в нем используется понятие интеллекта (иногда его переводят словом «разум»), хотя создается впечатление, что все меньше и меньше надежды остается на то, что понятию «интеллект человека» в обозримом будущем будет дано точное определение, пригодное одновременно и для философов, и для математиков, и для психологов, и для обыкновенных людей.

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

6 От редактора перевода

лением опыта и ростом технической вооруженности «деинтеллектуа-лизация» в этом смысле различных задач протекает все быстрее.

Еще недавно образование простейших условных рефлексов связывали с разумным поведением. Сегодня же известны работы по написанию программ для ЭВМ, которые по жестким алгоритмам имитируют творческую деятельность математика. Одна из таких программ (Д. Ленат), отправляясь от небольшого числа теоретикомножественных аксиом, открыла новые понятия в теории чисел, касающиеся чисел с большим числом делителей, доказала ряд интересных теорем о таких числах и сейчас продолжает свою работу...

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

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

Поэтому можно только приветствовать попытку Э. Ханта собрать воедино различные методы и идеи, лежащие в основе разнообразных систем, так или иначе относящихся к искусственному интеллекту. Существенно при этом то, что он не пытается отделить методы этого направления от, скажем, кибернетических методов, которые лежат в их основе. Автор считает, что искусственный интеллект базируется на идеях прикладной математики, математической логики, статистики, психологии и т. д. и что результаты, полученные в этих областях, более ценны, чем яркие результаты в области создания роботов или в машинной шахматной игре.

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

В. Л. Стефанюк 

 

ПРЕДИСЛОВИЕ

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

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

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

 

¹) Автор — профессор университета в Сиэтле, штат Вашингтон,— Прим. ред.

 

Благодарности

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

Моя следующая благодарность за научное сотрудничество адресуется д-ру Шарон Сикел, которая не раз заставляла меня обращать серьезное внимание на математическое доказательство теорем, хотя бы с целью убедиться в том, что я понимаю, о чем она говорит. Ее ясные и точные рассуждения в значительной мере определили мое изложение раздела, посвященного доказательству теорем.

Ряд моих коллег помогли мне как непосредственным участием в решении некоторых обсуждаемых здесь научных проблем, так и своими замечаниями по поводу различных утверждений и первоначального варианта текста. Я бы хотел особенно отметить Марка Стикела, Дэвида Гарната, Патрика Расселла, Эдварда Страсбургера и Майкла Делея — все они из Вашингтонского университета. Очень полезные замечания по тексту сделали Эдвард Картеретт из УКЛА, Корделл Грин из Станфордского университета и А. А. Марли из Мак-Гилла.

Большинство упоминаемых здесь оригинальных исследований были выполнены по заказу Отдела научных исследований ВВС США. Общий план книги определился в результате обсуждения с людьми, занимающимися различными применениями вычислительных машин в ВВС, какого рода справочное руководство было бы им полезно. Именно тогда стала особенно очевидной и была наиболее ясно выражена необходимость в книге, содержащей основные методы. Д-р Гленн Финч, в то время работавший в отделе научных исследований, в течение нескольких лет был постоянным источником ободрения и поддержки.

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

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

Ни издательство «Академик пресс», ни моя семья не бросали меня в течение длительных периодов, когда я был мало контактным и казался неспособным получить какие-нибудь осязаемые результаты. Сейчас работа завершена, и издательство получило рукопись, а моя семья — больше времени для общения со мной. Я надеюсь, что не только они будут довольны.

 

ВВЕДЕНИЕ

ОБЛАСТЬ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

 

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

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

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

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

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

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

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

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

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

 

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

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

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

 

¹) Л и П — первые буквы слов «левый» и «правый».— Прим. перев. 

 

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

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

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

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

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

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

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

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

 

¹) Процедура может не завершиться, если «теорема», подлежащая доказательству, не выводится из заданных аксиом. Этот случай подробнее обсуждается в части III.

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

 

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

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

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

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

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

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

 

^l) General Problem Solver.— Прим. перео. 

 

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

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

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

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

 

АϽВ, (1)

 

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

 

¹) С 1965 г. группы МТИ н Станфорда приложили много усилий в области проектирования и создания роботов — проблемы, которой не касались Ньюэлл, Саймон и их коллеги. Точно так же с 1965 г. группа Ньюэлла — Саймона, видимо, стала склоняться больше к занятиям психологическими проблемами. Естественно, любое такое утверждение нельзя относить ко всем членам группы,

 

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

Ꞁ (АϽ В) = Ꞁ (Ꞁ A U В) = (А ^. ꞀВ) (2)

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

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

прийти с Чарли. Но ее никогда не видели вместе с Чарли".

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

П1 (Тетя(дама, Чарли)ϽПрисутствует(дама, Чарли))            (3)

П2 (Ꞁ Присутствует(дама, Чарли))

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

П1 (ꞀA U Р),            П2 ( ꞀР),            ПЗ (А). (4)

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

(АUВ) ^. (ꞀАUС)Ͻ(ВUС). (5)

¹) Всюду в этой книге Ꞁ будет обозначать отрицание, (U —дизъюнкцию и ^. — конъюнкцию. Заметим, что если В — множество утверждений, которые, будучи взяты вместе, должны интерпретироваться как единое утверждение, то ꞀВ — дизъюнкция отрицаний каждого утверждения из В.

²) «Она» была переодетым Чарли.

 

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

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

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

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

1.2. Распознавание образов

Быть может, это и верно, что любой объект является единственным в своем роде, но жизнь была бы невозможна, если бы мы относились к этой мысли слишком серьезно. Для многих целей мы находим удобным считать уникальные существа типичными: типичным персоналом станций обслуживания, типичными лифтерами или сборщиками налогов. Мы применяем знания характеристик общего класса для определения наших действий в конкретном случае, однако во избежание неприятностей следует научиться правильно проводить классификации. Именно эту способность предлагалось считать основой разумного поведения (Боурн, 1966; Брунер, Гуд- нау и Остин, 1956; Гилфорд, 1967; Хант, 1962). Для людей осуществление весьма тонких классификаций — такое обыденное дело, что мы не осознаем, насколько впечатляющ этот процесс. Мужчина, вернувшись домой, сразу узнает свою жену, ребенка, собаку. Очевидно, различия между тем, как жена и тем более собака выглядели утром и вечером, незначительны, но именно в них суть дела. Как мы определим для ЭВМ, какое изменение образа несущественно, а какое потребует новой классификации?

В своей важной ранней работе Селфридж (1959) предложил осуществлять распознавание образов вычислением взвешенной суммы ряда „рекомендованных" классификаций, каждая из которых основана на различных характеристиках распознаваемого объекта (признаках). Хотя индивидуальные рекомендации могут носить почти случайный характер, система в целом может быть достаточно точной. Развитие этой идеи ведет к параллельному методу распознавания образов. Можно считать, что каждый объект имеет простейшее описание, представляемое вектором, элементы которого служат аргументами для ряда функций, и значения этих функций уже сосчитаны. Они в свою очередь служат аргументами для некоторой решающей функции, которая определяет окончательную классификацию.

Это описание, не отражающее полностью идей Селфриджа, пред-ставляет распознавание образов как задачу классификации векторов, или точек в n-мерном пространстве. В монографии Себестиана (1962), связывающей задачи распознавания образов с математической теорией решений, и в блестящем обзоре Мейзела (1972) методов распознавания образов этому подходу была придана более явная форма. Указанные аспекты распознавания образов тесно связаны с классическими статистическими методами многомерного анализа (Андерсон, 1958; Тацуока, 1971).

К проблеме распознавания образов можно подходить также, отталкиваясь от аналогии с биологическими процессами. В некоторых условиях способности животных к распознаванию образов превышают способности любой машины, которую только можно построить. Для простоты мы рассмотрим лишь человеческие способности. При классификации, основанной на непосредственном сенсорном опыте, т. е. при распознавании лиц или произнесенных слов, люди легко превосходят технические устройства. В „несенсорных" ситуациях действия людей на столь эффективны. Например, люди не могут соперничать с программами классификации образов, если правильный способ классификации включает логические комбинации абстрактных свойств, таких, как цвет, размер и форма (Хант, Марин и Стоун, 1966). Проблему осложняет то обстоятельство, что в этих ситуациях не ясно, по какой причине люди действуют нестабильно (т. е. очень хорошо или очень плохо). Какой тип распознавания образов используется в рассуждениях по аналогии? Этот вопрос представляет большой интерес.

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

Нейрологическая теория обучения, выдвинутая канадским пси-хологом Хеббом (1948), хотя и была рассчитана вначале на исполь-зование в качестве модели, предназначенной только для психологии, оказала большое влияние на искусственный интеллект. Ее модификация применялась при определении принципов системы распознавания образов, получившей название персептрон (Розенблатт, 1958, 1962). Персептрон, или, точнее, персептроны (ибо то, что описал Розенблатт, было скорее принципом построения программ, нежели единственной программой) существуют и в форме программ, и как специально сконструированные аналоговые вычислительные машины. Значительные усилия были направлены на анализ общего класса систем распознавания образов, которые представляют персептроны. Были развиты понятия систем линейного распознавания образов и систем пороговой логики. Первый термин относится к методу объединения индивидуальных решений распознающих элементов, соответствующих различным характеристикам, а второй — к использованию устройств, вырабатывающих постоянный сигнал,

1) Допустим, что каждый объект, подлежавши классификации, полностью описывается вектором, состоящим не более чем из k двоичных цифр. Тогда существует не более 2k различимых объектов. Нам нужна функция, которая, получив одно из возможных описаний, дает 1 тогда и только тогда, когда описанный объект принадлежит некоторому классу, и 0 в противном случае. Один из выводов работы Мак-Каллока и Питтса заключается в том, что такую функцию можно построить на сети идеальных нейронов.

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

если уровень их входных сигналов превышает некоторую фиксиро-ванную величину. Была разработана содержательная математическая теория (Нильсон, 1965а), вершиной которой является анализ круга задач, решаемых с применением линейных пороговых логических систем (Минский, Пейперт, 1969).

В работах с персептронами основное внимание уделяется установке весов, приписываемых фиксированному множеству детекторов признаков. Это совпадает с формулировкой задачи, данной Селфрид- жем. Альтернативный метод распознавания образов сводится к поиску „хороших" признаков, которые так четко проводят разделение между классами, что определение подходящего правила приписывания весов признакам не представляет труда. Этому подходу уделялось большое внимание в ряде исследовательских проектов, в особенности руководимых Уром и его сотрудниками (Ур, 1965; Ур и Восллер, 1963), и в советской литературе (Бонгард, 1967). Последние статьи в журнале Pattern Recognition свидетельствуют, что все большее значение придается обнаружению признаков, нежели определению их весов.

Системы распознавания образов, упоминавшиеся до сих пор, представляют собой по меньшей мере аналоги биологического рас-познавания образов. В биологии термин „распознавание образов" неявно относят к классификации на сенсорном уровне. Это проявляется в постоянном обращении к зрительным примерам распознавания образов. Психологи употребляют термин „обучение понятиям" по отношению к задаче, которая математически совпадает с задачей распознавания образов, но отличается от нее в психологическом аспекте. Эту разницу легко проиллюстрировать следующим примером. Вообразим, что написана программа, различающая изображения мужчин и женщин. Что в этом случае означает „показать изображение вычислительной машине"? Это значит, что полутоновые оттенки небольших участков изображения каким-то способом закодированы в числах и полученный вектор взят в качестве входа для программы распознавания образов. Очень простой пример приведен на рис. 1.1.

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

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

 

Рис. 1.1. Простой пример того, как изображение кодируется в вектор для задачи распознавания образов. Большой прямоугольник разбивается на четыре квадранта. Если верхний левый квадрант заштрихован, то первая компонента вектора равна 1, в противном случае — 0. Такие же правила применяются и к другим квадрантам и компонентам вектора.

 

результатов либо проводят второй тест, либо выполняют классификацию объекта. Характер второго теста может зависеть от результатов первого. Этот процесс, очевидно, можно распространить на любое число тестов. Правила классификации такого рода называются последовательными процедурами принятия решений. До последнего времени эти методы мало освещались в литературе по искусственному интеллекту, хотя такие же процедуры изучены подробно в статистике и исследовании операций. Интересно отметить, что по крайней мере в одном случае, когда подход к логическому распознаванию образов был осуществлен с чисто статистических позиций (Морган и Сонквист, 1963), полученные алгоритмы вычисления были очень похожи на те, что появились после независимо выполненной работы Ханта, Марина и Стоуна (1966) в области искусственного интеллекта. В последние несколько лет в литературе по распознаванию образов все большее значение придается последовательным процедурам (Фу, 1969а).

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

 

1.3. Игры а принятие решений

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

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

 

 

Третье основание для изучения игр на ЭВМ заключается в том, что в этой области большую роль играет обучение, хотя сам процесс не вполне понятен. Объяснение умному человеку шахматных правил еще не делает его выдающимся игроком. Необходим опыт, но не ясно, что это такое. Если бы мы могли составлять эффективные игровые программы, которые использовали бы свой опыт, возможно, появились бы некоторые идеи о том, что же значит обучаться, решая сложные задачи. Сэмюэль (1959, 1963, 1967), чья работа по игре в шашки является, наверное, наиболее изощренным исследованием по самоорганизующимся программам для игр, подчеркивал, что суть его работы не в исследовании шашек самих по себе, а в изучении процесса машинного обучения, в котором шашки берутся лишь в качестве удобного объекта.

Работы по игровым программам развивались почти независимо от математических исследований в области „теории игр“. Это отчасти можно объяснить тем, что данные два направления преследуют различные цели. Математический анализ игр изучает стратегии, которым должен следовать идеализированный совершенный игрок. При программировании же действий игрока пытаются добиться приемлемой игры при определенных ограничениях на использование ресурсов. Саймон точно резюмировал суть проблемы, разделив стратегии на оптимизирующие и удовлетворительные. Возможно, описание совершенного игрока сильно отличается от конструкции играющего приемлемо, однако резонно было бы спросить, почему между этими двумя областями исследований не было большей координации.

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

 

1.4. Естественный язык а машинное понимание его

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

Совершенно иной областью применения, требующей анализа лингвистических данных, являются все повторяющиеся попытки создания автоматического переводчика. В начале 50-х годов многие оптимисты считали, что механический перевод можно осуществить в основном за счет достаточно мощной аппаратуры, способной запомнить словарь, поскольку сам процесс перевода мог бы тогда быть достаточно прямым. Теперь оптимистов осталось немного, ибо разнообразные ранние проекты машинного перевода по существу лишь показали, насколько малы наши познания в лингвистике. Одно исследование показало, что, видимо, качество машинного перевода не улучшалось с 1964 по 1971 г. (Синайко, 1971). На самом же деле, если задаться целью создать общий язык для ученых и дипломатов, возможно, было бы легче вернуться к обучению классической латыни во всемирном масштабе, чем конструировать совершенный машинный переводчик! К счастью, более скромные цели и достижимы, и полезны.

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

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

 

1.4. Самоорганизующие системы

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

Фон Нейман (1956) привел доказательство, показывающее, что с точки зрения логики можно создать устройство, которое могло бы воспроизводить или (а) себя, или (б) свои модификации. Его рассуждения основаны на упомянутом ранее доказательстве Мак- Каллока и Питтса того, что любую вычислимую функцию можно реализовать с помощью сети идеальных нейронов. Сначала этот математический довод имел явную биологическую окраску. До-казательство фон Неймана подтвердило лишь возможность суще-ствования самовоспроизводящейся машины. Он не говорил ничего ни о ее структуре, ни об относительной эффективности различных схем „эволюции". Эти вопросы впоследствии разрабатывались, но не привели к убедительным результатам.

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

Винер (1948, 1950) подчеркивал, что ключом к построению системы, способной приспосабливаться к изменяющейся среде, является правильное применение кибернетического принципа. Грубо говоря, кибернетическим называется устройство, для которого одним из входов служит некоторая функция его выхода в предыдущие моменты. На более обыденном языке: если снайпер хочет продолжать хорошую стрельбу, он должен знать, куда пришлись неудачные выстрелы; и, вероятно, основной совет, который можно дать не нашедшему взаимности в любви,— это „следи за реакцией на свои действия". Мы намеренно выбрали примеры из совсем разных областей. Принципы систем, перестраивающихся с помощью управления с обратной связью, можно применить к любой системе, состояние которой описывается заданием взаимно зависимых переменных, начиная с нейрофизиологических объектов, которыми интересовался Винер, и кончая международной политикой. На таком уровне общности термин „кибернетика" связан больше с представлением о мире, чем с точно определенным математическим методом.

Абстрактные теории эволюции и обучения можно без преувеличения считать всеобъемлющими. Идеи, высказанные фон Нейманом и Винером, воплощают многие устройства, но мы не решились бы назвать все эти устройства „интеллектуальными". Хороший пример — автоматический термостат. Можно ли сказать что-нибудь содержательное о самоорганизации самой по себе? Некоторые думают, что можно, но я не из их числа. Я полагаю, что многое из проделанной работы имеет настолько общий характер, что граничит с пустотой. Это предубеждение и послужило причиной того, что самоорганизующиеся системы в книге не обсуждаются. 

 

 

1.6. Роботика

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

Современные исследования в области роботов развиваются по двум главным направлениям, которые за недостатком лучших слов мы будем называть „научным" и „коммерческим". Были времена, когда интерес к научным целям воспринимался, без преувеличения, как стрельба в небо. В 1965 г. на осенней Объединенной конференции по вычислительным машинам Мак-Каллок сообщил, что он пытался создать объект весом не более 5 фунтов, который мог бы перенести высадку на Марс и обладал бы сенсорными возможностями лягушки. После этого „Шейки", робот (в некотором роде), созданный в Станфордском исследовательском институте, был изображен на видном месте в журнале „Лайф", ныне уже не существующем. Несколько ученых заявили, что при условии необходимого обеспечения можно было бы в ближайшем будущем установить на Луне или какой-нибудь другой планете сложные автоматические устройства для исследований — и действительно, очень сложные приборы уже размещены там. Являются они роботами или нет, зависит от вашего определения этого термина. Конструкторы же коммерческих роботов удовлетворились созданием более простых устройств для работы несколько ближе к дому.

Определим произвольно занятия роботами как конструирование реальных устройств, исключив из рассмотрения изготовление игрушек для иллюстрации какого-то принципа, возможно, и полезного в каком-нибудь роботе. Мы знаем о важных проектах создания роботов в трех институтах — МТИ, Станфордском университете и Станфордском исследовательском институте. Некоторая работа проделана также в Эдинбургском университете. Хотя этими исследованиями занимались многие, внешне она выполнена под воздействием идей Мак-Карти, Минского и их коллег, что нашло выражение в инженерной и математической направленности их подхода к искусственному интеллекту, в отличие от подхода Ньюэлла и Саймона, более близкого к психологии. Единственным исключением в этом смысле была разработка системы зрения робота. Здесь психологические и физиологические модели оказали заметное влияние на конструирование робота. Особенно примечательными аспектами роботных проектов являются тяготение к технике обработки списков в программировании и тенденция рассматривать задачи очувствления робота скорее как инженерную проблему, чем как задачу моделирования процессов восприятия в биологии.

Другой характерной чертой научного подхода к роботам был интерес к общим решениям целых классов проблем, иногда за счет того, что для частных задач решение оказывалось неизящным. Например, при создании робота для манипулирования кубиками МакКарти и его группа уделили основное внимание схемам для анализа зрительных сцен и координации в системе рука — глаз, в то время как созданный для этой задачи коммерческий робот мог бы использовать световые лучи известной интенсивности для поверхностей с известной отражательной способностью в предположении, что сцена перед ним всегда удовлетворяет жестким ограничениям. Несмотря на замечания о применении роботов для исследования агрессивных сред, в научных роботных проектах обнаружился только второстепенный интерес к таким задачам, как миниатюризация, защитная упаковка и экономичность. Во время панельной дискуссии на осенней Объединенной конференции по вычислительным машинам в 1968 г. было замечено, что у робота Станфордского университета мозг расположен в машине PDP-10, уши — в обычном микрофоне, его циклопический глаз — в телевизионной камере, а единственная рука помещена на закрепленной стойке. В целом эта система называлась одним словом „робот", докладчик предложил также термин “kludge" ¹). Можно, однако, не очень бояться этой иронии, поскольку основная цель здесь — найти общие решения. Практическая техника появится позже — по крайней мере мы на это надеемся...

Разработки проектов коммерческих роботов пошли в точности по противоположному пути. Очевидно, было бы прекрасно иметь экономичную машину, которая была бы таким же многоцелевым манипулятором, как и человек. Это было бы особенно хорошо, если бы машина в меньшей степени, чем человек, боялась тепла, излучения и не требовала платы за сверхурочную работу. Такого устройства сейчас нет и в ближайшем будущем оно не появится. В то же время есть сотни тысяч видов работ, выполняемых сейчас человеком, которые можно автоматизировать с помощью специально сконструированных машин. Их можно было бы рассматривать как „манипуляторы специального назначения", точно так же, как аналоговую ЭВМ можно считать специализированным переработчиком информации. Все, что пытаются сделать конструкторы коммерческих роботов, — это разработать легко программируемые манипуляторы общего назначения. При этом конструкторы должны найти компромисс между общностью, эффективностью решения для определенных задач и стоимостью. Определение этого оптимума будет зависеть от развития техники и от назначения системы и будет время от времени изменяться. Материалы конференций по ЭВМ в конце 60-х годов позволяют предположить, что существующие коммерческие роботы могут выполнять самые разнообразные задачи. В них трудные места (такие, например, как обработка зрительной информации) хитроумно обходятся: при „инструктировании" робота для выполнения нового задания человек легко может запрограммировать новые решения.

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

 

¹) Решения 12 из 14 нерешенных задач не были доведены до конца из-за ограниченности физических возможностей ЭВМ, имевшихся в то время. Остальные выходили за пределы логических возможностей алгоритма. Модифицированный алгоритм ЛТ на более мощной ЭВМ позднее доказал все 52 теоремы (Стефферуд, 1963).

 

Конец ознакомительного фрагмента.

 

Скачать всю книгу.

 

 

 

 

 

 

 

 

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

²) Точнее, существует алгоритм определения оптимального хода на любой стадии игры я лиц, в которой каждый участник имеет полную информацию и число возможных ходов конечно (Льюс и Райфа, 1957).