Resumo Técnico: Descoberta de Mantos de Markov de Ordem Superior via uma Relaxação de Ordem $k$ da Suposição de Fidelidade

Definição do Problema

O problema de descoberta do manto de Markov (MB - Markov Blanket) envolve inferir o MB gráfico de uma variável alvo $Y$ a partir de um conjunto de dados amostrados de uma distribuição conjunta $P$. Esta tarefa é fundamental para a aprendizagem de estrutura em redes Bayesianas (BNs) e campos aleatórios de Markov (MRFs), descoberta causal e seleção de características.

A maioria dos métodos existentes de descoberta de MB baseados em restrições baseia-se na suposição de fidelidade (faithfulness assumption): a premissa de que qualquer independência condicional (CI) na distribuição $P$ implica uma correspondente separação na estrutura gráfica $G$ (e vice-versa). No entanto, esta suposição é frequentemente violada de duas formas:

1. Violações Reais: Certas relações funcionais, como o XOR ruidoso ou funções de paridade de ordem superior, criam dependências que são "infiéis" à estrutura do grafo. Por exemplo, em uma função de paridade ruidosa envolvendo $k+2$ variáveis, podem existir dependências de par ou de ordem inferior, apesar de as variáveis estarem conectadas no grafo.
2. Violações Empíricas: Mesmo quando a distribuição real é fiel, tamanhos de amostra finitos podem levar a erros estatísticos onde as CIs empíricas não correspondem à distribuição real. Em casos extremos com amostras pequenas, os algoritmos podem falhar em recuperar o verdadeiro MB ou descobrir dependências espúrias.

Embora relaxações anteriores, como a fidelidade de 2-adjacência, abordem relações do tipo XOR (envolvendo 3 variáveis), elas falham em capturar relações de paridade de ordem superior envolvendo mais de 3 variáveis.

Metodologia

A Relaxação de Fidelidade de Ordem $k$

Os autores propõem uma generalização da suposição de fidelidade chamada fidelidade de ordem $k$. Esta relaxação é projetada para capturar dependências do tipo paridade entre $k+2$ variáveis.

• Dependência de Ordem $k$: Duas variáveis $Y$ e $X$ são definidas como dependentes de ordem $|Z|$ dado um conjunto $Z$ se elas permanecerem condicionalmente dependentes independentemente de qualquer subconjunto de um conjunto separador $S$ ser adicionado ao conjunto de condicionamento, desde que $|Z| = k$.
• Suposição: Um grafo $G$ é $k$-ordem fiel a $P$ se, para quaisquer variáveis $Y, X$ e qualquer conjunto $S$, se $Y$ e $X$ são condicionalmente independentes dado $Z \cup S'$ para algum $Z$ de tamanho $\le k$ e algum $S' \subseteq S$, então eles são graficamente separados por $S$.
• Contrapositiva: Se $Y$ e $X$ não são separados por $S$ no grafo, deve existir um conjunto $Z$ de tamanho $\le k$ tal que $Y$ e $X$ estejam associados (dependentes) sobre $Z$ em relação a $S$.

Para tornar o algoritmo computacionalmente viável, os autores introduzem uma suposição de separador limitado por $l$ ($l$-bounded separator assumption). Esta assume que, se $Y$ e $X$ são condicionalmente independentes dado um grande conjunto, existe um subconjunto desse conjunto com tamanho $\le l$ que também os torna independentes. Isso limita o espaço de busca para conjuntos de condicionamento durante os testes de CI.

O Algoritmo kOMB

O artigo apresenta o kOMB (manto de Markov de ordem $k$), um algoritmo de prova de conceito que modifica o algoritmo Grow and Shrink (GS) para operar sob estas novas suposições.

1. Fase de Crescimento (Grow Phase): Em vez de testar variáveis individuais, o kOMB busca iterativamente subconjuntos de variáveis (até o tamanho $k$) que, quando condicionadas com o candidato atual ao MB, revelam dependências entre $Y$ e outras variáveis. Ele utiliza uma busca recursiva (find_inter_dep) para identificar conjuntos "inter-associados".
2. Fase de Encolhimento (Shrink Phase): O algoritmo remove variáveis do candidato ao MB se elas puderem ser separadas de $Y$ por um subconjunto das variáveis restantes do MB (limitado por $l$).
3. Garantias Teóricas: Os autores provam que, sob a Propriedade de Markov Global, fidelidade de ordem $k$ e a suposição de separador limitado por $l$, o kOMB recupera corretamente o MB gráfico de uma variável.

