Название проекта Формальные языки и методы спецификации, анализа и синтеза информационных систем

1. Номер проекта

14/12
2. Название проекта

Формальные языки и методы спецификации, анализа и синтеза информационных систем
3. Головная организация

Учреждение Российской академии наук Институт систем информатики им. А.П. Ершова Сибирского отделения РАН (ИСИ СО РАН)
4. Руководитель проекта

Марчук Александр Гурьевич
5. Цель и задачи проекта

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

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

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

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

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

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

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

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

Концепция портала знаний о компьютерных языках и его демонстрационная версия были представлены на Ершовской конференции по информатике PSI-2011. Надо сказать, что PSI – это один из главных форумов России, посвященных исследованиям и приложениям в таких областях информатики, ранее известный как Международная конференция памяти академика А.П. Ершова «Перспективы систем информатики».

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

Введено понятие относительной интерпретации (семантики) формы — функции, которая определяет, как интерпретируется форма относительно некоторой другой формы. Введено понятие функциональности, дополняющее понятие относительной семантики. Множество форм, являющихся функциональностями некоторой формы, определяют ее «интерфейс».

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

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

Выделены два новых класса предметно-ориентированных ИС.

Первый класс составляют информационно-онтологические модели языков программирования (ИОМЯП), базирующиеся на новом методе информационно-онтологического моделирования языков программирования. Второй класс составляют информационно-аналитические системы, описывающие различные трансформации ИОМЯП.

По фактографическому направлению проекта программы РАН за 2011 год были получены следующие результаты. Исследована возможность применения фактографических формализаций для изучения профессионально-образовательного социума. Задача решалась применительно к выпускникам и преподавателям Механико-математического факультета НГУ. Цель исследования – изучение профессионального пути выпускников ММФ за 50 лет деятельности факультета. Была построена полная база данных выпускников факультета по университетским выпускным приказам с фиксацией года выпуска и группы. Всего выпускников оказалось чуть меньше 10 тысяч. К этой базе данных была добавлена информация о преподавателях и сотрудниках СО РАН, работающих в математических институтах. К сожалению, база данных о преподавателях не полна, особенно в части давних лет. Была сделана попытка выявить информацию о выпускниках через наиболее популярные социальные сети. Удалось более или менее надежно установить около 2.500 выпускников. Использование полученной информации наткнулось на юридические ограничения по использованию данных социальных сетей. Был организован юбилейный сайт факультета, где также имелись части, связанные с исследованием, в частности, уточнялись текущие фамилии выпускников и в анонимной форме собиралась информация о настоящем месте их жизни. Получена информация приблизительно от 2 тысяч выпускников. Кроме того, были обработаны несколько коллекций фото, аудио и видео материалов, предоставленные активными выпускниками. Поскольку фотодокументы обрабатывались на предмет выявления персонажей, это также добавляет информацию в граф связей сформированной сети. Сделаны первичные выводы по цели исследования, работы продолжаются.

Создан технологический комплекс создания и ведения электронных фактографических архивов. Автоматизирована вся цепочка работ от обработки первичных документов и их аннотации, до публикации в виде сайтового решения. Ключевыми элементами технологии являются: кассетный механизм для накапливания документов и данных; сервис данных, обеспечивающий интеграцию информационных систем в распределенной конфигурации, в частности, использование CMS. Технологический комплекс был использован для проектов «Фотоархив СО РАН», «Энциклопедия ММФ», «Летние школы юных программистов». Существенно новым слоем технологического комплекса является применение технологии DeepZoom. Эта технология дает возможность удобно просматривать большие и очень большие растровые изображения и сборки таких изображений. С использованием DeepZoom был порожден интерфейс к сканированным страницам подборки газеты «Наука в Сибири» (ранее – «За науку в Сибири») выпусков с 1961 по 1997 годы. В настоящее время готовится технология аннотирования газетных статей с интеграцией средств работы с базой данных со средствами просмотра размеченных или аннотированных номеров газеты.

