For example,Бобцов

HIERARCHY OF ALGEBRAIC BAYESIAN NETWORK GLOBAL STRUCTURES AS A SYSTEM OF GRAPHS AND HYPERGRAPHS

А.А. Фильченков

УДК 004.8
ИЕРАРХИЯ ГЛОБАЛЬНЫХ СТРУКТУР АЛГЕБРАИЧЕСКОЙ БАЙЕСОВСКОЙ СЕТИ КАК СИСТЕМА ГРАФОВ И ГИПЕРГРАФОВ1
А.А. Фильченков
Алгебраические байесовские сети относятся к классу логико-вероятностных графических моделей и позволяют осуществлять логико-вероятностный вывод, в том числе и в отношении знаний с неопределенностью, формализуемых через скалярные и интервальные оценки истинности пропозициональных формул. В работе рассмотрены глобальные структуры алгебраической байесовской сети, предложена их систематизация через гиперграфовое представление и выявлена их функциональная иерархия. Предложенная систематизация позволяет приложить методы теории гиперграфов к решению ряда задач анализа глобальных структур алгебраической байесовской сети, в частности, предложить и обосновать критерий для выявления ацикличности ее первичной структуры, а также формирует теоретическую основу алгоритмизации автоматического обучения указанных сетей. Ключевые слова: алгебраическая байесовская сеть, графы смежности, машинное обучение, глобальная структура, вероятностные графические модели.
Введение
Алгебраические байесовские сети (АБС) лежат на стыке двух классов основных подходов, применяемых к построению математических моделей баз знаний с неопределенностью. Первый из этих классов – подходы, использующие оценки истинности над фрагментами знаний (ФЗ). Ко второму классу относятся так называемые «сетевые» подходы, заключающиеся в использовании графов для моделирования связей (причинно-следственных, логических, реляционных) между элементами или наборами элементов базы знаний [1, 2].
Так, АБС являются математической моделью базы ФЗ с неопределенностью, в которых, в свою очередь, математической моделью ФЗ выступает идеал конъюнктов с заданными над ними оценками вероятности их истинности [1]. Декомпозиция предметной области на базу (набор) таких моделей ФЗ, с прикладной точки зрения, позволяет снизить требования к вычислительным ресурсам (памяти и времени), необходимым для их хранения и обработки, а с теоретической – служит причиной для выделения двух структур АБС: первичной и вторичной.
Первичная структура АБС тесно связана с подходами первого из рассмотренных классов, поскольку представляет собой набор ФЗ. Вторичная же структура АБС – граф [3, 4], построенный над первичной структурой, – согласуется с «сетевыми» подходами. Эти две структурные особенности позволяют отнести АБС к классу логико-вероятностных графических моделей [5], из которого АБС выделяются возможностью использовать интервальные оценки вероятности истинности для представления неопределенности [1, 2]. Помимо первичной и вторичной структур у АБС выделяют также ряд других глобальных структур [6], тесно связанных друг с другом и играющих ключевую роль при решении задачи глобально-

1 Работа выполнена при финансовой поддержке РФФИ, гранты №№ 12-01-00945-а и 12-01-31202-мол_а. 

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)

75

ИЕРАРХИЯ ГЛОБАЛЬНЫХ СТРУКТУР АЛГЕБРАИЧЕСКОЙ БАЙЕСОВСКОЙ СЕТИ...

го обучения АБС. Глобальное обучение АБС – это один из видов машинного (автоматического) обучения, развитие методов, моделей и алгоритмов которого является одной из самых актуальных задач в искусственном интеллекте [2, 5, 7, 8]. Цель данной работы – выявить отношения между указанными глобальными структурами АБС, т.е. описать их иерархию и систематизировать составляющие ее объекты на языке теории гиперграфов. Формально каждое подобное сопоставление является теоремой о представлении, однако и формулировки, и доказательства подобных теорем однотипны, поэтому для краткости мы не будем их воспроизводить в полном масштабе, ограничиваясь лишь содержательным обоснованием и заключением. Выявленные представления позволяют применить известные результаты теории графов (в частности, гиперграфов) в рамках задач теории АБС, в особенности в отношении вопросов построения ациклических и связных вторичных структур.
Будем везде далее под структурой понимать структуру АБС.

Фрагмент знаний и первичная структура как набор фрагментов знаний

Далее во всей работе будем следовать системе терминов теории АБС, основанной на работах [4, 6, 9, 10] и теории графов по [11]. Алфавит A  {x1,, xn} – множество атомарных пропозициональных формул (атомов). Фрагмент знаний – пара CA , pA , где CA – идеал конъюнктов над подалфавитом A  A , не содержащий пустой конъюнкт:
  CA  xiK xi |K  A, K   ,
