Алгоритм недели: моделирование сложных причин и следствий с помощью байесовских сетей

Какую проблему я пытаюсь решить?

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

• Моделирование рисков
• Принятие решений
• Строгая интуиция

Давайте рассмотрим пример, который довольно хорошо известен с очень верным ответом: проблема Монти Холла. В задаче Монти Холла нам представлены три двери (красная, зеленая и синяя). Монти Холл говорит, что за одним из них стоит приз (новый ноутбук на ваш выбор!), А у двух других есть козы. Я знаю, о чем ты думаешь: Монти Холл — дурак, потому что любимый козел будет лучшим! Давайте представим, что мы вообще не хотим козла (используйте свое воображение). Давайте представим, что мы ДЕЙСТВИТЕЛЬНО хотим этот новый ноутбук. ОК? ХОРОШО.

Итак, Монти Холл просит вас выбрать дверь, за которой, по вашему мнению, стоит ваш ноутбук. Допустим, вы выбрали зеленую дверь #BecauseMoney. Ну, а теперь Монти Холл позаботится о вас. Он открывает одну из дверей, которую вы не выбрали, и показывает, что у нее есть коза. Чего бы я сейчас не дал за козу. Так или иначе. Итак, теперь у вас есть оригинальная дверь, которую вы выбрали, и Монти Холл открыл одну из двух других дверей и показал, что это коза. Теперь дерьмо становится реальностью. Он предлагает вам выбор.

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

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

Вы можете перейти непосредственно к исполняемому коду, перейдя в мой репозиторий github для этого здесь:  Bayesian Networks Git Repo

Что такое байесовская сеть?

Байесовская сеть — это графическая модель событий, их вероятностей и того, как они влияют друг на друга. Под графической моделью я не имею в виду, что вы используете картинки и карандаши. Графическая модель — это модель, которая состоит из серии объектов (обычно называемых узлами) и линий (или ребер), которые их соединяют. Оказывается, графические модели УДИВИТЕЛЬНЫ для механического рассуждения об отношениях между узлами. Пример, с которым связывается большинство людей, это то, что Facebook видит вас и ваших друзей в виде узлов на графике, а ваши дружбы — в качестве границ между вами.

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

Как бы я использовал это?

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

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

door_picked_node = BayesianNode('door_picked', door_picked_table)
prize_behind_node = BayesianNode('prize_behind', prize_behind_door_table)
shown_empty_node = BayesianNode('shown_empty', shown_empty_table)
win_prize_node = BayesianNode('win_prize', win_prize_table)
door_after_choice_node = BayesianNode('door_after_choice', door_after_choice_table)
switch_node = BayesianNode('switch_or_stay', switch_table)
informed_agent_node = BayesianNode('informed_agent', informed_agent_table)

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

Теперь, когда у нас есть все возможные события, нам нужно сформулировать, как они связаны. Мы делаем это с помощью кода, который выглядит следующим образом:

door_picked_node.affects(shown_empty_node)
prize_behind_node.affects(shown_empty_node)
shown_empty_node.affects(door_after_choice_node)
door_picked_node.affects(door_after_choice_node)
door_after_choice_node.affects(win_prize_node)
prize_behind_node.affects(win_prize_node)
switch_node.affects(door_after_choice_node)

Что тут происходит? Надеюсь, это читается довольно четко, но если это не так, позвольте мне объяснить другими словами. Здесь мы в основном говорим: «Когда это событие происходит, оно говорит нам о том, насколько вероятно, что это другое событие произойдет или нет». Вот более читаемая версия выше:

door_picked_node.affects(shown_empty_node)
# The contestant picking a door tells us something 
# about which doors Monty can show as empty since Monty 
# won't show us what's behind our own door ever.

prize_behind_node.affects(shown_empty_node)
# Knowing which door has a prize behind it tells us something 
# about which door Monty might choose to show as empty since 
# he would never show us the door with the prize behind it.

shown_empty_node.affects(door_after_choice_node)
# Showing the empty door affects our choices in doors since 
# there's now one less door to choose to switch to.

door_picked_node.affects(door_after_choice_node)
# The door we originally picked affects the door we might pick 
# once we're given the choice to switch doors.

door_after_choice_node.affects(win_prize_node)
# The door we decide to choose after being shown the empty door 
# affects whether or not we win the prize. The reason for this 
# is... well. If we chose the winning door, we'll win and if we 
# didn't, we won't.

prize_behind_node.affects(win_prize_node)
# Which door the prize is behind affects whether or not we 
# win the prize.

