1.7. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ

«Интеллект» вычислительных машин

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

Селфридж и Келли (1962) обсуждали вопрос об объеме практических трудностей, стоящих на пути создания разумных машин, после того, как они пришли к выводу о том, что здесь неизвестно никаких теоретических запретов. Хьюберт Дрейфус (1965) заявил, что цифровые вычислительные машины принципиально неспособны на выполнение таких обязательных для интеллекта действий, как «осознание края» и «ясное группирование». Его аргументация была последовательно опровергнута Пейпертом (1968)

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

Попытки упорядочить область искусственного интеллекта никогда не были вполне успешны. В важной обзорной статье Минский (1961а) предложил следующий перечень: поиск, распознавание образов, обучение, решение задач, логические выводы. Такая схема все еще приносит пользу, хотя ее классификационные достоинства сильно снижаются изобилием в литературе утверждений, имеющих форму: «проблема X по существу является проблемой У», где в качестве X и Y можно взять любую пару компонент, о которых говорил Минский. Уже не так давно Минский (1968) написал еще одну содержательную статью об основаниях искусственного интеллекта, где делается вывод, что главной является проблема образования, поддержания и извлечения сведений из некоторой большой их совокупности.

Различные подходы в области искусственного интеллекта

При попытке построить разумные машины мы, естественно, ставим вопрос о том, в чем же состоит секрет естественного интеллекта. Поиски ответа на этот вопрос были связаны с рядом замечательных событий, однако до сих пор никому не удалось раскрыть этой тайны. Розенблаттом (1962) были предложены модели мозга, названные персептронами. Это были сети из искусственных нейронов, в основе которых лежали нейронные модели Маккаллока — Питтса (1943). Изучение персептронов стимулировалось вначале исследователями по распознаванию образов и привело к некоторым изящным математическим результатам по вычислительной геометрии (Минский и Пейщерт, 1969). Однако сложные процессы, связанные с интеллектом, оказались вне пределов возможностей, заложенных в этих простых персептронных моделях.

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

машине. Поэтому такая «искусственная эволюция» не привела к созданию действительно сложных машин.

Другой способ понять, что такое естественный интеллект животных, состоит в том, чтобы изучать их поведение и в особенности поведение человека при решении задач. Трейвис 1963, 1967) обсуждает роль самонаблюдения при создании решателя задач. Ньюэлл, Шоу и Саймон (1959) описали «универсальный решатель задач», который обращается с задачей в значительной степени так же, как это делает человек. Богатым источником идей о том, как человек подходит к решению задач, является книга Пойа (1957).

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

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

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

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

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

Методы поиска решений

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

В настоящей книге мы делаем попытку выделить некоторые главнейшие концепции, связанные с поиском решений, и дать их связное изложение. Несколько иной путь систематизации обсуждения методов поиска решений предлагается Ньюэллом (1969). На построение настоящей книги оказала сильное влияние серия трудных, но очень ценных статей Амареля (1965, 1967, 1969). Формализация некоторых идей поиска решений, которыми мы занимаемся в нашей книге, дана в статье Сэндуолла (1969). Весьма формальное исследование вопросов решения задач и разыгрывания игр содержится в книге Бенерджи (1969).

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

Наше желание различать методы, использующие понятие пространства состояний, и методы, основанные на редукции задачи, связано с тем, что в этих методах применяются различные стратегии поиска. Это различие носит тот же характер, что и отмеченное Амарелем (1967) различие между методами «продукционного типа» и «редукционного типа». Слейджл (1963а) при описании своей программы, предназначенйой для символического интегрирования, также счел полезным использовать понятие сведения задачи к подзадачам. По нашему убеждению, работу универсального решателя задач (General Problem Solver) Ньюэлла и его сотрудников (Эрнст и Ньюэлл, 1969) гораздо легче себе уяснить, если его описывать как решатель задач, опирающийся на сведение задачи к подзадачам.

Использование формальных методов для построения логических выводов при решении задач может быть обнаружено в заметках Маккарти (1958, 1963) о системе, «воспринимающей советы». Эта система должна была выводить решения для задач из большого количества аксиом, представляющих те знания, которые имеются у решателя. Такой системе очень легко давать «советы», просто добавляя новые аксиомы. Работа Блэка (1964) была одной из первых работ, основанных на этой идее. О. некоторых из последних работ в этой области будет идти речь в гл. 7.

Ряд блестящих идей о решении больших комбинаторных задач высказал Лин Шен (1965, 1970). Он привел несколько эффективных стратегий разбиения задачи на подзадачи.

Приложения программ решения задач

Стоит задаться вопросом о том, был ли хоть один из методов, так хорошо работающих на головоломках и играх, когда-либо с пользой применен для «реальных» задач. Методы, использующие пространство состояний, нашли применение для решения задач исследования операций, таких, как известная задача о коммивояжере. Примером может служить метод, предложенный в диссертации Шапиро (1966) и рассмотренный затем Беллмором и Немхозером (1968). Хотя задача о коммивояжере может показаться легкомысленной, как головоломки и игры, она служит моделью важных с экономической точки зрения проблем, возникающих при составлении расписаний и планировании производства.

Другие приложения метода, использующего пространство состояний, даны в работе Уитни (1969) о дистанционном управлении манипуляторами, в работе Йелинека (1969) о последовательном декодировании и в работе Монтанари (1970) о подборе хромосом. Методы, основанные на редукции задачи, были использованы в одной системе, осуществляющей интегрирование в символической записи (Слейджл, 1963а), и в системе, анализирующей данные с масспектрографа (Фейгенбаум, Букхэнан и Ледерберг, 1971),

Важнейшая литература по искусственному интеллекту

По вопросам искусственного интеллекта имеется много обзоров и существует обширная литература. Один из первых аннотированных списков литературы принадлежит Минскому (19616). Более поздние обзоры Фейгенбаума (1963) и Соломонова (1966) содержат много дополнительных работ. Еще больше литературных ссылок, сопровождающихся рассуждениями о будущем этой области исследований, содержится в недавнем обзоре Фейгенбаума (1969).

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

Журнал Artificial Intelligence, целиком предназначенный для работ по искусственному интеллекту, начал издаваться в 1970 г. Статьи по этой тематике время от времени публикуются также в Journal of the Association for Computing Machinery.

В США координацию деятельности в области искусственного интеллекта осуществляет специальная исследовательская Группа по искусственному интеллекту (SIGART) Ассоциации вычислительных устройств (ACM). Она издает информационный бюллетень, в котором время от времени появляются реферативные материалы, нигде больше не публикуемые. В Европе издается информационный бюллетень Группой искусственного интеллекта и моделирования поведения (AISB) Британского общества вычислительных машин.

Программы решений задач были отшлифованы на ряде головоломок и игр. Хорошими книгами по головоломкам являются книги Мартина Гарднера (1959, 1961), который редактирует раздел головоломок в журнале The Scientific American. Интересны также книги по головоломкам Дьюденея (1958, 1967), известного английского составителя головоломок. В книге головоломок Шуха (1968) особо выделяются стратегии поиска-методом проб и ошибок и редукции задач. У игры в пятнадцать имеется длительная история, которая обсуждается Мартином Гарднером (1964, 1965а, б, в) и Боллом (1931).

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

Задачи

(см. скан)

(см. скан)