«Парадокс» Монти Хола или основы машинного обучения

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

Большинству может показаться, что нет никакой разницы. Но давайте копнем поглубже и разберемся. Обратимся к теории вероятности, чтобы решить задачку, и заодно докажем, что никакого парадокса тут нет. Для этого нам понадобиться немного упрощенной теории:

1. Бывают дискретные случайные величины с конечным или счетным набором исходов. Каждому из своих исходов они присваивают неотрицательную вероятность, и вероятности исходов в сумме дают единицу. Классический пример - бросание кубика;
2. Совместная вероятность – это вероятность одновременного наступления двух событий p(x,y). Также две случайные величины называются независимыми, если p(x,y)=p(x)*p(y). И чтобы получить обратно из совместной вероятности вероятность того или иного исхода одной из случайных величин, нужно просуммировать по другой;
3. Условная вероятность – вероятность наступления одного события, если известно, что произошло другое: p(x|y)=p(x,y)/p(y)
4. Условная независимость: x и y условно независимы при условии z, если p(x,y|z)=p(x|z)*p(y|z)

Вернемся к игре. Пронумеруем двери слева направо – 1,2,3. Рассмотрим события наличия автомобиля за тремя дверями, обозначив их через x1,x2,x3. Изначально их вероятности равны 1/3. Если бы ведущий просто открыл одну из дверей до вашего выбора, то две другие двери остались бы равновероятными: p( x1|x3=0)=p(x2|x3=0)=½

Но все намного сложнее. Ведь ведущий знает, где спрятан приз, да и открывает не случайную дверь из проигрышных, а одну из невыбранных вами. Поэтому события «какую дверь из двух с козами открыть ведущему» и «находится ли автомобиль за выбранной вами дверью» становятся зависимыми. Давайте обозначим выбор ведущего за y и также будем считать, что вы выбрали первую дверь. Тогда совместные вероятности разложатся так:

p(x1=1,y=2)=1/6

p(x1=1,y=3)=1/6

p(x2=1,y=2)=0

p(x2=1,y=3)=1/3

p(x3=1,y=2)=1/3

p(x3=1,y=3)=0

Получается, что вероятность события «вы с первого раза выбрали выигрышную дверь» равна 1/3, когда же вероятность «автомобиль находится за оставшейся закрытой дверью» будет 2/3.

Значит, парадокса действительно нет, и выгоднее изменить свое решение. Давайте проверим полученные решения другим способом. Для этого совместим пункты (2) и (3) :

p(x,y)=p(x|y)p(y)=p(y|x)p(x)

Мы получили главную формулу всего машинного обучения - формулу или теорему Байеса. Посчитаем вариантность теперь по ней:

Получили те же вероятности. Это наглядно демонстрирует удобство использования теоремы Байеса. Ведь классическая теория вероятности рассуждает о том, как оперировать вероятностями повторяющихся событий, когда можно устремить число экспериментов к бесконечности. Однако в жизни часто возникает необходимость подсчитать вероятность событий, до того как они наступят или когда их количество строго ограниченно. Теорема же с помощью априорной вероятности, вероятности данных и правдоподобия позволяет нам узнать апостериорную вероятность. А зачем она нам нужна? Если вам дали и вопрос, и ответ на него, то с ее помощью можно научиться предсказывать ответы на последующие подобные вопросы. Именно такое предсказание и является основой машинного обучения. Хорошим примером предсказания является подбор функции, проходящей максимально близко от заданных точек, которая в последствии сможет выдавать значения и для другой базы данных.

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