Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
Insiemi, sottoinsiemi, operazioni, prodotto cartesiano, relazioni, equivalenze e ordini — con diagrammi di Venn, la matrice di una relazione e a che cosa serve tutto questo nell’intelligenza artificiale.
Serie Basi di IA Parte 5 di 52
- Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
- Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
- Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
- Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
- Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
- Funzioni e applicazioni: perché ogni modello di IA è una funzione
- Logica e dimostrazioni: le regole con cui si ragiona nell’IA
- Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
- Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
- Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
- Discesa del gradiente: come impara un modello
- Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
- Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
- Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
- Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
- Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
- Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
- Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
- Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
- Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
- Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
- Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
- Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
- Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
- Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
- Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
- Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
- Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
- Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
- Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
- Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
- Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
- Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
- Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
- Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
- Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
- Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
- Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
- Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
- Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
- Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
- Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
- Prompt, contesto e RAG: come dare a un modello le informazioni giuste
- Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
- Reti generative avversarie (GAN): il falsario contro il detective
- Modelli di diffusione: come il rumore puro diventa un’immagine
- Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
- Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
- Policy gradient e PPO: imparare direttamente la politica
- Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
- Programmare con agenti IA: incarico, test e controllo
- Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare
Programma completo della serie 52 di 83 argomenti pubblicati
- Che cosa sono un insieme, un sottoinsieme e il prodotto cartesiano — e perché il numero di sottoinsiemi cresce in modo esponenziale.
- Che cos’è una relazione, quali proprietà ha e come disegnarla come matrice e come grafo.
- Perché la classificazione è una partizione in classi di equivalenza e un modello è una funzione — una relazione speciale.
Utile sapere prima: Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
Insiemi e relazioni sono i mattoncini con cui si costruisce quasi ogni definizione nell’IA. Lo spazio degli stati è un insieme di stati, le transizioni tra di essi sono relazioni, i dati di addestramento sono un insieme di coppie e la classificazione ripartisce gli input in classi. Chi capisce questi due concetti legge le definizioni delle parti successive come un testo normale.
La notazione dei simboli (∈, ⊆, ∪, ×) l’abbiamo vista nella parte precedente. Qui andremo sotto la superficie: che cosa significano esattamente, quali proprietà hanno e a che cosa servono nell’intelligenza artificiale.
1. Che cos’è un insieme
Definizione — insieme ed elemento
Un insieme è una collezione di oggetti distinti tra loro. Questi oggetti li chiamiamo elementi dell’insieme.
La scrittura x ∈ A significa «x è un elemento dell’insieme A», la scrittura x ∉ A «x non è un elemento di A».
Un insieme è un sacchetto in cui metti delle cose. Ci interessa solo che cosa c’è nel sacchetto — non in che ordine ce l’hai messo, né quante volte. Due biglie dello stesso colore, per l’insieme, sono un solo colore.
Un insieme si scrive o elencando i suoi elementi tra parentesi graffe — A = {1, 2, 3} oppure {↑, →, ↓, ←} — o tramite una proprietà che gli elementi soddisfano: {x ∈ ℕ : x è pari}. Per A = {1, 2, 3} vale 2 ∈ A e 5 ∉ A. La scrittura tramite proprietà sa descrivere anche insiemi infiniti e nell’IA si usa quasi sempre: «l’insieme di tutti gli stati da cui si può raggiungere l’obiettivo».
Definizione — uguaglianza di insiemi
Gli insiemi A e B sono uguali, A = B, quando hanno esattamente gli stessi elementi: ∀x : (x ∈ A ⇔ x ∈ B).
Due sacchetti sono uguali quando contengono le stesse cose. Per questo {1, 2, 2} = {2, 1} = {1, 2}: non contano né l’ordine né le ripetizioni.
Definizione — cardinalità e insieme vuoto
La cardinalità |A| di un insieme finito A è il numero dei suoi elementi.
L’insieme vuoto ∅ è l’insieme che non ha alcun elemento; |∅| = 0.
La cardinalità è la risposta alla domanda «quanta roba c’è nel sacchetto»: |{1, 2, 3}| = 3. L’insieme vuoto è un sacchetto vuoto — è pur sempre un insieme, solo che dentro non c’è niente.
2. Sottoinsiemi e insieme delle parti
Da un insieme possiamo sceglierne di più piccoli. Per farlo ci servono tre concetti che si basano l’uno sull’altro: il sottoinsieme, il sottoinsieme proprio e l’insieme delle parti.
Definizione — sottoinsieme
Un insieme A è un sottoinsieme di un insieme B, e si scrive A ⊆ B, quando ogni elemento di A è anche elemento di B: ∀x : x ∈ A ⇒ x ∈ B.
Un sottoinsieme è una scelta dal sacchetto: prendi alcune cose da B e le metti in un sacchetto più piccolo A. Non puoi aggiungere ad A niente che non sia in B. Così {1, 3} ⊆ {1, 2, 3}, ma {1, 4} ⊄ {1, 2, 3}, perché 4 non è nell’insieme di partenza. Ogni insieme è sottoinsieme di sé stesso e l’insieme vuoto è sottoinsieme di qualsiasi insieme.
Definizione — sottoinsieme proprio
A è un sottoinsieme proprio di B, e si scrive A ⊂ B, quando A ⊆ B e allo stesso tempo A ≠ B.
Un sottoinsieme proprio è una scelta in cui manca almeno qualcosa. {1, 3} ⊂ {1, 2, 3}, ma {1, 2, 3} non è sottoinsieme proprio di sé stesso — hai preso proprio tutto.
Definizione — insieme delle parti
L’insieme delle parti (insieme potenza) 𝒫(A) è l’insieme i cui elementi sono tutti i sottoinsiemi di A: 𝒫(A) = {S : S ⊆ A}.
Teorema. Per un insieme finito A vale |𝒫(A)| = 2|A|.
L’insieme delle parti è l’elenco di tutte le scelte che si possono fare dal sacchetto — compresa la scelta vuota e la scelta di tutto. Perché sono 2n: per ogni elemento decidi se metterlo nella scelta oppure no. Sono due possibilità per ogni elemento: per tre elementi 2 · 2 · 2 = 8, per dieci elementi già 1024.
Per A = {a, b, c} si ha 𝒫(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} — in tutto 8 sottoinsiemi. Questa crescita esponenziale la incontrerai nell’IA a ogni passo. Un modello che deve scegliere quali di 50 caratteristiche usare ha 250 scelte — oltre un milione di miliardi di possibilità. Per questo la selezione delle caratteristiche non si fa provando tutte le combinazioni.
3. Operazioni tra insiemi
Definizione — unione, intersezione, differenza, complementare
A ∪ B = {x : x ∈ A ∨ x ∈ B} — unione,
A ∩ B = {x : x ∈ A ∧ x ∈ B} — intersezione,
A ∖ B = {x : x ∈ A ∧ x ∉ B} — differenza,
Ac = U ∖ A — complementare rispetto all’insieme universo U (l’«universo»).
Leggi di De Morgan: (A ∪ B)c = Ac ∩ Bc e (A ∩ B)c = Ac ∪ Bc.
L’unione è «o l’uno, o l’altro, o entrambi», l’intersezione «entrambi insieme», la differenza «questo, ma non quello» e il complementare «tutto il resto». La legge di De Morgan dice che «non è vero che piove o nevica» equivale a «non piove e non nevica».
Nella pratica dell’IA le intersezioni servono per esempio a valutare un modello. Se P è l’insieme delle e-mail che il modello ha segnato come spam e S l’insieme delle e-mail che sono davvero spam, allora la precisione (precision) è |P ∩ S| / |P| — quante delle segnalate erano davvero spam — e il richiamo (recall) è |P ∩ S| / |S| — quanto spam il modello ha intercettato.
4. Prodotto cartesiano e n-uple
Definizione — coppia ordinata e prodotto cartesiano
Una coppia ordinata (a, b) si distingue dall’insieme {a, b} perché l’ordine conta: (a, b) = (c, d) ⇔ a = c ∧ b = d.
Prodotto cartesiano A × B = {(a, b) : a ∈ A, b ∈ B}. Per insiemi finiti |A × B| = |A| · |B|.
In generale A1 × … × An è l’insieme delle n-uple; An = A × … × A (n volte).
Il prodotto cartesiano è la tabella di tutte le combinazioni. Tre magliette e due paia di pantaloni danno 3 · 2 = 6 abbinamenti. Le coordinate di un punto del piano sono coppie di ℝ × ℝ = ℝ2.
Il prodotto cartesiano nell’IA è ovunque. I dati di addestramento supervisionato sono un sottoinsieme di X × Y — coppie (input, risposta corretta). Una foto di 28 × 28 pixel è un punto di ℝ784. E in un problema di ricerca la funzione di transizione è definita su S × A — sulle coppie (stato, azione).
5. Relazioni
Definizione — relazione
Una relazione binaria tra gli insiemi A e B è un qualsiasi sottoinsieme R ⊆ A × B. Al posto di (a, b) ∈ R si scrive a R b e si legge «a è in relazione con b».
Se A = B, si parla di relazione sull’insieme A.
Una relazione è un elenco di coppie che «stanno insieme». Chi è genitore di chi, quale città ha un collegamento diretto con quale, quale stato porta a quale. Niente di più — solo un elenco di coppie.
Una relazione su un insieme piccolo si può disegnare in due modi. Prendiamo la relazione «a divide b» (b è multiplo di a) sull’insieme {1, …, 6}. Come matrice: nella riga a e nella colonna b c’è un punto quando a divide b. E come grafo orientato: una freccia da a a b.
matrice: riga a, colonna b
grafo: freccia a → b (senza cappi a → a)
La relazione ha 14 coppie. Nell’IA incontrerai entrambe le forme: la matrice della relazione è ciò con cui calcola il computer (matrice di adiacenza di un grafo, matrice di similarità), il grafo è ciò che disegna una persona. Le transizioni tra stati nella ricerca sono una relazione sull’insieme degli stati, e il grafo dei k vicini più prossimi della propagazione delle etichette è la relazione «è tra i più vicini».
6. Proprietà delle relazioni
Definizione — proprietà di una relazione su un insieme
Una relazione R sull’insieme A è
- riflessiva se ∀a ∈ A : a R a,
- simmetrica se ∀a, b : a R b ⇒ b R a,
- antisimmetrica se ∀a, b : (a R b ∧ b R a) ⇒ a = b,
- transitiva se ∀a, b, c : (a R b ∧ b R c) ⇒ a R c.
Riflessiva: ognuno è in relazione con sé stesso. Simmetrica: funziona in entrambe le direzioni. Antisimmetrica: in entrambe le direzioni solo quando si tratta della stessa cosa. Transitiva: se c’è un cammino da a a b e da b a c, ce n’è anche uno diretto da a a c.
Per le relazioni sull’insieme {1, …, 6} il quadro è questo — e dalla combinazione delle proprietà si riconosce di che tipo di relazione si tratta:
| Relazione | Riflessiva | Simmetrica | Antisimmetrica | Transitiva |
|---|---|---|---|---|
| a ≤ b | sì | no | sì | sì |
| a divide b | sì | no | sì | sì |
| stesso resto nella divisione per 3 | sì | sì | no | sì |
| |a − b| = 1 («vicini») | no | sì | no | no |
7. Equivalenza e partizione in classi
Definizione — equivalenza e partizione
Una relazione riflessiva, simmetrica e transitiva è una relazione di equivalenza. La classe di equivalenza di un elemento a è [a] = {x ∈ A : x R a}.
Una partizione dell’insieme A è una famiglia di sottoinsiemi non vuoti, a due a due disgiunti, la cui unione è A.
Teorema. Le classi di ogni equivalenza formano una partizione di A — e viceversa, ogni partizione determina l’equivalenza «appartiene alla stessa parte».
Un’equivalenza è «è uguale per qualche aspetto a» — stesso colore, stesso resto, stessa classe. Una relazione così divide sempre l’insieme in cassetti che non si sovrappongono e che insieme coprono tutto. Ogni elemento sta esattamente in un cassetto.
È esattamente ciò che fa la classificazione: divide l’insieme di tutti gli input possibili in classi — spam e non spam; cane, gatto e pappagallo. E il clustering cerca una partizione dei dati senza che nessuno gli dica quali sono le classi. Il risultato di k-means della parte sui tipi di apprendimento è una partizione dei punti in tre classi.
8. Relazioni d’ordine
Definizione — ordine parziale e ordine totale
Una relazione riflessiva, antisimmetrica e transitiva è un ordine parziale.
Se inoltre ogni coppia di elementi è confrontabile (∀a, b : a R b ∨ b R a), si tratta di un ordine totale (lineare).
Un ordine dice che cosa viene «prima» di che cosa. Con i numeri ordinati per grandezza si può confrontare qualsiasi cosa con qualsiasi altra. In un ordine parziale non sempre: 4 e 6 non si dividono a vicenda, quindi secondo la divisibilità non sappiamo quale sia «minore».
Un ordine parziale si disegna con un diagramma di Hasse: gli elementi minori in basso, quelli maggiori in alto e una linea solo tra vicini immediati — il resto segue dalla transitività. Ecco i divisori di 12 ordinati per divisibilità:
Dal diagramma si vede che 1 divide tutto e 12 è divisibile per tutto — ma né 4 e 6 né 2 e 3 si possono confrontare. Nell’IA gli ordini compaiono ovunque si ordini o si pianifichi qualcosa: l’ordine dei risultati di ricerca, le priorità nella frontiera dell’algoritmo A*, o le dipendenze tra i passi di un piano («prima apri la porta, poi passa»). Il grafo delle dipendenze tra i moduli nel programma di questa serie, tra l’altro, è anch’esso un ordine parziale.
9. La funzione come relazione speciale
Definizione — funzione
Una funzione da A a B è una relazione f ⊆ A × B in cui ogni elemento a ∈ A ha esattamente un elemento b ∈ B con (a, b) ∈ f. Lo si indica con f(a).
Una funzione è una relazione che a ogni domanda dà esattamente una risposta. «È genitore di» non è una funzione — una persona può avere più figli. «Ha come madre» lo è — ognuno ne ha esattamente una.
Così il cerchio si chiude: un modello di apprendimento automatico è una funzione f : X → Y, cioè una relazione speciale tra input e output. Alle funzioni e alle loro proprietà è dedicata la prossima parte del programma.
10. Riepilogo
- Un insieme è una collezione di elementi senza ordine e senza ripetizioni; un insieme di n elementi ha 2n sottoinsiemi.
- Unione, intersezione, differenza e complementare sono «o», «e», «ma non» e «tutto il resto»; sulle intersezioni si basano precisione e richiamo di un modello.
- Il prodotto cartesiano crea coppie — di cui sono fatti sia i dati (input, risposta) sia le transizioni (stato, azione).
- Una relazione è un insieme di coppie. Un’equivalenza divide l’insieme in classi (classificazione, clustering), un ordine stabilisce che cosa viene prima di che cosa.
- Una funzione è una relazione con esattamente una risposta — e un modello è una funzione.
La vedi diversamente? Scrivi a support@coden-app.com.