Title: SUBMODULAR SUM-PRODUCT NETWORKS FOR SCENE UNDERSTANDING

Abstract: Sum-product networks (SPNs) are an expressive class of deep probabilistic models in which inference takes time linear in their size, enabling them to be learned effectively. However, for certain challenging problems, such as scene understanding, the corresponding SPN has exponential size and is thus intractable. In this work, we introduce submodular sum-product networks (SSPNs), an extension of SPNs in which sum-node weights are defined by a submodular energy function. SSPNs combine the expressivity and depth of SPNs with the ability to efficiently compute the MAP state of a combinatorial number of labelings afforded by submodular energies. SSPNs for scene understanding can be understood as representing all possible parses of an image over arbitrary region shapes with respect to an image grammar. Despite this complexity, we develop an efficient and convergent algorithm based on graph cuts for computing the (approximate) MAP state of an SSPN, greatly increasing the expressivity of the SPN model class. Empirically, we show exponential improvements in parsing time compared to traditional inference algorithms such as α-expansion and belief propagation, while returning comparable minima.
1 Formally, a min-cut/max-flow algorithm (Ahuja et al., 1993) on a graph constructed from the MRF.

1. INTRODUCTION:

Sum-product networks (SPNs) (Poon & Domingos, 2011; Gens & Domingos, 2012) are a class of deep probabilistic models that consist of many layers of hidden variables and can have unbounded treewidth. Despite this depth and corresponding expressivity, exact inference in SPNs is guaranteed to take time linear in their size, allowing their structure and parameters to be learned effectively from data. However, there are still many models for which the corresponding SPN has size exponential in the number of variables and is thus intractable. For example, in scene understanding (or semantic segmentation), the goal is to label each pixel of an image with its semantic class, which requires simultaneously detecting, segmenting, and recognizing each object in the scene. Even the simplest SPN for scene understanding is intractable, as it must represent the exponentially large set of segmentations of the image into its constituent objects.

Scene understanding is commonly formulated as a flat Markov (or conditional) random field (MRF) over the pixels or superpixels of an image (e.g., Shotton et al. (2006) ; Gould et al. (2009) ). Inference in MRFs is intractable in general; however, there exist restrictions of the MRF that enable tractable inference. For pairwise binary MRFs, if the energy of each pairwise term is submodular (alternatively, attractive or regular) (Kolmogorov & Zabih, 2004) , meaning that each pair of neighboring pixels prefers to have the same label, then the exact MAP labeling of the MRF can be recovered in low-order polynomial time through the use of a graph cut algorithm 1 (Greig et al., 1989; Boykov & Kolmogorov, 2004) . This result from the binary case has been used to develop a number of powerful approximate algorithms for the multi-label case (e.g., Komodakis et al. (2007) ; Lempitsky et al. (2010) ), the most well-known of which is α-expansion (Boykov et al., 2001) , which efficiently returns an approximate labeling that is within a constant factor of the true optimum by solving a series of binary graph cut problems. Unfortunately, pairwise MRFs are insufficiently expressive for com-plex tasks such as scene understanding, as they are unable to model high-level relationships, such as constituency (part-subpart) or subcategorization (superclass-subclass) , between arbitrary regions of the image, unless these can be encoded in the labels of the MRF and enforced between pairs of (super)pixels. However, this encoding requires a combinatorial number of labels, which is intractable. Instead, higher-level structure is needed to efficiently represent these relationships.

In this paper, we present submodular sum-product networks (SSPNs), a novel model that combines the expressive power of sum-product networks with the tractable segmentation properties of submodular energies. An SSPN is a sum-product network in which the weight of each child of a sum node corresponds to the energy of a particular labeling of a submodular energy function. Equivalently, an SSPN over an image corresponds to an instantiation of all possible parse trees of that image with respect to a given image grammar, where the probability distribution over the segmentations of a production on a particular region is defined by a submodular random field over the pixels in that region. Importantly, SSPNs permit objects and regions to take arbitrary shapes, instead of restricting the set of possible shapes as has previously been necessary for tractable inference. By exploiting submodularity, we develop a highly-efficient approximate inference algorithm, INFERSSPN, for computing the MAP state of the SSPN (equivalently, the optimal parse of the image). INFERSSPN is an iterative move-making-style algorithm that provably converges to a local minimum of the energy, reduces to α-expansion in the case of a trivial grammar, and has complexity O(|G|c(n)) for each iteration, where c(n) is the complexity of a single graph cut and |G| is the size of the grammar. As with other move-making algorithms, INFERSSPN converges to a local minimum with respect to an exponentially-large set of neighbors, overcoming many of the main issues of local minima (Boykov et al., 2001) . Empirically, we compare INFERSSPN to belief propagation (BP) on a multilevel MRF and to α-expansion on an equivalent flat MRF. We show that INFERSSPN parses images in exponentially less time than both of these while returning energies comparable to α-expansion, which is guaranteed to return energies within a constant factor of the true optimum.

