Red lógica de Markov

Una red lógica de Markov ( MLN ) es una lógica probabilística que aplica las ideas de una red de Markov a la lógica de primer orden , definiendo distribuciones de probabilidad en mundos posibles en cualquier dominio dado .

Historia

En 2002, Ben Taskar , Pieter Abbeel y Daphne Koller introdujeron las redes relacionales de Markov como plantillas para especificar redes de Markov de forma abstracta y sin referencia a un dominio específico . ^{[1] [2]} El trabajo sobre redes lógicas de Markov comenzó en 2003 por Pedro Domingos y Matt Richardson. ^{[3] [4]} Las redes lógicas de Markov son un formalismo popular para el aprendizaje relacional estadístico . ^[5]

Sintaxis

Una red lógica de Markov consiste en una colección de fórmulas de lógica de primer orden , a cada una de las cuales se le asigna un número real , el peso. La idea subyacente es que una interpretación es más probable si satisface fórmulas con pesos positivos y menos probable si satisface fórmulas con pesos negativos. ^[6]

Por ejemplo, la siguiente red lógica de Markov codifica cómo los fumadores tienen más probabilidades de ser amigos de otros fumadores y cómo el estrés fomenta el hábito de fumar: ^[7] $${\displaystyle {\begin{array}{lcl}2.0&::&\mathrm {smokes} (X)\leftarrow \mathrm {smokes} (Y)\land \mathrm {influences} (X,Y)\\0.5&::&\mathrm {smokes} (X)\leftarrow \mathrm {stress} (X)\end{array}}}$$

Semántica

Red de Markov inducida por la teoría de Sintaxis a un dominio de dos elementos.

Junto con un dominio dado, una red lógica de Markov define una distribución de probabilidad en el conjunto de todas las interpretaciones de sus predicados en el dominio dado. La idea subyacente es que una interpretación es más probable si satisface fórmulas con pesos positivos y menos probable si satisface fórmulas con pesos negativos.

Para cualquier símbolo de predicado -ario que aparece en la red lógica de Markov y cada - tupla de elementos del dominio, es una base de . Se da una interpretación asignando un valor de verdad booleano ( verdadero o falso ) a cada base de un elemento. Una base verdadera de una fórmula en una interpretación con variables libres es una asignación de variable de que hace que sea verdadera en esa interpretación. ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle n}$ ${\displaystyle a_{1},\dots ,a_{n}}$ ${\displaystyle R(a_{1},\dots ,a_{n})}$ ${\displaystyle R}$ ${\displaystyle \varphi }$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle \varphi }$

Entonces la probabilidad de cualquier interpretación dada es directamente proporcional a , donde es el peso de la -ésima oración de la red lógica de Markov y es el número de sus fundamentos verdaderos. ^{[1] [4]} ${\displaystyle \exp(\sum _{j}w_{j}n_{j})}$ ${\displaystyle w_{j}}$ ${\displaystyle j}$ ${\displaystyle n_{j}}$

Esto también puede verse como la inducción de una red de Markov cuyos nodos son los fundamentos de los predicados que aparecen en la red lógica de Markov. Las funciones características de esta red son los fundamentos de las oraciones que aparecen en la red lógica de Markov, con valor si el fundamento es verdadero y 1 en caso contrario (donde nuevamente es el peso de la fórmula). ^[1] ${\displaystyle e^{w}}$ ${\displaystyle w}$

Inferencia

Las distribuciones de probabilidad inducidas por redes lógicas de Markov pueden consultarse para la probabilidad de un evento particular, dada por una fórmula atómica ( inferencia marginal ), posiblemente condicionada por otra fórmula atómica. ^[6]

La inferencia marginal se puede realizar utilizando técnicas de inferencia de redes de Markov estándar sobre el subconjunto mínimo de la red de Markov relevante requerida para responder la consulta. Se sabe que la inferencia exacta es #P -completa en el tamaño del dominio. ^[6]

En la práctica, a menudo se aproxima la probabilidad exacta. ^[8] Las técnicas para la inferencia aproximada incluyen el muestreo de Gibbs , la propagación de creencias o la aproximación mediante pseudoverosimilitud .

