# Teoria dell'apprendimento statistico

La teoria dell'apprendimento statistico è il fondamento teorico su cui si basa l'apprendimento automatico.
Attingendo ai campi della statistica e dell'analisi funzionale, la teoria dell'apprendimento statistico cerca di risolvere il generico problema di trovare una funzione capace di effettuare previsioni basandosi sui dati. Questo campo di studio ha portato ad applicazioni pratiche in campi come la visione artificiale, il riconoscimento vocale e la bioinformatica.

## Introduzione

Gli obiettivi dell'apprendimento sono la comprensione dei dati presenti e la previsione dei dati futuri. L'apprendimento si divide in molte categorie, tra cui l'apprendimento supervisionato, l'apprendimento non supervisionato, l'apprendimento online e l'apprendimento per rinforzo. L'apprendimento supervisionato riguarda l'osservazione di dati contenuti in un insieme di addestramento (training set). Ogni punto nel training set è una coppia di valori input-output, in cui l'input viene mappato a un output. Il problema di apprendimento consiste nell'inferire la funzione che mappa l'input all'output, in modo tale che la funzione appresa possa essere utilizzata per prevedere l'output associato ad input del futuro.
La funzione stimata che associa un input ad un output è detta ipotesi, stimatore o predittore (nella letteratura inglese hypothesis, estimator, predictor), e si usa ${\hat {f}}$ come notazione.
A seconda del tipo di output, i problemi di apprendimento supervisionato sono problemi di regressione o problemi di classificazione. Se l'output appartiene ad un intervallo continuo di valori, si tratta di un problema di regressione.
I problemi di classificazione sono quelli per i quali l'output apparterrà ad un elemento di un insieme discreto di etichette. La classificazione è molto comune per le applicazioni di intelligenza artificiale. Nel riconoscimento facciale, ad esempio, l'immagine del volto di una persona sarebbe l'input e l'etichetta di output sarebbe il nome di quella persona. L'immagine input sarebbe rappresentata da un grande vettore multidimensionale i cui elementi rappresentano i pixel nell'immagine.

## Algoritmo

Lo scopo di un algoritmo di apprendimento è osservare i dati del training set e generare una funzione capace di predire l'output associato ad un input. Tale funzione viene convalidata su un test set, contenente dati che non sono presenti nel training set

## Formalismo

I valori di input ${\vec {x}}$ vivono in uno spazio vettoriale multidimensionale $X\subset \mathbb {R} ^{d}$, mentre gli output $y_{i}$ sono scalari reali, appartenenti a $Y\subset \mathbb {R}$. La coppia di valori $({\vec {x}},y)$ è detta punto o campione e compone l''insieme di addestramento, o training set, spesso denotato con $S$, che si scrive
    $S=\{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}$
L'assunzione di base del procedimento è l'esistenza di una distribuzione di probabilità $p({\vec {x}},y)$, definita sullo spazio del prodotto $X\times Y$, che lega gli input e gli output; tale distribuzione è fissa ma sconosciuta. In questo formalismo, il problema di inferenza consiste nel trovare una funzione $f:X\to Y$ tale che $f({\vec {x}})\sim y$. L'algoritmo cerchera la migliore funzione $f$ in un sottospazio denotato con ${\mathcal {H}}$ e chiamato spazio delle ipotesi.
Sia $V(f({\vec {x}}),y)$ la funzione di perdita, uno strumento per misurare la differenza tra il valore previsto $f({\vec {x}})$ e il valore vero $y$. Il rischio atteso (o errore atteso) è il valore atteso della funzione di perdita, ed è definito come
    $I[f]=\displaystyle \int _{X\times Y}V(f({\vec {x}}),y)\,p({\vec {x}},y)\,d{\vec {x}}\,dy$
La migliore funzione possibile $f$ che può essere scelta, soddisfa la condizione
    $f=\inf _{h\in {\mathcal {H}}}I[h]$
Poiché la distribuzione di probabilità $p({\vec {x}},y)$ non è nota, deve essere utilizzata una stima per il valore atteso della funzione di perdita. Questa misura si basa sul training set, un campione di questa distribuzione di probabilità sconosciuta. Si chiama rischio empirico
    $I_{S}[f]={\frac {1}{n}}\displaystyle \sum _{i=1}^{n}V(f({\vec {x}}_{i}),y_{i})$
Un algoritmo di apprendimento che sceglie la funzione $f_{S}$ che minimizza il rischio empirico si chiama minimizzazione del rischio empirico.

## Funzioni di perdita

La scelta della funzione di perdita è un fattore determinante sulla funzione $f_{S}$ che sarà scelto dall'algoritmo di apprendimento. La funzione di perdita influenza anche il tasso di convergenza per un algoritmo. È importante che la funzione di perdita sia convessa.
Vengono utilizzate diverse funzioni di perdita a seconda che il problema sia di regressione o di classificazione.
La funzione di perdita più comune per la regressione è la funzione di perdita quadrata (nota anche come norma L2). Questa familiare funzione di perdita viene utilizzata nella regressione dei minimi quadrati ordinari. Il modulo è:
    $V(f({\vec {x}}),y)=(y-f({\vec {x}}))^{2}$

### Classificazione

In un certo senso la funzione indicatrice 0-1 è la funzione di perdita più naturale per la classificazione. Prende il valore 0 se l'output previsto è lo stesso dell'output effettivo e assume il valore 1 se l'output previsto è diverso dall'output effettivo. Per la classificazione binaria con $Y=\{-1,1\}$, questo è:
    $V(f({\vec {x}}),y)=\theta (-yf({\vec {x}}))$
dove $\theta$ è la funzione gradino di Heaviside.

## Regolarizzazione

Nei problemi di apprendimento automatico, un grosso problema che si pone è quello del sovradattamento. Poiché l'apprendimento è un problema di previsione, l'obiettivo non è trovare una funzione che si adatti maggiormente ai dati (osservati in precedenza), ma trovarne una che preveda in modo più accurato l'output dall'input futuro. La minimizzazione del rischio empirico corre questo rischio di sovradattamento: trovare una funzione che corrisponda esattamente ai dati ma non preveda bene l'output futuro.
Il sovradattamento è sintomatico di soluzioni instabili; una piccola perturbazione nei dati del training set causerebbe una grande variazione nella funzione appresa. Si può dimostrare che se può essere garantita la stabilità per la soluzione, sono garantite anche la generalizzazione e la consistenza. La regolarizzazione può risolvere il problema del sovradattamento e dare stabilità al problema.
La regolarizzazione può essere ottenuta restringendo lo spazio delle ipotesi ${\mathcal {H}}$. Un esempio comune sarebbe la restrizione ${\mathcal {H}}$ alle funzioni lineari: questo può essere visto come una riduzione al problema standard della regressione lineare. ${\mathcal {H}}$ potrebbe anche essere limitato al polinomio di grado $p$, esponenziali o funzioni limitate su L1. La restrizione dello spazio delle ipotesi evita l'overfitting perché la forma delle funzioni potenziali è limitata, e quindi non consente la scelta di una funzione che dia un rischio empirico arbitrariamente vicino allo zero.
Un esempio di regolarizzazione è la regolarizzazione di Tichonov. Consiste nel minimizzare
    ${\frac {1}{n}}\displaystyle \sum _{i=1}^{n}V(f({\vec {x}}_{i}),y_{i})+\gamma \|f\|_{\mathcal {H}}^{2}$
dove $\gamma$ è un parametro fisso e positivo, il parametro di regolarizzazione. La regolarizzazione di Tikhonov garantisce l'esistenza, l'unicità e la stabilità della soluzione.