Как выбрать точки интерполяции, чтобы уменьшить максимальную ошибку для обратного поиска CDF

Question

ВОПРОС: Как выбрать точки интерполяции, которые сохраняют максимальную ошибку для любой точки в каждом интерполированном сегменте в пределах указанной границы?

Цель состоит в том, чтобы сформировать случайное распределение в соответствии с законом Ципфа, используя выборку с обратным преобразованием. Я нашел хорошее приближение фактора нормализации Zipf здесь:

https://arxiv.org/abs/1511.01480 ("Аппроксимация усеченного дзета-распределения и закона Ципфа" Маурицио Налди)

То, что я сейчас делаю, - это создание сплайна значений CDF в зависимости от ранга и попытка установить границу ошибки так, чтобы ни для какого ранга не было интерполированного значения более чем на определенный процент от его значения (относительная ошибка). Если у меня слишком много точек сплайна, это напрасно тратит память. Если у меня слишком мало очков, это увеличивает ошибку. Я пытаюсь найти оптимальное расположение точек сплайна, чтобы сбалансировать эти два.

Мой текущий подход (который терпит неудачу) состоит в том, чтобы перебрать все ранги и посмотреть на различия в значениях PDF между последовательными рангами. Эта разница является прокси для первой производной. Я отслеживаю значения MIN и MAX для разницы, и когда они отличаются слишком сильно пропорционально CDF, я предполагаю, что кривая изогнулась слишком сильно, и я добавляю новую точку интерполяции и начинаю отслеживать различия во всем. Этот алгоритм выдает слишком мало точек интерполяции, потому что ошибка накапливается быстрее, чем я ожидал.

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

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

Кстати, для каждого сегмента сплайна я пробовал следующие интерполирующие функции:

1. Линейный - плохие результаты.

2. Квадратичный - лучше, но все же бедный.

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

ПРИМЕЧАНИЕ. Гиперболический режим работает лучше, чем ожидалось, поскольку, в то время как гауссовы распределения дают S-кривую для CDF, как и большинство других распределений, Zipf PDF имеет свой пик в начале, поэтому его CDF выглядит как гипербола с асимптотой в единицу.

ОБНОВИТЬ:

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

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

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

Answer 1

Я решил проблему плохого соглашения о поездке туда и обратно. Функция ранга CDF имеет горизонтальную асимптоту в 1. У обратной функции есть вертикальная асимптота в N. У меня была неправильная интерполяционная функция!

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

Для N = 10000 мне нужно около 200 точек интерполяции, чтобы ошибка была очень низкой. Но если я просто использую дистрибутив Zipf для тестирования, тридцати достаточно.