Rationality: From AI to Zombies / Рациональность: от ИИ до Зомби: Conditional Independence, and Naive Bayes

Ранее я называл общей информацией I(X;Y) двух переменных X и Y разницу между энтропией составного распределения H(X,Y) и суммарной энтропией частных распределений H(X) + H(Y).

sepremento 12.10.19 в 07:52

Я давал пример переменной X с восемью равновероятными состояниями X1...X8 при отсутствии каких-либо свидетельств и переменной Y с четырьмя равновероятными состояниями Y1...Y4 при отсутствии каких-либо свидетельств. Затем, если вычислить энтропии частных распределений H(X) и H(Y), можно показать, что у X 3 бита, а у Y 2 бита энтропии.

sepremento 12.10.19 в 07:56

Однако нам известно, что X и Y либо одновременно чётные, либо одновременно нечётные. Таким образом, совместное распределение (X,Y) содержит 16 равновероятных состояний, и энтропия этого распределения равна 4 битам. Это приводит к недостатку энтропии в 1 бит по сравнению с 5 битами X и Y, будь они независимыми. Этот недостаток энтропии --- общая информация: информация, которую X сообщает нам об Y, и наоборот. Это уменьшает нашу неопределенность в знании одной переменной при получении знания о другой.

sepremento 12.10.19 в 08:01

Но предположим, что существует переменная Z с состояниями "чётно" и "нечётно", с идеальной корреляцией с четностью распределения (X,Y). Иными словами, Z --- это просто вопрос: "являются ли X и Y чётными или нечётными?"

sepremento 12.10.19 в 08:03

Если у нас нет свидетельств об X и Y, то Z необходимо имеет 1 бит энтропии, с учетом известной информации. Есть один бит общей информации между Z и X, а также один бит общей информации между Z и Y. И, как уже было сказано, один бит общей информации между X и Y. Итак, сколько энтропии у системы (X, Y, Z)? Можно наивно полагать, что

sepremento 13.10.19 в 17:27

H(X,Y,Z) = H(X) + H(Y) + H(Z) − I(X;Z) − I(Z;Y) − I(X;Y) ,

sepremento 14.10.19 в 17:32

но, оказывается, это не так.

sepremento 14.10.19 в 17:32

Составная система (X, Y, Z) обладает 16 возможными состояниями, поскольку Z это лишь вопрос "Являются X и Y четными или нечетными?", поэтому H(X,Y,Z) = 4 бита.Но если посчитать согласно вышеприведённой формуле, получится

sepremento 14.10.19 в 17:34

(3 + 2 + 1 − 1 − 1 − 1) бит = 3 бита = Неверно!

sepremento 14.10.19 в 17:34

Почему? Потому что, если есть общая информация между X и Z, а также общая информация между Z и Y, они могут содержать ту же общую информацию, которая появилась бы при подсчёте между X и Y. Например, в нашем случае, знание, что X - четно приводит к знанию, что Z - четно, а это в свою очередь говорит нам, что Y - четно, но это та же самая информация, которую нам даёт X о Y. Мы считаем одно и то же два раза, а потому энтропии оказывается слишком мало.

sepremento 14.10.19 в 17:39

Правильная формула такова:

sepremento 17.10.19 в 16:02

H(X,Y,Z) = H(X) + H(Y) + H(Z) − I(X;Z) − I(Z;Y) − I(X;Y|Z).

sepremento 17.10.19 в 16:02

Последнее слагаемое I(X;Y|Z) означает "информацию, которую X несёт об Y, при условии, что Z известно". В нашем случае X не несёт какой-либо информации об Y, при условии, что Z известно, поэтому слагаемое равно нулю, а уравнение даёт правильный результат. Ну вот, разве не прекрасно?

sepremento 17.10.19 в 16:04

"Нет," - правильно ответите вы, - "ведь ты не сказал, как вычислить слагаемое I(X;Y|Z), а лишь в словах описал, что оно должно быть равно нулю".

sepremento 17.10.19 в 16:06

Мы рассчитываем I(X;Y|Z) ровно так, как можно ожидать. Мы знаем, что I(X;Y) = H(X) + H(Y) − H(X,Y), а поэтому

sepremento 17.10.19 в 16:07

I(X;Y|Z) = H(X|Z) + H(Y|Z) − H(X,Y|Z).

sepremento 17.10.19 в 16:07

А теперь вам должно быть интересно, как вычислить условную энтропию? Исходная формула для энтропии выглядит так:

sepremento 17.10.19 в 16:07

H(S) = Σi−P(Si) × log 2(P(Si)).

sepremento 17.10.19 в 16:07

Если нам становится известен факт Z0, оставшаяся неопределенность относительно S окажется равна

sepremento 17.10.19 в 16:08

H(S|Z0) = Σi−P(Si|Z0)log2(P(Si|Z0)).

sepremento 17.10.19 в 16:09

А значит, если нам становится известно что-либо о Z, то в среднем мы ожидаем вот такой неопределенности после этого знания:

sepremento 17.10.19 в 16:10

H(S|Z) = Σj left (opening) parenthesisP(Zj)Σi−P(Si|Zj)log2(P(Si|Zj))right (closing) parenthesis.

sepremento 17.10.19 в 16:10

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

sepremento 17.10.19 в 16:11

Существует огромное количество вспомогательных теорем вроде

sepremento 17.10.19 в 16:12

H(X|Y) = H(X,Y) − H(Y)

