Validación cruzada K-fold vs. Monte Carlo

Question

Estoy intentando aprender varios métodos de validación cruzada, principalmente con la intención de aplicarlos a las técnicas de análisis multivariante supervisado. Dos de los que he encontrado son las técnicas de validación cruzada K-fold y Monte Carlo. He leído que K-fold es una variación de Monte Carlo, pero no estoy seguro de entender completamente lo que constituye la definición de Monte Carlo. ¿Podría alguien explicar la diferencia entre estos dos métodos?

Answer 1

$k$ -Validación cruzada de pliegues

Suponga que tiene 100 puntos de datos. Para $k$ -La validación cruzada doble, estos 100 puntos se dividen en $k$ de igual tamaño y que se excluyen mutuamente. Para $k$ =10, podría asignar los puntos 1-10 al pliegue #1, 11-20 al pliegue #2, y así sucesivamente, terminando por asignar los puntos 91-100 al pliegue #10. A continuación, seleccionamos un pliegue para que actúe como conjunto de prueba, y utilizamos el resto de $k-1$ pliegues para formar los datos de entrenamiento. Para la primera ejecución, podría utilizar los puntos 1-10 como conjunto de prueba y 11-100 como conjunto de entrenamiento. En la siguiente ejecución se utilizarían los puntos 11-20 como conjunto de prueba y se entrenaría con los puntos 1-10 más 21-100, y así sucesivamente, hasta que cada pliegue se utilice una vez como conjunto de prueba.

Validación cruzada de Monte-Carlo

Monte Carlo funciona de forma algo diferente. Se selecciona al azar (sin reemplazo) alguna fracción de los datos para formar el conjunto de entrenamiento, y luego se asigna el resto de los puntos al conjunto de prueba. Este proceso se repite varias veces, generando (al azar) nuevas particiones de entrenamiento y prueba cada vez. Por ejemplo, supongamos que decide utilizar el 10% de sus datos como datos de prueba. Entonces, su conjunto de prueba en la repetición nº 1 podría ser de 64 puntos, 90 , 63, 42 , 65, 49, 10, 64, 96 y 48. En la siguiente ejecución, su conjunto de pruebas podría ser 90 , 60, 23, 67, 16, 78, 42 , 17, 73 y 26. Como las particiones se hacen de forma independiente para cada ejecución, el mismo punto puede aparecer en el conjunto de pruebas varias veces, que es la principal diferencia entre Monte Carlo y la validación cruzada .

Comparación

Cada método tiene sus propias ventajas e inconvenientes. En la validación cruzada, cada punto se prueba exactamente una vez, lo que parece justo. Sin embargo, la validación cruzada sólo explora algunas de las posibles formas en que los datos podrían haberse dividido. Monte Carlo le permite explorar más particiones posibles, aunque es poco probable que las obtenga todas: hay $\binom{100}{50} \approx 10^{28}$ formas posibles de dividir 50/50 un conjunto de 100 puntos de datos (!).

Si se intenta hacer inferencia (es decir, comparar estadísticamente dos algoritmos), el promedio de los resultados de un $k$ -La validación cruzada doble le proporciona una estimación (casi) insesgada del rendimiento del algoritmo, pero con una alta varianza (como cabría esperar por tener sólo 5 o 10 puntos de datos). Dado que, en principio, puede ejecutarlo durante todo el tiempo que quiera/pueda permitirse, la validación cruzada de Monte Carlo puede proporcionarle una estimación menos variable, pero más sesgada.

Algunos enfoques fusionan los dos, como en la validación cruzada 5x2 (véase Dietterich (1998) por la idea, aunque creo que ha habido algunas mejoras desde entonces), o corrigiendo el sesgo (por ejemplo Nadeau y Bengio, 2003 ).

Answer 2

Supongamos que $ N $ es el tamaño del conjunto de datos, $k$ es el número de la $k$ -subconjuntos dobles , $n_t$ es el tamaño del conjunto de entrenamiento y $n_v$ es el tamaño del conjunto de validación. Por lo tanto, $N = k \times n_v$ para $k$ -validación cruzada y $N = n_t + n_v$ para la validación cruzada de Monte Carlo.

$k$ -validación cruzada (kFCV) divide el $N$ puntos de datos en $k$ subconjuntos mutuamente excluyentes de igual tamaño. A continuación, el proceso deja fuera uno de los $k$ como conjunto de validación y se entrena en los subconjuntos restantes. Este proceso se repite $k$ veces, dejando fuera una de las $k$ subconjuntos cada vez. El tamaño de $k$ puede ir desde $N$ a $2$ ( $k = N$ se denomina validación cruzada leave-one-out). Los autores en [2] sugieren establecer $k = 5$ o $10$ .

Validación cruzada de Monte Carlo (MCCV) simplemente divide el $N$ puntos de datos en los dos subconjuntos $n_t$ y $n_v$ por muestreo, sin reemplazo, $n_t$ puntos de datos. A continuación, el modelo se entrena con un subconjunto $n_t$ y validado en el subconjunto $n_v$ Existe $ {N\choose n_t} $ conjuntos de entrenamiento únicos, pero MCCV evita la necesidad de realizar tantas iteraciones. Zhang [3] muestra que la ejecución de MCCV para $N^2$ iteraciones tiene resultados cercanos a la validación cruzada sobre todos los $ {N\choose n_t} $ conjuntos de entrenamiento únicos. Cabe destacar que la literatura carece de investigaciones para N grandes.

