Math Ajax

суббота, 9 января 2016 г.

Фишка споров о шансах, или нормативная теория пари на деньги

Every day there'd be a half dozen bets around about anything — elections and sports. Dollar bills were changing hands all the time. It was part of the ingrained way of life. You really believed this stuff.
Robert Schlaifer (цитируется по книге Theory that Would not Die)
Otherwise, to a Bayesian, you are not really being rational. If after we have our little chat, you still think your forecast is better than mine, you should be happy to bet on it, since you stand to make money. If you don’t, you should have taken my forecast and adopted it as your own.
Nate Silver, The Signal and The Noise

(note: это немного причёсанный текст моего старого выступления на московском lesswrong-митапе в июле 2014 года. Есть видео, но оно не совсем полное)

Шансы и вероятности. 

Все байесианцы делятся на две категории. Первая считает, что в теорему Байеса нужно подставлять три числа, а вторая — что два числа. Соответственно, первая крестится двумя перстами, а вторая — тремя.

Дело в том, что есть две формы теоремы Байеса: традиционная форма преобразует априорную вероятность в апостериорную вероятность, а альтернативная преобразует априорные шансы в апостериорные шансы.

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

Шансы — это альтернативный вид вероятностей.

Если вероятность чего-то X, то шансы того же будут X/(1-X). Можно говорить, что шансы "X к 1-X за что-то" или "1-X к X против чего-то".

По шансам тоже можно восстановить вероятность; поэтому никакой информации при таких преобразованиях не теряется.

Например, вероятность того, что монета выпадет решкой — одна вторая, или 0,5. Шансы того же самого — одна вторая к одной второй (то есть 0,5 : 0,5), а это то же самое, что один к одному (то есть 1 : 1), или просто 1.

Шансы не обязаны в сумме давать единицу. Сумма шансов вообще никому ничего не обязана, и складывать шансы довольно бесмысленно[1].

Шансы известны тем, что их постоянно неправильно понимают журналисты, они удобнее математически, они используются в машинном обучении [логистическая регрессия, например] и букмекерских конторах. Кроме того, посредством логарифма шансов хорошо обьяснять провалы калибровки.

Ещё примеры шансов

Рассмотрим, например, игральный кубик. Вероятность того, что он выпадет единицей — одна шестая (нам нужен один исход, а всего их шесть). Шансы того, что он выпадет единицей — один к пяти (на каждый благоприятный исход приходится пять неблагоприятных). Или, в десятичных дробях, это будет примерно 0,1667 и 0,2 соответственно.

Вероятность того, что кубик выпадет НЕ единицей — пять шестых, или 0,8333. Шансы того же самого — пять к одному, или просто 5.

Вероятности находятся на отрезке $[0; 1]$, а шансы находятся на луче $[0; +\infty)$. При этом единичной вероятности соответствуют бесконечные шансы, и поэтому я испытываю непреодолимое желание объять необъятное и, заключив бесконечность в квадратные скобки, заявить, что шансы находятся на отрезке $[0; +\infty]$.

Байесляндия и "всем выгодно!".

Споры на шоколадку.

Часть первая, в которой мы узнаем, при чём тут букмекерские конторы.

Возьмём классический спор на шоколадку. Допустим, я согласился поспорить на  шоколадку. Это означает, что я счёл пари один к одному выгодным. Это  означает, что с моей точки зрения вероятность моей правоты больше 50 %.

Очень важная идея состоит в том, что спорить можно не только один к одному. Например, можно поставить один арбуз против двух арбузов. Или двести рублей против пятидесяти рублей.

Как понять, выгоден ли тебе какой-нибудь спор?

Пусть, например, это спор A:B касательно X. То есть ты ставишь A бутылок шотландского виски, надеясь заработать B бутылок шотландского виски. Твоя настоящая вероятность — $P(X) = p$, и если преобразовать её в шансы, то выйдет $O(X) = \frac{p}{1-p}$. Нужно просто сравнить $O(X)$ с $A/B$: если ваши шансы больше, то спор выгоден, иначе нет.