а pA – функция, заданная на элементах CA , значениями которой являются либо значения из отрезка
0;1, (тогда говорят о скалярных оценках), либо отрезок a;b : 0  a  b  1 (тогда говорят об интер-
вальных оценках). Если ФЗ непротиворечив, то pA в скалярном случае является вероятностью, а в интервальном – ассоциирована с заданием внешней и внутренней меры. Фрагмент знаний, построенный

над A – подалфавитом A – будем обозначать как KPA.

Первичной структурой MKPA , заданной над алфавитом A , называется набор максимальных по
включению ФЗ, построенных над подалфавитами A , образующими покрытие A :

MKPA  {KPAi }i1..N : 1  i, j  NCAi  CAj , Ai  A, причем

Ai  A.

i 1..N

Первичная структура как гиперграф и протоструктура

В данной работе нас будут интересовать лишь структуры АБС (ее «топология»), а не вероятност-

ная семантика, поэтому оказывается достаточным считать первичной структурой набор соответствую-

щих ФЗ подалфавитов [4]. Все рассуждения о подалфавитах, связанные с отношением включения, опе-

рациями объединения и пересечения, оказываются справедливы и для построенных над ними идеалов.

Таким образом, в рамках рассмотрения глобальных структур, первичной структурой над алфави-

том A называется набор максимальных по включению подалфавитов A , образующих покрытие A :

PSA  {Ai}i1..N , 1  i, j  NAi  Aj , Ai  A, причем

Ai  A.

i 1..N

С точки зрения классической системы определений теории гиперграфов [11], которой мы будем

придерживаться на протяжении всей работы, первичная структура является множеством ребер гипергра-

фа, вершинами которого выступают атомы A . Будем обозначать такой гиперграф как H A :

HPSA   A, PSA .

Теорема. Первичная структура является минимальным гиперграфом, т.е. она не содержит голых

элементов, вложенных ребер и кратных ребер.

Доказательство. Благодаря максимальности подалфавитов первичная структура не содержит

вложенных ребер, кратных ребер, а также голых ребер – т.е. ребер, степень которых равна нулю, по-

скольку любое неголое ребро будет содержать голое ребро. Благодаря тому, что подалфавиты образуют

покрытие алфавита A , в гиперграфе нет голых вершин.

Протоструктурой АБС будем называть первичный граф первичной структуры, т.е. ненаправлен-

ный граф, построенный над тем же алфавитом, в котором две вершины смежны тогда и только тогда,

когда они смежны в первичной структуре, т.е. входят в один и тот же подалфавит:

pSPSA   L2 (HPSA )   A,{(xi , x j ) | Ai  PSA : xi , x j  Ai} .
Далее для краткости будем под протоструктурой понимать протоструктуру АБС.

Клики в протоструктуре будут совпадать с кликами в H A , однако максимальные клики в протоструктуре вовсе не обязательно будут совпадать с подалфавитами, входящими в соответствующую пер-

вичную структуру.

76 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)

А.А. Фильченков

Магистральная связность и вторичная структура

Если в предыдущем разделе мы строили графы над алфавитом, то теперь будем строить их над первичной структурой. В подобных графах введем функцию нагрузки (веса) вершины: нагрузкой (весом) вершины будем называть соответствующий ей подалфавит. Будем обозначать нагрузку вершины v как
W v .

Сепаратор двух вершин v и u – пересечение нагрузок их вершин: Sep v,u  W v W u. Две
вершины будем называть сочлененными, если их сепаратор непуст. Нагрузкой ребра в подобных графах
будем называть сепаратор его концов: W v,u  Sep v,u.

Графы максимальных фрагментов знаний (граф МФЗ) над данной первичной структурой PSA – графы, построенные над подалфавитами, входящими в PSA , и в которых ребра возможны только сочлененными вершинами. Множество графов МФЗ над первичной структурой PSA обозначим как MKPG(PSA ) :
G  MKPG PSA   G  PSA, E ,u, v  E  Sep v,u   .

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

BBCG :

BBCG



{

u,

v



|



xi

n i0

:u



x0 , v



xn ,

и i 1, n  xi1, xi   E G ,W  xi   W u  W v} .
Магистрально связный граф – граф, в котором каждая пара сочлененных вершин магистрально связна. Множество магистрально связных графов над первичной структурой PSA обозначим как BBcon(PSA ) :
G  BBcon PSA   G  PSA, E , u, v  PSA ,Sep v,u    v, u  BBCG .

