Какова вычислительная сложность функции arima() в R?

Question

Если у моего временного ряда есть n членов, и я хочу поместить ARIMA(1,0,1) модель, какая будет сложность в большом O обозначение?

В следующем примере я должен знать, сложность второй строки кода:

series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=1000) 
result <- arima(series, order=c(1,0,1)) 

Спасибо.

Answer 1

Это O(n) сложность. История для этого? Смотри ниже.

Как я уже сказал в комментарии, мы можем измерить его по модели регрессии. В качестве демонстрации игрушек рассмотрите следующую процедуру сбора и регрессии данных.

Сначала определим функцию для измерения времени подгонки модели модели ARMA(1,1) (или ARIMA(1,0,1)). (Обратите внимание, что я использую основную system.time() здесь. Вы можете рассмотреть возможность использования microbenchmark() из пакета microbenchmark. Но в дальнейшем я буду использовать достаточно большой n, чтобы уменьшить чувствительность измерения времени.)

t_arma <- function(N) { 
    series <- arima.sim(list(order=c(1,0,1), ar=.9, ma=-.5), n=N) 
    as.numeric((system.time(arima(series, order=c(1,0,1)))))[3] 
    } 

Нам нужно собрать, скажем 100, данные. Мы стараемся, чтобы 100 все больше и больше стали n, и измерьте время подгонки модели t.

k <- 100; t <- numeric(k) 
n <- seq(20000, by = 1000, length = k) ## start from n = 20000 (big enough) 
for (i in 1:k) t[i] <- t_arma(n[i]) 

Теперь, если мы предполагаем, что сложность: a * (n^b) или O(n^b), мы можем оценить a, b по регрессионной модели:

log(t) ~ log(a) + b * log(n) 

и мы особенно заинтересованы в оценке отстойный: b ,

Так давайте назовем lm()

fit <- lm(log(t) ~ log(n)) 

#Coefficients: 
#(Intercept)  log(n) 
# -9.2185  0.8646 

Мы также можем набросать график рассеяния log(n) В.С. log(t), а также оборудованная линия:

plot(log(n), log(t), main = "scatter plot") 
lines(log(n), fit$fitted, col = 2, lwd = 2) 

Есть некоторые выпадающие в начале, следовательно, наклон ниже, чем должно быть. Теперь мы рассмотрим удаление выбросов и обновление модели для надежности.

Выбросы отличаются большими остатками. Давайте посмотрим:

plot(fit$resi, main = "residuals") 

Мы можем отметить и удалить эти выбросы. Похоже, 0.5 - достаточно хороший порог, чтобы отфильтровать эти выбросы.

exclude <- fit$resi > 0.5 
n <- n[!exclude] 
t <- t[!exclude] 

Теперь мы переоборудовать линейную модель и сделать сюжет:

robust_fit <- lm(log(t) ~ log(n)) 

#Coefficients: 
#(Intercept)  log(n) 
# -11.197  1.039 

plot(log(n), log(t), main = "scatter plot (outliers removed)") 
lines(log(n), robust_fit$fitted, col = 2, lwd = 2) 

Ого, здорово, мы золотые! Оценка склона равна 1. Таким образом, сложность O(n) оправдана!