Patent Publication Number: US-2021182675-A1

Title: Computer Vision Systems and Methods for End-to-End Training of Convolutional Neural Networks Using Differentiable Dual-Decomposition Techniques

Description:
RELATED APPLICATIONS 
     This application claims priority to U.S. Provisional Patent Application Ser. No. 62/947,874 filed on Dec. 13, 2019, the entire disclosure of which is hereby expressly incorporated by reference. 
    
    
     BACKGROUND 
     Field of the Disclosure 
     The present disclosure relates generally to the field of computer vision. More specifically, the present disclosure relates to computer vision systems and methods for end-to-end training of convolutional neural networks using differentiable dual-decomposition techniques. 
     Related Art 
     Modern computer vision approaches generally utilize convolutional neural networks (CNNs) that excel at hierarchal feature extraction. Conventional computer vision approaches generally utilize conditional random fields (CRFs) that excel at modeling flexible higher order interactions. The benefits of CNNs and CRFs are complementary, and as such, are often combined. However, these approaches generally utilize a mean-field (MF) approximation technique which does not directly optimize a real problem. 
     Therefore, there is a need for computer vision systems and methods which can utilize a deep network architecture to provide an alternative to the MF approximation technique for dual-decomposition base approaches to CRF optimization while improving the ability of computer systems to more efficiently process data. These and other needs are addressed by the computer vision systems and methods of the present disclosure. 
     SUMMARY 
     The present disclosure relates to computer vision systems and methods for end-to-end training of convolutional neural networks using differentiable dual-decomposition techniques. In particular, the system allows for segmenting an attribute of an image using a convolutional neural network and a conditional random field that learn to perform semantic image segmentation. Additionally, the system trains the convolutional neural network and the conditional random field using a fixed point algorithm for dual-decomposition and a plurality of images of a dataset. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The foregoing features of the disclosure will be apparent from the following Detailed Description, taken in connection with the accompanying drawings, in which: 
         FIG. 1  is a diagram illustrating an embodiment of the system of the present disclosure; 
         FIG. 2  is a flowchart illustrating overall processing steps carried out by the system of the present disclosure; 
         FIG. 3  is a flowchart illustrating step  52  of  FIG. 2  in greater detail; 
         FIG. 4  is a flowchart illustrating step  70  of  FIG. 3  in greater detail; 
         FIG. 5  is a diagram illustrating decomposition processing carried out by the system of the present disclosure according to step  96  of  FIG. 4 ; 
         FIG. 6  is a diagram illustrating a fixed-point algorithm for dual-decomposition implemented by the system of the present disclosure; 
         FIG. 7  is a flowchart illustrating step  72  of  FIG. 3  in greater detail; 
         FIG. 8  is a flowchart illustrating step  74  of  FIG. 3  in greater detail; 
         FIG. 9  is a flowchart illustrating step  76  of  FIG. 3  in greater detail; 
         FIG. 10  is a diagram illustrating an algorithm for implementing forward and backward passes for determining smoothed-max-marginals and their gradients; 
         FIG. 11  is a diagram illustrating an algorithm for implementing forward and backward passes for determining max-marginals and their gradients; 
         FIG. 12  is a compilation of images illustrating processing steps carried out by the system of the present disclosure; 
         FIG. 13  is a table illustrating quantitative processing results based on different network models; and 
         FIG. 14  is a diagram illustrating hardware and software components capable of being utilized to implement an embodiment of the system of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     The present disclosure relates to computer vision systems and methods for end-to-end training of convolutional neural networks using differentiable dual-decomposition, as discussed in detail below in connection with  FIGS. 1-14 . 
     End-to-end training of combined convolutional neural networks (CNNs) and conditional random fields (CRFs) generally improves quality in pixel labeling tasks in comparison with decoupled training. Conventional end-to-end trainable systems are generally based on a mean-field (MF) approximation to the CRF. The MF approximation approximates a posterior distribution of a CRF via a set of variational distributions, which are of simple forms and amendable to an analytical solution. This approximation is utilized in end-to-end trainable frameworks where the CRF is combined with a CNN because MF iterations can be unrolled as a set of recurrent convolutional and arithmetic layers and thus is fully differentiable. 
     However, despite computational efficiency and straight forward implementation, MF based approaches suffer from the assumptions that the underlying latent variables are independent and that the variational distributions are simple. Accordingly, an exact maximum-a-posteriori (MAP) solution of a CRF cannot be realized with MF iterations because in practical CRFs latent variables are generally not independent and posterior distributions are complex and cannot be analytically expressed. For example, to employ an efficient inference, a known approach can model pairwise potentials as a weighted sum of a set of Gaussian kernels over pairs of feature vectors which penalizes or yields a very small boost to dissimilar feature vectors and therefore tends to smooth-out pixel labels spatially. Alternatively, a more general pairwise model can encourage an assignment of different labels to a pair of dissimilar feature vectors, if they actually belong to different semantic classes in ground-truth. 
     The system of the present disclosure describes a dual-decomposition solution to MAP inference of a Markov random field (MRF). It should be understood that a CRF can be considered as an MRF conditioned on input data and therefore inference methods on an MRF are applicable to a CRF if input data and potential functions are fixed per inference. Dual-decomposition does not make assumptions about a distribution of a CRF but instead formulates the MAP inference problem as an energy maximization problem. Directly solving this problem on a graph with cycles is generally nondeterministic polynomial time (NP) hard. However, dual-decomposition relaxes the original problem by decomposing the graph into a set of trees that cover each edge and vertex at least once such that MAP inferences on these tree-structured sub-problems can be executed efficiently via dynamic programming while the solution to the original problem can be realized via dual-coordinate descent or sub-gradient descent utilizing solutions from the sub-problems. Dual decomposition is considered to be an approximate algorithm in that it can minimize a convex upper bound of an original problem and the solutions of the sub-problems do not necessarily agree with each other. However, the approximate primal objective can be realized via heuristic decoding at any time during optimization. Further, the duality-gap describes a quality of the current solution such that a gap of zero yields an optimal solution. In contrast, the MF approximation only yields a local minimum of the Kullback Leibler (KL) divergence. 
     With respect to learning parameters for CNNs and CRFs, the MF approximation is fully differentiable and therefore trainable with back-propagation. Known dual-decomposition approaches rely on sub-gradient descent or dual-coordinate-descent to maximize the energy objectives and therefore are not immediately differentiable with respect to CNN parameters that generate CRF potentials. Max-margin learning is generally utilized in such a situation for linear and non-linear deep neural network models. However, these models require that the MAP inference routine be sufficiently robust to determine reasonable margin violators to enable learning. This can be problematic when the underlying CRF potentials are parameterized by non-linear and complex CNNs instead of linear classifiers as in traditional max-margin frameworks (e.g., a structured support vector machine (SVM)). In contrast, the fixed-point iteration of the system of the present disclosure is derived from a special case of more general block coordinate descent algorithms and optimizes the CRF energy directly with respect to the CRF potentials and thus can be jointly trained with CNNs via back-propagation. Additionally, instead of employing a gradient predictor for MAP inference which can provide minimal theoretical guarantees, the system of the present disclosure derives a differentiable dual-decomposition algorithm for MAP inference including properties such as dual-monotonicity and provable optimality. 
     The systems and methods of the present disclosure derive a fixed-point algorithm having dual-monotonicity and dual-differentiability based on dual-decomposition that overcomes the aforementioned problems. In particular, a smoothed-max operator with negative-entropy regularization provides for the fixed-point algorithm to be fully-differentiable while remaining monotone for the dual objective. Additionally, the system provides an efficient and highly parallel graphics processing unit implementation for the algorithm. Accordingly, the system of the present disclosure can perform end-to-end training of CNNs and CRFs by differentiating through dual-composition layers thereby improving semantic segmentation accuracy on the PASCAL Visual Object Classes (VOC)  2012  dataset over baseline models. 
     Turning to the drawings,  FIG. 1  is a diagram  10  illustrating an embodiment of the system  10  of the present disclosure. The system  10  includes a neural network  14  which receives input data  12  and includes a fixed point algorithm module  16 , a model training system  18 , and a trained model system  20 . The neural network  14  also receives training input data  22  and validation input data  24 , and outputs output data  26 . The neural network  14  can be any type of neural network or machine learning system, or combination thereof, modified in accordance with the present disclosure to include the components shown and described herein. For example, the neural network  14  can be a deep convolutional neural network combined with a conditional random field and capable of, for example, semantic image segmentation and can use one or more frameworks (e.g., interfaces, libraries, tools, etc.). It should be understood that the neural network  14  can include the fixed point algorithm module  16  as a layer of the neural network  14 . 
       FIG. 2  is a flowchart  50  illustrating overall processing steps carried out by the system  10  of the present disclosure. Beginning in step  52 , the fixed point algorithm module  16  implements a monotone fixed point algorithm for dual-decomposition. As mentioned above, the algorithm is a differentiable dual-composition algorithm for MAP inference having theoretical properties such as dual-monotonicity and provable optimality. In step  54 , the model training system  18  trains the neural network  14  by applying the fixed point algorithm on the training input data  22 . In particular, the model training system  18  trains the neural network  14  to perform semantic image segmentation. The training input data  22  can include, but is not limited to, a predetermined number of images. In this regard, it is noted that the training input data  22  can be a set of images upon which a semantic segmentation task will be performed, such as the PASCAL VOC  2012  data set. It should be understood that the neural network  14  can be any type of neural network or machine learning system, or combination thereof. Then, in step  56 , the trained model system  20  processes validation input data  24  to perform semantic image segmentation. The validation input data  24  can include, but is not limited to, a predetermined number of images, such as (but not limited to) the PASCAL VOC  2012  data set. 
       FIG. 3  is a flowchart illustrating step  52  of  FIG. 2  in greater detail. Beginning in step  70 , the system  10  derives a fixed-point algorithm for dual-decomposition of a MAP inference problem. Then, in step  72 , the system  10  decodes primal results utilizing some intermediate max-marginals {μ t } with {x t *} of the fixed-point algorithm where the intermediate max-marginals {μ t } with {x t *} do not necessarily agree on each other. In step  74 , the system  10  processes the decoded results using a smoothed-max operator with negative entropy regularization to make the fixed-point algorithm fully differentiable. The forward pass is a log-sum-exp operator while the backward pass is a soft-max operator. Lastly, in step  76 , the system  10  creates a parallel dynamic program layer for the fixed-point algorithm to compute horizontal/vertical marginals on a pixel grid (as shown in line 6 of the fixed-point algorithm for dual-decomposition of  FIG. 6 ). 
       FIG. 4  is a flowchart illustrating step  70  of  FIG. 3  in greater detail. Beginning in step  100 , the system  10  determines the MAP inference problem. The system  10  performs per-pixel labeling on an image   with a size M×N to produce a label l∈  for each pixel in the image   (e.g., semantic classes or disparity). A CRF endeavors to model a conditional distribution P(L| ) with L∈   |M×N| . When modeled jointly with a CNN ƒ parameterized by θ, the conditional distribution is defined by Equation 1 below as: 
     
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         L 
                          
                         ℐ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       Z 
                     
                      
                     
                       exp 
                        
                       
                         ( 
                         
                           
                             f 
                             θ 
                           
                            
                           
                             ( 
                             
                               L 
                               ; 
                               ℐ 
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   1 
                 
               
             
           
         
       
     
     where Z=Σ L∈       |M×N|   exp(ƒ θ (L; )) is a normalizing constant that does not depend on L. It should be understood that the system  10  considers pairwise potential functions defined by Equation 2 below as: 
     
       
         
           
             
               
                 
                   
                     
                       f 
                       θ 
                     
                      
                     
                       ( 
                       
                         L 
                         ; 
                         ℐ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                        
                       
                         
                           ψ 
                           θ 
                         
                          
                         
                           ( 
                           
                             
                               l 
                               i 
                             
                             ; 
                             ℐ 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           ij 
                           ∈ 
                           E 
                         
                       
                        
                       
                         
                           φ 
                           θ 
                         
                          
                         
                           ( 
                           
                             
                               l 
                               i 
                             
                             , 
                             
                               
                                 l 
                                 j 
                               
                               ; 
                               ℐ 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   2 
                 
               
             
           
         
       
     
     where ψ(⋅) and ϕ(⋅,⋅) are neural networks modeling unary and pairwise potential functions. V denotes the set of all pixel locations and E denotes the pairwise edges in the graph. Determining the mode (or a maximum of the modes in a multi modal case) of the posterior distribution of Equation 1 is equivalent to determining the maximizing configuration L* of L to Equation 2 as given by Equation 3 and Equation 4 below: 
     
       
         
           
             
               
                 
                   
                     L 
                     * 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         max 
                       
                       L 
                     
                      
                     
                       
                         f 
                         θ 
                       
                        
                       
                         ( 
                         
                           L 
                           ; 
                           ℐ 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   3 
                 
               
             
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         
                           L 
                           * 
                         
                          
                         ℐ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       Z 
                     
                      
                     
                       exp 
                       ( 
                       
                         
                           max 
                           L 
                         
                          
                         
                           
                             f 
                             θ 
                           
                            
                           
                             ( 
                             
                               L 
                               ; 
                               ℐ 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   4 
                 
               
             
           
         
       
     
     The system  10  maximizes the objective function ƒ θ (L;  ) w.r.t. L when conducting test time optimization and therefore the optimization problem can be defined by Equation 5 as: 
     
       
         
           
             
               
                 
                   
                     max 
                     L 
                   
                    
                   
                     
                       f 
                       θ 
                     
                      
                     
                       ( 
                       
                         L 
                         ; 
                         ℐ 
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   5 
                 
               
             
           
         
       
     
     In particular, Equation 5 denotes the MAP inference problem and the system  10  solves this problem via dual-decomposition as described in further detail below. 
     In step  92 , the system  10  defines a graph G=(V, E) with M×N vertices representing a two-dimensional (2D) grid to define the MAP inference problem on the MRF. Each vertex can select one of the states in the label set  ={1, 2, . . . , L}. The system  10  defines a labeling of the 2D grid as L∈   |M×N|  and a state of the vertex at a location i as l i . For simplicity, the system  10  discards a dependency on θ and   for all potential functions ƒ, ϕ, and ψ during the derivation of the inference algorithm since they are fixed for each inference. Accordingly, the MAP inference problem on the MRF is defined by Equation 6 as: 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       L 
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                        
                       
                         ψ 
                          
                         
                           ( 
                           
                             l 
                             i 
                           
                           ) 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         ij 
                         ∈ 
                         E 
                       
                     
                      
                     
                       φ 
                        
                       
                         ( 
                         
                           
                             l 
                             i 
                           
                           , 
                           
                             l 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   6 
                 
               
             
           
         
       
     
     In step  94 , the system  10  transforms the MAP inference problem defined by Equation 6 to an integer linear programming (ILP) problem. The system  10  denotes x i (l) as a distribution corresponding to vertex/location i and x ij (l′, l) as a joint distribution corresponding to a pair of vertices/locations i, j. The system  10  defines a constraint set X G  to enforce the pairwise and unary distribution to be consistent and discrete as follows: 
     
       
         
           
             
                
                
             
             = 
             
               { 
               
                 x 
                  
                 
                   
                     
                       
                         
                           
                             
                               ∑ 
                               l 
                             
                              
                             
                               
                                 x 
                                 i 
                               
                                
                               
                                 ( 
                                 l 
                                 ) 
                               
                             
                           
                           = 
                           1 
                         
                         , 
                         
                           ∀ 
                           
                             i 
                             ∈ 
                             V 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 l 
                                 ′ 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   , 
                                   
                                     l 
                                     ′ 
                                   
                                 
                                 ) 
                               
                             
                           
                           = 
                           
                             
                               x 
                               i 
                             
                              
                             
                               ( 
                               l 
                               ) 
                             
                           
                         
                         , 
                         
                           ∀ 
                           
                             
                               ( 
                               
                                 ij 
                                 , 
                                 l 
                               
                               ) 
                             
                             ∈ 
                             
                               E 
                               × 
                               ℒ 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             
                               x 
                               i 
                             
                              
                             
                               ( 
                               l 
                               ) 
                             
                           
                           ∈ 
                           
                             { 
                             
                               0 
                               , 
                               1 
                             
                             } 
                           
                         
                         , 
                         
                           
                             
                               x 
                               ij 
                             
                              
                             
                               ( 
                               
                                 l 
                                 , 
                                 
                                   l 
                                   ′ 
                                 
                               
                               ) 
                             
                           
                           ∈ 
                           
                             { 
                             
                               0 
                               , 
                               1 
                             
                             } 
                           
                         
                       
                     
                   
                 
               
               } 
             
           
         
       
     
     As such, Equation 6 can be rewritten as an ILP as defined by Equation 7: 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       x 
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                        
                       
                         
                           ψ 
                           i 
                         
                         · 
                         
                           x 
                           i 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         ij 
                         ∈ 
                         E 
                       
                     
                      
                     
                       
                         φ 
                         ij 
                       
                       · 
                       
                         x 
                         ij 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   7 
                 
               
             
             
               
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                      
                     x 
                   
                   ∈ 
                   
                      
                      
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     where x i  and ψ i  are | | dimensional vectors denoting vertex distribution and scores at vertex i, while x ij  and ϕ ij  are | | 2  dimensional vectors denoting edge distribution and scores for a pair of vertices (i,j). 
     In step  96 , the system  10  decomposes the graph G with vertical and horizontal connections of arbitrary length into sets of horizontal and vertical chain sub-problems. Solving Equation 7 is generally NP-hard given an arbitrary graph with cycles. The system  10  tackles Equation 7 by first decomposing the graph G into a set of tree structured and solvable sub-problems such that each edge and vertex of the graph G=(V, E) is covered at least once by these sub-problems. Subsequently, the system  10  adds a set of additional constraints to enforce that maximizing configurations of each sub-problem agree with one another. These constraints are then relaxed by Lagrangian relaxation and the relaxed objective can be optimized by sub-gradient ascent or fixed point updates. 
     In particular, the system  10  defines a set of trees T that covers each vertex i∈V and edge ij∈E at least once. The set of variables corresponding to vertices and edges in tree t∈T and all sets of such variables are denoted as x t  and {x t }. Additionally, T(i) and T(ij) respectively denote the set of trees that cover vertex i∈V and edge ij∈E. In view of the foregoing, Equation 7 can be rewritten as Equation 8 below: 
     
       
         
           
             
               
                 
                   
                     max 
                     
                       
                         { 
                         
                           x 
                           i 
                         
                         } 
                       
                       , 
                       x 
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               V 
                             
                           
                            
                           
                             
                               x 
                               i 
                               t 
                             
                             · 
                             
                               ψ 
                               i 
                               t 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               ij 
                               ∈ 
                               E 
                             
                           
                            
                           
                             
                               x 
                               ij 
                               t 
                             
                             · 
                             
                               φ 
                               ij 
                               t 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   8 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             x 
                             i 
                             t 
                           
                           = 
                           
                             x 
                             i 
                           
                         
                         , 
                       
                     
                     
                       
                         
                           ∀ 
                           
                             i 
                             ∈ 
                             V 
                           
                         
                         , 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             x 
                             ij 
                             t 
                           
                           = 
                           
                             x 
                             ij 
                           
                         
                         , 
                       
                     
                     
                       
                         
                           ∀ 
                           
                             ij 
                             ∈ 
                             E 
                           
                         
                         , 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               ij 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     As mentioned above, the system  10  decomposes the graph G with vertical and horizontal connections of arbitrary length into sets of horizontal and vertical chain sub-problems. For example,  FIG. 5  is a diagram  110  illustrating decomposition processing carried out by the system  10  according to step  96  of  FIG. 4 . In particular,  FIG. 5  illustrates the decomposition of a grid-graph G including long range interactions into sets of horizontal chains  122   a ,  124   a  and vertical chains  122   b ,  124   b . The system  10  utilizes stride  1  and stride  2  edges for the system models. It should be understood that the derivation of the monotone fixed point algorithm for dual-decomposition described in further detail below with respect to step  98  of  FIG. 4  holds for general graphs with arbitrary connections. 
     Referring back to step  96  of  FIG. 4 , by decomposing the graph G into sets of horizontal and vertical chain sub-problems, each node is covered multiple times while each edge is covered once and the system  10  replicates their scores by the number of times they are covered by the sub-problems. It should be understood that the replicated scores {ψ t , ϕ t } satisfy Equation 9 below as: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                           
                             T 
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         ψ 
                         i 
                         t 
                       
                     
                     = 
                     
                       ψ 
                       i 
                     
                   
                   , 
                   , 
                   
                     
                       φ 
                       ij 
                       t 
                     
                     = 
                     
                       φ 
                       ij 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   9 
                 
               
             
           
         
       
     
     Without a replicated edge, Equation 8 can be rewritten as Equation 10 below: 
     
       
         
           
             
               
                 
                   
                     max 
                     
                       
                         { 
                         
                           x 
                           i 
                         
                         } 
                       
                       , 
                       x 
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               V 
                             
                           
                            
                           
                             
                               x 
                               i 
                               t 
                             
                             · 
                             
                               ψ 
                               i 
                               t 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               ij 
                               ∈ 
                               E 
                             
                           
                            
                           
                             
                               x 
                               ij 
                               t 
                             
                             · 
                             
                               φ 
                               ij 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   10 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             x 
                             i 
                             t 
                           
                           = 
                           
                             x 
                             i 
                           
                         
                         , 
                       
                     
                     
                       
                         
                           ∀ 
                           
                             i 
                             ∈ 
                             V 
                           
                         
                         , 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Applying Lagrangian multipliers to relax the second set of constraints (e.g., agreement constraints among sub-problems) yields Equation 11 below as: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         λ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       max 
                       
                         
                           { 
                           
                             x 
                             t 
                           
                           } 
                         
                         , 
                         x 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                                 i 
                               
                               · 
                               
                                 ( 
                                 
                                   
                                     ψ 
                                     i 
                                     i 
                                   
                                   + 
                                   
                                     λ 
                                     i 
                                     t 
                                   
                                 
                                 ) 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 ij 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                                 t 
                               
                               · 
                               
                                 φ 
                                 ij 
                               
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                               
                               · 
                               
                                 λ 
                                 i 
                                 t 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   11 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         x 
                         t 
                       
                     
                     ∈ 
                     
                        
                        
                     
                   
                   , 
                   
                     ∀ 
                     
                       i 
                       ∈ 
                        
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     where λ t  and {λ t } respectively denote dual variables for sub-problem t and the set of all sub-problems. λ i   t  denotes dual variables for sub-problem t at location i and has a dimension of L (e.g., the number of labels/states). As such, the system  10  can determine whether if Σ t∈τ(i) λ i   t ≠0 for any i∈V, then λ i   t =+∞. Thus the system  10  enforces and it follows that Σ i∈V Σ t∈τ x i ·λ i   t =0. Therefore, {x} can be eliminated from Equation 11 to yield Equation 12 as follows: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         λ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       max 
                       
                         { 
                         
                           x 
                           t 
                         
                         } 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                                 t 
                               
                               · 
                               
                                 ( 
                                 
                                   
                                     ψ 
                                     i 
                                     t 
                                   
                                   + 
                                   
                                     λ 
                                     i 
                                     t 
                                   
                                 
                                 ) 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 ij 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                                 t 
                               
                               · 
                               
                                 φ 
                                 ij 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   12 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 t 
                                 ∈ 
                                 
                                    
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                             
                              
                             
                               λ 
                               i 
                               t 
                             
                           
                           = 
                           0 
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     In step  98 , the system  10  derives a block coordinate-descent algorithm that monotonically decreases the objective of Equation 12. It is generally convenient to initialize λ&#39;s as 0 and fold them into {ψ t } terms such that the system  10  optimizes an equivalent objective to Equation 12 over {ψ t } as defined by Equation 13: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         ψ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       max 
                       
                         { 
                         
                           x 
                           t 
                         
                         } 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                                 t 
                               
                               · 
                               
                                 ψ 
                                 i 
                                 t 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 ij 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                                 t 
                               
                               · 
                               
                                 φ 
                                 ij 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   13 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 l 
                                 ∈ 
                                 
                                    
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                             
                              
                             
                               ψ 
                               i 
                               t 
                             
                           
                           = 
                           
                             ψ 
                             i 
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     The system  10  fixes the dual variables for all sub-problems at all locations except for those at one location k and optimizes with respect to the vector ψ k   t , ∀t∈τ(k) and primal variables {x t }. The system  10  also defines 
     
       
         
           
             
               
                 μ 
                 k 
                 t 
               
                
               
                 ( 
                 l 
                 ) 
               
             
             = 
             
               
                 
                   ψ 
                   k 
                   t 
                 
                  
                 
                   ( 
                   l 
                   ) 
                 
               
               + 
               
                 
                   max 
                   
                     
                       
                         x 
                         t 
                       
                       ∈ 
                       
                          
                          
                       
                     
                     
                       
                         
                           x 
                           k 
                           t 
                         
                          
                         
                           ( 
                           l 
                           ) 
                         
                       
                       = 
                       1 
                     
                   
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                       
                         V 
                          
                         \ 
                          
                         k 
                       
                     
                   
                    
                   
                     
                       x 
                       i 
                       t 
                     
                     · 
                     
                       ψ 
                       i 
                       t 
                     
                   
                 
               
               + 
               
                 
                   ∑ 
                   
                     ij 
                     ∈ 
                     E 
                   
                 
                  
                 
                   
                     x 
                     ij 
                     t 
                   
                   · 
                   
                     φ 
                     ij 
                   
                 
               
             
           
         
       
     
     as the max-marginal of sub-problem t at location k with x k   t (l)=1. Similarly, the system  10  defines the max-marginal vector of sub-problem t at location k as μ k   t  and the max energy of sub-problem t as μ t . It should be understood that μ k   t  is a vector value while μ k   t (l) and μ t  are scalar values. For a single location k∈V, a coordinate update to ψ k   t , ∀t∈τ(k) is optimal and can be given by Equation 14 as follows: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ψ 
                         k 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                     ← 
                     
                       
                         
                           ψ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                       - 
                       
                         ( 
                         
                           
                             
                               μ 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               1 
                               
                                  
                                 
                                    
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                  
                               
                             
                              
                             
                               
                                 ∑ 
                                 
                                   
                                     t 
                                     _ 
                                   
                                   ∈ 
                                   
                                      
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                                 
                                     
                                 
                               
                                
                               
                                 
                                   μ 
                                   k 
                                   
                                     t 
                                     _ 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   14 
                 
               
             
             
               
                 
                   
                     ∀ 
                     
                       t 
                       ∈ 
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                   , 
                   
                     
                       l 
                       k 
                     
                     ∈ 
                     ℒ 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     The system  10  aims to optimize the linear program as defined by Equation 15 with respect to the dual variables where the primal variables {x t } are included in the max energy terms μ t  as follows: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           ψ 
                           k 
                           t 
                         
                         ∈ 
                         
                           R 
                           
                              
                             ℒ 
                              
                           
                         
                       
                       
                         
                           
                             μ 
                             i 
                           
                           ∈ 
                           
                             ℝ 
                             
                                
                               ℒ 
                                
                             
                           
                         
                         
                           ∀ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         i 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                       
                           
                       
                     
                      
                     
                       μ 
                       t 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   15 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                         
                             
                         
                          
                         
                           
                             
                               μ 
                               ^ 
                             
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                       + 
                       
                         
                           ψ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                       - 
                       
                         
                           
                             ψ 
                             ^ 
                           
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                     ≤ 
                     
                       μ 
                       t 
                     
                   
                   , 
                   
                     ∀ 
                     
                       t 
                       ∈ 
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           ψ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         ψ 
                         k 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     where {circumflex over (μ)} k   t (l k ) and {circumflex over (ψ)} k   i (l k ) in the first set of constraints are max-marginals and unary potentials at location k after applying the update rule of Equation 14. This set of constraints is derived from the fact that {circumflex over (μ)} k   t (l k )+ψ k   i (l k )−{circumflex over (ψ)} k   i (l k )=μ k   t (l k ), ∀l k ∈  and μ t = μ k   t (l k ). Converting Equation 15 to dual form yields Equation 16 below: 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       
                         
                           
                             
                               α 
                               t 
                             
                             ≥ 
                             0 
                           
                           , 
                           
                             ∀ 
                             
                               t 
                               ∈ 
                               
                                  
                                  
                                 
                                   ( 
                                   k 
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             β 
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           ∈ 
                           
                             ℝ 
                             
                                
                               ℒ 
                                
                             
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                         
                             
                         
                       
                        
                       
                         
                           β 
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                         · 
                         
                           
                             ψ 
                             k 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                       
                        
                       
                         
                           
                             α 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 
                                   μ 
                                   ^ 
                                 
                                 k 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 
                                   ψ 
                                   ^ 
                                 
                                 k 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   16 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             1 
                             - 
                             
                               
                                 ∑ 
                                 
                                   
                                     l 
                                     k 
                                   
                                   ∈ 
                                   ℒ 
                                 
                               
                                
                               
                                 
                                   α 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                           
                           = 
                           0 
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             
                               β 
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 α 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                           
                           = 
                           0 
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     It can be inferred from the second set of constraints that the terms α t (l k )=α   t   (l k ), ∀(l, t )∈τ(k)×τ(k), setting β(l k )=α   t   (l k ) for any  t ∈τ(k) for all l k ∈ , yields the optimization as Equation 17 below: 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       
                         
                           α 
                           i 
                         
                         ≥ 
                         0 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                       
                        
                       
                         
                           
                             α 
                             
                               t 
                               _ 
                             
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                         · 
                         
                           ( 
                           
                             
                               
                                 ψ 
                                 k 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   ∈ 
                                   
                                      
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                                 
                                     
                                 
                               
                                
                               
                                 
                                   
                                     ψ 
                                     ^ 
                                   
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         
                           l 
                           k 
                         
                         ∈ 
                         ℒ 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                         
                           
                             α 
                             
                               t 
                               _ 
                             
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                         · 
                         
                           
                             
                               μ 
                               ^ 
                             
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   17 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       1 
                     
                     - 
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                       
                        
                       
                         
                           α 
                           
                             t 
                             _ 
                           
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     It should be understood that the update rule denoted by Equation 14 satisfies Σ t∈τ(k) {circumflex over (ψ)} k   t =ψ k . As such, Equation 17 can be simplified as Equation 18 below: 
     
       
         
           
             
               
                 
                   
                     max 
                     
                       
                         α 
                         
                           t 
                           _ 
                         
                       
                       ≥ 
                       0 
                     
                   
                    
                   
                     
                       ∑ 
                       
                         
                           l 
                           k 
                         
                         ∈ 
                         ℒ 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                         
                           
                             α 
                             
                               t 
                               _ 
                             
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                         · 
                         
                           
                             
                               μ 
                               ^ 
                             
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   18 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       1 
                     
                     - 
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                       
                        
                       
                         
                           α 
                           
                             t 
                             _ 
                           
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     It should be understood that applying Equation 14 yields {circumflex over (μ)} k   t ={circumflex over (μ)} k     t   , ∀(t, t )∈τ(k)×τ(k). Therefore, Equation 18 is equivalent to  Σ t∈τ(k) {circumflex over (μ)} k   t (l k )=Σ t∈τ(k) {circumflex over (μ)} t . Additionally, applying Equation 14 to a single location yields Σ t∈τ(k) {circumflex over (μ)} t =Σ t∈τ(k) μ t . Thus Equation 15 is equivalent to Equation 18 such that the duality gape of the LP is 0 and the update of Equation 14 is an optimal coordinate update step. 
     In practice, the system  10  could update all ψ&#39;s at once, which, although it may yield slower convergence, may provide for efficient parallel algorithms for modern Graphics Processing Unit (GPU) architectures. Intuitively, a neural network can minimize an empirical risk with respect to the coordinate-descent algorithm of the system  10  since an output from any coordinate-descent step is sub differentiable. 
     A known theorem states that applying an update to ψ i   t , ∀ i ∈V, t∈τ(i) does not increase the objective of Equation 13 where the update is defined by Equation 19 below as: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ψ 
                         i 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           i 
                         
                         ) 
                       
                     
                     ← 
                     
                       
                         
                           ψ 
                           i 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             i 
                           
                           ) 
                         
                       
                       - 
                       
                         
                           1 
                           
                              
                             
                               V 
                               0 
                             
                              
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 μ 
                                 i 
                                 i 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   i 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 1 
                                 
                                    
                                   
                                      
                                      
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                    
                                 
                               
                                
                               
                                 
                                   ∑ 
                                   
                                     
                                       t 
                                       _ 
                                     
                                     ∈ 
                                     
                                        
                                        
                                       
                                         ( 
                                         i 
                                         ) 
                                       
                                     
                                   
                                   
                                       
                                   
                                 
                                  
                                 
                                   
                                     μ 
                                     i 
                                     
                                       i 
                                       _ 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       i 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   19 
                 
               
             
             
               
                 
                   
                     ∀ 
                     
                       i 
                       ∈ 
                       V 
                     
                   
                   , 
                   
                     t 
                     ∈ 
                     
                        
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                   
                   , 
                   
                     
                       l 
                       i 
                     
                     ∈ 
                     ℒ 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     where |V 0 |=max t∈T |V t | and |V t | denotes a number of vertices in sub-problem t. To prove the theorem, {circumflex over (μ)} t  denotes the max energy of sub-problem t after applying the update defined by Equation 19 to {ψ t } and  μ   i   t  denotes the max energy of sub-problem t after applying the update defined by Equation 14 for location i. The changes in objective from updating {ψ t } according to Equation 19 are defined by Equation 20 as: 
     
       
         
           
             
               
                 
                   
                     - 
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                         
                             
                         
                       
                        
                       
                         μ 
                         t 
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                       
                           
                       
                     
                      
                     
                       
                         μ 
                         ^ 
                       
                       t 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   20 
                 
               
             
           
         
       
     
     μ t  can be briefly expanded by Equation 21 as: 
     
       
         
           
             
               
                 
                   
                     μ 
                     t 
                   
                   = 
                   
                     
                       
                         max 
                         
                           x 
                           t 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             ∈ 
                             V 
                           
                           
                               
                           
                         
                          
                         
                           
                             x 
                             i 
                             t 
                           
                           · 
                           
                             ψ 
                             i 
                             t 
                           
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           ij 
                           ∈ 
                           E 
                         
                       
                        
                       
                         
                           x 
                           ij 
                           t 
                         
                         · 
                         
                           φ 
                           ij 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   21 
                 
               
             
             
               
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                      
                     
                       x 
                       t 
                     
                   
                   ∈ 
                   
                      
                      
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     In view of the above, μ t  can be considered to be a convex function of ψ t  because μ t  is the maximum of a set of affine functions (each of which is defined by a point in X G ) of ψ t . When |V 0 |=max t∈T |V t |, Jensen&#39;s Inequality can be applied to the second term of Equation 20 as follows: 
     
       
         
           
             
               
                 Eq 
                 . 
                 
                     
                 
                  
                 
                   ( 
                   20 
                   ) 
                 
               
               ≤ 
               
                 
                   - 
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                     
                      
                     
                       μ 
                       t 
                     
                   
                 
                 + 
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                        
                     
                   
                    
                   
                     ( 
                     
                       
                         
                           
                             
                                
                               
                                 V 
                                 0 
                               
                                
                             
                             - 
                             
                                
                               
                                 V 
                                 t 
                               
                                
                             
                           
                           
                              
                             
                               V 
                               0 
                             
                              
                           
                         
                          
                         
                           μ 
                           t 
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             ∈ 
                             
                               V 
                               t 
                             
                           
                         
                          
                         
                           
                             1 
                             
                                
                               
                                 V 
                                 0 
                               
                                
                             
                           
                            
                           
                             
                               μ 
                               _ 
                             
                             i 
                             t 
                           
                         
                       
                     
                     ) 
                   
                 
               
             
             = 
             
               
                 
                   1 
                   
                      
                     
                       V 
                       0 
                     
                      
                   
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                        
                     
                   
                    
                   
                     
                       ∑ 
                       
                         i 
                         ∈ 
                         
                           V 
                           t 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             μ 
                             _ 
                           
                           i 
                           t 
                         
                         - 
                         
                           μ 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   1 
                   
                      
                     
                       V 
                       0 
                     
                      
                   
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                       
                         V 
                         t 
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         i 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             μ 
                             _ 
                           
                           i 
                           t 
                         
                         - 
                         
                           μ 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
     Here it is observed that Σ t∈τ(i)   μ   i   t  corresponds to Equation 18 while Σ t∈τ(i) μ t  corresponds to Equation 15. Since Equation 15 and Equation 18 are primal and dual of an LP, then Equation 18 is less than or equal to Equation 15. Therefore Σ t∈τ(i) ( μ   i   t −μ t )≤0 which results in Equation 20≤0. As such, the update of Equation 19 constitutes a non-increasing step to the objective of Equation 13. 
     It should be understood that the update rules of the system  10  differ from conventional tree-block coordinate descent and its variant. For example, Equation 19 avoids reparameterization of edge potentials which can be expensive when forming coordinate-descent as differential layers, as memory consumption grows linearly with the number of coordinate-descent steps while each step requires  (|E|×| | 2 ) memory for storing edge potentials. The update rules of the system  10  are similar to a fixed-point update of a known approach but the monotone fixed-point update of this known approach is effective on a single covering tree and therefore is not amenable for parallel computation. Furthermore, for a simultaneous update to all locations, the system  10  proves a monotone update step-size of 
     
       
         
           
             1 
             
               
                 max 
                 
                   i 
                   ∈ 
                   T 
                 
               
                
               
                  
                 
                   V 
                   t 
                 
                  
               
             
           
         
       
     
     while the known approach merely proves a monotone update step-size 
     
       
         
           
             1 
             
                
               V 
                
             
           
         
       
     
     which is smaller. The coordinate-descent fixed-point update algorithm is described in further detail below as Algorithm 1 with respect to  FIG. 6 . 
       FIG. 6  is a diagram  130  illustrating the fixed-point algorithm for dual-decomposition (Algorithm 1) implemented by the system  10 . Algorithm 1 provides several advantages. For example, Algorithm 1 is parallelizable with modern deep learning frameworks as the sub-problems t∈τ can be solved in parallel and operations can be defined in forms of a sum and a max of matrices. Additionally, unlike subgradient-based methods, the fixed-point update is fully sub-differentiable. It should be understood that the fixed-point update is not differentiable everywhere because of the utilization of max operators when computing max-marginals as described in further detail below with respect to  FIG. 8 . Accordingly, Algorithm 1 is sub-differentiable except for the decoding of a final primal solution as described in further detail below with respect to  FIG. 7 . 
       FIG. 7  is a flowchart illustrating step  72  of  FIG. 3  in greater detail. It should be understood that Algorithm 1 does not always converge. Therefore, in step  140  the system  10  decodes primal results given intermediate max-marginals {μ t } and {x t *} that do not necessarily agree on each other. In particular, the system  10  can decode x i * given μ i   t (l), ∀l∈{1, . . . L}, ∀t∈τ(i) as defined by Equation 22 below: 
     
       
         
           
             
               
                 
                   
                     x 
                     i 
                     * 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         max 
                       
                       
                         l 
                         ∈ 
                         
                           { 
                           
                             1 
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             L 
                           
                           } 
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           μ 
                           i 
                           t 
                         
                          
                         
                           ( 
                           l 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   22 
                 
               
             
           
         
       
     
     Equation 22 is neither differentiable nor sub-differentiable and is the only non-differentiable portion of Algorithm 1. Accordingly, in step  142 , the system  10  applies a softmax function on Σ t∈τ(i) μ i   t  where μ i   t  is a vector of length L to output a probability distribution over L labels defined by Equation 23 below: 
     
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         x 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       exp 
                       ( 
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                         
                          
                         
                           μ 
                           i 
                           t 
                         
                       
                       ) 
                     
                     
                       
                         ∑ 
                         
                           
                             l 
                             ′ 
                           
                           ∈ 
                           
                             { 
                             
                               1 
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               L 
                             
                             } 
                           
                         
                       
                        
                       
                         exp 
                         ( 
                         
                           
                             ∑ 
                             
                               t 
                               ∈ 
                               
                                  
                                  
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                             
                           
                            
                           
                             
                               μ 
                               i 
                               t 
                             
                             ( 
                             
                               l 
                               ′ 
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   23 
                 
               
             
           
         
       
     
     In step  144 , the system  10  utilizes one-hot encoding of pixel-wise labels as the ground truth. Then, in step  146 , the system  10  determines cross-entropy loss and gradients utilizing the softmax of the max-marginals which is sub-differentiable. Thus, the system  10  is end-to-end trainable with respect to CNN parameters θ. 
     Referring back to  FIG. 6 , it should be understood that line 6 of Algorithm 1 is indicative of dynamic programming over trees. The system  10  can expand max-marginals of any i∈V, t∈τ recursively as defined by Equation 24: 
     
       
         
           
             
               
                 
                   
                     
                       μ 
                       i 
                       t 
                     
                     ( 
                     l 
                     ) 
                   
                   = 
                   
                     
                       
                         ψ 
                         i 
                         t 
                       
                        
                       
                         ( 
                         l 
                         ) 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           max 
                           
                             l 
                             ′ 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 φ 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   , 
                                   
                                     l 
                                     ′ 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 μ 
                                 j 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   ′ 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   24 
                 
               
             
           
         
       
     
     where C(i) denotes a set of neighbors of node i. The max operator is only sub-differentiable. Common activation functions in neural networks such as Rectified Linear Unit (ReLU) and leaky ReLU are also based on a max operation and are thus sub-differentiable. In practice, the parameters for generating the {ψ, ϕ} terms are often initialized from zero-mean uniform Gaussian distributions. As such, at a start of training the {ψ, ϕ} terms are near-identical over classes and locations while max(⋅) over such terms can be random. It should be understood that in a backward pass, the gradient ∂L/∂μ i   t (l) will only flow through the maximum of the max operator which can hinder learning progression and can yield inferior training and testing results. Accordingly, the system  10  implements a smoothed-max operator with negative-entropy regularization, whose forward pass is a log-sum-exp operator while the backward pass is a soft-max operator. 
       FIG. 8  is a flowchart illustrating step  74  of  FIG. 3  in greater detail. In particular,  FIG. 8  illustrates processing steps for implementing a smoothed-max operator with negative-entropy regularization. Beginning in step  170 , the system  10  denotes y={y 1 , . . . , y L } as an input of L real values. Then, in steps  172  and  174 , the system  10  respectively defines a forward pass of the smoothed-max operator max Ω (y) by Equation 25 as: 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       Ω 
                     
                      
                     
                       ( 
                       y 
                       ) 
                     
                   
                   = 
                   
                     γ 
                      
                     
                         
                     
                      
                     
                       log 
                       ( 
                       
                         
                           ∑ 
                           l 
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 y 
                                 l 
                               
                               / 
                               γ 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   25 
                 
               
             
           
         
       
     
     and defines a gradient of the forward pass of the smoothed-max operator max Ω (y) by Equation 26 as: 
     
       
         
           
             
               
                 
                   
                     ∇ 
                     
                         
                     
                      
                     
                       
                         max 
                         Ω 
                       
                        
                       
                         ( 
                         y 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       exp 
                        
                       
                         ( 
                         
                           y 
                           / 
                           γ 
                         
                         ) 
                       
                     
                     
                       
                         ∑ 
                         l 
                       
                        
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               y 
                               l 
                             
                             / 
                             γ 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   26 
                 
               
             
           
         
       
     
     where γ denotes a positive value that controls a strength of the convex regularization. It should be understood that the gradient vector defined by Equation 26 is indicative of a softmax over input values. This ensures that gradients from the loss layer can flow equally through input logits when inputs are near-identical thereby facilitating an initialization of the training process. It should also be understood that the negative-entropy regularized smoothed-max operator of Equation 25 satisfies associativity and distributivity, and that for tree-structured graphs, the smoothed-max-energy determined via a recursive dynamic program is equivalent to the smoothed-max over the combinatorial space X G . As described in detail below, Algorithm 1 can optimize a convex upper bound of Equation 13 when replacing a standard max with the smoothed-max defined by Equation 25 while both Equations 14 and 19 still hold. The system  10  provides for faster convergence of Algorithm 1 when the smoothed-max is utilized with a reasonable γ (e.g., γ=1.0 or 2.0). 
     For simplicity and to prove that Equations 14 and 19 still hold for a monotone fixed-point algorithm for dual-composition with smoothed-max, the dual-decomposition objective (e.g., Equation 13) is restated as Equation 27 below: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         ψ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       max 
                       
                         { 
                         
                           x 
                           t 
                         
                         } 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                                 t 
                               
                               · 
                               
                                 ψ 
                                 i 
                                 t 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 ij 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                                 t 
                               
                               · 
                               
                                 φ 
                                 ij 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   27 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 t 
                                 ∈ 
                                 
                                    
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                             
                              
                             
                               ψ 
                               i 
                               t 
                             
                           
                           = 
                           
                             ψ 
                             i 
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Since x t &#39;s are independent of each other ∀t∈τ, the max can be moved to a right of τ t∈τ  to yield Equation 28: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         ψ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                     
                      
                     
                       
                         max 
                         
                           x 
                           t 
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 V 
                               
                             
                              
                             
                               
                                 x 
                                 i 
                                 t 
                               
                               · 
                               
                                 ψ 
                                 i 
                                 t 
                               
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 ij 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 x 
                                 ij 
                                 t 
                               
                               · 
                               
                                 φ 
                                 ij 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   28 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                       
                     
                     
                       
                         
                           
                             x 
                             t 
                           
                           ∈ 
                           
                              
                              
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           t 
                           ∈ 
                            
                         
                       
                     
                   
                   
                     
                       
                           
                       
                     
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 t 
                                 ∈ 
                                 
                                    
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                             
                              
                             
                               ψ 
                               i 
                               t 
                             
                           
                           = 
                           
                             ψ 
                             i 
                           
                         
                         , 
                       
                     
                     
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           V 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     The max can be replaced with the smoothed-max as defined by Equation 25 to yield a new objective as defined by Equation 29: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       { 
                       
                         ψ 
                         t 
                       
                       } 
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                     
                      
                     
                       γ 
                        
                       
                           
                       
                        
                       log 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   29 
                 
               
             
             
               
                 
                   
                     ∑ 
                     
                       
                         x 
                         t 
                       
                       ∈ 
                       
                          
                          
                       
                     
                   
                    
                   
                     exp 
                     ( 
                     
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               V 
                             
                           
                            
                           
                             
                               x 
                               i 
                               t 
                             
                             · 
                             
                               ψ 
                               i 
                               t 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               ij 
                               ∈ 
                               E 
                             
                           
                            
                           
                             
                               x 
                               ij 
                               t 
                             
                             · 
                             
                               φ 
                               ij 
                             
                           
                         
                       
                       γ 
                     
                     ) 
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   s 
                   . 
                   t 
                   . 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   t 
                                   ∈ 
                                   
                                      
                                      
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                 
                               
                                
                               
                                 ψ 
                                 i 
                                 t 
                               
                             
                             = 
                             
                               ψ 
                               i 
                             
                           
                           , 
                         
                       
                       
                         
                           ∀ 
                           
                             i 
                             ∈ 
                             V 
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     It should be understood that the objective with smoothed-max as defined by Equation 29 corresponds to a tree-reweighted belief propagation (TRBP) objective that bounds a partition function (e.g., Z in Equation 1) with a decomposition of a graph into trees and the system  10  implements a monotone, highly parallel coordinate descent approach to minimize bounds of the partition function. It is noted that dual-decomposition does not represent overhead when each edge is only covered once but if a more complex tree bound is required, then TRBP can be utilized to minimize over edge appearance probabilities. The smoothed-max marginal of state l i  at location i on sub-problem t is defined by Equation 30 below: 
     
       
         
           
             
               
                 
                   
                     
                       v 
                       i 
                       t 
                     
                      
                     
                       ( 
                       
                         l 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ψ 
                         i 
                         i 
                       
                        
                       
                         ( 
                         
                           l 
                           i 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         γ 
                          
                         
                             
                         
                          
                         
                           log 
                           ( 
                           
                             
                               ∑ 
                               
                                 
                                   l 
                                   j 
                                 
                                 ∈ 
                                 ℒ 
                               
                             
                              
                             
                               exp 
                               ( 
                               
                                 
                                   
                                     
                                       v 
                                       j 
                                       t 
                                     
                                      
                                     
                                       ( 
                                       
                                         l 
                                         j 
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       φ 
                                       ij 
                                       t 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           l 
                                           i 
                                         
                                         , 
                                         
                                           l 
                                           j 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 γ 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   30 
                 
               
             
           
         
       
     
     where C(i) denotes a set of neighbors of node i. 
     Similar to max-marginal vector μ i   t  for sub-problem t location i and max-energy μ t  for sub-problem t, the smoothed max-marginal vector v i   t  for sub-problem t location i is defined and the smoothed-max energy v t  for sub-problem t is also defined. In particular, Equation 31 defines the smoothed-max energy as: 
     
       
         
           
             
               
                 
                   
                     
                       v 
                       t 
                     
                     = 
                     
                       γ 
                        
                       
                           
                       
                        
                       
                         log 
                         ( 
                         
                           
                             ∑ 
                             
                               
                                 l 
                                 i 
                               
                               ∈ 
                               ℒ 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     v 
                                     i 
                                     t 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       i 
                                     
                                     ) 
                                   
                                 
                                 γ 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       i 
                       ∈ 
                       
                         V 
                         t 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   31 
                 
               
             
           
         
       
     
     Equation 31 is equivalent for any i∈V t  because a smoothed-max with negative-entropy regularization (e.g., log-sum-exp) over a combinatorial space of a tree-structured problem is equal to a smoothed-max-energy determined via dynamic programs with a smoothed-max operator. This is given by Equation 32 below as: 
     
       
         
           
             
               
                 
                   
                     v 
                     t 
                   
                   = 
                   
                     γ 
                      
                     
                         
                     
                      
                     log 
                      
                     
                         
                     
                      
                     
                       
                         ∑ 
                         
                           
                             x 
                             i 
                           
                           ∈ 
                           
                              
                              
                           
                         
                       
                        
                       
                         exp 
                         ( 
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   ∈ 
                                   V 
                                 
                               
                                
                               
                                 
                                   x 
                                   i 
                                   t 
                                 
                                 · 
                                 
                                   ψ 
                                   i 
                                   t 
                                 
                               
                             
                             + 
                             
                               
                                 ∑ 
                                 
                                   ij 
                                   ∈ 
                                   E 
                                 
                               
                                
                               
                                 
                                   x 
                                   ij 
                                   t 
                                 
                                 · 
                                 
                                   φ 
                                   ij 
                                 
                               
                             
                           
                           γ 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   32 
                 
               
             
           
         
       
     
     The system  10  provides and proves a new monotone update rule for Equation 29 when fixing the dual variables for all sub-problems at all locations except for those at one location k and optimizing with respect to the vector ψ k   t , ∀t∈τ(k). In particular, for a single location k∈V, the following coordinate update to ψ k   t , ∀t∈τ(k) defined by Equation 33 below is optimal: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ψ 
                         k 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                     ← 
                     
                       
                         
                           ψ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                       - 
                       
                         ( 
                         
                           
                             
                               v 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               1 
                               
                                  
                                 
                                    
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                  
                               
                             
                              
                             
                               
                                 ∑ 
                                 
                                   
                                     t 
                                     _ 
                                   
                                   ∈ 
                                   
                                      
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                                 
                                     
                                 
                               
                                
                               
                                 
                                   v 
                                   k 
                                   
                                     i 
                                     _ 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   33 
                 
               
             
             
               
                 
                   
                     ∀ 
                     
                       t 
                       ∈ 
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                   , 
                   
                     
                       l 
                       k 
                     
                     ∈ 
                     ℒ 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     The system  10  endeavors to optimize the linear program with respect to ψ k   t  as defined by Equation 34 below and where v k   t (l k ) is a function of ψ k   t (l k ): 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           ψ 
                           k 
                           i 
                         
                         ∈ 
                         
                           ℝ 
                           
                             
                                
                               ℒ 
                                
                             
                             , 
                           
                         
                       
                       
                         ∀ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                       
                           
                       
                     
                      
                     
                       γ 
                        
                       
                           
                       
                        
                       
                         log 
                         ( 
                         
                           
                             ∑ 
                             
                               
                                 l 
                                 k 
                               
                               ∈ 
                               ℒ 
                             
                             
                                 
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     v 
                                     k 
                                     t 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       k 
                                     
                                     ) 
                                   
                                 
                                 γ 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   34 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                          
                         
                           
                             ψ 
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         ψ 
                         k 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Since it is a monotonically increasing function (for positive γ), γ log(⋅) can be removed from Equation 34 to yield Equation 35 below as: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           ψ 
                           k 
                           i 
                         
                         ∈ 
                         
                           ℝ 
                           
                             
                                
                               ℒ 
                                
                             
                             , 
                           
                         
                       
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∏ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       ( 
                       
                         
                           ∑ 
                           
                             
                               l 
                               k 
                             
                             ∈ 
                             ℒ 
                           
                           
                               
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   v 
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                               γ 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   35 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                          
                         
                           
                             ψ 
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         ψ 
                         k 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Defining λ k   t  as the change of ψ k   t  after some update and optimizing over λ k   t  while fixing ψ k   t  yields Equation 36 below: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           λ 
                           k 
                           i 
                         
                         ∈ 
                         
                           ℝ 
                           
                             
                                
                               ℒ 
                                
                             
                             , 
                           
                         
                       
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∏ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       ( 
                       
                         
                           ∑ 
                           
                             
                               l 
                               k 
                             
                             ∈ 
                             ℒ 
                           
                           
                               
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   
                                     v 
                                     k 
                                     t 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       k 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     λ 
                                     k 
                                     t 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       k 
                                     
                                     ) 
                                   
                                 
                               
                               γ 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   36 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                          
                         
                           
                             λ 
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     0 
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     As such and in terms of λ k   t (l k ), the update rule defined by Equation 33 is equivalent to the solution given by Equation 37 below: 
     
       
         
           
             
               
                 
                   
                     
                       
                         λ 
                         k 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           k 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         - 
                         
                           
                             v 
                             k 
                             i 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                       + 
                       
                         
                           1 
                           
                              
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                              
                           
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 t 
                                 _ 
                               
                               ∈ 
                               
                                  
                                  
                                 
                                   ( 
                                   k 
                                   ) 
                                 
                               
                             
                           
                            
                           
                             
                               v 
                               k 
                               
                                 t 
                                 _ 
                               
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       t 
                       ∈ 
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   37 
                 
               
             
           
         
       
     
     This solution makes v k   t (l k )+λ k   t (l k )=v k     t   (l k )+λ k     t   (l k ), ∀l k ∈ , ∀(t, t )∈τ(k)×τ(k). Thus, if applying the solution given by Equation 37, the equality condition of the arithmetic mean and geometric mean (AM-GM) inequality is met resulting in: 
     
       
         
           
             
               
                 ∏ 
                 
                   t 
                   ∈ 
                   
                      
                      
                     
                       ( 
                       k 
                       ) 
                     
                   
                 
               
                
               
                   
               
                
               
                 ( 
                 
                   
                     ∑ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                     
                         
                     
                   
                    
                   
                     exp 
                      
                     
                       ( 
                       
                         
                           
                             
                               v 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               λ 
                               k 
                               i 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                         
                         γ 
                       
                       ) 
                     
                   
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     1 
                     
                        
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                        
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           
                             l 
                             k 
                           
                           ∈ 
                           ℒ 
                         
                         
                             
                         
                       
                        
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               
                                 
                                   v 
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   λ 
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                             γ 
                           
                           ) 
                         
                       
                     
                   
                 
                 ) 
               
               
                  
                 
                    
                    
                   
                     ( 
                     k 
                     ) 
                   
                 
                  
               
             
           
         
       
     
     When performing minimization, the denominator and exponent on the right-hand side can be eliminated. Accordingly, the objective is defined by Equation 38 below: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           λ 
                           k 
                           i 
                         
                         ∈ 
                         
                           ℝ 
                           
                             
                                
                               ℒ 
                                
                             
                             , 
                           
                         
                       
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           ∑ 
                           
                             
                               l 
                               k 
                             
                             ∈ 
                             ℒ 
                           
                           
                               
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   
                                     v 
                                     k 
                                     i 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       k 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     λ 
                                     k 
                                     t 
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       k 
                                     
                                     ) 
                                   
                                 
                               
                               γ 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   38 
                 
               
             
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                          
                         
                           
                             λ 
                             k 
                             t 
                           
                            
                           
                             ( 
                             
                               l 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     0 
                   
                   , 
                   
                     ∀ 
                     
                       
                         l 
                         k 
                       
                       ∈ 
                       ℒ 
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     It is equivalent to optimize for each unique l k ∈  independently since there is no constraint over different pairs in label space (e.g.,  × ). Thus, each optimization problem can be defined by Equation 39 below: 
     
       
         
           
             
               
                 
                   
                     min 
                     
                       
                         
                           
                             
                               λ 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           ∈ 
                           ℝ 
                         
                         , 
                       
                       
                         ∀ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                       exp 
                       ( 
                       
                         
                           
                             
                               v 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               λ 
                               k 
                               t 
                             
                              
                             
                               ( 
                               
                                 l 
                                 k 
                               
                               ) 
                             
                           
                         
                         γ 
                       
                       ) 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   39 
                 
               
             
             
               
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           λ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Converting Equation 39 to dual form yields Equation 40 below: 
     
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         
                           
                             
                               
                                 λ 
                                 k 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                             ∈ 
                             ℝ 
                           
                           , 
                         
                         
                           ∀ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                       
                     
                      
                     
                       
                         max 
                         
                           α 
                           ∈ 
                           ℝ 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             t 
                             ∈ 
                             
                                
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                          
                         
                           exp 
                           ( 
                           
                             
                               
                                 
                                   v 
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   λ 
                                   k 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     l 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                             γ 
                           
                           ) 
                         
                       
                     
                   
                   - 
                   
                     α 
                      
                     
                         
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           λ 
                           k 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             k 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   40 
                 
               
             
           
         
       
     
     It should be understood that the min can be positioned on an outside of Equation 40 because a Linear Programming (LP) problem always satisfies a Karush-Kuhn-Tucker (KKT) condition. Setting a derivative of Equation 40 w.r.t. λ k   t (l k ) to zero for any sub-problem t, yields Equation 41 below: 
     
       
         
           
             
               
                 
                   
                     α 
                     = 
                     
                       
                         1 
                         γ 
                       
                        
                       
                         exp 
                         ( 
                         
                           
                             
                               
                                 v 
                                 k 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 λ 
                                 k 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   k 
                                 
                                 ) 
                               
                             
                           
                           γ 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     
                       t 
                       ∈ 
                       
                          
                          
                         
                           ( 
                           k 
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   41 
                 
               
             
           
         
       
     
     In view of the foregoing, Equation 37 satisfies v k   t (l k )+λ k   t (l k )=v k     t   (l k )+λ k     t   (l k ), ∀(t, t )∈τ(k)×τ(k). It should be understood that Σ t∈τ(k) λ k   t (l k )=0 is satisfied when applying Equation 39 and therefore it follows that Equation 39 is equivalent to Equation 40 (e.g., the duality gap of the LP is 0 and the update rule defined by Equation 33 is an optimal update for Equation 29). 
     Additionally, the following proves the monotone update step for simultaneously updating all locations for dual-decomposition with smoothed-max. In particular, the update to ψ i   t , ∀i∈V, t∈τ(i) as defined by Equation 42 below does not increase the objective as defined by Equation 29: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ψ 
                         i 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           i 
                         
                         ) 
                       
                     
                     ← 
                     
                       
                         
                           ψ 
                           i 
                           t 
                         
                          
                         
                           ( 
                           
                             l 
                             i 
                           
                           ) 
                         
                       
                       - 
                       
                         
                           1 
                           
                              
                             
                               V 
                               0 
                             
                              
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 v 
                                 i 
                                 l 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   i 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 1 
                                 
                                    
                                   
                                      
                                      
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                    
                                 
                               
                                
                               
                                 
                                   ∑ 
                                   
                                     
                                       t 
                                       _ 
                                     
                                     ∈ 
                                     
                                        
                                        
                                       
                                         ( 
                                         i 
                                         ) 
                                       
                                     
                                   
                                 
                                  
                                 
                                   
                                     v 
                                     i 
                                     
                                       t 
                                       _ 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       l 
                                       i 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   42 
                 
               
             
             
               
                 
                   
                     ∀ 
                     
                       i 
                       ∈ 
                       V 
                     
                   
                   , 
                   
                     t 
                     ∈ 
                     
                        
                        
                       
                         ( 
                         i 
                         ) 
                       
                     
                   
                   , 
                   
                     
                       l 
                       i 
                     
                     ∈ 
                     ℒ 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     where |V 0 |=max t∈τ |V t | and |V t | denotes a number of vertices of sub-problem t. 
     It should be understood that {circumflex over (v)} t  is denoted as the smoothed-max-energy of sub-problem t after applying the update defined by Equation 42 to {ψ t } and that v i   t  is denoted as the smoothed-max-energy of sub-problem t after applying the update defined by Equation 33 for location i. Considering changes in the objective from updating {ψ t } according to Equation 42 yields Equation 43 below: 
     
       
         
           
             
               
                 
                   
                     - 
                     
                       
                         ∑ 
                         
                           t 
                           ∈ 
                            
                         
                         
                             
                         
                       
                        
                       
                         v 
                         t 
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                       
                           
                       
                     
                      
                     
                       
                         v 
                         ^ 
                       
                       t 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   43 
                 
               
             
           
         
       
     
     It can be deducted that v t  as defined by Equation 23 (and consequently {circumflex over (v)} t ) is a convex function of ψ t  in view of the following: (1) Σ i∈V x i   t ·ψ i   t +Σ ij∈E x ij   t ·ϕ ij  is a non-decreasing convex function of ψ t  for any x t ∈X G , and (2) the log-sum-exp function is a non-decreasing convex function, and a composition of two non-decreasing convex functions is convex such that v t  (and {circumflex over (v)} t ) is a convex function of ψ t . Applying Jensen&#39;s Inequality to the second term of Equation 43 yields: 
     
       
         
           
             
               
                 Eq 
                 . 
                 
                     
                 
                  
                 
                   ( 
                   43 
                   ) 
                 
               
               ≤ 
               
                 
                   - 
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                          
                       
                       
                           
                       
                     
                      
                     
                       v 
                       t 
                     
                   
                 
                 + 
                 
                   
                     ∑ 
                     
                       t 
                       ∈ 
                        
                     
                     
                         
                     
                   
                    
                   
                     ( 
                     
                       
                         
                           
                             
                                
                               
                                 V 
                                 0 
                               
                                
                             
                             - 
                             
                                
                               
                                 V 
                                 t 
                               
                                
                             
                           
                           
                              
                             
                               V 
                               0 
                             
                              
                           
                         
                          
                         
                           v 
                           t 
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             ∈ 
                             
                               V 
                               i 
                             
                           
                         
                          
                         
                           
                             1 
                             
                                
                               
                                 V 
                                 0 
                               
                                
                             
                           
                            
                           
                             
                               v 
                               _ 
                             
                             i 
                             i 
                           
                         
                       
                     
                     ) 
                   
                 
               
             
             = 
             
               
                 
                   1 
                   
                      
                     
                       V 
                       0 
                     
                      
                   
                 
                  
                 
                   
                     ∑ 
                     
                       t 
                       ∈ 
                        
                     
                     
                         
                     
                   
                    
                   
                     
                       ∑ 
                       
                         i 
                         ∈ 
                         
                           V 
                           t 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             v 
                             _ 
                           
                           i 
                           t 
                         
                         - 
                         
                           v 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   1 
                   
                      
                     
                       V 
                       0 
                     
                      
                   
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                       
                         V 
                         t 
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         t 
                         ∈ 
                         
                            
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       
                           
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             v 
                             _ 
                           
                           i 
                           t 
                         
                         - 
                         
                           v 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
     Accordingly, it can be observed that Σ t∈τ(x) v i   t  corresponds to the objective defined by Equation 34 before applying the update defined by Equation 33 and that Σ t∈τ(x)   v   t  corresponds to the same objective after applying the update defined by Equation 33. Based on the foregoing, the update defined by Equation 33 does not increase the objective defined by Equation 34. Therefore, it follows that τ t∈τ(x) ( v   i   t −v t )≤0, which results in Equation 43 being equal to or less than 0 and thus the update defined by Equation 42 constitues a non-increasing step to the objective defined by Equation 29. 
     As mentioned above, it should be understood that line 6 of Algorithm 1 (as shown in  FIG. 6 ) is indicative of dynamic programming over trees. Dynamic programming can be implemented utilizing basic operators of PyTorch together with its AutoGrad feature but can be inefficient. As such, the system  10  can create a dynamic programming layer to determine horizontal and vertical marginals on a pixel grid for line 6 of Algorithm 1 which can be ten times faster than a naïve PyTorch implementation. As described in detail below with respect to  FIGS. 9-11 , the system  10  can implement forward and backward passes for determining max-marginals and corresponding gradients on an M×M pixel grid as a parallel algorithm with a time complexity of  (M| |) for each of a smoothed-max operator and a max-operator. 
       FIG. 9  is a flowchart illustrating step  76  of  FIG. 3  in greater detail. In particular,  FIG. 9  illustrates processing steps for deriving an algorithm to determine smoothed-max-marginals and their corresponding gradients. It should be understood that a variation of these processing steps can be utilized to derive an algorithm to determine max-marginals and their corresponding gradients. Beginning in step  190 , the system  10  defines a dynamic programming layer for determining a smoothed-max-marginal term v i   t (l i ) as defined by Equation 44: 
     
       
         
           
             
               
                 
                   
                     
                       v 
                       i 
                       i 
                     
                      
                     
                       ( 
                       
                         l 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ψ 
                         i 
                         l 
                       
                        
                       
                         ( 
                         
                           l 
                           i 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         γ 
                          
                         
                             
                         
                          
                         
                           log 
                           ( 
                           
                             
                               ∑ 
                               
                                 
                                   l 
                                   j 
                                 
                                 ∈ 
                                 ℒ 
                               
                               
                                   
                               
                             
                              
                             
                               exp 
                                
                               
                                   
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         v 
                                         j 
                                         i 
                                       
                                        
                                       
                                         ( 
                                         
                                           l 
                                           j 
                                         
                                         ) 
                                       
                                     
                                     + 
                                     
                                       
                                         φ 
                                         ij 
                                         t 
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             l 
                                             i 
                                           
                                           , 
                                           
                                             l 
                                             j 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   γ 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   44 
                 
               
             
           
         
       
     
     It should be understood that the system  10  can alternatively define a dynamic programming layer for determining a max-marginal term μ i   t (l i ) as defined by Equation 45: 
     
       
         
           
             
               
                 
                   
                     
                       μ 
                       i 
                       t 
                     
                      
                     
                       ( 
                       
                         l 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ψ 
                         i 
                         t 
                       
                        
                       
                         ( 
                         
                           l 
                           i 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                              
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           max 
                           
                             
                               l 
                               j 
                             
                             ∈ 
                             ℒ 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 φ 
                                 ij 
                               
                                
                               
                                 ( 
                                 
                                   
                                     l 
                                     i 
                                   
                                   , 
                                   
                                     l 
                                     j 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               
                                 μ 
                                 j 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   l 
                                   j 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   45 
                 
               
             
           
         
       
     
     It should also be understood that for any leaf nodes k, that C(k)=Ø. In step  192  and without loss of generality, the system  10  defines an M×M pixel grid with stride  1  and stride  2  horizontal and vertical edges (as shown in  FIG. 5 ). In steps  194  and  196 , the system  10  respectively determines M horizontal chains (e.g., sub-problems) of length M and M vertical chains (e.g., sub-problems) of length M based on whether M is even or odd. In particular, if M is even, then the system  10  determines 2M horizontal chains and 2M vertical chains of length M/2. Alternatively, if M is odd, then the system  10  determines M horizontal chains and M vertical chains of length and ┌M/2┐ horizontal chains and M vertical chains of length └M/2┘. It is known that determining smoothed-max-marginals for each chain (e.g., sub-problem) can be performed in parallel. A less known point for parallelism is that for each sub-problem t at a location i, v i   t (l i ) can be determined for each l i ∈  in parallel. This requires the threads within sub-problem t to be synchronized at each location before proceeding to a next location. As such, in step  198 , the system  10  performs two passes of the dynamic programming layer over each sub-problem to determine the smoothed-max-marginals for each label at each location. Therefore, the total time complexity is  (M| |) and the space complexity is  (M| | 2 ) (| | 2  is for storing soft-max probabilities for later use in a backward pass and the space complexity becomes  (M| |) if the system  10  does not determine the gradients). 
     It should be understood that with respect to a backward pass, a loss function is determined with smoothed-max-marginals of all locations and labels thereby necessitating differentiation through all locations and labels. This yields an algorithm having a time complexity of  (M 2 | |) with parallelization over locations and labels at each location) such that a gradient at one location can be affected by a gradient from all locations. Alternatively, a backward pass can be performed by commencing from a root/leaf location, passing gradients to a next location while also adding in the gradients of the next location from the loss layer, and recursing till the leaf/root. The system  10  can perform two passes of this dynamic programming layer to determine final gradients for each location which yields an algorithm having a total time complexity  (M| |) and a space complexity  (M| | 2 ). 
     It should be understood that dynamic programming from root to leaf is known as forward dynamic programming and denoted by a subscript ƒ while dynamic programming from leaf to root is known as backward dynamic programming and denoted by a subscript b. In this context, C ƒ (i) denotes a set of previous node(s) of node i in a root-leaf direction, while C b (i) denotes a set of previous node(s) of node i in a leaf-root direction.  FIGS. 10 and 11  respectively illustrate algorithms for implementing forward and backward passes for determining smoothed-max-marginals and their gradients and max-marginals and their gradients. 
     Training, testing, and results of the system  10  will now be described in greater detail in relation to  FIGS. 12 and 13 . As mentioned above, the system  10  can execute semantic image segmentation utilizing the PASCAL VOC dataset. 
       FIG. 12  is a compilation of images  230  illustrating processing carried out by the system  10  of the present disclosure for semantic image segmentation. In particular,  FIG. 12  illustrates input images  232   a - c , ground truth images  234   a - c  and a qualitative comparison of DeepLabV3 images  236   a - c  and DeepLabV3 and system  10  combination images  238   a - c  with Xception-65 backbone. Rows a, b and c are respectively indicative of a crowded scene, inter-class contextual information and intra-class contextual information. As shown in  FIG. 12 , the CRF model and optimization provided by the system  10  yields a more refined boundary in image  238   a  compared to image  236   a  and encodes the inter-class contextual information of image  238   b  and the intra-class contextual information of image  238   c  to boost the weak unary classifier. 
     As mentioned above, the system  10  utilizes the PASCAL VOC  2012  semantic segmentation benchmark and average pixel intersection-over-union (mIoU) of the foreground as a performance measure. The PASCAL VOC dataset is widely utilized to benchmark various computer vision tasks such as object detection and semantic image segmentation. The semantic image segmentation benchmark includes 21 classes including a background class. The training dataset includes 1,464 images, the validation dataset includes 1,449 images and the testing dataset includes 1,456 images with pixel-wise semantic labeling. The system  10  utilizes additional annotations provided by the Semantics Boundaries Dataset (SBD) to augment the original PASCAL VOC  2012  training dataset thereby yielding an augmented training dataset including 10,582 images. The system  10  trains the network  14  on the augmented training dataset and evaluates a performance of the network on the validation dataset. 
     The system  10  re-implements DeepLabV3 in PyTorch with a block4-backbone (e.g., no additional block following the backbone except for one 1×1 convolution, two 3×3 convolutions and a final 1×1 convolution for classification) and Atrous Spatial Pyramid Pooling (ASPP) as a baseline. The system  10  sets the output stride to 16 for all models. The system  10  utilizes the Residual Neural Network 50 (ResNet-50) and Xception-65 as the backbones. To train the models, the system  10  utilizes a stochastic gradient descent (SGD) optimizer with a momentum of 0.9 and a “poly” learning rate policy with an initial learning rate of 0.007 for 30k steps. Additionally, the system  10  utilizes a weight decay of 0.00001 to train the ResNet-50 models and a weight decay of 0.00004 to train the Xception-65 models. With respect to data augmentation, the system  10  applies random color jittering, random scaling from 0.5 to 1.5, random horizontal flip, random rotation between −10° and 10°, and a randomly cropped 513×513 image patch of the transformed image. The system  10  also utilizes synchronized batch normalization with a batch size of 16 for all models which is the standard for training semantic segmentation models. With respect to the dual-composition augmented models, the system  10  obtains the pairwise potentials by applying a fully connected layer over concatenated features of pairs of locations on the feature map before the final layer of the baseline model, executes several steps of the fixed-point iteration (FPI) of Algorithm 1 utilizing output logits from unary and pairwise heads for each of training and inference, and maintains remaining configurations consistent with the baseline model. 
       FIG. 13  is a table  250  illustrating quantitative processing results based on different network models on the PASCAL VOC validation dataset. As shown in  FIG. 13 , the backbone can be augmented with at least one of a predetermined number of iterations of the FPI and/or the ASPP. The “#+Params” denotes a number of new parameters other than those in the backbone. The system  10  improves a performance of the baseline model when augmenting the baseline model with 15 iterations of the FPI and realizes 50% of the improvement of the ASPP while introducing approximately 2% additional parameters compared to that of the ASPP. The system  10  also improves the models augmented with ASPP when applying the FPI on top of the ASPP module. In particular, the system  10  respectively improves an mIOU of the ResNet-50 and Xeception-65 models by 0.6% and 0.2% when applying the FPI on top of the ASPP. It should be understood that the FPI operates directly on the output potentials/logits of the CNN rather than the features thereof and works in a parameter free manner such that the additional parameters originate from computing the pairwise potentials which are inputs to the FPI. 
     As described above, the system  10  utilizes a fixed-point algorithm having dual-monotonicity and dual-differentiability and provides an efficient and highly parallel graphics processing unit implementation for the algorithm. In particular, a smoothed-max operator with negative-entropy regularization provides for the fixed-point algorithm to be fully-differentiable while remaining monotone for the dual objective. Additionally, the system  10  can perform end-to-end training of CNNs and CRFs by differentiating through dual-composition layers thereby improving semantic segmentation accuracy on the PASCAL VOC  2012  dataset over baseline models. It should be understood that additional testing of the system  10  can be performed on other datasets and architectures, and tasks such as human-pose-estimation and stereo matching (which can be formulated as general CRF inference problems) in comparison to other models. It should be understood that certain modifications of the system  10  can include unsupervised/semi-supervised learning by enforcing an agreement of sub-problems. 
       FIG. 14  is a diagram  300  showing hardware and software components of a computer system  302  on which the system of the present disclosure can be implemented. The computer system  302  can include a storage device  304 , computer vision software code  306 , a network interface  308 , a communications bus  310 , a central processing unit (CPU) (microprocessor)  312 , a random access memory (RAM)  314 , and one or more input devices  316 , such as a keyboard, mouse, etc. It is noted that the CPU  312  could also be one or more graphics processing units (GPUs). The server  302  could also include a display (e.g., liquid crystal display (LCD), cathode ray tube (CRT), etc.). The storage device  304  could comprise any suitable, computer-readable storage medium such as disk, non-volatile memory (e.g., read-only memory (ROM), erasable programmable ROM (EPROM), electrically-erasable programmable ROM (EEPROM), flash memory, field-programmable gate array (FPGA), etc.). The computer system  302  could be a networked computer system, a personal computer, a server, a smart phone, tablet computer etc. It is noted that the server  202  need not be a networked server, and indeed, could be a stand-alone computer system. 
     The functionality provided by the present disclosure could be provided by computer vision software code  306 , which could be embodied as computer-readable program code stored on the storage device  304  and executed by the CPU  312  using any suitable, high or low level computing language, such as Python, Java, C, C++, C#, .NET, MATLAB, etc. The network interface  308  could include an Ethernet network interface device, a wireless network interface device, or any other suitable device which permits the server  302  to communicate via the network. The CPU  312  could include any suitable single-core or multiple-core microprocessor of any suitable architecture that is capable of implementing and running the computer software code  306  (e.g., Intel processor). The random access memory  314  could include any suitable, high-speed, random access memory typical of most modern computers, such as dynamic RAM (DRAM), etc. 
     Having thus described the system and method in detail, it is to be understood that the foregoing description is not intended to limit the spirit or scope thereof. It will be understood that the embodiments of the present disclosure described herein are merely exemplary and that a person skilled in the art can make any variations and modification without departing from the spirit and scope of the disclosure. All such variations and modifications, including those discussed above, are intended to be included within the scope of the disclosure. What is desired to be protected by Letters Patent is set forth in the following claims.