Представления знаний в информационных системах

Логический вывод осуществляется с помощью силлогизма (если из A следует B, а из B следует C, то из A следует C).

Логика предикатов является основой языка программирования Пролог, разработанного Алэном Колмероэ из Марсельского универси-

тета (Франция) в 1973 г. [9, 10].

Представляет интерес более детально остановиться на основ- ных понятиях и определениях, применяемых в логике предикатов первого порядка [3].

Определение формальной системы

Формальной системой называют множество абстрактных объек- тов, в котором определены правила манипулирования множеством сим- волов, обработанных синтаксическим образом, т.е. без учета смысла (семантики). Формальную систему составляют [3]:

1)конечный алфавит (конечное множество символов);

2)процедура образования формул (или слов) формальной систе-

мы;

3)множество формул, называемых аксиомами;

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

Эти правила могут быть представлены в виде U1 и U2 и... и U m →

W1 и W2 и... и Wm . Здесь Ui и Wj – формулы формальной системы, а

стрелка читается как "влечет" или "следует".

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

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

Формальное доказательство (или просто доказательство) опреде- ляется как конечное множество формул M1, M 2 ,...,M n , таких, что каждая

формула M i либо является аксиомой, либо выводится с помощью правил

вывода из предшествующих формул.

Формула t называется теоремой, если существует доказательство, в ко- тором она является последней, т.е. M n = t . В частности, всякая аксиома яв-

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

31

(в этом случае их называют продукциями, правилами продукции, или продук-

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

Так, в математике правило вывода « X < Y и Y < Z влечет X < Z » применяется к формуле как к целому. Это продукция с двумя посылками. Слово "влечет" часто заменяется стрелкой →. В отличие от предыдущего правила, x − x = 0 истинно при любом подвыражении х. Оно является прави- лом переписывания, и в этом случае для обозначения слова "влечет" исполь- зуется специальная стрелка a .

Пример

1)Алфавит: T, S, A.

2)Формула: любая последовательность символов алфавита.

3)Аксиома: TA.

4)Правила вывода:

d) SS a (переписывание).

Правило a является продукцией и применяется только тогда, ко- гда последняя буква теоремы есть A. Таким образом, из теоремы “TASTA” можно вывести “TASTAS”. Следует отметить, что символ t не принадлежит формальной системе и играет роль некоторого слова. Так, правило b позволяет из теоремы “TSA” вывести теорему “TSASA” . Пра- вило c позволяет переход, например, от “TSAAAST” к “TSSST”. Правило d заменяет в “TASSSSV” каждые два S пробелом и в результате получаем

“TAV”.

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

Например, в абстрактной модели: “Любой X есть Y.

Если Z есть X,

то Z есть Y.”

используются переменные X, Y, Z. Слова-связи: “если”, “то”, “или” и др. называются операторами.

Синтаксис языка предикатов первого порядка

Предикатом, или логической функцией, называется функция от любого числа аргументов, принимающая истинностные значения: И (ис-

32

тина – 1) и Л (ложь – 0). Аргументы принимают значения из произволь- ного, конечного или бесконечного множества D, называемого предмет- ной областью. Предикат от п аргументов называют п-местным преди- катом [3].

Предикат F(x), определенный на предметной области D, задает определенное свойство элементам множества D и интерпретируется как высказывание “х обладает свойством F”, причем F принимает значение И, если это высказывание истинно, и значение Л, если оно ложно. Пре- дикат F(x1, x2 ,..., xN ) задает отношение между элементами x1, x2 ,..., xN и

интерпретируется как высказывание “ x1, x2 ,..., xN находятся между собой

в отношении F”. Пусть, например, D – множество натуральных чисел. Тогда предикат F(x) может обозначать, что “х – четное число" или “х – нечетное число”, а предикат G(x,y) – “х больше у” или “х делится на y” и т.д.

Алфавит языка предикатов первого порядка включает множество следующих символов:

•разделители: запятая, открывающая и закрывающая скобки;

•константы, обозначаемые строчными буквами или соединением таких букв, например “друг”;

•переменные, обозначаемые прописными буквами, например: X,

АДРЕС;