sepremento 17.10.19 в 16:12

и

sepremento 17.10.19 в 16:12

если I(X;Z) = 0 и I(Y;X|Z) = 0, то I(X;Y) = 0,

sepremento 17.10.19 в 16:12

но я не стану вдаваться в подробности.

sepremento 17.10.19 в 16:12

"Но," --- спросите вы, --- "какое отношение это имеет к природе слов и их скрытой байесианской структуре?"

sepremento 17.10.19 в 16:13

Я несказанно рад вашему вопросу, ведь я собирался рассказать об этом, несмотря ни на что. Но вначале ещё несколько моментов.

sepremento 17.10.19 в 16:14

Вы конечно помните, что есть связь между общей информацией и Байесовым свидетельством. Общая информация положительна тогда и только тогда, когда вероятность хотя бы одного составного события P(x,y) не равна произведению вероятностей событий по отдельности P(x)P(y). Это, в свою очередь, эквивалентно наличию свидетельства между x и y.

sepremento 17.10.19 в 16:17

I(X;Y) > 0 =>
P(x,y) != P(x)*P(y)
P(x,y) / P(y) != P(x)
P(x|y) != P(x)

При условии известного Z, уравнения можно переписать как:

sepremento 17.10.19 в 16:19

I(X;Y | Z) > 0 =>
P(x,y|z) != P(x|z)*P(y|z)
P(x,y|z) / P(y|z) != P(x|z)
(P(x,y,z) / P(z)) / (P(y, z) / P(z)) != P(x|z)
P(x,y,z) / P(y,z) != P(x|z)
P(x|y,z) != P(x|z)

Последняя строчка обозначает: "Даже при известном Z, знание Y меняет наши представления об X"

sepremento 17.10.19 в 16:20

И наоборот, в нашем примере знание, что Z "четно" или "нечетно" закрывает X от Y. Поэтому, если мы знаем, что Z "четно", то информация Y = Y4 не даёт нам представления, в каком именно состоянии находится X -- X2, X4, X6, или X8. Также, если мы знаем, что Z "нечетно", то информация X = X5 не несёт информации, находится ли Y в состоянии Y1 или Y3. Знание Z сделало X и Y условно независимыми.

sepremento 17.10.19 в 16:23

Условная независимость это очень важная концепция в теории вероятностей -- ради примера скажу, что без условной вероятности у нашей Вселенной не было бы структуры.

sepremento 17.10.19 в 16:24

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

sepremento 17.10.19 в 16:26

Пусть дано пять переменных U, V, W, X и Y. Для каждой пары этих переменных, одна является свидетельством о другой. Так, например, если вы выберете U и W, то знание U = U1 изменит ваши убеждения о вероятности W = W1.

sepremento 19.10.19 в 17:05

Что это? Нераспутываемый клубок причин и следствий? Сумасшествие свидетельств? Не обязательно.

sepremento 19.10.19 в 17:06

Возможно, что U -- "пользуется разговорной речью", V -- "две руки и десять цифр", W - "носит одежду", X - "уязвим к болиголову", а Y - "цвет крови красный". Теперь, если вы встретите в повседневной жизни нечто, что может быть яблоком, а может быть и камнем и узнаете, что оно говорит по китайски, вы обязаны присвоить большую вероятность гипотезе, что оно носит одежду. А если вы узнаете, что это нельзя отравить болиголовом, вы присвоите меньшую вероятность гипотезе красной крови.

sepremento 19.10.19 в 17:09

Некоторые из подобных правил строже других. Есть Фред, который потерял палец во время извержения вулкана, есть малыш Барни, который пока не умеет говорить, есть IRC бот Ирвин, который пользуется речью, но не обладает кровью. Знание о цвете крови, полученное из факта обладания разговорной речью, не скроется от нас, если мы узнаем, что нечто не носит одежду. Тот, кто не носит одежду и при этом разговаривает может оказаться нудисткой Нелли.

sepremento 19.10.19 в 17:14

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

sepremento 19.10.19 в 17:17

Как показывает случай с нудисткой Нелли, зависимости не исчезают по мере узнавания одной переменной. Ну так что, это всё-таки нераспутываемый клубок причин и следствий?

sepremento 19.10.19 в 17:19

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

sepremento 19.10.19 в 17:20

P(U|V,W,X,Y,Z) = P(U|Z)
P(V|U,W,X,Y,Z) = P(V|Z)
P(W|U,V,X,Y,Z) = P(W|Z)
⋮
Возможно, при условии, что некоторый предмет является "человеком", вероятности, что он говорит, носит одежду и обладает стандартным количеством пальцев являются независимыми. У Фреда нет пальца -- но он точно так же может быть нудистом, как и другой человек. Нелли никогда не носит одежду, но это знание не уменьшает вероятности владения ею разговорной речью. А малыш Барни ещё не говорит, но при этом имеет все конечности.

sepremento 19.10.19 в 17:23

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

sepremento 19.10.19 в 17:26

Любое наблюдение U, V, W, X или Y лишь является свидетельством центрального класса Z, а мы используем апостериорное распределение Z для необходимых предсказаний ненаблюдаемых переменных U, V, W, X или Y

sepremento 20.10.19 в 16:26

Знакомо звучит? А должно бы:

sepremento 20.10.19 в 16:26

картинка

sepremento 20.10.19 в 16:27

Сеть 2

sepremento 20.10.19 в 16:27

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

sepremento 20.10.19 в 16:31