Cuando evaluamos la calidad de un Bosque Aleatorio, por ejemplo utilizando el AUC, ¿es más apropiado calcular estas cantidades sobre las muestras fuera de bolsa o sobre el conjunto de validación cruzada?
He oído que calcularlo sobre las muestras de OOB da una valoración más pesimista, pero no veo por qué.
Nota: Aunque creo que mi respuesta es probablemente correcta, también me siento dudoso debido al hecho de que inventé todo esto pensando en este problema sólo después de leer esta pregunta durante unos 30-60 minutos. Así que será mejor que seáis escépticos y analicéis esto y no os dejéis engañar por mi estilo de escritura, posiblemente demasiado confiado (que yo utilice palabras grandes y símbolos griegos extravagantes no significa que tenga razón).
Esto es sólo un resumen. Todos los detalles se mencionan en las secciones $\S1$ y $\S2$ abajo.
Supongamos el caso de la clasificación (puede extenderse también a la regresión, pero se omite por brevedad). Esencialmente, nuestro objetivo es estimar el error de un bosque de árboles. Tanto el error fuera de bolsa como la validación cruzada k-fold tratan de decirnos la probabilidad de que:
Que es idéntica a la probabilidad de que:
Y ambos son idénticos. La única diferencia es que la validación cruzada k-fold y la OOBE suponen un tamaño diferente de las muestras de aprendizaje. Por ejemplo:
Por lo tanto, en mi opinión, la única razón por la que el OOBE es una estimación pesimista del error del bosque es sólo porque normalmente entrena mediante un número menor de muestras que el que se suele hacer con la validación cruzada k-fold (en la que lo habitual son 10 pliegues).
Debido a esto, también creo que la validación cruzada de 2 veces va a ser una estimación más pesimista del error del bosque que el OOBE, y la validación cruzada de 3 veces va a ser aproximadamente igual de pesimista que el OOBE.
Cada árbol de la RF es cultivado por una lista de $n$ muestras que son al azar extraído del conjunto de aprendizaje $\mathcal{X}$ con sustitución. De esta manera, el $n$ muchas muestras pueden tener duplicados, y si $n = |\mathcal{X}|$ entonces se puede encontrar que aproximadamente un tercio de las muestras en $\mathcal{X}$ es probable que no estén en la lista de $n$ que se utilizan para cultivar un árbol determinado (son las muestras fuera de bolsa de este árbol concreto). Este proceso se repite de forma independiente para cada árbol, por lo que cada árbol tiene un conjunto diferente de muestras fuera de bolsa.
Ahora, vamos a volver a describir el embolsamiento de una manera un poco diferente con la esperanza de encontrar una descripción igual que, esperemos, sea más sencilla de tratar.
Lo hago afirmando que el árbol $t$ se entrena con las muestras embolsadas del conjunto $\mathcal{X}_t \subseteq \mathcal{X}$ . Sin embargo, esto no es exactamente cierto ya que el conjunto $\mathcal{X}_t$ no tiene muestras duplicadas (así funcionan los conjuntos), mientras que -por otro lado- el $n$ La lista de muestras puede tener duplicados.
Por lo tanto, podemos decir que un árbol $t$ se cultiva mediante el análisis de muestras $\mathcal{X}_t$ más un número de duplicados elegidos al azar de entre $\mathcal{X}_t$ , a saber $\mathcal{X}_{t,1}, \mathcal{X}_{t,2}, \ldots, \mathcal{X}_{t,r} \subseteq \mathcal{X}_t$ tal que..: \begin {equation} | \mathcal {X}_t| + \sum_ {i=1}^r| \mathcal {X}_{t,i}| = n \end {Ecuación}
Es trivial ver que a partir de esta colección de conjuntos $\mathcal{C} = \{\mathcal{X}_t, \mathcal{X}_{t,1}, \ldots, \mathcal{X}_{t,r}\}$ podemos definir una lista de $n$ -muchas muestras que contienen duplicados simplemente añadiendo los elementos de cada conjunto $\mathcal{C}_i \in \mathcal{C}$ a una matriz $a$ . De esta manera, para cualquier $1 \le p \le n$ existe al menos un valor de $i$ tal que $a[p] \in \mathcal{C}_i$ .
También podemos ver que la lista de $n$ muestras en la matriz $a$ es una generalización del ensacado tal y como lo definí en la sección 1. Es trivial ver que para alguna definición específica de $\mathcal{X}_t$ que he definido en esta sección ( $\S2$ ), lista de muestras en el array $a$ puede ser exactamente idéntico a la lista de muestras definida en la sección 1.
En lugar de cultivar el árbol $t$ por muestras en array $a$ , los haremos crecer por la lista de instancias libres de duplicación que se encuentran en $\mathcal{X}_t$ sólo.
Creo que, si $n$ es lo suficientemente grande, un árbol $t$ que se cultiva mediante el análisis de muestras en $\mathcal{X}_t$ es idéntico a otro árbol $t'$ que se cultiva a partir de las muestras de la matriz $a$ .
Mi razón es que, la probabilidad de duplicar muestras en $\mathcal{X}_t$ es igualmente probable en otras muestras del mismo conjunto. Esto significa que, cuando midamos la ganancia de información (GI) de alguna división, la GI seguirá siendo idéntica, ya que las entropías también lo serán.
Y la razón por la que creo que las entropías no cambiarán sistemáticamente para una determinada división es porque la probabilidad medida empíricamente de que una muestra tenga una etiqueta específica en algún subconjunto (después de aplicar una división de decisión) tampoco cambiará.
Y la razón por la que las probabilidades no deberían cambiar en mi opinión es que todas las muestras en $\mathcal{X}_t$ son igualmente susceptibles de ser duplicados en $d$ copias.
Dejemos que $\mathcal{O}_t$ sean las muestras fuera de bolsa del árbol $t$ . Es decir $\mathcal{O}_t = \mathcal{X} \setminus \mathcal{X}_t$ . Entonces el error de un solo árbol $t$ es: \begin {Ecuación} \frac { \text {total $\mathbf{x}$ en $\mathcal{O}_t$ correctamente clasificado por $t$ }}{| \mathcal {O}_t|} \end {Ecuación} Y el error total del bosque con $n_t$ muchos árboles es: \begin {Ecuación} \frac { \sum_ {t=1}^{n_t} \text {total $\mathbf{x}$ en $\mathcal{O}_t$ correctamente clasificado por $t$ }}{ \sum_ {t=1}^{n_t}| \mathcal {O}_t|} \end {ecuación} que puede considerarse como la medida empírica probabilidad de que el voto mayoritario de todos los árboles de un bosque sea un voto correcto .
En primer lugar, dividimos el conjunto de aprendizaje $\mathcal{X}$ en $n_k$ muchas particiones de igual tamaño, a saber $\mathcal{K} = \{\mathcal{K}_1, \mathcal{K}_2, \ldots, \mathcal{K}_{n_k}\}$ . Es decir $\mathcal{K}_1 \cup \mathcal{K}_2 \cup \ldots \cup \mathcal{K}_{n_k} = \mathcal{X}$ y para cualquier $\mathcal{K}_i, \mathcal{K}_j \in \mathcal{K}$ , $\mathcal{K}_i \cap \mathcal{K}_j = \emptyset$ (esto es lo que implica el racionamiento).
Dejemos que $\mathcal{K}_t$ sea el pliegue de la prueba, y $\mathcal{K} \setminus \{\mathcal{K}_t\}$ sea el conjunto de pliegues de aprendizaje.
Dejemos que $f$ ser un bosque de algunos árboles que se construye utilizando $\mathcal{K} \setminus \{\mathcal{K}_t\}$ como conjunto de aprendizaje.
A continuación, la validación cruzada k-fold del bosque $f$ es: \begin {Ecuación} \frac { \sum_ {t=1}^{n_k} \text {total $\mathbf{x}$ en $\mathcal{K}_t$ correctamente clasificado por $f$ }}{ \sum_ {t=1}^{n_k} | \mathcal {K}_t|} \end {Ecuación}
Que es también la probabilidad de que el bosque $f$ clasifica correctamente cualquier muestra de entrada.
La motivación :
Por lo tanto, en mi opinión, la única razón por la que la OOBE es una estimación pesimista estimación del error del bosque es sólo porque suele entrenar con un menor número de muestras que el que se suele hacer con la validación cruzada k-fold (donde 10 pliegues son comunes).
no parece correcto.
No es cierto que el hecho de que la estimación del error de OOBE sea pesimista se deba a que se haya entrenado con un número menor de muestras, sino que ocurre lo contrario. De hecho, cada árbol único de bosque aleatorio se entrena con una muestra del conjunto de entrenamiento, por lo que, mientras tanto, es cierto que, de media, cada árbol ve alrededor del 66% del conjunto de entrenamiento, pero, en general, el conjunto de bosques aleatorios ve más que eso (dependiendo del número de árboles ajustados) porque el las muestras fuera de bolsa de los árboles individuales no pueden superponerse . Por lo tanto, suponiendo que ajustamos un bosque aleatorio compuesto por $B$ a todo el conjunto de entrenamiento compuesto por $n$ muestras (como en el caso de la OOBE) tenemos eso:
por término medio, cada muestra $z_i$ aparece en el conjunto de entrenamiento de $\frac{2}{3}B$ y en las muestras fuera de bolsa del resto de $\frac{1}{3}B$
la probabilidad de que $z_j$ no aparece en el conjunto de entrenamiento de $m$ árboles seleccionados es $p_m = (\frac{1}{3})^m$
De los dos puntos anteriores se deduce que el OOBE en la muestra $z_i$ se calcula en promedio considerando un subconjunto de $\frac{1}{3}B$ árboles que se forman colectivamente en $n_{OOB}(B) = n-1-np_{\frac{B}{3}} = n(1-p_{\frac{B}{3}})-1$ muestras de datos en promedio.
Cuando estimamos el error con k-fold cv en cambio estamos haciendo lo siguiente (tomemos $k=10$ ): encajamos $B$ árboles utilizando $0.9n$ muestras de datos, pero de nuevo cada árbol utiliza una versión de entrenamiento con un bootstrap, por lo que colectivamente el conjunto ve $n_{10-Fold}(B) = 0.9n(1-p_B)$ muestras de datos en promedio. Entonces, considerando que $p_{\frac{B}{3}}<0.1$ implica que $n_{OOB} > n_{10-fold}$ concluimos que el conjunto de entrenamiento colectivo es mayor en el caso OOB siempre que $B>6$ , que es casi siempre en la práctica.
Teniendo en cuenta lo que hemos encontrado más arriba, ¿qué podemos decir de la estimación del CV OOB frente al CV k-fold para los bosques aleatorios? ¿Es el OOB pesimista?
Dado que el OOBE se evalúa en conjuntos que han visto colectivamente más datos, en realidad debería ser una estimación menos pesimista del error de la prueba con respecto a k-fold CV. Sin embargo, dado que los conjuntos OOBE se componen de menos árboles y se entrenan en conjuntos de entrenamiento superpuestos, la varianza de la estimación puede ser mayor.
En realidad, incluso se puede demostrar que para $\lim_{B\to\infty} $ la OOBE converge a la estimación del error LOO-CV (leave one out cross validation)[1] que es insesgada pero con mayor varianza respecto a k-fold CV con $k<n$ . Así que ninguno de los dos estimadores es por defecto mejor que el otro, aunque el OOBE tiene una clara ventaja computacional ya que se puede "ajustar y probar" el bosque al mismo tiempo.
[1] Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