С точки зрения структуры гиперграфа HPSA это означает, что для каждой пары его смежных ги-
перребер можно указать последовательность гиперребер, содержащих пересечение их вершин, такую, что в магистрально связном графе соответствующая последовательность вершин образует путь между вершинами, соответствующими исходным гиперребрам (следует отметить, что последовательность может быть и пустой, тогда две соответствующие исходным гиперребрам вершины должны быть соединены ребром).
Граф смежности – магистрально связный граф МФЗ. Множество графов смежности над первичной

структурой PSA обозначим как JG PSA  : JG PSA   MKPG PSA   BBcon PSA .

Максимальный граф смежности Gmax PSA  – граф смежности, число ребер которого максимально:

 Gmax PSA  argmaxGJGPSA  E G  . Заметим, что определение корректно, поскольку над заданной пер-
вичной структурой существует единственный максимальный граф смежности [4]. Он обладает рядом интересных особенностей. Во-первых, множество нагрузок его ребер совпадает с множеством непустых сепараторов соответствующей первичной структуры. Во-вторых, максимальный граф смежности является для соответствующего первичной структуре гиперграфа реберным графом (или, иначе, дуальным графом), т.е. графом над ребрами гиперграфа, в котором вершины соединены ребром, если соответствующие им гиперребра смежны:

    Gmax PSA  L HPSA  E HPSA , E ,v,u  E  W v W u .
Минимальным графом смежности называется граф смежности, число ребер которого минимально. Множество минимальных графов смежности над первичной структурой PSA будем обозначать как

MJG PSA  : MJG PSA   {G | G  argminGJGPSA  E G }. В общем случае минимальных графов смеж-
ности может быть несколько [4]. Вторичной структурой может выступать какой-либо граф смежности. Обычно в качестве вторич-
ной структуры рассматривают минимальный граф смежности. Задача обучения вторичной структуры

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)

77

ИЕРАРХИЯ ГЛОБАЛЬНЫХ СТРУКТУР АЛГЕБРАИЧЕСКОЙ БАЙЕСОВСКОЙ СЕТИ...
сводится к построению вторичной структуры, оптимальной (или хотя бы приемлемой в определенном смысле) с точки зрения применения алгоритмов глобального логико-вероятностного вывода в АБС [12].
Связность и ацикличность первичной структуры
Вторичная структура, построенная над первичной структурой, должна быть связна; для работы известных алгоритмов апостериорного логико-вероятностного вывода также требуется, чтобы она была и ациклической [12]. Однако не над любой первичной структурой можно построить связную вторичную структуру, так же как и не над любой первичной структурой можно построить ациклическую вторичную структуру [13]. Первичная структура называется связной, если над ней возможно построить граф смежности, который бы являлся связным. Первичная структура называется ациклической, если над ней возможно построить граф смежности, который является ациклическим. Известно [13], что все графы смежности над первичной структурой связны или несвязны одновременно, а также то, что все минимальные по числу ребер графы смежности будут циклическими или ациклическими одновременно.
На основе выявленных в предыдущих разделах соответствий, позволяющих систематизировать объекты теории АБС через графовое и гиперграфовое представление, можно предложить короткое, но строгое и ясное доказательство для следующей теоремы.
Теорема. Первичная структура PS связна тогда и только тогда, когда связен соответствующий ей гиперграф HPS .
Доказательство. Это следует непосредственно из того, что все графы смежности связны или несвязны одновременно, и из того, что максимальный граф смежности как дуальный граф гиперграфа связен или несвязен одновременно с протоструктурой как первичным графом гиперграфа [11].
Доказанная теорема дает простой и проверяемый за O(n2 ) критерий цикличности первичной структуры, где n – мощность алфавита A . Последнее важно в контексте синтеза первичной структуры АБС: поскольку известные алгоритмы логико-вероятностного вывода требуют, чтобы первичная структура АБС была ациклической, важно устанавливать это свойство на этапе синтеза именно первичной, а не вторичной структуры [13].
Третичная полиструктура и четвертичная структура
Сужением G  U графа G (заданного над первичной структурой с введенной на вершинах и ребрах функцией нагрузки) на подалфавит U называется подграф G , состоящий только из тех вершин и
ребер G , нагрузка которых содержит U : G  U  Vi | Vi V (G),U  W (Vi ),Ei | Ei  E(G),U  W (Ei ) .
Множество сужений графа G на произвольные нагрузки будем обозначать как Nar G . Для
краткости Nar Gmax PSA  будем обозначать как Nar PSA  . Nar G является частично-
упорядоченным множеством, в котором отношение порядка задается включением сужений друг в друга:
G U   G V   G  U  G V   U W .
Значимой кликой с нагрузкой U для первичной структуры PSA называется сужение графа
Gmax PSA  на нагрузку, являющуюся непустым сепаратором (т.е. совпадающим с каким-либо ребром
графа Gmax PSA  ). Множество значимых клик для первичной структуры PSA обозначим как
Clique PSA  . Оно как подмножество частично упорядоченного множества также является частично
упорядоченным множеством. Множество значимых клик образует набор гиперребер над МФЗ. Однако соответствующий гипер-
граф не является в общем случае минимальным, поскольку гиперребра содержатся в других гиперребрах (меньших их по определенному на множестве сужений порядку). В соответствии с этим над множеством
Clique PSA  можно построить направленный граф, в котором ребро от значимой клики P к значимой
клике Q проведено тогда и только тогда, когда P содержит Q . Построенный таким образом граф назы-
вается родовым графом над множеством Clique PSA  . Родовой граф можно строить и над произвольным
подмножеством Nar PSA  .
Родительский граф – это направленный граф над некоторым подмножеством Nar PSA  , в кото-
ром ребро проведено от P к Q тогда и только тогда, когда такое ребро содержится в родовом графе и одновременно не существует иного пути от P к Q . Определенный подобным образом родительский граф является транзитивной редукцией родового графа и выступает диаграммой Хассе для подмножества
78 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)

