Software & Systems

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

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

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

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

Интеллектуальные системы управления

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

Интеллектуальными в большом называются системы, соответствующие следующим пяти принципам:

-    наличие тесного информационного взаимодействия интеллектуальной системы управления с реальным внешним миром с использованием специально организованных информационных каналов связи;

-    принципиальная открытость систем с целью повышения интеллектуальности и совершенствования собственного поведения;

-    наличие механизмов прогноза изменений внешнего мира и собственного поведения системы в динамически меняющемся внешнем мире;

-    наличие у управляющей системы многоуровневой иерархической структуры, построенной в соответствии с правилом: повышение интеллектуальности и снижение требований к точности по мере повышения ранга иерархии в системе (и наоборот);

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

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

Фильтрация баз знаний

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

Во время разработки системы фильтрация базы знаний имеет дело с корректировкой и реструктуризацией базы знаний.

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

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

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

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

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

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

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

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

Таблицы принятия решений: определение и классификация аномалий

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

Это может быть сформулировано следующим образом. Пусть:

CS = {CSi} (i = 1 … cnum): множество объектов-условий;

CD = {CDi} (i = 1 … cnum): множество наборов условий, где CDi есть множество возможных значений, принимаемых CSi;

CT = {CTi} (i = 1 … cnum): множество множеств состояний условий, где CTi = {Sik} (k = 1 … ni) – упорядоченный набор ni состояний Sik. Каждое состояние Sik есть логическое выражение, содержащее элементы CDi, что определяет подмножество CDi таким образом, что множество всех таких подмножеств составляет разбиение CDi;

AS = {ASj} (j = 1 … anum): множество объектов-действий;

AV = {AVj} (j = 1 … anum): множество множеств значений действий, где AVj = {true(x), false(-), null(.)} – множество всех возможных значений действия ASj, которое в начальный момент равно null для любого j.

Тогда определение таблицы принятия решений запишется в виде:

DT: CT1 ´ CT2 ´ … ´ CT cnum ®

® AV1 ´ AV2 ´ … ´ AV anum.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы

1.   Захаров В.Н. Интеллектуальные системы управления: основные понятия и определения. //Изв. РАН. Теория и системы управления, 1997. - №3.

2.   Vanthienen J. et al. A tool-supported approach to inter-tabular verification. (Программный подход к межтабличной верификации)// Expert Systems with Applications 15, 1998, 277-285.

3.   Zlatareva N. P. A refinement framework to support validation and maintenance of knowledge-based systems. (Основы фильтрации для обеспечения проверки достоверности и ведения систем баз знаний) //Expert Systems with Applications 15, 1998, 245-252.

4.   Zakharov V.N., Stefanyuk T.A. Knowledge Base Update in the Decision Making Process. (Обновление базы знаний в процессе принятия решений) //Abstracts of 3rd Moscow International Conference On Operations Research (ORM 2001), Moscow, 2001, p.128.