Minimizzazione del rischio empirico: differenze tra le versioni
Creata dalla traduzione della pagina "Empirical risk minimization" |
(Nessuna differenza)
|
Versione delle 13:05, 19 gen 2022
La minimizzazione del rischio empirico (in inglese empirical risk minimization, da cui la sigla ERM) è un principio nella teoria dell'apprendimento statistico che definisce una famiglia di algoritmi di apprendimento e viene utilizzato per fornire limiti teorici alle loro prestazioni. L'idea centrale è che non è possibile sapere esattamente quanto bene funzionerà un algoritmo nella pratica (il "rischio vero") perché è ignota la vera distribuzione dei dati su cui lavorerà l'algoritmo, ma è invece possibile misurarne le prestazioni su un insieme di dati di addestramento noto (il rischio "empirico").
Contesto
Si consideri la seguente situazione, che è un'impostazione generale di molti problemi di apprendimento supervisionato. Si hanno due spazi e e l'obiettivo è conoscere una funzione (spesso chiamato ipotesi) che genera un oggetto , dato . Per fare ciò, si utilizza un training set con campioni dove è un input e è la risposta corrispondente da cui desideriamo ottenere .
In modo più formale, viene assunta l'esistenza di una distribuzione di probabilità congiunta su e , e che i campioni del training set siano stati estratte in maniera i. i. d. da . Si noti che l'assunzione di una distribuzione di probabilità congiunta consente di modellizzare l'incertezza nelle previsioni (ad esempio dal rumore nei dati) perché non è una funzione deterministica di , ma piuttosto una variabile casuale con distribuzione condizionale per un fisso .
Si assuma inoltre di avere una funzione obiettivo a valori reali non negativa che misura quanto sia diversa la previsione di un'ipotesi dal vero risultato Il rischio associato all'ipotesi viene quindi definita come il valore atteso della funzione obiettivo:
Una funzione obiettivo comunemente usata in teoria è la funzione 0-1 : .
L'obiettivo finale di un algoritmo di apprendimento è trovare un'ipotesi tra una classe fissa di funzioni per cui il rischio è minimo:
Per problemi di classificazione, il classificatore di Bayes è definito come il classificatore che minimizza il rischio definito con la funzione di perdita 0-1.
Minimizzazione del rischio empirico
In generale, il rischio non può essere calcolato perché la distribuzione è sconosciuto all'algoritmo di apprendimento (questa situazione viene definita apprendimento agnostico). Tuttavia, si calcola un'approssimazione, chiamata rischio empirico, che corrisponde alla media della funzione obiettivo sul training set:
Il principio della minimizzazione del rischio empirico[1] afferma che l'algoritmo di apprendimento dovrebbe scegliere un'ipotesi che minimizza il rischio empirico:
Pertanto l'algoritmo di apprendimento definito dal principio ERM consiste nella risoluzione del problema di ottimizzazione sopra descritto.
Proprietà
Complessità computazionale
È noto che la minimizzazione del rischio empirico per un problema di classificazione con una funzione 0-1 sia un problema NP-difficile anche per una classe di funzioni relativamente semplice come i classificatori lineari.[2] Tuttavia, può essere risolto in modo efficiente quando il rischio empirico minimo è zero, ovvero i dati sono separabili linearmente .
In pratica, gli algoritmi di apprendimento automatico affrontano questo problema utilizzando un'approssimazione convessa alla funzione 0-1 (come la hinge loss per SVM), che è più facile da ottimizzare, o imponendo ipotesi sulla distribuzione .
Voci correlate
Note
Bibliografia
- V. Vapnik, The Nature of Statistical Learning Theory, collana Information Science and Statistics, Springer-Verlag, 2000, ISBN 978-0-387-98780-4.
- ^ V. Vapnik (1992). [http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf Principles of Risk Minimization for Learning Theory.]
- ^ V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (See the paper and references therein)