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

На правах рукописи

Бессмертный Игорь Александрович

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

Специальность 05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург - 2014

Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики.

Научный консультант доктор технических наук, профессор

Тропченко Александр Ювснальевич

Официальные оппоненты: Тулупьев Александр Львович,

доктор физико-математических наук, профессор, СПИИ РАН, зав. лабораторией

Защита состоится 30 декабря 2014 года в 14 часов на заседании диссертационного совета Д 212.227.06 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д.49, конференц-зал центра интернет-образования

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д.49 и на сайте ГрролГто.ги.

Автореферат разослан «_»_2014 года.

Ученый секретарь диссертационного совета

Дорогов Александр Юрьевич,

доктор технических наук, профессор, ОАО «Интелтех», гл. науч. сотрудник

Семенов Николай Александрович,

доктор технических наук, профессор, ТвГТУ, профессор

Ведущая организация: Национальный исследовательский университет

«МЭИ»

к. ф-м. н., доцент

Лобанов

!•■"-,'•: -искля

! %■ С, Т Мi ИНАЯ

Ь/ЬПИО! tKA

2(114 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Последнее десятилетие характеризуется ростом потребности общества в информатизации и интеллектуализации во всех, сферах, в т.ч. в государственном управлении, здравоохранении, образовании, на транспорте, в промышленности и др. областях. Данная тенденция осознается как научным сообществом, так и на правительственном уровне, в частности, это нашло отражение в распоряжении Правительства Российской Федерации от 20 октября 2010 г. № 1815-р "О государственной программе Российской Федерации "Информационное общество (2011-2020 годы)", в котором предусмотрены мероприятия по созданию автоматизированных и информационно-аналитических систем в разных сферах.

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

Одновременно с ростом объемов и усложнением структуры баз знаний ужесточаются требования к глубине и широте поиска при ограничениях на время извлечения знаний. Несмотря на существенный рост общей производительности средств вычислительной техники, аппаратную поддержку узких вычислительных операций, возможности агрегирования ресурсов в ГРИД-структурах, рост сложности в пространстве поиска во много раз превышает возможность реализации поиска с помощью алгоритмов с экспоненциальной сложностью. Этим обстоятельством обусловлено ведение широкомасштабных исследований в области ускорения логического поиска как за рубежом (Стен-фордский университет, компании IBM, HP Lab, Google, Yahoo, и др.), так и в

России (ВЦ РАН, ИСА РАН, МЭИ, СПИИ РАН, Yandex и др.). К сожалению, существующие методы логического вывода не в полной мере учитывают многомерность баз данных и знаний большой размерности. Кроме того, известные реализации сводятся к алгоритмическим методам ускорения поиска, и даже достигаемое ускорение логического вывода на 2-3 порядка не позволяет устранить комбинаторную сложность задачи поиска решений.

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

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

Степень теоретической разработанности темы. Основные предпосылки создания искусственного интеллекта (ИИ) представлены работами Н. Винера и К. Шеннона в области управления сложными системами и теории информации, А. Тьюринга и М. Мински, Д. Люгера, П. Норвига и С. Рассела разработавших основные положения теории искусственного интеллекта, Л. Заде, внесшего вклад в применение нечеткой логики в интеллектуальных системах, Дж. МакКарти, создателя языка Lisp, работы В. Вапника в области обучающихся систем и С. Шапиро (представление знаний). Современные исследования представлены также деятельностью А. Банди, Д. Лената, М. Музена, К. Сикара, И. Братко.

Среди отечественных ученых следует упомянуть Д.А. Поспелова (исследования в области ситуационного управления), М.Г. Гаазе-Рапопорта, Д.Э. Попова, Т.А. Гаврилову, В.К. Финна, В.Ф. Хорошевского, А.П. Еремеева и В.Н. Вагина, внесших значительный вклад в теорию и практику экспертных систем и баз знаний.

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

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

Цель и задачи исследования. Цель исследования - повышение эффективности процессов обработки данных в базах знаний большой

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

Данная цель достигается решением следующих основных задач:

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

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

3. Исследование и разработка общесистемных методов ускорения логического вывода в базах знаний большой размерности за счет сокращения структурной избыточности дерева решений.

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

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

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

Область исследования соответствует пп. I, 4 паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

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

Информационная база исследования представлена опубликованными работами ведущих специалистов в области искусственного интеллекта и семантических сетей, материалами конференций по ИИ, в частности, Knowledge Engineering and Ontology Design (KEOD), ежегодного международного конгресса по интеллектуальным системам и информационным технологиям (IS-IT), международной конференции по инженерии знаний и технологиям

семантического веба (КЕБТУ), а также результатами экспериментов, проведенных в ходе данной работы, и \УеЬ-ресурсами.

Положения, выносимые на защиту, обладающие научной новизной:

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

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

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

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

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

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

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

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

Апробация результатов исследования. Результаты исследования докладывались на 17 всероссийских и международных научных конференциях, в т.ч. на VI Общероссийской научной конференции «Современная логика: Проблемы теории, истории и применение в науке» (СПб, 2000г.), 9-й, 10-й, 11-й и 12-й Всемирных конференциях по продолженному инженерному образованию (Токио, 2004г., Вена, 2006г., Атланта, 2008г., Сингапур, 2010г.), V международном симпозиуме по образовательным и информационным системам, технологиям и приложениям EISTA 2007 (Орландо, США, 2007г.), Международной конференции по языку Visual Prolog и приложениям VIP-ALC'08 (СПб, 2008г.), XXXIX Международной научно-практической конференции "Неделя науки СПбГПУ (СПб, 2010г.), на Международном конгрессе по интеллектуальным системам и информационным технологиям IS&iril, IS&ITM2, IS&IT13 (пос. Дивноморское, 2011, 2012, 2013 гг.), Международной конференции "Инженерия знаний и технологии Semantic Web" (СПб, 2010,2011,2012,2013гг.), 4-й Международной конференции по инженерии знаний и онтологическому дизайну (Барселона, 2012г.), 5-й Российской мультиконференции «Информационные технологии в управлении» ИТУ-2012 (СПб, 2012г.), Всероссийской конференции «Информационные и математические технологии в науке, технике, медицине» (Томск, 2012 г.), VIII Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» (Москва, 2013г.).

Публикация результатов исследования. По теме диссертации опубликовано 46 работ, из них 18 статей в журналах из перечня ВАК, в т.ч. две статьи, индексированные Web of Science и Scopus, три доклада в материалах международных конференций, индексированных Web of Science и Scopus, 23 доклада в сборниках трудов всероссийских и международных конференций,

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

Личный вклад. Все результаты, представленные в диссертации, получены лично автором либо совместно с аспирантами и студентами. В частности, эксперименты по организации логического поиска в среде СУБД выполнялись совместно с асп. P.C. Катериненко, эксперименты по исследованию методов построения баз знаний в троичной логике - совместно с асп. Ю.А. Королевой. На все совместные исследования имеются соответствующие указания в тексте.

Объем и структура работы. Диссертационная работа изложена на 304 страницах, состоит из введения, пяти глав, содержащих 65 рисунков и 22 таблицы, заключения и приложений. Библиографический список включает 120 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Описываемая система включает в себя базы данных с суммарным объемом 17 терабайт, десятки датацентров по всему миру, сотни тысяч терминалов нейтральных агентов (N) глобальных распределительных систем (ГРС) и терминалов национальных систем бронирования (Т и С), а также миллионы частных Интернет-клиентов. Каждая транзакция (поиск маршрута) в такой системе представляет собой задачу поиска на дереве решений, имеющую

экспоненциальную сложность.

Рисунок 1 — Структура глобальной автоматизированной системы бронирования авиаперевозок и взаиморасчетов на воздушном транспорте

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

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

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

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

Рисунок 2 - Алгоритм поиска в базах знаний с использованием прецедентов

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

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

Отсутствие решения чаще всего означает, что при обработке запроса не учитывается неоднородность пространства поиска, т.е. запрос затрагивает различные нредметные области, следовательно, требуется расширение домена. Противоречивость результатов является свидетельством слишком широкого домена, и требуется его уточнение.

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

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

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

Проведенные исследования показывают, что большая размерность дерева решений в различных приложениях часто обусловлена наличием многочисленных повторяющихся цепочек правил (продукций), каждая из которых может быть свернута в один узел уже после первого прохода. Путем замены повторяющихся ветвей одним узлом в известной логической игре «23 спички» автором достигнуто сокращение числа развертываемых узлов дерева поиска с 20 тысяч до 57 путем замены повторяющихся ветвей одним узлом. Рисунок 3 демонстрирует повторяющиеся фрагменты данного дерева решений.

Рисунок 3 - Дерево решений с повторяющимися фрагментами

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

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

Для обеспечения актуальности прецедентов предложена модель базы знаний в базисе «состояния-события», в которой множество фактов F представлено в виде ^ = {5, £}, где 5 = {«}, Е = {е} - множества состояний и событий соответственно. Каждое состояние в момент времени ( может быть

или аксиомой (начальным состоянием), если оно не может меняться, или результатом событий, определяемым с помощью множества правил Л: ({«,_,}, {<?,}) —* Эволюцию состояний иллюстрирует рисунок 4.

Рисунок 4 - Эволюция состояний в базисе «состояния - события»

Для того, чтобы вычислить состояние е( на текущий момент t, нужно либо применить необходимые правила ко всем событиям от начального состояния i0 до текущего момента /, т.е. вычислить ef =ßs0, е,, е2, .... е(1), либо извлечь из базы прецедент еи если таковой имеется. В последнем случае поиск решения имеет сложность 0(card(£)).

Формирование базы знаний в базисе «состояния-события» с использованием прецедентов влечет за собой проблему контроля актуальности прецедентов в условиях изменчивости базы фактов. Как показано на рисунке S, возможны три способа управления прецедентами: при обращении к нему из запроса, периодически по расписанию и при наступлении событий.

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

= Vi т |Р| + К xm\F\ = К i(|/>| + m|F|), (1)

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

= й т + 'Л m\F] ='Л А\Р\ + m\F]), (1)

Рисунок 5 - Алгоритмы управления прецедентами по запросу (а), по расписанию (б) и по наступлению события (в) где г - время извлечения одного факта, Р - множество прецедентов, т -среднее число первичных фактов, использованных при выводе прецедента. При третьем способе среднее время /2 извлечения прецедента

(2='Лт\Р\, (2)

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

', = т| Р\. (3)

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

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

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

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

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

Доказательство. Пусть Р={/) - множество фактов в базе, Рг={£} -множество фактов, релевантных /-му утверждению запроса (), т - время извлечения одного факта, М=сагд(Р), й =саг<1(0. Тогда время обработки запроса 0 без индексации Т = а с индексацией

Тогда

i=i

Допуская, что card(/j)= card(/^)= ...= card(fg)= /V ,

r^fjrcardi/). (4)

i>i

T _ t(N)j

т ~ d ' (5)

Пгсаг(1(^)

T _ (jN)'

Tx (tNJ {NJ

= <5" (6)

Теорема доказана.

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

Теорема 2. Для отбора фактов для подстановки в правило при поиске в базе знаний достаточно ограничиться операцией пересечения индексов.

Доказательство. Пусть базу фактов образуют триплеты вида субъект-предикат-объект либо субъект-атрибут-значение, представленные нотации языка Prolog следующим образом:

А*. Р. о),

где s - субъект, р - предикат (отношение, связывающее субъект и объект), о -объект. Присвоим каждому факту в базе знаний порядковый номер i; тогда нумерованный факт будет записан следующим образом: fn(i, s, р, о). Для множества термов Т= {/}, встречающегося в фактах, построим индекс в виде

Х= {*}= {(WU)}, (7)

I,=

где w - место данного терма в атоме (в качестве субъекта, предиката или объекта), {i^} - множество номеров фактов, имеющих терм t в роли w,

w = (V|>'| 'оУ

Теперь, при обращении к правилу, тело которого состоит из множества условий {с,, су ..., ск}, где с. = (г, р} оД Sj - субъект, р. - предикат, о. - объект, (j; о) = (// v), v - переменная, Pj = t. Каждое из условий с. может иметь одно из четырех сочетаний термов и переменных: (/, t, /); (t, t, v); (v, t, t); (v, t, v).

Для каждого из с. условий правила извлечение релевантных фактов для перечисленных сочетаний термов заключается в нахождении пересечений множеств индексов:

(4 } п {',„ } П {!,„ }, S, = const, о, = const; {i,P} П {/,„}, -ij = var,Oj = const; {'« } П {i,p >, s j =■ const, ot = var; {',,,}> sj = var.Oy = var.

Таким образом, число фактов, отобранных для условия с. правила зависит от сочетания переменных и констант в условии.

Каждой переменной v, используемой в j-ом условии, из списков 1.и можно поставить в соответствие множество кортежей {¿и.}, где / - номер факта, i<= Iг Ui - значение переменной v, извлекаемое из i-го факта. Если переменная v используется более чем в одном условии правила, пересечение

Uv(Cj)= П {"j) (9)

jec

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

= {МН«Л- (10)

Если в условии правила с участвуют более одной переменной, то пересечение списков

{j = П Kj (in

veCj

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

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

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

Пусть в результате отбора фактов для условий правила рг о,), с(.?2> р2, о2),..„ ф^ р^ су, где о1 - либо константа, либо переменная, получены множества кортежей Т = {{Л}}, >=(хп, хА если в условии правила две переменные, л =(*,), если одна переменная. Таким образом, для правила из к условий, получаем к таблиц приблизительно следующего вида:

> Ч>. ... -w. .

ж®,

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

1. Соединение двух таблиц по совпадению значений одной или более переменных у пары таблиц. В этом случае две таблицы объединяются реляционным оператором INNER JOIN.

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

Таким образом, интерпретация правил может быть заменена операциями реляционной алгебры и помещена в среду СУБД. Ниже приведен пример трансляции в SQL правила, определяющего возможность стыковки двух авиарейсов. Исходное правило на языке SWRL выглядит следующим образом: raceEnd (1 race 1,?х) л race Begin (? race!, 7 х) => canConnect (? race\, ? race2) Данное правило транслируется в оператор SELECT на языке SQL из таблицы F, состоящей из колонок (Subject, Predicate, Object)'.

SEl,ЕСТ F.Subject AS Racel, F_l.Subject AS Race2

FROM F INNER JOIN F AS FJ ON F.Object=F J. Object

WHERE (((F.Predicate) = "raceEnd") AND ((FJ.Predicate)="raceBegin")).

Ниже приведены правила для выполнения пересечения двух списков,

которые демонстрируют квадратичную сложность данной операции, поскольку при этом сканируется в среднем nnJ2 элементов, где nf п^ - количество элементов в списках ЛГ и К соответственно.

0Пу Х = х х = х

-— intersect 0 -"-intersect 1 -----intersect 2.

0 х Z Л

Если отсортировать списки Х={х} и Y={y} по возрастанию значений, то оба списка можно обрабатывать совместно. Правила для операции пересечения отсортированных списков приведены ниже.

X п^

0ПК Х = х-Х,, Y-x-Y,, —Ly—

———intsorted О--*-intsortedl

0 x Z

XDY

X = x X„ y = Y Ys,x>y, -—

-----— intsorted 2

z

X = xX„ Y = yYs,x<y.^----—— intsorted 3.

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

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

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

Вычислять информативность утверждений, представленных кортежами j[s, р, о), где s - субъект, seS, р - предикат, реР, о - объект, о е О предложено на пересечении следующего вида

/(40 = lc^O/KM: * е 5 л у е О} П {f(s,y,z): у б Ра г е О) (1

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

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

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

посадка_разрешена(ВоздСудно,ВПП) :- класс(ВПП) = класс(ВоздСудно),

not(ветер_поперек(БПП)).

разрешающее посадку при соответствии класса ВПП классу воздушного судна и отсутствии бокового ветра разрешит посадку также в случае отсутствия метеоданных. В то же время допущение открытого мира может инициировать глобальный поиск с непредсказуемой сложностью при обработке самых простых запросов. В базисе троичной логики разработаны принципы составления /Vo/og-правил, позволяющие устанавливать не только достоверность фактов, вычисляемых на их основе, но и определять, отсутствие каких фактов препятствует установлению их истинности. Пример Prolog-правила, разрешающего посадку воздушного судна X на ВПП Y, если ВПП соответствует первому классу и отсутствует боковой ветер, приведен ниже, ternary(X,посадка_разрешена,Y,Достоверность, [Condi, [ 'NOT' ICond2]) :-ternary(Y,соответствует,класс1, Cty1,Condi) , Ctyl>=0, ternary(ветер, поперек, Y, Cty2, Cond2), Cty2=<0, Достоверность is min(Ctyl, -Cty2).

Данное правило возвращает достоверность результата и список фактов, отсутствующих в данном домене и истинность которых требуется доказать, если достоверность = 0. Для случая отсутствия метеоданных список будет содержать [NOT [ветер, поперек, ВПП1]]. Таким образом, обосновывается необходимость расширения домена поиска. Кроме того, применение троичной логики позволяет автоматически обнаруживать противоречия в базе знаний, которые проявляются одновременным наличием самого факта и его отрицания.

В работе предложен способ визуализации результатов поиска в виде

семантических сетей, позволяющий в наглядной форме отображать факты, истинность которых следует доказать в расширенном домене. Пример такой визуализации условий истинности факта «А340, посадка_разрешсна, ВПП1» из рассмотренного выше примера приведен на рисунке 7.

Рисунок 7 - Визуализация условия истинности факта «Для А340 посадка_разрешена на ВПП1»

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

Теорема 3. Поиск в расширяющемся домене имеет полиномиальную сложность от мощносги домена.

Доказательство. Пусть N - число фактов в базе знаний, г - среднее время доступа к одному факту, А. - число атрибутов или классов, релевантных /-му условию запроса, <=(1,л). Среднее время Т обработки запроса на извлечение фактов для точно определенного домена

>г/< А \ I 1 . (Л + 3) i6)

T = tN{ + — + - + — + ... +-г «1N--'

2 2 2А 2А 2

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

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

Тх =тЩ\ + А + 8+— + ...+?—г)*тЩ\ + А + 6), (7)

А А

если также пренебречь малыми значениями членов ряда.

В том случае, если контекст расширяется до целого класса, то для 1-го условия запроса атрибут может принадлежать j-му классу, включающему С, экземпляров. Первое условие запроса порождает в среднем А{+С{ обращений к

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

Т. = гМ(1 + Л + С + — +1 + -4- + — + ... + — + —Ц-). (8)

С С2 С С" С"'1

Теорема доказана.

Таким образом, подтверждается целесообразность выбора домена поиска методом его постепенного расширения.

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

Процесс бронирования перевозок с рабочего места кассира или интернет-клиента является многофазным, как показано на рисунке 8.

Получение перевозочных документов

Формулировка намерений клиента

Расписания авиакомпаний

Оптимизация

маршрута и услуг

± \ \

Формирование РМЯ

1

Тарификация

маршрута и оформление

перевозочной

документации

Сазы тарифов

Базы мест

Рисунок 8 - Многофазный процесс бронирования перевозок

На каждой фазе требуется обращение к распределенным базам данных, размещенным на ресурсах компаний Сирена-Тревел, Амадеус, Сэйбр, Габриэл, Галилео, а поиск в базах данных, состоящих из миллионов записей, определяется деревом решений с глубиной от 1 до 4 (количество стыковочных маршрутов) и коэффициентом ветвления порядка сотен. Фрагмент дерева решений для поиска маршрута показан на рисунке 9. На данном графе вершины А1, А2, ... отражают аэропорты, а дуги Ш, Л2, ... - связывающие их рейсы. Поиск маршрута заключается в нахождении связи между исходным пунктом и пунктом назначения при выполнении множества ограничений, в т.ч.

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

Рисунок 9 - Фрагмент дерева маршрутов

Метод индексации и предварительной обработки фактов, релевантных условиям запроса в применении к поиску маршрута в упрощенном виде можно представить следующим образом. Для всех рейсов вида Я = (Д А, 4» 1а), где Д - аэропорт вылета, ^ и - день недели и время вылета, А - аэропорт прилета, с!а и /„ - день недели и время прилета, составляются индексы следующего вида:

х(£>, {Л}); {/?}); *(/А {Л}); х(А, {Л}); *(«/„, {Л}); х((а, {Л}).

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

Й=(Д _);

02 = (Д ¿А 5,, </,. /1), (5,, </,, А, _);

£>э = (Д ¿л 5|, Л). (5|, <11, <¡2, (2), Аг, /2+, А, _, _);

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

Предварительный отбор фактов для каждого запроса состоит в

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

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

Для исследования методов логического вывода с помощью операций реляционной алгебры выполнена загрузка тестовой базы знаний в среду реляционных СУБД и проведено исследование времени обработки правил как ^¿-запросов. На рисунке 10 приведены результаты экспериментального исследования скорости логического вывода методами реляционной алгебры в различных СУБД, которые демонстрируют трех-пятикратное ускорение по сравнению с существующим алгоритмом ускорения RETE.

10000

1000

с

ф

а

СИ

-Наивный вывод

-RETE JESS

5000 10000 15000

Число фактов

MS Access

-Oracle ХЕ

-*-MySai

Логический вывод в среде СУБД

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

На рисунке I! приведены результаты натурных экспериментов по измерению производительности библиотечных и разработанных быстрых предикатов для обработки списков в среде Visual Prolog. Проведенные экспериментальные исследования подтверждают, что замена процедуры интерпретации правил теоретико-множественными операциями обеспечивает квадратичный рост сложности вывода, а применение реляционных операций над отсортированными списками - полиномиальную сложность.

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

И Пересечение списков, наивный вывод

А Соединение кортежей, наивный вывод

К Сортировка списков —W— Сортировка кортежей -♦—Пересечение списков, библ.предикат 1 Объединение списков, библ.предикат

— Пересечение быстрый предикат

— Соединение кортежей, быстрый предикат

Объединение списков, быстрый предикат

Вычитание списков, быстрый предикат

Рисунок 11 - Временные характеристики стандартных и разработанных автором быстрых предикатов Пролога для выполнения реляционных операций

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

поддержание актуальности прецедентов, юоооо

&

100

10 -

0,1

0,01

100000 200000 400000 800000 1600000 Число фактов

0.06

0,04

0.05

Верификация (факт)

//

J

Удаление (факт)

£0

0,02

0,01

0

—Удаление (модель)

Верификации

(модель)

4000 8000 12000 16000 24000 32000 40000 Число первичных фактов в базе знаний

Рисунок 12 - Результаты экспериментального исследования времени обработки прецедентов

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

пространства поиска, ориентированной на использование методов быстрого логического вывода.

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

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

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

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

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

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

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

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

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

в) алгоритмы, реализующие логический вывод с помощью теоретико-

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

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

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

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

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

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

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

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

ж) теоретически обосновать линейную зависимость вероятности нахождения решения в узком домене от степени соответствия домена запроса домену поиска;

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

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

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

а) создана программно-аппаратная среда, отличающаяся использованием свободно распространяемого программного обеспечения, что обеспечивает воспроизводимость экспериментальных исследований;

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в ведущих рецензируемых журналах, утвержденных ВАК РФ для публикации основных научных результатов диссертаций соискателей ученой степени доктора наук:

1. Бессмертный, И.А., Коваль, A.A., Белоус, P.O. Ассоциативный поиск данных с помощью нейронной сети // Научно-технический вестник СПбГУ-ИТМО,2005. -№19, вып. «Программирование, управление и информационные технологии».-С. 132-139. -0,5 п.л.

2. Бессмертный, И.А. Методы поиска информации с использованием интеллектуального агента // Изв. вузов. Приборостроение, 2009. -№ 12. -С.26-31. - 0,4 п.л.

3. Бессмертный, И.А. Семантическая паутина и искусственный интеллект // Научно-технический вестник СПбГУИТМО, 2009. -Т.64, вып.6. -С.77-83. -0,4 п.л.

4. Бессмертный, И.А. Теоретико-множественный подход к логическому выводу в базах знаний И Научно-технический вестник СПбГУИТМО, 2010. -Т. 66, вып. 2. -С. 43-48. - 0,4 п.л.

5. Бессмертный, И.А. Быстрый логический вывод в среде программирования Visual Prolog // Научно-технический вестник СПбГУИТМО, 2010. -Т. 67, вып. 3. -С. 50-56. - 0,4 п.л.

6. Бессмертный, И.А. Визуализация знаний на основе семантической сети // Программирование. -М: Pleiades Publishing, Ltd., 2010. -Т. 36. -№ 4. -С. 16-24.

- 0,6 п.л. Англоязычный вариант: Knowledge Visualization Based on Semantic Networks // Programming and Computer Software. -2010. -Vol. 36. -No 4. -P. 197204. - 0,5 п.л.

7. Бессмертный, И.А. Применение реляционных операций для логического вывода в продукционных системах // Известия вузов. Приборостроение, 2010. -Т. 53, вып. 10. - Вычислительная техника. - С. 34-37. - 0,3 пл.

8. Бессмертный, И.А. Оценка количества информации в базах знаний // Научно-технический вестник СПбГУИТМО, 2011. - Вып. 2. - С. 146-149. - 0,3 п.л.

9. Бессмертный, И.А., Катериненко, P.C. Метод ускорения логического вывода в продукционной модели знаний // Программирование, 2011. - Т. 42. - № 4. - С. 76-80. - 0,3/0,15 п.л. Англоязычный вариант: Inference acceleration in production model of knowledge // Programming and Computer Software. -2011- Vol. 42. - N 4.-P. 197-199. -0,2/0,1 п.л.

10. Бессмертный, И.А., Булыгин, K.A. Многоагентный подход к решению задач неинформированного поиска // Научно-технический вестник СПбГУИТМО, 2011. - Т. 74. - Вып. 4. - С. 98-102. - 0,3/0,2 п.л.

11. Бессмертный, И.А. Методы поиска информации в продукционных системах // Изв. вузов Приборостроение, 2011. №. 6. - С. 56-59. - 0,3 п.л.

12. Бессмертный, И.А., Ковбаско, Д.В., Балгайракова, A.C. Контекстный подход к реализации интеллектуальных систем // Научно-технический вестник НИУИТМО, 2011. - Вып. 6. - С. 145. - 0,06/0,03 п.л.

13. Бессмертный И.А. Управление контекстом в информационных системах // Изв. вузов. Приборостроение, 2012. - Т. 55. -№10. - С.7-13. - 0,5 п.л.

14. Бессмертный, И.А., Нугуманова, А.Б. Метод автоматического построения тезаурусов на основе статистической обработки текстов на естественном языке // Изв. Томского политехнического ун-та, 2012. - Т. 321. - № 5. - С. 125-130. -0,4/0,2 п.л.

15. Бессмертный И. А., Катериненко P.C. Верификация данных в системах отслеживания задач с помощью продукционных правил // Научно-техн. вестник информационных технологий, механики и оптики, 2013. -№1. -С.86-90. - 0,4/0,2 П.Л.

16. Бессмертный, И.А., Невидимое, A.B. Подход к коллективной разработке онтологии // Научно-техн. вестник информационных технологий, механики и оптики, 2013. -№ 2. -С. 161. - 0,06/0,03 п.л.

17. Бессмертный, И.А. Контекстный подход к оценке количества информации в базах знаний // Искусственный интеллект и принятие решений, 2013. -№3. -С.40-47. - 0,5 п.л.

18. Бессмертный И.А., Королева Ю.А. О построении интеллектуальных систем в троичной логике // Программирование. - 2014. - № 1. - С.31-35. - 0,4/0,2 п.л. Англоязычный вариант: On constructing intellectual systems in ternary logic // Programming and Computer Software. -2014. -Vol.40. - 1. - P.43^46. - 0,3/0,2 п.л. Работы, опубликованные в материалах международных конференций, индексированные Scopus и/или Web of Science:

19. Bessmertny, I. Intellectual Agent in Training Systems // Proc. of Int'l MultiConference on Society, Cybernetics and Informatics IMSCI'07. -Orlando, FL, USA:

International Institute of Informatics and Systemics, 2007. -Vol. 1. -P.86-89. - 0,3 пл.

20. Bessmertnyi, I. Nevidimov, A., Eliseev, S. About creating intelligence systems in ternary logic // Proc. of 4dl Int'l Conf. on knowledge engineering and ontology development. - Barcelona: SciTePress.-2012.-P. 161-165. -0,3/0,1 п.л.

21. Bessmertny, I., Nugumanova A. Applying the Latent Semantic Analysis to the Issue of Automatic Extraction of Collocations from the Domain Texts // Communications in Computer and Information Science. Proc. of 4lh Conf. on knowledge engineering and Semantic Web, Oct. 7-9, 2013. - P. 92-101. - 0,6/0,3 п.л. Работы, опубликованные в материалах всероссийских и международных конференций, статьи в сборниках научных трудов и прочие работы:

22. Бессмертный, И.А. Джалиашвили, З.О., Максимов, В.В., Маркин, Д.А. Лингвооценочное управление текстом [электронный ресурс] // Материалы X Международной конференции "Применение новых технологий в образовании". - Троицк: Фонд новых технологий в образовании "Байтик", 1999.

23. Бессмертный, И.А., Джалиашвили, З.О. О корректности отношений в базах знаний // Тез. докл. VI Общеросс. научн. конф. "Современная логика: Проблемы теории, истории и применение в науке". - СПб: СПбГУ, 2000. - С. 27-30. -0,3/0,15 п.л.

24. Бессмертный, И.А., Джалиашвили, З.О., Зиньков, М.В. Концепция построения обучающей экспертной системы [электронный ресурс] // Материалы X Международной конференции "Применение новых технологий в образовании". -Троицк, 2001. -URL: http://www.bytic.ru/cue99M/cfd613d8yy.htinI.

25. Bessmertny, I.A., Kulagin, V.S. Artificial Intelligence: A Teaching Experience // Proc. of 1ACEE 9th World Conference on Continuing Engineering Education (WCCEE 2004). - Tokyo, 2004. C. 192-194. - 0,2/0,1 п.л.

26. Bessmertny, 1.А., Kulagin, V.S. An Approach to Building Learning Expert Systems [электронный ресурс] // Proc. of 10th World Conference on Continuing Engineering Education (WCCEE 2006). Vienna: Vienna University of Technology, 2006. - URL: http://www.ai.tuwien.ac.at/wccee2006/proceedings/

27. Bessmertny, I.A., Kulagin, V.S. Semantic Network as a Knowledge Base in Training Systems // Proc. of 11th IACEE World Conference on Continuing Engineering Education (WCCEE 2008). - Atlanta, GA, USA, 2008. - P. 95-99. - 0,3/0,15 пл.

28. Bessmertny, I.A. Visual Prolog and Semantic Networks at Knowledge Visualization // Proc. of Visual Prolog - Applications & Language Conference 2008 (VIP-AL'08). - SPb: Prolog Development Center A/S, 2008. - C.I07-111. - 0,3 пл.

29. Бессмертный, И.А., Шеховцов, M.M. Индексация фактов для ускорения логического вывода в базах знаний // Сб. трудов молодых ученых и сотрудников

кафедры ВТ. - СПб: СПбГУИТМО, 2010. - С. 18-22. - 0,3/0,115 п.л.

30. Bessmertny, I.A., Katerinenko, R.S. Semantic Web and a Global Artificial Intelligence // Proc. of 12th 1ACEE World Conf. on Continuing Engineering Education (WCCEE 2010). - Singapore: Research Publishing, 2010. -C.205-209. -0,3/0,15 п.л.

31. Бессмертный, И.А., Катериненко, P.C. Semantic Web и продукционная модель знаний // Сб. трудов Всеросс. конф. "Управление знаниями и технологии семантического веба". - СПб: СПбГУИТМО, 2010. - С. 183-185. - 0,2/0,1 п.л.

32. Бессмертный, И.А. Катериненко, P.C. Эффективная работа с продукционной моделью знаний с помощью реляционной алгебры // Сб. докл. XXXIX Межд. научно-практ. конф. "Неделя науки СПбГПУ". - СПб: СПбГПУ, 2011. - С. 17-18. -0,1/0,05 п.л.

33. Бессмертный, И.А., Катериненко, P.C. Компетентностная модель искусственного интеллекта // Труды Межд. конгресса по интеллектуальным системам и информационным технологиям IS&IT'I I. - М.: Физматлит, 2011. Т. 3. -С.11-16. - 0,4/0,2 п.л.

34. Бессмертный, И.А., Катериненко, P.C. Эффективный логический вывод в продукционной модели с помощью баз данных с вертикальной архитектурой // Сб. трудов Всеросс. конф. "Инженерия знаний и технологии Semantic Web 20И" (KESW2011).- СПб.: НИУИТМО, 2011. - С. 150-157. - 0,5/0,25 п.л.

35. Бессмертный, И.А., Ковбаско, Д.В., Балгайракова, A.C. Исследование вывода на основе прецедентов для базы знаний в среде JENA // Вестник КазНТУ. -Алматы: КазНТУ, 2012. -№ 2. - С.255-258. - 0,3/0,1 п.л.

36. Бессмертный, И.А. Применение троичной логики в интеллектуальных системах на продукционной модели знаний // Труды Межд. конгресса по интеллектуальным системам и информационным технологиям IS&IT42. - М.: Физматлит, 2012. - Т. 1. - С. 409-414. - 0,4 п.л.

37. Бессмертный, И.А., Катериненко, P.C., Пичугин, Н.С. Верификация систем управления проектами с помощью продукционных правил на основе двоичных диаграмм решений // Труды Межд. научно-практ. конф. «Инженерия знаний и технологии семантического веба» KESW-2012. - СПб, 2012. - С. 235-243. -0,6/0,2 п.л.

38. Бессмертный, И.А., Катериненко, P.C., Пичугин, Н.С. Разработка онтологического описания технических индикаторов // Труды Межд. научно-практ. конф. «Инженерия знаний и технологии семантического веба» KESW-2012. -СПб, 2012. - С. 68-74. - 0,4/0,1 п.л.

39. Бессмертный, И.А., Нугуманова, А.Б. Построение семантических отношений между ключевыми понятиями предметной области с помощью

<4-14688

латентного семантического анализа // Тез. докл. Всеросс. конф. Информационные и математические технологии в науке, технике, медицине. Томск: ТПУ, 5-8 нояб. 2012. -Томск: ТПУ, 2012. - С. 91-93. - 0,2/0,1 п.л.

40. Бессмертный, И.А., Нугуманова, А.Б. Создание тезауруса предметной области на основе автоматического извлечения ключевых слов из документов // Труды Межд. научно-практ. конф. «Инженерия знаний и технологии семантического веба» K.ESW-2012. - СПб: НИУ ИТМО, 2012. - С. 89-102. - 0,8/0,4 п.л.

41. Бессмертный, И.А. Интеллектуальные системы на продукционной модели знаний: Проблемы практической реализации /У LAP Lambert Academic Publishing GmbH & Co. KG, 2012. - 225 c. - 14 п.л.

42. Бессмертный, И.А., Королева, Ю.А. Поиск в базах знаний в базисе троичной логики и расширяющемся домене // Труды Межд. конгресса по интеллектуальным системам и информационным технологиям IS&IT'2013. - М.: Физматлит, 2013.-Т. 1.-С. 128-132. -0,3/0,15 п.л.

43. Бессмертный И.А., Нугуманова, А.Б., Каримов, А.Т., Новоселов, А.О. Реализация алгоритма извлечения ключевых слов из текстов предметной области на основе модели MapReduce // Труды VIII Международной научно-практической конференции "Современные информационные технологии и ИТ-образование".

- М.: МГУ им. М. В. Ломоносова, 2013. -С. 617-624.-0,5/0,1 п.л. Учебное пособие для вузов:

44. Бессмертный, И.А. Искусственный интеллект // СПб: СПбГУ ИТМО, 2010.

- С.132. - 8 п.л.

Зарегистрированные права интеллектуальной собственности на программы для ЭВМ:

45. Бессмертный И.А. Программа Semantic (св-во №2011614275 от 30.05.2011).

46. Бессмертный И.А. Библиотека быстрых Пролог-предикатов для обработки списков (св-во №20122611773 от 16.02.2012).

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Кронверкский пр., д. 49. Тел.(812)233 46 69 Объем2п.л.

Тираж 100 экз.

20

0015905