The literature on using higher-level information for scene understanding is vast. We briefly discuss the most relevant work on hierarchical random fields over multiple labels, image grammars for segmentation, and neural parsing methods. Hierarchical random field models (e.g., Russell et al. (2010) ; Lempitsky et al. (2011) ) define MRFs with multiple layers of hidden variables and then perform inference, often using graph cuts to efficiently extract the MAP solution. However, these models are typically restricted to just a few layers and to pre-computed segmentations of the image, and thus do not allow arbitrary region shapes. In addition, they require a combinatorial number of labels to encode complex grammar structures. Previous grammar-based methods for scene understanding, such as Zhu & Mumford (2006) and Zhao & Zhu (2011) , have used MRFs with AND-OR graphs (Dechter & Mateescu, 2007) , but needed to restrict their grammars to a very limited set of productions and region shapes in order to perform inference in reasonable time, and are thus much less expressive than SSPNs. Finally, neural parsing methods such as those in Socher et al. (2011) and Sharma et al. (2014) use recursive neural network architectures over superpixel-based features to segment an image; thus, these methods also do not allow arbitrary region shapes. Further, Socher et al. (2011) greedily combine regions to form parse trees, while (Sharma et al., 2014) use randomly generated parse trees, whereas inference in SSPNs finds the (approximately) optimal parse tree.

2. SUBMODULAR SUM-PRODUCT NETWORKS:

In the following, we define submodular sum-product networks (SSPNs) in terms of an image grammar because this simplifies the exposition with respect to the structure of the sum-product network (SPN) and because scene understanding is the domain we use to evaluate SSPNs. However, it is not necessary to define SSPNs in this way, and our results extend to any SPN with sum-node weights defined by a random field with submodular potentials. Due to lack of space we refer readers to Gens & Domingos (2012) , Poon & Domingos (2011) and Gens & Domingos (2013) for SPN details.

With respect to scene understanding, an SSPN defines a generative model of an image and a hierarchy of regions within that image where each region is labeled with a production (and implicitly by the head symbol of that production), can have arbitrary shape, and is a subset of the region of each of its ancestors. An example of an SSPN for parsing a farm scene is shown in Figure 1 . Given a starting symbol and the region containing the entire image, the generative process is to first choose a production of that symbol into its constituent symbols and then choose a segmentation of the region into a set of mutually exclusive and exhaustive subregions, with one subregion per constituent sym-Figure 1 : A partial (submodular) sum-product network for parsing an image with respect to the grammar shown. There is a sum node for each nonterminal symbol with a child sum node for each production of that symbol. Each sum node for a production has a child product nodefor each possible segmentation of its region.

bol. The process then recurses, choosing a production and a segmentation for each subregion given its symbol. The recursion terminates when one of the constituents is a terminal symbol, at which point the pixels corresponding to that region of the image are generated. This produces a parse tree in which each internal node is a pair containing a region and a production of the region, and the leaves are regions of pixels. For each node in a parse tree, the regions of its children are mutually exclusive and exhaustive with respect to the parent node's region. As in a probabilistic context-free grammar (PCFG) (Jurafsky & Martin, 2000) , productions are chosen from a categorical distribution over the productions of the current symbol. Segmentations of a given region, however, are sampled from a (submodular) Markov random field (MRF) over the pixels in the region.

Formally, let G = (N, Σ, R, S, w) be a non-recursive stochastic grammar, where N is a finite set of nonterminal symbols; Σ is a finite set of terminal symbols; R is a finite set of productions R = {v : X → Y 1 Y 2 . . . Y k } with head symbol X ∈ N and constituent symbols Y i ∈ N ∪ Σ for i = 1 . . . k and k > 0; S ∈ N is a distinguished start symbol, meaning that it does not appear on the right-hand side of any production; and w are the weights that parameterize the probability distribution defined by G. For a production v ∈ t in a parse tree t ∈ T G , we denote its region as P v and its parent and children as pa(v) and ch(v), respectively, where T G is the set of possible parse trees under the grammar G. The labeling corresponding to the segmentation of the pixels in

P v for production v : X → Y 1 . . . Y k is y v ∈ Y |Pv| v

