Order in Partial Markov Categories

1. Il Problema e il Contesto

Le Categorie di Markov sono un quadro sintetico per la teoria della probabilità che permette di ragionare sui processi probabilistici utilizzando pochi assiomi fondamentali (struttura monoidale simmetrica, comonoidi commutativi per copia e scarto, e la presenza di distribuzioni condizionali). Tuttavia, le Categorie di Markov tradizionali modellano solo computazioni totali: ogni mappa è definita ovunque.

Nella pratica della teoria della probabilità, molte operazioni sono intrinsecamente parziali. Un esempio cruciale è l'aggiornamento bayesiano: se l'evidenza è incompatibile con la credenza a priori, l'aggiornamento non è possibile (o è nullo). Le Categorie di Markov standard non possiedono la struttura necessaria per esprimere questa parzialità, poiché l'assioma di naturalezza dello scarto (discarding) impedisce di modellare casi in cui un processo fallisce o non è definito.

Per colmare questa lacuna, il paper si concentra sulle Categorie di Markov Parziali, che nascono dalle Categorie Copy-Discard (CD), dove la naturalezza dello scarto viene rimossa, permettendo di rappresentare computazioni probabilistiche parziali.

2. Metodologia

Gli autori adottano un approccio basato sulla teoria delle categorie sintetica, utilizzando la notazione dei string diagram per visualizzare e manipolare le strutture algebriche. La metodologia si articola nei seguenti punti:

• Definizione di Ordinamento Condizionale: Viene introdotta una nuova relazione di preordine ($\sqsubseteq$) tra morfismi paralleli in una categoria Copy-Discard. Due morfismi $f, g: X \to Y$ soddisfano $f \sqsubseteq g$ se esiste un "witness" (un morfismo $r: Y \otimes X \to I$) tale che $f = g \triangleleft r$, dove $\triangleleft$ è la composizione condizionale.
• Arricchimento in Preordini: Si dimostra che ogni categoria di Markov parziale è arricchita (nel senso di Kelly) nella categoria dei preordini e delle mappe monotone. Ciò significa che ogni insieme di morfismi (hom-set) è un preordine e le operazioni della struttura monoidale simmetrica sono monotone rispetto a questo ordine.
• Analisi dei "Least Conditionals": Si studiano le distribuzioni condizionali minimali rispetto a due ordini: l'ordine condizionale ($\sqsubseteq$) e l'ordine di restrizione ($\preceq$). Si indaga la relazione tra l'esistenza di questi minimi e l'esistenza di comparatori (morfismi di moltiplicazione $\mu$) o "caps" ($\cap$).
• Disuguaglianze Sintetiche: Si formulano sinteticamente la disuguaglianza di Cauchy-Schwarz e la disuguaglianza tra media aritmetica e quadratica (Means Inequality) all'interno del linguaggio delle categorie, per poi derivare proprietà fondamentali dell'aggiornamento bayesiano.

3. Contributi Chiave e Risultati Principali

A. Arricchimento in Preordini (Sezione 3)

Il contributo principale è la dimostrazione che ogni categoria di Markov parziale possiede un arricchimento canonico in preordini.

• Proprietà Universale: L'ordine condizionale è il minimo arricchimento in preordini sub-unitario (dove la verità è il predicato massimo).
• Unificazione: Questo ordine generalizza e unifica ordinamenti noti in altre strutture:
  • In Categorie di Restrizione Cartesiane, coincide con l'ordine di restrizione canonico ($f \preceq g$).
  • In Bicategorie Cartesiane di Relazioni, coincide con l'ordine di inclusione delle relazioni.
  • In Kernels di Sottoprobabilità (es. $FinStoch_{\leq 1}$), coincide con l'ordinamento puntuale.

B. Relazione tra Comparatori e Condizionali Minimi (Sezione 4)

Gli autori stabiliscono un legame profondo tra la struttura algebrica e l'ordine:

