Тестовый пример взвешенного отбора проб из резервуара

Мне нужно реализовать взвешенный отбор проб из резервуара. Я ссылался на документ, упомянутый в этом блоге. . Я хочу написать тестовые примеры для модульного тестирования моей реализации и не понимаю, как рассчитать ожидаемую вероятность того, что другой элемент будет находиться в резервуаре.

Я думал, что это должно быть пропорционально (weight_of_element/weight_of_all_elements), но в тестовом примере упоминалось здесь вычисляет его по-другому. как мне это сделать?


machine-learning cloudera probability sampling reservoir-sampling
person Amit    schedule 11.03.2015    source источник
comment
Ожидаемая вероятность для каждого элемента должна быть равна, верно? С какой проблемой вы столкнулись? Вас смущает процесс отбора проб?   -  person eigenchris    schedule 11.03.2015
comment
@eigenchris это не отбор проб из резервуара, а взвешенный отбор проб из резервуара, поэтому он должен быть пропорционален весу элемента. Но в тест-кейсах ожидаемые значения этому не соответствуют.   -  person Amit    schedule 12.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы написать тестовый пример, вы действительно можете оценить вероятность выбора элемента. Предположим, вы присвоили веса следующим образом:
веса ​​= [1, 5, 8, 2, 5]

Теперь вы выполняете взвешенную выборку резервуара, чтобы нарисовать один элемент. Какова вероятность появления элемента в результате? Их ровно (weight_of_element/weight_of_all_elements):
prob = [0,048, 0,238, 0,381, 0,095, 0,238]

Другими словами, если вы рисуете один элемент повторно 106 раз, у вас должно быть 0,381 * 106 экземпляров третьего элемента, 0,048 * 106 экземпляры первого элемента и так далее. Примерно, конечно.

Таким образом, вы можете посмотреть процент появления первого элемента из 106 попыток. Это должно быть примерно (weight_of_first_element/weight_of_all_elements). Сравните эти значения и посмотрите, близки ли они друг к другу.

Таким образом, тестовый пример может выглядеть так (псевдокод):

numTrials = 1000000
histogram = map<int, int>
for i = 1..numTrials:
  element = WeightedReservoir.sample(weights, 1) # draw one element
  histogram[element]++
for i = 1..len(weights):
  real_probability = weights[i] / sum(weights)
  observed_probability = histogram[elements[i]] / numTrials
  assert(abs(real_probability - observed_probability) <= epsilon) # measuring absolute difference, but you can switch to relative difference

См. эту тему для конкретной реализации на Java.

Что касается Cloudera, test, который вы указали, следует другой логике (я видел это в тестах пакета Python numpy для numpy.random.choice):

  1. Процедура выборки является вероятностной по своей природе, т. е. недетерминированной;
  2. Возьмем фиксированное начальное значение для генерации случайных чисел. Вставьте это значение в тестовый пример. Теперь он полностью детерминирован: несколько раз запуская тест-кейс, мы получаем один и тот же результат;
  3. Поскольку результат детерминирован, мы можем получить его вручную (для небольших входных данных). Вставьте ожидаемый результат в test.

Если вы не можете контролировать начальное значение, этот метод не для вас.

person Mike Koltsov    schedule 22.09.2015