Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization

Titel: Informatietheoretische selectie van coördinaat-subsets en partities van multivariate Markov-ketens via submodulaire optimalisatie

Auteurs: Zheyuan Lai en Michael C.H. Choi (National University of Singapore)

1. Probleemstelling

Het artikel adresseert twee fundamentele optimalisatieproblemen binnen het domein van eindige, ergodische multivariate Markov-ketens:

1. Projectie-optimalisatie: Het vinden van een optimale subset $S$ van coördinaten (met een beperkte grootte $|S| \le m$) zodat de geprojecteerde overgangsmatrix $P(S)$ een specifiek informatietheoretisch criterium maximaliseert of minimaliseert.
2. Partitie-optimalisatie: Het vinden van een optimale partitie van coördinaten zodat de gefactoriseerde Markov-keten (waarbij groepen van coördinaten onafhankelijk evolueren) de minimale informatieverlies heeft ten opzichte van de oorspronkelijke keten.

De auteurs richten zich op criteria gebaseerd op informatie-theorie, waaronder:

• Entropie-rate: Het maximaliseren van de "randomness" van een subset.
• Afstand tot stationariteit: Het minimaliseren van de Kullback-Leibler (KL) divergentie tussen de geprojecteerde keten en de stationaire verdeling.
• Onafhankelijkheid: Het minimaliseren van de afstand tot een model waarbij coördinaten onafhankelijk zijn.
• Factoriseerbaarheid: Het minimaliseren van de informatieverlies bij het benaderen van de keten door een gefactoriseerd model.

Traditionele methoden (zoals spectrale theorie) zijn vaak onpraktisch in hoge dimensies omdat ze eigenwaarden en eigenvectoren vereisen. Deze paper vult een gat door een combinatorische aanpak te gebruiken die directer is en gebaseerd is op de structuur van de overgangsmatrix.

2. Methodologie

De kern van de methodologie ligt in het identificeren van submodulaire en supermodulaire structuren in de objectief functies van de bovenstaande problemen.

• Submodulariteit en Supermodulariteit: De auteurs tonen aan dat veel informatietheoretische functies (zoals entropie-rate en KL-divergentie) de eigenschap van "diminishing returns" (submodulair) of "increasing returns" (supermodulair) vertonen.
  • Bijvoorbeeld: Het toevoegen van een coördinaat aan een kleine subset levert een grotere marginale winst op in entropie dan het toevoegen aan een grote subset.
• Transformatie van Doelfuncties: Veel van deze functies zijn niet monotoon (ze gaan niet altijd omhoog of omlaag bij het toevoegen van elementen), wat standaard greedy-algoritmen ongeschikt maakt. De auteurs gebruiken een transformatietechniek (gebaseerd op Theorem 2.5) om een niet-monotoon submodulair probleem om te vormen naar een verschil tussen een monotoon submodulaire functie $g$ en een modulaire functie $c$:
  $$\max (g(S) - c(S))$$
• Algoritmen:
  • Distorted Greedy Algorithm: Voor het maximaliseren van het verschil tussen een submodulaire en een modulaire functie. Dit algoritme biedt theoretische benaderingsgaranties.
  • Generalized Distorted Greedy Algorithm: De auteurs generaliseren het bestaande "distorted greedy" algoritme naar de k-submodulaire setting. Hierbij wordt de beslissingsvariabele een partitie van coördinaten in $k$ gelabelde groepen. Dit is essentieel voor het optimaliseren van gefactoriseerde modellen.
  • Batch Greedy Algorithm: Voor het maximaliseren van monotoon niet-dalende supermodulaire functies (zoals de afstand tot stationariteit).

3. Belangrijkste Bijdragen

1. Identificatie van Nieuwe Submodulaire Functies: De auteurs bewijzen dat diverse natuurlijke set-functies in de theorie van Markov-ketens submodulair of supermodulair zijn. Dit omvat de afstand tot stationariteit, onafhankelijkheid en factoriseerbaarheid, zowel voor subsets als voor complementen en partities.
2. Systematische Toepassing van Submodulaire Optimalisatie: Dit is, naar hun weten, de eerste systematische toepassing van greedy-submodulaire optimalisatie voor subset- en partitiekeuze-problemen specifiek voor multivariate Markov-ketens.
3. Generalisatie van het Distorted Greedy Algoritme: Ze introduceren een generalisatie van het distorted greedy algoritme voor k-submodulaire maximalisatie onder kardinaliteitsbeperkingen. Dit algoritme heeft theoretische ondergrenzen (approximation guarantees) en is van onafhankelijk belang voor andere k-submodulaire optimalisatieproblemen.
4. Numerieke Validatie: Uitgebreide experimenten met openbare code op twee bekende modellen:
   • Het Bernoulli-Laplace model.
   • Het Curie-Weiss model (een model uit de statistische fysica).

4. Resultaten

De numerieke experimenten tonen het volgende aan:

• Efficiëntie: De voorgestelde greedy-algoritmen identificeren efficiënt subsets en partities die de informatietheoretische criteria optimaliseren.
• Prestatieverschil: In veel gevallen (bijvoorbeeld bij het maximaliseren van de entropie-rate) presteert het distorted greedy algoritme beter dan de standaard heuristische greedy-algoritmen, vooral bij specifieke kardinaliteitsbeperkingen. Het distorted algoritme levert vaak een hogere entropie-rate of een lagere KL-divergentie.
• MCMC Toepassing: Een specifiek experiment met het Curie-Weiss model toont aan dat het selecteren van een subset die het dichtst bij de stationaire verdeling ligt (via het minimaliseren van de afstand tot stationariteit), kan leiden tot een verbeterde MCMC-sampler. Door een "slecht" coördinaat te isoleren en de rest van de keten te factoriseren, werd de totale variatie-afstand tot de stationaire verdeling na 10 stappen met ongeveer 14% verlaagd ten opzichte van de originele keten.
• k-submodulariteit: De generalisatie naar k-submodulariteit (voor partities) bleek succesvol in het vinden van optimale groepen van coördinaten die gezamenlijk de beste factorisatie opleveren.

5. Significantie

Deze studie is significant op meerdere vlakken:

• Methodologisch: Het biedt een nieuwe, wiskundig onderbouwde route voor modelreductie en coördinaatselectie in complexe stochastische systemen, zonder afhankelijk te zijn van zware spectrale berekeningen.
• Praktisch (MCMC): De resultaten hebben directe implicaties voor het versnellen van Markov Chain Monte Carlo (MCMC) methoden. Door te begrijpen welke coördinaten het meest "onafhankelijk" zijn of het snelst naar evenwicht convergeren, kunnen efficiëntere samplers worden ontworpen.
• Algoritmisch: De introductie van de generalisatie van het distorted greedy algoritme voor k-submodulaire problemen opent de deur voor het oplossen van een breed scala aan partitieproblemen in data science en statistiek, verder dan alleen Markov-ketens.

Kortom, de paper verbindt informatietheorie, combinatorische optimalisatie en stochastische processen om een krachtige toolkit te bieden voor het analyseren en vereenvoudigen van multivariate dynamische systemen.