دورية أكاديمية
СИНТЕЗ ВТОРИЧНОЙ СТРУКТУРЫ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ: ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ И СТАТИСТИЧЕСКАЯ ОЦЕНКА ЕГО СЛОЖНОСТИ
| العنوان: | СИНТЕЗ ВТОРИЧНОЙ СТРУКТУРЫ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ: ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ И СТАТИСТИЧЕСКАЯ ОЦЕНКА ЕГО СЛОЖНОСТИ |
|---|---|
| المؤلفون: | ЗОТОВ М.А., ЛЕВЕНЕЦ Д.Г., ТУЛУПЬЕВ А.Л., ЗОЛОТИН А.А. |
| بيانات النشر: | Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» |
| سنة النشر: | 2016 |
| المجموعة: | CyberLeninka (Scientific Electronic Library) / Научная электронная библиотека «Киберленинка» |
| مصطلحات موضوعية: | БАЙЕСОВСКИЕ СЕТИ,СИНТЕЗ ВТОРИЧНОЙ СТРУКТУРЫ,ЖАДНЫЙ АЛГОРИТМ,ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ,ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ,СТАТИСТИЧЕСКАЯ ОЦЕНКА,МИНИМАЛЬНЫЙ ГРАФ СМЕЖНОСТИ,BAYESIAN NETWORKS,SECONDARY STRUCTURE SYNTHESIS,GREEDY ALGORITHM,INCREMENTAL ALGORITHM,COMPUTATIONAL COMPLEXITY,STATISTICAL ESTIMATE,MINIMAL JOINT GRAPH |
| الوصف: | Предложен улучшенный алгоритм синтеза вторичной структуры алгебраических байесовских сетей, представленной в виде минимального графа смежности. Алгоритм отличается от предложенных ранее тем, что основывается на принципе инкрементализации, использует лишь особым образом отобранные ребра, исходящие из новой вершины, исключает оставшиеся избыточные ребра с помощью жадного алгоритма. Корректность работы инкрементального алгоритма обоснована математическим доказательством. Сравнение вычислительной сложности нового (инкрементального) алгоритма и двух известных (жадного и прямого) произведено с помощью статистических оценок сложности, построенных на основе выборки значений отношения времени работы программных реализаций двух сравниваемых алгоритмов. Теоретические оценки сложности жадного и прямого алгоритмов были получены ранее, но непригодны для осуществления компаративного анализа, поскольку опираются на скрытые характеристики вторичной структуры, которые можно вычислить лишь при ее построении. Для минимизации влияния случайных факторов при вычислении отношений использовано усредненное время работы программной реализации, полученное за счет K ее запусков на одном и том же наборе нагрузок. Выборка значений отношений сформирована для M таких наборов одинаковой мощности N. По выборке вычислены среднее геометрическое со статистиками, характеризующими разброс: границы 97% доверительного интервала, а также первый и третий квартили. Приведено описание алгоритмов стохастической генерации набора нагрузок заданной мощности, а также сбора статистических данных и вычисления статистических оценок отношения времени работы прямого и жадного алгоритма ко времени работы инкрементального алгоритма. Выполнена серия экспериментов, в которых N изменяется в диапазоне 1, 2…9, 10, 26, 42… 170. Результаты серии экспериментов, визуализированные с помощью графиков с использованием библиотеки Highcharts, показали, что инкрементальных алгоритм по скорости превзошел прямой и жадный алгоритмы, причем на диапазоне мощностей наборов нагрузок 10-170 ... |
| نوع الوثيقة: | text |
| وصف الملف: | text/html |
| اللغة: | unknown |
| الإتاحة: | http://cyberleninka.ru/article/n/sintez-vtorichnoy-struktury-algebraicheskih-bayesovskih-setey-inkrementalnyy-algoritm-i-statisticheskaya-otsenka-ego-slozhnostiTest http://cyberleninka.ru/article_covers/16414148.pngTest |
| رقم الانضمام: | edsbas.4A69AAE |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |