10.01.2025 21:33
volodya_research 17 2200 Источник

В данной статье я разбираю математику, лежащую в основе двух связанных технических задач. Я показываю, как из биномиального распределения рождается Бета-распределение и демонстрирую расчет доверительного интервала для последнего: через точную формулу для случая с k=0 (\alpha=1) и через нормальное приближение в общем случае.

Задача 1:

Осьминог Пауль предсказывает победу команды в турнире. Из 16 матчей Пауль совершил верное предсказание 14 раз. Оцените предсказательную силу осьминога.

Задача 2:

Вы подбрасываете монетку 10 раз подряд и 10 раз выпадает орел. Какая вероятность того, что в 11 раз выпадет решка?

По факту в обеих задачах нас просят оценить вероятность единичного успеха в схеме испытаний Бернулли.

Интуиция за биномиальным и Бета-распределениями

Биномиальное распределение позволяет рассчитать вероятность получения определенного количества успешных исходов в серии независимых испытаний Бернулли при фиксированной вероятности успеха. Математически это можно записать как:

Bin(p, n) [k] = P(k\; успехов\; в \; n \; испытыниях \; | \;вероятность\;успеха = p)

В практических задачах (см. выше) часто известны количество успехов k и общее число испытаний n, но неизвестна вероятность успеха p. Чтобы оценить вероятность единичного успеха на основе наблюдаемых данных, необходимо применить байесовский подход и "перевернуть" условную вероятность с помощью Бета-распределения. Эта идея хорошо показана в видео 3Blue1Brown про Биномиальное распределение, а также в видео Serrano Academy про Бета-распределение.

Beta(k, n) [p] \sim P(вероятность \; успеха = p \;|\; k\; успехов\; в\; n\; испытаниях)

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

Формула для Бета-распределения

Для биномиального распределения существует хорошо известная формула:

Bin(p, n)[k] = C_{n}^{k}\;p^k\;(1-p)^{n-k}

Если рассматривать эту формулу как функцию от p при фиксированных значениях k и n, мы получаем функцию плотности следующего вида:

Beta(k, n)[p] = (n+1) \; C_{n}^{k}\;p^k\;(1-p)^{n-k}

Дополнительный множитель n+1 возникает как артефакт нормирования этой функции по p (площадь функции на отрезке [0,1] должна быть равна единице).

Дисклеймер. В математической литературе Бета-распределение традиционно параметризуется через α и β (см. статью про Бета-распределение в Википедии). В контексте нашего обсуждения, где мы рассматриваем Бета-распределение через параметры k и n, это соответствует распределению с параметрами α = k+1 и β = n-k+1 в стандартной нотации.

Как получить нормировочный коэффициент:

Коэффициент перед множителями, содержащими p выражается следующим образом.

\int_{0}^{1}p^{k}(1-p)^{n-k}dp = \frac{Г(k+1)Г(n-k+1)}{Г(n+2)} = \frac{k!(n-k)!}{(n+1)!} = \frac{1}{(n+1)\; C_{n}^{k}}

Его также принято записывать через Beta-функцию (статья про Beta-функцию в Википедии):

\int_{0}^{1}p^{k}(1-p)^{n-k}dp = B(k+1, n-k+1)

Рисунок 1. Семейство кривых Бета-распределения для n = 10 и k = 0, 2, 5, 8, 10 — слева направо. Предельные кривые для k = 0 (слева) и k = 10 (справа) выделены синим цветом.
Рисунок 1. Семейство кривых Бета-распределения для n = 10 и k = 0, 2, 5, 8, 10 — слева направо. Предельные кривые для k = 0 (слева) и k = 10 (справа) выделены синим цветом.

Нормальное приближение и доверительные интервалы

Для достаточно больших k и n функцию Бета-распределения удобно аппроксимировать нормальным распределением:

Beta(k, n)[p] \xrightarrow[n \rightarrow \infty]{k\rightarrow \infty} Norm\Bigg(\mu = \frac{k}{n}, \;\sigma = \sqrt{\frac{k/n\;(1-k/n)}{n}} \Bigg)[p]

В общем виде формула нормального приближения будет слегка другой (ссылка на раздел Википедии со специальными пределами Бета-распределения). Будут добавляться целые числа в случайных места — можете также посмотреть хорошее видео на канале ritvikmath), но для больших n и k (10-20), мы вполне комфортно сможем пользоваться таким приближением.

Точная формула для среднего и стандартного отклонения Бета-распределения

Среднее (см. вывод в статье в Википедии (*)):

\mu = \frac{k+1}{n+2} \xrightarrow[n \rightarrow \infty]{k\rightarrow \infty} \frac{k}{n}

Эта формула для \mu известна также как правило последовательности Лапласа (ссылка на таймкод ролика 3Blue1Brown), которое гласит, что для оценки априорного распределения вероятностей по имеющейся выборке, нужно добавить к ней одно положительное и одно отрицательное наблюдения. Например, если 10/10 отзывов о фильме являются положительными, то оценкой хорошести фильма будет 11/12.

Смещение \mu следует из скошенности распределения. При k = n/2 никакого смещения не будет, и мы получим, что \mu = k/n = 1/2

Дисперсия (см. вывод в статье Википедии (*)):

\sigma^2=\frac{(k+1)(n-k+1)}{(n+2)^2(n+3)} \xrightarrow[n \rightarrow \infty]{k\rightarrow \infty} \frac{k/n\;(1-k/n)}{n}

(*) Чтобы воспользоваться формулами из статьи, необходимо сделать переход к \alpha и \beta. Напоминаю, что \alpha = k+1, \beta = n-k+1

Рисунок 2. Семейство кривых Бета-распределения для n = 10 и k = 0, 2, 5, 8, 10 — слева направо. Предельные кривые для k = 0 (слева) и k = 10 (справа) выделены синим цветом.Для кривых с k = 2, 5, 8 пунктирной линией (--) показано нормальное приближение.
Рисунок 2. Семейство кривых Бета-распределения для n = 10 и k = 0, 2, 5, 8, 10 — слева направо. Предельные кривые для k = 0 (слева) и k = 10 (справа) выделены синим цветом.
Для кривых с k = 2, 5, 8 пунктирной линией (--) показано нормальное приближение.

Для нормального распределения известна формула для расчета доверительного интервала через среднее и дисперсию. 95% значений находятся внутри 2 стандартных отклонений от среднего (точное значение 1.96), а 99.9%. значений находятся внутри 3 стандартных отклонений от среднего.

95% интервал для k\neq0:

\boxed{p = \frac{k}{n} ± 1.96 \cdot\sqrt{\frac{k/n(1-k/n)}{n}}}

Для задачи с осьминогом мы получим (87.5 ± 16.2)\; \%

95% доверительный интервал для k=0:

\boxed{p\leq1-0.05^{{1/(n+1)}}}

Для задачи с монеткой мы получим промежуток от 0 до 0.24.

Вывод формулы для доверительного интервала

При k=0(Это мы смотрим как будто \alpha=1 в известной терминологии) формула для Бета-распределения становится:

Beta(0, n)[p] = (n+1) \; (1-p)^n

Мы хотим найти такое p_{crit}, что площадь под распределением от 0 до p_{crit} равняется 95% (считаем 95%-доверительный интервал).

Решив уравнение:

\int_{0}^{p_{crit}}(n+1)(1-p)^{n}dp = 0.95

Мы и получаем формулу выше для расчета доверительного интервала :)

Заключение

Навык оценки вероятности успеха для каждого отдельного испытания (с помощью Бета-распределения) лежит в основе мощного алгоритма для тестирования различных бинарных объектов, таких как многорукий бандит. Этот метод предлагает стратегию выбора наилучшего варианта (например, лендинга) через постоянное обновление вероятности успеха по мере накопления данных и предпочтение более эффективных вариантов. Благодаря этому подходу можно избежать потерь, если один из вариантов окажется слишком плох, поскольку алгоритм будет отдавать приоритет более успешному лендингу, не снижая общие показатели. Видео по этой теме вы можете посмотреть в уже упомянутых мной каналах — ritvikmath и Serrano.Academy.

Комментарии (17)


  1. Sazonov
    10.01.2025 23:08
    #27767734

    Тервер действительно нужен всем 100% C++ программистам Яндекса?


    1. tbl
      10.01.2025 23:08
      #27767740

      Это скорее задачи аналитикам. Не понял только про монеты. Испытания же независимы. Вероятность выпадения решки и орла у монеты одинакова, и не зависит от исходов предыдущих испытаний.


      1. volodya_research Автор
        10.01.2025 23:08
        #27768306

        Да, все верно. Задачи для аналитиков.

        Вы все правильно написали. В схеме Бернулли испытания независимы. Вероятность, что в 11 раз выпадет орел при условии, что в первые 10 раз выпала решка равна вероятности, что на данной монете выпадет орел в принципе (в любой раз).

        При этом априорное распределение вероятностей монетки (с какой вероятностью каждый раз выпадет решка) оценивается и моделируется как распределение p при условии того, что мы 10 раз подряд получили решку.


        1. volodya_research Автор
          10.01.2025 23:08
          #27768312

          Здесь был ещё один комментарий про то, что в схеме Бернулли испытания независимы. Я его случайно удалил, когда заходил с телефона. Прошу прощения.


      1. Sazonov
        10.01.2025 23:08
        #27769214

        Лет 8-9 назад собеседовался на с++ в минский офис яндекса. Тервер был обязательным, причем еще до каких-либо вопросов по программированию.


  1. kulity
    10.01.2025 23:08
    #27768318

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

    Правильно понимаю, что в данном случае эксперимент с монеткой рассматривается как «чёрный ящик» и мы делаем вывод, что если орел выпал 10 раз подряд, то и в дальнейшем он будет выпадать чаще, так как мы просто не знаем условий проведения эксперимента?


    1. volodya_research Автор
      10.01.2025 23:08
      #27768330

      Именно так! Вы все написали верно! В задаче про монетку неизвестно, честная она или нет, и степень честности предлагается оценить на основе одного эксперимента из 10 испытаний.

      Вместо монетки могут быть отзывы в интернете. У одного товара 10/10 отзывов положительны. У другого 90/100 положительны.

      В этой статье я показываю, что для случая 10/10 распределение положительных отзывов скорее всего (с 95% уверенностью) лежит в интервале (76, 100)%, а в случае 90/100 распределение положительных отзывов скорее всего (с 95% уверенностью) лежит в интервале (84, 96)%


      1. bellerofonte
        10.01.2025 23:08
        #27768620

        есть мнемоническое правило, которое позволяет прикинуть "честность" бинарного эксперимента: нужно добавить к имеющейся выборке 1 положительное событие и 1 отрицательное (нулевое) и посчитать мат.ожидание полученной выборки. в случае 10 орлов для монетки получаем (11 / 12) ≈ 91% вероятность орла.

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


        1. volodya_research Автор
          10.01.2025 23:08
          #27769828

          Вы совершенно правы! Это мнемоническое правило называется правилом последовательности Лапласа и хорошо описано в видео 3Blue1Brown (ссылка на таймкод). Также в статье Википедии про Бета-распределение есть целый раздел на эту тему.

          Данное мнемоническое правило точно оценивает среднее значение Бета-распределения, и я упомянул про него в этой статье в блоке про точную оценку среднего и дисперсии.

          Это правило замечательно подходит для оценки априорной вероятности успеха, и я решил показать, как можно вычислить доверительный интервал для такой оценки. В вашем примере среднее, действительно, равно 11/12 = 91 %, но доверительный интервал для нее находится в диапазоне от 76 до 100 %. Зная доверительный интервал, можно обоснованно выбирать между товаром с 90 положительными отзывами из 100 и товаром с 10 положительными отзывами из 10. Если пользоваться только правилом Лапласа, в данном примере можно ошибочно отдать предпочтение товару с меньшим числом отзывов, что будет неверным или, по крайней мере, неверно обоснованным :)


    1. Ad_fesha
      10.01.2025 23:08
      #27768674

      Получал эту задачу на собесе Яндекса. Звучит задача так: "Какова вероятность выпадения монеты 10 раз подряд Орлом? Какова вероятность что в 11 раз так-же выпадет Орел?". Задача была с мини подвохом, что первый Ваш ответ повлияет на Ваше суждение и на второй ответ, но ничего сложного и тем более каких то разборов с формулами не требовала (задача от hr, как мини проверка на соответствие знаний, задается перед тем, как продолжить диалог). Собственно ответ 1 - 0.5 в 10 степени и ответ на 2 вопрос - 50%


      1. volodya_research Автор
        10.01.2025 23:08
        #27769964

        Спасибо за ваш комментарий! Вы абсолютно правы, и ваше решение идеально подходит, если заранее известно, что монетка честная.

        Однако монетка может быть деформированной, и вероятность выпадения орла или решки в таком случае может отличаться от 50%. Если про "честность" монетки ничего неизвестно, вероятность выпадения орла можно оценить на основе имеющихся данных. В вашей задаче оценка этой вероятности будет находиться в диапазоне от 76% до 100%, как я показал в статье.

        Можно утверждать следующее:

        "Имеющаяся серия испытаний (10 из 10 раз выпал орел) позволяет с 95%-й степенью уверенности предполагать, что вероятность выпадения орла отличается от 50%. Скорее всего (с вероятностью 95 %) она находится в диапазоне от 76% до 100%. Соответственно, есть основания ожидать, что при новом одиннадцатом броске монетка с большей вероятностью покажет орла, чем решку."


  1. kovserg
    10.01.2025 23:08
    #27768764

    А откуда вы взяли 1.98 ? Почему например не 2.13 ?


    1. volodya_research Автор
      10.01.2025 23:08
      #27769876

      Прошу прощения за предыдущую неточность. Я исправил значение коэффициента на более точное — 1.96, которое соответствует 95%-доверительному интервалу. Этот коэффициент обозначает количество стандартных отклонений от среднего значения, определяющих диапазон, в котором находится заданная доля данных (в данном случае 95 %). Вы можете прочитать об этом в статье Википедии про эмпирическое правило "68–95–99.7 rule".

      Известно, что для нормального распределения:
      — 95.5% данных лежит в промежутке [среднее ± 2 стандартных отклонения]
      — 99.7% данных лежит в промежутке [среднее ± 3 стандартных отклонения]

      Если мы ограничиваем 95% значений распределения, то это количество значений находятся в промежутке [среднее ± 1.96 стандартных отклонений] (см. отрывок в статье Википедии про Нормальное распределение).


  1. GospodinKolhoznik
    10.01.2025 23:08
    #27770136

    Оцените предсказательную силу осьминога.

    Предсказательная сила осьминога есть предсказательная масса на предсказательное ускорение осьминога. Что это за термин вообще? Он не математический. Это что то на философском. Формулировать математическую задачу с использованием размытых философских терминов это какой то позор!


    1. volodya_research Автор
      10.01.2025 23:08
      #27770600

      Предсказательная сила (англ. predictive power) — это термин, который используется в статистике и машинном обучении для обозначения способности алгоритма или метода делать точные предсказания.

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

      Хотя термин не имеет строгого математического определения, он активно используется в литературе, посвященной статистике и машинному обучению, например, в статье от Open Data Science про метрики машинного обучения, а также в статье о ROC-кривой в Википедии.


      1. GospodinKolhoznik
        10.01.2025 23:08
        #27771056

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

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

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


        1. volodya_research Автор
          10.01.2025 23:08
          #27771146

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

          На одном из собеседований я получил задачу именно с формулировкой "предсказательная сила". Под этим термином подразумевалась вероятность того, что предсказание осьминога окажется верным, что является интуитивно понятным. Если на собеседовании или в другом контексте вас просят оценить "предсказательную силу", но вам не кажется очевидным, что именно под этим термином подразумевается, я рекомендую задавать уточняющие вопросы. Это поможет избежать недоразумений и сосредоточиться на той интерпретации, которая важна для собеседующего.

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