Estimasi rata-rata yang kuat dengan efisiensi pembaruan O (1)

Saya mencari estimasi kuat dari mean yang memiliki properti spesifik. Saya memiliki serangkaian elemen yang ingin saya hitung statistik ini. Kemudian, saya menambahkan elemen baru satu per satu, dan untuk setiap elemen tambahan saya ingin menghitung ulang statistik (juga dikenal sebagai algoritma online). Saya ingin kalkulasi pembaruan ini menjadi cepat, lebih disukai O (1), yaitu tidak tergantung pada ukuran daftar.

Berarti biasa memiliki properti ini yang dapat diperbarui secara efisien, tetapi tidak kuat untuk outlier. Penduga kuat rata-rata rata-rata, seperti rata-rata antar kuartil dan rata-rata yang dipangkas tidak dapat diperbarui secara efisien (karena mereka memerlukan pemeliharaan daftar yang diurutkan).

Saya sangat menghargai saran untuk statistik yang kuat yang dapat dihitung / diperbarui secara efisien.

Solusi ini mengimplementasikan saran yang dibuat oleh @Innuo dalam komentar untuk pertanyaan:

Anda dapat mempertahankan subset acak yang seragam dengan ukuran 100 atau 1000 dari semua data yang terlihat sejauh ini. Set ini dan "pagar" yang terkait dapat diperbarui dalam waktu .$O(1)$

Setelah kami tahu cara mempertahankan subset ini, kami dapat memilih metode apa pun yang kami suka untuk memperkirakan rata-rata populasi dari sampel tersebut. Ini adalah metode universal, tidak membuat asumsi apa pun, yang akan bekerja dengan aliran input apa pun dalam keakuratan yang dapat diprediksi menggunakan rumus sampling statistik standar. (Akurasi berbanding terbalik dengan akar kuadrat dari ukuran sampel.)

Algoritma ini menerima sebagai input aliran data t = 1 , 2 , ... , ukuran sampel m , dan menampilkan aliran sampel s ( t ) yang masing-masing mewakili populasi X ( t ) = ( x ( 1 ) , x ( 2 ) , ... , x ( t ) ) . Khususnya, untuk 1 ≤ i $x(t),$ $t=1, 2, \ldots,$$m$$s(t)$$X(t) = (x(1),x(2), \ldots, x(t))$ , s ( i ) adalah sampel acak sederhana berukuran m dari X ( t ) (tanpa penggantian).$1\le i \le t$$s(i)$$m$$X(t)$

Agar hal ini terjadi, cukup bahwa setiap subset elemen dari { 1 , 2 , ... , t } memiliki peluang yang sama untuk menjadi indeks x dalam s ( t ) . Ini menyiratkan kemungkinan bahwa x ( i ) , 1 ≤ i < t , dalam s ( t ) sama dengan m / t asalkan t ≥ m .$m$$\{1,2,\ldots,t\}$$x$$s(t)$$x(i),$ $1\le i\lt t,$$s(t)$$m/t$$t \ge m$

Pada awalnya kami hanya mengumpulkan aliran sampai elemen telah disimpan. Pada saat itu hanya ada satu sampel yang mungkin, sehingga kondisi probabilitas sepele terpenuhi.$m$

Algoritma mengambil alih ketika . Anggaplah secara induktif bahwa s ( t ) adalah sampel acak sederhana X ( t ) untuk t > m . Sementara set s ( t + 1 ) = s ( t ) . Misalkan U ( t + 1 ) menjadi variabel acak seragam (tidak tergantung dari variabel sebelumnya yang digunakan untuk membangun s ( t ) ). Jika$t=m+1$$s(t)$$X(t)$$t\gt m$$s(t+1) = s(t)$$U(t+1)$$s(t)$ kemudian ganti elemen s yang dipilih secara acakdengan x ( t + 1 ) . $U(t+1) \le m/(t+1)$$s$$x(t+1)$ Itu seluruh prosedur!

Jelas memiliki probabilitas m / ( t + 1 ) berada di s ( t + 1 ) . Selain itu, dengan hipotesis induksi, x ( i ) memiliki probabilitas m / t berada di s ( t ) ketika saya ≤ t . Dengan probabilitas m / ( t + 1 ) × 1 /$x(t+1)$$m/(t+1)$$s(t+1)$$x(i)$$m/t$$s(t)$$i\le t$$m/(t+1) \times 1/m$= itu akan dihapus dari s ( t + 1 ) , di mana probabilitasnya tetap sama$1/(t+1)$$s(t+1)$

persis seperti yang dibutuhkan. Dengan induksi, maka, semua probabilitas inklusi dalam s ( t ) benar dan jelas tidak ada korelasi khusus di antara inklusi tersebut. Itu membuktikan algoritma itu benar.$x(i)$$s(t)$

Efisiensi algoritma adalah karena pada setiap tahap paling banyak dua angka acak dihitung dan paling banyak satu elemen dari array nilai m diganti. Persyaratan penyimpanan adalah O ( m ) .$O(1)$$m$$O(m)$

