автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгебраические байесовские сети: вычислительная сложность алгоритмов логико-вероятностного вывода в условиях неопределённости

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

005004248

СИРОТКИН Александр Владимирович

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ: ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМОВ ЛОГИКО-ВЕРОЯТНОСТНОГО ВЫВОДА В УСЛОВИЯХ НЕОПРЕДЕЛЁННОСТИ

05.13.18 — математическое моделирование, численные методы и комплексы программ, 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

-1 ЛЕК 2011

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

005004248

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

Научный руководитель: доктор физико-математических наук,

доцент ТУЛУП ЬЕВ Александр Львович

Официальные оппоненты: доктор физико-математических наук,

профессор ВАРАНОВ Сергей Николаевич (Учреждение Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН, лаборатория технологий и систем программирования)

доктор физико-математических наук, профессор БУРОВА Ирина Герасимовна (Санкт-Петербургский государственный университет, математико-механический факультет, кафедра вычислительной математики)

Ведущая организация: Учреждение Российской академии наук

Институт системного анализа РАН

Защита состоится 15 декабря 2011 г. в 14°° часов на заседании совета Д 212.232.51 по защитам докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург,, Старый Петергоф, Университетский пр., 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан ^ /} 1 1 2011 г°Аа-

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

Кривулин Н. К.

Общая характеристика работы

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

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

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

Применение математических моделей знаний с неопределённостью наиболее востребовано в различных прогностических системах, а также в интеллектуальных системах поддержки принятия решений. Создание программных продуктов, которые можно использовать на практике, требует не только строгой формализации математического аппарата, но также разработки и последующего анализа алгоритмов, который гарантирует, что результаты работы системы соответствуют действительности. Кроме того, в силу наличия неточности, надо чётко понимать, какая «ошибка в данных» фатальна и ведёт к неверному ответу на заданный вопрос, а какая — не повлияет на главный результат. Это влечёт необходимость построения оценок устойчивости и чувствительности логико-вероятностного вывода.

Корректность и чувствительность алгоритмов логико-вероятностного вывода отвечает на вопрос, можно ли «теоретически» использовать данные алгоритмы. Но при этом они не отвечают на вопрос, насколько ограничено (и вообще возможно) применение указанных алгоритмов на практике, и в частности, — дождёмся ли мы результатов моделирования процессов рассуждений за разумное время. Для ответа на эти вопросы требуется оценить сложность алгоритмов логико-вероятностного вывода, что и составляет основную цель диссертационной работы.

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

Цель исследования. Целью диссертационного исследования является оценка эффективности алгоритмов логико-вероятностного вывода в ABC. Её достижение осуществляется посредством решения следующих задач: 1) оценить вычислительную сложность алгоритмов логико-вероятностного вывода в ABC; 2) исследовать устойчивость и чувствительность алгоритмов проверки и поддержания непротиворечивости фрагмента знаний АБС; 3) исследовать возможности расширения семантики алгебраических байесовских сетей за счёт введения новой степени непротиворечивости (на-

крывающей непротиворечивости); 4) исследовать возможности моделирования байесовской сети доверия (БСД) с помощью АБС.

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

Научная новизна исследования. Предложен способ вычисления матрицы, соответствующей линейному оператору ненормированного локального апостериорного вывода в случае детерминированного свидетельства, на основе выражения её через фиксированные матрицы небольшой размерности. Даны оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод), а также алгоритмов поддержания различных степеней непротиворечивости АБС (глобальной, интервальной, экстернальной). Конструктивно доказано, что экстернальная непротиворечивость АБС не гарантирует интернальную непротиворечивость (построен соответствующий контрпример). Предложена математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость». Предложен алгоритм построения АБС, семантически эквивалентной заданной БСД, на основе представления последней в виде дерева смежности. Предложены подходы к оценке устойчивости процесса поддержания непротиворечивости ФЗ АБС. Создан комплекс программ на языке программирования С++, реализующий локальный логико-вероятностный вывод в АБС, а так же поддержание различных степеней непротиворечивости и глобальный апостериорный вывод для АБС представленной в виде дерева смежности.

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

Все результаты, выносимые на защиту диссертации, являются новыми.

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

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

Апробация результатов исследования. Результаты исследования были представлены автором на следующих конференциях: 1) VIII Международная конференция по мягким вычислениям и измерениям SCM'2005; 2) X Международная конференция по мягким вычислениям и измерениям SCM'2007; 3) XII Международная конференция по мягким вычислениям и измерениям SCM'2009; 4) Научная сессии МИФИ-

2008; 5) Научная сессии МИФИ-2009; 6) Научная сессии МИФИ-2010; 7) Научная сессии МИФИ-2011; 8) Всероссийская научная конференция по нечётким системам и мягким вычислениям, Тверь, 2006; 9) Вторая Всероссийская научная конференция с международным участием Нечёткие системы и мягкие вычисления (НСМВ-2008) 10) X Санкт-Петербургская международная конференция Региональная информатика-2006(РИ-2006) 11) XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008) 12) IV международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2007; 13) V-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2009 г.; 14) VI-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 16-19 мая 2011 г.; 15) V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2007; 16) Научно-практическая конференция студентов, аспирантов, молодых учёных и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Коломна, 26-27 мая 2009 г.; 17) Научная конференция «Информационные технологии и системы», Геленджик,

29 сентября - 03 октября, 2008 г. Кроме того, результаты диссертационного исследования неоднократно докладывались на Санкт-Петербургском общегородском научном семинаре «Информатика и компьютерные технологии» в 2005-2010 гг.

Исследования по теме диссертации были поддержаны грантом Фонда содействия отечественной науке по программе «Лучшие аспиранты РАН» (2008), грантом РФФИ (09-01-00861-а— «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределённостью»), госконтрактом 02.442.11.7289 от 28.02.2006 на выполнение НИР «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы», а так же грантом «У.М.Н.И.К.» (2008, 2009), госконтракт № 5353 р/7771 от 16 августа 2007 г на выполнение НИОКР по теме «Разработка методов и программных средств для создания автоматизированных систем мониторинга и управления динамическими объектами» и госконтракт №6468р/8764 от 11.01.2009 на выполнение НИОКР «Разработка автоматизированных систем для нужд навигации, управления движением, медицины, а также их компонентов, включая датчики, приборы, алгоритмы и программное обеспечение».

Издание монографии [1] соискателя «Байесовские сети: логико-вероятностный подход», СПб.: Наука, 2006 (в соавторстве с А. Л. Тулупьевым и С. И. Николенко), было поддержано грантом РФФИ № 06-01-14108-д, а в 2007 г. её авторский коллектив стал лауреатом конкурса на лучшую научную книгу 2006 года (Фонд развития отечественного образования, г. Сочи).

Публикации. По теме диссертации опубликовано 64 научные работы, из них — 2 монографии (в соавторстве), прошедших научное рецензирование, одна из последних поддержана в 2006 г. издательским грантом РФФИ, 10 статей опубликованы в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК,

30 статей и докладов на конференциях, 13 зарегистрированных программ (в Роспатенте и ЦИТиС/ОФЭРНИО) и 9 тезисов научных конференций. Кроме того, часть результатов включена в ряд отчётов по НИР и НИОКР.

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

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

В [4] A.B. Сироткину принадлежит обобщение метода пропагации детерминированного свидетельства на случай свидетельства, состоящего более чем из одного атома, в [6] — описание семантики различных степеней непротиворечивости АБС, в [8] — результат, связанный с выражением числа ребер в минимальном графе смежности, через ранг матроида, в [10] — выявление связи теоремы о множестве минимальных графов смежности и полнотой классификации владений. В [9] предложено улучшение алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей. В [12] — теорема 4 о непротиворечивой оболочке данных в общем случае.

В [3,5] A.B. Сироткин, используя индексацию объектов с помощью характеристических векторов, сформировал основу для алгебраизации синтеза согласованных оценок истинности и пропагации недетерминированных свидетельств.

Более подробное описание вклада A.B. Сироткина в совместные публикации содержится в тексте диссертации.

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

Краткое содержание диссертации

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

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

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

