Como várias técnicas estatísticas (regressão, PCA, etc.) são escalonadas com o tamanho e a dimensão da amostra?

10

Existe uma tabela geral conhecida de técnicas estatísticas que explique como elas são dimensionadas com tamanho e dimensão da amostra? Por exemplo, um amigo meu me disse outro dia que o tempo de computação da simples classificação rápida de dados unidimensionais do tamanho n é n * log (n).

Então, por exemplo, se regredirmos y contra X, onde X é uma variável d-dimensional, ela será igual a O (n ^ 2 * d)? Como é a escala se eu quiser encontrar a solução através da solução exata de Gauss-Markov versus mínimos quadrados numéricos com o método Newton? Ou simplesmente obter a solução vs usar testes de significância?

Acho que quero mais uma boa fonte de respostas (como um artigo que resuma o dimensionamento de várias técnicas estatísticas) do que uma boa resposta aqui. Como, digamos, uma lista que inclui o dimensionamento de regressão múltipla, regressão logística, PCA, regressão proporcional ao risco cox, agrupamento K-significa, etc.

Bridgeburners
fonte
Essa é uma boa pergunta. Muitos livros de estatística falam sobre os aspectos teóricos dos dados de alta dimensão e não os aspectos computacionais.
shadowtalker
Em muitos casos, a literatura original discutirá a complexidade. Mas muitas vezes a complexidade teórica é inútil. O QuickSort tem o pior caso de O (n ^ 2), mas geralmente é o mais rápido - mais rápido que o HeapSort, que tem o pior caso O (n log n). Se você pesquisar um pouco, descobrirá resultados de complexidade para muitos algoritmos - se conhecidos. Por exemplo, PCA ser O (ND ^ 3), k-ó meios sendo (NKID) etc
parou - anony-Mousse de

Respostas:

6

A maioria dos algoritmos estatísticos eficientes (e não triviais) é de natureza iterativa, de modo que a análise do pior caso O()é irrelevante, pois o pior caso é "falha na convergência".

No entanto, quando você tem muitos dados, mesmo os algoritmos lineares ( O(n)) podem ser lentos e você precisa se concentrar na constante 'oculta' por trás da notação. Por exemplo, o cálculo da variação de uma única variável é feito ingenuamente, varrendo os dados duas vezes (uma vez para calcular uma estimativa da média e depois uma vez para estimar a variação). Mas também pode ser feito de uma só vez .

Para algoritmos iterativos, o mais importante é a taxa de convergência e o número de parâmetros em função da dimensionalidade dos dados, um elemento que influencia bastante a convergência. Muitos modelos / algoritmos crescem vários parâmetros que são exponenciais com o número de variáveis ​​(por exemplo, splines), enquanto outros crescem linearmente (por exemplo, suportam máquinas de vetores, florestas aleatórias, ...)

damienfrancois
fonte
Não tenho certeza se concordo com isso: ao projetar um algoritmo para um problema estatístico, muita preocupação entra na complexidade de cada etapa iterativa (e geralmente é documentada em um manuscrito). Mas, como você aponta, muitas vezes não é tão fácil resumir, pois dois algoritmos com a mesma complexidade por iteração podem ter um desempenho muito diferente devido às iterações necessárias. Dito isto, é muito raro que o número de iterações necessárias cresça mais rápido que O(log(n) ).
Cliff AB
5

Você mencionou regressão e PCA no título, e há uma resposta definitiva para cada uma delas.

A complexidade assintótica da regressão linear reduz-se a O (P ^ 2 * N) se N> P, onde P é o número de características e N é o número de observações. Mais detalhes em Complexidade computacional da operação de regressão pelo quadrado mínimo .

O PCA de baunilha é O (P ^ 2 * N + P ^ 3), como no algoritmo PCA mais rápido para dados de alta dimensão . No entanto, existem algoritmos rápidos para matrizes muito grandes, explicados nessa resposta e no melhor algoritmo PCA para um grande número de recursos? .

No entanto, acho que ninguém compilou uma única resenha, referência ou livro sobre o assunto. Pode não ser um projeto ruim para o meu tempo livre ...

shadowtalker
fonte
Obrigado, isso é muito útil! Se você fizer uma revisão de literatura para várias técnicas de modelagem preditiva, tenho certeza de que seria muito referenciado. Seria muito útil para pessoas que desejam diferenciar entre quais algoritmos usar em casos grandes ou grandes ou para valores médios daqueles para cálculos mais precisos. Você sabe como algumas das técnicas mais obscuras escalam? (Como Cox proporcional regressão perigo ou análise fatorial confirmatória)
Bridgeburners
Infelizmente não, mas se eu fizer essa revisão, tentarei ser abrangente. Eu dificilmente chamaria a regressão de Cox de "obscura", pelo menos na minha área.
shadowtalker
5

Dei uma resposta parcial muito limitada ao pacote de análise fatorial confirmatória que desenvolvi para o Stata neste artigo do Stata Journal, com base no tempo das simulações reais. A análise fatorial confirmatória foi implementada como uma técnica de estimativa de máxima verossimilhança, e pude ver com muita facilidade como o tempo de computação cresceu com cada dimensão (tamanho da amostra n, número de variáveis p, número de fatores k). Como é fortemente dependente de como o Stata pensa sobre os dados (otimizado para calcular através de colunas / observações em vez de linhas), achei o desempenhoO(n^{0.68} (k+p)^{2.4})onde 2.4 é o mais rápido de inversão de matriz assintótica (e há muito disso na maximização iterativa da análise fatorial confirmatória). Não dei uma referência para o último, mas acho que peguei isso na Wikipedia .

X'X108

StasK
fonte
2
A formatação matemática não funciona no DataScience? Realmente? Pode ser que devemos pedir para obtê-lo.
StasK 14/08/14
Bom ponto sobre precisão numérica.
shadowtalker