Variación de $K$ -estimaciones de validación cruzada como $f(K)$ ¿Qué papel desempeña la "estabilidad"?

Question

TL,DR: Parece que, en contra de los consejos que se repiten a menudo, la validación cruzada con exclusión (LOO-CV), es decir, $K$ -CV doble con $K$ (el número de pliegues) igual a $N$ (el número de observaciones de entrenamiento) -- produce estimaciones del error de generalización que son el menos para cualquier $K$ no la más variable, asumiendo una cierta estabilidad en el modelo/algoritmo, en el conjunto de datos, o en ambos (no estoy seguro de cuál es el correcto, ya que no entiendo bien esta condición de estabilidad).

• ¿Puede alguien explicar claramente en qué consiste exactamente esta condición de estabilidad?
• ¿Es cierto que la regresión lineal es uno de esos algoritmos "estables", lo que implica que, en ese contexto, LOO-CV es estrictamente la mejor elección de CV en lo que respecta al sesgo y la varianza de las estimaciones del error de generalización?

---

La opinión generalizada es que la elección de $K$ en $K$ -El CV doble sigue un compromiso de sesgo-varianza, tales valores más bajos de $K$ (aproximación 2) conducen a estimaciones del error de generalización que tienen un sesgo más pesimista, pero una menor varianza, mientras que los valores más altos de $K$ (acercándose $N$ ) conducen a estimaciones menos sesgadas, pero con mayor varianza. La explicación convencional de este fenómeno de aumento de la varianza con $K$ se da quizás de forma más destacada en Los elementos del aprendizaje estadístico (Sección 7.10.1):

Con K=N, el estimador de validación cruzada es aproximadamente insesgado para el error de predicción verdadero (esperado), pero puede tener una alta varianza porque los N "conjuntos de entrenamiento" son muy similares entre sí.

La implicación es que el $N$ Los errores de validación están más correlacionados, por lo que su suma es más variable. Esta línea de razonamiento se ha repetido en muchas respuestas en este sitio (por ejemplo, aquí , aquí , aquí , aquí , aquí , aquí et aquí ), así como en varios blogs, etc. Pero prácticamente nunca se ofrece un análisis detallado, sino sólo una intuición o un breve esbozo de lo que podría ser un análisis.

Sin embargo, se pueden encontrar declaraciones contradictorias, normalmente citando una determinada condición de "estabilidad" que no entiendo muy bien. Por ejemplo, esta respuesta contradictoria cita un par de párrafos de un documento de 2015 que dice, entre otras cosas, "Para los modelos/procedimientos de modelización con baja inestabilidad La variabilidad más pequeña suele ser la de LOO" (el subrayado es nuestro). Este documento (sección 5.2) parece estar de acuerdo en que LOO representa la opción menos variable de $K$ siempre que el modelo/algoritmo sea "estable". Adoptando incluso otra postura sobre la cuestión, también hay este documento (Corolario 2), que dice "La varianza de $k$ la validación cruzada de pliegues [...] no depende de $k$ , citando de nuevo una determinada condición de "estabilidad".

La explicación de por qué la LOO puede ser la más variable $K$ -El doble CV es bastante intuitivo, pero hay una contraintuición. La estimación final del CV del error cuadrático medio (MSE) es la media de las estimaciones del MSE en cada pliegue. Por tanto, como $K$ aumenta hasta $N$ la estimación del CV es la media de un número creciente de variables aleatorias. Y sabemos que la varianza de una media disminuye con el número de variables que se promedian. Así que para que LOO sea la más variable $K$ -CV doble, tendría que ser cierto que el aumento de la varianza debido a la mayor correlación entre las estimaciones del MSE supera la disminución de la varianza debida al mayor número de pliegues que se promedian . Y no es en absoluto evidente que esto sea cierto.

Después de confundirme pensando en todo esto, decidí hacer una pequeña simulación para el caso de la regresión lineal. Simulé 10.000 conjuntos de datos con $N$ =50 y 3 predictores no correlacionados, estimando cada vez el error de generalización mediante $K$ -CV doblado con $K$ =2, 5, 10 o 50= $N$ . El código R está aquí. A continuación se muestran las medias y varianzas resultantes de las estimaciones del CV en los 10.000 conjuntos de datos (en unidades MSE):

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Estos resultados muestran el patrón esperado de que los valores más altos de $K$ conducen a un sesgo menos pesimista, pero también parecen confirmar que la varianza de las estimaciones del CV es menor, no mayor, en el caso de la LOO.

Por lo tanto, parece que la regresión lineal es uno de los casos "estables" mencionados en los documentos anteriores, donde el aumento $K$ se asocia con una varianza decreciente en lugar de creciente en las estimaciones de CV. Pero lo que sigo sin entender es:

• ¿En qué consiste exactamente esta condición de "estabilidad"? ¿Se aplica a los modelos/algoritmos, a los conjuntos de datos o a ambos en cierta medida?
• ¿Existe una forma intuitiva de pensar en esta estabilidad?
• ¿Cuáles son otros ejemplos de modelos/algoritmos o conjuntos de datos estables e inestables?
• ¿Es relativamente seguro asumir que la mayoría de los modelos/algoritmos o conjuntos de datos son "estables" y, por tanto, que $K$ debe elegirse, por lo general, tan alto como sea posible desde el punto de vista informático?

Answer 1

Esta respuesta es la continuación de mi respuesta en Sesgo y varianza en la validación cruzada de un solo paso frente a la de dos pasos que discute por qué LOOCV no siempre conducen a una mayor varianza. Siguiendo un enfoque similar, intentaré destacar un caso en el que LOOCV no conduce a una mayor varianza en presencia de valores atípicos y un "modelo inestable".

Estabilidad algorítmica (teoría del aprendizaje)

El tema de la estabilidad algorítmica es reciente y en los últimos 20 años se han demostrado varios resultados clásicos e infuyentes. He aquí algunos trabajos que se citan a menudo

• Heurística de inestabilidad y estabilización en la selección de modelos (1996): Leo Breiman
• Estabilidad algorítmica y límites de verificación de cordura para LOOCV (1997): Kearns, Ron
• Estabilidad y generalización (2002): Bousquet, Elisseef
• Validación cruzada y estabilidad cuadrática media (2011) Kale, Kumar, Vassilvitskii
• Estabilidad algorítmica en casi todas partes y error de generalización (2012): Kutin, Niyogi
• Algunas notas sobre el tema: Universidad de Arizona

La mejor página para obtener una comprensión es sin duda la página de wikipedia que ofrece un excelente resumen escrito por un usuario presumiblemente muy informado.

Definición intuitiva de estabilidad

Intuitivamente, un algoritmo estable es aquel cuya predicción no cambia mucho cuando los datos de entrenamiento se modifican ligeramente.

Formalmente, hay media docena de versiones de la estabilidad, vinculadas entre sí por condiciones técnicas y jerarquías, véase este gráfico de aquí por ejemplo:

El objetivo, sin embargo, es simple, queremos obtener límites ajustados en el error de generalización de un algoritmo de aprendizaje específico, cuando el algoritmo satisface el criterio de estabilidad. Como es de esperar, cuanto más restrictivo sea el criterio de estabilidad, más estricto será el límite correspondiente.

Notación

La siguiente notación procede del artículo de la wikipedia, que a su vez copia el artículo de Bousquet y Elisseef:

