Диссертация (1149691), страница 22
Текст из файла (страница 22)
Компонентывекторов, используемых в уравнениях апостериорного вывода, выраженыс помощью битовых операций, создавая возможность использования отложенных вычислений. В заключение приведены примеры вычисленияуказанных векторов для некоторых свидетельств.Были рассмотрены случаи обработки данных с неопределенностью,а именно пропагация неточного свидетельства в фрагменты знаний с интервальными оценками вероятностей.
Для каждого из типов фрагментовзнаний построены задачи линейного программирования, решение которыхдает апостериорные оценки вероятностей элементов фрагментов знаний.Для каждого из видов алгоритмов пропагации свидетельства предложеныоценки сложности и доказана их корректность.Также проведен анализ чувствительности уравнений апостериорноговывода и даны точные и накрывающие оценки чувствительности первойзадачи апостериорного вывода для стохастического и детерминированногосвидетельств. Каждый из описанных случаев снабжен доказательством.Наконец, рассмотрена задача распространения влияния поступившегосвидетельства по алгебраической байесовской сети.
Предложено 2 подхода к построению матрично-векторной формы уравнения, описывающегопропагацию свидетельства из одного фрагмента знаний в другой. Полученные уравнения позволяют уйти от функционального описания пропагациисвидетельства и тем более позволяют избежать погружения сети в объемлющий фрагмент знаний. Данный результат дает возможность уйтиот экспоненциального роста объема вычислений при увеличении алгебраической байесовской сети, а матрично-векторный подход существенноупрощает дальнейший анализ чувствительности и устойчивости модели.126Глава заканчивается параграфом, описывающим инкрементальныйподход к алгоритмам синтеза глобальных структур. В частности рассматривается алгоритм инкрементального синтеза минимального графасмежности, необходимого для проведения глобального вывода. Кроме тогорассмотрен подход к выделению множества всех измененных сепараторовв третичной структуре АБС при перестроении четвертичной структуры,что дает возможность также использовать принцип инкрементализации валгоритме синтеза четвертичной структуры.В последней главе будет описан комплекс программ, реализующийбольшую часть полученных теоретических результатов, даны примеры егоиспользования, а также приведены снимки экрана десктопного и веб-приложения с описанием функциональности присутствующих на них элементов.127Глава 4.
Комплекс программ4.1ВведениеЯвляясь отечественной разработкой, алгебраические байесовские сетиотносятся к тому же классу, что и байесовские сети доверия. Для операцийс моделями теории БСД существует множество свободно распространяемых и проприетарных пакетов, библиотек и полноценных комплексов.
Кним относятся:1. Bayes Net Library [6]2. Banjo [5]3. Bayesian Network tools in Java (BNJ) [7]4. UnBBayes [72]5. DLib [17] и другиеВ работе соискателя с соавторами [89] указывается, что в настоящее времясуществует ряд программных решений для компьютеризированного представления алгоритмов и структур теории АБС. В 2008 году ТулупьевымА.Л. был реализован комплекс программ на языке Java [141; 153; 167],включающий в себя базу данных для хранения структуры АБС, оценоквероятностей элементов фрагментов знаний, а также иную мета-информацию. С введением Сироткиным А.В.
матрично-векторных уравнений в 2009году, программный комплекс подвергся реинжинирингу [125; 162; 163]. Этинаработки [167] к настоящему моменту перестали отвечать ожиданиям иопираются на состояние теории десятилетней давности, хотя уже накопились существенные изменения [103; 165].В предыдущих главах рассмотрена теория алгебраических байесовских сетей и исследован математический аппарат локального логико-вероятностного вывода в них. Улучшенное матрично-векторное представлениеапостериорного вывода позволяет проще представлять и оперироватьданными с неопределенностью и упрощает программную реализацию алгоритмов.
Последним этапом, логично завершающим исследование, являетсяпроектирование, разработка и апробация комплекса программ [34; 111;128182], реализующего описанные ранее, улучшенные и полученные в ходе дипломной работы алгоритмы. Комплекс программ должен включать в себяследующие функциональности:– представление фрагментов знаний в алгебраических байесовскихсетях над идеалами конъюнктов, а также фрагментов знаний надпропозициями-квантами;– локальный синтез согласованных оценок истинности (проверка иподдержание локальной непротиворечивости, локальный априорный вывод);– локальный апостериорный вывод (вероятность появления данногосвидетельства над фрагментом знаний, вычисление апостериорныхвероятностных оценок истинности).4.2Математическая библиотекаОсновополагающим компонентом программного комплекса является [89] математическая библиотека, реализующая представления фрагментов знаний и свидетельств для различных моделей, лежащих в алгоритмылогико-вероятностного вывода над ними.4.2.1Средства разработкиВ качестве языка программирования программного комплекса былвыбран язык C#.
На выбор повлиял ряд факторов: свободно распространяемая среда разработки и компилятор, наличие сборщика мусора,освобождающего память от неиспользуемых объектов, а также большоечисло свободно распространяемых библиотек для решения задач линейного программирования.Основной средой разработки была выбрана Microsoft Visual Studio2013 Express [73]. Данная среда разработки обладает широким набором стандартных функций, упрощающих написание кода, а также дает возможность129расширения функциональности проекта с помощью менеджера пакетовNuGet [52], предоставляя лучшие функции коммерческого продукта в свободно распространяемой версии. Среди прочих основных возможностей,использованных в проекте можно обозначить такие, как поддержка системы контроля версий Git [23], дающая возможность расположить проектв удаленном репозитории Github, автоматизированный рефакторинг кода [36] и генерация аннотаций к методам и классам.Как упоминалось ранее, одним из преимуществ C# является большоечисло библиотек и пакетов, облегчающих выполнение различных задач.В рамках дипломного проекта были использованы библиотека для решения задач линейного программирования lp_solve 5.5 [69], распространяемаяпод лицензией GPL, и библиотека для решения задач линейной алгебры Math.NET Numerics [39], бесплатно распространяемая под лицензиейMIT/X11.
Последняя библиотека включает в себя методы, реализующиетакие операции линейной алгебры, как сложение, вычитание, произведение матриц, произведение Кронекера, а также умножение матрицы наскаляр. Кроме того, в составе библиотеки присутствуют различные видыматриц, такие как диагональная, плотная, разреженная. Выбор подходящей в контексте решаемой задачи матрицы существенно ускоряет процессвычисления результата за счет оптимизации вычислительных операций.4.2.2Основные классы и методыСогласно объектно-ориентированной парадигме программирования [21; 40; 41], каждая сущность, тип данных или решение задачиреализованы в виде отдельного класса. Таким образом, классы комплексапрограмм можно разбить на следующие пространства имен:– kp — содержит описание структуры данных для хранения фрагментов знаний над идеалами конъюнктов и пропозициями-квантамидля трех видов оценок вероятностей (бинарные, скалярные, интервальные);130–evidence — интерфейсы и классы, содержащие описание структурыданных для хранения свидетельств (бинарного, скалярного и неточного), основанное на структуре фрагмента знаний;– inferrer — интерфейсы и классы, содержащие реализацию алгоритмов локального априорного вывода, проверки и поддержаниянепротиворечивости фрагментов знаний;– propagator — интерфейсы и классы, содержащие реализацию алгоритмов локального апостериорного вывода.Описанные выше пакеты включают в себя следующие базовые классы:– BaseKnowledgePattern — базовый для всех типов фрагментов знанийкласс, реализующий общий функционал работы с оценками вероятностей и объявляющий методы, реализация которых зависит оттипов фрагментов знаний;–BinaryKnowledgePattern, ScalarKnowledgePattern, IntervalKnowledgePattern— классы-потомки BaseKnowledgePattern, описывающие конструкторыи реализующие методы работы с оценками вероятностей, объявленные в классе-родителе;– BaseInferrer — базовый класс, реализующий общую функциональность для алгоритмов локального априорного вывода и поддержания непротиворечивости;– BinaryInferrer, ScalarInferrer, IntervalInferrer — классы-наследникиBaseInferrer, реализующие алгоритмы априорного вывода и поддержания непротиворечивости для конкретных типов фрагментовзнаний;– BinaryEvidence, ScalarEvidence, IntervalEvidence — наследники классовBinaryKnowledgePattern, ScalarKnowledgePattern, IntervalKnowledgePatternсоответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
