¿Cómo puede aumentar la dimensión la varianza sin aumentar el sesgo en kNN?

Question

Mi pregunta es sobre la comprensión de la figura 2.8 en Los elementos del aprendizaje estadístico (2ª edición) . El tema de la sección es cómo el aumento de la dimensión influye en el sesgo/varianza.

Puedo entender a grandes rasgos la figura 2.7 de ESL, pero no tengo ni idea de la 2.8. ¿Alguna explicación sobre el sesgo que no cambia, o la varianza dominante? No puedo imaginar cómo cambian cuando la dimensión aumenta.

A continuación, el detalle:

Supongamos que tenemos 1000 ejemplos de entrenamiento $x_i$ generado uniformemente en $[-1,1]^p$ . Supongamos que la verdadera relación entre $X$ y $Y$ (mayúsculas para las variables) es $$ Y=F(X)=\frac12(X_1 + 1)^3 $$ donde $X_1$ denota el primer componente de $X$ ( $X$ tiene totalmente $p$ componentes, es decir, características). Utilizamos la regla del vecino más cercano para predecir $y_0$ en el punto de prueba $x_0 = 0$ . Denotemos el conjunto de entrenamiento por $\mathcal{T}$ . Podemos calcular el error de predicción esperado en $x_0$ para nuestro procedimiento, promediando sobre todas esas muestras de tamaño 1000. Este es el error cuadrático medio (ECM) para estimar $f(0)$ :

\begin{align} \operatorname{MSE}(x_0) &=E_{\mathcal{T}}[f(x_0)-\hat{y}_0]^2 \\ &= E_{\mathcal{T}}[\hat{y}_0-E_{\mathcal{T}}(\hat{y}_0)]^2 + [E_{\mathcal{T}}(\hat{y}_0)-f(x_0)]^2 \\ &= \operatorname{Var}_{\mathcal{T}}(\hat{y}_0) + \operatorname{Bias}^2(\hat{y}_0) \end{align}

La cifra es la siguiente. El gráfico de la derecha es el caso con el aumento de $p$ (dimensión).

Answer 1

En primer lugar, el sesgo de un clasificador es la discrepancia entre su función media estimada y la función verdadera, mientras que la desviación de un clasificador es la divergencia esperada de la función de predicción estimada con respecto a su valor medio (es decir, lo dependiente que es el clasificador del muestreo aleatorio realizado en el conjunto de entrenamiento).

Por lo tanto, la presencia de sesgo indica que hay algo básicamente erróneo en el modelo, mientras que desviación también es malo, pero un modelo con alta varianza podría al menos predecir bien en promedio.

La clave para entender los ejemplos que generan las figuras 2.7 y 2.8 es:

La varianza se debe a la varianza de muestreo del 1-nearest vecino más cercano. En dimensiones bajas y con $N = 1000$ el vecino más cercano está muy cerca de $0$ por lo que tanto el sesgo como la varianza son pequeños. Como la dimensión $p$ aumenta, el vecino más cercano tiende a alejarse más lejos del punto objetivo, y tanto el sesgo como la varianza se se producen. En $p = 10$ para más de $99\%$ de las muestras el vecino más cercano vecino más cercano está a una distancia mayor que $0.5$ desde el origen.

Recordemos que la función objetivo del ejemplo que genera la figura 2.7 depende de $p$ variables, por lo que el error MSE se debe en gran medida al sesgo.

Por el contrario, en la figura 2.8 la función objetivo del ejemplo sólo depende de $1$ variable, y por lo tanto la varianza domina. En general, esto sucede cuando se trata de dimensiones bajas.

Espero que esto pueda ayudar.

Answer 2

Bueno, no sé si es apropiado responder a una pregunta hecha por mí mismo... Pero creo que tengo una respuesta relativamente intuitiva y quiero compartirla.

En primer lugar, permítanme añadir la función verdadera de la figura 2.7 para comparar: $$Y=f_1(X)=e^{-8||X||^2}$$ y el de la figura 2.8 es $$Y=f_2(X)=\frac12(X_1+1)^3$$

Como dijo @stochazesthai, la verdadera función de 2,7 depende de todos $p$ componentes y 2.8 solamente $1$ componente. Por otro lado, el algoritmo 1-NN implica la norma ordinaria (por defecto), por lo que la distancia se mide por todos los componentes. Otra cosa que hay que mencionar es que la expectativa se lleva al objetivo estimado $\hat{y}$ sobre la distribución de la muestra.

Ahora considere la entrada $X$ . Dada cualquier distancia $d$ al origen, cuando $p=1$ , sólo hay $2$ elecciones del valor de $X$ que son $d$ y $-d$ . Cuando $p$ es creciente, con cualquier distancia fija, las opciones de $X$ se incrementará drásticamente, donde el valor del primer componente $X_1$ puede oscilar cada vez más libremente.

Entonces considere el 1-NN. Cuando $p$ es creciente, como citó @stochazesthai, el vecino más cercano de origen estará lejos con alta probabilidad, lo que significa que el menor $||X||$ será grande.

Por lo tanto, para $f_1$ (donde $||X||$ implicados), $E(\hat{y}_0)$ aumentará mucho cuando $p$ está aumentando, por lo que el sesgo aumentará significativamente; pero al mismo tiempo $\hat{y}_0$ también será grande con alta probabilidad, por lo que la varianza no aumentará demasiado.

Por otro lado, para $f_2$ (donde sólo $X_1$ implicados), cuando $p$ está aumentando, como ya he mencionado, $X_1$ puede oscilar más y más dramáticamente con la misma distancia $E_{\mathcal{T}}(\hat{y}_0)$ . Así que el aumento de la varianza dominará, pero $E_{\mathcal{T}}(\hat{y}_0)$ no cambiará mucho, por lo que el sesgo se mantendrá más o menos sin cambios en comparación con la varianza.

Espero que sea de ayuda.