Apprendimento probabilmente approssimativamente corretto

Nella teoria dell'apprendimento computazionale, quello dell'apprendimento probabilmente approssimativamente corretto (PAC) è un quadro di riferimento per l'analisi matematica dell'apprendimento automatico proposto nel 1984 da Leslie Valiant.^[1]

In questo contesto, l'algoritmo di apprendimento riceve esempi e deve selezionare una funzione di generalizzazione (detta ipotesi) da una data classe di possibili funzioni. L'obiettivo è far sì che, con alta probabilità (parte "probabilmente"), la funzione selezionata abbia un basso errore di generalizzazione (parte "approssimativamente corretto"). L'algoritmo dev'essere in grado di apprendere il concetto fissati un tasso di approssimazione arbitrario, una probabilità di successo e una distribuzione dei dati.

Successivamente il modello di riferimento è stato esteso per trattare la presenza di rumore (esempi classificati in modo errato).

Un'importante innovazione del framework PAC è l'introduzione di concetti della teoria della complessità computazionale nell'apprendimento automatico. In particolare, ci si aspetta che l'algoritmo di apprendimento trovi funzioni efficienti (requisiti di tempo e spazio limitati da un polinomio nelle dimensioni del campione di dati) e che sia implementato a sua volta come procedura efficiente (che richieda un numero di esempi limitato polinomialmente nelle dimensioni del concetto, modificato in base ai limiti posti all'approssimazione e alla verosimiglianza).

Definizioni e terminologia

Per dare la definizione di qualcosa che possa essere definito apprendibile nel framework PAC, si deve prima di tutto introdurre un po' di terminologia.^[2]

Per le definizioni che seguono, verranno utilizzati due casi esemplificativi. Il primo è il problema del riconoscimento dei caratteri dato un array di ${\displaystyle n}$  bit che codificano un'immagine bianco/nero. L'altro è il problema di trovare un intervallo che classifichi correttamente i punti all'interno dell'intervallo come esempi positivi e i punti al di fuori dell'intervallo come esempi negativi.

Sia ${\displaystyle X}$  un insieme detto spazio delle istanze ossia la codifica di tutti i possibili esempi. Nel problema del riconoscimento dei caratteri, lo spazio delle istanze è ${\displaystyle X=\{0,1\}^{n}}$  Nel problema dell'intervallo lo spazio delle istanze ${\displaystyle X}$  è l'insieme di tutti gli intervalli limitati in ${\displaystyle \mathbb {R} }$ , dove ${\displaystyle \mathbb {R} }$  indica l'insieme dei numeri reali.

Un concetto è un sottoinsieme ${\displaystyle c\subset X}$ . Ad esempio, un concetto potrebbe essere l'insieme di tutti gli schemi di bit in ${\displaystyle X=\{0,1\}^{n}}$  che codificano un'immagine della lettera "P". Un concetto esemplificativo nel secondo caso potrebbe essere l'insieme degli intervalli aperti ${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$ , ognuno dei quali contiene solo i punti positivi. Una classe di concetti ${\displaystyle C}$  è una collezione di concetti su ${\displaystyle X}$ . Questa potrebbe essere costituita dall'insieme di tutti i sottoinsiemi dell'array di bit che abbiano uno scheletro morfologico di pixel quadri-connessi (con larghezza del font pari a 1).

Sia data una procedura ${\displaystyle \operatorname {EX} (c,D)}$  che sappia estrarre un esempio ${\displaystyle x}$ , utilizzando una distribuzione di probabilità ${\displaystyle D}$  e anche fornire l'etichetta corretta ${\displaystyle c(x)}$ , cioè 1 se ${\displaystyle x\in c}$  e 0 altrimenti. Ora, dati ${\displaystyle 0<\epsilon }$  e ${\displaystyle \delta <1}$ , si assuma che ci sia un algoritmo ${\displaystyle A}$  e un polinomio ${\displaystyle p}$  in ${\displaystyle 1/\epsilon ,1/\delta }$  (ed altri parametri rilevanti per la classe ${\displaystyle C}$ ) tali che, dato un campione di dim. ${\displaystyle p}$  estratto da ${\displaystyle \operatorname {EX} (c,D)}$ , allora, con una probabilità di almeno ${\displaystyle 1-\delta }$ , ${\displaystyle A}$  restituisce un’ipotesi ${\displaystyle h\in C}$  che abbia un tasso d'errore medio minore o uguale a ${\displaystyle \epsilon }$  su ${\displaystyle X}$  con la stessa distribuzione ${\displaystyle D}$ . Inoltre se la condizione sopra citata sull’algoritmo ${\displaystyle A}$  è vera per ogni concetto ${\displaystyle c\in C}$  , per ogni distribuzione ${\displaystyle D}$  su ${\displaystyle X}$  e per ogni ${\displaystyle 0<\epsilon ,\delta <1}$  allora si dice che ${\displaystyle C}$  è (efficientemente) PAC appredibile (o distribution-free PAC learnable). Si dirà anche che ${\displaystyle A}$  è un algoritmo di apprendimento PAC per ${\displaystyle C}$ .

Equivalenza

Sotto certe condizioni di regolarità, le seguenti proprietà risultano equivalenti: ^[3]

1. La classe di concetti ${\displaystyle C}$  è PAC apprendibile,
2. La dimensione VC di ${\displaystyle C}$  è finita,
3. ${\displaystyle C}$  è una classe uniforme secondo Glivenko-Cantelli
4. ${\displaystyle C}$  è comprimibile (secondo Littlestone e Warmuth)

Voci correlate

• Occam learning (framework alternativo)
• Data Mining

Note

1. ^ L. G. Valiant, A theory of the learnable, in Commun. ACM, vol. 27, n. 11, 5 novembre 1984, pp. 1134–1142, DOI:10.1145/1968.1972. URL consultato il 15 agosto 2025.
2. ^ Kearns and Vazirani, pp. 1-12,
3. ^ Blumer, Learnability and the Vapnik-Chervonenkis Dimension, in Journal of the Association for Computing Machinery, vol. 36, October 1989, pp. 929–965, DOI:10.1145/76359.76371.

Ulteriori riferimenti

• M. Kearns, U. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
• M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, 2018. Chapter 2 contains a detailed treatment of PAC-learnability. open access.
• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework Archiviato il 28 settembre 2011 in Internet Archive..
• L. Valiant. Probably Approximately Correct. Basic Books, 2013.
• Littlestone, N.; Warmuth, M. K. (1986). "Relating Data Compression and Learnability" .
• Moran, Shay; Yehudayoff, Amir (2015). "Sample compression schemes for VC classes". arXiv:1503.06960.

Collegamenti esterni

• Spiegazione interattiva dell'apprendimento PAC