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 $X$ e $Y$ con l'obiettivo è conoscere una funzione $h\colon X\to Y$ (spesso chiamato ipotesi) che genera un oggetto $y\in Y$, dato $x\in X$. Per fare ciò, si utilizza un training set con $n$ campioni $\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}$ dove $x_{i}\in X$ è un input e $y_{i}\in Y$ è la risposta corrispondente da cui desideriamo ottenere $h(x_{i})$ .

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

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

$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:

$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 $h^{*}$ tra una classe fissa di funzioni ${\mathcal {H}}$ per cui il rischio $R(h)$ è minimo:

$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 $R(h)$ non può essere calcolato perché la distribuzione $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:

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

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

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

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