Во второй главе изложены математические основы теории алгебраических байесовских сетей на языке, удобном для дальнейшего анализа. Материалы второй главы базируются преимущественно на результатах исследований других специалистов, в особенности — В.И. Городецкого и А.Л. Тулупьева, но при этом она содержит ряд результатов, полученных автором. В главе даются необходимые определения, описываются понятия элементов локального логико-вероятностного вывода. Определяются понятия поддержания непротиворечивости, априорного и апостериорного вывода. Во второй главе приводится первый результат, принадлежащий автору, связанный с вычислением матрицы, соответствующей линейному оператору ненормированного локального апостериорного вывода при детерминированном свидетельстве. Кроме того, в разделе, посвящённом непротиворечивости алгебраических байесовских сетей, приводится второй результат (контрпример), принадлежащий автору, о различии экстер-нальной и интернальной степенях непротиворечивости АБС.

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

Определение 1. Идеал конъюнктов (идеал цепочек конъюнкций) — это множество вида {XI, Лх;2 Л...Лх1к|0 < ^ < \г < ••. < гк < п- 1, 0 < к < и}. Идеал конъюнктов над алфавитом А, будем обозначать С а •

Определение 2. Фрагмент знаний (ФЗ) со скалярными оценками — это пара вида (С,р), где С — это идеал конъюнктов, о р — функция из С в интервал [0;1]. Фрагмент знаний обозначим С.

Определение 3. Фрагмент знаний с интервальными оценками — это структура вида (С,р), где С — идеал конъюнктов, а р — функция из С в множество интервалов вида {[а; Ь]: а, Ь £ [0; 1], а < Ь}.

Каждому из конъюнктов видахг, %12 ... х^ можно сопоставить число 21' +212 +...+ — индекс (номер) конъюнкта. Зафиксировав такой порядок на идеале конъюнктов, функции р можно сопоставить вектор оценок Рс, таким образом, что ТНЧ = р[Сх), где а — г-тый конъюнкт. Аналогичным образом можно определить вектора и Т?; + такие что р(сО = [Рс"М,Рс + й].

Используя введённые обозначения, определим непротиворечивые ФЗ следующим образом:

Определение 4. Фрагмент знаний со скалярными оценками (С, Т^) непротиворечив тогда и только тогда, когда 1П х Тс ^ О.

Определение 5. Фрагмент знаний с интервальными оценками (С, 1с~, 1ст) непротиворечив тогда и только тогда, когда

гласуем тогда и только тогда, когда существует непротиворечивый фрагмент знаний с интервальными оценками (С,Р~,Р+) такой, что Рс~ <Р~ и Р+ < Рс +.

Определение 7. На множестве всех ФЗ с интервальными оценками определим частичный порядок -< следующим, образом:

