Order in Partial Markov Categories

Título: Ordem em Categorias de Markov Parciais

Autores: Elena Di Lavore, Mario Román, Paweł Sobociński, M´ark Sz´eles
Publicação: Electronic Notes in Theoretical Informatics and Computer Science (ENTICS), Vol. 5, MFPS 2025.

---

1. Problema e Contexto

As Categorias de Markov são um framework sintético para a teoria da probabilidade, permitindo raciocinar sobre processos probabilísticos usando axiomas básicos (como cópia e descarte de informação) e condicionais. No entanto, as Categorias de Markov tradicionais modelam apenas computações totais (onde a probabilidade total é sempre 1).

Muitas operações fundamentais na teoria da probabilidade são inerentemente parciais. O exemplo mais notável é a atualização bayesiana: se uma evidência é incompatível com uma crença anterior (prior), a atualização é impossível (a probabilidade de sucesso é zero). As Categorias de Markov padrão não possuem estrutura para expressar essa parcialidade, pois o axioma de "descarte natural" impede que mapas sejam "parciais".

Para abordar isso, o artigo foca nas Categorias de Markov Parciais, que são baseadas em categorias de "copia-descarte" (copy-discard) onde o descarte não é natural. O problema central é: como definir e explorar relações de ordem nessas categorias para raciocinar sobre desigualdades probabilísticas (como "a atualização aumenta a validade da evidência") de forma sintética e abstrata?

2. Metodologia

Os autores utilizam a Teoria das Categorias e o Cálculo de Diagramas de Cordas (string diagrams) para desenvolver uma estrutura algébrica abstrata. A metodologia envolve:

• Definição de Estruturas: Introdução e refinamento de conceitos como Categorias de Copia-Descarte (CD), Categorias de Copia-Descarte-Comparação (CDC) e Categorias de Markov Parciais.
• Enriquecimento de Pré-ordem: Definição de uma relação de ordem específica (chamada desigualdade condicional) entre morfismos paralelos. Dois morfismos $f$ e $g$ satisfazem $f \sqsubseteq g$ se $f$ pode ser obtido de $g$ através de uma "condicional" $r$ (representando uma atualização ou restrição).
• Análise de Exemplos: Verificação da teoria em modelos concretos, incluindo:
  • Kernels de subprobabilidade (espaços de Borel e matrizes estocásticas finitas).
  • Categorias de Restrição Cartesianas (funções parciais).
  • Bicategorias Cartesianas de Relações.
• Derivação Axiomática: Uso de axiomas de Frobenius e propriedades de condicionais mínimas para provar teoremas sobre desigualdades fundamentais (Cauchy-Schwarz e médias).

3. Principais Contribuições

A. Enriquecimento Canônico em Pré-ordem

O resultado central é a prova de que toda Categoria de Markov Parcial é naturalmente enriquecida em pré-ordens.

• Define-se uma relação de ordem $f \sqsubseteq g$ (onde $f$ é uma "restrição" ou "atualização" de $g$) baseada na existência de um morfismo $r$ tal que $f = g \triangleleft r$.
• Demonstra-se que esta relação é uma pré-ordem reflexiva e transitiva.
• Mostra-se que as operações da categoria monoidal simétrica (composição e produto tensorial) são monótonas em relação a esta ordem.
• Significado: Isso recupera e unifica várias ordenações conhecidas em diferentes contextos (como a ordem de restrição em categorias de restrições e a ordem pontual em kernels de probabilidade) sob um único framework sintético.

B. Relação entre Comparadores e Condicionais Mínimas

Os autores investigam a existência de mapas de comparação (comparators/caps), que permitem verificar a igualdade de recursos.

• Estabelecem uma ligação profunda entre a existência de comparadores e a existência de condicionais mínimos (os menores condicionais possíveis para um dado morfismo).
• Teorema 4.4 e 4.6: Provam que a existência de condicionais mínimos para mapas de cópia ($\delta$) e identidade ($id$) implica a existência de uma estrutura de "Copia-Descarte-Comparação". Em outras palavras, a capacidade de encontrar o "menor" condicional é equivalente à capacidade de comparar recursos.

C. Desigualdade de Cauchy-Schwarz Sintética e Aumento de Validade

O artigo introduz uma versão sintética da Desigualdade de Cauchy-Schwarz e da Desigualdade das Médias (entre média aritmética e quadrática) dentro do contexto das categorias de Markov parciais.

• A partir dessas desigualdades, derivam um teorema fundamental: A atualização bayesiana aumenta a validade da evidência.
• Formalmente, se $\sigma$ é um estado anterior e $p$ é uma evidência (predicado), a validade de $p$ no estado posterior é maior ou igual à sua validade no estado anterior ($\sigma \# p \sqsubseteq p^\dagger_\sigma \# p$).
• Isso é provado sem recorrer a medidas concretas, apenas usando as propriedades da ordem e a cancelabilidade de escalares não nulos.

4. Resultados Chave

1. Unificação de Ordens: A ordem condicional definida é a menor enriquecimento de pré-ordem subunitária em Categorias de Markov Parciais. Em categorias discretas (como restrições cartesianas ou kernels finitos), ela coincide com as ordens canônicas já conhecidas.
2. Existência de Condicionais Mínimos: Em categorias balanceadas com a propriedade de "testemunha nítida" (sharp witness), a ordem de restrição e a ordem condicional coincidem. Isso garante a unicidade de condicionais mínimos em muitos casos práticos.
3. Contra-exemplo em Espaços Contínuos: O artigo mostra que em espaços de Borel padrão ($BorelStoch_{\le 1}$), condicionais mínimos nem sempre existem (devido a problemas de medida em conjuntos de medida zero), o que destaca a importância das condições de "balanceamento" e "testemunha nítida" para a teoria geral.
4. Recuperação Sintética de Resultados Clássicos: O teorema de que "atualizações aumentam a validade" (conhecido em probabilidade discreta) é provado de forma abstrata, generalizando-o para qualquer categoria que satisfaça a desigualdade sintética de Cauchy-Schwarz e tenha escalares canceláveis.

5. Significado e Impacto

• Fundamentação da Inferência Probabilística Parcial: O trabalho fornece a base matemática rigorosa para raciocinar sobre inferência bayesiana em cenários onde a evidência pode ser incompatível com o prior (falha de atualização), algo que as categorias de Markov totais não suportam.
• Ferramenta para Semântica de Programação: A estrutura de pré-ordem permite o raciocínio inequacional (desigualdades) em linguagens de programação probabilística, essencial para analisar otimizações, correção e comportamento de programas que envolvem probabilidades parciais.
• Generalização Sintética: Ao axiomatizar desigualdades como Cauchy-Schwarz e o aumento de validade, os autores mostram que esses fenômenos não são apenas propriedades de medidas reais, mas consequências estruturais da teoria categórica de processos probabilísticos parciais.
• Conexão com Lógica e Relações: A ligação com categorias de restrições e bicategorias de relações conecta a teoria da probabilidade com a lógica de predicados e a teoria de relações, sugerindo novas direções para o desenvolvimento de lógicas probabilísticas.

Em resumo, o artigo estabelece que a parcialidade na probabilidade não é apenas uma limitação, mas uma estrutura rica que, quando formalizada através de pré-ordens e condicionais mínimos, revela propriedades fundamentais sobre a natureza da inferência e da atualização de crenças.