Формально-логическая модель

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

Иван студент и Татьяна студентка;

Иван студент или Татьяна студентка.

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

Можно ли на основе высказывания А получить высказывание В?

Истинно ли высказывание В при истинности высказывания А?

Элементарные высказывания, т.е. те, которые нельзя разделить на частичные, могут рассматриваться как переменные логического типа, над которыми разрешены следующие логические операции: отрицание (┐); конъюнкция, или логическое умножение (۸); дизъюнкция, или логическое сложение (۷); импликация (→); эквивалентность (↔). Исчисление высказываний позволяет формализовать лишь малую часть множества рассуждений, поскольку этот аппарат не позволяет учитывать внутреннюю структуру высказывания, которая существует в естественных языках.

Пример 2.3.Пусть сформулированы следующие высказывания:

P: Все люди смертны;

Q: Сократ – человек;

R: Сократ – смертен.

Можно составить формулу

(P۸Q) → R.

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

человек (Сократ)

или в общем случае

человек (x)

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

Исчисление предикатов первого порядка – это формальный язык, используемый для представления отношений между объектами и для выявления новых отношений между объектами на основе существующих [7,10]. Алфавит языка исчисления предикатов первого порядка включает переменные, константы, предикаты, логические операции, функции, кванторы ( ). Конструкцией предложений в языке исчисления предикатов первого порядка управляют синтаксические правила.

Терм – это переменная, константа или результат применения функции к терму, например, a, x, f (x). Предложения языка исчисления предикатов первого порядка есть формулы, определенные следующим образом:

1. Если P – n-арный предикат (предикат от n аргументов) и t₁, t₂, …, t_n – термы, тогда P (t₁, t₂, …, t_n) – атомическая формула (атом).

2. Атом – это правильно построенная формула.

3. Если F₁ и F₂ – атомы, то F₁ ۸ F₂, F₁ ۷ F₂, F₁ → F₂, ┐F₁ – тоже атомы.

4. Если F – формула и x – не связанная квантором переменная в F, тогда x (F) и x (F) – также атомы.

Чтобы избежать неоднозначности, необходимо определять формулы, в которых все переменные квантованы, т.е. связаны кванторами, например, x y ЛЮБИТ (x,y).

Такая формула называется замкнутой. Замкнутая формула имеет единственное истинное значение. Формула y ЛЮБИТ (x,y) является незамкнутой или открытой.

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

Пример 2.4.Пусть заданы предикаты:

E (x) – «x» въезжает в страну;

۷ (x) – «x» высокопоставленное лицо;

S (x,y) – «y» обыскивает «x»;

C (y) – «y» - таможенник;

P (x) – «x» способствует провозу наркотиков.

Тогда произвольные предложения на естественном языке могут быть записаны в виде:

1. Таможенники обыскивают всех, кто въезжает в страну, кроме высокопоставленных лиц:

x (E (x) ۸ ┐ ۷ (x) → ( y (S (x,y) ۸ C (y)))).

2. Некоторые люди, въезжавшие в страну и способствовавшие провозу наркотиков, были обысканы исключительно людьми, способствовавшими провозу наркотиков:

x (E (x) ۸ P (x) ۸ ( y (S (x,y) → P (y)))).

3. Никто из высокопоставленных лиц не способствовал провозу наркотиков:

x (P (x) → ┐ ۷ (x)).

4. Некоторые таможенники способствуют провозу наркотиков:

x (P (x) ۸ C (x)).

Задача состоит в том, чтобы, признав фактами предложения 1, 2, 3, доказать, что предложение 4 является истинным.

Для машинного решения вышеприведенной задачи используется методика автоматического формирования суждений, или метод дедукции. При этом последовательно реализуются процедуры: исключение знаков импликации; ограничение области действия знака отрицания; переименование переменных; вынесение кванторов в начало формулы; исключение кванторов и др. При автоматизации вывода доказательств методами исчисления предикатов требуется определить ряд процедур для выбора правил, позволяющих предотвратить «комбинаторный взрыв» и обеспечить проведение немонотонных рассуждений [11]. Решением стало создание декларативных (непроцедурных) языков программирования, в частности Пролога. Программирование на Прологе состоит из этапов:

- объявление некоторых фактов об объектах и отношениях между ними;

- определения некоторых правил об объектах и отношениях между ними;

