О простом методе быстрого обновления абсолютных центральных моментов06.12.2023 11:16

Привет, Хабр! Иногда сидишь, решаешь задачу, и, в процессе решения, чтобы продвинуться на следующий шаг, нужно придумать как сделать что-то очень простое — ну, то что наверняка уже делалось тысячи раз другими людьми. Кинувшись в поисковик перелопачиваешь какое-то количество литературы и вдруг понимаешь что либо ты просто искать не умеешь, либо это действительно никто до тебя не делал, или делал, но об этом не писал. В какой-то момент проще просто взять и решить задачу самому…

В этой заметке мы расскажем об одной такой задаче — простой, но которая нам понадобилась для кое-чего другого. Задача — придумать, как при увеличении наблюдаемой выборки быстро пересчитать ее абсолютный центральный момент.

Конкретная задача, которую мы решали, когда наткнулись на эту проблему — не очень существенна — мы пытались ускорить моделирование следующего комбинированного результата распознавания текстовой строки в видеопотоке, которое нам нужно для принятия решение об остановке (мы про это писали раньше на хабре). В процессе разработки метода (описанного, кстати, вот в этом докладе) мы наткнулись на задачу, которая один в один совпадала с задачей быстрого обновления абсолютного центрального момента первого порядка по некоторой выборке. И, к нашему удивлению, не смогли нагуглить, как это обычно делают. На самом деле делать это не трудно, и мы решили рассказать об этом здесь на Хабре, в более общем виде, на случай, если подобная проблема когда-то у кого-нибудь еще возникнет.

Итак, для начала нужно рассказать, что такое моменты выборок и какие они бывают. Для выборки $A = \{a_1, ..., a_n\}$ можно определить два вида моментов -го порядка:

$\text{Начальный:}\quad \nu_k (A) = \frac{1}{n}\sum^n_{i=1} a_i^k,$ $\text{Центральный:}\quad \mu_k (A) = \frac{1}{n}\sum^n_{i=1} \left(a_i - \nu_1 (A) \right)^k.$

Для каждого из них так же существуют абсолютные версии:

$\text{Абсолютный начальный:}\quad \widetilde{\nu}_k (A) = \frac{1}{n}\sum^n_{i=1} \left|a_i \right|^k,$ $\text{Абсолютный центральный:}\quad \widetilde{\mu}_k (A) = \frac{1}{n}\sum^n_{i=1} \left|a_i - \nu_1 (A) \right|^k.$

Первый начальный момент $\nu_1(A)$ — математическое ожидание по выборке (или просто среднее значение по выборке), а 2-й центральный момент $\mu_2(A)$ также называется дисперсией выборки. Очевидно также, что абсолютные моменты четных порядков совпадают с соответствующими обычными моментами тех же порядков.

Задача быстрого обновления моментов выборки формулируется так: пусть наша выборка пополняется по одному элементу за один раз. На -м шаге процесса существует некоторая выборка $A = \{a_1, ..., a_{n-1}\}$ размера n-1 , и этой выборке добавляется очередной элемент a_n . После добавления a_n в выборку нужно пересчитать текущее значение того или иного момента выборки как можно быстрее, используя какие-нибудь аккумуляторы.

Из четырех типов моментов три легко и быстро обновляются. Действительно, чтобы обновлять начальный или абсолютный начальный моменты порядка достаточно аккумулировать сумму -х степеней элементов выборки или их модулей, соответственно. Чтобы понять, как быстро обновлять центральный момент порядка , можно воспользоваться вот этой формулой, напрямую следующей из разложения формулы центрального момента с помощью бинома Ньютона:

$\mu_k(A)=\sum_{j=0}^k C_k^j \left( \frac1n \sum_{i=1}^n a_i^{k-j} \right)(-\nu_1(A))^j.$

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

Что же делать с абсолютным центральным моментом? Если порядок четный, то он совпадает с обычным центральным моментом, это понятно. А если порядок нечетный?…

