Sum-product networks: A survey <s> VII. Applications <s> The key limiting factor in graphical model inference and learning is the complexity of the partition function. We thus ask the question: what are general conditions under which the partition function is tractable? The answer leads to a new kind of deep architecture, which we call sum-product networks (SPNs). SPNs are directed acyclic graphs with variables as leaves, sums and products as internal nodes, and weighted edges. We show that if an SPN is complete and consistent it represents the partition function and all marginals of some graphical model, and give semantics to its nodes. Essentially all tractable graphical models can be cast as SPNs, but SPNs are also strictly more general. We then propose learning algorithms for SPNs, based on backpropagation and EM. Experiments show that inference and learning with SPNs can be both faster and more accurate than with standard deep networks. For example, SPNs perform image completion better than state-of-the-art deep networks for this task. SPNs also have intriguing potential connections to the architecture of the cortex. <s> BIB001 </s> Sum-product networks: A survey <s> VII. Applications <s> A new deep architecture MSPN is proposed for image segmentation.Multiscale unary potentials are used to model image spatial layouts.A superpixel-based refinement method is used to improve the parsing results. Semantic image segmentation is challenging due to the large intra-class variations and the complex spatial layouts inside natural scenes. This paper investigates this problem by designing a new deep architecture, called multiscale sum-product network (MSPN), which utilizes multiscale unary potentials as the inputs and models the spatial layouts of image content in a hierarchical manner. That is, the proposed MSPN models the joint distribution of multiscale unary potentials and object classes instead of single unary potentials in popular settings. Besides, MSPN characterizes scene spatial layouts in a fine-to-coarse manner to enforce the consistency in labeling. Multiscale unary potentials at different scales can thus help overcome semantic ambiguities caused by only evaluating single local regions, while long-range spatial correlations can further refine image labeling. In addition, higher orders are able to pose the constraints among labels. By this way, multi-scale unary potentials, long-range spatial correlations, higher-order priors are well modeled under the uniform framework in MSPN. We conduct experiments on two challenging benchmarks consisting of the MSRC-21 dataset and the SIFT FLOW dataset. The results demonstrate the superior performance of our method comparing with the previous graphical models for understanding scene images. <s> BIB002 </s> Sum-product networks: A survey <s> VII. Applications <s> This paper addresses detection and localization of human activities in videos. We focus on activities that may have variable spatiotemporal arrangements of parts, and numbers of actors. Such activities are represented by a sum-product network (SPN). A product node in SPN represents a particular arrangement of parts, and a sum node represents alternative arrangements. The sums and products are hierarchically organized, and grounded onto space-time windows covering the video. The windows provide evidence about the activity classes based on the Counting Grid (CG) model of visual words. This evidence is propagated bottom-up and top-down to parse the SPN graph for the explanation of the video. The node connectivity and model parameters of SPN and CG are jointly learned under two settings, weakly supervised, and supervised. For evaluation, we use our new Volleyball dataset, along with the benchmark datasets VIRAT, UT-Interactions, KTH, and TRECVID MED 2011. Our video classification and activity localization are superior to those of the state of the art on these datasets. <s> BIB003 </s> Sum-product networks: A survey <s> VII. Applications <s> Segmenting retinal tissue deformed by pathologies can be challenging. Segmentation approaches are often constructed with a certain pathology in mind and may require a large set of labeled pathological scans, and therefore are tailored to that particular pathology. <s> BIB004 </s> Sum-product networks: A survey <s> VII. Applications <s> Recognizing actions from still images is popularly studied recently. In this paper, we model an action class as a flexible number of spatial configurations of body parts by proposing a new spatial SPN (Sum-Product Networks). First, we discover a set of parts in image collections via unsupervised learning. Then, our new spatial SPN is applied to model the spatial relationship and also the high-order correlations of parts. To learn robust networks, we further develop a hierarchical spatial SPN method, which models pairwise spatial relationship between parts inside sub-images and models the correlation of sub-images via extra layers of SPN. Our method is shown to be effective on two benchmark datasets. <s> BIB005
SPNs have been used for a wide variety of applications, from toy problems to real-world challenges. A. Image processing 1) Image reconstruction and classification: Poon and Domingos, in their seminal paper about SPNs BIB001 , applied them to image reconstruction, using a hand-designed structure that took into account the local structure of the image data. They tested their method on the datasets Caltech-101 and Olivetti. Then Gens and Domingos  used a different hand-made structure for image classification on the datasets CIFAR-10 and STL-10, obtaining excellent results for that time, as mentioned in Section I-A. 2) Image segmentation: Image segmentation consists in labeling every pixel with the object it belongs to. Yuan et al. BIB002 developed an algorithm that scales down every image recursively to different sizes and generates object tags and unary potentials for every scale. Then, it builds a multi-stacked SPN where every stack has a bottom and a top SPN. The bottom SPN works on a pixel and its vicinity, going from the pixel to bigger patches. Product nodes model correlations between patches while sum nodes combine them into a feature of a bigger patch. When the patch is as big as the pixel in the next scaled image, the results are introduced in the top SPN alongside the unary potentials and the tags of that scale. This process is stacked until the "patch" treated is the whole image. Multi-stacked SPNs have been especially effective for handling occlusions in scenes. Rathke et al. BIB004 applied SPNs to segmentation OCT scans of retinal tissue. They first built a segmentation model for the health model and for every pathology and then added to those models typical shape variations of the retina tissue for some pathology-specific regions. The resulting SPN extracts candidate regions (either healthy or unhealthy) and selects the combination that maximizes the likelihood. After a smoothing step, they obtain a complete segmentation of the retina tissue as well as the diagnosis and the affected regions. This method achieved state-of-the-art performance without needing images labeled by pathologies. 3) Activity recognition: Wang and Wang BIB005 addressed activity recognition on still images. They used unsupervised learning and a convolutional neural network to isolate parts of the images, such as a hand or a glass, and designed a spatial SPN including the spatial indicator nodes "above", "below", "left", and "right" for the product nodes to encode spatial relations between pairs of these parts. They first partitioned the image to consider only local part configurations. Its SPN structure has two components: the top layers represent a partitioning of the image into sub-images where product nodes act as partitions and sum nodes as combinations of different partitions, while the bottom layers represent the parts included in each sub-image and their relative position using the spatial indicator nodes. In this sense the SPN first learns spatial relations of isolated parts in sub-images and then learns correlations between sub-images. Spatial SPNs outperformed other activity recognition algorithms and were able to discover discriminant pairs of parts for each class. Amer and Todorovic BIB003 worked on activity localization and recognition in videos. In their work, a visual word is a meaningful piece of an image, previously extracted with a neural network. Visual words lie in a grid with three dimensions: height, width, and time. Every grid position has a histogram of associated visual words, called bag of words. To construct an SPN, each bag of words is treated as a variable with two states: foreground and background. Product nodes represent a combination of sub-activities into a more complex activity (for example, "join hands + separate hands = clap") and sum nodes represent variations of the same activity. An SPN is trained for every activity in a supervised context, in which the foreground and the background values are known, and in a weakly supervised context, in which only the activity is known. The structure is a near-completely connected graph, pruned after parameter learning, which proceeds iteratively: it learns-with GD-the weights of the SPN from the parameters of the bag of words and then learnswith variational methods-the parameters of the bag of words from the weights of the SPN. The accuracy of this weakly supervised setting was only 1.6 to 3% worse than that of the supervised setting. This approach in general achieved better performance than state-of-the-art algorithms on several action-recognition datasets. 4) Object detection: Stelzner et al.  proved that the attend-infer-repeat (AIR) framework used for object detection and location is much more efficient when the variational autoencoders (VAEs) that model individual objects are replaced by SPNs: they achieved an improvement in speed of an order of magnitude, with slightly higher accuracy, as well as robustness against noise.