Jag accepterar att kakor lagras på min dator

Läs mer

Dempster´s rule for evidence ordered in a directed acyclic graph.

Dempster´s rule for evidence ordered in a directed acyclic graph. Beställ tryckt exemplar Lägg i kundvagnen
Författare: Bergsten Ulla, Schubert Johan
Ort: Stockholm
Sidor: 30
Utgivningsår: 1992
Publiceringsdatum: 1992-01-28
Rapportnummer: (FOA C 20857-2.7)
Nyckelord Artificial intelligence, decision, support systems, belief functions, Dempster-Shafer theory, evidential reasoning, uncertainty, directed acyclic graph, computational complexity, anti-submarine warfare
Sammanfattning Dempster-Shaferteorien, vilken är ett sätt att hantera osäker information, baserar sig på att man har evidenser för och/eller emot en eller flera olika utsagor. Dempster-Shaferteorin innehåller en regel för hur dessa evidenser skall vägas samman, Dempsters regel. Denna rapport presenterar en ny algoritm med lägre beräkningskomplexitet för Dempsters regel i fallet med evidenser ordnade i en riktad acyklisk graf än för den klassiska steg for steg användningen av Dempsters regel. Detta är problemet när vi för varje par av evidenser har en evidens emot den samtidiga tron på båda utsagorna. De ursprungliga evidenserna är belägna på noderna och de nya på mellanliggande kanter. Den nya algoritmen vilken uttalar sig om hela färdvägar genom grafen är O(n.4n), jämfört med O(2n2) för den klassiska algoritmen. Efter att ha gjort en detaljerad presentation av tankarna bakom den nya algoritmen drar vi slutsatsen att det är möjligt att uttala sig utan approximation om hela färdvägar genom en riktad acyklisk graf inte endast för de minsta problemen.
Abstract Dempster-Shafer theory, which is a way to manage uncertain information, is based upon that one has evidences for and/or against one or more different propositions. Dempster-Shafer theory contains a rule for the fusion of these evidences, Dempster´s rule. This report presents a new algorithm with lower computational complexity for Dempster´s rule in the case of evidence ordered in a directed acyclic graph than for the classic step by step application of Dempster´s rule. This is the problem when we for every pair of evidences have an evidence against the simultaneous belief in both propositions. The original evidences are situated on the vertices and the new ones are situated on the intermediate edges. The new algorithm which reasons about complete paths through the graph is O(n.4n), compared to O(2n2) of the classic algorithm. After having made a detailed presentation of the reasoning behind the new algorithm we conclude that it is feasible to reason without any approximation about complete paths through a directed acyclic graph not only for the smallest problems.

Kundvagn

Inga rapporter i kundvagnen

FOI, Totalförsvarets forskningsinstitut

FOI
Totalförsvarets forskningsinstitut
164 90 Stockholm

Tel: 08-555 030 00
Fax: 08-555 031 00

Orgnr: 202100-5182