Velocidade, despesas computacionais de PCA, LASSO, rede elástica

18

Estou tentando comparar a complexidade computacional / velocidade de estimativa de três grupos de métodos para regressão linear, conforme distinguido em Hastie et al. "Elementos da aprendizagem estatística" (2ª ed.), Capítulo 3:

  1. Seleção de subconjunto
  2. Métodos de encolhimento
  3. Métodos usando direções de entrada derivadas (PCR, PLS)

A comparação pode ser muito difícil, apenas para se ter uma ideia. Entendo que as respostas podem depender da dimensão do problema e de como isso se ajusta à arquitetura do computador; portanto, para um exemplo concreto, pode-se considerar um tamanho de amostra de 500 e 50 candidatos a regressores. Estou interessado principalmente na motivação por trás da complexidade computacional / velocidade de estimativa, mas não em quanto tempo levaria em um determinado processador para o exemplo dado.

Richard Hardy
fonte
Ao usar PCR ou PLS, o número de componentes é um parâmetro de ajuste (semelhante a na regressão de crista). Portanto, esses métodos também precisarão de validação cruzada para encontrar o número ideal de componentes. O LASSO também possui um parâmetro de regularização, mas a rede elástica possui dois (rede elástica = cume + LASSO), portanto, a validação cruzada é mais cara. Além disso, o LASSO provavelmente é mais lento do que todos os outros modelos, porque não possui uma solução de forma fechada. λ
Ameba diz Reinstate Monica
Obrigado! O seu comentário seria uma boa resposta se você incluísse mais dois detalhes: (1) quão caro é uma iteração de PCR e PLS em comparação com uma execução OLS da regressão regular; (2) quantificar a velocidade do LASSO com mais precisão para torná-lo comparável à velocidade da regressão regular (é polinomial, exponencial ou linearmente mais caro e por quê).
Richard Hardy
Infelizmente, não tenho uma resposta pronta para isso, especialmente para (2). Por isso deixei apenas um comentário. +1, a propósito, e parabéns com 5k rep!
Ameba diz Reinstate Monica
1
@amoeba, obrigado! Eu não esperava atingir 5k quando comecei (muito lentamente) no ano passado. Mas é muito emocionante e gratificante ser um membro ativo aqui na Cross Validated!
Richard Hardy
@amoeba, acho que entendi a complexidade do LASSO se o algoritmo LARS for usado; Eu atualizei minha postagem de acordo. Mas eu não ler o jornal LARS com cuidado, por isso não estou completamente certo de que é correto ...
Richard Hardy

Respostas:

5

Grupo 1 :
A complexidade / velocidade do grupo 1. não parece muito difícil de descobrir se algoritmos de força bruta são usados ​​(embora possa haver alternativas mais eficientes, como o algoritmo "trancos e barrancos"). Por exemplo, a seleção completa do subconjunto exigirá que regressões de sejam ajustadas, dado um conjunto de recursos candidatos. Um ajuste OLS de uma regressão linear tem a complexidade de (conforme esta postagem ) em que é o tamanho da amostra. Portanto, a complexidade total da seleção de subconjunto completo de força bruta deve ser .2KKO(K2n)nO(2KK2n)

Grupo 2 :
A complexidade / velocidade do grupo 2. é discutida nas seções 3.8 e 3.9 do livro. Por exemplo, a regressão de crista com uma determinada penalidade tem a mesma complexidade computacional que uma regressão regular. Como λ precisa ser encontrado usando a validação cruzada, a carga computacional aumenta linearmente no número de divisões de dados usadas na validação cruzada (por exemplo, ). Se a grade tiver pontos , a complexidade total da regressão de crista com o ajuste do parâmetro será . Fala-se bastante sobre o LASSOλλSλeuλO(euSK2n)
no livro, mas não consegui encontrar exatamente o que preciso. No entanto, encontrei na p. 443 de Efron et al. "Regressão menos angular" (2004) que a complexidade do LASSO para um dado é a mesma que a complexidade de um ajuste OLS de regressão linear se o método LARS for usado. Então a complexidade total do LASSO com o ajuste do parâmetro será . (Não li esse documento com atenção, por favor, corrija-me se eu entendi errado.) Rede elástica combina cume e LASSO; os dois têm a mesma complexidade computacional; portanto, a complexidade da rede elástica deve ser que é o tamanho da grade do parâmetro de ajusteλλO(euSK2n)
O(UMAeuSK2n)UMAα que equilibra os pesos da crista versus LASSO.

Grupo 3 :
Eu ainda perca qualquer nota sobre a complexidade / velocidade para o grupo 3. que consiste de componentes principais de regressão (PCR) e mínimos quadrados parciais (PLS).

Richard Hardy
fonte
2

É apenas para uma parte da pergunta 2 do grupo 3 acima (ou seja, PLS), mas pode ser informativo: Srinivasan et al (2010, relatório técnico; consulte https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) fez algumas medições no PLS usando o algoritmo NIPALS - declarando que a complexidade do tempo (e espaço) desse algoritmo é O (dN) - para extração e inclusão em modelos diferentes para a) detecção de seres humanos em imagens e b ) reconhecimento facial. As medições foram feitas usando sua própria implementação baseada em GPU.

jf1
fonte