30 Years after the Seminal Paper of Dempster
- A Fresh Look at the Evidence Theory

• M.A. Kłopotek <klopotek@ipipan.waw.pl> :
  Metody identyfikacji i interpretacje struktur rozkładów przekonań w teorii Dempstera-Shafera.
  (in Polish: Methods of Identification and Interpretations of Belief Distributions in the Dempster-Shafer Theory).
  Publisher: Institute of Computer Science, Polish Academy of Sciences,
  Warsaw, Poland, 1998, (236 pages) ISBN 83-900820-8-x.

• Available from the Publisher, (price about 18 new Polish Zloty)

• Also available as winzipped Postscript file (about 480 kb)
• Keywords:
  new (the only known correct) frequecy interpretation of the theory of belief functions (DST),
  new (the only known) statistical methods for testing of conditional independence in DST,
  new graphoidal structure for representation of joint DST belief distribution,
  new (the only known) methods of identification of DST belief networks from data,
  new methods of generation of joint DST belief distribution from DST belief networks
  

From the history of computer science

• 1948 - Development of computers in Poland began with the formation of the Group ior Mathematical Apparatus of the Mathematical Institute in Warsaw.
• 1958 - First Polish digital computer XYZ! is working
• 1968 - Dempster publishes his first papers on the theory of belief functions, proposing (as it turned out later an incorrect) interpretation of belief and plausibility as lower and upper bounds on event probability
• 1998 - The first book on the first correct frequecy interpretation of the theory of belief functions published.

Metody identyfikacji i interpretacje struktur rozkładów przekonań w teorii Dempstera-Shafera

Mieczysław A. Kłopotek

<klopotek@ipipan.waw.pl>

Wprowadzenie

Jednym z poważnych wyzwań stawianych systemom informatycznym jest wspomaganie procesów podejmowania decyzji. Często model procesu decyzyjnego jest bardzo złożony i niepełny, co skłania lub nawet zmusza do proponowania uproszczonego i sparametryzowanego modelu rzeczywistości. Uproszczenie obarcza model na ogół określonym stopniem niepewności. Jednym z pierwszych modeli przeznaczonych do wspomagania decyzji w systemach z czynnikiem niepewności był model regułowy zaimplementowany w systemie MYCIN.

Wprawdzie system regułowy posiadał szereg zalet, ale wady takie jak brak relacji między współczynnikami pewności tego modelu a obserwowanymi częstościami zdarzeń w modelowanych procesach skłoniły do poszukiwania alternatywnych modeli reprezentacji wiedzy niepełnej i/lub niepewnej.

Dużym zainteresowaniem cieszyły się tzw. sieci bayesowskie, reprezentujące w graficzny sposób łączny rozkład prawdopodobieństwa, m.in. ze względu na oczywistą relację między prawdopodobieństwem a częstością warunkową. Dla sieci bayesowskich opracowano kilka metod efektywnego wnioskowania z wykorzystaniem ich grafoidalnej struktury. Opracowano też szereg metod odkrywania sieci bayesowskich z danych. Uogólniono definicję sieci bayesowskich do tzw. struktur grafoidalnych, w których można jakościowo wnioskować o warunkowej zależności i niezależności zmiennych.

W powszechnym przekonaniu formalizm probabilistyczny nie jest w stanie wyrazić wielu form niepewności m.in. problem częściowej ignorancji co do wartości atrybutu. Dlatego model wnioskowania bayesowskiego modyfikowano tworząc modele teorii zbiorów rozmytych, zbiorów przybliżonych, teorii posybilistycznych czy teorii funkcji przekonania (zwanej teorią Dempstera-Shafera). Dążono równocześnie do uogólnienia grafoidalnych metod wnioskowania bayesowskiego na nowe formalizmy.

Badania formalne teorii Dempstera-Shafera (DS) wskazywały, że oferuje ona szereg ważnych korzyści metodologicznych takich jak: zdolność do reprezentowania ignorancji w sposób prosty i bezpośredni, spójność z klasyczną teorią prawdopodobieństwa, zgodność z logiką boolowską oraz znośną złożoność obliczeniową opracowanych metod wnioskowania w tzw. strukturach hiperdrzew (Hiperdrzewo jest specyficzną reprezentacją łącznego rozkładu przekonań w postaci złożenia składowych funkcji przekonania).

Uważa się, że teoria DS jest w stanie objąć statystykę zbiorów losowych i może służyć jako narzędzie do reprezentacji niekompletnej wiedzy statystycznej.

Założenia i cel książki

