Надежная средняя оценка с эффективностью обновления O (1)

Я ищу надежную оценку среднего значения, которое обладает определенным свойством. У меня есть набор элементов, для которых я хочу рассчитать эту статистику. Затем я добавляю новые элементы по одному, и для каждого дополнительного элемента я хотел бы пересчитать статистику (также известный как онлайн-алгоритм). Я хотел бы, чтобы этот расчет обновления был быстрым, предпочтительно O (1), то есть не зависит от размера списка.

Обычное среднее значение обладает этим свойством, что оно может эффективно обновляться, но не является устойчивым к выбросам. Типичные надежные оценки среднего, такие как среднее квартиль и усеченное среднее, не могут быть эффективно обновлены (так как они требуют ведения отсортированного списка).

Буду признателен за любые предложения для надежной статистики, которая может быть эффективно рассчитана / обновлена.

Это решение реализует предложение, сделанное @Innuo в комментарии к вопросу:

Вы можете поддерживать однородную выборку случайного подмножества размером 100 или 1000 из всех данных, просмотренных до сих пор. Этот набор и связанные с ним «ограждения» могут быть обновлены за раз.$O(1)$

Как только мы узнаем, как поддерживать это подмножество, мы можем выбрать любой метод, который нам нравится, чтобы оценить среднее значение популяции из такой выборки. Это универсальный метод, не делающий никаких предположений, который будет работать с любым входным потоком с точностью, которая может быть предсказана с использованием стандартных формул статистической выборки. (Точность обратно пропорциональна корню квадратному из размера выборки.)

Этот алгоритм принимает в качестве входных данных поток данных размер выборки и выводит поток выборок каждая из которых представляет совокупность . В частности, для , представляет собой простой случайной выборки размера от (без замены).t = 1 , 2 , … , m s ( t ) X ( t ) = ( x ( 1 ) , x ( 2 ) , … , x ( t ) ) 1 ≤ i ≤ t s ( i ) м х ( т $x(t),$ $t=1, 2, \ldots,$$m$$s(t)$$X(t) = (x(1),x(2), \ldots, x(t))$$1\le i \le t$$s(i)$$m$$X(t)$

Для этого достаточно, чтобы каждое подмножество -элемента имело равные шансы быть индексами в . Это означает, что вероятность того, что находится в равна при условии .{ 1 , 2 , … , t } x s ( t ) x ( i ) , 1 ≤ i < t , s ( t ) m / t t ≥ $m$$\{1,2,\ldots,t\}$$x$$s(t)$$x(i),$ $1\le i\lt t,$$s(t)$$m/t$$t \ge m$

В начале мы просто собираем поток, пока не будет сохранено элементов. На данный момент существует только одна возможная выборка, поэтому условие вероятности тривиально выполняется.$m$

Алгоритм вступает во владение, когда . Индуктивно предположим, что - простая случайная выборка для . Предварительно установите . Пусть - равномерная случайная величина (независимая от любых предыдущих переменных, использованных для построения ). Если то заменить случайно выбранный элемент на . Вот и вся процедура!s ( t ) X ( t ) t > m s ( t + 1 ) = s ( t ) U ( t + 1 ) s ( t ) U ( t + 1 ) ≤ m / ( t + 1 ) s x ( t + 1 )$t=m+1$$s(t)$$X(t)$$t\gt m$$s(t+1) = s(t)$$U(t+1)$$s(t)$$U(t+1) \le m/(t+1)$$s$$x(t+1)$

Ясно, что имеет вероятность быть в . Более того, по предположению индукции, имел вероятность быть в когда . С вероятностью = он будет удален из , откуда его вероятность оставшихся равнаm / ( t + 1 ) s ( t + 1 ) x ( i ) m / t s ( t ) i ≤ t m / ( t + 1 ) × 1 / m 1 / ( t + 1 ) s ( t + 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$$1/(t+1)$$s(t+1)$

именно так, как нужно. Таким образом, по индукции все вероятности включения в являются правильными, и ясно, что между этими включениями нет особой корреляции. Это доказывает, что алгоритм правильный.s ( t $x(i)$$s(t)$

Эффективность алгоритма составляет потому что на каждом этапе вычисляются не более двух случайных чисел и заменяется не более одного элемента массива из значений. Требование к хранению составляет .m O ( м $O(1)$$m$$O(m)$

Структура данных для этого алгоритма состоит из выборки вместе с индексом популяции которую он выбирает. Сначала мы берем и продолжаем алгоритм для Вот реализация для обновления значением для получения . (Аргумент играет роль и равен . Индекс будет поддерживаться вызывающей стороной.)t X ( t ) s = X ( m ) t = m + 1 , m + 2 , … . ( s , t ) x ( s , t + 1 ) t m $s$$t$$X(t)$$s = X(m)$$t=m+1, m+2, \ldots.$R$(s,t)$$x$$(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)
}

Чтобы проиллюстрировать и проверить это, я буду использовать обычную (ненадежную) оценку среднего значения и сравнивать среднее значение, оцененное по с фактическим средним значением (совокупный набор данных, наблюдаемых на каждом этапе ). Я выбрал довольно сложный входной поток, который меняется довольно плавно, но периодически подвергается резким скачкам. Размер выборки довольно мал, что позволяет нам увидеть колебания выборки на этих графиках.X ( t ) m = $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]))

