Rete logica di Markov

Nell'ambito dell'apprendimento automatico, una rete logica di Markov o Markov logic network (MLN) è una logica probabilistica che applica la nozione di rete di Markov alla logica del primo ordine, definendo distribuzioni di probabilità sui mondi possibili in un dato dominio.

Nel 2002, Ben Taskar, Pieter Abbeel e Daphne Koller hanno introdotto le reti di Markov relazionali come modelli utili a specificare le reti di Markov in modo astratto e senza fare riferimento a uno specifico dominio^[1][2]. Il lavoro sulle MLN è stato iniziato nel 2003 da Pedro Domingos and Matt Richardson^[3][4]. Le MNL costituiscono un formalismo comune nell'ambito dell'apprendimento statistico relazionale ovvero l'apprendimento di modelli probabilistici relazionali^[5].

Una MLN consiste di un insieme di formule in logica del primo ordine, a ciascuna delle quali è assegnato un numero reale, il peso. L'idea di base è che un'interpretazione sarà più probabile se soddisfa formule con pesi positivi e meno probabile se soddisfa formule con pesi negativi.^[6]

Ad esempio la seguente MLN codifica il fatto che i fumatori siano più facilmente amici di altri fumatori e che lo stress incoraggi a fumare:^[7]

${\displaystyle {\begin{array}{lcl}2.0&::&{\mathtt {fuma}}(X)\leftarrow {\mathtt {fuma}}(Y)\land {\mathtt {influenza}}(X,Y)\\0.5&::&{\mathtt {fuma}}(X)\leftarrow {\mathtt {stress}}(X)\end{array}}}$

Insieme a un dato dominio, una MLN definisce una distribuzione di probabilità sull'insieme di tutte le interpretazioni dei suoi predicati su quel dominio. L'idea di fondo è che un'interpretazione sia più probabile se soddisfa formule con pesi positivi e meno probabile se soddisfa formule con pesi negativi.

Per ciascun simbolo di predicato ${\displaystyle n}$-ario ${\displaystyle R}$ che occorre nella MLN e ciascuna ${\displaystyle n}$-pla ${\displaystyle a_{1},\dots ,a_{n}}$ di elementi del dominio, ${\displaystyle R(a_{1},\dots ,a_{n})}$ è un grounding di ${\displaystyle R}$. Un'interpretazione viene definita assegnando un valore di verità booleano (vero o falso) a ogni grounding di un elemento. Un grounding vero di una formula ${\displaystyle \varphi }$ in un'interpretazione con variabili libere ${\displaystyle x_{1},\dots ,x_{n}}$ è una assegnazione alle variabili ${\displaystyle x_{1},\dots ,x_{n}}$ che rende ${\displaystyle \varphi }$ vera in quell'interpretazione.

Allora la probabilità di una data interpretazione è direttamente proporzionale a

${\displaystyle \exp \left(\sum _{j}w_{j}n_{j}\right)}$,

dove ${\displaystyle w_{j}}$ è il peso del ${\displaystyle j}$-esimo enunciato della MLN e ${\displaystyle n_{j}}$ è il numero dei suoi grounding veri.^[1][4]

Ciò può anche essere considerato come la definizione di una rete di Markov i cui nodi sono i grounding dei predicati presenti nella MLN. Le funzioni caratteristiche di questa rete sono i grounding degli enunciati presenti nella MLN, con valore ${\displaystyle e^{w}}$ se il grounding è vero e 1 altrimenti (dove ${\displaystyle w}$ è sempre il peso della formula)^[1].

È possibile interrogare le distribuzioni di probabilità indotte dalle MLN per ottenere la probabilità di un evento specifico, dato da una formula atomica (inferenza marginale), eventualmente condizionata da un'altra formula atomica^[6].

L'inferenza marginale può essere eseguita utilizzando tecniche standard di inferenza sulle reti di Markov sul sottoinsieme minimo della rete di Markov pertinente necessario per rispondere alla query. È noto che l'inferenza esatta è #P-completa rispetto alle dimensioni del dominio^[6].

In pratica, spesso si ricorre a un'approssimazione della probabilità esatta^[8]. Le tecniche di inferenza approssimata comprendono il campionamento di Gibbs, la belief propagation e l'approssimazione tramite pseudoverosimiglianza.

La classe delle reti logiche di Markov che utilizzano solo due variabili in ogni formula consente un'inferenza esatta in tempo polinomiale mediante riduzione al conteggio dei modelli ponderati.^[9][6]

• Campo casuale di Markov