W opinii niektórych badaczy przyczyna niepowodzeń w tworzeniu interpretacji częstościowej teorii DS leży w subiektywnym charakterze funkcji przekonania, która miałaby odzwierciedlać ludzki sposób myślenia. Prawdopodobnie jednak przyczyną niepowodzeń jest niedostateczne zbadanie podstaw teoretycznych funkcji przekonania. Zauważmy bowiem, że nie zbadano gruntownie relacji między niezależnością brzegową i warunkową zmiennych a możliwością zwartej reprezentacji funkcji przekonania. Nie zaproponowano takiej definicji warunkowej funkcji przekonania, w której niezależność warunkowa od zmiennej automatycznie umożliwiłaby eliminację tej zmiennej z reprezentacji warunkowej funkcji przekonania. Nie analizowano dostatecznie problemu ujemnych mas "prawdopodobieństwa bazowego" w warunkowej funkcji przekonania i nie zaproponowano takiej miary DS, która dla warunkowej funkcji przekonania byłaby nieujemna i mogłaby być w naturalny sposób wyliczana z bezwarunkowej funkcji masy (tzn. funkcji masy sprzed operacji warunkowania względem zmiennej) i miałaby charakter zbliżony do funkcji prawdopodobieństwa warunkowego (suma na danym poziomie zmiennej warunkującej równa 1). żadna z dotychczas znanych miar niepewności w teorii DS, tj. ani funkcja masy ("bazowego prawdopodobieństwa") m, ani funkcja przekonania Bel, ani funkcja domniemania Pl ani zespolenia Q nie spełnia tego postulatu. Nie rozważano relacji między hipergrafową reprezentacją funkcji przekonania a grafoidalną reprezentacją niezależności warunkowej w teorii DS, w szczególności problemu, czy są one w aspekcie niezależności zmiennych równoważne czy też jedna ma większą siłę ekspresji niż druga. Nie badano relacji między składowymi funkcji przekonania w reprezentacji hipergrafowej ani w reprezentacji hiperdrzewa a lokalnymi własnościami (rzutami) łącznego rozkładu przekonań. Z punktu widzenia potencjalnych algorytmów odkrywania wiedzy z danych brakiem teoretycznym jest to, że własności grafoidalne udowodniono dla zbyt wąskiej klasy funkcji przekonania - tzw. pozytywnych funkcji przekonania. Klasa ta implikuje konieczność obecności w danych obiektów, o których zupełnie nic nie wiemy, natomiast wyklucza tzw. bayesowskie funkcje przekonania czyli populacje obiektów, których wszystkie wartości atrybutów są znane, co jest zaprzeczeniem zdroworozsądkowej intuicji w wypadku odkrywania wiedzy z danych.

Należy podkreślić, że brak spójnej interpretacji częstościowej funkcji przekonania oznacza w praktyce niecelowość stosowania tej teorii do wnioskowania w systemach konsultacyjnych, ponieważ:

• niemożliwe jest wnioskowanie z danych,
• nie jest możliwe empiryczne zweryfikowanie poprawności modelu rzeczywistości reprezentowanego w formalizmie teorii DS, w tym struktury niezależności zmiennych ani składowych funkcji przekonania,
• nie jest możliwe poprawne przygotowanie danych wejściowych (pochodzących z obserwacji) do wnioskowania,
• nie jest możliwe odniesienie wyników wnioskowania do danych empirycznych,
• bezprzedmiotowym jest opracowany dla teorii DS mechanizm uzasadniania wyników wnioskowania,
• niemożliwa jest walidacja tzw. wnioskowania jakościowego czyli o niezależności (brzegowej i warunkowej) zmiennych,
• niemożliwe jest opracowanie metod i algorytmów identyfikacji struktury grafoidalnej funkcji przekonania DS z danych, która jest podstawą efektywnych procedur wnioskowania w teorii DS.

1. Gruntowne zbadanie relacji między niezależnością a zwartą reprezentacją funkcji przekonania.
2. Zaproponowanie nowej definicji warunkowej funkcji przekonania, umożliwiającej usunięcie z reprezentacji warunkowej funkcji przekonania zmiennej warunkującej, od której zmienna warunkowana jest niezależna względem innych zmiennych warunkujących.
3. Analiza problemu ujemnych mas i opracowanie nowej miary niepewności, która dla warunkowej funkcji przekonania będzie odpowiednikiem warunkowej funkcji prawdopodobieństwa.
4. Zaproponowanie nowej reprezentacji łącznego rozkładu przekonań w formie grafoidalnej, sieci przekonań, w której składowe funkcje przekonania będą mogły być wyliczane z rzutów łącznego rozkładu przekonań.
5. Zbadanie relacji zawierania między hipergrafową reprezentacją a proponowaną reprezentacją grafoidalną funkcji przekonania w aspekcie niezależności warunkowej.
6. Udowodnienie własności grafoidalnych dla szerszej klasy funkcji przekonania, obejmującej bayesowskie funkcje przekonania.
7. Adaptacja i uogólnienie znanych metod identyfikacji sieci bayesowskich z danych na nowe sieci przekonań DS.

