4. деревья решений

4. деревья решений

Приведенная выше табл. 2.1 может быть представлена в виде дерева решений (рис. 2.3).

Рис. 2.3. Дерево решений

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

Для чего нужно дерево решений? Мы можем использовать его для представления своих возможных действий и для нахождения последовательности правильных решений, ведущих к максимальной ожидаемой полезности. Чтобы показать это, усложним задачу. Пусть в вазе 1-го типа содержится 6 красных и 4 черных шара. В вазе второго типа содержится 3 красных и 7 черных шаров. Предоставим человеку, выбирающему между действиями d1 и d2, дополнительные возможности. Пусть он может до своего ответа вытащить за определенную плату один шар из вазы, причем после вытаскивания шар кладется обратно в вазу. Плата за вытаскивание одного шара равна 60 д. е.

Дерево решений с двумя его основными ветвями представлено на рис. 2.4. Вот теперь вопрос о том, какое решение следует принимать, стал сложнее: необходимо решить, стоит ли вынимать шар и какой ответ дать после вытаскивания красного или черного шара. При принятии этих решений нам окажет существенную помощь известный в теории вероятностей [4] (и в теории статистических решений) способ подсчета изменения вероятностей событий после получения дополнительной информации.

Рис. 2.4. Дерево решений

Вернемся к описанию задачи. Вероятность вытащить красный шар из вазы 1-го типа pK(B1) = 0,6, а из вазы 2-го типа pK(В2) = 0,3. Зная все условные вероятности (зависящие от условия), а также вероятности p1 и p2 выбора ваз 1-го и 2-го типа (см. табл. 2.1), мы можем поставить следующие вопросы.

Первый вопрос: каковы вероятности вытащить красный и черный шары? Для ответа на этот вопрос произведем простые вычисления. Вероятность вытащить красный шар: pK(B1) = 0,7Ä0,6 = 0,42, если ваза окажется 1-го типа, рк(В2) = 0,3 Ä0,3 = 0,09, если ваза окажется 2-го типа. Следовательно, вероятность вытащить красный шар в общем случае рк = 0,51. Аналогичным образом можно посчитать, что вероятность вытащить черный шар рч = 0,49.

Второй вопрос более сложный. Пусть вытащенный шар оказался красным (черным). Какое действие следует выбрать: d1 или d2? Для ответа на этот вопрос нужно знать вероятности принадлежности ваз к 1-му и 2-му типам после получения дополнительной информации. Эти вероятности позволяет определить знаменитая формула Байеса [4].

Например, мы вытащили красный шар. Какова после этого вероятность того, что перед нами стоит ваза 1-го типа?

Приведем все обозначения вероятностей:

pK(B1) — вероятность вытащить красный шар из вазы 1-го типа;

pЧ(B1) вероятность вытащить черный шар из вазы 1-го типа;

pK(В2) — вероятность вытащить красный шар из вазы 2-го типа;

pЧ(В2) — вероятность вытащить черный шар из вазы 2-го типа;

p(B1) — вероятность того, что ваза окажется 1-го типа;

р(В2) — вероятность того, что ваза окажется 2-го типа;

p(B1/K) — вероятность того, что ваза окажется 1-го типа после вытаскивания красного шара;

pЧ(B1/Ч) вероятность того, что ваза окажется 1-го типа после вытаскивания черного шара;

р(В2/к) — вероятность того, что ваза окажется 2-го типа после вытаскивания красного шара;

р(В2/ч) — вероятность того, что ваза окажется 2-го типа после вытаскивания черного шара.

Формула Байеса позволяет оценить p(Bi/K) и p(Bi/Ч), где 1 = 1, 2, используя все прочие вероятности. Например:

Для нашей задачи: p(B1/K) = 0,82; p(B1/Ч) = 0,57; p(B2/K) = 0,18; р(В2/ч) = 0,43.

Теперь мы имеем всю информацию, необходимую для принятия решений.

На рис. 2.4 показаны две основные ветви дерева решений, причем верхняя просто повторяет дерево решений на рис. 2.3. Квадратик 1 слева соответствует первому решению — вытаскивать шар или нет. Случаю отказа от вытаскивания шара соответствует верхняя основная ветвь. Решению вытаскивать шар соответствует нижняя ветвь, начинающаяся со случайного события (кружок). В квадратиках 2, 3, 4 принимаются решения о выборе одной из двух стратегий: di или d2. Далее все решает случай (кружки).

Есть три простых правила выбора оптимальной (по критерию максимума ожидаемой полезности) последовательности решений на основе дерева решений:

1) идти от конечных ветвей дерева к его корню;

2) там, где есть случайность (кружок), находится среднее значение;

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

Применим эти правила к дереву решений, представленному на рис. 2.4. В результате получим дерево решений, показанное на рис. 2.5.

Рис. 2.5. «Сворачивание» дерева решений

На этом рисунке над кружками указаны средние значения полезности, двумя черточками отсечены ветви с меньшим значением ожидаемой полезности. Наилучший вариант действий: шар не вытаскивать и выбирать действие d1. Этот вариант соответствует самому верхнему пути дерева решений на рис. 2.5. Такая процедура нахождения оптимального пути на деревьях решений получила название «сворачивание» дерева решений.

Деревья решений при заданных числовых значениях вероятностей и исходов позволяют осуществить выбор той стратегии (последовательности действий), при которой достигается наибольший выигрыш, т.е. достигается максимум функции полезности ЛПР.