Compositionality in algorithms for smoothing

Título: Composicionalidade em algoritmos para suavização (Compositionality in algorithms for smoothing)

Autores: Moritz Schauer, Frank van der Meulen e Andi Q. Wang.
Publicação: Compositionality, Vol. 8, Issue 3 (2026).

---

1. Problema

O artigo aborda o problema de inferência bayesiana em sistemas parcialmente observados, especificamente o problema de suavização (smoothing).

• Contexto: Sistemas modelados como processos estocásticos em árvores direcionadas (generalizando Modelos Ocultos de Markov - HMMs). O objetivo é inferir a distribuição do processo em todos os vértices internos (não observados), condicionada às observações nos vértices folha.
• Desafio: Algoritmos tradicionais de suavização, como a recursão forward-backward normalizada ou a decomposição forward, muitas vezes só podem ser calculados em forma fechada em configurações muito específicas (ex: estados finitos ou sistemas lineares gaussianos com filtro de Kalman).
• Solução Existente: O algoritmo Backward Filtering Forward Guiding (BFFG), proposto por Mider et al. [2021], oferece uma estrutura geral para lidar com esse problema, permitindo o uso de dinâmicas simplificadas na etapa de filtragem reversa para guiar a amostragem na etapa forward. No entanto, a estrutura composicional profunda deste algoritmo e sua relação com a teoria das categorias não haviam sido formalizadas.

2. Metodologia

Os autores utilizam ferramentas da Teoria das Categorias para analisar a estrutura do algoritmo BFFG.

• Abordagem Categorical: Em vez de focar em detalhes de implementação, o trabalho abstrai o algoritmo para estudar sua estrutura composicional.
• Kernels de Markov: Os processos estocásticos são modelados como morfismos na categoria Stoch (cujos objetos são espaços mensuráveis e morfismos são kernels de Markov).
• Ópticas (Optics): Para modelar o fluxo de dados bidirecional (passo forward e passo backward) inerente ao BFFG, os autores utilizam o conceito de Ópticas (introduzido por Riley [2018]). Uma óptica consiste em um par de mapas: um primeiro mapa (forward) e um segundo mapa (backward), conectados por um estado interno.
• Construção do Functor: O trabalho define formalmente como o algoritmo BFFG mapeia kernels de Markov para ópticas, demonstrando que essa transformação preserva a estrutura de composição.

3. Contribuições Principais

A. Formalização do BFFG como Óptica

Os autores definem os mapas que compõem o BFFG no contexto de ópticas:

1. Primeiro Mapa (Backward Filtering): Mapeia funções de orientação (guiding functions) através da pullback do kernel aproximado ($\tilde{\kappa}$).
2. Segundo Mapa (Forward Guiding): Mapeia medidas através da transformada-h (h-transform) utilizando o kernel real ($\kappa$) e as funções de orientação obtidas no passo backward.
   Esses dois mapas formam uma óptica $O(\kappa, \tilde{\kappa})$ na categoria Optic(Set).

B. Teorema 8: Functorialidade (Composição Sequencial)

O resultado central é que o algoritmo BFFG define um functor contravariante da categoria de pares de kernels ($Stoch^2$) para a categoria de ópticas ($Optic(Set)$).

• Significado: A composição de kernels de Markov (sequência de transições) corresponde exatamente à composição sequencial das ópticas resultantes.
• Implicação: Isso permite decompor um algoritmo de suavização complexo em partes menores (vértices/arestas da árvore), calcular as ópticas para cada parte e compostá-las, garantindo que o resultado global seja equivalente ao cálculo direto. Isso é crucial para modularidade e implementação eficiente.

C. Teorema 11: Lax Monoidalidade (Composição Paralela)

O artigo investiga se o algoritmo preserva a composição paralela (produto tensorial de kernels).

• Resultado: O algoritmo BFFS (Backward Filtering Forward Sampling, onde o kernel de guia é idêntico ao kernel real, $\tilde{\kappa} = \kappa$) é um functor lax monoidal.
• Limitação do BFFG Geral: O BFFG geral (com $\tilde{\kappa} \neq \kappa$) não é lax monoidal estritamente. A falha ocorre devido à necessidade de rastrear pesos globais (likelihood ratios) que dependem de interações entre ramos independentes quando condicionados a observações conjuntas (fenômeno de confusão).
• Relevância Prática: A falha na monoidalidade estrita não afeta a aplicação prática em métodos de Monte Carlo (como Sequential Monte Carlo), pois os fatores de normalização constantes cancelam-se no estimador final.

4. Resultados e Exemplos

Os teoremas permitem manipulações estruturais no grafo do processo estocástico sem alterar a inferência:

1. Colapso de Arestas (Missing Observation): Se uma observação está faltando em um nó intermediário, as arestas adjacentes podem ser fundidas em uma única aresta com um kernel composto, e o algoritmo BFFG produzirá o mesmo resultado (Teorema 8).
2. Divisão de Arestas (Intractable Composition): Se um kernel de transição é intratável, mas pode ser decomposto em uma sequência de kernels tratáveis, pode-se introduzir um vértice latente intermediário. O algoritmo pode então ser executado em duas etapas compostas, facilitando o cálculo (Exemplo 20).
3. Discretização de SDEs: Para Equações Diferenciais Estocásticas (SDEs) sem densidade de transição conhecida, pode-se introduzir vértices intermediários para aplicar uma discretização de Euler, dividindo o problema em passos menores tratáveis (Exemplo 21).

5. Significado e Impacto

• Estrutura de Alta Ordem: O trabalho revela que existe um núcleo de preservação de estrutura de alta ordem dentro de algoritmos de suavização complexos.
• Modularidade e Implementação: Ao fornecer uma perspectiva categórica, os autores permitem que desenvolvedores quebrem algoritmos complexos em blocos constituintes (mapas forward/backward por aresta), facilitando a implementação, a depuração e a compreensão.
• Ponte entre Áreas: O artigo conecta a estatística computacional (inferência em modelos ocultos) com a teoria das categorias moderna (ópticas e probabilidades categóricas), oferecendo uma linguagem unificada para entender a bidirecionalidade em algoritmos de aprendizado de máquina e inferência.
• Generalização: Os resultados generalizam propriedades conhecidas de algoritmos específicos (como o FFBS e o Filtro de Kalman) para uma classe muito mais ampla de modelos de suavização.

Em resumo, o paper demonstra que o algoritmo BFFG não é apenas uma heurística computacional, mas uma estrutura matemática robusta que preserva a composição de processos estocásticos, permitindo a construção de algoritmos de inferência escaláveis e modulares através da teoria das ópticas.