Давайте мысленно разобьем нашу выборку на две части: и . Часть $L=\{a\in A | a < \nu_1(A)\}$ — это элементы выборки со значениями, меньшими среднего, а часть $R=\{a\in A | a \ge \nu_1(A)\}$ — элементы выборки со значениями, большими и равными среднему. Сумма модулей, возникающая в определении абсолютного центрального момента, может теперь быть раскрыта как две суммы без модулей — отдельно по части , для которой модули раскрываются «со знаком минус» и по части , для которой они раскрываются «со знаком плюс»:

$\widetilde{\mu}_k(A)=\frac1n \left( \sum_{l\in L} (\nu_1(A)-l)^k + \sum_{r\in R} (r-\nu_1(A))^k \right).$

Раскроем эту формулу с помощью бинома Ньютона:

$\widetilde{\mu}_k(A)=\frac1n \left( \sum_{l\in L} \sum_{j=0}^k (\nu_1(A))^{k-j}(-1)^kl^jC_k^j + \sum_{r\in R}\sum_{j=0}^kr^{k-j}(-1)^j(\nu_1(A))^jC_k^j \right).$

И, аналогично формуле для обычного центрального момента, вынесем за скобки и за знаки суммы все, что можем:

$\widetilde{\mu}_k(A)=\frac1n \left( \sum_{j=0}^k(-1)^jC_k^j \left( (\nu_1(A))^j\sum_{r\in R}r^{k-j}+(\nu_1(A))^{k-j}\sum_{l\in L} l^j \right) \right).$

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

Аккумулировать суммы всех нужных нам степеней элементов множества легко, если хранить выборку в виде сбалансированного дерева поиска (к примеру, АВЛ-дерева, декартова дерева, или любого другого). Пусть каждому элементу выборки соответствует вершина дерева поиска, а также в вершине содержатся суммы всех нужных нам степеней всех элементов в поддереве с корнем в этой вершине. Тогда в таком дереве можно реализовать ответ на вопрос вида «какова сумма -х степеней всех элементов выборки , меньших заданного значения ?» (в качестве мы всегда будем использовать $\nu_1(A)$ ). Действительно, чтобы ответить на такой вопрос, достаточно спуститься по дереву в поиске значения и каждый раз при переходе в правое поддерево добавлять к ответу -ю степень текущей вершины и ее левого поддерева. Трудоемкость операции — $O(\log n)$ .

Трудоемкость добавления нового элемента в сбалансированное дерево будет составлять $O(k\log n)$ — логарифм на перестроение структуры, и мультипликатор , поскольку при каждой операции над деревом придется пересчитывать аккумуляторов в нескольких вершинах. За эту же трудоемкость мы можем получить значения всех аккумуляторов, которые используются в нашей формуле абсолютного центрального момента, а трудоемкость всех остальных операций для ее вычисления не превышает O(k) .

Таким образом, у нас получилось обновить -й абсолютный центральный момент выборки размера за время $O(k\log n)$ , хотя для этого нам пришлось содержать сбалансированное дерево с вершинами и с аккумулятором размера O(k) в каждой вершине.

Пару слов про то, зачем это нам вообще понадобилось. Ранее мы писали на хабре, что нас интересует задача поиска оптимального момента остановки — когда принимать решение о том, что захват кадров при распознавании в видеопотоке можно прекратить, и текущий результат принять как окончательный. Алгоритм, которым мы пользовались, состоял в моделировании возможного следующего наблюдения (т.е. следующего комбинированного результата распознавания) и в оценке расстояния от текущего результата до возможного следующего. Однако моделирование следующего результата, которое мы использовали, было достаточно накладным — оно нас устраивало теоретически, но практически требовало слишком много вычислений, да еще и это количество вычислений линейно зависело от количества уже просмотренных кадров. Мы придумали (и описали в этом докладе) более дешевый способ такого моделирования, и для обновления значения расстояния от текущего результата распознавания до моделируемого нам пришлось решать задачу, один в один совпадающую с задачей обновления 1-го абсолютного центрального момента. Решив ее так, как мы описали выше, с использованием декартовых деревьев в качестве поисковой структуры данных, мы получили способ принятия решения об остановке процесса распознавания, который вычисляет свое решение в десятки раз быстрее, чем то, что мы использовали до этого.

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