Байесовский сетевой вывод

В этой статье я буду использовать распространение убеждений (BP) с некоторыми примерами данных. Я предполагаю, что вы уже знаете о байесовских сетях (BN). В этом посте объясняется, как рассчитать убеждения различных переменных в BN, которые помогают разуму.

Распространение веры

Я создал репозиторий с кодом для BP на GitHub, который буду использовать для объяснения алгоритма.

Для начала представьте, что у нас есть поли-дерево, которое представляет собой граф без петель. Например, график, изображенный на следующей иллюстрации. У нас есть 4 переменных: «Дождь», «Спринклер», «Холмс» и «Ватсон» с направленными краями: «Дождь» в «Холмс», «Дождь» в «Ватсон» и «Спринклер» в «Холмс». Байесовская сеть моделирует историю о том, что Холмс и Ватсон были соседями. Однажды утром Холмс выходит из дома и видит, что трава мокрая. Либо шел дождь, либо он забыл выключить ороситель. Поэтому он идет к своему соседу Ватсону, чтобы посмотреть, не мокрая ли у него трава. Поскольку он видит, что он действительно мокрый, он совершенно уверен, что он не забыл о разбрызгивателе, но что шел дождь. Таким образом, информация перетекала от Watson к спринклерной машине. Этот поток информации моделируется с помощью BP в BN.

В BP мы позволяем переменным разговаривать друг с другом, чтобы обмениваться мнениями друг о друге. Есть 2 вида сообщений: сообщения от родителей детям и сообщения от детей родителям. Всего нам нужно использовать только 5 формул, чтобы сделать АД. В своих объяснениях я буду использовать разные имена для определенных формул и переменных, так как я нашел некоторые источники, вводящие в заблуждение.

1. Вероятность

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

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

Если у переменной нет дочерних элементов, поскольку она является листовым узлом в графе и не наблюдается, ее вектор вероятности будет единичным вектором, все единицы для всех возможных значений, например так как вначале мы не наблюдали траву Холмса, мы установили ее вектор вероятности равным [1, 1] для «не мокрый» и «мокрый» соответственно.

В коде Python (numpy) это выглядит так.

def likelihood(self):
    incoming_children_messages = np.array([
        c.message_to_parent(self) for c in self.children
    ])
    return incoming_children_messages.prod(axis=0)

2. Приоры

Приоры - это вероятности определенных событий, которые уже известны вначале, например идет дождь с вероятностью 20%. Если априорные значения неизвестны, его вычисляет следующая формула. Это немного сложнее, но я попробую. Априор дает вам безусловную вероятность соответствующей переменной. Следовательно, нам нужно включить и условный.

Условные вероятности также приведены в нашем примере. В формуле этому соответствует «P (X | W)». Более того, нам нужно использовать входящие сообщения от всех родителей, что является «ϕ» в формуле. Индекс показывает направление сообщения - от родительской «K» к текущей переменной «X». Эти две части (условная вероятность и сообщение от родителей) используются, поскольку обе дают информацию о вероятности переменных. С одной стороны, мы видим вероятность, исходя из значений некоторых родителей, с другой стороны, мы видим сообщения этих родителей. Без наблюдения эти сообщения соответствуют старшим родителям. Следовательно, здесь вычисляются маржинальные значения «X» и избавляются от условных переменных.

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

def priors(self):
     parents_messages = [
         p.message_to_child(self) for p in self.parents
     ]
     return reduce(np.dot, [self.m.transpose()]+parents_messages)

3. Вера

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

Мы берем вероятности, которые знали заранее, и вводим новые знания, полученные от детей. Таким образом, мы формируем новое представление о нашей переменной. Если у переменной есть и родители, и дети, убеждение представляет собой обновленную вероятность (апостериорную), включающую информацию снизу и сверху. Таким образом, каждое входящее сообщение учитывается. «Α» - нормализующая константа, так как произведение вероятности и априорной суммы может быть больше 1. Это сокращенная форма для деления с суммой всех возможных состояний переменных.

В этом фрагменте Python нормализующая часть становится более ясной.

def belief(self):
     unnormalized = self.likelihood() * self.priors()
     normalized = unnormalized/unnormalized.sum()
     return normalized

4. Обращение к родителям

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

Эта формула довольно запутана, но ее лучше понять, глядя на некоторый код Python. В общем, мы исключаем K из P (X | U), в то время как X - отправитель (дети), K - получатель (родитель), а U - все родители X, включая K. Если представить себе таблицу условной вероятности для X, для каждой записи мы берем соответствующие активации родителей и умножаем соответствующие входящие сообщения ϕ без самого K. Затем мы умножаем это значение на вероятность X. В конце мы суммируем все значения с одинаковым значением для K, и остается вектор, являющийся сообщением от X к K.

