Math Ajax

вторник, 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$ между этими числами есть разница примерно в сто раз.


Комментариев нет:

Отправить комментарий