Теорема 1. Пусть (С,Рс",Рс+) — согласуемый ФЗ. Тогда ФЗ (С,Р ,Р+), построенный по следующей формуле:

((С,Рс-,Рс+) Ч (С,Р-,Р+)) Ф» ((Рс- < Р")&(Р+ < Рс+)).

0)

Р" И = тш{Рс [г]}, Р+ И = тах{Рс [г]}, 1 < 1 < 2П - 1

Юи£ 1>и£

юи £

будет непротиворечив.

Более того, построенный таким образом непротиворечивый ФЗ будет наибольшим по порядку X. Или формально:

Теорема 2. Пусть (С,Рс~,Рс+) — согласуемый ФЗ, а (С,Р",Р+) — ФЗ, построенный в предыдущей теореме (формула 2). Тогда для любого непротиворечивого ФЗ (С,Р'-,Р'+), из условия (С,Р'-,Р'+) Ч (С,Рс-,Рс+) следует (С,Р'-,Р'+) Ч (С,Р-,Р+).

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

Для ФЗ со скалярными оценками априорный вывод можно провести по формуле p(f) = (Lf, Рс), где Lf = Ц х Xf> a Xf ~ характеристический вектор, отражающий вхождение соответствующих квантов в СДНФ-представление формулы f. Для ФЗ с интервальными оценками априорный вывод сводится к поиску экстремальных значений:

p-(f)=nún(Lf,Pc) p+(f)=max(Lf,Pc). (3)

В теории ABC рассматриваются три вида свидетельств. Детерминированные свидетельства — когда известно означивание части атомов, обозначается (ci, Cj) или обозначается (i, j); Стохастическое свидетельство {(СTJ)) рассматриваются как случайный элемент, принимающий значения конкретных детерминированных свидетельств с заданными вероятностями. Неточное свидетельство ((С',Рс~,Тс+)) рассматривается как совокупность (семейство) стохастических свидетельств.

Для указанных свидетельств выделяют две задачи апостериорного вывода: первая — оценить вероятность истинности свидетельства при уже заданных оценках истинности элементов ФЗ; вторая — оценить условные вероятности истинности элементов ФЗ при предположении, что свидетельство истинно. Для стохастического и неточного свидетельств в качестве решения первой и второй задач апостериорного вывода рассматриваются соответствующие математические ожидания. Оставаясь в рамках задач линейного программирования (ЗЛП), эти математические ожидания не всегда можно вычислить точно. Поэтому предложен способ получить их приближенные накрывающие оценки.

"Утверждение 1. В случае ФЗ со скалярными оценками, решением первой задачи апостериорного вывода для свидетельства (i,j) является (т^1'^ х 1с)[0].

Теорема 3. Если p((ci, c¡)|e) /О, то формула

Рс<">= У'°хРс . (4)

{Т<1;'> х Рс)[0]

даёт решение второй задачи апостериорного вывода в случае детерминированного свидетельства.

Одним из результатов диссертации является следующая теорема о разложении оператора ненормированного локального апостериорного вывода:

Теорема 4. Матрица Т'1,''> равна тензорному произведению:

т(го) t(1,í> ох*1''* хх x(i,i)

Т' =ТП_, ®ТП_2 ® ...Т0 ,

где

~(i i) I если Хк вх°дит в съ

Tk ' =< Т~, если Хк входит в су, I Т°, иначе,

причём T+ = (¡5¡); Т=(о О ) ; Т°-(о?)'

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

min{(C<u>,Pc)} и max{(jb<w>,Pe)}. (5)

sue виг

Теорема 5. Решением второй задачи локального апостериорного вывода в случае детерминированного свидетельства и фрагмента знаний с интервальными оценками является решение серии задач линейного программирования по поиску: х D} и max {T<t;i> xD}, при условиях: {ART < D}U{D < APc+}U{InxD > 0}U{(X:(l'i>,D) = 1}U{A>0}.

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

Определение 9. Алгебраическая байесовская сеть со вторичной структурой — это граф смежности с фрагментами знаний в узлах.

Выделяются четыре степени непротиворечивости ABC: 1) глобальная непротиворечивость; 2) интернальная непротиворечивость; 3) экстернальная непротиворечивость; 4) локальная непротиворечивость. Все перечисленные степени непротиворечивости различаются. В частности, автору принадлежит доказательство следующей теоремы. Теорема 6. Экстернальная и интернальная степени непротиворечивости АБС не совпадают.

В третьей главе представляется ряд разработанных формальных описаний алгоритмов для локального логико-вероятностного вывода и вычисляются оценки сложности, выраженные в количестве ЗЛП, которые нужно решить, а также числе переменных и числе ограничений в этих задачах. В главе описываются алгоритмы поддержания степеней непротиворечивости ABC, доказывается их корректность и даются оценки вычислительной сложности. Даётся определение байесовских сетей доверия, рассматривается их вероятностная семантика, и описывается метод построения алгебраической байесовской сети со скалярными оценками истинности, обладающей вероятностной семантикой, эквивалентной исходной баесовской сети доверия. Описывается модель согласования противоречивых оценок истинности на основе понятия «накрывающая непротиворечивость». Вводятся теоретические оценки чувствительности процесса проверки согласуемости ФЗ.

В диссертации разработан ряд алгоритмов (даны формальные описания) и построены оценки их сложности. В автореферате мы приводим только оценки сложности. Здесь и далее n обозначает число атомов в ФЗ, если не оговорено иное. (Напомним, что это число, по предположению, небольшое). Важно отметить, что количество исходной информации о ФЗ — это 2п — 1 оценка для ФЗ со скалярными оценками и 2 • (2П — 1) — для ФЗ с интервальными оценками. Таким образом, заметная часть оценок, приводимые ниже, линейны относительно объёма входных данных. Здесь и далее, когда мы говорим о вычислительной сложности описываемых алгоритмов, мы считаем, что для чисел зафиксировано некоторое представление константного размера, а сложность операций с ним считается константой. В частности, это справедливо для операций с типом double.

Теорема 7. Для проверки непротиворечивости ФЗ со скалярными оценками истинности потребуется сделать не более чем Зп — 2п сложений и вычитаний и не более чем 2П сравнений с нулём.

Теорема 8. Для поддержания непротиворечивости ФЗ с интервальными оценками истинности потребуется решить не более 2(2п — 1) ЗЛП с 2П — 1 переменной, содержащих 2(2П — 1) ограничений на переменные из предметной области и 2п ограничений из аксиоматики теории вероятностей.

Теорема 9. Пусть функция f задана в виде характеристического вектора ее СДНФ Xf и задан ФЗ С со скалярными оценками, тогда для вычисления вероятности истинности формулы f, потребуется Зп — 1 сложений и вычитаний и 2п умножений.

Теорема 10. Пусть функция f задана в виде характеристического вектора ее СДНФ Xf и задан ФЗ С с интервальными оценками, тогда для вычисления оценок вероятности истинности формулы f, потребуется Зп — 2п сложений и вычитаний, 2п умножений и решение двух ЗЛП с 2П — 1 переменной, содержащих 2{2п - 1) ограничений на переменные из предметной области, и 2П ограничений из аксиоматики теории вероятностей.

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

Теорема 11. Для проведения пропагации детерминированного свидетельства в ФЗ со скалярными оценками требуется сделать не более 2п — 2п_к сложений/вычитаний и 2п_к — 1 делений на одно и то же число.

Теорема 12. Для пропагации детерминированного свидетельства в ФЗ с интервальными оценками потребуется решить 2п_к+1 задач линейного программирования, содержащие 2[2п) ограничений на переменные из предметной области, и 2п ограничений из аксиоматики теории вероятностей и одно дополнительное ограничение.

Теорема 13. Для проведения пропагации стохастического свидетельства в ФЗ со скалярными оценками истинности требуется сделать не более 2п+п'-2п'+1 +1 сложений/вычитаний, 2п~п' -Зп' — 2п' делений и2п~п'-Зп'-2п' умножений.

Теорема 14. Для пропагации стохастического свидетельства в ФЗ с интервальными оценками требуется решить 2п~п +13п' ЗЛП, содержащие 2(2п) ограничений на переменные из предметной области, 2п ограничений из аксиоматики теории вероятностей и одно дополнительное ограничение, а также сделать

2п-п'+13п' умноженийи 2n-n'+i3n'_2n+i сложений_

Теорема 15. Для пропагации неточного свидетельства в ФЗ с интервальными оценками требуется решить 2п-Т1'+,Зп' ЗЛП, содержащие 2(2п) ограничений на переменные из предметной области, и 2п ограничений из аксиоматики теории вероятностей и одно дополнительное ограничение, каждая, а также 2(2п — 1) задач линейного программирования. Каждая из этих задач над 2п — 1 переменной, содержащих 2(2п — 1) ограничений на переменные из предметной области, 2п ограничений из аксиоматики теории вероятностей.

Построены оценки сложности поддержания степеней непротиворечивости АБС:

Теорема 16. Для поддержания глобальной непротиворечивости требуется решить 2к задач линейного программирования с 2п — 1 переменной, 2к ограничениями из предметной области и 2п ограничениями из аксиоматики теории вероятностей, где п — число атомарных пропозиций, а к — число различающихся конъюнктов, входящих в АБС.

Теорема 17. Для поддержания интерналъной непротиворечивости потребуется решить 2к задан линейного программирования, каждая из которых будет содержать к переменных, 2к оценок из предметной области и не более m • 2Пш": ограничений из аксиоматики теории вероятностей, где nmax = тах(ти).

При рассмотрении байесовских сетей доверия доказывается следующая теорема.

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

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

Вводятся следующие определения, связанные с устойчивостью непротиворечивости АБС.

Определение 10. Назовём алгебраическую байесовскую сеть N на множестве переменных А = {хо,*1, • • • ,*tv-i} устойчиво согласуемой с показателем устойчивости £ > 0, если она согласуема, и для всякого конъюнкта X £ К и всяких —£<61,6и<£ байесовская сеть К£, множество ограничений которой вместо ограничения р~(Х) < р(Х) < р+(Х) содержит ограничение р~(Х) + б1 < р(Х) < р+(Х) +6и, также согласуема.

Определение 11. Назовём алгебраическую байесовскую сеть N на множестве переменных S множественно устойчиво согласуемой с показателем устойчивости е > 0, если она согласуема, и для всякого набора конъюнктов Xi, Хг,..., Х^ € N и всяких

-£<5Í,fiíl,65I8j,...,6t,6lí1<£ байесовская сеть N£l множество ограничений которой вместо ограничений вида р-(Хт) < р(Хт) <Р+(ХТ) содержит ограничения р"(Xr) + 5l <р(Хг) <p+(Xr) + 6u, также согласуема.

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

Теорема 19. Устойчиво согласуемая алгебраическая байесовская сеть с показателем устойчивости £ является множественно устойчиво согласуемой с показателем устойчивости 21г*_,, где п — количество атомарных пропозициональных переменных, над которыми построена данная АБС.

Теорема 20. Пусть АБС множественно устойчиво согласуема с показателем £. Тогда, если все интервалы оценок истинности конъюнктов этой АБС имеют длину не менее 4е, то данная АБС устойчиво непротиворечива с показателем 2е.

Понятие «накрывающая непротиворечивость» возникает при решении следующей задачи. Пусть задан фрагмент знаний с интервальными оценками Со = (C,Pq ,р0 ).

Задача — построить непротиворечивый фрагмент знаний е = (С,р~,р+) такой, что все оценки нового ФЗ будут содержать, как подынтервалы (возможно, несобственные), соответствующие оценки исходного ФЗ. При этом из всех возможных ФЗ мы будем выбирать тот, для которого набор интервальных оценок обладает минимальной суммой длин интервалов. Решение данной задачи сведено к решению одной задачи линейного программирования. Показывается, что в некоторых случаях оптимальное решение может быть не единственно.

В четвертой главе приводятся ключевые моменты реализации комплекса программ на языке С++. Описываются используемые структуры данных (классы KnovledgePattern, ABNAlphabet, ABNFormulae, Locallnferrer, KnowledgeBase и их потомки), a также основные методы, реализующие поддержание непротиворечивости ФЗ, локальный априорный вывод, локальный апостериорный вывод, поддержание всех четырёх степеней непротиворечивости ABC.

Кроме того, демонстрируются примеры использования реализованной функциональности. Подробно разбирается формирование и решение ЗЛП, возникающих в теории алгебраических байесовских сетей, с помощью разных библиотек (ILOG CPLEX и lp.solve 5.5). Описывается структура классов, реализующих представление ФЗ в программном коде. Даются разъяснения по поводу реализации поддержания непротиворечивости ФЗ, априорного вывода, апостериорного вывода для трёх типов свидетельств. Описываются дополнительные классы, реализующие специальное представление формул пропозициональной логики. Демонстрируется пример использования библиотеки для моделирования особого класса скрытых марковских моделей.

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

В заключении приводятся основные результаты работы, выносимые на защиту. ~ ' Г

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

2. Построен контрпример ABC, являющейся экстернально непротиворечивой, но не являющейся интернально непротиворечивой.

3. Получены оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод).

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

5. Сформирована математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость».

6. Разработан алгоритм построения АБС, семантически эквивалентной заданной БСД, на основе представления последней в виде дерева смежности.

7. Исследована устойчивость процесса поддержания непротиворечивости ФЗ АБС.

8. Разработан комплекс программ на языке С++, обеспечивающий локальный логико-вероятностный вывод в АБС, а так же поддержание различных степеней непротиворечивости для ABC, представленной в виде дерева смежности.

Работы автора по теме диссертации

Монографии

1. Тулупъев А.Л., Николенко С.И., Сиротпкин A.B. Байесовские сети: логико-

вероятностный подход. СПб.: Наука, 2006. 607 с.

2. Тулупъев A.A., Сиротпкин A.B., Николенко С.И. Байесовские сети доверия: логико-

вероятноствый вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб.

ун-та, 2009. 400 с.

Статьи, опубликованные в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК

3. Тулупьев А.Л., Сироткин A.B., Николенко С.И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах / / Известия высших учебных заведений: Приборостроение. 2006. Х'7. С. 20-26.

4. Тулупьев А.Л., Николенко С.И., Никитин Д.А., Сироткин A.B. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Известия высших учебных заведений: Приборостроение. 2006. №11. С. 35-39.

5. Тулупьев А.Л., Николенко С.И., Сироткин A.B. Синтез апостериорных оценок 1уи поступлении свидетельств с неопределенностью в интегрированную систему знаний о неточных вероятностях // Известия высших учебных заведений: Приборостроение. 2006. №11. С. 39-44. _

6. Тулупьев А.Л., Сироткин A.B. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. №10, т. 6. С. 85-87.

7. Сироткин A.B. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32-37.

8. Опарин В.В., Фильченков A.A., Сироткин A.B., Тулупьев А. Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник СПбГУ ИТМО. 2010. №04(68). С. 73-76.

9. Пинский М.Я., Сироткин A.B., Тулупьев А.Л., Фильченков A.A. Повышение быстродействия алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей // Научно-технический вестник СПбГУ ИТМО. 2011. №05(75). С. 69-73.

10. Фильченков A.A., Тулупьев A.A., Сироткин А.В. Структурный анализ клик максимальных графов смежности алгебраических байесовских сетей // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139-151.

11 Сироткин A.B. Вычислительная сожность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 3(18). С. 188-214.

12. Сироткин A.B., Тулупьев А.Л. Моделирование знаний и рассуждений в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности // Труды СПИИРАН. 2011. Вып. 3(18). С. 108-135.

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

13. Сироткин A.B., Николенко С.И., Тулупьев A.A. Устойчивость и множественная устойчивость глобальной непротиворечивости алгебраических байесовских сетей. Труды СПИИРАН. 2005. Вып. 2., т. 2. СПб.: Наука. 2005. С. 86-93.

14. Николенко С.И., Сироткин A.B., Тулупьев А.Л. Устойчивость непротиворечивости алгебраических байесовских сетей // Труды конференции SCM'2005, СПб., 2005. С. 101-110.

15. Николенко С.И., Сироткин A.B., Тулупьев А.Л. Минимальная непротиворечивая оболочка данных в алгебраических байесовских сетях // Сборник материалов конференции «Интеллектуальные и многопроцессорные системы - 2005. Искусственный интеллект -2005». Таганрог: НИИ МВС ТРТУ, 2005. . . .

16. Сироткин A.B., Тулупьев А.Л., Николенко С.И. Генетические алгоритмы и алгебраические байесовские сети: моделирование отбора под действием неблагоприятных факторов // Научная сессия МИФИ-2006. Сборник научных трудов. Том 3. М., 2006. С. 178-179.

17. Николенко С.И., Сироткин A.B., Тулупьев А.Л. Направленный цикл и его влияние на соседние узлы в байесовских сетях доверия // Сборник трудов всероссийской научной конференции «Нечеткие системы и мягкие вычисления». Тверь, 2006. С. 150-166.

18. Сироткин A.B. Байесовские сети доверия: дерево сочленений и его вероятностная семантика // Труды СПИИРАН. 2006. Вып. 3., т. 1. СПб.: Наука, 2006. С. 228-239.

19 Тулупьев А.Л., Николенко СМ., Сироткин A.B. Циклы в байесовских сетях: вероятностная семантика и отношения с соседними узлами // Труды СПИИРАН. 2006. Вып. 3., т. 1. СПб.: Наука, 2006. С. 240-263. .

20 Сироткин A.B., Тулупьев А.Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмов // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С.

100-111. „ . , .

21. Сироткин A.B. Алгебраические байесовские сети как вероятностно-семантическии образ байесовских сетей доверия // X Международная конференция по мягким вычислениям и измерениям (SCM'2007), Санкт-Петербург, 25-27 июня 2007 г.: Сборник докладов. Т. 1. СПб.: СПбГЭТУ «ЛЭТИ», 2007. С. 208-211.

22. Тулупьев А.Л., Сироткин A.B. Алгебраические байесовские сети: согласованность и согласуе-мость вероятностных оценок истинности // IV-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2007 г.: Сборник научных трудов. Т. 1. М.: Физматлит, 2007. С. 296-302.

23. Абрамян А.К., Сироткин A.B. Программная реализация локального синтеза согласованных оценок истинности в алгебраических байесовских сетях: java-технологии // IV-Я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2007 г.: Сборник научных трудов. Т. 1. М.: Физмат-лит, 2007. С. 258-265.

24. Тулупъев А.Л., Сироткин A.B. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Программируемые инфокомму-никационные технологии. Сборник статей / Под ред. В. В. Александрова, В. А. Сарычева М • Радиотехника, 2008. С. 85-87.

25. Сироткин A.B., Тулупъев А.Л. Матричные уравнения локального логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2008. Вып. 6. СПб.: Наука, 2008 С 134-143.

26. Тулупъев А.Л., Горшков A.C., Сироткин A.B., Тулупъева Т.В., Пащенко А.Е., Чжен Жичан Моделирование систем «Личность-Деятельность-Эффективность» на основе байесовских сетей: постановка проблемы // Труды СПИИРАН. 2008. Вып. 6. СПб.: Наука, 2008. С. 198-202.

27. Сироткин А. В., Тулупъев А. Л. Локальный априорный вывод в расширенном фрагменте знаний с вероятностной неопределенностью // Научная сессия МИФИ-2008. Сб. научн. трудов. В 15 томах. Т. 10. Интеллектуальные системы и технологии. М.: МИФИ, 2008. С. 144-145.

28. Тулупъев А. Л., Сироткин А. В. Матрично-векторное представление операций локального логико-вероятностного вывода в алгебраических байесовских сетях // Нечеткие системы и мягкие вычисления (НСМВ-2008): Сборник научных трудов Второй Всероссийской научной конференции с международным участием (г. Ульяновск, 27-29 октября 2008 г.). В 2 т Т 2 Ульяновск: УлГТУ, 2008. С. 175-185.

29. Тулупъев А. Л., Сироткин А. В. Байесовские и марковские сети: логико-вероятностный вывод в базах фрагментов знаний с неопределенностью // Научн. конф. Информационные технологии и системы, Геленджик, сентябрь 29 - октябрь 03, 2008 г.: Труды конференции. М.: ИППИ РАН.

2008. С. 440-456

30. Сироткин А. В. Сложность алгоритмов проверки и поддержания степеней непротиворечивости алгебраических байесовских сетей // Научн. конф. Информационные технологии и системы, Геленджик, сентябрь 29 - октябрь 03, 2008 г.: Труды конференции. М.: ИППИ РАН, 2008. С. 417-422

31. Сироткин А. В. Вычислительная сложность локального апостериорного вывода // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26-27 мая 2009 г.). Научные доклады. В 2-х т. Т. 1. М.: Физматлит, 2009. С. 234-242.

32. Тулупъев А. Л., Сироткин А. В. Локальный апостериорный вывод в алгебраических байесовских сетях как система матрично-векторных операций // Интегрированные модели и мягкие вычисления в искусственном интеллекте. V-я Международная научно-практическая конференция. Сборник научных трудов. В 2-х т. Т. 1. С. 425-434.

33. Сироткин А. В., Тулупъев А. Л. Комплекс программ логико-вероятностного вывода в базах фрагментов знаний: локальный алгоритм поддержания непротиворечивости // Международная конференция по мягким вычислениям и измерениям. Сборник докладов. 2009. Т. 1. СПб • Изд-во СПбГЭТУ «ЛЭТИ», 2009. С. 148-151.

34. Сироткин А. В. Алгоритмы построения алгебраической байесовской сети, семантически эквивалентной многосвязной байесовской сети доверия // Международная конференция по мягким вычислениям и измерениям. Сборник докладов. 2009. Т. 1. СПб.: Изд-во СПбГЭТУ «ЛЭТИ»

2009. С. 131-134.

35. Филъченков A.A., Тулупъев A.A., Сироткин A.B. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1(12). С. 97-118.

36. Момзикова М.П., Великодпал О.И., Пинский М.Я., Сироткин A.B., Тулупъев А.Л., Филъченков A.A.-Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 1(12). С. 134-150.

37. Филъченков A.A., Тулупъев A.A., Сироткин A.B. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2С131 С. 87-105. к '

38. Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин A.B., Тулупъев А.Л., Филъченков A.A. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2010. Вып. 2(13). С. 122-142.

39. Филъченков A.A., Тулупъев А.Л., Сироткин A.B. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3(14). С. 132-149.

40. Филъченков A.A., Тулупъев А.Л., Сироткин A.B. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4(15). С. 136-161.

41. Сироткин A.B. Проверка и поддержание непротиворечивости алгебраических байесовских сетей: вычислительная сложность алгоритмов // Труды СПИИРАН. 2010. Вып. 4(15). С. 162-192.

42. Сироткин A.B. Представление байесовской сети доверия с бинарными переменными в виде алгебраической байесовской сети // Интегрированные модели и мягкие вычисления в искусственном интеллекте. VI-я Международная научно-практическая конференция. Сборник научных трудов. В 2-х т. Т. 2. С. 992-1000.

Зарегистрированные программы для ЭВМ

43. Тулупъев А.Л., Сироткин A.B. Программа для генерации графического представления матрицы линейного оператора, преобразующего вероятности пропозиций-конъюнктов в вероятности пропозиций-квантов, и обратной ей матрицы. № госуд. регистрации 50200900179 от 22.01.2009 (информационная карта алгоритмов и программ ВНТИЦ) / Свид. об отраслевой регистрации разработки, отвечающей требованиям новизны, приоритетности и научности, (ОФАП Госкоор-центр Минобрауки РФ) № 12175 от 20.01.2009.

44. Тулупъев А.Л., Сироткин A.B. Программа для моделирования фрагмента знаний алгебраической байесовской сети, поддержания его непротиворечивости и апостериорного вывода в нем Algebraic Bayesian Network Knowledge Pattern Modeler, Reconciler and Propagator Version 01 for С++ (AlgBN KP MRP cpp.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X» 2010615242(13.08.2010). Роспатент.

45. Тулупъев А.Л., Сироткин A.B. Программа для моделирования и поддержания непротиворечивости базы фрагментов знаний, представленной в виде алгебраической байесовской сети, Algebraic Bayesian Network Knowledge Patterns Base Reconciler, Version 01 for С++ (AlgBN KPB Reconciler cpp.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X» 2010615241(13.08.2010). Роспатент.

46. Тулупъев А.Л., Опарин В.В., Сироткин A.B. Программа для обеспечения динамически меняющегося отображения фрагментов знаний алгебраической байесовской сети и построенного нпд ними минимального графа смежности Algebraic Bayesian Network Minimal Join Graph Dynamic Visualizer, Version 01 for Java (AlgBN MJGDV j.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X« 2010615244(13.08.2010). Роспатент.

47. Тулупъев A.A., Опарин В.В., Сироткин A.B. Программа для формирования экземпляра минимального графа смежности над фрагментами знаний алгебраической байесовской сети Algebraic Bayesian Network Minimal Join Graph Single Instance Composer, Version 01 for Java (AlgBN MJGSIC j.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X" 2010615243(13.08.2010). Роспатент.

48. Тулупъев A.A., Филъченкод A.A., Сироткин A.B. Программа для поддержки синтеза наборов бинарных последовательностей без поглощающих элементов при формировании алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Refiner, Version 01 for Java (AlgBN PSR j.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X« 2010614270(30.06.2010). Роспа-тент.//Вюлл. «Прогр. для ЭВМ, ВД, топол. инт. микросх.». 2010. Х»3. С. 456

49. Тулупъев A.A., Филъ\енков A.A., Сироткин A.B. Программа для визуализации операций по формированию первичной структуры алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Visualizer, Version 01 for Java (AlgBN PSV j.v.01) / Свид. о гос. per. прогр. для ЭВМ. Per. X1 2010614268(30.06.2010). Роспатент. // Бюлл. «Прогр. для ЭВМ, ВД, топол. инт. микросх.». 2010. Х*3. С. 455

50. Тулупъев A.A., Филыченкав A.A., Сироткин A.B. Программа для синтеза семейства минимальных графов смежности Algebraic Bayesian Networks Secondary Structures Generator, Version 01 for Java (AlgBN SSG j.v.01). / Свид. о гос. per. прогр. для ЭВМ. Per. X« 2010614269(30.06.2010). Роспатент.//Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2010. Х'З. С. 455-456

51. Тулупъев А.Л., Сироткин A.B. Объектно-ориентированная С++ библиотека для представления фрагмента знаний алгебраической байесовской сети и осуществления логико-вероятностного вывода в нем / Свид. о регистрации электронного ресурса, отвечающего требованиям новизны и приоритетности, (ОФЭРНиО ИИО ГАН РАО) X» 15766 от 20.05.2010. //Бюлл. «Хроники объедин.фонда электр.ресурсов «Наука и образование» Х=5. 2010. с. 26

52. Тулупъев А.Л., Момзикова М.П., Сироткин A.B. Объектно-ориентированная библиотека для оценки правдоподобия серии наблюдений в скрытых марковских моделях на основе их представления в виде алгебраических байесовских сетей / Свид. о регистрации электронного ресурса, отвечающего требованиям новизны и приоритетности, (ОФЭРНиО ИИО ГАН РАО) X« 15768 от 20.05.2010. // Бюлл. «Хроники объедин.фонда электр.ресурсов «Наука и образование» Х'5. 2010. с. 27

53. Тулупъев А.Л., Филъченков A.A., Сироткин A.B. Система для построения и визуализации семейства минимальных вторичных структур алгебраической байесовской сети, соответствующих ее первичной структуре / Свид. о регистрации электронного ресурса, отвечающего требованиям новизны и приоритетности, (ОФЭРНиО ИИО ГАН РАО) X" 15769 от 20.05.2010.//Бюлл. «Хроники объедин.фонда электр.ресурсов «Наука и образование» Х"5. 2010. с. 27

54. Тулупъев A.A., Опарин В.В., Сироткин A.B. Объектно-ориентированная программа для автоматического формирования отдельного экземпляра вторичной структуры алгебраической байесовской сети над заданной совокупностью фрагментов знаний / Свид. о регистрации электронного ресурса, отвечающего требованиям новизны и приоритетности, (ОФЭРНиО ИИО ГАН РАО) Х> 15876 от 17.06.2010. // Бюлл. «Хроники объедин.фонда электр.ресурсов «Наука и образование» Х«6. 2010. с. 25

55. Тулупъев A.A., Сироткин A.B. Объектно-ориентированная программа для моделирования и поддержания непротиворечивости баз фрагментов знаний, представленных в виде алгебраических байесовских сетей / Свид. о регистрации электронного ресурса, отвечающего требованиям новизны и приоритетности, (ОФЭРНиО ИИО ГАН РАО) Х> 15877 от 17.06.2010.//Бюлл. «Хроники объедин.фонда электр.ресурсов «Наука и образование» Х"6. 2010. с. 25-26

Тезисы научных конференций

56. Сироткин A.B. Интернальная и экстернальная степени непротиворечивости ациклических алгебраических байесовских сетей // X Санкт-Петербургская международная конферен-ция«Регионалъная информатика - 2006 (РИ-2006)», Санкт-Петербург, 24-26 октября 2006 г • Материалы конференции. СПб.: СПОИСУ, 2006. С. 52.

57. Тулупъев А.Л., Сироткин A.B. Вероятностная семантика ациклических байесовских сетей. // X Санкт-Петербургская международная конференция «Региональная информатика - 2006 (РИ-2006)», Санкт-Петербург, 24-26 октября 2006 г.: Материалы конференции. СПб.: СПОИСУ 2006. С. 56.

58. Сироткин A.B., Тулупъев A.A. Технология представления и обработки интервальных оценок вероятности в задачах принятия критичных решений // V Санкт-Петербургская межрегиональная конференция«Информационная безопасность регионов России (ИБРР-2007)», Санкт-Петербург, 23-25 октября 2007 г.: Материалы конференции. СПб.: СПОИСУ, 2007. С. 64-65.

59. Сироткин А. В. Байесовские сети: переход от условных вероятностей к совмесныи // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22-24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб., 2008. С. 51.

60. Тулупъев А. Л., Сироткин А. В. Матрично-векторный язык в задачах логико-вероятностного вывода // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22-24 октября, 2008 г.: Материалы конференции / СПОИСУ СПб., 2008. С. 54-55.

61. Сироткин А. В., Тулупъев А. Л. Постановка экстремальных задач локального логико-вероятностного вывода в алгебраических байесовских сетях на матрично-векторном языке // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22-24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб.

2009. С. 88-91.

62. Сироткин А. В. Байесовские сети доверия и семантически эквивалентные им алгебраические байесовские сети // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22-24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб., 2009. С. 85-87.

63. Сироткин А. В., Тулупъев А. Л. Матрично-векторные операции с неточными вероятностями // Научная сессия МИФИ-2009. Аннотации докладов. В 3 т. Т. 3: Информационно-телекоммуникационные системы. Проблемы информационной безопасности в системе высшей школы. Экономика, инновации и управление. М.: МИФИ, 2009. С. 85.

64. Тулупъев А. Л., Сироткин А. В. Чувствительность результатов локального априорного и апостериорного вывода в алгебраических байесовских сетях // Научная сессия НИЯУ МИФИ-

2010. Аннотации докладов. В 3 т. Т. 3: Информационно-телекоммуникационные системы. Проблемы информационной безопасности в системе высшей школы. Экономика, управление и нормативно-правовые вопросы высоких технологий. Инновационные образовательные технологии в Национальном исследовательском ядерном университете. М.: НИЯУ МИФИ, 2010. С.

Подписано в печать 10.11.2011. Формат 60 х 84/16.

Бумага офсетная. Печать цифровая. Объем 1,0 печ.л. Тираж 100 экз. Заказ №1568/0047

Копировальный центр «Василеостровский» 199004, С.-Петербург, 6-я линия ВО, д. 29.

Введение

1 Вероятностные графические модели

1.1 Введение.

1.2 Моделирование данных и знаний с неопределённостью

1.3 Вероятностная логика

1.4 Сетевые структуры над случайными элементами

1.5 Выводы по главе

2 Основные объекты и результаты теории алгебраических байесовских сетей

2.1 Введение.

2.2 Базовые объекты и индексация.

2.3 Оценки вероятностей над пропозициями.

2.4 Фрагмент знаний АБС.

2.5 Непротиворечивость фрагмента знаний.

2.6 Локальный априорный вывод.

2.7 Локальный апостериорный вывод и свидетельства

2.8 Апостериорный вывод над интервальными оценками

2.9 Недетерминированные свидетельства

2.10 Алгебраические байесовские сети и вторичная структура

2.11 Степени непротиворечивости АБС.

2.12 Выводы по главе

3 Алгоритмы логико-вероятностного вывода в алгебраических байесовских сетях 71 3.1 Введение.

3.2 Формализация алгоритмов локального вывода и их сложность

3.3 Вероятностная семантика байесовских сетей доверия

3.4 Синтез ABC на основе БСД.

3.5 Устойчивость и чувствительность локального синтеза согласованных оценок истинности.

3.6 Объемлющая непротиворечивость.

3.7 Выводы по главе

4 Комплекс программ и его применение

4.1 Введение.

4.2 Среда разработки и компоненты комплекса.

4.3 Реализация фрагмента знаний

4.4 Реализация ABC.

4.5 Реализация расширенной функциональности.

4.6 Примеры использования.

4.7 Выводы по главе

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

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

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

Применение математических моделей знаний с неопределённостью наиболее востребовано в различных прогностических системах, а также в интеллектуальных системах поддержки принятия решений. Создание программных продуктов, которые можно использовать на практике, требует не только строгой формализации математического аппарата, но также разработки и последующего анализа алгоритмов, который гарантирует, что результаты работы системы соответствуют действительности. Кроме того, в силу наличия неточности, надо чётко понимать, какая «ошибка в данных» фатальна и ведёт к неверному ответу на заданный вопрос, а какая — не повлияет на главный результат. Это влечёт необходимость построения оценок устойчивости и чувствительности логико-вероятностного вывода.

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

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

Цель исследования. Целью диссертационного исследования является оценка эффективности алгоритмов логико-вероятностного вывода в АБС. Её достижение осуществляется посредством решения еледующих задач: 1) оценить вычислительную сложность алгоритмов логико-вероятностного вывода в АБС; 2) исследовать устойчивость и чувствительность алгоритмов проверки и поддержания непротиворечивости фрагмента знаний АБС; 3) исследовать возможности расширения семантики алгебраических байесовских сетей за счёт введения новой степени непротиворечивости (накрывающей непротиворечивости); 4) исследовать возможности моделирования байесовской сети доверия (БСД) с помощью АБС.

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

Научная новизна исследования. Предложен способ вычисления матрицы, соответствующей линейному оператору ненормированного локального апостериорного вывода в случае детерминированного свидетельства, на основе выражения её через фиксированные матрицы небольшой размерности. Даны оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод), а также алгоритмов поддержания различных степеней непротиворечивости АБС (глобальной, интернальной, экстернальной). Конструктивно доказано, что экстернальная непротиворечивость АБС не гарантирует ин-тернальную непротиворечивость (построен соответствующий контрпример). Предложена математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость». Предложен алгоритм построения АБС, семантически эквивалентной заданной БСД, на основе представления последней в виде дерева смежности. Предложены подходы к оценке устойчивости процесса поддержания непротиворечивости ФЗ АБС. Создан комплекс программ на языке программирования С++, реализующий локальный логико-вероятностный вывод в АБС, а также поддержание различных степеней непротиворечивости и глобальный апостериорный вывод для АБС, представленной в виде дерева смежности.

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

Все результаты, выносимые на защиту диссертации, являются новыми.

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

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

Апробация результатов исследования. Результаты исследования были представлены автором на'следующих-конференциях:

1. VIII Международная конференция по мягким вычислениям и-измерениям ЗСМ'2005;

2. X Международная конференция по1 мягким вычислениям и измерениям ЗСМ'2007;

3. XII Международная конференция по мягким вычислениям и измерениям ЗСМ'2009;

4. Научная сессии МИФИ-2008;

5. Научная сессии МИФИ-2009;

6. Научная сессии МИФИ-2010;

7. Научная сессии МИФИ-2011;

8. Всероссийская научная конференция по нечётким системам и мягким вычислениям, Тверь, 2006;

9. Вторая Всероссийская научная конференция с международным участием Нечёткие системы и мягкие вычисления (НСМВ12008);

10. X Санкт-Петербургская международная конференция Региональная информатика-2006(РИ-2006);

11. XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ^ООв);

12. IV международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2007;

13. У-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2009 г.;

14. У1-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 16-19 мая 2011 г.;

15. V Санкт-Петербургская межрегиональная конференция- «Информационная безопасность регионов России», Санкт-Петербург, 2007;

16. Научно-практическая конференция-студентов, аспирантов, молодых учёных и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Коломна, 26-27 мая 2009 г.;

17. Научная конференция «Информационные технологии и системы», Геленджик, 29 сентября - 03 октября,, 2008 г.

Крометого, результаты диссертационного исследования неоднократно докладывались на Санкт-Петербургском общегородском научном семинаре «Информатика и компьютерные технологии» в 2005-2010 гг.

Исследования по теме диссертации были поддержаны грантом Фонда содействия отечественной науке по программе «Лучшие аспиранты РАН» (2008), грантом РФФИ (09-01-00861-а — «Методология построения-интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределённостью»), госконтрактом 02.442.11.7289 от 28.02.2006 на выполнение НИР «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы», а так же грантом «У.М.Н.И.К.» (2008, 2009), госконтракт № 5353 р/7771 от 16 августа 2007 г на выполнение НИОКР по теме «Разработка методов и программных средств для создания автоматизированных систем мониторинга и управления динамическими объектами» и госконтракт №6468р/8764 от 11.01.2009 на выполнение НИОКР «Разработка автоматизированных систем для нужд навигации, управления движением, медицины, а также их компонентов, включая датчики, приборы, алгоритмы и программное обеспечение».

Издание монографии [64] соискателя «Байесовские сети: логико-вероятностный подход», СПб.: Наука, 2006 (в соавторстве с А. Л. Тулу-пьевым и С. И. Николенко) было поддержано грантом РФФИ № 06-01-14108-д, а в 2007 г. её авторский коллектив стал лауреатом конкурса на лучшую научную книгу 2006 года (Фонд развития отечественного образования, г. Сочи).

Публикации. По теме диссертации опубликовано 64 научные работы, из них — 2 монографии (в соавторстве), прошедшие научное рецензирование, одна из них поддержана в 2006 г. издательским грантом РФФИ, 10 статей опубликованы в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК, 30 статей и докладов на конференциях, 13 зарегистрированных программ (в Роспатенте и ЦИТиС/ОФЭРНИО) и 9 тезисов научных конференций. Кроме того, часть результатов включена в ряд отчётов по НИР и НИОКР.

Личный вклад A.B. Сироткина публикациях с соавторами характеризуется следующим образом.

В монографиях [64, 85] A.B. Сироткину принадлежат результаты, связанные со сложностью алгоритмов, выявлением структуры матрицы, участвующей в матрично-векторном уравнении локального апостериорного вывода, построением контрпримеров, демонстрирующих различие интернальной и экстернальной степеней непротиворечивости АБС. Кроме того, ему принадлежит авторство алгоритма поддержания экстернальной непротиворечивости ациклической алгебраической байесовской сети и алгоритма построения алгебраической байесовской сети, являющейся семантически эквивалентным образом байесовской сети доверия с допустимыми (ненаправленными) циклами. A.B. Сироткину принадлежит формализация объемлющей непротиворечивости-и решение задачи поиска наименьшей* непротиворечивой оболочки. Наконец, в указанных монографиях приведены примеры программного кода, написанного A.B. Сироткиным.

В статьях, опубликованных в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК, результаты распределяются следующим образом. В [63] A.B. Сироткину принадлежит обобщение метода пропагации детерминированного свидетельства на случай свидетельства, состоящего более чем из одного атома, в [77] — описание семантики различных степеней непротиворечивости АБС, в [27] — результат, связанный с выражением числа ребер в минимальном графе смежности через ранг матроида, в [100] — выявление связи теоремы о множестве минимальных графов смежности и полнотой классификации владений. В [29] предложено улучшение алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей. В [4-9] — теорема 4 о непротиворечивой оболочке данных в общем случае.

В [65, 84] A.B. Сироткин, используя индексацию объектов с помощью характеристических векторов, сформировал основу для алгебраизации синтеза согласованных оценок истинности и пропагации недетерминированных свидетельств.

В других публикациях A.B. Сироткину принадлежат следующие результаты: в [24,42] — соотношения двух видов устойчивости непротиворечивости АБС и примеры; в [23] — сведение решения задачи о поиске минимальной непротиворечивой оболочки данных в общем случае к задаче линейного программирования; в [50] — способ кодирования популяции генетического алгоритма в виде АБС; в [25,66] — способ учёта информации о родителях элементов направленного цикла; в [76] — пример АБС, являющейся экстернально непротиворечивой и интернально противоречивой одновременно; в [1] — формализация алгоритмов; в [78] — описание семантики различных степеней' непротиворечивости АБС; в [45,79,80,82] — результаты, связанные с выявлением и описанием структуры матрицы, соответствующей оператору ненормированного апостериорного вывода; в [61] — формализация компонент системы на языке АБС; в [46] — формализация алгоритмов и примеры кода на С++; в [43,44] — описание способа разбора пропозициональных формул; в [20,21] — алгоритм оценки вероятности наблюдаемой последовательности на основе пропагации свидетельства в АБС; в [96-99] — формализация вторичной структуры АБС на основе понятия магистральная связность.

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

4.7 Выводы по главе

В этой главе мы описали прототип комплекса программ, реализующий основные алгоритмы локального логико-вероятностного вывода и поддержания различных степеней непротиворечивости АБС, привели примеры использования созданной библиотеки. Результаты работы прототипа полностью совпали с предсказываемыми теорией, из чего можно сделать вывод о корректности кода. Созданный прототип библиотек может быть встроен в другое программное обеспечение, что демонстрируется на примере моделирования скрытых марковских моделей в разделе 4.6. Прототип комплекса программ был зарегистрирован в РОСПАТЕНТЕ, ОФЕРНиО и ЦИТиС. Копии свидетельств приведены в приложении.

Заключение

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

1) разработан алгоритм вычисления элементов матрицы, соответствующей* линейному оператору ненормированного локального апостериорного вывода в случае детерминированного свидетельства, на основе выражения ее через фиксированные «элементарные» мат4 рицы малой размерности;

2) построен контрпример АБС, являющейся экстернально непротиворечивой, но не являющейся интернально непротиворечивой;

3) получены оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод);

