Stochastic And-Or Grammars: A Unified Framework and Logic Perspective

Formal grammars are a popular class of knowledge representation that is traditionally confined to the modeling of natural and computer languages. However, several extensions of grammars have been proposed over time to model other types of data such as images [1, 2, 3] and events [4, 5, 6]. One prominent type of extension is stochastic And-Or grammars (AOG) [2]. A stochastic AOG simultaneously models compositions (i.e., a large pattern is the composition of several small patterns arranged according to a certain configuration) and reconfigurations (i.e., a pattern may have several alternative configurations), and in this way it can compactly represent a probabilistic distribution over a large number of patterns. Stochastic AOGs can be used to parse data samples into their compositional structures, which help solve multiple tasks (such as classification, annotation, and segmentation of the data samples) in a unified manner. This work was supported by the National Natural Science Foundation of China (61503248).