Redes de Lógica de Markov

Visão geral

Redes Lógicas de Markov (Markov Logic Networks, MLNs) são um arcabouço de aprendizado relacional estatístico (statistical relational learning) que unifica:

lógica de primeira ordem (first-order logic) (para expressar conhecimento relacional e estruturado com variáveis e quantificadores), e
campos aleatórios de Markov (Markov random fields) (para expressar incerteza probabilística sobre muitas variáveis que interagem entre si).

Uma MLN se parece com um conjunto de fórmulas lógicas, mas cada fórmula tem um peso (weight) associado. Intuitivamente:

Uma regra de peso alto é “geralmente verdadeira” (violações são improváveis, mas permitidas).
Uma regra de peso baixo é uma evidência fraca.
Uma restrição rígida (hard constraint) é uma regra que deve sempre valer (muitas vezes tratada como um peso infinito).

Isso permite que MLNs representem domínios em que regras são geralmente verdadeiras, mas têm exceções — algo comum em linguagem, visão, dados sociais e bases de conhecimento.

MLNs pertencem à família mais ampla de Modelos Gráficos Probabilísticos (Probabilistic Graphical Models) e são intimamente relacionadas a Campos Aleatórios de Markov (Markov Random Fields). Se você está familiarizado com Redes Bayesianas (Bayesian Networks), MLNs podem ser vistas como uma abordagem diferente (não direcionada, log-linear (log-linear)) que é particularmente natural para estruturas relacionais.

Por que MLNs: incerteza em regras relacionais

A lógica de primeira ordem pura é frágil: um único contraexemplo torna uma regra universal “falsa”. Por exemplo:

∀x: Smokes(x) → Cancer(x)

Isso não é estritamente verdadeiro. Alguns fumantes não têm câncer; alguns não fumantes têm. Mas a regra ainda carrega um sinal útil.

MLNs transformam isso em uma restrição suave:

Mundos (atribuições de valores-verdade a todos os predicados instanciados) que satisfazem muitas fórmulas importantes recebem maior probabilidade.
Mundos que violam fórmulas de peso alto são penalizados, mas não se tornam impossíveis.

Isso fornece uma forma fundamentada de fazer inferência probabilística sobre estruturas relacionais, como grafos de entidades e links, com regras que capturam conhecimento do domínio.

Formulação de MLNs

Sintaxe: fórmulas de primeira ordem ponderadas

Uma MLN é um conjunto de pares:

[ {(F_i, w_i)}_{i=1}^m ]

(F_i) é uma fórmula de lógica de primeira ordem (frequentemente escrita como uma cláusula em CNF).
(w_i \in \mathbb{R}) é um peso de valor real.

Predicados são definidos sobre constantes em um domínio (por exemplo, pessoas: {Anna, Bob, …}). Quando você faz a instanciação (grounding) das fórmulas substituindo constantes por variáveis, obtém um grande modelo gráfico não direcionado.

Semântica: de fórmulas a uma rede de Markov

Dado um conjunto finito de constantes (C), cada predicado (por exemplo, Smokes(Ana)) torna-se uma variável aleatória booleana. Cada fórmula ponderada gera características (features) sobre essas variáveis.

Uma visão comum é:

Cada instanciação de uma fórmula (F_i) torna-se um fator (potencial de clique) em um modelo não direcionado.
Se a instanciação é satisfeita, ela contribui com (w_i) (ou contribui para uma contagem de instanciações satisfeitas).

Isso é equivalente a um modelo log-linear (log-linear model) sobre mundos possíveis.

Distribuição de probabilidade

Seja (X) o conjunto de todos os átomos instanciados (ground atoms) (variáveis booleanas). Um mundo possível (possible world) (x) atribui Verdadeiro/Falso a cada átomo instanciado.

Defina (n_i(x)) como o número de instanciações da fórmula (F_i) que são verdadeiras no mundo (x). Então MLNs definem:

[ P(X = x) = \frac{1}{Z} \exp\left(\sum_{i=1}^{m} w_i , n_i(x)\right) ]