La elección de $k$ y $n_t$ afecta a la compensación de sesgo/varianza. Cuanto mayor sea $k$ o $n_t$ cuanto menor sea el sesgo y mayor la varianza. Los conjuntos de entrenamiento más grandes son más similares entre las iteraciones, por lo que se sobreajustan a los datos de entrenamiento. Véase [2] para más información sobre este tema. El sesgo y la varianza de kFCV y MCCV son diferentes, pero el sesgo de los dos métodos puede igualarse eligiendo niveles adecuados de $k$ y $n_t$ . Los valores del sesgo y la varianza para ambos métodos se muestran en [1] (en este documento se refiere a MCCV como modelo de prueba de aprendizaje repetido).

---

[1] Burman, P. (1989). Un estudio comparativo de la validación cruzada ordinaria, $v$ -La validación cruzada doble y los métodos de prueba de aprendizaje repetido. Bometrika 76 503-514.

[2] Hastie, T., Tibshirani, R. y Friedman, J. (2011). Los elementos del aprendizaje estadístico: Minería de datos, inferencia y predicción. Segunda edición. Nueva York: Springer.

[3] Zhang, P. (1993). Model Selection Via Muiltfold Cross Validation. Ann. Stat. 21 299-313

Answer 3

Las otras dos respuestas son geniales, sólo añadiré dos imágenes así como un sinónimo.

---

K-fold cross-validation (kFCV):

Validación cruzada de Monte Carlo (MCCV) = Validación por submuestreo aleatorio repetido (RRSSV):

---

Referencias:

Las imágenes proceden de (1) ( páginas 64 y 65 ), y el sinónimo se menciona en (1) y (2).

• (1) Remesan, Renji, y Jimson Mathew. Modelización hidrológica basada en datos: Un enfoque de estudio de casos . Vol. 1. Springer, 2014.

• (2) Dubitzky, Werner, Martin Granzow y Daniel P. Berrar, eds. Fundamentos de la minería de datos en genómica y proteómica . Springer Science & Business Media, 2007.

Answer 4

¿Y en la práctica?

En determinadas situaciones (datos más pequeños), combino tanto Monte Carlo como K-Fold CV en una validación cruzada repetida y anidada:

1. CV interno de K-fold para la selección de hiperparámetros
2. CV exterior de K-fold para estimar el rendimiento de la generalización
3. Ahora, repita los pasos 1 y 2 muchas veces (Monte Carlo).

Si para 2. utilizas K=5, y luego lo repites 100 veces en el paso 3, tendrás 5*100 = 500 estimaciones de rendimiento de generalización.

Esto está disponible en scikit-learn como Validación cruzada K-fold repetida (estratificada): Documentos de scikit-learn . Véase también la validación cruzada anidada y no anidada: Documentos de scikit-learn

Answer 5

K-fold CV se entrena con más datos de los que se tienen para la validación; esto es un problema. MCCV tiene un gran potencial para corregir este error; para más detalles, véase más adelante, pero el conjunto de validación debería siempre ser al menos tan grande como el conjunto de entrenamiento, y no al revés.

Según el libro seminal de Jun Shao de 1993 papel En el artículo "Linear Model Selection by Cross-Validation", publicado en el volumen 88, número 422 del Journal of the American Statistical Association, la validación cruzada de Montecarlo (MCCV) tendría como resultado óptimo al menos el mismo número $b$ de pliegues como puntos $n$ en el conjunto de datos para el entrenamiento y la prueba (las simulaciones en papel utilizan $b = 2n$ repetido mil veces con la probabilidad empírica de seleccionar un modelo "verdadero" conocido que se informa en la última sección del documento).

En las simulaciones de Shao, el tamaño de cada conjunto de entrenamiento, ya sea para LOOCV o MCCV (también incluía un diseño aproximado de bloques incompletos o BIBD) era $n_c \approx \sqrt[4]{n^3}$ es decir, la parte entera de la fracción (después de truncarla). Por ejemplo, con un conjunto global de $n = 10,000$ puntos de datos, cada conjunto de entrenamiento tendría un tamaño $n_c = 1,000 = \sqrt[4]{10,000^3}$ . Además, el $n_c$ ejemplos de formación para cada uno de los $b \geq n $ Los pliegues para MCCV se extrajeron aleatoriamente sin ni siquiera estratificar por clase, y sin tener en cuenta si los sorteos eran con o sin reemplazo.

Para $k$ -En cambio, en la validación cruzada doble, se determina arbitrariamente el número $k$ de pliegues antes de empezar, así como los tamaños de cada entrenamiento ( $n_c$ ) y las pruebas ( $n - n_c$ ) partición. No se dibuja al azar, sino en el orden de aparición de los datos dentro del marco/matriz de datos (aunque se podría barajar una vez antes de elegir los pliegues). Si el número $n = k \cdot n_c$ de puntos de datos es impar, uno podría verse obligado arbitrariamente a seleccionar un número impar $k$ de pliegues para que cada conjunto de entrenamiento tenga estrictamente el mismo tamaño $n_c = n/k$ .