П И Бидюк - Методика построения байесовских сетей - страница 1

Страницы:
1 

Інформаційні технології в наукових дослідженнях і навчальному процесі : матеріали Міжнар. наук.-практ. конф. (21-23 листоп. 2005 р.), Луганськ, 2005

МЕТОДИКА ПОСТРОЕНИЯ БАЙЕСОВСКИХ СЕТЕЙ

П.И.Бидюк, А.С.Гасанов, В.И.Литвиненко

Інститут прикладного системного аналізу НТУУ "КПІ"

Міжнародний науково-навчальний центр інформаційних технологій і систем НАН и МОН України

Херсонський морський інститут

Байесовские сети (БС) представляют собой графические модели событий и процессов на основе объединения некоторых результатов теории вероятностей и теории графов. Они тесно связаны с диаграммами влияния, которые можно использовать для принятия решений. Несмотря на свое название, эти сети не обязательно подразумевают тесную связь с байесовскими методами. Название связано, прежде всего, с байесовским правилом вероятностного вывода. БС представляют собой удобный инструмент для описания достаточно сложных процессов и событий с неопределенностями. Они оказались особенно полезными при разработке и анализе машинных алгоритмов обучения. БС доверия - это направленный ациклический граф. БС - это пара, в которой первый компонент G, является направленным нециклическим графом, соответствующий случайным переменным. С БС связано более сложное понятие независимости, которое учитывает направленность дуг. Граф записан как набор условий независимости: каждая переменная независима от ее родителей в G. Вторая компонента пары, представляет собой набор параметров, который определяет сеть. Он содержит параметр

0 , = P(XApa(X:))     для    каждого возможного

значения Xi из Xi, и pa(Xi) из Pa(Xi). Pa(Xi)

обозначает набор родителей Xt в G и pa(Xi) - родителей. Если рассмотреть больше чем один граф, тогда мы используем

PaG (X), чтобы определить X родителей в графе G. БС B определяет распределение вероятности D = (x1 ,...,XN } по X,

PB (X1Xn) = Y\j=! PB (Xi \Pa (Xi)). Самой распространенной

задачей, которая решается с помощью БС, является вероятностный вывод.

Рассмотрена последовательность построения БС в виде: анализа процесса; сбора данных и экспертных оценок; формирования базы данных; генерации топологии сети (узлы и дуги); определения априорных вероятностей и оптимизации топологии сети; обучения сети; использования сети для классификации; представления результатов пользователю.

Рассмотрены следующие типы БС. Дискретные БС - сети, у которых переменные узлов являются дискретными величинами.В БС доверия вершины представляют собой случайные переменные, а дуги - вероятностные зависимости, которые определяются через таблицы условных вероятностей. Таблица условных вероятностей каждой вершины содержит вероятности состояний этой вершины при условии состояний её "родителей. Динамические БС - сети, у которых значения узлов изменяется со временем. Они идеально подходят для моделирования временных процессов. Их преимущество в том, что они используют табличное представления условных вероятностей что облегчает представление различных нелинейных явлений. Самый простой тип динамической БС -это скрытая модель Маркова, у которой в каждом слое есть один дискретный скрытый узел и один дискретный или непрерывный наблюдаемый узел. Для задания динамической БС, нужно определить начальное распределение, топологию внутри слоя и межслойную топологию (между двумя слоями). Сети такого вида используют при распознавании речи. В этом случае узлы представляют собой фонемами при произношении слов, а узлы -буквы из которых состоит произносимое слово. Такая модель будет динамической в том смысле, что данная сеть будетпредставлять собой множество повторяющихся блоков в разные моменты времени. Непрерывные БС - переменные узлов сети являются непрерывными величинами. Во многих случаях события могут принимать любые состояния из некоторого диапазона. Непрерывные БС используются для моделирования стохастических процессов в пространстве состояний с непрерывным временем. Гибридные БС - сети, содержащие как узлы с дискретными переменными, так и с непрерывными. При использовании БС, содержащих как непрерывные, так и дискретные переменные существует ряд ограничений. Логический вывод в таких БС доверия заключается в распространении вероятностей и параметров гауссовых законов распределения по всей сети в зависимости от полученных свидетельств. В основе процесса логического вывода лежат довольно сложные математические алгоритмы, которые мы рассмотрим на простейшей двухуровневой сети для случая прямого распространения распределения вероятностей.

Обучение сети. Для описания БС необходимо определить топологию графа и параметры каждого узла. Эту информацию мы можем получить из обучаемых данных, но получение правильной топологии сети является более сложной задачей, чем получение параметров узлов. Особого подхода требует случай, когда некоторые из узлов скрыты, или мы имеем дело с некорректными или недостаточными данными. Поэтому существует 4 следующих случая обучения сети.

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

Структура известная, наблюдаемость частичная. Когда некоторые из узлов скрыты, то можно применить алгоритммаксимизации математического ожидания (ММО), для нахождения локальной оптимальной оценки максимального правдоподобия (ОМП) параметров. Основная идея алгоритма ММО состоит в том что, если бы мы знали значения всех узлов, обучение (на шаге M) было бы простым, поскольку знакомы с предыдущими. Так на шаге E, мы вычисляем ожидаемые значения всех узлов, использующих алгоритм вывода, и затем используем эти значения как если бы они были получены из наблюдений. Учитывая ожидаемое количество выполнения события, мы максимизируем параметры, а затем повторно вычисляем ожидаемое количество выполнения события и так далее. Этот итеративный метод сходится к локальному максимуму значения вероятности.

Структура     неизвестная,     наблюдаемость полная.

Наиболее вероятной моделью в данном случае является полный граф, потому что в этом случае будет задействовано наибольшее количество параметров, следовательно, такая модель будет больше всего соответствовать данным. Эта задача является НП-трудной, то есть задачей с нелинейной полиномиальной оценкой числа итераций. Поэтому обычно используют локальные алгоритмы поиска (например, "жадный" метод поиска экстремума или метод ветвей и границ, для поиска в пространстве графов.

Структура неизвестная, наблюдаемость частичная. Это самый сложный случай, когда структура неизвестна и есть скрытые переменные и некорректные данные. В этом случае используют структурный алгоритм максимизации математического ожидания (CMMO) или алгоритм сжатия границ (СГ). Алгоритм СММО соединяет в себе стандартный алгоритм ММО, который оптимизирует параметры, со структурным поиском модели отбора. Этот алгоритм обучает сети, основываясь на штрафных вероятностных значениях, которые включают значения, полученные с помощью байесовского информационного критерия, принципа минимальной  длины   описания,   а  также   значения другихкритериев. Метод СГ моделирует отсутствие данных, предполагая, что вероятность отсутствия данных находится в интервале 0 - 1. То есть производится вычисление по имеющейся информации этого интервала при отсутствии данных. После этого производится СГ интервала в точку посредством использования выпуклой комбинации точек экстремумов, основываясь на информации о неполных данных.

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

ВИКОРИСТАННЯ ЕЛЕМЕНТІВ НЕЙРО-ЛІНГВІСТИЧНОГО ПРОГРАМУВАННЯ У СУЧАСНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЯХ

НАВЧАННЯ

Т.В.Бондаренко

Луганський національний педагогічний університет імені Тараса Шевченка

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

Страницы:
1 


Похожие статьи

П И Бидюк - Методика построения байесовских сетей