Процедура распознавания на байесовских сетях
Приведены алгоритмы определения структуры байесовской сети в виде дерева или леса. Рассмотрены байесовские процедуры распознавания, построенные на обучающих выборках с использованием оценок переходных вероятностей заданных порядков. Описано поліноміальні алгоритми визначення структури байєсівської м...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2010 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84594 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Процедура распознавания на байесовских сетях / А.А. Вагис // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 124-130. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860038484325040128 |
|---|---|
| author | Вагис, А.А. |
| author_facet | Вагис, А.А. |
| citation_txt | Процедура распознавания на байесовских сетях / А.А. Вагис // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 124-130. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Приведены алгоритмы определения структуры байесовской сети в виде дерева или леса. Рассмотрены байесовские процедуры распознавания, построенные на обучающих выборках с использованием оценок переходных вероятностей заданных порядков.
Описано поліноміальні алгоритми визначення структури байєсівської мережі у вигляді дерева або лісу. Для відомої структури байєсівської мережі розглянуто байєсівські процедури розпізнавання, які побудовано на навчаючих вибірках за допомогою оцінок перехідних ймовірностей.
The polynomial algorithms of determination of Bayesian network structure are described as a tree or polytree. For the known Bayesian networks structure, Bayesian recognition procedures built on teaching samples with the use of estimations of transitional probabilities are considered.
|
| first_indexed | 2025-12-07T16:54:32Z |
| format | Article |
| fulltext |
124 Компьютерная математика. 2010, № 2
Ýêñïåðòíûå ñèñòåìû,
ìåòîäû èíäóêòèâíîãî
âûâîäà
Приведены алгоритмы определе-
ния структуры байесовской сети
в виде дерева или леса. Рассмот-
рены байесовские процедуры рас-
познавания, построенные на обу-
чающих выборках с использова-
нием оценок переходных вероят-
ностей заданных порядков.
А.А. Вагис, 2010
ÓÄÊ 519.68
À.À. ÂÀÃÈÑ
ÏÐÎÖÅÄÓÐÛ ÐÀÑÏÎÇÍÀÂÀÍÈß
ÍÀ ÁÀÉÅÑÎÂÑÊÈÕ ÑÅÒßÕ
Введение. В работах специалистов Институ-
та кибернетики имени В.М. Глушкова НАН
Украины построена теория статистического
оценивания дискретных процедур распозна-
вания [1]. При решении задач распознавания
определяющим моментом является структура
описания объекта. Если она известна, то не
представляет труда по обучающей выборке
построить байесовские процедуры, как это
проделано для цепей Маркова, и независи-
мых признаков. Задача распознавания рас-
сматривается с точки зрения минимизации
среднего риска. Такая постановка является
обобщением классических задач, решаемых
на основе метода наименьших квадратов, в
том смысле, что наблюдению объекта может
соответствовать не одно, а несколько состоя-
ний объектов.
Каждый наблюдаемый объект описывается
конечным набором признаков, принимаю-
щих конечное число значений. Описанию
объекта может соответствовать конечное
число состояний (исходов экспериментов),
которые наблюдаются с неизвестными веро-
ятностями. В результате проведенных опы-
тов над объектами формируется конечная
обучающая выборка, состоящая из множест-
ва описаний объектов и их состояний.
Требуется оценить эффективность процеду-
ры распознавания, которая по измерениям
набора признаков любого следующего объ-
екта и обучающей выборке определяет
состояние наблюдаемого объекта. Теория
сложности дискретных задач распознавания
развивается на основе байесовского подхода.
ПРОЦЕДУРЫ РАСПОЗНАВАНИЯ НА БАЙЕСОВСКИХ СЕТЯХ
Компьютерная математика. 2010, № 2 125
В работе [1] выбран прямой подход к построению методов распознавания:
исследуются такие структуры описания объектов, для которых можно построить
эффективные процедуры распознавания. Вместо выполнения достаточно слож-
ных процедур минимизации эмпирического риска или других функционалов ка-
чества применяется простое байесовское правило классификации, которое ис-
пользуется для решения задач большой размерности. Показано, что байесовская
процедура распознавания является оптимальной для объектов с независимыми
признаками.
Байесовская процедура распознавания обладает многими свойствами, кото-
рые присущи иммунной системе человека: самообучаемая, обладает памятью,
ошибкоустойчивая и самотестирующая, обладает параллельным характером вы-
числений и относительно проста. По нашему мнению, байесовские процедуры
могут быть эффективно использованы в процессе разработки искусственных
иммунных систем для решения широкого спектра прикладных задач.
Наиболее общим аппаратом для извлечения структур описания объектов из
данных является аппарат байесовских сетей. За последние 10 лет выпущено бо-
лее двух десятков монографий по байесовским сетям. Были проведены исследо-
вания вероятностных моделей зависимостей, структурированные ациклически-
ми орграфами (АОГ-модели, байесовские сети). АОГ-модели являются нагляд-
ным и компактным языком представления систем зависимостей. Это эффектив-
ный аппарат отображения связей (вплоть до причинно-следственных отноше-
ний) и инструмент вероятностных рассуждений от свидетельств (в экспертных
системах). Эти свойства делают АОГ-модели средством решения разнообразных
задач, среди которых: медицинская и техническая диагностика, распознавание
речи, прогнозирование последствий решений и действий, анализ данных в эко-
нометрике, биоинформатике и т. д. Для решения исследовательских и прогноз-
но-аналитических задач необходимо вывести структуру модели на основе из-
вестной выборки данных наблюдений. Известно, что задача вывода АОГ-модели
из данных в общем случае – NP-сложная. Вычислительные сложности становят-
ся уже серьезной практической проблемой, когда число переменных модели
достигает нескольких десятков.
При выводе структуры АОГ-модели из данных возникает проблема поиска и
подбора сепараторов (фактов условной независимости между переменными в
модели), которая решается на основе, так называемого, “constraint-based” (или
сепарационного) подхода. Поиск сепараторов в сложных структурах выполняет-
ся комбинаторным путем с помощью статистических критериев. В работах [2, 3]
были разработаны подходы к построению минимальных сепараторов модели.
Полученные результаты открывают новые возможности по пути построения эф-
фективных методов вывода структуры байесовской сети из имеющихся стати-
стических данных и полученного набора минимальных сепараторов.
В пионерской работе [4] рассматривались вопросы извлечения структуры
описания из статистических данных. Используя методологический принцип
экономии в научном объяснении, известный как «бритва Оккама», вначале
А.А. ВАГИС
Компьютерная математика. 2010, № 2 126
предпочтение было отдано простейшей структуре, которая описывается лишь
небольшим числом зависимостей. Такой разреженной структурой является
сеть – дерево, она имеет минимальное число связей между переменными. Дере-
во – единственная структура графа, в которой связи могут быть ориентированы
таким образом, что каждая переменная зависит не более чем от одной родитель-
ской переменной. Заметим, что аналогичная ситуация присуща однородным це-
пям Маркова.
Если каждая переменная iX принимает r значений, то случайный вектор
),...,( 1 nxx=x может принимать nr значений. Если вероятностное распределение
P неизвестно и имеется независимая выборка 1x ,…, sx , то для оценивания
)(xP требуется вычислить и сохранить nr величин относительных частот век-
торов x среди наблюдений 1x ,…, sx . Однако, если компоненты 1X , …, nX
независимы, т. е.
( )i
n
i
n xPxxP ∏
=
=
1
1 ),...,( ,
то каждая вероятность )( ixP вычисляется с помощью относительной частоты
ii xX = , поэтому для определения )(xP требуется провести только rn ⋅ вычис-
лений. Поскольку предположение о независимости часто не выполняется, то це-
лесообразно исследовать модели, для которых требуется умеренное число вы-
числений и хранений данных. Вероятностное распределение для зависимых пе-
ременных в виде дерева является одной из таких моделей.
Вероятностное распределение дерева )(xP t записывается в виде произве-
дения 1−n условных вероятностей
( )∏
=
=
n
i
iji
t xxPxP
1
)()( , (1)
где )(ijX – родительская переменная для iX при некоторой ориентации дерева.
Корень 1X не имеет родителей, ( ) ( )101 xPxxP = . Поэтому число параметров,
необходимых для определения вероятностного распределения дерева, равно
( ) ( ) ( )111 −+−− rnrr , а именно ( )1−rr параметров для каждой из ( )1−n матриц
условных (переходных) вероятностей и ( )1−r параметров для корня дерева.
Таким образом, байесовская процедура для сети – дерево строится аналогично
процедуре распознавания для цепи Маркова [1, 5]. Для ее построения использу-
ются оценки переходных вероятностей
( ) ( )
( )
, ,ˆ , ,
,
j i
i j
j
k x x l
P x x f l
k x l
= = (2)
где lf = – состояние объекта, ( )lxk j , , ( )lxxk ij ,, – соответственно число на-
блюдений значений jx переменной jX (пар ( )ij xx , ) в обучающей выборке lV ,
{ }hl ,...,1∈ .
ПРОЦЕДУРЫ РАСПОЗНАВАНИЯ НА БАЙЕСОВСКИХ СЕТЯХ
Компьютерная математика. 2010, № 2 127
Исследование эффективности байесовской процедуры распознавания на
цепях Маркова основано на исследовании свойств оценок переходных
вероятностей. В отличие от независимых бернуллиевых величин математи-
ческое ожидание оценок переходных вероятностей, построенных в виде частот,
смещено и не совпадает с точными значениями вероятностей. Т. Андерсон и
Л. Гудмен показали, что оценки переходных вероятностей асимптотически
нормальны и вывели формулы дисперсии и ковариации оценок для этого
предельного распределения [1, 6]. На основе этих результатов для цепей
Маркова получены асимптотические оценки погрешности байесовской
процедуры распознавания, которые аналогичны оценкам для независимых
признаков [1, 5].
Байесовская процедура распознавания состояния l объекта ),...,( 1 nxx=x ,
{ }hl ,...,1∈ строится на основе формулы Байеса
( ) ( ) ( )
( )n
n
n xxP
lfPlfxxP
xxlfP
,...,
,...,
,...,
1
1
1
==
== . (3)
Оценки вероятностей в числителе (3) строятся с помощью соотношений (1),
(2) и обучающих выборок описаний объектов ),...,( 1 nxx=x , имеющих заданные
состояния. Знаменатель в (3) не используется, поскольку байесовская процедура
определяет такое состояние наблюдаемого объекта ),...,( 11 nn dxdx ===d ,
которое имеет максимальную оценку в (3).
Структура сети – дерево выводится на основе формулы взаимной информа-
ции между парами переменных
( ) ( )∑ ≥=
ji xx ji
ji
jiji xPxP
xxP
xxPXXI
,
0
(
),(
ln),(),( . (4)
С помощью (4) вычисляют веса всех ( ) 2/1−nn ребер и упорядочивают их
по величине. Алгоритм построения структуры – дерево выполняется на основе
следующих шагов.
1. Выбирают два ребра, имеющих наибольшие веса.
2. Проверяют следующее по порядку ребро и добавляют его в дерево, если
при этом не образуется петля. В противном случае ребро исключается и выбира-
ется следующее по порядку величины веса ребро.
3. Повторяют шаг 1 до тех пор, пока не будут выбраны 1−n ребер.
Алгоритм вывода структуры сети – дерево в [4] был обобщен на схему
байесовской сети, в которой вершина может иметь нескольких родителей и
между двумя вершинами существует единственный путь. Такую сеть называют
лесом (polytree), так как ее можно рассматривать как объединение нескольких
деревьев, сливающихся между собой через вершины, имеющие связи вида
ZYX ←→ .
А.А. ВАГИС
Компьютерная математика. 2010, № 2 128
Вероятностное распределение сети – лес определяется соотношениями
( ))()()(
1
1 ,...,,),...,(
21 ijijiji
n
i
n m
xxxxPxxP ∏
=
= , (5)
где { }
1 2( ) ( ) ( ), ,...,
mj i j i j ix x x – множество (возможно пустое) прямых родителей
переменной ix , причем родители каждой переменной взаимно независимы, т. е.
( ) ( )∏
=
=
m
k
ijijijij km
xPxxxP
1
)()()()( ,...,,
21
. (6)
Структура сети – лес в отличие от структуры – дерево не всегда восстанав-
ливается однозначно из эмпирических данных, поскольку в ней могут присут-
ствовать три вида триплетов соседей:
1. ZYX →→
2. ZYX →← (7)
3. ZYX ←→ .
Триплеты 1 и 2 представляют собой один вид зависимости между перемен-
ными модели, поэтому они не различимы в сети. Наоборот, триплет 3 определя-
ется однозначно, так как переменные X и Z независимы, пары { }YX , , { }ZY ,
являются зависимыми. Поэтому скелет этих трех триплетов одинаковый, а на-
правления дуг можно определить лишь частично.
Структура зависимостей всех потомков заданной вершины X в сети – лес
такая же, как и в случае простой сети – дерево, и вершины, содержащие родите-
лей ,X независимы друг от друга. Поэтому алгоритм аналогичный сети – дере-
во способен определить скелет структуры сети – лес. Если скелет структуры за-
дан, то зависимость вида 3 в (7) дает возможность для переменной, которая име-
ет нескольких родителей (коль скоро определены первые два родителя), опреде-
лить направление всех ребер родитель – потомок. В частности, заметим, что час-
тично ориентированный триплет ZYX −→ может быть завершен с помощью
тестирования взаимной независимости переменных X и Z . Если X и Z неза-
висимы, то Z – родитель переменной Y , в противном случае Y – родитель
переменной Z .
В терминах количества информации для некоторой пары переменных
( )ji XX , , которые не имеют общих потомков, выполняются соотношения
),( ji XXI 0> , (8)
и если kX не блокирует путь между переменными iX и jX , то
),( kji XXXI 0> , (9)
где
, ,
( , )
( , ) ( , , ) ln
( ) ( )
i j k
i j k
i j k i j k
x x x i k j k
P x x x
I X X X P x x x
P x x P x x
= ∑ . (10)
ПРОЦЕДУРЫ РАСПОЗНАВАНИЯ НА БАЙЕСОВСКИХ СЕТЯХ
Компьютерная математика. 2010, № 2 129
Дополнительно к этому родители любой переменной взаимно независимы,
поэтому
0),( )()( 21
=ijij XXI , (11)
и если kX блокирует путь между переменными iX и jX , то из (5)
),( kji XXXI 0= . (12)
С помощью неравенств (8), (9) и соотношений (11), (12) можно провести
точное восстановление скелета структуры и частично направления дуг.
Алгоритм построения структуры – лес состоит из следующих шагов.
1. Выполняются шаги 1 – 3 описанной выше процедуры для структуры сети
– дерево.
2. Находят внутреннюю вершину скелета, начиная поиск с наиболее уда-
ленных слоев, до тех пор, пока не будет найдена вершина со многими родителя-
ми, используя правило тестирования триплета ZYX ←→ .
3. Для вершины со многими родителями определяют направления всех ее
ребер, используя тест триплета ZYX ←→ .
4. Для каждой вершины, которая имеет, по крайней мере, одну входящую
дугу, определяют направления всех ее соседних ребер, используя
ZYX ←→ тест.
5. Повторяют шаги 2 – 4, пока не будут проставлены, по возможности, все
направления ребер.
6. Ребра, для которых не удалось определить направления, помечаются как
«неопределенные». Для завершения процесса определения направлений остав-
шихся ребер необходимо привлекать ряд дополнительных соображений.
Выбор направлений ребер проводится путем решения серии задач распо-
знавания на тестовых примерах. Останавливаются на такой структуре, которая
обладает наилучшими результатами тестирования.
В байесовской процедуре распознавания на структуре сети – лес использу-
ются оценки переходных вероятностей, построенные в виде частот, для цепей
Маркова определенных порядков. Если переменная имеет нескольких родите-
лей, то при вычислении вероятности (5) применяются оценки переходных веро-
ятностей заданных порядков, построеннные аналогично (2).
Заключение. В статье приведены полиномиальные алгоритмы определения
структуры байесовской сети, имеющей вид дерева или леса (polytree). Для
заданной структуры байесовской сети рассмотрены байесовские процедуры рас-
познавания, построенные на обучающих выборках и использующие оценки пе-
реходных вероятностей заданных порядков.
О.А. Вагіс
ПРОЦЕДУРИ РОЗПІЗНАВАННЯ НА БАЙЄСІВСЬКИХ МЕРЕЖАХ
Описано поліноміальні алгоритми визначення структури байєсівської мережі у вигляді дере-
ва або лісу. Для відомої структури байєсівської мережі розглянуто байєсівські процедури
розпізнавання, які побудовано на навчаючих вибірках за допомогою оцінок перехідних
ймовірностей.
А.А. ВАГИС
Компьютерная математика. 2010, № 2 130
A.A. Vagis
RECOGNITION PROCEDURES ON BAYESIAN NETWORKS
The polynomial algorithms of determination of Bayesian network structure are described as a tree or
polytree. For the known Bayesian networks structure, Bayesian recognition procedures built on
teaching samples with the use of estimations of transitional probabilities are considered.
1. Гупал А.М., Сергиенко И.В. Оптимальные процедуры распознавания. – Киев: Наук. дум-
ка, 2008. – 232 с.
2. Балабанов А.С. Минимальные сепараторы в структурах зависимостей. Свойства и иден-
тификация // Кибернетика и системный анализ. – 2008. – № 6. – C. 17 – 32.
3. Балабанов А.С. Формирование минимальных d-сепараторов в системе зависимостей //
Кибернетика и системный анализ. – 2009. – № 5. – C. 38 – 50.
4. P e a r l J . Probabilistic reasoning in intelligent systems: networks of plausible inference. – San
Mateo: Morgan Kaufmann, 1988. –552 p.
5. Гупал А.М., Вагис А.А. Статистическое оценивание марковской процедуры распознавания
// Проблемы управления и информатики. – 2001. – № 2 – С. 62–71.
6. Anderson T.W., Goodman L.A. Statistical inference about Markov Chains // The Annals of
Mathematical Statistics. – 1957. – 28. – P. 89–110.
Получено 22.12.2009
Îá àâòîðå:
Вагис Александра Анатольевна,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
|
| id | nasplib_isofts_kiev_ua-123456789-84594 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T16:54:32Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Вагис, А.А. 2015-07-10T17:41:26Z 2015-07-10T17:41:26Z 2010 Процедура распознавания на байесовских сетях / А.А. Вагис // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 124-130. — Бібліогр.: 6 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84594 519.68 Приведены алгоритмы определения структуры байесовской сети в виде дерева или леса. Рассмотрены байесовские процедуры распознавания, построенные на обучающих выборках с использованием оценок переходных вероятностей заданных порядков. Описано поліноміальні алгоритми визначення структури байєсівської мережі у вигляді дерева або лісу. Для відомої структури байєсівської мережі розглянуто байєсівські процедури розпізнавання, які побудовано на навчаючих вибірках за допомогою оцінок перехідних ймовірностей. The polynomial algorithms of determination of Bayesian network structure are described as a tree or polytree. For the known Bayesian networks structure, Bayesian recognition procedures built on teaching samples with the use of estimations of transitional probabilities are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Экспертные системы, методы индуктивного вывода Процедура распознавания на байесовских сетях Процедури розпізнавання на Байєсівських мережах Recognition procedures on Bayesian networks Article published earlier |
| spellingShingle | Процедура распознавания на байесовских сетях Вагис, А.А. Экспертные системы, методы индуктивного вывода |
| title | Процедура распознавания на байесовских сетях |
| title_alt | Процедури розпізнавання на Байєсівських мережах Recognition procedures on Bayesian networks |
| title_full | Процедура распознавания на байесовских сетях |
| title_fullStr | Процедура распознавания на байесовских сетях |
| title_full_unstemmed | Процедура распознавания на байесовских сетях |
| title_short | Процедура распознавания на байесовских сетях |
| title_sort | процедура распознавания на байесовских сетях |
| topic | Экспертные системы, методы индуктивного вывода |
| topic_facet | Экспертные системы, методы индуктивного вывода |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84594 |
| work_keys_str_mv | AT vagisaa proceduraraspoznavaniânabaiesovskihsetâh AT vagisaa procedurirozpíznavannânabaiêsívsʹkihmerežah AT vagisaa recognitionproceduresonbayesiannetworks |