Regresión por la ley del poder

7

Esta es una publicación cruzada de Math SE .

Tengo algunos datos (tiempo de ejecución de un algoritmo) y creo que sigue una ley de potencia

yrmisol=kXuna

Quiero determinar y . Lo que he hecho hasta ahora es hacer una regresión lineal (mínimos cuadrados) a través de y determinar y partir de sus coeficientes.kunaIniciar sesión(X),Iniciar sesión(y)kuna

Mi problema es que, dado que el error "absoluto" se minimiza para los "datos de registro de registro", lo que se minimiza cuando observa los datos originales es el cociente

yyrmisol

Esto lleva a un gran error absoluto para valores grandes de . ¿Hay alguna forma de hacer una "regresión de la ley de potencia" que minimice el error "absoluto" real? ¿O al menos hace un mejor trabajo para minimizarlo?y


Ejemplo:

ingrese la descripción de la imagen aquí

La curva roja se ajusta a todo el conjunto de datos. La curva verde se ajusta solo a través de los últimos 21 puntos.

Aquí están los datos para la trama. La columna izquierda son los valores de ( eje ), la columna derecha son los valores de ( eje )norteXty

1.000000000000000000e+02,1.944999820000248248e-03
1.120000000000000000e+02,1.278203080000253058e-03
1.250000000000000000e+02,2.479853309999952970e-03
1.410000000000000000e+02,2.767649050000500332e-03
1.580000000000000000e+02,3.161272610000196315e-03
1.770000000000000000e+02,3.536506440000266715e-03
1.990000000000000000e+02,3.165302929999711402e-03
2.230000000000000000e+02,3.115432719999944224e-03
2.510000000000000000e+02,4.102446610000356694e-03
2.810000000000000000e+02,6.248937529999807478e-03
3.160000000000000000e+02,4.109296799998674206e-03
3.540000000000000000e+02,8.410178100001530418e-03
3.980000000000000000e+02,9.524117600000181830e-03
4.460000000000000000e+02,8.694799099998817837e-03
5.010000000000000000e+02,1.267794469999898935e-02
5.620000000000000000e+02,1.376997950000031709e-02
6.300000000000000000e+02,1.553864030000227069e-02
7.070000000000000000e+02,1.608576049999897034e-02
7.940000000000000000e+02,2.055535920000011244e-02
8.910000000000000000e+02,2.381920090000448978e-02
1.000000000000000000e+03,2.922614199999884477e-02
1.122000000000000000e+03,1.785056299999610019e-02
1.258000000000000000e+03,3.823622889999569313e-02
1.412000000000000000e+03,3.297452850000013452e-02
1.584000000000000000e+03,4.841355780000071440e-02
1.778000000000000000e+03,4.927822640000271981e-02
1.995000000000000000e+03,6.248602919999939054e-02
2.238000000000000000e+03,7.927740400003813193e-02
2.511000000000000000e+03,9.425949999996419137e-02
2.818000000000000000e+03,1.212073290000148518e-01
3.162000000000000000e+03,1.363937510000141629e-01
3.548000000000000000e+03,1.598689289999697394e-01
3.981000000000000000e+03,2.055201890000262210e-01
4.466000000000000000e+03,2.308686839999722906e-01
5.011000000000000000e+03,2.683506760000113900e-01
5.623000000000000000e+03,3.307920660000149837e-01
6.309000000000000000e+03,3.641307770000139499e-01
7.079000000000000000e+03,5.151283440000042901e-01
7.943000000000000000e+03,5.910637860000065302e-01
8.912000000000000000e+03,5.568920769999863296e-01
1.000000000000000000e+04,6.339683309999486482e-01
1.258900000000000000e+04,1.250584726999989016e+00
1.584800000000000000e+04,1.820368430999963039e+00
1.995200000000000000e+04,2.750779816999994409e+00
2.511800000000000000e+04,4.136365994000016144e+00
3.162200000000000000e+04,5.498797844000023360e+00
3.981000000000000000e+04,7.895301083999981984e+00
5.011800000000000000e+04,9.843239714999981516e+00
6.309500000000000000e+04,1.641506008199996813e+01
7.943200000000000000e+04,2.786652209900000798e+01
1.000000000000000000e+05,3.607965075100003105e+01
1.258920000000000000e+05,5.501840400599996883e+01
1.584890000000000000e+05,8.544515980200003469e+01
1.995260000000000000e+05,1.273598972439999670e+02
2.511880000000000000e+05,1.870695913819999987e+02
3.162270000000000000e+05,3.076423412130000088e+02
3.981070000000000000e+05,4.243025571930002116e+02
5.011870000000000000e+05,6.972544795499998145e+02
6.309570000000000000e+05,1.137165088436000133e+03
7.943280000000000000e+05,1.615926472178005497e+03
1.000000000000000000e+06,2.734825116088002687e+03
1.584893000000000000e+06,6.900561992643000849e+03

(Perdón por la desordenada notación científica)

0x539
fuente
2
Tenga en cuenta que el centro de ayuda dice: " Tenga en cuenta, sin embargo, que no se recomienda la publicación cruzada en los sitios de SE. Elija una mejor ubicación para publicar su pregunta. Más adelante, si resulta más adecuado en otro sitio, se puede migrar " .
Glen_b -Reinstale a Monica el
2
Es muy claro de su trama que una sola ley de potencia no se ajusta a estos datos. Puede encontrar algún valor en las otras preguntas sobre la ley de poder en el sitio. También puede valer la pena leer el artículo de Aaron Clauset, Cosma Rohilla Shalizi, MEJ Newman (2009), "Distribuciones de leyes de poder en datos empíricos", SIAM Review 51, 661-703 (ver la versión arXiv aquí arXiv: 0706.1062v2 ); y esta publicación de Shalizi.
Glen_b -Reinstate Monica
2
Alguna información relevante aquí
Glen_b -Reinstate Monica

