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

9

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

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

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

побитовое
источник
Почему бы просто не использовать начальный сегмент данных - например, первые 100 или первые 1000 или что-то еще - чтобы установить «заборы» для скрининга выбросов? Вам не нужно обновлять их снова, поэтому нет необходимости поддерживать дополнительные структуры данных.
whuber
@whuber Я не могу гарантировать, что исходный образец будет представлять остальные данные. Например, порядок, в котором мне дают данные, не является случайным (представьте себе сценарий, в котором мне сначала дают более высокие значения, а затем более низкие значения).
Побитовый
1
Это важное наблюдение. Это означает, что вам нужно проявлять больше заботы, чем обычно, потому что изначально вы будете получать «надежную» оценку среднего высокого выброса. Продолжая обновлять эту оценку, вы можете выбросить все более низкие значения. Таким образом, вам потребуется структура данных, в которой ключевые части всего распределения данных записываются и периодически обновляются. Проверьте наши темы с ключевыми словами "онлайн" и "квантиль" для идей. Два таких многообещающих находятся по адресу stats.stackexchange.com/questions/3372 и stats.stackexchange.com/q/3377 .
whuber
Я бы предложил вознаграждение, но у меня не хватает репутации
Джейсон С.
1
Чтобы продолжить идею в первом комментарии @ whuber, вы можете поддерживать однородную выборку случайного подмножества размером или из всех данных, увиденных до сих пор. Этот набор и связанные с ним «ограждения» могут быть обновлены за O (1) раз. 10001001000
Innuo

Ответы:

4

Это решение реализует предложение, сделанное @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,,ms(t)X(t)=(x(1),x(2),,x(t))1its(i)mX(t)

Для этого достаточно, чтобы каждое подмножество -элемента имело равные шансы быть индексами в . Это означает, что вероятность того, что находится в равна при условии .{ 1 , 2 , , t } x s ( t ) x ( i ) , 1 i < t , s ( t ) m / t t mm{1,2,,t}xs(t)x(i), 1i<t,s(t)m/ttm