(Z) é a função de partição (partition function) (constante de normalização), tipicamente intratável para computar exatamente.
Aumentar (w_i) aumenta a probabilidade de mundos em que mais instanciações de (F_i) são satisfeitas.

Essa é exatamente a forma de uma rede de Markov / modelo log-linear (veja também Modelos de Máxima Entropia (Maximum Entropy Models)).

Interpretando pesos

Uma intuição útil:

Peso positivo: incentiva a satisfação da fórmula.
Peso negativo: incentiva a violação (útil para expressar padrões do tipo “geralmente não”).
Grande magnitude: influência forte.
Fórmula rígida: tratada como uma restrição que não pode ser violada (a implementação varia; às vezes modelada com um peso muito grande).

Pesos não correspondem diretamente a probabilidades; eles moldam uma distribuição global por meio de restrições que interagem entre si.

Um exemplo prático: “Smokes, Friends, Cancer”

Uma MLN clássica de brinquedo usa estes predicados:

Smokes(x) — a pessoa x fuma
Cancer(x) — a pessoa x tem câncer
Friends(x, y) — x e y são amigos

Fórmulas ponderadas:

Amigos influenciam uns aos outros: [ Friends(x,y) \rightarrow (Smokes(x) \leftrightarrow Smokes(y)) ]
Fumar aumenta o risco de câncer: [ Smokes(x) \rightarrow Cancer(x) ]

Em uma sintaxe ao estilo de MLN (ilustrativa):

// If two people are friends, they tend to have similar smoking behavior
1.2  Friends(x, y) => (Smokes(x) <=> Smokes(y))

// Smoking is a risk factor for cancer
2.0  Smokes(x) => Cancer(x)

Suponha que o domínio tenha as constantes {Anna, Bob} e que as evidências incluam:

Friends(Anna, Bob) = True
Smokes(Anna) = True
Smokes(Bob) = ?
Cancer(Bob) = ?

Então a MLN pode inferir:

Smokes(Bob) é mais provável de ser verdadeiro porque isso ajuda a satisfazer a regra de similaridade entre amigos.
Se Smokes(Bob) se tornar provavelmente verdadeiro, então Cancer(Bob) também se torna mais provável devido à regra de risco.

Isso ilustra a capacidade das MLNs de propagar incerteza por meio de estrutura relacional.

Instanciação e visão de grafo de fatores (por que a inferência é difícil)

O desafio computacional central é a instanciação:

Se você tem (N) constantes e um predicado binário Friends(x,y), há (O(N^2)) átomos instanciados.
Uma fórmula com (k) variáveis pode ter (O(N^k)) instanciações.

Na prática, a inferência em MLNs frequentemente depende de:

instanciação preguiçosa / sob demanda (lazy / on-demand grounding) (instanciar apenas o que é necessário),
inferência levantada (lifted inference) (raciocinar no nível de primeira ordem explorando simetria), ou
métodos aproximados que conseguem lidar com grandes redes instanciadas.

MLNs frequentemente são representadas internamente usando um grafo de fatores (factor graph) (veja Grafos de Fatores (Factor Graphs)) derivado das fórmulas instanciadas.

Inferência em MLNs

A inferência responde a perguntas como:

inferência marginal (marginal inference): (P(Q \mid E)) — probabilidade dos átomos de consulta (Q) dado o conjunto de evidências (E).
inferência MAP (MAP inference): (\arg\max_x P(x \mid E)) — atribuição mais provável consistente com a evidência.