, where Y v = {Y 1 , . . . , Y k }. The region of any production v ∈ t is the set of pixels in P pa(v) whose assigned label is the head of v, i.e., P v = {p ∈ P pa(v) : y pa(v) p = head(v)}, except for the production of the start symbol, which has the entire image as its region. The probability of an image x is p w (x) = t∈T G p w (t, x), where the joint probability of parse tree t and the image is the product over all productions in t of the probability of choosing that production v and then segmenting its region P v according to y v :

p w (t, x) = 1 Z exp(-E w (t, x)) = 1 Z exp(- v∈t E v w (v, y v , head(v), P v , x)).

Here, Z = t∈T G exp(-E w (t, x)) is the partition function, w are the model parameters, and E is the energy function. In the following, we will simplify notation by omitting head(v), P v , x, w, and superscript v from the energy function when they are clear from context. The energy of a production and its segmentation on the region P v are given by a pairwise Markov random field (MRF) as

E(v, y v ) = p∈Pv θ v p (y v p ; w) + (p,q)∈Ev θ v pq (y v p , y v q ; w)

, where θ v p and θ v pq are the unary and pairwise costs of the segmentation MRF, {y v p : p ∈ P v } is the labeling defining the segmentation of the pixels in the current region, and E v are the edges in P v . Without loss of generality we assume that E v contains only one of (p, q) or (q, p), since the two terms can always be combined. Here, θ v p is the per-pixel data cost and θ v pq is the boundary term, which penalizes adjacent pixels within the same region that have different labels. We describe these terms in more detail below. In general, even computing the segmentation for a single production is intractable. In order to permit efficient inference, we require that θ v pq satisfies the submodularity condition

θ v pq (Y 1 , Y 1 ) + θ v pq (Y 2 , Y 2 ) ≤ θ v pq (Y 1 , Y 2 ) + θ v pq (Y 2 , Y 1

) for all productions v : X → Y 1 Y 2 once the grammar has been converted to a grammar in which each production has only two constituents, which is always possible and in the worst case increases the grammar size quadratically (Jurafsky & Martin, 2000; Chomsky, 1959) . We also require for every production v ∈ R and for every production c that is a descendant of v in the grammar that θ v pq (y v p , y v q ) ≥ θ c pq (y c p , y c q ) for all possible labelings (y v p , y v q , y c p , y c q ), where y v p , y v q ∈ Y v and y c p , y c q ∈ Y c . This condition ensures that segmentations for higher-level productions are submodular, no matter what occurs below them. It also encodes the reasonable assumption that higher-level abstractions are separated by stronger, shorter boundaries (relative to their size), while lower-level objects are more likely to be composed of smaller, more intricately-shaped regions.

The above model defines a sum-product network containing a sum node for each possible region of each nonterminal, a product node for each segmentation of each production of each possible region of each nonterminal, and a leaf function on the pixels of the image for each possible region of the image for each terminal symbol. The children of the sum node s for nonterminal X s with region P s are all product nodes r with a production v r : X s → Y 1 . . . Y k and region P vr = P s . Each product node corresponds to a labeling y vr of P vr and the edge to its parent sum node has weight exp(-E(v, y vr , P vr )). The children of product node r are the sum or leaf nodes with matching regions that correspond to the constituent nonterminals or terminals of v r , respectively. Since the weights of the edges from a sum node to its children correspond to submodular energy functions, we call this a submodular sum-product network (SSPN).

A key benefit of SSPNs in comparison to previous grammar-based approaches is that regions can have arbitrary shapes and are not restricted to a small class of shapes such as rectangles (Poon & Domingos, 2011; Zhao & Zhu, 2011) . This flexibility is important when parsing images, as realworld objects and abstractions can take any shape, but it comes with a combinatorial explosion of possible parses. However, by exploiting submodularity, we are able to develop an efficient inference algorithm for SSPNs, allowing us to efficiently parse images into a hierarchy of arbitrarily-shaped regions and objects, yielding a very expressive model class. This efficiency is despite the size of the underlying SSPN, which is in general far too large to explicitly instantiate.

2.1. MRF SEGMENTATION DETAILS:

As discussed above, the energy of each segmentation of a region for a given production is defined by a submodular MRF E(v, y v ) = p∈Pv θ v p (y v p ; w) + (p,q)∈Ev θ v pq (y v p , y v q ; w). The unary terms in E(v, y v ) differ depending on whether the label y v p corresponds to a terminal or nonterminal symbol. For a terminal T ∈ Σ, the unary terms are a linear function of the image features θ v p (y v p = T ; w) = w PC v +w T φ U p , where w P C v is an element of w that specifies the cost of v relative to other productions and φ U p is a feature vector representing the local appearance of pixel p. In our experiments, φ U p is the output of a deep neural network. For labels corresponding to a nonterminal X ∈ N , the unary terms are

