Inferência Lifted (Inferência Probabilística Lifted)

Visão geral

Inferência elevada (lifted inference) (também chamada de inferência probabilística elevada (lifted probabilistic inference)) é uma família de algoritmos para responder a consultas probabilísticas em modelos probabilísticos relacionais / de primeira ordem (relational / first-order probabilistic models) sem instanciá-los (grounding) completamente em um modelo gráfico proposicional (propositional graphical model).

Em um modelo instanciado, você cria uma variável aleatória (random variable) por entidade (e por tupla de relação) no domínio. Para modelos relacionais, isso pode explodir para milhões ou bilhões de variáveis e fatores (factors). A inferência elevada evita isso explorando simetria (symmetry) e permutabilidade (exchangeability): muitas variáveis aleatórias instanciadas são indistinguíveis dada a estrutura do modelo (e, frequentemente, dada a evidência), então elas podem ser tratadas como um grupo e processadas com contagem (counting) em vez de computação por instância.

A inferência elevada é muito usada em formalismos de Aprendizado Relacional Estatístico (Statistical Relational Learning, SRL), como Redes de Lógica de Markov (Markov Logic Networks), modelos relacionais probabilísticos (probabilistic relational models) e representações lógicas probabilísticas de primeira ordem (first-order probabilistic logic representations). Conceitualmente, ela é para SRL o que algoritmos clássicos de inferência — eliminação de variáveis (variable elimination) e propagação de crença (belief propagation) — são para Redes Bayesianas (Bayesian Networks) e Campos Aleatórios de Markov (Markov Random Fields / Markov Networks) proposicionais, mas “elevada” ao nível de primeira ordem/de template.

Instanciação vs. elevação: por que isso importa

Modelos relacionais descrevem templates que se repetem entre entidades:

• Predicados unários (unary predicates) como Smokes(Person)
• Relações binárias (binary relations) como Friends(Person, Person)

Se você tem n pessoas:

• Smokes(Person) produz n átomos instanciados (ground atoms).
• Friends(Person, Person) produz até n^2 átomos instanciados.
• Uma regra como Friends(X,Y) -> (Smokes(X) <-> Smokes(Y)) pode gerar fatores instanciados O(n^2).

A inferência padrão (por exemplo, eliminação de variáveis, propagação de crença) rodaria sobre esse enorme grafo instanciado. A inferência elevada busca manter a computação mais próxima do tamanho do template, idealmente polinomial em n (ou até independente de n para algumas consultas), manipulando grupos como:

“todas as pessoas não observadas são simétricas, então podemos raciocinar sobre quantas delas fumam, em vez de quais fumam.”

Isso está intimamente relacionado à ideia de comprimir um grafo de fatores (factor graph) mesclando nós simétricos; veja Grafos de Fatores (Factor Graphs) e Propagação de Crença (Soma-Produto / Passagem de Mensagens) (Belief Propagation (Sum-Product / Message Passing)) para as versões proposicionais.

Modelos probabilísticos relacionais/de primeira ordem em poucas palavras

Diferentes formalismos de SRL usam sintaxes diferentes, mas compartilham uma estrutura comum:

• Variáveis lógicas (logical variables, logvars) variam sobre objetos do domínio (por exemplo, X varia sobre todas as pessoas).
• Predicados (predicates) definem famílias de variáveis aleatórias (por exemplo, Smokes(X)).
• Fórmulas / fatores (formulas / factors) especificam como predicados interagem, tipicamente repetidas para todas as instanciações de logvars.

Uma abstração genérica útil é a variável aleatória parametrizada (parameterized random variable, PRV), como:

• Smokes(X) onde X ∈ People

e fatores parametrizados (parameterized factors) (frequentemente chamados de parfatores (parfactors)) que conectam PRVs, como:

• Um template de fator conectando Smokes(X) e Cancer(X) para todo X.

A instanciação substitui cada PRV por uma variável por entidade e cada parfator por um fator por instanciação. A inferência elevada tenta operar diretamente sobre PRVs/parfatores.

A ideia central: simetria, permutabilidade e “contar em vez de enumerar”

Indistinguibilidade e permutabilidade

Duas variáveis aleatórias instanciadas são (grosso modo) permutáveis se trocá-las não altera a distribuição conjunta, dado o modelo e a evidência. Em modelos relacionais, a permutabilidade frequentemente surge porque:

