Лекции 2 Макашова (Лекции 2 Макашова)

Посмотреть архив целиком

13


Лекция №6 (18.10.11)



Байесовские сети доверия (Bayesian Belief Networks, 1998, Pearl)



Пример.

На дороге замедлилось движение автотранспорта. Могут быть две причины:

A – аварийная ситуация

R – дорожные работы

Вероятность проведения дорожных работ при условии замедления движения:

Общая вероятность образования затора:

Если, кроме того, имеется такое свидетельство, как дорожные рабочие (D), то причиной затора, скорее всего, послужили дорожные работы. Если же заметен автомобиль ГАИ (M), то авария вероятнее.

Если известна статистика по трассе, из вероятностной схемы

R

Z

P

t

t

0.3

t

f

0.2

f

t

0.1

f

f

0.4



P(Z&R) = 0.3, а P(Z) = 0.3 + 0.1 = 0.4. Тогда



т.е. причиной затора могут быть дорожные работы с вероятностью 0.75.

В случаи с пятью переменными

получится вероятностная схема с строками.

Другой вариант подсчёта



Другой вариант подсчёта осуществляется по следующей формуле:

в предположении, что родительские вершины независимы.

Для такого случая получается таблица в 20 строк.





Часто байесовские сети используются как абдуктивные. В основном в байесовских сетях не более двух родителей.

Ограничения:

  • Байесовские сети ацикличны (причины и следствия разделяются)

  • Сеть разделяется на независимые подблоки



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



Лекция №7 (25.10.11)

Метод субъективных коэффициентов уверенности



Мд(H,E) – мера доверия к гипотезе H при условии E





Мн(H,E) – мера недоверия к гипотезе H при условии E





Коэффициент уверенности k(H|E) = Мд(H,E) - Мн(H,E), при условиях 0 ≤ Мд(H,E), Мн(H,E) ≤ 1,

причём -1 ≤ k(H|E) ≤ 1. Если k = -1, то E – контрсвидетельство.

При условии, что гипотезы и независимы, справедливо:

В противном случае





(схема суммирования вероятностей).

Если свидетельство правдоподобное,

-a a

|____________________|____________________|

A

Шкала на степень уверенности свидетельства.

то формулы для вычисления мер доверия и недоверия выглядят так:

где 0 ≤ k ≤ 1, - aAa


Используется, когда не подходит байесовский подход.

Методы обработки неопределённостей в GURU

GURU ориентирован на продукционные системы

= a

Выбор формулы объединения факторов уверенности (алгебры) определяется системными переменными E.CFJO для конъюнктивных зависимостей аргументов, E.CFCO – для дизъюнктивных зависимостей аргументов и E.CFVA – для объединения фактора уверенности левой и правой частей правил:

E.CFVA=XX

CFJO = для AND

Объединение факторов уверенности для левой и правой частей правила

CFJO = для OR

Объединение факторов уверенности, полученных по нескольким правилам для одной переменной

M: Min(a, b)

M: Max(a, b)

P: (a * b) / 100

P: a + b – (a * b) / 100

A: ( +

) / 2

A: ( +

) / 2

B: Max(a, b) + Min(a, b)

B: (1 - a / 100) * (1 – b / 100)



Где М – максимин, P –вероятностная логика, A – смешанная логика, B – нечёткая логика.

Пример.

Пусть целевая вершина R – надёжность поставщика. Основные факторы, которые при этом учитываются:

  1. Финансовое состояние (рентабельность, наличие задолженностей).

  2. Наличие рекламаций.

  3. Статус предприятия(государственное, кооперативное, индивидуальное, частное).

  4. Удалённость поставщика.

Надежность поставщика

Финансовое состояние



Удаленность поставщика







Наличие рекламаций



Статус предпрт





Рентабельность

долженность









Дано: ()



  1. Нет неопределённости в исходных данных.

ММ: max{0.9; 0.8; 0.5; 0.6} = 0.9

PP: 0.9 + 0.8 - 0.72 = 0.98

0.98 + 0.5 – 0.49 = 0.99

0.99 + 0.6 – 0.594 ≈ 1.00



  1. Есть неопределённость в исходных данных. Даже можно задать пороговое значение.

