Duálna reprezentácia zrýchľuje Gibbsovo vzorkovanie bez drahšieho jedného prechodu

Gibbsovo vzorkovanie je klasická metóda Markovových reťazcov Monte Carlo, ktorá vytvára vzorky z komplikovaného viacrozmerného rozdelenia postupnou aktualizáciou jednotlivých premenných. Používa sa v bayesovskej štatistike, strojovom učení, spracovaní obrazu aj vo fyzikálnych modeloch. Jeho slabinou môže byť pomalé miešanie: ak sú premenné silno previazané, reťazec potrebuje veľa prechodov, kým prestane výrazne závisieť od počiatočného stavu a začne spoľahlivo reprezentovať cieľové rozdelenie.

Borna Khodabandeh z Oxfordskej univerzity a Mehdi Molkaraie z Universitat Politècnica de Catalunya a University of Toronto skúmajú spôsob, ako tento problém zmierniť zmenou reprezentácie modelu. Zamerali sa na náhodný Gibbsov sampler pre gaussovské grafové modely s takzvaným thin-membrane priorom. Namiesto vzorkovania iba v pôvodnej, primárnej doméne vytvoria duálny normálny faktorový graf pomocou Fourierovej transformácie lokálnych faktorov a sampler spustia nad premennými tejto transformovanej reprezentácie.

Gaussovský grafový model opisuje viacrozmerné normálne rozdelenie, v ktorom hrany grafu zachytávajú lokálne závislosti medzi premennými. Pri veľkom grafe by presný výpočet niektorých štatistík vyžadoval inverziu matice presnosti s kubickou zložitosťou vzhľadom na počet vrcholov. Gibbsovo vzorkovanie vie využiť riedkosť grafu a jeden prechod vykonať s nákladmi úmernými počtu hrán. To je výhodné, iba ak na získanie použiteľných vzoriek netreba priveľa pomaly konvergujúcich prechodov.

Kľúčová myšlienka práce spočíva v tom, že Fourierova transformácia lokálnych faktorov zachová gaussovský charakter modelu, ale zmení jeho kovariančnú a grafovú reprezentáciu. V duálnom grafe sa pôvodné vzťahy medzi vrcholovými premennými premietnu do premenných spojených s hranami. Autori odvodili explicitné algebraické prepojenie medzi kovariančnými štruktúrami primárneho a duálneho modelu. Vďaka tomu možno z duálnych vzoriek spätne získať marginálne štatistiky pôvodného modelu.

Pre homogénne k-regulárne grafy práca prináša presné konvergenčné rýchlosti v oboch doménach. Autori tvrdia, že pri homogénnych modeloch, ktorých grafy obsahujú cykly, má rýchlosť v duálnej doméne univerzálnu podobu nezávislú od konkrétnej topológie grafu. Efektívnu konvergenciu navyše ovplyvňuje algebraická konektivita, teda spektrálna vlastnosť vyjadrujúca, ako dobre je graf prepojený. Vyššia konektivita môže v tomto nastavení priniesť ďalšie zrýchlenie.

Dôležitý je pomer medzi zrýchlením a cenou jednej iterácie. Podľa analýzy zostáva výpočtová zložitosť jedného prechodu v duálnej doméne prakticky rovnakého rádu ako v pôvodnom modeli. Nejde teda o zrýchlenie dosiahnuté jednoducho tým, že sa na každý krok použije podstatne viac výpočtov. Kompromisom je vyššia spotreba pamäte, pretože duálna reprezentácia pracuje s počtom premenných naviazaným na hrany grafu, ktorý môže byť väčší než počet pôvodných vrcholov.

Numerické experimenty na viacerých rodinách grafov podľa autorov potvrdili teoretické predpovede a ukázali podstatné zlepšenie konvergencie v rozličných nastaveniach. Štúdia skúmala okrem pravidelných grafov aj úplné, bipartitné, mriežkové a ďalšie štruktúry a preverovala správanie pri zväčšovaní grafu. Praktický význam je najväčší v prípadoch, kde je primárny sampler brzdený silnými lokálnymi závislosťami, zatiaľ čo transformovaná reprezentácia ich dokáže pre sampler usporiadať priaznivejšie.

Prístup môže byť zaujímavý pre odhad marginálnych variancií vo veľkých grafových modeloch, rekonštrukciu povrchov a niektoré úlohy počítačového videnia, kde thin-membrane prior vyjadruje preferenciu hladkých susedných hodnôt. Širší odkaz práce je však všeobecnejší: pri MCMC nemusí byť jedinou cestou k rýchlejšej konvergencii komplikovanejší sampler. Niekedy môže byť účinnejšie zachovať jednoduchý aktualizačný mechanizmus a nájsť matematicky ekvivalentnú reprezentáciu, v ktorej sa mu pracuje ľahšie.

Obmedzenia sú podstatné. Analytické záruky sa týkajú najmä homogénnych gaussovských modelov a základného náhodného Gibbsovho prechodu. Reálne bayesovské modely bývajú nehomogénne, negaussovské a hierarchické; v takom prostredí nemusí byť dualizácia rovnako jednoduchá ani výhodná. Autori tiež upozorňujú na pamäťový kompromis a širšie experimentálne overenie nehomogénnych prípadov ponechávajú ako ďalšiu prácu. Výsledok je navyše zverejnený ako preprint, takže ešte neprešiel štandardným recenzným procesom časopisu alebo konferencie.

Štúdia napriek tomu ponúka konkrétny teoretický výsledok aj reprodukovateľnú výpočtovú myšlienku. Ukazuje, že dualita faktorových grafov, známa z teórie kódovania a štatistickej fyziky, môže mať praktický význam aj pri modernom štatistickom vzorkovaní. Ak sa výhody potvrdia na širších modeloch, transformácia reprezentácie by mohla doplniť blokované, kolabované a iné pokročilé varianty Gibbsovho samplera bez toho, aby bolo potrebné opustiť jeho základnú jednoduchosť.