Technische Samenvatting: Een Differentieerbare Bayesiaanse Relaxatie voor Latente Partiële-Orde-Inferentie

Probleemstelling

Veel datasets die rankings, agentensporen en workflows omvatten, worden vastgelegd als lineaire sequenties (totale ordeningen). De onderliggende beperkingen die deze sequenties beheersen, zijn echter vaak slechts partiëel geordend (posets). In dergelijke situaties kan een waargenomen lineaire orde willekeurige linearisatie, planning of logboekartefacten weerspiegelen in plaats van ware prerequisietrelaties. Het behandelen van alle waargenomen voorafgaandheden als echte prerequisieten leidt tot overmatig sequentiële en onrealistische structuren, met name in complexe workflows of LLM-agentomgevingen waar onnodige ordening redundante uitvoeringsstappen induceert.

De kernuitdaging bestaat uit het infereren van de latente partiële orde uit deze ruisbeladen lineaire extensies. Hoewel Bayesiaanse inferentie natuurlijk is voor het hanteren van de onzekerheid die inherent is aan schaarse of ruisbeladen sporen, staan bestaande methoden voor een ernstig computatief knelpunt. Bestaande "hard-PO"-benaderingen vertrouwen op combinatorische Markov Chain Monte Carlo (MCMC) om de discrete ruimte van partiële ordeningen te verkennen. Dit is computatief onhaalbaar omdat het tellen van lineaire extensies van een poset #P-compleet is. Bovendien verhindert de discontinuïteit van harde voorafgaandheidsbeperkingen het gebruik van efficiënte op gradiënten gebaseerde inferentiemethoden (zoals gradiënt-MCMC of variatie-inferentie), wat de schaalbaarheid beperkt tot kleine instanties.

Methodologie

De auteurs stellen een differentieerbare Bayesiaanse relaxatie voor die het discrete, combinatorische inferentieprobleem transformeert in een continu optimalisatieprobleem, terwijl de semantische structuur van het oorspronkelijke harde model behouden blijft.

1. Latente Product-Orde Parametrisatie

In plaats van direct partiële ordeningen te bemonsteren, parametrisert het model de latente structuur met een inbeddingsmatrix $U \in \mathbb{R}^{M \times d}$, waarbij elk item $x$ een latent vector $u_x$ toegewezen krijgt. De harde voorafgaandheidsrelatie wordt gedefinieerd via een productorde: $z \succ_U x$ dan en slechts dan als $u_{z,k} > u_{x,k}$ voor alle dimensies $k=1,\dots,d$. Dit maakt onvergankelijkheid mogelijk (wanneer vectoren niet strikt gedomineerd zijn in alle dimensies) en codeert de geometrie van de partiële orde.

2. Differentieerbare Relaxatie van Harde Beperkingen

Om op gradiënten gebaseerde inferentie mogelijk te maken, vervangen de auteurs de discontinuïteitscomponenten van de likelihood met harde frontieerbeperkingen door gladde vervangers:

• Zachte Voorafgaandheid: De harde indicator $1[z \succ_U x]$ wordt vervangen door een zachte score $D_U(z, x) = \sigma(\gamma M_U(z, x))$. Hierbij wordt de harde minimale marge $m_U(z, x) = \min_k (u_{z,k} - u_{x,k})$ benaderd door een soft-minimum functie $smin_\tau$, en wordt de indicator gladgestreken via een sigmoidfunctie $\sigma$ met een scherpte-parameter $\gamma$.
• Zachte Frontiere: De harde frontiere (de verzameling maximale elementen die beschikbaar zijn voor selectie) wordt vervangen door een zachte frontiere-gewicht $\tilde{F}_t(x; U)$. Dit gewicht is het product van $(1 - D_U(z, x))$ voor alle resterende items $z$, wat items die sterk door anderen worden voorafgegaan effectief afwaardeert, maar een niet-nul waarschijnlijkheid toestaat voor keuzes buiten de frontiere.
• Gegladde Likelihood: De oorspronkelijke frontiere-softmax-likelihood, die een waarschijnlijkheid van nul toekent aan items buiten de frontiere, wordt vervangen door een gegladde versie die kleine maar niet-nul waarschijnlijkheden toekent aan items buiten de frontiere. Dit resulteert in een continu differentieerbare objectfunctie met betrekking tot de inbeddingsparameters $U$.

3. Theoretische Waarborgen

Het artikel biedt verschillende theoretische bewijzen met betrekking tot de relaxatie:

