Методы построения байесовских сетей на основе оценочных функций

Проведено аналіз існуючих методів побудови мереж Байєса із застосуванням оціночної функції. Описано функції Купера - Гершковича й опису мінімальної довжини, а також проведено порівняльний аналіз алгоритмів побудови байєсівських мереж з використанням цих функцій....

Full description

Saved in:

Bibliographic Details
Published in:	Кибернетика и системный анализ
Date:	2008
Main Authors:	Згуровский, М.З., Бидюк, П.И., Терентьев, А.Н.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Subjects:	Системный анализ
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/71999
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:	Методы построения байесовских сетей на основе оценочных функций / М.З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. — 2008. — № 2. — С. 81-88. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859586597237817344
author	Згуровский, М.З. Бидюк, П.И. Терентьев, А.Н.
author_facet	Згуровский, М.З. Бидюк, П.И. Терентьев, А.Н.
citation_txt	Методы построения байесовских сетей на основе оценочных функций / М.З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. — 2008. — № 2. — С. 81-88. — Бібліогр.: 13 назв. — рос.
collection	DSpace DC
container_title	Кибернетика и системный анализ
description	Проведено аналіз існуючих методів побудови мереж Байєса із застосуванням оціночної функції. Описано функції Купера - Гершковича й опису мінімальної довжини, а також проведено порівняльний аналіз алгоритмів побудови байєсівських мереж з використанням цих функцій.
first_indexed	2025-11-27T11:15:03Z
format	Article
fulltext	ÓÄÊ 62-50 Ì.Ç. ÇÃÓÐÎÂÑÊÈÉ, Ï.È. ÁÈÄÞÊ, À.Í. ÒÅÐÅÍÒÜÅÂ ÌÅÒÎÄÛ ÏÎÑÒÐÎÅÍÈß ÁÀÉÅÑÎÂÑÊÈÕ ÑÅÒÅÉ ÍÀ ÎÑÍÎÂÅ ÎÖÅÍÎ×ÍÛÕ ÔÓÍÊÖÈÉ Êëþ÷åâûå ñëîâà: áàéåñîâñêàÿ ñåòü, îöåíî÷íûå ìåòîäû ïîèñêà, âû÷èñëèòåëü- íûå õàðàêòåðèñòèêè, ìèíèìàëüíàÿ äëèíà îïèñàíèÿ. ÂÂÅÄÅÍÈÅ Âî âñåõ ñòðàíàõ ìèðà íàêàïëèâàþòñÿ áîëüøèå îáúåìû èíôîðìàöèè, òðåáóþ- ùèå íàäëåæàùåé îáðàáîòêè è ïðèíÿòèÿ ðåøåíèé íà îñíîâå ðåçóëüòàòîâ ýòîé îáðàáîòêè. Ìåòîäû èíòåëëåêòóàëüíîãî àíàëèçà äàííûõ (ÈÀÄ), ê êîòîðûì ïðè- íàäëåæàò è áàéåñîâñêèå ñåòè (ÁÑ), ïðåäîñòàâëÿþò âîçìîæíîñòü àâòîìàòè÷åñ- êîãî ïîèñêà çàêîíîìåðíîñòåé, õàðàêòåðíûõ äëÿ ìíîãîìåðíûõ äàííûõ. Â îñíî- âå áîëüøèíñòâà èíñòðóìåíòîâ èíòåëëåêòóàëüíîãî àíàëèçà äàííûõ ëåæàò äâå òåõíîëîãèè: ìàøèííîå îáó÷åíèå è âèçóàëèçàöèÿ èíôîðìàöèè. Áàéåñîâñêèå ñåòè îáúåäèíÿþò â ñåáå ýòè äâå òåõíîëîãèè. Øèðîêîå ïðèìåíåíèå ÁÑ íàøëè â ìåäèöèíñêîé è òåõíè÷åñêîé äèàãíîñòèêå â óñëîâèÿõ íåïîëíîé è íåòî÷íîé èíôîðìàöèè, â ñèñòåìàõ êëàññèôèêàöèè äàí- íûõ ðàçëè÷íîé ïðèðîäû, ñèñòåìàõ àâòîìàòè÷åñêîãî ðàñïîçíàâàíèÿ ðå÷åâûõ ñèã- íàëîâ, ìàðêåòèíãå, áèçíåñå è âî ìíîãèõ äðóãèõ ñôåðàõ äåÿòåëüíîñòè. Â îáùåì ñëó÷àå ÁÑ äàåò âîçìîæíîñòü âîñïðîèçâåñòè ïðè÷èííî-ñëåäñòâåííûå ñâÿçè ìåæäó ñîáûòèÿìè è îïðåäåëèòü âåðîÿòíîñòü íàñòóïëåíèÿ òîé èëè èíîé ñèòóàöèè ïðè ïîëó÷åíèè íîâîé èíôîðìàöèè îòíîñèòåëüíî èçìåíåíèÿ ñîñòîÿíèÿ ëþáîãî óçëà (ïåðåìåííîé) ñåòè. Ñòåïåíü öåëåñîîáðàçíîñòè ïðèìåíåíèÿ äàííîãî ìåòîäà ìîäå- ëèðîâàíèÿ è ôîðìèðîâàíèÿ âåðîÿòíîñòíîãî âûâîäà çàâèñèò îò óìåíèÿ êîððåêòíî îñóùåñòâèòü ïîñòàíîâêó çàäà÷è, âûáðàòü ïåðåìåííûå ïðîöåññà, êîòîðûå â äîñòà- òî÷íîé ìåðå õàðàêòåðèçóþò åãî äèíàìèêó èëè ñòàòèêó, íàéòè íåîáõîäèìûå äàííûå è èñïîëüçîâàòü èõ äëÿ îáó÷åíèÿ ñåòè, à òàêæå êîððåêòíî ñôîðìóëèðîâàòü ðåçóëüòàò-âûâîä ñ ïîìîùüþ ïîñòðîåííîé ñåòè. Â àíãëîÿçû÷íîé ëèòåðàòóðå òåðìèí «ïîñòðîåíèå ÁÑ» îçíà÷àåò ðåàëèçàöèþ ñëåäóþùèõ ïðîöåññîâ: 1) ïîèñê îïòèìàëüíîé ñòðóêòóðû ÁÑ, ò.å. íàïðàâëåííîãî àöèêëè÷åñêîãî ãðàôà, íàèáîëåå àäåêâàòíî ñîîòâåòñòâóþùåãî îáó÷àþùèì äàí- íûì èëè èññëåäóåìîìó ïðîöåññó; 2) âû÷èñëåíèå çíà÷åíèé òàáëèö óñëîâíûõ âåðîÿòíîñòåé ÁÑ äëÿ ñîîòâåòñòâóþùèõ óçëîâ ýòîãî ãðàôà. Öåëü íàñòîÿùåé ñòàòüè — àíàëèç ñóùåñòâóþùèõ ìåòîäîâ ðåøåíèÿ çàäà÷è âûáîðà îïòèìàëüíîé ñòðóêòóðû áàéåñîâñêîé ñåòè, îïèñàíèå çàëîæåííûõ â íèõ ïðèíöèïîâ è ïðàêòè÷åñêîãî èñïîëüçîâàíèÿ. ÔÎÐÌÀËÜÍÀß ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÇÀÏÈÑÜ ÁÑ Áàéåñîâñêàÿ ñåòü — ýòî ãðàôè÷åñêàÿ ìîäåëü ïðîöåññà èëè îáúåêòà ïðîèçâîëü- íîé ïðèðîäû, ïðåäñòàâëåííàÿ ïàðîé � �G B, . Ïåðâîé êîìïîíåíòîé G ÿâëÿåòñÿ íàïðàâëåííûé àöèêëè÷åñêèé ãðàô, ñîîòâåòñòâóþùèé ñëó÷àéíûì ïåðåìåííûì îáúåêòà èëè ïðîöåññà. Îí çàïèñûâàåòñÿ êàê íàáîð óñëîâèé íåçàâèñèìîñòè: êàæäàÿ ïåðåìåííàÿ íå çàâèñèò îò åå ðîäèòåëåé â G. Âòîðàÿ êîìïîíåíòà ïàðû B ïðåäñòàâëÿåò ìíîæåñòâî ïàðàìåòðîâ, îïðåäåëÿþùèõ ñåòü. Ýòà êîìïîíåíòà ñîäåðæèò ïàðàìåòðû � x pa X i i i i P X pa X( ) \| ( ) ( ) ( )( \| ( ))� äëÿ êàæäîãî âîçìîæíîãî ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 81 © Ì.Ç. Çãóðîâñêèé, Ï.È. Áèäþê, À.Í. Òåðåíòüåâ, 2008 çíà÷åíèÿ x Xi i( ) ( )� è pa X Pa Xi i( ) ( )( ) ( )� , ãäå Pa X i( )( ) îçíà÷àåò íàáîð ðî- äèòåëåé ïåðåìåííîé X Gi( ) � . Êàæäàÿ ïåðåìåííàÿ X Gi( ) � ïðåäñòàâëÿåòñÿ â âèäå âåðøèíû. Åñëè ðàññìàòðèâàþò áîëåå îäíîãî ãðàôà, òî äëÿ îïðåäåëåíèÿ ðîäèòåëåé ïåðåìåííîé X i( ) â ãðàôå G èñïîëüçóþò îáîçíà÷åíèå Pa XG i( )( ) . Ïîëíàÿ ñîâìåñòíàÿ âåðîÿòíîñòü ÁÑ âû÷èñëÿåòñÿ ïî ôîðìóëå P X X P X Pa XB N i N B i i( , . . . , ) ( \| ( ))( ) ( ) ( ) ( )1 1 � � � . Ìíîæåñòâî îáó÷àþùèõ äàííûõ çàïèñûâàåòñÿ ñëåäóþùèì îáðàçîì: D d dn� { }1, . . . , , d x x xi i i i N� { }( ) ( ) ( ), , . . . ,1 2 . Çäåñü íèæíèé èíäåêñ — ýòî íîìåð íà- áëþäåíèÿ, à âåðõíèé — íîìåð ïåðåìåííîé; n — êîëè÷åñòâî íàáëþäåíèé, êàæäîå èç êîòîðûõ ñîñòîèò èç N (N � 2) ïåðåìåííûõ X X X N( ) ( ) ( ), , . . . ,1 2 . Êàæäàÿ j-ÿ ïåðåìåííàÿ ( j N�1, . . . , ) èìååò A j j( ) ( ), , . . . ,� { }0 1 1� (� ( )j � 2) ñîñòîÿíèé, à êàæäàÿ ñòðóêòóðà g G� ÁÑ ïðåäñòàâëÿåòñÿ N ìíîæåñòâàìè ïðåäêîâ ( , . . . ,( ) ( ) 1 N ). Èíûìè ñëîâàìè, äëÿ êàæäîé âåðøèíû j N�1, . . . , ìíîæåñòâî ( )j — íàáîð ðîäèòåëüñêèõ âåðøèí òàêèõ, ÷òî ( ) ( ) ( ), . . . , \j N jX X X� { } { }1 (âåðøèíà íå ìîæåò áûòü ïðåäêîì ñàìîé ñåáå, ò. å. ïåòëè â ãðàôå îòñóòñòâóþò). ÃÐÀÔÈ×ÅÑÊÎÅ ÎÒÎÁÐÀÆÅÍÈÅ ÑÒÐÓÊÒÓÐÛ ÁÑ Äåðåâî — òàêàÿ ñòðóêòóðà ÁÑ, â êîòîðîé ëþáàÿ âåðøèíà ìîæåò èìåòü íå áî- ëåå îäíîé âåðøèíû-ïðåäêà (ðèñ. 1). Ïîëè-äåðåâî — òàêàÿ ñòðóêòóðà ÁÑ, â êîòîðîé ëþáàÿ âåðøèíà ìîæåò èìåòü áîëåå îäíîé âåðøèíû-ïðåäêà, íî ïðè ýòîì ìåæäó ëþáûìè äâóìÿ âåðøèíàìè äîëæíî áûòü íå áîëåå îäíîãî ñâÿçûâàþùåãî èõ ïóòè (ðèñ. 2). Ñåòè — ñåòåâàÿ ñòðóêòóðà, â êîòîðîé ëþáàÿ âåðøèíà ìîæåò èìåòü áîëåå ÷åì îäíó âåðøèíó-ïðåäêà; ïðè ýòîì ìåæäó ëþáûìè äâóìÿ âåðøèíàìè ìîæåò áûòü áîëåå îäíîãî ñâÿçûâàþùåãî èõ ïóòè (ðèñ. 3). Äåðåâüÿ è ïîëè-äåðåâüÿ íàçûâàþò òàêæå îäíîñâÿçíûìè ñåòÿìè, à ñåòè — ìíîãîñâÿçíûìè ñåòÿìè. ÀËÃÎÐÈÒÌÛ ÏÎÑÒÐÎÅÍÈß ÑÒÐÓÊÒÓÐÛ ÑÅÒÅÉ ÁÀÉÅÑÀ ×ó è Ëèó (Chow and Liu) â 1968 ã. ïðåäëîæèëè àëãîðèòì äëÿ ïîñòðîåíèÿ ÁÑ â âèäå äåðåâà [1], îñíîâàííûé íà èñïîëüçîâàíèè çíà÷åíèé îáîþäíîé èíôîðìà- öèè ìåæäó âåðøèíàìè. Â êà÷åñòâå ðåøåíèÿ ìåòîä âûäàåò ñòðóêòóðó ÁÑ ñî çíà÷åíèåì ñîâìåñòíîãî ðàñïðåäåëåíèÿ âåðîÿòíîñòè, íàèáîëåå ñîîòâåòñòâóþùå- 82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 Ðèñ. 1. Ñòðóêòóðà ÁÑ â âèäå äåðåâà Ðèñ. 2. Ñòðóêòóðà ÁÑ â âèäå ïîëè-äåðåâà Ðèñ. 3. Ñòðóêòóðà ÁÑ â âèäå ñåòè ãî îáó÷àþùèì äàííûì. Ïîñòðîåíèå ñòðóêòóðû ÁÑ îñóùåñòâëÿåòñÿ çà O N( )2 øàãîâ, ãäå N — ÷èñëî âåðøèí ñåòè, îäíàêî ýòîò àëãîðèòì íå ïðèìåíèì äëÿ ìíîãîñâÿçíûõ ÁÑ. Â 1988 ã. Ðèáàí è Ïåðë (Rebane and Pearl) ïðåäëîæèëè óñîâåðøåíñòâîâàí- íûé èçìåíåííûé àëãîðèòì ×ó è Ëèó äëÿ ïîñòðîåíèÿ ÁÑ â âèäå ïîëè-äåðåâà [2]. Êóïåð è Ãåðøêîâè÷ (Cooper and Herskovits) â 1990 ã. ðàçðàáîòàëè àëãîðèòì Êóòà- òî (Kutato) [3]. Íà ýòàïå èíèöèàëèçàöèè àëãîðèòìà ñ ó÷åòîì, ÷òî âñå âåðøèíû ÁÑ íåçàâèñèìû, âû÷èñëÿåòñÿ ýíòðîïèÿ ýòîé ñåòè. Çàòåì ïðîèñõîäèò äîáàâëåíèå äóã ìåæäó âåðøèíàìè â ñåòè òàêèì îáðàçîì, ÷òîáû ìèíèìèçèðîâàòü ýíòðîïèþ ÁÑ. Äëÿ ðàáîòû àëãîðèòìà òðåáóåòñÿ íàëè÷èå óïîðÿäî÷åíîãî ìíîæåñòâà âåðøèí. Àëãîðèòì SGS [4], ïðåäëîæåííûé â 1991 ã., ïðè ïîñòðîåíèè ñòðóêòóðû îá- õîäèòñÿ áåç óïîðÿäî÷åíîãî ìíîæåñòâà âåðøèí, íî âìåñòî ýòîãî åìó ïðèõîäèòñÿ âûïîëíÿòü ýêñïîíåíöèàëüíîå êîëè÷åñòâî òåñòîâ íà óñëîâíóþ íåçàâèñèìîñòü ìåæäó âåðøèíàìè. Êóïåð è Ãåðøêîâè÷ â 1992 ã. ïðåäëîæèëè øèðîêî èçâåñòíûé àëãîðèòì Ê2 [5], êîòîðûé âûïîëíÿåò ïîèñê ñòðóêòóðû ñ ìàêñèìàëüíûì çíà÷åíè- åì ôóíêöèè Êóïåðà–Ãåðøêîâè÷à (ÊÃ). Äëÿ ðàáîòû àëãîðèòìà òðåáóåòñÿ íàëè÷èå óïîðÿäî÷åííîãî ìíîæåñòâà âåðøèí. Àëãîðèòì Ëåìà–Áàõóñà (Lam–Bacchus) [6], ïðåäëîæåííûé â 1996 ã., âûïîë- íÿåò ýâðèñòè÷åñêîå ïîñòðîåíèå ñòðóêòóðû ñåòè, èñïîëüçóÿ îáîþäíóþ èíôîðìà- öèþ ìåæäó âåðøèíàìè, à â êà÷åñòâå îöåíî÷íîé ôóíêöèè ïðèìåíÿåòñÿ îïèñàíèå ìèíèìàëüíîé äëèíû (ÎÌÄ). Àëãîðèòì Áåíåäèêòà (Benedict) [7], ïðåäëîæåííûé â 1996 ã., âûïîëíÿåò ýâ- ðèñòè÷åñêèé ïîèñê íà îñíîâå óïîðÿäî÷åíîãî ìíîæåñòâà âåðøèí, àíàëèçèðóÿ óñëîâíûå íåçàâèñèìîñòè â ñòðóêòóðå ñåòè íà îñíîâå d-ðàçäåëåíèÿ, à â êà÷åñòâå îöåíî÷íîé ôóíêöèè èñïîëüçóåòñÿ ýíòðîïèÿ. Àëãîðèòì CB [8] ïðåäëîæåí â 1995 ã. Îí èñïîëüçóåò òåñò íà óñëîâíóþ íåçà- âèñèìîñòü ìåæäó âåðøèíàìè ñåòè äëÿ ïîñòðîåíèÿ óïîðÿäî÷åííîãî ìíîæåñòâà âåðøèí. Ïðè ïîñòðîåíèè ñòðóêòóðû ñåòè èñïîëüçóåòñÿ ôóíêöèÿ ÊÃ. Àëãîðèòì Ôðèäìàíà–Ãîëäøìèäòà (Friedman–Goldszmidt) [9] ïðåäëîæåí â 1996 ã. Ïðè ïîñòðîåíèè ñåòè ïðèìåíÿåòñÿ àíàëèç åå ëîêàëüíûõ ïîäñòðóêòóð, à â êà÷åñòâå îöåíî÷íûõ ôóíêöèé èñïîëüçóþòñÿ ÎÌÄ è îöåíêà Áàéåñà. Â àëãîðèòìå WKD [10], ïðåäëîæåííîì â 1996 ã., â êà÷åñòâå îöåíî÷íîé ôóíêöèè ïðè ïîñòðîåíèè ñåòè èñïîëüçóåòñÿ ôóíêöèÿ ñîîáùåíèÿ ìèíèìàëüíîé äëèíû, êîòîðàÿ èìååò ñõîäñòâî ñ ÎÌÄ. Àëãîðèòì Ñóçóêè (Suzuki) [11], ïðåäëîæåííûé â 1999 ã., îñíîâàí íà ìåòîäå âåòâåé è ãðàíèö äëÿ çàäàíèÿ ïîñëåäîâàòåëüíîñòè ïîñòðîåíèÿ ñòðóêòóðû ñåòè, à â êà÷åñòâå îöåíî÷íîé ôóíêöèè èñïîëüçóåòñÿ ÎÌÄ. ÔÓÍÊÖÈß ÊÓÏÅÐ–ÃÅÐØÊÎÂÈ×À Â ðàáîòå [5] Êóïåð è Ãåðøêîâè÷ ïðåäëîæèëè ìåòîä ÊÃ äëÿ îáó÷åíèÿ ÁÑ, êî- òîðûé îñíîâàí íà ïîèñêå ñòðóêòóðû ÁÑ ñ ìàêñèìàëüíûì çíà÷åíèåì ôóíêöèè ÊÃ. Ôóíêöèÿ ÊÃ ñòðóêòóðû g G� ïðè çàäàííîé ïîñëåäîâàòåëüíîñòè èç n íà- áëþäåíèé x d d dn n� 1 2 . . . çàïèñûâàåòñÿ óðàâíåíèåì P g x P g n q s n j J s S j g j q A j ( , ) ( ) ( ) ! ( [ , , ( , ) ( ) ( ) � � � � � �� 1 j g n s j g j , ]!) ( [ , , ] ) !( ) � � � � � � � � � � � � � 1 . Çäåñü P g( ) — àïðèîðíàÿ âåðîÿòíîñòü ñòðóêòóðû g G� , êîòîðóþ ÷àñòî îïóñêà- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 83 þò ïðè âû÷èñëåíèÿõ; çàïèñü j J N� � { }1, . . . , îçíà÷àåò ïåðåáîð âñåõ âåðøèí ñòðóêòóðû ñåòè g, à s S j g� ( , ) — ïåðåáîð ìíîæåñòâà âñåõ íàáîðîâ çíà÷åíèé, ïðèíèìàåìûõ ïðåäêàìè j-é âåðøèíû; n s j g I s i n i j( , , ) ( )( )� � � � 1 � ; n q s j g I x q s i n i i j[ , , , ] ( , )( )� � � � � 1 � , ãäå � ( ) ( )j j� , ôóíêöèÿ I E( ) �1, êîãäà ïðåäèêàò E � true, â ïðîòèâíîì ñëó÷àå I E( ) � 0. Àëãîðèòì îáó÷åíèÿ ÁÑ ñ èñïîëüçîâàíèåì ôóíêöèè ÊÃ îñíîâàí íà öèêëè÷åñ- êîì ïåðåáîðå âñåõ âîçìîæíûõ àöèêëè÷åñêèõ ñåòåâûõ ñòðóêòóð. Â g * ñîõðàíÿåòñÿ îïòèìàëüíàÿ ñåòåâàÿ ñòðóêòóðà. Îïòèìàëüíîé ñòðóêòóðîé áóäåò òà, êîòîðàÿ èìå- åò íàèáîëüøåå çíà÷åíèå ôóíêöèè P g x n( , ): 1) g g G* ( )� �0 ; 2) � � g G g{ }0 : åñëè P g x P g xn n( , ) ( , )� , òî g g � ; 3) íà âûõîäå èìååì g * â êà÷åñòâå ðåøåíèÿ. Îäíàêî ïðè èñïîëüçîâàíèè ôóíêöèè ÊÃ íåîáõîäèìî ó÷èòûâàòü âû÷èñëèòåëüíûå îãðàíè÷åíèÿ ìîäåëèðóþùèõ ñèñòåì, ñâÿçàííûå ñ êîíå÷íîé äëèíîé ðàçðÿäíîé ñåòêè. Ïðèâåäåì òðèâèàëüíûé ïðèìåð, êîãäà â ñòðóêòóðå èìåþòñÿ äâå âåðøè- íû: X ( )1 è X ( )2 , à ìíîæåñòâî îáó÷àþùèõ ïðèìåðîâ âêëþ÷àåò ìèëëèîí çàïèñåé D d d� { }( ) ( . . ), ,1 1 000 000 � . Â òàêîì ñëó÷àå ïðè íàõîæäåíèè P g x n( , ) ïîòðåáóåòñÿ âû÷èñëèòü ôàêòîðèàë âèäà ( [ , , ] )!( )n s j g j �� 1 ( . . ) !( )1000000 1 � j , â òî âðå- ìÿ êàê òàêèå 32-ðàçðÿäíûå ïðîãðàììû êàê MatLab è MathCAD ñïîñîáíû âû- ÷èñëèòü ôàêòîðèàëû íå áîëåå 170!. ÌÎÄÈÔÈÖÈÐÎÂÀÍÍÀß ËÎÃÀÐÈÔÌÈ×ÅÑÊÀß ÔÓÍÊÖÈß ÊÓÏÅÐÀ È ÃÅÐØÊÎÂÈ×À Äëÿ áîëåå øèðîêîãî èñïîëüçîâàíèÿ ôóíêöèè ÊÃ ñëåäóåò èçáàâèòüñÿ îò ôàêòî- ðèàëà. Äëÿ ýòîãî ïðîëîãàðèôìèðóåì óðàâíåíèå, îïèñûâàþùåå ôóíêöèþ ÊÃ: log log( ( , )) ( ) ( ) ! ( , ) ( ) ( ) P g x P gn j J s S j g j q A j � � � � �� 1 ( [ , , , ]!) ( [ , , ] ) !( ) n q s j g n s j g j � � � � � � � � � � � � � � � � � � � � 1 � � � � � � � � � � � � � � � �log ( ( )) ( , ) [ , ( ) ( ) P g i j J s S j g i q A i n q j j1 1 1 � s j g i n s j g j i , , ] [ , , ] ( ) � � � � � � � � � � � � � � � � � � � � � � � �� 1 1� � � � � � � � � � � � � � � � � �log ( ( )) ( , ) [ , , , ] ( ) P g j J s S j g q A i n q s j g j 1 � � � � � � � � � � � � � � � � � � � � � i n s j g j j i � � ( ) ( ) [ , , ] 1 . Ïîëó÷åííîå âûðàæåíèå óìíîæèì íà – 1 è äëÿ ýêîíîìèè âû÷èñëèòåëüíûõ ðåñóðñîâ èñêëþ÷èì èç íåãî log ( ( ))P g . Êàê è â [5] ïðåäïîëàãàåì, ÷òî àïðèîðíûå âåðîÿòíîñòè P g( ) âñåõ ñòðóêòóð ðàâíû. Òåïåðü âìåñòî ïîèñêà ñòðóêòóðû ñ ìàê- ñèìàëüíûì çíà÷åíèåì ôóíêöèè ÊÃ ñëåäóåò îñóùåñòâëÿòü ïîèñê ñòðóêòóðû ñ ìè- íèìàëüíûì çíà÷åíèåì ìîäèôèöèðîâàííîé ëîãàðèôìè÷åñêîé ôóíêöèè Êóïåðà è 84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 Ãåðøêîâè÷à (ÌËÊÃ): F g x in j J s S j g i n s j g j j ( , ) ( , ) [ , , ] ( ) ( ) � � � � � � �� 1 � � � � � � � � � � � � � � � � � � � � � � � �� j J s S j g q A i n q s j g j i ( , ) [ , , , ] ( ) 1 � � � � � � � � � � . Êàê ïîêàçàëè âû÷èñëèòåëüíûå ýêñïåðèìåíòû, ôóíêöèè ÊÃ è ÌËÊÃ âûäàþò íà îäíèõ è òåõ æå îáó÷àþùèõ äàííûõ àáñîëþòíî îäèíàêîâûå ðåøåíèÿ. Îäíàêî íà ìàëåíüêèõ ñåòÿõ (äî 10 âåðøèí) àëãîðèòì ñ èñïîëüçîâàíèåì ôóíêöèè ÊÃ ðà- áîòàåò áûñòðåå, ÷åì ÌËÊÃ, à íà ñåòÿõ ñ áîëüøèì êîëè÷åñòâîì âåðøèí ñèòóàöèÿ ïðîòèâîïîëîæíà. ÔÓÍÊÖÈß ÎÏÈÑÀÍÈß ÌÈÍÈÌÀËÜÍÎÉ ÄËÈÍÛ Ïðè ïîñòðîåíèè ÁÑ â êà÷åñòâå îöåíî÷íîé ÷àñòî èñïîëüçóþò ôóíêöèþ ÎÌÄ [6, 9, 11, 12] èëè åå ìîäèôèêàöèè. Äëÿ çàäàííîé ïîñëåäîâàòåëüíîñòè x d d dn n� 1 2, , . . . , èç n íàáëþäåíèé ÎÌÄ ñòðóêòóðû g G� âû÷èñëÿåòñÿ ïî ôîðìóëå L g x H g x k g nn n( , ) ( , ) ( ) ( )� � 2 log , ãäå k g( ) — êîëè÷åñòâî íåçàâèñèìûõ óñëîâíûõ âåðîÿòíîñòåé â ñåòåâîé ñòðóê- òóðå g; H g x n( , ) — ýìïèðè÷åñêàÿ ýíòðîïèÿ: H g x H j g x k g k j gn j J n j J ( , ) ( , , ), ( ) ( , )� � � � � � . ÎÌÄ j-é âåðøèíû âû÷èñëÿåòñÿ ïî ôîðìóëå L j g x H j g x k j g nn n( , , ) ( , , ) ( , ) ( )� � 2 log , ãäå k j g( , ) — êîëè÷åñòâî íåçàâèñèìûõ óñëîâíûõ âåðîÿòíîñòåé j-é âåðøèíû: k j g a j k j k( , ) ( )( ) ( ) � � � �1 � � , � ( ) , . . . , , , . . . ,j j j N� { }1 1 1 — ýòî òàêîå ìíîæåñòâî, ïðè êîòîðîì ( ) ( ) ( ):j k jX k� �{ }� . Ýìïèðè÷åñêàÿ ýíòðîïèÿ j-é âåðøèíû âû÷èñëÿåòñÿ ñîãëàñíî âûðàæåíèþ H j g x n q s j g n q s j gn s S j g q A j ( , , ) [ , , , ] [ , , , ( , ) ( ) � � � � � � log ] [ , , ]n s j g ; n s j g I s n q s j g I x q i n i j i n i i( , , ) ( ); [ , , , ] ( ,( )� � � � � � � � 1 1 � � ( ) )j s� , ãäå � ( ) ( )j j� îçíà÷àåò, ÷òî X x kk k j( ) ( ) ( )� � �� ; ôóíêöèÿ I E( ) �1, êîãäà ïðåäèêàò E � true, â ïðîòèâíîì ñëó÷àå I E( ) � 0. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 85 ÝÂÐÈÑÒÈ×ÅÑÊÈÉ ÏÎÈÑÊ Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÓÏÎÐßÄÎ×ÅÍÍÎÃÎ ÌÍÎÆÅÑÒÂÀ ÂÅÐØÈÍ Êóïåð è Ãåðøêîâè÷ [5], à òàêæå Äåõòåð [13] è ìíîãèå äðóãèå èññëåäîâàòåëè [8] äëÿ óìåíüøåíèÿ ïðîñòðàíñòâà ñòðóêòóð ñåòè ïðåäëàãàþò ñ÷èòàòü ìíîæåñòâî âåð- øèí óïîðÿäî÷åííûì. Èíûìè ñëîâàìè, èìååòñÿ óïîðÿäî÷åíîå ìíîæåñòâî âåðøèí âèäà { }X X X N( ) ( ) ( ), , . . . ,1 2 , ãäå âåðøèíà X ( )1 — ãëàâíàÿ êîðíåâàÿ âåðøèíà, ó êîòîðîé íåò ïðåäêîâ; X ( )2 — äî÷åðíÿÿ âåðøèíà ïî îòíîøåíèþ ê X ( )1 ; X ( )3 — äî÷åðíÿÿ âåðøèíà ïî îòíîøåíèþ ê êàêîé-òî ïðåäûäóùåé âåðøèíå èëè êî âñåì ïðåäûäóùèì âåðøèíàì îäíîâðåìåííî è ò.ä. Â ñòàòüå [5] ïðåäëàãàåòñÿ ýâðèñòè÷åñêèé ìåòîä, èçâåñòíûé â ëèòåðàòóðå êàê àëãîðèòì Ê2. Ê âåðøèíå X N( ) ïî î÷åðåäè äîáàâëÿþòñÿ ïðåäêè îò X ( )1 äî X N( ) 1 . Ñ ïîìîùüþ ôóíêöèè ÊÃ âû÷èñëÿþòñÿ P g x n( , )( ) äëÿ êàæäîé êîìáèíà- öèè. Â êà÷åñòâå ïðåäêà äëÿ âåðøèíû X N( ) îñòàâëÿþò âåðøèíó X i( ) , ïðè êîòî- ðîé P g x n( , )( ) ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå. Ïîñëå ýòîãî ê âåðøèíàì X N( ) è X N( ) 1 ïî î÷åðåäè äîáàâëÿþòñÿ ïðåäêè îò X ( )1 äî X N( ) 2 è âû÷èñëÿ- þòñÿ P g x n( , )( ) . Íà âûõîäå ìåòîä âûäàåò ñòðóêòóðó ñåòè g, äëÿ êîòîðîé P g x n( , )( ) ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå. Íàëè÷èå óïîðÿäî÷åíîãî ìíîæåñòâà âåðøèí ñóùåñòâåííî ñîêðàùàåò ïðî- ñòðàíñòâî âñåõ âîçìîæíûõ íåöèêëè÷åñêèõ ñòðóêòóð. Íî â ýòîì ñëó÷àå ïîÿâëÿåò- ñÿ íîâàÿ íåòðèâèàëüíàÿ çàäà÷à — êàê ïî ìíîæåñòâó îáó÷àþùèõ äàííûõ ïîëó- ÷èòü óïîðÿäî÷åííîå ìíîæåñòâî âåðøèí ñåòè. Íàèáîëåå î÷åâèäíûé ñïîñîá — ïðèâëå÷ü ýêñïåðòîâ. Îäíàêî ìîæåò âîçíèêíóòü ïîòðåáíîñòü ìîäåëèðîâàíèÿ äàí- íûõ â òàêîé ïðåäìåòíîé îáëàñòè, ãäå êâàëèôèöèðîâàííûõ ýêñïåðòîâ íåò. ÇÍÀ×ÅÍÈÅ ÎÁÎÞÄÍÎÉ ÈÍÔÎÐÌÀÖÈÈ ÌÅÆÄÓ ÂÅÐØÈÍÀÌÈ Äëÿ îöåíêè ñòåïåíè çàâèñèìîñòè äâóõ ïðîèçâîëüíûõ ïåðåìåííûõ x i è x j â ðàáîòå [1] Øîó è Ëèó ïðåäëîæèëè â 1968 ã. èñïîëüçîâàòü çíà÷åíèå îáîþä- íîé èíôîðìàöèè (mutual information) MI x xi j( , ). Äëÿ ðàñ÷åòà ïðåäëîæåíî ñëåäóþùåå âûðàæåíèå: MI x x P x x P x x P x P x i j x x i j i j i j i j ( , ) ( , ) ( , ) ( ) ( ), � � � � � �� log � � � � � . Ïî ñâîåé ñóòè çíà÷åíèå îáîþäíîé èíôîðìàöèè ÿâëÿåòñÿ àíàëîãîì êîððåëÿ- öèè, íî ïî ñâîåìó ñîäåðæàíèþ — ýòî îöåíêà êîëè÷åñòâà èíôîðìàöèè î ïåðåìåí- íîé x j , ñîäåðæàùåéñÿ â ïåðåìåííîé x i . Çíà÷åíèå îáîþäíîé èíôîðìàöèè ïðèíè- ìàåò íåîòðèöàòåëüíûå çíà÷åíèÿ MI x xi j( , ) � 0, à â ñëó÷àå, åñëè âåðøèíû x i è x j ïîëíîñòüþ íåçàâèñèìû îäíà îò äðóãîé, òî MI x xi j( , ) � 0, òàê êàê P x x P x P xi j i j( , ) ( ) ( )� � ; ñëåäîâàòåëüíî, log log P x x P x P x P x P x P x i j i j i j i ( , ) ( ) ( ) ( ) ( ) ( )� � � � � � � � � � � � � � � � � � � � � � P x j( ) ( )log 1 0. Çíà÷åíèå îáîþäíîé èíôîðìàöèè èñïîëüçóåòñÿ âìåñòî óïîðÿäî÷åíîãî ìíî- æåñòâà âåðøèí ïðè ïîñòðîåíèé ÁÑ [1, 2, 6, 12]. 86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 ÐÅÇÓËÜÒÀÒÛ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÝÊÑÏÅÐÈÌÅÍÒÎÂ Íàèáîëåå ðàñïðîñòðàíåííûìè îöåíî÷- íûìè ôóíêöèÿìè ïðè ïîñòðîåíèè ñòðóêòóð ÁÑ ÿâëÿþòñÿ ôóíêöèè ÊÃ è ÎÌÄ, à òàêæå èõ ìîäèôèêàöèè. Ïîýòî- ìó â íàñòîÿùåé ñòàòüå âûïîëíåíî ñðàâ- íåíèå àëãîðèòìîâ, èñïîëüçóþùèõ ÌËÊÃ è ÎÌÄ îòíîñèòåëüíîãî âðåìåíè, çàòðà÷åíîãî íà ïîñòðîåíèå ÁÑ. Äëÿ îïðåäåëåíèÿ ïîðÿäêà äîáàâëåíèÿ äóã â ÁÑ èñïîëüçîâàëîñü çíà÷åíèå îáîþäíîé èíôîðìàöèè [12], à äëÿ ïîñòðîåíèÿ — âûáîðêà ãåíåòè÷åñêèõ äàííûõ, ñîñòîÿ- ùàÿ èç 600 îáó÷àþùèõ çàïèñåé. Íà ðèñ. 4 è 5 ïîêàçàíû ãðàôèêè âðåìåííûõ çàòðàò âû÷èñëåíèÿ àëãîðèòìîâ. Êàê âèäíî, äëÿ ïîñòðîåíèÿ ÁÑ, ñîñòîÿùèõ èç áîëåå ÷åì 30 âåðøèí, àëãîðèòì ñ èñ- ïîëüçîâàíèåì ÎÌÄ ðàáîòàåò áûñòðåå, ÷åì ñ ÌËÊÃ. ÇÀÊËÞ×ÅÍÈÅ Èñïîëüçîâàíèå ÁÑ ÿâëÿåòñÿ âîñòðåáî- âàííûì ñîâðåìåííûì ïîäõîäîì â îá- ëàñòè îáðàáîòêè èíôîðìàöèè ïðè ìî- äåëèðîâàíèè ïðîöåññîâ ðàçëè÷íîé ïðè- ðîäû è ñëîæíîñòè. Â ñòàòüå âûïîëíåí àíàëèç äåñÿòè ìåòîäîâ ïîñòðîåíèÿ ÁÑ, èñïîëüçóþùèõ îöåíî÷íûå ôóíêöèè. Íàèáîëåå ðàñïðîñòðàíåííûìè îöåíî÷íû- ìè ôóíêöèÿìè ÿâëÿþòñÿ ôóíêöèè ÊÃ è ÎÌÄ, à òàêæå èõ ìîäèôèêàöèè. Ðå- çóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ïîêàçàëè, ÷òî íà êîðîòêèõ îáó÷àþ- ùèõ âûáîðêàõ (äî 170 çàïèñåé) è ñåòÿõ, ñîñòîÿùèõ íå áîëåå ÷åì èç 10 âåðøèí, àëãîðèòì ñ èñïîëüçîâàíèåì ôóíêöèè ÊÃ ðàáîòàåò áûñòðåå ïî ñðàâíåíèþ ñ ÌËÊÃ è ÎÌÄ. Îäíàêî àëãîðèòìû, èñïîëüçóþùèå ÌËÊÃ è ÎÌÄ, â îòëè÷èå îò ÊÃ, ðà- áîòàþò ñ îáó÷àþùèìè âûáîðêàìè ëþáîãî ðàçìåðà. Âû÷èñëèòåëüíûå ýêñïåðèìåí- òû ïîêàçàëè, ÷òî ìåòîäû ïîñòðîåíèÿ ÁÑ ñ ïðèìåíåíèåì ôóíêöèé ÊÃ è åå ìîäè- ôèêàöèé, âûïîëíÿþò ïåðåîáó÷åíèå ÁÑ, ò. å. òàêèå ñåòè ñîäåðæàò ëèøíèå äóãè. Ïðè ñðàâíåíèè ôóíêöèé ÌËÊÃ è ÎÌÄ íà âûáîðêàõ ãåíåòè÷åñêèõ äàííûõ, ñîñòîÿùèõ èç 600 îáó÷àþùèõ çàïèñåé, ôóíêöèÿ ÌËÊÃ ïîêàçàëà ëó÷øåå âðåìÿ âû÷èñëåíèÿ íà ñåòÿõ, ñîñòîÿùèõ íå áîëåå ÷åì èç 30 âåðøèí. Íî àëãîðèòì ñ èñ- ïîëüçîâàíèåì ÎÌÄ ïî ñðàâíåíèþ ñ ÌËÊÃ ðàáîòàåò â íåñêîëüêî ðàç áûñòðåå íà áîëüøèõ ñåòÿõ, ñîñòîÿùèõ èç áîëåå ÷åì 30 âåðøèí. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. C h o w C . K . , L i u C . N . Approximating discrete probability distributions with dependence trees // IEEE Transactions on information theory. — 1968. — 4, N 3. — P. 462–467. 2. R e b a n e G . , P e a r l J . The recovery of causal poly-trees from statistical data // Intern. Jour. of Approx. Reas. — 1988. — 2, N 3. — P. 175–182. 3. H e r s k o v i t s E . , C o o p e r G . Kutato: an entropy-driven system for construction of probabilistic expert systems from databases // Proc. of the Sixth Intern. Conf. on Uncertainty in Arti- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 87 Ðèñ. 4. Äèàãðàììà âðåìåíè âû÷èñëåíèÿ àëãîðèòìîâ ñ èñïîëüçîâàíèåì ÌËÊÃ è ÎÌÄ Ðèñ. 5. Ãðàôèê âðåìåííûõ çàòðàò àëãîðèòìà ñ èñïîëüçîâàíèåì ÎÌÄ ficial Intelligence (UAI’90), Cambridge, MA, USA. — New York: Elsevier science, 1991. — P. 54–62. 4. S p i r t e s P . , G l y m o u r C . , S c h e i n e s R . From probability to causality // Philos. Studies. — Amsterdam: Springer Netherlands. — 1991. — 64, N 1. — P. 1–36. 5. C o o p e r G . , H e r s k o v i t s E . A Bayesian method for the induction of probabilistic net- works from data // Machine Learning. — 1992. — 9. — P. 309–347. 6. L a m W . , B a c c h u s F . Learning Bayesian belief networks: an approach based on the MDL principle // Computational Intelligence. — 1994. — 10, N 4. — P. 269–293. 7. A c i d S . , C a m p o s L . Benedict : an algorithm for learning probabilistic belief networks // Proc. of the Sixth International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU’96), Granada, Spain. — New York: Springer, 1997. — P. 979–984. 8. S i n g h M . , V a l t o r t a M . Construction of Bayesian network structures from data: a brief survey and an efficient algorithm // Intern. Jour. of Approx. Rea. — 1995. — 12. — P. 111–131. 9. F r i e d m a n N . , G o l d s z m i d t M . Learning Bayesian networks with local structure // Proc. of the Twelfth International Conf. on Uncertainty in Artificial Intelligence (UAI’96), Portland, Oregon, USA. — SF.: Morgan Kaufmann, 1996. — P. 252–262. 10. W a l l a c e C . , K o r b K . , D a i H . Causal discovery via MML / Proc. of the Thirteenth In- tern. Conf. on Machine Learning (ICML’96), Bari, Italy. — SF.: Morgan Kaufmann, 1996. — P. 516–524. 11. S u z u k i J . Learning Bayesian belief networks based on the MDL principle: an efficient algo- rithm using the branch and bound technique // IEICE Trans. on Inform. and Systems. — 1999. — P. 356–367. 12. Ò å ð å í ò ü å â À . Í . , Á è ä þ ê Ï . È . Ýâðèñòè÷åñêèé ìåòîä ïîñòðîåíèÿ áàéåñîâñêèõ ñåòåé // Ìàò. ìàøèíû è ñèñòåìû. — 2006. — 3. — Ñ. 12–23. 13. D e c h t e r R . Bucket elimination: a unifying framework for reasoning // ACM Press. — 1996. — 28, N 61. — P. 1–51. Ïîñòóïèëà 27.06.2007 88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
id	nasplib_isofts_kiev_ua-123456789-71999
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
language	Russian
last_indexed	2025-11-27T11:15:03Z
publishDate	2008
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Згуровский, М.З. Бидюк, П.И. Терентьев, А.Н. 2014-12-15T22:12:23Z 2014-12-15T22:12:23Z 2008 Методы построения байесовских сетей на основе оценочных функций / М.З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. — 2008. — № 2. — С. 81-88. — Бібліогр.: 13 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/71999 62-50 Проведено аналіз існуючих методів побудови мереж Байєса із застосуванням оціночної функції. Описано функції Купера - Гершковича й опису мінімальної довжини, а також проведено порівняльний аналіз алгоритмів побудови байєсівських мереж з використанням цих функцій. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Методы построения байесовских сетей на основе оценочных функций Article published earlier
spellingShingle	Методы построения байесовских сетей на основе оценочных функций Згуровский, М.З. Бидюк, П.И. Терентьев, А.Н. Системный анализ
title	Методы построения байесовских сетей на основе оценочных функций
title_full	Методы построения байесовских сетей на основе оценочных функций
title_fullStr	Методы построения байесовских сетей на основе оценочных функций
title_full_unstemmed	Методы построения байесовских сетей на основе оценочных функций
title_short	Методы построения байесовских сетей на основе оценочных функций
title_sort	методы построения байесовских сетей на основе оценочных функций
topic	Системный анализ
topic_facet	Системный анализ
url	https://nasplib.isofts.kiev.ua/handle/123456789/71999
work_keys_str_mv	AT zgurovskiimz metodypostroeniâbaiesovskihseteinaosnoveocenočnyhfunkcii AT bidûkpi metodypostroeniâbaiesovskihseteinaosnoveocenočnyhfunkcii AT terentʹevan metodypostroeniâbaiesovskihseteinaosnoveocenočnyhfunkcii

Методы построения байесовских сетей на основе оценочных функций

Institution

Similar Items