Задача выбора распределения, отражающего вероятностную семантику алгебраической байесовской сети
Рассмотрение различных подходов к конструированию распределения, задаваемого алгебраической байесовской сетью. Характеристика и особенности основных подходов к выбору распределения. Специфика алгоритма поиска распределения, случай циклической сети.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 15.01.2019 |
| Размер файла | 30,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задача выбора распределения, отражающего вероятностную семантику алгебраической байесовской сети Работа выполнена при финансовой поддержке РФФИ, гранты № 12-01-00945-a, 12-01-31202-мол_а.
Фроленков К. В.
Аннотация
В работе рассматриваются различные подходы к конструированию распределения, задаваемого алгебраической байесовской сетью. Для сети, представленной ациклическим графом, показаны подходы, опирающиеся на понятие объемлющего фрагмента знаний для подсети и предположения об условной независимости. Поскольку последний подход не применим для циклической сети, предложен метод выбора распределения с максимальной энтропией и алгоритм для его конструирования.
Введение
Настоящий доклад посвящен одной из задач теории алгебраических байесовских сетей (АБС). АБС может быть использована для моделирования вероятностных взаимосвязей в сложных системах [4]. Такие системы представляются как наборы зависимых булевых случайных элементов, разбитые на поднаборы, образующие фрагменты знаний. АБС формализованы с помощью вероятностной логики [7], что позволяет говорить об оценках вероятностей пропозициональных формул, составленных на основе случайных элементов сети и о вероятностной семантике сети, то есть наборе совместных распределений данных элементов, задаваемом АБС.
Алгоритмы логико-вероятностного вывода [1], предоставленные инструментарием АБС, позволяют модифицировать параметры модели для её применения в конкретной ситуации, что осуществляется посредством передачи свидетельства в сеть. Для того чтобы ответить на вопрос, каким образом поступающее свидетельство меняет вероятностную семантику сети, необходимо предоставить метод её определения для случаев циклической и ациклической сети.
Описание модели
Фрагментом знаний (ФЗ) будем называть пару , где -- множество всех возможных положительных элементарных конъюнкций некоторого набора пропозициональных переменных (данный набор будем называть нагрузкой ФЗ и обозначать , и (через обозначим множество интервалов ), отображение, задающее нижние и верхние оценки вероятности для каждой конъюнкции из. может быть представлено парой функций и, удовлетворяющими для всех конъюнкций из.
Частным случаем для такого определения является фрагмент знаний, у которого нижние и верхние границы совпадают. Такие ФЗ будем называть ФЗ со скалярными оценками и обозначать.
АБС определяется набором ФЗ . В данной работе рассматриваются только сети, включающие ФЗ со скалярными оценками и обладающие свойством непротиворечивости, то есть такие, что существует распределение .
Подходы к выбору распределения
Случай ациклической сети
Для набора ФЗ , задающего непротиворечивую сеть можно построить [2] объемлющий ФЗ со следующими свойствами: , . Такой ФЗ обладает интервальными оценками вероятности и задаёт семейство всех возможных распределений, задаваемых сетями, содержащими заданный набор ФЗ.
Поскольку в теории АБС разработаны методы обработки интервальных вероятностей [3], возможно не разрешать неопределенность, присущую АБС, и определять её вероятностную семантику как набор всех возможных распределений, построенных с помощью алгоритма построения объемлющего ФЗ. Недостатком такого подхода является сложность операций по обработке интервальных вероятностей по сравнению с их эквивалентами для скалярного представления.
Другим подходом к определению семантики АБС является типичное [6] для вероятностных графических моделей использование предположений об условной независимости. Наборы таких предположений представляются с помощью графа. Данный граф в теории АБС называется графом смежности [5] и отражает структуру пересечений ФЗ. В вершинах такого графа располагаются ФЗ, а каждому из ребер сопоставлен сепаратор -- множество переменных, содержащихся в ФЗ, инцидентных данному ребру. Для АБС набор таких предположений определяется правилом: если для двух случайных элементов и , не лежащих в одном ФЗ, и набора сепараторов верно , если любой путь из ФЗ, содержащего , до ФЗ, содержащего , проходит по ребру, соответствующему одному из сепараторов из . В случае ациклической сети построенный таким образом набор предположений позволяет полностью задать совместное распределение для всех переменных, входящих в сеть. алгебраическая байесовская сеть циклический
Случай циклической сети
Описанный выше подход не может быть применен без изменений к сети, содержащей циклы. Для иллюстрации приведем пример АБС, состоящей из трех ФЗ с нагрузками , и . Граф смежности такой сети является полным и не определяет ни одного соотношения условной независимости, таким образом, неопределенность значения вероятности формула не может быть разрешена. Следует отметить, что циклические АБС могут задавать предположения независимости, но их недостаточно для обоснования выбора единственного распределения.
Несмотря на приведенные выше рассуждения, данный подход всё же может быть использован и для циклических сетей. Так как среди всех возможных распределений то, которое построено с применением набора предположений об условной независимости, в случае ациклической сети, обладает максимальной энтропией, будем искомое распределение по такому же принципу.
Алгоритм поиска распределения.
Подход, основанный на максимизации энтропии, позволяет выбирать единственное распределение, определяемое сетью, но требует решения оптимизационных задач с большим количеством переменных (экспоненциальным от размера цикла). Для его поиска для циклических сетей с большим числом ФЗ предложим следующий метод. Для каждого цикла:
1. Из набора ФЗ , содержащихся в цикле, случайным образом выберем один.
2. Так как сеть, состоящая из всех остальных ФЗ данного набора, является ацикличной, применим алгоритм выбора распределения на основе предположений об условной независимости, ФЗ -- результат применения такого алгоритма -- обозначим через .
3. До тех пор, пока данное действие изменяет , передадим в один из фрагментов знаний в качестве свидетельства.
Данный алгоритм является адаптацией алгоритма IPFP [8], в котором фрагмент знаний АБС рассматривается как набор ограничений на совместное распределение.
Для проверки правильности работы описанного алгоритма была реализована программа на языке java. Для всех автоматически сгенерированных примеров циклов АБС верны свойства:
1. Алгоритм завершает работу, т.е. конструируется результирующий ФЗ , который не изменяется при подаче в него произвольного ФЗ из в качестве свидетельства, из чего следует .
2. Результат не зависит от выбора фрагмента знаний на шаге 1.
3. Результат выполняет ограничения независимости, накладываемые сетью.
4. Результат совпадает с ФЗ, полученным непосредственным решением оптимизационных задач.
Заключение
В докладе были рассмотрены различные методы определения вероятностной семантики как ациклической, так и циклической АБС, продемонстрирована неприменимость подхода, основанного на представленного графом набора предположений об условной независимости переменных сети в случае наличия в АБС обособленного цикла. Данный метод обобщен на такие сети путём использования принципа максимизации энтропии. Предложен алгоритм выбора распределения, задаваемого сетью, сформулированы его свойства.
Литература
1. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Элементы мягких вычислений).
2. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
3. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та. 2009. 400 c.
4. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Известия высших учебных заведений: Приборостроение. 2006. №7. 20-26 с.
5. Фильченков А.А., Тулупьев А. Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. № 11. С. 104-129.
6. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Tech-niques. MA:MIT Press. 2009. 1231 p.
7. Nilson N. J. Probabilistic logic // Artificial Intelligence. N. 28(1). 1986. P. 71-87.
8. Vomlel. J. Methods of Probabilistic Knowledge Integration. PhD Thesis. Department of Cybernetics, Faculty of Electrical Engineering, Czech Technical University. December 1999.
Размещено на Allbest.ru
...Подобные документы
Понятие и виды статистических рядов распределения, основные формы их представления. Расчет и анализ показателей, характеризующих центральную тенденцию, вариацию, структуру и форму ряда распределения. Проведение сглаживания эмпирического распределения.
курсовая работа [698,3 K], добавлен 07.06.2011Проверка гипотезы о законе распределения. Определение значения вероятности по классам распределения случайных величин нефтеносных залежей. Расчет распределения эффективных мощностей месторождения, которое подчиняется нормальному закону распределения.
презентация [187,0 K], добавлен 15.04.2019Закон распределения случайной величины Х, функция распределения и формулы основных числовых характеристик: математическое ожидание, дисперсия и среднеквадратичное отклонение. Построение полигона частот и составление эмпирической функции распределения.
контрольная работа [36,5 K], добавлен 14.11.2010Пространства элементарных событий. Совместные и несовместные события. Функция распределения системы случайных величин. Функции распределения и плотности распределения отдельных составляющих системы случайных величин. Условные плотности распределения.
задача [45,4 K], добавлен 15.06.2012Функция распределения непрерывной случайной величины. Математическое ожидание непрерывной случайной величины, плотность распределения вероятностей системы. Ковариация. Коэффициент корреляции.
лабораторная работа [52,3 K], добавлен 19.08.2002Построение полигона относительных частот, эмпирической функции распределения, кумулянты и гистограммы. Расчет точечных оценок неизвестных числовых характеристик. Проверка гипотезы о виде распределения для простого и сгруппированного ряда распределения.
курсовая работа [216,2 K], добавлен 28.09.2011Особенности функции распределения как самой универсальной характеристики случайной величины. Описание ее свойств, их представление с помощью геометрической интерпретации. Закономерности вычисления вероятности распределения дискретной случайной величины.
презентация [69,1 K], добавлен 01.11.2013Плотность распределения непрерывной случайной величины. Характеристика особенностей равномерного и нормального распределения. Вероятность попадания случайной величины в интервал. Свойства функции распределения. Общее понятие о регрессионном анализе.
контрольная работа [318,9 K], добавлен 26.04.2013Двумерная функция распределения вероятностей случайных величин. Понятие условной функции распределения и плотности распределения вероятностей. Корреляция двух случайных величин. Система произвольного числа величин, условная плотность распределения.
реферат [325,3 K], добавлен 23.01.2011Оценки параметров распределения, наиболее важные распределения, применяемые в математической статистике: нормальное распределение, распределения Пирсона, Стьюдента, Фишера. Факторное пространство, формулирование цели эксперимента и выбор откликов.
реферат [105,5 K], добавлен 01.01.2011Определение математического ожидания и дисперсии параметров распределения Гаусса. Расчет функции распределения случайной величины Х, замена переменной. Значения функций Лапласа и Пуассона, их графики. Правило трех сигм, пример решения данной задачи.
презентация [131,8 K], добавлен 01.11.2013Расчет параметров экспериментального распределения. Вычисление среднего арифметического значения и среднего квадратического отклонения. Определение вида закона распределения случайной величины. Оценка различий эмпирического и теоретического распределений.
курсовая работа [147,0 K], добавлен 10.04.2011Вариация признаков в совокупности. Типы рядов распределения: атрибутивные и вариационные. Классификация по характеру вариации. Основные характеристики и графическое изображение вариационного ряда. Показатели центра распределения и колеблемости признака.
курсовая работа [110,0 K], добавлен 23.07.2009Определение вероятность срабатывания устройств при аварии. Расчет математического ожидания, дисперсии и функции распределения по заданному ряду распределения. Построение интервального статистического ряда распределения значений статистических данных.
контрольная работа [148,8 K], добавлен 12.02.2012Исследование стационарного распределения сетей массового обслуживания и доказательство инвариантности. Уравнения глобального равновесия и понятие эргодичности. Доказательство инвариантности стационарного распределения, а также определение его вида.
дипломная работа [439,7 K], добавлен 12.12.2009Вероятность совместного выполнения двух неравенств в системе двух случайных величин. Свойства функции распределения. Определение плотности вероятности системы через производную от соответствующей функции распределения. Условия закона распределения.
презентация [57,9 K], добавлен 01.11.2013Изучение сути и выдвижение предположения о законе распределения вероятности экспериментальных данных. Понятие и оценка асимметрии. Принятие решения о виде закона распределения вероятности результата. Переход от случайного значения к неслучайной величине.
курсовая работа [126,0 K], добавлен 27.04.2013Вычисление математического ожидания, дисперсии, функции распределения и среднеквадратического отклонения случайной величины. Закон распределения случайной величины. Классическое определение вероятности события. Нахождение плотности распределения.
контрольная работа [38,5 K], добавлен 25.03.2015Возможные варианты расчета вероятности событий. Выборочное пространство и события, их взаимосвязь. Общее правило сложения вероятностей. Законы распределения дискретных случайных величин, их математическое ожидание. Свойства биномиального распределения.
презентация [1,4 M], добавлен 19.07.2015Определение, доказательство свойств и построение графика функции распределения. Вероятность попадания непрерывной случайной величины в заданный интервал. Понятие о теореме Ляпунова. Плотность распределения "хи квадрат", Стьюдента, F Фишера—Снедекора.
курсовая работа [994,4 K], добавлен 02.10.2011
