Поиск предложений для представления данных распределения вероятности

Ответ 1

Интересная проблема. Вот предложение, которое может быть довольно сложно реализовать в зависимости от того, насколько вы математически склонны.

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

Сначала используйте функциональный подход. Распределение вероятностей является вероятностной мерой:

struct Distribution
{
    virtual ~Distribution() {};
    virtual double integrate(std::function<double(double)>) = 0;
};

Таким образом, вы абстрагируетесь от образцов, которые вы производите, поскольку вы не хотите их хранить. Убедите себя, что вы можете сделать почти что угодно с помощью метода "интегрировать".

Конечно, с явными образцами вы делаете что-то вроде

struct SampledDistribution
{
    double integrate(std::function<double(double)> f)
    {
        double acc = 0;
        for (double x: samples) acc += f(samples);
        return acc / samples.size();
    }

    std::deque<double> samples;
};

Теперь часть хранения:

Обычное представление - массив гистограмм - нежелательно в основном из-за компромисса между квантованием/разрешением и пространством. я представьте, что должен быть метод представления, который адаптивно изменяется размер корзины в зависимости от локальной сложности.

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

Затем для десериализации вы создаете объект Distribution, метод integrate выполняет интеграцию с всплесками. Интеграция может быть выполнена с помощью вашего любимого квадратурного метода. Я остаюсь преднамеренно неопределенным здесь, потому что фактическая реализация зависит от семейства вейвлетов, которые вы выбираете (гладкие, компактно поддерживаемые, ортогональные или нет и т.д.). В любом случае вам нужно будет погрузиться в litterature.

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

Кроме того, показатель 0.001 довольно высокий: я подозреваю, что вам понадобится только несколько коэффициентов

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

Я бы предпочел всплески, которые определены в области Фурье (например, вялотемы Lemarie), так как их значение и производные в нуле в пространстве Фурье известны, это позволяет вам применять противопоказания к распределению: вероятностные меры должны интегрироваться в один, и вы можете заранее знать ожидаемое значение или дисперсию.

Кроме того, вы можете изменить переменные только для работы с функциями, например. на [0,1]. На впадинах на интервале имеется обильная литратура.

Ответ 2

Как насчет этого:

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

Теперь давайте построим для него приближение, начиная с тривиальной гистограммы с одним ведром, содержащим все образцы.

Для всех ковши в приближении рассмотрим расщепление его в середине int два ведра, но только на самом деле разбить ведро, что даст лучшее улучшение в приближении.

до тех пор, пока не будет достигнуто желаемое приближение или не будет получено максимально допустимых ковшей.

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

Вам также нужен некоторый критерий, когда нужно остановиться.

Я думаю, что это на самом деле очень похоже на Octree в 1D. Вы можете посмотреть там для эффективных реализаций.

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

Ответ 3

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

Как уже упоминалось здесь, октет для многократно разрешенных данных кажется правильным представлением структуры данных, которую вы желаете. Вместо плоской гистограммы, содержащей данные, привязанные к корзинам, ваша цель - хранить возмущения в наборе данных на разных уровнях фиксированной детализации. Это наиболее похоже на алгоритм, используемый для сжатия JPEG, с дополнительным желанием вытягивать образцы из дистрибутива на определенном уровне детализации и сложности.

Для создания алгоритма классификации или дихотомизатора для заполнения структуры данных я настоятельно рекомендую посмотреть алгоритмы декомпозиции, такие как JPEG 2000 для определения формы и сложность возмущений в данных. Другие подходы (например, ID3 и C4.5) также может быть уместным, но я чувствую, что простая, векторизованная декомпозиция может работать для ваших целей.

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

Ответ 4

Храните n квантилей. Они будут адаптивно адаптироваться вокруг режимов.

Пусть n является степенью 2, затем поиск плотности (и кумулятивной вероятности) может быть ограничен O (log (n)) путем сохранения квантилей в виде двоичного дерева медианов и "субсредних" рекурсивно.