4) получены оценки сложности алгоритмов поддержания различных степеней непротиворечивости АБС (глобальной, интернальной, экстернальной);

5) сформирована математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость»;

6) разработан алгоритм построения АБС, семантически эквивалентной заданной БСД, на основе представления последней в виде дерева смежности;

7) исследована устойчивость процесса поддержания непротиворечивости ФЗ АБС;

8) разработан комплекс программ на языке С++, обеспечивающий локальный логико-вероятностный вывод в АБС, а так же поддержание различных степеней непротиворечивости для АБС, представленной в виде дерева смежности. .

1. Аверкин А. Н. Модели приближенных рассуждений: обзор зарубежных исследований // Новости искусственного интеллекта. 1991. Т. 3. С. 85-92.

2. Аверкин А. Н., Костерев В. В. Триангулярные нормы в системах искусственного интеллекта // Изв. РАН. Сер. Теория и системы управления. 2000. № 5. С. 107-119.

3. Ахо А., Ульман Д. Теория синтаксического!анализа, перевода и компиляции (Том 1. Синтаксический анализ). М.: Мир, 1998. 612 с.

4. Ватыршин И. 3., Недосекин А. О., Стецко А. А., Тарасов В. В., Язенин А. В., Ярушкина Н. Г1. Нечеткие гибридные системы. Теория и практика / Под ред. Н. Г. Ярушкиной. М.: Физматлит, 2007. 208 с.