Это правило не очень легко запомнить, поэтому удобно просто восстанавливать его по примеру.

Например, я на 66% уверен в том, что завтра не будет дождя. Это означает, что мои шансы дождя — 0.33/0.66 = 1/2 = 0.5, и спор 1 к 1 — с соотношением ставок 1 — будет невыгоден (мне только что предложили надеяться на то, что завтра будет дождь, но я же знаю, что дождя не будет, и что, я дурак что ли какой-то на такое соглашаться?), но если поменять сторону спора — тогда мои шансы будут 2 — то мне станет уже выгодно спорить на шоколадку.

На практике такие предложения обычно заканчиваются тем, что слова людей начинают расходиться с делом. Что-то такое:

— Просто позвони Васе.
— Неа, я не буду, он уже спит и не будет рад меня видеть.
— Он не ложится в это время и всегда рад помочь людям.
— Ммммм... Нет, я думаю, что он лёг. Лучше завтра.
— Ставлю двести рублей против твоих пятидесяти на то, что он не лёг.
— Ладно, ладно, я позвоню.
— Эй, а где мои деньги?!

И ты испытываешь смешанные чувства. С одной стороны, ты очень легко переубедил собеседника, и это хорошо. С другой стороны, денег ты не получил, и это обидно.

Байесляндия

Часть вторая, в которой мы узнаем, как такое должно было происходить по-хорошему.

Нэйт Сильвер приводит замечательную метафору. Есть далёкая страна Байесляндия, жители которой, как принято по обычаю, носят на себе таблички примерно такого вида:
ВРАГ ВОЛШЕБНИКОВ СКРЫВАЕТСЯ В АВСТРАЛИИ 5 %
В ЭТОЙ ДЕРЕВНЕ ЕСТЬ ХОТЯ БЫ ОДИН КУЗНЕЦ 70 %
НЕЛЬЗЯ СЪЕСТЬ ПАЧКУ ПЕЧЕНЬЯ "ЮБИЛЕЙНОЕ" ЗА ДЕСЯТЬ МИНУТ НЕ ЗАПИВАЯ 95 %
ЖИЗНЬ НА МАРСЕ 2 %
СТРОИТЕЛЬСТВО ЭТОГО МОСТА ЗАТЯНЕТСЯ ДО СЛЕДУЮЩЕЙ ВЕСНЫ 90 %

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

Например, если этот человек встретит человека, считающего, что съесть пачку Юбилейного — затея ерундовая, и даже после объяснений про то, что печенье очень сухое и его невозможно проглотить, считающего, что вероятность успеха — 20 %, то первый поставит 90 своих долларов против 10 долларов собеседника на то, что пачку печенья съесть невозможно, и оба будут довольными.

(почему  $90 \$$ против $10 \$$? Потому что шансы на "съесть нельзя" первого — 95/5 = 19, а второго — 80/20 = 4. Для того, чтобы найти соотношение ставок, которое выгодно обоим игрокам, нужно взять любое число посередине между 4 и 19. Например, 9 вполне годится.

Осталось только выбрать между "$9 \$$ к $1 \$$", "$90 \$$ к $10 \$$" и "$900 \$$ к $100 \$$". [2])

С точки зрения первого, он только что выиграл условные $0.95\cdot 10 \$ - 0.05\cdot 90 \$ = 5$ долларов. Он может проиграть 90 долларов, но этого скорее всего не случится; а 10 долларов на дороге не валяются. Вероятность неуспеха исчезающе мала, и поэтому пари выгодно.

С точки зрения второго, он только что выиграл условные $0.20\cdot 90 \$ - 0.80 \cdot 10 \$ = 10$ долларов. Да,  скорее всего, он проиграет 10 долларов, но ведь он может выиграть 90:  рискнуть 10, чтобы получить 90 с вероятностью 20% — отнюдь не самое худшее из возможных вложений. Если он будет руководствоваться этой стратегией и дальше, то в среднем он будет зарабатывать 10 долларов на каждом таком пари.

И после этого, разумеется, второй всё-таки пытается съесть пачку печенья "Юбилейное", страшно огребает и в итоге проигрывает 10 долларов.

