Variação das estimativas de validação cruzada com

37

TL, DR: Parece que, ao contrário do conselho muitas vezes repetida, leave-one-out validação cruzada (LOO-CV) - isto é,CV fold com(o número de dobras) igual a(o número das observações de treinamento) - produz estimativas do erro de generalização que é a menor variável para qualquer, não a mais variável, assumindo uma certacondição de estabilidade no modelo / algoritmo, no conjunto de dados ou em ambos (não tenho certeza de qual está correto porque eu realmente não entendo essa condição de estabilidade).K N KKKNK

  • Alguém pode explicar claramente o que exatamente é essa condição de estabilidade?
  • É verdade que a regressão linear é um desses algoritmos "estáveis", o que implica que, nesse contexto, o LOO-CV é estritamente a melhor escolha de CV no que diz respeito ao viés e variação das estimativas de erro de generalização?

A sabedoria convencional é que a escolha de K em CV com K fold segue uma troca de viés e variância; valores mais baixos de K (aproximando-se de 2) levam a estimativas do erro de generalização que têm viés mais pessimista, mas menor variação, enquanto valores mais altos de K (aproximando-se de N ) levam a estimativas menos tendenciosas, mas com maior variação. A explicação convencional para esse fenômeno de variação que aumenta com K é dada talvez com mais destaque em Os elementos do aprendizado estatístico (Seção 7.10.1):

Com K = N, o estimador de validação cruzada é aproximadamente imparcial para o erro de previsão verdadeiro (esperado), mas pode ter alta variação porque os N "conjuntos de treinamento" são muito semelhantes entre si.

A implicação é que os N erros de validação são mais altamente correlacionados, de modo que sua soma é mais variável. Essa linha de raciocínio foi repetida em muitas respostas neste site (por exemplo, aqui , aqui , aqui , aqui , aqui , aqui e aqui ), bem como em vários blogs e etc. Mas uma análise detalhada praticamente nunca é fornecida, em vez disso apenas uma intuição ou um breve esboço de como pode ser uma análise.

No entanto, pode-se encontrar afirmações contraditórias, geralmente citando uma certa condição de "estabilidade" que eu realmente não entendo. Por exemplo, esta resposta contraditória cita alguns parágrafos de um artigo de 2015 que diz, entre outras coisas, "Para modelos / procedimentos de modelagem com baixa instabilidade , a LOO geralmente tem a menor variabilidade" (ênfase adicionada). Este artigo (seção 5.2) parece concordar que o LOO representa a opção menos variável de K , desde que o modelo / algoritmo seja "estável". Tomando ainda outra posição sobre o assunto, há também este artigo (Corolário 2), que diz "A variação da validação cruzada de k fold [...] não depende de k, "citando novamente uma certa condição de" estabilidade ".

A explicação sobre por que o LOO pode ser o CV com dobra mais variável Ké intuitiva o suficiente, mas há uma contra-intuição. A estimativa final do CV do erro quadrático médio (MSE) é a média das estimativas do MSE em cada dobra. Assim, à medida que K aumenta até N , a estimativa CV é a média de um número crescente de variáveis ​​aleatórias. E sabemos que a variância de uma média diminui com o número de variáveis ​​sendo calculadas sobre a média. Portanto, para que o LOO seja o CV mais variável em K , seria necessário que o aumento da variação devido ao aumento da correlação entre as estimativas do MSE superasse a diminuição da variação devido ao maior número de dobras sendo calculadas. E não é de todo óbvio que isso seja verdade.

Tendo ficado completamente confuso pensando sobre tudo isso, decidi fazer uma pequena simulação para o caso de regressão linear. I simulada 10.000 conjuntos de dados com = 50 e 3 preditores não correlacionados, cada vez que a estimativa do erro de generalização utilizando K CV fold com K = 2, 5, 10, ou 50 = N . O código R está aqui. Aqui estão as médias e variações resultantes das estimativas de CV em todos os 10.000 conjuntos de dados (em unidades MSE):NKKN

         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

