Формы представления и типы моделей знаний

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

Императивные формы представления знаний – это традиционные (процедурные) способы описания процессов решения задач в виде последовательностей операций над данными, совершаемых согласно заданным алгоритмам или формулам (как, например, последовательность операций вычисления выражения y:═ x∙ (z+v). В процедурах знания (связи, зависимости, законы) представлены (учтены) неявно: в организации вычислительного процесса, в структуре программы решения задачи, в характере и последовательностях операций. По этой причине императивная форма представления знаний наиболее эффективна с вычислительной точки зрения (по затратам времени и памяти на решение задачи), поскольку в процедурах поиска решения глубоко учитывается специфика конкретной проблемной области и решаемой задачи, что является важным фактором при создании систем, работающих в реальных условиях (в системах реального времени). Главный недостаток этой формы представления знаний – сложность внесения изменений, что делает ее непригодной для использования в слабо изученных и изменяющихся ПО.

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

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

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

– логические модели;

– продукционные модели;

– сетевые модели;

– фреймовые модели.

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

2.1. Логические модели [3, 4, 5, 13, 14, 16, 17]

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

Языки, предназначенные для описания предметных областей, называются языками представления знаний. Универсальным языком представления знаний является естественный язык, но применение естественного языка для машинного представления знаний наталкивается на ряд препятствий, главным из которых является отсутствие формальной семантики естественного языка. Семантика – это смысловое значение единиц языка. В естественном языке смысл слов и выражений часто зависит от текста, в котором они встречаются. Кроме того, естественные языки – это «живые», постоянно меняющиеся и развивающиеся языки.

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

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

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

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

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

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

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

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

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

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

Исчисление высказываний – наиболее простой пример формальной аксиоматической теории в логике. Существует несколько исчислений высказываний (Д. Гильберта, С. Клини, Ж. Фреге, П. С. Новикова). Мы рассмотрим исчисление высказываний Я. Лукасевича (исчисление ), использующее функционально полную систему связок, состоящую из отрицания () и импликации (). Исчисление описывает множество тождественно истинных формул (тавтологий), что соответствует реальному положению вещей в математике, где теоремы как высказывания являются тождественно истинными формулами.

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

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

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

Правилом вывода в исчислении является modus ponens (правило заключения), согласно которому из данных формул вида и выводится формула .

Исчисление предикатов первого порядка и теории первого порядка. Предикат – это логическая функция от нелогических аргументов (например, функция sum (x, y, z) принимает истинные значения, когда x + y = z, и ложные – в противном случае). Исчисление предикатов первого порядка и теории первого порядка отличаются от теорий более высоких порядков тем, что в них допускается применение кванторов только лишь к переменным. Однако установлено, что большинство теорий более высоких порядков сводимо к теориям первого порядка. Каждая теория первого порядка располагает системой аксиом, включающей логические (общие) и собственные (частные) аксиомы. Исчисление предикатов первого порядка – это теория первого порядка, использующая только логические аксиомы. Дополнение исчисления предикатов аксиомами некоторой предметной области превращает его в частную теорию первого порядка этой предметной области.

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

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

– символов предметных констант;

– функциональных символов (функторов);

– предикатных символов (предикатов);

– символов предметных переменных;

– логических символов;

– вспомогательных символов.

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

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

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

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

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

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

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

Например, формула в любой алгебраической системе либо тождественно истинна, либо тождественно ложна, так как каждая из входящих в нее переменных связана квантором. Пусть интерпретируется как число 1, – как умножение (∙), – как сложение (+), – как неравенство (<). Тогда в привычной записи формула принимает вид . Эта формула истинна, если областью интерпретации (множеством констант и возможных значений переменных) является множество натуральных чисел (т. е. ={1, 2, 3,…}), и ложна, если областью интерпретации является множество всех целых (положительных и отрицательных) чисел (т. е. ={…, -3, -2, 0, 1, 2, 3, …}).

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

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

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

,

где суть формула и – терм, свободный для в ;

,
если формула не содержит свободных вхождений .

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

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

Правилами вывода в теориях первого порядка являются следующие два основных правила: modus ponens (правило заключения), по которому из формул и выводится формула ; правило обобщения (связывания квантором общности), по которому из формулы выводится формула .

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

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

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

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

а) ;