- формулировки вопросов об объектах и отношениях между ними.

Реально исчисление предикатов первого порядка в промышленных ЭС практически не используется. Формально-логическая модель представления знаний применима в основном в исследовательских системах, т.к. предъявляет очень высокие требования и ограничения к предметной области [8].

Фреймовая модель

Термин «фрейм» (англ. frame – каркас, рамка) был предложен Марвином Минским в 70-е годы XX века для обозначения структуры знаний при восприятии пространственных сцен. Фрейм– это абстрактный образ для представления стереотипа объекта, понятия или ситуации [8]. В психологии и философии известно понятие абстрактного образа. Например, произнесение слова «комната» порождает образ жилого помещения (стены, потолок, пол, дверь, окна). Из этого описания ничего нельзя убрать, но есть слоты – незаполненные значения некоторых атрибутов (количество окон, высота потолков, цвет стен). В теории фреймов такой образ называется фреймом комнаты [12].

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

Структура фрейма представляется как список свойств:

(имя ФРЕЙМА:

(имя 1-го слота: значение 1-го слота),

(имя 2-го слота: значение 2-го слота),

…

(имя N-го слота: значение N-го слота)).

При описании предметной области для классов задач структурно-параметрической идентификации, прогнозирования временных рядов, распознавания образов используются классификационные фреймы (КФ) и фреймы-смысловые связки (ФСС) [9].

В нормальных формах Бэкуса – Науэра КФ определяется следующим образом:

<КФ>::=<идентификатор><имя фрейма>:=<список классификаций>

<список классификаций>::={[<поле>:]}<классификация>

<поле>::=<идентификатор>

<классификация>::={<вариант>}

<вариант>::=<идентификатор>{<условие><альтернатива>}|<иденти-фикатор> <альтернатива>

<альтернатива>::=<текст>{<указание>}

<указание>::=<ссылка на фрейм>|<описание фрейма>|<принуди-тельное разрешение фрейма>

Пример 2.5.Применительно к предметной области регрессионного анализа КФ имеет вид:

К0 <цель исследования>:=

V1 <регрессионный анализ данных>

К1 <этапы решения задачи>:=

V1 <предварительный анализ исходных данных>

V2 <структурно-параметрическая идентификация регрессионных моделей>

V3 <оценка качества регрессионных моделей>

К2 <предварительный анализ исходных данных>:=

V1 <анализ корректности исходных данных>

V2 <проверка условий применимости регрессионного анализа>

V3 <функциональное преобразование матрицы регрессоров>

К7 <оценка качества регрессионных моделей>:=

V1 <для К6 = 1 ۷ К6 = 4>

V2 <для мультипликативных моделей>

V3 <для нелинейных нереализуемых моделей>

ФСС определяется конструкцией

<ФСС>::=<идентификатор><входной аргумент> <глагол> <выходной аргумент>

Пример 2.6.Применительно к предметной области регрессионного анализа ФСС имеет вид [9]:

C0 <начало работы> требует

A <обеспечить ввод исходных данных>

B <назначить режим работы>

C1 <предварительный анализ исходных данных>

A <восстановление отсутствующих значений>

B <исключение аномальных значений отклика>

C <проверку значений отклика на нормальность распределения>

D <проверку значений отклика на статистическую независимость>

E <проверку матрицы регрессоров на мультиколлинеарность>

. . .

C3 <оценка качества регрессионных моделей> требует

A (если К7 = 1, то)

А1 <проверку нормальности распределения значений остатков>

А2 <проверку статистической независимости значений остатков>

. . .

С (если К7=3, то)

С1 <вычисление F-статистик>

С2 <визуальный анализ значений остатков>

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

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

Рис. 2.1. Сеть фреймов

Существует несколько способов получения слотом значений во фрейме-экземпляре:

- по умолчанию от фрейма-образца;

- через наследование свойств от фрейма, указанного в слоте АКО («это»);

- по формуле, указанной в слоте;

- через присоединенную процедуру;

- явно из диалога с пользователем;

- из БД.

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

U – уникальный, показывает, что значение не наследуется;

S – показывает, что значение слота наследуется;

R – показывает, что значения слота должны находиться в пределах значений, указанных в одноименных слотах родительского фрейма;

O – выполняет одновременно функции U и S (при отсутствии значения наследуется, в противном случае не наследуется).

