Avaliar floresta aleatória: OOB vs CV

13

Quando avaliamos a qualidade de uma floresta aleatória, por exemplo, usando AUC, é mais apropriado calcular essas quantidades nas amostras fora da bolsa ou no conjunto de validação cruzada de espera?

Ouvi dizer que calculá-lo sobre as amostras OOB oferece uma avaliação mais pessimista, mas não vejo o porquê.

user695652
fonte

Respostas:

12

Nota: Embora eu ache que minha resposta provavelmente esteja correta, também me sinto em dúvida devido ao fato de ter inventado tudo isso pensando nesse problema somente depois de ler essa pergunta por cerca de 30 a 60 minutos. Então é melhor você ser cético e examinar isso e não se deixar enganar pelo meu estilo de escrita possivelmente muito confiante (eu usar palavras grandes e símbolos gregos extravagantes não significa que estou certo).

Sumário

Este é apenas um resumo. Todos os detalhes são mencionados nas seções §1 e §2 abaixo.

Vamos assumir o caso da classificação (também pode ser estendido à regressão, mas omitir a brevidade). Essencialmente, nosso objetivo é estimar o erro de uma floresta de árvores. O erro fora da bolsa e a validação cruzada k-fold tentam nos dizer a probabilidade de que:

  • A floresta fornece a classificação correta (a validação cruzada da dobra k olha dessa maneira).

O que é idêntico à probabilidade de que:

  • O voto da maioria das árvores da floresta é o voto correto (o OOBE olha dessa maneira).

E ambos são idênticos. A única diferença é que a validação cruzada k-fold e o OOBE assumem diferentes tamanhos de amostras de aprendizado. Por exemplo:

  • Na validação cruzada 10 vezes, o conjunto de aprendizado é de 90%, enquanto o conjunto de testes é de 10%.
  • No entanto, no OOBE, se cada bolsa tiver amostras, de modo que n = número total de amostras no conjunto de amostras completo, isso implica que o conjunto de aprendizado é praticamente de cerca de 66% (dois terços) e o conjunto de testes é de cerca de 33% ( um terço).nn=

Portanto, na minha opinião, a única razão pela qual o OOBE é uma estimativa pessimista do erro da floresta é apenas porque ele geralmente treina com um número menor de amostras do que o normalmente feito com a validação cruzada de dobras k (onde 10 dobras são comuns).

Por esse motivo, também acho que a validação cruzada em duas vezes será uma estimativa mais pessimista do erro da floresta que o OOBE e a validação cruzada em três vezes será aproximadamente igualmente pessimista para o OOBE.

1. Entendendo o erro fora da bolsa

1.1 Visão comum sobre ensacamento

Cada árvore no RF é cultivada por uma lista de amostras que são sorteadas aleatoriamente do conjunto de aprendizado X com substituição. Desta forma, os n muitas amostras podem ter duplicatas, e se n = | X | pode-se descobrir que aproximadamente um terço das amostras em X provavelmente não consta da lista de n amostras usadas para cultivar uma determinada árvore (essas são as amostras prontas para uso dessa árvore específica. Esse processo é repetido independentemente para cada árvore, para que cada árvore tenha um conjunto diferente de amostras prontas para uso.nXnn=|X|Xn

1.2 Outra visão sobre ensacamento

Agora, vamos re-descrever o empacotamento de maneira um pouco diferente, com a esperança de encontrar uma descrição igual que, esperamos, seja mais simples de lidar.

Eu faço isso, afirmando que a árvore é treinado pelas amostras ensacadas no conjunto X tX . No entanto, isso não é exatamente verdade, pois o conjunto X t não possui amostras duplicadas (é assim que os conjuntos funcionam), enquanto, por outro lado, a n lista de amostras pode ter duplicatas.tXtXXtn

Portanto, podemos dizer que uma árvore é cultivada analisando as amostras X t mais um número de duplicatas escolhidas aleatoriamente, extraídas de X t , ou seja, X t , 1 , X t , 2 , , X t , rX t , como que: | X t | + r i = 1 | X t , i | = ntXt XtXt,1,Xt,2,,Xt,rXt

|Xt|+Eu=1r|Xt,Eu|=n

É trivial para ver que a partir desta colecção de conjuntos , pode-se definir uma lista de n amostras -muitos que contêm duplicados por simplesmente adicionando os elementos em cada defina C iCC={Xt,Xt,1,,Xt,r}nCiC para uma matriz . Dessa forma, para qualquer 1 p n , existe pelo menos um valor de i tal que um [ p ] C ia1pnia[p]Ci.

Também podemos ver que a lista de amostras na matriz a é uma generalização de ensacamento, conforme definido na Seção 1. É trivial ver que, para alguma definição específica de X t que defini nesta seção ( § 2 ) , a lista de amostras na matriz a pode ser exatamente idêntica à lista de amostras, conforme definido na Seção 1.naXt§2a

1.3 Simplificando o ensacamento

Em vez de aumentar a árvore por amostras na matriz a , vamos aumentá-las pela lista de instâncias sem duplicação que são encontradas apenas em X t .taXt

Acredito que, se for grande o suficiente, uma árvore t que é cultivada pela análise de amostras em X t é idêntica a outra árvore t ' que é cultivada a partir das amostras da matriz a .ntXtta

Minha razão é que, a probabilidade de duplicar amostras em é igualmente provável em outras amostras no mesmo conjunto. Isso significa que, quando medimos o ganho de informação (IG) de alguma divisão, o IG permanecerá idêntico, pois as entropias também permanecerão idênticas.Xt

E a razão pela qual acredito que as entropias não mudarão sistematicamente para uma determinada divisão é porque a probabilidade empiricamente medida de uma amostra com uma etiqueta específica em algum subconjunto (após aplicar uma divisão de decisão) também não será alterada.

E a razão as probabilidades não deve mudar na minha opinião é que que todas as amostras de são igualmente propensos a ser duplicado em d cópias.Xtd

1.4 Medindo erros fora da bolsa

Seja as amostras prontas da árvore t . Ou seja, O t = XX t . Então o erro de uma única árvore tOttOt=XXtt é: x E o erro total da floresta comntmuitas árvores é: Σ n t t = 1

total x in Ot correctly classified by t|Ot|
nt que pode ser pensada como aprobabilidadeempiricamente medida deque a maioria dos votos de todas as árvores em uma floresta é uma votação correta.
t=1nttotal x in Ot correctly classified by tt=1nt|Ot|

2. Compreendendo a validação cruzada k-fold

XnkK={K1,K2,,Knk}K1K2Knk=XKi,KjKKiKj=

KtK{Kt}

fK{Kt}

f

t=1nktotal x in Kt correctly classified by ft=1nk|Kt|

f

homem das cavernas
fonte