5. Веллман Р. Введение в теорию матриц. М.: Наука, Гл. редакция физико-математической литературы, 1969. 368 с.

6. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями: учебное пособие. Л.: ЛГУ, 1984. 175 с.

7. Горбатов В. А., Огиренко А. Г., Смирнов М. И. Искусственный интеллект в САПР. М., 1994. 184 с.

8. Городецкий В. И. Алгебраические байесовские сети — новая парадигма экспертных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993. С. 120-141.

9. Городецкий В. И., Тулупьев А. Л. Алгебраические байесовские сети для представления и обработки знаний с неопределенностью // 4-я Санкт-Петербургская конференция «Региональная информатика-95»: Тезисы докладов, ч. 1. СПб., 1995. С. 51-52.

10. Городецкий В. И., Тулупьев А. А. Непротиворечивость баз знаний с интервальной мерой вероятности // 4-я Санкт-Петербургская конференция «Региональная информатика-95»: Труды. СПб., 1996.

11. Городецкий В. И., Тулупьев А. Л. Формирование непротиворечивых баз знаний с неопределенностью // Изв. РАН*. Сер. Теория и системы управления. 1997. Т. 5. С. 33-42.

12. Городецкий В. И., Тулупьев А. А. Непротиворечивость 6a3í3Ha-ний с количественными мерами неопределенности // КИИ'98. Сборник научных трудов. Пущино, 1998. С. 100-106.

