Логика минимальной сепарации в каузальных сетях
Виявлено логічні властивості та імплікації на підмножині марківських властивостей систем залежностей, структурованих орієнтованими графами. Результати чинні для широкого класу структур, включаючи змішані графи й структури з орієнтованими циклами. Визначено три типи сепараторів: мінімальні, локально-...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/86212 |
| 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: | Логика минимальной сепарации в каузальных сетях / А.С. Балабанов // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 36-47. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86212 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-862122015-09-10T03:02:21Z Логика минимальной сепарации в каузальных сетях Балабанов, А.С. Кибернетика Виявлено логічні властивості та імплікації на підмножині марківських властивостей систем залежностей, структурованих орієнтованими графами. Результати чинні для широкого класу структур, включаючи змішані графи й структури з орієнтованими циклами. Визначено три типи сепараторів: мінімальні, локально-мінімальні й ненадлишкові. Сформульовано необхідні вимоги до членів ненадлишкового сепаратора та принципи формування ненадлишкових сепараторів з елементарних фактів (не)залежності. We reveal new entailments (implications) on a subset of pairwise Markov properties which hold in causal nets. The results obtained characterize a wide class of graphical models, including mixed graphs and cyclic digraphs. Three kinds of separators are defined: minimal, locally-minimal, and non-redundant. We state necessary conditions for members of non-redundant separator and propose principles of forming a non-redundant separator from elementary (in)dependency facts. 2013 Article Логика минимальной сепарации в каузальных сетях / А.С. Балабанов // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 36-47. — Бібліогр.: 18 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/86212 519.5:681.3.00 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Балабанов, А.С. Логика минимальной сепарации в каузальных сетях Кибернетика и системный анализ |
| description |
Виявлено логічні властивості та імплікації на підмножині марківських властивостей систем залежностей, структурованих орієнтованими графами. Результати чинні для широкого класу структур, включаючи змішані графи й структури з орієнтованими циклами. Визначено три типи сепараторів: мінімальні, локально-мінімальні й ненадлишкові. Сформульовано необхідні вимоги до членів ненадлишкового сепаратора та принципи формування ненадлишкових сепараторів з елементарних фактів (не)залежності. |
| format |
Article |
| author |
Балабанов, А.С. |
| author_facet |
Балабанов, А.С. |
| author_sort |
Балабанов, А.С. |
| title |
Логика минимальной сепарации в каузальных сетях |
| title_short |
Логика минимальной сепарации в каузальных сетях |
| title_full |
Логика минимальной сепарации в каузальных сетях |
| title_fullStr |
Логика минимальной сепарации в каузальных сетях |
| title_full_unstemmed |
Логика минимальной сепарации в каузальных сетях |
| title_sort |
логика минимальной сепарации в каузальных сетях |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86212 |
| citation_txt |
Логика минимальной сепарации в каузальных сетях / А.С. Балабанов // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 36-47. — Бібліогр.: 18 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT balabanovas logikaminimalʹnojseparaciivkauzalʹnyhsetâh |
| first_indexed |
2025-07-06T13:40:36Z |
| last_indexed |
2025-07-06T13:40:36Z |
| _version_ |
1836905122499657728 |
| fulltext |
ÓÄÊ 519.5:681.3.00
À.Ñ. ÁÀËÀÁÀÍÎÂ
ËÎÃÈÊÀ ÌÈÍÈÌÀËÜÍÎÉ ÑÅÏÀÐÀÖÈÈ Â ÊÀÓÇÀËÜÍÛÕ ÑÅÒßÕ
Êëþ÷åâûå ñëîâà: ìàðêîâñêèå ñâîéñòâà, öèêëè÷åñêèé è àöèêëè÷åñêèé îðãðàôû,
m-ñåïàðàöèÿ, íåèçáûòî÷íûé ñåïàðàòîð, êîëëàéäåð, èäåíòèôèêàöèÿ ðåáåð ìîäåëè.
 íàñòîÿùåé ðàáîòå àíàëèçèðóþòñÿ ïàðíûå ìàðêîâñêèå ñâîéñòâà ñèñòåì çàâè-
