Programmazione logica induttiva probabilistica

La programmazione logica induttiva probabilistica (in inglese probabilistic inductive logic programming, acronimo PILP) è un'area di ricerca dell'intelligenza artificiale situata all'intersezione tra l'apprendimento automatico, la logica formale e la teoria della probabilità.

La PILP estende la programmazione logica induttiva (ILP) tradizionale integrando il ragionamento probabilistico. Ciò consente di apprendere regole logiche generali partendo da dati strutturati, complessi e intrinsecamente affetti da incertezza, rumore o incompletezza. Questo paradigma si classifica all'interno del più ampio filone dell'apprendimento relazionale statistico (o Statistical Relational Learning, SRL) che mira all'apprendimento di modelli probabilistici relazionali.

Motivazione

La programmazione logica classica (come il Prolog) e l'ILP tradizionale si basano sulla logica del primo ordine, la quale presuppone una visione binaria della realtà: un'affermazione può essere esclusivamente vera o falsa. Tuttavia, le applicazioni del mondo reale, in settori come la bioinformatica, l'elaborazione del linguaggio naturale o la robotica, sono complicate dal problema dell'incertezza nei dati che possono essere spesso rumorosi e incompleti (parzialmente osservati).

La PILP supera questo limite combinando tre aspetti fondamentali:

Logica del primo ordine: per rappresentare relazioni complesse tra oggetti ed esprimere la conoscenza di dominio in modo leggibile sia dall'uomo che dalla macchina.
Modelli probabilistici (ad es. reti bayesiane, campi casuali di Markov): per quantificare l'incertezza e gestire la natura stocastica dei fenomeni.
Induzione (apprendimento): per generalizzare regole relazionali astratte partendo da esempi positivi, negativi e da conoscenza pregressa (background knowledge).

Fondamenti e rappresentazione

Nel contesto della PILP, un programma logico probabilistico è generalmente un insieme di clausole logiche a cui sono associate delle probabilità. Esistono diversi formalismi per la rappresentazione, tra cui i più noti sono il ProbLog, l'Independent Choice Logic (ICL) e i Probabilistic Horn Abductive Programs (PHA).

Prendendo come riferimento la sintassi del ProbLog, una clausola probabilistica ha la forma:

p_{i}::H\leftarrow B_{1},B_{2},\dots ,B_{n}.

dove:

$H$ (head) è l'atomo della conclusione.
$B_{j}$ (body) rappresenta i letterali della condizione.
$p_{i}\in [0,1]$ è la probabilità che la clausola sia estratta (ovvero che sia definita come "vera"), assumendo l'indipendenza stocastica tra le diverse scelte del programma.

Semantica dei mondi possibili

La semantica di un programma PILP si basa sulla semantica distribuzionale (Distribution Semantics). Sia $L$ un programma logico probabilistico composto da un insieme di fatti probabilistici $F=\{f_{1},\dots ,f_{m}\}$ con rispettive probabilità $\{p_{1},\dots ,p_{m}\}$ e da un insieme di regole deterministiche $R$ .

Un mondo possibile $w\subseteq F$ è una specifica selezione di fatti probabilistici che si assumono veri. La probabilità di un atomo ground $q$ è definita dalla somma delle probabilità dei mondi possibili in cui $q$ è logicamente derivabile ( $w\cup R\models q$ ):

P(q)=\sum _{w\subseteq F:w\cup R\models q}P(w)

dove la probabilità di un singolo mondo $w$ è calcolata tramite il prodotto:

P(w)=\prod _{f_{i}\in w}p_{i}\times \prod _{f_{i}\in F\setminus w}(1-p_{i})

Problema di apprendimento (induzione)

L'obiettivo della PILP è apprendere sia la struttura del programma logico (le regole) sia i parametri numerici (le probabilità) partendo da un insieme di osservazioni (esempi) $E$ e dalla conoscenza di fondo $B$ .

Il problema viene formalizzato nel seguente modo:

Dati:

un insieme di esempi positivi e negativi $E=E^{+}\cup E^{-}$ (oppure una distribuzione di probabilità-obiettivo su atomi);

la conoscenza di fondo $B$ espressa come programma logico probabilistico;