E.UNKN = k(20)

E.JCR = TRUE (0 ≤ CF ≤ 100)

ММ: max{min{0.6;0.9} ; min{ 0.6; 0.8}; min{0.5;1}; min{0.6;1}} = 0.6

PP: 0.6*0.9 + 0.6*0.8 – 0.54*0.48 = 0.76

0.76 + 0.5 – 0.76*0.5 = 0.88

0.88 + 0.6 – 0.88*0.6 = 0.95



Если факторы положительны:

R

= 0.9 = 0.9


a = 1 b=1



k(R) = a+b-ab

0.9 + 0.8 -0.72 = 0.98




Если какой-то фактор отрицателен:

R

= 0.9 = 0.9


a = 1 b=-1



k(R) = a(1-b)

0.9 *0.2 = 0.18

0.18 < 0.2 не превышает порогового значения → поставщик не надёжен






Если факторы положительны:

R

= 0.9 = 0.9


a = 0.6 b = 0.6



k(R) = 0.6*0.9 + 0.6*0.8 – 0.54*0.48 = 0.76




Если какой-то фактор отрицателен:

R

= 0.9 = 0.9


a = 0.6 b = -0.6



k(R) = 0.6*0.9 * (1 - 0.6*0.8) = 0.28



Использование нечёткой переменной.


Нечёткая переменная может одновременно принимать несколько значений.


E.IFUZ = <n>


Пример


= (200 cf 90, 100 cf 30)

= (150 cf 80, 50 cf 20)


P1 =( > цена = ‘↓’)

P2 = < цена = ‘↑’)

P3 = = цена = '=’)


Что ожидать от таких данных, если прогнозируются и

Классической логикой нечётких переменных является логика Заде.

cf ( > ) = max{min(0,9; 0,8), min(0,9; 0,2), min(0,3; 0,2)} = 80

cf ( < ) = min{80; 30} = 30

Цена = {‘↑’cf 30, ‘падает’ cf 80, 'не изменяется’ cf 0}


Одна переменная может принять ряд значений с соответствующими степенями принадлежности.

Пример


Построение прогнозирующей системы для банка. Характеристики клиента:

  • Возраст

  • Семейное положение

  • Профессиональный статус


Вклад – нечёткая переменная.

Правила:

P1 = (возраст < 20 вклад = (‘образование’ cf 40, ‘жильё’ cf 10, ‘сбережения’ cf 5))

P2 = (возраст ≥ 20 & возраст < 30 вклад = (‘образование’ cf 20, ‘жильё’ cf 20, ‘сбережения’ cf 10))

P3 = (семейное положение = ‘одинокий’ вклад = (‘образование’ cf 30, ‘жильё’ cf 10, ‘сбережения’ cf 20))

P4= (семейное положение = ‘семейный’ вклад= (‘образование’ cf 10, ‘жильё’ cf 40, ‘сбережения’ cf 20))

P5 = (профессия= ‘рабочий’ вклад = (‘образование’ cf 20) ; вклад = (‘образование’ cf 60))


Дано:

(Возраст < 20; семейное положение = ‘семейный’; профессиональный статус = ‘рабочий’)

Последовательность действий GURU при выборе логики PP:





P1


P5

Σ

P5



Образование

40

10

46

-60

18

Жильё

10

40

46


46

Сбережения

5

20

24

20

39



Σ =( a + b – a*b)/100% a + b – a*b/100%


Ответ:

Вклад = (‘образование’ cf 18, ‘жильё’ cf 46, ‘сбережения’ cf 39) -в сумме 100%

Нормировка к 100%:

Вклад = (‘образование’ 17,6% , ‘жильё’ 44,6%, ‘сбережения’ 37,8%)

ММ: Вклад = (‘образование’ cf (40-60) , ‘жильё’ 40, ‘сбережения’ cf 20)




Лекция №8 (1.11.11)

Поиск решений в условиях неопределенности с использованием Дерева Решений (ДР)


Конъюнктивная вершина



Если , можно констатировать R с вероятностью k.

R




а) Логика maxmin.