• Teorema 4.4: In una categoria Copy-Discard-Compare (CDC), il moltiplicatore $\mu_X$ è il condizionale minimo (rispetto all'ordine di restrizione) della mappa di copia $\delta_X$. Analogamente, il "cap" $\cap_X$ è il condizionale minimo dell'identità.
• Teorema 4.6 (Converso): Se in una categoria Copy-Discard esistono condizionali minimi per le mappe di copia e identità (sotto certe condizioni di uniformità), allora la categoria ammette una struttura di CDC (ha comparatori).
• Questo risultato collega l'esistenza di strutture algebriche specifiche (comparatori) alla proprietà di esistenza di elementi minimi nell'ordine parziale.

C. Aumento della Validità nell'Aggiornamento (Sezione 5)

Utilizzando l'ordine introdotto, gli autori derivano una versione sintetica del teorema secondo cui l'aggiornamento bayesiano aumenta la validità dell'evidenza.

• Disuguaglianza di Cauchy-Schwarz Sintetica: Viene definita una disuguaglianza che generalizza quella classica per vettori, espressa tramite diagrammi a stringa e l'ordine $\sqsubseteq$.
• Disuguaglianza delle Medie (Means Inequality): Derivata da Cauchy-Schwarz, afferma che $u \otimes u \otimes v \otimes v \sqsubseteq u \otimes v \otimes v$ (in notazione diagrammatica).
• Teorema 5.13: In una categoria di Markov parziale che soddisfa la disuguaglianza delle medie e in cui gli scalari non nulli sono cancellativi, l'aggiornamento di uno stato a priori $\sigma$ con un predicato $p$ aumenta la validità di $p$ nello stato a posteriori. Formalmente: $\sigma \circ p \sqsubseteq p^\dagger_\sigma \circ p$.
• Questo risultato recupera sinteticamente il teorema noto per le distribuzioni discrete (Jacobs) e si estende a spazi di Borel standard.

4. Esempi e Applicazioni

Il paper valida la teoria su diverse classi di modelli:

• $FinStoch_{\leq 1}$ e $BorelStoch_{\leq 1}$: Categorie di kernel di sottoprobabilità. Qui l'ordine corrisponde alla dominazione puntuale. Viene mostrato che $FinStoch_{\leq 1}$ ammette condizionali minimi unici, mentre $BorelStoch_{\leq 1}$ no (a causa di problemi di misura, es. Esempio 4.9).
• Categorie di Restrizione Cartesiane: Dove tutti i morfismi sono deterministici. L'ordine condizionale coincide con l'ordine di restrizione.
• Bicategorie di Relazioni: Dove l'ordine condizionale coincide con l'inclusione delle relazioni, ma l'ordine di restrizione può differire se la categoria non è bilanciata.

5. Significato e Impatto

Questo lavoro è significativo per diversi motivi:

1. Fondamenti Sintetici: Fornisce un quadro unificato per la probabilità parziale, permettendo di ragionare su computazioni parziali (come l'aggiornamento bayesiano fallito) in modo puramente categorico, senza dipendere da modelli insiemistici specifici.
2. Strumento di Ragionamento: L'introduzione dell'arricchimento in preordini offre nuovi strumenti per il ragionamento inequazionale nella teoria della probabilità sintetica, permettendo di dimostrare proprietà come l'aumento di validità attraverso disuguaglianze strutturali.
3. Ponte tra Algebra e Logica: La connessione tra l'esistenza di condizionali minimi e la presenza di comparatori (struttura Frobenius parziale) offre nuove prospettive sulla classificazione delle categorie probabilistiche.
4. Generalizzazione: I risultati si applicano sia a contesti discreti che continui (Borel), e coprono sia la logica probabilistica che la semantica dei linguaggi di programmazione probabilistici.

In sintesi, il paper stabilisce che la struttura ordinale è intrinseca alle categorie di Markov parziali, offrendo una base solida per lo sviluppo di una teoria sintetica dell'inferenza probabilistica che gestisce nativamente l'incertezza e la parzialità.