б) .

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

2.2. Продукционные модели [4, 9, 14, 18]

Этот способ представления знаний основан на понятии формальной продукционной системы, которое в 1943 году ввел в обращение американский логик Е. Пост. Он показал, что любая формальная система (в том смысле, как она определяется в разделе о логических моделях) может быть представлена как система продукций, т. е. как совокупность правил { R_i: Φ _i → Ψ _i }, где выражение R_i: Φ _i → Ψ _i означает, что в данной формальной системе по правилу R_i из посылки Φ _i непосредственно выводится заключение Ψ _i.

В 1972–1973 годах Ньюэлл и Саймон (авторы идеи экспертных систем) показали, что человек в ходе рассуждений и деятельности использует правила, подобные продукциям, т. е. делает заключения по схеме «условие→следствие» и действует по схеме «ситуация→действие». Тогда же Ньюэлл предложил использовать продукционные системы для моделирования процессов принятия решений в системах искусственного интеллекта. Сегодня системы продукций (наряду с сетевыми моделями) являются наиболее популярными средствами представления знаний в системах искусственного интеллекта.

В общем случае продукция – это утверждение вида если А, то B, обозначаемое логическим выражением вида A → B. Продукция A → B может истолковываться в логическом смысле – как следование истинности B из истинности А. Возможны и другие интерпретации продукции: например, А может быть описанием некоторого условия, наличие которого необходимо для выполнения действия B.

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

а) выявление совокупности активных правил, т. е. тех продукций, условия для применения которых выполнены (правил, которые могут действовать);

б) разрешение конфликтов между правилами (с учетом приоритетов, эффективности, эвристик) и выбор правила для применения (правила, которое должно действовать);

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

В различных оболочках (пакетах программ, предназначенных для проектирования экспертных систем) используются различные способы управления системами продукций, определяющие также способы оформления самих продукций и их систем. В самом общем виде продукционное правило представляет собой набор (I, Q, P, A → B, N) следующих компонент:

I – имя (или порядковый номер) правила, имя может выражать суть правила, смысл выполняемого им действия;

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

P – предусловие применения правила – общие условия, при которых разрешено или имеет смысл обращаться к данному правилу;

A → B – ядро правила (если А, то В), где А и В соответственно либо посылка и заключение, либо ситуация и действие;

N – постусловие применения правила – другие последствия и изменения, обусловленные применением данного правила, не учтенные в правой части В ядра продукции.

Наиболее ориентированной на применение продукционных моделей представления знаний является концепция систем искусственного интеллекта, основанных на использовании глобальной базы данных. В состав такой системы входит база правил (множество продукций), глобальная база данных и система управления. База правил представляет собой совокупность знаний в форме правил вида A → B (если А, то В). Глобальная база данных содержит знания, представляющие собой данные или уже установленые факты. Система управления формирует заключения, используя базу правил и глобальную базу данных.

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

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

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

Обычно существует несколько способов такого представления. Искусство выбора хорошего представления очень существенно для применения методов искусственного интеллекта к практическим задачам.

Для наглядности и простоты обсудим решение задачи представления на примере головоломки, известной как игра в 8. На рис. 2.1 приведены две конфигурации фишек. Рассмотрим задачу преобразования начальной конфигурации в указанную на рисунке целевую.

Решением задачи игры в 8 служит правильная последовательность ходов (например, передвинуть фишку 6 вниз, передвинуть фишку 8 вниз, передвинуть фишку 2 вправо, передвинуть фишку 1 вверх, передвинуть фишку 8 влево).

1

Целевая конфигурация

Исходная конфигурация

Рис. 2.1. Задача в игре в 8

Определим основные компоненты задачи: состояния, ходы и цель.

В игре в 8 каждая конфигурация фишек является состоянием задачи. Множество всех возможных конфигураций образует пространство состояний задачи. Многие задачи имеют пространство состояний очень большого размера. У игры в 8 оно относительно невелико: 9! (362880) различных конфигураций.

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

Определив на смысловом уровне состояния задачи с учётом того, что необходимо такое их машинное представление (описание), которое затем можно будет использовать как глобальную базу данных системы продукций. Для игры в 8 простым описанием является массив или матрица чисел размером 3×3.

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

