ТЕМПОРАЛЬНЫЕ ОТНОШЕНИЯ МЕЖДУ СОБЫТИЯМИ В МОДЕЛЯХ, ПРЕДСТАВЛЕННЫХ СЕМАНТИЧЕСКИМИ ГИПЕРГРАФАМИ - Студенческий научный форум

V Международная студенческая научная конференция Студенческий научный форум - 2013

ТЕМПОРАЛЬНЫЕ ОТНОШЕНИЯ МЕЖДУ СОБЫТИЯМИ В МОДЕЛЯХ, ПРЕДСТАВЛЕННЫХ СЕМАНТИЧЕСКИМИ ГИПЕРГРАФАМИ

Починский И.А. 1
1Пензенский Государственный Университет
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение

В работах [5] [8] был исследован семантический гиперграф как формализм представления декларативных знаний. Но существуют свойства знаний [3], которые невозможно [6] [7] описать только с помощью языков представления декларативных знаний:

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

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

  3. Активность (не только появление в базе фактов или описаний каких-либо событий, но и установление новых связей и даже сам факт изменения знаний может стать источником активности ИСУЗ).

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

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

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

Концепция событийного управления изменением семантики системы

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

Изменение семантики моделируемой системы производится вследствие последовательности событий, происходящих в ней, формально событие записывается как следующий класс (используется представление с помощью объектно-ориентированных семантических гиперграфов [7] [8]):

Свойства id и evID используются для идентификации вершины: первое – глобально в пределах гиперграфа, второе – в пределах класса event.

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

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

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

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

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

.

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

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

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

– ядро продукции в классическом его понимании: из истинности A следует истинность B1, из ложности A следует истинность B2. Другими словами ЕСЛИ A, то B1, ИНАЧЕ B2. В качестве B1 и B2 могут использоваться как атомарные операции (например, удаление/создание вершины или семантической дуги), так и комплексные действия, модифицирующие большие фрагменты гиперграфа.

Q – постусловие продукции, которое актуализируется только после выполнения ее ядра (независимо от того, было выполнено действие B1 или B2).

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

Ex – условие, при истинности которого ядро продукции активизировано не будет. Может являться конкретизацией условия применимости ядра продукции.

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

Представление темпоральных отношений между событиями в ретроспективе объектно-ориентированных семантических гиперграфов

Выделяют 4 основных подхода к представлению темпоральных отношений:

  • Пространство состояний.

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

Системы, использующие такой подход неудобны, главным образом, из-за оперирования только текущим состоянием модели [9].

  • Системы, основанные на датах.

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

Данный подход неудобен из-за представления событий стянутыми во временном пространстве в одну точку (т.е. момент начала события и момент его окончания совпадают), в следствие чего такие системы не могут представить факты вроде «событие A не пересекается с событием B».

  • Цепочки до/после.

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

  • Темпоральные сети Петри.

Аппарат темпоральных сетей Петри предполагает работу с количественными временными зависимостями, однако ясно, что выразительность представления увеличится при наличии средств, позволяющих выражать как количественные, так и качественные временные зависимости. Поэтому для эффективного использования этого аппарата в составе ИСУЗ необходимо решить задачу представления и оперирования качественными временными зависимостями. Хоть решением этой задачи и занимаются некоторые ученые [1] [2] [10] 11], но до сих пор универсального решения не представлено.

Аллен выделяет [9] четыре основные характеристики темпоральных отношений, которые должны поддерживаться моделью:

  • должны поддерживаться как строгие (количественные), так и нестрогие (качественные) отношения;

  • должна поддерживаться неполная и неточная информация (могут, например, быть известны ограничения, накладываемые на отношения, но сами отношения оставаться неизвестными);

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

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

Дополнив эти характеристики предложенными в [4] логико-темпоральными концептами знаний, можно получить перечень ключевых свойств, которыми должна обладать модель для адекватного и семантически полного представления темпоральных отношений:

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

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

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

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

В качестве одного из возможных путей решения задачи представления логико-темпоральных отношений в модели, представленной объектно-ориентированным семантическим гиперграфом, предлагается использовать интервальную логику Аллена [9], которая характеризуется достаточной выразительностью и наличием полиномиальных алгоритмов вывода, что позволяет использовать ее в ИСУЗ.

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