Esses resultados mostram o padrão esperado de que valores mais altos de levam a um viés menos pessimista, mas também parecem confirmar que a variação das estimativas de CV é mais baixa, e não mais alta, no caso da LOO.K

Portanto, parece que a regressão linear é um dos casos "estáveis" mencionados nos artigos acima, onde o aumento de está associado à diminuição, em vez de aumento da variância nas estimativas de CV. Mas o que eu ainda não entendo é:K

  • O que exatamente é essa condição de "estabilidade"? Aplica-se a modelos / algoritmos, conjuntos de dados ou ambos, até certo ponto?
  • Existe uma maneira intuitiva de pensar sobre essa estabilidade?
  • Quais são outros exemplos de modelos / algoritmos ou conjuntos de dados estáveis ​​e instáveis?
  • É relativamente seguro assumir que a maioria dos modelos / algoritmos ou conjuntos de dados são "estáveis" e, portanto, que deve geralmente ser escolhido o mais alto possível em termos computacionais?K
Jake Westfall
fonte
11
+1. O que exatamente é "mau" nos seus resultados de simulação? Estimativa CV média do erro de generalização (média entre 10.000 conjuntos de dados)? Mas com o que devemos compará-lo? Seria mais significativo mostrar o viés, ou seja, o desvio médio da raiz quadrada do verdadeiro erro de generalização. Além disso, o que é "verdadeiro erro de generalização" neste caso? Verdadeiro erro de generalização da estimativa em um dado conjunto de dados N = 100? Ou valor esperado do verdadeiro erro de generalização (valor esperado em todos os conjuntos de dados N = 100)? Ou alguma outra coisa?
Ameba diz Reinstate Monica
3
+1. Após uma breve olhada em en.wikipedia.org/wiki/… , parece que neste contexto estabilidade significa que um algoritmo produz resultados semelhantes no conjunto de treinamento com exemplos e N - 1 . Onde meios semelhantes diferença wrt alguma função perda delimitada por algum valor baixoNN-1 1
Łukasz Grad
11
Além disso, recentemente conversei sobre isso com @DikranMarsupial (que provavelmente é um dos nossos principais especialistas em validação cruzada aqui no CV) aqui nos comentários - ele sugeriu ler o artigo de Kohavi em 1995 . Dikran também estava falando sobre estabilidade. Infelizmente, não acompanhei desde então.
Ameba diz Reinstate Monica
2
Acho que não, @Jake. O que escrevi invalida sua "contra-intuição", mas a principal "intuição" (sobre modelos de dobras diferentes sendo altamente dependentes) ainda é válida.
Ameba diz Reinstate Monica
11
Outra simulação suportando suas conclusões de que a variação diminui com : stats.stackexchange.com/a/357749/28666 . K
Ameba diz Reinstate Monica

Respostas:

15

Essa resposta segue a minha resposta em Viés e variação na validação cruzada de um para fora versus dobra em K que discute por que o LOOCV nem sempre leva a uma variação maior. Seguindo uma abordagem semelhante, tentarei destacar um caso em que o LOOCV leva a uma maior variação na presença de outliers e a um "modelo instável".

Estabilidade algorítmica (teoria da aprendizagem)

O tópico da estabilidade algorítmica é recente e vários resultados clássicos e influenciados foram comprovados nos últimos 20 anos. Aqui estão alguns artigos que são freqüentemente citados

A melhor página para entender é certamente a página da wikipedia, que fornece um excelente resumo escrito por um usuário presumivelmente muito experiente.

Definição intuitiva de estabilidade

Intuitivamente, um algoritmo estável é aquele para o qual a previsão não muda muito quando os dados de treinamento são modificados levemente.

Formalmente, existem meia dúzia de versões de estabilidade, vinculadas por condições e hierarquias técnicas; veja este gráfico aqui, por exemplo:

insira a descrição da imagem aqui

