Developing probabilistic graphical models for identifying text patterns and semantics

In this dissertation, we discuss a new probabilistic graphical model called the data sequence dependence model (DSDM). This model is derived from the joint probability function for a sequence of class assignments given a sequence of input symbols (words) under fewer and different conditional independence assumptions than the commonly used probabilistic graphical models, such as hidden Markov models (HMMs), maximum entropy Markov models (MEMMs), and conditional random fields (CRF s). Our model accounts for the data sequence dependency rather than the class sequence dependency. In order to find a sequence of optimal class assignments for a sequence of input symbols, the HMM and CRF models have to employ dynamic programming. In contrast to these models, our method does not need to employ dynamic programming. Although dynamic programming is an efficient optimization technique, our model leads to an algorithm whose computational complexity is less than dynamic programming and whose performance is just as good or better. Based on DSDM, we develop algorithms for identifying semantics in texts. In this research, semantics consists of three types of text patterns. They are the semantic arguments of a verb, the sense of a polysemous word, and the noun phrases of a sentence. In addition, two other probabilistic graphical models are described. They are called the context independence model (CIM) and the class sequence dependence model (CSDM). These models have the same economic gain function as DSDM. However, they are derived under the different conditional independence assumptions. Finally, statistical testing methodologies are employed to validate these models. For our task of identifying semantic patterns, we compare each pair of the models by testing the null hypothesis that the two models are equally good at identifying semantic patterns against the alternative hypothesis that one model is better able to identify semantic patterns. The resulting p-value shows that DSDM is better able to identify semantic patterns than the other models.