•предикаты, обозначаемые прописными буквами, например: Р, Q, БОЛЬШЕ;

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

•логические операции:

1) “ ” (отрицание или дополнение). Высказывание “ A” читает- ся “не A”. Оно истинно (И), если высказывание А – ложно (Л);

2)“ ” (конъюнкция). Высказывание "А В" читается “А и B”. Оно истинно в том случае, когда истинно как A, так и B;

3)“ ” (дизъюнкция). Высказывание "А В" читается “А или B”. Оно истинно, если истинно хотя бы одно из высказываний;

4)“ →” (импликация). Высказывание “A → B” читается "если A, то B". Оно ложно в том и только в том случае, если A истинно, а B лож- но;

5)“ ↔” (эквивалентность). Высказывание “А↔В” читается “A то- гда и только тогда, когда B”. Оно истинно тогда и только тогда, когда A

иB имеют одно и то же истинностное значение;

33

Пропозициональной формой, или формулой алгебры логики, назы-

вают всякое высказывание, составленное из некоторых исходных вы- сказываний посредством логических операций. Другими словами, если F и G – пропозициональные формы, то F, (F G), (F G), (F→G) и (F ↔G) – пропозициональные формы.

Определение формулы как основного объекта в логике предика- тов включает понятие "терм".

Терм – выражение, включающее константы, переменные или n- местные функции f (t1,...,tN ), где t1,...,tN – термы. Например, f (X ,Y ),

вес(b) – термы.

Атом, или элементарная (атомная) формула, – это выражение,

включающее константы, переменные, функции и предикаты. Таким об- разом, если Р – N-местный предикат, а t1,...,tN – термы, то P(t1,...,tN ) –

атом. Например, выражения P(X, зеленый), ABC являются атомами.

Формула, или правильно построенная формула, определяется сле-

дующим образом:

всякий атом есть ППФ;

если G и Н – ППФ, а Х – переменная, тогда

( H), (G H), (G H), ( X)G, ( X)H – ППФ.

Примерами ППФ являются:

P(a, X , f (Y, a,b)),G(X ,Y ) → F(a,b),(P(a) → (G(b) ¬F(a))).

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

На практике ППФ используется для представления знаний. На- пример, ППФ ( X )(M (X ) → F(X )) может выражать "все матери есть

женщины", условившись, что M(Х) означает: “X есть мать” и что F(X) означает: “Х – есть женщина”.

Правилом вывода называют процедуру, которая из одной или не- скольких ППФ производит другие ППФ. Например, правило вывода: G и (G → H ) производит одну ППФ Н; из ППФ ( X )G(X ) и любой кон-

станты “а” получают ППФ G(a) , при этом значения X в G заменяются

34

на “а”. Исходные ППФ называют аксиомами, а ППФ, полученные из правил вывода, называют теоремами.

Семантика языка предикатов первого порядка

Интерпретация формул. Формула имеет определенный смысл, т.е. обозначает некоторое высказывание, если существует какая-либо интерпре- тация. Интерпретировать формулу – это значит связать с ней определенное непустое множество D, т.е. конкретизировать предметную область, называе-

мую также областью интерпретации [3] и указать:

∙для каждой константы в формуле – конкретный элемент из D;

∙для каждой n-местной функциональной буквы в формуле – конкрет- ную n-местную функцию на D;

∙для каждой n-местной предикатной буквы в формуле – конкретное отношение между п элементами из D.

Пример

Рассмотрим атом: G( f (a,b), g(a,b)) и следующую интерпретацию:

D – множество действительных чисел; a = 2,b = 3;

f – функция сложения f (a,b) = a + b; g – функция умножения g(a,b) = a*b;

G – отношение “не меньше”.

При такой интерпретации приведенная ниже формула обозначает вы- сказывание “сумма 2+3 не меньше произведения 2*3”. Это утверждение не- верно и поэтому G( f (a,b), g(a,b)) = Л . Если видоизменить интерпрета-

цию, приняв b=1 или b=2, то G( f (a,b), g(a,b)) = И .

Свойства правильно построенных формул. При заданной ин-