uno spazio di ipotesi ${\mathcal {H}}$ (l'insieme dei possibili programmi logici probabilistici);

Trovare:

un'ipotesi $H^{*}\in {\mathcal {H}}$ che massimizzi la verosimiglianza (likelihood) dei dati:

$H^{*}=\arg \max _{H\in {\mathcal {H}}}P(E|B\cup H)$

L'apprendimento si divide classicamente in due sotto-problemi:

apprendimento dei parametri: Data una struttura di regole fissa, stimare i valori ottimali delle probabilità associate alle clausole. Viene risolto frequentemente tramite algoritmi di Expectation-Maximization (EM) o ottimizzazione basata su gradiente.
apprendimento della struttura: Trovare la combinazione ottimale di clausole logiche esplorando lo spazio di raffinamento (top-down o bottom-up) combinato con l'apprendimento dei parametri per valutare quantitativamente ciascuna candidata.

Esempio

Consideriamo uno scenario di rete sociale semplificato in cui si desidera modellare la trasmissione di un'influenza o di un virus.

Conoscenza di fondo e ipotesi corrente

% Fatti probabilistici (incertezza intrinseca)
0.1 :: stress(X).
0.2 :: portatore_sano(X).

% Regole probabilistiche (la trasmissione non è deterministica)
0.6 :: contagioso(X, Y) :- amico(X, Y).

% Fatti deterministici della rete relazionale
amico(alice, berto).
amico(berto, carlo).

Calcolo della probabilità (Inferenza)

Per calcolare la probabilità che l'atomo contagioso(alice, berto) sia vero, l'algoritmo PILP (o il motore ProbLog sottostante) costruisce un diagramma di decisione binaria (BDD) o compila la teoria logica in forme normali come la d-DNNF al fine di calcolare in modo efficiente la probabilità marginale esatta, evitando l'enumerazione esponenziale dei mondi possibili.

Algoritmi e sistemi

Nel corso degli anni sono stati sviluppati diversi sistemi software di riferimento per il paradigma PILP:

ProbLog / ProbLog2: Sviluppato presso la KU Leuven, permette l'apprendimento dei parametri e della struttura tramite algoritmi dedicati.^[1] Consente l'inferenza probabilistica avanzata applicata al link mining.^[2]
SLIPCOVER (Structure Learning of Inductive Logic Programs for video and text): Sistema avanzato che apprende sia la struttura sia i parametri di programmi LPAD (Logic Programs with Annotated Disjunctions) mediante una ricerca nello spazio delle clausole guidata da funzioni di score relazionali.^[3]
cALICORN / LFI-ProbLog: Sistemi specificamente dedicati alla stima statistica dei parametri (modeling simbolico-statistico) in presenza di dati parziali, mancanti o incompleti.^[4]

Note

↑ De Raedt, L., Frasconi, P., Kersting, K., & Muggleton, S., Probabilistic Inductive Logic Programming: Theory and Applications, Springer Berlin Heidelberg, 2008, DOI:10.1007/978-3-540-78652-8.
↑ De Raedt, L., Kimmig, A., & Toivonen, H., ProbLog: A Probabilistic Prolog and Its Application in Link Mining, in Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), 2007, pp. 2468–2473, DOI:10.5555/1625275.1625673.
↑ Bellodi, E., & Riguzzi, F., Structure learning of probabilistic logic programs by searching the clauses space, in Machine Learning, vol. 100, n. 1, 2015, pp. 25-59, DOI:10.1007/s10994-014-5471-1.
↑ Sato, T., & Kameya, Y., Parameter learning of logic programs for symbolic-statistical modeling, in Journal of Artificial Intelligence Research, vol. 15, 2001, pp. 391-454, DOI:10.1613/jair.877.

Voci correlate

[1] De Raedt, L., Frasconi, P., Kersting, K., & Muggleton, S., Probabilistic Inductive Logic Programming: Theory and Applications, Springer Berlin Heidelberg, 2008, DOI:10.1007/978-3-540-78652-8.

[2] De Raedt, L., Kimmig, A., & Toivonen, H., ProbLog: A Probabilistic Prolog and Its Application in Link Mining, in Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), 2007, pp. 2468–2473, DOI:10.5555/1625275.1625673.

[3] Bellodi, E., & Riguzzi, F., Structure learning of probabilistic logic programs by searching the clauses space, in Machine Learning, vol. 100, n. 1, 2015, pp. 25-59, DOI:10.1007/s10994-014-5471-1.

[4] Sato, T., & Kameya, Y., Parameter learning of logic programs for symbolic-statistical modeling, in Journal of Artificial Intelligence Research, vol. 15, 2001, pp. 391-454, DOI:10.1613/jair.877.

[1]

[2]

[3]

[4]