ñèìîñòåé, ñòðóêòóðèðîâàííûõ îðèåíòèðîâàííûìè ãðàôàìè. Ðåçóëüòàòû õàðàê-
òåðèçóþò ìîäåëè ñ îðèåíòèðîâàííî-àöèêëè÷åñêîé ñòðóêòóðîé [1–5], à òàêæå
áîëåå îáùèå êëàññû ìîäåëåé, â òîì ÷èñëå íà îñíîâå ñìåøàííûõ ãðàôîâ, è
ñòðóêòóðû ñ îðèåíòèðîâàííûìè öèêëàìè [1, 2, 5, 6]. Ìàðêîâñêèå ñâîéñòâà ñåòåé
çàâèñèìîñòåé îïðåäåëÿþòñÿ ñîîòâåòñòâóþùèìè ãðàôîâûìè êðèòåðèÿìè ñåïà-
ðàöèè. Êàê ïîêàçàíî äàëåå, ñóùåñòâóåò âàæíîå ïîäìíîæåñòâî ìàðêîâñêèõ
ñâîéñòâ (øèðîêîãî êëàññà ìîäåëåé), íà êîòîðîì âûïîëíÿþòñÿ áîëåå ñèëüíûå
èìïëèêàòèâíûå ïðàâèëà è îãðàíè÷åíèÿ ïî ñðàâíåíèþ ñ èçâåñòíûìè. Ýòî ïîä-
ìíîæåñòâî ìàðêîâñêèõ ñâîéñòâ îïðåäåëÿåòñÿ ïîíÿòèåì ëîêàëüíî-ìèíèìàëüíî-
ãî (íåèçáûòî÷íîãî) ñåïàðàòîðà [7, 8]. Âàæíàÿ ðîëü âûäåëåííûõ ñâîéñòâ îáúÿñ-
íÿåòñÿ, â ÷àñòíîñòè, òåì ôàêòîì, ÷òî êàêîé-ëèáî ñåïàðàòîð äëÿ çàäàííîé ïàðû
âåðøèí ìîäåëè ñóùåñòâóåò, åñëè è òîëüêî åñëè ñóùåñòâóåò íåêîòîðûé íåèç-
áûòî÷íûé (ëîêàëüíî-ìèíèìàëüíûé) ñåïàðàòîð äëÿ ýòîé ïàðû. Âûïîëíÿÿ ñèí-
òåç èëè âûâîä ñòðóêòóðû ìîäåëè èç äàííûõ, ìîæíî îáîéòèñü ïðîâåðêîé ìè-
íèìàëüíûõ (íåèçáûòî÷íûõ) ñåïàðàòîðîâ. Ïðèìåíåíèå èìïëèêàòèâíûõ ïðàâèë
ïîäáîðà è ôîðìèðîâàíèÿ íåèçáûòî÷íûõ ñåïàðàòîðîâ ïîçâîëÿåò çíà÷èòåëüíî
ïîâûñèòü ýôôåêòèâíîñòü àëãîðèòìîâ âûâîäà ñòðóêòóðû ìîäåëè [9–11].
ÑÅÒÈ ÇÀÂÈÑÈÌÎÑÒÅÉ. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß
Âåðîÿòíîñòíûå ìîäåëè çàâèñèìîñòåé íà îñíîâå ãðàôîâ — àêòóàëüíîå íàïðàâ-
ëåíèå èññëåäîâàíèé íà ñòûêå ìíîãîìåðíîãî ñòàòèñòè÷åñêîãî àíàëèçà, àïïàðàòà
ãðàôîâ, òåîðèè âåðîÿòíîñòåé, êàóçàëüíîãî ìîäåëèðîâàíèÿ è äð. Íàèáîëåå ïî-
ïóëÿðíû ìîäåëè íà îñíîâå àöèêëè÷åñêèõ îðèåíòèðîâàííûõ ãðàôîâ (ÀÎÃ),
ê êîòîðûì îòíîñÿòñÿ áàéåñîâû, ãàóññîâû è ãèáðèäíûå ñåòè. ÀÎÃ-ìîäåëè ïðè-
âëåêàþò êîìïàêòíîñòüþ, ñïîñîáíîñòüþ îòîáðàæàòü ïðè÷èííî-ñëåäñòâåííûå
ñâÿçè è ðàçâèòîé òåõíèêîé âåðîÿòíîñòíûõ ðàññóæäåíèé [1–3]. Ìîäåëè ýòîãî
êëàññà ïðèìåíÿþòñÿ äëÿ ðåøåíèÿ ðÿäà çàäà÷ (êàóçàëüíûé àíàëèç, äèàãíîñòèêà,
ïðîãíîçèðîâàíèå, êëàññèôèêàöèÿ è ò.ï.) èç ñàìûõ ðàçíûõ îáëàñòåé. Ââèäó
âçàèìíî îäíîçíà÷íîãî ñîîòâåòñòâèÿ òåðìèíû «âåðøèíà» (ãðàôà) è «ïåðåìåí-
íàÿ» (ìîäåëè) óïîòðåáëÿþòñÿ êàê âçàèìîçàìåíÿåìûå (ïî êîíòåêñòó). ÀÎÃ-ìî-
äåëü (â óçêîì ñìûñëå) îïðåäåëÿåòñÿ êàê ( , )G � ; çäåñü G — ÀÎÃ, à � —
ñîâîêóïíîñòü ëîêàëüíî çàäàííûõ ïàðàìåòðîâ, ò.å. óñëîâíûõ ðàñïðåäåëåíèé ïåðå-
ìåííûõ p X X( | ( ))F , ãäå F( )X — ìíîæåñòâî ðîäèòåëåé (ïðè÷èí) ïåðåìåííîé X .
ÀÎÃ-ìîäåëü îïðåäåëÿåò ñîâìåñòíîå ðàñïðåäåëåíèå âåðîÿòíîñòåé ïåðåìåííûõ.
Âûðàçèòåëüíîñòü è ýôôåêòèâíîñòü îðèåíòèðîâàííûõ ñåòåé çàâèñèìîñòåé
îáóñëîâëåíû èõ ìàðêîâñêèìè ñâîéñòâàìè, êîòîðûå ìîæíî îáîñíîâàòü êàóçàëü-
íûì ìàðêîâñêèì óñëîâèåì è àêñèîìàìè óñëîâíîé íåçàâèñèìîñòè [1, 2, 12]. Ìàð-
êîâñêèå ñâîéñòâà ìîäåëè — ìíîæåñòâî òàêèõ ôàêòîâ óñëîâíîé íåçàâèñèìîñòè
ïåðåìåííûõ, êîòîðûå èíâàðèàíòíû ê ïàðàìåòðèçàöèè ìîäåëè è îïðåäåëÿþòñÿ
èñêëþ÷èòåëüíî ãðàôîâûì êðèòåðèåì íà ñòðóêòóðå G ìîäåëè. Äëÿ ÀÎÃ-ìîäåëåé
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
© À.Ñ. Áàëàáàíîâ, 2013
òàêèì êðèòåðèåì ÿâëÿåòñÿ d-ñåïàðàöèÿ [1]. Ôàêò d-ñåïàðàöèè âëå÷åò ñîîòâåòñòâó-
þùóþ óñëîâíóþ íåçàâèñèìîñòü [12].
Íàïîìíèì ýëåìåíòàðíûå ïîíÿòèÿ, íåîáõîäèìûå äëÿ îïèñàíèÿ ñòðóêòóðû
ìîäåëè. Â ñåòÿõ çàâèñèìîñòåé ìîãóò èñïîëüçîâàòüñÿ ðåáðà òðåõ òèïîâ: îðèåíòè-
ðîâàííûå (îäíîîðèåíòèðîâàííûå) X Y� (èëè äóãè); íåîðèåíòèðîâàííûå; áè-
îðèåíòèðîâàííûå (äâóñòîðîííå îðèåíòèðîâàííûå) X Y� . Âåðøèíû íàçûâàþò-
ñÿ ñìåæíûìè, åñëè îíè ñîåäèíåíû ðåáðîì ëþáîé îðèåíòàöèè.  ñëó÷àå äóãè
X Y� âåðøèíà X íàçûâàåòñÿ ðîäèòåëåì (ïðè÷èíîé) âåðøèíû Y , à âåðøèíà Y —
ðåáåíêîì (ýôôåêòîì) âåðøèíû X . Áèîðèåíòèðîâàííîå ðåáðî X Y� îòîáðàæàåò
ýôôåêò ñêðûòîãî îáùåãî ðîäèòåëÿ âåðøèí X è Y . Ïóòü â îðãðàôå — ïîñëåäîâà-
òåëüíîñòü ðåáåð (áåç ïîâòîðåíèÿ ïðîìåæóòî÷íûõ âåðøèí), ãäå âòîðàÿ âåðøèíà
êàæäîãî î÷åðåäíîãî ðåáðà ÿâëÿåòñÿ ïåðâîé âåðøèíîé ñëåäóþùåãî ðåáðà. (Î÷å-
âèäíî, ÷òî åñëè ìåæäó X è Y ñóùåñòâóåò «ïóòü» ñ ïîâòîðåíèåì ïðîìåæóòî÷íîé
âåðøèíû, òî ìîæíî ïîëó÷èòü äðóãîé ïóòü ìåæäó X è Y , óäîâëåòâîðÿþùèé óêà-
çàííîìó âûøå îïðåäåëåíèþ.) Åñëè ïåðâàÿ è ïîñëåäíÿÿ âåðøèíû ïóòè ñîâïàäàþò,
ýòîò ïóòü íàçûâàþò öèêëîì. Îðïóòü (ò.å. ñòðîãî îðèåíòèðîâàííûé ïóòü) — ýòî
ïóòü, íà êîòîðîì âñå ðåáðà îðèåíòèðîâàíû â íàïðàâëåíèè îäíîãî è òîãî æå êîíöà
ïóòè X Y� ��� � . Òîãäà âåðøèíû X è Y íàçûâàþòñÿ ñîîòâåòñòâåííî ïðåäêîì è
ïîòîìêîì äðóã äðóãà. Îðïóòü âèäà X X� ��� � íàçûâàåòñÿ îðöèêëîì (öèêëîíîì).
Àöèêëè÷åñêèé îðèåíòèðîâàííûé ãðàô — ýòî îðãðàô, â êîòîðîì íåò öèêëîíîâ.
Êîëëàéäåðîì (êîëëèçîðîì) â ãðàôå íàçûâàåòñÿ ôðàãìåíò âèäà X Y Z� � ,
X Y Z� � , X Y Z� � èëè X Y Z� � . Âñå âàðèàíòû êîëëàéäåðà îáîçíà÷àþò
* *� �Y . Âåðøèíó Y , âõîäÿùóþ â ñîñòàâ êîëëàéäåðà * *� �Y , íàçîâåì êîë-âåð-
øèíîé íà òîì ïóòè, íà êîòîðîì ëåæèò äàííûé êîëëàéäåð. Áåñêîëëàéäåðíûé (áåñêîë-
ëèçîðíûé) ïóòü, èëè öåïü, — ýòî ïóòü, íå ñîäåðæàùèé íè îäíîãî êîëëàéäåðà.
ÀÎà â óçêîì ñìûñëå, ò.å. îÀÎà (îäíîîðèåíòèðîâàííûé), ñòðîèòñÿ èñêëþ÷è-
òåëüíî èç îäíîîðèåíòèðîâàííûõ ðåáåð. Îáîáùåíèåì è ðàñøèðåíèåì îÀÎÃ-ìîäåëåé
ÿâëÿþòñÿ ìîäåëè ñî ñòðóêòóðàìè â êëàññå àíöåñòðàëüíûõ ãðàôîâ, êîòîðûå ñòðîÿòñÿ
èç ðåáåð òðåõ óêàçàííûõ òèïîâ [4, 5]. Îäíàêî â àíöåñòðàëüíûõ ãðàôàõ çàïðåùåíû
(íå äîïóñêàþòñÿ) îïðåäåëåííûå âèäû öèêëîâ (ïîìèìî öèêëîíîâ) [4].  ÷àñòíîñòè,
ìåæäó âåðøèíàìè, êîòîðûå ñâÿçàíû îðïóòåì, ïî îïðåäåëåíèþ çàïðåùåíî áèîðèåí-
òèðîâàííîå ðåáðî. Ìîäåëè íà àíöåñòðàëüíûõ ãðàôàõ ïîçâîëÿþò àäåêâàòíî îòîáðà-
çèòü ýôôåêòû ñêðûòûõ (ëàòåíòíûõ) ïåðåìåííûõ è ñåëåêöèè äàííûõ.
Äëÿ äàëüíåéøåãî èçëîæåíèÿ öåëåñîîáðàçíî ñîñðåäîòî÷èòüñÿ íà ïîäìíîæåñ-
òâå ìîäåëåé, êîòîðûå íå ñîäåðæàò íåîðèåíòèðîâàííûõ ðåáåð (ñâîéñòâà íåîðèåí-
òèðîâàííûõ ñòðóêòóð — çíà÷èòåëüíî ïðîùå). Ïîýòîìó äàëåå îáîçíà÷åíèå âèäà
X —Y ñëåäóåò ïîíèìàòü êàê ðåáðî íåêîòîðîé îðèåíòàöèè, êðîìå òåõ, êîòîðûå
èñêëþ÷àþòñÿ ïî êîíòåêñòó. Íåðåêóðñèâíûìè êàóçàëüíûìè ñåòÿìè (ÍÐÊÑ) íàçî-
âåì ïîäêëàññ àíöåñòðàëüíûõ ìîäåëåé, â êîòîðîì íå èñïîëüçóþòñÿ íåîðèåíòèðî-
âàííûå ðåáðà. (Çàìåòèì, ÷òî îÀÎà íàçûâàþò ðåêóðñèâíûìè êàóçàëüíûìè ñåòÿ-
ìè.) Äàëüíåéøèì ðàñøèðåíèåì ÿâëÿþòñÿ ìîäåëè íà ñìåøàííûõ ãðàôàõ (ñ îðèåí-
òèðîâàííûìè è áèîðèåíòèðîâàííûìè ðåáðàìè), â êîòîðûõ çàïðåùåíû òîëüêî
öèêëîíû. Òàêèå ãðàôû íàçîâåì ÌÀÎà (ñÌåøàííûå ÀÎÃ). Îñíîâíûå ðåçóëüòàòû
ñòàòüè ñîõðàíÿþò ñèëó òàêæå äëÿ ìîäåëåé ñ öèêëîíàìè. Öèêëè÷åñêèé îðãðàô
(ÖÎÃ) — ýòî ãðàô èç îäíîîðèåíòèðîâàííûõ ðåáåð (öèêëîíû äîïóñêàþòñÿ, íî
ïåòëè X X� îáû÷íî íå èñïîëüçóþòñÿ).
Äëÿ àíöåñòðàëüíûõ ãðàôîâ îïðåäåëåí êðèòåðèé m-ñåïàðàöèè, êîòîðûé ÿâëÿ-
åòñÿ åñòåñòâåííûì ðàñøèðåíèåì êðèòåðèÿ d-ñåïàðàöèè è âûïîëíÿåò àíàëîãè÷-
íóþ ðîëü [2, 4]. Â ôîðìóëèðîâêå êðèòåðèÿ m-ñåïàðàöèè òåðìèí «êîíäèöèîíèðî-
âàíèå» ìîæíî ïîíèìàòü êàê ââåäåíèå âåðøèíû â óñëîâèå. Èçâåñòíî, ÷òî êðèòå-
ðèé d-ñåïàðàöèè ïðèìåíèì òàêæå â îðãðàôàõ ñ öèêëîíàìè [6, 13].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 37
Îïðåäåëåíèå 1 (m-ñåïàðàöèÿ). Ïóòü � â îðãðàôå íàçûâàþò m-ïåðåêðûòûì
(m-áëîêèðîâàííûì) ñ èñïîëüçîâàíèåì (êîíäèöèîíèðîâàíèÿ) ìíîæåñòâà âåðøèí S,
åñëè è òîëüêî åñëè íà ïóòè � èìååòñÿ äóãà Z � (èëè � Z), ãäå Z � S, èëè íà ïóòè �
ëåæèò õîòÿ áû îäèí êîëëàéäåð * *� �Y , ïðè÷åì Y � S è íå ñóùåñòâóåò íèêà-
êîé âåðøèíû Q � S, òàêîé, ÷òî èìååòñÿ îðïóòü Y Q� ��� � .
Åñëè ïóòü ìåæäó âåðøèíàìè X è Y íå ÿâëÿåòñÿ m-ïåðåêðûòûì, çíà÷èò, îí
m-îòêðûò (àêòèâåí). Åñëè ïðè êîíäèöèîíèðîâàíèè ìíîæåñòâà âåðøèí S ñóùåñòâóåò
õîòÿ áû îäèí m-îòêðûòûé ïóòü ìåæäó âåðøèíàìè X è Y , òî ýòè âåðøèíû ÿâëÿþòñÿ
m-ñîåäèíåííûìè (m-çàâèñèìûìè), èíà÷å îíè m-ñåïàðèðîâàíû (m-íåçàâèñèìû).
Äëÿ ôàêòîâ m-ñåïàðàöèè ñîõðàíèì îáîçíà÷åíèå, ïðèíÿòîå â [7, 8] äëÿ d-ñå-
ïàðàöèè: çàïèñü Ds ( ; ; )X YS (ãäå X Y, �S) îçíà÷àåò, ÷òî ìíîæåñòâî S m-ñåïàðè-
ðóåò âåðøèíû X è Y .  ýòîì ñëó÷àå ìíîæåñòâî S íàçûâàåòñÿ m-ñåïàðàòîðîì (èëè
ïðîñòî ñåïàðàòîðîì) äëÿ ïàðû ( , )X Y . Êîãäà ìíîæåñòâî S ïóñòî, m-ñåïàðàöèÿ çà-
ïèñûâàåòñÿ êàê Ds ( ;; )X Y . Åñëè ìíîæåñòâî S íå ÿâëÿåòñÿ m-ñåïàðàòîðîì äëÿ
ïàðû ( , )X Y , òî ýòî âûðàæàåòñÿ â âèäå ~ ( ; ; )Ds X YS .
ÇÀÄÀ×À ÂÛÂÎÄÀ ÑÒÐÓÊÒÓÐÛ. ËÎÊÀËÜÍÎ-ÌÈÍÈÌÀËÜÍÛÉ
È ÍÅÈÇÁÛÒÎ×ÍÛÉ ÑÅÏÀÐÀÒÎÐÛ
Äëÿ ðåøåíèÿ ïîçíàâàòåëüíûõ, èññëåäîâàòåëüñêèõ è ïðîãíîçíî-àíàëèòè÷åñêèõ
çàäà÷ òðåáóåòñÿ âûâîäèòü ñòðóêòóðó ìîäåëè çàâèñèìîñòåé èç ñòàòèñòè÷åñêîé
âûáîðêè äàííûõ íàáëþäåíèé çà ìîäåëèðóåìîé ñèñòåìîé. Â ðàìêàõ òàê íàçû-
âàåìîãî constraint-based (ñåïàðàöèîííîãî) ïîäõîäà [2, 3, 5–10] çàäà÷à âûâîäà
ìîäåëè ñâîäèòñÿ ê çàäà÷å ïîèñêà è ïîäáîðà ñåïàðàòîðîâ (èëè óñòàíîâëåíèÿ
ôàêòîâ èõ îòñóòñòâèÿ). Îñíîâíîé ýòàï âûâîäà ñòðóêòóðû ìîäåëè — ïîñòðîåíèå
åå ñêåëåòà — ñîñòîèò â èäåíòèôèêàöèè âñåõ ðåáåð (áåç îðèåíòàöèè). Ñèíòåç
ìîäåëè — ýòî âûâîä ñòðóêòóðû, èñõîäÿ èç ôàêòîâ m-ñåïàðàöèè.
Äëÿ âñåõ êëàññîâ ìîäåëåé òðèâèàëüíî èìååì
( ,� �Z Z( ):X Y Ds ( ; ; ))X YZ îòñóòñòâóåò (X —Y ) .
Äëÿ îÀÎà âåðíà òàêæå îáðàòíàÿ èìïëèêàöèÿ [2, 3, 7]
(
�Z Z Z( ) DsX Y X Y, : ~ ( ; ; )) (X —Y ) . (1)
Èíûìè ñëîâàìè, â îÀÎà ñóùåñòâîâàíèå ðåáðà ýêâèâàëåíòíî îòñóòñòâèþ ñå-
ïàðàòîðà. Îäíàêî èìïëèêàöèÿ (1) íåâåðíà â áîëåå îáùèõ ñëó÷àÿõ, â ÷àñòíîñòè
â àíöåñòðàëüíûõ ãðàôàõ è ãðàôàõ ñ öèêëîíàìè.
Óñëîâíóþ íåçàâèñèìîñòü ïåðåìåííîé X îò ïåðåìåííîé Y ïðè êîíäèöèîíèðî-
âàíèè ìíîæåñòâà ïåðåìåííûõ Z (X Y, �Z) îáîçíà÷èì Pr( ; ; )X YZ . Ýòà óñëîâíàÿ
íåçàâèñèìîñòü îçíà÷àåò, ÷òî
�x y p xy, , ( | )z z: p x p y( | ) ( | )z z� . Ïðè ýòîì ìíîæåñ-
òâî ïåðåìåííûõ Z áóäåì íàçûâàòü ñòàòèñòè÷åñêèì ñåïàðàòîðîì äëÿ ïàðû ( , )X Y .
Ïåðåõîä îò ÿçûêà ãðàôîâ ê ðàñïðåäåëåíèÿì âåðîÿòíîñòåé (÷åðåç êðèòåðèé
m-ñåïàðàöèè) îáåñïå÷èâàåòñÿ îðèåíòèðîâàííûì ìàðêîâñêèì ñâîéñòâîì ìîäåëè.
 ëþáîì ðàñïðåäåëåíèè âåðîÿòíîñòåé, ãåíåðèðîâàííîì èç ãðàôà G ìîäåëè