Badania i wyniki badań

Nadano wnioskowaniu w teorii Dempstera-Shafera sens empiryczny definiując go jako proces przeetykietowywania populacji. Udowodniono, że w procesie przeetykietowania populacja zachowuje się tak, jak przy składaniu ewidencji regułą Dempstera (tj. jak podczas wnioskowania w teorii DS). W ten sposób uzyskano nie znany dotąd model empiryczny procesu wnioskowania w teorii DS. "Modelem" bazy wiedzy może być nieetykietowana populacja obiektów. Obserwacje można uwzględnić jako "funkcje procesu przeetykietowania". Wnioskowanie należy rozumieć jako proces przeetykietowania populacji zgodnie z "funkcją procesu przeetykietowania". Wynikiem wnioskowania będą funkcje przekonania wyliczane dla interesujących zmiennych bezpośrednio z etykietowanej populacji.

Rozważano problem brzegowej niezależności zmiennych i stwierdzono, że wbrew popularnym opiniom w ogólnym przypadku niezależność brzegowa nie implikuje możliwości odtworzenia łącznego rozkładu przekonań dla zmiennych z brzegowych rozkładów przekonań. Badania wykazały, że dopiero założenie o kompozycyjnym pomiarze wartości zmiennych (niezależnym pomiarze dla poszczególnych zmiennych) pozwala na odtworzenie rozkładu łącznego z rozkładów brzegowych. Znaleziono interpretację i uzasadnienie pojęcia pustego rozszerzenia w świetle statystycznej niezależności między zmiennymi w teorii DS.

Zaproponowano nową koncepcję warunkowej funkcji przekonania (tzw. funkcji antywarunkowej) i zbadano podstawowe własności. Wykazano, że jeśli zmienne X i Y są niezależne od Z, to w reprezentacji warunkowej funkcji przekonania X względem Z i Y można pominąć zmienną Y, co nie było możliwe dla warunkowych funkcji przekonania zdefiniowanych przez innych autorów.

Wprowadzono pojęcie nowej miary przekonań: kumulacyjnej funkcji masy K, która dla warunkowych funkcji przekonania przyjmuje wartości nieujemne i ma charakter zbliżony do funkcji prawdopodobieństwa warunkowego (suma na danym poziomie zmiennej warunkującej równa 1). Na jej bazie zaproponowano testy statystyczne na dempsterowsko-shaferowską niezależność warunkową zmiennych. Na przykładzie numerycznym pokazano, że niezależność warunkowa DS różni się od tradycyjnej probabilistycznej niezależności warunkowej.

W oparciu o nowe pojęcie warunkowej funkcji przekonania zaproponowano nowy sposób reprezentacji funkcji przekonania w postaci sieci przekonań, analogicznej dla sieci bayesowskiej. Zbadano jej własności. Wykazano, że podsieci tej sieci reprezentują łączne lub warunkowe rozkłady przekonań w podzbiorach zbioru zmiennych. Stąd składowe funkcji przekonania posiadają - w przeciwieństwie do reprezentacji hipergrafowej - bezpośrednią lokalną interpretację w danych. Dla tej sieci grafoidalna niezależność warunkowa (tzw. d-separacja) implikuje niezależność warunkową w reprezentowanej funkcji przekonania, a grafoidalna zależność warunkowa implikuje istnienie funkcji przekonania o danej strukturze takiej, że w tej funkcji obowiązuje dana zależność. Z przeprowadzonych badań wynika, że nowa sieć posiada własności grafoidalne dla funkcji przekonania charakteryzujących się tym, że funkcja zespolenia przybiera dodatnie wartości dla każdego zbioru o liczności 1. Ta klasa funkcji obejmuje tzw. bayesowskie funkcje przekonania. Ponieważ opracowano testy statystyczne na niezależność warunkową z danych, istnieje możliwość statystycznej weryfikacji na danych rzeczywistych słuszności jakościowej modelu funkcji przekonania w postaci sieci przekonań poprzez badanie, czy d-separacja w sieci bayesowskiej jest uzasadniona przez niezależność warunkową w danych.