K(R)=min {k(Ci), k(Cj)}* k

Если длинная конъюнкция, то

K(R)=min {k(Ci), …, …, …, k(Cj)}* k

b) Вероятностная логика.

K(R)=k(Ci)* k(Cj)* k

Дизъюнктивная вершина

R


k( k(



а) Логика maxmin.

K(R)=max{ *, *, …}





b) Вероятностная логика.

Упорядочиваем свидетельства по важности и включаем дополнительное:

K(R)=

K(R)=



Пример

{Pi} – набор правил,

{Fj} – наблюдаемые факторы,

i} – множество промежуточных заключений,

R – целевое заключение.

P1 = (F1 C1 ; 0.8)

P2 = (F2 C1 ; 0.7)

P3 = (F3 C2 ;1)

P4 = (F4 & F5 C3 ; 0.9)

P5 = (F6 C6 ;1)

P6 = (F7 C6 ; 0.7)

P7 = (F8 & F9 C4 ; 0.4)

P8 = (C1 & C2 & C3 C5 ; 0.9)

P9 = (C4 C6 ; 0.8)

P10 = (C5 & C6 R ; 1)

Если дерево оборвалось на промежуточном заключении и нет правила, позволяющего его связать, то база не полна.













R

P10 ; 1

C6 C6

P8 ; 0.8 P5 ; 1 P6 ; 0.7 P9 ; 0.8

C1 C2 C3 F6 F7 C4

P1 ; 0.8 P2 ; 0.7 P3 ;1 P4 ; 0.9 P7 ; 0.4

F1 F2 F3 F4 F5 F8 F9



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

, i =

k()

- коэффициент уверенности наблюдаемого фактора

k(), k() Є [0,1]


Sн = (0,9; 0; 1; 0,8; 0,9; 0,1; 0,8; 0,7; 0,5)

F1 F2 F3 F4 F5 F6 F7 F8 F9

а) maxmin

k(C1) = max{(0.9*0.8); (0.7*0)} = 0.72

k(C2) = 1

k(C3) = min{0.8; 0.9)*0.9 = 0.72

k(C4) = min{0.7; 0.5)*0,4 = 0.2

k(C5) = min{0.72; 1; 0.72)*0.9= 0.65

k(C6) = max{(0.7*0.8); (0,8*0.2)} = 0.56

k(R) = min{0.65; 0.56)*= 0.56 (56%)



б) вероятностная логика

k(C1) = 0.8*0.9 = 0.72

k(C2) = 1

k(C3) = 0.9*0.8*0.9 = 0.65

k(C4) = 0.5*0.7*0.4 = 0.14

k(C5) = 0.72*1*0.65*0.9 = 0.42

k(C6) = 0.8*0.7 + 0.14*0.8 – 0.56*0.12 = 0.57

k(R) = 0,42*0.57*1 = 0.24 (24%)

Пусть теперь нашли ещё одного эксперта, который считает по своим правилам:

Тогда:

а) k(R) = 0.6

k(R) = max{0.56*0.6} = 0.6

а) k(R) = 0.5

k(R) = max{0.56*0.5} = 0.56

б) k(R) = 0.6

k(R) = 0.24 + 0.6 – 0.24*0.6 = 0.7

б’) k(R) = 0.5

k(R) = 0.7 + 0.5 – 0.7*0.5 = 0.85



В случае maxmin привлечение дополнительных правил ничего не изменило, а в случае вероятностной логики – существенно повлияло. Значит, надо тщательнее выбирать логику.



Теория свидетельств Демпстера-Шефера

(A.Dempster – G.Shafer)

A Mathematical Theory of Evidence (G.Shafer, 1976)

Минусы схемы Байеса:

1. p(H) + pH) = 1

2. Свойство индифферентности:

Если не известна вероятность гипотезы (события), то все гипотезы считаются равновероятностными.

3. Точечная оценка (оценку получают в виде точки).

Аксиомы ТВ Колмогорова:

1. 0 ≤ P(H) ≤ 1;

2. P(true) = 1; P(false) = 0;

3. P(HQ) = P(H) + P(Q) – P(H&Q) => 4

