Duálny faktorový graf zrýchľuje Gibbsovo vzorkovanie pri rovnakej zložitosti prechodu

Keď problémom nie je sampler, ale reprezentácia

Gibbsovo vzorkovanie patrí medzi základné metódy Markovových reťazcov Monte Carlo. Zložité viacrozmerné rozdelenie spracúva postupným prepočítavaním jednotlivých premenných podľa ich podmienených rozdelení. V gaussovských grafových modeloch pritom dokáže využiť riedku štruktúru grafu: jeden úplný prechod má výpočtovú zložitosť úmernú počtu hrán. Slabinou je miešanie reťazca. Ak sú susedné premenné silno previazané, ďalšie vzorky zostávajú výrazne korelované a na spoľahlivý odhad variancií či kovariancií treba veľa prechodov. Nezávislá učebnica Monte Carlo metód od Arta Owena túto citlivosť Gibbsovho samplera na korelované komponenty uvádza ako všeobecnú vlastnosť metódy, nejde teda o problém špecifický iba pre novú štúdiu.

Borna Khodabandeh z Oxfordskej univerzity a Mehdi Molkaraie z Universitat Politècnica de Catalunya a University of Toronto navrhujú meniť reprezentáciu modelu namiesto samotného aktualizačného algoritmu. Ich preprint sa sústreďuje na random-sweep Gibbs sampler, ktorý pri každej aktualizácii náhodne vyberie jednu súradnicu. Cieľom sú gaussovské grafové modely s takzvaným thin-membrane priorom: susedné hodnoty majú tendenciu byť podobné, čo sa používa napríklad pri modelovaní hladkých povrchov a v úlohách počítačového videnia. Pri veľkom grafe by presné získanie kovariančnej matice vyžadovalo nákladnú inverziu matice presnosti, kým vzorkovanie zachováva výhodu lokálnych výpočtov.

Čo mení duálny normálny faktorový graf

Autori zapíšu pôvodné rozdelenie ako normálny faktorový graf a na jeho lokálne faktory aplikujú Fourierovu transformáciu. Keďže Fourierova transformácia gaussovského faktora zostáva až na mierku gaussovská, výsledkom je ďalší gaussovský model. Premenné sa však presunú z vrcholov na hrany a zmení sa štruktúra ich závislostí. Nejde iba o aproximáciu pôvodného cieľového rozdelenia. Práca odvodzuje explicitný algebraický vzťah medzi kovariančnými štruktúrami primárnej a duálnej domény, takže marginálne variancie a ďalšie štatistiky pôvodného modelu možno rekonštruovať zo vzoriek vytvorených v duálnom modeli.

Toto rozlíšenie je dôležité pri porovnaní s inými spôsobmi zrýchľovania gaussovského vzorkovania. Napríklad práca Clone MCMC publikovaná na NeurIPS 2017 umožňuje paralelizáciu tým, že vzorkuje z aproximácie cieľového gaussovského rozdelenia a zavádza nastaviteľný kompromis medzi skreslením a varianciou. Nový duálny prístup sa v skúmanej triede modelov usiluje zachovať informáciu o pôvodnom rozdelení cez presné algebraické mapovanie. To však neznamená, že je automaticky lepší vo všetkých situáciách: metódy riešia odlišné prevádzkové obmedzenia a nová analýza zatiaľ nepokrýva všeobecné negaussovské modely.

Pre homogénne k-regulárne grafy autori odvodzujú presné rýchlosti konvergencie v primárnej aj duálnej doméne. Pri homogénnych grafoch obsahujúcich cykly má byť základná rýchlosť v duálnej doméne univerzálna, teda nezávislá od konkrétnej topológie grafu. Pre k-regulárne grafy s k väčším ako dva vychádza asymptotická konvergencia duálneho samplera rýchlejšia než konvergencia primárneho. Efektívna rýchlosť relevantná pre rekonštrukciu pôvodných štatistík sa môže zlepšiť ešte viac a riadi ju algebraická konektivita grafu, čiže jeho najmenšia nenulová laplaciánová vlastná hodnota.

Dôvodom ďalšieho zrýchlenia je rozklad hranových premenných na cyklový a rezový priestor. Veličina, z ktorej sa rekonštruujú pôvodné vrcholové štatistiky, cyklovú zložku anuluje. Pomalšie módy reťazca nachádzajúce sa iba v tomto priestore preto nemusia určovať praktickú rýchlosť odhadu. Lepšie prepojený graf má spravidla vyššiu algebraickú konektivitu, a tým môže umožniť rýchlejší zánik relevantnej chyby. Ide o presnejšie tvrdenie než všeobecné konštatovanie, že transformácia „zrýchľuje sampler“: zrýchlenie sa týka konkrétnych štatistík a spektrálnych smerov, ktoré ich ovplyvňujú.

