Моделирование деятельности образовательного учреждения в статике с использованием сетей Байеса, Основы Байесовского вывода - Моделирование сетей
Основы Байесовского вывода
Сети Байеса Jensen, Finn An introduction to Bayesian networks. -- Berlin: Springer, 1996. -- ISBN 0-387-91502-8 - наглядный инструмент моделирования сложных вероятностных процессов, включающих большое количество случайных переменных, связанных причинно-следственной связью. Сети Байеса - частный случай так называемых вероятностных графических моделей Koller, D.; Friedman, N. (2009). Probabilistic Graphical Models. Massachusetts: MIT Press. p. 1208. ISBN 0-262-01319-3..
Переменная в байесовском моделировании - некая сущность, обладающая именем и областью определения Comley J. W. and Dowe D. L., "Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages", chapter 11 (pp265--294) in P. Grunwald, M. A. Pitt and I. J. Myung (eds).,Advances in Minimum Description Length: Theory and Applications, Cambridge, MA: MIT Press, April 2005, ISBN 0-262-07262-9.. Обычно, рассматриваются переменные двух типов: дискретные и непрерывные. Дискретные переменные принимают значения из некоторого конечного множества X, а непрерывные - определены на некотором подмножестве множества действительных чисел. В общем случае, переменная определяется упорядоченной парой V=(N, X), где N - имя переменной, а X - множество возможных значений. В дальнейшем мы будем рассматривать только дискретные переменные.
Центральным понятием вероятностных графических моделей является понятие фактора Дьяконов А. П., Круглов В. В. MATLAB 6.5 SP1/7/7 SP1/7 SP2+Simulink 5/6. Инструменты искусственнго интеллекта и биоинформатики. М.: СОЛОН-Пресс, 2006. 456с.. Фактор это некая функция, которая ставит в соответствие каждому возможному набору значений некого множества переменных действительное число (значение фактора):
Фактор определен на некотором упорядоченном множестве переменных, называемом областью определения (scope) фактора. Область определения обозначается так: F(A, B, C) или так: scope(F)={A, B, C}, где F - фактор, A, B и C - переменные, входящие в фактор. Заметим, что определение фактора не накладывает никаких ограничений ни на отдельные значения, ни на сумму этих значений, несмотря на то, что теория вероятности предусматривает такие ограничения. Фактор - это базовый строительный блок в вероятностных графических моделях. и представление вероятностей - всего лишь одно из возможных применений факторов. Например, определим фактор на одной переменной M, следующим образом:
Фактор, представляющий безусловную вероятность
M |
F |
"орел" |
0.5 |
"решка" |
0.5 |
Этот фактор может быть интерпретирован как безусловная вероятность того, что данная переменная примет соответствующее значение. Это возможно потому, что сумма всех значений данного фактора равна 1. В математических обозначениях данный фактор определяется следующим образом: f=("P(M)", {M}, {0.5, 0.5}). можно определить другой фактор на той же области определения:
Фактор, представляющий ненормализованную меру
M |
G |
"орел" |
20 |
"решка" |
21 |
Данный фактор может представлять, например, количество выпадений значений данной переменной в некой серии экспериментов, допустим для определения оценки вероятности значений переменной. Оба этих фактора являются корректными, но только первый из них (f) является корректным представлением безусловной вероятности.
Факторы удобны для использования в вероятностных графических моделях тем, что на них определены некоторые операции, часто выполняемые в процессе логического вывода, в довольно общей форме, что позволяет использовать их как элементарные объекты для построения логических сетей. Определим три переменные A, B, C. A=("A", {1, 2, 3}), B=("B", {1, 2}), C=("C", {1, 2}). Одной из наиболее часто используемых операций над факторами является факторное произведение. F(A, B)*G(B, C)=H(A, B, C). Произведение факторов объединяет области определения двух факторов. Значением для каждого назначения является произведение соответствующих назначений множителей.
Еще одной операцией является маргинализация: H(A, B, C) - B = J(A, C). Маргинализация позволяет исключить переменную из области определения фактора, просуммировав соответствующие значения назначений маргинализируемого фактора. Маргинализация является основой алгоритма variable elimination.
Последней элементарной факторной операцией является сокращение (reduction). H(A, B, C) / B = K(A, C).
Существенно, что, несмотря на то, что в таблице для фактора K указаны значения переменной B, значения фактора не зависят от нее, то есть областью определения является набор {A, C}. Сокращение фактора позволяет выбрать те значения фактора, которые согласуются с определенным значением одной из переменных области определения этого фактора.
Также, факторы могут представлять условные вероятности. Рассмотрим пример из медицинской диагностики. Определим бинарную переменную с=("болезнь", {"нет", "есть"}) и бинарную переменную t=("тест", {"положительный", "отрицательный"}). Переменная с показывает, есть ли у пациента определенное заболевание. а переменная t - результат диагностического теста. Допустим, что априорная вероятность данного заболевания равна 1%. Сконструируем фактор С=("P(c)", {c}, {0.99, 0.01}). Очевидно, что вероятность получения определенного результата теста зависит от того, есть ли данное заболевание у пациента, или нет, то есть мы предполагаем известной вероятность P(t|c). Допустим, что вероятность получения положительного результата теста равна 90%. Соответственно, вероятность ложноотрицательного результата равна 0,1. Вероятность получить отрицательный результат при отсутствии заболевания равна 0,8, а вероятность ложноположительного результата - 0,2. Создадим фактор, представляющий данную условную вероятность: Т=("P(t|c)", {c, t}, {0.2, 0.8, 0.9, 0.1}).
Условная вероятность
C |
T |
P(c|t) |
Нет |
Положительный |
0,2 |
Нет |
Отрицательный |
0,8 |
Есть |
Положительный |
0,9 |
Есть |
Отрицательный |
0,1 |
Графическая модель такой системы факторов в виде направленного ациклического графа G представлена на рисунке 16. Это простейшая Байесовская сеть, состоящая из двух переменных, связанных причинно-следственной связью.
Простейшая байесовская сеть
Сети Байса традиционно представляются в виде графа, в котором вершины представляют переменные, входящие в сеть, а ребра - причинно следственные связи, причем ребро направлено от причины к следствию. Это очень наглядное представление является одним из главных достоинств вероятностных графических моделей и позволяет отобразить условную вероятность в виде взаимосвязей переменных и факторов, а также зачастую построить граф по экспертным или эмпирическим данным для моделирования распределения вероятностей Korb Kevin B. Bayesian Artificial Intelligence. -- CRC Press, 2004. --ISBN 1-58488-387-1. В графе наглядно видна иерархичность условной вероятности. Если некая переменная X зависит от переменной Y, то переменная Y будет среди родителей переменной X на графе. Заметим, что причинно-следственная связь не эквивалентна зависимости переменных, которая в свою очередь, может быть прослежена на графе, используя механизм G-разделяемости (G-separation).
Рассмотрим подробнее процесс Байсовского вывода. Определим системы из трех бинарных переменных a, b, c и трех факторов: A=("P(a)", {a}, {0.6, 0.4}), B=("P(b)", {b}, {0.7, 0.3}), C=("P(c|a, b)", {a, b, c}, {0.7, 0.3, 0.9, 0.1, 0.8, 0.2, 0.6, 0.4}). Вычислим распределение полной вероятности P(a, b, c) = P(c|a, b)*P(a)*P(b): J=A*B*C.
Сеть Байеса
Байесовский вывод состоит в определении вероятности некого назначения при известном назначении другого набора переменных. Например, можно говорить о следующих вопросах к данной сети:
Какова вероятность того, что переменная X примет значение x0?
Какова вероятность того, что переменная X примет значение x0, если известно, что переменная Y принимает значение y0?
Каково распределение вероятности для переменной Х?
Каково распределение вероятности для переменной X, если известно, что переменная Y принимает значение y0? [8,15,19,20]
Заметим, что в общей форме вопрос к байесовской сети выглядит следующим образом: каково распределение полной вероятности набора переменных Q, при условии, что набор переменных E принимает назначение q? Множество переменных Q называется запросом (query) или целевыми переменными и может состоять из одной и более переменных. Множество условий E называется наблюдения (evidence) или наблюдаемыми переменными и, в общем случае, может быть пустым. Множества Q и E не должны пересекаться. Множество переменных, входящих в байесовскую сеть, но не входящих во множества Q и E называется скрытые (hidden) переменные. Семантика этих множеств довольно очевидна. Запрос - это целевые переменные, которые нас интересуют, исходя из контекста конкретной задачи. Наблюдение - это те переменные, значения которых мы можем измерить или предсказать. Скрытые переменные не являются ни тем, ни другим, но могут оказывать неявное влияние на запрос и/или на наблюдения. В таких обозначениях использование сети Байеса для логического вывода сводится к вычислению вероятности P(Q|E).
Достоинством сетей Байеса является универсальность. Единожды сконструированная, сеть может использоваться для вычисления любых корректных запросов на области ее определения, то есть не нужно изменять конструкцию сети, чтобы выполнять запросы определенного вида. Запрос является корректным, если выполняются два условия:
- - все переменные входящие в множества наблюдений и запросов входят в область определения сети: - множества Q и E не пересекаются: Ш;
Итак, каждый запрос разбивает множество переменных области определения сети на три непересекающихся множества: Q, E и H. Значение любого запроса к Байсовской сети на этих множествах может быть вычислен только из фактора, представляющего распределение полной вероятности P().
Рассмотрим несколько запросов к сети G:
P(C|A, B) - P(C|A=0, B=1). В данном случае скрытых переменных нет (пустое множество), С - целевая переменная, А и В - наблюдения. Требуется найти распределение вероятности переменной С при условии, что А=0. а В=1. Для вычисления необходимо выполнить последовательно четыре действия:
Из распределения полной вероятности J сократим переменную А со значением 0:
Сокращенный фактор
В |
С |
P'(B, C|A=0) |
0 |
0 |
0.294 |
0 |
1 |
0.126 |
1 |
0 |
0.162 |
1 |
1 |
0.018 |
Важно, что данный фактор представляет так называемую ненормализованную меру вероятности: его значения не суммируются к единице. Сумма значений данного фактора равна 0,6, что в точности соответствует вероятности P(A=0).
Нормализуем все вероятности так, чтобы в сумме они давали единицу:
Нормализованный фактор
В |
С |
P(B, C|A=0) |
0 |
0 |
0,49 |
0 |
1 |
0,21 |
1 |
0 |
0,27 |
1 |
1 |
0,03 |
Из получившегося распределения сократим переменную В со значением 1
Сокращенный фактор
С |
P'(C|A=0,B=1) |
0 |
0,27 |
1 |
0,21 |
Нормализуем вероятности:
Нормализованный фактор
С |
P(C|A=0,B=1) |
0 |
0,9 |
1 |
0,1 |
Получившееся распределение и является ответом на запрос P(C|A=0, B=1). Заметим, что данное распределение явно присутствует в таблице (3-я и 4-я строки), что очевидно. Данный конкретный запрос является тривиальным, так как распределение P(C|A, B) в явном виде использовалось нами для задания сети.
Таким образом, общий алгоритм байесовского вывода не зависит от направления причинно-следственных связей в модели и может применяться независимо от направлений ребер в графе G. Все вышесказанное верно и в общем случае. Определим общий алгоритм байсовского вывода для произвольного корректного запроса:
Построить распределение полной вероятности на множестве по формуле (1).
Для каждой скрытой переменной маргинализовать ее из этого распределения
Для каждой пары (наблюдаемая переменная, ее значение) сократить ее по соответствующему значению, а затем нормализовать вероятности.
Полученное распределение будет представлять собой полную вероятность множества целевых переменных при данном наблюдении.
Похожие статьи
-
Стандарт Bluetooth (802.15.1) на сегодняшний день хорошо развит и применяется для связи мобильных телефонов, КПК, периферии. Однако он не рассчитан на...
-
Расчет энергопотребления и времени работы, Выводы - Моделирование беспроводных сенсорных сетей
Энергопотребление - один из ключевых вопросов для сенсорных сетей, так как устройства питаются в основном от батареек. Информация о потреблении энергии в...
-
- Проектирование автоматизированного рабочего места (АРМ) воспитателя специализированного ДОУ. Информационная среда ДОУ способствует достижению целей...
-
Классификация компьютерных сетей - Теоретические основы информационных процессов и систем
Для классификации компьютерных сетей используются разные признаки, выбор которых заключается в том, чтобы выделить из существующего многообразия такие,...
-
Моделирование различных вычислительных систем можно разделить на два главенствующих класса: матечатическое моделировании и имитационное. Математическое...
-
1. Изучение планировки зданий; 2. Составление логической схемы административного корпуса; 3. Составление логической схемы жилых зданий; 4. Объединение...
-
Данная компания является ведущем производителем оборудования и выпуска квалифицированных специалистов в мире. Это одна из самых оцененных компаний в...
-
Наиболее распространенная форма - ЭВМ. Раньше чаще использовались вычислительные центры (ВЦ). Вычислительный центр - организуется и специализируется на...
-
Введение, Теоретические основы - Разработка консольного приложения на языке С++
Данная работа посвящена созданию своего рода базы данных на языке программирования С++. База данных содержит информацию о сотрудниках этого предприятия,...
-
ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ База данных как основа информационного обеспечения В состав информационного, программного и математического обеспечения...
-
1 Характеристика технологий xDSL - Разработка корпоративной сети на основе технологий xDSL
HDSL (High-bit-rate DSL) , или технология высокоскоростной цифровой абонентской линии, - это первенец семейства xDSL, разработанный в конце 80-х гг....
-
Оборудование корпоративных сетей - Разработка корпоративной сети на основе технологий xDSL
Корпоративная сеть - это достаточно сложная структура, использующая различные типы связи, коммуникационные протоколы и способы подключения ресурсов. Все...
-
Введение - Разработка корпоративной сети на основе технологий xDSL
Корпоративный сеть интерфейс Любая организация - это совокупность взаимодействующих структурных элементов (подразделений), каждый из которых может иметь...
-
Актуальность Сегодня всемирная популярность социальных информационных сетей продолжает набирать обороты, все большее пользователей не может отказать себе...
-
Описание стандарта IEEE 802.15.4 - Моделирование беспроводных сенсорных сетей
Стандарт 802.15.4 предназначен для организации двух нижних уровней эталонной модели OSI в беспроводной сенсорной сети - физический (PHY) и канальный...
-
Или Живой журнал. - Возможности использования социальной сети для проведения SMM-активности
Представляет собой глобальный сервис блогов, многоязычный, позволяет создавать раздел информационных сообщений и ленты новостей, а также разные...
-
Создание конфигурационного файла - Моделирование беспроводных сенсорных сетей
Для моделирования сети необходимо создать файл конфигурации omnetpp. ini: [General] Network = SN Include../Parameters/Castalia. ini Sim-time-limit =...
-
Выбор стандарта - Моделирование беспроводных сенсорных сетей
Различных стандартов беспроводных сетей существует великое множество, однако их всех можно подразделить на три группы: WPAN (Wireless Personal Area...
-
1 Беспроводная сенсорная сеть В настоящее время бурно развивается технология беспроводных сенсорных сетей. Беспроводные сенсорные сети - это...
-
Введение, Постановка задачи - Моделирование беспроводных сенсорных сетей
Данная квалификационная работа посвящена моделированию беспроводных сенсорных сетей (БСС) на базе современных маломощных модулей. Рассматриваются...
-
Плюсы и минусы - Разработка корпоративной сети на основе технологий xDSL
Недостаток приведенной схемы состоит в том, что возрастает нагрузка на сетевое оборудование вследствие троекратного прохода одного и того же трафика...
-
Схема сети - Разработка корпоративной сети на основе технологий xDSL
Все рабочие станции центрального офиса и часть серверов подключаются к одному коммутатору. Прочее серверное оборудование центрального офиса работает...
-
Система IP-адресации. - Использование компьютерных сетей
Для организации всемирной сети нужна хорошая система адресации, которая будет использоваться для направления информации всем адресатам. Союз Internet...
-
Сетевые протоколы, используемые в сети Интернет. - Использование компьютерных сетей
Иерархия протоколов TCP/IP 5 Application level 4 Transport level 3 Internet level 2 Network interface 1 Hardware level Протоколы TCP/IP широко...
-
Технологии с кольцевой архитектурой - Использование компьютерных сетей
Технологии Token Ring и FDDI используются для создания эстафетных сетей с маркерным доступом. Они образуют непрерывное кольцо, в котором в одном...
-
Протокол(Protocol) Строго определенная процедура и формат сообщений, допустимые для коммуникаций между двумя или более системами через общую среду...
-
Сетевые интерфейсные платы, Концентраторы - Использование компьютерных сетей
Сетевые интерфейсные платы (NIC, Network Interface Card) устанавливаются на настольных и портативных ПК. Они служат для взаимодействия с другими...
-
Универсальная платформа - Разработка корпоративной сети на основе технологий xDSL
Многие обозреватели рынка телекоммуникационного оборудования отмечают, что будущее - за универсальными и гибкими решениями. Это справедливо и для опорных...
-
Конфиденциальность очень важна для некоторых организаций, так как то, что обычно считается безобидной информацией, может на самом деле содержать полезные...
-
Выбор средства моделирования, Выводы - Моделирование беспроводных сенсорных сетей
Наиболее перспективными в плане дальнейшей поддержки и развития представляются модели open-zb и Castalia. Особое внимание необходимо обратить на модель...
-
Правил по техники безопасности и гигиенические рекомендации при использовании средств ИКТ в ДОУ и профессиональной деятельности На сегодняшний день для...
-
Моделирование сети, Выводы - Моделирование беспроводных сенсорных сетей
Для моделирования сети в терминале вводим команду: Alex@alex:~$ cd omnetpp41/samples/diplom/Simulations/dipl Для перехода в директорию, содержащую файл...
-
Сравнительный анализ известных инструментов моделирования Основной целью выбора стандарта функционального проектирования является соответствие...
-
Имитационная модель автоматизированной информационной системы специального назначения должна отвечать данного вида деятельности двум основным требованиям...
-
Для поддержки работы педагогического коллектива со стороны учащихся и родителей была разработана специальная программа обучения учащихся эффективной...
-
Выводы, Введение - Моделирование беспроводных сенсорных сетей
При данных показателях производство можно считать рентабельным. 4. Охрана труда Введение Охрана труда - это система обеспечения безопасности жизни и...
-
В третьей главе "Проектирование школьной социальной сети как среды организации внеурочной деятельности учащихся" представлены результаты формирующей...
-
Паттерн репозиторий - Программирование на языке C++
Паттерн Repository Посредничает между уровнями области определения и распределения данных (domain and data mapping layers), используя интерфейс, схожий с...
-
Как записываются алгоритмы на школьном алгоритмическом языке - Основы программирования
Основные служебные слова Алг (алгоритм) Сим (символьный) Дано Для Да Арг (аргумент) Лит (литерный) Надо От Нет Рез (результат) Лог (логический) Если До...
-
Сеть Петри это двудольный направленный граф с маркировкой, ребра которого задают причинно-следственные отношения "события-условия" и именуются дугами....
Моделирование деятельности образовательного учреждения в статике с использованием сетей Байеса, Основы Байесовского вывода - Моделирование сетей