Zbadano także relację między hipergrafową reprezentacją funkcji przekonania a nową siecią przekonań. Każdą sieć nowego typu da się przetransformować do równoważnej postaci hipergrafowej, ale nie vice versa. Jednakże wiadomo, że wnioskowanie w teorii DS nie odbywa się w strukturach hipergrafowych, lecz w ich podzbiorze, tzn. w strukturach hiperdrzew. Przeprowadzone badania pokazały, że każde hiperdrzewo da się przedstawić w postaci nowej sieci. Tak więc dla celów wnioskowania nowa sieć przekonań zawiera wystarczającą informację o rozkładzie przekonań. Jest zatem uzasadnione identyfikowanie struktury łącznego rozkładu przekonań w postaci nowej sieci przekonań. Badania wykazały również, że hiperdrzewo otrzymane z nowej sieci przekonań upraszcza proces przetwarzania prostych kwerend do bazy wiedzy DS, ponieważ do odpowiedzi na kwerendy nie zawsze jest potrzebne wnioskowanie w całym hiperdrzewie, lecz wystarczy wnioskowanie w pewnej jego części.

Badano możliwość identyfikacji nowej sieci przekonań z danych. Nie były dotychczas znane żadne metody identyfikacji struktur funkcji przekonania z danych: ani dla struktur w postaci hipegrafu, ani hiperdrzewa, ani struktur grafoidalnych dla tzw. pozytywnych funkcji przekonania. Z tego względu konstruując metody identyfikacji nowej sieci przekonań z danych posłużono się analogią między nową siecią przekonań a sieciami bayesowskimi. Na bazie istniejących algorytmów dla probabilistycznych sieci bayesowskich opracowano algorytmy odkrywania struktur sieci przekonań z danych korzystając z nowo opracowanych testów na niezależność brzegową i warunkową dla funkcji przekonania DS. Opracowano algorytmy zarówno dla przypadku znajomości wszystkich istotnych zmiennych jak i w wypadku istnienia zmiennych ukrytych.

Rozważano klasy równoważności między różnymi sieciami przekonań ze względu na reprezentację tej samej jakościowej informacji o warunkowej niezależności zmiennych, gdyż w powszechnym przekonaniu, jeśli orientacja danego łuku łączącego zmienne jest taka sama we wszystkich sieciach klasy równoważności, to wyraża ona relację przyczyna-skutek. W ramach badań nad algorytmem SGS odkrywania probabilistycznych sieci bayesowskich z danych, oprócz dostosowania do teorii DS, poszerzono jego podstawy teoretyczne w taki sposób, że można było opracować nowy algorytm generujący graf częściowo zorientowany, z którego przez orientację nieskierowanych łuków można otrzymać wszystkie sieci przekonań należące do jednej klasy równoważności. Wprowadzono pojęcie tzw. p-d-separacji w grafie częściowo zorientowanym. Udowodniono równoważność p-d-separacji w grafie częściowo zorientowanym z d-separacją w każdej sieci przekonań z klasy równoważności.

W ramach prac nad algorytmem odkrywania sieci przekonań z danych w wypadku istnienia zmiennych ukrytych stwierdzono błędność znanego z literatury algorytmu FCI odkrywania sieci bayesowskich z danych i zaproponowano metodę jego poprawienia oraz dostosowania do identyfikacji sieci przekonań DS z danych. W związku z błędem w algorytmie FCI oraz faktem, iż w literaturze dowód poprawności innego algorytmu, tzw. CI, opiera się na dowodzie algorytmu FCI, w ramach przystosowania algorytmu CI do odkrywania sieci przekonania DS z danych zaproponowano nowy dowód poprawności algorytmu CI. Zaproponowano również nowy algorytm (r(k)CI) odkrywania sieci przekonań z danych przy założeniu górnego pułapu stopnia badanej warunkowej niezależności wykazując, że efekty pominięcia wyższych niezależności dadzą się poprawnie interpretować jako zmienne ukryte.

Rozważano problemy inżynierskie związane z konstrukcją systemu ekspertowego opartego o nową koncepcję sieci bayesowskich: problem generacji próbek losowych z nowej sieci przekonań, dodawanie nowej wiedzy w postaci wyrażeń logicznych oraz wnioskowanie z danych.

Przeanalizowano istniejące i zaproponowano nowe algorytmy generowania próbki losowej z łącznego rozkładu przekonań. Znane algorytmy generowania próbek losowych działają w oparciu o strukturę hipergrafową, co prowadzi do tzw. konfliktów strukturalnych, w wyniku których pojedynczy element próbki musi być generowany wielokrotnie. Nie jest także możliwe zadanie z góry warunkowych niezależności między zmiennymi. Nowe algorytmy pozwalają na generację próbki o z góry zadanej strukturze niezależności zmiennych i eliminują potrzebę wielokrotnej generacji pojedynczego elementu próbki, ponieważ wykorzystują nowo opracowaną sieciową reprezentację łącznego rozkładu przekonań.