• Zachte Transitiviteit: De gegladde scores voldoen aan een eigenschap van zachte transitiviteit ($\text{logit } D_U(z, x) \ge \text{logit } D_U(z, y) + \text{logit } D_U(y, x)$), die convergeert naar harde transitiviteit naarmate de gladmakende parameters hun limieten benaderen.
• Herstel bij Scherpe Limiet: Naarmate de temperatuur $\tau \to 0$ en de scherpte $\gamma \to \infty$, convergeren de gegladde frontiere-gewichten en de likelihood naar het harde frontiere-beperkte model.
• Marginaal Consistentie: De prior over de gegladde partiële ordeningen is marginaal consistent, waardoor wordt gegarandeerd dat de verdeling over sub-orden consistent is met de globale verdeling.

4. Inferentiestrategieën

De continue posterior maakt toepassing van efficiënte inferentie-algoritmes mogelijk:

• Relaxed-MCMC: Gebruikt Hamiltonian Monte Carlo (NUTS) om te bemonsteren uit de gegladde posterior.
• FullRank-VI: Past automatische differentiatie variatie-inferentie (ADVI) toe met een full-rank Gaussische benadering.
• Flow-VI: Gebruikt normaliserende stromen om de posteriorverdeling te modelleren, wat meer flexibiliteit biedt dan Gaussische benaderingen.

Belangrijkste Bijdragen

1. Differentieerbare Relaxatie: De introductie van een differentieerbare Bayesiaanse relaxatie voor latente partiële-orde-inferentie, waardoor het gebruik van gradiënt-gebaseerde MCMC en variatie-inferentie mogelijk wordt voor een probleem dat eerder beperkt was tot discrete combinatorische zoekopdrachten.
2. Gladde Frontiere-Beperkte Likelihood: De ontwikkeling van een gladde likelihood die de frontiere-semantiek van het harde model behoudt (het onderscheiden van haalbare van onhaalbare acties), terwijl discrete beperkingen worden vervangen door continue vervangers.
3. Theoretische Convergentie: Bewijzen die aantonen dat het gegladde model convergeert naar het harde model in de scherpe limiet en zachte transitiviteit vertoont.
4. Empirische Validatie: Uitgebreide experimenten die aantonen dat de gegladde methoden een hoge posterior-trouw bereiken ten opzichte van harde MCMC op kleine instanties en superieure trade-offs tussen runtime en nauwkeurigheid bieden op grotere problemen.

Experimentele Resultaten

De auteurs hebben de methode geëvalueerd op drie datasets: synthetische data, het Bishops getuigenlijst-corpus (historische sociale dominantie) en Cloud-agentensporen (door LLM gegenereerde workflows).

• Synthetische Data: Op instanties met tot 100 items kwamen de gegladde methoden (Relaxed-MCMC, FullRank-VI, Flow-VI) nauwkeurig overeen met de posterior-trouw van Hard-MCMC (gemeten door de Mean Absolute Error van paarwijze voorafgaandheidskansen), terwijl ze orde van grootte sneller waren. Hard-MCMC werd onhaalbaar voor $n > 30$ vanwege combinatorische explosie, terwijl Flow-VI efficiënt schaalde tot $n=100$.
• Bishops Corpus: Op 68 getuigenlijsten met 45 acteurs behaalde Relaxed-MCMC de beste voorspellende fit (laagste WAIC), aanzienlijk beter dan Plackett-Luce-mengsel-baselines. FullRank-VI bood de beste praktische trade-off, met een runtime van 5,5 minuten vergeleken met 70 minuten voor Hard-MCMC, met vergelijkbare WAIC.
• Cloud Agent Sporen: Op 54 workflowsporen kwam Relaxed-MCMC Hard-MCMC bijna gelijk in structureel herstel (closure F1) en behaalde de beste voorspellende prestaties (laagste Step NLL). FullRank-VI bood de snelste inferentie met sterk structureel herstel, terwijl Flow-VI een verbeterde voorspellende kalibratie toonde ten opzichte van Hard-MCMC, ondanks iets zwakker structureel herstel.

Betekenis en Claims

Het artikel claimt dat dit werk de kloof overbrugt tussen de semantische correctheid van harde partiële-orde-inferentie en de schaalbaarheid van op gradiënten gebaseerde methoden. Door de discrete beperkingen te relaxeren, stellen de auteurs Bayesiaanse inferentie op latente partiële ordeningen mogelijk voor datasets die eerder computatief onhandelbaar waren.

De auteurs benadrukken dat de gegladde posterior niet louter een benadering voor snelheid is, maar een "goed model op zichzelf" dat de voor het interpreteren van prerequisieten essentiële frontiere-beperkte semantiek behoudt. Zij merken op dat hoewel de methode schaalt tot $M=100$, deze te maken krijgt met geheugenbeperkingen bij $M=200$ vanwege de $O(M^2)$ opslag van de zachte-voorafgaandheidsmatrix. Het werk positioneert zichzelf als een praktische oplossing voor het infereren van interpreteerbare structuren in agentensporen en workflows, waarbij stabiele prerequisieten worden onderscheiden van herschikbare acties zonder de computatiekosten van discrete combinatorische zoekopdrachten te induceren.