• o mesmo template se aplica a todas as entidades, e
• entidades não têm identificadores únicos no modelo além da evidência fornecida.

Se nenhuma evidência distingue indivíduos, então Smokes(alice), Smokes(bob), … podem ser simétricas. Mesmo com evidência, grandes subconjuntos podem permanecer simétricos (por exemplo, “todas as pessoas exceto Alice”).

Partições em órbitas (intuição)

A inferência elevada pode ser vista como a manutenção de uma partição de variáveis em classes de equivalência (equivalence classes) (“órbitas”) tal que todas as variáveis em uma classe se comportam de forma idêntica. Os algoritmos então calculam:

• uma marginal por classe em vez de por variável e/ou
• probabilidades como função de contagens (quantas variáveis em uma classe assumem cada valor).

Fórmulas de contagem: um mecanismo-chave

Um truque recorrente é substituir muitas variáveis binárias por uma única variável de contagem.

Exemplo: suponha que Smokes(X) seja binária para cada pessoa X e (por enquanto) assuma que o modelo trata pessoas simetricamente. Em vez de raciocinar sobre 2^n atribuições para Smokes(1..n), você pode raciocinar sobre o número de fumantes:

• C = #{ X : Smokes(X)=true } que varia de 0..n

Muitos fatores relacionais dependem apenas dessa contagem (ou de um pequeno número de contagens desse tipo), transformando a enumeração exponencial em n em programação dinâmica (dynamic programming) polinomial em n.

Um exemplo concreto: influência simétrica em pares

Considere um modelo relacional simplificado:

• Para cada pessoa X, Smokes(X) ∈ {0,1}
• Para cada par (X,Y) com X ≠ Y, há o mesmo fator de influência incentivando comportamento de fumar semelhante.

No nível instanciado, isso é um MRF denso par-a-par com n nós e O(n^2) arestas. De forma ingênua, inferência exata é intratável para grandes n.

No entanto, se nenhuma evidência distingue indivíduos, então a distribuição é totalmente simétrica: ela depende apenas de quantas pessoas fumam, não de quais fumam. A probabilidade de uma atribuição muitas vezes pode ser escrita em termos da contagem m de fumantes:

• um termo que depende de m (preferências unárias), e
• um termo que depende de quantos pares concordantes/discordantes existem, o que é uma função de m e n.

Isso reduz a inferência sobre Smokes(X) a computações sobre m = 0..n, isto é, O(n) estados em vez de 2^n. Algoritmos de inferência elevada automatizam esse tipo de redução mesmo em estruturas relacionais mais complexas.

Quando você adiciona evidência como Smokes(Alice)=true, a simetria total se rompe, mas você ainda obtém grandes grupos simétricos:

• {Alice} e {todos os demais}

Agora a contagem se aplica ao grupo “todos os demais”.

Famílias de algoritmos de inferência elevada

A inferência elevada não é um algoritmo, mas uma família. As principais famílias que você verá na prática são:

1. Eliminação de Variáveis Elevada (Lifted Variable Elimination, LVE) e métodos relacionados de eliminação elevada exata
2. Propagação de Crença Elevada (Lifted Belief Propagation, Lifted BP) (passagem de mensagens comprimida, frequentemente aproximada)
3. Compilação de conhecimento de primeira ordem (first-order knowledge compilation) / contagem ponderada de modelos de primeira ordem (weighted first-order model counting, WFOMC)

Cada uma corresponde a uma abordagem proposicional bem conhecida, mas realizada sobre grupos em vez de variáveis instanciadas.

1) Eliminação de Variáveis Elevada (LVE)

Base proposicional: Eliminação de Variáveis (Variable Elimination, VE) em modelos gráficos.
Ideia elevada: eliminar conjuntos de variáveis instanciadas simétricas de uma só vez.

Em que a LVE opera

A LVE trabalha com estruturas parametrizadas:

• PRVs como Smokes(X)
• parfatores como φ(Smokes(X), Cancer(X))
• restrições como X ≠ Y (importante em modelos relacionais)

Uma implementação típica de LVE mantém um grafo de parfatores (parfactor graph), análogo a um grafo de fatores, mas no nível de template.

Operações elevadas-chave (alto nível)