Výpočtová cena a experimentálne výsledky

Duálna matica presnosti môže pôsobiť hustejšie než pôvodná, takže naivná implementácia by výhodu konvergencie znehodnotila drahšími aktualizáciami. Autori však priebežne udržiavajú pomocnú vrcholovú veličinu odvodenú z hranových premenných. Po zmene jednej hrany sa upravia iba jej dva koncové vrcholy, vďaka čomu zostáva aktualizácia jednej súradnice konštantná a celý prechod má zložitosť O(|E|). To zodpovedá rádu primárneho samplera. Cena sa presúva najmä do pamäte: duálna reprezentácia pracuje s premennou pre každú hranu, takže pri hustom grafe môže byť ich podstatne viac než pôvodných vrcholov.

Experimenty najprv overujú algebraické mapovanie na toroidálnej mriežke 8 × 8 pomocou 100 000 duálnych vzoriek. Pri porovnaní konvergencie na mriežke 10 × 10 autori uskutočnili 10 000 nezávislých behov; duálny odhad kovariančnej matice podľa ich grafov klesol o niekoľko rádov počas niekoľkých prechodov, zatiaľ čo primárny odhad klesal pomalšie. Výhodu pozorovali aj na 64 heterogénnych Wattsových–Strogatzových grafoch a pri náhodnom poradí bez opakovania či deterministickom poradí aktualizácií. Pre tieto alternatívne stratégie však štúdia poskytuje experimentálne pozorovanie, nie rovnakú teoretickú záruku ako pre random-sweep variant.

Test škálovateľnosti používa toroidálnu mriežku 100 × 100 a 600 nezávislých behov. Namiesto celej kovariančnej matice sleduje marginálne variancie, ktorých referenčnú hodnotu možno pri tejto symetrickej štruktúre vypočítať analyticky. Duálny sampler sa podľa výsledkov dostal k referenčnej hodnote v priebehu niekoľkých prechodov, kým primárny konvergoval výrazne pomalšie. Autori zverejnili aj implementáciu a skripty na reprodukciu experimentov. To zvyšuje overiteľnosť výsledkov, nenahrádza však nezávislú replikáciu ani odborné recenzné konanie.

Praktický význam a hranice výsledku

Pre slovenské a európske výskumné tímy môže byť myšlienka relevantná v úlohách spracovania obrazu, rekonštrukcie povrchov, priestorovej štatistiky či analýzy sietí, kde veľké riedke grafy znemožňujú priamu inverziu matice presnosti. Ak výpočet beží na obmedzenom univerzitnom alebo podnikovom hardvéri, menej potrebných prechodov môže skrátiť čas analýzy aj spotrebu výpočtových zdrojov. Pred praktickým nasadením však treba merať celkový čas, pamäť, autokoreláciu a efektívnu veľkosť vzorky na konkrétnom modeli. Rovnaká asymptotická zložitosť jedného prechodu sama osebe nezaručuje rovnaké konštantné náklady implementácie.

Otvorené neistoty sú výrazné. Presné výsledky sa týkajú najmä homogénnych gaussovských modelov s konkrétnou párovou štruktúrou a základného náhodného poradia aktualizácií. Autori experimentálne skúšajú aj nehomogénne a nepravidelné grafy, ale všeobecnú teóriu pre ne ešte neodvodili. Nejasné zostáva, ako ľahko sa dualizácia prenesie na širšie gaussovské faktory, hierarchické modely alebo negaussovské rozdelenia, pri ktorých Fourierova transformácia nemusí viesť k rovnako jednoduchej podmienenej aktualizácii. Samotná práca je navyše verziou v1 na arXive a nemá uvedené recenzované prijatie.

Najdôležitejším prínosom preto nie je tvrdenie o univerzálnom zrýchlení MCMC, ale konkrétny dôkaz, že matematicky ekvivalentná reprezentácia môže zásadne zmeniť spektrum jednoduchého samplera. Štúdia spája dualitu faktorových grafov, známu z teórie kódovania a štatistickej fyziky, s praktickým odhadom kovariancií. Ak výsledky potvrdia nezávislé replikácie a rozšírenia na všeobecnejšie modely, duálna reprezentácia môže doplniť blokované, kolabované či paralelné varianty Gibbsovho vzorkovania. Zatiaľ ide o sľubný a reprodukovateľný preprint, nie o hotové univerzálne riešenie pomalého miešania.