Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

FORMAL MODELS OF STRUCTURAL ERRORS IN KNOWLEDGE BASES OF INTELLECTUAL DECISION MAKING SYSTEMS

Dolinina O.N. 1 Suchkova N.K. 1 Rezchikov A.F. 2
1 Yuri Gagarin State Technical University of Saratov
2 Institute of Precision Mechanics and Control of Russian Academy of Sciences
The paper describes the first stage of the intellectual systems debugging – static analysis. The paper accumulates information on structural errors in the rule-based knowledge bases of intellectual systems. It provides classification of structural errors on the base of the graph theory. There are 3 types of structural errors identified: redundancy errors, incompleteness errors and inconsistency. There are suggested the ways of deleting of the errors in the knowledge bases. For each class of the error there is described the detailed description of the incorrect rules. The described approach to the debugging of the intellectual system is considered as the method of static analysis which does not demand the running of the system. Deleting of these types of errors allows to transfer the rule-based knowledge base to the state of the static correctness. The stage of static analysis is a necessary stage of the knowledge base debugging but does not guarantee the absence of the errors in knowledge because of the inconsistency of the knowledge field itself.
debugging of the intellectual decision making systems
static analysis
structural errors
rule-based systems

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

В литературе описаны различные подходы для отладки баз знаний проверки корректности и полноты баз знаний [2–4]. Некоторые ошибки в знаниях могут быть выявлены только в процессе тестирования. К таким относятся ошибки, связанные с противоречивостью самой предметной области, например ошибки вида «забывание об исключении» [1]. В то же время ряд ошибок, связанных со структурой знаний, так называемые структурные ошибки, могут быть обнаружены и исправлены на стадии статической отладки базы знаний.

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

В работах [7–11] приведены некоторые структурные ошибки в базах знаний и описаны алгоритмы их обнаружения, однако формализация ошибок имеется лишь частично. Среди наиболее известных автоматизированных средств верификации необходимо отметить программное обеспечение NuSMV, прошедшее в своем развитии несколько этапов, позволяющее выявлять ряд структурных ошибок для определенного класса продукционных баз знаний и имеющее в своем составе NuSMV язык программирования [6].

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

Формализация структурных ошибок в продукционных базах знаний

Наиболее распространённый способ представления баз знаний интеллектуальных систем – продукции. Продукционную базу знаний можно представить в следующем виде:

P = (F, R, G, C, I), (1)

где F – множество фактов о решаемой проблеме; R – множество правил вида

rm: если fi и fj … и fn то fk, (2)

G – множество целей; C – множество разрешенных комбинаций фактов; I – интерпретатор правил, реализующий вывод.

Пусть S – множество входных фактов, т.е. фактов, устанавливаемых пользователем в интеллектуальной системе. S ⊂ F.

База знаний может быть представлена в виде И/ИЛИ графа. Например, пусть база знаний содержит следующие правила:

r1: если s1 и s2, то f1;

r2: если s2 и s3, то f2;

r3: если s3 и s4 и s5, то f3;

r4: если f1, то g1;

r5: если f2 и f3, то g2.

Тогда приведённым правилам соответствует И/ИЛИ граф на рис. 1.

Правило ri вида

если dol01.wmf и dol02.wmfdol03.wmf, то dol04.wmf (3)

можно представить в виде пары:

dol05.wmf,

где dol06.wmf и dol07.wmf

Как видно из представления, dol08.wmf состоит из единственного элемента, далее обозначаемого как dol09.wmf.

Пусть L – множество цепочек вывода.

dolin1.tif

Рис. 1. И/ИЛИ граф базы знаний

Определение 1. Цепочка вывода li – последовательность правил dol10.wmf такая, что dol11.wmf dol12.wmf при k = 2, …, (n – 1).

Тогда для графа, приведённого на рис. 1, L = {l1, l2, l3, l4, l5, l6, l7, l8}, где l1 = (r1); l2 = (r2); l3 = (r3); l4 = (r4); l5 = (r5); l6 = (r1, r4); l7 = (r2, r5); l8 = (r3, r5).

Определение 2. Начало цепочки вывода li вида dol13.wmf – множество фактов в условии выполнения первого правила, dol14.wmf

Определение 3. Конец цепочки вывода li вида dol15.wmf – следствие последнего правила, dol16.wmf

