Teoria dei calcolatori e algoritmi: Algoritmi per intelligenza artificiale
Dagli algoritmi di ricerca informata fino all’ottimizzazione su hardware specializzato, questo articolo offre una panoramica completa sugli strumenti fondamentali dell’intelligenza artificiale moderna. Una guida che unisce teoria, complessità computazionale e pratiche di implementazione, pensata per studenti, sviluppatori e ricercatori che vogliono approfondire le basi algoritmiche e le tecniche avanzate per il machine learning e il deep learning. Perfetta per chi desidera non solo capire il funzionamento degli algoritmi, ma anche applicarli in scenari reali, ottimizzando prestazioni ed efficienza.
- Come si implementano algoritmi di ricerca informata (A*, beam search)?
- Quali algoritmi si usano per machine learning (gradient descent, EM)?
- Come funzionano gli algoritmi per reti neurali (backpropagation)?
- Cos'è la complessità computazionale del training di ML models?
- Come si ottimizzano algoritmi AI per hardware specifico (GPU, TPU)?
Come si implementano algoritmi di ricerca informata (A*, beam search)?
Gli algoritmi di ricerca informata sfruttano informazioni euristiche per concentrarsi sulle porzioni più promettenti dello spazio di ricerca, riducendo drasticamente il numero di stati esplorati rispetto a metodi blind come BFS o DFS.
A* Search: mantiene:
Open list (min-heap o coda di priorità) con stati da esplorare, ordinati per f(n)=g(n)+h(n);
Closed list per stati già espansi e prevenire riespansioni;
g(n): costo accumulato dal nodo di partenza a n;
h(n): stima euristica del costo da n al goal.
Con h ammissibile (non sovrastima) A* garantisce ottimalità, e se h è consistente non serve riespansione. L’implementazione richiede struttura dati efficienti per open/closed (binary heap + hash set) e memorizzazione
di g, parent pointer e f per ogni stato.
Beam Search: è una best-first search troncata che, a ogni profondità, mantiene solo i k stati con i migliori valori di scoring (tipicamente g+h o probabilità normalizzata). Questo
limita memoria e tempo a O(k·d) dove d è la profondità massima, ma sacrifica completezza e ottimalità. Viene usata in:
decodifica sequenziale in NLP (modeli seq2seq, trasformer)
speech recognition
pianificazione robotica con vincoli di tempo
Per mitigare early stopping si applicano tecniche di dynamic beam resizing o length normalization dello score.
Quali algoritmi si usano per machine learning (gradient descent, EM)?
Nel machine learning due algoritmi di training fondamentali sono:
Gradient Descent: ottimizza una funzione di perdita L(θ) iterando:
θ ← θ − α ∇L(θ), dove α è il learning rate. Varianti:
Batch GD: calcola il gradiente su tutti i dati a ogni passo (stabile, lento);
SGD: gradiente su singolo esempio (rumoroso, veloce e capace di uscire da minimi locali);
Mini-batch: compromesso tra batch e SGD (2–512 esempi per batch).
Acceleratori: Momentum, Nesterov, RMSProp, Adam/AdamW con weight decay o L2 regularization. Tecniche di scheduling (step decay, cosine decay, one-cycle) e warm-up aiutano stabilità e convergenza rapida.
Expectation-Maximization (EM): ottimizza la verosimiglianza in presenza di variabili latenti:
E-step: stima le distribuzioni posteriori delle variabili latenti dato θ vecchio;
M-step: aggiorna θ massimizzando l’aspettativa calcolata.
Converge a massimo locale. Usato in Gaussian Mixture Models, HMM, clustering basato su latent variables. Richiede criteri di arresto su Δlog-likelihood o numero max di iterazioni.
Come funzionano gli algoritmi per reti neurali (backpropagation)?
La backpropagation calcola gradiente di rete multilivello con regola della catena:
Forward pass: calcolo attivazioni layer per layer, memorizzando input/pre-activations.
Loss: computo della funzione di perdita su output.
Backward pass: dalla loss verso input, si propaga il gradiente layer per layer:
δ^L = ∇_aL ∘ σ'(z^L), δ^l = ((W^{l+1})^T δ^{l+1}) ∘ σ'(z^l). I pesi si aggiornano con un ottimizzatore (SGD, Adam).
Stabilità e buone pratiche:
Inizializzazioni He/Xavier per evitare saturazione;
Normalizzazione: BatchNorm, LayerNorm per stabilità del gradiente;
Attivazioni ReLU/GELU per mitigare vanishing gradient;
Gradient clipping e loss scaling (mixed precision) per stabilità numerica;
Dropout, weight decay e data augmentation per regolarizzazione;
Checkpointing: salva attivazioni su disco per ridurre memoria.
Cos'è la complessità computazionale del training di ML models?
La complessità di training dipende da:
N: numero di esempi;
C: costo per esempio (FLOPs avanti+indietro ≈ 2–3× inferenza).
Per reti dense C ≈ O(P) con P parametri; per CNN C ≈ O(Σ_{layers}(channels_in·channels_out·kernel²·output_area)); per Transformer C ≈ O(L²·d) per self-attention (L=sequence length, d=dimension). Memoria: O(P + A) dove A ≈ batch_size×depth×activation_size. Combinando, per epoca è O(N·C), e total training O(E·N·C) con E epoche. Tecniche: early stopping, learning rate schedulers, curriculum learning per ridurre E e N effettivi.
Come si ottimizzano algoritmi AI per hardware specifico (GPU, TPU)?
L’ottimizzazione sfrutta parallelismo e acceleratori:
Parallelismo dati: batch dimensionale massivo per saturare SM (GPU) o TPU cores; Mixed precision: FP16/BF16 con loss scaling su Tensor Cores; Kernel fusion: combinare operazioni element-wise (XLA, TVM) per ridurre overhead di lancio; Memory: layout contiguo, prefetching, async data loading; memorizzazione su device.
Multi-device:
Data parallel con all-reduce (NCCL, Horovod);
Model parallel e pipeline parallel per layer molto grandi;
ZeRO & sharding di optimizer states (DeepSpeed, ZeRO-2/3);
Activation offload/checkpointing per ridurre memory footprint.
Per TPU: XLA compilation e static shape; per GPU: ottimizzare warp occupancy, evitare branch divergences, scegliere dimensioni di block/grid appropriate.
Faq
Qual è la differenza tra ricerca informata e non informata?
La ricerca non informata esplora lo spazio senza alcuna conoscenza del problema (es. BFS, DFS), mentre quella informata usa euristiche per guidare l’esplorazione verso il goal più velocemente e con meno stati visitati.
Quali sono i vantaggi dell’algoritmo A* rispetto a Dijkstra?
A* riduce lo spazio esplorato combinando costo accumulato e stima euristica, mantenendo l’ottimalità se l’euristica è ammissibile. Dijkstra invece considera solo i costi reali, senza guida euristica, risultando più lento.
In quali casi la beam search è preferibile?
Quando serve bilanciare qualità e velocità, come in traduzione automatica, NLP sequenziale o riconoscimento vocale, dove è più importante ottenere risultati plausibili in tempo reale piuttosto che soluzioni ottimali.
Perché lo stochastic gradient descent è così diffuso?
Lo SGD aggiorna i parametri usando mini-batch casuali, riducendo il costo computazionale per iterazione e introducendo rumore utile a sfuggire da minimi locali, migliorando generalizzazione e scalabilità.
Come funziona l’Expectation-Maximization (EM) in pratica?
Alterna due passi: E-step stima la distribuzione delle variabili latenti, M-step aggiorna i parametri massimizzando la log-verosimiglianza. Ripetuto fino a convergenza, trova soluzioni locali ottimali.
Qual è il ruolo della backpropagation nei modelli neurali?
La backpropagation calcola in modo efficiente i gradienti attraverso tutti i layer, usando la regola della catena, consentendo l’aggiornamento dei pesi tramite ottimizzatori come SGD e Adam.
Quali sono le principali cause del problema del vanishing gradient?
Attivazioni sigmoidi o tanh saturano per input grandi, annullando i gradienti nei layer profondi. Soluzioni includono ReLU/GELU, inizializzazioni corrette e tecniche di normalizzazione come BatchNorm.
Da cosa dipende la complessità del training di un modello?
Dal numero di esempi, dalla complessità computazionale del modello (FLOPs per forward e backward) e dal numero di epoche. Modelli come Transformer hanno complessità quadratica nella lunghezza della sequenza.
Come si riduce il tempo di training su dataset molto grandi?
Con tecniche come early stopping, data parallel su più GPU/TPU, curriculum learning, campionamento intelligente dei dati e compressione del modello per ridurre i calcoli per iterazione.
Quali strategie permettono di sfruttare al meglio GPU e TPU?
Batch di grandi dimensioni, mixed precision con FP16/BF16, kernel fusion, sharding degli stati dell’ottimizzatore, pipeline parallelism e compilazione con XLA/TVM per ridurre overhead.
