Software & Systems

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

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

Древоподобные решающие структуры

Дрсвоподобная решающая структура (ДРС) может служить моделью процедуры принятия решения в задаче определения класса, которому принадлежит предъявленный объект, по набору значений признаков, описывающих этот объект [7]. Внутренние вершины ДРС соответствуют некоторым закономерностям предметной области (ПО), определяемым через параметры ПО (признаки), а внешние (листья) -названиям допустимых классов (решений). Совокупность признаков образует признаковое пространство, а набор конкретных значений признаков представляет собой объект (точку) признакового пространства. Если известен класс, которому принадлежит объект, то этот объект может рассматриваться в качестве призера решения задачи определения класса. Каждый лист ДРС соответствует некоторой части признакового пространства и через определенные внутренние вершины - решающие правила (Р-П) соединен с единственной корневой вершиной дугами, образующими конъюнктивную ветвь ДРС.

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

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

-    интерактивный режим последовательного по строения ДРС "сверху-вниз", при котором оконча тельный выбор и коррекцию Р-П, приписываемых вершинам, мог бы производить эксперт;

-    одновременное использование различных типов знаний - сведений о структуре ПО и о ее связях с "внешним миром", примеров и правил принятия ре шений - для обеспечения достаточной полноты базы знаний;

-    использование при построении ДРС и выводе решения всех введенных знаний, а не только наиболее информативных, для обеспечения большей избыточ ности знаний;

-    возможность работы в условиях неопределен ности (отсутствие данных о части признаков при эксплуатации ДРС не должно приводить к прекраще нию вывода решения);

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

-    возможность модификации ДРС без полной ее перестройки в случае появления новых знаний о ПО, адаптации к изменению конкретных условий эксплуа тации;

-    реализацию функций объяснения;

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

Построение ДРС

Большинство существующих методов построения ДРС [2, 3] основано на подходе "снизу-вверх", состоящем в предварительном определении набора фрагментов пространства признаков, или, иначе, разбиении множества объектов (примеров) на группы, крто-рые затем используются для дальнейшего синтеза Р-П [5]. При таком построении ДРС содержат в себе Р-П, отражающие присущие ПО статистические зависимости, по не поддающиеся, как правило, содержательной интерпретации на основе представлений о структуре и внутренних связях ПО, сложившихся у прикладных специалистов. Если решающая система на базе ДРС функционирует в автоматическом режиме, то указанная особенность не является недостатком. В диалоговом же режиме система последовательно задает пользователю вопросы о значениях признаков, соответствующие Р-П. Если сами вопросы и их очередность не поддаются содержательной интерпретации и противоречат сложившимся в ПО представлениям, это вызывает недоверие к решающей системе и делает невозможным ее применение.

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

Для построения ДРС предлагается использовать уже показавший свою эффективность в ШЗ-методе [10] и ряде программных средств [9] таксономический подход "сверху-вниз".

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

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

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

Для построения ДРС важен способ оценки эффективности Р-П. Следует заметить, что при использовании Интегральных критериев, как например,

эвристические цены свойств-предикатов в СА-методе [5] или оценки вероятности ошибки элементарных высказываний в методе логических функций [10], оценка Р-П производится на основе некоторой обобщенной величины, что не дает возможности содержательного анализа эффективности Р-П.

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

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

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

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

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

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

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

Опыт работы с экспертами по созданию ЭС показал, что практически все передаваемые им правила продукционного вида "если..., то..." могут быть отнесены к одному из четырех типов: необходимость (от классов — к признакам), достаточность (от признаков - к классам), закономерная связь признаков, условие разделяемости классов. Для совместного использования примеров и правил предлагается, во-первых, проводить их взаимную проверку на непротиворечивость и, во-вторых, представлять экспертные правила в виде элементарных предикатов, которые затем, как и правила, сгенерированные по примерам, могут быть выбраны в качестве Р-П вершины ДРС.

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

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

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

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

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