А.А. Фильченков

Nar PSA  , над которым он построен, с порядком, индуцированным порядком над множеством
Nar PSA  .
Третичной полиструктурой АБС (далее третичной полиструктурой) для данной первичной структуры PSA называется множество графов (направленных, ненаправленных и гибридных), построенных
над подмножествами Nar PSA  .
Замкнутым сверху множеством значимых клик Clique PSA  для данной первичной структуры
PSA называется множество Clique PSA  , к которому добавили праклику – сужение Gmax PSA   .
Праклика совпадает с Gmax PSA  . Нагрузкой праклики является пустое множество. Благодаря этому
множество нагрузок элементов Clique PSA  совпадает с множеством сепараторов PSA .
Рассмотрим произвольный элемент Clique PSA  , назовем его CU , где U – его нагрузка. Че-
рез Son CU  будем обозначать подмножество Clique PSA , соответствующее сыновьям CU в роди-
тельском графе над Clique PSA  . Два элемента Son CU  называются собратьями, если они пересека-
ются как сужения ( Son CU  – подмножество Nar PSA  , более того, даже Clique PSA  ):
   Si , S j  Fel  Si , S j  Son CU   Si  S j   .
Полусиблинговый граф HSU для элемента Clique PSA  с нагрузкой U (назовем его CU ) – это
граф, построенный над множеством сыновей CU , ребра в котором проведены между собратьями:
 HSU  Son CU ,{ Si , S j |Si , S j  Fel} .
Четвертичная структура – семейство полусиблинговых графов, построенных для каждого сепара-
тора: {HSU | U  Clique PSA } .
Родственный граф – гибридный граф, получаемый дополнением направленного родительского
графа над Clique PSA  ненаправленными ребрами между собратьями. Согласно определению, родст-
венный граф является элементом третичной полиструктуры, при этом множество его ненаправленных ребер совпадает с множеством ребер в четвертичной структуре.
Иерархия глобальных структур
Отношения, возникающие между введенными выше графовыми и гиперграфовыми объектами, представим явно – в виде единой иерархии.
Основной структурой на данный момент выступает первичная структура, с которой начинается построение АБС экспертом или программой, выявляющей в имеющихся данных скрытые закономерности, отражающие стохастические зависимости, независимости и условные независимости [1, 2].
Для данной первичной структуры PS однозначно восстанавливается ее протоструктура pSPS .
Протоструктура открывает один из возможных подходов осуществить глобальное автоматическое обучение первичной структуры (или первичной и вторичной структур одновременно) [12]. Кроме того, протоструктура может использоваться в анализе особенностей первичной структуры, в частности – для выявления ее связности и ацикличности [14].
Для данной первичной структуры однозначно определяется множество сужений Nar(PS) , а также
его подмножество – множество значимых клик CliquePS . Последнее множество играет значительную
роль в синтезе вторичной структуры, поскольку используется во всех известных алгоритмах ее построения [9, 14].
Множество Nar(PS) , а также его подмножества, в особенности Clique PS выступают в роли
множества вершин для графов (в том числе пустого графа), совокупность которых образует третичную полиструктуру. Элементы третичной полиструктуры используются для синтеза вторичной структуры, в том числе для синтеза всех возможных вариантов такой структуры [14]. Родительский граф над расши-
ренным вверх множеством значимых клик Clique PS используется для построения четвертичной
структуры. Последняя тесно связана с третичной полиструктурой: в частности, она индуцирует нена-
правленные ребра семейного графа над Clique PS . Кроме того, наблюдается также и функциональная
связь: и элементы третичной полиструктуры, и четвертичная структура используются для выявления ацикличности первичной структуры [15]. Следует отметить, что метод выявления ацикличности первич-

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)