На этом этапе onlineпредставлена ​​последовательность средних оценок, полученных при сохранении этой текущей выборки из значений, а также последовательность средних оценок, полученных на основе всех данных, доступных в каждый момент. На графике показаны данные (серым цветом), (черным цветом) и два независимых применения этой процедуры отбора проб (в цветах). Соглашение находится в пределах ожидаемой ошибки выборки:$50$actualactual

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

Для надежной оценки среднего, пожалуйста, ищите на нашем сайте выбросы и связанные с ними термины. Среди возможностей, которые стоит рассмотреть, - средства Winsorized и M-оценки.

Вы можете подумать о том, чтобы связать свою проблему с проблемой рекурсивной контрольной диаграммы. Такая контрольная диаграмма будет оценивать, контролируется ли новое наблюдение. Если это так, это наблюдение включается в новую оценку среднего значения и дисперсии (необходимо для определения контрольных пределов).

Некоторые фон на надежных, рекурсивные, одномерные контрольных карт можно найти здесь . Один из классических текстов о контроле качества и контрольных диаграммах, кажется, доступен онлайн здесь .

Интуитивно, используя среднее значение, и дисперсию качестве входных данных, вы можете определить, является ли новое наблюдение в момент времени выбросом по ряду подходов. Можно было бы объявить выбросом, если он находится за пределами определенного числа стандартных отклонений (задано , но это может привести к проблемам, если данные не соответствуют определенным предположениям распределения. Если вы хотите пойти по этому пути, то предположим, что вы определили, не является ли новая точка выбросом, и хотели бы включить ее в свою среднюю оценку без особой скорости забвения. Тогда вы не можете сделать лучше, чем: σ 2 t - 1 t x t μ t - 1 σ 2 t - 1$\mu_{t-1}$$\sigma^2_{t-1}$$t$$x_t$$\mu_{t-1}$$\sigma^2_{t-1})$

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

Точно так же вам нужно рекурсивно обновить дисперсию:

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

Тем не менее, вы можете попробовать несколько более обычных контрольных диаграмм. Рекомендуются EWMA или CUSUM - другие контрольные диаграммы, которые более устойчивы к распределению данных и могут обрабатывать нестационарность (например, вашего процесса медленно растет) (см. Учебник, на который есть ссылки выше, для получения более подробной информации о графики и их контрольные пределы). Эти методы, как правило, будут менее вычислительно интенсивными, чем надежные, потому что они имеют преимущество, заключающееся в том, что им просто необходимо сравнивать одно новое наблюдение с информацией, полученной из не всплывающих наблюдений. Вы можете уточнить свои оценки долгосрочного процесса и использованные в расчетах контрольного предела этих методов, с помощью приведенных выше формул обновления, если хотите.μ σ $\mu$$\mu$$\sigma^2$

Что касается диаграммы типа EWMA, которая забывает старые наблюдения и придает больший вес новым, если вы думаете, что ваши данные являются стационарными (то есть параметры генерирующего распределения не меняются), то нет необходимости забывать старые наблюдения в геометрической прогрессии. Вы можете установить коэффициент забывания соответственно. Однако, если вы считаете, что это нестационарность, вам нужно будет выбрать правильное значение для коэффициента забвения (снова см. Учебник, чтобы узнать, как это сделать).

Я также должен упомянуть, что прежде чем начать мониторинг и добавление новых наблюдений в режиме онлайн, вам необходимо получить оценки и (начальные значения параметров на основе обучающего набора данных), на которые не влияют выбросы. Если вы подозреваете, что в ваших данных обучения есть выбросы, вы можете оплатить единовременную стоимость использования надежного метода для их оценки.σ 2 $\mu_0$$\sigma^2_0$

Я думаю, что подход в этом направлении приведет к быстрейшему обновлению вашей проблемы.