Minimizzazione del rischio empirico

Nella teoria dell'apprendimento statistico, la minimizzazione del rischio empirico (in inglese empirical risk minimization, da cui la sigla ERM) è un principio 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

In molti problemi di apprendimento supervisionato, l'impostazione generale prevede due spazi ${\displaystyle X}$ e ${\displaystyle Y}$ con l'obiettivo è conoscere una funzione ${\displaystyle h\colon X\to Y}$ (spesso chiamato ipotesi) che genera un oggetto ${\displaystyle y\in Y}$, dato ${\displaystyle x\in X}$. Per fare ciò, si utilizza un training set con ${\displaystyle n}$ campioni ${\displaystyle \{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$ dove ${\displaystyle x_{i}\in X}$ è un input e ${\displaystyle y_{i}\in Y}$ è la risposta corrispondente da cui desideriamo ottenere ${\displaystyle h(x_{i})}$ .

In modo più formale, viene assunta l'esistenza di una distribuzione di probabilità congiunta ${\displaystyle P(x,y)}$ su ${\displaystyle X}$ e ${\displaystyle Y}$, e che i campioni del training set${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ siano stati estratte in maniera i. i. d. da ${\displaystyle P(x,y)}$. 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é ${\displaystyle y}$ non è una funzione deterministica di ${\displaystyle x}$, ma piuttosto una variabile casuale con distribuzione condizionale ${\displaystyle P(y|x)}$ per un fisso ${\displaystyle x}$ .

Si assuma inoltre di avere una funzione obiettivo a valori reali non negativa ${\displaystyle L({\hat {y}},y)}$ che misura quanto sia diversa la previsione ${\displaystyle {\hat {y}}}$ di un'ipotesi dal vero risultato ${\displaystyle y.}$ Il rischio associato all'ipotesi ${\displaystyle h(x)}$ viene quindi definita come il valore atteso della funzione obiettivo:

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$

Una funzione obiettivo comunemente usata in teoria è la funzione 0-1:

${\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{se}}\quad {\hat {y}}\neq y\\0&{\mbox{se}}\quad {\hat {y}}=y\end{cases}}}$ .

L'obiettivo finale di un algoritmo di apprendimento è trovare un'ipotesi ${\displaystyle h^{*}}$ tra una classe fissa di funzioni ${\displaystyle {\mathcal {H}}}$ per cui il rischio ${\displaystyle R(h)}$ è minimo:

${\displaystyle h^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,R(h).}$

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 ${\displaystyle R(h)}$ non può essere calcolato perché la distribuzione ${\displaystyle P(x,y)}$ è 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:

${\displaystyle R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

Il principio della minimizzazione del rischio empirico^[1] afferma che l'algoritmo di apprendimento dovrebbe scegliere un'ipotesi ${\displaystyle {\hat {h}}}$ che minimizza il rischio empirico:

${\displaystyle {\hat {h}}={\underset {h\in {\mathcal {H}}}{\operatorname {argmin} }}\,R_{\text{emp}}(h).}$

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 ${\displaystyle P(x,y)}$.

Note

Bibliografia

• V. Vapnik, The Nature of Statistical Learning Theory, collana Information Science and Statistics, Springer-Verlag, 2000, ISBN 978-0-387-98780-4.

Voci correlate

• Metodo della massima verosimiglianza

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Regole di associazione · Apprendimento non supervisionato · Apprendimento supervisionato · Apprendimento per rinforzo · Apprendimento profondo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Dbscan · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random fields · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Probabilistic graphical model · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Rete neurale a base radiale · Rete bayesiana · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · Torch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

Portale Informatica

Portale Statistica