¿Cómo se comparan los diferentes métodos de validación cruzada en términos de varianza y sesgo del modelo?

Mi pregunta está en parte motivada por este hilo: número óptimo de pliegues en la validación cruzada de - pliegues : ¿es el CV de dejar uno solo siempre la mejor opción? $K$ K. La respuesta allí sugiere que los modelos aprendidos con la validación cruzada de dejar uno fuera tienen una varianza más alta que los aprendidos con la validación cruzada de doble regular , lo que hace que el CV de dejar uno fuera sea una peor elección.$K$

Sin embargo, mi intuición me dice que en el CV de dejar uno fuera uno debería ver una variación relativamente menor entre los modelos que en el CV de pliegues, ya que solo estamos cambiando un punto de datos entre pliegues y, por lo tanto, los conjuntos de entrenamiento entre pliegues se superponen sustancialmente.$K$

O yendo en la otra dirección, si es bajo en el CV de veces, los conjuntos de entrenamiento serían bastante diferentes en los pliegues, y es más probable que los modelos resultantes sean diferentes (por lo tanto, una mayor varianza).$K$$K$

Si el argumento anterior es correcto, ¿por qué los modelos aprendidos con CV de dejar uno tienen una mayor varianza?

¿Por qué los modelos aprendidos con CV de dejar uno afuera tienen mayor varianza?

[TL: DR] Un resumen de publicaciones y debates recientes (julio de 2018)

Este tema ha sido ampliamente discutido tanto en este sitio como en la literatura científica, con opiniones, intuiciones y conclusiones contradictorias. De nuevo en 2013, cuando se le preguntó por primera vez esta cuestión, la opinión dominante era que LOOCV conduce a mayor varianza del error de generalización se espera de un algoritmo de entrenamiento producción de modelos de muestras de tamaño .$n(K−1)/K$

Sin embargo, este punto de vista parece ser una generalización incorrecta de un caso especial y yo diría que la respuesta correcta es: "depende ..."

Parafraseando a Yves Grandvalet, autor de un artículo de 2004 sobre el tema, resumiría el argumento intuitivo de la siguiente manera:

1. Si la validación cruzada promediara estimaciones independientes : entonces el CV de dejar uno afuera debería ver una variación relativamente menor entre los modelos, ya que solo estamos cambiando un punto de datos a través de los pliegues y, por lo tanto, los conjuntos de entrenamiento entre pliegues se superponen sustancialmente.
2. Esto no es cierto cuando los conjuntos de entrenamiento están altamente correlacionados : la correlación puede aumentar con K y este aumento es responsable del aumento general de la varianza en el segundo escenario. Intuitivamente, en esa situación, el CV de omisión puede ser ciego a las inestabilidades que existen, pero no puede activarse al cambiar un solo punto en los datos de entrenamiento, lo que lo hace muy variable para la realización del conjunto de entrenamiento.

Las simulaciones experimentales de mí mismo y de otros en este sitio, así como las de los investigadores en los documentos vinculados a continuación, le mostrarán que no hay una verdad universal sobre el tema. La mayoría de los experimentos se disminuye de forma monótona o con varianza constante , pero algunos casos especiales muestran el aumento de la varianza con .$K$$K$

El resto de esta respuesta propone una simulación en un ejemplo de juguete y una revisión informal de la literatura.

[Actualización] Puede encontrar aquí una simulación alternativa para un modelo inestable en presencia de valores atípicos.

Simulaciones de un ejemplo de juguete que muestra varianza decreciente / constante

Considere el siguiente ejemplo de juguete donde estamos ajustando un polinomio de grado 4 a una curva senoidal ruidosa. Esperamos que a este modelo le vaya mal para pequeños conjuntos de datos debido al sobreajuste, como lo muestra la curva de aprendizaje.

Tenga en cuenta que trazamos 1 - MSE aquí para reproducir la ilustración de ESLII página 243

 Metodología

Puede encontrar el código para esta simulación aquí . El enfoque fue el siguiente:

1. Genere 10,000 puntos de la distribución donde se conoce la verdadera varianza de$sin(x) + \epsilon$$\epsilon$
2. Iterar veces (p. Ej. 100 o 200 veces). En cada iteración, cambie el conjunto de datos volviendo a muestrear puntos de la distribución original$i$$N$
3. Para cada conjunto de datos : $i$
   • Realizar validación cruzada K-fold para un valor de$K$
   • Almacene el error cuadrático medio (MSE) promedio en los pliegues K
