FormularioArtificial Intelligence and Machine Learning: definizioni, teoremi e formule delle note, in ordine di capitolo

1. Introduzione e agenti intelligenti

Intelligenza artificiale - definizioni, test di Turing e storia

Definizione. L'intelligenza artificiale è lo studio di come far fare ai computer cose in cui, al momento, gli umani sono migliori (Rich e Knight).

Definizione. Comportamento razionale = "fare la cosa giusta", cioè quella da cui ci si aspetta il massimo raggiungimento degli obiettivi, date le informazioni disponibili.

Agenti intelligenti - ambienti, PEAS e tipi di agente

Definizione. Un agente è un'entità che percepisce il proprio ambiente tramite sensori e agisce su di esso tramite attuatori. Astrattamente è una funzione dalle sequenze di percezioni (percept sequences, la storia di tutto ciò che ha percepito) alle azioni: $$f : P^\ast \to A .$$

Definizione (agente razionale). Per ogni possibile sequenza di percezioni, un agente razionale seleziona un'azione da cui ci si aspetta di massimizzare la propria misura di prestazione (performance measure), date le evidenze fornite dalla sequenza di percezioni e la conoscenza incorporata nell'agente.

2. Algoritmi di ricerca

Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata

Definizione. Un problema è definito da:

• l'insieme degli stati possibili (lo spazio degli stati, un grafo);
• lo stato iniziale (per esempio "in Arad");
• uno o più stati obiettivo, descritti in modo esplicito ("in Bucarest") o implicito (NoDirt(x), nessuna sporcizia), con un test dell'obiettivo is_goal(s);
• le azioni: Actions(s) è l'insieme delle azioni applicabili in $s$ (Actions(Arad) = {verso Timisoara, verso Zerind, verso Sibiu});
• il modello di transizione: Result(s, a) è lo stato raggiunto applicando $a$ in $s$ (Result(Arad, verso Zerind) = Zerind);
• la funzione di costo delle azioni $c(s, a, s')$, supposta $\ge 0$, e il costo del cammino come somma dei costi dei passi (somma di distanze, numero di azioni eseguite, ecc.).

Una soluzione è una sequenza di azioni che porta dallo stato iniziale a uno stato obiettivo; una soluzione ottima è quella di costo minimo.

Definizione. Uno stato è (la rappresentazione di) una configurazione fisica. Un nodo è una struttura dati che fa parte dell'albero di ricerca e contiene: stato, genitore (parent), azione che l'ha generato, figli, profondità $d$ e costo del cammino $g$.

Ricerca informata - greedy best-first, A* ed euristiche

Definizione. La ricerca greedy best-first espande il nodo che sembra più vicino all'obiettivo: $f(n) = h(n)$, con $h(n)$ stima del costo da $n$ all'obiettivo più vicino.

Definizione. A∗ usa la funzione di valutazione $$f(n) = g(n) + h(n),$$ dove $g(n)$ è il costo finora speso per arrivare a $n$, $h(n)$ la stima del costo restante e $f(n)$ la stima del costo totale di un cammino che passa per $n$. Idea: evitare di espandere cammini già costosi.

Definizione. Un'euristica $h$ è ammissibile se $h(n) \ge 0$, $h(G) = 0$ per ogni obiettivo $G$ e non sovrastima mai il costo vero: $h(n) \le h^\ast(n)$, con $h^\ast(n)$ costo del cammino ottimo da $n$ all'obiettivo. È consistente (o monotona) se per ogni nodo $n$, ogni azione $a$ e successore $n'$ $$h(n) \le c(n, a, n') + h(n').$$

Teorema. Se $h$ è ammissibile, A∗ (versione ad albero) è ottima. Se $h$ è consistente, anche la versione su grafo con tabella dei raggiunti è ottima.

Definizione (hill climbing). L'ascesa del colle (hill climbing, anche greedy local search) parte da uno stato e passa sempre al vicino di valore più alto; si ferma quando nessun vicino è migliore e restituisce lo stato corrente, un massimo locale.

3. Logica (corso da 9 CFU)

Agenti logici e logica proposizionale - inferenza e risoluzione

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.

Logica del primo ordine - unificazione, forward e backward chaining

Definizione (sostituzione). Una sostituzione $\theta = \{v_1/t_1, \dots, v_n/t_n\}$ assegna un termine a ciascuna variabile. Dato un enunciato $S$, $S\theta$ è il risultato di applicare $\theta$ a $S$.

Definizione (unificazione). $Unify(\alpha, \beta) = \theta$ con $\mathrm{Subst}(\theta, \alpha) = \mathrm{Subst}(\theta, \beta)$. Se non esiste $\theta$ l'unificazione fallisce.

4. Incertezza e reti bayesiane

Incertezza - probabilità, regola di Bayes e indipendenza condizionata

Definizione. Teoria delle decisioni (decision theory) = teoria della probabilità + teoria dell'utilità. Ogni stato ha un'utilità (quanto è desiderabile). Un agente è razionale se sceglie l'azione con utilità attesa massima, cioè la media delle utilità dei possibili esiti pesata con le loro probabilità: $EU(a)=\sum_s P(s\mid a)\,U(s)$.

Teorema. Se $b_1,\dots,b_N$ sono eventi mutuamente esclusivi ed esaustivi, $P(a)=\sum_k P(a,b_k)=\sum_k P(a\mid b_k)P(b_k)$.

Formula (inferenza per marginalizzazione). Sia $\mathbf X$ l'insieme di tutte le variabili, $\mathbf Y$ le variabili di interrogazione (query), $\mathbf E$ le variabili di evidenza con valori osservati $\mathbf e$ e $\mathbf H=\mathbf X-\mathbf Y-\mathbf E$ le variabili nascoste. Allora $$\mathbf P(\mathbf Y\mid\mathbf e)=\alpha\,\mathbf P(\mathbf Y,\mathbf e)=\alpha\sum_{\mathbf h}\mathbf P(\mathbf Y,\mathbf e,\mathbf h).$$

Teorema (regola di Bayes). $$P(b\mid a)=\frac{P(a\mid b)\,P(b)}{P(a)}\qquad\Longleftrightarrow\qquad \mathbf P(\text{causa}\mid\text{effetto})=\frac{\mathbf P(\text{effetto}\mid\text{causa})\,\mathbf P(\text{causa})}{P(\text{effetto})}.$$

Definizione (indipendenza). $a$ e $b$ sono indipendenti se $P(a\mid b)=P(a)$, o equivalentemente $P(b\mid a)=P(b)$, o $P(a,b)=P(a)P(b)$. Vedi Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →.

Definizione (indipendenza condizionata). $a$ e $b$ sono condizionalmente indipendenti dato $c$ se $P(a\mid b,c)=P(a\mid c)$, o equivalentemente $P(b\mid a,c)=P(b\mid c)$, o $P(a,b\mid c)=P(a\mid c)P(b\mid c)$. Vedi Eventi indipendenti e indipendenza condizionataA e B sono indipendenti se P(AB) = P(A)P(B), cioè (se P(B) > 0) P(A | B) = P(A): sapere B non cambia la probabilità di A. Se A, B sono indipendenti lo sono anche A e Bᶜ. Tre eventi sono indipendenti se lo sono a coppie E P(ABC) = P(A)P(B)P(C): l'indipendenza a coppie non basta. Prove ripetute indipendenti: le probabilità si moltiplicano. Indipendenza condizionata a F: P(AB | F) = P(A | F)P(B | F); non implica l'indipendenza (due lanci della stessa moneta scelta a caso). Eventi disgiunti con probabilità positive non sono mai indipendenti.Eventi indipendenti e indipendenza condizionata →.

Reti bayesiane - semantica, indipendenze e inferenza esatta

Definizione (scomposizione in prodotto). $$P(x_1,\dots,x_n)=\prod_{i=1}^n P\big(x_i\mid \text{parents}(X_i)\big).$$

Definizione (rete bayesiana). Un DAG (grafo diretto senza cicli) in cui:

• ogni nodo è una variabile aleatoria;
• un arco $X\to Y$ dice che $X$ è genitore di $Y$ (di solito: $X$ è una causa di $Y$);
• ogni nodo ha una tabella delle probabilità condizionate (conditional probability table, CPT) $\mathbf P(X_i\mid\text{Parents}(X_i))$; un nodo senza genitori ha una distribuzione a priori.

La rete rappresenta la congiunta come prodotto delle CPT. Topologia + CPT = rappresentazione compatta, di solito semplice da costruire anche per non esperti.

Inferenza approssimata nelle reti bayesiane - campionamento

Definizione (Markov blanket). Il Markov blanket di un nodo $X$ è l'insieme dei suoi genitori, dei suoi figli e degli altri genitori dei suoi figli. Dato il suo blanket, $X$ è condizionalmente indipendente da tutti gli altri nodi della rete.

Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothing

Definizione (HMM del primo ordine). Hidden Markov model: stati nascosti $X_t$ che formano una catena di Markov e osservazioni $E_t$ figlie dello stato. Distribuzione congiunta, con prior $\mathbf P(X_0)$: $$P(x_0,x_{1:t},e_{1:t})=P(x_0)\prod_{i=1}^t P(x_i\mid x_{i-1})\,P(e_i\mid x_i).$$ In senso stretto l'HMM ha un'unica variabile di stato discreta (le evidenze possono essere più d'una).

Apprendimento delle reti bayesiane - parametri e struttura

Formula (stima ML). Per un nodo $B$ con genitori $A,C$: $$P(B=b_i\mid A=a_j,C=c_k)\approx\frac{N_{i,j,k}}{N_{j,k}},$$ dove $N_{i,j,k}$ conta le righe con $B=b_i,A=a_j,C=c_k$ e $N_{j,k}$ quelle con $A=a_j,C=c_k$ (qualunque $B$).

Formula (Laplace). Variabile discreta con $k$ valori, $N$ campioni, in cui $x_i$ compare $m$ volte: $$P(x_i)=\frac{1+m}{k+N}.$$ (Per una CPT: $N$ = righe con quella configurazione dei genitori.)

Formula (BIC). $$\text{BIC}(m)=\log P(D\mid m)-\frac{|m|\,\log|D|}{2},$$ con $|D|$ numero di campioni e $|m|$ numero di parametri indipendenti del modello. Il secondo termine penalizza la complessità. Si sceglie il massimo.

5. Inferenza causale (corso da 9 CFU)

Inferenza causale - modelli causali strutturali e scala della causalità

Definizione (SCM, structural causal model). Un SCM è formato da

• un insieme di variabili esogene $U$: non dipendono da nessun'altra variabile del modello (sono i fattori esterni, il «rumore»);
• un insieme di variabili endogene $V$: ciascuna è determinata dalle altre;
• un insieme di funzioni $F=\{f_v\}_{v\in V}$, una per ogni variabile endogena, $v=f_v(\text{pa}(v),u_v)$;

e (implicitamente) da un grafo con una freccia da ogni variabile che compare in $f_v$ verso $v$.

Definizione (causa). $X$ è causa diretta di $Y$ se compare nella funzione $f_Y$. $X$ è causa di $Y$ se è causa diretta di $Y$ o di un'altra causa di $Y$ (definizione ricorsiva).

Definizione (d-separazione). Sia $Z$ l'insieme delle variabili condizionanti. $X$ e $Y$ sono d-separate da $Z$ se ogni cammino $p$ tra loro (di qualunque verso delle frecce) soddisfa almeno una condizione:

• $p$ contiene una catena $A\to B\to C$ o un fork $A\leftarrow B\to C$ con $B\in Z$;
• $p$ contiene un collider $A\to B\leftarrow C$ e né $B$ né i suoi discendenti sono in $Z$.

In tal caso $X\perp\!\!\!\perp Y\mid Z$.

Interventi e operatore do - criterio backdoor e aggiustamento

Definizione (operatore do). $do(X=x)$ indica che si forza $X$ al valore $x$ (per esempio con un esperimento), indipendentemente da ciò che $X$ avrebbe fatto spontaneamente. $P(Y=y\mid do(X=x))$ è la probabilità di $y$ nel mondo in cui $X$ è stato imposto.

Definizione (intervento come chirurgia). L'intervento $do(X=x)$ trasforma l'SCM $M$ in un modello $M_x$ in cui la funzione di $X$ è sostituita dalla costante $X=x$ e tutte le frecce entranti in $X$ sono tolte. Le altre funzioni restano invariate. Si ha $$P(y\mid do(x))=P_{M_x}(y\mid x).$$

Formula di aggiustamento (regola dell'effetto causale). $$P(y\mid do(x))=\sum_{z\in\Lambda}P(y\mid x,z)\,P(z),$$ con $\Lambda$ l'insieme dei genitori di $X$.

Definizione (ACE). Per un trattamento $X\in\{1,0\}$ e un esito $Y=1$, $$ACE=P(Y=1\mid do(X=1))-P(Y=1\mid do(X=0)).$$ $ACE>0$: il trattamento ha effetto positivo; $ACE<0$ negativo; $ACE=0$ neutro.

Definizione (cammino backdoor). Un cammino backdoor tra $X$ e $Y$ è un qualunque cammino da $X$ a $Y$ che inizia con una freccia entrante in $X$ (passa per i genitori di $X$). Si blocca condizionando su una catena o un fork, oppure è già bloccato da un collider non condizionato (d-separazione: Inferenza causale - modelli causali strutturali e scala della causalitàI dati e la distribuzione congiunta da soli non dicono quali variabili causano quali: lo mostrano il paradosso di Simpson (la medicina funziona in ogni sottogruppo ma sembra peggiorare la popolazione) e il fatto che reti bayesiane diverse (A→B e B→A) descrivono la stessa congiunta. Serve un modello causale: un modello causale strutturale (SCM) ha variabili esogene U, endogene V e funzioni $v_i=f_i(\text{genitori},u_i)$; il suo grafo è la rete causale, e una rete causale è una rete bayesiana in cui le frecce sono cause. Le tre strutture elementari decidono l'indipendenza: catena $A\to B\to C$ e fork $A\leftarrow B\to C$ si bloccano osservando B, il collider $A\to B\leftarrow C$ si blocca se B e i suoi discendenti NON sono osservati (osservarlo crea dipendenza, explaining away). d-separazione: X e Y sono separati da Z se ogni cammino è bloccato; allora $X\perp!!!\perp Y\mid Z$. La scala della causalità (Pearl): associazione $P(y\mid x)$, intervento $P(y\mid do(x))$, controfattuali. Argomento del corso da 9 CFU.Inferenza causale - modelli causali strutturali e scala della causalità →).

Definizione (criterio backdoor). Un insieme $S$ di variabili soddisfa il criterio backdoor per $(X,Y)$ se

1. blocca ogni cammino backdoor tra $X$ e $Y$;
2. non contiene alcun discendente di $X$.

Formula di aggiustamento con il criterio backdoor. Se $S$ soddisfa il criterio backdoor, $$P(y\mid do(x))=\sum_sP(y\mid x,s)\,P(s),$$ con $s$ che varia su tutte le combinazioni di valori delle variabili di $S$.

Formula front-door. $$P(y\mid do(x))=\sum_zP(z\mid x)\sum_{x'}P(y\mid z,x')\,P(x').$$ Criterio: $S$ soddisfa il front-door per $(X,Y)$ se (1) blocca ogni cammino diretto da $X$ a $Y$; (2) non ci sono cammini backdoor non bloccati da $X$ a $S$; (3) tutti i cammini backdoor da $S$ a $Y$ sono bloccati da $X$. L'espressione non dipende da $U$.

Definizione (CDE). Per un valore fissato $z$: $$CDE(z)=P(y\mid do(x),do(z))-P(y\mid do(x^*),do(z)).$$ L'effetto diretto medio (ADE) si ottiene mediando i $CDE$ sui valori di $Z$.

Controfattuali e scoperta causale

Definizione (SCM lineare). Le equazioni strutturali sono lineari, per esempio $$X=U_X,\quad Z=aX+U_Z,\quad W=bX+cZ+U_W,\quad Y=dZ+eW+U_Y.$$ I coefficienti strutturali (di cammino) $a,b,c,d,e$ quantificano l'effetto diretto di un genitore sul figlio.

6. Processi decisionali di Markov

Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iteration

Definizione (utilità attesa). Se l'azione $a$ porta nello stato $s'$ con probabilità $P(\text{RESULT}(a)=s')$ e $U(s')$ misura quanto è desiderabile $s'$ (di solito normalizzata tra 0 e 1, ma può essere in euro, punti, ...), l'utilità attesa dell'azione è $$EU(a)=\sum_{s'}P(\text{RESULT}(a)=s')\,U(s').$$ Il principio di massima utilità attesa (MEU) sceglie l'azione con $EU$ più alta. È un Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → (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 → per le probabilità).

Definizione (MDP). Problema decisionale sequenziale in un ambiente completamente osservabile e stocastico, dato da

• un insieme di stati $S$, con stato iniziale $s_0$;
• un insieme di azioni $A(s)$ per ogni stato;
• un modello di transizione $P(s'\mid s,a)$: probabilità di arrivare in $s'$ eseguendo $a$ in $s$;
• una funzione di ricompensa $R(s,a,s')$, numero (positivo o negativo) assegnato alla transizione.

La proprietà di Markov dice che $P(s'\mid s,a)$ non dipende dalla storia passata.

Definizione (equazione di Bellman). L'utilità di uno stato è la ricompensa attesa della prossima transizione più l'utilità scontata dello stato successivo, supponendo di scegliere l'azione ottima: $$U(s)=\max_{a\in A(s)}\sum_{s'}P(s'\mid s,a)\,\big[R(s,a,s')+\gamma\,U(s')\big].$$ La somma da massimizzare è la funzione azione-utilità (Q-function) $$Q(s,a)=\sum_{s'}P(s'\mid s,a)\,\big[R(s,a,s')+\gamma\,U(s')\big],\qquad U(s)=\max_aQ(s,a).$$ La politica ottima si legge da $U$: $\ \pi^*(s)=\arg\max_aQ(s,a)$.

Definizione (stato di credenza, belief state). Distribuzione di probabilità $b$ sugli stati: $b(s)=P(\text{stato}=s)$. Si risolve il problema come un normale MDP i cui stati sono le credenze.

7. Machine learning e deep learning

Apprendimento automatico nell'IA - supervisionato, SVM e valutazione

Definizione. Dato un training set di $N$ esempi $(x_1,y_1),\dots,(x_N,y_N)$ generati da una funzione sconosciuta $y=f(x)$, si cerca un'ipotesi $h$ (un modello dei dati) che approssimi $f$. Gli $y_i$ si chiamano ground truth. Un'ipotesi generalizza bene se predice con accuratezza le uscite di esempi non ancora visti: la sua qualità si misura sul test set, non sul training set.

Definizione. Un albero di decisione mappa un vettore di valori di attributi in un'uscita con una sequenza di test, dalla radice a una foglia: ogni nodo interno testa un attributo, i rami sono i suoi valori, le foglie danno la decisione. Dettagli, Gini e CART in Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione →.

Deep learning - reti profonde, CNN e addestramento con Keras

Definizione (unità). Un'unità (neurone) calcola la somma pesata dei suoi ingressi, $in_j=w_{0,j}+\sum_iw_{i,j}\,a_i$ (con $w_0$ il peso del bias, ingresso fisso $+1$), e applica una funzione di attivazione non lineare $g_j$: $a_j=g_j(in_j)$. Se $g$ fosse lineare la combinazione di più unità sarebbe ancora lineare.