• El conjunto de entrenamiento $S = \{ z_1 = (x_1,y_1), ..., z_m = (x_m, y_m)\}$ se extrae i.i.d. de una distribución desconocida D
• La función de pérdida $V$ de una hipótesis $f$ con respecto a un ejemplo $z$ se define como $V(f,z)$
• Modificamos el conjunto de entrenamiento eliminando el $i$ -enésimo elemento: $S^{|i} = \{ z_1,...,z_{i-1}, z_{i+1},...,z_m\}$
• O sustituyendo el $i$ -enésimo elemento: $S^{i} = \{ z_1,...,z_{i-1}, z_i^{'}, z_{i+1},...,z_m\}$

Definiciones formales

Tal vez la noción más fuerte de estabilidad que un algoritmo de aprendizaje interesante podría obedecer es la de estabilidad uniforme :

Estabilidad uniforme Un algoritmo tiene una estabilidad uniforme $\beta$ con respecto a la función de pérdida $V$ si se cumple lo siguiente:

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Considerado en función de $m$ El término $\beta$ puede escribirse como $\beta_m$ . Decimos que el algoritmo es estable cuando $\beta_m$ disminuye a medida que $\frac{1}{m}$ . Una forma ligeramente más débil de estabilidad es:

Estabilidad de la hipótesis

$$\forall i \in \{ 1,...,m\}, \ \ \mathbb{E}[\ | V(f_s,z) - V(f_{S^{|i},z}) |\ ] \ \leq \beta$$

Si se elimina un punto, la diferencia en el resultado del algoritmo de aprendizaje se mide por la diferencia absoluta promediada de las pérdidas ( $L_1$ norma). Intuitivamente: los pequeños cambios en la muestra sólo pueden hacer que el algoritmo se desplace a hipótesis cercanas.

La ventaja de estas formas de estabilidad es que proporcionan límites para el sesgo y la varianza de los algoritmos estables. En particular, Bousquet demostró estos límites para la estabilidad Uniforme y de Hipótesis en 2002. Desde entonces, se ha trabajado mucho para tratar de relajar las condiciones de estabilidad y generalizar los límites, por ejemplo en 2011, Kale, Kumar, Vassilvitskii argumentan que estabilidad media cuadrática proporciona mejores límites de reducción de la varianza cuantitativa.

Algunos ejemplos de algoritmos estables

Se ha demostrado que los siguientes algoritmos son estables y tienen límites de generalización probados:

• Regresión por mínimos cuadrados regularizada (con un prior adecuado)
• Clasificador KNN con función de pérdida 0-1
• SVM con un núcleo acotado y una gran constante de regularización
• Margen suave SVM
• Algoritmo de entropía relativa mínima para la clasificación
• Una versión de regularizadores de bolsa

Una simulación experimental

Repitiendo el experimento del hilo anterior ( ver aquí ), ahora introducimos una cierta proporción de valores atípicos en el conjunto de datos. En concreto:

• El 97% de los datos tiene $[-.5,.5]$ ruido uniforme
• El 3% de los datos con $[-20,20]$ ruido uniforme

Como el $3$ Si el modelo polinómico de orden no está regularizado, se verá muy influenciado por la presencia de unos pocos valores atípicos en conjuntos de datos pequeños. Para conjuntos de datos más grandes, o cuando hay más valores atípicos, su efecto es menor ya que tienden a anularse. Vea a continuación dos modelos para 60 y 200 puntos de datos.

Si se realiza la simulación como se ha hecho anteriormente y se traza la media del MSE y la varianza del MSE resultante, se obtienen resultados muy similares a los del Experimento 2 del Bengio y Grandvalet 2004 papel.

Lado izquierdo : no hay valores atípicos. Lado derecho : 3% de valores atípicos.

(véase el documento enlazado para la explicación de la última figura)

Explicaciones

Citando a Respuesta de Yves Grandvalet en el otro hilo:

Intuitivamente, [en la situación de los algoritmos inestables], la CV sin límite puede ser ciega a las inestabilidades que existen, pero no puede ser desencadenada por el cambio de un solo punto en los datos de entrenamiento, lo que la hace muy variable a la realización del conjunto de entrenamiento.

En la práctica es bastante difícil simular un aumento de la varianza debido a la LOOCV. Requiere una combinación particular de inestabilidad, algunos valores atípicos pero no demasiados, y un gran número de iteraciones. Tal vez sea lo esperado, ya que la regresión lineal ha demostrado ser bastante estable. Un experimento interesante sería repetir esto para datos de mayor dimensión y un algoritmo más inestable (por ejemplo, árbol de decisión)

Answer 2

Daré mi respuesta en el contexto del párrafo que citas:

Con K=N, el estimador de validación cruzada es aproximadamente insesgado para el error de predicción verdadero (esperado), pero puede tener una varianza elevada porque los N "conjuntos de entrenamiento" son muy similares entre sí.

El estimador CV del verdadero (esperado) error de predicción se basa en un ejemplo del conjunto de entrenamiento, así que aquí, la expectativa es sobre las muestras del conjunto de entrenamiento, si lo entiendo correctamente.

Entonces, lo que dice este párrafo respecto a la "alta varianza" es que hay una "alta" diferencia entre el error esperado y el error estimado por el CV (que es aquí, el promedio sobre los pliegues).

Esto tiene sentido porque el modelo se ajusta a un conjunto de entrenamiento concreto y porque todos los pliegues de entrenamiento son muy similares dentro de la exclusión. Sin embargo, aunque los pliegues de entrenamiento son muy similares dentro de una ronda de CV, la estimación probablemente difiere mucho si intercambiamos las muestras de entrenamiento por las de CV. En el CV de k pliegues, dado que "diversificamos" los pliegues de entrenamiento, tenemos algún efecto de promediación, y entre los k pliegues, las estimaciones varían menos.

O, en otras palabras, el estimador de CV "leave-one-out" es básicamente casi como un método "holdout" en el que no se rotan los pliegues y se basa la estimación del error en un conjunto de validación. De nuevo, sobre los ejemplos de entrenamiento, habrá una alta varianza comparada con las estimaciones de k-fold, donde se promedia sobre los pliegues entrenando ya modelos algo diversos dentro de la ronda de k-fold (en otras palabras, si se intercambian los conjuntos de entrenamiento, las estimaciones del error a través de k-fold probablemente no variarán mucho).

EDITAR:

Cuando leo algunas respuestas aquí sobre la validación cruzada y en internet en general, creo que parece haber cierta confusión a qué estimador nos referimos. Creo que algunas personas se refieren a un modelo que tiene una alta varianza (con es la charla de ML para la pérdida que tiene un componente de varianza dominante) frente a la alta varianza del estimador CV k-fold. Y, otro conjunto de respuestas se refieren a la varianza como la varianza de la muestra con respecto a los pliegues cuando alguien dice "k-fold tiene alta varianza". Por lo tanto, sugiero que se especifique, porque las respuestas son diferentes en ambos casos.

Answer 3

Ya hemos hablado de esto antes te estás poniendo demasiado matemático con un caballo muerto. Véase el clásico artículo de Ron Kohavi (Stanford-Univ) sobre el CV y el dilema sesgo-varianza aquí . Cuando termine de leer esto, no querrá realizar el LOOCV y probablemente se sentirá atraído por el CV de 10 pliegues y/o el CV de sesgo bootstrap.

También hay que pensar en grandes conjuntos de datos, para los que LOOCV es demasiado caro computacionalmente. En la actualidad, LOOCV no es realmente una opción en la mayoría de los flujos de trabajo/procesos de los grupos.

¿En qué consiste exactamente esta condición de "estabilidad"? ¿Se aplica a modelos/algoritmos, a los conjuntos de datos o a ambos en cierta medida?

En el universo de todas las funciones de coste y en el universo de todos los conjuntos de características, yo no asumiría que hay un índice de "estabilidad" global, porque no sería inadmisible, y sería demasiado propenso a romperse bajo un conjunto infinitamente grande de condiciones. Fundamentalmente, $k=n$ es apropiado cuando la f.d. y/o los parámetros # son tan grandes que se necesitan más datos de entrenamiento. El sesgo también será mayor para $k=n$ ya que se utilizan más datos, y la varianza sería artificialmente cero, ya que los conjuntos de datos de entrenamiento son demasiado similares entre sí. También se estaría aprendiendo más ruido en los datos cuando $k=n$ .

LREG como clasificador funcionaría cuando los datos son linealmente separables, pero en promedio su sesgo sería demasiado alto, ya que muchos conjuntos de datos no son linealmente separables.

¿Existe una forma intuitiva de pensar en esta estabilidad?

En mi opinión, no, ya que no existe una norma general sobre la estabilidad.

¿Cuáles son otros ejemplos de modelos/algoritmos estables e inestables o conjuntos de datos?

Se trata de una pregunta abierta y demasiado amplia, ya que se puede inventar un número infinitamente grande de respuestas, lo que no sería útil.

¿Es relativamente seguro asumir que la mayoría de los modelos/algoritmos o conjuntos de datos son "estables" y, por tanto, que $K$ debe ser generalmente ¿se debe elegir tan alto como sea computacionalmente factible?

No. No. Confiando sólo en $k$ supone que se creen los datos. Un ejemplo es Random Forests, para el que realmente no hay $k$ . Mientras que aproximadamente el 37% de los datos se utilizarán para las pruebas (por término medio, el 37% de los objetos no se seleccionan cuando se realiza un muestreo con reemplazo), existen, por ejemplo, 5.000 conjuntos de datos diferentes (bootstraps), cada uno de los cuales se divide en entrenamiento/prueba de forma diferente. El ejemplo que has sacado de los documentos supone que cada conjunto de datos utilizado es una realización real de los datos, lo cual es un supuesto erróneo.

Dado el bootstrapping, la regla de estabilidad que rodea $k$ es admisible, ya que la muestra de datos utilizada para un enfoque directo de CV que implica $k$ no es una realización real del universo de todos los datos de los que se obtuvo la muestra.