Respuestas:

4

Si desea la misma varianza de error en cada observación en la escala no transformada, puede usar mínimos cuadrados no lineales.

(Esto a menudo no será adecuado; los errores en muchos órdenes de magnitud rara vez son constantes en tamaño).

Si seguimos adelante y lo usamos, nos adaptamos mucho más a los valores posteriores:

Gráfico de ajuste de mínimos cuadrados no lineales

Y si examinamos los residuos, podemos ver que mi advertencia anterior está completamente fundada:

Gráfico residual contra registro (ajustado) para el modelo anterior

Esto muestra que la variabilidad no es constante en la escala original (y que el ajuste de esta curva de potencia única tampoco encaja muy bien en el extremo superior, ya que hay una curvatura distinta en el tercer trimestre del rango de los valores de registro en la escala x: entre aproximadamente 0 y 5 en el eje x anterior). La variabilidad es más cercana a constante en la escala logarítmica (aunque es un poco más variable en términos relativos a valores bajos que a valores altos allí).

Lo que sería mejor hacer aquí depende de lo que intente lograr.

Glen_b -Reinstate a Monica
fuente
En este caso, un ajuste que es mejor para los más grandes. y-los valores pueden ser apropiados, ya que no importa tanto el tiempo de ejecución cuando es bajo ...
kjetil b halvorsen
1
@kjetilbhalvorsen Hay mejores formas de lograrlo, pero el hecho de que el modelo no se ajuste es una advertencia clara de que si el interés fuera a predecir incluso un poco fuera del rango de los datos, las predicciones serían demasiado bajas, tal vez dramáticamente. El ajuste a solo los últimos 21 puntos todavía no se ajusta a la curvatura dentro de esa parte de los datos.
Glen_b -Reinstale a Monica el
2

Un artículo de Lin y Tegmark resume muy bien las razones por las cuales las distribuciones de procesos lognormales y / o de Markov no se ajustan a los datos que muestran comportamientos críticos de la ley de potencia ... https://ai2-s2-pdfs.s3.amazonaws.com/5ba0/3a03d844f10d7b4861d3b116818afe2b75f2 .pdf . Como señalan, "los procesos de Markov ... fallan épicamente al predecir información mutua en descomposición exponencial ..." Su solución y recomendación es emplear redes neuronales de aprendizaje profundo, como los modelos de memoria a corto y largo plazo (LSTM).

Como soy de la vieja escuela y no estoy familiarizado ni me siento cómodo con las NN o las LSTM, daré un consejo al enfoque no lineal de @ glen_b. Sin embargo, prefiero soluciones alternativas más manejables y fácilmente accesibles, como la regresión cuantil basada en valores. Después de haber utilizado este enfoque en reclamaciones de seguros de colas pesadas, sé que puede proporcionar un ajuste mucho mejor a las colas que los métodos más tradicionales, incluidos los modelos multiplicativos de registro de registro. El desafío modesto en el uso de QR es encontrar el cuantil apropiado alrededor del cual basar los modelos. Por lo general, esto es mucho mayor que la mediana. Dicho esto, no quiero sobrevender este método ya que seguía habiendo una falta de ajuste significativa en los valores más extremos de la cola.

Hyndman, et al ( http://robjhyndman.com/papers/sig-alternate.pdf ), proponen un QR alternativo que ellos llaman aumentar la regresión cuantil aditiva . Su enfoque construye modelos en un rango completo o cuadrícula de cuantiles, produciendo estimaciones o pronósticos probabilísticos que pueden evaluarse con cualquiera de las distribuciones de valores extremos, por ejemplo, Cauchy, Levy-stable, lo que sea. Todavía tengo que emplear su método, pero parece prometedor.

Otro enfoque para el modelado de valores extremos se conoce como modelos POT o pico sobre umbral. Esto implica establecer un umbral o límite para una distribución empírica de valores y modelar solo los valores más grandes que caen por encima del límite en función de un GEV o una distribución generalizada de valores extremos. La ventaja de este enfoque es que cualquier posible valor extremo futuro puede calibrarse o ubicarse en función de los parámetros del modelo. Sin embargo, el método tiene la desventaja obvia de que uno no está usando el PDF completo.

Finalmente, en un artículo de 2013, JP Bouchaud propone el RFIM (modelo de generación aleatoria de campos) para modelar información compleja que muestra la criticidad y los comportamientos de cola pesada como el pastoreo, las tendencias, las avalanchas, etc. Bouchaud pertenece a una clase de polimatos que deberían incluir a personas como Mandelbrot, Shannon, Tukey, Turing, etc. Puedo afirmar que está muy intrigado por su discusión y, al mismo tiempo, estar intimidado por los rigores involucrados en la implementación de sus sugerencias. . https://www.researchgate.net/profile/Jean-Philippe_Bouchaud/publication/230788728_Crises_and_Collective_Socio-Economic_Phenomena_Simple_Models_and_Challenges/links/5682d40008ae051f9aeepf.adjetivo_inteligente.png

Mike Hunter
fuente