Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,858

ФОРМАЛЬНЫЕ МОДЕЛИ СТРУКТУРНЫХ ОШИБОК В БАЗАХ ЗНАНИЙ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ

Долинина О.Н. 1 Сучкова Н.К. 1 Резчиков А.Ф. 2
1 ФГБОУ ВО «Саратовский государственный технический университет имени Гагарина Ю.А.»
2 Институт проблем точной механики и управления РАН
В статье описана первая стадия отладки интеллектуальных систем – статический анализ; обобщается информация о структурных ошибках в продукционных базах знаний интеллектуальных систем. Приводится классификация структурных ошибок и их формализация на основе теории графов. Выделяется 3 класса структурных ошибок: ошибки избыточности, ошибки неполноты и противоречия – и приводятся рекомендации по их устранению. Для каждого класса ошибок приводится детальный анализ наличия ошибочных продукций. Описываемый подход к отладке интеллектуальных систем относится к методам статического анализа, не требующим запуска системы на выполнение. Устранение данных ошибок позволяет привести продукционную базу знаний в состояние статической корректности. Этап статического анализа является необходимым этапом отладки баз знаний, но не гарантирует отсутствия ошибок в знаниях за счет противоречивости самой предметной области.
отладка интеллектуальных систем принятия решений
статический анализ
структурные ошибки
продукционные базы знаний
1. Долинина О.Н. Алгоритмы и методы разработки и отладки экспертных систем: монография. – Саратов: Саратовский гос. технический ун-т, 2015 – 225 с.
2. Рыбина Г.В., Смирнов В.В. Методы и алгоритмы верификации баз знаний в интегрированных экспертных системах // Известия РАИ. Теория и системы управления. – 2007. – № 4. – С. 91–102.
3. Cimatti A., Corvino R., Lazzaro A., Narasamdya I., Rizzo T., Roveri M., Sanseviero A., Tchaltsev A.: Formal Verification and Validation of ERTMS Industrial Railway Train Spacing System. In Madhusudan, P., Seshia, S.A., eds.: CAV. Volume 7358 of LNCS., Springer (2012). P. 378–393.
4. Cragun B.J. Stendel H.J. A decision-table-based processor for checking completeness and consistency in rule-based expert systems // Int. J. Man-Mach. Stud. – 1987. – Vol. 26, № 5. – P. 633–648.
5. Dolinina O. Method of the Debugging of the Knowledge Bases of Intellectual Decision Making Systems / Advances in Intelligent Systems and Computing // Proc. Of the 5th Computer Science On-line Conf. 2016 (CSOC2016), 2016. – vol. 3. – P. 301–315.
6. Ferrante O., Benvenuti L., Mangeruca L., Sofronis C., Ferrari A.: Parallel NuSMV: A NuSMV Extension for the Verification of Complex Embedded Systems / Ortmeier, F., Daniel, P., eds.: SAFECOMPWorkshops. Volume 7613 of LNCS., Springer (2012). – P. 409–416.
7. Knauf R., Gonzalez A.J., Abel T. A framework for validation of rule-based systems / IEEE Trans Syst Man Cybern B Cybern. 2002; 32(3), P. 281–295.
8. Miller S.P., Whalen M.W., Cofer D.D. Software model checking takes off / Commun. ACM 53(2). (February 2010), Р. 58–64.
9. Pira E., Reza Zand Miralvand M., and Soltani F. Verification of Confliction and Unreachability in Rule-Based Expert Systems with Model Checking. URL: https://arxiv.org/abs/1404.2768 (дата обращения: 10.04.2014).
10. Suwa H., Scott A.C., Shortliffe. An Approach to Veryfing Consistency and Completeness in a Rule-Based Expert System // Rule-Based Expert Systems. – London: Addison – Wesley, 1984. – P. 159–170.
11. Xu D., Kejian Xia, Dezheng Zhang, Huangsheng Zhang Model Checking the Inconsistency and Circularity in Rule-Based Expert Systems / Computer and Information Science. – 2009. – vol. 2, № 1. – P.12–17.

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

В литературе описаны различные подходы для отладки баз знаний проверки корректности и полноты баз знаний [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 типа структурных ошибок: ошибки класса избыточности, ошибки неполноты и противоречия. К первому типу отнесены дубликаты, избыточные цепочки вывода, незначащие цепочки вывода, некорректные цепочки вывода и циклы. Ошибка вида «изолированные вершины» рассмотрена как ошибка класса неполноты. Противоречия в базах знаний представлены в работе противоречивыми цепочками вывода. Каждая рассмотренная ошибка формализована и снабжена описанием способа её исправления.

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


Библиографическая ссылка

Долинина О.Н., Сучкова Н.К., Резчиков А.Ф. ФОРМАЛЬНЫЕ МОДЕЛИ СТРУКТУРНЫХ ОШИБОК В БАЗАХ ЗНАНИЙ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ // Современные наукоемкие технологии. – 2017. – № 3. – С. 7-11;
URL: http://www.top-technologies.ru/ru/article/view?id=36607 (дата обращения: 20.11.2018).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252