Применение HyperLogLog к выборке населения

HyperLogLog алгоритм Flajolet и др. описывает умный способ оценки мощности набора, использующего только небольшой объем памяти. Однако он принимает учет всех N элементов исходного набора в расчете. Что если у нас был доступ только к небольшой случайной выборке (скажем, 10%) исходного N? Проводилось ли какое-либо исследование того, как HyperLogLog или подобные алгоритмы могут быть адаптированы к этой ситуации?

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

Ответ 1

Тем не менее, исследование по отдельной оценке стоимости, которое мне известно использует ряд специальных оценок, сильно отличающихся от подхода используется HyperLogLog.

Да, потому что они решают совсем другую проблему.

Предположим, вы только что конфисковали котировку 1.000.000 фальшивых долларовых купюр, и вы хотите узнать количество различных серийных номеров.

Сэмплирование 100 000 из них (с использованием HyperLogLog, так как ваша старинная паровая счетная машина имеет только 1кб памяти), вы считаете 5000 разных серийных номеров, каждый из которых происходит где-то около 20 раз. Тогда вы можете быть уверены, что весь тайник будет содержать только немногим более 5000 различных серийных номеров.

Теперь предположим, что 1 серийный номер происходит 95.001 раз, а серийные номера 4999 - только один раз. По-видимому, в ваш тайник попали некоторые добросовестные банкноты. Теперь вы можете быть достаточно уверены, что в кошельке содержится около 5% честных банкнот, так что весь тайник содержит около 50 000 различных серийных номеров.

Обратите внимание, что распределение частот в вашем образце используется, чтобы вывести что-то о распределении во всем тире. Это фактически упоминается как один из методов "ad hoc" (ваши слова) в второй документ, который вы цитируете ( "Оценка на основе выборки количество различных значений (..)" ):

Идея параметрической оценки состоит в том, чтобы сопоставить распределение вероятностей с наблюдаемые относительные частоты различных значений атрибутов.

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

Мой совет: используйте метод по вашему выбору (например, HyperLogLog) для подсчета количества различных значений в вашем примере, а затем используйте один из методов в "Оценка на основе выборки", чтобы оценить количество значений во всем мультимножестве, или используйте свои прежние знания, связанные с распределением мультимножества, чтобы рассчитать оценку (возможно, вы видели печатный станок для фальшивомонетчиков, и вы знаете, что он мог печатать только один серийный номер)

Ответ 2

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

Оптимальный алгоритм для проблемы с отдельными элементами