Каждый ход преобразует одно состояние задачи в другое. Удобно интерпретировать игру в 8 как игру, в которой имеется 4 хода: передвижение пустой клетки влево, вверх, вправо и вниз. Эти ходы моделируются правилами (продукциями), которые соответствующим образом применяются к описаниям состояний. Каждое правило имеет предусловие, которому должно удовлетворять описание состояния, чтобы это правило можно было применить к данному описанию состояния. Так, предварительным условием для передвижения пустой клетки вверх является требование, чтобы эта клетка не находилась в верхнем ряду.

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

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

Одним из способов организации взаимодействия подсистем продукций гибридной системы является механизм, получивший название «доска объявлений», впервые применный в системе распознавания человеческой речи HEARSAY-II, разработанной в американском университете Карнеги-Меллона (рис. 2.2).

В этой системе для каждой из подпроблем, образующих в совокупности единую проблему, создается отдельная система знаний. Общение между разнородными системами знаний осуществляется через рабочую память («доску объявлений») так, что все знания используются согласованно относительно автономно работающими продукционными подсистемами, именуемыми в HEARSAY-II «источниками знаний». Состав подсистем продукций в HEARSAY-II соответствует этапам процесса распознавания речи:

а) анализ сигнала с голосовых детекторов;

б) анализ фонем (электрических сигналов, соответствущих звукам);

в) анализ (выделение и распознавание) слогов;

г) анализ (выделение и распознавание) слов;

д) анализ (выделение и распознавание) последовательностей слов;

е) анализ (выделение и распознавание) предложений.

Рис. 2.2. Структура системы HEARSAY-II

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

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

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

2.3. Сетевые модели [4, 14, 18]

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

а) классификационные (отношения типа часть-целое, род, вид, индивид);

б) функциональные (преобразование информационных единиц);

в) каузальные (причинно-следственные отношения);

г) смешаннные (использующие разноообразные типы отношений).

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

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

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

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

Исследования по семантическим сетям начались с работ М. Р. Куиллиана, который в качестве структурной модели долговременной человеческой памяти предложил модель, получившую название TLC-модели (Teachable Language Comprehender – доступный механизм понимания языка). В этой модели для описания долговременной памяти была использована сетевая структура как способ представления семантических (смысловых) отношений между словами (концептами).

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

Базовым элементом семантической сети служит пара понятий и связывающее их отношение, что обычно представляется в виде пары соответствующих понятиям вершин графа, соединенных соответствующей отношению дугой. В качестве простого примера представим предложения «Куин Мэри является океанским лайнером» и «Каждый океанский лайнер является кораблем» в виде семантической сети, приведенной на рис. 2.3.

Рис. 2.3. Пример простой семантической сети

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

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

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

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

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

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

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

Такого рода классификации представляются в семантических сетях с помощью отношения isa (от англ. is a – есть некоторый). Одной из важных черт isa-иерархии является то, что свойства вышележащих типов автоматически переносятся на нижележащие. Например, если свойство разумный присуще человеку, то оно присуще также мужчине, женщине, ребенку (как подклассам класса человек). Это позволяет избежать значительной части дублирования информации в сети. Так, если некоторый факт имеет место для каждого подмножества некоторого множества, то его можно хранить в структуре знаний только для этого множества.

Не менее важным является также отношение целое-часть. Оно носит название part of (часть чего-либо). Это отношение позволяет разбивать информацию по уровням детализации. Part of-структура может представлять собой дерево, в котором каждая родительская вершина является part of-структурой для ее потомков.

Утверждение все собаки – животные можно представить сетью вида рис. 2.5, а, используя вершины собака, животное и дугу, показывающую отношение между ними. В сети рис. 2.5, б из представленных в ней фактов (Шарик – собака и собака – животное) можно вывести новый факт (Шарик – животное), используя наследование по иерархии, присущее отношению isa.

В сети можно представить также знания, касающиеся атрибутов объекта. Например, факт все собаки имеют хвост показан в сети на рис. 2.5, в. Если сеть на рис. 2.5, в дополнить фактом Шарик имеет конуру, то сеть приобретет вид, представленный на рис. 2.5, г, где конура i – это конкретная конура, которой владеет Шарик, она является экземпляром понятия конура. При необходимости сеть можно дополнить информацией «Шарик владеет конурой с весны по осень», тогда вершинами надо представить не только объекты, но также ситуации, действия и события. На рис. 2.6 показана такая семантическая сеть.

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

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

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

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

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

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

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