switch_node.affects(door_after_choice_node)
# Whether we switch doors or keep our original door affects the 
# door we have.

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

Теперь, когда мы соединили все эти события / узлы вместе, мы можем фактически начать видеть, что происходит, когда события разворачиваются. Мы начнем с оценки вероятностей всех событий, прежде чем делать что-либо:

Полученные результаты:

• Дверь выбрана

  • синий: 0,3333
  • зеленый: 0,3334
  • красный: 0,3333

• Приз за дверью:

  • синий: 0,3333
  • зеленый: 0,3334
  • красный: 0,3333

• Дверь показана пустой:

  • синий: 0.33333333333333337
  • зеленый: 0.33333333333333337
  • красный: 0.33333333333333337

• Выиграть приз:

  • False: 0.6666666666666667
  • Правда: 0.3333333333333333

• Обновлен выбор дверей:

  • синий: 0.3333333333333333
  • зеленый: 0.3333333333333333
  • красный: 0.3333333333333333

• Переключить или остаться:

  • переключатель: 0.5
  • пребывание: 0.5

Пройдите через них и убедитесь, что они соответствуют вашим рассуждениям.

Помните выше, как мы проходили настройку игры, и у нас был выбор? Давайте перейдем к обновлению нашей Байесовской сети:

door_picked_node.given('red')
shown_empty_node.given('green')

Это результат запуска этих двух обновлений через нашу сеть:

• Дверь выбрана

  • синий: 0.0
  • зеленый: 0.0
  • красный: 1,0

• Приз за дверью

  • синий: 0.6666666666666666
  • зеленый: 0.0
  • красный ‘: 0,3333333333333333

• Дверь показана пустой

  • синий: 0.0
  • зеленый: 1,0
  • красный: 0.0

• Выиграть приз

  • Ложь: 0.5
  • True: 0,5

• Обновленный выбор дверей

  • синий: 0,5
  • зеленый: 0.0
  • красный: 0.5

• Переключиться или остаться

  • переключатель: 0.5
  • пребывание: 0.5

Теперь что-то интересное произошло. Посмотри результаты. Некоторые из событий более чем очевидны. Например, выбранная дверь на 100% красная. Ну да. Да уж. Мы сделали этот выбор. Это было дано, не важно. Наш выбор в дверях теперь 50/50, так как одна из дверей была открыта (зеленая дверь, которая подтверждается дверью, показанной пустым узлом).

Еще одна вещь … Вероятность того, что приз окажется за синей дверью, составляет 0,6666, что вдвое больше вероятности того, что приз окажется за нашей собственной красной дверью. Также! Обратите внимание, что наш шанс выиграть приз составляет всего 50/50. Почему наша вероятность выигрыша равна 50/50, если мы теперь знаем, что приз, вероятно, находится за другой дверью? Потому что мы никогда ничего не моделировали о нашей вероятности сделать оптимальный выбор. Однако я ожидаю, что, если мы перезапишем эти числа, учитывая, что мы поменялись дверями, мы увидим, что вероятность «выигрыша» возрастет, чтобы соответствовать вероятности того, что приз находится за синей дверью.

Я переосмыслил это. Учитывая, что мы изменили наш выбор, наша вероятность выбора синей двери равна 1, а наша вероятность выиграть приз теперь равна .66666!

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

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

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

Совместные таблицы вероятностей, Байес и вы

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

Это таблица, которая показывает все возможные комбинации событий в игре. Все возможности дверей, которые вы могли бы выбрать, независимо от того, сможете ли вы выиграть. Возьмите первый ряд в качестве примера. Это читается как: «Из всех возможностей, включая событие« выбрана дверь »и« дверь выбрана победителем », есть вероятность 11,11%, что красная дверь была выбрана И красная дверь — победная дверь». Следующий ряд говорит нам, что вероятность того, что красная дверь проиграет, в два раза выше.

Условные вероятности работают, говоря что-то вроде: «Если дверь выбрана красным, найдите вероятность выигрыша». Когда мы сделаем это, мы возьмем таблицу выше и ограничим ее только строками с красной дверью, выбранной следующим образом:

Затем мы «нормализуем» таблицу, чтобы все строки снова суммировались на 100%.

Теперь мы можем сказать: «Учитывая, что выбрана красная дверь, есть шанс 33,33%, что это выигрышная дверь». Вы можете удивиться, как я сделал нормализацию. Все, что мне нужно было сделать, это взять мою новую таблицу и разделить каждое значение на общую сумму всех значений. Для первого ряда это будет .11111 / .33333, то есть .33333.