O objetivo, no entanto, é simples: queremos obter limites rígidos sobre o erro de generalização de um algoritmo de aprendizado específico, quando o algoritmo satisfizer o critério de estabilidade. Como seria de esperar, quanto mais restritivo for o critério de estabilidade, mais apertado será o limite correspondente.

Notação

A seguinte notação é do artigo da wikipedia, que copia o artigo de Bousquet e Elisseef:

  • O conjunto de treino é extraído iid de uma distribuição desconhecida DS={z1 1=(x1 1,y1 1),...,zm=(xm,ym)}
  • A função de perda de uma hipótese f em relação a um exemplo z é definida como V ( f , z )VfzV(f,z)
  • Modificamos o conjunto de treinamento removendo o ésimo elemento: S | i = { z 1 , . . . , Z i - 1 , z i + 1 , . . . , z m }EuS|Eu={z1 1,...,zEu-1 1,zEu+1 1,...,zm}
  • Ou substituindo a o elemento -ésimo: S i = { z 1 , . . . , z i - 1 , zEuSEu={z1 1,...,zEu-1 1,zEu,zEu+1 1,...,zm}

Definições formais

Talvez a noção mais forte de estabilidade que um algoritmo interessante de aprendizado possa obedecer seja a de estabilidade uniforme :

Estabilidade uniforme Um algoritmo possui estabilidade uniforme com relação à função de perda V, se o seguinte for válido:βV

SZm  Eu{1 1,...,m},  sup|V(fs,z)-V(fS|Eu,z)|  β

mββmβm1 1m

Estabilidade da hipótese

Eu{1 1,...,m},  E[ |V(fs,z)-V(fS|Eu,z)| ] β

eu1 1

A vantagem dessas formas de estabilidade é que elas fornecem limites para o viés e a variação de algoritmos estáveis. Em particular, Bousquet provou esses limites para a estabilidade de Uniformes e Hipóteses em 2002. Desde então, muito trabalho foi feito para tentar relaxar as condições de estabilidade e generalizar os limites, por exemplo, em 2011, Kale, Kumar, Vassilvitskii argumentam que estabilidade quadrada significa fornece melhor variação limites de redução quantitativa de variação.

Alguns exemplos de algoritmos estáveis

Os algoritmos a seguir demonstraram ser estáveis ​​e têm limites de generalização comprovados:

  • Regressão mínima quadrada regularizada (com prévia apropriada)
  • Classificador KNN com função de perda 0-1
  • SVM com um kernel limitado e grande constante de regularização
  • SVM com margem suave
  • Algoritmo de entropia relativa mínima para classificação
  • Uma versão dos regularizadores de sacos

Uma simulação experimental

Repetindo o experimento do segmento anterior ( veja aqui ), agora apresentamos uma certa proporção de outliers no conjunto de dados. Em particular:

  • [-.5,.5]
  • [-20,20]

3

insira a descrição da imagem aqui

A realização da simulação como anteriormente e a plotagem da média MSE resultante e da variação da MSE resultam em resultados muito semelhantes ao Experimento 2 do artigo de Bengio & Grandvalet 2004 .

Lado Esquerdo : sem discrepâncias. Lado Direito : 3% de outliers.

insira a descrição da imagem aqui

insira a descrição da imagem aqui

(veja o artigo vinculado para explicação da última figura)

Explicações

Citando a resposta de Yves Grandvalet no outro tópico:

Intuitivamente, [na situação de algoritmos instáveis], o CV deixado de fora pode ser cego às instabilidades existentes, mas pode não ser desencadeado pela alteração de um único ponto nos dados de treinamento, o que o torna altamente variável para a realização do conjunto de treinamento.

Na prática, é bastante difícil simular um aumento na variação devido ao LOOCV. Requer uma combinação específica de instabilidade, alguns discrepantes, mas não muitos, e um grande número de iterações. Talvez isso seja esperado, uma vez que a regressão linear demonstrou ser bastante estável. Um experimento interessante seria repetir isso para dados dimensionais mais altos e um algoritmo mais instável (por exemplo, árvore de decisão)

Xavier Bourret Sicotte
fonte
+1, mas espero que esse segmento possa ser encerrado como duplicado do vinculado (esperaria até que o período de recompensa terminasse e as discussões se subjugassem e veria qual resposta acabaria sendo aceita). Vou comentar mais tarde.
Ameba diz Reinstate Monica
Não estou realmente convencido de que a pergunta seja uma duplicata. Minha pergunta usa a variação da questão do LOO principalmente como uma maneira de enquadrar as perguntas principais, que tratam de tentar obter uma explicação acessível sobre o que significa "estabilidade" - veja as perguntas marcadas na parte superior e inferior do OP. Falando nisso, embora essa resposta seja útil (+1), não vejo que você tentou responder às perguntas de estabilidade ... você usa o termo algumas vezes, mas parece fazê-lo de uma maneira que assume que o leitor já sabe o que isso significa. Não tenho certeza se posso aceitar a resposta em sua forma atual.
21418 Jake Westfall
11
@JakeWestfall Quando escrevi que "espero" que este tópico possa eventualmente ser fechado como duplicado, eu quis dizer que espero que uma resposta aceita nesse tópico seja grande o suficiente para cobrir as coisas que você perguntou :) Dê uma olhada no artigo de Bengio & Grandvalet, Experimento 2. Eles mostram que, usando regressão linear e dados gaussianos, obtêm variação mínima para LOOCV (esse também é o seu resultado), mas se os dados contiverem uma fração de outliers, LOOCV terá uma variação maior que 10- dobre mais ou menos. Eu acho que isso sugere o que é a "estabilidade" relevante.
Ameba diz Reinstate Monica
3
Eu amo @XavierBourretSicotte. Obrigado por fazer um excelente trabalho nesta resposta.
21418 Jake Westfall
11
Sim, citando este artigo: pdfs.semanticscholar.org/bf83/… : "Um algoritmo estável tem a propriedade de que substituir um elemento em seu conjunto de aprendizado não altera muito seu resultado. Como conseqüência, o erro empírico, se considerado um variável aleatória, deve ter uma pequena variação algoritmos estáveis podem então ser bons candidatos para o seu erro empírica para estar perto de seu erro generalização..
Xavier Bourret Sicotte
2