В 2011 году работа по визуализации информации была ориентирована на исследование применимости разработанных ранее методов визуализации к данным большого объема. В качестве тестовых данных использовались информационные наполнения порталов из множества Linked Open Data (ACM, DBLP, CiteSeer). Из контента этих порталов извлекались данные о публикациях и генерировались сети соавторства и сети цитирования. Затем сгенерированные сети визуализировались при помощи ранее реализованных алгоритмов. В результате этих экспериментов было обнаружено, что реализованный ранее метод иерархических жгутов ребер не всегда хорошо справляется с визуализацией сетей цитирования большого объема и возникла необходимость в разработке более развитых алгоритмов для визуализации таких сетей.

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

Методы реинжиниринга онтологий были исследованы на примере переноса уже разработанной нами онтологии портала знаний по компьютерной лингвистике на язык OWL-DL, для последующего ее использования в приложениях, построенных на технологии Semantic Web. Так как онтология портала знаний хранится в реляционной базе данных специального вида, была разработан методы реинжиниринга, включающий три этапа: (1) отображение онтологии из реляционной БД в высокоуровневый формализм онтологии представления (получение концептуальной модели), (2) анализ и улучшение полученной концептуальной модели, (3) отображение онтологии, представленной в указанном формализме, в онтологию на языке OWL-DL.

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

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

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

В 2011 году предложен подход к построению информационных Wiki-систем на основе онтологий предметных областей, который обеспечивает построение Wiki-систем с согласованной системой понятий. Исследованы методы реинжиниринга онтологий на примере переноса уже разработанной нами онтологии портала знаний по компьютерной лингвистике на язык OWL-DL, для последующего ее использования в приложениях, построенных на технологии Semantic Web.

В 2011 году проводились прикладные исследования проблем, связанных со спамом. Исследования посвящены разработке алгоритмов идентификации спам сообщений и пользователей, осуществляющих рассылку спам сообщений. Рассмотрена модель вероятностной идентификации спама, на основе Марковских цепей. Модель была протестирована на приблизительно 200 тыс. экземплярах спам сообщений. Предложены алгоритмы идентификации т.н. спам ботов на основе имен пользователей и наименований почтовых ящиков и др. информации, имеющейся в компании, предоставляющей почтовые сервисы. А именно, рассмотрены вероятностные, энтропийные, лингвистические и логические критерии классификации имен пользователей, дат созданий почтовых ящиков и прочих атрибутов почтовых ящиков. В настоящее время алгоритмы тестируются на массиве данных, содержащих информацию об около 1 млн. 900 тыс. пользователей.

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

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

Анализ комплексных данных на основе технологии Oracle BI. Целью данной работы является дальнейшее развитие системы анализа комплексных данных (data-mining) на основе технологии Oracle BI применительно к интеллектуальным системам управления, основанным на применении бизнес-процессов. В настоящее время подготовлена к публикации книга по данной теме.
7. Возможное практическое использование результатов

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

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

Разработанный технологический комплекс создания и ведения электронных фактографических архивов может применяться для автоматизации всей цепочки работ от обработки первичных документов и их аннотации, до публикации в виде сайтового решения. Ключевыми элементами технологии являются: кассетный механизм для накапливания документов и данных; сервис данных, обеспечивающий интеграцию информационных систем в распределенной конфигурации. Технологический комплекс был использован для проектов «Фотоархив СО РАН», «Энциклопедия ММФ», «Летние школы юных программистов» и др.

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

В одном из больших региональных банков Урала была разработана модель, в которой данные из программы операционного дня банка (ЦФТ IBSO) и программы обработки транзакций по картам VISA складываются в одну базу примерно 1 раз в час и в дальнейшем подвергаются анализу. Эта модель была расширена модулем обработки бизнес-процессов. В дальнейшем планируется внедрить технологию работы с бизнес-процессами в несколько предприятий малого и среднего бизнеса для проведения тестовых испытаний.