La clase de redes lógicas de Markov que utilizan sólo dos variables en cualquier fórmula permite una inferencia exacta en tiempo polinomial mediante la reducción al recuento de modelos ponderados. ^{[9] [6]}

Véase también

• Campo aleatorio de Markov
• Aprendizaje relacional estadístico
• Red lógica probabilística
• Lógica blanda probabilística
• Registro de problemas

Recursos

1. Cozman, Fabio Gagliardi (2020), "Lenguajes para modelado probabilístico sobre dominios estructurados y relacionales", Un recorrido guiado por la investigación en inteligencia artificial , Cham: Springer International Publishing, págs. 247–283, doi :10.1007/978-3-030-06167-8_9, ISBN 978-3-030-06166-1
2. Taskar, Ben; Abbeel, Pieter; Koller, Daphne (1 de agosto de 2002). "Modelos probabilísticos discriminativos para datos relacionales". Actas de la decimoctava conferencia sobre incertidumbre en inteligencia artificial . UAI'02. San Francisco, CA, EE. UU.: Morgan Kaufmann Publishers Inc.: 485–492. ISBN 978-1-55860-897-9.
3. Domingos, Pedro (2015). El algoritmo maestro: cómo el aprendizaje automático está transformando nuestra forma de vida . p. 246-7.
4. Richardson, Matthew; Domingos, Pedro (2006). "Redes lógicas de Markov" (PDF) . Aprendizaje automático . 62 (1–2): 107–136. doi : 10.1007/s10994-006-5833-1 .
5. Augustine, Eriq (2023). Construcción de sistemas prácticos de aprendizaje estadístico relacional (tesis). UC Santa Cruz.
6. Sun, Zhengya; Zhao, Yangyang; Wei, Zhuoyu; Zhang, Wensheng; Wang, Jue (2017). "Aprendizaje escalable e inferencia en redes lógicas de Markov". Revista internacional de razonamiento aproximado . 82 : 39–55. doi :10.1016/j.ijar.2016.12.003. ISSN  0888-613X.
7. Marra, Giuseppe; Dumančić, Sebastijan; Manhaeve, Robin; De Raedt, Luc (1 de marzo de 2024). "De la inteligencia artificial relacional estadística a la neurosimbólica: una encuesta". Inteligencia artificial . 328 : 104062. arXiv : 2108.11451 . doi :10.1016/j.artint.2023.104062. ISSN  0004-3702. Este artículo incorpora texto de Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve y Luc De Raedt disponible bajo la licencia CC BY 4.0.
8. Venugopal, Deepak (2017). "Avances en métodos de inferencia para redes lógicas de Markov" (PDF) . Boletín de informática inteligente del IEEE . 18 (2): 13–19.
9. Kuzelka, Ondrej (29 de marzo de 2021). "Recuento de modelos ponderados de primer orden en el fragmento de dos variables con cuantificadores de conteo". Revista de investigación en inteligencia artificial . 70 : 1281–1307. arXiv : 2007.05619 . doi :10.1613/jair.1.12320. ISSN  1076-9757.

Enlaces externos

• Grupo de aprendizaje relacional estadístico de la Universidad de Washington
• Alquimia 2.0: Redes lógicas de Markov en C++
• pracmln: Redes lógicas de Markov en Python
• ProbCog: Redes lógicas de Markov en Python y Java que pueden utilizar su propio motor de inferencia o el de Alchemy
• markov thebeast: redes lógicas de Markov en Java
• RockIt: Redes lógicas de Markov en Java (con interfaz web/API REST)
• Tuffy: un motor de aprendizaje e inferencia con una sólida optimización basada en RDBM para la escalabilidad
• Felix: un sucesor de Tuffy, con submódulos prediseñados para acelerar las subtareas comunes
• Factorie: lenguaje de inferencia probabilística basado en Scala, con submódulos prediseñados para procesamiento de lenguaje natural, etc.
• Figaro: lenguaje MLN basado en Scala
• LoMRF: Campos aleatorios lógicos de Markov, una implementación de código abierto de redes lógicas de Markov en Scala