Deriving Complete Constraints in Hidden Variable Models

Título: Derivação de Restrições Completas em Modelos de Variáveis Ocultas

Autores: Michael C. Sachs, Erin E. Gabriel, Robin J. Evans, Arvid Sjölander.

1. O Problema

Em modelos gráficos com variáveis ocultas (não observadas), a estrutura causal impõe restrições sobre a distribuição conjunta das variáveis observáveis. Tradicionalmente, a inferência causal foca em:

• Independências condicionais observáveis: Relações simples de independência (ex: $X \perp Y | Z$).
• Restrições de igualdade: Como as restrições "Verma" ou de Markov aninhado.

No entanto, existem restrições observáveis mais complexas que não são apenas independências condicionais simples. Estas incluem:

• Restrições de desigualdade: Como as desigualdades instrumentais (Pearl, 1995).
• Restrições de igualdade complexas: Que vão além do Markov aninhado padrão.

O problema central é que, em muitos cenários, é difícil determinar o conjunto completo dessas restrições observáveis. Métodos existentes, como a eliminação de variáveis algébrica (Fourier-Motzkin) ou programação linear intensiva, tornam-se computacionalmente inviáveis para espaços de estado moderados ou não garantem a completude (ou seja, podem falhar em encontrar todas as restrições possíveis). Sem o conjunto completo, é impossível falsificar completamente um modelo estrutural ou otimizar a eficiência estatística da estimação.

2. Metodologia

Os autores propõem um método sistemático para derivar o conjunto completo de restrições observáveis para uma classe específica de modelos. A abordagem baseia-se na transformação do modelo de equações estruturais não paramétricas (NPSEM) em um espaço de variáveis de resposta (response functions).

Passos Principais do Algoritmo:

1. Pré-processamento e Definição de Distritos:

   • O modelo é representado por um DAG (Gráfico Acíclico Direcionado) com variáveis observadas ($W$) e ocultas ($U$).
   • O gráfico é transformado para satisfazer condições de exogeneidade e estrutura de filhos.
   • O gráfico é particionado em distritos (ou componentes-c), que são conjuntos de variáveis conectadas por caminhos de confusão (variáveis ocultas compartilhadas).

2. Restrição de Grau-c (c-degree):

   • O método foca inicialmente em modelos onde cada distrito tem um c-degree de 1. Isso significa que cada distrito é afetado por no máximo uma variável oculta comum (ou é um nó singleton).
   • Para distritos com c-degree 1, o modelo pode ser transformado em um gráfico misto usando variáveis de resposta ($R_{W_i}$), que são variáveis categóricas latentes que determinam a função de resposta de cada variável observada aos seus pais.

3. Restrições Funcionais Lineares:

   • As probabilidades observáveis são expressas como funções lineares das probabilidades das variáveis de resposta.
   • Isso gera um sistema de equações lineares na forma $p = Br$, onde $p$ é o vetor de probabilidades observáveis e $r$ é o vetor de probabilidades das variáveis de resposta.

4. Conversão Vértice-Halfspace (V-to-H):

   • O sistema $p = Br$ define um poliedro convexo no espaço das variáveis latentes.
   • Utilizando algoritmos de geometria computacional (como o método de dupla descrição implementado em bibliotecas como cddlib), os autores convertem a representação de vértices (V-representation) do poliedro para uma representação de semi-espaços (H-representation).
   • O resultado é um conjunto de desigualdades e igualdades lineares ($Hp \leq b$ e $He = b_e$) que definem as restrições apenas em termos das probabilidades observáveis.

5. Identificação de Restrições Não Triviais:

   • O algoritmo gera muitas restrições, algumas das quais são triviais (implicadas apenas pelos axiomas de probabilidade, como somar 1).
   • Os autores propõem um método para filtrar as restrições não triviais testando se as restrições derivadas são violadas pelos pontos extremos do simplex de probabilidade não restrito.

3. Contribuições Chave

• Generalização do Método de Bonet (2001): Estendem a técnica de programação linear, originalmente aplicada apenas ao modelo de variável instrumental binária, para uma classe muito mais ampla de modelos com variáveis categóricas e múltiplos distritos.
• Completude Garantida: Provam que, para a classe de modelos "lineares" (onde o c-degree de cada distrito é 1), o método derivado fornece o conjunto completo de restrições observáveis (tanto igualdades quanto desigualdades).
• Novas Restrições: Demonstram a existência de restrições de igualdade não triviais em modelos que não são capturadas apenas pelo Markov aninhado, além de novas desigualdades.
• Extensão para c-degree > 1: Embora a completude não seja garantida para distritos com c-degree > 1 (múltiplas variáveis ocultas no mesmo distrito), os autores propõem uma heurística de "fusão" de variáveis latentes para obter um subconjunto de restrições válidas (necessárias, mas não suficientes).
• Equivalência Observacional: Apresentam proposições (baseadas em trabalhos anteriores de Evans, Henson, Lal e Pusey) para converter DAGs com c-degree > 1 em DAGs observacionalmente equivalentes com c-degree 1, permitindo a aplicação do método completo em mais cenários.

4. Resultados e Exemplos

Os autores ilustram o método em vários cenários:

• Variáveis Instrumentais Sequenciais: Derivam conjuntos de desigualdades instrumentais para múltiplos estágios.
• Modelos Equivalentes de Markov Aninhado: Mostram dois grafos que são equivalentes em termos de Markov aninhado (mesmas igualdades), mas que possuem desigualdades distintas. O método consegue distinguir entre eles, provando que o Markov aninhado não é suficiente para caracterizar completamente a distribuição.
• Gráficos de Bell Tripartite: Aplicam o método ao cenário de Bell em física quântica. O algoritmo derivou automaticamente um conjunto completo de 53.894 restrições (incluindo 53.856 desigualdades e 32.866 não triviais) em menos de 0,5 horas de CPU, concordando com resultados teóricos anteriores mas de forma automatizada e completa.
• Cenário do Triângulo: Discutem as limitações do método em grafos com c-degree alto (como o triângulo clássico), onde a fusão de variáveis latentes não gera o conjunto completo de restrições, mas ainda fornece restrições válidas.

5. Significado e Impacto

• Falsificação de Modelos: O método fornece uma ferramenta poderosa para testar a validade de modelos causais com variáveis ocultas. Se os dados observados violarem qualquer uma das restrições derivadas, o modelo estrutural pode ser rejeitado.
• Inferência Causal e Descoberta: Oferece uma estratificação mais fina das classes de equivalência causal do que apenas testes de independência. Isso pode melhorar algoritmos de descoberta causal.
• Inferência Estatística Restrita: As restrições podem ser usadas para melhorar a eficiência da estimação de parâmetros (inferência parcial) ao restringir o espaço de parâmetros viáveis.
• Ferramenta Computacional: Os autores disponibilizam o software no GitHub (meraconstraints), tornando a aplicação prática deste método teórico acessível para pesquisadores.

Em resumo, o artigo estabelece uma ponte robusta entre a teoria dos modelos gráficos causais e a geometria computacional, fornecendo um algoritmo sistemático para extrair todas as implicações observáveis (desigualdades e igualdades) de uma ampla classe de modelos com variáveis latentes.