4. Una vez que se completa el ciclo sobre , calcule la media y la desviación estándar del MSE en los conjuntos de datos para el mismo valor dei $i$$i$$K$
5. Repita los pasos anteriores para todas las en el rango hasta el final para dejar un CV (LOOCV){ 5 , . . . , N $K$$\{ 5,...,N\}$

Impacto de en el sesgo y la varianza del MSE en los conjuntos de datos .$K$$i$

Lado izquierdo : pliegues en K para 200 puntos de datos, lado derecho : pliegues en K para 40 puntos de datos

Desviación estándar de MSE (en conjuntos de datos i) vs Kfolds

De esta simulación, parece que:

• Para un número pequeño de puntos de datos, el aumento de hasta o menos mejora significativamente el sesgo y la varianza. Para más grande no hay ningún efecto sobre el sesgo o la varianza.K K = 10 $N = 40$$K$$K=10$$K$
• La intuición es que para un tamaño de entrenamiento efectivo demasiado pequeño, el modelo polinómico es muy inestable, especialmente para$K \leq 5$
• Para mayor , el aumento de no tiene un impacto particular tanto en el sesgo como en la varianza.$N = 200$$K$

Una revisión informal de la literatura.

Los siguientes tres artículos investigan el sesgo y la varianza de la validación cruzada

• Ron Kohavi (1995)
• Yves Grandvalet y Yoshua Bengio (2004)
• Zhang y Yang (2015)

Kohavi 1995

A menudo se hace referencia a este documento como la fuente del argumento de que LOOC tiene una mayor varianza. En la sección 1:

"Por ejemplo, dejar uno es casi imparcial, pero tiene una gran variación, lo que lleva a estimaciones poco confiables (Efron 1983)"

Esta declaración es fuente de mucha confusión, porque parece ser de Efron en 1983, no de Kohavi. Tanto los argumentos teóricos de Kohavi como los resultados experimentales van en contra de esta afirmación:

Corolario 2 (Variación en CV)

Dado un conjunto de datos y un inductor. Si el inductor es estable bajo las perturbaciones causadas por la eliminación de las instancias de prueba para los pliegues en k-fold CV para varios valores de , entonces la varianza de la estimación será la misma$k$

Experimento En su experimento, Kohavi compara dos algoritmos: un árbol de decisión C4.5 y un clasificador Naive Bayes en múltiples conjuntos de datos del repositorio de UC Irvine. Sus resultados son los siguientes: LHS es precisión frente a pliegues (es decir, sesgo) y RHS es desviación estándar frente a pliegues

De hecho, solo el árbol de decisión en tres conjuntos de datos claramente tiene una mayor varianza para aumentar K. Otros resultados muestran una varianza decreciente o constante.

Finalmente, aunque la conclusión podría estar más redactada, no hay argumento para que LOO tenga una mayor varianza, sino todo lo contrario. De la sección 6. Resumen

"La validación cruzada k-fold con valores moderados de k (10-20) reduce la varianza ... A medida que k-disminuye (2-5) y las muestras se hacen más pequeñas, hay varianza debido a la inestabilidad de los conjuntos de entrenamiento.

Zhang y Yang

Los autores tienen una opinión firme sobre este tema y lo establecen claramente en la Sección 7.1

De hecho, en la regresión lineal de mínimos cuadrados, Burman (1989) muestra que entre los CV de k veces, al estimar el error de predicción, LOO (es decir, CV de n veces) tiene el sesgo y la varianza asintótica más pequeños. ...

... Luego, un cálculo teórico ( Lu , 2007) muestra que LOO tiene el sesgo y la varianza más pequeños al mismo tiempo entre todos los CV de delete-n con todas las posibles eliminaciones de n_v

Resultados experimentales De manera similar, los experimentos de Zhang apuntan en la dirección de disminución de la varianza con K, como se muestra a continuación para el modelo Verdadero y el modelo incorrecto para la Figura 3 y la Figura 5.

El único experimento para el cual la varianza aumenta con es para los modelos Lasso y SCAD. Esto se explica como sigue en la página 31:$K$

Sin embargo, si la selección del modelo está involucrada, el rendimiento de LOO empeora en la variabilidad a medida que la incertidumbre de la selección del modelo aumenta debido al gran espacio del modelo, los coeficientes de penalización pequeños y / o el uso de coeficientes de penalización basados ​​en datos

$k$$k$$S$$S_i$$S \setminus S_i$$S_i$

$k>2$

$k$

Sin embargo, tenga en cuenta que, si bien la validación cruzada doble no tiene el problema de superponer conjuntos de entrenamiento, a menudo también tiene una gran variación porque los conjuntos de entrenamiento son solo la mitad del tamaño de la muestra original. Un buen compromiso es la validación cruzada diez veces.

Algunos documentos interesantes que tocan este tema (de muchos más):

• Un estudio de validación cruzada y bootstrap para la estimación de precisión y la selección del modelo por Ron Kohavi
• No hay un estimador imparcial de la varianza de la validación cruzada k-fold por Yoshua Bengio e Yves Grandvalet

$K$

Creo que su intuición es sensata si está pensando en las predicciones hechas por los modelos en cada pliegue de dejar uno afuera. Se basan en datos correlacionados / muy similares (el conjunto de datos completo menos un punto de datos) y, por lo tanto, harán predicciones similares, es decir, baja variabilidad.

Sin embargo, la fuente de confusión es que cuando las personas hablan de que LOOCV conduce a una alta variabilidad, no están hablando de las predicciones hechas por los muchos modelos construidos durante ese ciclo de validación cruzada en los conjuntos de reserva. En cambio, están hablando de cuánta variabilidad tendría su modelo final elegido (el elegido a través de LOOCV) si entrena ese modelo / parámetros exactos en nuevos conjuntos de entrenamiento: conjuntos de entrenamiento que su modelo no ha visto antes. En este caso, la variabilidad sería alta.

¿Por qué la variabilidad sería alta? Simplifiquemos esto un poco. Imagine que, en lugar de usar LOOCV para elegir un modelo, solo tenía un conjunto de entrenamiento y luego probó un modelo construido usando esos datos de entrenamiento, por ejemplo, 100 veces en 100 puntos de datos de prueba individuales (los puntos de datos no son parte del conjunto de entrenamiento) . Si elige el conjunto de modelos y parámetros que funciona mejor en esas 100 pruebas, entonces seleccionará uno que permita que este conjunto de entrenamiento en particular sea realmente bueno para predecir los datos de la prueba. Potencialmente, podría elegir un modelo que capture el 100% de las asociaciones entre ese conjunto de datos de entrenamiento en particular y los datos de reserva. Desafortunadamente, parte de esas asociaciones entre los conjuntos de datos de entrenamiento y prueba serán asociaciones de ruido o espurias porque, aunque el conjunto de prueba cambia y puede identificar el ruido de este lado, el conjunto de datos de entrenamiento no lo hace y no puede determinar qué variación explicada se debe al ruido. En otras palabras, lo que esto significa es que ha ajustado sus predicciones a este conjunto de datos de entrenamiento en particular.

Ahora, si tuviera que volver a entrenar este modelo con los mismos parámetros varias veces en nuevos conjuntos de entrenamiento, ¿qué pasaría? Bueno, un modelo que está sobreajustado a un conjunto particular de datos de entrenamiento conducirá a una variabilidad en su predicción cuando el conjunto de entrenamiento cambie (es decir, cambie el conjunto de entrenamiento ligeramente y el modelo cambiará sustancialmente sus predicciones).

Debido a que todos los pliegues en LOOCV están altamente correlacionados, es similar al caso anterior (mismo conjunto de entrenamiento; diferentes puntos de prueba). En otras palabras, si ese conjunto de entrenamiento en particular tiene una correlación espuria con esos puntos de prueba, su modelo tendrá dificultades para determinar qué correlaciones son reales y cuáles son espurias, porque a pesar de que el conjunto de prueba cambia, el conjunto de entrenamiento no.

En contraste, los pliegues de entrenamiento menos correlacionados significan que el modelo se ajustará a múltiples conjuntos de datos únicos. Entonces, en esta situación, si vuelve a entrenar el modelo en otro conjunto de datos nuevo, dará lugar a una predicción similar (es decir, una pequeña variabilidad).

Aunque esta pregunta es bastante antigua, me gustaría agregar una respuesta adicional porque creo que vale la pena aclarar esto un poco más.

Mi pregunta está en parte motivada por este hilo: número óptimo de pliegues en la validación cruzada de pliegues en K: ¿es el CV de dejar uno solo siempre la mejor opción? . La respuesta allí sugiere que los modelos aprendidos con la validación cruzada de dejar uno fuera tienen una varianza mayor que los aprendidos con la validación cruzada K-fold regular, lo que hace que el CV de dejar uno fuera sea una peor elección.

Esa respuesta no sugiere eso, y no debería. Repasemos la respuesta provista allí:

La validación cruzada Leave-one-out generalmente no conduce a un mejor rendimiento que K-fold, y es más probable que sea peor, ya que tiene una variación relativamente alta (es decir, su valor cambia más para diferentes muestras de datos que el valor para k-fold validación cruzada).

Está hablando de rendimiento . Aquí el rendimiento debe entenderse como el rendimiento del estimador de errores del modelo . Lo que está estimando con k-fold o LOOCV es el rendimiento del modelo, tanto al usar estas técnicas para elegir el modelo como para proporcionar una estimación de error en sí misma. Esta NO es la varianza del modelo, es la varianza del estimador del error (del modelo). Vea el ejemplo (*) a continuación.

Sin embargo, mi intuición me dice que en el CV de dejar uno fuera uno debería ver una variación relativamente menor entre los modelos que en el CV de K-fold, ya que solo estamos cambiando un punto de datos a través de los pliegues y, por lo tanto, los conjuntos de entrenamiento entre pliegues se superponen sustancialmente.

$n-2$$n$

Es precisamente esta menor varianza y mayor correlación entre modelos lo que hace que el estimador del que hablo anteriormente tenga más varianza, porque ese estimador es la media de estas cantidades correlacionadas, y la varianza de la media de los datos correlacionados es mayor que la de los datos no correlacionados . Aquí se muestra por qué: varianza de la media de datos correlacionados y no correlacionados .

O yendo en la otra dirección, si K es bajo en el CV de K-fold, los conjuntos de entrenamiento serían bastante diferentes entre los pliegues, y los modelos resultantes son más propensos a ser diferentes (por lo tanto, una mayor varianza).

En efecto.

Si el argumento anterior es correcto, ¿por qué los modelos aprendidos con CV de dejar uno tienen una mayor varianza?

El argumento anterior es correcto. Ahora, la pregunta está mal. La varianza del modelo es un tema completamente diferente. Hay una varianza donde hay una variable aleatoria. En el aprendizaje automático, se manejan muchas variables aleatorias, en particular y no se limitan a: cada observación es una variable aleatoria; la muestra es una variable aleatoria; el modelo, dado que está entrenado a partir de una variable aleatoria, es una variable aleatoria; el estimador del error que producirá su modelo cuando se enfrente a la población es una variable aleatoria; y por último, pero no menos importante, el error del modelo es una variable aleatoria, ya que es probable que haya ruido en la población (esto se llama error irreducible). También puede haber más aleatoriedad si hay estocasticidad involucrada en el proceso de aprendizaje modelo. Es de suma importancia distinguir entre todas estas variables.

$err$$err$$E$$\tilde{err}$$\tilde{err}$$var(\tilde{err})$$E(\tilde{err}-err)$$var(\tilde{err})$$k-fold$$k < n$$err = 10$$\tilde{err}_1$$\tilde{err}_2$

Debe preferirse el último, aunque tiene más sesgo, ya que tiene mucha menos varianza y un sesgo aceptable , es decir, un compromiso ( compensación de sesgo-varianza ). ¡Tenga en cuenta que tampoco desea una variación muy baja si eso conlleva un sesgo alto!

Nota adicional : en esta respuesta trato de aclarar (lo que creo que son) los conceptos erróneos que rodean este tema y, en particular, trata de responder punto por punto y precisamente las dudas que tiene el autor de la pregunta. En particular, trato de aclarar de qué variación estamos hablando , que es lo que esencialmente se pregunta aquí. Es decir, explico la respuesta que está vinculada por el OP.

Dicho esto, aunque proporciono el razonamiento teórico detrás de la afirmación, todavía no hemos encontrado evidencia empírica concluyente que la respalde. Así que por favor ten mucho cuidado.

Idealmente, primero debe leer esta publicación y luego consultar la respuesta de Xavier Bourret Sicotte, que proporciona una discusión perspicaz sobre los aspectos empíricos.

$k$$k-fold$$k$$10 \ \times \ 10-fold$

Los problemas son realmente sutiles. Pero definitivamente no es cierto que LOOCV tenga una mayor variación en general. Un artículo reciente analiza algunos aspectos clave y aborda varios conceptos erróneos aparentemente generalizados sobre la validación cruzada.

Yongli Zhang y Yuhong Yang (2015). Validación cruzada para seleccionar un procedimiento de selección de modelo. Revista de Econometría, vol. 187, 95-112.

Los siguientes conceptos erróneos se ven con frecuencia en la literatura, incluso hasta ahora:

"El CV Leave-one-out (LOO) tiene un sesgo menor pero una varianza mayor que el CV de dejar más afuera"

Esta vista es bastante popular. Por ejemplo, Kohavi (1995, Sección 1) declara: "Por ejemplo, dejar uno afuera es casi imparcial, pero tiene una gran variación, lo que lleva a estimaciones poco confiables". La declaración, sin embargo, no es generalmente cierta.

Con más detalle:

En la literatura, incluso en publicaciones recientes, hay recomendaciones excesivamente tomadas. La sugerencia general de Kohavi (1995) de utilizar 10 veces el CV ha sido ampliamente aceptada. Por ejemplo, Krstajic et al (2014, página 11) afirman: "Kohavi [6] y Hastie et al [4] muestran empíricamente que la validación cruzada de pliegue en V en comparación con la validación cruzada de dejar uno fuera tiene una varianza menor". En consecuencia, toman la recomendación de 10 CV (con repetición) para todas sus investigaciones numéricas. En nuestra opinión, tal práctica puede ser engañosa. Primero, no debe haber ninguna recomendación general que no tenga en cuenta el objetivo del uso de CV. En particular, El examen del sesgo y la varianza de la estimación de la precisión CV de un modelo candidato / procedimiento de modelado puede ser un asunto muy diferente de la selección óptima del modelo (con cualquiera de los dos objetivos de la selección del modelo establecidos anteriormente). En segundo lugar, incluso limitado al contexto de estimación de precisión, la afirmación generalmente no es correcta. Para modelos / procedimientos de modelado con baja inestabilidad, LOO a menudo tiene la variabilidad más pequeña. También hemos demostrado que para procedimientos altamente inestables (p. Ej., LASSO con pn mucho mayor que n), los CV de 10 o 5 veces, aunque reducen la variabilidad, pueden tener un MSE significativamente mayor que LOO debido a un aumento de sesgo aún peor. Para modelos / procedimientos de modelado con baja inestabilidad, LOO a menudo tiene la variabilidad más pequeña. También hemos demostrado que para procedimientos altamente inestables (p. Ej., LASSO con pn mucho mayor que n), los CV de 10 o 5 veces, aunque reducen la variabilidad, pueden tener un MSE significativamente mayor que LOO debido a un aumento de sesgo aún peor. Para modelos / procedimientos de modelado con baja inestabilidad, LOO a menudo tiene la variabilidad más pequeña. También hemos demostrado que para procedimientos altamente inestables (p. Ej., LASSO con pn mucho mayor que n), los CV de 10 o 5 veces, aunque reducen la variabilidad, pueden tener un MSE significativamente mayor que LOO debido a un aumento de sesgo aún peor.

En general, de las Figuras 3-4, LOO y CV repetidos de 50 y 20 veces son los mejores aquí, 10 veces es significativamente peor y k ≤ 5 es claramente pobre. Para la estimación predictiva del rendimiento, tendemos a creer que LOO suele ser el mejor o uno de los mejores para un modelo fijo o un procedimiento de modelado muy estable (como BIC en nuestro contexto) tanto en sesgo como en varianza, o bastante cercano al mejor en MSE para un procedimiento más inestable (como AIC o incluso LASSO con p ≫ n). Si bien el CV 10 veces (con repeticiones) ciertamente puede ser el mejor a veces, pero con mayor frecuencia, está en una posición incómoda: es más riesgoso que LOO (debido al problema de sesgo) para la estimación del error de predicción y generalmente es peor que eliminar -n / 2 CV para identificar al mejor candidato.

Antes de discutir sobre el sesgo y la varianza, la primera pregunta es:

¿Qué se estima mediante validación cruzada?

$K$$n(K-1)/K$$K$$K$

$K$

$K$

$K$

Creo que hay una respuesta más directa. Si aumenta k, los conjuntos de prueba se hacen cada vez más pequeños. Dado que los pliegues se muestrean aleatoriamente, puede suceder con conjuntos de prueba pequeños, pero no tan probable con los más grandes, que no sean representativos de una combinación aleatoria. Un conjunto de prueba podría contener todos los registros difíciles de predecir y otro todos los fáciles. Por lo tanto, la varianza es alta cuando predice conjuntos de pruebas muy pequeños por pliegue.