Вы также можете сказать: «Какова вероятность выбора выигрышной двери в целом?» В этом случае мы просто забыли бы о столбце «Выбор двери» и затем суммировали все вероятности для каждого уникального значения «Победная дверь». Это будет та таблица:

Шаг 1:

Шаг 2:

Теперь можно сказать, что вероятность выбора выигрышной двери составляет 33,33%. Это все, что нужно для условных вероятностей. Это все о выборе подмножества возможностей и нормализации ваших вероятностей между ними. Это легко сделать, пока стол маленький. Однако, когда вы попадаете в таблицу с тремя разными переменными с 3 возможными значениями в каждой … теперь вы говорите о 27 строках для заполнения. И это становится намного НАМНОГО быстрее, поскольку каждая добавленная переменная увеличивает количество строк в геометрической прогрессии.

Чтобы справиться с этим, я сделал класс в Python, чтобы сделать вычисления для меня. Я называю это «JointProbabilityTable». ТВОРЧЕСТВО В ДВИЖЕНИИ!

Обработка больших таблиц вероятности соединения

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

door_picked_table = JointProbabilityTable(
	columns=['door_picked'],
	data = [
		['red',   0.3333],
		['blue',  0.3333],
		['green', 0.3334],

	])

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

Эта таблица не очень интересна, так как на самом деле это просто список вероятностей без какого-либо интересного способа их свернуть. Давайте перейдем к РЕАЛЬНОМУ столу.

shown_empty_table = JointProbabilityTable(
	columns=['door_picked', 'prize_behind', 'shown_empty'],
	data = [
		['red', 'red',  'red',       0.0],
		['red', 'red',  'green',     0.5],
		['red', 'red',  'blue',      0.5],
		['red', 'green',  'red',     0.0],
		['red', 'green',  'green',   0.0],
		['red', 'green',  'blue',    1.0],
		['red', 'blue',  'red',      0.0],
		['red', 'blue',  'green',    1.0],
		['red', 'blue',  'blue',     0.0],

		['green', 'red',  'red',     0.0],
		['green', 'red',  'green',   0.0],
		['green', 'red',  'blue',    1.0],
		['green', 'green',  'red',   0.5],
		['green', 'green',  'green', 0.0],
		['green', 'green',  'blue',  0.5],
		['green', 'blue',  'red',    1.0],
		['green', 'blue',  'green',  0.0],
		['green', 'blue',  'blue',   0.0],

		['blue', 'red',  'red',      0.0],
		['blue', 'red',  'green',    1.0],
		['blue', 'red',  'blue',     0.0],
		['blue', 'green',  'red',    1.0],
		['blue', 'green',  'green',  0.0],
		['blue', 'green',  'blue',   0.0],
		['blue', 'blue',  'red',     0.5],
		['blue', 'blue',  'green',   0.5],
		['blue', 'blue',  'blue',    0.0],
	])

Сейчас, когда. 32 ряда удивительности. Эта общая таблица вероятностей описывает нашу вселенную возможностей с точки зрения трех событий, которые влияют друг на друга: какая дверь была выбрана, какая дверь за призом, и какая дверь была показана пустой. Вы можете заметить, что эта таблица не составляет до 100%. Класс JointProbabilityTable нормализует мои таблицы при создании, поэтому мне легче рассуждать. Как так? Это позволило мне мысленно разбить этот большой стол на группы из трех человек.

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

Таким образом, для первого ряда мы хотим знать вероятность того, что красная дверь будет показана как пустая. Хорошо. За этим стоит приз, так что нет никаких шансов, что Монти откроет эту дверь. Обратите внимание, что вероятность справа от первого ряда равна 0. Итак, есть две другие двери, и у меня нет никакой другой информации, поэтому я могу сказать, что другие две двери имеют шанс 50/50 быть открытыми Монти.

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

Допустим, у вас есть кровь, и ваши результаты оказались положительными для болезни Бозорея. В исследование было включено 1219 человек. 61 человек имел заболевание и дал положительный результат, у 14 был заболевание и отрицательный результат, у 14 не было заболевания и положительный результат при тестировании, у 1130 человек не было заболевания и отрицательный результат тестирования. Какова вероятность того, что у вас действительно есть заболевание, учитывая, что вы дали положительный результат?

Сначала мы начнем с ненормализованной таблицы, которая просто перечисляет факты:

Далее мы нормализуем таблицу, чтобы получить вероятности