• Multiplicação elevada: multiplica parfatores sem instanciar, quando eles se alinham de forma a preservar simetria.
• Somatório elevado (eliminação): soma uma PRV explorando que muitas instanciações contribuem de modo idêntico.
• Conversão para contagem: substitui conjuntos como {Smokes(x) : x in Group} por uma variável de contagem.
• Divisão / estilhaçamento (splitting / shattering): quando evidência ou restrições diferenciam indivíduos, o algoritmo divide grupos em subgrupos simétricos menores.

Um esboço simplificado:

LVE(Factors, Query, Evidence):
  Incorporate(Evidence)                      # may force splitting/shattering
  while exists non-query PRV to eliminate:
      choose PRV A
      if A is count-convertible:
          replace A's ground set by counting representation
      combine all parfactors containing A
      eliminate A in a lifted way (summing with multiplicities)
      add resulting parfactor back
  return normalize(result over Query)

Exemplo prático: “câncer por fumar” com parâmetros compartilhados

Suponha que um template no estilo de uma Rede de Lógica de Markov diga, para todo X:

• Smokes(X) -> Cancer(X) com peso w

e um prior sobre fumar. Se você consulta P(Cancer(Bob)) com nenhuma evidência, então:

• toda pessoa é simétrica,
• a marginal de Cancer(X) é a mesma para todo X,
• a LVE pode calcular a marginal uma vez e reutilizá-la.

Se você adicionar a evidência Smokes(Alice)=true, a LVE dividirá as pessoas em:

• X = Alice
• X ≠ Alice

e ainda assim eliminará o grupo dos “outros” em bloco usando contagens.

Pontos fortes e limitações

• Pontos fortes: exata quando se mantém suficientemente elevada; pode gerar economias dramáticas; fortemente ligada à intuição clássica da VE.
• Limitações: pode ser forçada a instanciar parcial ou totalmente quando a evidência destrói simetrias; gerenciar divisão/estilhaçamento de forma eficiente não é trivial. O desempenho depende mais da “largura elevada (lifted width)” do que da largura de árvore (treewidth) instanciada.

Variantes notáveis incluem algoritmos do tipo C-FOVE / estilo FOVE e refinamentos de “inversão em grupo” (frequentemente descritos como melhorias em quando e como a contagem é aplicada).

2) Propagação de Crença Elevada (Lifted BP)

Base proposicional: propagação de crença / soma-produto em grafos de fatores; veja Propagação de Crença (Soma-Produto / Passagem de Mensagens).
Ideia elevada: executar passagem de mensagens em um grafo comprimido onde nós simétricos compartilham mensagens.

Como a elevação funciona para passagem de mensagens

Se muitos nós de variáveis e nós de fatores forem estruturalmente idênticos (e virem evidência idêntica), eles enviarão mensagens idênticas na BP. A BP elevada identifica essas classes de equivalência e executa BP na estrutura quociente/comprimida.

Abordagens comuns incluem:

• Propagação de cores / refinamento (color passing / refinement): rotula iterativamente nós pelo seu entorno e evidência; nós com o mesmo rótulo são tratados como equivalentes.
• BP com contagem (counting BP): as mensagens incorporam multiplicidades (por exemplo, “este fator se conecta a 10.000 variáveis idênticas”).

Exemplo: influência coletiva em um template de rede social

Em uma Rede de Lógica de Markov, você pode ter templates como:

• Friends(X,Y) ∧ Smokes(X) -> Smokes(Y) (influência)
• um prior sobre Smokes(X)

Se a evidência observada apenas informa “Alice fuma” e a estrutura de rede é em grande parte não observada ou regular, então muitos indivíduos não-Alice podem ser indistinguíveis. A BP elevada calculará um conjunto de mensagens para a classe “não-Alice genérico” em vez de por pessoa.

Pontos fortes e limitações

• Pontos fortes: escalável; funciona naturalmente com grandes grafos com ciclos (loopy graphs) onde inferência exata é impossível de qualquer forma; frequentemente usada como método de inferência elevada aproximado.
• Limitações: quando o grafo instanciado tem muitos entornos únicos (por exemplo, um grafo social totalmente observado e irregular), simetrias desaparecem e a elevação traz menos benefício. Além disso, a própria BP pode ser aproximada em grafos com ciclos.

3) Compilação de conhecimento de primeira ordem (WFOMC e circuitos compilados)