Разработанные алгоритмы на базе системы Link Grammar Parser, которые, проникая в структуру текста, могут выводить достаточно адекватную оценку релевантности (адекватности) текста поисковому запросу, не ограничивающиеся только ключевыми словами, их близостью или частотой, могут использоваться различными организациями и отдельными пользователями, осуществляющими регулярный поиск в сети различного рода информации: технологической, новостной, политической и социально-экономической, военной и др.
8. Публикации

Всего за 2009-2010 годы (т.е. за первые 2 года) по проекту было опубликовано 56 научных работ, в 2011 году опубликовано 30 печатных работ, среди них:

Монографии

Ануреев И.С., Батура Т.В., Боровикова О.И., Загорулько Ю.А., Кононенко И.С., Марчук А.Г., Марчук П.А., Мурзин Ф.А., Сидорова Е.А., Шилов Н.В. Модели и методы построения информационных систем, основанных на формальных, логических и лингвистических подходах / Отв. ред. А.Г. Марчук ; Рос. акад. наук, Сиб. отд-ние, Ин-т систем информатики им. А.П. Ершова. – Новосибирск: Изд-во СО РАН, 2009. ISBN 978–5–7692–1113–3. – 330 с.

Батура Т.В., Мурзин Ф.А. Машинно-ориентированные логические методы отображения семантики текста на естественном языке// Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. – Новосибирск: Изд. НГТУ, ISBN 978-5-7782-1138-4, 2008. – 248с. (вышла из печати в 2009-м году).

Семич Д.Ф. Построение хранилища данных ORACLE Business Intelligence (Siebel Analytics) // Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. – Новосибирск: Изд-во СО РАН, 2010. ISBN будет получен. – 160 с. (находится в редподготовке, выйдет из печати в 2011-м году).
Прочие наиболее важные публикации публикации
Бодин Е.В., Гаранина Н.О., Шилов Н.В. Задача о роботах на Марсе (мультиагентный подход к задаче Дейкстры). Моделирование и анализ информационных систем, №2, 2011, стр.111-126.

Anureev I.S. The Atoment Language by Examples // Second Workshop on Program Semantics, Specification and Verification: Theory and Applications (PSSV 2011), Saint-Petersburg, 2011. – P. 1-9.

Fomin D.V., Anureev I.S. Attribute Annotation Method for VCG Simplification // Second Workshop on Program Semantics, Specification and Verification: Theory and Applications (PSSV 2011), Saint-Petersburg, 2011. – P. 35-42.

Марчук А.Г., Марчук П.А. Архивная фактографическая система // Электронные библиотеки: Перспективные методы и технологии, электронные коллекции. Труды XI Всероссийской научной конференции (RCDL-2009), Петрозаводск, 2009 г., -С. 177-185.

Марчук А.Г., Марчук П.А. Особенности построения цифровых библиотек со связанным контентом // Электронные библиотеки: перспективные методы и технологии, электронные коллекции. Труды XII Всероссийской научной конференции RCDL'2010; Казань, Россия 13-17 октября 2010 г. - Казань: Казан. ун-т, 2010. С. 19-23.

Апанович З.В., Винокуров П.С., Кислицина Т.А. Средства Визуального анализа Информационного наполнения порталов, входящих в облако Linked OpenData // Труды 13-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» - RCDL’2011, Воронеж, Россия, 2011.—C. 216-223.

Апанович З.В., Винокуров П.С., Кислицина Т.А. Методы и средства визуализации информационного наполнения больших научных порталов // Вестник НГУ Серия: Информационные технологии, 2011. – том 9, выпуск 3 –с. 5-14.

Загорулько Ю.А. Подход к построению интеллектуальных информационных систем на основе семантических сетей // Международная научно-техническая конференция «Открытые семантические технологии проектирования интеллектуальных систем» (OSTIS-2011) / под ред. В.В. Голенкова. – Минск: БГУИР, 2011. –С. 15-20.