Давайте интерпретировать эту таблицу. Сколько людей имеют заболевание независимо от результатов их тестов? Сложите все строки с «Имеет заболевание», равное true. Так 6,15% делают. Оставив 93,85% не имеющих заболевания.

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

Далее нам нужно перенормировать вероятности. Когда мы делаем это, мы получаем эту таблицу:

Вероятность того, что у вас заболевание, составляет 81,3%. Это вероятно, но далеко не уверен.

Обновление убеждений в совместных таблицах вероятностей

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

Когда мы помечаем событие как данное и фактически говорим, что теперь наверняка произошло, вероятности изменения связанных событий также изменяются. Мы видели это выше, когда мы выбрали красную дверь, а затем зеленая дверь показалась нам пустой. Опять же все это следует тому, что мы уже рассмотрели выше. За исключением того, что теперь эти новые убеждения передаются между событиями и применяются везде, где это имеет смысл.

Как мне сделать это вообще?

def update_belief(self, event_name, new_beliefs):
	current_beliefs = self._get_current_beliefs_for_event(event_name)
	belief_shifts = self._get_belief_shifts(current_beliefs, new_beliefs)
	event_column_index = self._columns.index(event_name)
	new_table = self._clone_data()
	for row in new_table:
		row[-1] = row[-1] * belief_shifts[row[event_column_index]]
	return JointProbabilityTable(self._columns, new_table)

1. Мы обновляем убеждения только для одного события в узле за раз.
2. Параметр new_beliefs, который передается, является списком каждого значения для данного события и новых вероятностей.
3. Получить текущие убеждения ТОЛЬКО для события, которое мы обновляем. Это эквивалентно суммированию всех вероятностей и группированию их по различным значениям события для этого конкретного события, которое мы обновляем.
4. Теперь мы знаем, каковы были вероятности, и мы знаем, что они должны быть обновлены, чтобы мы могли рассчитать процент, на который можно скорректировать каждую вероятность в объединенной таблице вероятностей узла.
5. Мы просматриваем каждую строку в базовой таблице вероятностей и корректируем ее на величину, указанную значением события, на которое ссылается строка в таблице.
6. Я попытался использовать неизменность, когда это возможно, поэтому я создаю совершенно новую таблицу вероятностей и возвращаю ее с обновленными данными.

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

def _get_belief_shifts(self, current_beliefs, new_beliefs):
	belief_shifts = {}
	for event_value in new_beliefs:
		updated_probability = new_beliefs[event_value]
		current_probability = current_beliefs[event_value]
		if current_probability != 0:
			probability_shift = updated_probability / current_probability
		else:
			probability_shift = 0
		belief_shifts[event_value] = probability_shift
	return belief_shifts

Связывая все вместе

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

Волшебство происходит в «данном» методе:

class BayesianNode:
	def __init__(self, name, joint_probability_table):
		self._name = name
		self._original_joint_probability_table = joint_probability_table
		self._joint_probability_table = joint_probability_table
		self._affects_nodes = []
		self._affected_by = []
		self._known = False
	def affected_by(self, other_node):
		self._affected_by.append(other_node)
	def affects(self, node):
		self._affects_nodes.append(node)
		node.affected_by(self)
	def _forward_propagate(self, joint_probability_table):
		self._joint_probability_table.update_applicable_beliefs(self._name, joint_probability_table)
		for affected_node in self._affects_nodes:
			affected_node._forward_propagate(self._joint_probability_table)
	def _backward_propagate(self, joint_probability_table):
		self._joint_probability_table.update_applicable_beliefs(self._name, joint_probability_table)
		for affected_node in self._affected_by:
			affected_node._backward_propagate(self._joint_probability_table)
	def given(self, value):
		if not self._known:
			self._joint_probability_table = self._joint_probability_table.given(self._name, value)
			self._known = True
			jpt = self._joint_probability_table.clone()
			for affected_node in self._affects_nodes:
				affected_node._forward_propagate(jpt)
			for affected_node in self._affected_by:
				affected_node._backward_propagate(jpt)
			for affected_node in self._affects_nodes:
				affected_node._backward_propagate(jpt)
			for affected_node in self._affected_by:
				affected_node._forward_propagate(jpt)
	def probability(self):
		return self._joint_probability_table.probability(self._name)
	def __str__(self):
		return str(self._joint_probability_table)

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

Обратите внимание, что мне нужно установить для «self._known» значение true. Это так, что узел не распространяется сам по себе до бесконечности.

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

Опять же, вот код, если вы хотите взглянуть на него более подробно:  Bayesian Networks Git Repo

Спасибо за чтение.

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