Software & Systems

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

К сожалению, в большинстве случаев известные СОЗ и ЭС [1, 2, 4] либо узко проблемно-ориентированные (позволяют решать задачи только в одной предметной области и не могут применяться для других предметных областей), либо ориентированы на использование только одной определенной модели представления знаний и не дают возможности автоматизировать преобразования построенной модели знаний из одной структуры в другую.

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

Постановка задачи

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

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

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

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

Разработка математического обеспечения для представления знаний

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

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

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

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

Система функционирует так, как показано на рисунке 2.

Вначале осуществляется выбор режима работы системы.

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

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

Подсистема моделирования семантических сетей

Данная подсистема основана на ранее разработанной автором библиотеке Semantic Network Toolbox (SNToolbox) [10] и содержит функции для работы с моделями на основе семантических сетей (МCC) [1, 6]. Процесс создания и использования МCC состоит в последовательном выполнении следующих этапов.

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

Этап 2. Загрузка и визуализация МСС: осуществляется загрузка сети с диска в переменную среды, если сеть отсутствует в среде; затем для заданной переменной, содержащей МСС, выполняется вызов функции визуализации МСС, после чего по желанию пользователя построенная схема МСС сохраняется в файле на диске или выводится на принтер.

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

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

Функции подсистемы предъявляют определенные требования к семантической сети: каждый узел должен носить уникальное имя; сеть должна иметь узлы указанного типа (AND или OR); для поиска в сети-запросе должен быть только один целевой узел; обеспечивается только вывод от предпосылок к следствиям; функция Snfind работает исключительно с иерархическими (слоистыми) сетями. То есть для корректного использования этой функции нельзя задавать полносвязные сети, сети с латеральными связями (связями между узлами одного слоя) и сети с элементами, которые связаны сами с собой. Рассмотрим основные функции подсистемы.

Функция SN=Snnew создает новую структу- ру для семантической сети в переменной SN. В структуру семантической сети переменной SN будут входить поля: SN.node – клеточный одномерный массив, содержащий названия узлов сети, которые являются строками; SN.relation – клеточный двухмерный массив, содержащий названия отношений между узлами сети, являющимися строками (строки массива соответствуют узлам, от которых направлены отношения, а столбцы – узлам, к которым направлены отношения); SN.nodetype – обычный одномерный массив, содержащий коды типов узлов сети (0 – AND-узел, 1 – OR-узел).

Узлы семантической сети в подсистеме делятся на два типа:

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

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