θ v p (y v p = X; w) = w PC v + θ c p (y c p )

, where c is the child production of v in the current parse tree that contains p, such that p ∈ P c . This dependence makes inference challenging, because the choice of children in the parse tree itself depends on the region that is being parsed as X, which depends on the segmentation this unary is being used to compute.

The pairwise terms in E(v, y v ) are a recursive version of the standard contrast-dependent pairwise boundary potential (e.g., Shotton et al. (2006) ) defined for each production v and each pair of adjacent pixels p, q as

θ v pq (y v p , y v q ; w) = w BF v exp(-β -1 ||φ B p -φ B q || 2 )•[y v p = y v q ]+θ c pq (y c p , y c q ; w)

, where β is half the average image contrast between all adjacent pixels in an image, w BF v is the boundary factor that controls the relative cost of this term for each production, φ B p is the pairwise per-pixel feature vector, c is the same as in the unary term above, and [•] is the indicator function, which has value 1 when its argument is true and is 0 otherwise. For each pair of pixels (p, q), only one such term will ever be non-zero, because once two pixels are labeled differently at a node in the parse tree, they are placed in separate subtrees and thus never co-occur in any region below the current node. In our experiments, φ B p are the intensity values for each pixel.

3. INFERENCE:

Scene understanding (or semantic segmentation) requires labeling each pixel of an image with its semantic class. By constructing a grammar containing a set of nonterminals in one-to-one correspondence with the semantic labels and only allowing these symbols to produce terminals, we can recover the semantic segmentation of an image from a parse tree for this grammar. In the simplest case, a grammar need contain only one additional production from the start symbol to all other nonterminals. More generally, however, the grammar encodes rich structure about the relationships between image regions at various levels of abstraction, including concepts such as composition and subcategorization. Identifying the relevant structure and relationships for a particular image entails finding the best parse of an image x given a grammar G (or, equivalently, performing MAP inference in the corresponding SSPN), i.e., t * = arg max t∈T G p(t|x) = arg min t∈T G v∈t E(v, y v , x).

× × × × Y Z A B C D fuse X➞YZ × A B C D Y Z × × C D A B × × C B Y Z Z Y Y Y Z Z E F H G E F G H A B C D -confusing part: not clear that X->Y->AB in

× × × × Y Z A B C D fuse X➞YZ × A B C D Y Z × × C D A B × × C B Y Z Z Y Y Y Z Z E F H G E F G H A B C D -confusing part: not clear that X->Y->AB in

In PCFGs over sentences (Jurafsky & Martin, 2000) , the optimal parse can be recovered exactly in time O(n 3 |G|) with the CYK algorithm (Hopcroft & Ullman, 1979) , where n is the length of the sentence and |G| is the number of productions in the grammar, by iterating over all possible split points of the sentence and using dynamic programming to avoid recomputing sub-parses. Unfortunately, for images and other 2-D data types, there are 2 n possible segmentations of the data for each binary production, rendering this approach infeasible in general. With an SSPN, however, it is possible to efficiently compute the approximate optimal parse of an image. In our algorithm, INFERSSPN, this is done by iteratively constructing parses of different regions in a bottom-up fashion.

3.1. PARSE TREE CONSTRUCTION:

Given a production v : X → Y 1 Y 2 and two parse trees t 1 , t 2 over the same region P and with head symbols Y 1 , Y 2 , respectively, then for any labeling y v ∈ {Y 1 , Y 2 } |P| of P we can construct a third parse tree t X over region P with root production v, labeling y v , and subtrees t 1 , t 2 over regions P 1 , P 2 , respectively, such that P i = {p ∈ P : y v p = Y i } and t i = t i ∩ P i for each i, where the intersection of a parse tree and a region t ∩ P is the new parse tree resulting from intersecting P with the region at each node in t. Of course, the quality of the resulting parse tree, t X , depends on the particular labeling (segmentation) y v used. Recall that a parse tree t on region P has energy E(t, P) = v∈t E(v, y v , P v ), which can be written as E(t, P) = p∈P θ t p + (p,q)∈E θ t pq , where

θ t p = v∈t θ v p (y v p ) • [p ∈ P v ] and θ t pq = v∈t θ v pq (y v p , y v q ) • [(p, q) ∈ E v ]