Opracowane nowe metody generacji próbek losowych z danych w połączeniu z interpretacją funkcji przekonania z danych oraz interpretacją procesu wnioskowania mogą służyć do weryfikacji działania maszyny wnioskującej w systemie ekspertowym. Mogą też być wykorzystane do empirycznej weryfikacji algorytmów identyfikacjisieci przekonań DS z danych. W ramach rozprawirycznie badano w ten sposób zachowanie algorytmu opartego o idee Chow/Liu oraz algorytmu opartego o idee SGS: najpierw z rozkładu o zadanej strukturze sieci przekonań wygenerowano próbkę losową, a następnie odtwarzano strukturę rozkładu za pomocą wspomnianych algorytmów. Zgodnie z oczekiwaniem algorytm oparty o idee SGS odtwarzał z dużej próbki strukturę rozkładu z dokładnością do klasy równoważności, zaś algorytm oparty o idee Chow/Liu znajdował drzewo w strukturze sieci zarówno dla małej jak i dużej próbki.

Zaproponowano metodę wnioskowania z danych w warunkach istnienia dodatkowej wiedzy w postaci wyrażeń logicznych.

Podsumowanie

• Opracowano metody identyfikacji struktur rozkładów przekonań z danych w teorii Dempstera-Shafera w postaci sieci przekonań o własnościach grafoidalnych.
• Opracowano prawidłową interpretację częstościową łącznego rozkładu przekonań, rozkładów cząstkowych w strukturze funkcji przekonania oraz procesów wnioskowania w teorii Dempstera-Shafera.
• Zbadano relację między niezależnością a zwartą reprezentacją funkcji przekonania i wyróżniono klasę funkcji przekonania, dla której niezależność implikuje zwartą reprezentację.
• Metody identyfikacji struktur rozkładów przekonań z danych opracowano poprzez adaptację i uogólnienie znanych metod identyfikacji sieci bayesowskich z danych na nowe sieci przekonań DS, a także przez opracowanie nowych algorytmów.
• Zaproponowano nową definicję warunkowej funkcji przekonania, umożliwiającą usunięcie z reprezentacji warunkowej funkcji przekonania zmiennej warunkującej, od której zmienna warunkowana jest niezależna względem innych zmiennych warunkujących.
• Zaproponowano nową miarę niepewności K, która dla warunkowej funkcji przekonania jest odpowiednikiem warunkowej funkcji prawdopodobieństwa, tzn. jest nieujemna i sumuje się do 1 na każdym poziomie zmiennej warunkującej.
• Zaproponowano nową reprezentację łącznego rozkładu przekonań w formie sieci przekonań o własnościach grafoidalnych. Składowe funkcje przekonania tej sieci są warunkowymi funkcjami przekonania i dlatego mogą być wyliczane z rzutów łącznego rozkładu przekonań.
• Stwierdzono, że zaproponowana sieć przekonań zawiera wszystkie informacje o niezależności zmiennych, co hiperdrzewo reprezentujące ten sam rozkład. Dlatego identyfikacja nowej sieci zamiast hipergrafu zapewnia taką samą efektywność wnioskowania w strukturach hipergrafowych.
• Udowodniono własności grafoidalne dla klasy funkcji przekonania, obejmującej bayesowskie funkcje przekonania.
• Nowa interpretacja częstościowa funkcji przekonania umożliwia wnioskowanie z danych.
• Interpretacja ta umożliwia empiryczne zweryfikowanie poprawności modelu rzeczywistości reprezentowanego w formalizmie teorii DS, w tym struktury niezależności zmiennych oraz składowych funkcji przekonania.
• Nowa interpretacja pozwala na poprawne przekazanie danych wejściowych do procesu wnioskowania w teorii DS i pozwala na odniesienie wyników wnioskowania do danych empirycznych.
• Nowa interpretacja nadaje sens empiryczny uzasadnieniom wyników wnioskowania, generowanym przez maszynę wnioskującą DS.
• Nowa interpretacja zezwala na walidacją tzw. wnioskowania jakościowego czyli o niezależności (brzegowej i warunkowej) zmiennych na podstawie struktur grafoidalnych.
• Nowa interpretacja umożliwiła opracowanie kilku metod identyfikacji struktur rozkładów przekonań z danych i otwiera możliwości prowadzenia dalszych prac nad nowymi metodami i algorytmami identyfikacji struktur funkcji przekonania DS z danych.

Orientacyjna cena - ok. 18 zł.