13. Дюбуа Д., Прад А. Теория возможностей: М.: Радио и связь, 1990. 290 с.

14. Емельянов В. В., Ясиновский С. И. Имитационное моделирование систем: Учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. 584 с.

15. Ершов Ю. А., Палютин Е. А. Математическая логика. М.: Наука, 1977. 336 с.

16. Заде Л. Понятие лингвистической переменной'и*его применение к принятию приближенных решений. М.: Мир, 1976. 165 р.

17. Заде А. Размытые множества и их применение в распознавании образов и кластерном анализе // Классификация и кластер. М.: Мир, 1980. С. 208-247.

18. Колмогоров А. Н. Основные понятия теории вероятностей. М., Фазис, 1998. 144 с.

19. Основополагающий труд, в котором А. Н. Колмогоров аксиоматизировал теорию вероятностей. Приведены данные свежего переиздания, первое издание — Москва-Ленинград, 1936 г.

20. Нгуен М. X. Моделирование приближенных рассуждений, с помощью нечеткозначной вероятностной логики // Изв. РАН. Сер. Техническая кибернетика. 1993. Т. 5. С. 94-100.

21. Николенко С. И., Сироткин А. В., Тулупъев А. Л. Устойчивость непротиворечивости алгебраических байесовских сетей // Труды конференции ЗСМ'2005. Вып. 2, Т. 2. СПб., 2005. С. 101110.

