Visualizza wikitesto di Minimizzazione del rischio empirico

Nella [[teoria dell'apprendimento statistico]], la '''minimizzazione del rischio empirico''' ({{Inglese|empirical risk minimization}}, da cui la sigla ERM) è un principio che definisce una famiglia di [[Apprendimento automatico|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 [[Training e test set|insieme di dati di addestramento]] noto (il rischio "empirico").

== Contesto ==
In molti problemi di [[apprendimento supervisionato]], l'impostazione generale prevede due spazi <math>X</math> e <math>Y</math> con l'obiettivo è conoscere una funzione <math>h\colon X \to Y</math> (spesso chiamato ''ipotesi'') che genera un oggetto <math>y \in Y</math>, dato <math>x \in X</math>. Per fare ciò, si utilizza un training set con <math>n</math> campioni <math>\{(x_1, y_1), \ldots, (x_n, y_n)\}</math> dove <math>x_i \in X</math> è un input e <math>y_i \in Y</math> è la risposta corrispondente da cui desideriamo ottenere <math>h(x_i)</math> .

In modo più formale, viene assunta l'esistenza di una [[Distribuzione congiunta|distribuzione di probabilità congiunta]] <math>P(x, y)</math> su <math>X</math> e <math>Y</math>, e che i campioni del training set<math>\ (x_1, y_1), \ldots, (x_n, y_n)</math> siano stati estratte in maniera [[Variabili indipendenti e identicamente distribuite|i. i. d.]] da <math>P(x, y)</math>. 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é <math>y</math> non è una funzione deterministica di {{Tutto attaccato|<math>x</math>,}} ma piuttosto una [[variabile casuale]] con [[Distribuzione condizionata|distribuzione condizionale]] <math>P(y | x)</math> per un fisso <math>x</math> .

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

: <math>R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y)\,dP(x, y).</math>

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

:<math>L(\hat{y}, y) = \begin{cases} 1 & \mbox{se}\quad \hat{y} \ne y \\ 0 & \mbox{se}\quad \hat{y} = y \end{cases}</math> .

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

: <math>h^* = \underset{h \in \mathcal{H}} \operatorname{arg\, min}\, R(h).</math>

Per problemi di classificazione, il [[Classificatore bayesiano|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 <math>R(h)</math> non può essere calcolato perché la distribuzione <math>P(x, y)</math> è 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:

: <math>R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i).</math>

Il principio della minimizzazione del rischio empirico<ref>{{Cita libro|autore=V. Vapnik|anno=1992|url=https://papers.nips.cc/paper_files/paper/1991/file/ff4d5fbbafdf976cfdc032e3bde78de5-Paper.pdf|titolo=Principles of Risk Minimization for Learning Theory}}</ref> afferma che l'algoritmo di apprendimento dovrebbe scegliere un'ipotesi <math>\hat{h}</math> che minimizza il rischio empirico:

: <math>\hat{h} = \underset{h \in \mathcal{H}}{\operatorname{arg min}}\, R_\text{emp}(h).</math>

Pertanto l'algoritmo di apprendimento definito dal principio ERM consiste nella risoluzione del problema di [[Ottimizzazione (matematica)|ottimizzazione]] sopra descritto.

== Proprietà ==
=== Complessità computazionale ===
È noto che la minimizzazione del rischio empirico per un problema di classificazione con una [[Funzione obiettivo|funzione 0-1]] sia un problema [[NP-difficile]] anche per una classe di funzioni relativamente semplice come i [[Classificatore lineare|classificatori lineari]].<ref>{{Cita libro|autore=V. Feldman, V. Guruswami, P. Raghavendra e Yi Wu|anno=2009|arxiv=1012.0729|titolo=Agnostic Learning of Monomials by Halfspaces is Hard}}</ref> 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'[[Ottimizzazione convessa|approssimazione convessa]] alla funzione 0-1 (come la ''hinge loss'' per [[Macchine a vettori di supporto|SVM]]), che è più facile da ottimizzare, o imponendo ipotesi sulla distribuzione <math>P(x, y)</math>.

== Note ==
<references/>

== Bibliografia ==
* {{Cita libro|autore=Vapnik|nome=V.|wkautore=Vladimir Vapnik|titolo=The Nature of Statistical Learning Theory|collana=Information Science and Statistics|anno=2000|editore=Springer-Verlag|ISBN=978-0-387-98780-4}}

== Voci correlate ==
* [[Metodo della massima verosimiglianza]]

{{Apprendimento automatico}}
{{Portale|informatica|statistica}}

[[Categoria:Apprendimento automatico]]