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

Размещено на http://www.allbest.ru/

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



Оглавление

Введение

1. Общая часть

1.1 Анализ логики времени в пространстве в естественном языке

1.2 Методики описания ПВ-отношений

1.3 Обзор форматов представления семантической сети

2. Специальная часть

2.1 Разработка формата представления ПВ-отношений в ОА-сети

2.2 Расширение ОА-грамматики для работы с ПВ-отношениями

2.3 Разработка программного модуля анализа ПВ-отношений

2.4 Тестирование программного модуля анализа ПВ-отношений

Заключение

Список используемой литературы

Приложение А

Приложение Б

Приложение В

Приложение Г



Введение

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

ѕ автоматические системы ориентации мобильных технических объектов в пространстве;

ѕ интерфейс человек-компьютер;

ѕ системы виртуальной реальности и компьютерные игры;

ѕ системы для смыслового (семантического) анализа текста на естественном языке, ведь в тексте достаточно часто встречается описание пространственно-временных отношений.

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

В данном исследовании было применено представление и анализ ПВ-отношений с помощью семантической сети (графа), построенной по объектно-атрибутному (ОА) принципу [2]. Аналогичный подход был описан в [3], где для представления ПВ-отношения применялся формат XML, а для их анализа - ПВ-исчисление RCC. Модификация графа осуществляется с помощью аппарата графовой грамматики (граф-трансформирующей системы) [4]. Однако существующие грамматики достаточно громоздки и, самое главное, с их помощью можно описать только трансформацию структуры семантической сети, но не ее информационное содержание. Исключением является только атрибутная грамматика, разработанная Н. Хомским [5].

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

Для реализации цели были поставлены следующие задачи:

ѕ Разработка формата представлений ПВ отношений;

ѕ Анализ слов, описывающие ПВ отношения и их классификация;

ѕ Выделение типов ПВ отношений;

ѕ Выделение типов множеств;

ѕ Создание формата представления данных (конфайны);

ѕ Создание правил трансформаций;

ѕ Создание программного модуля для анализа ПВ отношений;

ѕ Тестирование программного модуля.



1. Общая часть

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

1.1 Анализ логики времени в пространстве в естественном языке

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

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

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

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

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

Иные признаки языковых средств в естественном языке:

ѕ Заполненность/незаполненность временного отрезка.

ѕ Единичность/повторяемость какого-то действия, либо временного отрезка.

ѕ Завершенность/незавершенность действия.

ѕ Одновременность/разновременность действия, либо временных отрезков.

1.2 Методики описания ПВ-отношений

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

Логическая модель

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

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

ѕ Реляционная модель

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

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

ѕ Предикативная модель

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

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

Эвристическая модель

Эвристические модели описывают структуры знаний, занимается процессом поиска решения задачи. К ней можно отнести фреймовые модели с ООП, сетевые модели и семантические сети.

ѕ Фреймовая модель и ООП

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

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

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

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

ѕ Семантическая сеть

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

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

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

Нейронные сети

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

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

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

Обзор ПВ-исчислений

Для разработки модели для описания ПВ-отношений между физическими объектами, система управления базой данных (СУБД) самым уместным способом является применение графовой модели БД (сетевой).

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

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

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

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

ОА-грамматика

ОА-грамматика представляется как граф-трансформированная система, которая обрабатывает ОА-граф.

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

Пространственно-временные исчисления и различные логики, являются одними из важных предпосылок в создании трансформационной части. Одним из таких является псевдофизическая логика, которая описана в [6] здесь приставка "псевдо" означает, что аппарат служит для описания, как определенный субъект может воспринимать физический мир, а не сама физическая действительность. Также предпосылками создания были интервальная алгебра Алена [15], дельта-исчисление [16], исчисление пересечения областей [17] и т.п. Идея, что новую информацию о пространстве-времени можно получать с помощью применения преобразующий правил и определенных порождающих из уже имеющихся, была позаимствована из пространственно-временных исчислений. В случае с АО-грамматикой, будут применяться правила преобразования семантической сети. В действительности, ОА-грамматика представляет из себя граф-трансформирующую систему, которая обрабатывает ОА-граф. В ОА-грамматике присутствует четыре главных компонента: OAG={A,L,P,G}, где A - алфавит атрибутов ИП; L - алфавит нагрузок ИП (в этот алфавит входят не только числа и строки, но и ссылки (индексы) на ИК); G - первоначальный ОА-граф; P - правила преобразования ОА-графа.[2]

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

