Файл: Методыискусственногоинтеллекта.pdf

10
Введение
представления и модели доставляют психологические исследования,
в частности, исследования в области когнитивных наук.
Первые исследования, относящиеся к искусственному интеллекту,
были предприняты почти сразу же после появления первых вычисли- тельных машин.
В 1954 г. американский исследователь А. Ньюэлл (A. Newel) решил написать программу для игры в шахматы. Этой идеей он поделил- ся с аналитиками корпорации «РЭНД» (RAND Corporation (J. Show)
и Г. Саймоном (H. Simon), которые предложили Ньюэллу свою по- мощь. В качестве теоретической основы такой программы было ре- шено использовать метод, предложенный в 1950 г. Клодом Шенноном
(К. Shannon), основателем теории информации. Точная формализация этого метода была выполнена Аланом Тьюрингом (Alan Turing). Он же промоделировал его вручную.
К работе была привлечена группа голландских психологов под руководством А. Де Гроота (A. de Groot), изучавших стили игры выда- ющихся шахматистов. Через два года совместной работы этот кол- лектив создал язык программирования ИПЛ1 — по-видимому первый символьный язык обработки списков. Вскоре была написана и первая
программа, которую можно отнести к достижениям в области искус- ственного интеллекта. Эта была программа «Логик-Теоретик» (1956 г.),
предназначенная для автоматического поиска доказательств теорем в исчислении высказываний.
Собственно же программа для игры в шахматы, NSS, была завер- шена в 1957 г. В основе ее работы лежали так называемые эвристики
(правила выбора в отсутствии теоретических оснований) и описания целей. Управляющий алгоритм пытался уменьшить различия между оценками текущей ситуации и оценками цели или одной из подцелей.
В 1960 г. та же группа на основе принципов, использованных в NSS,
написала программу, которую ее создатели назвали GPS (General
Problem Solver) — универсальный решатель задач. GPS могла справ- ляться с рядом головоломок, вычислять неопределенные интегралы,
решать некоторые другие задачи. Эти результаты привлекли внимание специалистов в области вычислений. Появились программы автома- тического поиска доказательств теорем из планиметрии и решения алгебраических задач.
Джона Маккарти (J. McCarty) из Стэнфорда заинтересовали мате- матические основы этих результатов и вообще символьных вычисле- ний. В результате в 1963 г. он разработал язык ЛИСП (LISP, от List
Processing), основу которого составило использование единого списко- вого представления для программ и данных, применение выражений для определения функций, скобочный синтаксис.

Введение
11
В это же время в СССР, в основном, в Московском государственном университете и Академии наук СССР был выполнен ряд пионерских исследований, возглавленных Вениамином Пушкиным и Дмитрием По- спеловым [1], целью которых было выяснение того, как же, в действи- тельности, человек решает переборные задачи.
В качестве полигона для этих исследований были выбраны различ- ные математические игры, в частности, игра «15» и игра «5», а в каче- стве инструментального метода исследования — регистрация движения глаз или гностическая динамика. Основными методами регистрации движения глаз были электроокулограмма и использование присоски,
помещаемой на роговицу.
Цель каждой такой игры заключается в переходе от некоторой исходной ситуации к конечной. Переходы осуществляются путем по- следовательного перемещения фишек по горизонталям и вертикалям на свободное поле.
Возьмем, например, игру «5», исходная и конечная ситуации в ко- торой выглядят, соответственно, следующим образом:
2 3
5 1
4
и
1 2
3 4
5
Оптимальным образом задача решается за шесть ходов, которые соответствуют перемещениям фишек 1, 4, 5, 3, 2, 1. Решение было бы намного сложнее, если бы на первом ходу двигалась бы, например,
фишка 2, или на втором ходу — фишка 3. Понятно, что задача может быть представлена в виде дерева (или лабиринта), корнем которого является исходная ситуация, а перемещение каждой фишки приводит в новую вершину. Все ситуации являются при таком подходе вер- шинами графа или точками на дереве игры и именно они являются теми элементами, из которых строится «модель мира». Два элемента связывает ход — преобразование одной ситуации в другую.
Такая модель игры приводит, вообще говоря, к полному перебору или «лабиринту» вариантов и составляет основу так называемой лаби- ринтной гипотезы решения переборных задач.
C другой стороны, анализ экспериментальных данных позволил вычленить два вида изменений параметров гностической динамики в процессе обучения решению задачи. А именно, изменения ряда пара-

12
Введение
метров уже при решении второй или третьей из множества однотипных задач у одной из групп испытуемых характеризуется появлением точки излома.
К числу этих параметров относятся время решения задачи, количе- ство осмотров условий, количество осмотров цели, общее количество осмотров, плотность осмотра и отношение числа осмотров условий к числу осмотров цели. У другой же группы испытуемых таких изме- нений не происходит.
Так, например, отношение числа осмотров условий задачи к числу осмотров цели у первой группы испытуемых претерпевает излом после решения второй задачи и продолжает уменьшаться при решении числа последующих задач. У второй группы испытуемых уменьшения этого отношения не происходит. То же относится и к времени решения задач.
Анализ и других экспериментальных данных подтвердил существо- вание некоторых общих тенденций в динамике обучения решению задач.
Есть все основания полагать, что основным фактором, влияющим на временные характеристики этого процесса у первой группы ис- пытуемых, является момент понимания эквивалентности задач или транспозиции (переноса) отношений, сформированных в ходе решения первых задач.
Изучение всей совокупности данных позволяет связать формирова- ние подобной системы отношений со временем решения второй и по- следующих задач — именно тогда формируется то общее, что связы- вает первую и вторую задачи. Осознание общности и, следовательно,
«открытие» эквивалентности происходит при столкновении с третьей задачей.
Сопоставление экспериментальных данных свидетельствует также о том, что соотнесение различных ситуаций связано между собой посредством такого когнитивного компонента, как анализ цели. Иначе говоря, анализ исходной ситуации управляется анализом цели и про- цессом соотнесения исходной и конечной ситуаций. Таким образом,
моделирование исходной ситуации является управляемым компонен- том, а установленные в конечной ситуации отношения являются ре- гулятором этого моделирующего процесса. Сама же модель исходной ситуации рассматривается с точки зрения ситуации конечной.
Эту модель можно также изобразить в виде графа, но вершинами этого графа будут не ситуации, как при использовании «лабиринта»
вариантов, а элементы ситуаций. Ребрами, соединяющими вершины,
будут не переходы из одной ситуации в другую, а те отношения,
которые были выявлены на множестве этих элементов с помощью гностической динамики. Эти соображения составили основу модельной

Введение
13
гипотезы решения переборных задач и привели к появлению в 1964 г.
языка (и метода) ситуационного управления [2].
К исследованиям в области искусственного интеллекта стали про- являть интерес и логики. В том же 1964 г. была опубликована работа ленинградского логика Сергея Маслова «Обратный метод установления выводимости в классическом исчислении предикатов», в которой впер- вые предлагался метод автоматического поиска доказательства теорем в исчислении предикатов.
На год позже (в 1965 г.) в США появляется работа Дж. А. Робинсо- на (J. A. Pobinson), посвященная иному методу автоматического поиска доказательства теорем в исчислении предикатов первого порядка. Этот метод был назван методом резолюций и послужил отправной точкой для создания нового языка программирования со встроенной процеду- рой логического вывода — языка Пролог (Prolog) в 1971 г.
В 1966 г. в СССР Валентином Турчиным был разработан язык рекурсивных функций Рефал, предназначенный для описания языков и разных видов их обработки. Хотя он и был задуман как алгорит- мический метаязык, но для пользователя это был, подобно ЛИСПу и Прологу, язык обработки символьной информации.
В конце 60-х годов появились первые игровые программы, систе- мы для элементарного анализа текста и решения некоторых мате- матических задач (планиметрии, взятия неопределенных интегралов).
В возникавших при этом сложных переборных проблемах количество перебираемых вариантов резко снижалось применением всевозможных эвристик и «здравого смысла». Такой подход стали называть эври-
стическим программированием. Дальнейшее бурное развитие эври- стического программирования шло по пути усложнения алгоритмов и улучшения эвристик. Однако вскоре стало ясно, что существует неко- торый предел, за которым никакие улучшения эвристик и усложнения алгоритма не повысят качества работы системы и, главное, не расширят ее возможностей. Программа, которая играет в шахматы, никогда не будет играть в шашки или карточные игры.
Постепенно исследователи стали понимать, что всем ранее создан- ным программам недостает самого важного — знаний в соответству- ющей области. Специалисты, решая задачи, достигают высоких ре- зультатов, благодаря своим знаниям и опыту; если программы будут обращаться к знаниям и применять их, то они тоже достигнут высокого качества работы.
Это понимание, возникшее в начале 70-х годов, по существу, озна- чало качественный скачок в работах по искусственному интеллекту.
Основополагающие соображения на этот счет высказал в 1977 г. на
5-й Объединенной конференции по искусственному интеллекту амери- канский ученый Э. Фейгенбаум (E. Feigenbaum).

14
Введение
Уже к середине 70-х годов появляются первые прикладные интел- лектуальные системы, использующие различные способы представле- ния знаний для решения задач — экспертные системы. Одной из первых была экспертная система DENDRAL, разработанная в Станфорд- ском университете и предназначенная для порождения формул химиче- ских соединений на основе спектрального анализа. В настоящее время
DENDRAL [3] поставляется покупателям вместе со спектрометром. Си- стема MYCIN предназначена для диагностики и лечения инфекционных заболеваний крови. Система PROSPECTOR прогнозирует залежи полез- ных ископаемых. Имеются сведения о том, что с ее помощью были открыты залежи молибдена, ценность которых превосходила 100 мил- лионов долларов. Система оценки качества воды, реализованная на основе российской технологии SIMER + MIR [4] обнаружила причины превышения предельно допустимых концентрациий загрязняющих ве- ществ в Москве-реке в районе Серебрянного Бора. Система CASNET
предназначена для диагностики и выбора стратегии лечения глаукомы и т. д.
В настоящее время разработка и реализация экспертных систем превратилась в инженерную дисциплину. Научные же исследования сосредоточены в ряде сформировавшихся и формирующихся направле- ний; некоторые из них перечислены ниже.

Введение
15
регированные объекты). Дескриптивная логика вырабатывает методы работы с такими сложными концептами, методы рассуждений об их свойствах и выводимости на них. Дескриптивная логика может быть использована, кроме того, для построения объяснительной компоненты базы знаний.
Онтологические исследования посвящены способам концептуализа- ции знаний и методологическим соображениям о разработке инстру- ментальных средств для анализа знаний.
2. Автоматизация рассуждений. В основе автоматизации рас- суждений лежат различные способы представления знаний.
Автоматизация рассуждений, помимо автоматизации дедуктивных рассуждений, включает: автоматизацию индуктивных рассуждений,
автоматизацию рассуждений на основе прецедентов (case-based reasoning, CBR), на основе аргументации, на основе ограничений,
автоматизацию рассуждений с неопределенностью, рассуждения о действиях и изменениях, автоматизацию немонотонных рассуждений и др. Остановимся кратко на некоторых из них.
Рассуждения на основе прецедентов. Здесь главные проблемы —
«фокусировка поиска» на использовании прошлого опыта, оценка сход- ства прецедентов, поиск алгоритмов адаптации прецедентов и техноло- гии визуализации.
Пусть задано множество прецедентов как множество пар hСЛУЧАЙ,
РЕШЕНИЕi, множество зависимостей между различными атрибутами
СЛУЧАЕВ и РЕШЕНИЙ, а также целевая проблема ЦЕЛЬ. Для возника- ющей новой ситуации («нового случая») требуется найти пару hНОВЫЙ
СЛУЧАЙ, ИСКОМОЕ РЕШЕНИЕi, которая решает целевую проблему.
Алгоритмы для таких задач основаны обычно на сравнении пре- цедентов с новым случаем (в какой-либо метрике), с использованием зависимостей между атрибутами случаев и атрибутами решения. Такие зависимости могут задаваться человеком при построении базы случаев,
или обнаруживаться в базе случаев автоматически. При поиске ре- шения для целевой проблемы выполняется адаптация уже имеющихся в базе прецедентов решения. Для этой адаптации и используются означенные зависимости.
Важной проблемой рассуждений на основе прецедентов (CBR) яв- ляется проблема выбора подходящего прецедента. Естественно искать подходящий прецедент в той области пространства поиска, где нахо- дятся решения сходных проблем. Но как определить, какие именно решения надо считать сходными?
Одна из гипотез, называемая гипотезой компактности, состоит в том, что сходство проблем налагает ограничения на сходство соот-