Тип значения слота показывают указатели типа данных: frame (указатель на фрейм), real, integer, boolean, text, list, table.

Демон – это процедура, автоматически запускаемая при выполнении некоторого условия. Демоны запускаются при обращении к соответствующему слоту. Демон IF-NEEDED запускается, если в момент обращения к слоту его значение не было установлено. Демон IF-ADDED запускается при попытке изменения значения слота. Демон IF-REMOVED запускается при удалении значения слота.

Основным преимуществом фреймов как модели представления знаний является то, что она отражает концептуальную основу организации памяти человека, а также ее гибкость и наглядность [8]. Фреймовый подход реализуется на основе специальных языков представления знаний FRL, KRL, фреймовая «оболочка» Карра.

Семантические сети

Семантика – это наука, устанавливающая отношения между символами и объектами, которые они обозначают, т.е. наука, определяющая смысл знаков.

Семантическая сеть – это ориентированный граф, вершины которого – понятия, а дуги – отношения между ними.

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

Характерной особенностью семантических сетей является обязательное наличие трех типов отношений:

- класс – элемент класса (цветок – роза);

- свойство – значение (цвет – красный);

- пример элемента класса (роза – чайная).

Наиболее часто в семантических сетях используются отношения:

- атрибутивные связи – «иметь свойство» (память – объем);

- часть – целое – «имеет частью» (велосипед – руль);

- функциональные связи – «производит», «влияет»;

- количественные – «больше», «меньше», «равно»;

- пространственные – «далеко», «близко», «за», «под», «над»;

- временные – «раньше», «позже», «в течение»;

- логические связи – «и», «или», «не».

Фрагмент семантической сети приведен на рис. 2.2 [8].

Рис. 2.2. Семантическая сеть

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

Для реализации семантических сетей существуют специальные сетевые языки, например NET, SIMER+MIR.

Глава 3. Структура и технология проектирования
экспертных систем

3.1. Структура статической и динамической ЭС

ЭС – сложные программные комплексы, аккумулирующие знания специалистов в конкретных предметных областяхи тиражирующие этот эмпирический опыт для консультаций менее квалифицированных пользователей [2]. Первые ЭС, получившие практическое использование, были статическими, то есть не учитывали изменение исходных данных во время решения задачи (рис 3.1).

Рис. 3.1. Обобщенная структура статической ЭС

Интерфейс пользователя – комплекс программ, реализующих диалог пользователя и ЭС как на стадии ввода информации, так и при получении результатов. Рабочая память предназначена для хранения исходных и промежуточных данных решаемой в текущий момент задачи. Решатель является программой, моделирующей ход рассуждений эксперта на основании знаний, имеющихся в БЗ. Синонимами понятия «решатель» являются дедуктивная машина, машина вывода, блок логического вывода. Используя исходные данные рабочей памяти знания из БЗ, решатель формирует такую последовательность правил, которая, будучи применима к исходным данным, приведет к решению задачи. БЗ – ядро ЭС, совокупность знаний предметной области. Подсистема объяснений – это программа, позволяющая пользователю получить ответы на вопросы: «Как была получена рекомендация? Почему система приняла такое решение?». Ответ на вопрос «Как?..» – это трассировка всего процесса получения решения с указанием использованных фрагментов БЗ. Ответ на вопрос «Почему?..» – ссылка на умозаключение, непосредственно предшествовавшее полученному решению, то есть отход на один шаг назад. Развитие подсистемы объяснений поддерживают и другие типы вопросов. Интеллектуальный редактор БЗ – программа, представляющая инженеру по знаниям (когнитологу) возможность создавать БЗ в диалоговом режиме. Программа включает в себя систему вложенных меню, шаблонов языка представления знаний, подсказок и других сервисных средств, облегчающих работу с БЗ. Промышленные прикладные ЭС включают дополнительно БД, интерфейсы обмена данными с различными пакетами прикладных программ (ППП).

ЭС может функционировать в двух режимах: режиме приобретения знаний и режиме использования. В режиме приобретения знаний эксперт, используя интеллектуальный редактор, наполняет БЗ знаниями. В режиме использования общение с ЭС осуществляет конечный пользователь, который в общем случае не является специалистом в данной проблемной области.

Существуют проблемные области, требующие учитывать динамику исходных данных в процессе решения задачи (системы противовоздушной обороны, управление атомными электростанциями). Соответствующие ЭС называются динамическими (рис. 3.2) [7].