Darei minha resposta no contexto do parágrafo que você citar:

Com K = N, o estimador de validação cruzada é aproximadamente imparcial para o erro de previsão verdadeiro (esperado), mas pode ter alta variação porque os N "conjuntos de treinamento" são muito semelhantes entre si.

O estimador CV do erro de previsão verdadeiro (esperado) é baseado em um exemplo de conjunto de treinamento; portanto, aqui, a expectativa é superior a amostras de conjuntos de treinamento, quando entendi isso corretamente.

Portanto, o que este parágrafo diz respeito à "alta variância" diz é que existe uma diferença "alta" entre o erro esperado e o erro estimado pelo CV (que é aqui, a média das dobras).

Isso faz sentido porque o modelo se encaixa em um conjunto de treinamento específico e porque todas as dobras de treinamento são muito semelhantes no processo de deixar um de fora. No entanto, embora as dobras de treinamento sejam muito semelhantes em uma rodada de CV, a estimativa provavelmente varia muito se trocarmos as amostras de treinamento por CV. No CV com dobras k, uma vez que "diversificamos" as dobras de treinamento, temos algum efeito médio e entre as dobras k, as estimativas variam menos.

Ou, em outras palavras, o estimador de CV de exclusão única é basicamente quase como um método de validação, caso você não gire dobras e baseie sua estimativa de erro em um conjunto de validação. Novamente, nos exemplos de treinamento, haverá uma alta variação em relação às estimativas da dobra em k, em que você calcula a média das dobras já treinando modelos um tanto diversos na rodada da dobra em k (em outras palavras, se você trocar conjuntos de treinamento, as estimativas de o erro via k-fold provavelmente não variará muito).