a = l - обозначение IP, где a?A, l?L (A - это множество атрибутов, L - это множество нагрузок ИП);

Name{…} - это ИК, где между фигурных скобок записываются обозначения ИП, которые входят в ИК), Name - это имя, которое заменят индекс ИК;

{… a= NameIC{Ip1,Ip2…} …} - это ИП, здесь в нагрузке находится указатель на ИК, NameIC - это имя ИК, оно может и не указываться;

* - это конкатенация ИК;

' - удаление первой или последней ИП из IC;

F - выделение первой ИП в ИК;

L - выделение последней ИП в ИК;

1.3 Обзор форматов представления семантической сети

Первоначально необходимо определиться с форматом представления связей семантической сети, для этого вначале рассмотрим по отдельности форматы XML, RDF, JSON и ОА-подход. После этого произведем сравнение по критериям и выберем лучший формат.

XML

XML - это язык разметки документов, производный от SGML, расшифровывается как Extensible Markup Language. Он позволяет структурировать информацию разных типов, при этом он использует инструкции произвольного набора [18].

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

Теперь рассмотрим физические и логические структуры данных.

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

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

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

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

Главное преимущество XML в том, что в данном языке нет предопределенных тегов, программист сам определяет свои теги и структуру документа, нежеле в HTML, где можно использовать только те теги, которые определены в стандартах (например, <li>,<p>,<br> и т.д.). В XML можно выделять фрагменты внутри документа, а не только разделять его на абзацы и заголовки. Для эффективности можно определять перечень всех своих элементов в описании типа документа или в схеме и придерживаться его.

В XML вначале обязательно вводить объявление, в котором должны указываться версия и кодировка (стандартом является Unicode), например: <?xml version="1.1" encoding="UTF-8" ?>.

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

= RDF

Resource Description Framework(RDF) -- это язык для описания ресурсов, знаний, который был разработан консорциумом W3C [19].

В RDF можно выделить три правила:

1. Факты, похожие на простое предложение в естественном языке, выражаются в виде тройки: подлежащее, сказуемое и дополнение.

2. Данная тройка - это имена конкретных или абстрактных сущностей реального времени. Имя может быть глобальным и локальным. Если имя глобальное, то оно ссылается во всех RDF документах на одну и ту же сущность, где оно используется. Во втором случае, на сущность нельзя ссылается из-за пределов документа, только на ту сущность, на которую может ссылаться это имя.

3. Литералы - это дополнения, которые текстовые строки.

RDF содержит тройки данных: объект-предикат-субъект, которые называется триплетом (рис.1.). Например, утверждение "вода прозрачного цвета" будет иметь следующий вид: субъект - вода, предикат - имеет цвет, объект - прозрачный. RDF использует URI для описания субъектов, объектов и отношений.

Рис. 1. "Триплет RDF"

Ориентированный граф, где вершины - это субъекты и объекты, а ребра показывают отношения, образует множество RDF утверждений.

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

Для наглядности ниже приведен простой пример кода на языке RDF, где говорится, что у Марии есть мать, которую зовут Екатерина, отец Александр и у Александра есть сестра по имени Линда:

@prefix : <https://www.exemple.ru>.

:john a :Maria .

:john :hasMother :Ekaterina.

:john :hasFather :Alexander.

:Alexander :hasSister :Linda.

Благодаря @prefix мы используем глобальное имена сущностей, в данном случае это: john, hasMother, hasFather, hasSister. Данные имена имеют один и тот же смысл во всех документах со значением @prefix.

RDF не затрагивает семантики описываемого, он предоставляет средства, чтобы построить информационную модель. Граф, взятый в отдельности, можно воспринимать в RDF только как граф. Формат способен разъяснять отдельные URI, структуру графа и строковые литералы, и только по ним потом интерпретировать семантику данных и остальные URI.

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

JSON

JSON (JavaScript Object Notation) - это простой формат для обмена данными, он удобен для чтения, а также для написания и человеку, и компьютеру. JSON основан от языка программирования JavaScript, это текстовый формат, который использует соглашения Си подобных языков программирования, например Си, Си#, Си++, Python, JavaScript и т.п. [ 21].

JSON может использовать две универсальные структуры (в закодированном виде), они легли в основу языка, потому что JSON используется для обмена данными между разными языками программирования:

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

