martes, 3 de mayo de 2022

(761) - Mínimos cuadrados en machine learning. Least trimmed squares (LTS)

En el día de hoy veamos cómo se utiliza la regresión lineal en machine learning. Recapitulemos un poco cómo funcionan los mínimos cuadrados ordinarios, ordinary least squares u OLS por sus siglas en inglés, el caso más simple: Dadas dos sucesiones de valores, una predictora $\{x_i\}_{i=1}^n$ (abscisas), y otra respuesta $\{y_i\}_{i=1}^n$ (ordenadas), se buscan los argumentos (parámetros) que minimicen la siguiente restricción $Z_{OLS}$ (del alemán Zwang - obligación): $$ Z_{OLS} = \sum_{i=1}^n \big(y_i-(\beta_0+\beta_1x_i)\big)^2 \qquad \hat{\beta}_0,\hat{\beta}_1 = \operatorname{arg\,min} Z_{OLS}$$ Nótese que esta restricción siempre es no-negativa, $Z_{OLS}\geqslant 0$ , y la igualdad (que sería lo deseable) solo se da si el ajuste es perfecto y no hay ninguna desviación.

Dado que queremos hallar la recta que mejor se ajuste a $\{y_i\}_{i=1}^n$ en la expresión aparece $\beta_0+\beta_1x_i$ , sino, si supiésemos o si intuyésemos que los $\{y_i\}_{i=1}^n$ siguen una función $f(x)$ genérica (polinómica, sinusoidal, exponencial,...), entonces se buscaría qué parámetros de $f(x)$ minimizan $\displaystyle Z_{OLS} = \sum_{i=1}^n \big(y_i-f(x_i)\big)^2$ . Se suele denotar por $\hat{y}_i=f(x_i)$ a los valores predichos. El método de mínimos cuadrados busca los argumentos, i.e. parámetros, $\hat{\beta}_0,\hat{\beta}_1,\cdots$ que minimizan la suma total de los cuadrados de todas las $n$ diferencias entre los valores reales $y_i$ , y los valores predichos $\hat{y}_i$ , $Z_{OLS}$ , (esta diferencia es el residual $r_i\overset{\text{def}}{=}y_i-\hat{y}_i$, por eso realmente se suele poner como hallar los argumentos que minimizan $\displaystyle Z_{OLS}=\sum_{i=1}^n {r_i}^2$ ). En nuestro caso para la regresión de una recta si denotamos como $\hat{\beta}_0,\hat{\beta}_1$ a la ordenada en el origen y pendiente predichas según el modelo respetivamente, se tiene que $\hat{y}_i = \hat{\beta}_0+\hat{\beta}_1x_i$ .

Sin embargo, en machine learning no se utiliza esto, al menos no así. Se hace lo que se conoce como mínimos cuadrados recortados, least trimmed squares o LTS por sus siglas en inglés: Primero se preselecciona un número $k$ de puntos que se tendrán en cuenta (y los $(n-k)$ restantes para un estudio posterior), donde $k$ suele estar entre el $75\%-80\%$ del total $n$ de puntos. Empero dichos $k$ puntos que se toman no son al azar, sino que se escogen de una manera muy particular: de entre todos los $n$ puntos $\big\{(x_i,y_i)\big\}_{i=1}^n$ , se busca entre todas las $\displaystyle \binom{n}{k}$ posibles combinaciones (de $k$ elementos tomados de un supraconjunto de $n$ elementos) aquella cuya restricción $Z$ de $k$ sumandos sea la mínima de todas las posibles, es decir, en cualquier otro subconjunto de tamaño $k$ sobre el supraconjunto $n$ se ajustan peor entre sí a mínimos cuadrados (su restricción $Z$ es mayor).

Sea $\mathcal{Z}$ el conjunto de las $\displaystyle |\mathcal{Z}|=\binom{n}{k}$ posibles mínimas sumas parciales de los cuadrados de $k$ residuales, $\displaystyle \mathcal{Z} \overset{\text{def}}{=} \bigg\{ \min\!\sum_{i=1}^k {r_{\sigma(i)}}^2 \;|\; k\leqslant n\, ,\,\sigma\in S_n\bigg\}$ con $k$ fijo , donde $\sigma(\cdot)$ indica una permutación de los $n$ puntos. Buscamos qué argumentos minimizan $Z_{LTS}\overset{\text{def}}{=}\min\{\mathcal{Z}\}\geqslant 0$ . Por esta definición el coeficiente de correlación $R^2$ de $Z_{LTS}$ es el máximo de los del conjunto $\mathcal{Z}$ , es decir, $R^2(Z_{LTS})\triangleq\max\big\{R^2(\mathcal{Z})\big\}$ .