EDITAR:

Quando li algumas respostas aqui sobre validação cruzada e a Internet em geral, acho que parece haver alguma confusão a qual estimador estamos nos referindo. Eu acho que algumas pessoas se referem a um modelo com alta variância (com o ML falando para a perda ter um componente de variância dominante) vs alta variância do estimador CV de dobras k. E, outro conjunto de respostas refere-se à variação como a variação da amostra em relação às dobras quando alguém diz que "a dobra k tem alta variação". Então, sugiro ser específico, porque as respostas são diferentes nos dois casos.


fonte
Ao discutir a variação, suponho que estamos falando da variação do estimador CV no conjunto de treinamento D, conforme definido aqui: stats.stackexchange.com/questions/365224/… e aqui: stats.stackexchange.com/questions/325123/… . Yves Grandvalet e Bengio argumentam em seu artigo de 2004 que o CV estima o erro de previsão esperado. Você pode ver a resposta dele aqui: stats.stackexchange.com/a/358138/192854
Xavier Bourret Sicotte
Se você basear sua resposta em diferentes definições de variação, acho que seria útil adicionar as definições e fórmulas formais. Talvez eu deveria fazê-lo em minhas respostas, bem ..
Xavier Bourret Sicotte
Sim, preciso revisar um pouco a literatura e devo adicionar algumas fórmulas à resposta. A citação de Os elementos do aprendizado estatístico ainda é intuitiva para mim, que LOOCV tem uma alta variação se o modelo tiver uma alta variação, porque é uma média sobre as dobras. Se um modelo tem um viés alto, tanto o LOOCV quanto qualquer estimador de dobras em k devem ter baixa variação (independente do viés) porque as previsões não variam muito. Mas o ponto no parágrafo era prob. esse LOOCV em comparação com o k-fold na maioria dos casos #
A citação foi mostrado para ser incorreta - pelo menos como uma generalização - ver os múltiplos papéis cotados em minhas respostas
Xavier Bourret Sicotte
1

Já falamos sobre isso antes - você está ficando muito matemático sobre um cavalo morto. Veja o artigo clássico de Ron Kohavi (Stanford-Univ) sobre CV e o dilema de viés e variância aqui . Quando você terminar de ler isso, não desejará executar o LOOCV e provavelmente será atraído pelo CV 10 vezes e / ou pelo viés de bootstrap.

Você também precisa pensar em grandes conjuntos de dados, para os quais o LOOCV é muito caro em termos de computação. Atualmente, o LOOCV não é realmente uma opção nos fluxos de trabalho / pipelines da maioria dos grupos.

O que exatamente é essa condição de "estabilidade"? Aplica-se a modelos / algoritmos, conjuntos de dados ou ambos, até certo ponto?

k=nk=nk=n

O LREG como classificador funcionaria quando os dados são separáveis ​​linearmente, mas, em média, seu viés seria muito alto, pois muitos conjuntos de dados não são separáveis ​​linearmente.

Existe uma maneira intuitiva de pensar sobre essa estabilidade?

Não, na minha opinião - já que não há regra geral sobre estabilidade.

Quais são outros exemplos de modelos / algoritmos ou conjuntos de dados estáveis ​​e instáveis?

Isso é aberto e muito amplo, pois um número infinitamente grande de respostas pode ser planejado, o que não seria útil.

K

kk

kk

JoleT
fonte
Obrigado por seus comentários, mas isso não parece responder à pergunta.
Jake Westfall
Veja a resposta em anexo ao OP.
Jolet
3
Apenas pesquisaram o artigo, mas eles realmente parecem afirmar que 10x é o melhor em terreno extremamente instável. Eu não posso acreditar que tem 7k citações. Com isso dito, parece haver boas razões para acreditar que há muitos benefícios em mais de 10x. Darei uma leitura mais completa quando tiver uma chance.
Cliff AB