Автореферат (1149689)

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

Текст из файла

На правах рукописиЗолотин Андрей АлексеевичМатрично-векторные уравнениялокального апостериорного выводав алгебраических байесовских сетяхСпециальность 05.13.17 —Теоретические основы информатикиАвторефератдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург — 2018Работа выполнена на кафедре информатики Федерального государственногобюджетного образовательного учреждения высшего образования «Санкт-Петер­бургский государственный университет» и в лаборатории теоретических имеждисциплинарных проблем информатики Федерального государственногобюджетного учреждения науки Санкт-Петербургского института информатикии автоматизации Российской академии наук.Научный руководитель:Официальные оппоненты:Александр Львович Тулупьев,доктор физико-математических наук, доцент, профес­сор кафедры информатики Федерального государ­ственного бюджетного образовательного учреждениявысшего образования «Санкт-Петербургский государ­ственный университет»Сергей Дмитриевич Махортов,доктор физико-математических наук, доцент, заведу­ющийкафедройматематическогообеспеченияЭВМфакультета прикладной математики, информатики имеханикиФедеральногогосударственногобюджетно­го образовательного учреждения высшего образования«Воронежский государственный университет»;Илья Сергеевич Солдатенко,кандидат физико-математических наук, доцент, заме­ститель декана факультета прикладной математики икибернетики по научной работе и информатизации, до­цент кафедры информационных технологий, начальникотдела информационных технологий Федерального го­сударственного бюджетного образовательного учрежде­ния высшего образования «Тверской государственныйуниверситет»Ведущая организация:Федеральное государственное бюджетное обра­зовательное учреждение высшего образования«Санкт-Петербургский государственный техноло­гический институт (технический университет)»Защита состоится 17 мая 2018 г.

в 13:30 на заседании диссертационногосовета Д 212.232.51 при Санкт-Петербургском государственном университете поадресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28.С диссертацией можно ознакомиться в Научной библиотеке им. М.

Горь­кого Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., 7–9 и на сайте https://disser.spbu.ru/files/disser2/disser/64fRq835PC.pdf.Автореферат разослан 7 марта 2018 года.Ученый секретарьдиссертационного советаД 212.232.51,д-р физ.-мат. наук, профессорДемьянович Юрий КазимировичОбщая характеристика работыАктуальность темы. Развитие информационных технологий и усовер­шенствование методов сбора данных ставит перед исследователями в областиискусственного интеллекта задачу увеличения скорости обработки полученныхданных, что приводит к появлению новых математических моделей, структури алгоритмов над ними.

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

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

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

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

На базе лаборатории теоретических имеждисциплинарных проблем информатики СПИИРАН (ТиМПИ СПИИРАН)были формализованы понятия непротиворечивости для фрагментов знаний сбинарными, скалярными и интервальными оценками вероятностей [47], разра­ботаны методы проверки и поддержания непротиворечивости как на локальномтак и на глобальном уровне [45]. Кроме того, в контексте теории АБС были фор­мализованы локальный априорный логико-вероятностный вывод для формулыв СДНФ [48] и функциональное описание глобального апостериорного вывода вслучае ациклической сети [46].

Все вышеупомянутые теоретические изысканияподкреплены зарегистрированным комплексом программ, реализующим хране­ние, представление и процедуры ЛВВ в АБС [50].3Приблизительно в это же время исследованием АБС занимался А.В. Си­роткин. В своих работах он предложил линейный оператор ненормированноголокального апостериорного вывода и дал оценки сложности алгоритмов ло­кального ЛВВ и алгоритмов поддержания непротиворечивости, что позволилочисленно охарактеризовать эффективность АБС [49]. Все полученные резуль­таты были реализованы в комплексе программ на C++ [44] с использованиемматрично-векторных операций, что позволило увеличить производительностьЛВВ [2].Вопросы графов смежности в АБС, а также иные направления изуче­ния глобальных структур развивал А.А.

Фильченков [51]. Один из вариантовалгоритмов синтеза минимального графа смежности был предложен В.В. Опари­ным [42]. Существенный вклад в развитие и компаративный анализ реализацийалгоритмов синтеза глобальных структур также внесли Д.М. Столяров, Д.Г.Левенец, А.В. Романов, М.А. Зотов, А.И. Березин и соискатель [40; 41; 50].Объектом данного исследования являются алгебраические байесовскиесети, а предметом — алгоритмы локального апостериорного вывода оценоквероятности истинности.Целью данной работы является автоматизация локального апостериорно­го вывода в алгебраических байесовских сетях в условиях неопределенности наоснове развития формализации с помощью матрично-векторного языка.Для достижения поставленной цели достаточно было решить следующиезадачи:1.

Развить и усовершенствовать алгоритмы локального апостериорного вы­вода за счет сведения всех компонент уравнений к матрично-векторной форме;2. Сформулировать ограничения и построить задачи линейного програм­мирования для первой и второй задач апостериорного вывода в случае неточногосвидетельства или интервальных оценок вероятностей элементов фрагмента зна­ний с учетом новой матрично-векторной формализации;3. Предложить способ формирования виртуального свидетельства (при егораспространении) на основе матрично-векторных уравнений;4.

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

Сущность методологии состо­ит в формулировании математических утверждений с последующим их дока­зательством, в описании алгоритмов в сочетании с изучением их свойств, вапробации теоретических результатов, посредством их реализации в коде про­грамм и проведении вычислительных экспериментов, что, в целом, характернодля научного поиска в области математики и информатики. Методология работыоснована на методах формализации, математического моделирования, анализаи синтеза теоретического и практического материала, методах индукции, дедук­ции и методах программной инженерии.В обзорной части, а также при развитии теоретической части исследованияиспользуются объекты и методы теории вероятностей, вероятностной логики,методы линейной алгебры, булевой алгебры и теория экстремальных задач (врешении и описании задач линейного и гиперболического программирования).В основу проектирования и разработки комплекса программ легли принципы ишаблоны структурного объектно-ориентированного программирования, а также4ряд технологий, связанных с языками реализации (C# и Javascript) и средамиразработки (Microsoft Visual Studio и Microsoft Visual Studio Code).По своим подходам и методам, использованным при решении ряда задачпо построению моделей, анализу и обработке знаний с вероятностной неопреде­лённостью, диссертационное исследование относится к разделу искусственногоинтеллекта, изучающему и развивающему методы, алгоритмы и средства пред­ставления знаний с неопределенностью.Основные положения, выносимые на защиту:1.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации