ML: Теорія Демпстера-Шафера

Вступ

У теорії Демпстера-Шафера (ТДШ) для міри істинності твердження $A$ використовується інтервальна оцінка $[a,~1-\bar{a}]$, де нижня межа $a$ називається довірою і дорівнює сумі фактів, що підтримують твердження, а верхня межа, що називається правдоподібністю, дорівнює $1-$ сумі фактів, що суперечать твердженню $A$, тобто підтримують його заперечення $\bar{A}$. Якщо немає фактів, що підтримують твердження, то нижня межа (довіра) дорівнює нулю, а якщо немає і фактів, що суперечать твердженню, то верхня межа (правдоподібність) дорівнює одиниці. Така ситуація $[0,1]$ відповідає повній невизначеності ("або зустріну динозавра, або не зустріну").

Можливість розрізняти невизначеність $[0,1]$ і рівноймовірність $[0.5,~0.5]$ важлива при проведенні міркувань. Наприклад, у методі Байєса, якщо апріорна ймовірність події $A$ невідома, зазвичай вважають, що $P(A)=1/2$. Цей же вибір ми змушені робити для "істинно рівноймовірної" події (підкидання монети). Теорія Демпстера-Шафера дозволяє розрізняти ці дві ситуації.

Інтервал істинності події

Розглянемо як приклад твердження про те, що "всередині скрині знаходиться шкатулка" (скриня закрита).
Є дві взаємовиключні гіпотези: $A$:"знаходиться" і $\bar{A}$: "не знаходиться". Інтервали цих істинності цих гіпотез можуть перетинатися або не перетинатися:

На першому рисунку $a\lt 1/2$, а на другому $a\gt 1/2$ і в обох випадках $\bar{a}\lt a$. Ще два варіанти відповідають перестановці $A$ і $\bar{A}$. Коли інтервали не перетинаються і $a=1-\bar{a}$, ми отримуємо звичайні точкові ймовірності $P(A)=a$ і $P(\bar{A})=\bar{a}$.

Оскільки в інтервалі $A:~[\text{Bel}(A),~1-\text{Bel}(\bar{A})]=[a,\,1-\bar{a}]$ верхня межа інтервалу повинна бути не нижче нижньої, то необхідно дотримуватися такого обмеження: $$ \text{Bel}(A) + \text{Bel}(\bar{A}) \le 1. $$

Для великого числа взаємовиключних тверджень $\{H_1,...,H_n\}$, відстежувати подібні нерівності для підтримання несуперечливості теорії вже непросто. Власне задачею ТДШ є побудова способу узгодження меж інтервалів оцінки істинності різних тверджень.

Масові функції

Нехай є множина взаємовиключних тверджень (гіпотез): $\mathbb{H}=\{H_1,...,H_n\}$, так що $H_i\,\&\,H_j = \mathbb{F}$ (хибність) для всіх $i\neq j$. У ТДШ така множина називається фреймом розрізнень (frame of discernment) або універсальною множиною. Зокрема, множина $\mathbb{H}$ може складатися з елементарних подій.

Розглянемо всі підмножини множини $\mathbb{H}$. Їх можна нумерувати $n$-значними бінарними числами $101...1$ (у дану підмножину гіпотеза $H_1$ включена, гіпотеза $H_2$ не включена і т.д.). Таких чисел буде $2^{|\mathbb{H}|}$, де $|\mathbb{H}|=n$ - число елементів множини $\mathbb{H}$. Множину всіх підмножин прийнято позначати як $2^{\mathbb{H}}=\{\,A\mid A\subseteq \mathbb{H}\,\}$, де перед рискою стоїть елемент, а після риски умова якій він задовольняє.

◊ Для $\mathbb{H}=\{H_1,H_2,H_3\}$ існує вісім підмножин (включаючи порожню множину $\varnothing$ і саму $\mathbb{H}$): $$ 2^{\mathbb{H}} ~=~ \{~ \varnothing,~\{H_1\},~\{H_2\},~\{H_3\},~\{H_1,H_2\},~\{H_1,H_3\},~\{H_2,H_3\},~\mathbb{H}~ \}. $$

Підмножини трактуються як об'єднання гіпотез за допомогою логічного виключного або: $H_1\oplus H_2$, тобто $\{H_1,H_2\}$ означає, що вірно або $H_1$, або $H_2$ (щось одне). Заперечення гіпотези $\bar{H}_1$ означає, що істинно все що завгодно крім неї, тобто $\{~\{H_2\},~\{H_3\},~\{H_2,H_3\}~\}$ (все, що не містить $H_1$).