ѕ Упорядоченный набор значений, реализовано с помощью массива, вектора, списка иди последовательности.

В JSON в качестве значений могут быть использованы следующие определения:

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

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

ѕ Литералы могут принимать три значения: true, false или null.

ѕ Число, используется только десятичный формат данных.

ѕ Строка - упорядоченное множество из символов Unicode, заключается в двойные кавычки. Она похожа на тот одноименный тип данных, который используется в C и Java.

Ниже приведен наглядный пример, описывающий данные человека, имя, фамилия, адрес проживания и номер телефона, в данном примере значение представляет из себя вложенную структуру [22]:

{

"firstName": "Евгения",

"lastName": "Сидорова",

"address": {

"city": "Москва",

"streetAddress": "Лубянский проезд, дом 1",

},

"phoneNumbers": [

"8 915 123 45 67",

"8 495 987 65 43"

]

}

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

ѕ JSON5 - разрешение, поддерживаемое синтаксис ECMAScript 5. Формат JSON5 поддерживает однострочные и многострочные комментарии (// и /*...*/), для удобного копирования, списки и объекты могут иметь запятую только после последнего элемента, если ключи объекта являются валидными идентификаторами синтаксиса ECMAScript 5, то они могут писаться без кавычек, заключаться строки могут и в одинарные кавычки, и в двойные. Числа могут включать в себя Infinity, -Infinity, NaN и -NaN, также они могут быть в шестнадцатеричном виде и начинаться со знака плюс (+). Некоторые языки программирования имеют парсеры JSON5.

ѕ JSON Schema - это язык описания структуры JSON документа, который использует синтаксис JSON. Данный язык базируется на следующих концепциях: XML Schema, Kwalify, RelaxNG. Это самоописательный язык, если его использовать для описания и обработки данных, то могут использоваться одинаковые инструменты сериализации и десериализации.

ѕ JSON-LD разработал W3C, он используется для передачи связанных данных, при помощи формата JSON. При использовании JSON-LD, облегчается структурирование данных и распознавание понятий. Данные, которые размечены с помощью данного формата, легко распознаются поисковыми системами. Он структурирует информации, при этом не вмешиваясь в контент, который отображается пользователям. Разметка представлена в виде мета-данных, которые упакованы в контейнере <head> в тег <script>. Формат JSON-LD поддерживает семантику.

ОА-подход

Объектно-атрибутный подход был разработан авторами [1].

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

В объектно-атрибутный (ОА) подход, авторами [1] были выделены следующие понятия:

"Информационная пара (ИП) (атрибутированные данные) - совокупность нагрузки (данных или ссылки на данные), и ярлыка/атрибута (уникального идентификатора), описывающего нагрузку.

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

Милликоманда (мК) - это ИП, где ярлык указывает устройству (ФУ), каким образом следует обрабатывать прикрепленные к нему данные.

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

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

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

Рис.2. "Работа вычислительной системы с ОА-деревом абстракций"

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

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

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

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

Разработанная авторами [2] архитектура, полностью поддерживает принцип изоморфизма, так как любую процедуру можно реализовать с помощью ФУ. Модификация ФУ состоит из расширения набора милликоманд и изменения в количестве операндов и последовательности их передачи для ФУ влиять критически на ОА-программу не будет.

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

Для описания преобразования ОА-графа, которые применяются для вывода новых ПВ-отношений применяется нотация ОА-грамматики [23].

Основные обозначения нотации в АО-грамматике:

ѕ ">" или ">-" - замена одного фрагмента ОА-графа на другой, слева ОА-граф, который необходимо заменить на другой фрагмент ОА-графа, который справа;

ѕ ">+" - добавление ОА-графа, слева ОА-граф, который необходимо преобразовать, справа преобразованный ОА-граф, обычно используется при модификации семантического графа;

ѕ :: - добавленная конструкция;

ѕ = - ИП, где слева находится мнемоника атрибута, а справа нагрузка;

ѕ {...} - ОА-капсула;

ѕ Point{...}, где oint - это указатель на капсулу, описанную после мнемоники Point;

ѕ Atr = Const/Point, где Const - константа, которая хранится в нагрузке ИП и может быть числовой, логической, символом или строкой символов, а Point - указатель, который хранится в ИП;

ѕ * - сцепление двух ИК (конкатенация);

ѕ Atr=*{} - конкатенация к ИК из нагрузки ИП;

ѕ #Point - копирование ИК, куда указывает Point;

ѕ F/L Point - первая/последняя ИП в капсуле по адресу Point;

ѕ 'Point - удаление из ИК первой ИП по адресу Point;

ѕ Point' - удаление из ИК последней ИП по адресу Point;

ѕ {…} {…} - операция перечисления;

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

ѕ ( ) - знак старшинства операций (например операция альтернатив имеет меньший приоритет, чем перечисление ИП, и чтобы можно было изменить приоритет, используется знак (,));

ѕ [...] - если в данных скобках описан ОА-граф, то он может не присутствовать в списке или только один раз присутствовать.

Сейчас, с помощью ОА-подхода, разработана методика поискового поиска. Пользователь отправляет запрос на естественном языке, он преобразуется в ОА-граф, потом в базе данных (БД) осуществляется поиск подграфа, который совпадает с графом запроса. Совпадение происходит, если топологии графа запроса и подграфа из БД идентичны, при этом множества ИП, которые расположены в узлах графа запроса, обязаны быть подмножествами подобающих множеств подграфа БД в узлах [23].

Сравнение форматов представления семантической сети

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

Первоначально рассмотрим структуры и гибкость построения таких форматов, как XML, RDF, JSON и ОА-язык.

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

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

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

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

Если сравнивать данные форматы на простоту описания и объемность кода, то XML проигрывает сразу в двух критериях, его код имеет существенно больший размер по сравнению с остальными форматами и достаточно трудно воспринимается. RDF имеет меньший размер кода и легче воспринимается, но тоже проигрывает форматам JSON и ОА-языку.

Далее рассмотрим форматы на возможность отражения семантики.

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

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

JSON является наиболее близким к ОА-языку. Текстовый формат языка облегчает обмен между языками программирования структурированными данными.

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

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

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

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



2. Специальная часть

Разработку программного модуля анализа ПВ-отношений можно разделить на несколько этапов.

Первый - разработка формата представления ПВ-отношений в виде семантической сети.

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

Третий - реализация программного модуля анализа ПВ-отношений.

2.1 Разработка формата представления ПВ-отношений в ОА-сети

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

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

Выделение типов конфайнов

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

1. Расстояние между объектами (с относительной метрикой): "далеко", "в отдалении", "вблизи", "рядом", "возле", "у", "около" и т.д.;

2. Расстояние между объектами (с точной метрикой): "в 10 метрах";

3. Интервал времени между событиями (с относительной метрикой) "скоро", "быстро", "незадолго" и т.д.;

4. Интервал времени между событиями (с точной метрикой) "через 10 минут", "за 2 часа до" и т.д.;

5. Локация (взаимное расположение объектов без метрики): "в", "вне", "через" и т.д.;

6. Направление (задается точка начала координат и используется полярная система координат):

6.1. На плоскости: "справа", "слева", "вперед", "назад", "обратно" и т.д.;

6.2. В пространстве: "вверху", "внизу" и т.д.;

7. Последовательность (объекты или явления, которые можно упорядочить в пространстве и/или времени):

7.1. Пространственная: "между", "перед", "после", "дальше", "за" и т.д.;

7.2. Временная: "сначала…" "потом", "перед тем как..."

7.3. Пространственно-временные (траектория): описание движения объекта в пространстве-времени ("Днем он был в деревне, а вечером - в городе.");

7.4. Индексированное множество: "первый", "второй" и т.д., "во-первых", "во-вторых" и т.д.;

7.5. Осевая нить (может иметь прямолинейную или криволинейную ось, которая определяет пространственное расположение объектов): "параллельно", "поперек", "Река течет вдоль леса" и т.д.;

7.6. Причинно-следственные: "если..то";

8. Цикличность (описание циклических действий):

8.1. Пространственная ("через километр", "каждые 2 метра");

8.2. Временная ("ежечасно", "ежесекундно", "единожды", "ежеквартально" и т.д.);

9. Период (описание периода или цикла во времени или пространстве): "круглосуточно", "круглогодично", "опять", "периодически" и т.д;

10. Скорость (описание скорости по времени или в пространстве): "неторопливо", "потихонечку", "скоро", "быстро" быстрее", "в паре шагах от дома" и т.д.;

11. Контакт (указывается наличие контакта с объектами): "по", "на" и т.д.

Выделение типов множеств объектов или явлений

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

ѕ Неупорядоченное множество: Set (от англ. "Set" - "набор");

ѕ Упорядоченное множество: OSet (от англ. "Order Set" - "упорядоченный набор");

ѕ Упорядоченное множество в обратном порядке: RSet(от англ. "Reverse Set" - "обратный набор");

ѕ Упорядоченное множество в обоих направлениях: ToFSet(от англ. "to and from" - "туда и обратно");

ѕ Неполное упорядоченное множество, т.е. возможно, что некоторые элементы присутствуют в множестве, но их описания нет: ONFSet (от англ. "Order Not Full Set" - "неполный упорядоченный набор");

ѕ Неполное неупорядоченное множество: NFSet(от англ. "Not Full Set" - "неполный набор");

ѕ Индексированное множество, т.е. каждый элемент имеет свой уникальным номер: IndSet (от англ. "Index" - "индекс");

ѕ Последовательные индексы, т.е. множество в котором элементы проиндексированы подряд идущими номерами: StrictIndSet (от англ. "Strict Index" - "строгий индекс");

ѕ Подмножество: SubSet;

ѕ Типичный представитель множества: Templ;

ѕ Типичный представитель подмножества: TemplSubSet;

ѕ Множество "ИЛИ", т.е. в действительности присутствуют один или несколько объектов: OrSet (от англ. "Or" - "или");

ѕ Множество "И" (в действительности присутствуют все объекты из множества): AndSet (от англ. "And" - "и");

ѕ Множество "Исключающее ИЛИ", т.е. в действительности присутствует только один объект из множества): XorSet (Xor - это операция, которая сможет принять значение "истина" только только в том случае, если всего один из аргументов будет иметь значение "истина");

