Быстрый алгоритм вывода структур байесовых сетей из данных

Розроблено новий алгоритм відтворення структур залежностей з даних, який відноситься до constraint-based підходу. Новизна запропонованого алгоритму походить від правил прискорення індуктивного виведення, які радикально скорочують простір пошуку сепараторів при виведенні скелета моделі. На прикладах...

Full description

Saved in:

Bibliographic Details
Date:	2011
Main Authors:	Балабанов, А.С., Гапеев, А.С., Гупал, А.М., Ржепецкий, С.С.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Series:	Проблемы управления и информатики
Subjects:	Методы обработки информации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/207340
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Быстрый алгоритм вывода структур байесовых сетей из данных / А.С. Балабанов, А.С. Гапеев, А.М. Гупал, С.С. Ржепецкий // Проблемы управления и информатики. — 2011. — № 5. — С. 73–80. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207340
record_format	dspace
spelling	irk-123456789-2073402025-10-07T00:22:18Z Быстрый алгоритм вывода структур байесовых сетей из данных Швидкий алгоритм виведення структур байєсових мереж з даних Fast Algorithm for Learning Bayesian Networks from Data Балабанов, А.С. Гапеев, А.С. Гупал, А.М. Ржепецкий, С.С. Методы обработки информации Розроблено новий алгоритм відтворення структур залежностей з даних, який відноситься до constraint-based підходу. Новизна запропонованого алгоритму походить від правил прискорення індуктивного виведення, які радикально скорочують простір пошуку сепараторів при виведенні скелета моделі. На прикладах байєсових мереж помірної насиченості новий алгоритм показав прискорення у кілька разів порівняно з відомим алгоритмом РС We have developed a new constraint-based algorithm for learning dependency structures from data. Novelty of proposed algorithm comes from implementing rules of inductive inference acceleration, which can radically reduce a searching space for skeleton inference. We have demonstrated that proposed algorithm learns Bayesian nets (of moderate density) multiple times faster than well-known PC algorithm. 2011 Article Быстрый алгоритм вывода структур байесовых сетей из данных / А.С. Балабанов, А.С. Гапеев, А.М. Гупал, С.С. Ржепецкий // Проблемы управления и информатики. — 2011. — № 5. — С. 73–80. — Бібліогр.: 13 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207340 007:681.3.00 10.1615/JAutomatInfScien.v43.i10.10 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Балабанов, А.С. Гапеев, А.С. Гупал, А.М. Ржепецкий, С.С. Быстрый алгоритм вывода структур байесовых сетей из данных Проблемы управления и информатики
description	Розроблено новий алгоритм відтворення структур залежностей з даних, який відноситься до constraint-based підходу. Новизна запропонованого алгоритму походить від правил прискорення індуктивного виведення, які радикально скорочують простір пошуку сепараторів при виведенні скелета моделі. На прикладах байєсових мереж помірної насиченості новий алгоритм показав прискорення у кілька разів порівняно з відомим алгоритмом РС
format	Article
author	Балабанов, А.С. Гапеев, А.С. Гупал, А.М. Ржепецкий, С.С.
author_facet	Балабанов, А.С. Гапеев, А.С. Гупал, А.М. Ржепецкий, С.С.
author_sort	Балабанов, А.С.
title	Быстрый алгоритм вывода структур байесовых сетей из данных
title_short	Быстрый алгоритм вывода структур байесовых сетей из данных
title_full	Быстрый алгоритм вывода структур байесовых сетей из данных
title_fullStr	Быстрый алгоритм вывода структур байесовых сетей из данных
title_full_unstemmed	Быстрый алгоритм вывода структур байесовых сетей из данных
title_sort	быстрый алгоритм вывода структур байесовых сетей из данных
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207340
citation_txt	Быстрый алгоритм вывода структур байесовых сетей из данных / А.С. Балабанов, А.С. Гапеев, А.М. Гупал, С.С. Ржепецкий // Проблемы управления и информатики. — 2011. — № 5. — С. 73–80. — Бібліогр.: 13 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT balabanovas bystryjalgoritmvyvodastrukturbajesovyhsetejizdannyh AT gapeevas bystryjalgoritmvyvodastrukturbajesovyhsetejizdannyh AT gupalam bystryjalgoritmvyvodastrukturbajesovyhsetejizdannyh AT ržepeckijss bystryjalgoritmvyvodastrukturbajesovyhsetejizdannyh AT balabanovas švidkijalgoritmvivedennâstrukturbajêsovihmerežzdanih AT gapeevas švidkijalgoritmvivedennâstrukturbajêsovihmerežzdanih AT gupalam švidkijalgoritmvivedennâstrukturbajêsovihmerežzdanih AT ržepeckijss švidkijalgoritmvivedennâstrukturbajêsovihmerežzdanih AT balabanovas fastalgorithmforlearningbayesiannetworksfromdata AT gapeevas fastalgorithmforlearningbayesiannetworksfromdata AT gupalam fastalgorithmforlearningbayesiannetworksfromdata AT ržepeckijss fastalgorithmforlearningbayesiannetworksfromdata
first_indexed	2025-10-07T01:10:17Z
last_indexed	2025-10-08T01:04:54Z
_version_	1845373691818409984
fulltext	© А.С. БАЛАБАНОВ, А.С. ГАПЕЕВ, А.М. ГУПАЛ, С.С. РЖЕПЕЦКИЙ, 2011 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 73 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 007:681.3.00 А.С. Балабанов, А.С. Гапеев, А.М. Гупал, С.С. Ржепецкий БЫСТРЫЙ АЛГОРИТМ ВЫВОДА СТРУКТУР БАЙЕСОВЫХ СЕТЕЙ ИЗ ДАННЫХ В последние годы для решения разведочно-познавательных и прогнозно- аналитических задач в разнообразных сферах деятельности все чаще используют- ся вероятностные модели зависимостей, структурированные ациклическими ори- ентированными графами. Приложения таких моделей охватывают: медицинскую и техническую диагностику, социометрику и эконометрику, микробиологические исследования, распознавание речи, анализ решений, прогнозирование последствий воздействий на объект моделирования и т.д. Модели зависимостей на основе ориен- тированных графов — это строгий язык представления знаний о системе влияний в условиях неполной наблюдаемости. Такие модели привлекают наглядностью, ком- пактностью и способностью отображать причинно-следственные связи. Другие до- стоинства — выводимость, тестируемость и гибкость, которая обеспечивает точный вероятностный вывод от предъявленного набора свидетельств [1–3]. Задача ставится так: вывести (реконструировать) структуру модели на основе статистической выборки данных наблюдений за моделируемой системой. Задача вывода модели из данных в общем случае комбинаторно сложная, особенно когда неизвестен каузальный порядок переменных. Вычислительная сложность начина- ет сдерживать практические применения, когда число переменных достигает не- скольких десятков (для линейных моделей больше). В микробиологических и со- циологических исследованиях возникают задачи с сотнями переменных. Поэтому аналитики часто вынуждены прибегать к жестким ограничениям и сомнительным предположениям, что может привести к потере истинной модели. Различают три основные разновидности моделей на основе ациклических ор- графов: байесовы, гауссовы и гибридные сети. Байесовы сети строятся из дис- кретных переменных. Гауссовы сети полагают линейность зависимостей (пере- менные — действительные). Гибридные сети собирают переменные разных ти- пов. Результаты статьи применимы ко всем указанным разновидностям моделей, поскольку базируются на их общих свойствах. В работе рассматривается подход, основанный на независимости (constraint-based) к индуктивному выводу модели, который опирается на выявление условных независимостей, иначе говоря, на по- иск сепараторов (поэтому такие методы называют также сепарационными). Пока- зано, как можно сфокусировать и сократить поиск сепараторов, используя требо- вания к членам сепараторов. Демонстрируется, что задача верификации связей модели значительно упрощается за счет правил ускорения индуктивного вывода, которые вытекают из марковских свойств модели. 1. Проблемы вывода модели сепарационными методами Напомним базовые определения. Если в графе G есть дуга ,yx то верши- на x называется «родителем» вершины .y Пусть )F(x — множество родителей x. Когда ориентация дуги неизвестна или игнорируется, она обозначается как 74 ISSN 0572-2691 ребро .yx Вершины, соединенные ребром (дугой), называются смежными. Путь, на котором все ребра ориентированы в одном направлении ),( yx  называют орпутем. Фрагмент вида zyx  называется коллайдером (колли- зором). Ациклический ориентированный граф (АОГ) — это орграф, в котором нет ориентированных циклов. Установлено взаимно-однозначное соответствие между переменными (мо- дели) и вершинами (графа). АОГ-модель зависимостей — это модель со струк- турой в виде АОГ (сети) [1–3]. АОГ-модель определяется как ),,( JD где D — АОГ, а J — совокупность локально заданных параметров, т.е. условных распреде- лений в форме )).F(\|( xxp Пара ),( JD однозначно определяет совместное рас- пределение вероятностей переменных согласно правилу Байеса и каузальному марковскому условию [1–4]. Определение 1 (d-сепарация). Путь Т в АОГ называют d-закрытым (d-бло- кированным) с помощью (кондиционирования) множества вершин ,Z если и только если: 1) на пути Т имеется дуга x (или x ) и ;Zx или 2) на пути Т лежит хотя бы один коллайдер , y причем Zy и нет никакой вершины ,Zw такой, что существует орпуть .wy  Если между вершинами x и y существует хотя бы один путь, который не яв- ляется d-закрытым с помощью Z, то вершины x и y d-соединены (d-зависимы) при кондиционировании Z. В противном случае говорят, что множество Z d-се- парирует вершины x и ,y обозначая это как ),;;(Ds yx Z причем множество вершин Z называют d-сепаратором (графовым сепаратором) для пары ).,( yx Со- ответственно d-зависимость записывается как ).;Z;Ds( yx Условную независимость переменной x от переменной y при кондициониро- вании множества переменных Z Z)yx,( обозначим ).;;(Pr yx Z Эта условная независимость означает )()()( ZZZ ypxpxyp  для всех значений перемен- ных. Тогда, очевидно, выполняется 0)Z\|;( yxInf для условной взаимной ин- формации по Шеннону, а множество переменных Z называется эмпирическим се- паратором для пары ).,( yx Безусловную независимость будем записывать в фор- ме ),;(Pr yx а безусловную зависимость — как ).;(Pr yx Известно, что критерий d-сепарации определяет марковские свойства АОГ- модели: :, ZZ  yx );;Ds( yx Z ).;;(Pr yx Z (1) Марковские условные независимости выполняются при любой параметриза- ции модели. Для обоснования методов вывода структуры из данных прибегают к соответ- ствующим предположениям. Обычно принимают предположение каузальной не- обманчивости (faithfulness) распределения вероятностей переменных модели от- носительно АОГ [2–6]. Полная форма предположения каузальной необманчиво- сти выражается как :, ZZ  yx );;(Pr yx Z ).;;(Ds yx Z (2) (Слово «каузальной» далее будем опускать.) Впрочем, для идентификации скелета модели (совокупности неориентированных ребер) можно удовлетворить облегчен- ной формой предположения необманчивости и использовать следующий принцип: :),()( ZZ  yxyx .);;(Pr yx Z (3) Для идентификации скелета модели требуется найти сепаратор для каждой пары переменных (x, y) или удостовериться, что его не существует. (Поэтому ме- тоды, основанные на независимости, называют также cепарационными). Когда имеется большое число кандидатов в сепаратор, поиск сепаратора приводит к Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 75 сложному перебору подмножеств переменных. Этот перебор наиболее сложен, ко- гда неизвестен темпоральный порядок переменных (именно такую ситуацию мы рассматриваем). Например, в модели с 20-ю вершинами может быть до 3420 тестов первого ранга, до 29070 тестов второго ранга, сотни тысяч тестов третьего ранга и миллионы тестов высокого ранга. При этом возрастание ранга тестов условной независимости ведет к снижению их надежности. Оценивая индуктивно-эмпирические алгоритмы вывода структур зависимо- стей, необходимо учитывать вычислительную сложность, корректность и робаст- ность к качеству выборки данных (которая определяет надежность, т.е. риск оши- бок). Когда метод рассчитан на точное воспроизведение истинной (генеративной) модели, постановка задачи является восстановительной. Если же генеративная модель выходит за рамки класса, в которым алгоритм конструирует модель, по- становка задачи называется редукционной. В таком случае выведенная модель, как правило, является покрытием (аппроксимацией) генеративной. Наиболее известны- ми подклассами структур, в которых выполняется покрытие АОГ-моделей, являют- ся деревья (леса) зависимостей, полидеревья и монопотоковые модели. Топология этих подклассов определяется соответствующими ограничениями. В полидеревьях запрещены циклы, а в монопотоковых моделях — одноколлайдерные циклы. Ре- дукцию АОГ-модели в классе монопотоковых структур можно выполнить алго- ритмом «Proliferator-D» [7]. 2. Анализ алгоритма РС Наиболее известный алгоритм сепарационного подхода — алгоритм PC [2–5]. Первый принцип алгоритма PC — сепараторы ищутся в порядке возрастания кар- динальности (размера). Для сокращения перебора используется второй принцип: сепаратор для пары (x, y) подбирается среди множества вершин, которые счита- ются (возможно) смежными к x (или к y) на текущем этапе вывода модели. Это значительно сужает поиск и гарантирует нахождение сепаратора (если он суще- ствует). Но все же вычислительная эффективность поиска сепараторов часто остается неудовлетворительной. Алгоритм PC не оснащен никакими средствами распознавания ребра (или его отсутствия) и поэтому продолжает искать сепаратор до полного исчерпания всех возможностей, даже когда сепаратора не существует. Кроме того, алгоритм PC не всегда находит минимальные сепараторы. Принцип идентификации ребра в алгоритме PC можно выразить следующим образом. Если испытаны и отвергнуты все подмножества из множества вершин, возможно, смежных к x (соответственно, к y) , то существует ребро .yx  Центральный этап методов constraint-based подхода, на который расходуется большая часть времени вывода, — идентификация скелета модели. Логика алго- ритма РС отображена на рис. 1. Вычислительная сложность определяется количе- ством выполняемых тестов и объемом вычисления необходимых статистик. Сложность вычисления статистик для теста );;(Pr yx Z возрастает вместе с ран- гом теста (т.е. кардинальности условия Z), особенно в дискретных моделях. Несо- вершенство алгоритма РС объясняется тем, что в процессе поиска сепаратора ал- горитм привлекает много кандидатов в состав пробных сепараторов. Неэффек- тивность алгоритма РС особенно проявляется в ситуации, когда ребро существует, ибо алгоритм РС пытается «опровергнуть» ребро и исчерпывает все варианты пробных сепараторов. При этом алгоритм достигает тестов высокого ранга и может допустить ошибку. Было предпринято немало попыток усовершенствовать алгоритм РС. Отме- тим только предложения, направленные на повышение скорости восстановления модели. Не претендуя на обзор, назовем три примера. Алгоритм TPDA, представ- ленный в [8], заметно превосходит РС по скорости. Однако он не является асимп- тотически корректным (при стандартном предположении необманчивости). Алго- 76 ISSN 0572-2691 ритм, исследованный в [9], использует регрессию с техникой линейного ядра. Он проявил себя как очень быстрый, однако был испытан лишь на разряженных структурах с линейными зависимостями. Алгоритм, описанный в [10], работает в классе марковских сетей (это структуры, построенные на неориентированных связях). Другие известные нам модифицированные варианты алгоритма РС лишь незначительно ускоряют вывод модели. S1 Form the complete undirected graph U on the set of variables V S2 k = 0 Repeat For each pair of variables X and Y that are adjacent in (the current) U such that ADJ(U;X)\{Y} or ADJ(U;Y)\{X} has at least k elements, check through the subsets of ADJ(U;X)\{Y} and the subsets of ADJ(U;Y)\{X} that have exactly k variables. If a subset S is found conditional on which X and Y are independent, remove the edge between X and Y in U, and record S as Sepset(X;Y) k = k + 1 until for each ordered pair of adjacent variables X and Y, ADJ(U;X)\{Y} has less than k elements S3 Execute the orientation rules, using Sepset(X;Y) Рис. 1 3. Идея и техника ускорения поиска сепараторов Для сокращения перебора при поиске сепараторов предлагается использовать дополнительные требования к кандидатам в члены сепаратора. Показано, как можно узко направить (сфокусировать) поиск сепаратора для заданной пары пе- ременных. В частности, некоторый кандидат в сепараторы отсеивается, если одна из переменных заданной пары служит сепаратором для второй переменной и это- го кандидата [11]. Было показано, что можно выявлять факты отсутствия искомых сепараторов на раннем этапе вывода. Желательно находить минимальные сепара- торы, поэтому было введено следующее понятие [6, 11]. Определение 2. Локально-минимальным сепаратором для пары вершин (x, y) в АОГ называется такой сепаратор S, что после удаления из S любого его члена (элемента) он перестает быть сепаратором для (x, y). Минимальный сепаратор для пары вершин (x, y) — это сепаратор минимальной кардинальности. В [6, 11, 12] сформулированы требования к членам локально-минимальных сепараторов в АОГ и обоснованы правила, позволяющие исключить вершину из числа кандидатов для искомого сепаратора. Одним из ключевых является следу- ющее правило. Правило «отстранения» кандидата в сепаратор (‘placing aside’). Если в АОГ верно );;Ds( yxz & ),;Ds( yz то вершина z не входит ни в один локально- минимальный сепаратор для пары вершин ).,( yx Заметим, доказательство правила отстранения выписано в [11] аккуратнее, чем в [12]. Помимо основного правила отстранения также используем правило обоб- щенного отстранения. И хотя применение этого правила может привести к потере минимального сепаратора, обычно это значительно сокращает пространство по- иска. Для отвержения вершины-кандидата также предназначено следующее пра- вило «чужого гена» (в первоначальную формулировку правила внесены неболь- шие уточнения). Обозначим )Adj(x множество вершин, смежных с вершиной x. Правило «чужого гена». Если в орграфе для заданной вершины z существует такая вершина w, что выполняется )Adj()Adj( yxz  и z);Ds(w & );Ds( xw & & ),;Ds( yw то вершина z не входит в состав ни одного локально-минимального сепаратора для пары вершин (x, y). Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 77 Задача поиска сепараторов упрощается не только в результате отвержения воз- можных членов-кандидатов, но и в результате выяснения факта, что определенная вершина должна обязательно входить в каждый сепаратор. Потенциальным стерж- нем сепаратора называется вершина z, которая не отстраняется от пары (x, y ) и за- висит от обеих вершин. Как показано в [11, 12], в составе каждого непустого сепа- ратора должен быть хотя бы один потенциальный стержень сепаратора. Правило обязательности потенциального стержня. В состав каждого сепа- ратора для пары зависимых вершин ),( yx входит как минимум одна вершина z такая, что выполняется );Ds( xz & );Ds( yz & );;Ds( xyz & ).;;Ds( yxz Аналогичную (но более жесткую) функцию выполняет правило «изолиро- ванной общей близкой в контексте» [6]. Функцию сокращения списка кандидатов в сепаратор выполняет также правило замкнутости стержней сепаратора. В неко- торых ситуациях это правило удаляет из списка сразу несколько кандидатов. Предложенные правила подсказывают необходимость изменения принципов вывода скелета модели [6]. Названный выше принцип алгоритма РС перерастает в новую форму, а именно. Резолюция смежности: если испытаны все подмножества неотверженных кандидатов в сепаратор для пары зависимых вершин ),( yx и сепаратор не найден, то существует ребро .yx Дополнительно требуется ввести новый принцип вывода. Специальная экспресс-резолюция смежности: если для пары зависимых вершин (x, y) все претенденты в стержни сепаратора отвергнуты, то существует ребро .yx Предложенные правила часто позволяют исключить (отвергнуть) значи- тельно больше кандидатов в сепаратор, чем тактика РС. В частности, иногда удается исключить вершину, смежную с одной из сепарируемых вершин. Более того, иногда можно верифицировать некоторые ребра без перебора сепараторов и тогда вывод скелета может завершиться на раннем этапе. Как показано в [13], чтобы восстанавливать структуры зависимостей без циклов (т.е. леса и полилеса) исключительно на основе тестов первого ранга, достаточно ввести в алгоритм правило отстранение и экспресс-резолюцию смежности. Очевидно, что указанные правила, как они сформулированы в [6, 11, 12], непо- средственно подходят для вывода скелета модели из совокупности d-независимостей (зависимостей). Для вывода модели из данных необходимо перейти к эмпирическим версиям (формам) правил, которые будут построены на статистических фактах условной (не)зависимости. Чтобы обосновать эмпирические версии правил вывода, необходимо соответствующее предположение необманчивости. Ясно, что предпо- ложение необманчивости в полной форме (2) будет достаточным. Но также ясно, что предположение (2) излишне сильное и не обязательное для наших целей. Для обоснования эмпирических двойников правил, использующих только факты сепарации нулевого и первого рангов, достаточно двух нижеследующих предположений, являющихся значительно ослабленными формами предположе- ния необманчивости. Предположение «безусловной (маргинальной) цепной необманчивости»: zyx ,, : ).;(Ds);(Pr yxyx  (4) Предположение необманчивости первого ранга:  zyx ,, : ).;;(Ds);;(Pr yzxyzx  (5) Указанные формы предположения можно ослабить еще больше, проанализи- ровав каждое конкретное правило. Действительно, условия правил различаются, а кроме того, можно учесть локальность фрагмента модели, задействованного в каждом правиле. 78 ISSN 0572-2691 Выполнение предположений (4) и (5) обеспечивает асимптотическую кор- ректность вывода модели из данных алгоритмами, которые аккуратно используют эмпирические двойники доказанных правил. Запишем эмпирические версии двух правил ускорения индуктивного вывода. Правило отстранения: если );;{Pr( yxz & });Pr( yz или { );;({Pr zyx & & )},;(Pr zx то исключить переменную z из списка кандидатов в сепаратор для пары переменных (x, y). Правило «чужого гена»: если для заданной переменной )Adj()Adj( yxz  существует такая переменная w, что выполняется );Pr( xw & );;Pr( xzw & );Pr( yw & ),;;Pr( yzw то переменная z не входит в состав ни одного локально-мини- мального сепаратора для пары переменных (x, y). 4. Вариант алгоритма «Razor». Результаты испытания Изложенные принципы и правила позволяют разрабатывать новые алгорит- мы вывода модели. Опишем принципы идентификации скелета модели (ориента- ция ребер выполняется точно так же, как в РС). Идея построения алгоритмов се- рии «Razor» (на основе стандартного алгоритма вывода) отображена на рис. 2. Поскольку главная цель предлагаемых методов — высокая скорость вывода модели, то для разработанного алгоритма сохранена тактика PC-алгоритма, а именно: а) множество кандидатов в сепаратор для пары (x, y) ограничивается верши- нами, смежными c x или c y; б) сепаратор для (x, y) ищется попеременно среди смежных с x и среди смежных с y Заметим, что принцип б) иногда приводит к потере минимальных се- параторов [6]. Сохранение принципа а) делает некоторые правила из [6, 12] не- нужными. При реализации алгоритмов серии «Razor» необходимо различать состояния «ребро возможно» и «ребро существует». Центральной структурой рабочих дан- ных алгоритмов «Razor» является квадратная матрица связей PAR. Содержимое ячейки PAR с координатами (x, y) отображает текущее состояние связи для пары переменных (x, y ). Предусмотрено четыре состояния (0, 1, 2, 3), которые означа- ют соответственно: возможно ребро; существует ребро; нет ребра и сепаратор не- известен; нет ребра и сепаратор известен. В данной работе представляем первую версию алгоритма, разработанную в со- ответствии с декларированными принципами. В предлагаемой версии (Razor-1.1) реализованы, в частности, правила отстранения и обобщенного отстранения, а также принцип стержня сепаратора. Логическая корректность алгоритма под- тверждена на множестве контрольных задач, выполненных в режиме граф- логического синтеза, когда на вход алго- ритма подавались результаты соответству- ющих проверок d-сепарации в истинной модели. Таким образом, вопросы практиче- ской точности вывода сводятся к эмпири- ческой надежности алгоритма. В целях корректного сравнения производительно- сти все сравниваемые алгоритмы реализо- ваны в одной среде и используют, по воз- можности, идентичный код. Большая дли- тельность выполнения задач объясняется работой в режиме интерпретации (в среде MATLAB). Для оценки быстродействия до- статочно выяснить соотношение затрат времени для разных алгоритмов. Старт k: 0 Поиск сепараторов ранга k среди множеств кандидатов Анализ промежуточных результатов и применение правил ускорения индуктивного вывода k:  k  1 Конец Поиск исчерпан? Да Нет Рис. 2 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 79 Для демонстрации производительности алгоритма Razor-1.1 выполнен вывод из- вестной байесовой сети Alarm. Эта модель содержит 37 вершин и 46 ребер. Перемен- ные — бинарные, трехзначные и четырехзначные. Значения параметров взяты из ре- позитория на сайте: http://www.cs.huji.ac.il/labs/compbio/Repository/networks.html. Использовались выборки размером 10 тыс. записей. При выводе алгоритм Razor-1.1 выполнил тесты независимости до второго ранга включительно, а алго- ритм РС — до четвертого ранга. Для алгоритма РС число тестов, распределенное по рангам (начиная с нулевого), составило: 666; 2779; 638; 205; 10. Аналогичные показатели для алгоритма Razor-1.1 равны: 666; 1752; 225; 0; 0. В итоге новый алго- ритм завершил вывод модели в 2,3 раза быстрее, чем РС. К сожалению, Razor-1.1 допустил почти вдвое больше ошибок идентификации ребер. Для более полной характеристики предложенный алгоритм испытывался на моделях, более насыщенных связями. Были случайно сгенерированы структуры модели и параметры. Число вершин (переменных) равно 20. Набор моделей состо- ит из трех групп, с числом ребер 40, 50 и 60 соответственно. Переменные — бинар- ные и трехзначные. Из каждой модели генерировались выборки данных. Ниже при- водятся результаты вывода моделей из выборок размером 20 тыс. записей. Простым, но наглядным и адекватным показателем эффективности алгорит- мов служит максимальный ранг (Мax_Rank) тестов независимости, использован- ных при выводе. Некоторые результаты испытаний для группы моделей «20 вер- шин — 50 ребер» представлены в таблице. Точность вывода модели отображена двумя показателями: Mi — количество пропущенных ребер, Ex — количество ошибочно вставленных ребер («добавок»). Таблица № мо- дели Арность переменных Алгоритм Показатели Mi Ex Длительность (мин) Мax_Rank В21 3 РС 5 1 31,0 7 Razor-1,1 2 7 7,4 4 В22 2 РС 9 0 3,9 6 Razor-1,1 7 3 0,9 3 В23 3 РС 3 1 57,1 9 Razor-1,1 2 9 8,6 4 В25 2 РС 11 1 2,1 6 Razor-1,1 8 3 0,8 3 В26 2 РС 8 0 3,2 6 Razor-1,1 6 2 1,1 3 В28 3 РС 12 0 8,3 6 Razor-1,1 6 0 1,2 2 В30 3 РС 3 0 87,4 10 Razor-1,1 2 5 5,8 3 Как видим, новый алгоритм понижает максимальный ранг тестов в два-три раза по сравнению с алгоритмом РС. Соответственно сокращается время вывода модели. В частности, для вывода модели В30 алгоритм РС затратил около полу- тора часов, а новый алгоритм только 6 мин. Однако возросло количество ошибок. В целом результаты для трех групп моделей можно просуммировать следую- щей сводкой. В среднем для группы моделей из 20 переменных и 40 ребер алгоритм Razor-1.1 показал ускорение (относительно РС) в 5,4 раза. Для группы моделей «20 на 50» среднее ускорение (относительно РС) составило 7,5 раза. Для группы моде- лей «20 на 60» алгоритм Razor-r-1.1 обеспечил ускорение в среднем в 5,8 раза. Новый алгоритм допускает заметно больше ошибок. В частности, для группы моделей из 20 переменных и 50 ребер относительное число ошибочных ребер (про- пусков и добавок) составило 19 % (для РС) и 22 % (для Razor-1.1). Для группы моде- лей «20 на 60» число ошибочных ребер возросло в 1,4 раза. Необходимо найти резер- вы снижения риска ошибок. Но интересно, что алгоритм Razor-1.1 совершает пропус- http://www.cs.huji.ac.il/labs/compbio/Repository/networks.html 80 ISSN 0572-2691 ки ребер реже, чем РС. В целом результаты позволяют оценивать алгоритмы «Razor» как перспективные, поскольку они обеспечивают значительное ускорение вывода. Итак, разработанные правила ускорения индуктивного вывода радикально повышают быстродействие алгоритмов вывода структуры зависимостей. Однако использование этих правил ведет к заметному увеличению риска структурных ошибок, несмотря на асимптотическую корректность правил (они обоснованы простыми версиями предположения каузальной необманчивости). О.С. Балабанов, О.С. Гапєєв, А.М. Гупал, С.С. Ржепецький ШВИДКИЙ АЛГОРИТМ ВИВЕДЕННЯ СТРУКТУР БАЙЄСОВИХ МЕРЕЖ З ДАНИХ Розроблено новий алгоритм відтворення структур залежностей з даних, який відноситься до constraint-based підходу. Новизна запропонованого алгоритму походить від правил прискорення індуктивного виведення, які радикально ско- рочують простір пошуку сепараторів при виведенні скелета моделі. На прикла- дах байєсових мереж помірної насиченості новий алгоритм показав прискорен- ня у кілька разів порівняно з відомим алгоритмом РС. A.S. Balabanov, A.S. Gapyeyev, A.M. Gupal, S.S. Rzhepetskyy FAST ALGORITHM FOR LEARNING BAYESIAN NETWORKS FROM DATA We have developed a new constraint-based algorithm for learning dependency struc- tures from data. Novelty of proposed algorithm comes from implementing rules of inductive inference acceleration, which can radically reduce a searching space for skeleton inference. We have demonstrated that proposed algorithm learns Bayesian nets (of moderate density) multiple times faster than well-known PC algorithm. 1. Pearl J. Causality: models, reasoning, and inference. — Cambridge Univ. Press, 2000. — 526 p. 2. Spirtes P., Glymour C., Scheines R. Causation, prediction and search. (2nd Ed.). — New York : MIT Press, 2001. — 543 p. 3. Neapolitan R.E. Learning Bayesian networks. — Upper Saddle River : Prentice Hall, NJ, 2004. — 693 p. 4. The TETRAD Project: Constraint-based aids to causal model specification / R. Scheines, P. Spirtes, C. Glymour et al. // Multivariate Behavioral Research. — 1998. — 33, N 1. — P. 65–118. 5. Spirtes P., Glymour C. An algorithm for fast recovery of sparse causal graphs // Soc. Sci. Comput. Rev. — 1991. — 9. — P. 62–72. 6. Балабанов А.С. Формирование минимальных d-сепараторов в системе зависимостей // Ки- бернетика и системный анализ. — 2009. — № 5. — С. 38–50. 7. Балабанов А.С. Реконструкция модели вероятностных зависимостей по статистическим данным. Инструментарий и алгоритм // Проблемы управления и информатики. — 2009. — № 6 — С. 90–103. 8. Learning Bayesian networks from data: an information-theory based approach / J. Cheng, R. Greiner, J. Kelly, D.A. Bell, W. Liu // Artificial Intelligence. — 2002. — 137. — P. 43–90. 9. Pellet J.P., Elisseeff A. Using Markov blankets for causal structure learning // J. Machine Learn. Res. — 2008. — 9. — P. 1295–1342. 10. Bromberg F., Margaritis D., Honavar V. Efficient Markov network structure discovery using in- dependence tests // J. Art. Int. Res. — 2009. — 35. — P. 449–484. 11. Балабанов О.С. Правила підбору сепараторів у баєсівських мережах // Проблеми програму- вання. — 2007. — № 4. — С. 22–33. 12. Балабанов А.С. Минимальные сепараторы в структурах зависимостей. Свойства и иденти- фикация // Кибернетика и системный анализ. — 2008. — № 6. — С. 17–32. 13. Балабанов О.С. Прискорення алгоритмів відтворення баєсових мереж. Адаптація до струк- тур без циклів // Проблеми програмування. — 2011. — № 1. — С. 63–69. Получено 04.05.2011

Быстрый алгоритм вывода структур байесовых сетей из данных

Institution

Similar Items