Передбачається, що існують експерти, кожен з яких може вибрати одну з підмножин як вірну. Частку експертів, що "проголосували" за дану підмножину $A\in 2^{\mathbb{H}}$ назвемо масою її підтримки $m(A)$. Вважаємо, що кожен експерт вибір зробив, тому: $$ m(\varnothing)=0,~~~~~~~~m(A) \ge 0,~~~~~~~~\sum_{A\,|\,A\,\in \,2^{\mathbb{H}}} m(A) = 1. $$ Замість експертів часто говорять про суму (масу) свідчень на підтримку даної підмножини. Підмножини для яких $m(A) \gt 0$ називають фокальними елементами (focal elements), а їх об'єднання - ядром.

◊ Нехай у прикладі з трьома гіпотезами розподіл голосів експертів по підмножинах має вигляд: $$ \begin{array}{r|l|l|l|l|l|l|l|l|} A: & \varnothing & \{H_1\} & \{H_2\} & \{H_3\} & \{H_1,H_2\} & \{H_1,H_3\} & \{H_2,H_3\} & \mathbb{H}\\ \hline m(A): & 0 & 0.1 & 0.4 & 0 & 0.2 & 0 & 0.3 & 0 \end{array} $$ Так, не знайшлося жодного голосу за $H_3$, але при цьому $30\%$ експертів вважають, що вірно або $H_2$, або $H_3$.
Крім цього, $\mathbb{H}=\{H_1,H_2,H_3\}$ не отримало жодного голосу на підтримку. Фокальними елементами є $\{H_1\}$, $\{H_2\}$, $\{H_1,H_2\}$, $\{H_2,H_3\}$, а ядро (їх об'єднання) збігається з $\mathbb{H}$.

Довіра

Ключовим для TДШ поняттям є функція довіри підмножини $A$ (belief function). Вона позначається як $\text{Bel}(A)$ і дорівнює сумарній масі всіх підмножин гіпотез, що входять у $A$: $$ \text{Bel}(A) ~=~ \sum_{S\,\mid\, S\subseteq A} m(S) ~=~ m(A)~+~\sum_{S\,\mid\, S\subset A} m(S). $$

◊ Обчислимо в прикладі з трьома гіпотезами значення довіри деяких множин: $$ \begin{array}{lcll} \text{Bel}(H_1) &=& m(H_1) = 0.1,\\ \text{Bel}(H_1,H_2) &=& m(H_1) + m(H_2) + m(H_1,H_2) = 0.1+0.4 + 0.2 = 0.7, \\ \text{Bel}(H_1,H_3) &=& m(H_1) + m(H_3) + m(H_1,H_3) = 0.1+0 + 0 = 0.1, \\ \text{Bel}(H_1,H_2,H_3) &=& 1 \text{ (щось одне істинно)}. \end{array} $$

Функція довіри всіх гіпотез завжди дорівнює одиниці: $\text{Bel}(\mathbb{H})=1$, а довіра до гіпотези дорівнює її масі $\text{Bel}(H_i)=m(H_i)$. Нескладно бачити, що знаючи довіри всіх підмножин, можна відновити їх маси: $$ m(\varnothing)=0,~~~~~~~~~m(A)~=~\text{Bel}(A) - \sum_{S\,\mid\, S\subset A} m(S) ~=~ \sum_{S\,\mid\, S\subseteq A} (-1)^{|A-S|}\,\text{Bel}(S). $$

Зазначимо, що, будь-яка підмножина $B\subset A$ представляє сильніше твердження (більш конкретне), ніж $A$. Зазвичай, воно вимагає більш вагомих доказів для його підтримки. Тим не менш, навіть якщо $m(B)\gt m(A)$, довіра до $A$ завжди буде не нижчою: $\text{Bel}(B)\le \text{Bel}(A)$.

Правдоподібність

Нехай множина $\mathbb{H}$ складається з п'яти гіпотез, а подія (твердження) $A=\{H_1,H_2\}$.
Тоді заперечення $\bar{A}=\{H_3,H_4,H_5\}$. У результаті подія $A$ і її заперечення $\bar{A}$ розбивають простір гіпотез $\mathbb{H}$ на дві неперетинні частини. Зрозуміло, що довіра заперечення $\bar{A}$ дорівнює сумі мас усіх підмножин $2^{\mathbb{H}}$, які не перетинаються з $A$: $$ \text{Bel}(\bar{A}) = \sum_{S\,\mid\,S\cap A = \varnothing} m(S). $$

Множина $2^\mathbb{H}$ розбивається на три частини: усі підмножини $A$ (на рисунку - зелений колір): $\{S\,\mid\, S\subseteq A\}$; усі підмножини його заперечення $\bar{A}$ (червоний колір): $\{S\,\mid\, S\subseteq \bar{A}\}$; і всі підмножини, які перетинаються і з $A$, і з $\bar{A}$ (синій): $\{S\,\mid\,S\cap A\neq\varnothing \,\&\,S\cap \bar{A}\neq\varnothing \,\}$. Сума їх мас (як маса всього $2^\mathbb{H}$) дорівнює одиниці. Тому правдоподібність (degree of plausibility), що дорівнює одиниці, зменшеній на довіру істинності заперечення $A$ можна записати таким чином: $$ \text{Pl}(A) ~=~ 1-\text{Bel}(\bar{A}) ~=~\sum_{S\,\mid\, S \cap A \neq \varnothing}m(S), $$ де сума йде по "синіх" і "зелених" підмножинах, а $\text{Bel}(\bar{A})$ - це сумарна маса "червоних".

Оскільки в $\text{Bel}(A)$ і $\text{Bel}(\bar{A})$ не потрапляють "сині" підмножини, маси яких у загальному випадку відмінні від нуля, приходимо до висновку, що сума довіри твердження і його заперечення не перевищує одиниці: $$ \text{Bel}(A)+\text{Bel}(\bar{A}) \le 1. $$ Власне саме це і потрібно для будь-якого твердження. Наприклад для прикладу з трьома гіпотезами з попереднього розділу, якщо $A=\{H_2\}$, тоді $\text{Bel}(\bar{A})=\text{Bel}(H_1,H_3)$ і $\text{Bel}(A)+\text{Bel}(\bar{A}) = 0.5$.

◊ Обчислимо в прикладі з трьома гіпотезами значення довіри деяких множин: $$ \begin{array}{lcll} \text{Pl}(H_1) &=& m(H_1)+m(H_1,H_2)+m(H_1,H_3)+m(H_1,H_2,H_3) = 0.3,\\ \text{Pl}(H_1,H_2) &=& m(H_1) + m(H_2) + m(H_1,H_2) + m(H_1,H_3)+ m(H_2,H_3)+ m(H_1,H_2,H_3) = 1, \\ \text{Pl}(H_1,H_3) &=& m(H_1) + m(H_3) + m(H_1,H_2)+ m(H_1,H_3)+ m(H_2,H_3)+ m(H_1,H_2,H_3) = 0.6, \\ \text{Pl}(H_1,H_2,H_3) &=& 1. \end{array} $$

Ймовірність $P(A)$ істинності твердження $A$ знаходиться в інтервалі: $ m(A)~\le~\text{Bel}(A)~\le~P(A)~\le~ \text{Pl}(A). $

Правило Демпстера

Часто інформація про підтримку (масу) підмножин надходить з різних незалежних джерел і може бути суперечливою. Правило Демпстера узгоджує між собою таку інформацію. Нехай є два набори мас $m_1(S)$ і $m_2(S)$ для всіх $S\subseteq \mathbb{H}$. В єдину систему мас вони об'єднуються таким чином: $$ m(A) = \frac{1}{\mathcal{N}}\,\sum_{S_1\cap S_2=A} m_1(S_1)\cdot m_2(S_2). $$ Вище перебираються всі пари підмножин $S_1,S_2 \subseteq \mathbb{H}$, перетин яких дає $A\neq\varnothing$. Об'єднана маса $m(A)$ пропорційна сумі добутків мас таких підмножин. Це співвідношення інспіроване звичайною теорією ймовірності, у якій ймовірність спільного настання незалежних подій дорівнює добутку їх ймовірностей.

Нормувальний коефіцієнт $\mathcal{N}$ обчислюється таким чином, щоб сума $m(A)$ по всіх підмножинах $\mathbb{H}$ дорівнювала одиниці: $$ \mathcal{N} ~=~ \sum_{S\subseteq \mathbb{H}}\sum_{S_1\cap S_2=S} m_1(S_1)\cdot m_2(S_2) ~=~ \sum_{S_1\cap S_2\neq \varnothing} m_1(S_1)\cdot m_2(S_2). $$ Набори мас $m_1$, $m_2$ передбачаються нормованими на одиницю, тому: $$ 1 = \sum_{S_1\subseteq \mathbb{H}}m_1(S_1) ~\sum_{S_2\subseteq \mathbb{H}}m_2(S_2) = \sum_{S_1,S_2\subseteq \mathbb{H}} m_1(S_1)m_2(S_2) = \sum_{S_1\cap S_2\neq \varnothing} m_1(S_1)\cdot m_2(S_2) ~~+ \sum_{S_1\cap S_2 = \varnothing} m_1(S_1)\cdot m_2(S_2), $$ де в останній рівності всі пари підмножин $(S_1,S_2)$ розбиті на перетинні і неперетинні. У результаті нормувальний коефіцієнт можна записати в більш зручному для практичних обчислень вигляді: $$ \mathcal{N} ~=~ 1~~-\sum_{S_1\cap S_2 = \varnothing} m_1(S_1)\cdot m_2(S_2). $$ Величина $\mathcal{N}$ є мірою конфлікту наборів $m_1(S)$ і $m_2(S)$, оскільки підсумовує всі неперетинні підмножини $S_1\cap S_2=\varnothing$, які тим не менш у кожному наборі отримали ненульові маси (є "голоси" на їх користь).

Пошук злочинця

Розглянемо приклад, запозичений з Yager, Liu (2008). Нехай є троє підозрюваних у пограбуванні банку: Тоні ($T$), Сміт ($S$) і Дік ($D$). Літня свідкиня місіс Джонсон бачила високу людину біля банку в момент пограбування. Зір у неї не дуже хороший, тому будемо вважати достовірність її показань як $60\%$. Оскільки високий зріст мають Тоні і Дік, то $m_1(T,\,D) = 0.6$. У той же час, інших злочинців у місті немає, місіс Джонсон більше нічого не бачила, тому $m_1(T,\,S,\,D) = 0.4$.

Інший набір свідчень заснований на відеоспостереженні. Хоча злочинець був у масці, камера зафіксувала нечітке зображення його очей, які в $4$ рази частіше були чорними, ніж сірими. Оскільки у Сміта чорні очі, вважаємо, що $m_2(S)=0.8$ і $m_2 (T,\,D) = 0.2$.

$$ m(S) = \frac{1}{\mathcal{N}}\,m_1(T,\,S,\,D)\,m_2(S)=\frac{0.32}{\mathcal{N}},~~~~~~~~~\mathcal{N}=1-m_1(T,\,D)\,m_2(S)=1-0.48~~~~~~\Rightarrow~~~~~m(S)=0.62. $$ Аналогічно: $$ m(T,D) = \frac{0.12+0.08}{1-0.48}=0.38. $$

Наведемо інтервали винності підозрюваних окремо по кожному джерелу свідчень і їх об'єднання: $$ \begin{array}{ccccc} ~ & \text{місіс Джонсон} & \text{відеоспостереження} & \text{об'єднання} \\ \hline T & [0.0,\,1.0] & [0.0,\,0.2] & [0.00,\,0.62] \\ S & [0.0,\,0.4] & [0.8,\,0.8] & [0.62,\,0.62] \\ D & [0.0,\,1.0] & [0.0,\,0.2] & [0.00,\,0.62] \end{array} $$