Es más, si denotamos por $\big\{{r_{(i)}}^2\big\}_{i=1}^n$ la sucesión de los cuadrados de los residuales ordenados de menor a mayor, es decir, ${r_{(i)}}^2\leqslant {r_{(i+1)}}^2$ , buscamos qué parámetros minimizan la suma parcial $\displaystyle Z_{LTS}=\sum_{i=1}^k {r_{(i)}}^2$ , que es menor o igual que la suma total $\displaystyle \sum_{i=1}^n {r_{(i)}}^2=\sum_{i=1}^n {r_i}^2 = Z_{OLS}$ . Esta última restricción es como ya hemos dicho, la que se busca minimizar en OLS. La suma parcial será igual a la suma total si y solo si $r_{(i)}=0 \quad i = 1,\cdots, n$, es decir, si todos, los $n$ puntos, están perfectamente alineados.

Para comparar ambos resultados, ya hemos visto que $0\leqslant Z_{LTS}\leqslant Z_{OLS}$ , pero estaría bien comparar sendos errores cuadráticos medios, es decir, $\displaystyle \frac{1}{k} Z_{LTS}$ frente a $\displaystyle \frac{1}{n} Z_{OLS}$ , o también $\displaystyle \frac{1}{k-p} Z_{LTS}$ frente a $\displaystyle \frac{1}{n-p} Z_{OLS}$ (que se pueden entender como estimadores de las varianzas de sendos residuales) donde $p$ es el número de parámetros que se estiman (en una recta por ejemplo son dos: la ordenada en el origen y la pendiente), siendo $(k-p)$ y $(n-p)$ sendos grados de libertad.

A este conjunto de $k$ elementos que minimizan la suma parcial de los $k$ cuadrados de los residuales entre todas las posibles se lo conoce como conjunto de entrenamiento (training data set en inglés), mientras que el conjunto restante de $(n-k)$ elementos se lo conoce como conjunto de validación (test data set en inglés). El porqué de separar estos dos es debido a que el conjunto con los $(n-k)$ elementos restantes puede estar corrupto, contaminado, o ser defectuoso (son los outliers). Por eso este método es robusto: considera el conjunto de $k$ elementos que mejor se ajustan entre sí, mientras que el conjunto de $(n-k)$ elementos se utiliza para comprobar cómo de bueno es nuestro modelo, si las hipótesis son las correctas, y si hay que replantearse algo. Sin embargo, el conjunto de $(n-k)$ elementos no influyen en hallar los argumentos que minimizan la restricción $Z_{LTS}$ .

Cabe resaltar que $\displaystyle \frac{n^k}{k!}\geqslant \binom{n}{k} \geqslant \frac{(n-k+1)^k}{k!}$ siendo equivalentes cuando $n\to\infty$, es decir, que aumentando $n$ (al aumentar también $k$ ) implica que las posibles elecciones tienen un crecimiento exponencial-potencial, por lo que hallar qué conjunto de $k$ elementos es el adecuado puede ser muy costoso computacionalmente, en especial con $n$ medianos o con algoritmos no-óptimos. Por otro lado intentar estimar el conjunto de los $k$ con una simulación tipo Monte Carlo no parece ser muy fructífera, ya que la probabilidad de acertar aleatoriamente es $\displaystyle \frac{1}{\binom{n}{k}}$ .

Como último comentario, también existe un método que generaliza OLS conocido como mínimos cuadrados ponderados, weighted least squares o WLS por sus siglas en inglés, donde en vez de minimizar $\displaystyle Z_{OLS}=\sum_{i=1}^n {r_i}^2$ , se busca minimizar $\displaystyle Z_{WLS}=\sum_{i=1}^n \omega_i\,{r_i}^2$ donde $\{\omega_i\}_{i=1}^n$ es una sucesión de pesos no-negativos con cada $\omega_i$ asociado a su respectivo $r_i$ (realmente a $x_i$ , pero es equivalente) y normalmente normalizados, $\displaystyle \sum_{i=1}^n \omega_i=1$ . Nuestro modelo de LTS es en realidad un caso muy particular de WLS donde $\displaystyle\omega_{\sigma(i)}=\begin{cases} \displaystyle \frac{1}{k} & i\in\{1,\cdots,k\} \\ 0 & i\in\{k+1,\cdots,n\} \end{cases}$ . Es más, se podría generalizar esto aún más a un modelo de mínimos cuadrados ponderados y recortados, weighted least trimmed squares o WLTS por sus siglas en inglés donde se buscan: $$\operatorname{arg\,\min} \sum_{i=1}^k \omega_{(i)}\,{r_{(i)}}^2 $$
Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.

No hay comentarios:

Publicar un comentario