Existe-t-il un tableau général connu des techniques statistiques expliquant comment elles évoluent avec la taille et la dimension de l'échantillon? Par exemple, un de mes amis m'a dit l'autre jour que le temps de calcul d'un simple tri rapide des données unidimensionnelles de taille n correspond à n * log (n).
Ainsi, par exemple, si nous régressons y contre X où X est une variable de dimension d, cela va-t-il comme O (n ^ 2 * d)? Comment évolue-t-il si je veux trouver la solution via une solution de Gauss-Markov exacte par rapport aux moindres carrés numériques avec la méthode de Newton? Ou simplement obtenir la solution ou utiliser des tests de signification?
Je suppose que je veux plus une bonne source de réponses (comme un article qui résume l'échelle de diverses techniques statistiques) qu'une bonne réponse ici. Comme, par exemple, une liste qui inclut la mise à l'échelle de la régression multiple, de la régression logistique, de l'ACP, de la régression des risques proportionnels cox, du regroupement des moyennes K, etc.
la source
Réponses:
La plupart des algorithmes statistiques efficaces (et non triviaux) sont de nature itérative, de sorte que l'analyse du pire des cas
O()n'est pas pertinente car le pire des cas est «elle ne parvient pas à converger».Néanmoins, lorsque vous avez beaucoup de données, même les algorithmes linéaires (
O(n)) peuvent être lents et vous devez alors vous concentrer sur la constante «cachée» derrière la notation. Par exemple, le calcul de la variance d'une seule variable se fait naïvement en balayant les données deux fois (une fois pour calculer une estimation de la moyenne, puis une fois pour estimer la variance). Mais cela peut aussi se faire en un seul passage .Pour les algorithmes itératifs, ce qui est plus important est le taux de convergence et le nombre de paramètres en fonction de la dimensionnalité des données, un élément qui influence grandement la convergence. De nombreux modèles / algorithmes développent un certain nombre de paramètres qui est exponentiel avec le nombre de variables (par exemple les splines) tandis que d'autres se développent de manière linéaire (par exemple, prennent en charge les machines à vecteurs, les forêts aléatoires, ...)
la source
O(log(n) ).Vous avez mentionné la régression et l'ACP dans le titre, et il y a une réponse définitive pour chacun d'eux.
La complexité asymptotique de la régression linéaire se réduit à O (P ^ 2 * N) si N> P, où P est le nombre de caractéristiques et N est le nombre d'observations. Plus de détails sur la complexité de calcul de l'opération de régression des moindres carrés .
Vanilla PCA est O (P ^ 2 * N + P ^ 3), comme dans l' algorithme PCA le plus rapide pour les données de grande dimension . Cependant, des algorithmes rapides existent pour les très grandes matrices, expliqués dans cette réponse et Meilleur algorithme PCA pour un grand nombre de fonctionnalités? .
Cependant, je ne pense pas que quiconque ait compilé une seule critique éclairée ou référence ou livre sur le sujet. Ça pourrait ne pas être un mauvais projet pour mon temps libre ...
la source
J'ai donné une réponse partielle très limitée pour le package d'analyse de facteur de confirmation que j'ai développé pour Stata dans cet article du Stata Journal basé sur le timing des simulations réelles. L'analyse factorielle confirmatoire a été mise en œuvre comme technique d'estimation du maximum de vraisemblance, et j'ai pu voir très facilement comment le temps de calcul a augmenté avec chaque dimension (taille de l'échantillon
n, nombre de variablesp, nombre de facteursk). Comme cela dépend fortement de la façon dont Stata pense les données (optimisées pour calculer sur plusieurs colonnes / observations plutôt que sur des lignes), j'ai trouvé que les performances étaientO(n^{0.68} (k+p)^{2.4})où 2,4 est l'asymptotique d'inversion de matrice la plus rapide (et il y en a beaucoup dans la maximisation itérative de l'analyse factorielle confirmatoire). Je n'ai pas donné de référence pour ce dernier, mais je pense que je l'ai obtenu de Wikipedia .X'Xla source