The Classification Using the Hierarchy and Exclusion Graphs

Abstract

This thesis first reviews the Conditional Random Fields (CRF) model. Then, we introduce the Hierarchy and Exclusion (HEX) graphs and describe the probabilistic classification model based on these graphs (HEX model). Next, we demonstrate that the HEX model is a special case of the CRF model. This allows us to train the HEX model using the framework of the CRF model. After that, we explain the algorithm for this process that calculates the marginals (Exact Inference algorithm). The main objective of the research was to design the sparsification and densification steps for the exact inference algorithm. We propose algorithms for these steps. Then, we introduce the betting model that is modified HEX model. We calculate marginals for this model using the Exact Inference algorithm without sparsification and densification steps. After that, we perform the same experiments using these steps. Finally, by estimating the execution time for the experiments we demonstrate that using the sparsification and densification steps in the exact inference algorithm boosts its performance.....