Struktur data untuk algoritma ini terdiri dari sampel bersama-sama dengan indeks t dari populasi $s$$t$ yang sampel. Awalnya kami mengambil s = X ( m ) dan melanjutkan dengan algoritma untuk t = m + 1 , m + 2 , … . Berikut ini adalahimplementasi untuk memperbarui ( s , t ) dengan nilai x untuk menghasilkan ( s , t $X(t)$$s = X(m)$$t=m+1, m+2, \ldots.$R$(s,t)$$x$ . (Argumenmemainkan peran t danadalah m . Indeks t akan dipertahankan oleh pemanggil.)$(s,t+1)$n$t$sample.size$m$$t$

update <- function(s, x, n, sample.size) {
  if (length(s) < sample.size) {
    s <- c(s, x)
  } else if (runif(1) <= sample.size / n) {
    i <- sample.int(length(s), 1)
    s[i] <- x
  }
  return (s)
}

Untuk menggambarkan dan menguji ini, saya akan menggunakan penduga rata-rata (tidak-kuat) rata-rata dan membandingkan rata-rata seperti yang diperkirakan dari dengan rata-rata aktual X ( t ) (kumpulan data kumulatif yang terlihat pada setiap langkah ). Saya memilih aliran input yang agak sulit yang berubah cukup lancar tetapi secara berkala mengalami lompatan dramatis. Ukuran sampel m = 50 cukup kecil, memungkinkan kami untuk melihat fluktuasi sampel dalam plot ini.$s(t)$$X(t)$$m=50$

n <- 10^3
x <- sapply(1:(7*n), function(t) cos(pi*t/n) + 2*floor((1+t)/n))
n.sample <- 50
s <- x[1:(n.sample-1)]
online <- sapply(n.sample:length(x), function(i) {
  s <<- update(s, x[i], i, n.sample)
  summary(s)})
actual <- sapply(n.sample:length(x), function(i) summary(x[1:i]))

Pada titik ini onlineadalah urutan estimasi rata-rata yang dihasilkan dengan mempertahankan sampel yang berjalan ini dari nilai sedangkan urutan estimasi rata-rata dihasilkan dari semua data yang tersedia pada setiap saat. Plot menunjukkan data (berwarna abu-abu), (hitam), dan dua aplikasi independen dari prosedur pengambilan sampel ini (berwarna). Perjanjian tersebut dalam kesalahan pengambilan sampel yang diharapkan:$50$actualactual

plot(x, pch=".", col="Gray")
lines(1:dim(actual)[2], actual["Mean", ])
lines(1:dim(online)[2], online["Mean", ], col="Red")

Untuk penaksir yang kuat dari rata-rata, silakan cari situs kami untuk pencilan dan istilah terkait. Di antara kemungkinan yang layak dipertimbangkan adalah sarana Winsorized dan penaksir-M.

Anda mungkin berpikir untuk menghubungkan masalah Anda dengan bagan kontrol rekursif. Diagram kontrol seperti itu akan mengevaluasi apakah pengamatan baru terkendali. Jika ya, pengamatan ini termasuk dalam estimasi baru dari mean dan varians (diperlukan untuk menentukan batas kontrol).

Beberapa latar belakang pada diagram kontrol yang kuat, rekursif, dan univariat dapat ditemukan di sini . Salah satu teks klasik tentang kendali mutu dan diagram kendali tampaknya tersedia online di sini .

$\mu_{t-1}$$\sigma^2_{t-1}$$t$$x_t$$\mu_{t-1}$$\sigma^2_{t-1})$, tetapi ini dapat mengalami masalah jika data tidak sesuai dengan asumsi distribusi tertentu. Jika Anda ingin pergi ke jalan ini, maka seandainya Anda telah menentukan apakah suatu titik baru bukan merupakan outlier, dan ingin memasukkannya dalam perkiraan rata-rata Anda tanpa ada tingkat khusus untuk melupakan. Maka Anda tidak bisa melakukan lebih baik daripada:

$\mu_t = \frac{t-1}{t}\mu_{t-1}+\frac{1}{t}x_t$

Demikian pula, Anda perlu memperbarui varians secara rekursif:

$\sigma^2_t = \frac{t-1}{t}\sigma^2_{t-1}+\frac{1}{t-1}(x_t-\mu_t)^2$

$\mu$$\mu$$\sigma^2$

Mengenai bagan seperti EWMA, yang melupakan pengamatan lama dan lebih memberi bobot pada yang baru, jika Anda berpikir bahwa data Anda diam (artinya parameter distribusi penghasil tidak berubah) maka tidak perlu melupakan pengamatan lama secara eksponensial. Anda dapat mengatur faktor yang lupa sesuai. Namun, jika Anda berpikir bahwa ini adalah non-stasioneritas, Anda harus memilih nilai yang baik untuk faktor yang melupakan (lihat lagi buku teks tentang cara untuk melakukan ini).

Saya juga harus menyebutkan bahwa sebelum Anda mulai memantau dan menambahkan pengamatan baru secara online, Anda perlu memperoleh perkiraan $\mu_0$$\sigma^2_0$

Saya pikir pendekatan di sepanjang garis ini akan mengarah pada pembaruan tercepat untuk masalah Anda.