Зазначимо, що правило Демпстера у сильно конфліктуючих ситуаціях може призводити до дивних результатів. Нехай, наприклад, є три підозрювані $Т,D,S$ і два свідки $W_1$ і $W_2$, які висловлюють такі судження: $$ \begin{array}{lll} W1:& m(T)=0.9 & m(D)=0.1\\ W2:& m(S)=0.9 & m(D)=0.1\\ \end{array} $$ Застосування правила Демпстера дає $\mathcal{N}=0.99$ і $m(D)=1$, хоча обидва свідки приписали гіпотезі $m(D)$ малі маси.

Алгоритм класифікації

У роботі Chena et.,al. (2014) був запропонований алгоритм класифікації, побудований на основі правила Демпстера. Як фрейм розрізнень $\mathbb{H}$ беруться гіпотези $H_k$ про належність об'єкта до $k$-го класу.

У найпростішому випадку двох класів $\mathbb{H}=\{H_1,H_2\}$ алгоритм працює таким чином. Для кожної ознаки (окремо) будуються масові функції у вигляді сигмоїд $m_i(H_1)=1/(1+e^{v_i-t_i})$, $m(H_2)=1-m(H_1)$, де $v_i$ - значення $i$-ї ознаки, а $t_i$ - поріг (параметр навчання). Потім масові функції параметрів перемножуються (правило Демпстера) і нормуються. Отримана масова функція використовується як класифікатор: якщо $m(H_1) \gt m(H_2)$, то вибираємо клас $H_1$.

Існує реалізація цього алгоритму на Python.

Література