Здесь важно понять, что дело было не в том, что один верил в прожорливость человека, а другой нет: они оба считали, что пачку печенья съесть скорее нельзя. Дело в том, что один верил в слабость прожорливости недостаточно сильно. Различия были не качественными, а количественными.

И да, количественные различия тоже важны. Вещи не делятся на абсолютно чёрные  и сверкающе белые: мир состоит из оттенков серого, и трудно быть искателем истины, не умея их различать.

------------
[1] На самом деле, иногда складывать шансы полезно: есть Odds Algorithm, но это уже оффтоп.

[2] Более изощрённый и/или изысканный подход изложен здесь.

вторник, 5 января 2016 г.

Расстояние Кульбака-Лейблера, политика и асимметричные альянсы

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

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

Давайте начнём.

Политические разногласия

Сенатор Марк Катон прежде всего известен за то, что он методично задалбывал своих собратьев-сенаторов фразой  "я считаю, что Карфаген должен быть разрушен", поскольку он считал, что все должны знать о его видении внешней политике Рима. Но у него были и другие хлёсткие реплики.

Например, в 168 году римляне забрали в заложники тысячу знатных греков, которые в итоге пробыли в плену 17 лет. Зная о политической смекалке греков и об эллинофилии римлян, нетрудно догадаться о том, что греки быстро нашли себе союзников и совершенно не стеснялись использовать своё влияние для того, чтобы вернуться домой. Среди греков особенно стоит отметить Полибия, будущего автора "Всеобщей Истории", который стал достаточно важной фигурой на политической сцене. Но слово Катона было весомее, и он голосовал против каждый раз, когда до этого вопроса доходило дело.

Лишь через 17 лет расстановка сил изменилась настолько, что Катон был вынужден согласиться. Он сказал: «Неужели у нас нет других более важных дел, чем сидеть целый день и обсуждать, где кучка старых греков ляжет в гроб — здесь или в Греции?».

Что получается в итоге? Катон имеет определённое мнение по поводу Карфагена и считает, что это вопрос жизни или смерти Рима. С другой стороны, он не хочет отпускать греков-заложников, но при этом (предположительно) не видит в этом ничего принципиального.

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

В то же время, этот гипотетический второй сенатор (назовём его Клавдий) может с негодованием отвергнуть помощь Марка Катона: один из греков есть ни кто иной, как Полибий — философ, автор трактата о военной тактике и человек, старающийся извлечь из истории уроки. И то, что Марк считает это ненужной ерундой лишь подчёркивает всю бездну между ними.

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

Все это может навести на следующие мысли:

1) Pick your battles: не все разногласия одинаково важны. Прежде чем фокусироваться на каком-то разногласии, стоит вспомнить консеквенциализм и подумать о том, каким образом ваше разногласие проявляется в реальности. Нужно спуститься на уровень фактов, предсказаний и наилучших действий, а не оставаться рассуждать о метапозициях и мутных метаценностных расхождениях без правдоподобного механизма проявления в мире.

2) Это ещё одна иллюстрация того, что мир состоит не из чёрного и белого, а из оттенков серого. Мнение людей может совпадать на грубых бинарных вопросах "верно ли, что вероятность икса меньше 50%?", но при этом радикально расходиться в более точной оценке: 10% или 0.1%. И во многих контекстах это должно быть важным.

3) Из того, что Вася считает что-то ерундой (или само собой разумеющимся), вовсе не следует, что все остальные люди тоже будут так считать.

Расстояние между распределениями вероятностей

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

Эту ситуацию можно описать математически, если сделать одно — возможно, нереалистичное — допущение.Я буду считать, что каждый политик может не только сказать, что $X$ важнее $Y$, но и назвать, насколько важен $X$ (в процентах). Полученные распределения важности очень похожи на распределения вероятностей, и поэтому их можно анализировать также.

Поговорим теперь про распределения вероятностей.

* * *

