статистика — выборка дискретного распределения c ++ с часто меняющимися вероятностями
Проблема: мне нужно сделать выборку из дискретного распределения, построенного из определенных весов, например, {w1, w2, w3, ..} и, следовательно, распределение вероятностей {p1, p2, p3, …}, где pi = wi / (w1 + w2 + …).
некоторые из них меняются очень часто, но только очень малая доля всех wi. Но сам дистрибутив, таким образом, должен быть перенормирован каждый раз, когда это происходит, и поэтому я считаю, что метод Alias не работает эффективно, потому что каждый раз нужно будет создавать весь дистрибутив с нуля.
Метод, о котором я сейчас думаю, — это двоичное дерево (метод кучи), где все wi сохраняются на нижнем уровне, а затем сумма каждых двух на более высоком уровне и так далее. Сумма всех из них будет на самом высоком уровне, который также является константой нормализации. Таким образом, чтобы обновить дерево после изменения в wi, нужно сделать log (n) изменений, а также столько же, чтобы получить образец из дистрибутива.
Вопрос:
Q1. У вас есть идея, как добиться этого быстрее?
Q2. Самая важная часть: я ищу библиотеку, которая уже сделала это.
Объяснение: я сделал это сам несколько лет назад, создав структуру кучи в векторе, но с тех пор я узнал много вещей, включая обнаружение библиотек (:)) и таких контейнеров, как map … Теперь мне нужно переписать этот код с более высокой функциональностью, и я хочу сделать это прямо сейчас:
так что Q2.1 есть хороший способ упорядочить и найти карту c ++ не по индексу, а по совокупной сумме ее элементов (это то, как мы производим выборку, верно? ..). (это моя текущая теория, как я хотел бы это сделать, но это не обязательно должно быть так …)
Q2.2 Может быть, есть еще лучший способ сделать то же самое? Я полагаю, что эта проблема настолько частая, что я очень удивлен, что не смог найти какую-то библиотеку, которая бы сделала это для меня …
Большое спасибо, и мне очень жаль, если это было задано в какой-то другой форме, пожалуйста, направьте меня к этому, но я потратил много времени, глядя …
-Z
Изменить: Существует возможность, что мне может понадобиться удалить или добавить элементы, но я считать Я мог бы избежать этого, если бы это имело огромное значение, оставляя только изменение значения весов.
Edit2: веса в общем случае действительны, я бы подумал, если бы я мог сделать их целыми числами …
Решение
Я бы на самом деле использовал хеш-набор строк (не помните контейнер C ++ для него, вам может понадобиться реализовать свой собственный). Поместите элементы wi для каждого i со значениями «w1_1», «w1_2», … все через «w1_ [w1]» (то есть элементы w1, начинающиеся с «w1_»).
Когда вам нужно сделать выборку, выберите элемент случайным образом, используя равномерное распределение. Если вы выбрали w5_ *, скажем, вы выбрали элемент 5. Из-за количества элементов в хэше это даст вам искомый дистрибутив.
Теперь, когда wi меняется с A на B, просто добавьте элементы B-A в хеш (если B> A) или удалите последние элементы A-B элемента wi (если A> B).
Добавление новых элементов и удаление старых элементов в этом случае тривиально.
Очевидно, проблема заключается в том, чтобы «выбрать элемент наугад». Если ваш хэш является закрытым, вы выбираете ячейку массива наугад, если она пуста — просто выберите случайную ячейку снова. Если вы сохраните свой хэш в 3 или 4 раза больше, чем общая сумма весов, ваша сложность будет довольно хорошей: O (1) для получения случайной выборки, O (| A-B |) для изменения весов.
Другой вариант, поскольку изменяется только небольшая часть ваших весов, — разделить веса на две части — фиксированную часть и измененную часть. Тогда вам нужно только беспокоиться об изменениях в измененной детали и о разнице между общим весом измененных деталей и общим весом неизмененных деталей. Затем для фиксированной части ваш хеш становится простым массивом чисел: 1 появляется w1 раз, 2 появляется w2 раз и т. Д., А выбор случайного фиксированного элемента — это просто выбор случайного числа.
Другие решения
Обновление коэффициента нормализации при изменении значения тривиально. Это может предложить алгоритм.
w_sum = w_sum_old - w_i_old + w_i_new;
Если вы оставите p_i в качестве вычисляемого свойства p_i = w_i / w_sum, вы избежите пересчета всего массива p_i за счет вычисления p_i каждый раз, когда они необходимы. Однако вы сможете обновить многие статистические свойства без пересчета всей суммы.
expected_something = (something_1 * w_1 + something_2 * w_2 + ...) / w_sum;
С некоторой долей алгебры вы можете обновлять Ожидаемый_счет, вычитая вклад со старым весом и добавляя вклад с новым весом, умножая и деля на коэффициенты нормализации по мере необходимости.
Если вы во время выборки будете отслеживать, какие результаты являются частью выборки, можно было бы распространить, как вероятности были обновлены в сгенерированной выборке. Позволит ли это вам обновить, а не пересчитать значения, связанные с образцом? Я думаю, что растровое изображение может обеспечить эффективный способ хранения индекса, результаты которого были использованы для построения выборки.
Один из способов хранения вероятностей вместе с суммами — начать со всех вероятностей. В следующих N / 2 позициях вы сохраняете суммы пар. После этого N / 4 суммы пар и т. Д. Где находятся суммы, очевидно, можно рассчитать за O (1) время. Эта структура данных вроде кучи, но с ног на голову.