Материал: Алгебра_кортежей
Преобразуем условия правил 1 и 2 в АК-объекты, приведя их к единой схеме отношения [XYZ]. Тогда получим:
Условие правила 1: R1 |
{c} {b} |
|
, |
||
= |
|
|
|
||
|
|
|
{c} |
|
|
Условие правила 2: R2 |
{b} |
|
|
. |
|
= |
|
|
|
||
|
|
|
{b} |
|
|
Покажем, как используются |
эти |
правила в АК. Пусть поступила |
|||
информация: "Основные источники вышли из строя в одном эшелоне, аварийные источники в строю и канализация энергии нарушена частично". Эта информация преобразуется в C-кортеж T = [{b} {a} {b}]. Применим правило 1, для чего найдем пересечение T R1 = . Следовательно, ситуация не соответствует этому правилу. Применим правило 2:
T R2 = [{b} {a} {b}].
Поскольку пересечение не пусто, то W = b.
Проанализируем корректность указанных правил средствами АК. Вопервых, проверим неоднозначности, то есть определим, содержат ли разные
условия какие-либо общие ситуации. Для |
этого |
вычислим |
пересечение |
||||
R1 R2 |
{c} |
{b} {b} |
. Анализ показывает, |
что |
все общие |
для данных |
|
= |
|
|
|||||
|
{b} |
{c} |
|
|
|
|
|
условий ситуации соответствуют состоянию W = c. Но в самой ЭС неоднозначности не возникают, так как приоритет правила 1, в котором предусмотрено это состояние, более высок, и эта ситуация распознается правильно. Возможен и другой вид некорректности, когда некоторые критические состояния не включены ни в одно из условий для аварийных ситуаций. Для анализа вычислим множество таких состояний с помощью формулы R1 R2 .
|
|
|
|
|
{c} {b} |
||
|
|
|
|
R1 R2 |
= |
||
|
{b} |
|
|
|
|
|
|
|
|
||
{c} {b} {c} = {b} {b}
{b,c} ,
200
{a,b}
R1 R2 = {a,c}
{a}
{a} .
Получилась D-система. Преобразуем ее в ортогональную C-систему:
{a,b} |
{a} |
|
|
{a} |
{a} |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
{a} |
= {c} |
{a} {a} . |
|||
{a,c} |
|
|
|
|
|
|
|
|
|
|
|
|
|
Для специалиста понятно, что из 3-х возможных ситуаций одна (а именно [{c} {a} {a}]) является аварийной и соответствует состоянию W = c. Но она не включена ни в одно из условий, поэтому правила нужно откорректировать. В данном случае корректировка заключается в добавлении C-кортежа [{c} {a} {a}] в условие R1. В результате получим:
|
|
|
|
|
|
|
{c} {b} |
|
|||
|
|
|
|
|
|
R1 = |
|
{c} . |
|||
|
{c} {a} {a} |
||||
|
|
|
|
|
|
Используя средства АК, можно также заменить комплект правил одним АК-объектом. Для этого объединим созданные в системе АК условия в один АК-объект и добавим атрибут, характеризующий состояние всей системы, в который запишем соответствующие состояния. Тогда получим АК-объект, позволяющий распознать все возможные ситуации. В частности, для рассмотренного примера таким АК-объектом будет C-система
|
|
|
|
|
{c} |
{b} |
{c} |
||
|
|
|
{c} |
{c} |
|
|
|
|
|
{c} |
{a} {a} {c} |
|||
R[XYZW] = |
|
|
|
|
{b} |
{b} |
|||
|
|
|
{b} {b} |
|
|
|
|
|
|
{a} |
{a} {a} |
|||
Допустим, на вход поступила информация X = b, Z = c. Она преобразуется в C-кортеж T[XYZW] = [{b} {c} ], и находится пересечение T R. В данном случае после выполнения операции получим C-систему
|
|
|
|
|
{b} |
{c} |
{c} |
= [{b} {c} {c, b}] |
|
|
|
|
|
|
{b} |
{c} |
{b} |
|
|
|
|
|
|
201 |
снеоднозначным результатом в атрибуте W. Однако эту неоднозначность можно устранить, если использовать правило приоритета. Приоритет здесь определяется порядком расположения C-кортежей в R: первый полученный непустой результат пересечения является окончательным. С учетом этого для заданного входа получается результат W = c.
Из приведенного примера видно, что на основе АК можно создавать "прозрачные" и сравнительно простые в реализации интерпретаторы экспертных систем и к тому же проверять корректность правил на этапе проектирования системы. В последние годы по мере усложнения прикладных ЭС стало ясно, что для их разработки явно недостаточно средств, которые используются в "интеллектуальных" языках программирования (Пролог, Лисп и др.). Поэтому разработчики вынуждены переходить на программирование ЭС
спомощью языков высокого уровня, таких как C++, Object Pascal, Perl и т.д., где используются и средства управления базами данных, и методы объектноориентированного программирования. Вызвано это необходимостью совмещения структур данных и знаний. Использование АК позволяет более просто решить эту проблему, так как в ней данные и знания органично выражаются в одних и тех же структурах и обеспечены соответствующими алгоритмами.
Семантические сети. Покажем, как в АК осуществляется вывод на семантических сетях [Kulik, 2010]. Каждую семантическую сеть можно представить как совокупность бинарных отношений. Правила вывода в семантической сети записываются в виде продукций, в левой части которых содержится какой-либо фрагмент семантической сети (соединения или композиции некоторых из исходных отношений), а в правой части – фрагмент, заменяющий левую часть или добавляемый в семантическую сеть как новое отношение при срабатывании правила. Например, отношение "быть внуком" появляется в результате композиции отношения "быть сыном" с самим собой.
При реализации продукционного правила средствами АК в общем случае необходимо выполнить следующую последовательность шагов:
1)получить соединение или композицию отношений, стоящих в левой части правила;
2)исключить из получившегося отношения P все кортежи, не удовлетворяющие заданным ограничениям;
202
3)получить соединение (композицию) отношений T, стоящих в правой части продукции, при необходимости с учетом множества кортежей, получившихся при вычислении левой части правила;
4)если в правиле предусматривается замена левой части на правую, то из исходной базы знаний удалить все связи, содержащиеся в P;
5)добавить в базу знаний все связи из отношения T.
Рассмотрим пример из книги Д.А. Поспелова [Поспелов, 1989].
Исходная семантическая сеть изображена на рис. 5.6, правило вывода на этой сети на рис. 5.7, а результат применения правила – на рис. 5.8.
Рис. 5.6. Исходная семантическая сеть
Рис. 5.7. Продукция
Рис. 5.8. Результат применения продукции
Сначала выразим в структурах АК исходную сеть. Ее на языке АК можно записать в виде совокупности C-систем и С-кортежей:
|
|
|
|
|
|
R1[XY] = {A} |
{B} |
|
{A} |
{D} |
|
; R2[ZY] = {D} |
{E} ; |
||||
{D} |
{C,F,G,H} |
{K} |
{F,G,H,I} |
||
|
|
|
|
|
|
R3[VY] = [{K} {L}]; R4[ZW] = [{A} {A}].
В левой части продукции предусматривается соединение отношений R1 и
203
R2 при условии, что значением атрибута X в R1 является D, а в R2 – K. Процедура выполнения продукции осуществляется в соответствии с уже описанным алгоритмом, за исключением того, что фильтрация отношений производится перед их соединением (иногда это более эффективно).
Шаг 1. Сначала отношения R1 и R2 приводятся в соответствие с ограничениями.
P1[XY] = R1[XY] [{D} ] = [{D} {C, F, G, H}];
P2[ZY] = R2[ZY] [{K} ] = [{K} {F, G, H, I}].
Шаг 2. Далее выполним перестановку атрибутов в отношении P2[ZY] и вычислим соединение полученных отношений:
P[XYZ] = P1[XY] P2[YZ] = [{D} {C, F, G, H} ] [ {F, G, H, I} {K}] = = [{D} {F, G, H} {K}].
Шаг 3. Отсутствует.
Шаг 4. Теперь, когда определено значение атрибута Y, можно вычислить правую часть продукции: P3[VY] = [{M} {F, G, H}].
Шаги 5 и 6. Остается откорректировать базу знаний. Для этого отношение R3 объединим с отношением P3 и откорректируем отношения R1 и R2 с учетом
проекций |
отношения |
P: |
P4[XY] = P[XY] = [{D} {F, G, H}] |
и |
||
P5[ZY] = P[ZY] = [{K} {F, G, H}], |
соответственно. Для этого с помощью |
|||||
алгоритмов |
АК вычислим |
разности R1[XY] \ P4[XY] = R1[XY] |
|
[XY] |
и |
|
P4 |
||||||
R2[ZY] \ P5[ZY] = R2[ZY] P5 [ZY]. Теперь добавим к R3[VY] кортежи отношения P3[VY] и получим сеть, изображенную на рис. 5.8:
R1[XY] =
R3[VY] =
|
|
{A} {D} |
||
|
|
|||
{A} {B} |
||||
|
|
; R2[ZY] = {D} |
{E} ; |
|
{D} {C} |
{K} |
{I} |
||
|
|
|
|
|
{K} |
{L} |
; R4[ZW] = [{A} {A}]. |
|
|
|
{M} |
{F,G,H} |
|
Фреймы. Каждый фрейм состоит из набора слотов. Имя фрейма соответствует имени некоторого отношения, а имя слота внутри фрейма – имени какого-либо атрибута этого отношения. Таким образом, в простейшем случае фрейм есть своеобразное представление обычных файлов базы данных (таблиц или АК-объектов). Фрейм может иметь более разветвленную структуру, когда значениями некоторых слотов являются не элементы
204