Dirichletův proces - Dirichlet process
v teorie pravděpodobnosti, Dirichletovy procesy (po Peter Gustav Lejeune Dirichlet ) jsou rodinou stochastické procesy jehož realizace jsou rozdělení pravděpodobnosti. Jinými slovy, Dirichletův proces je rozdělení pravděpodobnosti, jehož rozsah je sám o sobě množinou rozdělení pravděpodobnosti. Často se používá v Bayesovský závěr popsat předchozí znalosti o distribuci náhodné proměnné —Jako je pravděpodobné, že náhodné proměnné jsou distribuovány podle toho či onoho konkrétního rozdělení.
Dirichletův proces je určen základní distribucí a pozitivní reálné číslo nazývá se parametr koncentrace (také známý jako parametr měřítka). Základní distribuce je očekávaná hodnota procesu, tj. Dirichletův proces kreslí distribuce „kolem“ základního rozdělení způsobem a normální distribuce kreslí reálná čísla kolem své střední hodnoty. I když je ale základní distribuce kontinuální, jsou distribuce čerpané z Dirichletova procesu téměř jistě oddělený. Parametr měřítka určuje, jak silná je tato diskretizace: v limitu , jsou všechny realizace soustředěny na jedinou hodnotu, zatímco jsou na hranici realizace se stávají kontinuálními. Mezi dvěma extrémy jsou realizace diskrétní distribuce se stále menší koncentrací zvyšuje.
Na Dirichletův proces lze také pohlížet jako na nekonečně dimenzionální zobecnění Dirichletova distribuce. Stejným způsobem jako Dirichletova distribuce je před konjugátem pro kategorické rozdělení, Dirichletův proces je konjugát před nekonečným, neparametrické diskrétní distribuce. Obzvláště důležité použití Dirichletových procesů je jako předchozí pravděpodobnost distribuce v modely nekonečné směsi.
Dirichletův proces formálně představil Thomas Ferguson v roce 1973[1]a od té doby byl použit v dolování dat a strojové učení, mimo jiné pro zpracování přirozeného jazyka, počítačové vidění a bioinformatika.
Úvod
Dirichletovy procesy se obvykle používají při modelování dat, která mají tendenci opakovat předchozí hodnoty takzvaným způsobem „rich rich richer“. Konkrétně předpokládejme, že generování hodnot lze simulovat následujícím algoritmem.
- Vstup: (rozdělení pravděpodobnosti zvané základní rozdělení), (volalo kladné reálné číslo parametr měřítka )
- Pro :
a) S pravděpodobností kreslit z .
b) S pravděpodobností soubor , kde je počet předchozích pozorování .
(Formálně, kde označuje počet prvků v sadě.)
Ve stejné době, další společný model pro data je, že pozorování se předpokládá, že jsou nezávislé a identicky distribuované (i.i.d.) podle nějaké (náhodné) distribuce . Cílem zavedení Dirichletových procesů je být schopen popsat postup popsaný výše v tomto i.i.d. Modelka.
The pozorování v algoritmu nejsou nezávislý, protože při generování další hodnoty musíme vzít v úvahu předchozí výsledky. Jsou to však vyměnitelné. Tuto skutečnost lze prokázat výpočtem společné rozdělení pravděpodobnosti pozorování a všimněte si, že výsledný vzorec závisí pouze na tom hodnoty se vyskytují mezi pozorováními a kolik opakování mají. Kvůli této zaměnitelnosti de Finettiho věta o reprezentaci platí a znamená to, že pozorování jsou podmíněně nezávislý vzhledem k (latentní) distribuci . Tento je náhodná proměnná sama o sobě a má distribuci. Tato distribuce (přes distribuce) se nazývá Dirichletův proces (). V souhrnu to znamená, že dostaneme ekvivalentní postup k výše uvedenému algoritmu:
- Nakreslete distribuci z
- Kreslete pozorování nezávisle na .
V praxi se však kreslí konkrétní rozdělení je nemožné, protože jeho specifikace vyžaduje nekonečné množství informací. Toto je v kontextu Bayesianů běžný jev neparametrické statistiky kde typickým úkolem je naučit se distribuce ve funkčních prostorech, které zahrnují efektivně nekonečně mnoho parametrů. Klíčovým poznatkem je, že v mnoha aplikacích se nekonečně dimenzionální distribuce objevují pouze jako zprostředkující výpočetní zařízení a nejsou vyžadovány ani pro počáteční specifikaci dřívějších přesvědčení, ani pro vyjádření konečné závěry.
Formální definice
Vzhledem k tomu, měřitelná množina S, základní rozdělení pravděpodobnosti H a pozitivní reálné číslo , Dirichletův proces je stochastický proces jehož ukázková cesta (nebo realizace, tj. nekonečná posloupnost náhodné variace čerpané z procesu) je rozdělení pravděpodobnosti S, takže platí následující. Pro jakoukoli měřitelnou konečnou rozdělit z S, označeno ,
kde označuje Dirichletova distribuce a zápis znamená, že náhodná proměnná má distribuci .
Alternativní pohledy
Existuje několik ekvivalentních pohledů na Dirichletův proces. Kromě výše uvedené formální definice lze Dirichletův proces definovat implicitně prostřednictvím de Finettiho věty, jak je popsáno v první části; tomu se často říká Proces čínské restaurace. Třetí alternativou je proces lámání hůlky, který definuje Dirichletův proces konstruktivně zápisem distribuce vzorkované z procesu jako , kde jsou vzorky ze základní distribuce , je funkce indikátoru soustředěný na (nula všude kromě ) a jsou definovány rekurzivním schématem, které opakovaně vzorkuje z beta distribuce .
Proces čínské restaurace
Široce používaná metafora pro Dirichletův proces je založena na tzv Proces čínské restaurace. Metafora je následující:
Představte si čínskou restauraci, do které zákazníci vstupují. Nový zákazník si sedne ke stolu s pravděpodobností úměrnou počtu zákazníků, kteří tam již sedí. Zákazník navíc otevře novou tabulku s pravděpodobností úměrnou parametru škálování . Poté, co vstoupí nekonečně mnoho zákazníků, získá se rozdělení pravděpodobnosti na nekonečně mnoho zvolených tabulek. Toto rozdělení pravděpodobnosti přes tabulky je náhodný vzorek pravděpodobností pozorování získaných z Dirichletova procesu s parametrem měřítka .
Pokud jeden přidruží čerpá ze základní míry s každou tabulkou výsledná distribuce ve vzorovém prostoru je náhodný vzorek procesu Dirichlet. Proces čínské restaurace souvisí s Schéma vzorkování urny Pólya který poskytuje vzorky z konečných Dirichletových distribucí.
Protože zákazníci sedí u stolu s pravděpodobností úměrnou počtu zákazníků, kteří již sedí u stolu, lze odvodit dvě vlastnosti DP:
- Dirichletův proces vykazuje samonosnou vlastnost: Čím častěji byla daná hodnota vzorkována v minulosti, tím je pravděpodobnější, že bude vzorkována znovu.
- I kdyby je distribuce přes nespočetná sada, je nenulová pravděpodobnost, že dva vzorky budou mít přesně stejnou hodnotu, protože hmotnost pravděpodobnosti se soustředí na malý počet tabulek.
Proces lámání hůlky
Třetím přístupem k Dirichletovu procesu je takzvaný pohled na rozbití procesu. Pamatujte, že čerpání z Dirichletova procesu jsou distribuce přes množinu . Jak již bylo zmíněno dříve, nakreslená distribuce je diskrétní s pravděpodobností 1. V pohledu procesu rozbíjení tyčinek explicitně používáme diskrétnost a dáváme funkce pravděpodobnostní hmotnosti této (náhodné) diskrétní distribuce jako:
kde je funkce indikátoru který se hodnotí na nulu všude, kromě . Protože toto rozdělení je náhodné samo o sobě, jeho hromadná funkce je parametrizována dvěma sadami náhodných proměnných: lokacemi a odpovídající pravděpodobnosti . V následujícím textu bez důkazu uvádíme, o jaké náhodné proměnné jde.
Místa jsou nezávislé a identicky distribuovány podle , základní distribuce Dirichletova procesu. Pravděpodobnosti jsou dány postupem připomínajícím zlomení páčky jednotkové délky (odtud název):
kde jsou nezávislé náhodné proměnné s beta distribuce . Podobnost s „rozbíjením hůlky“ lze vidět zvážením jako délka kusu tyčinky. Začneme tyčovou jednotkou a v každém kroku odlomíme část zbývající tyčky podle a přiřadit tento odlomený kus . Vzorec lze pochopit poznamenáním, že po prvním k - 1 hodnotám jsou přiřazeny jejich části, délka zbývající části páčky je a tento kus je rozbit podle a bude přidělen .
Menší to znamená, že pro následující hodnoty (v průměru) zbude méně tyčinky, čímž se získá koncentrovanější distribuce.
Proces rozbíjení tyčinek je podobný konstrukci, ze které se postupně vzorkuje marginální beta distribuce za účelem vygenerování vzorku z a Dirichletova distribuce. Vidět [3] pro důkaz.
Schéma urny Pólya
Ještě další způsob, jak vizualizovat proces Dirichlet a proces čínské restaurace, je upravený Schéma urny Pólya někdy nazývaný Blackwell-MacQueen schéma vzorkování. Představte si, že začneme s urnou naplněnou černé koule. Poté postupujeme následovně:
- Pokaždé, když potřebujeme pozorování, nakreslíme z urny míč.
- Pokud je míč černý, generujeme rovnoměrně novou (nečernou) barvu, označíme nový míč touto barvou, umístíme nový míč do urny spolu s míčem, který jsme nakreslili, a vrátíme barvu, kterou jsme vygenerovali.
- Jinak označte novou kouli barvou koule, kterou jsme nakreslili, vložte novou kouli do urny spolu s koulí, kterou jsme nakreslili, a vraťte barvu, kterou jsme pozorovali.
Výsledná distribuce přes barvy je stejná jako distribuce přes tabulky v procesu čínské restaurace. Když navíc nakreslíme černou kouli, místo generování nové barvy místo toho vybereme náhodnou hodnotu ze základního rozdělení a použijte tuto hodnotu k označení nové koule, výsledné rozdělení přes štítky bude stejné jako rozdělení přes hodnoty v Dirichletově procesu.
Použít jako předchozí distribuci
Dirichletův proces lze použít jako předchozí distribuci pro odhad rozdělení pravděpodobnosti, které generuje data. V této části uvažujeme o modelu
Distribuce Dirichlet uspokojuje předchozí konjugace, zadní konzistence a Věta Bernstein – von Mises. [4]
Zadní konjugace
V tomto modelu je zadní distribuce opět Dirichletovým procesem. To znamená, že Dirichletův proces je a před konjugátem pro tento model. The zadní distribuce darováno
Zadní konzistence
Vezmeme-li častý z pohledu pravděpodobnosti věříme, že existuje skutečné rozdělení pravděpodobnosti který generoval data. Pak se ukázalo, že Dirichletův proces je konzistentní v slabá topologie, což znamená, že pro každé slabé sousedství z , zadní pravděpodobnost konverguje k .
Bernstein-Von Misesova věta
Za účelem interpretace důvěryhodných sad jako sad spolehlivosti a Věta Bernstein – von Mises je potřeba. V případě Dirichletova procesu porovnáváme zadní distribuci s empirický proces . Předpokládat je -Donskerova třída, tj.
pro nějaký Brownův most . Předpokládejme také, že existuje funkce takhle takhle , pak, téměř jistě
To znamená, že důvěryhodné množiny, které vytvoříte, jsou asymptotické sady spolehlivosti a Bayesiánská inference založená na Dirichletově procesu je asymptoticky také platná častá inference.
Použití v modelech směsí Dirichlet
Abychom pochopili, jaké jsou Dirichletovy procesy a problém, který řeší, považujeme příklad shlukování dat. Je běžnou situací, že se předpokládá, že jsou datové body distribuovány hierarchicky, kdy každý datový bod patří do (náhodně vybraného) klastru a členové klastru jsou dále náhodně distribuováni v rámci tohoto klastru.
Příklad 1
Mohlo by nás například zajímat, jak budou lidé v nadcházejících volbách hlasovat o řadě otázek. Rozumným modelem pro tuto situaci může být klasifikace každého voliče jako liberála, konzervativce nebo umírněného a poté modelovat událost, kdy volič řekne „ano“ jakékoli konkrétní otázce, jako Bernoulliho náhodná proměnná s pravděpodobností závislou na tom, ke kterému politickému klastru patří. Při pohledu na to, jak se v předchozích letech hlasovalo o podobných právních předpisech, by bylo možné přizpůsobit prediktivní model pomocí jednoduchého klastrového algoritmu, jako je k-prostředky. Tento algoritmus však vyžaduje vědět předem počet klastrů, které generovaly data. V mnoha situacích to není možné určit předem, ai když můžeme rozumně předpokládat řadu klastrů, chtěli bychom tento předpoklad ještě ověřit. Například v příkladu hlasování výše nemusí být rozdělení na liberální, konzervativní a umírněné dostatečně vyladěno; atributy jako náboženství, třída nebo rasa mohou být také rozhodující pro modelování chování voličů, což má za následek více shluků v modelu.
Příklad 2
Jako další příklad by nás mohlo zajímat modelování rychlostí galaxií pomocí jednoduchého modelu za předpokladu, že rychlosti jsou seskupeny, například za předpokladu, že každá rychlost je rozdělena podle normální distribuce , Kde toto pozorování patří k shluk galaxií se společnou očekávanou rychlostí. V tomto případě není zdaleka zřejmé, jak a priori určit, kolik klastrů (běžných rychlostí) by mělo být a jakýkoli model by byl velmi podezřelý a měl by být porovnán s údaji. Použitím Dirichletova procesu před distribucí prostředků klastru obcházíme potřebu výslovně předem určit, kolik klastrů existuje, ačkoli parametr koncentrace to stále implicitně řídí.
Zvažujeme tento příklad podrobněji. Prvním naivním modelem je předpokládat, že existují shluky normálně distribuovaných rychlostí s běžně známými pevnými rozptyl . Označující událost, kterou toto pozorování je v th cluster jako můžeme tento model napsat jako:
To znamená, předpokládáme, že data patří odlišné shluky s prostředky a to je (neznámá) předchozí pravděpodobnost datového bodu patřícího k th shluk. Předpokládáme, že nemáme žádné počáteční informace rozlišující klastry, které jsou zachyceny symetrickým předchozím . Tady označuje Dirichletova distribuce a označuje vektor délky kde každý prvek je 1. Dále přiřadíme nezávislé a identické předchozí distribuce ke každému z klastrových prostředků, kde může být libovolné parametrické rozdělení s parametry označenými jako . Hyperparametry a jsou považovány za známé pevné konstanty, zvolené tak, aby odrážely naše předchozí přesvědčení o systému. Abychom pochopili souvislost s Dirichletovým procesem, přepíšeme tento model do ekvivalentní, ale podnětnější formy:
Místo toho, abychom si představovali, že každému datovému bodu je nejprve přiřazen klastr a poté čerpán z distribuce přidružené k tomuto klastru, nyní myslíme na to, že každé pozorování je spojeno s parametrem čerpané z nějaké diskrétní distribuce s podporou na prostředek. To znamená, že nyní ošetřujeme jak jsou čerpány z náhodného rozdělení a naše předchozí informace jsou začleněny do modelu distribucí přes distribuce .
Nyní bychom chtěli rozšířit tento model tak, aby fungoval bez předem určeného pevného počtu klastrů . Matematicky to znamená, že bychom chtěli vybrat náhodné předchozí rozdělení kde hodnoty klastrů znamenají jsou opět nezávisle distribuovány podle a distribuce skončila je symetrický nad nekonečnou sadou shluků. To je přesně to, čeho model dosahuje:
S tímto v ruce můžeme lépe porozumět výpočetním výhodám Dirichletova procesu. Předpokládejme, že jsme chtěli kreslit pozorování z naivního modelu přesně shluky. Jednoduchým algoritmem pro to by bylo kreslení hodnoty z , distribuce z a poté pro každé pozorování nezávisle vzorek shluku s pravděpodobností a hodnota pozorování podle . Je snadné vidět, že tento algoritmus nefunguje v případě, že povolíme nekonečné shluky, protože by to vyžadovalo vzorkování nekonečného rozměrného parametru . Stále je však možné odebrat vzorky pozorování . Lze např. použijte níže popsanou čínskou restauraci a vypočítejte pravděpodobnost pro použité klastry a nový klastr, který má být vytvořen. Tím se vyhnete nutnosti výslovně specifikovat . Jiná řešení jsou založena na zkrácení klastrů: Zavádí se (vysoká) horní hranice skutečného počtu klastrů a čísla klastrů vyšší než dolní hranice se považují za jeden klastr.
Montáž výše popsaného modelu na základě pozorovaných údajů znamená najít zadní distribuce nad pravděpodobnostmi klastru a jejich přidruženými prostředky. V nekonečném dimenzionálním případě je zjevně nemožné výslovně zapsat zadní. Je však možné odebrat vzorky z této zadní části pomocí upravené Gibbsův vzorkovač.[5] Toto je kritická skutečnost, díky níž je Dirichletův proces užitečný dříve odvození.
Aplikace Dirichletova procesu
Dirichletovy procesy se často používají v Bayesian neparametrické statistiky. „Neparametrický“ zde neznamená model bez parametrů, spíše model, ve kterém reprezentace rostou, protože je pozorováno více dat. Bayesovské neparametrické modely si získaly značnou popularitu v oblasti strojové učení z důvodu výše zmíněné flexibility, zejména v neřízené učení. V bayesovském neparametrickém modelu nejsou předchozí a zadní distribuce parametrické distribuce, ale stochastické procesy.[6] Skutečnost, že Dirichletovo rozdělení je rozdělení pravděpodobnosti na simplexní množin nezáporných čísel, která se sčítají k jednomu, je dobrým kandidátem na modelování distribucí přes distribuce nebo distribucí přes funkce. Neparametrická povaha tohoto modelu navíc z něj činí ideálního kandidáta na problémy s klastrováním, kde je předem neznámý počet klastrů. Kromě toho byl Dirichletův proces také použit k vývoji směsi expertních modelů v kontextu supervizovaných algoritmů učení (nastavení regrese nebo klasifikace). Například směsi Gaussianských expertů na procesy, kde z údajů musí být odvozen počet požadovaných expertů.[7][8]
Protože čerpání z Dirichletova procesu jsou diskrétní, je důležité je použít jako předchozí pravděpodobnost v modely nekonečné směsi. V tomto případě, je parametrická sada distribucí komponent. Generativní proces tedy spočívá v tom, že se vzorek čerpá z Dirichletova procesu, a pro každý datový bod se zase hodnota čerpá z této distribuce vzorku a použije se jako distribuce komponent pro daný datový bod. Skutečnost, že neexistuje žádné omezení počtu odlišných složek, které mohou být generovány, činí tento druh modelu vhodným pro případ, kdy počet složek směsi není předem dobře definován. Například nekonečná směs Gaussianova modelu,[9] stejně jako související regresní modely směsi, např.[10]
Nekonečná povaha těchto modelů je také propůjčuje zpracování přirozeného jazyka aplikace, kde je často žádoucí zacházet se slovní zásobou jako s nekonečnou, diskrétní sadou.
Dirichletův proces lze také použít pro neparametrické testování hypotéz, tj. K vývoji Bayesiánských neparametrických verzí klasických neparametrických testů hypotéz, např. podepsat test, Wilcoxonův test součtu, Wilcoxonův podepsaný test Například Bayesovské neparametrické verze Wilcoxonova testu součtu a Wilcoxonova testu se znaménkem byly vyvinuty pomocí nepřesný Dirichletův proces, předchozí Dirichletův proces neznalosti.[Citace je zapotřebí ]
Související distribuce
- The Pitman – Yorův proces je zevšeobecněním Dirichletova procesu, aby se přizpůsobily ocasům zákonů moci
- The hierarchický Dirichletův proces rozšiřuje běžný Dirichletův proces pro modelování seskupených dat.
Reference
- ^ Ferguson, Thomas (1973). „Bayesiánská analýza některých neparametrických problémů“. Annals of Statistics. 1 (2): 209–230. doi:10.1214 / aos / 1176342360. PAN 0350949.
- ^ http://topicmodels.west.uni-koblenz.de/ckling/tmt/crp.html?parameters=0.5&dp=1#
- ^ Paisley, John. Jednoduchý důkaz o lámání konstrukce Dirichletova procesu. Technická zpráva, Princetonská univerzita, Katedra informatiky, 2010.
- ^ Aad van der Vaart, Subhashis Ghosal (2017). Základy bayesovského neparametrického závěru. Cambridge University Press. ISBN 978-0-521-87826-5.
- ^ Sudderth, Erik (2006). Grafické modely pro vizuální rozpoznávání a sledování objektů (PDF) (Ph.D.). MIT Stiskněte.
- ^ Nils Lid Hjort Chris Holmes, Peter Müller a Stephen G. Walker (2010). Bayesiánská neparametrie. Cambridge University Press. ISBN 978-0-521-51346-3.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Sotirios P. Chatzis, „Latentní variabilní Gaussův procesní model s Pitman-Yorskými procesními prioritami pro klasifikaci více tříd,“ Neurocomputing, sv. 120, s. 482-489, listopad 2013. [1]
- ^ Sotirios P. Chatzis, Yiannis Demiris, „Neparametrické směsi Gaussových procesů s chováním podle zákona o moci,“ IEEE Transactions on Neural Networks and Learning Systems, sv. 23, č. 12, s. 1862-1871, prosinec 2012. [2]
- ^ Rasmussen, Carl (2000). „Nekonečný Gaussův model směsi“ (PDF). Pokroky v systémech zpracování neurálních informací. 12: 554–560.
- ^ Sotirios P. Chatzis, Dimitrios Korkinof a Yiannis Demiris, „Neparametrický bayesovský přístup k učení robotů pomocí demonstrace,“ Robotics and Autonomous Systems, sv. 60, č. 6, s. 789–802, červen 2012. [3]
externí odkazy
- Úvod do distribuce dirichletů a souvisejících procesů od Frigyika, Kapily a Gupty
- Přehled Dirichletových procesů Yee Whye Teh
- Webová stránka pro workshop NIPS 2003 o neparametrických bayesiánských metodách
- Výukový program Michaela Jordana NIPS 2005: Neparametrické Bayesovské metody: Dirichletovy procesy, čínské restaurační procesy a tak dále
- Shrnutí Petera Greena o konstrukci Dirichletových procesů
- Papír Petera Greena o pravděpodobnostních modelech Dirichletových procesů s důsledky pro statistické modelování a analýzu
- Výukový program Zoubin Ghahramani na UAI 2005 o neparametrických bayesovských metodách
- Software GIMM pro provádění klastrové analýzy pomocí modelů nekonečné směsi
- Příklad shlukování hraček pomocí Dirichletova procesu. podle Zhiyuan Weng