This note should be considered deprecated. There is not much about Bias Variance Trade-off, and its quite random and old. For a correct derivation for this, you should consider looking at Linear Regression methods.

Introduction

È una cosa ormai risaputa che c’è una sorta di trade-off fra la varianza e il bias per una certo modello. Aumentare la varianza del modello certamente ci permetterà di avere un modello che abbia un errore di training molto basso, però appena vede dei dati nuovi non sarà in grado di generalizzare correttamente. Dall’altra parte avere un bias alto significa avere un modello eccessivamente semplice, poco flessibile, che comunque allenato non riesce ad avere una grande accuratezza né in fase di allenamento, né di in fase di validazione o di test.

Mathematical decomposition

Si può derivare una decomposizione di questo trade-off da un punto di vista matematico, quanto enunciato è dimostrato nel capitolo 8.1.1 delle Note di andrew NG 229 stanford proviamo a descrivere in modo molto leggero quanto presente in quelle note qui. Solitamente vogliamo minimizzare la loss, descritta come

$$ \mathcal{L}(\theta) = \mathbb{E}_{(x, y) \sim \mathcal{D}} [(y - h_{\theta}(x))^{2}] $$

Assumiamo che in $y$ ci sia presente del rumore causato dalla misurazione, e che la famiglia di funzioni descritta da $h$ riesca a modellare la distribuzione reale, questo ci motiva a descrivere $y = h_{\theta^{*}} + \varepsilon$ dove $\varepsilon$ è l’errore intrinseco data dalla misurazione e $\theta^{*}$ è la parametrizzazione migliore esistente.

Allora abbiamo: $$ MSE(x) = \mathbb{E}[(y - h_{\theta}(x))^{2}] = \mathbb{E}[(h_{\theta^{*} }+ \varepsilon - h_{\theta}(x))^{2}]

\mathbb{E}[\varepsilon^{2}] + \mathbb{E}[(h_{\theta^{*}}(x) - h_{\theta}(x))^{2}] $$

Questo si può scomporre ancora assumendo l’esistenza di un modello medio. (vedere derivazione 121 delle note). Avremo alla fine che

$$ MSE(x) = \sigma^{2} + \text{ bias}^{2} + \text{ variance} $$

Dove $\text{ bias} = h_{\theta^{*}}(x) - h_{avg}(x)$ e la varianza uguale ad altro.

Dall’espressione matematica, deriviamo che anche nel caso in cui riusciamo ad eliminare del tutto la varianza e il bias, rimarrebbe l’errore irriducibile di cui abbiamo parlato in Introduction to statistical learning.

Considerazioni generali

Questo trade-off è nato principalmente nell’analisi teorica dei modelli, però è bene tenere in mente la presenza di ciò anche per i modelli reali. Non possiamo calcolare esplicitamente il MSE, però ci dovrebbe essere. Questa è l’osservazione principale per asserire che non sempre il modelli più complicato è la migliore, abbiamo il no-free-lunch theorem!

Statistical learning framework

Introduction to the problem

We will introduce the most common statistical learning framework. There will be a lot of new words to learn for this setting. We will have

  • A classifier $h : \mathcal{ X} \to \left\{ 0, 1 \right\}$ mapping our data to a label, taken from a set $\mathcal{H}$ of all possible hypothesis.
  • Then pairs $(x, y)$ which are training examples and our dataset.
  • A dataset $S_{in} = \left( (x_{1}, y_{1}), \dots, (x_{m}, y_{m}) \right)$ our learning algorithm will be identified as an $\mathcal{A} : \text{ training sequence } \to \text{ classifier }$.
  • So our training algorithm will output a classifier, which we call it in this manner: $h = A(S_{in})$ and we would like this to be correct, which means that $h(x) = y$. for most of our examples. We will briefly introduce also a simple error measure for this theory. There will be mainly two approaches, one based on statistics the other one based on game theory. We will briefly touch both of them. The statistical approach has been mainly explored by the famous Vapnik, then explored by Valiant. We point to (Shalev-Shwartz & Ben-David 2014) as a good resource for the statistical learning approach.

We now assume that our dataset $(X, Y)$ is drawn from $D$ which is unknown. We assume that our data is i.i.d. which is a very strong assumption, but useful to give a general feeling about the field. We define a concept of risk also called loss, which we describe as

$$ l_{D}(h) = P(h(X) \not = Y) $$

Which is just the probability that our classifier is wrong.

We call the realizable case this $\inf_{h \in \mathcal{H}} l_{D}(h) = 0$ Sometimes is interesting to try to characterize the expected loss, i.e. the value $\mathbb{E}_{A}[l_{D}(A(S_{m}))]$. We define the optimal risk to be $\inf_{h \in \mathcal{H}} l_{D}(h)$.

We define the excess risk to be $E_{m} (A, \mathcal{H}) = \sup_{D} (\mathbb{E}\left[ l_{D} (A(S_{m}))\right] - \inf_{h \in \mathcal{H}} l_{D}(h))$ We would like to minimize this, because this is the worst case scenario for a certain algorithm $A$. We say that the set of hypothesis $\mathcal{H}$ is learnable if $E_{m}(\mathcal{H}) = \inf_{A} E_{m}(A, \mathcal{H}) \to 0$. as $m \to \infty$ (i think $m$ is number of training cases??)

We call the empirical risk minimizer to be $\text{ erm}_{\mathcal{H}} (S)$ to be classifier $\mathcal{H}$ that minimizes classification mistakes on $S$. Now that we have these definitions we can ask some questions.

  • Is $\mathcal{H}$ learnable?
  • How can we minimize the excess risk?
  • how can we learn $\mathcal{H}$ fast?

Learnability

We now try to further define the problem

References

[1] Shalev-Shwartz & Ben-David “Understanding Machine Learning: From Theory to Algorithms” Cambridge University Press 2014