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 las 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]} A partir de 2023 ^[actualizar], las redes lógicas de Markov todavía se encuentran entre los formalismos más populares para el aprendizaje relacional estadístico . ^[5]

Sintaxis

Una red lógica de Markov consta de un conjunto 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 ponderaciones positivas y menos probable si satisface fórmulas con ponderaciones negativas. ^[6]

Por ejemplo, la siguiente red lógica de Markov codifica cómo es más probable que los fumadores sean amigos de otros fumadores y cómo el estrés fomenta el tabaquismo: ^[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 la 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 ponderaciones positivas y menos probable si satisface fórmulas con ponderaciones negativas.

Para cualquier símbolo de predicado -ario que aparece en la red lógica de Markov y en cada tupla de elementos de dominio, es una base de . Una interpretación se da asignando un valor de verdad booleano ( verdadero o falso ) a cada fundamento de un elemento. Una verdadera fundamentación de una fórmula en una interpretación con variables libres es una asignación de variable que la hace 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 ocurren en la red lógica de Markov. Las funciones características de esta red son las bases de las oraciones que ocurren en la red lógica de Markov, con valor si la base es verdadera y 1 en caso contrario (donde nuevamente está el peso de la fórmula). ^[1] ${\displaystyle e^{w}}$ ${\displaystyle w}$

Inferencia

Las distribuciones de probabilidad inducidas por las redes lógicas de Markov pueden consultarse para determinar 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 estándar de inferencia de redes de Markov sobre el subconjunto mínimo de la red de Markov relevante requerido para responder la consulta. Se sabe que la inferencia exacta es #P -completa en el tamaño del dominio. ^[6]

En la práctica, la probabilidad exacta suele ser aproximada. ^[8] Las técnicas de 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 la inferencia exacta en tiempo polinómico mediante la reducción al recuento de modelos ponderados. ^{[9] [6]}

Ver 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", una visita guiada a 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 . AUI'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á cambiando nuestra forma de vivir . pag. 246-7.
4. Richardson, Mateo; 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. Agustín, Eriq (2023). Construcción de sistemas prácticos de aprendizaje estadístico relacional (tesis). UC Santa Cruz.
6. Sol, Zhengya; Zhao, Yangyang; Wei, Zhuoyu; Zhang, Wensheng; Wang, Jue (2017). "Aprendizaje e inferencia escalables 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; Dumancic, Sebastijan; Manhaeve, Robin; De Raedt, Luc (1 de marzo de 2024). "De la inteligencia artificial estadística relacional 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 IEEE . 18 (2): 13-19.
9. Kuzelka, Ondrej (29 de marzo de 2021). "Modelo ponderado de primer orden que cuenta en el fragmento de dos variables con cuantificadores de recuento". 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
• Alchemy 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 usar 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 lograr 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 el procesamiento del lenguaje natural, etc.
• Figaro: lenguaje MLN basado en Scala
• LoMRF: Logical Markov Random Fields, una implementación de código abierto de Markov Logic Networks en Scala