Browsing by Author "Streicher, Simon"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Incremental inference on higher-order probabilistic graphical models applied to constraint satisfaction problems
    (Stellenbosch : Stellenbosch University, 2022-04) Streicher, Simon; Du Preez, Johan; Stellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering.
    ENGLISH ABSTRACT: Probabilistic graphical models (PGMs) are used extensively in the probabilistic reasoning domain. They are powerful tools for solving systems of complex relationships over a variety of probability distributions, such as medical and fault diagnosis, predictive modelling, object recognition, localisation and mapping, speech recognition, and language processing [5, 6, 7, 8, 9, 10, 11]. Furthermore, constraint satisfaction problems (CSPs) can be formulated as PGMs and solved with PGM inference techniques. However, the prevalent literature on PGMs shows that suboptimal PGM structures are primarily used in practice and a suboptimal formulation for constraint satisfaction PGMs. This dissertation aimed to improve the PGM literature through accessible algorithms and tools for improved PGM structures and inference procedures, specifically focusing on constraint satisfaction. To this end, this dissertation presents three published contributions to the current literature: a comparative study to compare cluster graph topologies to the prevalent factor graphs [1], an application of cluster graphs in land cover classification in the field of cartography [2], and a comprehensive integration of various aspects required to formulate CSPs as PGMs and an algorithm to solve this formulation for problems too complex for traditional PGM tools [3]. First, we present a means of formulating and solving graph colouring problems with probabilistic graphical models. In contrast to the prevailing literature that mostly uses factor graph configurations, we approach it from a cluster graph perspective, using the general-purpose cluster graph construction algorithm, LTRIP. Our experiments indicate a significant advantage for preferring cluster graphs over factor graphs, both in terms of accuracy as well as computational efficiency. Secondly, we use these tools to solve a practical problem: land cover classification. This process is complex due to measuring errors, inefficient algorithms, and low-quality data. We proposed a PGM approach to boost geospatial classifications from different sources and consider the effects of spatial distribution and inter-class dependencies (similarly to graph colouring). Our PGM tools were shown to be robust and were able to produce a diverse, feasible, and spatially-consistent land cover classification even in areas of incomplete and conflicting evidence. Lastly, in our third publication, we investigated and improved the PGM structures used for constraint satisfaction. It is known that tree-structured PGMs always result in an exact solution [12, p355], but is usually impractical for interesting problems due to exponential blow-up. We, therefore, developed the “purge-and merge” algorithm to incrementally approximate a tree-structured PGM. This algorithm iteratively nudges a malleable graph structure towards a tree structure by selectively merging factors. The merging process is designed to avoid exponential blow-up through sparse data structures from which redundancy is purged as the algorithm progresses. This algorithm is tested on constraint satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro and manages to outperform other PGM-based approaches reported in the literature [13, 14, 15]. Overall, the research reported in this dissertation contributed to developing a more optimised approach for higher order probabilistic graphical models. Further studies should concentrate on applying purge-and-merge on problems closer to probabilistic reasoning than constraint satisfaction and report its effectiveness in that domain.