а) скелетный, пустой фрейм (шаблон), превращаемый после его заполнения в общее или конкретное понятие;

б) фрейм общего понятия (прототип) – шаблон, заполненный не конкретными значениями, константами, а переменными;

в) фрейм конкретного понятия (экземпляр) – прототип, заполненный конкретными значениями, константами.

Особенности фреймовых моделей видны на примере скелетного фрейма для понятия РУКОВОДИТЕЛЬ (рис. 2.7).

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

Рис. 2.7. Скелетный фрейм для понятия РУКОВОДИТЕЛЬ

Каждый слот фрейма предназначен для заполнения определенной структурой данных (в скелетном фрейме все они пусты, кроме первого, который имеет значение СЛУЖАЩИЙ, являющееся в данном случае именем фрейма, описывающего понятие служащий).

На рис. 2.8 представлен тот же фрейм, что и на рис. 2.7, но только с заполненными слотами. При этом часть из них заполнена не простыми именами значений, а некими объектами.

Рис. 2.8. Фрейм для общего понятия РУКОВОДИТЕЛЬ

В данном примере фигурируют три типа таких заполнителей слотов: имя другого фрейма (например, ЗАРПЛАТА); агрегат (например, <фамилия, имя, отчество>); интервал (например, <производство, администрация>). Имя другого фрейма служит в качестве ссылки на фрейм, в котором дается описание соответствующего понятия. Обозначение агрегат указывает на то, какими конкретными объектами должен быть заполнен слот. Обозначение интервал указывает, что конкретное значение слота должно быть выбрано из представленного списка значений. Если значение слота не задается самим пользователем, то оно заполняется значением по умолчанию. Обозначения агрегат, интервал, по умолчанию называют фасетами (fasets) слота.

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

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

ИМЯ ФРЕЙМА
Имя слота	Указатель наследования	Указатель атрибутов	Значение слота	Демон
Имя слота 1
Имя слота 2
……………	………………	……………	………….	……….
Имя слота n

Рис. 2.9. Структура данных (внутренняя структура) фрейма

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

Имя слота – это идентификатор слота, уникальный в пределах фрейма. Обычно имя слота смысловой нагрузки не имеет, кроме некоторых случаев: IS-A (родительский фрейм); DDESENDANT (указатель прямого дочернего фрейма); FINEDBY (пользователь, определивший фрейм); DEFINEDON (дата определения); MODIFINEDON (дата модификации); COMMENT (комментарий) и т. п. А также имена, используемые для представления структурированных объектов: HASPART (имеет часть); RELATION (отношение) и др. Все это системные слоты, используемые для редактирования базы знаний и управления выводом.

Указатель наследования. Эти указатели создаются только во фреймовых системах иерархического типа, основанных на отношениях абстрактное-конкретное, и показывают, какую информацию об атрибутах слотов верхнего уровня наследуют слоты с такими же именами во фреймах нижнего уровня. Типичные указатели: U (unique – уникальный, показывает, что каждый фрейм может иметь слоты с различными значениями); S (same – такой же, показывает, что все слоты должны иметь одинаковые значения); R (range – в пределах границ, показывает, что значения слотов фреймов нижнего уровня должны быть в пределах значений слотов фрейма верхнего уровня); O (overridge – игнорировать, при отсутствии указаний ведет себя как указатель типа S, а при наличии значения – как указатель типа U) и т. п.

Указатель атрибутов слота – это указатель типа данных слота. К таким типам относятся FRAME (указатель); INTEGER (целое); REAL (вещественное); BOOL (булево); LISP (присоединенная процедура); TEXT (текст); LIST (список); TABLE (таблица); EXPRESSION (выражение) и др.

Значение слота – значение, соответствующее типу данных слота и удовлетворяющее условиям наследования.

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

Присоединенная процедура – это служебная программа процедурного типа, используемая в качестве значения слота, запускается по сообщению, переданному из другого фрейма (например, если поступает сообщение об изменении значения слота зарплата во фрейме ПЕТРОВ, то автоматически должна быть запущена процедура пересчета налога на Петрова во фрейме НАЛОГ).

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