çàâèñèìîñòè, âûïîëíÿåòñÿ èìïëèêàöèÿ
X Y, , Z (X Y, �Z): [ ( ; ; )Ds X YZ Pr( ; ; )X YZ ]. (2)
Îáðàòíàÿ èìïëèêàöèÿ âûïîëíÿåòñÿ íå âñåãäà (òîëüêî àñèìïòîòè÷åñêè, çà èñ-
êëþ÷åíèåì îñîáûõ ñëó÷àåâ). Èìïëèêàöèÿ, îáðàòíàÿ ê (2), ðàññìàòðèâàåòñÿ êàê ïðåä-
ïîëîæåíèå êàóçàëüíîé íåîáìàí÷èâîñòè (faithfulness) ðàñïðåäåëåíèÿ âåðîÿòíîñòåé
ïåðåìåííûõ îòíîñèòåëüíî ñòðóêòóðû ìîäåëè [2, 3, 8, 9].
Êîãäà ñòðóêòóðà ìîäåëè âûâîäèòñÿ èç ñòàòèñòè÷åñêèõ äàííûõ, îòûñêèâàþò
ñòàòèñòè÷åñêèå ñåïàðàòîðû. Äëÿ ñëîæíûõ ñòðóêòóð ýòî òðóäíàÿ ïåðåáîðíàÿ çàäà÷à,
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
îñîáåííî êîãäà íåèçâåñòíà íå òîëüêî ñòðóêòóðà ìîäåëè, íî è òåìïîðàëüíûé ïîðÿ-
äîê ïåðåìåííûõ. Íàëè÷èå èëè îòñóòñòâèå ðåáåð âåðèôèöèðóåòñÿ òåñòèðîâàíèåì
ñòàòèñòè÷åñêèõ ôàêòîâ óñëîâíîé íåçàâèñèìîñòè ïåðåìåííûõ â âûáîðêå äàííûõ.
Âîçðàñòàíèå êàðäèíàëüíîñòè óñëîâèÿ Z âåäåò ê óñëîæíåíèþ âûâîäà è ñíèæåíèþ
íàäåæíîñòè òåñòîâ. Ïîèñê ñòàòèñòè÷åñêèõ ñåïàðàòîðîâ íàèáîëåå òðóäîåìêèé
â ñëó÷àÿõ, êîãäà çàâèñèìîñòè íåëèíåéíûå, êîãäà ïåðåìåííûå äèñêðåòíûå èëè ðàç-
íîòèïíûå. Ïîýòîìó ïðåäïî÷òèòåëüíî íàõîäèòü ìèíèìàëüíûå ñåïàðàòîðû è êàê
ìîæíî ðàíüøå âûÿâëÿòü ôàêòû îòñóòñòâèÿ ïðåäïîëàãàåìûõ ñåïàðàòîðîâ.
Îïðåäåëåíèå 2 [7, 14, 15]. Ëîêàëüíî-ìèíèìàëüíûì m-ñåïàðàòîðîì (ËîÌÑ)
äëÿ ïàðû âåðøèí ( , )X Y íàçûâàåòñÿ òàêîé ñåïàðàòîð Z , ÷òî åñëè èñêëþ÷èòü èç Z ëþ-
áîé åãî ÷ëåí, òî ïîëó÷åííîå ìíîæåñòâî âåðøèí íå áóäåò ñåïàðàòîðîì äëÿ ( , )X Y .
Ôîðìàëüíî ýòî çàïèñûâàåòñÿ òàê: Ds ( ; ; )X YZ ;
�W X W YZ Z:~ ( ; \ ; )Ds { } .
Ìèíèìàëüíûì ñåïàðàòîðîì äëÿ ïàðû âåðøèí ( , )X Y åñòåñòâåííî íàçâàòü
òàêîé ñåïàðàòîð Z*, ÷òî äëÿ ( , )X Y íå ñóùåñòâóåò ñåïàðàòîðà ìåíüøåé êàðäè-
íàëüíîñòè. Èíûìè ñëîâàìè, åñëè Z* — ìèíèìàëüíûé ñåïàðàòîð äëÿ ïàðû ( , )X Y ,
òî äëÿ âñåõ äðóãèõ ñåïàðàòîðîâ Z äëÿ ( , )X Y âåðíî | | | *|Z Z� . Åñëè ñòðóêòóðà
ãðàôà ìîäåëè èçâåñòíà, çàäà÷à ïîèñêà ìèíèìàëüíûõ ñåïàðàòîðîâ ðåøàåòñÿ ìåòî-
äàìè, èçâåñòíûìè èç òåîðèè ãðàôîâ.
Ïîñêîëüêó â êëàññ àíàëèçèðóåìûõ ìîäåëåé âêëþ÷åíû ñåòè ñ öèêëîíàìè, íå-
îáõîäèìî ââåñòè íîâîå ïîíÿòèå.
Îïðåäåëåíèå 3. Íåèçáûòî÷íûì m-ñåïàðàòîðîì (ÍÈÑ) äëÿ ïàðû âåðøèí
( , )X Y íàçûâàåòñÿ òàêîé ñåïàðàòîð Z , ÷òî íèêàêîå åãî ïîäìíîæåñòâî íå ÿâëÿåòñÿ
ñåïàðàòîðîì äëÿ ïàðû âåðøèí ( , )X Y . Ôîðìàëüíî: Ds ( ; ; )X YZ è äëÿ âñåõ Z Z
�
èìååì ~ ( ; ; )Ds X YZ
.
Îáîçíà÷èì ñåïàðàòîðû äëÿ ïàðû ( , )X Y : ëîêàëüíî-ìèíèìàëüíûé — Slom ( , )X Y ;
íåèçáûòî÷íûé — Snred ( , )X Y ; ìèíèìàëüíûé — Smin ( , )X Y . Êàæäûé ÷ëåí ëþáîãî
ËîÌÑ Z íå ÿâëÿåòñÿ êîë-âåðøèíîé íà òîì ïóòè (òåõ ïóòÿõ), êîòîðûé îí áëîêèðóåò,
ïðè÷åì ýòîò ïóòü (êàê ìèíèìóì, îäèí èç òåõ ïóòåé) íå áëîêèðóåòñÿ íèêàêèì äðóãèì
÷ëåíîì ñåïàðàòîðà Z .
 ðàìêàõ àïïàðàòà îðèåíòèðîâàííûõ ãðàôîâ ïîíÿòèå íåèçáûòî÷íîãî d-ñåïà-
