Датчики дождя и сложные решения простых задач
Саша Якунин рассказал о задачке на теорию вероятностей:
Есть два сенсора дождя, работающие с 75% точностью.
Оба говорят, что идёт дождь.
Какова вероятность того, что дождь действительно идёт?
К нам в гости прилетел dfyz и я рассказал ему о задачке. Сели решать, вспоминать теорию вероятностей.
Для начала решили определить, а независимые ли вообще датчики? Есть основания полагать, что нет: если, скажем, датчик основывается на величине влажности (относительной, абсолютной), и правильно откалиброван, то два датчика будут давать ответы совершенно синхронно, одинаковые. В этом случае совершенно неважно, сколько датчиков в системе, один или много, и можно применять формулу для случая с одним датчиком.
Дальше предположили, что датчики выдают результаты и ошибаются независимо (например, случайным образом в 25% случаев ответ меняется на противоположный).
Какой подход использовать дальше?
1. Один вариант - расписать вероятность по формуле Байеса. Сразу становится ясно, что для ответа нужно знать априорную вероятность дождя: действительно, если дождь идёт всегда, то вы находитесь в Сиэттле и ваш сенсор дождя ошибается только если говорит, что дождя нет.
А если вы находитесь в Сахаре, но напротив, датчик будет врать в тех случаях, когда будет утверждать, что идёт дождь.
Это вообще важное интуитивное соображение: типы ошибок (false positive, false negative) распределены неравномерно, кроме возможно единственного частного случая с априорной вероятностью дождя 50%.
Дальше всё просто, остается только расписать полную вероятность в знаменателе, и получаем ответ.
2. Второй вараинт: интуитивное решение. Для двух датчиков, оба из которых говорят "идёт дождь" расписываем 4 варианта возможных (или невозможных) событий:
A: 1 и 2 говорят правду
B: 1 лжёт, 2 говорит правду
C: 1 говорит правду, 2 лжёт
D: оба лгут
События B & C неосуществимы: они означали бы, что дождь одновременно идёт и не идёт, что невозможно.
"Вероятность" события A: PA = 0.75 * 0.75 * априорную вероятность дождя.
"Вероятность" события D: PD = 0.25 * 0.25 * (1 - априорная вероятность дождя).
A и D покрывают пространство осуществимых событий полностью, сумма их вероятностей должна быть равна 1, поэтому для получения ответа нормируем поделив на (PA + PD):
X = PA / (PA + PD).
Для случая с произвольным числом датчиков оба решения обобщаются одинаковым образом, получающиеся формулы совпадают.
Для проверки sanity прогнали ответ черези симуляцию, сравнили результаты вычислений с симуляцией "сломанных датчиков", всё совпало.
Код решения для задачи с разными априорными вероятностями дождя и разным количеством сенсоров
Есть два сенсора дождя, работающие с 75% точностью.
Оба говорят, что идёт дождь.
Какова вероятность того, что дождь действительно идёт?
К нам в гости прилетел dfyz и я рассказал ему о задачке. Сели решать, вспоминать теорию вероятностей.
Для начала решили определить, а независимые ли вообще датчики? Есть основания полагать, что нет: если, скажем, датчик основывается на величине влажности (относительной, абсолютной), и правильно откалиброван, то два датчика будут давать ответы совершенно синхронно, одинаковые. В этом случае совершенно неважно, сколько датчиков в системе, один или много, и можно применять формулу для случая с одним датчиком.
Дальше предположили, что датчики выдают результаты и ошибаются независимо (например, случайным образом в 25% случаев ответ меняется на противоположный).
Какой подход использовать дальше?
1. Один вариант - расписать вероятность по формуле Байеса. Сразу становится ясно, что для ответа нужно знать априорную вероятность дождя: действительно, если дождь идёт всегда, то вы находитесь в Сиэттле и ваш сенсор дождя ошибается только если говорит, что дождя нет.
А если вы находитесь в Сахаре, но напротив, датчик будет врать в тех случаях, когда будет утверждать, что идёт дождь.
Это вообще важное интуитивное соображение: типы ошибок (false positive, false negative) распределены неравномерно, кроме возможно единственного частного случая с априорной вероятностью дождя 50%.
Дальше всё просто, остается только расписать полную вероятность в знаменателе, и получаем ответ.
2. Второй вараинт: интуитивное решение. Для двух датчиков, оба из которых говорят "идёт дождь" расписываем 4 варианта возможных (или невозможных) событий:
A: 1 и 2 говорят правду
B: 1 лжёт, 2 говорит правду
C: 1 говорит правду, 2 лжёт
D: оба лгут
События B & C неосуществимы: они означали бы, что дождь одновременно идёт и не идёт, что невозможно.
"Вероятность" события A: PA = 0.75 * 0.75 * априорную вероятность дождя.
"Вероятность" события D: PD = 0.25 * 0.25 * (1 - априорная вероятность дождя).
A и D покрывают пространство осуществимых событий полностью, сумма их вероятностей должна быть равна 1, поэтому для получения ответа нормируем поделив на (PA + PD):
X = PA / (PA + PD).
Для случая с произвольным числом датчиков оба решения обобщаются одинаковым образом, получающиеся формулы совпадают.
Для проверки sanity прогнали ответ черези симуляцию, сравнили результаты вычислений с симуляцией "сломанных датчиков", всё совпало.
Код решения для задачи с разными априорными вероятностями дождя и разным количеством сенсоров