Ю.А.Загорулько, Г.Б. Загорулько Использование онтологий в экспертных системах и системах поддержки принятия решений // Труды Второго симпозиума «Онтологическое моделирование» (Казань, октябрь 2010 г.),. Москва: ИПИ РАН, 2011. -С.321-351.

Yury A. Zagorulko. On Experience of Building Knowledge Portals on Humanities // First Russia and Pacific Conference on Computer Technology and Applications, 6-9 September, 2010, Vladivostok, Russia. –P.336-339.

Yury Zagorulko, Olesya Borovikova, Galina Zagorulko. Knowledge Portal on Computational Linguistics: Content-Based Multilingual Access to Linguistic Information Resources // Selected topics in Applied Computer Science. Proceedings of the 10th WSEAS International Conference on Applied Computer Science (ACS’10). Hamido Fujita, Jun Sasaki (Eds.). (Iwate Prefectural University, Japan, October 4-6, 2010). – WSEAS Press, 2010. –P.255-262.

Yury Zagorulko, Galina Zagorulko. Architecture of Extensible Tools for Development of Intelligent Decision Support Systems // New Trends in Software Methodologies, Tools and Techniques. Proceedings of the Tenth SoMeT_11. Hamido Fujita and Tatiana Gavrilova (Eds.) –IOS Press, -Amsterdam,. –2011. –P.253-263.

Batura Tatiana, Murzin Feodor, Proskuryakov Alexey, Trelevich Some Approaches to Detection of Spam and Senders of Spam // Восьмая междунар. конф. памяти акад. А.П. Ершова, “Перспективы систем информатики”, Рабочий семинар “Наукоемкое программное обеспечение”, Новосибирск 2011. – С. 1–6.

Перфильев А.А., Мурзин Ф.А. Методы синтаксического анализа и сопоставления конструкций естественного языкаи их использование в поисковых системах // Восьмая междунар. конф. памяти акад. А.П. Ершова, “Перспективы систем информатики”, Рабочий семинар “Наукоемкое программное обеспечение”, Новосибирск 2011. – С. 200–207.
9. Участие в конференциях, организация конференций по теме программы
Конференции, традиционно проводимые ИСИ СО РАН

Седьмая междунар. конф. памяти академика А.П. Ершова “Перспективы систем информатики”, PSI’09, Новосибирск, 2009.

Восьмая междунар. конф. памяти академика А.П. Ершова “Перспективы систем информатики”, PSI’11, Новосибирск, 2011.

В период с 2008 по 2001 гг. сложилась серия российских семинаров «Знания и Онтология *ELSEWHERE*». Она была задумана сотрудниками нескольких лабораторий Института систем информатики им. А.П. Ершова СО РАН для публичного обсуждения некоторых аспектов исследований, которые велись по проектам РАН 14/9, 2006 – 2008 и 14/12, 2009 – 2011.
Участие в международных и всероссийских научных мероприятиях

В рамках проекта было принято участие более, чем в 15-ти международных конференциях, среди них:

Second Workshop on Program Semantics, Specification and Verification: Theory and Applications (PSSV 2011), Saint-Petersburg, Russia, 12-13 June 2011.

Всероссийская конференция с международным участием «Знания – Онтология – Теория» (ЗОНТ–09) и (ЗОНТ–11), Новосибирск, 2009, 2011.

Международный семинар "Семантика, спецификация и верификация программ: теория и приложения" (PSSV 2010), Казань, 2010.

Международная конференция «Компьютерная лингвистика и интеллектуальные технологии» (Диалог-2011), Бекасово, 25-29 мая 2011.

9th SoMeT_10 conference “New Trends in Software Methodologies, Tools, and Techniques”. Yokohama, Japan, 29 September – 1 October 2010.

10th WSEAS International Conference on Applied Computer Science (ACS’10). Iwate Prefectural University, Morioka, Japan, October 4-6, 2010.


Руководитель проекта А.Г. Марчук