. This allows us to define the fusion operation, which is a key subroutine in INFERSSPN. Note that δ ij is the Kronecker delta.

Definition 1. For a production v : X → Y 1 , Y 2 and two parse trees t 1 , t 2 over region P with head symbols Y 1 , Y 2 then t X is the fusion of t 1 and t 2 constructed from the minimum energy labeling

y v = arg min y∈Y |P| v E(v, t 1 , t 2 , y), where E(v, t 1 , t 2 , y) = p∈P θ t1 p • δ ypY1 + θ t2 p • δ ypY2 + (p,q)∈E θ t1 pq • δ ypY1 • δ yqY1 + θ t2 pq • δ ypY2 • δ yqY2 + θ v pq (Y 1 , Y 2 ) • δ ypY1 • δ yqY2 .

Figure 2a shows an example of fusing two parse trees to create a new parse tree. Although fusion requires finding the optimal labeling from an exponentially large set, the energy is submodular and can be efficiently optimized with a single graph cut. All proofs are presented in the appendix.

Proposition 1. The energy E(v, t 1 , t 2 , y v ) of the fusion of parse trees t 1 , t 2 over region P with head symbols Y 1 , Y 2 for a production v : X → Y 1 Y 2 is submodular.

Once a parse tree has been constructed, INFERSSPN then improves that parse tree on subsequent iterations. The following result shows how INFERSSPN can improve a parse tree while ensuring that the energy of that parse tree never gets worse. Lemma 1. Given a labeling y v which fuses parse trees t 1 , t 2 into t with root production v, energy E(t, P) = E(v, t 1 , t 2 , y v ), and subtree regions P 1 ∩ P 2 = ∅ defined by y v , then any improvement ∆ in E(t 1 , P 1 ) also improves E(t, P) by at least ∆, regardless of any change in E(t 1 , P\P 1 ).

Finally, it will be useful to define the union t = t 1 ∪ t 2 of two parse trees t 1 , t 2 that have the same production at their root but are over disjoint regions P 1 ∩ P 2 = ∅, as the parse tree t with region P = P 1 ∪ P 2 and in which all nodes that co-occur in both t 1 and t 2 (i.e., have the same path to them from the root and have the same production) are merged to form a single node in t. In general, t may be an inconsistent parse tree, as the same symbol may be parsed as two separate productions, in which case we define the energy of the boundary terms between the pixels parsed as these separate productions to be infinite.

3.2. INFERSSPN:

Pseudocode for our algorithm, INFERSSPN, is presented in Algorithm 1. INFERSSPN is an iterative bottom-up algorithm based on graph cuts (Kolmogorov & Zabih, 2004 ) that provably converges to a local minimum of the energy function. In its first iteration, INFERSSPN constructs a parse tree over the full image for each production in the grammar. The parse of each terminal production is trivial to construct and simply labels each pixel as the terminal symbol. The parse for every other production v : X → Y 1 Y 2 is constructed by choosing productions for Y 1 and Y 2 and fusing their corresponding parse trees to get a parse of the image as X. Since the grammar is non-recursive, we can construct a directed acyclic graph (DAG) containing a node for each symbol and an edge from each symbol to each constituent of each production of that symbol and then traverse this graph from the leaves (terminals) to the root (start symbol), fusing the children of each production of each symbol when we visit that symbol's node. Of course, to fuse parses of Y 1 and Y 2 into a parse of X, we need to choose which production of Y 1 (and Y 2 ) to fuse; this is done by simply choosing the production of Y 1 (and Y 2 ) that has the lowest energy over the current region. The best parse of the image, t, now corresponds to the lowest-energy parse of all productions of the start symbol.

Further iterations of INFERSSPN improve t in a flexible manner that allows any of its productions or labelings to change, while also ensuring that its energy never increases. INFERSSPN does this by again computing parses of the full image for each production in the grammar. This time, however, when parsing a symbol X, INFERSSPN independently parses each region of the image that was parsed as any production of X in t (none of these regions will overlap because the grammar is nonrecursive) and then parses the remainder of the image given these parses of subregions of the image, meaning that the pixels in these other subregions are instantiated in the MRF but fixed to the labels that the subregion parses specify. The parse of the image as X is then constructed as the union of these subregion parses. This procedure ensures that the energy will never increase (see Theorem 1 and Lemma 1), but also that any subtree of t can be replaced with another subtree if it results in lower energy. Figure 2b shows a simple example of updating a parse of a region as X → Y Z.

Further, this (re)parsing of subregions can again be achieved in a single bottom-up pass through the grammar DAG, resulting in a very efficient algorithm for SSPN inference. This is because each pixel only appears in at most one subregion for any symbol, and thus only ever needs to be parsed once per production. See Algorithm 1 for more details.