ðàòîðà (íàçâàííîãî «ìèíèìàëüíûì») îïðåäåëåíî â [16], ãäå èçó÷åíû òàêæå íå-
êîòîðûå åãî ñâîéñòâà. Â [5] ýòî ïîíÿòèå èñïîëüçóåòñÿ äëÿ îáîñíîâàíèÿ ïðîöåäóð
âûâîäà ñêåëåòà ìîäåëè. Â ýòèõ ðàáîòàõ óñòàíîâëåíî ñâîéñòâî, îòðàæåííîå âî
âòîðîì ïóíêòå ñôîðìóëèðîâàííîé â ñëåäóþùåì ðàçäåëå áàçîâîé òåîðåìû. Ïîç-
æå, íåçàâèñèìî îò óêàçàííûõ ðàáîò, àâòîð íàñòîÿùåé ñòàòüè äàë îïðåäåëåíèå ëî-
êàëüíî-ìèíèìàëüíûõ ñåïàðàòîðîâ è ïîêàçàë èõ ðîëü â âûâîäå ìîäåëè [15].
Èñïîëüçîâàíèå ËîÌÑ ïîçâîëèëî ðàçðàáîòàòü ýôôåêòèâíûå ïðàâèëà ïîäáîðà ñå-
ïàðàòîðîâ è âåðèôèêàöèè ðåáåð â îÀÎà [7, 8, 14].
Äëÿ êëàññà ÀÎÃ-ìîäåëåé ïîíÿòèÿ ËîÌÑ è ÍÈÑ ñîâïàäàþò [16]. Îäíàêî â îðè-
åíòèðîâàííî-öèêëè÷åñêèõ ãðàôàõ íå êàæäûé ËîÌÑ ÿâ-
ëÿåòñÿ íåèçáûòî÷íûì ñåïàðàòîðîì. Íà ðèñ. 1 ïðåäñòàâ-
ëåí ïðèìåð ÖÎÃ, ãäå äëÿ ïàðû âåðøèí ( , )X Y èìååòñÿ
øåñòü ëîêàëüíî-ìèíèìàëüíûõ ñåïàðàòîðîâ: { }R , { }Q V, ,
{ }R Z W, , , { }Q V Z W, , , , { }R T U W, , , , { }Q V T U W, , , , . Íå-
èçáûòî÷íûìè ÿâëÿþòñÿ ïåðâûé è âòîðîé èç ýòèõ ñåïà-
ðàòîðîâ, à ìèíèìàëüíûì — òîëüêî ïåðâûé.
Äëÿ âñåõ êëàññîâ ìîäåëåé èìååò ìåñòî âëîæåí-
íîñòü ìíîæåñòâ ñåïàðàòîðîâ íàçâàííûõ âèäîâ:
S � Smin ( , )X Y S � Snred ( , )X Y S � Slom ( , )X Y ,
ãäå çíàê ðàâåíñòâà ïîíèìàåòñÿ êàê «… ÿâëÿåòñÿ íåêîòîðûì …».
Óòâåðæäåíèÿ îòíîñèòåëüíî ËîÌÑ èëè ÍÈÑ íå ïåðåíîñÿòñÿ ïîëíîñòüþ íà
ìèíèìàëüíûå ñåïàðàòîðû (òåì áîëåå íà ëþáûå ñåïàðàòîðû). Òåì íå ìåíåå ñîâî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 39
Y
QV
RX
Z
W
T
U
Ðèñ. 1. Ãðàô ñ öèêëîíàìè
êóïíîñòü ôàêòîâ î ëîêàëüíî-ìèíèìàëüíûõ èëè èçáûòî÷íûõ ñåïàðàòîðàõ èíîãäà
ïîçâîëÿåò ïîëó÷àòü âûâîäû êàñàòåëüíî ìèíèìàëüíûõ ñåïàðàòîðîâ èëè ðåáåð.
Êàæäûé ìèíèìàëüíûé ñåïàðàòîð ÿâëÿåòñÿ òàêæå ëîêàëüíî-ìèíèìàëüíûì. Åñëè
íå ñóùåñòâóåò íè îäíîãî ËîÌÑ äëÿ ( , )X Y , òî íå ñóùåñòâóåò íèêàêîãî ñåïàðàòî-
ðà äëÿ ( , )X Y . Óñòàíîâëåííûå â ðàáîòàõ [7, 8] ïðàâèëà âçàèìîñâÿçè ìåæäó ñîñòà-
âàìè «ñîïðÿæåííûõ» ËîÌÑ ïîçâîëÿþò íàïðàâëÿòü è (àäàïòèâíî) îïòèìèçèðî-
âàòü ïîèñê ñëîæíûõ ìèíèìàëüíûõ ñåïàðàòîðîâ, èñõîäÿ èç çíàíèÿ óæå íàéäåí-
íûõ â «îêðåñòíîñòè» ïðîñòûõ ñåïàðàòîðîâ è ïàòòåðíîâ çàâèñèìîñòåé.
ÎÑÍÎÂÍÎÉ ÐÅÇÓËÜÒÀÒ
Ñôîðìóëèðîâàííàÿ íèæå òåîðåìà ÿâëÿåòñÿ ðàçâèòèåì ðåçóëüòàòîâ, ïîëó÷åííûõ
ðàíåå. Ïåðâàÿ (íåòî÷íàÿ) ôîðìóëèðîâêà òðåáîâàíèé ê ÷ëåíó ËîÌÑ è èäåÿ äî-
êàçàòåëüñòâà áûëè ïðèâåäåíû â [15]. Êîððåêòíàÿ ôîðìóëèðîâêà òåîðåìû è äî-
êàçàòåëüñòâî äëÿ ñëó÷àÿ îÀÎÃ-ìîäåëåé ïðåäñòàâëåíû â [14]. Ýòà òåîðåìà ïî-
âòîðåíà â [7] ñ äîáàâëåíèåì óòî÷íÿþùèõ óòâåðæäåíèé. Äîêàçàòåëüñòâî òåîðå-
ìû èç [14] ïðè íåçíà÷èòåëüíîì óòî÷íåíèè ëåãêî ðàñïðîñòðàíÿåòñÿ íà êëàññ
ÍÐÊÑ è êëàññ ÖÎà (ñ çàìåíîé ËîÌÑ íà ÍÈÑ). Ïðèâåäåì ðàñøèðåííóþ ôîð-
ìóëèðîâêó òåîðåìû è äîêàçàòåëüñòâî.
Áàçîâàÿ òåîðåìà î ÷ëåíå íåèçáûòî÷íîãî ñåïàðàòîðà. Ïóñòü â ãðàôå çàâè-
ñèìîñòåé, îáðàçîâàííîì èç îðèåíòèðîâàííûõ è áèîðèåíòèðîâàííûõ ðåáåð, âåð-
øèíà Z âõîäèò â ñîñòàâ íåêîòîðîãî íåèçáûòî÷íîãî ñåïàðàòîðà S äëÿ ïàðû âåð-
øèí ( , )X Y .  òàêîì ñëó÷àå âåðíî ñëåäóþùåå:
1) âåðøèíà Z ïåðåêðûâàåò íåêîòîðûé ïóòü ìåæäó âåðøèíàìè X è Y , ïðè÷åì
íà ýòîì ïóòè åñòü ïî êðàéíåé ìåðå îäíà âåðøèíà, êîòîðàÿ ëåæèò íà öåïè ìåæäó
âåðøèíàìè X è Y ;
2) ñóùåñòâóåò íåêîòîðûé îðïóòü îò âåðøèíû Z äî âåðøèíû X , êîòîðûé íå
ïðîõîäèò ÷åðåç Y , èëè ñóùåñòâóåò íåêîòîðûé îðïóòü � îò âåðøèíû Z äî âåðøè-
íû Y , êîòîðûé íå ïðîõîäèò ÷åðåç X ;
3) åñëè íå ñóùåñòâóåò íè îäíîé öåïè ìåæäó X è Z, êîòîðàÿ íå ïðîõîäèò ÷å-
ðåç Y , òî òîãäà:
3à) ñóùåñòâóþò ïî ìåíüøåé ìåðå äâå íåêîòîðûå öåïè �1 è � 2 ìåæäó Z è Y ,
êîòîðûå íå ïðîõîäÿò ÷åðåç X è çàêàí÷èâàþòñÿ äóãàìè � Y ;
3á) ñóùåñòâóåò íåêîòîðàÿ öåïü � 0 ìåæäó âåðøèíàìè X è Y , êîòîðàÿ íå ïðîõîäèò
÷åðåç âåðøèíó Z è çàêàí÷èâàåòñÿ äóãîé � Y ; ÷àñòü �
öåïè � 0 , ïðèëåãàþùàÿ ê âåðøè-
íå X , ÿâëÿåòñÿ ÷àñòüþ íåêîòîðîãî ïóòè � ìåæäó âåðøèíàìè X è Y , ïðè÷åì âòîðàÿ
÷àñòü �
ïóòè � ïðîõîäèò ÷åðåç âåðøèíó Z è ñóùåñòâóåò äóãà Z � íà �
; âñå êîë-
ëàéäåðû íà �
îòêðûòû ïðè êîíäèöèîíèðîâàíèè S \ {Z}; ïóñòü ïóòè � 0 è � ðàñõî-
äÿòñÿ íà âåðøèíå Q; òîãäà áëèæàéøèì ê X êîëëàéäåðîì íà ïóòè � áóäåò � �Q ,
à ÷àñòüþ öåïè � 0 , ïðèëåãàþùåé ê âåðøèíå Y , áóäåò îðïóòü âèäà � � ��� �Q Y .
Äîêàçàòåëüñòâî. Ñíà÷àëà ðàññìîòðèì ï. 2. Äîêàçàòåëüñòâî ñòðîèòñÿ ïî èòå-
ðàòèâíîé ñõåìå. Åñëè âåðøèíà Z ëåæèò íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè X
è Y , òî ñðàçó ïîëó÷àåì òðåáóåìîå. Èíà÷å, ïóñòü âåðøèíà Z íå ëåæèò íè íà êàêîé
öåïè ìåæäó âåðøèíàìè X è Y . Âåðøèíà Z ïåðåêðûâàåò ïî êðàéíåé ìåðå îäèí
íåêîòîðûé ïóòü � ìåæäó X è Y , ïðè÷åì Z íå ÿâëÿåòñÿ êîë-âåðøèíîé íà ïóòè �.
Áóäåì ïðîäâèãàòüñÿ ïî �, íà÷èíàÿ ñ äóãè Z �. ßñíî, ÷òî, ïðîõîäÿ äóãè ñîãëàñíî
èõ îðèåíòàöèè, ëèáî äîñòèãíåì âåðøèíû X èëè Y (è òîãäà äîêàçàòåëüñòâî çàâåð-
øåíî), ëèáî íàòîëêíåìñÿ íà íåêîòîðûé êîëëàéäåð � �Q1 (áëèæàéøèé ê âåðøè-
íå Z) íà ïóòè �. Ïîñêîëüêó Z ÿâëÿåòñÿ ÷ëåíîì ÍÈÑ S è ïåðåêðûâàåò ïóòü �, êîë-
ëàéäåð � �Q1 m-îòêðûò ïðè êîíäèöèîíèðîâàíèè ìíîæåñòâà âåðøèí S \ {Z}.
Çíà÷èò, ëèáî èìååì Q1 � S, ëèáî S âêëþ÷àåò íåêîòîðîãî ïîòîìêà âåðøèíû Q1,
ñêàæåì T1 (ïóñòü ýòî áëèæàéøèé òàêîé ïîòîìîê). Ñîîòâåòñòâåííî ïîëó÷èì
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
îðïóòü Z Q� ��� � 1 èëè Z Q T� ��� � � ��� �1 1. Ðàññìîòðèì T1 (èëè Q1) êàê ÷ëå-
íà ÍÈÑ àíàëîãè÷íî òîìó, êàê ðàññìàòðèâàëè âåðøèíó Z. Òåïåðü èç äîñòèãíóòîé
âåðøèíû ïðîäâèãàåìñÿ äàëåå ïî òîìó ïóòè ìåæäó X è Y , êîòîðûé ïåðåêðûâàåò-
ñÿ ñ ïîìîùüþ T1 (íà÷èíàÿ ñ äóãè T1 �). Ïîâòîðÿÿ èçëîæåííûå ðàññóæäåíèÿ èòå-
ðàòèâíî, ïðîäëåâàåì îðïóòü îò Z äî î÷åðåäíîãî ÷ëåíà Q2 (èëè T2) ñåïàðàòîðà S
è ò.ä. (Äëÿ îïðåäåëåííîñòè âîçüìåì Ti � S, èìåÿ â âèäó, ÷òî âîçìîæíî Q Ti i� .)
Åñëè äîïóñòèòü, ÷òî â ýòîì ïðîöåññå áóäåì ïîâòîðíî âîçâðàùàòüñÿ â òó æå ñàìóþ
âåðøèíó, ò.å. íåò íè îäíîé äóãè Ti �, êîòîðàÿ âûâîäèò èç öèêëîíà â ñòîðîíó X èëè
Y , òî ýòî îçíà÷àëî áû, ÷òî íåò íè îäíîãî îðïóòè, âûõîäÿùåãî èç êàêîé-ëèáî
ïðîéäåííîé êîë-âåðøèíû Qi è âåäóùåãî ê X , èëè ê Y , èëè ê äðóãèì ÷ëåíàì ìíî-
æåñòâà âåðøèí S \ {T Ti1, ..., }. Îòñþäà âûòåêàëî áû, ÷òî íè îäèí èç âñòðå÷åííûõ
êîëëàéäåðîâ � �Qi íå îòêðûâàåòñÿ ïðè êîíäèöèîíèðîâàíèè ÷ëåíîâ ìíîæåñòâà
S \ {T Ti1, ..., }. Çíà÷èò, íåò íè îäíîãî ïóòè ìåæäó X è Y ÷åðåç T Ti1, ,� , îòêðûòî-
ãî ïðè êîíäèöèîíèðîâàíèè S \ {T Ti1, ..., }. Òîãäà ìíîæåñòâî S \ {T Ti1, ..., } áûëî
áû ñåïàðàòîðîì äëÿ ïàðû ( , )X Y . Ýòî ïðîòèâîðå÷èò íåèçáûòî÷íîñòè S. Ñëåäîâà-
òåëüíî, íåîáõîäèìî ïðèçíàòü, ÷òî ñóùåñòâóåò îðïóòü îò Z äî âåðøèíû X èëè Y .
Ïóíêò 2 äîêàçàí.
Ïåðåõîäèì ê ï. 3à. Âåðøèíà Z ïåðåêðûâàåò íåêîòîðûé ïóòü � ìåæäó X è Y ;
áóäåì äâèãàòüñÿ ïî ýòîìó ïóòè îò Z â ñòîðîíó âåðøèíû X ; ïðîäâèæåíèå ïðèâå-
äåò ê íåêîòîðîìó êîëëàéäåðó � �Q1 , îòêðûòîìó ïðè êîíäèöèîíèðîâàíèè
S \ { }Z . Âåðøèíà Q1 èëè íåêîòîðûé åå ïîòîìîê âõîäèò â ñîñòàâ S. Ñëåäîâàòåëüíî,
ñóùåñòâóåò îðïóòü Q Y1 � ��� � . ( ïðîòèâíîì ñëó÷àå, ñîãëàñíî ï. 2 òåîðåìû,
ïðèäåòñÿ ïðåäïîëîæèòü ñóùåñòâîâàíèå îðïóòè Q X1 � ��� � , è òîãäà ïîëó÷èì
öåïü Z Q X— ��� � � ��� �1 , ÷òî ïðîòèâîðå÷èò óñëîâèþ ï. 3.) Òàêèì îáðàçîì,
èìååì ïåðâóþ èñêîìóþ öåïü �1: Z Q Y— ��� � � ��� �1 . Íàïîìíèì, ÷òî âåðøèíà Z
ïåðåêðûâàåò ïóòü � ìåæäó X è Y , ïîýòîìó ñóùåñòâóåò ïóòü � ZY îò Z â ñòîðîíó
âåðøèíû Y , êîòîðûé íà÷èíàåòñÿ äóãîé, îòëè÷íîé îò äóãè, âåäóùåé â ñòîðîíó
âåðøèíû X . Åñëè íà÷íåì ïðîäâèãàòüñÿ ïî ýòîìó ïóòè � ZY îò âåðøèíû Z â ñòî-
ðîíó âåðøèíû Y , òî ëèáî äîéäåì äî Y , íå âñòðåòèâ êîëëàéäåðà (÷òî çàâåðøàåò
äîêàçàòåëüñòâî), ëèáî íàòîëêíåìñÿ íà íåêîòîðûé êîëëàéäåð � �W . Ââèäó íå-
èçáûòî÷íîñòè S ýòîò êîëëàéäåð îòêðûò ïðè êîíäèöèîíèðîâàíèè S. Ñëåäîâàòåëü-
íî, àíàëîãè÷íî ïîêàçàííîìó âûøå äîëæåí áûòü îðïóòü W Y� ��� � . Òàêèì îáðà-
çîì, ïîëó÷àåì âòîðóþ èñêîìóþ öåïü � 2 :Z W Y� ��� � � ��� � .
Äîêàæåì ï. 3á. Âåðøèíà Z ïåðåêðûâàåò íåêîòîðûé ïóòü (ïóòè) ìåæäó X è Y , ñêà-
æåì �. (ßñíî, ÷òî âñå êîëëàéäåðû íà ïóòè � îòêðûòû ïðè êîíäèöèîíèðîâàíèè S \ {Z},
èíà÷å âåðøèíà Z íå áûëà áû ÷ëåíîì íèêàêîãî ÍÈÑ äëÿ ïàðû âåðøèí ( , )X Y .) Íà÷-
íåì ïðîäâèãàòüñÿ ïî ïóòè � îò Z â ñòîðîíó âåðøèíû X , ðàññìàòðèâàÿ êîë-âåðøèíû
íà ýòîì ïóòè. Ïóñòü ïåðâûì (áëèæàéøèì ê Z) âñòðåòèëñÿ êîëëàéäåð � �Q1 .
Åñëè ìåæäó Q1 è X ñóùåñòâóåò íåêîòîðàÿ öåïü �, íå ïðîõîäÿùàÿ ÷åðåç Y , òî
� (è êàæäàÿ òàêàÿ öåïü) èìååò âèä X Q� ��� � 1 (èíà÷å ïîëó÷èì ïðîòèâîðå÷èå
óñëîâèþ ï. 3). Ïîñêîëüêó êîëëàéäåð � �Q1 íà ïóòè � îòêðûò, ñóùåñòâóåò
îðïóòü Q R1 � ��� � , ãäå R Z� S \ { }. ( ÷àñòíîñòè, âîçìîæíî R Q� 1.) ßñíî, ÷òî
íå ñóùåñòâóåò íè îäíîãî îðïóòè âèäà R X� ��� � , èíà÷å ïîëó÷èëè áû öåïü
Z Q R X— ��� � � ��� � � ��� �1 , íå ïðîõîäÿùóþ ÷åðåç Y , ÷òî ïðîòèâîðå÷èò
óñëîâèþ ï. 3. Ñëåäîâàòåëüíî, ñîãëàñíî ï. 2 äîëæåí ñóùåñòâîâàòü îðïóòü âèäà
R Y� ��� � . Òîãäà êîíêàòåíàöèÿ öåïè � (ìåæäó Q1 è X ) ñ îðïóòåì Q R1 � ��� � è
îðïóòåì R Y� ��� � äàåò öåïü � 0 ìåæäó âåðøèíàìè X è Y , òðåáóåìóþ äëÿ
ï. 3á. ×àñòü öåïè � 0 íàëàãàåòñÿ íà ÷àñòü ïóòè � ìåæäó âåðøèíàìè X è Y , êîòî-
ðûé ïðîõîäèò ÷åðåç âåðøèíó Z.
Ïóñòü òåïåðü ìåæäó Q1 è X íå ñóùåñòâóåò öåïè, íå ïðîõîäÿùåé ÷åðåç Y .
Êîëëàéäåð � �Q1 íà ïóòè � îòêðûò ïðè êîíäèöèîíèðîâàíèè S \ }{Z . Ïðîäîë-
æèì ïðîäâèãàòüñÿ ïî ïóòè � â ñòîðîíó âåðøèíû X , ðàññìàòðèâàÿ êîë-âåðøèíû
íà ýòîì ïóòè. Ââèäó êîíå÷íîñòè ïóòè � îáÿçàòåëüíî âñòðåòèòñÿ òàêàÿ êîë-âåðøè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 41
íà Q, êîòîðàÿ ñîåäèíåíà ñ X öåïüþ �
, íå ïðîõîäÿùåé ÷åðåç Y , ïðè÷åì âñå ïðîé-
äåííûå êîëëàéäåðû îòêðûòû ïðè êîíäèöèîíèðîâàíèè S \ }{Z . Ñóùåñòâîâàíèå
îðïóòè Q Y� ��� � ñëåäóåò èç òîãî, ÷òî âåðøèíà, êîíäèöèîíèðîâàíèå êîòîðîé
îòêðûâàåò êîëëàéäåð � �Q íà ïóòè �, ïðèíàäëåæèò ÍÈÑ äëÿ ïàðû ( , )X Y . Ïî-
ëó÷åíû âñå íåîáõîäèìûå äëÿ ï. 3á âûâîäû.
Äîêàæåì ï. 1. Åñëè âåðøèíà Z ëåæèò íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè
X è Y , òî äîêàçàòåëüñòâî ï. 1 çàâåðøåíî. Åñëè âåðøèíà Z íå ëåæèò íè íà îäíîé
öåïè ìåæäó X è Y , òî áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ñîãëàñíî ï. 2 ñó-
ùåñòâóåò íåêîòîðûé îðïóòü îò âåðøèíû Z äî âåðøèíû Y , êîòîðûé íå ïðîõîäèò
÷åðåç X . Òîãäà âûïîëíÿþòñÿ óñëîâèÿ ï. 3 è òðåáóåìîå äîêàçàòåëüñòâî ñîäåðæèò-
ñÿ â äîêàçàòåëüñòâå ï. 3á. Äîêàçàòåëüñòâî òåîðåìû çàâåðøåíî.
Èçëîæåííîå äîêàçàòåëüñòâî îõâàòûâàåò âñå óïîìÿíóòûå âûøå êëàññû ìîäå-
ëåé, âêëþ÷àÿ ÍÐÊÑ è ÖÎÃ-ìîäåëè. Òåîðåìó ëåãêî ðàñïðîñòðàíèòü òàêæå íà äðó-
ãèå ñëó÷àè. Âîïðîñ îòêðûò äëÿ ìîäåëåé ñ «ôëàãàìè» è íåîðèåíòèðîâàííûìè ïåò-
ëÿìè (äëÿ íèõ íóæíî îïðåäåëèòü èëè âûáðàòü ñîîòâåòñòâóþùèé âàðèàíò ìàðêîâ-
ñêèõ ñâîéñòâ). Åñëè ðàññìîòðåòü ìîäåëü, ïîñòðîåííóþ èç ïîäëèííî
íåîðèåíòèðîâàííûõ ðåáåð, òî âñå ïóòè ñòàíîâÿòñÿ öåïÿìè è ïîíÿòèå êîëëàéäåðà
òåðÿåò ñìûñë. Òîãäà ï. 2 òåîðåìû òàêæå òåðÿåò ñìûñë, óñëîâèÿ ï. 3 âûïîëíèòü íå-
âîçìîæíî, à ï. 1 ïðèìåò ñëåäóþùóþ ôîðìó: âåðøèíà Z ïåðåêðûâàåò íåêîòîðóþ
öåïü ìåæäó X è Y .
Çàìåòèì, ÷òî áàçîâàÿ
òåîðåìà ïðåäîñòàâëÿåò íå-
îáõîäèìûå òðåáîâàíèÿ
ê ÷ëåíàì ÍÈÑ. Ýòèì òðå-
áîâàíèÿì ìîãóò òàêæå
óäîâëåòâîðÿòü íåêîòîðûå
âåðøèíû, íå ïðèíàäëåæà-
ùèå íèêàêîìó ÍÈÑ.
Íà ðèñ. 2 èçîáðàæåíû
äâå ìîäåëè, ãäå Z âõîäèò
â ñîñòàâ ÍÈÑ è ËîÌÑ äëÿ
ïàðû ( , )X Y , ïðè÷åì ï. 3
áàçîâîé òåîðåìû âûïîëíÿ-
åòñÿ. Ðàññìàòðèâàÿ ÍÐÊÑ
íà ðèñ. 2, à, íàõîäèì S { } Slom ( , ) , , , , ( , )minX Y R Q V W Z X Y� � . Âåðøèíà Z ïåðå-
êðûâàåò ïóòè ìåæäó X è Y , êîòîðûå ïðîõîäÿò ÷åðåç Q V W Z U, , , , (è ñîîòâåòñòâó-
þùèå íåïîèìåíîâàííûå âåðøèíû, îòîáðàæåííûå êðóæêàìè). Êàæäûé èç ïóòåé �
ïðîõîäèò ÷åðåç âåðøèíó Q, êîòîðàÿ ëåæèò íà öåïè ìåæäó X è Y . Äâå öåïè, �1 è � 2 ,
óïîìÿíóòûå â ï. 2, — îðïóòü �: Z U Y� � è öåïü Z W Y� � . Öåïü � 0 — ýòî
X Q Y� � .
Íà ðèñ. 2, á ïîêàçàí ïðèìåð ÖÎÃ. Ýòà ìîäåëü, â ÷àñòíîñòè, îòëè÷àåòñÿ òåì, ÷òî
äëÿ ñåïàðàòîðà S { } Snred ( , ) , , , ( , )minX Y R Q T Z X Y� � �S âåðøèíà Z ïåðåêðûâàåò
íåñêîëüêî ïóòåé, íà êîòîðûõ âñå êîë-âåðøèíû, êðîìå îäíîé, íå âõîäÿò â ñîñòàâ S.
Ýòè êîë-âåðøèíû îòêðûâàþòñÿ ïðè êîíäèöèîíèðîâàíèè âåðøèíû T . Êðîìå òîãî,
â îòëè÷èå îò ñëó÷àÿ íà ðèñ. 2, à, â ýòîì ÖÎà ñóùåñòâóåò çàâèñèìîñòü ~ ( ;; )Ds X Z .
ÔÎÐÌÈÐÎÂÀÍÈÅ ÍÈÑ È ËîÌÑ
Èç áàçîâîé òåîðåìû âûòåêàþò ñëåäñòâèÿ.
Ñëåäñòâèå 1. Åñëè Z X Y�Snred ( , ) è íå ñóùåñòâóåò íè îäíîé öåïè ìåæäó X
è Z, òî âñå öåïè ìåæäó âåðøèíàìè Z è Y çàêàí÷èâàþòñÿ äóãàìè � Y è âñå öåïè
ìåæäó X è Y çàêàí÷èâàþòñÿ äóãàìè � Y .
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
W
T
V
Z
U
X YQ
R
Q
Z
U
X Y
R
W
V
Ðèñ. 2. Èëëþñòðàöèÿ áàçîâîé òåîðåìû: ÍÐÊÑ (à); ÖÎÃ ñ îä-
íèì öèêëîíîì (á)
a á
Ñëåäñòâèå 2 (ïðàâèëî àïïåíäèêñà). Åñëè ñóùåñòâóåò òàêàÿ R, ÷òî âåðíî
Ds Ds( ; ; )& ( ; ; )X R Z Y R Z , òî Z íå ïðèíàäëåæèò íèêàêîìó Snred ( , )X Y .
(Ëîãèêà ýòîãî ïðàâèëà ïîäîáíà ëîãèêå ïðàâèëà îòñòðàíåíèÿ.)
Ñëåäñòâèå 3 (ïðàâèëî ïîëó÷óæîãî ãåíà; semi-alien gene). Åñëè âåðíû ôàêòû
Ds ( ;; )X Z , ~ ( ;; )Ds W Z è Ds ( ;; )W Y , òî Z íå ïðèíàäëåæèò íèêàêîìó Snred ( , )X Y .
Äëÿ âñåõ èçâåñòíûõ êëàññîâ ñåòåé çàâèñèìîñòåé âåðíî ñëåäóþùåå ïðîñòîå,
íî âàæíîå óòâåðæäåíèå.
Ïðèíöèï ñòåðæíÿ ñåïàðàòîðà (necessity of separator’s pivot). Â ñîñòàâ êàæ-
äîãî ñåïàðàòîðà äëÿ ïàðû áåçóñëîâíî çàâèñèìûõ âåðøèí ( , )X Y âõîäèò, êàê ìè-
íèìóì, îäíà âåðøèíà Z, êîòîðàÿ ëåæèò íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè X
è Y . (Òàêàÿ âåðøèíà Z íàçûâàåòñÿ ñòåðæíåì ñåïàðàòîðà äëÿ ( , )X Y .)
Ýòî óòâåðæäåíèå äîêàçûâàåòñÿ ïðîñòî (ñì., íàïðèìåð, [14]). Â ï. 1 áàçîâîé
òåîðåìû ñîäåðæèòñÿ âàðèàíò ïðèíöèïà ñòåðæíÿ äëÿ ÍÈÑ. Ïðåäïîëîæèòåëüíî,
äëÿ ïðèíöèïà ñòåðæíÿ ìîæíî íàéòè óíèâåðñàëüíîå îñíîâàíèå — ïðèíöèï îáùåé
ïðè÷èíû (H. Reichenbach).
Äëÿ âñåõ óêàçàííûõ âûøå êëàññîâ ìîäåëåé âûïîëíÿåòñÿ ñëåäóþùåå ïðàâèëî.
Ïðàâèëî îòñòðàíåíèÿ. Åñëè â îðãðàôå ìîäåëè âåðíî Ds ( ; ; )X Y Z , òî âåð-
øèíà Z íå âõîäèò â ñîñòàâ íèêàêîãî ÍÈÑ äëÿ ïàðû âåðøèí ( , )X Y .
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì ïðîòèâíîå, ò.å. ïóñòü âåðíî Ds ( ; ; )X Y Z è
Z X Y�Snred ( , ) . Òîãäà ôàêò Ds ( ; ; )X Y Z îçíà÷àåò, ÷òî íå ñóùåñòâóåò íèêàêîé
öåïè ìåæäó âåðøèíàìè Z è X , êîòîðàÿ íå ïðîõîäèò ÷åðåç Y . Ñëåäîâàòåëüíî, ââè-
äó ôàêòà Z X Y�Snred ( , ) è â ñèëó ï. 3á áàçîâîé òåîðåìû ñóùåñòâóåò íåêîòîðàÿ
öåïü �: X Y� ��� � , êîòîðàÿ íå ïðîõîäèò ÷åðåç Z. Ñîãëàñíî ï. 2 áàçîâîé òåîðåìû
ñóùåñòâóåò îðïóòü �: Z Y� ��� � , êîòîðûé íå ïðîõîäèò ÷åðåç X . Êîíêàòåíàöèÿ
öåïè � è îðïóòè � îáðàçóåò ïóòü ìåæäó Z è Y ñ îäíèì êîëëàéäåðîì. Ïðè ýòîì
âîçìîæíû äâà ñëó÷àÿ: 1) îðïóòü � è öåïü � íå ïåðåñåêàþòñÿ, à ñòûêóþòñÿ íà âåð-
øèíå Y ; 2) îðïóòü � è öåïü � ïåðåñåêàþòñÿ íà íåêîòîðîé âåðøèíå W. Â ïåðâîì
ñëó÷àå (ïî îïðåäåëåíèþ m-ñåïàðàöèè) ïîëó÷àåì ~ ( ; ; )Ds X Y Z , ÷òî ïðîòèâîðå-
÷èò óñëîâèþ ïðàâèëà. Âî âòîðîì ñëó÷àå ëåãêî âèäåòü, ÷òî îðïóòü � è öåïü � ñõî-
äÿòñÿ ê âåðøèíå W äóãàìè � W, ò.å. èìåþò âèä Z W Y� ��� � � ��� � è
X W Y� ��� � � ��� � . (Äåéñòâèòåëüíî, åñëè ïðåäïîëîæèòü àëüòåðíàòèâíóþ îðè-
åíòàöèþ äóã âîçëå âåðøèíû W, òî ïîëó÷èì öåïü ìåæäó âåðøèíàìè Z è X , êîòî-
ðàÿ íå ïðîõîäèò ÷åðåç Y , ÷òî ïðîòèâîðå÷èò ôàêòó Ds ( ; ; )X Y Z ). Ñëåäîâàòåëüíî,
âî âòîðîì ñëó÷àå (ïî îïðåäåëåíèþ m-ñåïàðàöèè) ïîëó÷èì ~ ( ; ; )Ds X Y Z , ÷òî
òàêæå ïðîòèâîðå÷èò óñëîâèþ ïðàâèëà.
Äàííîå äîêàçàòåëüñòâî ëàêîíè÷íåå ïðåäëîæåííûõ ðàíåå è îõâàòûâàåò êëàññ
ÖÎÃ-ìîäåëåé. Âàðèàíò äîêàçàòåëüñòâà, èçëîæåííûé â [14], èñïîëüçóåò çàïðåò öèê-
ëîíîâ. (Âàðèàíò äîêàçàòåëüñòâà èç [7] ñîäåðæèò íåòî÷íîñòè.) Äëÿ ñòàòèñòè÷åñêîãî
òåñòèðîâàíèÿ öåëåñîîáðàçíåå èñïîëüçîâàòü ïðàâèëî àêòóàëüíîãî îòñòðàíåíèÿ [7, 14].
Òðèâèàëüíûì ñëåäñòâèåì èç ïðàâèëà îòñòðàíåíèÿ ÿâëÿåòñÿ ïðàâèëî ïðîâî-
êàöèè: åñëè Z X Y�Snred ( , ) è âåðíî Ds ( ;; )X Z , òî ~ ( ; ; )Ds X Y Z .
Áàçîâàÿ òåîðåìà èñïîëüçîâàíà äëÿ äîêàçàòåëüñòâà ðÿäà ïðàâèë. Âñå ïðàâèëà,
ïðåäëîæåííûå â [7, 8] (à òàêæå ïðàâèëà, ðåàëèçîâàííûå â àëãîðèòìå âûâîäà ìî-
äåëè [9, 11]), ìîæíî ðàçáèòü íà «ñåìåéñòâà» ñîãëàñíî âûïîëíÿåìîé èìè ôóíêöèè
(ðîëè). Ïðàâèëà ýòèõ ñåìåéñòâ ðàñïîçíàþò ñîîòâåòñòâåííî: ïðèñóòñòâèå ðåáðà;
îòñóòñòâèå ðåáðà; âåðøèíó êàê íå ÷ëåíà íèêàêîãî ËîÌÑ (ÍÈÑ) äëÿ çàäàííîé
ïàðû âåðøèí; âåðøèíó êàê îáÿçàòåëüíîãî ÷ëåíà âñåõ ËîÌÑ (ÍÈÑ) äëÿ ïàðû âåð-
øèí. (Ñóùåñòâóþò òàêæå ïðàâèëà ñ äðóãèìè ôóíêöèÿìè.)
Õîòÿ óïîìÿíóòûå ïðàâèëà áûëè ñôîðìóëèðîâàíû äëÿ îÀÎÃ-ìîäåëåé, òåì
íå ìåíåå ìíîãèå ïðàâèëà ñîõðàíÿþò ñèëó è â áîëåå îáùåì ñëó÷àå. Íåêîòîðûå èç
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 43
ïðàâèë îñòàíóòñÿ êîððåêòíûìè ïîñëå óòî÷íåíèÿ ôîðìóëèðîâêè. Íàïðèìåð, â
õîäå äîêàçàòåëüñòâà íåñêîëüêèõ ïðàâèë, ðàñïîçíàþùèõ îòñóòñòâèå ðåáðà â îÀÎÃ
(â òîì ÷èñëå íåïîãëîùåíèÿ, èçîëÿòîðà, ïîëóàïïåíäèêñà, êâàçèèíñòðóìåíòàëüíîé
ïàðû [7, 8]), íåÿâíî èñïîëüçîâàëàñü ñëåäóþùàÿ ëîãèêà ðàññóæäåíèé: «Ïîñêîëüêó
íåâîçìîæíî íè ðåáðî X Y� , íè ðåáðî X Y� , òî íå ñóùåñòâóåò íèêàêîãî ðåáðà
ìåæäó X è Y ». ßñíî, ÷òî äëÿ ñëó÷àÿ ÍÐÊÑ íåîáõîäèìî ïåðåïèñàòü îêîí÷àíèå
ýòîãî óòâåðæäåíèÿ òàêèì îáðàçîì: «…, òî íåò îäíîîðèåíòèðîâàííîãî ðåáðà ìåæ-
äó X è Y ». Â äîêàçàòåëüñòâå äðóãèõ ïðàâèë òàêæå ïðåäïîëàãàëîñü, ÷òî îòñó-
òñòâóþò áèîðèåíòèðîâàííûå ðåáðà. Ïîýòîìó äëÿ ÍÐÊÑ òåðÿþò ñèëó òàêèå ïðà-
âèëà: «ìíîæåñòâà èçîëèðîâàííûõ îáùèõ êîâàðèàò» è «èçîëèðîâàííîé îáùåé êî-
âàðèàòû â êîíòåêñòå» (ñì. ïðåäëîæåíèÿ 4 è 5 â [8]). Íà êëàññ ÍÐÊÑ íåëüçÿ
ðàñïðîñòðàíèòü óòâåðæäåíèå î ñóùåñòâîâàíèè «ãåíåòè÷åñêè ìèíèìàëüíîãî» ñå-
ïàðàòîðà (ïðàâèëî 3 â [17]). Â ÖÎÃ-ìîäåëÿõ ïðàâèëî ÷óæîãî ãåíà (alien gene) èç
[7, 11, 17] êîððåêòíî äëÿ ÍÈÑ, íî äëÿ ËîÌÑ òðåáóåò äîïîëíèòåëüíûõ óñëîâèé.
Äëÿ ËîÌÑ â ÖÎÃ-ìîäåëÿõ íåâåðíû ïðàâèëî èçîëÿòîðà è ôàêò 10 èç [7].
 îòëè÷èå îò îÀÎÃ-ìîäåëåé â ÍÐÊÑ, ñìåøàííûõ ñåòÿõ è ÖÎà èìïëèêà-