Стандартная постановка задачи из теории информации звучит так. Случаются различные события, причём событие $x$ свершается с вероятностью $p(x)$. Информацию о том, какое именно событие случилось, нужно закодировать нулями или единицами и передать по каналу связи, причём чем экономнее, тем лучше.

Например: ты оператор телеграфа, тебе нужно передать в соседний город последовательность звуков, которую произнёс клиент. Тут события — это буквы английского алфавита, и буква $s$ возникает с частотой $p(s)$.

Мы кодируем события при помощи двоичных слов: если случилось событие $A$, то по каналу отправляется $C(A)$, последовательность из нулей и единиц длины $|C(A)|$ бит.

Нужно кодировать события таким образом, чтобы минимизировать загруженность канала связи. Загруженность канала — это суммарное число бит, которые по нему отправили. Минимизировать суммарную длину — примерно то же самое, что и минимизировать среднюю длину сообщения.

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

Например, если возможны лишь четыре события, — $A, B, C$ и $D$ — и мы кодируем их как $00$, $01$, $10$ и $11$ соответственно, то мы всегда будем посылать ровно два бита. Однако, если $A$ случается в $50%$ случаях, $B$ — в $25%$, а $C$ и $D$ — в $12,5%$, то лучше кодировать их как $0$, $10$, $110$ и $111$: тогда с вероятностью $50%$ случится $A$ и длина сообщения будет $1$ бит, с вероятностью $25%$ случится $B$, на которое мы потратим $2$ бита, и в остальных $25%$ случаях происходит $C$ или $D$, для описания которых нужно 3 бита. Получается, что в среднем сообщение состоит из $1 \cdot 0.5 + 2 \cdot 0.25 + 3 \cdot 0.25 = 1.75$ бит.

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

Однако, что будет, если мы считаем, что события приходят из распределения $q$ (и строим оптимальное кодирование под $q$, со словами, длины которых рассчитаны так, чтобы короткие слова встречались часто, а длинные редко), но на самом деле они приходят из другого распределения $p$?

Можно вернуться к предыдущему примеру и посмотреть, что случится, если мы перепутали события $A, B, C, D$ местами и на самом деле $A$ и $B$ случаются в $12,5%$ случаях, $C$ — в $25%$, а $D$ — в $50%$. Тогда с вероятностью $50%$ случается $D$, и мы отправляем $3$ бита, и так далее. Получается, что в среднем сообщение состоит из $3 \cdot 0.5 + 3 \cdot 0.25 + 2 \cdot 0.125 + 1 \cdot 0.125 = 2.625$ бит (вместо $1.75$, на которые мы надеялись).

Выходит, что «в действительности» средняя длина сообщения будет больше. Это верно всегда. Число бит, которое «теряется» при таком неоптимальном кодировании — и есть расстояние Кульбака-Лейблера от $p$ до $q$.

Важно сказать, что $p$ и $q$ участвуют здесь неравноправно. Дело в том, что $q$ отвечает за наши предсказания и символизирует карту, а $p$ генерирует результаты экспериментов и символизирует местность. Реальность — это главный судья наших убеждений.

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

Как следствие, расстояние от $p$ до $q$ может быть совсем не равно расстоянию от $q$ до $p$. Более того, можно привести пример, когда расстояние в одну сторону ничтожно маленькое, а расстояние в другую сторону бесконечно большое.

В терминах передачи информации: дело в том, что событие $X$, исчезающе редкое с точки зрения $q$ может быть частым с точки зрения $p$. Если строить оптимальное кодирование под $q$, то описание $X$ будет очень длинным (но редким, так что в среднем получается коротко). Из-за этого средняя длина сообщения рискует чудовищно разбухнуть, если в действительности $X$ встречается часто (поэтому расстояние в одну сторону бесконечно). Это рассуждение может не работать в обратную сторону, если все редкие события с точки зрения $p$ остаются редкими с точки зрения $q$ (поэтому расстояние в другую сторону может быть ничтожным).

* * *

Теперь изложим  историю Марка Катона на этом языке.

