Abstract:
A function optimization method includes the operations of: constructing an upper bound using a double majorization bounding process to a sum-of-exponentials function including a summation of exponentials of the form 
     
       
         
           
             
               
                 ∑ 
                 
                   k 
                   = 
                   1 
                 
                 K 
               
                
               
                  
                 
                   
                     β 
                     k 
                     T 
                   
                    
                   x 
                 
               
             
             ; 
           
         
       
     
     optimizing the constructed upper bound respective to parameters β to generate optimized parameters β; and outputting the optimized sum-of-exponentials function represented at least by the optimized parameters β. An inference process includes the operations of: invoking the function optimization method respective to a softmax function constrained by discrete observations y defining categorization observation conditioned by continuous variables x representing at least one input object; and applying the optimized softmax function output by the invocation of the softmax function optimization method to the continuous variables x representing at least one input object to generate classification probabilities.

Description:
BACKGROUND 
       [0001]    The following relates to the information processing arts and related arts. 
         [0002]    The softmax function is the extension of the sigmoid function for more than two variables. The softmax function has the form: 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     n 
                   
                   = 
                   
                     
                       
                          
                         
                           x 
                           n 
                         
                       
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The denominator is a sum-of-exponentials function of the form: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         k 
                         = 
                         1 
                       
                       K 
                     
                      
                     
                        
                       
                         x 
                         k 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where x k εxε           K . The softmax function finds application in neural networks, classifiers, and so forth, while the sum-of-exponentials function finds even more diverse application in these fields as well as in statistical thermodynamics (for example, the partition function), quantum mechanics, information science, classification, and so forth. For some applications a log of the sum-of-exponentials function is a more useful formulation. 
         [0003]    One application of the softmax function is in the area of inference problems, such as Gaussian process classifiers, Bayesian multiclass logistic regression, and more generally for deterministic approximation of probabilistic models dealing with discrete variables conditioned on continuous variables. Such applications entail computing the expectation of the log-sum-of-exponentials function: 
         [0000]    
       
         
           
             
               
                 
                   
                     γ 
                     = 
                     
                       
                         E 
                         Q 
                       
                       [ 
                       
                         log 
                          
                         
                             
                         
                          
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                              
                             
                               
                                 β 
                                 k 
                                 T 
                               
                                
                               x 
                             
                           
                         
                       
                       ] 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where E Q  denotes the expectation for a distribution Q(β) which is the probability density function (pdf) of a given multidimensional distribution in            d×K  and x is a vector of            d . The expectation can be computed using Monte Carlo simulations, but this can be computationally expensive. Taylor expansion techniques are also known, but tend to provide skewed results when the variance of the pdf Q(β) is large. 
         [0004]    Another known approach for computing the expectation is to use an upper bound. In this approach an upper bound on the log-sum-of-exponentials function is identified, from which an estimate of the expectation is obtained. The chosen upper bound should be tight respective to the log-sum-of-exponentials function, and should be computationally advantageous for computing the expectation. For the log-sum-of-exponentials function, a known upper bound having a quadratic form is given by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       log 
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                     ≤ 
                     
                         
                     
                      
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             ( 
                             
                               
                                 x 
                                 k 
                               
                               - 
                               
                                 χ 
                                 k 
                               
                             
                             ) 
                           
                           2 
                         
                       
                       - 
                       
                         
                           1 
                           K 
                         
                          
                         
                           ( 
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                               ( 
                               
                                 
                                   x 
                                   k 
                                 
                                 - 
                                 
                                   χ 
                                   k 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   k 
                                 
                                 - 
                                 
                                   χ 
                                   k 
                                 
                               
                               ) 
                             
                              
                             
                                
                               
                                 χ 
                                 k 
                               
                             
                           
                           
                             
                               ∑ 
                               
                                 
                                   k 
                                   ′ 
                                 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 χ 
                                 
                                   k 
                                   ′ 
                                 
                               
                             
                           
                         
                       
                       + 
                       
                         log 
                          
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                              
                             
                               χ 
                               k 
                             
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    See, e.g., Krishnapuram et al., Sparse multinomial logistic regression: fast algorithms and generalization bounds. IEEE Trans. Pattern Anal. Mach. Intell., 27(6):957-68, 2005; Böhning, Multinomial logistic regression algorithm. Annals of the Institute of Statistical Mathematics, 44(9):197-200, 1992. These quadratic bounds are generally tight. However, they use the worst curvature over the space, which can result in inefficient integrating when using the upper bound. 
         [0005]    As a result, the use of the softmax function for inference problems with more than two variables has heretofore been computationally difficult or impossible for many practical inference and classification problems. 
       BRIEF DESCRIPTION 
       [0006]    In some embodiments disclosed as illustrative examples, a storage medium stores instructions executable to implement a sum-of-exponentials function optimization method including the operations of: constructing an upper bound using a double majorization bounding process to a sum-of-exponentials function including at least one summation of exponentials; optimizing the constructed upper bound respective to parameters of the exponentials of the at least one summation of exponentials to generate optimized parameters; and outputting the optimized sum-of-exponentials function represented at least by the optimized parameters. 
         [0007]    In some embodiments disclosed as illustrative examples, an inference engine is disclosed comprising a processor programmed to perform an inference process comprising: generating an upper bound by double majorization for a sum-of-exponentials function including at least one summation of exponentials of the form 
         [0000]    
       
         
           
             
               ∑ 
               
                 k 
                 = 
                 1 
               
               K 
             
              
             
                
               
                 
                   β 
                   k 
                   T 
                 
                  
                 x 
               
             
           
         
       
     
         [0000]    constrained by an input object representation vector and an output classification observation vector; optimizing the upper bound respective to parameters β k  of the sum-of-exponentials function; and classifying one or more input objects by applying the sum-of-exponentials function with the optimized parameters β k  to said one or more input objects. 
         [0008]    In some embodiments disclosed as illustrative examples, a storage medium stores instructions defining a function for optimizing a sum-of-exponentials function including a summation of exponentials of the form 
         [0000]    
       
         
           
             
               ∑ 
               
                 k 
                 = 
                 1 
               
               K 
             
              
             
                
               
                 
                   β 
                   k 
                   T 
                 
                  
                 x 
               
             
           
         
       
     
         [0000]    by optimization operations comprising: upper bounding the sum of exponentials 
         [0000]    
       
         
           
             
               ∑ 
               
                 k 
                 = 
                 1 
               
               K 
             
              
             
                
               
                 
                   β 
                   k 
                   T 
                 
                  
                 x 
               
             
           
         
       
     
         [0000]    by a product of sigmoids; upper bounding terms of the form log(1+e x ) in the product of sigmoids to generate a double majorization upper bound; minimizing the double majorization upper bound respective to the parameters β to generate optimized parameters β; and outputting the optimized sum-of-exponentials function represented at least by the optimized parameters β. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  illustrates a tables of results discussed in the text. 
           [0010]      FIG. 2  diagrammatically shows a Bayesian inference engine. 
           [0011]      FIG. 3  illustrates a table of quadratic upper bounds discussed in the text. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The log-sum-of-exponentials function has concavity and a suitable upper bound is given by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       log 
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                     ≤ 
                     
                       
                         φ 
                          
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                              
                             
                               x 
                               k 
                             
                           
                         
                       
                       - 
                       
                         log 
                          
                         
                             
                         
                          
                         φ 
                       
                       - 
                       1 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the equality holds if and only if: 
         [0000]    
       
         
           
             
               
                 
                   φ 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                              
                             
                               x 
                               k 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Advantageously, the expectation of the right hand side can be readily computed for certain useful distributions since E Q e x     k    is the moment-generating function of the distribution Q. To obtain a better local quadratic approximation, a bound for the log-sum of exponentials is generated by a double majorization process comprising: (i) a first majorization operation in which the sum of the exponential is upper bounded by a product of sigmoids; and (ii) a second majorization operation using a standard quadratic bound on log(1+e x ) to obtain the final upper bound. 
         [0013]    For any xε           K  and for any αε         , a product of sigmoids and corresponding bound can be written as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           ∏ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                             
                         
                          
                         
                           ( 
                           
                             1 
                             + 
                             
                                
                               
                                 
                                   x 
                                   k 
                                 
                                 - 
                                 α 
                               
                             
                           
                           ) 
                         
                       
                       ≤ 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             
                               x 
                               k 
                             
                             - 
                             α 
                           
                         
                       
                     
                     = 
                     
                       
                          
                         
                           - 
                           α 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    from which can be obtained: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       log 
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                     ≤ 
                     
                       α 
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           log 
                            
                           
                             ( 
                             
                               1 
                               + 
                               
                                  
                                 
                                   
                                     x 
                                     k 
                                   
                                   - 
                                   α 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    A property for this bound is that its asymptotes are parallel in most directions. More exactly, by applying the bound to ax where a→∞, the difference between the right and the left part of equation tends to a constant if there exists at least one x k  positive and x k ≠x k′  for all k≠k′. The standard quadratic bound for log(1+e x ) is given by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       log 
                        
                       
                         ( 
                         
                           1 
                           + 
                           
                              
                             x 
                           
                         
                         ) 
                       
                     
                     ≤ 
                     
                       
                         
                           λ 
                            
                           
                             ( 
                             ξ 
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               x 
                               2 
                             
                             - 
                             
                               ξ 
                               2 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           x 
                           - 
                           ξ 
                         
                         2 
                       
                       + 
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             
                                
                               ξ 
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    for all ξε         . It is applied inside the sum of Equation (8). For any xε           K  and any αε           K , and for any ξε[0,∞) K  to yield: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       log 
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             x 
                             k 
                           
                         
                       
                     
                     ≤ 
                     
                         
                     
                      
                     
                       α 
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             
                               x 
                               k 
                             
                             - 
                             α 
                             - 
                             
                               ξ 
                               k 
                             
                           
                           2 
                         
                       
                       + 
                       
                         
                           λ 
                            
                           
                             ( 
                             
                               ξ 
                               k 
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     k 
                                   
                                   - 
                                   α 
                                 
                                 ) 
                               
                               2 
                             
                             - 
                             
                               ξ 
                               k 
                               2 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             
                                
                               
                                 ξ 
                                 k 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     where 
                      
                     
                         
                     
                      
                     
                       : 
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       λ 
                        
                       
                         ( 
                         
                           ξ 
                           k 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           1 
                           
                             2 
                              
                             
                                 
                             
                              
                             ξ 
                           
                         
                         [ 
                         
                           
                             1 
                             
                               1 
                               + 
                               
                                  
                                 
                                   - 
                                   ξ 
                                 
                               
                             
                           
                           - 
                           
                             1 
                             2 
                           
                         
                         ] 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Equations (10) and (11) set forth an upper bound on the log-sum-of-exponentials. 
         [0014]    Attention is turned to the illustrative application of estimating the expectation γ of the log-sum-of-exponentials set forth in Equation (3). A variational technique based on the maximization of a lower bound of γ can be used. In the following, the pdf Q(β k ) is considered to be a multivariate normal distribution with mean μ k  and variance Σ k . This illustrative example is readily extended to other multivariate distributions with bounded variances. Using the moment generating function 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       E 
                       Q 
                     
                      
                     
                       [ 
                       
                          
                         
                           
                             β 
                             k 
                             T 
                           
                            
                           x 
                         
                       
                       ] 
                     
                   
                   = 
                   
                      
                     
                       
                         
                           μ 
                           k 
                           T 
                         
                          
                         x 
                       
                       + 
                       
                         
                           1 
                           2 
                         
                          
                         
                           x 
                           T 
                         
                          
                         
                           Σ 
                           k 
                         
                          
                         
                             
                         
                          
                         x 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    of the multivariate normal distribution, the following bound on the expectation γ is obtained: 
         [0000]    
       
         
           
             
               
                 
                   
                     γ 
                     = 
                     
                       
                         
                           E 
                           Q 
                         
                         [ 
                         
                           log 
                            
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 
                                   β 
                                   k 
                                   T 
                                 
                                  
                                 x 
                               
                             
                           
                         
                         ] 
                       
                       ≤ 
                       
                         
                           φ 
                            
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 
                                   
                                     μ 
                                     k 
                                     T 
                                   
                                    
                                   x 
                                 
                                 + 
                                 
                                   
                                     1 
                                     2 
                                   
                                    
                                   
                                     x 
                                     T 
                                   
                                    
                                   
                                     Σ 
                                     k 
                                   
                                    
                                   x 
                                 
                               
                             
                           
                         
                         - 
                         
                           log 
                            
                           
                             ( 
                             φ 
                             ) 
                           
                         
                         - 
                         1 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    for every φε           K . Minimizing the right hand side with respect to φ leads to the upper bound: 
         [0000]    
       
         
           
             
               
                 
                   γ 
                   = 
                   
                     
                       
                         E 
                         Q 
                       
                        
                       
                         [ 
                         
                           log 
                            
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 
                                   β 
                                   k 
                                   T 
                                 
                                  
                                 x 
                               
                             
                           
                         
                         ] 
                       
                     
                     ≤ 
                     
                       log 
                        
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             
                               
                                 μ 
                                 k 
                                 T 
                               
                                
                               x 
                             
                             + 
                             
                               
                                 1 
                                 2 
                               
                                
                               
                                 x 
                                 T 
                               
                                
                               
                                 
                                   ∑ 
                                   k 
                                 
                                  
                                 x 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which shows that the bound becomes accurate when the variance of Q is small. The expectation over quadratic bounds gives: 
         [0000]    
       
         
           
             
               
                 
                   
                     γ 
                     ≤ 
                     
                       
                         
                           ( 
                           
                             K 
                             - 
                             1 
                           
                           ) 
                         
                          
                         
                           x 
                           T 
                         
                          
                         
                           Σ 
                           _ 
                         
                          
                         x 
                       
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             ( 
                             
                               
                                 
                                   μ 
                                   k 
                                   T 
                                 
                                  
                                 x 
                               
                               - 
                               
                                 χ 
                                 k 
                               
                             
                             ) 
                           
                           2 
                         
                       
                       - 
                       
                         
                           K 
                            
                           
                             ( 
                             
                               
                                 
                                   
                                     μ 
                                     _ 
                                   
                                   T 
                                 
                                  
                                 x 
                               
                               - 
                               
                                 χ 
                                 _ 
                               
                             
                             ) 
                           
                         
                         2 
                       
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     μ 
                                     k 
                                     T 
                                   
                                    
                                   x 
                                 
                                 - 
                                 
                                   χ 
                                   k 
                                 
                               
                               ) 
                             
                              
                             
                                
                               
                                 χ 
                                 k 
                               
                             
                           
                           
                             
                               ∑ 
                               
                                 
                                   k 
                                   ′ 
                                 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 χ 
                                 
                                   k 
                                   ′ 
                                 
                               
                             
                           
                         
                       
                       + 
                       
                         log 
                          
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                              
                              
                             
                                 
                             
                              
                             
                               χ 
                               k 
                             
                           
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                       
                   
                    
                   where 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       Σ 
                       _ 
                     
                     = 
                     
                       
                         1 
                         K 
                       
                        
                       
                         
                           ∑ 
                           k 
                         
                          
                         
                           
                             Σ 
                             k 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0000]    A minimization of the right hand side with respect to χ gives the solution χ k =μ k   T x. At this point, the difference between the expectation γ and its upper bound is at least (K−1)x T Σx. This means that the bound is tight if the distribution lies in a manifold orthogonal to x. 
         [0015]    Returning to Equation (10), the following holds: 
         [0000]    
       
         
           
             
               
                 
                   
                     γ 
                     ≤ 
                     
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             λ 
                              
                             
                               ( 
                               
                                 ξ 
                                 k 
                               
                               ) 
                             
                           
                            
                           
                             ( 
                             
                               
                                 
                                   x 
                                   T 
                                 
                                  
                                 
                                   Σ 
                                   k 
                                 
                                  
                                 x 
                               
                               + 
                               
                                 
                                   ( 
                                   
                                     
                                       μ 
                                       k 
                                       T 
                                     
                                      
                                     x 
                                   
                                   ) 
                                 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                       + 
                       
                         
                           ( 
                           
                             
                               1 
                               2 
                             
                             - 
                             
                               2 
                                
                               
                                   
                               
                                
                               α 
                                
                               
                                   
                               
                                
                               
                                 λ 
                                  
                                 
                                   ( 
                                   
                                     ξ 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                           
                           ) 
                         
                          
                         
                           μ 
                           k 
                           T 
                         
                          
                         x 
                       
                       + 
                       α 
                       - 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           
                             
                               ξ 
                               k 
                             
                             + 
                             α 
                           
                           2 
                         
                       
                       + 
                       
                         
                           λ 
                            
                           
                             ( 
                             
                               ξ 
                               k 
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               α 
                               2 
                             
                             - 
                             
                               ξ 
                               k 
                               2 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             
                                
                               
                                 ξ 
                                 k 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The minimization of the upper bound with respect to ξ gives: 
         [0000]      ξ k   2   =x   T Σ h   x +(μ k   T   x ) 2 +α 2 −2αμ k   T   x   (18), 
         [0000]    for k=1, . . . , K. The minimization with respect to α gives: 
         [0000]    
       
         
           
             
               
                 
                   α 
                   = 
                   
                     
                       
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                             
                               λ 
                                
                               
                                 ( 
                                 
                                   ξ 
                                   k 
                                 
                                 ) 
                               
                             
                              
                             
                               μ 
                               k 
                               T 
                             
                              
                             x 
                           
                         
                         + 
                         
                           
                             1 
                             2 
                           
                            
                           
                             ( 
                             
                               
                                 K 
                                 2 
                               
                               - 
                               1 
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           λ 
                            
                           
                             ( 
                             
                               ξ 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0016]    Several experiments were performed to compare the approximations based on the log, on the quadratic upper bound for the softmax (see Equation (4)), and the upper bound based on a double majorization as disclosed herein. The table shown in  FIG. 1  summarizes the results. For every experiment, a vector xε           d  was randomly sampled, a mean μ k  according to a standardized normal distribution, and a covariance matrix using a Wishart distribution with identity scale matrix and 10 I d  for experiments labeled with var=10. The dimension d of the x vector varied from 2 to 100, the number of classes ranged from K=2 (corresponding to the classical binary case) to K=1000. The Wishart distribution had 100 degrees of freedom and (d+1 in the highly correlated (high corr) case). In the high discrepancy (high disc) case, the vector x has many extreme values: it was generated using a student t distribution with 10 degrees of freedom. In experiments labelled samecov, the covariance of every Q(β k ) was the same. A hundred independent replications of the same experience were replicated. Every bound was compared to a Monte-Carlo sample of size 100,000 (its variance was negligible compared to the error of the bound). 
         [0017]    With continuing reference to the table shown in  FIG. 1 , the variance of Q is seen to directly influence the choice of the bounding methods. For small variances, the linear approximation of the log seems to give the best results. For large variances, the bound disclosed herein is substantially more accurate than the other methods. Without being limited to any particular theory of operation, this is believed to be mainly due to the fact that the approximation disclosed herein is asymptotically optimal, so that it is robust to cases where the distribution is not precisely localized. For truly Bayesian models, having a model that is accurate in the high variance cases is advantageous since it enable a correct (that is, not too biased) estimation of the uncertainty. It is noteworthy that the quality of the approximations do not degrades too much when dealing with a large number of classes or high dimensional data. Another item evidenced in the experiments summarized in  FIG. 1  is that the quadratic upper bound of the Hessian (which is often used find the MAP solutions of multiclass logistic regression) gives poor results in most of the cases. 
         [0018]    With reference to  FIG. 2 , a Bayesian inference engine  10  employing the illustrative upper bound based on a double majorization is described. The inference engine  10  is suitably embodied by a computer  12  or other digital processing device including a digital processor such as a microprocessor, microcontroller, or so forth and storage. In other embodiments, the inference engine may be embodied by a server including a digital processor and including or having access to digital data storage, such server being suitably accessed via the Internet or a local area network, or by a personal data assistant (PDA) including a digital processor and digital data storage, or so forth. The computer  12  or other digital processing device suitably includes or is operatively connected with one or more user input devices such as an illustrated keyboard  14  for receiving user input to control the inference processing, and further includes or is operatively connected with one or more display devices such as an illustrated display  16  for displaying output generated based on the output of the inference engine. In other embodiments, the input for controlling the inference process is received from another program running previously to or concurrently with the inference engine on the computer  12 , or from a network connection, or so forth. Similarly, in other embodiments the output may serve as input to another program running subsequent to or concurrently with the inference engine on the computer  12 , or may be transmitted via a network connection, or so forth. 
         [0019]    In some embodiments, the disclosed softmax optimization processes, inference engines employing same, and so forth are embodied by a storage medium storing instructions executable (for example, by a digital processor) to implement a softmax function optimization method, inference engine, or so forth. The storage medium may include, for example: a magnetic disk or other magnetic storage medium; an optical disk or other optical storage medium; a random access memory (RAM), read-only memory (ROM), or other electronic memory device or chip or set of operatively interconnected chips; an Internet server from which the stored instructions may be retrieved via the Internet or a local area network; or so forth. 
         [0020]    The illustrative Bayesian inference engine  10  employs multinomial logistic regression. A multinomial logistic model is considered, with discrete observations y=(y 1 , . . . , y n )□{1, . . . , K} n    20  conditioned by continuous variables x=(x 1 , . . . , x n )ε           n×d    22 , such as a vector to be transformed, via a softmax function of the form: 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         
                           y 
                           = 
                           
                             k 
                             | 
                             x 
                           
                         
                         ; 
                         β 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                          
                         
                           
                             β 
                             k 
                             T 
                           
                            
                           x 
                         
                       
                       
                         
                           ∑ 
                           
                             
                               k 
                               ′ 
                             
                             = 
                             1 
                           
                           K 
                         
                          
                         
                            
                           
                             
                               β 
                               
                                 k 
                                 ′ 
                               
                               T 
                             
                              
                             x 
                           
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0000]    An initial (that is, not yet optimized) softmax function  24  has the form of Equation (20) with an initial (that is, not yet optimized) transformation matrix β  26 . The objective is to optimize the transformation matrix β of the softmax function respective to the constraints  20 ,  22 . As an example of one practical application of the Bayesian inference engine  10 , the discrete observations y  20  may be category observations for a text-based document classifier, and the continuous variables x  22  may represent bag-of-words” representations of documents to be classified. In another practical application, the discrete observations y  20  may be category observations for an image classifier, and the continuous variables x  22  may represent features vector representations of images to be classified. These are merely illustrative practical applications, and numerous other applications entailing optimization of parameters  26  of the softmax function  24  constrained by observations  20  conditioned by continuous variables  22  are contemplated. 
         [0021]    The Bayesian inference determines values for the transformation matrix elements of the parameters matrix β  26  that optimally satisfy the softmax function  24  under the constraints  20 ,  22 . In other words, it is desired to maximize the posterior distribution P(β|x,y). For any choice of the prior there do not exist a closed form solution for the posterior distribution P(β|x,y). Variational approximations are based on the minimization of KL(Q(β)∥P(β|y,x)) over a class of distributions F Q  for which the computation is effective. 
         [0022]    With continuing reference to  FIG. 2 , the problem is solved indirectly by constructing  30  an upper bound based on double majorization and computing  32  a minimum of the upper bound respective to the transformation matrix β in order to obtain an optimized transformation matrix β  34 . the problem is equivalent to maximizing the following lower bound L on P(y,x): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             log 
                              
                             
                                 
                             
                              
                             P 
                              
                             
                               ( 
                               
                                 y 
                                 , 
                                 x 
                               
                               ) 
                             
                           
                           ≥ 
                             
                            
                           
                             
                               
                                 E 
                                 Q 
                               
                                
                               
                                 [ 
                                 
                                   log 
                                    
                                   
                                       
                                   
                                    
                                   
                                     P 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         x 
                                         , 
                                         β 
                                       
                                       ) 
                                     
                                   
                                 
                                 ] 
                               
                             
                             - 
                             
                               KL 
                                
                               
                                 ( 
                                 
                                   
                                     Q 
                                      
                                     
                                       ( 
                                       β 
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                      
                                   
                                    
                                   
                                     P 
                                      
                                     
                                       ( 
                                       β 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         := 
                         
                           L 
                            
                           
                             ( 
                             
                               μ 
                               , 
                               Σ 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                               
                                 ∑ 
                                 
                                   i 
                                   , 
                                   
                                     
                                       y 
                                       i 
                                     
                                     = 
                                     k 
                                   
                                 
                               
                                
                               
                                 
                                   E 
                                   Q 
                                 
                                  
                                 
                                   [ 
                                   
                                     
                                       β 
                                       k 
                                       T 
                                     
                                      
                                     
                                       x 
                                       i 
                                     
                                   
                                   ] 
                                 
                               
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               n 
                             
                              
                             
                               
                                 E 
                                 Q 
                               
                               [ 
                               
                                 log 
                                  
                                 
                                   
                                     ∑ 
                                     
                                       
                                         k 
                                         ′ 
                                       
                                       = 
                                       1 
                                     
                                     K 
                                   
                                    
                                   
                                      
                                     
                                       
                                         β 
                                         
                                           k 
                                           ′ 
                                         
                                         T 
                                       
                                        
                                       
                                         x 
                                         i 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           - 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             KL 
                              
                             
                               ( 
                               
                                 
                                   Q 
                                    
                                   
                                     ( 
                                     β 
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                    
                                 
                                  
                                 
                                   P 
                                    
                                   
                                     ( 
                                     β 
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Using a quadratic bound for the second expectation, a lower bound F(μ,Σ,ξ) of L(μ,Σ) is obtained: 
         [0000]    
       
         
           
             
               
                 
                   
                     F 
                      
                     
                       ( 
                       
                         μ 
                         , 
                         Σ 
                         , 
                         ξ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         - 
                         
                           1 
                           2 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           tr 
                            
                           
                             ( 
                             
                               
                                 A 
                                 k 
                               
                                
                               
                                 
                                   E 
                                   Q 
                                 
                                  
                                 
                                   [ 
                                   
                                     
                                       β 
                                       k 
                                     
                                      
                                     
                                       β 
                                       k 
                                       T 
                                     
                                   
                                   ] 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         
                           b 
                           k 
                           T 
                         
                          
                         
                           
                             E 
                             Q 
                           
                            
                           
                             [ 
                             
                               β 
                               k 
                             
                             ] 
                           
                         
                       
                     
                     - 
                     
                       KL 
                       ( 
                       
                         
                           
                             
                               Q 
                                
                               
                                 ( 
                                 β 
                                 ) 
                               
                             
                              
                             
                                
                                
                             
                              
                             
                               P 
                                
                               
                                 ( 
                                 β 
                                 ) 
                               
                             
                           
                           - 
                           c 
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where A k , b k , and c depend on the choice of the quadratic bound. Equation (22) represents the upper bound output by the construction operation  30 . 
         [0023]    It will be appreciated that it is possible to construct  30  the upper bound as set forth in Equation (22) without actually generating the initial softmax function  24 . To illustrate this option, in  FIG. 2  the initial softmax function  24  is illustrated using dotted lines to represent that it may optionally be a conceptual element that is not actually generated. 
         [0024]    With continuing reference to  FIG. 2  and with brief reference to  FIG. 3 , the terms A k , b k , and c are given for the quadratic bound (B1) of Equation (4) and for the upper bound (B2) based on a double majorization of Equation (10). For the bound based on double majorization, the terms are: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       A 
                       k 
                     
                     = 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         
                           ∑ 
                           i 
                         
                          
                         
                           
                             λ 
                              
                             
                               ( 
                               
                                 ξ 
                                 ik 
                               
                               ) 
                             
                           
                            
                           
                             x 
                             i 
                           
                            
                           
                             x 
                             i 
                             T 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       b 
                       k 
                     
                     = 
                     
                       
                         ∑ 
                         i 
                       
                        
                       
                         
                           ( 
                           
                             
                               y 
                               ik 
                             
                             - 
                             
                               1 
                               2 
                             
                             + 
                             
                               2 
                                
                               
                                   
                               
                                
                               
                                 α 
                                 i 
                               
                                
                               
                                 λ 
                                  
                                 
                                   ( 
                                   
                                     ξ 
                                     ik 
                                   
                                   ) 
                                 
                               
                             
                           
                           ) 
                         
                          
                         
                           x 
                           i 
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     and 
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                     c 
                     = 
                     
                       
                         2 
                          
                         
                             
                         
                          
                         
                           
                             ∑ 
                             
                               i 
                               , 
                               k 
                             
                           
                            
                           
                             
                               α 
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   K 
                                   2 
                                 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                         
                       
                       + 
                       
                         
                           ξ 
                           ik 
                         
                         2 
                       
                       - 
                       
                         
                           λ 
                            
                           
                             ( 
                             
                               ξ 
                               ik 
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               α 
                               i 
                               2 
                             
                             - 
                             
                               ξ 
                               ik 
                               2 
                             
                           
                           ) 
                         
                       
                       - 
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             
                                
                               
                                 ξ 
                                 ik 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
     
         [0025]    With continuing reference to  FIG. 2 , the upper bound output by the construction operation  30  is minimized in computation operation  32  to generate the optimized transformation matrix  34 . Assuming independent Gaussian priors P=N(  μ   k ,  Σ   k ) for the parameters β k , k=1, . . . , K, the KL-divergence between Gaussians is given by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       KL 
                        
                       
                         ( 
                         
                           
                             Q 
                              
                             
                               ( 
                               β 
                               ) 
                             
                           
                            
                           
                              
                              
                           
                            
                           
                             P 
                              
                             
                               ( 
                               β 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         - 
                         
                           1 
                           2 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             1 
                           
                           K 
                         
                          
                         
                           ( 
                           
                             
                               
                                 
                                   
                                     log 
                                      
                                     
                                       
                                          
                                         
                                           
                                             Σ 
                                             _ 
                                           
                                           k 
                                         
                                          
                                       
                                       
                                          
                                         
                                           Σ 
                                           k 
                                         
                                          
                                       
                                     
                                   
                                   + 
                                   
                                     tr 
                                     ( 
                                     
                                       
                                         Σ 
                                         k 
                                       
                                        
                                       
                                         
                                           Σ 
                                           _ 
                                         
                                         k 
                                         
                                           - 
                                           1 
                                         
                                       
                                     
                                     ) 
                                   
                                   + 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       
                                         ( 
                                         
                                           
                                             μ 
                                             k 
                                           
                                           - 
                                           
                                             
                                               μ 
                                               _ 
                                             
                                             k 
                                           
                                         
                                         ) 
                                       
                                       T 
                                     
                                      
                                     
                                       
                                         
                                           Σ 
                                           _ 
                                         
                                         k 
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             μ 
                                             k 
                                           
                                           - 
                                           
                                             
                                               μ 
                                               _ 
                                             
                                             k 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                   - 
                                   Kd 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
     
         [0000]    so that a closed-form solution is obtained of the maximum of F(μ,Σ,ξ) with respect to μ and Σ: 
         [0000]      {circumflex over (Σ)} k =( A   k +  Σ   k   −1 ) −1   (27), 
         [0000]      and 
         [0000]      {circumflex over (μ)} k ={circumflex over (Σ)} k ( b+  Σ     k   −1   μ   k )  (28). 
         [0000]    This gives the updates: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         Σ 
                         ^ 
                       
                       k 
                       
                         - 
                         1 
                       
                     
                     = 
                     
                       
                         
                           Σ 
                           _ 
                         
                         k 
                         
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           ∑ 
                           i 
                         
                          
                         
                           2 
                            
                           
                               
                           
                            
                           
                             λ 
                              
                             
                               ( 
                               
                                 ξ 
                                 ik 
                               
                               ) 
                             
                           
                            
                           
                             x 
                             i 
                           
                            
                           
                             x 
                             i 
                             T 
                           
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   and 
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       μ 
                       ^ 
                     
                     k 
                   
                   = 
                   
                     
                       
                         
                           Σ 
                           ^ 
                         
                         k 
                       
                       [ 
                       
                         
                           
                             
                               Σ 
                               _ 
                             
                             k 
                             
                               - 
                               1 
                             
                           
                            
                           
                             
                               μ 
                               _ 
                             
                             k 
                           
                         
                         + 
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ( 
                               
                                 
                                   y 
                                   ik 
                                 
                                 - 
                                 
                                   1 
                                   2 
                                 
                                 + 
                                 
                                   2 
                                    
                                   
                                       
                                   
                                    
                                   
                                     α 
                                     i 
                                   
                                    
                                   
                                     λ 
                                      
                                     
                                       ( 
                                       
                                         ξ 
                                         ik 
                                       
                                       ) 
                                     
                                   
                                 
                               
                               ) 
                             
                              
                             
                               x 
                               i 
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
         [0026]    The optimized parameters β k , k=1, . . . , K  34  are directly computed from the optimized independent Gaussian priors P=N(  μ   k ,  Σ   k ). These optimized parameters  34  are then used to generate an optimized softmax function  40 , for example by inserting the optimized transformation matrix β  34  into the softmax function of Equation (20). A transformed vector P(y|x)  42  is readily generated by evaluating the optimized softmax function  40  for the input vector  22  to be transformed. For the illustrative practical application in which the continuous variables x  22  represent bag-of-words” representations of documents to be classified, the output transformed vector P(y|x)  42  represents the probabilities of the categories  24  for various documents represented as bags-of-words. In other words, the transformed vector P(y|x)  42  provides the soft classification probabilities for the input documents. In the illustrative practical application in which the continuous variables x  22  represent features vector representations of images, the output transformed vector P(y|x)  42  represents the probabilities of the categories  24  for various images represented by feature vectors. In other words, the transformed vector P(y|x)  42  provides the soft classification probabilities for the images to be classified. Again, these are merely non-limiting illustrative practical applications. The resulting output transformed vector P(y|x)  42  may be used in various ways, such as displaying the classification on the display  16 . For example, a “hard” classification may be obtained and displayed by assigning each text document or image the class having the highest probability in P(y|x). Alternatively, a plot of classification probabilities may be generated and displayed suitably coded by color or other distinguishing aspect. In other embodiments, the output transformed vector P(y|x)  42  is not directly displayed, but rather may be used to assign a hard or soft classification to the continuous variables  22  (text documents or images, in the illustrative practical examples) for use in indexing the documents or images in a database or other storage arrangement. 
         [0027]    In some applications, it may be desirable to operate on the moment generating function E Q [e β     k       T     x ], rather than on the log-sum-of-exponentials. In the case of the bound constructed  30  based on the moment generating function of Equation (12), the result is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       F 
                        
                       
                         ( 
                         
                           μ 
                           , 
                           Σ 
                           , 
                           φ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         - 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                             
                               μ 
                               k 
                               T 
                             
                              
                             
                               s 
                               k 
                             
                           
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           
                             φ 
                             i 
                           
                            
                           
                             
                               ∑ 
                               
                                 k 
                                 = 
                                 1 
                               
                               K 
                             
                              
                             
                                
                               
                                 
                                   
                                     μ 
                                     k 
                                     T 
                                   
                                    
                                   
                                     x 
                                     i 
                                   
                                 
                                 + 
                                 
                                   
                                     1 
                                     2 
                                   
                                    
                                   
                                     x 
                                     i 
                                     T 
                                   
                                    
                                   
                                     
                                       ∑ 
                                       k 
                                     
                                      
                                     
                                       x 
                                       i 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                       - 
                       
                         log 
                          
                         
                           ( 
                           
                             φ 
                             i 
                           
                           ) 
                         
                       
                       - 
                       n 
                       - 
                       
                         KL 
                          
                         
                           ( 
                           
                             
                               Q 
                                
                               
                                 ( 
                                 β 
                                 ) 
                               
                             
                              
                             
                                
                                
                             
                              
                             
                               P 
                                
                               
                                 ( 
                                 β 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     where 
                      
                     
                         
                     
                      
                     
                       : 
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       s 
                       k 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           , 
                           
                             
                               y 
                               i 
                             
                             = 
                             k 
                           
                         
                       
                        
                       
                         
                           x 
                           i 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The minimization  32  with respect to φ is straightforward. For a fixed φ, the objective can be decomposed into a sum of independent functions of (μ k ,Σ k ) that can be maximized independently for k=1, . . . , K. Since the gradient can be computed easily and F is concave with respect to μ and Σ, the minimization and can be done using a standard optimization package. In one suitable approach the reparameterizations φ=a 2  and Σ=R 0.5  (R 0.5 ) T  are used to transform to an unconstrained maximization problem. Alternatively, it is possible to find μ k  and Σ k  using a fixed point equation. In the case of quadratic bounds, the maximization of this function is done by iteratively maximizing with respect to the variational parameters and (μ,Σ). Every computation is analytical in this case. 
         [0028]    As used herein, the terms “optimization”, “minimization”, and the like are intended to encompass both absolute optimization or absolute minimization, and approximate optimization or approximate minimization. For example, in the Bayesian inference engine  10  of  FIG. 2 , the computing of the minimum of the upper bound may employ an iterative minimization algorithm whose iterations may be terminated based on a stopping criterion at some point before the absolute minimum is obtained. As used herein, this iterative minimization algorithm terminated prior to the absolute minimization computes a minimum of the upper bound, even though it may not be the absolute minimum. Similarly, the optimized transformation matrix  34  optimizes the softmax function respective to the constraints  20 ,  22 , even though it may not be the absolute most optimum matrix for the softmax function respective to the constraints  20 ,  22 . Indeed, since the upper bound is tight but not exactly equal to the softmax function (it is an upper bound and not, in general, an equality) the optimized transformation matrix  34  respective to the upper bound can be expected to be an approximate, but not exact, optimum for the bounded softmax function. 
         [0029]    Phraseology such as “of the form” when used respective to mathematical expressions is intended to be broadly construed to encompass the base mathematical expression modified by substantially any substantively insubstantial modification. For example, the softmax function form of Equation (20) may be modified by the addition of scalar constants, scaling constants within the exponential, or so forth, and the softmax function so modified remains of the same form as that of Equation (20). 
         [0030]    The illustrated embodiments relate to the softmax function. However, the disclosed techniques are more generally applicable to substantially any sum-of-exponentials function that includes at least one summation of exponentials. The optimization techniques disclosed herein entail constructing an upper bound using a double majorization bounding process to the softmax function or other sum-of-exponentials function including at least one summation of exponentials, and optimizing the constructed upper bound respective to parameters of the exponentials of the at least one summation of exponentials to generate optimized parameters. 
         [0031]    It will be appreciated that various of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.