79

ИЕРАРХИЯ ГЛОБАЛЬНЫХ СТРУКТУР АЛГЕБРАИЧЕСКОЙ БАЙЕСОВСКОЙ СЕТИ...
ной структуры на основе четвертичной структуры дает сильный аналитический критерий, лежащий в основе алгоритмов устранения циклов первичной структуры [16].
Необходимо также указать, что родительский граф может использоваться для осуществления алгоритмов апостериорного логико-вероятностного вывода, причем предполагается, что по скорости работы и минимизации ошибок в вычислении оценок такой вывод окажется лучше, чем над любой вторичной структурой, построенной над той же первичной структурой.
Заключение
В рамках данной работы были рассмотрены и систематизированы глобальные структуры алгебраической байесовской сети, в частности, введено понятие ее протоструктуры. Протоструктура, элементы третичной полиструктуры и четвертичная структура не используются непосредственно для осуществления алгоритмов логико-вероятностного вывода или для обеспечения представления знаний, хранящихся в сети, однако играют важную роль в решении задач глобального обучения АБС (являющегося подвидом машинного обучения вероятностных графических моделей), в частности, непосредственно для построения вторичной структуры.
Благодаря представлению первичной структуры и элементов третичной полиструктуры как гиперграфов открывается возможность для использования существующих в этой теории результатов для решения задач в теории АБС; в частности, в работе был предложен критерий ацикличности первичной структуры, опирающийся на свойства протоструктуры.
Выделение объекта как структуры АБС основано на соображениях функциональности: каждая глобальная структура выполняет одну или несколько функций в рамках теории АБС. Иерархия структур строится на основе отношений зависимости при синтезе указанных структур. Так, на вершине иерархии структур, описанной в настоящей работе, оказывается первичная структура, тогда как вторичная структура оказывается в самом низу.
Литература
1. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. – СПб: Наука, 2006. – 607 с.
2. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. – СПб: Изд-во СПбГУ, 2009. – 400 с.
3. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. – 2007. – Вып. 5. – С. 71– 99.
4. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. – 2009. – Вып. 11. – С. 104–127.
5. Alpaydin E. Introduction to Machine Learning. – 2nd ed. – Cambridge, Mass. MIT Press, 2010. – 581 p. 6. Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети // Труды
СПИИРАН. – 2011. – Вып. 18. – С. 164–187. 7. Егоров К.В., Царев Ф.Н., Шалыто А.А. Применение генетического программирования для построения
автоматов управления системами со сложным поведением на основе обучающих примеров и спецификации // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 5 (69). – С. 81–89. 8. Тихомиров А.В., Шалыто А.А. Применение генетического подхода для генерации клеточных автоматов // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 2 (72). – С. 62–66. 9. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 4 (68). – C. 73–76. 10. Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник СПбГУ. Серия 1. Математика. Механика. Астрономия. – 2012. – Вып. 2. – С. 65–74. 11. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 384 с. 12. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. – 2011. – Т. 9. – № 11. – С. 57–61. 13. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Управление глобальной структурой знаний в интеллектуальных системах, основанных на алгебраических байесовских сетях // Материалы конференции «Информационные технологии в управлении» (ИТУ–2012). – СПб: ОАО «Концерн «ЦНИИ «Электроприбор». – 2012. – С. 25–33. 14. Фильченков A.A. Алгоритмы построения элементов третичной полиструктуры алгебраической байесовской сети // Труды СПИИРАН. – 2011. – Вып. 3 (18). – С. 237–266.
80 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)

С.В. Попова, И.А. Ходырев

15. Фильченков А.А., Тулупьев А.Л. Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети // «Гибридные и синергетические интеллектуальные системы: теория и практика». Материалы 1-го международного симпозиума. Т. 2. – Калининград: БФУ им. Канта, 2012. – С. 9–18.
16. Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры // Труды СПИИРАН. – 2012. – Вып. 21. – С. 143–156.

Фильченков Андрей Александрович

– СПИИРАН,. мл. научный сотрудник, Санкт-Петербургский государственный университет, аспирант, aaafil@mail.ru

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)

81