Марк Катон считает, что внешняя политика Рима важна почти на 100%, а важность кучки дряхлых греков можно считать нулевой, ошибившись разве что в сотом знаке после запятой. Клавдий же считает эти вопросы одинаково важными. Что будет, если собрать числа и подсчитать расстояние между их мнениями?

Клавдий считает, что Марк бесконечно ужасен (и в этом нет ничего удивительного, это согласуется с интуицией). С другой стороны, Марк считает, что степень ужасности Клавдия равна примерно $\ln 2 \approx 0.69$ битам. Это число маленькое, но всё же не ничтожно. Это означает, что Марк не совсем одобряет Клавдия, и не слишком охотно вступит с ним в союз. Это отличается от изначальной истории. Почему это случилось?

Эти $0.69$ бит расхождения возникают из-за того, что внешняя политика Рима важна для Марка на 100%, а для Клавдия лишь на 50% (разница в два раза, от которой и берётся логарифм). Иными словами, это расхождение возникает из-за того, что вероятности должны быть нормированными; из-за того, что положить интерес в чашку под названием "заложники" означает убрать интерес из чашки под названием "война с Карфагеном".

Для того, чтобы получить пример с нулём и бесконечностью, нужно взять двух сенаторов, озабоченных судьбой Рима на 100%, но так, чтобы первый беспокоился судьбой греков в масштабе пятой точки после запятой, а второй - в масштабе пятисотой. Про конфликт на этой почве очень трудно сочинить правдоподобную драматическую историю.

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

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

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

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

С другой стороны, история Васи и Пети не играет на каких-то глубинных струнах. Я не могу перенести её назад во времени раньше Блеза Паскаля, и не могу пересказать её, заменив вероятности чем-то менее современным и более естественным, Для того, чтобы сыграло расхождение между $10^{-5}$ и $10^{-500}$, эти числа должны очень сильно беспокоить людей. Но ситуация, когда человека хоть как-то волнует сценарий, вероятность которого исчезающе мала, кажется очень контринтуитивной. Чтобы эта крохотные шансы хоть как-то проявили себя, нужны какие-то ментальные костыли. Например, утилитаризм, пробабилизм или какие-то другие идеи, которые — мягко говоря — не слишком часто встречались в доисторической саванне.

Видимо, дивергенция Кульбака-Лейблера — плохая модель для (привычных?) человеческих политических альянсов. Поскольку one man's modus ponens is another man's modus tollens, то предположения можно сделать два:

Первое предположение скучное: просто модель неподходящая, мы вышли за рамки её применимости. Аналогия натянута, все попытки извлечь вероятности порядка $10^{-500}$ изначально обречены на провал из-за плохой откалиброванности и ошибок измерений; да и вообще, изначально всё нужно мерять в ожидаемой полезности, а не в какой-то странной ереси.

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

Приложение 1, математическое

Про оптимальное кодирование: если $x$ случается с вероятностью $p(x)$, и нужно минимизировать среднюю длину сообщения ($-\sum_x p(x) \log p(x)$), то оптимальный ответ на эту задачу — каждый $x$ кодировать каким-то словом длины $-\log p(x)$ (это всегда возможно). Средняя длина сообщения тогда будет равна энтропии распределения $p$: $-\sum_x p(x) \log p(x)$.

Про расстояние Кульбака-Лейблера: если мы строим кодирование под $q$, но в реальности случается $p$, то тогда средняя длина сообщения будет равна
\[
-\sum_x p(x) \log q(x)
\]
Разница в средней длине относителньо оптимального кодирования будет равна:
\[
-\sum_x p(x) \log q(x) - (-\sum_x p(x) \log p(x) ) = -\sum_x p(x) \log \frac{q(x)}{p(x)} = D(P || Q)
\]
А это как раз и есть дивергенция Кульбака Лейблера.

Про пример с нулём и бесконечностью:  пусть $p(A) = 1 - \frac{1}{k}, p(B) = \frac{1}{k}$, а $q(A) = 1 - e^{-k^2}, q(B) = e^{-k^2}$. Тогда $D(Q || P) \approx 0$, $D(P || Q) \approx \infty$,и уже при $k = 10$ между этими числами есть разница примерно в сто раз.