Методики ИИ

Качур Д.

Содержание

• Введение
• Знания и их представление
• Представление знаний и процедуры выводов с помощью логики предикатов
• Представление знаний правилами и логический вывод
  • Системы продукций
  • Задачи представления
  • Стратегии поиска для систем продукций
  • Специализированные системы продукций
• Системы дедукции на основе правил
  • Импликационные ППФ
  • Прямая система дедукции
  • Обратные системы продукций
  • Стратегии управления для систем дедукции
  • "Резолюция" внутри графов И/ИЛИ
  • Комбинация прямой и обратной системы
• Сетевые модели представления знаний
  • Модель семантической сети Куиллиана
  • Структурирование знаний
  • Разделение семантической сети
  • Представление семантической сети в виде совокупности фреймов
  • Дедуктивный вывод на семантических сетях
• Особенности различных способов представления знаний
• Приложения
  • Пример преобразования ППФ в форму предложений
• Литература

Введение

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

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

Работа по построению таких систем проводится в области, получившей название искусственный интеллект (ИИ).

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

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

1. Представление знаний. В рамках этого направления решаются задачи, связанные с формализацией и представлением знаний в памяти системы ИИ. Для этого разрабатываются специальные модели представления знаний и языки описания знаний, внедряются различные типы знаний. Проблема представления знаний является одной из основных проблем для системы ИИ, так как функционирование такой системы опирается на знания о проблемной области, которые хранятся в ее памяти.
2. Манипулирование знаниями. Чтобы знаниями можно было пользоваться при решении задачи, следует научить систему ИИ оперировать ими. В рамках данного направления разрабатываются способы пополнения знаний на основе их неполных описаний, создаются методы достоверного и правдоподобного вывода на основе имеющихся знаний, предлагаются модели рассуждений, опирающихся на знания и имитирующих особенности человеческих рассуждений. Манипулирование знаниями очень тесно связано с представлением знаний, и разделить эти два направления можно лишь условно.
3. Общение. В круг задач этого направления входят: проблема понимания и синтеза связных текстов на естественном языке, понимание и синтез речи, теория моделей коммуникаций между человеком и системой ИИ. На основе исследований в этом направлении формируются методы построения лингвистических процессов, вопросно - ответных систем, диалоговых систем и других систем ИИ, целью которых является обеспечение комфортных условий для общения человека с системой ИИ.
4. Восприятие. Это направление включает разработку методов представления информации о зрительных образах в базе знаний, создание методов перехода от зрительных сцен к их текстовому описанию и методов обратного перехода, создание средств для порождения зрительных сцен на основе внутренних представлений в системах ИС.
5. Обучение. Для развития способности систем ИИ к обучения, т.е. к решению задач, с которыми они раньше не встречались, разрабатываются методы формирования условий задач по описанию проблемной ситуации или по наблюдению за ней, методы перехода от известного решения частных задач (примеров) к решению общей задачи, создание приемов декомпозиции исходной задачи на более мелкие и уже известные для систем ИИ. В этом направлении ИИ сделано еще весьма мало.
6. Поведение. Поскольку системы ИИ должны действовать в некоторой окружающей среде, то необходимо разрабатывать некоторые поведенческие процедуры, которые позволили бы им адекватно взаимодействовать с окружающей средой, другими системами ИИ и людьми. Это направление в ИИ разработано очень слабо.

В настоящем пособии рассматриваются только основы первых двух направлений - представление знаний и методы вывода.

Знания и их представление

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

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

Базовая структура экспертной системы приведена на рис. 1.1.

Структурные элементы, составляющие систему, выполняют следующие функции.

База знаний - реализует функции представления знаний в конкретной предметной области и управление ими.

Механизм логических выводов - выполняет логические выводы на основании знаний, имеющихся в базе знаний.

Пользовательский интерфейс - необходим для правильной передачи ответов пользователю, иначе пользоваться системой крайне неудобно.

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

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

Рис 1.1

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

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

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

• логические модели;
• продукционные модели;
• сетевые модели;
• фреймовые модели.

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

Логические модели

В основе моделей такого типа лежит понятие формальной системы.

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

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

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

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

(Семантика - значение единиц языка).

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

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

Продукционные модели

Продукции (наряду с сетевыми моделями) являются наиболее популярными средствами представления знаний в системах ИИ. В общем виде под продукцией понимают выражение вида A ' B. Обычное прочтение продукции выглядит так: ЕСЛИ А, ТО B. Импликация может истолковываться в обычном логическом смысле как знак логического следования B из истинного А. Возможны и другие интерпретации продукции, например А описывает некоторое условие, необходимое, чтобы можно было совершить действие B.

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

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

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

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

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

Сетевые модели

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

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

В качестве простого примера рассмотрим предложения "Куин Мэри является океанским лайнером" и "Каждый океанский лайнер является кораблем". Они могут быть представлены через семантическую сеть (рис 1.2). В этом примере используется важный тип дуг "является".

