Intelligenza Artificiale: Concetti e Algoritmi

Flashcard di terminologia basate sulle dispense del corso di Intelligenza Artificiale, comprensive di algoritmi di ricerca, logica, probabilità e reti neurali.

Intelligenza Artificiale (AI)

Campo vasto e interdisciplinare che integra logica, probabilità, percezione e ragionamento, basandosi oggi sull'estrazione di informazioni dai dati (information mining).

Test di Turing

Definizione di AI secondo cui un essere umano non deve riuscire a distinguere se sta interagendo con una macchina o con un altro essere umano.

Agenti razionali

Sistemi che agiscono in modo da massimizzare il miglior risultato atteso date le conoscenze attuali e le percezioni ricevute.

Pattern Recognition (PR)

Sottodominio dell'AI dedicato al riconoscimento di schemi ricorrenti (pattern) all'interno dei dati.

Machine Learning (ML)

Processo di apprendimento automatico tramite il quale un sistema migliora le proprie prestazioni partendo da esempi.

Deep Learning (DL)

Sottocategoria del Machine Learning che utilizza reti neurali con molti neuroni e strati, capaci di apprendere in modo autonomo.

Agente intelligente

Sistema che percepisce l'ambiente tramite sensori e agisce su di esso attraverso attuatori.

Funzione agente

Funzione descritta matematicamente come $F: P^* \rightarrow a$, che associa le sequenze percettive passate a un'azione specifica.

PEAS

Approccio alla progettazione di agenti razionali basato su quattro elementi: Performance measure, Environment, Actuators e Sensors.

Ambiente Deterministico

Ambiente in cui lo stato successivo è completamente determinato dallo stato corrente e dall'azione eseguita dall'agente.

Ambiente Stocastico

Ambiente non deterministico in cui le conseguenze delle azioni sono governate da probabilità.

Simple Reflex Agents

Agenti che scelgono l'azione basandosi esclusivamente sulla percezione corrente, ignorando la storia passata; funzionano solo in ambienti completamente osservabili.

Learning Agents

Agenti capaci di migliorare le proprie decisioni basandosi sull'esperienza, composti da elemento esecutivo, elemento d'apprendimento, elemento critico e generatore di problemi.

Frontiera

Insieme dei nodi in un algoritmo di ricerca che separa i nodi già visitati da quelli ancora da esplorare.

Completezza

Parametro di valutazione di un algoritmo che garantisce il ritrovamento di una soluzione se essa esiste, o la segnalazione di fallimento in caso contrario.

Breadth-first search (BFS)

Ricerca in ampiezza che espande tutti i nodi di un livello prima di passare al successivo, garantendo l'ottimalità se tutti i costi sono identici.

Uniform Cost Search (Dijkstra)

Algoritmo che espande il nodo con il costo di cammino minimo, garantendo l'ottimalità se i costi sono maggiori di una costante $\text{epsilon}$ positiva.

Iterative Deepening Search

Strategia che combina i vantaggi di BFS e DFS, incrementando gradualmente il limite di profondità; è l'unico algoritmo di ricerca non informata sempre completo.

Funzione Euristica ($h(n)$)

Funzione che stima il costo del cammino meno oneroso da un nodo corrente $n$ allo stato obiettivo.

Ricerca Greedy

Strategia di ricerca informata che espande il nodo che sembra più vicino all'obiettivo basandosi solo sulla funzione euristica $h(n)$, senza considerare i costi accumulati.

Ricerca A*

Algoritmo di ricerca best-first che valuta i nodi usando $f(n) = g(n) + h(n)$, dove $g(n)$ è il costo effettivo e $h(n)$ è la stima euristica.

Euristica Ammissibile

Un'euristica che non sovrastima mai il costo reale per raggiungere l'obiettivo; garantisce l'ottimalità dell'algoritmo A*.

Euristica Consistente

Proprietà per cui la stima del costo da un nodo non è mai superiore al costo per raggiungere un successore più la stima del successore stesso.

Hill Climbing

Algoritmo di ricerca locale che analizza solo gli stati vicini e si muove verso quello con valore più alto della funzione obiettivo; può bloccarsi in massimi locali.

Simulated Annealing

Algoritmo ispirato alla metallurgia che accetta mosse peggiorative con una certa probabilità per uscire dai massimi locali, basandosi sulla costante di Boltzmann e una temperatura $T$ decrescente.

Algoritmi Genetici

Algoritmi di ricerca locale ispirati alla selezione naturale che utilizzano popolazioni di individui, crossover e mutazioni per generare nuove soluzioni migliorate.

Algoritmo Minimax

Algoritmo perfetto per giochi deterministici a informazione completa dove MAX massimizza l'utilità e MIN cerca di minimizzarla.

$$\text{alpha-beta pruning}$$

Tecnica di ottimizzazione per Minimax che taglia i rami dell'albero che non possono influenzare la decisione finale, riducendo la complessità temporale fino a $O(b^{m/2})$.

Expected Minimax

Estensione del Minimax per giochi non deterministici che gestisce i nodi di chance calcolando la media pesata dei valori dei figli in base alla probabilità.

Stato di Credenza

Rappresentazione di tutte le situazioni possibili in cui un agente potrebbe trovarsi in ambienti a informazione parziale o probabilistica.

Knowledge Base (KB)

Insieme di formule in un linguaggio formale (sentences) che definiscono le conoscenze specifiche di un dominio possedute da un agente logico.

Entailment ($KB \neq \text{alpha}$)

Concetto di implicazione logica in cui se una sentence $\text{alpha}$ è vera in tutti i modelli in cui la base di conoscenza è vera, allora la KB implica $\text{alpha}$.

Forward Chaining

Algoritmo di inferenza data-driven che parte dalle informazioni note nella KB per dedurre tutte le possibili conclusioni.

Backwards Chaining

Algoritmo di inferenza goal-driven che parte da una query cercata e risale alle condizioni necessarie nella KB per soddisfarla.

Clausole di Horn

Disgiunzione di letterali con al massimo un letterale positivo, fondamentali per rendere l'inferenza efficiente e lineare.

Quantificatore Universale ($\forall$)

Simbolo della logica del prim'ordine utilizzato per esprimere che una proprietà è vera per ogni elemento del dominio.

Unificazione

Processo nella logica del prim'ordine che consiste nel trovare sostituzioni che rendono identiche due espressioni logiche diverse.

PROLOG

Linguaggio di programmazione logica basato su fatti e regole che utilizza la concatenazione all'indietro in profondità per eseguire query.

Teorema di Bayes

Formula probabilistica $P(b|a) = \frac{P(a|b)P(b)}{P(a)}$ utilizzata per aggiornare la probabilità di una causa dato un effetto osservato.

Percettrone

Uno dei primi modelli di rete neurale artificiale, funge da classificatore lineare calcolando una somma pesata degli input più un bias.

Backpropagation

Algoritmo di addestramento per reti neurali multistrato che propaga l'errore registrato in uscita all'indietro per aggiornare i pesi dei livelli nascosti.

Overfitting

Fenomeno in cui una rete neurale apprende i dati di addestramento così bene da non riuscire più a generalizzare correttamente su nuovi dati.

Self-Organizing Maps (SOM)

Reti neurali con apprendimento non supervisionato utilizzate per mappare e visualizzare dati complessi riducendone la dimensionalità.

Reti di Hopfield

Modello di rete neurale che funge da memoria correttiva, capace di recuperare pattern memorizzati partendo da input incompleti o danneggiati.