22. Николенко С. И., Сироткин А. В., Тулупъев А. Л. Направленный цикл и его влияние на соседние узлы в байесовских сетях доверия // Сборниктрудов: всероссийскойнаучной конференции «Нечеткие системы и мягкие вычисления». Тверь, 2006: С*. 150166.

23. Николенко С. И., Тулупъев А. Л. Разворот ребер как метод работы с направленными циклами в байесовских сетях // Научная сессия МИФИ-2005. Сборник научных трудов. В 15 томах. Т. 3. 2005; С. 176-178:

24. Опарин В. В., Филъченков А. А., Сироткин А. В., Тулупъев А. Л. Матроидное представление семейства графов смежности над набором фрагментов; знаний // Научно-технический вестник СПбГУ ИТМО. 2010. № 04(68). С. 73-76.

25. Осипов Г. С. Динамические: интеллектуальные системы // Ис-. кусственный интеллект и принятие решений. 2008:. № 1.

26. Сироткин А. В: Байесовские сети доверия: дерево сочленений!; и его вероятностная семантика // Труды СПИИРАН. Вып. З,, Т. 1. СПб.: Наука, 2006. С. 228-239.

27. Сироткин А. В. Алгебраические1 байесовские сети как вероятностно-семантический образ байесовских, сетей доверия //

