¿Cómo se escalan las diversas técnicas estadísticas (regresión, PCA, etc.) con el tamaño y la dimensión de la muestra?

10

¿Existe una tabla general conocida de técnicas estadísticas que explique cómo se escalan con el tamaño y la dimensión de la muestra? Por ejemplo, un amigo mío me dijo el otro día que el tiempo de cálculo de simplemente clasificar rápidamente datos unidimensionales de tamaño n es n * log (n).

Entonces, por ejemplo, si retrocedemos y contra X donde X es una variable d-dimensional, ¿va como O (n ^ 2 * d)? ¿Cómo se escala si quiero encontrar la solución a través de la solución exacta de Gauss-Markov versus mínimos cuadrados numéricos con el método de Newton? ¿O simplemente obtener la solución frente al uso de pruebas de significación?

Supongo que más quiero una buena fuente de respuestas (como un documento que resume la escala de varias técnicas estadísticas) que una buena respuesta aquí. Como, digamos, una lista que incluye la escala de regresión múltiple, regresión logística, PCA, regresión de riesgo proporcional de cox, agrupación de K-medias, etc.

bigdata statistics efficiency scalability Quemadores de puente
fuente
Esta es una buena pregunta. Muchos libros de estadísticas hablan de los aspectos teóricos de los datos de alta dimensión y no de los aspectos computacionales.
shadowtalker
En muchos casos, la literatura original discutirá la complejidad. Pero a menudo la complejidad teórica es inútil. QuickSort tiene el peor caso de O (n ^ 2), pero a menudo es el más rápido, más rápido que HeapSort, que tiene el peor de los casos O (n log n). Si investiga un poco, encontrará resultados de complejidad para muchos algoritmos, si se conocen. Ej PCA ser O (nd ^ 3), siendo k-medias O (nkid) etc.
ha dejado - Anony-Mousse

Respuestas:

6

La mayoría de los algoritmos estadísticos eficientes (y no triviales) son de naturaleza iterativa, por lo que el análisis del peor de los casos O()es irrelevante ya que el peor de los casos es "no puede converger".

Sin embargo, cuando tiene muchos datos, incluso los algoritmos lineales ( O(n)) pueden ser lentos y luego debe centrarse en la constante 'oculta' detrás de la notación. Por ejemplo, calcular la varianza de una sola variante se hace ingenuamente escaneando los datos dos veces (una vez para calcular una estimación de la media y luego una vez para estimar la varianza). Pero también se puede hacer de una sola vez .

Para los algoritmos iterativos, lo más importante es la tasa de convergencia y el número de parámetros en función de la dimensionalidad de los datos, un elemento que influye mucho en la convergencia. Muchos modelos / algoritmos crecen una cantidad de parámetros que es exponencial con el número de variables (por ejemplo, splines), mientras que otros crecen linealmente (por ejemplo, máquinas de vectores de soporte, bosques aleatorios, ...)

damienfrancois
fuente
No estoy seguro de estar de acuerdo con esto: al diseñar un algoritmo para un problema estadístico, se preocupa mucho la complejidad de cada paso iterativo (y generalmente se documenta en un manuscrito). Pero como usted señala, a menudo no es tan fácil de resumir, ya que dos algoritmos con la misma complejidad por iteración pueden funcionar de manera muy diferente debido a las iteraciones necesarias. Dicho esto, es muy raro que la cantidad de iteraciones requeridas crezca más rápido que O(log(n) ).
Cliff AB
5

Usted mencionó regresión y PCA en el título, y hay una respuesta definitiva para cada uno de ellos.

La complejidad asintótica de la regresión lineal se reduce a O (P ^ 2 * N) si N> P, donde P es el número de características y N es el número de observaciones. Más detalles en la complejidad computacional de la operación de regresión de mínimos cuadrados .

Vanilla PCA es O (P ^ 2 * N + P ^ 3), como en el algoritmo de PCA más rápido para datos de alta dimensión . Sin embargo, existen algoritmos rápidos para matrices muy grandes, explicadas en esa respuesta y ¿El mejor algoritmo de PCA para un gran número de características? .

Sin embargo, no creo que nadie haya compilado una sola crítica o referencia o libro sobre el tema. Puede que no sea un mal proyecto para mi tiempo libre ...

Shadowtalker
fuente
Gracias, eso es muy útil! Si hace una revisión de la literatura para varias técnicas de modelado predictivo, estoy seguro de que se hará mucha referencia. Sería muy útil para las personas que desean diferenciar entre qué algoritmos usar en casos grandes n o p grandes, o para valores medios de aquellos para cálculos más precisos. ¿Sabes cómo escalan algunas de las técnicas más oscuras? (Al igual que la regresión de riesgos proporcionales de Cox o el análisis factorial confirmatorio)
Bridgeburners
Lamentablemente no, pero si alguna vez hago esa revisión, intentaré ser exhaustivo. Difícilmente llamaría a la regresión de Cox "oscura", al menos en mi campo.
shadowtalker
5

Di una respuesta parcial muy limitada para el paquete de análisis factorial confirmatorio que desarrollé para Stata en este artículo de Stata Journal basado en el tiempo de las simulaciones reales. El análisis factorial confirmatorio se implementó como una técnica de estimación de máxima verosimilitud, y pude ver muy fácilmente cómo creció el tiempo de cálculo con cada dimensión (tamaño de la muestra n, número de variables p, número de factores k). Como depende en gran medida de cómo piensa Stata sobre los datos (optimizado para calcular en columnas / observaciones en lugar de filas), descubrí que el rendimiento esO(n^{0.68} (k+p)^{2.4})donde 2.4 es la asintótica de inversión matricial más rápida (y hay mucho de eso en la maximización iterativa del análisis factorial confirmatorio). No di una referencia para esto último, pero creo que lo obtuve de Wikipedia .

X'X108

StasK
fuente
2
El formato matemático no funciona en DataScience? De Verdad? Tal vez deberíamos pedir obtenerlo.
StasK
Buen punto sobre la precisión numérica.
shadowtalker