Функции Res=SNaddANDnode(SN, 'node1', 'no­de2', ..., 'node') и Res=SNaddORnode(SN, 'node1', 'node2', ..., 'node') добавляют узлы 'node1', 'node2', ..., 'node' типа AND и OR, соответственно, в семантическую сеть переменной SN (переменная SN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=SNdelnode(SN, 'node1', 'node2', ..., 'node') удаляет узлы 'node1', 'node2', ..., 'node' из семантической сети переменной SN (переменная SN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=SNaddrelation(SN, 'node1', 'rela­tion', 'node2') добавляет отношение 'relation', направленное от узла 'node1' к узлу 'node2' семантической сети переменной SN (переменная SN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=SNdelrelation(SN, 'node1', 'rela­tion', 'node2') удаляет отношение 'relation', направленное от узла 'node1' к узлу 'node2' семантической сети переменной SN (переменная SN при этом не модифицируется). Результат возвращается в переменной Res.

Функция SNplot(SN, type, NodeColour, Relation­Colour) строит графическое изображение структуры семантической сети переменной SN (см. рис.: http://www.swsys.ru/uploaded/image/2015/2015_dop/1.jpg). Параметр type должен быть строкой, задающей расположение узлов семантической сети на графике: 'circle' – по кругу, 'random' – случайно, 'hierarchy' – иерархично. Параметры NodeColour и RelationColour являются необязательными, они должны быть строками, определяющими цвет узлов и цвет связей сети соответственно. Цвета должны быть заданы символами: b – синий, g – зеленый, r – красный, c – светло-голубой, m – сиреневый, y – желтый, k – черный.

Функция Res=SNfind(SN, SN1) ищет целевой узел МСС переменной SN1 в МСС переменной SN. Сеть переменной SN1 должна быть подсетью сети переменной SN. Целевой узел в переменной SN1 должен иметь название '?'. Функция возвращает результат в переменной Res. В итоге получаем значение "[]", если целевой узел не был найден, или имена целевых узлов, если они были найдены.

Подсистема моделирования фреймовых сетей

Подсистема моделирования фреймовых сетей (ФС) [5, 8] содержит набор функций для создания, модификации и обработки знаний на основе фреймовых моделей. Процесс создания и использования ФС состоит в последовательном выполнении следующих этапов.

Этапы 1 и 2 выполняются аналогично этапам рассмотренного выше процесса создания МСС: простые узлы заменяются на фреймы, которые можно задавать как программно в консольном режиме, так и в графической форме.

Этап 3. Поиск на ФС: для заданной переменной ФС-базы знаний осуществляется последовательный поиск сверху вниз с последовательной конкретизацией значений слотов фреймов посредством задания системой вопросов пользователю.

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

Функция FN=Fnnew создает новую структуру для ФС в переменной FN аналогично функции Snnew, однако поле FN.node будет содержать клеточный одномерный массив структур узлов-фреймов; FN.relation – клеточный двумерный массив, содержащий названия отношений между узлами сети, являющимися строками (строки массива соответствуют узлам, от которых направлены отношения, а столбцы – узлам, к которым направлены отношения).

Функция Res=FNnewframe('framename', slots) создает переменную-фрейм Res в среде. Узлы ФС в подсистеме описываются структурой, содержащей следующие поля: framename – имя фрейма, slots – клеточный массив слотов фрейма. Каждый слот представляет собой структуру, содержащую поля: slotname – имя слота, slottype – тип значений слота, slotvalue – значение слота, slotinheritance – указатель типа наследования (определяет, наследуются ли слот и его значение от родительского фрейма и каким образом), slotproc – имя функции, реализующей присоединенную к слоту процедуру обработки событий. По умолчанию каждому слоту сопоставляются функции-демоны, которые вызываются при отсутствии в слоте значений: вначале они пытаются получить значение слота из вышерасположенных фреймов путем наследования, а при невозможности это сделать выдают пользователю запрос на ввод значения. При наличии заданной присоединенной функции она вызывается при каждом обращении к слоту, а функция-демон вызывается после нее и лишь при отсутствии значения в слоте.

Функция Res=FNaddnode(FN, 'node1', 'node2', ..., 'node') добавляет узлы из переменных среды с именами 'node1', 'node2', ..., 'node' в ФС пе- ременной FN (переменная SN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=FNdelnode(FN, 'node1', 'node2', ..., 'node') удаляет узлы с именами фреймов 'node1', 'node2', ..., 'node' из ФС переменной FN (переменная FN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=FNaddrelation(FN, 'node1', 'rela­tion', 'node2') добавляет отношение 'relation', направленное от фрейма-узла с именем 'node1' к фрейму-узлу с именем 'node2' ФС переменной FN (переменная FN при этом не модифицируется). Результат возвращается в переменной Res.

Функция Res=FNdelrelation(FN, 'node1', 'rela­tion', 'node2') удаляет отношение 'relation', направленное от фрейма-узла с именем 'node1' к фрейму-узлу с именем 'node2' ФС переменной FN (переменная FN при этом не модифицируется). Результат возвращается в переменной Res.

Функция FNplot(FN) строит графическое изображение структуры ФС переменной FN.

Функция Res=FNfind(FN, ['frame']) осуществляет поиск в ФС переменной FN узла, соответствующего протофрейму, заданному переменной среды с именем 'frame'. При отсутствии параметра 'frame' либо указанной переменной в среде осуществляется поиск сверху вниз по фреймовой модели с использованием корня сети как протофрейма (поискового образца). Результат возвращается в переменной Res как фрейм, наиболее соответствующий запросу.

Подсистема моделирования продукционных моделей

Подсистема содержит набор функций для создания, модификации и обработки знаний на основе продукционных моделей (ПМ) [4, 5, 7]. Процесс создания и использования ПМ состоит в последовательном выполнении следующих этапов.

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

Этап 2. Загрузка продукционной базы знаний с диска в переменную среды, если переменная базы знаний отсутствует в среде.

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

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

Функция PM=PMnew создает новую структуру для ПМ в переменной PM. Поле PM.variables содержит массив структур переменных-фактов, поле PM.rules – массив структур правил.

Функция Res=PMaddvariable(PM, 'variablena­me', vartype, 'question', [answers]) добавляет новую переменную с именем 'variablename', типом vartype (0 – логическая, 1 – целая, 2 – вещественная, 3 – текстовая), вопросом 'question', выдаваемым пользователю при запросе значения переменной, и answers – клеточным массивом вариантов ответов-значений переменной (если задан, то пользователю будут предлагаться для выбора только варианты, содержащиеся в массиве, в противном случае будут приниматься произвольные значения, удовлетворяющие типу переменной, вводимые в диалоговое поле).

Функция Res=PMaddrule(PM, 'rulename', antec­type, antecvar, antecval, 'consvar', consval, CF) добавляет в базу знаний PM правило с именем 'rulename', типом объединения условий antectype (0 – тип «И», 1 – тип «ИЛИ»), массивом текстовых строк – имен переменных антецедента правила antecvar, клеточным массивом значений переменных антецедента правила antecval, именем переменной консеквента 'consvar', значением переменной консеквента 'consval' и коэффициентом уверенности правила CF.

Функция PMNplot(PM) строит графическое изображение сети правил переменной PM.

Функция Res=PMfind(PM, 'var', strategy) осуществляет поиск в базе знаний продукционной модели PM значения целевой переменной с именем 'var'. При отсутствии значения целевой пе- ременной пользователю задаются вопросы, необ- ходимые для занесения фактов в переменные рабочей памяти, и вызывается функция вывода по набору правил c использованием стратегии разрешения конфликта правил с кодом strategy (0 – стратегия новизны правил, 1 – стратегия старости правил, 2 – стратегия новизны фактов, 3 – стратегия старости фактов, 4 – стратегия простоты, 5 – стратегия сложности). Результат возвращается в переменной Res в виде структуры с полями: value – найденное значение целевой переменной и СF – коэффициент уверенности в результате.

Подсистема преобразования и анализа структур представления знаний

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

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

Преобразование ФС в семантическую сеть: двигаясь от корня ФС сверху вниз, из слотов фрейма верхнего уровня осуществляется подстановка значений в связанные с ним фреймы нижнего уровня в соответствии с указателями наследования, после чего фреймы нижнего уровня с подставленными значениями преобразуются в вершины СМ: имена фреймов нижнего уровня – в вершины значений целевой переменной, имя фрейма верхнего уровня – в вершину целевой переменной, которые связываются связями type (вид), направленными от вершины целевой переменной к вершинам-зна­чениям, имена слотов преобразуются в вершины-вопросы, а значения слотов – в вершины ответы, вершины-вопросы связываются с вершинами-ответами связями type (вид). От вершин-ответов устанавливаются связи includes (включает) с вершинами значений целевой переменной в соответствии с комбинацией значений слотов во фреймах нижнего уровня ФМ. Добавляется вершина Question (Вопрос), от которой устанавливаются связи type (вид) с вершинами вопросов. Добавляется вершина Model (Модель), от которой устанавливаются связи has (имеет) с вершиной Question и вершиной целевой переменной.

Преобразование ФС в ПМ: имя каждого фрейма нижнего уровня преобразуется в значение целевой переменной, а имя фрейма верхнего уровня – в имя целевой переменной; имена слотов фреймов пре- образуются в имена переменных, с которыми связывается вопрос «Укажите, каково значение пе- ременной имя_переменной?»; значения слотов преобразуются в возможные значения переменных; присоединенные процедуры при преобразовании игнорируются; фреймы преобразуются в правила: в антецеденты попадают как имена и значения переменных, соответствующие именам и значениям слотов, тип антецедентов правил устанавливается равным нулю, в консеквенты правил заносятся для фреймов нижнего уровня – имя целевой переменной и название фрейма как ее значение; фреймы промежуточных уровней используются только для подстановки значений слотов во фреймы нижнего уровня; коэффициенты уверенности правил принимаются равными единице.

Преобразование ПМ в семантическую сеть: вопросы для переменных ПМ преобразуются в вершины СМ с соответствующими именами, ответы на вопросы переменных ПМ преобразуются в вершины СМ с соответствующими именами, вершины вопросов и вершины ответов связываются связью type (вид); каждое продукционное правило преобразуется во фрагмент СМ: создается вершина с именем переменной консеквента, к которой направляются связи includes (включает) от вершин значений переменных антецедентов, указанных в правиле. Добавляется вершина Question (Вопрос), от которой устанавливаются связи type (вид) с вершинами вопросов. Добавляется вершина Model (Модель), от которой устанавливаются связи has (имеет) с вершиной Question и вершиной целевой переменной.

Преобразование ПМ в ФС: ПМ преобразуется в СМ, которая затем преобразуется в ФС.

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

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

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

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

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

Литература

1.     Люгер Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем; [пер. с англ.]. М.: Вильямс, 2005. 864 c.

2.     Джексон П. Введение в экспертные системы. М.: Вильямс, 2001. 624 с.

3.     Субботін С.О. Подання й обробка знань у системах штучного інтелекту та підтримки прийняття рішень: навчальний посібник. Запорiжжя: Изд-во ЗНТУ, 2008. 341 с.

4.     Джарратано Д., Райли Г. Экспертные системы. Принципы разработки и программирование. М.: Вильямс, 2007. 1152 с.

5.     Liebowitz J. (Ed.) The handbook of applied expert systems. Boca Raton, CRC Press LLC, 1997, 736 p.

6.     Представление и использование знаний; [под ред. X. Уэно, М. Исидзука]. М.: Мир, 1989. 220 с.

7.     Ein-Dor P. Commonsense Knowledge Representation I. Encyclopedia of artificial intelligence. Eds. by J.R.R. Dopico, J.D. de la Calle, A.P. Sierra. Hershey: Information Science Reference, 2009, pp. 327–333.

8.     Brachman R., Levesque H. Knowledge representation and reasoning. San Francisco: Morgan Kaufmann publ., 2004, 381 p.

9.     Magrab E., Azarm S., Balachandran B. et al. An engineers guide to MATLAB. Upper Saddle River: Prentice Hall Publ., 2010, 848 p.

10.  Субботин С.А. Подсистема моделирования семантических сетей // Моделирование неравновесных систем: матер. IX Всерос. сем. (13–15 октября 2006 г., Красноярск); [под ред. В.В. Слабко]. Красноярск: Изд-во ИВМ СО РАН, 2006. С. 172–174.