В начале мы просто собираем поток, пока не будет сохранено элементов. На данный момент существует только одна возможная выборка, поэтому условие вероятности тривиально выполняется.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+1s(t)X(t)t>ms(t+1)=s(t)U(t+1)s(t)U(t+1)m/(t+1)sx(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/ts(t)itm/(t+1)×1/m1/(t+1)s(t+1)

mt(11t+1)=mt+1,

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

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

Структура данных для этого алгоритма состоит из выборки вместе с индексом популяции которую он выбирает. Сначала мы берем и продолжаем алгоритм для Вот реализация для обновления значением для получения . (Аргумент играет роль и равен . Индекс будет поддерживаться вызывающей стороной.)t X ( t ) s = X ( m ) t = m + 1 , m + 2 , . ( s , t ) x ( s , t + 1 ) t m tstX(t)s=X(m)t=m+1,m+2,.R(s,t)x(s,t+1)ntsample.sizemt

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 = 50s(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представлена ​​последовательность средних оценок, полученных при сохранении этой текущей выборки из значений, а также последовательность средних оценок, полученных на основе всех данных, доступных в каждый момент. На графике показаны данные (серым цветом), (черным цветом) и два независимых применения этой процедуры отбора проб (в цветах). Соглашение находится в пределах ожидаемой ошибки выборки:50actualactual

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

фигура


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

Whuber
источник
мне не ясно, как выглядит порог отклонения в этом подходе (например, порог, после которого наблюдения отклоняются как выбросы). Можете ли вы добавить их к сюжету?
user603
@ user603 «Порог отклонения» или любой другой надежный метод, используемый для оценки среднего значения, не имеет значения: выберите метод, который вы хотите оценить среднее. (Кстати, не все надежные методы работают, устанавливая пороги и отклоняя данные.) Это можно было бы сделать в коде моего ответа, заменив summaryего надежным вариантом.
whuber
Что-то мне не понятно в этом примере. Являются ли серые данные "хорошими" или "выбросами"? Если предыдущий, кажется, что смещение смещено вниз (оно должно соответствовать им лучше, так как ситуация будет похожа на нисходящий тренд @ Bitwise, которому мы хотели бы следовать). Если данные серого цвета при более высоких значениях индекса являются выбросами, тогда кажется, что подгонка смещена вверх. Какую цель вы хотите здесь разместить? Нынешнее соответствие, кажется, разрывается между этими двумя сценариями.
Deathkill14
@Death Как объяснено в тексте, непосредственно предшествующем рисунку, серые данные являются исходным потоком данных. Его среднее значение - черная кривая. Цветные кривые основаны на алгоритме. Вертикальные отклонения цветных кривых относительно черной кривой обусловлены случайностью выборки. Ожидаемая величина отклонения по любому индексу пропорциональна стандартному отклонению значений серого, предшествующего этому индексу, и обратно пропорциональна квадратному корню из размера выборки (в этом примере принята за 50).
whuber
3

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

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

Интуитивно, используя среднее значение, и дисперсию качестве входных данных, вы можете определить, является ли новое наблюдение в момент времени выбросом по ряду подходов. Можно было бы объявить выбросом, если он находится за пределами определенного числа стандартных отклонений (задано , но это может привести к проблемам, если данные не соответствуют определенным предположениям распределения. Если вы хотите пойти по этому пути, то предположим, что вы определили, не является ли новая точка выбросом, и хотели бы включить ее в свою среднюю оценку без особой скорости забвения. Тогда вы не можете сделать лучше, чем: σ 2 t - 1 t x t μ t - 1 σ 2 t - 1 )μt1σt12txtμt1σt12)

μt=t1tμt1+1txt

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

σt2=t1tσt12+1t1(xtμt)2

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

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

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

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

Deathkill14
источник
1
Использование контрольных диаграмм - интересная идея. Однако может показаться, что трудно преодолеть трудности, изложенные в комментариях к вопросу. В нестационарном случае, если вы «забываете» более старые значения, кажется, что оценки могут быть сильно смещены. Например, как ваши предложения будут работать с потоком данных, заданным ? (Это падает очень постепенно, внезапно прыгает и поднимается очень постепенно, внезапно снова прыгает и т. Д.)xt=cos(πt/106)+2t/106
whuber
@Bitwise говорит, что первоначальный образец может не представлять будущие данные. Без информации о том, насколько отличными будут остальные данные, вы по сути ничего не сможете сделать. Однако, если исходные данные содержат информацию о нестационарности процесса (скажем, нисходящую тенденцию), то можно допустить новые наблюдения с учетом того факта, что мы ожидаем, что они будут ниже. Однако, некоторая информация о нестационарности необходима. Вы предлагаете один патологический тип нестационарности. Некоторые методы, например EWMA, оптимальны для конкретного процесса, но в целом довольно хороши. Ваш процесс потребует более индивидуальной работы.
Deathkill14
(Я обнаружил в вас математику, потому что это очень математический шаг, чтобы отклонить его как «патологическое», с которым вы не можете справиться :-). Но я позволю себе не согласиться с вашим прогнозом: методы, подобные тем, которые предлагает @Innuo, действительно могут защитить от таких «патологий» и всего остального, что может бросить в вас реальный мир, особенно когда в выборку включается рандомизация.
whuber
На самом деле, я согласен с тем, что нельзя сбрасывать со счетов проблему, с которой сталкиваешься. Не могли бы вы связать меня с обсуждаемыми методами @Innuo (я не могу найти их в этом посте - были ли они в ссылках, которые вы предоставили выше, и я пропустил их?). Спасибо.
Deathkill14
@Innuo опубликовал краткий комментарий на stats.stackexchange.com/questions/56494/…, предлагая сохранить единую случайную выборку всех ранее наблюдавшихся данных за раз. Хотя не совсем ясно, как именно это будет сделано, соединение его с надежной оценкой среднего значения будет представлять собой универсальное решение, применимое к любому потоку данных вообще. O(1)
whuber