Использование описанного подхода позволило построить и применить ДРС для решения ряда типичных логических задач, среди которых - задача о распределении ресурсов и задача "о людоедах и миссионерах", фактически являющаяся примером теста для интеллектуальных систем.

Одним из характерных свойств решающих систем, в частности ЭС, является способность приобретать новые знания на любом этапе функционирования. Однако ДРС - "жесткая" структура, учитывающая множественные зависимости между параметрами, характеризующими ПО, и появление новых знаний о ПО обычно приводит к необходимости построения ДРС вновь.

Вместе с тем, разработаны способы автоматической модификации ДРС без полной ее перестройки в случаях, когда описание ПО дополняется новыми классами, признаками, или вводятся новые примеры и правила. Такие модификации связаны с продлением ветвей ДРС. Адаптация ДРС к конкретным условиям функционирования производится настройкой весовых коэффициентов альтернативных правил и пороговых значений признаков в Р-П.

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

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

На основе описанной методики разработан программный комплекс для построения ЭС и СПР "HtddenLine" [3].

Программный комплекс для построения ЭС и СПР "HiddenLine"

"HiddenLine" может быть использован для построения ЭС, работающих на IBM PC/PS в нескольких схемах диалога о возможностью получения информации как от пользователя через клавиатуру, так и от внешних датчиков, программных модулей и баз данных, а также для построения ДРС, предназначенных для последующего использования в других системах, требующих принятия решений, например, для интеграции в АСУ ТП.

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

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

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

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

Опытная эксплуатация программного комплекса "HiddenLine" подтвердила эффективность предлагаемой методики.

Сравнение работы "HiddenLine" с работой "1-st Class" показало несомненное преимущество первой системы в решении задач с неопределенными значениями признаков. Сравнение с "Rule Master" позволило сделать вывод о том, что "Hidden Line" строит ДРС с более адекватной представлениям о ПО фрагментацией признакового пространства и с более эффективными Р-П. В отличие от обеих указанных систем, "HiddenLine" справляется с задачами, в которых решающей системе предъявляются объекты, обладающие свойствами двух или более классов.

Следует заметить, что круг задач, на которых проводилось сравнение, ограничивается со стороны "I-st Class" и "Rule Master", поскольку возможности "HiddenLine'1 существенно шире.

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

1.      Лбов Г.С., Пестунова Т.М. Построение дерева разбие ний в задаче группировки объектов с использованием логических функций. - Вычислительные системы, 1986. - Вып. 117. -С.63-77.

2.      Обручев В.Л., Ковале» А.В., Пригожий Б.В. Инстру ментальное средство создания экспертных систем "ДИАГ НОСТ". / Тез. докл. Всесоюз. со вещ. по экспертным системам. (Суздаль, декабрь 1990 г.). - М.: ИПУ, 1990.

3.      Обручев В.Л., Ковалев А.В., Прнгожнн Б.В. Комплекс инструментальных средств разработки экспертных систем "HIDDEN LINE". / Тез. докл. Международ, конф. "Технология программирования 90-х". (Киев, май 1991 г.). - Киев, 1991. - C.48-S0.

4.      Приобретение знаний. / Под ред. С.Осуги, Ю.Саэки. - М.:Мир, 1990. -304 с.

5.      Теорий R-функций и актуальные проблемы приклад ной математики. - Киев: Наукоаа думка, 1986. - 264 с.

6.      Уотермен Д. Руководство по экспертным системам. - М-: Мир, 1989. - 388 с.

7.      Фу К. Структурные методы распознавания образов. - М.:Мир, 1977.-319 с.

8.      Gevarter W.B. The Nature and Evaluation of Commercial Expert System Building Tools // Computer. 1987. - Vol. 20, N 5.- p. 24-41.

9.      Michie D., Muggleton S., Riese C, Zubrick S. RULE MASTER: a second-generation knowledge-engineering facility. Proceeding of the 1-st Conference on Artifical Intelligence Applications, IEEE Computer Society, December, 1984.

10. Quinlan J.R. Induction of decision tree // Machine Learning. - 1986. Vol.1, N 1. - pp. 81-106.