Количественные темпоральные отношения при этом удобно представить как свойства экземпляра класса event. Выше была обоснована семантическая несостоятельность систем с поддержкой точечных темпоральных отношений, поэтому необходимо предусмотреть возможность определения моментов начала и окончания события, а также единиц измерения времени. Для этого будут использованы свойства starts:timeDate, lasts:timeDuration и measures:timeMetric, описывающие момент начала события, его длительность и единицы измерения времени соответственно.

Аллен определил 13 темпоральных отношений (6 основных + их инверсии, а также отношение полного совпадения), которые необходимо реализовать в ИСУЗ:

  • equals;

  • before;

  • meets;

  • overlaps;

  • during;

  • starts;

  • finishes.

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

Рисунок 1

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

Поддержка представления неполной информации о темпоральных отношениях решается с помощью предикатных выражений в составе ядер продукционных правил, например, представить фразу «события s1 и s2 начались с интервалом в k» можно следующим способом:

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

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

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

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

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

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

  1. отсутствие доступа к СПД;

  2. звонок в ТП;

  3. проверка соединения модема и сплиттера;

  4. проверка соединения модема и ПК;

  5. проверка подключения модема к сети 220V;

  6. проверка подключения ПК к сети 220V;

  7. проверка конфигурации ПК;

  8. проверка конфигурации модема;

  9. оформление заявки на выезд;

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

Рисунок 2

Рисунок 3

Вывод

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

Литература

  1. Еремеев А.П., Королев Ю.И. Средства моделирования на основе темпоральных сетей Петри для интеллектуальных систем поддержки принятия решений // Труды XIII Национальной конференции по искусственному интеллекту с международным участием. – Белгород, 2012.

  2. Ефимов М. И., Желтов В. П. Нечеткие временные сети Петри // Современные наукоемкие технологии. – 2004. – № 5 – С. 90-90.

  3. Искусственный интеллект. Справочник в трех томах / Под ред. Захарова В.Н., Попова Э.В., Поспелова Д.А., Хорошевского В.Ф. . М.: Радио и связь, 1990.

  4. Ковалев С.М. Модели представления и поиска нечетких темпоральных знаний в базах временных рядов // Труды XI Национальной конференции по искусственному интеллекту с международным участием. – Дубна, 2008.

  5. Починский И.А. Использование гиперграфов для представления онтологии сетевого оборудования. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей XI Междунар. научно-техн. конф. – Пенза: ПДЗ, 2011. – с. 74-78.

  6. Починский И.А. Продукционные правила в качестве средства формализации семантического гиперграфа. / И.А. Починский // Университетское образование: Сб. статей XVI Междунар. научно-метод. конф. – Пенза: Изд-во ПГУ, 2012. – с. 443-445.

  7. Починский И.А. Проектирование онтологии сети передачи данных на основе формализма семантических гиперграфов // Труды Всероссийского конкурса научно-исследовательских работ студентов и аспирантов в области технических наук : материалы работ победителей и лауреатов конкурса. – СПб. : Изд-во Политехн. ун-та, 2012. – С. 139-141.

  8. Починский И.А. Формальное представление семантических гиперграфов и операций над ними. // Молодежь. Наука. Инновации: Труды V междунар. научно-практ. интернет-конференции / Под ред. Г.К. Сафаралиева, А.Н. Андреева, В.А. Казакова – Пенза: Изд-во Пензенского филиала ФГБОУ ВПО «РГУИТП», 2012. – с. 373-377.

  9. J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26 (11):832-843, 1983.

  10. Murata, M., "Temporal Uncertainty and Fuzzy-Timing High-Level Petri Nets," Invited paper at the 17th International Conference on Application and Theory of Petri Nets, Osaka, Japan, LNCS Vol. 1091, pp. 11-28. 1996.

  11. Szpyrka M., Szmuc T. Integrated approach to modelling and analysis using RTCPnets // IFIP International Federation for Information Processing, vol. 227, New York, 2006.

Просмотров работы: 3463