Minimizzazione del rischio empirico

Nella teoria dell'apprendimento statistico, la minimizzazione del rischio empirico (Template:Inglese, 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: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),\dots ,(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),\dots ,(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 Template:Tutto attaccato 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)=𝐄[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{array}{cc}1& \text{se}\hat{y}\ne y\\ 0& \text{se}\hat{y}=y\end{array}$ .

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

$h^{*}=\underset{h\in \mathscr{H}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}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 \mathscr{H}}{\mathrm{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

• Template:Cita libro

Voci correlate

• Metodo della massima verosimiglianza