Chow – Liu strom - Chow–Liu tree
V teorii pravděpodobnosti a statistice Chow – Liu strom je efektivní metoda pro konstrukciobjednat aproximace produktu a společné rozdělení pravděpodobnosti, poprvé popsáno v příspěvku od Chow & Liu (1968). Cíle takového rozkladu, jako u takových Bayesovské sítě obecně může být buď komprese dat nebo odvození.
Zastoupení Chow – Liu
Metoda Chow – Liu popisuje a společné rozdělení pravděpodobnosti jako produkt podmíněného a okrajového rozdělení druhého řádu. Například šestrozměrné rozdělení lze aproximovat jako
kde každý nový výraz v produktu zavádí pouze jednu novou proměnnou a produkt lze reprezentovat jako strom závislostí prvního řádu, jak je znázorněno na obrázku. Algoritmus Chow – Liu (níže) určuje, jaké podmíněné pravděpodobnosti mají být použity v aproximaci produktu. Obecně platí, že pokud nedochází k žádným interakcím třetího nebo vyššího řádu, je Chow – Liu aproximace skutečně přiblížení, a nemůže zachytit úplnou strukturu původní distribuce. Pearl (1988) poskytuje moderní analýzu stromu Chow – Liu jako a Bayesovská síť.
Algoritmus Chow – Liu
Chow a Liu ukazují, jak vybrat podmínky druhého řádu pro aproximaci produktu tak, aby mezi všemi takovými aproximacemi druhého řádu (stromy závislostí prvního řádu) byla vytvořená aproximace má minimum Kullback – Leiblerova divergence do skutečné distribuce , a je tedy nejbližší aproximace v klasice informační teoretik smysl. Kullback-Leiblerova divergence mezi aproximací produktu druhého řádu a skutečným rozdělením se ukazuje jako
kde je vzájemné informace mezi proměnnými a jeho rodič a je společná entropie proměnné sady . Protože podmínky a jsou nezávislé na pořadí závislostí ve stromu, pouze součet párů vzájemné informace, , určuje kvalitu aproximace. Pokud je tedy každé větvi (hraně) na stromu přidělena váha odpovídající vzájemné informaci mezi proměnnými na jejích vrcholech, pak strom, který poskytuje optimální aproximaci druhého řádu k cílovému rozdělení, je jen strom maximální hmotnosti. Výše uvedená rovnice také zdůrazňuje roli závislostí v aproximaci: Když neexistují žádné závislosti a první člen v rovnici chybí, máme pouze aproximaci založenou na marginálech prvního řádu a vzdálenost mezi aproximací a pravdou rozdělení je způsobeno nadbytečností, která se neberou v úvahu, když se s proměnnými zachází jako s nezávislými. Když zadáme závislosti druhého řádu, začneme zachycovat část této struktury a zmenšovat vzdálenost mezi dvěma distribucemi.
Chow a Liu poskytují jednoduchý algoritmus pro konstrukci optimálního stromu; v každé fázi postupu algoritmus jednoduše přidá maximum vzájemné informace spárovat se stromem. Podívejte se na originální papír, Chow & Liu (1968), pro všechny podrobnosti. V článku byl načrtnut efektivnější algoritmus konstrukce stromu pro běžný případ řídkých dat Meilă (1999).
Chow a Wagner dokázali v pozdějším článku Chow & Wagner (1973) že učení stromu Chow – Liu je konzistentní s danými vzorky (nebo pozorováními) nakreslenými i.i.d. ze stromově strukturované distribuce. Jinými slovy, pravděpodobnost zjištění nesprávného stromu se snižuje na nulu, protože počet vzorků má sklon k nekonečnu. Hlavní myšlenkou důkazu je kontinuita vzájemných informací v párovém okrajovém rozdělení. Nedávno byla poskytnuta exponenciální míra konvergence pravděpodobnosti chyby.[1]
Variace stromů Chow – Liu
Zjevný problém, ke kterému dochází, když skutečná distribuce ve skutečnosti není stromem závislostí druhého řádu, lze v některých případech vyřešit fúzováním nebo agregací hustě propojených podmnožin proměnných za účelem získání stromu Chow – Liu „s velkým uzlem“ (Huang & King 2002 ) , nebo rozšířením myšlenky chamtivého výběru maximální hmotnosti větve na nestromové (více nadřazené) struktury (Williamson 2000 ). (Podobné techniky variabilní substituce a konstrukce jsou v EU běžné Síť Bayes literatura, např. pro práci se smyčkami. Vidět Pearl (1988).)
Zobecnění stromu Chow – Liu jsou tzv t-třešňové křižovatky. Je dokázáno, že spojovací stromy t-cherry poskytují lepší nebo alespoň stejně dobrou aproximaci pro diskrétní vícerozměrné rozdělení pravděpodobnosti, jaké dává strom Chow – Liu. Pro spojovací strom t-cherry třetího řádu viz (Kovács & Szántai 2010 ), pro kth-order t-cherry junction tree see (Szántai & Kovács 2010 ). Strom t-třešňového spojení druhého řádu je ve skutečnosti strom Chow – Liu.
Viz také
Poznámky
- ^ Analýza velké odchylky pro maximální pravděpodobnost učení stromových struktur. V. Y. F. Tan, A. Anandkumar, L. Tong a A. Willsky. Na mezinárodním sympoziu o teorii informací (ISIT), červenec 2009.
Reference
- Chow, C. K .; Liu, C.N. (1968), „Aproximace diskrétních rozdělení pravděpodobnosti se stromy závislostí“, Transakce IEEE na teorii informací, IT-14 (3): 462–467, CiteSeerX 10.1.1.133.9772, doi:10.1109 / tit.1968.1054142.
- Huang, Kaizhu; King, Irwin; Lyu, Michael R. (2002), „Konstrukce velkého stromu Chow – Liu na základě častých položek“, Wang, Lipo; Rajapakse, Jagath C .; Fukushima, Kunihiko; Lee, Soo-Young; Yao, Xin (eds.), Sborník příspěvků z 9. mezinárodní konference o zpracování neurálních informací ({ICONIP} '02), Singapur, str. 498–502.
- Pearl, Judea (1988), Pravděpodobnostní uvažování v inteligentních systémech: sítě pravděpodobného závěru, San Mateo, Kalifornie: Morgan Kaufmann
- Williamson, Jon (2000), „Aproximace diskrétních rozdělení pravděpodobnosti s Bayesianskými sítěmi“, Sborník z mezinárodní konference o umělé inteligenci ve vědě a technologii, Tasmánie, s. 16–20.
- Meilă, Marina (1999), „Zrychlený algoritmus Chow a Liu: Přizpůsobení distribuce stromů vysokodimenzionálním řídkým datům“, Sborník příspěvků ze šestnácté mezinárodní konference o strojovém učení, Morgan Kaufmann, str. 249–257.
- Chow, C. K .; Wagner, T. (1973), „Konzistence odhadu rozdělení pravděpodobnosti závislé na stromu“, Transakce IEEE na teorii informací, IT-19 (3): 369–371, doi:10.1109 / tit.1973.1055013.
- Kovács, E .; Szántai, T. (2010), „O aproximaci diskrétního vícerozměrného rozdělení pravděpodobnosti pomocí nového konceptu t-třešňového spojovacího stromu“, Přednášky z ekonomie a matematických systémů, 633, část 1: 39–56, doi:10.1007/978-3-642-03735-1_3, ISBN 978-3-642-03734-4.
- Szántai, T .; Kovács, E. (2010), „Hypergrafy jako prostředek k objevení struktury závislosti diskrétního vícerozměrného rozdělení pravděpodobnosti“, Annals of Operations Research.