4. P(H∪¬H) = P(H) + P(¬H) = 1



Посылки теории свидетельств

(слабее посылок ТВ)

  1. Использование субъективных свидетельств (субъективных вероятностей)

  2. Использование правила объединения свидетельств

  3. Различаются ситуации неопределённости (uncertainty) и незнания (ignorence):

Т.е. если эксперт выступает “за” гипотезу с уверенностью a, то это не значит, что он отвергает её с уверенностью (1-a)

  1. Вместо точечных вероятностей используется вероятностный интервал доверия.

В 1967г. Dempster ввёл значения:

P*(H) – верхнее значение вероятности события или гипотезы

(H) – нижне значение вероятности события или гипотезы

Интервал доверия [P*(H), (H)]

Shafer:

Bel(H) – мера (функция) доверия к H

Pl(H) – мера правдоподобия гипотезы H

Pl(H) = 1- Bel(H)

Bel – ф-я, т.к. для неё возможен аппарат вычислений

[Bel(H), Pl(H)]

Bel – нижняя граница, мера необходимости

Pl – верхняя граница, уровень возможности, при котором гипотеза ещё может иметь место



Пример

Н – покупать акции

  1. Эксперт А: ) = 0.9

Эксперту А можно верить с вероятностью 0.9

) = 0.1

Эксперт А советует покупать, т.е. он за гипотезу H.

Bel(H) = 0.9

Pl(H) = 1 – Bel(¬H) = 1-0 = 1

Нет информации, что не следует покупать акции.

Вероятностный интервал доверия [0.9; 1.0]

  1. Эксперт B: ) = 0.8, ) = 0.2

Нужно объединить результаты.

а) A,B → H

Вероятность, что обоим можно верить:

Bel(H) = 0.98

Pl(H) = 1

[0.98; 1]



б) AH, B → ¬ H



- нормирующее

Bel(H) = = 0.645

Bel(¬H) = = 0.286

[Bel(H); Pl(H)= 1- Pl(¬H)]

Вероятностный интервал доверия H: [0.643; 0.714]

PlH) = 1- Bel(H) = 0.357

Вероятностный интервал доверия ¬H: [0.286; 0.357]



Если , , то вероятностный интервал [0.99; 1

Если эксперты говорят одно и то же, то следует купить акции.

Если эксперты противоречат друг другу, то вероятность гипотезы не 0.5, а [0.47; 0.53].

Здесь не работает принцип P(H) + PH) =1.



Лекция №9 (8.11.11)



Правило объединения свидетельств.



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

Рассмотрим ситуацию конфликта свидетельств. Субъективные вероятности: учитывается то, что известно. Неопределённость и неизвестность – не одно и то же.

{H} – множество гипотез (простудные заболевания)

- множество всех подмножеств из множества {H}

H – подгипотезы гипотезы H (грипп, ангина, ОРЗ)

Задаётся базовое распределение вероятностей (мер) на множестве :

0 ≤ m(H) ≤ 1

Ф-я (мера) доверия к гипотезе H:

Мера правдоподобия H: Pl(H) =

[Bel(H), Pl(H)]

Правило объединения свидетельств Демпстера:

- конфликт свидетельств.

Пример

Задача медицинской диагностики.

Пусть H – сложная гипотеза, которая содержит 4 подгипотезы:

  • шок (k1)

  • грипп (k2)

  • мигрень (k3)

  • менингит (k4)



  1. Свидетельство – у пациента лихорадка

{} с вероятностью 0.6

= 0.6

= 0.4

Hвсё, что осталось

Свидетельство лихорадка подтверждает гипотезы с вероятностью 0.6. Значит, вероятность всего остального 0.4.



  1. Свидетельство – рвота

{} с вероятностью 0.7

= 0.7



Нужно объединить свидетельства.

Как получить правило объединения свидетельств, зная и ?



X – мн-во гипотез, на которых мера принимает нулевое значение

Y – мн-во гипотез, на которых мера принимает нулевое значение



0.4

0.3

0.4

0.3

0.12



1.00


Случайные файлы

Файл
25352.rtf
28603-1.rtf
38996.rtf
2500-1.rtf
146200.doc