3.3. ANALYSIS:

As shown in Theorem 1, INFERSSPN always converges to a local minimum of the energy function. Similar to other graph-cut-based algorithms, such as α-expansion (Boykov et al., 2001) , IN-FERSSPN explores an exponentially large set of moves at each step, so the returned local minimum is much better than those returned by more local procedures, such as max-product belief propagation. Further, we observe convergence within a few iterations in all experiments, with the majority of the energy improvement occurring in the first iteration.

Theorem 1. Given a parse (tree) t of S over the entire image with energy E( t), each iteration of INFERSSPN constructs a parse (tree) t of S over the entire image with energy E(t) ≤ E( t) and since the minimum energy of an image parse is finite, INFERSSPN will always converge.

As shown in Proposition 2, each iteration of INFERSSPN takes time O(|G|c(n)), where n is the number of pixels in the image and c(n) is the complexity of the underlying graph cut algorithm used, which is low-order polynomial in the worst-case but nearly linear-time in practice (Boykov & Kolmogorov, 2004; Boykov et al., 2001) . Proposition 2. Let c(n) be the time complexity of computing a graph cut on n pixels and |G| be the size of the grammar defining the SSPN, then each iteration of INFERSSPN takes time O(|G|c(n)).

Algorithm 1 Compute the (approximate) MAP assignment of the SSPN variables (i.e., the productions and labelings) defined by an image and a grammar. This is equivalent to parsing the image.

Input: The image x, a non-recursive grammar G = (N, Σ, R, S, w), and (optional) input parse t.

Output: A parse of the image, t * , with energy E(t * , x) ≤ E( t, x).

EQUATION

T, E ← empty lists of parse trees and energies, respectively, both of length |R| + |Σ| 3:

for each terminal Y ∈ Σ do 4:

T [Y ] ← the trivial parse with all pixels parsed as Y

5:

E[Y ] ← p∈x w Y φ U p 6:

while the energy of any production of the start symbol S has not converged do 7:

for each symbol X ∈ N , in reverse topological order do // as defined by the DAG of G 8:

for each subtree ti of t rooted at a production u i with head X do 9: P i , y i ← the region that ti is over and its labeling in ti // {Pi} are all disjoint 10:

for each production v j : X → Y 1 Y 2 do // iterate over all productions of X 11:

t ij , e ij ←FUSE(P i , y i , v j , T ) // parse Pi as vj by fusing parses of Y1 and Y2

12::

P X ← all pixels that are not in any region P i 13:

for each production v j : X → Y 1 Y 2 do // iterate over all productions of X 14:

y rand ← a random labeling of P X // use random for initialization 15:

t X , e X ← FUSE(P X , y rand , v j , T, (∪ i t ij ))

// parse P X as vj given (∪itij)

16: update lists: T [v j ] ← (∪ i t ij ) ∪ t X and E[v j ] ← i e ij + e X for all v j with head X 17:

t, ê ← the production of S with the lowest energy in E and its energy 18: return t, ê

Input: A region P, a labeling y of P, a production v : X → Y 1 Y 2 , a list of parses T , and an optional parse t P of pixels not in P, used to set pairwise terms of edges that are leaving P. Output: A parse tree rooted at v over region P and the energy of that parse tree.

1: function FUSE(P, y, v, T, t P ) 2:

for each Y i with i ∈ 1, 2 do 3: y v , e v ← (arg) min y E(v, y, P, x)

u i ← production of Y i in

// label each pixel in P as Y1 or Y2 using graph cuts 6:

t v ← combine T [u 1 ]

and T [u 2 ] according to y v and append v as the root 7:

return t v , e v

Note that a straightforward application of α-expansion to image parsing that uses one label for every possible parse in the grammar requires an exponential number of labels in general.

INFERSSPN can be extended to productions with more than two constituents by simply replacing the internal graph cut used to fuse subtrees with a multi-label algorithm such as α-expansion. INFERSSPN would still converge because each subtree would still never decrease in energy. An algorithm such as QPBO (Kolmogorov & Rother, 2007) could also be used, which would allow the submodularity restriction to be relaxed. Finally, running INFERSSPN on the grammar containing k -1 binary productions that results from converting a grammar with a single production on k > 2 constituents is equivalent to running α-expansion on the k constituents.

4. EXPERIMENTS:

We evaluated INFERSSPN by parsing images from the Stanford background dataset (SBD) using grammars with generated structure and weights inferred from the pixel labels of the images we parsed. SBD is a standard semantic segmentation dataset containing images with an average size of 320 × 240 pixels and a total of 8 labels. The input features we used were from the Deeplab system (Chen et al., 2015; 2016) trained on the same images used for evaluation (note that we are not evaluating learning and thus use the same features for each algorithm and evaluate on the training data in order to separate inference performance from generalization performance). We compared IN-FERSSPN to α-expansion on a flat pairwise MRF and to max-product belief propagation (BP) on a multi-level (3-D) pairwise grid MRF. Details of these models are provided in the appendix. We note that the flat encoding for α-expansion results in a label for each path in the grammar, where there are an exponential number of such paths in the height of the grammar. However, once α-expansion converges, its energy is within a constant factor of the global minimum energy (Boykov et al., 2001) and thus serves as a good surrogate for the true global minimum, which is intractable to compute.

We compared these algorithms by varying three different parameters: boundary strength (strength of pairwise terms), grammar height, and number of productions per nonterminal. Each grammar used for testing contained a start symbol, multiple layers of nonterminals, and a final layer of nonterminals in one-to-one correspondence with the eight terminal symbols, each of which had a single production that produces a region of pixels. The start symbol had one production for each pair of symbols in the layer below it, and the last nonterminal layer (ignoring the nonterminals for the labels) had productions for each pair of labels, distributed uniformly over this last nonterminal layer.

Boundary strength. Increasing the boundary strength of an MRF makes inference more challenging, as individual pixel labels cannot be easily flipped without large side effects. To test this, we constructed a grammar as above with 2 layers of nonterminals (not including the start symbol), each containing 3 nonterminal symbols with 4 binary productions to the next layer. We vary w BF v for all v and plot the mean average pixel accuracy returned by each algorithm (the x-axis is log-scale) in Figure 3a . INFERSSPN returns parses with almost identical accuracy (and energy) to α-expansion. BP also returns comparable accuracies, but almost always returns invalid parses with infinite energy (if it converges at all) that contain multiple productions of the same object or a production of some symbol Y even though a pixel is labeled as symbol X. Grammar height. In general, the number of paths in the grammar is exponential in its height, so the height of the grammar controls the complexity of inference and thus the difficulty of parsing images. For this experiment, we set the boundary scale factor to 10 and constructed a grammar with four nonterminals per layer, each with three binary productions to the next layer. Figure 3b shows the effect of grammar height on total inference time (to convergence or a maximum number of iterations, whichever first occurred). As expected from Proposition 2, the time taken for INFERSSPN scales linearly with the height of the grammar, which is within a constant factor of the size of the grammar when all other parameters are fixed. Similarly, inference time for both α-expansion and BP scaled exponentially with the height of the grammar because the number of labels for both increases combinatorially. Again, the energies and corresponding accuracies achieved by INFERSSPN were nearly identical to those of α-expansion (see Figure 5 in the appendix). Productions per nonterminal. The number of paths in the grammar is also directly affected by the number of productions per symbol. For this experiment, we increased each pairwise term by a factor of 10 and constructed a grammar with 2 layers of nonterminals, each with 4 nonterminal symbols. Figure 3c shows the effect of increasing the number of productions per nonterminal, which again demonstrates that INFERSSPN is far more efficient than either α-expansion or BP as the complexity of the grammar increases, while still finding comparable solutions (see Figure 6 in the appendix).

5. CONCLUSION:

This paper proposed submodular sum-product networks (SSPNs), a novel extension of sum-product networks that can be understood as an instantiation of an image grammar in which all possible parses of an image over arbitrary shapes are represented. Despite this complexity, we presented INFERSSPN, a move-making algorithm that exploits submodularity in order to find the (approximate) MAP state of an SSPN, which is equivalent to finding the (approximate) optimal parse of an image. Analytically, we showed that INFERSSPN is both very efficient -each iteration takes time linear in the size of the grammar and the complexity of one graph cut -and convergent. Empirically, we showed that INFERSSPN achieves accuracies and energies comparable to α-expansion, which is guaranteed to return optima within a constant factor of the global optimum, while taking exponentially less time to do so.

We have begun work on learning the structure and parameters of SSPNs from data. This is a particularly promising avenue of research because many recent works have demonstrated that learning both the structure and parameters of sum-product networks from data is feasible and effective, despite the well-known difficulty of grammar induction. We also plan to apply SSPNs to additional domains, such as activity recognition, social network modeling, and probabilistic knowledge bases.

