Работа с небольшими вероятностями через журналы
Источник: ошибка в Google Code. https://code.google.com/codejam/contest/10224486/dashboard#s=a&a=1
Мы попросили рассчитать Prob (K успехов из N испытаний), где каждое из N испытаний имеет известную вероятность успеха p_n.
Некоторые анализы и мысли по проблеме задаются после пробки кода.
Они отмечают, что оценка всех возможных результатов ваших испытаний N приведет к экспоненциальному времени в N, поэтому вместо этого они обеспечивают хорошее решение стиля "динамического программирования", которое O (N ^ 2).
Пусть P (p # q) = Prob (p Успехи после первых q испытаний)
Тогда заметим, что:
Prob(p#q) = Prob(qth trial succeeds)*P(p-1#q-1) + Prob(qth trial fails)*P(p#q-1)
Теперь мы можем построить таблицу P (i # j), где я <= j, для я = 1... N
Что все прекрасное - я следую всему этому и могу его реализовать.
Затем, как последний комментарий, они говорят:
In practice, in problems like this, one should store the logarithms of
probabilities instead of the actual values, which can become small
enough for floating-point precision errors to matter.
Я думаю, что в целом понимаю, что они пытаются сделать, но я не могу понять, как использовать это предложение.
Взяв вышеприведенное уравнение и подставив в него некоторые буквенные переменные:
P = A*B + C*D
Если мы хотим работать в Log Space, мы имеем:
Log(P) = Log(A*B + C*D),
где мы рекурсивно предварительно вычислено Log(B) и Log(D), а A и B известны, легко обрабатываемые десятичные числа.
Но я не вижу никакого способа вычислить Log(P), не делая просто e^(Log(B)) и т.д., который чувствует, что он победит точку работы в лог-пространстве`?
Кто-нибудь лучше понимает, что я должен делать?
Ответы
Ответ 1
Начиная с начального отношения:
P = A⋅B + C⋅D
Из-за его симметрии мы можем предположить, что B больше, чем D, без потери общности.
Полезна следующая обработка:
log (P) = log (A⋅B + C⋅D) = log (A⋅e log(B) + C⋅e log(D)) = log (e log(B) ⋅ (A + C⋅e log(D) - log(B))
log (P) = log (B) + log (A + C⋅e log(D) - log(B)).
Это полезно, потому что в этом случае log (B) и log (D) являются отрицательными числами (логарифмы некоторых вероятностей). Предполагалось, что B больше, чем D, поэтому его лог ближе к нулю. Следовательно, log (D) - log (B) по-прежнему отрицательно, но не так отрицательно, как log (D).
Так что теперь вместо того, чтобы выполнять возведение в степень log (B) и log (D) по отдельности, нам нужно только возвести возведение в степень log (D) - log (B), который является слегка отрицательным числом. Таким образом, приведенная выше обработка приводит к лучшему числовому поведению, чем использование логарифмов и тривиальным способом возведения в степень, или, что эквивалентно, чем не использование логарифмов вообще.