Рис 1.2

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

Фреймовые модели

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

В качестве идентификатора фрейму присваивается имя фрейма. Это имя должно быть единственным во всей фреймовой системе.

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

Фрейм:	Имя
Имя слота:	Значение слота
Класс:	Животное
Структурный элемент:	Голова, шея, руки, …
Рост:	30 220 см
Масса:	1 200 кг
Хвост:	Нет
Язык:	Русский, английский, китайский …
Фрейм аналогии:	Обезьяна

Рис 1.3

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

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

Представление знаний и процедуры выводов с помощью логики предикатов

• Понятие формальной системы
• Исчисление высказываний как формальная система
• Исчисление предикатов первого порядка
• Правила вывода логики предикатов
• Семантика логики предикатов
• Доказательство методом резолюции
• Система опровержения на основе резолюции
• Стратегии управления для методов резолюции
• Извлечение ответа из опровержения на основе резолюции

Понятие формальной системы

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

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

Формальные системы - это аксиоматические системы, т.е. системы с наличием определенного числа исходных заранее выбранных и фиксированных высказываний, называемых аксиомами.

Формальная система считается заданной, если выполнены следующие условия.

1. Задано некоторое множество, состоящее из конечного или бесконечного числа элементов, которые носят название термов. Имеется другое конечное множество, элементы которого есть связки или операции.
2. Любую линейную упорядоченную совокупность термов и операций называют формулой. Из множества формул выделяют подмножеств правильно построенных формул (ППФ). Для ППФ задают правила их конструирования, т.е. определяется эффективная процедура, позволяющая по данному выражению выяснять, является ли оно ППФ в данной ФС.
3. Выделено некоторое множество ППФ, называемых аксиомами ФС. При этом должна иметься эффективная процедура, позволяющая для произвольной ППФ, решить, является ли она аксиомой.
4. Имеется конечное множество R1, R2, …, Rk отношений между ППФ называемых правилами вывода. Понятие "вывода" также должно быть эффективным, т.е. должна существовать эффективная процедура, позволяющая для произвольной конечной последовательности ППФ решать, можно ли каждый член этой последовательности вывести из одной или нескольких предшествующих ППФ посредством некоторых фиксированных правил вывода. Выводом ФС называется любая последовательность ППФ A1, A2, …, An такая, что для любого i (i = ) ППФ Ai есть либо аксиома ФС, либо непосредственное следствие каких-либо предыдущих ППФ по одному из правил вывода.

ППФ В называется теоремой ФС, если существует вывод ФС, в котором последней ППФ является В.

Любая ФС задается четверкой <T, H, A, R> где T - множество термов и операций; H - множество правил конструирования ППФ; A - система аксиом; R - множество правил вывода.

Можно расширить формальную систему введением дополнительных правил на множества H, A и R. Если на множество H действуют правила h, изменяющие синтаксис ФС, на множество A - правила , изменяющие систему аксиом, и если в ФС разрешается изменять набор правил вывода с помощью некоторых правил , то такое расширение ФС называется семиотической системой.

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

Два класса формальных систем являются математической базой для построения систем ИИ: исчисление высказываний и исчисление предикатов первого порядка.

Исчисление высказываний как формальная система

Сложное высказывание имеет истинностное значение, которое однозначно определяется истинностными значениями простых высказываний, из которых оно составлено.

Например: "Если студент ложится поздно спать и пьет кофе, то утром он встанет в плохом настроении или с головной болью". Это сложное высказывание состоит из следующих простых высказываний:

"Студент ложиться поздно спать"
"Студент пьет на ночь кофе"
"Утром студент встанет в плохом настроении"
"Утром студент встанет с головной болью"

Обозначив сложное высказывание через X, а простые соответственно через Y, Z, U, V, можно записать

X = если Y и Z, то U или V

Или X = (Y and Z) → (U or V)

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

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

Пусть дана формула B и X1, X2, …, Xn - атомы, в ней встречающиеся. Тогда под интерпретацией формулы B будем понимать приписывание истинных значений атомам X1, X2, …, Xn. Формула B истинна в данной интерпретации тогда и только тогда, когда B принимает значение "истина", иначе B ложна в этой интерпретации.

Для формулы состоящей из n атомов существует 2n интерпретаций.

Формула исчисления высказываний, которая истинна во всех интерпретациях, называется тавтологией или общезначимой формулой. Примерами тавтологий являются X or not(X), X→(Y→X).

Формула исчисления высказываний называется противоречием, если она ложна во всех интерпретациях. Например, X and not(X).

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

1. Пусть B есть некоторая формула, а B* - формула, полученная из B подстановкой формулы C вместо атома X везде, где он встречается в B. Тогда, если B - тавтология, то и B* также тавтология.

Это правило называется в ФС правилом подстановки.

2. Если B и B → C - тавтологии, то C - также тавтология.

Этот результат известен как правило дедуктивного вывода - modus ponens.

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

Продолжение в архиве или в первоисточнике.