Principais Contribuições

1. Estrutura Teórica: A definição de fidelidade de ordem $k$, que generaliza relaxações anteriores (como a fidelidade de 2-adjacência) para lidar com relações de paridade de ordem superior envolvendo $k+2$ variáveis.
2. Implementação Algorítmica: O desenvolvimento do kOMB, um algoritmo baseado em restrições que aproveita a fidelidade de ordem $k$ para descobrir MBs na presença de dependências de ordem superior.
3. Validação Empírica: Demonstração de que o kOMB pode recuperar MBs em cenários onde métodos tradicionais falham devido tanto à infidelidade real (ex: funções de paridade) quanto à infidelidade empírica (efeitos de amostra finita).

Resultados Experimentais

Dados Sintéticos

Os autores testaram o kOMB em redes Bayesianas sintéticas com 4 variáveis, onde o alvo $Y$ foi gerado via cinco diferentes funções Booleanas (incluindo XOR, paridade e "exatamente-1").

• Desempenho: O kOMB superou consistentemente o algoritmo Grow and Shrink (GS) e outros métodos existentes (IAMB, HITON, etc.).
• Recuperação de Alta Ordem: Para a função de paridade (uma extensão de 3 variáveis do XOR), os métodos padrão falharam em recuperar o MB. O kOMB com $k=2$ alcançou recuperação perfeita (F1 score de 1.0), confirmando sua capacidade de detectar dependências que exigem 3 variáveis de condicionamento.
• Sensibilidade ao Tamanho da Amostra: Em regimes de baixa amostragem, o kOMB com valores de $k$ mais altos demonstrou maior robustez contra violações de fidelidade empírica em comparação com métodos de ordem inferior.

Conjuntos de Dados de Referência (Benchmark)

Experimentos foram conduzidos em quatro conjuntos de dados padrão: Alarm1, Barley, Insurance e Mildew.

• Desempenho: O kOMB geralmente alcançou pontuações F1 competitivas ou superiores em relação a métodos de estado da arte como BAMB, HITON e MMMB.
• Sensibilidade de Ordem: O benefício de valores de $k$ mais altos foi dependente do conjunto de dados. Em redes de menor cardinalidade (Alarm1, Insurance), $k=2$ melhorou o desempenho. Em redes de alta cardinalidade (Barley, Mildew), $k=1$ frequentemente performou melhor, pois conjuntos de condicionamento maiores levaram a testes de CI com baixo poder estatístico dado o tamanho da amostra (5000 amostras).
• Tempo de Execução: Como esperado, o tempo de execução aumentou significamente com $k$ e a cardinalidade da rede. Para redes de alta cardinalidade, configurações de $k=2$ foram substancialmente mais lentas do que $k=1$ ou métodos de linha de base.

Significância e Alegações

O artigo posiciona o kOMB como uma prova de conceito demonstrando que explorar dependências de ordem superior pode melhorar a descoberta de MB na presença de violações de fidelidade.

• Alegações Modestas: Os autores afirmam explicitamente que o kOMB não é otimizado para eficiência; seu objetivo principal é validar a utilidade teórica da fidelidade de ordem $k$.
• Implicações Práticas: Os resultados sugerem que, para problemas envolvendo relações do tipo paridade ou onde os tamanhos de amostra são limitados, relaxar a suposição de fidelidade para ordens mais altas é benéfico.
• Direções Futuras: O artigo identifica a necessidade de algoritmos aproximados para reduzir o custo computacional de pior caso, métodos fundamentados para selecionar $k$ e $l$ sem conhecimento especializado, e a integração de testes de independência condicional mais recentes além do teste G e SCI usados nos experimentos.

O trabalho estabelece que, embora as suposições de fidelidade tradicionais sejam frequentemente suficientes, relações estruturais específicas (como a paridade) e as realidades de amostras finitas necessitam de uma abordagem mais flexível e de ordem superior para a aprendizagem de modelos gráficos.