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.

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.

Per le definizioni che seguono, verranno utilizzati due casi esemplificativi. Il primo è il problema del riconoscimento dei caratteri dato un array di 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 un insieme detto spazio delle istanze ossia la codifica di tutti i possibili esempi. Nel problema del riconoscimento dei caratteri, lo spazio delle istanze è Nel problema dell'intervallo lo spazio delle istanze è l'insieme di tutti gli intervalli limitati in , dove indica l'insieme dei numeri reali.

Un concetto è un sottoinsieme . Ad esempio, un concetto potrebbe essere l'insieme di tutti gli schemi di bit in che codificano un'immagine della lettera "P". Un concetto esemplificativo nel secondo caso potrebbe essere l'insieme degli intervalli aperti , ognuno dei quali contiene solo i punti positivi. Una classe di concetti è una collezione di concetti su . 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 che sappia estrarre un esempio , utilizzando una distribuzione di probabilità e anche fornire l'etichetta corretta , cioè 1 se e 0 altrimenti. Ora, dati e , si assuma che ci sia un algoritmo e un polinomio in (ed altri parametri rilevanti per la classe ) tali che, dato un campione di dim. estratto da , allora, con una probabilità di almeno , restituisce un’ipotesi che abbia un tasso d'errore medio minore o uguale a su con la stessa distribuzione . Inoltre se la condizione sopra citata sull’algoritmo è vera per ogni concetto , per ogni distribuzione su e per ogni allora si dice che è (efficientemente) PAC appredibile (o distribution-free PAC learnable). Si dirà anche che è un algoritmo di apprendimento PAC per .

Equivalenza Sotto certe condizioni di regolarità, le seguenti proprietà risultano equivalenti:

La classe di concetti è PAC apprendibile, La dimensione VC di è finita, è una classe uniforme secondo Glivenko-Cantelli è comprimibile (secondo Littlestone e Warmuth)

Note

Bibliografia

.

Moran, Shay; Yehudayoff, Amir (2015). "Sample compression schemes for VC classes". arXiv:1503.06960.

Voci correlate Data mining

Collegamenti esterni

Categoria:Apprendimento automatico Categoria:Teoria della complessità computazionale