Base proposicional: compilação de conhecimento e contagem ponderada de modelos para inferência probabilística.
Ideia elevada: compilar estrutura de primeira ordem uma vez e, então, responder muitas consultas por avaliação eficiente, usando decomposição de primeira ordem (first-order decomposition) e recursão de domínio (domain recursion) em vez de instanciação.

Um formalismo central é a Contagem Ponderada de Modelos de Primeira Ordem (Weighted First-Order Model Counting, WFOMC):

• Converter um modelo probabilístico relacional (frequentemente um subconjunto/tradução de uma Rede de Lógica de Markov ou de uma lógica probabilística) em uma teoria lógica de primeira ordem (first-order logical theory) com pesos em predicados/literais.
• Calcular uma contagem ponderada de modelos que satisfazem a teoria.
• Derivar probabilidades de consultas como razões de contagens ponderadas.

Por que a compilação pode ser “elevada”

Métodos de compilação exploram simetrias ao:

• decompor a teoria em subteorias independentes sobre subdomínios idênticos,
• aplicar argumentos de contagem para indivíduos indistinguíveis,
• usar análise de casos elevada que ramifica por contagens (por exemplo, “quantos elementos satisfazem o predicado P?”) em vez de por cada átomo instanciado.

O resultado é frequentemente uma representação em forma de circuito (por exemplo, formas do tipo d-DNNF no mundo proposicional), mas com estrutura de primeira ordem/elevada preservada pelo maior tempo possível.

Pontos fortes e limitações

• Pontos fortes: resposta a consultas muito rápida após a compilação; bom quando você tem muitas consultas no mesmo modelo/evidência; fortes conexões teóricas com fragmentos tratáveis (por exemplo, certas classes de lógica de primeira ordem).
• Limitações: a compilação pode ser cara; evidência e estrutura relacional complexa ainda podem forçar explosões de tamanho.

Inferência elevada em Redes de Lógica de Markov (MLNs) e SRL

Redes de Lógica de Markov combinam lógica de primeira ordem com pesos log-lineares. Instanciar uma Rede de Lógica de Markov produz um (tipicamente enorme) Campo Aleatório de Markov: uma variável por átomo instanciado, um fator por instanciação de fórmula instanciada.

A inferência elevada se aplica a Redes de Lógica de Markov de múltiplas formas:

Vendo Redes de Lógica de Markov como modelos de parfatores (para LVE)

Uma fórmula de Rede de Lógica de Markov como:

w: Friends(X,Y) ∧ Smokes(X) -> Smokes(Y)

induz, para cada instanciação (x,y), um fator que depende de Friends(x,y), Smokes(x) e Smokes(y). A eliminação de variáveis elevada agrupa essas instanciações quando:

• o mesmo template de fórmula se aplica, e
• restrições/evidência não distinguem pares específicos.

Se você observa apenas alguns fatos (evidência esparsa), grandes conjuntos de indivíduos não mencionados frequentemente permanecem simétricos, tornando a LVE eficaz.

Grafos de fatores comprimidos (para BP elevada)

Redes de Lógica de Markov frequentemente produzem grandes grafos de fatores com ciclos. A BP elevada pode:

• agrupar átomos instanciados idênticos (por exemplo, todos os Smokes(x) para pessoas não observadas),
• agrupar fatores instanciados idênticos (todas as instanciações da mesma fórmula sob condições simétricas),
• executar inferência aproximada com mensagens que incorporam multiplicidades.

Isso pode ser muito mais rápido do que a BP no grafo de fatores totalmente instanciado.

Redes de Lógica de Markov via contagem ponderada de modelos (compilação de conhecimento)

Certos fragmentos de Redes de Lógica de Markov podem ser traduzidos para teorias lógicas ponderadas adequadas para inferência no estilo WFOMC. Isso é especialmente atraente quando:

• você precisa de funções de partição ou muitas marginais,
• sua teoria está em um fragmento elevado tratável, ou
• o domínio é grande, mas altamente simétrico.

Na prática, sistemas de Rede de Lógica de Markov frequentemente combinam múltiplas técnicas (às vezes incluindo instanciação parcial mais inferência aproximada) dependendo da estrutura do modelo e dos padrões de evidência.

Evidência: o principal destruidor de simetria (e como métodos elevados lidam com isso)

A inferência elevada funciona melhor quando muitos indivíduos são indistinguíveis sob a evidência. A evidência frequentemente quebra a simetria:

• Se você observa um atributo único para cada pessoa, então cada pessoa se torna distinguível.
• Se a estrutura relacional (por exemplo, arestas de um grafo) é totalmente observada e irregular, os entornos diferem.

Por isso, sistemas elevados gastam muito esforço em:

• Estilhaçamento / divisão: refinar grupos até que cada grupo seja de fato permutável dada a evidência.
• Elevação parcial: fazer computação elevada quando possível e instanciar apenas as partes “difíceis”.
• Cache e reutilização: mesmo com evidência, subestruturas podem se repetir.

Um bom modelo mental é: a inferência elevada tenta manter as maiores classes de equivalência válidas consistentes com evidência e restrições.

Quando a inferência elevada é efetiva?

A inferência elevada pode fornecer ganhos de ordens de magnitude quando:

• O modelo contém muitos templates repetidos sobre grandes domínios.
• A evidência é esparsa ou grosseira (muitos indivíduos compartilham o mesmo padrão observado).
• A estrutura relacional não é totalmente observada ou tem regularidades.
• As consultas são sobre propriedades genéricas (por exemplo, a marginal de um indivíduo típico) em vez de eventos altamente específicos e fortemente condicionados.

Ela pode oferecer benefício limitado quando:

• A evidência identifica de modo único muitos indivíduos (atributos granulares).
• O grafo relacional é totalmente observado e altamente irregular.
• A consulta condiciona em muitas constantes específicas, forçando divisão extensa.

Trabalhos teóricos frequentemente caracterizam classes elevadas no domínio (domain-lifted) onde a inferência é polinomial no tamanho do domínio, mas, em geral (como na inferência proposicional), a complexidade no pior caso permanece alta.

Aplicações práticas

A inferência elevada é uma boa opção sempre que você precisa de raciocínio probabilístico sobre muitas entidades e relações similares:

• Domínios sociais e relacionais: influência, comportamento de comunidades, classificação coletiva (por exemplo, rótulos de classe correlacionados entre nós conectados).
• Bases de conhecimento: fatos incertos com restrições lógicas compartilhadas; raciocínio sobre propriedades e relações de entidades.
• Bancos de dados probabilísticos: a avaliação de consultas pode se assemelhar à contagem de modelos com simetrias sobre linhas/tuplas.
• Programação probabilística com placas (plates): alguns programas probabilísticos induzem estruturas permutáveis onde ideias elevadas (contagem, simetria) reduzem a computação.

Em muitos sistemas reais, a inferência elevada é combinada com métodos aproximados (por exemplo, amostragem, aproximações variacionais) para escalar ainda mais, especialmente para grandes Redes de Lógica de Markov.

Relação com outros métodos de inferência em PGM

A inferência elevada é melhor entendida como uma generalização relacional de ideias centrais de inferência em modelos gráficos probabilísticos (PGMs):

• A VE elevada generaliza a eliminação de variáveis para grupos de variáveis permutáveis.
• A BP elevada generaliza a passagem de mensagens em Grafos de Fatores ao comprimir subgrafos simétricos; veja Propagação de Crença (Soma-Produto / Passagem de Mensagens).
• A compilação de conhecimento de primeira ordem generaliza inferência compilada/contagem de modelos para estrutura de primeira ordem.

Se você está confortável com inferência proposicional em Redes Bayesianas e Campos Aleatórios de Markov (Redes de Markov), a inferência elevada adiciona um grande conceito: realizar as mesmas computações, mas no nível de templates e contagens em vez de variáveis instanciadas.

Resumo

• Inferência probabilística elevada evita a instanciação de modelos probabilísticos relacionais explorando simetrias e permutabilidade.
• A técnica central é agrupar variáveis aleatórias indistinguíveis e usar contagem em vez de enumerar indivíduos.
• As principais famílias de algoritmos incluem:
  • Eliminação de Variáveis Elevada (LVE): eliminação exata sobre parfatores com contagem e divisão.
  • Propagação de Crença Elevada: passagem de mensagens comprimida sobre classes de equivalência (frequentemente aproximada).
  • Compilação de conhecimento de primeira ordem / WFOMC: compilar estrutura de primeira ordem e responder consultas via contagem ponderada.
• A inferência elevada é central para escalar a inferência em Redes de Lógica de Markov e outros formalismos de SRL, especialmente em grandes domínios com estrutura repetida e evidência esparsa.

---