28. X Международная конференция по мягким вычислениям и измерениям (8СМ'2007), Санкт-Петербург, 25-27 июня 2007 г.: Сборник докладов. Т. 1. СПб.: СПбГЭТУ «ЛЭТИ», 2007. С. 208-211.

29. Сироткин А. В. Модели, алгоритмы и вычислительная сложность. синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. № 11. С. 32-37. ;

30. Сироткин А. В. Проверка и поддержание непротиворечивости алгебраических байесовских сетей: вычислительная сложность, алгоритмов // Труды СПИИРАН. 2010. Вып. 4(15). С. 1624192.

31. Сироткин А. В. Вычислительная сожность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 3(18). С. 188-214.

32. Сироткин А. В., Николенко С. И., Тулупъев: А. Л. Устойчивость и множественная устойчивость глобальной непротиворечивости алгебраических байесовских сетей // Труды СПИИРАН. Вып. 2, Т. 2. СПб.: Наука, 2005. С. 86-93.

33. Сироткин А. В., Тулупъев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс: основных алгоритмов // Труды СПИИРАН. Вып. 5. СПб.: Наука, 2007. С. 100111.

34. Сирот/кии А. В., Тулупъев А. Л. Матричные-уравнения локального: логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. Вып. 6. СПб.: Наука, 2008. С. 134-143;

35. Сироткин А. В., Тулупъев А. Л. Моделирование знаний и рассуждении в условиях неопределенности: матрично-векторная формализация локального синтеза согласованных оценок истинности // Труды СПИИРАН. 2011. Вып. 3(18). С. 108-1135.

36. Сироткин А. В., Тулупъев А. Л., Николенко С. И. Генетические алгоритмы и алгебраические байесовские сети: моделирование отбора под действием неблагоприятных факторов // Научная сессия МИФИ-2006. Сборник научных трудов. Т. 3. М.,2006. С. 178-179.

37. Тулупъев А. А. Алгебраические байесовские сети: теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с.

38. Тулупъев А. А. Композиция распределений случайных бинарных последовательностей // Информационные технологии и интеллектуальные методы. 1996. Т. 1. С. 105-112.

39. Тулупъев А. А. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 с.

40. Тулупъев А. А. Метод построения и исследования баз фрагментов знаний с неопределенностью // Труды СПИИРАН. Вып. 1. 2002. Т. 1. С. 258-271.

41. Тулупъев А. А. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Труды СПИИРАН. Вып. 3. Т. 1. СПб., 2006. С. 198-227.

42. Тулупъев А. А. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с.

43. Тулупъев А. А. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство «Анатолия»,2007. 80 с.

44. Тулупъев А. А. Байесовские сети доверия: непротиворечивость направленного циклического паттерна // Международная конференция по мягким вычислениям и измерениям. Сборник докладов. 2007. Т. 1. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2007.1. С. 212-215.

45. Тулупъев А. А. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с.

46. Тулупъев А. А. Алгебраические байесовские сети: логико-вероятностная графическая модель баз фрагментов знаний с неопределённостью: дис. .д-ра физ.-мат. наук. (Санкт-Петербургский государственный университет). СПб., 2009. 670 с.

47. Тулупъев А. Л.} Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Известия высших учебных заведений: Приборостроение. 2006. № И. С. 35-39.

48. Тулупъев А. А., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 608 с.

49. Тулупъев А. А., Николенко С. И., Сиротпкин А. В. Циклы в байесовских сетях: вероятностная семантика и отношения с соседними узлами // Труды СПИИРАН. Вып. 3, Т. 1. СПб.: Наука, 2006. С. 240-263.

50. Тулупъев А. А., Сироткин А. В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. Т. 6, № 10. С. 85-87.

51. Тулупъев А. А., Сироткин А. В. Чувствительность результатов локального априорного и апостериорного вывода в алгебраических байесовских сетях // Научная сессия НИЯУ

52. Тулупъев А. А., Сироткин А. ВНиколенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Известия высших учебных заведений: Приборостроение. 2006. № 7. С. 20-26.

53. Тулупъев А. Л., Сироткин А. В., Николенко С. И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петербургского ун-та, 2009. 400 с.

54. Тулупъев А. Л., Филъченков А. А., Сироткин А. В. Программа для визуализации операций по формированию первичной структуры алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Visualizer, Version 01 for Java

55. AlgBN PSV j.v.Ol) / Свид. о гос. рег. прогр. для ЭВМ. Рег. № 2010614268(30.06.2010). Роспатент. // Вюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2010. №3. С. 455.

56. Филъченков А. А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2(13). С. 119-133.

57. Филъченков А. А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4(15). С. 192-212.

58. Филъченков А. А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1(12). С. 119-133.

59. Филъченков А. А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3(14). С. 119-133.

60. Филъченков А. А. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 2(17). С. 197-218.

61. Филъченков А. А., Тулупъев А. А., Сироткин А. В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2(13). С. 87-105.

62. Филъченков А. А., Тулупъев А. А., Сироткин А. В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4(15). С. 136-161.

63. Филъченков А. А., Тулупъев А. А., Сироткин А. В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1(12). С. 97-118.

64. Филъченков А. А., Тулупъев А. А., Сироткин А. В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3(14). С. 132-149.

65. Филъченков А. А., Тулупъев А. А., Сироткин А. В. Структурный анализ клик максимальных графов смежности алгебf