guaranteed to be within a constant factor of the global minimum energy (Boykov et al., 2001) and thus serves as a good surrogate for the true global minimum, which is intractable to compute. The multi-layer MRF is constructed similarly. The number of levels in the MRF is equal to the height of the DAG corresponding to the grammar used. The labels at a particular level of the MRF are all (production, constituent) pairs that can occur at this height in the grammar. The pairwise term between the same pixel in two levels is 0 when the parent label's constituent equals the child label's production head, and ∞ otherwise. Pairwise terms within a layer are defined as in the flat MRF with infinite cost for incompatible labels (i.e., two neighboring productions of the same symbol), unless two copies of that nonterminal could be produced at that level by the grammar.

All experiments were run on the same computer running an Intel Core i7-5960X with 8 cores and 128MB of RAM. Each algorithm was limited to a single thread. 

:



Figures and Tables:

subregion of LHS figure is just sub-selecting from existing parse of Y->AB over entire region -need to explain clearly what's happening…

Figure 2: The two main components of INFERSSPN: (a) Parsing a region P as X → Y Z by fusing two parses of P as Y → AB and as Z → CD, and (b) Improving the parse of P as X → Y Z by (re)parsing each of its subregions, taking the union of the new Y and Z parses of P, and then fusing these new parses.

T with lowest energy over {p : y p = Y i } given t P 4: create submodular energy function E(v, y, P, x) on P from T [u 1 ], T [u 2 ], and t P 5:

Figure 3: The mean average pixel accuracy of the returned solution and total running time for each of belief propagation, α-expansion, and INFERSSPN when varying (a) boundary strength, (b) grammar height, and (c) number of productions. Each data point is the average value over (the same) 10 images. Missing data points indicate out of memory errors. Figures 4, 5, and 6 in the appendix show all results for each experiment.

Figure 4: The (a) best energy, (b) total running time, and (c) resulting semantic segmentation accuracy (mean average pixel accuracy) for belief propagation, α-expansion, and INFERSSPN when varying boundary strength. Each data point is the average value over (the same) 10 images. Missing data points indicate that an algorithm ran out of memory (middle and right) or returned infinite energy (left).

Figure 5: The (a) best energy, (b) total running time, and (c) resulting semantic segmentation accuracy (mean average pixel accuracy) for belief propagation, α-expansion, and INFERSSPN when varying grammar height. Each data point is the average value over (the same) 10 images. Missing data points indicate that an algorithm ran out of memory (middle and right) or returned infinite energy (left). Low accuracies for grammar height 0 are a result of the grammar being insufficiently expressive.

Figure 6: The (a) best energy, (b) total running time, and (c) resulting semantic segmentation accuracy (mean average pixel accuracy) for belief propagation, α-expansion, and INFERSSPN when varying grammar height. Each data point is the average value over (the same) 10 images. Missing data points indicate that an algorithm ran out of memory (middle and right) or returned infinite energy (left).

Peer review (iclr2017):
The paper discusses sub modular sum-product networks as a tractable extension for classical sum-product networks. The proposed approach is evaluated on semantic segmentation tasks and some early promising results are provided. Summary: ——— I think the paper presents a compelling technique for hierarchical reasoning in MRFs but the experimental results are not yet convincing. Moreover the writing is confusing at times. See below for details. Quality: I think some of the techniques could be described more carefully to better convey the intuition. Clarity: Some of the derivations and intuitions could be explained in more detail. Originality: The suggested idea is great. Significance: Since the experimental setup is somewhat limited according to my opinion, significance is hard to judge at this point in time. Detailed comments: ——— 1. I think the clarity of the paper would benefit significantly from fixes to inaccuracies. E.g., alpha-expansion and belief propagation are not `scene-understanding algorithms’ but rather approaches for optimizing energy functions. Computing the MAP state of an SSPN in time sub-linear in the network size seems counterintuitive because it means we are not allowed to visit all the nodes in the network. The term `deep probabilistic model’ should probably be defined. The paper states that InferSSPN computes `the approximate MAP state of the SSPN (equivalently, the optimal parse of the image)’ and I’m wondering how the `approximate MAP state* can be optimal. Etc. 2. Albeit being formulated for scene understanding tasks, no experiments demonstrate the obtained results of the proposed technique. To assess the applicability of the proposed approach a more detailed analysis is required. More specifically, the technique is evaluated on a subset of images which makes comparison to any other approach impossible. According to my opinion, either a conclusive experimental evaluation using, e.g., IoU metric should be given in the paper, or a comparison to publicly available results is possible. 3. To simplify the understanding of the paper a more intuitive high-level description is desirable. Maybe the authors can even provide an intuitive visualization of their approach.