Байесовские процедуры распознавания на сетях
Описано поліноміальні алгоритми визначення структури байєсівської мережі у вигляді «дерева» або «лісу». Для відомої структури байєсівської мережі розглянуто байєсівські процедури розпізнавання, побудовані на навчаючих вибірках за допомогою оцінок перехідних ймовірностей. The polynomial algorithms of...
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/210850 |
| 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. — № 6. — С. 85-90. — Бібліогр.: 6 назв. — рос.ния и информатики. — 2010. — № 6. — С. ХХ-ХХ. — Бібліогр.: ХХ назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859890431414763520 |
|---|---|
| author | Вагис, А.А. |
| author_facet | Вагис, А.А. |
| citation_txt | Название / ИОФамилия // Проблемы управлеБайесовские процедуры распознавания на сетях / А.А. Вагис // Проблемы управления и информатики. — 2010. — № 6. — С. 85-90. — Бібліогр.: 6 назв. — рос.ния и информатики. — 2010. — № 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 network structure Bayesian recognition procedures which are built on learning samples by estimations of transition probabilities are considered.
|
| first_indexed | 2026-03-17T06:42:15Z |
| format | Article |
| fulltext |
© А.А. ВАГИС, 2010
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 85
УДК 519.68
А.А. Вагис
БАЙЕСОВСКИЕ ПРОЦЕДУРЫ
РАСПОЗНАВАНИЯ НА СЕТЯХ
Введение. В последние годы развитие эффективных процедур распознавания
сложных объектов представляет значительный интерес в связи большим числом
приложений, прежде всего, в таких областях, как биоинформатика, экономика,
медицина, где к настоящему времени накоплены (как правило, с помощью доро-
гостоящих экспериментов) огромные обучающие выборки. В связи с этим возни-
кает целый комплекс разнообразных задач прогностического характера, когда на
основе конечного числа эмпирических данных наблюдаемых объектов можно
адекватно спрогнозировать их состояния (в медицине — диагноз пациентов).
В биоинформатике речь идет о прогнозировании на основе геномных последова-
тельностей функциональных особенностей бактерий, вирусов, высших организ-
мов (в том числе человека). Значительный интерес представляют задачи прогно-
зирования пространственной структуры белков, поскольку это связано напрямую
с разработкой новых видов лекарств. На повестку дня выдвигаются задачи иссле-
дования состояний генных сетей, клеток и целых организмов.
Особенность распознавания сложных объектов заключается в том, что опи-
санию объекта может соответствовать несколько значений состояний (исходов
экспериментов). Например, по конечному набору анализов невозможно устано-
вить точный диагноз пациента; в задачах предсказания пространственной струк-
туры белков каждая аминокислота белка может присутствовать в трех состояниях,
определяющих вторичную структуру белка [1].
Пусть наблюдаемый объект описывается вектором ,...,,, 21 nxxx y, где
nxxx ...,,, 21 — признаки (измерения) объекта, y — его состояние. В дальнейшем
будем считать рассматриваемые величины дискретными. В настоящее время об-
щепринятой является вероятностная постановка задач распознавания. Предпола-
гается, что на множестве YX существует неизвестное вероятностное распреде-
ление ),,( yxP согласно которому сгенерирована конечная обучающая выборка
пар ).,( yx
Формально качество распознавания состояния y с помощью функции )(xA
в булевом случае для двух состояний записывается в виде
),,())(()( 2
1
0
yxPyxAAI
yXx
(1)
где усреднение проводится по всем n2 векторам )....,,,( 21 nxxxx Средний
риск (1) отличен от нуля, поскольку при суммировании исключается только одна
из двух вероятностей ).,( yxP Для булевых векторов )...,,,( 21 nxxxx число раз-
личных функций }1,0{)( xA равно ,22n
т.е. проблема минимизации среднего
риска относится к задачам сверхбольшой размерности. Для небольших значений
10n эта величина превосходит ,10300
поэтому аппроксимировать такое множе-
ство функций с помощью конечного числа известных непрерывных функций не
представляется возможным. Аналогично (1) строится средний риск для дискрет-
ных объектов.
86 ISSN 0572-2691
Минимизация среднего риска (1) является обобщением классических задач,
решаемых на основе метода наименьших квадратов, т.е. когда наблюдению
)...,,,( 21 nxxxx соответствует не одно, а несколько состояний объектов (исхо-
дов экспериментов). В.Н. Вапник и А.Я. Червоненкис одни из первых придали за-
дачам распознавания строгую математическую трактовку [2]. В дальнейшем зада-
ча минимизации среднего риска (1) привлекла внимание многих ученых.
Постановка задачи в дискретном случае. Пусть имеется конечное множест-
во B описаний объектов );,...,,,( 21 yxxxb n здесь n — натуральное число, jx
},1...,,1,0{ g ;...,,2,1 nj };1...,,1,0{ hy g, h — натуральные числа, ,2g
;2h g — число значений признаков; h — число состояний. Допустим, прове-
дено m наблюдений над объектами и в каждом случае зафиксировано состояние
объекта. Из этого множества выделена обучающая выборка V. Пусть некоторое
описание объекта получено из множества B независимо от выборки V в соответ-
ствии с распределением P, причем известны только значения признаков
....,,, 21 nxxx По этим значениям и по обучающей выборке V требуется опреде-
лить значение состояния y.
Структура обучающей выборки. Подмножество объектов из B, у которых
целевой признак равен i, называется i-м классом объектов. В обучающей
выборке V количества объектов различных классов заданы. Поэтому считаем, что
выборка V состоит из 1h части, )....,,,( 10 hVVVV Пусть hmmm ...,,, 10 — це-
лые неотрицательные детерминированные числа, они определяют размеры клас-
сов. Часть iV представляет собой целочисленную матрицу размерности .nmi
Каждая строка этой матрицы — наблюдаемое значение вектора ),...,,,( 21 nxxxx
описывающего объект класса i, который выбран из множества B в соответствии с
распределением вероятностей P при условии .iy
Последняя часть hV представляет собой целочисленный вектор размерно-
сти .hm Каждая компонента этого вектора — наблюдаемое значение состояния y,
которое выбирается в соответствии с распределением P. Иными словами, вероят-
ность того, что j-я компонента вектора hV принимает значение i, равна ).( iyP
Все строки матрицы ,iV ,1...,,1,0 hi и компоненты вектора hV — независи-
мые случайные элементы.
Индуктивный шаг. Требуется построить такую процедуру индуктивного
вывода, которая по измерениям nxxx ...,,, 21 любого следующего объекта и обу-
чающей выборке V определяет состояние y объекта.
В [1] выбран прямой подход к построению методов распознавания (мини-
мизации среднего риска): исследуются такие структуры описания объектов, для
которых можно построить эффективные процедуры распознавания. Вместо вы-
полнения достаточно сложных процедур минимизации эмпирического риска
или других функционалов качества применяется простое байесовское правило
классификации, которое используется для решения задач большой размерности.
Байесовская процедура распознавания для независимых признаков строится
на основе известной формулы Байеса
,
)...,,(
)()(
)...,,(
1
1
n
j
n
ij
n
xxP
iyPiyxP
xxiyP
}.1...,,1,0{ hi (2)
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 87
При построении процедуры распознавания неизвестные вероятности ),( iyxP j
)( iyP заменяются частотами, вычисленными на обучающих выборках, при
этом математические ожидания частот совпадают с неизвестными значениями ве-
роятностей. Состояние нового объекта выбирается на основе максимальной оцен-
ки вероятности в (2). В [1] исследована эффективность байесовской процедуры рас-
познавания дискретных объектов с независимыми признаками.
При решении задач распознавания определяющим моментом является струк-
тура описания объекта. Если она известна, то не представляет труда по обучаю-
щей выборке построить байесовские процедуры, как это проделано для цепей
Маркова и независимых признаков. В [1] показано, что байесовская процедура
для независимых признаков субоптимальна: нижняя оценка сложности класса за-
дач совпадает с верхней оценкой погрешности с точностью до абсолютной кон-
станты. Количество классов и число значений признаков линейным образом вхо-
дят в оценку погрешности байесовской процедуры распознавания. Таким образом,
проблема минимизации среднего риска решена для дискретных объектов с неза-
висимыми признаками: построены оптимальные оценки погрешности процедуры
в зависимости от входных параметров задачи.
Наиболее общим аппаратом для извлечения структур описания объектов из
данных является аппарат байесовских сетей. За последнее десятилетие выпущено
свыше двадцати монографий по байесовским сетям, однако вопросы построения
процедур распознавания на сетевых структурах не исследуются. Рассмотрим при-
менение байесовского подхода к задачам распознавания на сетевых структурах.
В монографии [3] отражены вопросы извлечения структуры описания из ста-
тистических данных и полиномиальные процедуры построения специальных се-
тевых структур «дерева» и «леса».
Сетевая структура «дерево» — простейшая структура, которая описывается
небольшим числом зависимостей, она имеет минимальное число связей между
переменными. «Дерево» — структура графа, в которой связи могут быть ориенти-
рованы таким образом, что каждая переменная зависит не более чем от одной ро-
дительской переменной. Заметим, что аналогичная ситуация присуща однород-
ным цепям Маркова.
Если каждая переменная ix принимает g значений, то случайный вектор
)...,,,( 21 nxxxx может принимать
ng значений. Если вероятностное распреде-
ление P неизвестно и имеется независимая выборка x, то для оценивания )(xP
требуется вычислить и
ng величин относительных частот векторов x. Для неза-
висимых компонент вектора x, т.е.
),()...,,(
1
1 i
n
i
n xPxxP
каждая вероятность )( ixP вычисляется с помощью относительной частоты ,ix
поэтому для определения )(xP требуется провести только gn вычислений. По-
скольку предположение о независимости часто не выполняется, целесообразно
исследовать модели, для которых требуется умеренное число вычислений и хра-
нений данных. Вероятностное распределение для зависимых переменных в виде
дерева — одна из таких моделей.
Как и для независимых признаков, вероятностное распределение дерева
)(xP записывается в виде произведения 1n условных вероятностей (переход-
ных вероятностей)
88 ISSN 0572-2691
),(),...,( )(
1
1 iji
n
i
n xxPxxP
(3)
где )(ijx — родительская переменная для величины ix при некоторой ориентации
дерева. Корень 1x не имеет родителей, ).()( 101 xPxxP Поэтому число парамет-
ров, необходимых для определения оценок вероятностного распределения дерева,
равно ),1()1()1( gngg а именно )1( gg параметров для каждой из )1( n
матриц условных (переходных) вероятностей и )1( g параметров для корня дерева.
Байесовская процедура для сети «дерево» строится аналогично процедуре
распознавания для цепей Маркова [1, 4]. Переходные вероятности (3) заменяются
оценками в виде частот
,
),(
),,(
),(ˆ
lxk
lxxk
lyxxP
j
ij
ji (4)
где ly — состояние объекта, ),,( lxk j ),,( lxxk ij — соответственно число
наблюдений значений переменной jx (пар )),( ij xx в обучающей выборке ,lV
}....,,1{ hl
Исследование эффективности байесовской процедуры распознавания на це-
пях Маркова основано на изучении свойств оценок переходных вероятностей.
В отличие от независимых бернуллиевских величин математическое ожидание
оценок переходных вероятностей, построенных в виде частот, смещено и не сов-
падает с точными значениями вероятностей. Т. Андерсон и Л. Гудмен показали,
что оценки переходных вероятностей асимптотически нормальны и вывели фор-
мулы дисперсии и ковариации оценок для этого предельного распределения [1, 5].
На основе этих результатов для цепей Маркова получены асимптотические оцен-
ки погрешности байесовской процедуры распознавания, которые аналогичны
оценкам для независимых признаков [1, 2].
Процедура распознавания состояния l объекта ),...,,,( 21 nxxxx }...,,1{ hl
в сети «дерево» строится на основе формулы Байеса
.
)...,,(
)()...,,(
)...,,(
1
1
1
n
n
n
xxP
lfPlfxxP
xxlfP
(5)
Оценки вероятностей в числителе (5) строятся с помощью соотношений (3), (4)
и обучающих выборок описаний объектов ),...,,,( 21 nxxxx имеющих заданные
состояния. Знаменатель в (5) не используется, поскольку байесовская процедура
определяет такое состояние наблюдаемого объекта ),...,,,( 21 nxxxx которое
имеет максимальную оценку вероятности в числителе (5).
Структура сети «дерево» выводится на основе формулы взаимной информа-
ции между парами переменных
.0
)()((
),(
ln),(),(
,
ji
ji
ji
xx
ji
xPxP
xxP
xxPXXI
ji
(6)
С помощью (6) вычисляют веса всех 2/)1( nn ребер и упорядочивают их по
величине. Полиномиальный алгоритм построения структуры «дерево» выполня-
ется на основе следующих шагов [3]. Выбирают два ребра, имеющих наибольшие
веса. Проверяют следующее по порядку ребро и добавляют его в «дерево», если
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 89
при этом не образуется петля. В противном случае ребро исключается и выбира-
ется следующее по порядку величины веса ребро. Повторяют предыдущие шаги
до тех пор, пока не будет выбрано 1n ребро.
Алгоритм вывода структуры сети «дерево» в [3] был обобщен на схему байе-
совской сети, в которой вершина может иметь нескольких родителей и между
двумя вершинами существует единственный путь. Такую сеть называют «лесом»
(polytree), так как ее можно рассматривать как объединение нескольких «деревь-
ев», сливающихся между собой через вершины, имеющие связи вида .ZYX
Вероятностное распределение сети «лес» определяется соотношениями
)),(()...,,(
1
1 ii
n
i
n xFxPxxP
(7)
где )( ixF — множество прямых родителей переменной ,ix причем родители
каждой переменной взаимно независимы. Если в графе есть дуга ,yx то пере-
менная x называется родителем переменной y, а переменная y — ребенком пере-
менной x. При небольшом числе родителей условные вероятности ))(( ii xFxP по
сути являются переходными вероятностями определенного порядка в цепях Мар-
кова.
Структура сети «лес» в отличие от структуры «дерево» не всегда восста-
навливается однозначно из эмпирических данных, поскольку в ней могут
присутствовать три вида триплетов соседей: 1) ;ZYX 2) ;ZYX
3) .ZYX
Триплеты 1 и 2 представляют собой один вид зависимости между перемен-
ными модели, поэтому они неразличимы в сети. Наоборот, триплет 3 определяет-
ся однозначно, так как переменные X и Z независимы, пары },,{ YX },{ ZY зави-
симы. Поэтому скелет этих трех триплетов одинаков, а направления дуг можно
определить лишь частично.
Структура зависимостей всех потомков заданной вершины X в сети «лес»
такая же, как и в случае простой сети «дерево», и вершины, содержащие родите-
лей X, независимы друг от друга. Поэтому алгоритм сети «дерево» способен
определить скелет структуры сети «лес». Подробное описание алгоритма сети
«лес» приведено в [3].
Выбор направлений ребер, для которых не удалось определить направления,
проводится путем решения серии задач распознавания на тестовых примерах. По-
скольку байесовские процедуры легко вычислимы (полиномиальны), решение та-
ких задач не вызывает дополнительных сложностей. Останавливаются на такой
структуре, которая обладает наилучшими результатами тестирования.
В байесовской процедуре распознавания на структуре сети «лес» использу-
ются оценки переходных вероятностей, построенные в виде частот, аналогично
цепям Маркова определенных порядков. Если переменная имеет нескольких ро-
дителей, то при вычислении вероятностей (5), (7) применяются оценки переход-
ных вероятностей заданных порядков, построенные аналогично оценкам (4).
Заключение. Известно, что задача вывода структуры байесовской сети из
эмпирических данных в общем случае NP-трудная. Вычислительные сложности
становятся серьезной практической проблемой, когда число переменных модели
достигает нескольких десятков. При этом чаще всего используется сепарацион-
ный подход, при котором выявляются факты условной независимости между пе-
ременными (с помощью статистического тестирования гипотез) и тем самым
определяется структура сети. В настоящее время пока не удается прийти к по-
90 ISSN 0572-2691
строению эффективных полиномиальных алгоритмов выведения структуры сети
из данных, кроме того, известные методы находят лишь каркас сети, т.е. направ-
ления дуг определяются лишь частично.
Практический опыт решения задач распознавания сложных объектов боль-
шой размерности показывает, что эффективные результаты чаще всего можно
получить на достаточно простых структурах: моделях цепей Маркова, сетевых
структурах типа «дерево», «лес». Численные расчеты на основе информации из
Всемирного банка белковых структур подтвердили высокую эффективность байе-
совских процедур распознавания (на моделях цепей Маркова различных поряд-
ков) в задачах распознавания вторичной структуры белков [1]. Эффективные бай-
есовские процедуры предсказания пространственной структуры белков на моде-
лях цепей Маркова предложены в [6].
О.А. Вагіс
БАЙЄСІВСЬКІ ПРОЦЕДУРИ
РОЗПІЗНАВАННЯ НА МЕРЕЖАХ
Описано поліноміальні алгоритми визначення структури байєсівської мережі у
вигляді «дерева» або «лісу». Для відомої структури байєсівської мережі розг-
лянуто байєсівські процедури розпізнавання, побудовані на навчаючих вибір-
ках за допомогою оцінок перехідних ймовірностей.
A.A. Vagis
BAYESIAN RECOGNITION
PROCEDURES ON NETWORKS
The polynomial algorithms of determination of Bayesian network structure are
described as a «tree» or «polytree». For the known Bayesian network structure
Bayesian recognition procedures which are built on learning samples by estima-
tions of transition probabilities are considered.
1. Гупал А.М., Сергиенко И.В. Оптимальные процедуры распознавания. — Киев : Наук. дум-
ка, 2008. — 232 с.
2. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М. : Наука, 1974. —
416 с.
3. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. — San
Mateo : Morgan Kaufmann, 1988. — 552 p.
4. Гупал А.М., Вагис А.А. Статистическое оценивание марковской процедуры распознавания //
Проблемы управления и информатики. — 2001. — № 2. — С. 62–71.
5. Anderson T.W., Goodman L.A. Statistical inference about Markov chains // The Annals of
Mathematical Statistics. — 1957. — 28. — P. 89–110.
6. Сергиенко И.В., Белецкий Б.А., Гупал А.М. Предсказание торсионных углов в аминокислот-
ных последовательностях белков на основе байесовской процедуры на цепах Маркова //
Кибернетика и системный анализ. — 2010. — № 5. — С. 4–11.
Получено 09.09.2010
|
| id | nasplib_isofts_kiev_ua-123456789-210850 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2026-03-17T06:42:15Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Вагис, А.А. 2025-12-18T10:08:31Z 2010 Название / ИОФамилия // Проблемы управлеБайесовские процедуры распознавания на сетях / А.А. Вагис // Проблемы управления и информатики. — 2010. — № 6. — С. 85-90. — Бібліогр.: 6 назв. — рос.ния и информатики. — 2010. — № 6. — С. ХХ-ХХ. — Бібліогр.: ХХ назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210850 519.68 10.1615/JAutomatInfScien.v42.i11.60 Описано поліноміальні алгоритми визначення структури байєсівської мережі у вигляді «дерева» або «лісу». Для відомої структури байєсівської мережі розглянуто байєсівські процедури розпізнавання, побудовані на навчаючих вибірках за допомогою оцінок перехідних ймовірностей. The polynomial algorithms of determination of Bayesian network structure are described as a «tree» or «polytree». For the known Bayesian network structure Bayesian recognition procedures which are built on learning samples by estimations of transition probabilities are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Байесовские процедуры распознавания на сетях Байєсівські процедури розпізнавання на мережах Bayesian recognition procedures on networks Article published earlier |
| spellingShingle | Байесовские процедуры распознавания на сетях Вагис, А.А. Методы обработки информации |
| title | Байесовские процедуры распознавания на сетях |
| title_alt | Байєсівські процедури розпізнавання на мережах Bayesian recognition procedures on networks |
| title_full | Байесовские процедуры распознавания на сетях |
| title_fullStr | Байесовские процедуры распознавания на сетях |
| title_full_unstemmed | Байесовские процедуры распознавания на сетях |
| title_short | Байесовские процедуры распознавания на сетях |
| title_sort | байесовские процедуры распознавания на сетях |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210850 |
| work_keys_str_mv | AT vagisaa baiesovskieproceduryraspoznavaniânasetâh AT vagisaa baiêsívsʹkíprocedurirozpíznavannânamerežah AT vagisaa bayesianrecognitionproceduresonnetworks |