Первые исследования в области искусственного интеллекта

Введение
Что такое искусственный интеллект
Истоки (с чего все начиналось)
Основные направления исследований в ИИ
CBR
Моделирование рассуждений на основе ограничений
Немонотонные модели рассуждений
Рассуждения о действиях и изменениях
Рассуждения с неопределенностью
Приобретение знаний, машинное обучение и автоматическое порождение гипотез.
Два подхода к искусственному интеллекту
Заключение
Литература
Приложение 1
Приложение 2

Первые исследования в области искусственного интеллекта

В конце 60-х годов появились первые игровые программы, системы для элементарного анализа текста и решения некоторых математических задач (геометрии, интегрального исчисления). В возникавших при этом сложных переборных проблемах количество перебираемых вариантов резко снижалось применением всевозможных эвристик и «здравого смысла». Такой подход стали называть эвристическим программированием. Дальнейшее развитие эвристического программирования шло по пути усложнения алгоритмов и улучшения эвристик. Однако вскоре стало ясно, что существует некоторый предел, за которым никакие улучшения эвристик и усложнения алгоритма не повысят качества работы системы и, главное, не расширят ее возможностей. Программа, которая играет в шахматы, никогда не будет играть в шашки или карточные игры.
Постепенно исследователи стали понимать, что всем ранее созданным программам недостает самого важного - знаний в соответствующей области. Специалисты, решая задачи, достигают высоких результатов, благодаря своим знаниям и опыту; если программы будут обращаться к знаниям и применять их, то они тоже достигнут высокого качества работы.
Это понимание, возникшее в начале 70-х годов, по существу, означало качественный скачок в работах по искусственному интеллекту.
Основополагающие соображения на этот счет высказал в 1977 году на 5-й Объединенной конференции по искусственному интеллекту американский ученый Э.Фейгенбаум (E.Feigenbaum).
Уже к середине 70-х годов появляются первые прикладные интеллектуальные системы, использующие различные способы представления знаний для решения задач - экспертные системы. Одной из первых была экспертная система DENDRAL, разработанная в Станфордском университете и предназначенная для порождения формул химических соединений на основе спектрального анализа. В настоящее время DENDRAL поставляется покупателям вместе со спектрометром. Имеются сведения о том, что с ее помощью были открыты залежи молибдена, ценность которых превосходит 100 миллионов долларов. Система оценки качества воды, реализованная на основе российской технологии SIMER + MIR несколько лет назад причины превышения предельно допустимых концентрациий загрязняющих веществ в Москве-реке в районе Серебрянного Бора. Система CASNET предназначена для диагностики и выбора стратегии лечения глаукомы и т.д.
В настоящее время разработка и реализация экспертных систем выделилась в самостоятельную инженерную область. Научные же исследования сосредоточены в ряде направлений, некоторые из которых перечислены ниже9.
Основные направления исследований в ИИ
Представление знаний (knowledge representation) - одно из наиболее сформировавшихся направлений искусственного интеллекта. Традиционно к нему относилась разработка формальных языков и программных средств для отображения и описания так называемых когнитивных структур10 [1] . Сегодня к представлению знаний причисляют также исследования по дескриптивной логике, логикам пространства и времени, онтологиям.
Пространственные логики позволяют описывать конфигурацию пространственных областей, объектов в пространстве; изучаются также семейства пространственных отношений. В последнее время эта область, из-за тесной связи с прикладными задачами, становится доминирующей в исследованиях по представлению знаний. Например, для задач роботики важно уметь по изображению некоторой сцены восстановить ее вербальное (формальное) описание, с тем чтобы далее это описание использовать, например, для планирования действий робота11.
Объектами дескриптивной логики являются так называемые концепты, (базовые структуры для описания объектов в экспертных системах) и связанные в единое целое множества концептов (агрегированные объекты). Дескриптивная логика вырабатывает методы работы с такими сложными концептами, рассуждений об их свойствах и выводимости на них. Дескриптивная логика может быть использована, кроме того, для построения объяснительной компоненты базы знаний.
Наконец, онтологические исследования посвящены способам концептуализации знаний и методологическим соображениям о разработке инструментальных средств для анализа знаний.
Различные способы представления знаний лежат в основе моделирования рассуждений, куда входят: моделирование рассуждений на основе прецедентов (case-based reasoning, CBR), аргументации или ограничений, моделирование рассуждений с неопределенностью, рассуждения о действиях и изменениях, немонотонные модели рассуждений, и др. Остановимся на некоторых из них12.
CBR
Здесь главные проблемы – поиск алгоритмов адаптации, "фокусировка поиска" на использовании прошлого опыта, вывод, основанный на оценке сходства и технологии визуализации.
Пусть заданы прецеденты как множество пар <СЛУЧАЙ, РЕШЕНИЕ>, множество зависимостей между различными атрибутами СЛУЧАЕВ и РЕШЕНИЙ, а также целевая проблема ЦЕЛЬ. Для возникающей новой ситуации («нового случая») требуется найти пару <НОВЫЙ СЛУЧАЙ, ИСКОМОЕ РЕШЕНИЕ>, которая решает целевую проблему.
Алгоритмы для таких задач основаны обычно на сравнении прецедентов с новым случаем (в какой-либо метрике), с использованием зависимостей между атрибутами случаев и атрибутами решения. Такие зависимости могут задаваться человеком при построении базы случаев, или обнаруживаться в базе случаев автоматически. При поиске решения для целевой проблемы выполняется адаптация уже имеющегося в базе прецедентов решения. Для этой адаптации и используются означенные зависимости.
Важной проблемой CBR является проблема выбора подходящего прецедента. Естественно искать подходящий прецедент в той области пространства поиска, где находятся решения сходных проблем. Но как определить, какие именно решения надо считать сходными?
Существуют гипотезы, что сходство проблем налагает ограничения на сходство соответствующих гипотез в форме слабой связи между ними. Это обстоятельство и используется для ограничения области поиска решений.
Пусть, например, речь идет о некотором клиенте, который (с супругой) желает две недели провести на Канарах и хочет заплатить за это не более полутора тысяч долларов.
Первый вариант диалога с системой, не обладающей способностями к рассуждениям (и на основе прецедентов тоже):
Клиент: здравствуйте, я бы хотел слетать в отпуск на две недели в июле на Канарские острова. Я бы хотел поехать со своей женой, но не могу заплатить более полутора тысяч долларов.
Система: извините, но такой возможности у нас нет.
Клиент: хорошо, но, может быть, у вас найдется что-нибудь похожее в близком регионе.
Система: не могли бы Вы уточнить, что Вы имеете в виду, говоря о близком регионе.
Клиент: я имею в виду побережье Испании.
Система: извините, но это не близкий регион. Это более тысячи километров от Канарских островов!
Клиент: но климат там похожий…
Система: извините, что Вы имеете в виду, говоря о климате...
Скорее всего, клиент обратится в другое турагенство.
Второй вариант диалога:
Клиент: здравствуйте, я бы хотел слетать в отпуск на две недели в июле на Канарские острова. Я бы хотел поехать со своей женой, но не могу заплатить более полутора тысяч долларов.
Система: извините, такой возможности сейчас нет. Но может быть, Вас устроит побережье Испании?
Клиент: а как насчет климата, он похож на Канарский?
Система: да и, кроме того, билеты дешевле!
Клиент: отлично, забронируйте, пожалуйста13.
Из этого, может быть, не очень серьезного примера видно, что
а) во втором случае клиент имеет дело с системой, которая понимает, что хоть регион и не близок Канарам, но более близок клиенту, во всяком случае, билет дешевле и
б) так как клиент хочет поехать в июле, видимо, его интересуют морские купания и пляжи, а это есть как на Канарах, так и на побережье Испании. Из этого система делает вывод о сходстве ситуаций (описанной клиентом и имеющейся вакансии в ее базе) и на основании этого полагает, что решение «отдых в Испании» является близким решению «отдых на Канарах».
Методы CBR уже применяются в множестве прикладных задач – в медицине, управлении проектами, для анализа и реорганизации среды, для разработки товаров массового спроса с учетом предпочтений разных групп потребителей, и т.д. Следует ожидать приложений методов CBR для задач интеллектуального поиска информации, электронной коммерции (предложение товаров, создание виртуальных торговых агентств), планирования поведения в динамических средах, компоновки, конструирования, синтеза программ14.
Моделирование рассуждений на основе ограничений
Наиболее интересны здесь задачи моделирования рассуждений, основанных на процедурных динамических ограничениях. Они мотивированы сложными актуальными задачами – например, планированием в реальной обстановке.
Под задачей удовлетворения ограничений понимается четверка множеств: множество переменных, множество соответствующих областей переменных, множество ограничений на переменные и множество отношений над областями. Решением проблемы удовлетворения ограничений называется набор значений переменных, удовлетворяющих ограничениям на переменные, такой, что при этом области, которым принадлежат эти значения, удовлетворяют отношениям над областями.
Задача удовлетворения динамических ограничений есть последовательность задач удовлетворения ограничений, в которой каждая последующая задача есть ограничение предыдущей. Эти задачи по смыслу близки задачам динамического программирования. Они связаны также с интервальной алгеброй15.
Немонотонные модели рассуждений
Сюда относятся исследования по логике умолчаний (default logic), по логике "отменяемых" (Defeasible) рассуждений, логике программ, теоретико - аргументационой характеризации логик с отменами, характеризации логик с отношениями предпочтения, построению эквивалентных множеств формул для логик с очерчиванием (circumscription) и некоторые другие. Такого рода модели возникают при реализации индуктивных рассуждений, например, по примерам; связаны они также с задачами машинного обучения и некоторыми иными задачами. В частности, в задачах моделирования рассуждений на основе индукции источником первоначальных гипотез служат примеры. Если некоторая гипотеза Н возникла на основе N положительных примеров (например, экспериментального характера), то никто не может дать гарантии, что в базе данных или в поле зрения алгоритма не окажется N+1 - й пример, опровергающий гипотезу (или меняющий степень ее истинности). Это означает, что ревизии должны быть подвержены и все следствия гипотезы H16.
Рассуждения о действиях и изменениях
Большая часть работ в этой области посвящена применениям ситуационного исчисления - формализма, предложенного Джоном Маккарти в 1968 году для описания действий, рассуждений о них и эффектов действий. Для преобразования плана поведения робота в исполняемую программу, достигающую с некоторой вероятностью фиксированной цели, вводится специальное логическое исчисление, основанное на ситуационной логике. Для этой логики предложены варианты реализации на языке pGOLOG - версии языка GOLOG, содержащей средства для введения вероятностей17.
Активно исследуются логики действий, применение модальных логик для рассуждений о знаниях и действиях.
Рассуждения с неопределенностью
Сюда относится использование байесовского формализма в системах правил и сетевых моделях. Байесовские сети – это статистический метод обнаружения закономерностей в данных. Для этого используется первичная информация, содержащаяся либо в сетевых структурах либо в базах данных. Под сетевыми структурами понимается в этом случае множество вершин и отношений на них, задаваемое с помощью ребер(Рис 1 приложения 2). Содержательно, ребра интерпретируются как причинные связи. Всякое множество вершин Z, представляющее все пути между некоторыми двумя иными вершинами X и Y соответствует условной зависимости между этими двумя последними вершинами.
Далее задается некоторое распределение вероятностей на множестве переменных, соответствующих вершинам этого графа и полученная, но минимизированная (в некотором смысле) сеть называется байсовской сетью.
На такой сети можно использовать, так называемый байесовский вывод, т.е. для вычисления вероятностей следствий событий можно использовать (с некоторой натяжкой) формулы теории вероятностей.
Иногда рассматриваются так называемые гибридные байесовские сети, с вершинами которых связаны как дискретные, так и непрерывные переменные. Байесовские сети часто применяются для моделирования технических систем.
Приобретение знаний, машинное обучение и автоматическое порождение гипотез.
Работы в области приобретения знаний интеллектуальными системами были и остаются важнейшим направлением теории и практики искусственного интеллекта. Целью этих работ является создание методологий, технологий и программных средств переноса знаний (или, как иногда говорят, компетентности), в базу знаний системы. При этом в качестве источников знаний выступают эксперты (т.е. высококвалифицированные специалисты предметных областей), тексты и данные, например, хранимые в базах данных. Соответственно, развиваются различные методы приобретения знаний.
Машинному обучению в мире уделяется большое внимание. Существует множество алгоритмов машинного обучения, среди самых распространенных – алгоритмы класса C4. Один из алгоритмов этого класса С4.5, является, по существу, алгоритмом декомпозиции и строит дерево решений. Исходной информацией для построения этого дерева является множество примеров. С каждой вершиной дерева ассоциируется наиболее (на текущем шаге) частотный класс примеров. На следующем шаге этот принцип рекурсивно применяется к текущей вершине, т.е. множество примеров, связанных с текущей вершиной также разбивается на подклассы. Алгоритм завершает свою работу либо при удовлетворении некоторого критерия либо при исчерпании подклассов (если они заданы).
Активно исследуются методы обучения причинам действий. Иногда говорят о так называемой теории действий, имея в виду ситуационное исчисление в духе Джона МакКарти. В этой теории причины действий и сами действия описываются в виде клаузальных структур (один из видов таких структур представляет собой импликацию, левая часть которой есть конъюнкция атомарных формул, а правая состоит из одной атомарной формулы).
Далее, методы индуктивного логического программирования модифицируются таким образом, чтобы быть применимыми к поиску таких структур. Когда такие структуры найдены, их можно использовать в языках логического программирования для рассуждений о действиях и их причинах18.
Многие работы этого направления посвящены "нейронной парадигме". Нейросетевой подход используется в огромном количестве задач - для кластеризации информации из Интернета, автоматической генерации локальных каталогов, представления образов (в рекурсивных нейронных сетях). Среди активно изучаемых в последнее время тем - неоднородные нейронные модели с отношениями сходства. (Heterogeneous Neural Networks with similarity relation).
Это отношение сходства определяется на множестве входов и множестве состояний сети, а мерой сходства является скалярное произведение векторов либо эвклидово расстояние (где один вектор-вектор входов, а другой распределение весов нейронов, описывающих текущую ситуацию).
Работы по автоматическому порождению гипотез связаны, главным образом, с формализацией правдоподобных рассуждений, поиском зависимостей причинно-следственного типа между некоторыми сущностями. В качестве примеров можно привести порождение гипотез о свойствах химических соединений (прогноз биологических активностей), о возможных причинах дефектов (диагностика) и т.п19.
Два подхода к искусственному интеллекту
Технологии, применяемые в настоящее время в области искусственного интеллекта, можно отнести к двум обширным категориям:
явное моделирование с помощью слов и символов и
неявное моделирование с помощью численных методов.
В первую категорию входят такие приемы, как рассуждения на базе правил, моделей, систем отсчета и конкретных ситуаций. В этой категории проблему можно смоделировать с использованием явно выраженных правил. Например:
Если давление (внутри сосуда) высоко, и выпускной клапан закрыт, значит выпускной клапан заклинило.
Можно составить более сложное правило, чтобы принять в расчет фактор неопределенности:
Если давление (внутри сосуда) высоко, и выпускной клапан закрыт, значит выпускной клапан, возможно, заклинило20.
В своих узких областях применения подобные методы зарекомендовали себя неплохо, но они ограничены по самой своей природе. Эти методы пригодны для работы лишь с явно смоделированными ситуациями и не подходят для неизвестных ситуаций.