Markov logiska nätverk

Ett Markov-logiknätverk ( MLN ) är en probabilistisk logik som tillämpar idéerna från ett Markov-nätverk på första ordningens logik, vilket möjliggör osäker slutledning . Markov-logiknätverk generaliserar första ordningens logik, i den meningen att alla otillfredsställande påståenden inom en viss gräns har en sannolikhet på noll och alla tautologier har sannolikheten en.

Historia

Arbetet inom detta område började 2003 av Pedro Domingos och Matt Richardson, och de började använda termen MLN för att beskriva det.

Beskrivning

Kortfattat är det en samling formler från första ordningens logik , som var och en tilldelas ett reellt tal , vikten. Tagna som ett Markov-nätverk är hörnen på nätverksgrafen atomformler och kanterna är de logiska kopplingarna som används för att konstruera formeln. Varje formel anses vara en klick , och Markovfilten är uppsättningen formler där en given atom förekommer. En potentiell funktion är kopplad till varje formel och tar värdet av ett när formeln är sann och noll när den är falsk. Den potentiella funktionen kombineras med vikten för att bilda Gibbs mått och partitionsfunktion för Markov-nätverket.

Ovanstående definition överskuggar en subtil punkt: atomformler har inget sanningsvärde om de inte är grundade och ges en tolkning ; det vill säga tills de är malda atomer med en Herbrand-tolkning . Således blir ett Markov-logiknätverk ett Markov-nätverk endast med avseende på en specifik jordning och tolkning; det resulterande Markov-nätverket kallas mark Markov-nätverket . Topparna av grafen för markens Markov-nätverk är markatomerna. Storleken på det resulterande Markov-nätverket beror alltså starkt (exponentiellt) på antalet konstanter i diskursdomänen .

Slutledning

Målet med slutledning i ett Markov-logiknätverk är att hitta den stationära fördelningen av systemet, eller en som är nära det; att detta kan vara svårt eller inte alltid möjligt illustreras av den rikedom av beteende som syns i Ising-modellen . Som i ett Markov-nätverk hittar den stationära fördelningen den mest sannolika tilldelningen av sannolikheter till grafens hörn; i detta fall är hörnen grundatomerna i en tolkning. Det vill säga fördelningen indikerar sannolikheten för sanningen eller osanningen för varje jordatom. Givet den stationära fördelningen kan man sedan göra slutledning i den traditionella statistiska betydelsen av betingad sannolikhet : få sannolikheten $P(A|B)$ som formel A håller, givet att formel B är sann.

Slutledning i MLN kan utföras med hjälp av standardtekniker för Markov-nätverksslutning över den minimala delmängden av det relevanta Markov-nätverket som krävs för att svara på frågan. Dessa tekniker inkluderar Gibbs sampling , som är effektiv men kan vara överdrivet långsam för stora nätverk, trosutbredning eller approximation via pseudolikelihood .

Se även

• Markov slumpmässigt fält
• Statistiskt relationellt lärande
• Probabilistiskt logiskt nätverk
• Probabilistisk mjuk logik

externa länkar

• University of Washington Statistical Relational Learning-grupp
• Alchemy 2.0: Markov logiska nätverk i C++
• pracmln: Markov logiska nätverk i Python
• ProbCog: Markov logiska nätverk i Python och Java som kan använda sin egen inferensmotor eller Alchemys
• markov thebeast: Markov logiska nätverk i Java
• RockIt: Markov logiska nätverk i Java (med webbgränssnitt/REST API)
• Tuffy: A Learning and Inference Engine med stark RDBM-baserad optimering för skalbarhet
• Felix: En efterföljare till Tuffy, med förbyggda undermoduler för att påskynda vanliga underuppgifter
• Fabrik: Scalabaserat probabilistiskt inferensspråk, med förbyggda undermoduler för naturlig språkbehandling etc.
• Figaro: Scalabaserat MLN-språk
• LoMRF: Logical Markov Random Fields, en öppen källkodsimplementering av Markov Logic Networks i Scala