A inferência exata é, em geral, intratável (#P-hard) devido ao tamanho e à conectividade da rede instanciada, então sistemas práticos de MLN usam métodos aproximados ou especializados.

Inferência marginal aproximada

Abordagens comuns incluem:

amostragem de Gibbs (Gibbs sampling): um método padrão de Monte Carlo via Cadeias de Markov (Markov Chain Monte Carlo, MCMC) em que você reamostra repetidamente uma variável dada sua vizinhança de Markov (Markov blanket). Funciona bem quando a mistura é razoável, mas pode ter dificuldades com correlações fortes e regras quase determinísticas.
MC-SAT: um algoritmo híbrido que combina MCMC com movimentos ao estilo SAT para lidar com restrições quase rígidas de forma mais eficaz do que a Gibbs pura.
propagação de crenças com ciclos (loopy belief propagation): passagem de mensagens em grafos com ciclos (veja Propagação de Crenças (Belief Propagation)). Frequentemente é rápida, mas não há garantia de convergência ou acurácia em MLNs com muitos ciclos.

Nota prática: Em muitas aplicações de MLN, a inferência marginal é usada para produzir saídas probabilísticas para relações incertas (por exemplo, “este par de menções é correferente com probabilidade 0,87”).

Inferência MAP (mundo mais provável)

A inferência MAP em MLNs frequentemente é reduzida a problemas de otimização como:

Weighted Max-SAT / MaxWalkSAT: busca local estocástica que tenta satisfazer cláusulas de peso alto.
Formulações de Programação Linear Inteira (Integer Linear Programming, ILP) (veja Programação Linear Inteira (Integer Linear Programming)): úteis quando você quer soluções exatas ou aproximadas com limite, com restrições.
plano de corte / MAP preguiçoso (cutting-plane / lazy MAP): começa com um pequeno subconjunto de restrições instanciadas e adiciona iterativamente as que forem violadas pela solução atual, evitando instanciação completa.

MAP é especialmente útil quando você quer uma única saída estruturada consistente (por exemplo, um grafo de entidades resolvido).

Inferência levantada (quando a simetria ajuda)

A inferência levantada explora o fato de que muitos indivíduos são intercambiáveis dado o conjunto de evidências. Em vez de raciocinar sobre cada instanciação separadamente, ela agrupa variáveis/restrições equivalentes.

Métodos levantados podem gerar acelerações dramáticas em domínios com estrutura repetida e pouca evidência distintiva (veja Inferência Levantada (Lifted Inference)).

Aprendizado em MLNs

MLNs suportam aprendizado a partir de dados de duas formas principais:

aprendizado de pesos (weight learning) (parâmetros (w_i) para um conjunto fixo de fórmulas),
aprendizado de estrutura (structure learning) (descoberta de fórmulas úteis).

Aprendizado de pesos

Dado um conjunto de dados de treinamento (atribuições de verdade para alguns ou todos os átomos instanciados), queremos pesos que tornem os mundos observados prováveis.

Aprendizado generativo (máxima verossimilhança)

Se os dados fornecem atribuições completas, a log-verossimilhança é:

[ \log P(x) = \sum_i w_i n_i(x) - \log Z(w) ]

O gradiente tem a forma clássica “observado menos esperado”:

[ \frac{\partial}{\partial w_i} \log P(x) = n_i(x) - \mathbb{E}_{P_w}[n_i(X)] ]

Assim, o aprendizado exige computar contagens esperadas sob o modelo — um problema de inferência — tornando-o caro.

Pseudo-verossimilhança (alternativa prática)

A pseudo-verossimilhança (pseudo-likelihood) substitui a verossimilhança global por um produto de probabilidades condicionais locais:

[ PL(x) = \prod_j P(X_j = x_j \mid X_{\setminus j} = x_{\setminus j}) ]

Isso evita computar a função de partição global e é muito mais barato, embora possa sacrificar acurácia quando dependências de longo alcance importam.

Aprendizado discriminativo (condicional)

Frequentemente, você quer prever predicados de consulta (Y) dado o conjunto de evidências (X), isto é, (P(Y \mid X)). O aprendizado discriminativo (discriminative learning) otimiza a verossimilhança condicional e normalmente produz melhor desempenho preditivo em tarefas supervisionadas.

A otimização costuma ser feita com métodos baseados em gradiente como L-BFGS, muitas vezes com regularização (L2 ou L1) para evitar sobreajuste.

Aprendizado de estrutura

O aprendizado de estrutura busca entre fórmulas candidatas (cláusulas) para encontrar aquelas que melhoram o ajuste. Isso está intimamente relacionado à Programação Lógica Indutiva (Inductive Logic Programming), mas com pontuação probabilística.

Abordagens comuns:

Busca top-down de regras: começa com templates gerais e especializa adicionando literais.
Bottom-up / características de caminhos relacionais: propõe cláusulas com base em padrões relacionais nos dados.
Seleção baseada em pontuação: adiciona/remove fórmulas com base em melhorias de verossimilhança/pseudo-verossimilhança (frequentemente com penalidades por complexidade).

O aprendizado de estrutura é poderoso, mas computacionalmente pesado, porque cada regra candidata interage com instanciação e inferência.

Padrões de modelagem e dicas práticas

Escolhendo predicados e suposições de “mundo fechado”

Conjuntos de dados reais raramente informam explicitamente todos os fatos negativos. Uma escolha prática comum é a hipótese de mundo fechado (closed world assumption) para certos predicados: se um fato não está presente, tratá-lo como falso. Isso pode simplificar o treinamento, mas pode ser inadequado para bases de conhecimento com dados ausentes.

Muitos sistemas de MLN também assumem lógica de primeira ordem sem funções (function-free) (sem símbolos de função) para manter a instanciação finita.

Regras suaves para evidência ruidosa

MLNs brilham quando você consegue codificar heurísticas imperfeitas como regras ponderadas. Por exemplo, em resolução de entidades:

3.0  SameEmail(p1, p2) => SamePerson(p1, p2)
1.0  SameLastName(p1, p2) => SamePerson(p1, p2)
-2.0 SamePerson(p1, p2) => !DifferentDOB(p1, p2)

Same email is strong evidence.
Same last name is weaker evidence.
Different date-of-birth is evidence against being the same person.

O modelo combina esses sinais globalmente e pode impor consistência (por exemplo, transitividade) por meio de regras adicionais.

Evitando explosões de instanciação

Para manter MLNs tratáveis:

Limite a aridade e o número de variáveis por fórmula quando possível.
Use evidência para podar: muitos sistemas instanciam apenas cláusulas relevantes para a consulta/evidência.
Prefira regras que conectem um pequeno número de átomos incertos.
Use domínios tipados (por exemplo, Person, Company) para reduzir instanciações irrelevantes.

Onde MLNs são usadas

MLNs são mais adequadas para representação de conhecimento com incerteza e raciocínio relacional onde:

Entidades e relações formam um grafo,
Há regras relacionais reutilizáveis,
Observações são ruidosas ou incompletas.

Áreas comuns de aplicação incluem:

Extração de informação e inferência conjunta

Em pipelines de PLN, tarefas como reconhecimento de entidades, extração de relações e correferência (coreference) são interdependentes. MLNs podem combinar classificadores locais com restrições globais, como:

Se duas menções são correferentes, elas devem compartilhar atributos.
Certas relações implicam restrições de tipo (por exemplo, WorksFor(person, org) implica Person(person) e Organization(org)).

Essa inferência conjunta (joint inference) pode reduzir inconsistências em comparação com resolver tarefas independentemente. (Relacionado: Campos Aleatórios Condicionais (Conditional Random Fields, CRFs) para rotulagem de sequência; MLNs generalizam para restrições relacionais mais ricas.)

Resolução de entidades / vinculação de registros

MLNs representam naturalmente a tensão entre sinais de similaridade ruidosos e restrições globais de consistência:

Strings semelhantes sugerem a mesma entidade,
Mas um registro não pode corresponder a duas entidades incompatíveis,
A correferência é transitiva (muitas vezes imposta de forma suave ou rígida).

Completação de base de conhecimento e predição relacional

Dado um conjunto parcial de fatos sobre entidades (pessoas, lugares, proteínas), MLNs podem inferir links ausentes usando regras e relações observadas — em espírito semelhante ao raciocínio sobre Grafos de Conhecimento (Knowledge Graphs), mas com restrições lógicas explícitas e semântica probabilística.

Raciocínio em redes sociais e biológicas

Em grafos onde links e atributos influenciam uns aos outros (amizade, colaboração, interações proteicas), MLNs podem codificar homofilia (homophily), fechamento triádico (triadic closure) e restrições do domínio como fórmulas ponderadas.

Robótica e reconhecimento de atividades (incerteza estruturada)

Em domínios estruturados (objetos, relações, eventos temporais), MLNs podem dar suporte a raciocínio de alto nível com evidência perceptual incerta — embora, em sistemas modernos, isso frequentemente seja complementado ou substituído por modelos neurais e programação probabilística (probabilistic programming).

Relação com outros arcabouços

MLNs ficam na interseção entre lógica e modelagem probabilística:

Em comparação com Redes Bayesianas (Bayesian Networks): MLNs são não direcionadas e tipicamente mais fáceis de especificar usando regras relacionais simétricas; redes bayesianas exigem escolhas de fatoração direcionada e aciclicidade.
Em comparação com Campos Aleatórios de Markov (Markov Random Fields): MLNs fornecem uma linguagem de templates relacionais (fórmulas de primeira ordem) que gera um campo aleatório de Markov quando instanciado.
Em comparação com Campos Aleatórios Condicionais (Conditional Random Fields): CRFs são modelos log-lineares condicionais sobre estruturas tipicamente fixas (por exemplo, cadeias); MLNs generalizam a modelagem log-linear condicional para estruturas relacionais arbitrárias com templates baseados em lógica.
Em comparação com Lógica Suave Probabilística (Probabilistic Soft Logic) e abordagens diferenciáveis/neuro-simbólicas (neural-symbolic): MLNs usam lógica booleana discreta; abordagens mais novas frequentemente relaxam a lógica para valores de verdade contínuos para escalabilidade, ou embutem relações com redes neurais. MLNs permanecem fundamentais para entender lógica probabilística com semântica clara.

Pontos fortes e limitações

Pontos fortes

Modelagem relacional expressiva: codifica naturalmente regras com variáveis e quantificadores.
Incerteza fundamentada: restrições suaves permitem raciocínio robusto sob ruído.
Consistência global: pode inferir conjuntamente muitas decisões interdependentes.

Limitações

Escalabilidade: a instanciação pode ser enorme; inferência e aprendizado frequentemente são caros.
Complexidade de engenharia: o desempenho depende fortemente de modelagem cuidadosa, tratamento de evidências e configuração de inferência.
Difícil integrar percepção bruta: MLNs funcionam melhor com predicados simbólicos; pipelines modernos frequentemente dependem de modelos neurais para produzir predicados/características.

Na prática, MLNs ainda são valiosas quando conhecimento do domínio e restrições relacionais importam, mas não são a escolha padrão para problemas em escala muito grande, a menos que métodos levantados/preguiçosos especializados sejam eficazes.

Ecossistema de implementação (nota prática)

Historicamente, kits de ferramentas populares de MLN incluíram sistemas como Alchemy e, mais tarde, variantes escaláveis (por exemplo, sistemas de instanciação/inferência apoiados em banco de dados). Embora o ecossistema não seja tão ativo quanto os frameworks de aprendizado profundo (deep learning), MLNs continuam influentes em pesquisa e em domínios que precisam de raciocínio probabilístico interpretável e baseado em regras.

Resumo

Redes Lógicas de Markov oferecem uma ideia limpa e poderosa: tratar fórmulas lógicas como características em uma rede de Markov, ponderadas por quão fortemente acreditamos nelas. Isso possibilita:

Representação de conhecimento com incerteza,
Inferência probabilística sobre domínios relacionais,
Aprendizado de pesos (e, às vezes, de estrutura) a partir de dados.

Mesmo quando arcabouços alternativos são usados em sistemas modernos, MLNs permanecem uma ponte conceitual importante entre lógica simbólica e modelagem probabilística — especialmente para entender como fazer raciocínio com regras incertas em escala.