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:
- Seleção de subconjunto
- Métodos de encolhimento
- 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.
machine-learning
estimation
feature-selection
algorithms
time-complexity
Richard Hardy
fonte
fonte
Respostas:
Grupo 1 :2K K O ( K2n ) n O ( 2KK2n )
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 .
Grupo 2 :λ λ S λ eu λ O (LSK2n ) λ λ O (LSK2n )
O (ALSK2n ) UMA α que equilibra os pesos da crista versus LASSO.
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
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
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).
fonte
É 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.
fonte