Таким образом, сообщение для родителя учитывает все входящие сообщения, независимо от того, были ли они отправлены детьми или родителями (за исключением того, что родитель получает сообщение), и учитывает вероятности с учетом значений определенных родителей. Следовательно, настройка переменной с высокой вероятностью пересылает входящие сообщения легче, чем с низкой вероятностью. Входящее сообщение оценивается по условной вероятности настройки этого сообщения.

Я надеюсь, что код Python немного проясняет это.

def message_to_parent(self, parent):
    likelihood = self.likelihood()
    parents_priors = np.array([
        p.message_to_child(self) 
            for p in self.parents if p != parent
    ])
    parent_i = self.parents.index(parent)

    stack = np.vstack([
        np.dot(
            self.m.take(r, axis=parent_i).transpose(),    
            parents_priors.prod(axis=0)
        ) 
        for r in range(parent.cardinality)
    ])
    return np.dot(stack, likelihood)

или на примере Холмса:

message = np.zeros(rain.cardinality)
for r in rain:
  for s in sprinkler:
    for h in holmes:
      message[r] = probas[r, s, h] \
                   * sprinkler_message[s] \
                   * likelihood[h]

5. Обращение к детям

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

Мы считаем, что эта формула называется Каппа с индексом, указывающим нам направление сообщения (от X до K).

Если мы посмотрим на формулу убеждения, мы увидим, что эта формула является произведением вероятности и априорной вероятности. Однако вероятность - это результат всех входящих сообщений. Следовательно, убеждение, разделенное на входящее сообщение от K, приводит к произведению всех входящих сообщений - за исключением того, на которое мы разделили - и предыдущего. Таким образом, мы можем объяснить равенство двух способов вычисления Каппы. Интуиция, стоящая за сообщением для детей, аналогична сообщению для родителей. Вы учитываете все входящие сообщения (так что учитывайте всю информацию, которую можете получить) и отправляете агрегирование следующему узлу.

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

def message_to_child(self, child):
    children_messages = []
    for c in self.children:
        if c != child:
            children_messages.append(c.message_to_parent(self))
    if len(children_messages) > 0:
        unnormalized = (children_messages * self.get_priors())
        unnormalized = unnormalized.prod(axis=0)
        message = unnormalized/unnormalized.sum()
        return message
    return self.get_priors()

Пример

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

Чтобы использовать библиотеку, нам нужно импортировать ее вместе с библиотекой NumPy.

import numpy as np
from node import Node

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

rain = Node("rain")
rain.cardinality = 2
rain.priors = np.array([0.8, 0.2]) #  no=0 yes=1

sprinkler = Node("sprinkler")
sprinkler.cardinality = 2
sprinkler.priors = np.array([0.9, 0.1]) #  no=0 yes=1

Для узлов без дочерних узлов это просто. Для других узлов, у которых есть родительские узлы и уже не доступны априорные элементы, нам необходимо определить таблицу условной вероятности (CPT), которая определяет вероятность переменной с учетом всех возможных входных данных от родителей. Этот CPT обозначается в коде буквой «m».

m = np.zeros((2, 2, 2)) #  rain, sprinkler, holmes' grass
m[1, 1, 1] = 1
m[0, 1, 1] = 0.9 #  <-- here
m[0, 1, 0] = 0.1
m[1, 0, 1] = 1
m[0, 0, 0] = 1
holmes = Node("holmes")
holmes.cardinality = 2
holmes.m = m
holmes.likelihood = np.array([1, 1])

m = np.zeros((2, 2)) # rain, watson's grass
m[1, 1] = 1
m[0, 1] = 0.2
m[0, 0] = 0.8
watson = Node("watson")
watson.cardinality = 2
watson.m = m
watson.likelihood = np.array([1, 1])

Как видите, «m» принимает значения родителей в первых измерениях матрицы и значение фактической переменной в последнем, например («Здесь» в комментарии к коду) вероятность того, что трава будет влажной (1), если не было дождя (0) и спринклер был забыт (1), составляет 0,9. Вероятность того, что трава намокнет, равна 1, 1, что означает, что оба состояния имеют одинаковую вероятность.

Затем мы должны соединить узлы, чтобы определить причинно-следственные связи. Класс Node имеет метод под названием «add_parent», который может соединять переменную с родительской переменной.

holmes.add_parent(rain)
holmes.add_parent(sprinkler)
watson.add_parent(rain)

На следующих этапах мы делаем вид, что трава Холмса мокрая (отсюда вероятность [0,1]). Затем мы хотим знать, влажная ли трава у Ватсона (или насколько вероятно, что она будет влажной).

holmes.likelihood = np.array([0, 1])
holmes.message_to_parent(rain)
holmes.message_to_parent(sprinkler)
watson.get_belief() #  array([0.21176471, 0.78823529])

Мы видим, что мнение о том, что трава Уотсона мокрая, действительно имеет тенденцию к намоканию (0,21 против 0,79). Следовательно, BN ожидает, что трава Ватсона будет влажной, поскольку есть соединение через узел дождя, через который распространялось убеждение.

Заключение

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

использованная литература

Пример взят отсюда.