ѕ Исключение т.е. элементы, не входящие в множество: Excl (от англ. "Exclude" - "исключение") - например, "Все кроме маленьких детей…".

Также ниже указаны основные типы конфайнов (LType) вместе с пояснением:

ѕ Distance - используется для описания дистанции и расстояния;

ѕ Location - используется для определения местонахождения;

ѕ OderingTime - упорядоченная последовательность во времени;

ѕ OderingSpace - упорядоченная последовательность в пространстве;

ѕ Time - используется для описания времени;

ѕ TimeSet - последовательность точек во времени;

ѕ Cause - для описания причинно-следственных связей;

ѕ PlaceSet - последовательность точек в пространстве;

ѕ TimeSimultaneity - параллельность по времени;

ѕ Topology- используется для описания топологии;

ѕ Direction - используется для описания направления;

ѕ DistanceRelative - субъективное описание расстояния;

ѕ TimeRalative - субъективное описание времени;

ѕ Above, in, under и т.п. - сверху, в, под и т.п. предлоги.

Для ясности использования множеств приведем несколько примеров. Например, если у нас расположены элементы по порядку, то они будут иметь множество "ToFSet", так как элементы будут иметь упорядоченное расположение в двух направлениях. А если у нас будет использоваться выбор из нескольких элементов, например "кошка или собака", то мы будем использовать множество "или" - "OrSet". При сравнении множеств "OSubset" учитывает порядок элементов в множестве, при этом, данные точки должны идти строго подряд.

Разработка формата описания конафайна

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

Рис. 3. "Формат семантической сети для представления ПВ-отношений"

Каждая вершина ОА-графа принадлежит одному из указанных в рисунке уровней. Для описания пространственно-временных отношений в формате выделен специальный уровень, который состоит из четырех подуровней. Непосредственно конфайны описываются на двух последних подуровнях, два верхних подуровня необходимы для того, чтобы задавать множества конфайнов; например, "Вода потекла из ванной в коридор и на кухню". В данном предложении два конфайна "коридор" и "кухня", и они объединяются в множество тип "И", т.е. объект ("вода") занимает сразу два конфайна.

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

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

Далее приведем примеры описания информационных конструкций семантической сети для описания некоторых классов ПВ-отношений.

Далее приведем форматы выделенных типов конфайнов:

1. Расстояние (Рис.4)

{Set={..} LType=Distance{...}}

Рис.4. "Конфайн "расстояние"

Где свойства "Contact" может быть только два состояния - "true" или "false", "Set" означает неупорядоченное множество, а "LType" - это тип, в данном конфайне используется тип "Distance", который используется для описания дистанций и расстояний. После описания типов конфайнов будут описаны основные типы функций.

...