BC/NW 2011; №2 (19):13.2

РАЗРАБОТКА МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ ДЛЯ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ НА ОСНОВЕ ПРЕЦЕДЕНТОВ

Варшавский П.Р., Пчелина С.М.

(Национальный исследовательский университет «МЭИ», Россия)

Работа выполнена при финансовой поддержке грантов РФФИ (проекты № 09‑01‑00076-а, № 11-01-00140-а)

Проблема представления, накопления и оперирования знаниями в интеллектуальных (экспертных) системах является очень актуальной в области искусственного интеллекта (ИИ). Эта проблема тесно связана с задачей моделирования правдоподобных рассуждений для интеллектуальных (экспертных) систем и, в частности, систем поддержки принятия решений (ИСППР) [1].

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

В большинстве энциклопедических источников прецедент определяется как случай, имевший место ранее и служащий примером или оправданием для последующих случаев подобного рода, а рассуждение на основе прецедентов (CBR – Case-Based Reasoning) является подходом, позволяющим решить новую, неизвестную задачу, используя или адаптируя решение уже известной задачи.

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

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

В работе основное внимание уделяется моделям представления прецедентов и методам извлечения прецедентов из библиотеки прецедентов (БП) системы.

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

Как правило, CBR-методы включают четыре основных этапа, образующих так называемый CBR-цикл или цикл обучения по прецедентам (примерам) [3], структура которого представлена на рис. 1.

Рис. 1. Структура CBR-цикла

Основными этапами CBR-цикла являются:

− извлечение наиболее подходящего (подобного) прецедента (или прецедентов) для сложившейся ситуации из БП;

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

− адаптация и применение полученного решения для решения текущей проблемы;

− сохранение вновь приятого решения как части нового прецедента.

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

Выбор метода извлечения прецедентов напрямую зависит от выбранного метода представления знаний (МПЗ). Существует множество способов представления и хранения прецедентов [4]. Основные способы представления прецедентов можно разделить на следующие группы: параметрические, объектно-ориентированные, специальные (в виде деревьев, логических формул и т.д.).

В большинстве случаев для представления прецедентов достаточно простого параметрического представления, т.е. представления прецедента в виде набора параметров с конкретными значениями и решения (диагноз по проблемной ситуации и рекомендации ЛПР):

CASE = (x₁, x₂, … , x_n, R),

где x₁…x_n – параметры ситуации, описывающей данный прецедент (x₁X₁, x₂X₂, … ,x_nX_n), R – диагноз и рекомендации ЛПР, n – количество параметров прецедента, а X₁, … , X_n – области допустимых значений соответствующих параметров прецедента.

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

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

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

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

Знания о ПО представляются набором правил, которые проверяются на группе фактов и знаний о текущей ситуации (входной информации). Интерпретатор правил сопоставляет часть правил ЕСЛИ с фактами и выполняет то правило, для которого часть ЕСЛИ соответствует фактам, то есть интерпретатор правил работает в цикле «сопоставить – выполнить», формируя последовательность действий. Таким образом, продукционные правила обеспечивают формальный способ представления рекомендаций, знаний или стратегий.

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

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

Существует целый ряд методов извлечения прецедентов и их модификаций [4]. В случае параметрического представления прецедентов чаще всего используется метод ближайшего соседа (Nearest Neighbor) [5].

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

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

С целью применения предложенной гибридной модели представления прецедентов и метода накопления знаний для CBR-системы была выполнена программная реализация базовых модулей с использованием языка программирования C# под ОС Windows XP.

В работе рассмотрена проблема представления и накопления знаний (прецедентов) в интеллектуальных системах на основе прецедентов (CBR-системах). Рассмотрены различные модели представления прецедентов и предложена гибридная модель представления прецедентов для CBR-системы. Исследованы методы извлечения прецедентов из БП CBR-системы. Выполнена программная реализация соответствующих базовых модулей для прототипа CBR-системы.

Литература

1. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах / под ред. В.Н. Вагина, Д.А. Поспелова.
– М.: ФИЗМАТЛИТ, 2004. – 704 с.

2. Варшавский П.Р., Еремеев А.П. Методы правдоподобных рассуждений на основе аналогий и прецедентов для интеллектуальных систем поддержки принятия решений // Новости искусственного интеллекта. 2006. №3. – С. 39-62.

3. Aamodt A., Plaza E. Case-based reasoning: foundational issues, methodological variations, and system approaches // AI Communications. IOS Press. Vol. 7: 1. 1994. – P. 39-59.

4. Варшавский П.Р., Еремеев А.П. Моделирование рассуждений на основе прецедентов в интеллектуальных системах поддержки принятия решений // Искусственный интеллект и принятие решений. 2009. №2. – С. 47-48.

5. Варшавский П.Р. Механизмы правдоподобных рассуждений на основе прецедентов (накопленного опыта) для систем экспертной диагностики // 11-я национальная конференция КИИ-2008: Труды конференции. В 3-х т., Т. 2. – М: Ленанд, 2008. – С. 321-329.