Определение 4. Структурной ошибкой в продукционной базе знаний называется ошибка, обнаружимая в ходе анализа И/ИЛИ графа. Базы знаний, в которых отсутствуют структурные ошибки, являются статически корректными. Классификация структурных ошибок приведена на рис. 2.

dolin2.tif

Рис. 2. Классификация структурных ошибок в продукционных базах знаний

Рассмотрим подробнее формальные модели ошибок класса «избыточность».

Определение 5. Правила ri и rj называются дубликатами, если dol17.wmf и dol18.wmf

Выделяют 3 вида дубликатов:

- включающие дубликаты;

- полные дубликаты;

- неполные дубликаты.

Определение 6. Правила ri и rj называются включающими дубликатами, если dol19.wmf, при этом dol20.wmf и dol21.wmf В этом случае правило ri называется включаемым.

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

Определение 7. Правила ri и rj называются полными дубликатами, если dol22.wmf и dol23.wmf

Решением в данном случае является удаление всех дубликатов, кроме одного.

Определение 8. Правила ri и rj называются неполными дубликатами, dol24.wmf и dol25.wmf, при этом dol26.wmf и dol27.wmf

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

Определение 9. Цепочка вывода li называется избыточной, если dol28.wmf и ¬qlj такой, что dol29.wmf и dol30.wmf

На рис. 3 приведен пример избыточной цепочки вывода l1 = (r1, r2):

r1: если s1 и s2, то f2;

r2: если f1 и f2, то f3;

dol31.wmf;

dol32.wmf

dolin3.tif

Рис. 3. Избыточная цепочка вывода

Избыточные цепочки вывода могут быть удалены из базы знаний.

Определение 10. li вида dol33.wmf называется незначащей цепочкой вывода, если dol34.wmf при j = 1, …, n.

Выделяют 2 вида незначащих цепочек вывода:

- явные;

- неявные.

Определение 11. Незначащая цепочка вывода li называется явной, если ?rj такое, что dol35.wmf

Явные незначащие цепочки вывода могут быть удалены из базы знаний.

Определение 12. Незначащая цепочка вывода li называется неявной, если ¬?rj такое, что dol36.wmf

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

Определение 13. Сведением к предшествующему правилу rn незначащей цепочки вывода li при условии, что dol37.wmf, называется создание правила rm такого, что dol38.wmf, и удаление li и rn из базы знаний.

Определение 14. Сведением к следующему правилу rn незначащей цепочки вывода li при условии, что dol39.wmf, называется создание правила rm такого, что dol40.wmf, и удаление li и rn из базы знаний.

Различают 2 типа некорректных цепочек вывода:

- цепочки, избыточные по входу;

- цепочки, избыточные по выходу.

Определение 15. Цепочка вывода li называется избыточной по входу, если dol41.wmf

Решением в данном случае является удаление избыточной по входу цепочки.

Определение 16. Цепочка вывода li называется избыточной по выходу, если dol42.wmf

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

Определение 17. Цепочка вывода li называется циклом, если dol43.wmf

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

Определение 18. Правило ri называется простым циклом, если dol44.wmf

Простой цикл должен быть удален из базы знаний.

Рассмотрим класс ошибок «неполнота».

К данному классу ошибок относятся изолированные вершины.

Определение 19. Вершина dol45.wmf называется изолированной, если ¬?rj такое, что dol46.wmf или dol47.wmf

dolin4.tif

Рис. 4. Изолированная вершина

Вершина g1 на рис. 4 является изолированной, т.к. нет правил, ведущих к ней.

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

Рассмотрим класс ошибок «противоречия».

Пусть C – множество разрешенных комбинаций фактов, тогда dol48.wmf

Тогда определим противоречащие цепочки вывода.

Определение 20. Цепочки вывода li и lj называются противоречивыми, если ?fk, такой, что dol49.wmf и dol50.wmf, и ¬?cm такая, что dol51.wmf и dol52.wmf

dolin5.tif

Рис. 5. Противоречивые цепочки вывода

На рис. 5 l1 = (r1, r2) и l2 = (r3) являются противоречивыми:

- dol53.wmf

- dol54.wmf

- dol55.wmf

- dol56.wmf

- dol57.wmf

- нет ck = (f6, f7).

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

Заключение

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

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