Abstract
The convenience, intuitiveness, and versatility of Dempster-Shafer (DS) theoretic models of data uncertainty make DS evidence theory an ideal framework for reasoning under uncertainty and decision making in artificial intelligence (AI) applications. However, a major criticism cast towards DS theoretic (DST) evidential reasoning is the heavy computational burden it entails. If the advantages offered by DS theory are to be fully realized, it is essential that one explores efficient data structures and algorithms that can be used for DST operations and computations. We present a novel general computational framework for exactly this purpose. We develop three representations — DS-Vector, DS-Matrix, and DS-Tree — which allow DST computations to be performed with significantly less time and space complexity. We provide the algorithms to carry out DST operations as well as to work with dynamic frames. These three representations can also be utilized as tools for visualizing DST models and computations. A new strategy, which we refer to as REGAP, which allows REcursive Generation of and Access to Propositions, is introduced and harnessed in the development of this framework and computational algorithms. As data streams expand and the associated DST computations become more complex, devising tools to visualize these complex computations is essential to augment decision-making and reasoning. We introduce two new visualization tools, DS-LASIC and DS-TRISEV, and propose a novel family of geometrical diagrams, which we refer to as nested layered diagrams, for the flexible representation of DST quantities. Based on the DS-Tree from our computational framework and the DS-LASIC tool, we generate a new class of graphical diagrams in the family of nested layered diagrams. These new diagrams, which we refer to as concentric layered diagrams, satisfy certain symmetric and concentric properties, and address the limitations of illustrating higher order DST computations. Also introduced are variations of the proposed diagrams, which can be employed to design new computational models and efficient algorithms. As in Bayesian probability theory, the conditional operation plays a pivotal role in DST strategies for evidence updating and fusion. Again, a major limitation in applying DST techniques for reasoning under uncertainty is the absence of a feasible computational framework to overcome the prohibitive computational burden this conditional operation imposes, which is a non-deterministic polynomial-time hard (NP-hard) problem. We address this critical challenge via two novel generalized conditional computational models — DS-Conditional-One and DS-Conditional-All — which allow significantly less computational time and space complexity when computing conditional mass and belief. They provide deeper insight into the DST conditional itself and so act as a valuable visualization tool during conditional computation. We also provide two highly efficient exact dynamic programming algorithms for computing all the conditionals generated from consonant bodies of evidence. The time and space complexities of these novel algorithms are linear for computing all the conditional beliefs, and hence they significantly outperform the exponential time and space complexity requirements of the brute force approach and other currently available conditional computation strategies. We provide implementations for computing both the Dempster’s conditional and the Fagin-Halpern conditional, the two most widely utilized DST conditional strategies. With the increased automation required by the next levels of autonomous driving tasks as identified by experts in the field, there is heightened interest in how to manage uncertain and exception conditions. As an application of our computational framework, we propose a robust event prediction model which harnesses DST framework’s ability to capture and account for evidence uncertainties throughout the decision-making pipeline so that a more informed decision, calibrated according to the underlying uncertainty, can be provided. We provide a thorough analysis and experimental validation of the utility, efficiency, and implementation of the proposed data structures and algorithms presented in this dissertation. A collection of computational libraries complementing our work is made available as an outcome of this research work.