Головна |
Підхід, прийнятий в теорії Демпстера-Шефера (ТДШ) [64] відрізняється від байєсівського підходу і методу коефіцієнтів впевненості тим, що, по-перше, тут використовується не точкова оцінка впевненості (коефіцієнт впевненості), а інтервальна оцінка. Така оцінка характеризується нижньою і верхньою межею, що більш надійно. По-друге, ТДШ дозволяє виключити взаємозв'язок між невизначеністю (неповнотою знань) і недовірою, яка властива Байєсова підходу.
В рамках ТДШ безлічі висловлювань А приписується діапазон значень [Bl (А), р1 (А)], в якому знаходяться ступеня довіри (правдоподібності) кожного з висловлювань. тут В1 (А) - ступінь довіри до безлічі висловлювань, що змінює свої значення від 0 (немає свідетельствв користь А) До 1 (безліч висловлювань А істинно); Р1 (А) - ступінь правдоподібності безлічі висловлювань А, що визначається за допомогою формули: Pl (A) = 1-Bl (not A)
Припустимо, що існують дві конкуруючі гіпотези h1 і h2. При відсутності інформації, яка підтримує ці гіпотези, міра довіри і правдоподібності кожної з них належать відрізку [0; 1]. У міру накопичення ці інтервали будуть зменшаться, а довіра гіпотезам - збільшуватися. У теорії Демпстера-Шефера невизначеність знань представляється за допомогою деякого безлічі X. Елементи цієї множини відповідають можливим фактам або висновкам. Невизначеність полягає в тому, що заздалегідь невідомо, яке з можливих значень прийме факт або висновок х I X. Для характеристики ступеня визначеності в ТДШ вводиться деяка одинична міра впевненості (її називають також одиничної масою впевненості), яка розподіляється між елементами X. При цьому, якщо вся маса (ступінь) впевненості доводиться на один елемент х I X, То ніякої невизначеності немає. Невизначеність виникає, коли маса впевненості розподіляється між кількома елементами х I X. Розподіл мас впевненості (Малюнок 6.2) між елементами безлічі X, Представлено у вигляді точок [64]. тут Х ={х1 , х2 , х3}.
Малюнок 6.2 Розподіл мас впевненості
З кожним елементом безлічі X жорстко пов'язана відповідна маса впевненості. так, х1 відповідає m1= 0,3 x2-m2= 0,1 x3-m3= 0,2. Є також вільні маси впевненості m4= 0,2 m5= 0,2, які відносяться відразу до кількох елементів. маса m4 вільно переміщається між елементами x1 и x2, А маса m5 - Між елементами x2 и x3, Т. Е. m4 закріплена за підмножиною {x1, x2}, А m5 - За підмножиною {x2, x3,}. Маси висловлюють ступінь впевненості в можливих значеннях фактів або висновків. Так, ступінь впевненості в значенні х1 може змінюватися від 0,3 до 0,5. Таким чином, ступінь незнання відповідає масі, місце розташування якої не визначено.
У загальному випадку розподіл мас впевненості задається функцією m (А), Що володіє наступними властивостями:
m (O) = 0,
?m (А) = 1,
тут А - Безліч, утворене з підмножин X, Яким призначені відповідні маси (ступеня) впевненості; m (А)- Функція, яка задає відображення А на інтервал [0, 1]. Для прикладу (Малюнок 6.2) маємо:
А = {O, {х1}, {Х2}, {Х3}, {Х1, х2}, {Х2, х3}, {Х1, х3}},
а розподіл мас впевненості задається функцією m (А), Яка характеризується великою кількістю значень:
т (А) = {0; 0,3; 0,1; 0,2; 0,2; 0,2; 0}.
Звернемо увагу, що А складається з підмножин. Позначимо кожне таке підмножина через Аi. Ступінь довіри до висловлювань, відповідним подмножеству Аi, Може бути обчислена за формулою
Тут підсумовування виконується по всім іншим підмножини Aj входять A1 . наприклад:
Bl ({х1, х2}) = m (A1) + M (A2) + M (A3) = M ({x1}) + M ({x2}) + M ({x1, x2}) =
0.3 + 0.1 + 0.2 = 0.6
Результати обчислень ступенів правдоподібності дані нижче (Таблиця 6.2).
Таблиця 6.2 Значення Bl (Ai) І Pl (Ai)
Ai | O | {х1} | {х2} | {х3} | {х1, х2} | {х2, х3} | {х1, х3} | X |
Bl (Ai) | 0.3 | 0.1 | 0.2 | 0.6 | 0.5 | 0.5 | ||
Pl (Ai) | 0.5 | 0.5 | 0.4 | 0.8 | 0.7 | 0.9 |
Ступінь правдоподібності підмножини Аi визначається за формулою:
величини Bl (Ai) І Pl (Ai) мають просту інтерпретацію: Bl (Ai) представляє загальну масу впевненості, яка залишається, якщо з X видалити всі елементи, які не асоціюються з Ai. Pl (Ai) представляє максимальну масу впевненості, яку можна отримати, якщо зрушити вільні маси до елементів безлічі Ai. причому Bl (Ai) ? Pl (Ai) . Іншими словами, Bl (Ai) представляє нижню межу довіри до Ai, а Pl (Ai) - Верхню.
Найважливішим елементом ТДШ є правило комбінації свідчень:
Сума в чисельнику правила поширюється на безліч Ak = A1i ? A2j. Правило є наближеним і дозволяє здійснювати розподіл ступенів довіри в ході виведення. Наприклад, мірою довіри mn(Z) гіпотезі Z - Для n = 3 джерел свідчень вважається сума творів гіпотетичних заходів довіри m1(X) и m2(Y), Спільне входження яких підтримує Z, т. Е. X ? Y = Z. Знаменник в правилі Демстера допускає пусте перетин X Y, А сума заходів довіри повинна бути нормалізована.
Розглянемо застосування правила Демпстера для завдання медичної діагностики, описане в [76].
Припустимо, що розглядається область Q, що містить чотири гіпотези:
1. пацієнт був без свідомості (С);
2. у нього був грип (F);
3. мігрень (H);
4. менінгіт (М).
Необхідно пов'язати заходи довіри з множинами гіпотез в рамках Q. Наприклад, лихоманка свідетельствеут на користь {C, F, M}. Так як елементи Q трактується як взаємовиключні гіпотези, підтвердженням однієї з них може впливати на достовірність інших.
Нехай є свідчення, що у пацієнта лихоманка. Воно підтримує {C, F, M} з ймовірністю 0,6. Назвемо це першою мірою довіри m1. Якщо це всього лише гіпотеза, то m1{C, F, M} = 0,6, де m1{Q} = 0,4 залишок (1-0.6) решту розподілу вірогідності, т. Е. Все інші можливі заходи довіри Q, а не достовірність доповнення {C, F, M}.
Потім були отримано факт про новий прояві хвороби-у пацієнта блювання, яка свідчить про {С, F, н} зі ступенем довіри 0,7. Нехай це буде міра довіри свідоцтва m2. Тоді маємо m2{C, F, н} = 0,7, де m2{Q} = 0,3.
Отримуємо таким чином безліч X - набір підмножин Q на якому m1 приймає ненульові значення, і Y - набір підмножин Q на якому m2 приймає ненульові значення.
Застосуємо правило Демпстера [76] для визначення об'єднаної заходи довіри m3: Перемножимо X і Y. Знаменник дорівнює 1, т. К. Поки не існує порожніх множин X ? Y. Результат обчислень Таблиця 6.3.
Таблиця 6.3 Застосування правила Демстера для об'єднання свідоцтв m1 і m2
m1 | m2 | m3 |
m1{C, F, M} = 0,6 | m2{C, F, н} = 0,7 | m2{C, F} = 0,42 |
m1{Q} = 0,4 | m2{C, F, н} = 0,7 | m2{C, F, H} = 0,28 |
m1{C, F, M} = 0,6 | m2{Q} = 0,3 | m2{C, F, M} = 0,18 |
m1{Q} = 0,4 | m2{Q} = 0,3 | m3{Q} = 0,12 |
Зверніть увагу на міркування і угруповання гіпотез. Чотири безлічі стовпчика m3 являють собою всі можливі перетину X і Y. Цих даних явно недостатньо для установки діагнозу, що і відображають отримані числа.
Додамо дані лабораторного аналізу, який свідчить на користь менінгіту m4{M} = 0,8 і m4{Q} = 0,2.
Застосуємо ще раз правило Демпстера [76] для визначення об'єднаної заходи довіри m5. Результат обчислень Таблиця 6.4.
Так як m5{M} виходить в декількох випадках, то загальна ймовірність m5{M} = (0,144 + 0,096) = 0,240.
В результаті перетину декількох пар множин виходить порожня множина {}, значить знаменник в рівняння Демпстера потрібно вважати як
(1- (0,336 + 0,224)) = 0,44.
Таблиця 6.4 Застосування правила Демстера для об'єднання свідоцтв m3 і m4
m3 | m4 | m5 |
m2{C, F} = 0,42 | m4{M} = 0,8 | m5{} = 0,336 |
m3{Q} = 0,12 | m4{M} = 0,8 | m5{M} = 0,096 |
m2{C, F} = 0,42 | m4{Q} = 0,2 | m5{C, F} = 0,084 |
m3{Q} = 0,12 | m4{Q} = 0,2 | m5{Q} = 0,024 |
m2{C, F, H} = 0,28 | m4{M} = 0,8 | m5{} = 0,224 |
m2{C, F, M} = 0,18 | m4{M} = 0,8 | m5{M} = 0,144 |
m2{C, F, H} = 0,28 | m4{Q} = 0,2 | m5{C, F, H} = 0,056 |
m2{C, F, M} = 0,18 | m4{Q} = 0,2 | m5{C, F, M} = 0,036 |
Остаточні значення заходи довіри мають вигляд:
m5{M} = 0,240 / 0.44 = 0.545 | m5{C, F} = 0.084 / 0.44 = 0.191 |
m5{C, F, H} = 0.056 / 0.44 = 0.127 | m5{C, F, M} = 0,82 |
m5{} = 0,336 + 0.224 = 0.56 |
m5{Q} = 0,024 / 0.44 = 0.055 |
Висока вірогідність порожнього безлічі m5{} = 0.56 означає існування конфлікту свідоцтв на безлічі заходів довіри mj т. к. в прикладі дані коректні з точки зору медицини дані.
При існуванні великих множин гіпотез обчислення заходів довіри може виявитися громіздким, але все ж значно менше ніж при використанні теореми Байеса (розділ 6.2).
Правило Демстера- приклад міркувань суб'єктивних ймовірностей, на відміну від об'єктивних ймовірностей Байеса.
Методи стратегії пошуку рішень | Методи пошуку рішень в одному просторі | Процеси пошуку на графі | евристичний пошук | Експертна система на правилах | Експертні системи, що базуються на логіці | Принцип організації систем з дошкою оголошень | система HEARSAY | види невизначеності | Байєсівський метод |