Rede lógica de Markov

Uma rede lógica de Markov (MLN) é uma lógica probabilística que aplica as ideias de redes de Markov à lógica de primeira ordem, possibilitando inferência incerta. Redes lógicas de Markov generalizam a lógica de primeira ordem, no sentido de que, até certo ponto, todas as sentenças insatisfatíveis têm uma probabilidade igual a zero, e todas as tautologias têm probabilidade igual a um.

História

O trabalho nesta área começou em 2003 por Pedro Domingos e Matt Richardson, e eles começaram a usar o termo MLN para descrevê-lo.

Descrição

Resumidamente, é uma coleção de fórmulas da lógica de primeira ordem, para cada uma das quais é atribuído um número real, o peso. Tomados como uma rede de Markov, os vértices do grafo de rede são fórmulas atômicas, e as arestas são os conectivos lógicos utilizados para construir a fórmula. Cada fórmula é considerada um clique, e o manto de Markov (Markov blanket) é o conjunto de fórmulas em que um determinado átomo aparece. Uma função potencial é associada a cada fórmula, e assume valor 1 quando a fórmula é verdadeira, e 0 quando ela é falsa. A função potencial é combinada com o peso para formar a medida de Gibbs e a função de partição para a rede de Markov.

A definição acima encobre um ponto sutil: fórmulas atômicas não têm um valor verdade, a menos que elas sejam básicas e recebam uma interpretação; isto é, até que elas sejam átomos básicos com uma interpretação de Herbrand. Assim, uma rede lógica de Markov torna-se uma rede de Markov apenas em relação a uma determinada base (grounding) e interpretação; a rede de Markov resultante é chamada rede básica de Markov. Os vértices do grafo da rede básica de Markov são os átomos básicos. O tamanho da rede de Markov resultante, portanto, depende fortemente (exponencialmente) do número de constantes no domínio do discurso.

Inferência

O objetivo da inferência em uma rede lógica de Markov é encontrar a distribuição estacionária do sistema, ou uma que seja próxima a essa; o fato de isso poder vir a ser difícil ou nem sempre possível é ilustrado pela riqueza de comportamento observada no modelo de Ising. Como em uma rede de Markov, a distribuição estacionária encontra a mais provável atribuição de probabilidades para os vértices do grafo; neste caso, os vértices são os átomos básicos de uma interpretação. Isto é, a distribuição indica a probabilidade de veracidade ou falsidade de cada átomo básico. Dada a distribuição estacionária, pode-se então realizar inferência no senso estatístico tradicional  de probabilidade condicional: obter a probabilidade ${\displaystyle }$ que a fórmula A possui, dado que a fórmula B é verdadeira.

Inferências em MLNs podem ser realizadas utilizando-se técnicas de inferência padrão na rede de Markov sobre o subconjunto mínimo da rede de Markov relacionada (relevant), necessária para responder a questão. Estas técnicas incluem a amostragem de Gibbs, que é eficaz, mas pode ser excessivamente lenta para grandes redes, propagação de crença, ou aproximação através de pseudo-verossimilhança.

Veja também

• Campo aleatório de Markov
• Aprendizagem estatística relacional
• Rede lógica probabilística

Ligações externas

• University of Washington Statistical Relational Learning group
• Alchemy 2.0: Markov logic networks in C++
• pracmln: Markov logic networks in Python
• ProbCog: Markov logic networks in Python and Java that can use its own inference engine or Alchemy's
• markov thebeast: Markov logic networks in Java
• RockIt: Markov logic networks in Java (with web interface/REST API)
• Tuffy: A Learning and Inference Engine with strong RDBMs-based optimization for scalability
• Felix: A successor to Tuffy, with prebuilt submodules to speed up common subtasks
• Factorie: Scala based probabilistic inference language, with prebuilt submodules for natural language processing etc
• Figaro: Scala based MLN language
• LoMRF: Logical Markov Random Fields, an open-source implementation of Markov Logic Networks in Scala