терпретации значения истинности ППФ можно вычислить по правилам, объединенным в таблице истинности.

Если F и G – любые две ППФ, то значения истинности составного выражения, построенного из этих ППФ, даются таблицей истинно-

сти [3] (табл. 2.1).

Т а б л и ц а 2.1

Таблица истинности

35

Принцип резолюций. Аппарат логики предикатов используется для представления задачи в виде теоремы: формула Н логически следует из формулы G, т.е. G → Н. Доказательство этой теоремы состоит в том, чтобы показать, что каждая интерпретация, удовлетворяющая G, удовле- творяет и Н. С целью упрощения доказательства теоремы все формулы представляются в виде дизъюнкции литералов.

Литералом называется атом или его отрицание. Формулу, пред- ставляющую собой дизъюнкцию литералов, называют предложением (или дизъюнктом). Любую ППФ исчисления предикатов первого по- рядка можно преобразовать во множество предложений [3, 9].

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

формализованных знаний эксперта в системе строгой логики не всегда удается осуществить. Это объясняется нечеткой структурой человече- ской логики [2, 3].

2.3. Представление знаний продукционными правилами

Продукционная модель, или модель, основанная на правилах, по- зволяет представить знания в виде предложений типа “Если (условие), то (действие)”. Под “условием” понимается некоторое предложение- образец, по которому осуществляется поиск в базе знаний, а под “дей- ствием” – действия, выполняемые при успешном исходе поиска. Чаще всего вывод на такой базе знаний бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения – к данным). Дан- ные – это исходные факты, хранящиеся в базе фактов, на основании ко- торых запускается машина вывода или интерпретатор правил, переби- рающий правила из продукционной базы знаний [1].

Простота и наглядность этого способа обусловили его примене- ние во многих системах. Системы обработки знаний, использующие представление знаний продукционными правилами, получили название продукционных систем [11]. В состав продукционной системы входят база правил, база данных и интерпретатор правил (рис. 2.1).

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

36

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

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

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

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

Продукционные системы принципиально весьма просты, и успехи самых первых ЭС DENDRAL и MYCIN, использующих продукционные правила, внесли огромный вклад в становление инженерии знаний.

ЭС DENDRAL (1965) – родоначальник инженерии знаний. Непо-

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

38

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

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

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

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

Внастоящее время имеется большое число программных средств, реализующих продукционный подход (язык OPS-5; “оболочки” ЭС – EXSYS Professional, Kappa, ЭКСПЕРТ, ЭКО, инструментальные систе- мы ПИЭС (Хорошевский В.Ф., 1993) и СПЭИС (Ковригин О.В., Пер- фильев К.Г., 1988)), а также промышленных ЭС на его основе (напри- мер ЭС, созданных средствами G2 (Попов Э.В., 1996)) [1].

2.4. Модель представления знаний в виде фреймов

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

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

39

Представление знаний, основанное на фреймах, является альтер- нативным по отношению к системам продукции: оно дает возможность хранить родовидовую иерархию понятий в БЗ в явной форме.

Термин “фрейм” (от английского frame, что означает “каркас” или “рамка”) был предложен Марвином Минским в 1979 г. для обозначе- ния структуры данных при восприятии пространственных сцен. Эта мо- дель имеет психологическое обоснование. Фрейм – это абстрактный образ для представления некоего стереотипа восприятия [1].

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

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

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

Фреймы обладают способностью наследовать значения характе- ристик своих родителей, находящихся на более высоком уровне иерар- хии. Так, фрейм АФРИКАНСКИЙ СЛОН наследует от фрейма СЛОН значение СЕРЫЙ характеристики ЦВЕТ.

Значения характеристик фреймов могут передаваться по умолча- нию фреймам, находящимся ниже их в иерархии, но если последние со- держат собственные значения данных характеристик, то в качестве ис- тинных применяются именно они [4]. Это обстоятельство позволяет легко учитывать во фреймовых системах различного рода исключения. В частности, во фрейме АЗИАТСКИЙ СЛОН значением слота ЦВЕТ будет КОРИЧНЕВЫЙ, а не СЕРЫЙ, которое могло бы в нем находить-

40