Agenti logici e logica proposizionale - inferenza e risoluzione

Argomento del corso da 9 CFU. Fonte: slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD.

Agenti basati sulla conoscenza

Un agente basato sulla conoscenza (knowledge-based agent) ha una base di conoscenza (KBKnowledge Base: insieme di enunciati scritti in un linguaggio formale, con cui l'agente rappresenta ciò che sa del mondo.) e un motore di inferenza che ne ricava conseguenze.

• La KB contiene i contenuti specifici del dominio; il motore usa algoritmi indipendenti dal dominio.
• Approccio dichiarativo: si dice all'agente cosa sa (Tell), poi gli si chiede cosa fare (Ask): la risposta deve seguire dalla KB. Non si programma "come" decidere.
• Due livelli di lettura: livello della conoscenza (cosa sa l'agente, a prescindere da come è realizzato) e livello di implementazione (strutture dati della KB e algoritmi che le manipolano).

L'agente deve saper rappresentare stati e azioni, incorporare nuove percezioni, aggiornare la rappresentazione del mondo, dedurre proprietà nascoste e azioni appropriate. Lo schema è un agente come quelli di Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →, con la KB al posto della tabella o delle regole fisse:

def kb_agent(kb, percept, t):          # t = contatore del tempo
    kb.tell(make_percept_sentence(percept, t))
    action = kb.ask(make_action_query(t))
    kb.tell(make_action_sentence(action, t))
    return action                      # il chiamante incrementa t

Il mondo del Wumpus

Mondo giocattolo per provare il ragionamento logico: griglia $4 \times 4$ con un mostro (Wumpus), pozzi, un tesoro.

PEAS (vedi Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →):

Caratterizzazione: parzialmente osservabile (solo percezioni locali), deterministico, sequenziale, statico (Wumpus e pozzi non si muovono), discreto, a singolo agente (il Wumpus è una caratteristica del mondo, non insegue l'agente).

Esplorazione. L'agente parte da $[1,1]$, sicuro, senza percezioni: quindi $[1,2]$ e $[2,1]$ sono sicure. Va in $[2,1]$ e sente brezza: c'è un pozzo in $[1,1]$ (escluso), $[2,2]$ o $[3,1]$. Torna e va in $[1,2]$: sente puzza ma non brezza. Allora:

• niente brezza in $[1,2]$: nessun pozzo in $[2,2]$ (né in $[1,3]$), quindi la brezza di $[2,1]$ viene da un pozzo in $[3,1]$;
• niente puzza in $[2,1]$: il Wumpus non è in $[2,2]$, quindi la puzza di $[1,2]$ viene da un Wumpus in $[1,3]$.

Sono deduzioni che nessuna singola percezione dà: servono più percezioni combinate con le regole del mondo. (Nelle slide un indice è scritto "$[3.1]$": è un refuso di $[3,1]$.)

Logica, sintassi e semantica

Una logica è un linguaggio formale per rappresentare informazione in modo da trarne conclusioni corrette se l'informazione è corretta.

• Sintassi: quali sequenze di simboli sono enunciati. Esempio aritmetico: $x + 2 \ge y$ è un enunciato, $x2 + y >$ no.
• Semantica: il significato, cioè la verità di un enunciato in un mondo. $x + 2 \ge y$ è vero se il numero $x + 2$ non è minore di $y$: vero in un mondo con $x=7, y=1$, falso con $x=0, y=6$.
• Un modello è un assegnamento di valori a tutti i simboli, cioè un "mondo possibile". Se $\alpha$ è vero nel modello $m$ si dice che $m$ soddisfa $\alpha$.

Definizione (conseguenza logica, entailment). La KB implica logicamente $\alpha$, e si scrive $KB \models \alpha$, se e solo se $\alpha$ è vero in tutti i modelli in cui la KB è vera.

Esempi. La KB con "Giovanni ha vinto" e "Maria ha vinto" implica "o Giovanni o Maria ha vinto". L'enunciato $x + y = 4$ implica $4 = x + y$. È una relazione tra enunciati, definita attraverso i modelli. È ciò che serve all'agente: dedurre solo ciò che è vero in ogni mondo compatibile con la KB.

Logica proposizionale

È la logica più semplice. I simboli proposizionali $P_1, P_2, \dots$ sono enunciati atomici, veri o falsi. Se $S, S_1, S_2$ sono enunciati lo sono anche:

• $\neg S$ (negazione);
• $S_1 \land S_2$ (congiunzione);
• $S_1 \lor S_2$ (disgiunzione);
• $S_1 \Rightarrow S_2$ (implicazione);
• $S_1 \Leftrightarrow S_2$ (doppia implicazione, biconditional).

La semantica è composizionale: la verità di un enunciato complesso in un modello si calcola da quella dei componenti con le tavole dei connettivi (verificate con Python).

Attenzione a $\Rightarrow$: $P \Rightarrow Q$ è falso solo se $P$ è vero e $Q$ falso. Dire $Pioggia \Rightarrow PavimentoBagnato$ vieta "piove e il pavimento è asciutto", ma ammette il pavimento bagnato senza pioggia (per un'altra causa). Se $P$ è falso l'implicazione è vera "a vuoto".

Equivalenze logiche. Due enunciati sono equivalenti ($\alpha \equiv \beta$) se hanno gli stessi modelli. Servono per trasformare le formule (tabella verificata con Python su tutte le righe):

Un enunciato è valido (tautologia) se è vero in tutti i modelli, soddisfacibile se è vero in almeno uno, insoddisfacibile se in nessuno. Legame fondamentale, usato dalla risoluzione:

$$KB \models \alpha \iff (KB \Rightarrow \alpha) \text{ è valida} \iff KB \land \neg\alpha \text{ è insoddisfacibile.}$$

(Se $KB \land \neg\alpha$ avesse un modello, quel modello renderebbe vera la KB e falsa $\alpha$, contro la definizione di $\models$.)

Enunciati del mondo del Wumpus

Siano $P_{i,j}$ "c'è un pozzo in $[i,j]$" e $B_{i,j}$ "c'è brezza in $[i,j]$". Sempre vero:

• $R_1:\ \neg P_{1,1}$ (nessun pozzo nella casella di partenza);
• $R_2:\ B_{1,1} \Leftrightarrow (P_{1,2} \lor P_{2,1})$ (brezza se e solo se c'è un pozzo adiacente);
• $R_3:\ B_{2,1} \Leftrightarrow (P_{1,1} \lor P_{2,2} \lor P_{3,1})$;
• e così via per ogni casella: una frase per casella.

Dalle percezioni, con l'agente in $[1,1]$ (nessuna brezza) e poi in $[2,1]$ (brezza):

• $R_4:\ \neg B_{1,1}$;
• $R_5:\ B_{2,1}$.

La KB è $R_1 \land R_2 \land R_3 \land R_4 \land R_5$. Domanda: $KB \models \neg P_{1,2}$?

Inferenza per model checking

Dalla definizione di $\models$ discende un algoritmo: (1) enumerare tutte le righe (assegnamenti ai simboli); (2) dove la KB è vera, controllare che anche $\alpha$ lo sia.

Esempio. I simboli sono $B_{1,1}, B_{2,1}, P_{1,1}, P_{1,2}, P_{2,1}, P_{2,2}, P_{3,1}$: $7$ simboli, $2^7 = 128$ modelli. La KB è vera solo in $3$:

1. $R_1$ impone $P_{1,1}$ falso; $R_4$ impone $B_{1,1}$ falso.
2. $R_2$ con $B_{1,1}$ falso: $P_{1,2} \lor P_{2,1}$ deve essere falso, quindi $P_{1,2} = P_{2,1} =$ F.
3. $R_5$ impone $B_{2,1}$ vero; $R_3$ allora richiede $P_{1,1} \lor P_{2,2} \lor P_{3,1}$ vero. Con $P_{1,1}$ falso resta $P_{2,2} \lor P_{3,1}$: le coppie $(P_{2,2}, P_{3,1})$ possibili sono $(0,1), (1,0), (1,1)$.

In tutti e $3$ i modelli $P_{1,2}$ è falso: $KB \models \neg P_{1,2}$ sì (e anche $\neg P_{2,1}$, $\neg P_{1,1}$). Invece $\neg P_{2,2}$ non è conseguenza (è falso nel secondo e nel terzo modello), e neppure $P_{3,1}$ (falso nel secondo): l'agente non può concludere nulla di sicuro su quelle caselle, ed è giusto non entrarci.

from itertools import product
syms = ["B11", "B21", "P11", "P12", "P21", "P22", "P31"]

def kb(m):
    return (not m["P11"]                                   # R1
            and m["B11"] == (m["P12"] or m["P21"])         # R2
            and m["B21"] == (m["P11"] or m["P22"] or m["P31"])  # R3
            and not m["B11"] and m["B21"])                 # R4, R5

modelli = [dict(zip(syms, v)) for v in product([False, True], repeat=7)]
buoni = [m for m in modelli if kb(m)]
print(len(modelli), len(buoni))                  # 128 3
print(all(not m["P12"] for m in buoni))          # True

Il model checking è corretto e completo ma costa $O(2^n)$ con $n$ simboli: inutilizzabile appena la KB cresce.

Inferenza per risoluzione

Idea: dimostrazione per assurdo. Per mostrare $KB \models \alpha$ si mostra che $KB \land \neg\alpha$ è insoddisfacibile (nessun mondo la rende vera): allora $\alpha$ è vera.

Forma normale congiuntiva (CNF)

Un letterale è un simbolo o la sua negazione; una clausola è una disgiunzione di letterali; la CNF (conjunctive normal form) è una congiunzione di clausole, per esempio $(A \lor \neg B) \land (B \lor \neg C \lor \neg D)$. Ogni enunciato proposizionale si converte in CNF con quattro passi.

Esempio sulla regola $R_2$: $B_{1,1} \Leftrightarrow (P_{1,2} \lor P_{2,1})$.

1. Eliminare $\Leftrightarrow$, sostituendo $\alpha \Leftrightarrow \beta$ con $(\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha)$: $$(B_{1,1} \Rightarrow (P_{1,2} \lor P_{2,1})) \land ((P_{1,2} \lor P_{2,1}) \Rightarrow B_{1,1}).$$
2. Eliminare $\Rightarrow$, sostituendo $\alpha \Rightarrow \beta$ con $\neg\alpha \lor \beta$: $$(\neg B_{1,1} \lor P_{1,2} \lor P_{2,1}) \land (\neg(P_{1,2} \lor P_{2,1}) \lor B_{1,1}).$$
3. Portare $\neg$ all'interno con De Morgan e doppia negazione: $\neg(P_{1,2} \lor P_{2,1}) = \neg P_{1,2} \land \neg P_{2,1}$: $$(\neg B_{1,1} \lor P_{1,2} \lor P_{2,1}) \land ((\neg P_{1,2} \land \neg P_{2,1}) \lor B_{1,1}).$$
4. Distribuire $\lor$ su $\land$ e appiattire: $(\neg P_{1,2} \land \neg P_{2,1}) \lor B_{1,1} = (\neg P_{1,2} \lor B_{1,1}) \land (\neg P_{2,1} \lor B_{1,1})$, quindi $$(\neg B_{1,1} \lor P_{1,2} \lor P_{2,1}) \land (\neg P_{1,2} \lor B_{1,1}) \land (\neg P_{2,1} \lor B_{1,1}).$$

Tre clausole. Con $R_3$, che ha tre simboli a destra, ne escono quattro: $(B_{2,1} \lor \neg P_{1,1}) \land (B_{2,1} \lor \neg P_{2,2}) \land (B_{2,1} \lor \neg P_{3,1}) \land (\neg B_{2,1} \lor P_{1,1} \lor P_{2,2} \lor P_{3,1})$ (controllato con sympy).

Regola di risoluzione

Regola di risoluzione. Date due clausole con letterali complementari $l_i$ e $m_j = \neg l_i$: $$\frac{l_1 \lor \dots \lor l_i \lor \dots \lor l_k \qquad m_1 \lor \dots \lor m_j \lor \dots \lor m_n}{l_1 \lor \dots \lor l_{i-1} \lor l_{i+1} \lor \dots \lor l_k \lor m_1 \lor \dots \lor m_{j-1} \lor m_{j+1} \lor \dots \lor m_n}$$ la risolvente contiene tutti i letterali tranne la coppia complementare.

Esempio: da $P_{1,3} \lor P_{2,2}$ e $\neg P_{2,2}$ si ottiene $P_{1,3}$. La regola è corretta: in ogni modello che rende vere le due clausole, $l_i$ e $\neg l_i$ non possono esserlo entrambi, quindi una delle due clausole deve essere vera grazie a un altro letterale, che compare nella risolvente.

Casi particolari: risolvendo $P$ e $\neg P$ si ottiene la clausola vuota $\square$, che è sempre falsa e quindi segnala una contraddizione. Una risolvente con una coppia complementare ($A \lor \neg A \lor \dots$) è una tautologia e si scarta.

Algoritmo

def risoluzione(kb_clausole, alfa_negata):
    clausole = set(kb_clausole) | {alfa_negata}   # clausole = frozenset di letterali
    while True:
        nuove = set()
        for ci, cj in coppie(clausole):
            for r in risolventi(ci, cj):          # una per ogni coppia complementare
                if not r:                         # clausola vuota
                    return True                   # KB |= alfa
                nuove.add(r)
        if nuove <= clausole:                     # niente di nuovo
            return False                          # KB non implica alfa
        clausole |= nuove

Termina perché i simboli sono finiti, quindi le clausole distinte sono finite. È corretta e completa per refutazione: se $KB \land \neg\alpha$ è insoddisfacibile, la clausola vuota viene prima o poi derivata.

Esempio: nessun pozzo in $[1,2]$

L'agente è in $[1,1]$ e non sente brezza. Si può inferire che non c'è un pozzo in $[1,2]$?

$$KB = (B_{1,1} \Leftrightarrow (P_{1,2} \lor P_{2,1})) \land \neg B_{1,1}, \qquad \alpha = \neg P_{1,2}.$$

Si deve mostrare che $KB \land \neg\alpha$ è insoddisfacibile. Clausole in CNF:

1. $C_3$ e $C_4$ (complementari $B_{1,1}$ e $\neg B_{1,1}$) danno $C_6 = \neg P_{1,2}$.
2. $C_6$ e $C_5$ (complementari $\neg P_{1,2}$ e $P_{1,2}$) danno $\square$.

Quindi $KB \land \neg\alpha$ è insoddisfacibile e $KB \models \neg P_{1,2}$, come col model checking. (Le altre coppie danno clausole sempre vere, per esempio $C_2$ con $C_1$ su $P_{2,1}$ dà $\neg B_{1,1} \lor P_{1,2} \lor B_{1,1}$, che si scarta.) Il vantaggio rispetto al model checking: si lavora solo sulle clausole rilevanti, senza enumerare $2^n$ modelli.

Pregi e limiti

• La logica proposizionale è dichiarativa (frammenti di sintassi corrispondono a fatti), ammette informazione parziale, disgiuntiva e negata (a differenza di molti database), è composizionale e indipendente dal contesto (a differenza del linguaggio naturale).
• Ha però espressività molto limitata: per dire "i pozzi causano brezza nelle caselle adiacenti" serve una frase per ogni casella. La Logica del primo ordine - unificazione, forward e backward chainingLogica del primo ordine (oggetti, relazioni, funzioni, quantificatori e errori tipici), sostituzioni, istanziazione universale ed esistenziale (Skolem), proposizionalizzazione e suoi limiti, unificazione con occur check, risoluzione nel primo ordine con conversione in CNF, esempio Criminal(West), clausole definite, forward e backward chaining, ingegneria della conoscenza.Logica del primo ordine - unificazione, forward e backward chaining → aggiunge oggetti, relazioni e quantificatori per scrivere una regola sola. Quando la KB ha solo clausole con al più un letterale positivo (clausole di Horn) l'inferenza si fa in modo molto più efficiente, ed è il caso di Prolog - fatti, regole, ricorsione, liste e cutProlog come logica del primo ordine ristretta alle clausole di Horn: fatti, regole, query, motore di inferenza (backward chaining in profondità con backtracking, ordine delle clausole), termini, unificazione e occur check, aritmetica con is, ricorsione, liste e operatore barra, length e append, cut verde e rosso, cut e fail, negazione come fallimento.Prolog - fatti, regole, ricorsione, liste e cut →.

Per ragionare con incertezza (se non si sa se il pozzo c'è, ma con quale probabilità) si passa a Incertezza - probabilità, regola di Bayes e indipendenza condizionataUn agente con osservazioni parziali non può usare regole logiche rigide ("mal di denti implica carie" è falso): usa la probabilità come grado di credenza e, con la teoria dell'utilità, sceglie l'azione con utilità attesa massima. Strumenti: distribuzione congiunta completa (tabella di $2^n$ valori), marginalizzazione $P(Y\mid e)=\alpha\sum_h P(Y,e,h)$ con costante di normalizzazione $\alpha=1/P(e)$, regola del prodotto $P(a,b)=P(a\mid b)P(b)$, regola di Bayes $P(\text{causa}\mid\text{effetto})=\frac{P(\text{effetto}\mid\text{causa})P(\text{causa})}{P(\text{effetto})}$ e indipendenza condizionata $P(a,b\mid c)=P(a\mid c)P(b\mid c)$, che permette di scomporre la congiunta in tabelle più piccole. Un test con sensibilità 73% e falsi positivi 12% su una malattia con prior 1/700 dà una probabilità a posteriori di appena 0,9%.Incertezza - probabilità, regola di Bayes e indipendenza condizionata →. I connettivi e le tavole di verità sono gli stessi dell'algebra booleana (Algebra di Boole - assiomi, teoremi e complemento di una funzioneL'algebra di Boole opera su variabili a due valori con AND, OR, NOT. Identità fondamentali (neutro, idempotenza, complemento, commutativa, associativa, distributiva in entrambe le forme), dualità (si scambiano AND/OR e 0/1), De Morgan $\overline{X+Y}=\overline X,\overline Y$, assorbimento $X+XY=X$, $X+\overline XY=X+Y$, adiacenza $XY+X\overline Y=X$, consenso $XY+\overline XZ+YZ=XY+\overline XZ$. Si dimostrano per induzione perfetta (tabella) o algebricamente. Il complemento di una funzione si ottiene con De Morgan o con duale + negazione dei letterali. Costo: numero di letterali o di ingressi delle porte.Algebra di Boole - assiomi, teoremi e complemento di una funzione →) e dei quantificatori in Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →.

Domande d'esame

1. La KB è $\{A \Rightarrow B,\ B \Rightarrow C,\ A\}$. Vale $KB \models C$? Sì: la KB è vera solo con $A$ vero, quindi $B$ vero, quindi $C$ vero, e in quell'unico modello $C$ è vera. Con la risoluzione: CNF $\neg A \lor B$, $\neg B \lor C$, $A$, più $\neg C$; $A$ con $\neg A \lor B$ dà $B$, con $\neg B \lor C$ dà $C$, con $\neg C$ dà $\square$.
2. Quanti modelli su $P, Q, R$ ha $(P \lor Q) \land (\neg P \lor R)$? $4$: con $P$ vero serve $R$ vero ($Q$ libero, $2$ modelli); con $P$ falso serve $Q$ vero ($R$ libero, $2$ modelli). Totale $2+2 = 4$ su $8$.
3. Risolvere $P \lor Q$ e $\neg P \lor R$. La risolvente è $Q \lor R$ (si elimina la coppia complementare $P$ e $\neg P$ e si uniscono i letterali restanti). Non è la clausola vuota, quindi qui non c'è contraddizione.
4. $(P \Rightarrow Q) \Rightarrow (Q \Rightarrow P)$ è valida? No: con $P$ falso e $Q$ vero l'antecedente $P \Rightarrow Q$ è vero e il conseguente $Q \Rightarrow P$ è falso, quindi l'intera formula è falsa. (Scambiare un'implicazione con il suo inverso è l'errore di "affermare il conseguente".)