öèÿ (1) íå âûïîëíÿåòñÿ. Èíûìè ñëîâàìè, áûâàþò ñëó÷àè, êîãäà ñåïàðàòîðà íå ñó-
ùåñòâóåò äëÿ ïàðû âåðøèí, íå ñâÿçàííûõ ðåáðîì [1, 2, 4, 5]. Íà ðèñ. 3 ïðè-
âåäåíû ïðîñòûå ïðèìåðû ìîäåëåé, ãäå äëÿ íåñìåæíûõ âåðøèí X è Y íå ñóùåñ-
òâóåò m-ñåïàðàòîðà. Ñëó÷àé ÖÎà íà ðèñ. 3, á ïàðàäîêñàëåí òåì, ÷òî åäèíñòâåí-
íàÿ öåïü ìåæäó X è Y ïðîõîäèò ÷åðåç Z, è ïðè ýòîì âåðøèíû X è Z ìîæíî
ñåïàðèðîâàòü, à X è Y — íåò.
Çàìåòèì, ÷òî â àíöåñò-
ðàëüíûõ ìîäåëÿõ è ÍÐÊÑ îò-
ñóòñòâèå ñåïàðàòîðà äëÿ íå-
ñìåæíûõ âåðøèí (X , Y ) íåâîç-
ìîæíî â òîì ñëó÷àå, åñëè
èìååòñÿ òîëüêî îäíà öåïü ìåæ-
äó X è Y . Ïîýòîìó ïðàâèëà,
çàïèñàííûå â [8] êàê ïðåäëî-
æåíèå 6 (ïðîñòîé ïîòåíöèàëü-
íûé ñòåðæåíü ñåïàðàòîðà) è
ïðåäëîæåíèå 10 (èçîëÿöèÿ
åäèíñòâåííîãî âîçìîæíîãî
ñòåðæíÿ ñåïàðàòîðà), îñòàþòñÿ
êîððåêòíûìè äëÿ ÍÐÊÑ è àíöåñòðàëüíûõ ãðàôîâ. Íî äëÿ ÌÀÎÃ ýòè ïðàâèëà ñòà-
íîâÿòñÿ íåâåðíûìè â ñëó÷àå, êîãäà åäèíñòâåííûé êàíäèäàò â ñòåðæíè èìååò
òîëüêî îäíîãî ðîäèòåëÿ.
Îáðàòèìñÿ ê âîïðîñó îá îáÿçàòåëüíûõ èëè óñëîâíî-îáÿçàòåëüíûõ ÷ëåíàõ
âñåõ ÍÈÑ (ËîÌÑ) äëÿ çàäàííîé ïàðû âåðøèí. Ñîãëàñíî ïðèíöèïó ñòåðæíÿ â ñî-
ñòàâ êàæäîãî íåïóñòîãî ñåïàðàòîðà äëÿ ïàðû âåðøèí ( , )X Y äîëæíà âõîäèòü õîòÿ
áû îäíà âåðøèíà Z, êîòîðàÿ ëåæèò íà íåêîòîðîé öåïè ìåæäó âåðøèíàìè X è Y .
Íåîáõîäèìûå òðåáîâàíèÿ ê ñòåðæíþ ñåïàðàòîðà ñôîðìóëèðîâàíû â [8] ÷åðåç ïî-
íÿòèå ïîòåíöèàëüíîãî ñòåðæíÿ ñåïàðàòîðà. Ïîòåíöèàëüíûì ñòåðæíåì ñåïàðàòîðà
äëÿ ïàðû ( , )X Y íàçâàíà âåðøèíà Z, óäîâëåòâîðÿþùàÿ óñëîâèÿì: ~ ( ;; )Ds X Z ,
~ ( ;; )Ds Y Z , ~ ( ; ; )Ds X Y Z è ~ ( ; ; )Ds Z X Y . Ìîæíî óæåñòî÷èòü òðåáîâàíèÿ
ê ñòåðæíþ ñåïàðàòîðà, îïèðàÿñü íà áàçîâóþ òåîðåìó. Ñôîðìóëèðóåì ïîíÿòèå
«ïðåòåíäåíò â ñòåðæíè» (ïðåä-ñòåðæåíü; pre-pivot).
Îïðåäåëåíèå 3. Âåðøèíà Z íàçûâàåòñÿ ïðåòåíäåíòîì â ñòåðæíè ñåïàðàòîðà
äëÿ ïàðû âåðøèí ( , )X Y , åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
1) ~ ( ;; )& ~ ( ;; )& ~ ( ; ; )& ~ ( ; ; )Ds Ds Ds DsX Z Y Z X Y Z Z X Y ;
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
X Z Y
X Y
Z
Q
X Y
Z
Q
X Z Y
Ðèñ. 3. Ìîäåëè ñ íåñåïàðèðóåìûìè âåðøèíàìè: ÍÐÊÑ (à);
ÖÎà (á); ÌÀÎà (â); ÖÎà ñ êðàò÷àéøèì öèêëîíîì (ã)
a á
â ã
2) íå ñóùåñòâóåò òàêîé âåðøèíû R, ÷òî âåðíî Ds Ds( ; ; )& ( ; ; )X R Z Y R Z ;
3) íå ñóùåñòâóåò òàêèõ W è Q, ÷òî âåðíî ~ ( ;; )& ~ ( ;; )Ds DsW Z Q Z &
& Ds Ds( ;; )& ( ;; )W X Q Y (â ÷àñòíîñòè, îõâàòûâàåòñÿ ñëó÷àé W Q� ).
Óñëîâèå 3 îáúåäèíÿåò ïðàâèëî ÷óæîãî ãåíà (êîãäà W Q� ) è ïðàâèëî èçîëÿòî-
ðà. Îïðåäåëåíèå 3 íå èñ÷åðïûâàåò íåîáõîäèìûõ òðåáîâàíèé ê ñòåðæíÿì ñåïàðàòî-
ðà (â ÷àñòíîñòè, ó÷òåíû íå âñå ñâîéñòâà èç [7, 8]). Çàìåòèì, ÷òî äëÿ ìîäåëè íà ðèñ.
3, á äëÿ ïàðû ( , )X Z èìååòñÿ òîëüêî îäèí ñòåðæåíü ñåïàðàòîðà (Q), îäíàêî ïðåòåí-
äåíòîì â ñòåðæåíü ÿâëÿåòñÿ òàêæå Y . Èíòåðåñíî, ÷òî íèêàêèå ôàêòû (íå)çàâèñè-
ìîñòè íå ïîìîãàþò ðàñïîçíàòü, ÷òî Y íå ëåæèò íè íà êàêîé öåïè ìåæäó X è Z.
Îõàðàêòåðèçóåì òåõ ÷ëåíîâ ÍÈÑ (ËîÌÑ), êîòîðûå íå ÿâëÿþòñÿ ñòåðæíÿìè
ñåïàðàòîðà.
Îïðåäåëåíèå 4. Âåðøèíà Z íàçûâàåòñÿ íåñòåðæíåâûì (non-pivotal), èëè âîâ-
ëå÷åííûì (engaged), ÷ëåíîì ÍÈÑ äëÿ ïàðû âåðøèí ( , )X Y , åñëè Z íå ëåæèò íè íà
îäíîé öåïè ìåæäó âåðøèíàìè X è Y è ÿâëÿåòñÿ ÷ëåíîì õîòÿ áû îäíîãî
Snred ( , )X Y .
 îòëè÷èå îò êëàññà îÀÎà â êëàññàõ ÖÎà è ÌÀÎà âåð-