Рис. 3.2. Обобщенная структура динамической ЭС

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

3.2. Характеристики, стадии существования
и этапы проектирования статических ЭС

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

Характеристики, определяющие ЭС [2]:

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

- связанность правил. Малосвязанные задачи удается разбить на несколько подзадач;

- пространство поиска, которое определяется размером, глубиной и широтой. Малыми считаются пространства поиска до 10! состояний. Глубина характеризуется средним числом последовательно применяемых правил, преобразующих исходные данные в конечный результат. Ширина характеризуется средним числом правил, пригодных к выполнению в текущем состоянии.

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

Выделяют три поколения ЭС:

- статические поверхностные, в которых знания представляются в виде правил и процесс поиска не обрывается до решения;

- статические глубинные, которые обладают способностью при возникновении неизвестной ситуации определить действия, которые следует выполнить;

- динамические (глубинные и гибридные).

Простые ЭС являются поверхностными, традиционными, БЗ включает от 200 до 1000 правил. Сложные ЭС – это глубинные, гибридные системы с БЗ от 1500 до 10 000 правил.

Стадии существования ЭС:

- демонстрационный прототип – решает часть требуемых задач, БЗ содержит до 100 правил;

- исследовательский прототип – решает все задачи, в работе не устойчив, БЗ содержит до 500 правил;

- действующий прототип – решает все задачи , но для решения сложных задач требуется большой объем вычислительных ресурсов. БЗ содержит до 1000 правил;

- промышленный образец обеспечивает высокое качество решаемых задач;

- коммерческая система – предназначена для широкого распространения.

Статические поверхностные ЭС предусматривают следующие этапы проектирования:

- идентификация – определяются задачи, выявляются цели, ресурсы, наличие экспертов, категории пользователей;

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

- формализация – определяются способы представления, специфицируются выделенные ранее понятия, фиксируются способы интерпретации знаний, моделируется работа ЭС, оцениваются полученные результаты;

- реализация – создание программной обстановки, в которой будет функционировать ЭС и наполнение БЗ;

- тестирование – эксперт и когнитолог в интерактивном режиме, используя объяснения, проверяют компетентность ЭС.

Процесс разработки промышленной ЭС можно разделить на шесть основных этапов.

1. Выбор проблемы.Данный этап предшествует решению начать разработку ЭС и предусматривает:

-определение проблемной области;

- нахождение экспертов и разработчиков;

- определение предварительного подхода к решению подставленных задач;

- анализ расходов и прибыли от разработки;

- подготовку плана разработки ЭС.

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

2. Разработка прототипной системы.Прототипная система является усеченной версией ЭС, спроектированной для проверки жизнеспособности выбранного подхода к представлению фактов, связей и стратегий рассуждений эксперта. Разработка прототипной ЭС включает стадии:

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

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

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

- Формализация. Строится формализованное представление концепции предметной области на основе выбранного языка представления знаний (ЯПЗ) или специального формализма с использованием логических методов, продукционных моделей, семантических сетей, фреймов. Задача стадии – разработка БЗ.

- Реализация. Создается прототип ИИС, включающий БЗ и остальные блоки (п. 2.1), при помощи одного из следующих способов: программирование на языках С⁺⁺, Паскаль и др.; программирование на специализированных языках ЛИСП, ПРОЛОГ, SMALL TALK; использование инструментальных средств типа СПЭИС, ПИЭС, ART, J2; использование «пустых» ЭС GURU, ЭКСПЕРТ, ФИАКР. Задача стадии – разработка программного комплекса, демонстрирующего жизнеспособность подхода в целом.

- Тестирование. Прототип проверяется на удобство и адекватность интерфейсов ввода/вывода, эффективность стратегии управления, качество проверочных примеров, корректность БЗ. Задача стадии – выявление ошибок в подходе и реализации прототипа, выработка рекомендаций по доводке системы до промышленного образца.

3. Доработка прототипа до промышленной ИИС. Основное на данном этапе заключается в добавлении большого числа дополнительных эвристик, которые увеличивают «глубину» ЭС. После установления основной структуры системы когнитолог приступает к разработке и адаптации интерфейсов, с помощью которых ЭС будет общаться с пользователем и экспертом.

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

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

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