øèíà Z, óäîâëåòâîðÿþùàÿ îïðåäåëåíèþ 4, ìîæåò îáëàäàòü
ñâîéñòâîì ~ ( ;; )&Ds Z X ~ ( ;; )Ds Z Y . Èëëþñòðàöèåé ñëó-
æèò ðèñ. 2, á. Îòìåòèì, ÷òî â ÖÎÃ âîçìîæåí ïàðàäîêñàëüíûé
ñëó÷àé, êîãäà äëÿ Z X Y�Slom ( , ) âûïîëíÿåòñÿ
Ds Ds( ;; )& ( ;; )Z X Z Y . Ïðèìåð ïðåäñòàâëåí íà ðèñ. 4, ãäå
S { }lom ( , ) , , ,X Y R Q W Z� , Snred ( , ) { }X Y R� .
Òåïåðü ñêîìïèëèðóåì íåêîòîðûå íåîáõîäèìûå òðå-
áîâàíèÿ ê íåñòåðæíåâûì ÷ëåíàì ÍÈÑ (ËîÌÑ).
Îïðåäåëåíèå 5. Âåðøèíà Z íàçûâàåòñÿ ïðåòåíäåíòîì â íåñòåðæíåâûå (âîâ-
ëå÷åííûå) ÷ëåíû ÍÈÑ äëÿ ïàðû âåðøèí ( , )X Y , åñëè îíà óäîâëåòâîðÿåò ñëåäóþ-
ùèì óñëîâèÿì:
1) ~ ( ; ; )& ~ ( ; ; )& {~ ( ;; )Ds Ds DsX Y Z Z X Y X Z or ~ ( ;; )Ds Y Z };
2) íå ñóùåñòâóåò òàêîé R, ÷òî âåðíî Ds Ds( ; ; )& ( ; ; )X R Z Y R Z ;
3) íå ñóùåñòâóåò òàêèõ W è Q, ÷òî âåðíî ~ ( ;; )Ds W Z & ~ ( ;; )&Ds Q Z
& ( ;; )&Ds W X Ds ( ;; )Q Y (â ÷àñòíîñòè, îõâàòûâàåòñÿ ñëó÷àé W Q� );
4) åñëè Ds ( ;; )Z X , òî íå ñóùåñòâóåò òàêîé W, ÷òî âåðíî ~ ( ;; )&Ds W Z
& ( ;; )Ds W Y .
Îáúåäèíèì óêàçàííûå íåîáõîäèìûå òðåáîâàíèÿ è îõàðàêòåðèçóåì ÍÈÑ
â öåëîì.
Ïðèíöèï êîìïîçèöèè ÍÈÑ. Êàæäûé (íåïóñòîé) ÍÈÑ äëÿ ïàðû âåðøèí
( , )X Y ñîñòîèò èç íåïóñòîãî ìíîæåñòâà V ïðåòåíäåíòîâ â ñòåðæíè ñåïàðàòîðà äëÿ
ïàðû ( , )X Y è íåêîòîðîãî ìíîæåñòâà L (ìîæåò áûòü, ïóñòîãî) ïðåòåíäåíòîâ â íå-
ñòåðæíåâûå (âîâëå÷åííûå) ÷ëåíû ÍÈÑ äëÿ ïàðû âåðøèí ( , )X Y . Åñëè ìíîæåñòâî
L íå ïóñòîå, òî íåêîòîðàÿ âåðøèíà Q �L m-çàâèñèò îò íåêîòîðîé âåðøèíû R �V.
Ïðîöåññ âûâîäà (ñèíòåçà) ñêåëåòà ìîäåëè [2, 3, 5, 6, 8, 9] ìîæíî ñâåñòè ê ïî-
èñêó ñåïàðàòîðîâ. Äëÿ ýôôåêòèâíîñòè ýòîãî ïðîöåññà íåîáõîäèìî ñîêðàùàòü
ìíîæåñòâî êàíäèäàòîâ â ÷ëåíû ñåïàðàòîðà (îòâåðãàÿ êàíäèäàòîâ) è ðàñïîçíàâàòü
ñóùåñòâîâàíèå èëè îòñóòñòâèå ðåáðà êàê ìîæíî ðàíüøå. Íàïðèìåð, èçâåñòíûé
àëãîðèòì PC [2, 3, 5] ðàññìàòðèâàåò êàê êàíäèäàòîâ â ÷ëåíû ñåïàðàòîðà äëÿ ïàðû
( , )X Y âñå âåðøèíû, êîòîðûå ñ÷èòàþòñÿ (âîçìîæíî) ñìåæíûìè ê X èëè Y . Ïðà-
âèëà è òðåáîâàíèÿ, ïðåäëîæåííûå âûøå, à òàêæå â [7–9], ñóùåñòâåííî îáîãàùà-
þò òàêòèêó âûâîäà ìîäåëè è ïîâûøàþò ýôôåêòèâíîñòü îòñåèâàíèÿ êàíäèäàòîâ
â ñåïàðàòîðû. Äåéñòâèòåëüíî, íåêîòîðûå èç ðàçðàáîòàííûõ ïðàâèë èíîãäà ïîçâî-
ëÿþò èñêëþ÷èòü èç ñïèñêà êàíäèäàòîâ â ÷ëåíû ñåïàðàòîðà äëÿ ( , )X Y âåðøèíó,
ñìåæíóþ ñ X èëè Y . Óñëîâèå 3 îïðåäåëåíèÿ 3 îòêðûâàåò âîçìîæíîñòü îòêëîíÿòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 45
Y
W
RX
Q
Z
Ðèñ. 4. Ïðèìåð ÖÎÃ
íåêîòîðûõ êàíäèäàòîâ â ÷ëåíû ñåïàðàòîðà äëÿ ( , )X Y , êîòîðûå ÿâëÿþòñÿ ñìåæ-
íûìè îäíîâðåìåííî ñ X è Y . Âàæíî, ÷òî ïîëó÷åííûå ðåçóëüòàòû ïîçâîëÿþò çà-
âåðøèòü ïðîöåññ âûâîäà ìîäåëè íàìíîãî ðàíüøå, ÷åì òðàäèöèîííûå ìåòîäû.
Ïðèíöèïû òàêîãî çàâåðøåíèÿ âûâîäà ñôîðìóëèðîâàíû â [7–9] êàê ðåçîëþöèè
(íå)ñìåæíîñòè. Îäíàêî ââèäó òîãî ÷òî â îáùåì ñëó÷àå îòñóòñòâèå ñåïàðàòîðà íå
îáÿçàòåëüíî îçíà÷àåò ñóùåñòâîâàíèå ðåáðà, íåîáõîäèìî ïåðåôîðìóëèðîâàòü
íåêîòîðûå ðåçîëþöèè.
Ýêñïðåññ-ðåçîëþöèÿ ñìåæíîñòè: åñëè äëÿ ïàðû çàâèñèìûõ âåðøèí ( , )X Y íå
îñòàëîñü íè îäíîãî íå îòâåðãíóòîãî ïðåòåíäåíòà â ñòåðæíè ñåïàðàòîðà, òî ñóùåñò-
âóåò ðåáðî ìåæäó X è Y . Òàêèì îáðàçîì, ïîëó÷àåì ñèëüíîå äîñòàòî÷íîå óñëîâèå
äëÿ èäåíòèôèêàöèè ðåáðà â ìîäåëè. (Ýòà ðåçîëþöèÿ âåðíà äàæå äëÿ îáùåãî êëàññà
ñìåøàííûõ ãðàôîâ. Òàêæå êîððåêòíî ïðàâèëî Lack of separator’s pivot [11].)
Òðàäèöèîííûé ïðèíöèï çàâåðøåíèÿ ïîèñêà ñåïàðàòîðà ïðèíèìàåò íîâóþ
ôîðìó. Ðåçîëþöèÿ íåñåïàðàáåëüíîñòè: åñëè äëÿ ïàðû çàâèñèìûõ âåðøèí ( , )X Y
èñïûòàíû âñå «îáÿçàòåëüíûå» âàðèàíòû íàáîðîâ íå îòâåðãíóòûõ êàíäèäàòîâ
â ÷ëåíû ñåïàðàòîðà (â ñîîòâåòñòâèè ñ ïðèíöèïîì êîìïîçèöèè ÍÈÑ) è íåçàâèñè-
ìîñòè (ñåïàðàöèè) íå íàéäåíî, òî íèêàêîãî ñåïàðàòîðà äëÿ ( , )X Y íå ñóùåñòâóåò.
Âî ìíîãèõ ñèòóàöèÿõ íåñåïàðàáåëüíîñòü âëå÷åò ñìåæíîñòü, íàïðèìåð, äëÿ
àíöåñòðàëüíûõ ãðàôîâ, ïðè óñëîâèè, ÷òî îñòàëñÿ òîëüêî îäèí íå îòâåðãíóòûé
ïðåòåíäåíò â ñòåðæíè ñåïàðàòîðà. Êðîìå òîãî, áûñòðàÿ èäåíòèôèêàöèÿ îòñóò-
ñòâèÿ îðïóòè [8, 17] äàåò âîçìîæíîñòü èäåíòèôèöèðîâàòü îòñóòñòâèå êàóçàëüíîé
ñâÿçè êîñâåííî, áåç íàõîæäåíèÿ ñîîòâåòñòâóþùåãî ôàêòà íåçàâèñèìîñòè.
Êîãäà èäåíòèôèöèðîâàíà íåñåïàðàáåëüíîñòü âåðøèí X è Y (íî íåò óâåðåí-
íîñòè â ïðèñóòñòâèè ðåáðà), âîçìîæíû òðè âàðèàíòà ðåøåíèÿ. Ïðèäåðæèâàÿñü
ïðèíöèïà, ïðèíÿòîãî â îÀÎÃ, ìîæíî ñ÷èòàòü, ÷òî ðåáðî ñóùåñòâóåò. Èíà÷å, âîï-
ðîñ î ñóùåñòâîâàíèè ðåáðà îñòàåòñÿ íåðåøåííûì. È íàêîíåö, ìîæíî ïðèáåãíóòü
ê àëüòåðíàòèâíûì ìåòîäàì âåðèôèêàöèè ðåáðà (ðå÷ü èäåò î âûâîäå ìîäåëè èç
äàííûõ).  ÷àñòíîñòè, â ñîñòàâå ÌÀÎÃ-ìîäåëè äëÿ òàê íàçûâàåìîé Ð-êîíôèãóðà-
öèè îòñóòñòâèå ðåáðà ïðîÿâëÿåòñÿ êàê ñïåöèàëüíûé ïàòòåðí (Verma constraint).
Èçâåñòíû ìåòîäû âåðèôèêàöèè èíñòðóìåíòàëüíîñòè ïåðåìåííîé, êîòîðûå èíîã-
äà ìîãóò ïîäòâåðäèòü ñóùåñòâîâàíèå ñîîòâåòñòâóþùåãî ðåáðà èëè ïðåäîñòàâèòü
àñèìïòîòè÷åñêè êîððåêòíûå ñâèäåòåëüñòâà îá åãî îòñóòñòâèè.
×òîáû ïîëó÷èòü ýìïèðè÷åñêèå «äâîéíèêè» (counterparts) ïðåäëîæåííûõ
ïðàâèë, ïðåäíàçíà÷åííûå äëÿ âûâîäà ñêåëåòà ìîäåëè èç äàííûõ (èëè èç ðàñïðå-
äåëåíèÿ âåðîÿòíîñòåé), òðåáóåòñÿ â ëåâîé ÷àñòè ñîîòâåòñòâóþùåãî ïðàâèëà çàìå-
íèòü ãðàôîâûå ïðåäèêàòû ñòàòèñòè÷åñêèìè.  ìîäåëÿõ áåç öèêëîíîâ çàìåíà òåð-
ìà âèäà ~ ( ; ; )Ds A B C òåðìîì ~ ( ; ; )Pr A B C êîððåêòíà â ñèëó èìïëèêàöèè (2).
Äëÿ îáîñíîâàíèÿ êîððåêòíîñòè çàìåíû Ds ( ; ; )A B C íà Pr( ; ; )A B C íåîáõîäèìî
ïðèíÿòü ñîîòâåòñòâóþùèå âåðñèè ïðåäïîëîæåíèÿ êàóçàëüíîé íåîáìàí÷èâîñòè.
Ïîñêîëüêó â òðåáîâàíèÿõ ê ÷ëåíàì ÍÈÑ (ËîÌÑ) è â óñëîâèÿõ ïðåäëîæåííûõ ïðà-
âèë èñïîëüçîâàíû èñêëþ÷èòåëüíî ôàêòû m-íåçàâèñèìîñòè íóëåâîãî è ïåðâîãî
ðàíãà, òî è ïðåäïîëîæåíèÿ òðåáóþòñÿ íå î÷åíü «æåñòêèå». Äîñòàòî÷íî ïðèíÿòü
ïðåäïîëîæåíèå «áåçóñëîâíîé (ìàðãèíàëüíîé) öåïíîé íåîáìàí÷èâîñòè» è ïðåäïî-
ëîæåíèå «íåîáìàí÷èâîñòè ïåðâîãî ðàíãà» [8, 9]. Íî ìîæíî îñëàáèòü è ýòè ïðåäïî-
ëîæåíèÿ. (Çàìåòèì, ÷òî óñëîâèÿ 3 è 4 îïðåäåëåíèé 3 è 5 ïîðîæäàþò ñòàòèñòè÷åñêè
íåíàäåæíûå ïðàâèëà, òàê êàê ïîëàãàþòñÿ íà òðàíçèòèâíîñòü çàâèñèìîñòåé.)
 ÖÎÃ-ìîäåëÿõ çíà÷åíèÿ ïåðåìåííûõ ìîãóò ìíîãîêðàòíî èçìåíÿòüñÿ (âîçìîæíà
áåñêîíå÷íàÿ îñöèëëÿöèÿ). Ïîýòîìó àíàëèòèê äîëæåí óòî÷íèòü, êàêîå ñîâìåñòíîå ðàñ-
ïðåäåëåíèå âåðîÿòíîñòåé íåîáõîäèìî àíàëèçèðîâàòü. (Ðàñïðåäåëåíèå âåðîÿòíîñòåé,
ïîðîæäàåìîå âûáîðêîé äàííûõ, ìîæåò íå ñîîòâåòñòâîâàòü ðàâíîâåñíîìó ñîñòîÿíèþ
öèêëè÷åñêîé ìîäåëè.) Êðîìå òîãî, íåÿñíî, êàê â öèêëè÷åñêîé ìîäåëè îïèñûâàòü àâòî-
ðåãðåññèîííûå ñâÿçè. Ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ öåëåñîîáðàçíî «ðàñøèòü» öèêëî-
íû âî âðåìåíè, ïåðåéòè ê «ñïèðàëÿì». Åñëè îñöèëëÿöèÿ áûñòðî ïðèõîäèò â ðàâíîâå-
ñèå, ðåçîííî èñïîëüçîâàòü ìîäåëè íà îñíîâå öåïíûõ ãðàôîâ [18].
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
Ýêñïåðèìåíòû ïîêàçàëè, ÷òî îñíàùåíèå àëãîðèòìà âûâîäà îÀÎÃ-ìîäåëè èç
äàííûõ íàáîðîì ðàçðàáîòàííûõ ïðàâèë ïîçâîëèëî ðåçêî ñîêðàòèòü êîëè÷åñòâî
òåñòîâ óñëîâíîé íåçàâèñèìîñòè âûñîêîãî ðàíãà, à èíîãäà è ñíèçèòü ìàêñèìàëü-
íûé ðàíã òåñòîâ [9, 11]. Â ðåçóëüòàòå ñíèæàåòñÿ ðèñê ëîæíîãî ïðèíÿòèÿ ãèïîòå-
çû íåçàâèñèìîñòè.  ñëó÷àå ñòðóêòóð òèïà ëåñ èëè ïîëèëåñ äëÿ àëãîðèòìà âûâî-
äà ìîäåëè, îñíàùåííîãî òîëüêî äâóìÿ ïðàâèëàìè, áóäåò äîñòàòî÷íî òåñòîâ íóëå-
âîãî è ïåðâîãî ðàíãà [10]. Îñíîâíîé ýôôåêò âíåäðåíèÿ îïèñàííûõ ñðåäñòâ
â àëãîðèòì âûâîäà ìîäåëè — çíà÷èòåëüíîå ñíèæåíèå ñóììàðíîãî êîëè÷åñòâà
âûïîëíÿåìûõ òåñòîâ è îáúåìà âû÷èñëåíèÿ íåîáõîäèìûõ ñòàòèñòèê.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. P e a r l J . Causality: models, reasoning, and inference. — Cambridge: Cambridge Univ. Press,
2000. — 526 p.
2. S p i r t e s P . , G l y m o u r C . , a n d S c h e i n e s R . Causation, prediction and search. — 2nd
ed. — New York: MIT Press, 2001. — 543 p.
3. T h e T E T R A D project: Constraint based aids to causal model specification / R. Scheines,
P. Spirtes, C. Glymour et al. // Multivar. Behavior. Res. — 1998. — 33, N 1. — P. 65–118.
4. R i c h a r d s o n T . , S p i r t e s P . Ancestral graph Markov models // Ann. Statistics. — 2002. —
30, N 4. — P. 962–1030.
5. S p i r t e s P . , M e e k C . , R i c h a r d s o n T . An algorithm for causal inference in the presence
of latent variables and selection bias // Computation, Causation, and Discovery. — Menlo Park
(CA): AAAI Press, 1999. — P. 211–252.
6. S p i r t e s P . Directed cyclic graphical representations of feedback models // Proc. of the 11th Conf.
on Uncertainty in Artificial Intelligence (1995). — San Francisco (CA): Morgan Kaufmann, 1995.
— P. 491–498.
7. Á à ë à á à í î â À . Ñ . Ìèíèìàëüíûå ñåïàðàòîðû â ñòðóêòóðàõ çàâèñèìîñòåé. Ñâîéñòâà è èäåí-
òèôèêàöèÿ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 6. — Ñ. 17–32.
8. Á à ë à á à í î â A . C . Ôîðìèðîâàíèå ìèíèìàëüíûõ d-ñåïàðàòîðîâ â ñèñòåìå çàâèñèìîñòåé //
Òàì æå. — 2009. — ¹ 5. — Ñ. 38–50.
9. Á à ë à á à í î â À . Ñ . , Ã à ï å å â À . Ñ . , Ã ó ï à ë À . Ì . , Ð æ å ï å ö ê è é Ñ . Ñ . Áûñòðûé àë-
ãîðèòì âûâîäà ñòðóêòóð áàéåñîâûõ ñåòåé èç äàííûõ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè.
— 2011. — ¹ 5. — Ñ. 73–80.
10. Á à ë à á à í î â Î . Ñ . Ïðèñêîðåííÿ àëãîðèòì³â â³äòâîðåííÿ áàºñîâèõ ìåðåæ. Àäàïòàö³ÿ äî
ñòðóêòóð áåç öèêë³â // Ïðîáëåìè ïðîãðàìóâàííÿ. — 2011. — ¹ 1. — Ñ. 63–69.
11. B a l a b a n o v O . S . Acceleration of inductive inference of causal diagrams // Proc. of the 4th Intern.
Workshop on Inductive Modelling (ICIM’2011), Kyiv, July 4–11, 2011. — Kyiv, 2011. — P. 16–21.
12. V e r m a T . , P e a r l J . Causal networks: Semantics and expressiveness // Proc. of the Fourth
Conf. on Uncertainty in Artificial Intelligence (UAI-88). — New York (NY): Elsevier Science,
1988. — P. 352–359.
13. N e a l R . M . On deducing conditional independence from d-separation in causal graphs with
feedback // J. Artif. Intellig. Res. — 2000. — 12. — P. 87–91.
14. Á à ë à á à í î â Î . Ñ . Ïðàâèëà ï³äáîðó ñåïàðàòîð³â ó áàºñ³âñüêèõ ìåðåæàõ // Ïðîáëåìè ïðî-
ãðàìóâàííÿ. — 2007. — ¹ 4. — Ñ. 22–33.
15. Á à ë à á à í î â A . C . Âîññòàíîâëåíèå ñòðóêòóð ñèñòåì âåðîÿòíîñòíûõ çàâèñèìîñòåé èç äàí-
íûõ. Àïïàðàò ãåíîòèïîâ ïåðåìåííûõ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2003. —
¹ 2. — C. 91–99.
16. T i a n J . , P a z A . , P e a r l J . Finding minimal d-separators: (Tech. rep.) / Computer Sci. Dep.,
Univ. of California, LA. — R-254. — Los Angeles (CA), 1998. — 15 p.
17. Á à ë à á à í î â À . Ñ . Î ëîãèêå íåçàâèñèìîñòè êàóçàëüíûõ äèàãðàìì // Êîìïüþòåðíàÿ ìàòåìà-
òèêà. — Êèåâ: Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2009. — ¹ 2. —
Ñ. 109–115.
18. L a u r i t z e n S . L . , R i c h a r d s o n T . S . Chain graph models and their causal interpretations //
J. Royal Statist. Soc. — 2002. — B-64. — P. 321–361.
Ïîñòóïèëà 22.02.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 47
|