# Patent

## Title
Systems, device, and methods for parameter optimization

## Abstract

A computerized method for optimizing parameters is described. A system can initialize a group of parameters to respective values within a set of allowable models and bound a partition function across a number of variable pairs to generate a plurality of bounds. The system can also determine new values for the group of parameters that minimize a sum of the plurality of bounds. The system can set the group of parameters to the new values and optimize the parameters by iteratively performing the bounding, determining and setting. The system can stop optimizing when a termination condition is reached.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of U.S. Provisional Application No. 61/494,281, entitled “Data Learning Using Probability Models and Conditional Random Fields” filed on 7 Jun. 2011, which is hereby incorporated herein by reference in its entirety.


FIELD
Embodiments relate generally to parameter optimization, and, more particularly, to computer systems, devices, methods and computer readable media for optimizing model parameters using partition function bounding.
BACKGROUND
Estimating probability density functions over sets of random variables can be a central problem in machine learning. For some problems, such as conditional random fields (CRFs) and log-linear models, estimation often requires minimizing a partition function.
Conventional bound-majorization methods were once used to optimize parameters and train models, but were overtaken by faster first-order and then second order methods.
SUMMARY
An embodiment optimizes partition functions by computing a quadratic variational upper bound. Embodiments include methods for computing a bound of the partition function for structured prediction (e.g., conditional random fields), conditional likelihood problems, graphical models and latent likelihood problems. Structured prediction applications can include, but are not limited to, pattern recognition, shallow parsing, named entity recognition, gene finding, object recognition and image segmentation systems.
Embodiments can include methods for tuning parameters for deep belief networks, automated labeling of data, web page parsing, named entity recognition, logistic regression, machine translation and web page annotation.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a flow chart of an example method for parameter optimization using a partition function bound in accordance with at least one embodiment.
FIG. 2 is a flow chart of an example method for parameter optimization for a model conditioned on observed input in accordance with at least one embodiment.
FIG. 3 is a flow chart of an example method for parameter optimization for a graphical model in accordance with at least one embodiment.
FIG. 4 is a flow chart of an example method for parameter optimization for high dimensional models in accordance with at least one embodiment.
FIG. 5 is a diagram of an example parameter optimization system in accordance with at least one embodiment.
FIG. 6 is a diagram of an example unsupervised machine learning system in accordance with at least one embodiment.
FIG. 7 is a diagram of an example supervised machine learning system in accordance with at least one embodiment.
FIG. 8 is a diagram of an example junction tree of depth 2.
FIG. 9 is a diagram of an example junction tree of depth 3.



DETAILED DESCRIPTION
The partition function can play a key role in probabilistic modeling including conditional random fields (CRFs), maximum entropy methods, graphical models and maximum likelihood estimation. An embodiment can include upper bounding a partition function using a quadratic function and optimizing parameters using the bounding.
FIG. 1 is a flow chart of an example method for parameter optimization using a partition function bound in accordance with at least one embodiment. In particular, at 102, initial parameters are provided to a system. At 104, a feature function (e.g., ƒ(y)) is provided to the system and, at 106, an a priori probability function (e.g., h(y)) is provided to the system.
At 108, the system computes a quadratic upper bound on a partition function as described below.
At 110, the system tests a loop index. If the end of the index has been reached, processing continues to 112, otherwise processing continues to 108.
At 112, the quadratic parameters of the partition function bound are provided for downstream processing.
The mathematical basis for partition function bounding (e.g., as shown in FIG. 1) is set forth below:
Consider a log-linear density model over discrete yεΩ




  
    p
    ⁡
    
      (
      
        y
        |
        θ
      
      )
    
  
  =
  
    
      1
      
        Z
        ⁡
        
          (
          θ
          )
        
      
    
    ⁢
    
      h
      ⁡
      
        (
        y
        )
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            θ
            T
          
          ⁢
          
            f
            ⁡
            
              (
              y
              )
            
          
        
        )
      
    
  




which is parameterized by a vector θεd of dimensionality dεZ. Here, ƒ:Ωd is any vector-valued function mapping an input y to some arbitrary vector. The prior h:Ω+ is a fixed non-negative measure. The partition function Z(θ) is a scalar that ensures that p(y|θ) normalizes, i.e. Z(θ)=Σyh(y)exp(θTƒ(y)). Assume that the number of configurations of y is |Ω|=n and is finite. The partition function is clearly log-convex in θ and a linear lower-bound is given via Jensen's inequality. As mentioned above, an embodiment can include computing a quadratic upper-bound on the partition function. Algorithm 1, below, provides a mathematical computation for the bound's parameters. Theorem 1, below, shows the precise guarantee it provides.










Algorithm 1



















Input {tilde over (θ)}, f(y), h(y) ∀y ε Ω




Init z → 0+, μ = 0, Σ = zI









For each y ε Ω {













α = h(y)exp({tilde over (θ)}Tf(y))





l = f(y) − μ



 









  Σ
  +=
  
    
      
        tan
        ⁢
        
          
        
        ⁢
        
          h
          ⁡
          
            (
            
              
                1
                2
              
              ⁢
              
                ln
                ⁡
                
                  (
                  
                    α
                    ⁢
                    
                      /
                    
                    ⁢
                    z
                  
                  )
                
              
            
            )
          
        
      
      
        2
        ⁢
        
          ln
          ⁡
          
            (
            
              α
              ⁢
              
                /
              
              ⁢
              z
            
            )
          
        
      
    
    ⁢
    
      ll
      T
    
  







 









  μ
  +=
  
    
      α
      
        z
        +
        α
      
    
    ⁢
    l
  







 





z += α }









Output z, μ, Σ










Theorem 1

Algorithm 1 finds z, μ, Σ such that z exp(1⁄2(θ−{tilde over (θ)})TΣ(θ−{tilde over (θ)})+(θ−{tilde over (θ)})Tμ) upper-bounds Z(θ)=Σyh(y)exp(θTƒ(y)) for any θ, {tilde over (θ)}, ƒ(y)εd and h(y)ε+ for all yεΩ.
The bound can improve previous inequalities and its proof is in the Appendix. For example, the bound can be computed using Algorithm 1 by iterating over the y variables (“for each yΣΩ”) according to an arbitrary ordering via the bijective function π:Ω{1, . . . , n} which defines i=π(y). The order in which we enumerate over Ω slightly varies the Σ in the bound (but not the μ and z) when |Ω|>2. Recall that choosing Σ=Σyh(y)exp({tilde over (θ)}Tƒ(y))(ƒ(y)−μ)(ƒ(y)−μ)T with μ and z as in Algorithm 1 yields the second-order Taylor approximation (the Hessian) of the log-partition function. Algorithm 1 replaces a sum of log-linear models with a single log-quadratic model which makes monotonic majorization straightforward.
FIG. 2 is a flow chart of an example method for parameter optimization for a model conditioned on observed input in accordance with at least one embodiment.
At 202, initial parameters are provided to a system.
At 204, the system computes or updates partition functions bounds. For example, the partition function bounds can be computed according to Algorithm 1 discussed above.
At 206, parameters are selected that minimize the sum of the bounds.
At 208, the current parameters are updated based on the selected parameters.
At 210, the system determines if a termination condition has been reached. The termination condition can include one or more of a predetermined number of iterations, a predetermined amount of elapsed time, and a difference between current parameters and subsequent parameters of less than a predetermined threshold. If the termination condition has been reached, the parameters can be provided for use in a downstream process. Otherwise, if the termination condition has not been reached, processing can continue back to 204, where the bounding and minimizing can be performed again. In general, the bounding and minimizing can be repeated until the parameters converge.
Partition functions arise naturally in maximum entropy estimation or minimum relative entropy




  
    R
    ⁢
    
      
    
    ⁢
    
      E
      ⁡
      
        (
        
          p
          ||
          h
        
        )
      
    
  
  =
  
    
      ∑
      y
    
    ⁢
    
      
        p
        ⁡
        
          (
          y
          )
        
      
      ⁢
      ln
      ⁢
      
        
          p
          ⁡
          
            (
            y
            )
          
        
        
          h
          ⁡
          
            (
            y
            )
          
        
      
    
  




estimation as follows





  
    
      
        min
        p
      
      ⁢
      
        
          RE
          ⁡
          
            (
            
              p
              ||
              h
            
            )
          
        
        ⁢
        
          s
          .
          t
          .
          
            
              ∑
              y
            
            ⁢
            
              
                p
                ⁡
                
                  (
                  y
                  )
                
              
              ⁢
              
                f
                ⁡
                
                  (
                  y
                  )
                
              
            
          
        
      
    
    =
    0
  
  ,
  
    
      
        ∑
        y
      
      ⁢
      
        
          p
          ⁡
          
            (
            y
            )
          
        
        ⁢
        
          g
          ⁡
          
            (
            y
            )
          
        
      
    
    ≥
    0.
  




Therein, yεΩ, ƒ:Ωd and g:Ω are arbitrary (non-constant) vector-valued functions over the sample space. The solution distribution p(y)=h(y)exp(θTƒ(y)+θTg(y))/Z(θ, θ) is recovered by the dual optimization




  θ
  ,
  
    θ
    =
    
      
        
          max
          arg
        
        
          
            θ
            ≥
            0
          
          ,
          θ
        
      
      ⁢
      
        
          -
          ln
        
        ⁢
        
          
            ∑
            y
          
          ⁢
          
            
              h
              ⁡
              
                (
                y
                )
              
            
            ⁢
            
              exp
              ⁡
              
                (
                
                  
                    
                      θ
                      T
                    
                    ⁢
                    
                      f
                      ⁡
                      
                        (
                        y
                        )
                      
                    
                  
                  +
                  
                    
                      θ
                      T
                    
                    ⁢
                    
                      g
                      ⁡
                      
                        (
                        y
                        )
                      
                    
                  
                
                )
              
            
          
        
      
    
  




where θεd and θεd′. These are obtained by minimizing Z(θ, θ) or equivalently by maximizing its negative logarithm. Algorithm 1 permits variational maximization of the dual via the quadratic program





  
    
      min
      
        
          θ
          ≥
          0
        
        ,
        θ
      
    
    ⁢
    
      
        1
        2
      
      ⁢
      
        
          (
          
            β
            -
            
              β
              ~
            
          
          )
        
        T
      
      ⁢
      
        Σ
        ⁡
        
          (
          
            β
            -
            
              β
              ~
            
          
          )
        
      
    
  
  +
  
    
      β
      T
    
    ⁢
    μ
  




where βT=[θTθT]. In fact, any general convex hull of constraints βεΛ⊂d+d′ could be imposed without loss of generality. In the case where there are no inequality constraints in the maximum entropy problem, only θεd is to be recovered and a simple closed-form iterative update rule emerges: {tilde over (θ)}←{tilde over (θ)}−Σ−1μ. This rule is interleaved with the bound computation to solve the dual optimization and obtain θ.

The partition function also arises in conditional extensions of the maximum entropy paradigm where the model is conditioned on an observed input. Such models are known as conditional random fields and have been useful for structured prediction problems. CRFs are given a data-set {(x1, y1), . . . , (xt, yt)} of independent identically-distributed (iid) input-output pairs where yj is the observed sample in a (discrete) space Ωj conditioned on the observed input xj. A CRF defines a distribution over all yεΩj (of which yj is a single element) as the log-linear model




  
    p
    ⁡
    
      (
      
        
          y
          |
          
            x
            j
          
        
        ,
        θ
      
      )
    
  
  =
  
    
      1
      
        
          z
          
            x
            j
          
        
        ⁡
        
          (
          θ
          )
        
      
    
    ⁢
    
      
        h
        
          x
          j
        
      
      ⁡
      
        (
        y
        )
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            θ
            T
          
          ⁢
          
            
              f
              
                x
                j
              
            
            ⁡
            
              (
              y
              )
            
          
        
        )
      
    
  




where Zxj(θ)=ΣyεΩjhxj(y)exp(θTƒxj(y)). For the j'th training pair, we are given a non-negative function hxj(y)ε+ and a vector-valued function ƒxj(y)εd defined over the domain yεΩj. In this section, for simplicity, assume n=maxj=1t|Ωyj|. Each partition function Zxj(θ) is a function of θ. The parameter θ for CRFs is estimated by maximizing the regularized conditional log-likelihood or log-posterior:





  
    
      ∑
      
        j
        =
        1
      
      t
    
    ⁢
    
      ln
      ⁢
      
        
      
      ⁢
      
        p
        ⁡
        
          (
          
            
              
                y
                j
              
              |
              
                x
                j
              
            
            ,
            θ
          
          )
        
      
    
  
  -
  
    
      
        t
        ⁢
        
          
        
        ⁢
        λ
      
      2
    
    ⁢
    
      
        
        θ
        
      
      2
    
  




where λε+ is a regularizer set using prior knowledge or cross-validation. Rewriting gives the objective of interest





  
    
      
        
          J
          ⁡
          
            (
            θ
            )
          
        
        =
        
          
            
              ∑
              
                j
                =
                1
              
              t
            
            ⁢
            
              ln
              ⁢
              
                
              
              ⁢
              
                
                  
                    h
                    
                      x
                      j
                    
                  
                  ⁡
                  
                    (
                    
                      y
                      j
                    
                    )
                  
                
                
                  
                    z
                    
                      x
                      j
                    
                  
                  ⁡
                  
                    (
                    θ
                    )
                  
                
              
            
          
          +
          
            
              θ
              T
            
            ⁢
            
              
                f
                
                  x
                  j
                
              
              ⁡
              
                (
                
                  y
                  j
                
                )
              
            
          
          -
          
            
              
                t
                ⁢
                
                  
                
                ⁢
                λ
              
              2
            
            ⁢
            
              
                
                  
                  θ
                  
                
                2
              
              .
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




If prior knowledge (or constraints) restrict the solution vector to a convex hull Λ, the maximization problem becomes argmaxθεΛJ(θ). The maximization of Equation 1 thus subsumes the minimum relative entropy problem.
Algorithm 3 proposes a method for maximizing the regularized conditional likelihood J(θ) or, equivalently minimizing the partition function Z(θ). It solves the problem in Equation 1 subject to convex constraints by interleaving the quadratic bound with a quadratic programming procedure. Theorem 2 establishes the convergence of the algorithm and the proof is in the Supplement.










Algorithm 2
















0:
Input xj, yj and functions hxj, fxj for j = 1, ..., t



Input regularizer λ ε   + and convex hull Λ ⊂   d


1:
Initialize θ0 anywhere inside Λ and set {tilde over (θ)} = θ0



While not converged


2:
 For j = 1, ..., t



  Get μj, Σj from hxj, fxj, {tilde over (θ)} via Algorithm 1


3:
 Set {tilde over (θ)} = arg minθεΛ Σj 1⁄2(θ − {tilde over (θ)})T (Σj + λI)(θ − {tilde over (θ)})



        + Σj θT (μj − fxj(yj) + λ{tilde over (θ)})


4:
Output {circumflex over (θ)} = {tilde over (θ)}









Theorem 2

For any θ0εΛ, all ∥ƒxj(y)∥2≦r and all |Ωj|≦n, Algorithm 2 outputs a {circumflex over (θ)} such that



  
    
      J
      ⁡
      
        (
        
          θ
          ^
        
        )
      
    
    =
    
      
        J
        ⁡
        
          (
          
            θ
            0
          
          )
        
      
      ≥
      
        
          (
          
            1
            -
            ɛ
          
          )
        
        ⁢
        
          
            max
            θεΛ
          
          ⁢
          
            
              (
              
                
                  J
                  ⁡
                  
                    (
                    θ
                    )
                  
                
                -
                
                  J
                  ⁡
                  
                    (
                    
                      θ
                      0
                    
                    )
                  
                
              
              )
            
            ⁢
            
              
            
            ⁢
            within
          
        
      
    
  




  
    
      ⌈
      
        
          ln
          (
          
            1
            ɛ
          
          )
        
        /
        
          ln
          (
          
            1
            +
            
              
                λ
                
                  2
                  ⁢
                  r
                
              
              ⁢
              
                
                  (
                  
                    
                      ∑
                      
                        i
                        =
                        1
                      
                      
                        n
                        -
                        1
                      
                    
                    ⁢
                    
                      
                        tanh
                        ⁡
                        
                          (
                          
                            
                              ln
                              ⁡
                              
                                (
                                i
                                )
                              
                            
                            /
                            2
                          
                          )
                        
                      
                      
                        ln
                        ⁡
                        
                          (
                          i
                          )
                        
                      
                    
                  
                  )
                
                
                  -
                  1
                
              
            
          
          )
        
      
      ⌉
    
    ⁢
    
      
    
    ⁢
    
      steps
      .
    
  



The series




  
    
      ∑
      
        i
        =
        1
      
      
        n
        -
        1
      
    
    ⁢
    
      
        tanh
        ⁡
        
          (
          
            
              ln
              ⁡
              
                (
                i
                )
              
            
            /
            2
          
          )
        
      
      
        ln
        ⁡
        
          (
          i
          )
        
      
    
  
  =
  
    
      ∑
      
        i
        =
        1
      
      
        n
        -
        1
      
    
    ⁢
    
      
        i
        -
        1
      
      
        
          (
          
            i
            +
            1
          
          )
        
        ⁢
        
          ln
          ⁡
          
            (
            i
            )
          
        
      
    
  




is the logarithmic integral which is





  O
  ⁡
  
    (
    
      n
      
        ln
        ⁢
        
          
        
        ⁢
        n
      
    
    )
  




asymptotically.

Maximum conditional likelihood is extended to the setting where some variables are latent. We are given t iid samples x1, . . . , xt from some unknown distribution p(x) and t corresponding samples y1, . . . , yt drawn from identical conditional distributions p(y|x1), . . . , p(y|xt) respectively. Assume that the true generating distributions p(x) and p(y|x) are unknown. Therefore, we aim to estimate a conditional distribution p(y|x) from some set of hypotheses that achieves high conditional likelihood given the data-set D={(x1, y1), . . . , (xt, yt)}. We will select this conditional distribution by assuming it emerges from a conditioned joint distribution over x and y as well as a hidden variable m which is being marginalized as




  
    p
    ⁡
    
      (
      
        
          y
          |
          x
        
        ,
        Θ
      
      )
    
  
  =
  
    
      
        
          ∑
          m
        
        ⁢
        
          p
          ⁡
          
            (
            
              x
              ,
              y
              ,
              
                m
                |
                Θ
              
            
            )
          
        
      
      
        
          ∑
          
            y
            ,
            m
          
        
        ⁢
        
          p
          ⁡
          
            (
            
              x
              ,
              y
              ,
              
                m
                |
                Θ
              
            
            )
          
        
      
    
    .
  




Here mεΩm represents a discrete hidden variable, xεΩx is an input and yεΩy is a discrete output variable. The parameter Θ contains all parameters that explore the function class of such conditional distributions. The latent likelihood of the data L(Θ)=p(D|Θ) subsumes Equation 1 and is the new objective of interest





  
    
      
        
          L
          ⁡
          
            (
            Θ
            )
          
        
        =
        
          
            
              ∏
              
                j
                =
                1
              
              t
            
            ⁢
            
              p
              ⁡
              
                (
                
                  
                    
                      y
                      j
                    
                    |
                    
                      x
                      j
                    
                  
                  ,
                  Θ
                
                )
              
            
          
          =
          
            
              ∏
              
                j
                =
                1
              
              t
            
            ⁢
            
              
                
                  
                    ∑
                    m
                  
                  ⁢
                  
                    p
                    ⁡
                    
                      (
                      
                        
                          x
                          j
                        
                        ,
                        
                          y
                          j
                        
                        ,
                        
                          m
                          |
                          Θ
                        
                      
                      )
                    
                  
                
                
                  
                    ∑
                    
                      y
                      ,
                      m
                    
                  
                  ⁢
                  
                    p
                    ⁡
                    
                      (
                      
                        
                          x
                          j
                        
                        ,
                        y
                        ,
                        
                          m
                          |
                          Θ
                        
                      
                      )
                    
                  
                
              
              .
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




A good choice of the parameters is one that achieves a large conditional likelihood value (or posterior) on the data set D. Next, assume that each p(x|y, m, Θ) is an exponential family distribution

p(x|y,m,Θ)=hy,m(x)exp(θy,mTφy,m(x)−ay,m(θy,m))

where each conditional is specified by a function hy,m:Ωx+ and a feature mapping φy,m:Ωxdy,m which are then used to derive the normalizer ay,mdy,m+. A parameter θy,mεdy,m selects a specific distribution. Multiply each exponential family term by an unknown marginal distribution called the mixing proportions





  
    p
    ⁡
    
      (
      
        y
        ,
        
          m
          |
          π
        
      
      )
    
  
  =
  
    
      
        π
        
          y
          ,
          m
        
      
      
        
          ∑
          
            y
            ,
            m
          
        
        ⁢
        
          π
          
            y
            ,
            m
          
        
      
    
    .
  




This is parametrized by an unknown parameter π={πy,m}∀y,m where πy,mε[0, ∞). Finally, the collection of all parameters is Θ={θy,m, πy,m}∀y,m. Thus, we have the complete likelihood





  
    p
    ⁡
    
      (
      
        x
        ,
        y
        ,
        
          m
          |
          Θ
        
      
      )
    
  
  =
  
    
      
        
          π
          
            y
            ,
            m
          
        
        ⁢
        
          h
          ⁡
          
            (
            x
            )
          
        
      
      
        
          ∑
          
            y
            ,
            m
          
        
        ⁢
        
          π
          
            y
            ,
            m
          
        
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            
              θ
              
                y
                ,
                m
              
              T
            
            ⁢
            
              φ
              ⁡
              
                (
                x
                )
              
            
          
          -
          
            a
            ⁡
            
              (
              
                θ
                
                  y
                  ,
                  m
                
              
              )
            
          
        
        )
      
    
  




where, without loss of generality, we dropped the index y, m indexing h(x), φ(x), and a(θ), making each conditional belong to the same exponential family form. Insert this expression into Equation 2 and remove constant factors that appear in both denominator and numerator. Apply the change of variables exp(vy,m)=πy,mexp(−a(θy,m)) and rewrite as





  
    L
    ⁡
    
      (
      Θ
      )
    
  
  =
  
    
      ∏
      
        j
        =
        1
      
      t
    
    ⁢
    
      
        
          
            ∑
            m
          
          ⁢
          
            exp
            ⁡
            
              (
              
                
                  
                    θ
                    
                      
                        y
                        j
                      
                      ,
                      m
                    
                    T
                  
                  ⁢
                  
                    φ
                    ⁡
                    
                      (
                      
                        x
                        j
                      
                      )
                    
                  
                
                +
                
                  v
                  
                    
                      y
                      j
                    
                    ,
                    m
                  
                
              
              )
            
          
        
        
          
            ∑
            
              y
              ,
              m
            
          
          ⁢
          
            exp
            ⁡
            
              (
              
                
                  
                    θ
                    
                      y
                      ,
                      m
                    
                    T
                  
                  ⁢
                  
                    φ
                    ⁡
                    
                      (
                      
                        x
                        j
                      
                      )
                    
                  
                
                +
                
                  v
                  
                    y
                    ,
                    m
                  
                
              
              )
            
          
        
      
      .
    
  




The objective as a function (it is now easy to regularize L(θ) by adding





  
    
      -
      
        
          t
          ⁢
          
            
          
          ⁢
          λ
        
        2
      
    
    ⁢
    
      
        
        θ
        
      
      2
    
  
  )




of a vector θ is simply





  
    L
    ⁡
    
      (
      θ
      )
    
  
  =
  
    
      ∏
      
        j
        =
        1
      
      t
    
    ⁢
    
      
        
          ∑
          m
        
        ⁢
        
          exp
          ⁡
          
            (
            
              
                θ
                T
              
              ⁢
              
                f
                
                  j
                  ,
                  
                    y
                    j
                  
                  ,
                  m
                
              
            
            )
          
        
      
      
        
          ∑
          
            y
            ,
            m
          
        
        ⁢
        
          exp
          ⁡
          
            (
            
              
                θ
                T
              
              ⁢
              
                f
                
                  j
                  ,
                  y
                  ,
                  m
                
              
            
            )
          
        
      
    
  




after arranging parameters Θ in θε|Ωy∥Ωm|(d+1) as

[θ1,1Tv1,1θ1,2Tv1,2 . . . θ|Ωy|,|Ωm|Tv|Ωy|,|Ωm|]T.

Similarly, introduce vectors ƒj,ŷ,{circumflex over (m)}ε|Ωy∥Ωm|(d+1) defined as

[[φ(xj)T1]δ[(ŷ,{circumflex over (m)})=(1,1)] . . . [φ(xj)T1]δ[(ŷ,{circumflex over (m)})=(|Ωy|,|Ωm|)]]T.

In other words, the feature vector [φ(xj)T1]T is positioned appropriately in the longer ƒj,ŷ,{circumflex over (m)} vector which is otherwise equal to zero. Consider finding a variational lower bound on L(θ)≧Q(θ, {tilde over (θ)}) which is tight when θ={tilde over (θ)} such that L({tilde over (θ)})=Q({tilde over (θ)}, {tilde over (θ)}). We proceed by bounding each numerator and each denominator in the product over j=1, . . . , t as follows. Apply Jensen's inequality to lower bound each numerator term as



  
    
      
        ∑
        m
      
      ⁢
      
        exp
        ⁡
        
          (
          
            
              θ
              T
            
            ⁢
            
              f
              
                j
                ,
                
                  y
                  j
                
                ,
                m
              
            
          
          )
        
      
    
    ≥
    
      e
      
        
          θ
          ⁢
          
            
          
          ⁢
          T
          ⁢
          
            
              ∑
              m
            
            ⁢
            
              
                η
                
                  j
                  ,
                  m
                
              
              ⁢
              
                f
                
                  j
                  ,
                  m
                
              
              ⁢
              
                f
                
                  j
                  ,
                  
                    
                      y
                      
                        j
                        ,
                      
                    
                    ⁢
                    m
                  
                
              
            
          
        
        -
        
          
            ∑
            m
          
          ⁢
          
            
              η
              
                j
                ,
                m
              
            
            ⁢
            l
            ⁢
            
              
            
            ⁢
            n
            ⁢
            
              
            
            ⁢
            
              η
              
                j
                ,
                m
              
            
          
        
      
    
  




  where




  
    
      η
      
        j
        ,
        m
      
    
    =
    
      
        (
        
          e
          
            
              
                θ
                ~
              
              T
            
            ⁢
            
              f
              
                j
                ,
                
                  
                    y
                    
                      j
                      ,
                    
                  
                  ⁢
                  m
                
              
            
          
        
        )
      
      /
      
        
          (
          
            
              ∑
              
                m
                ′
              
            
            ⁢
            
              e
              
                
                  
                    θ
                    ~
                  
                  T
                
                ⁢
                
                  f
                  
                    j
                    ,
                    
                      y
                      j
                    
                    ,
                    
                      m
                      ′
                    
                  
                
              
            
          
          )
        
        .
      
    
  



Algorithm 1 then bounds the denominator





  
    
      ∑
      
        y
        ,
        m
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            θ
            T
          
          ⁢
          
            f
            
              j
              ,
              y
              ,
              m
            
          
        
        )
      
    
  
  ≤
  
    
      z
      j
    
    ⁢
    
      
        e
        
          
            
              1
              2
            
            ⁢
            
              
                (
                
                  θ
                  -
                  
                    θ
                    ~
                  
                
                )
              
              T
            
            ⁢
            
              
                ∑
                j
              
              ⁢
              
                (
                
                  θ
                  -
                  
                    θ
                    ~
                  
                
                )
              
            
          
          +
          
            
              
                (
                
                  θ
                  -
                  
                    θ
                    ~
                  
                
                )
              
              T
            
            ⁢
            
              μ
              j
            
          
        
      
      .
    
  




The overall lower bound on the likelihood is then




  
    Q
    ⁡
    
      (
      
        θ
        ,
        
          θ
          ~
        
      
      )
    
  
  =
  
    
      L
      ⁡
      
        (
        
          θ
          ~
        
        )
      
    
    ⁢
    
      e
      
        
          
            -
            
              1
              2
            
          
          ⁢
          
            
              (
              
                θ
                -
                
                  θ
                  ~
                
              
              )
            
            T
          
          ⁢
          
            
              Σ
              ~
            
            ⁡
            
              (
              
                θ
                -
                
                  θ
                  ~
                
              
              )
            
          
        
        -
        
          
            
              (
              
                θ
                -
                
                  θ
                  ~
                
              
              )
            
            T
          
          ⁢
          
            μ
            ~
          
        
      
    
  




where {tilde over (Σ)}=Σj=1tΣj and {tilde over (μ)}=Σj=1tμj−Σmηj,mƒj,yj,m. The right hand side is simply an exponentiated quadratic function in θ which is easy to maximize. In the unconstrained case, this yields the update rule θ={tilde over (θ)}−{tilde over (Σ)}−1{tilde over (μ)}. Alternatively, if θ must satisfy linear (convex) constraints it is straightforward to compute an update by solving a quadratic (convex) program. This yields an iterative scheme similar to Algorithm 2 for monotonically maximizing latent conditional likelihood.

FIG. 3 is a flow chart of an example method for parameter optimization for a graphical model in accordance with at least one embodiment.
At 302, a graphical model is provided to a system. The graphical model can be in the form of a junction tree, for example, or converted from a first form into a junction tree.
At 304, the system can set indexes to begin at a leaf node level of the graphical model.
At 306, bounds at the current node level can be computed and/or updated. The bound computation includes collecting pre-computed bounds from child nodes, as described below with respect to Algorithm 3.
At 308, the system traverses up one level in the graphical model.
At 310, the system determines if it has reached a root node level (e.g., reached the node level associated with index m as discussed below). If the system has not reached the root node level, then processing continues to 306. If the system has reached the root node level, then processing continues to 312 where parameters of a quadratic partition function bound are provided as output.
The bounds discussed above (e.g., Algorithms 1 and 2) are straightforward to compute when Ω is small. However, for graphical models, enumerating over Ω can be daunting. The method described in FIG. 3 above and in Algorithm 3 below provides faster algorithms that recover the bound efficiently for graphical models of bounded tree-width. A graphical model represents the factorization of a probability density function. This example uses a factor graph notation of a graphical model. A factor graph is a bipartite graph G=(V, W, E) with variable vertices V={1, . . . , k}, factor vertices W={1, . . . , m} and a set of edges E between V and W. In addition, define a set of random variables Y={y1, . . . , yk} each associated with the elements of V and a set of non-negative scalar functions Ψ={ψ1, . . . , ψm} each associated with the elements of W. The factor graph implies that p(Y) factorizes as




  
    p
    ⁡
    
      (
      
        
          y
          1
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          y
          k
        
      
      )
    
  
  =
  
    
      1
      Z
    
    ⁢
    
      
        ∏
        
          c
          ∈
          W
        
        
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          ψ
          c
        
        ⁡
        
          (
          
            Y
            c
          
          )
        
      
    
  




where Z is a normalizing partition function (the dependence on parameters is suppressed here) and Yc is a subset of the random variables that are associated with the neighbors of node c. In other words, Yc={yi|iεNe(c)} where Ne(c) is the set of vertices that are neighbors of c.

Inference in graphical models requires the evaluation and the optimization of Z. These computations can be NP-hard in general yet are efficient when G satisfies certain properties. Consider the function class p(Y|θ) indexed by a parameter θεΛ where Λ⊂d is a convex hull. More specifically, consider the log-linear model




  
    p
    ⁡
    
      (
      
        Y
        |
        θ
      
      )
    
  
  =
  
    
      1
      
        Z
        ⁡
        
          (
          θ
          )
        
      
    
    ⁢
    
      
        ∏
        
          c
          ∈
          W
        
        
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          
            h
            c
          
          ⁡
          
            (
            
              Y
              c
            
            )
          
        
        ⁢
        
          exp
          ⁡
          
            (
            
              
                θ
                T
              
              ⁢
              
                
                  f
                  c
                
                ⁡
                
                  (
                  
                    Y
                    c
                  
                  )
                
              
            
            )
          
        
      
    
  




where Z(θ)=ΣYΠcεWhc(Yc)exp(θTƒc(Yc)). The model is defined by a set of vector-valued functions ƒc(Yc)εd and scalar-valued functions hc(Yc)ε+. Choosing a function from the function class hinges on estimating θ by optimizing Z(θ). However, Algorithm 1 may be inapplicable due to the large number of configurations in Y. Instead, consider a more efficient surrogate algorithm which computes the same bound parameters by efficiently exploiting the factorization of the graphical model. This is possible since exponentiated quadratics are closed under multiplication and the required bound computations distribute nicely across decomposable graphical models.
Begin by assuming that the graphical model in question is a junction tree and satisfies the running intersection property. It is known that any graphical model can be converted into such a form at the expense of growing the cardinality of the factors cεW. Starting with a general graph G, convert it into a junction tree T as follows. First, triangulate it by adding as few edges as possible (this does not change p(Y|θ)). Once triangulated, form a junction tree T by connecting overlapping cliques to maximize the sum of the cardinalities of clique intersections. Then, using the junction tree T, compute the bound parameters via Algorithm 3. This algorithm only requires enumerating over each configuration of pairs of adjacent cliques which is clearly more efficient than enumerating over all configurations of Y. Algorithm 3 can be used interchangeably with Algorithm 1 when the partition function involves a graphical model.
In Algorithm 3, take ch(c) to be the set of children-cliques of clique c and pa(c) to be the parent of c. Note that the algorithm enumerates over uεYpa(c)∩Yc and vεYc\Ypa(c). The algorithm stores a quadratic bound for each configuration of u (where u is the set of variables in common across both clique c and its parent). It then forms the bound by summing over vεYc\Ypa(c), each configuration of each variable a clique c has that is not shared with its parent clique. The algorithm also collects precomputed bounds from children of c. Also define w=uvεYc as the conjunction of both indexing variables u and v. Thus, the two inner for loops enumerate over all configurations wεYc of each clique. Note that w is used to query the children bεch(c) of a clique c to report their bound parameters zb|w, μb|w, Σb|w. This is done for each configuration w of the clique c. Note, however, that not every variable in clique c is present in each child b so only the variables in w that intersect Yb are relevant in indexing the parameters zb|w, μb|w, Σb|w, and the remaining variables do not change the values of zb|w, μb|w, Σb|w.










Algorithm 3















Input {tilde over (θ)} ∈  d and reverse-topological tree T with


 c=1, . . .,m factors hc(Yc)exp({tilde over (θ)}T fc(Yc))


for c=1, . . . ,m


if (c<m) {Yboth = Yc ∩ Ypa(c), Ysolo = Yc\Ypa(c)}


else {Yboth = {}, Ysolo = Yc}


for each u ∈ Yboth


initialize zc|x ← 0+, μc|x = 0, Σc|x = zc|xI


for each v ∈ Ysolo


{  w = u   v


 αw = hc(w) Πb∈ch(c) zb|w


 lw = fc(w) − μc|u + Σb∈ch(c) μb|w


 


 



  
    ∑
    
      c
      ⁢
      
        
      
      |
      
        
      
      ⁢
      u
    
  
  ⁢
  
    +=
    
      
        ∑
        
          b
          ⁢
          
            
          
          ∈
          
            
          
          ⁢
          
            ch
            ⁡
            
              (
              c
              )
            
          
        
      
      ⁢
      
        
          ∑
          
            b
            ⁢
            
              
            
            |
            
              
            
            ⁢
            w
          
        
        ⁢
        
          
            +
            
              
                tanh
                ⁡
                
                  (
                  
                    
                      1
                      2
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      ln
                      ⁡
                      
                        (
                        
                          
                            α
                            w
                          
                          
                            z
                            
                              c
                              ⁢
                              
                                
                              
                              |
                              
                                
                              
                              ⁢
                              u
                            
                          
                        
                        )
                      
                    
                  
                  )
                
              
              
                2
                ⁢
                
                  ln
                  ⁡
                  
                    (
                    
                      
                        α
                        w
                      
                      
                        z
                        
                          c
                          ⁢
                          
                            
                          
                          |
                          
                            
                          
                          ⁢
                          u
                        
                      
                    
                    )
                  
                
              
            
          
          ⁢
          
            l
            w
          
          ⁢
          
            l
            w
            T
          
        
      
    
  






 


 



  
    μ
    
      c
      |
      u
    
  
  +=
  
    
      
        α
        w
      
      
        
          z
          
            c
            |
            u
          
        
        +
        
          α
          w
        
      
    
    ⁢
    
      l
      w
    
  






 


 zc|u+= αw              }


Output    Bound as z = zm, μ = μm, Σ = Σm









Algorithm 3 is efficient in the sense that computations involve enumerating over all configurations of each clique in the junction tree rather than over all configurations of Y. This shows that the computation involved is O(Σc|Yc|) rather than O(|Ω|) as in Algorithm 1. Thus, for estimating the computational efficiency of various algorithms in this article, take n=Σc|Yc| for the graphical model case rather than n=|Ω|. Algorithm 3 is a simple extension of the known recursions that are used to compute the partition function and its gradient vector. Thus, in addition to the Σ matrix which represents the curvature of the bound, Algorithm 3 is recovering the partition function value z and the gradient since




  
    
      
        μ
        =
        
          
            
              ∂
              ln
            
            ⁢
            
              
            
            ⁢
            
              Z
              ⁡
              
                (
                θ
                )
              
            
          
          
            ∂
            θ
          
        
      
      
    
    
      θ
      =
      
        θ
        ~
      
    
  
  .




FIG. 4 is a flow chart of an example method for parameter optimization for high dimensional models in accordance with at least one embodiment.
At 402 a system is provided with initial parameters and/or data having one or more large dimensions.
At 404, the quadratic bound of the partition function is updated by representing the curvature of the quadratic with a group of matrices of relatively low rank compared to a dimension of one or more of the inputs.
At 406, the system finds parameters that minimize a sum of the bounds.
At 408, the system updates stored parameters.
At 410, the system test for a termination condition. The termination condition can include one or more of the conditions described above with respect to 210 of FIG. 2.
At 412, the system provides parameters as output.
Consider the situation where d is large and Algorithm 2 cannot store and invert the matrix Σ=tλI+Σj=1tΣj. Each loop of the algorithm requires O(tnd2+d3) time since step 2 requires computes each Σjεd×d and step 3 performs inversion. Algorithm 4 provides a low-rank version of the bound which majorizes the log-partition function but requires only O ̃(tnd) complexity (on par with LBFGS). Below is a description of the mathematical algorithm changes to Algorithm 3 in order to efficiently handle high dimension inputs.
We first replace step 3 in Algorithm 2 with {tilde over (θ)}={tilde over (θ)}−Mu with M=Σ−1 and u=tλ{tilde over (θ)}+Σj=1tμj−ƒxj(yj). Clearly, we can recover u by only computing μ→j for j=1, . . . , t and skipping all steps involving matrices. This merely requires O(tnd) work. Second, instead of Σ, we initialize




  M
  =
  
    
      1
      
        t
        ⁢
        
          
        
        ⁢
        λ
      
    
    ⁢
    I
  




and use Sherman-Morrison to incrementally invert it via




  
    
      
        M
        i
      
      =
      
        
          M
          
            i
            -
            1
          
        
        -
        
          
            
              
                M
                
                  i
                  -
                  1
                
              
              ⁢
              
                q
                i
              
              ⁢
              
                q
                i
                T
              
              ⁢
              
                M
                
                  i
                  -
                  1
                
              
            
            
              1
              +
              
                
                  q
                  i
                  T
                
                ⁢
                
                  M
                  
                    i
                    -
                    1
                  
                
                ⁢
                
                  q
                  i
                
              
            
          
          ⁢
          
            
          
          ⁢
          where
        
      
    
    ⁢
    
      
    
  




  
    
      q
      i
    
    =
    
      
        
          
            tanh
            ⁡
            
              (
              
                
                  1
                  2
                
                ⁢
                
                  ln
                  ⁡
                  
                    (
                    
                      α
                      /
                      z
                    
                    )
                  
                
              
              )
            
          
          
            2
            ⁢
            
              
            
            ⁢
            
              ln
              ⁡
              
                (
                
                  α
                  /
                  z
                
                )
              
            
          
        
      
      ⁢
      
        
          (
          
            
              f
              i
            
            -
            
              μ
              i
            
          
          )
        
        .
      
    
  



Here, the index i ranges over all rank 1 updates to the matrix Σ for all elements of Ω as well as j=1, . . . , t. Third, we store M using a low-rank representation VSV^T+D where VεR^(k×d) is orthonormal, SεR^(k×k) is non-positive diagonal and DεR^(n×n) is non-negative diagonal. To decrement the matrix by a rank one update of the form Mi=Mi−1−ririT, simply project ri onto each eigenvector in V and update the appropriate singular value in S. After k such projections, the remaining residual from ri is a new candidate eigenvector e(k+1) and its magnitude is a candidate singular value. The resulting rank (k+1) system is orthonormal with (k+1) singular values. We discard the smallest singular value and its corresponding eigenvector to revert back to an order k eigensystem. However, instead of discarding it we absorb the smallest singular value and eigenvector into the D component by bounding the remaining outer-product with a diagonal term. This provides a guaranteed overall upper bound in O ̃(tnd) (k is set be logarithmic with dimension d).











Algorithm 4
















 
Input {tilde over (θ)}, ft(y) ∈  d and λ, ht(y) ∈  + with k ∈  


 







  
    S
    =
    
      diag
      ⁡
      
        (
        0
        )
      
    
  
  ,
  
    V
    =
    orthonormal
  
  ,
  
    D
    =
    
      
        1
        
          
            
            t
            
          
          ⁢
          λ
        
      
      ⁢
      
        diag
        ⁡
        
          (
          I
          )
        
      
    
  






 



For each t {



Set z → 0+; μ = 0;



For each y {


 



 



  
    α
    =
    
      
        
          h
          t
        
        ⁡
        
          (
          y
          )
        
      
      ⁢
      
        e
        
          
            
              θ
              ~
            
            T
          
          ⁢
          
            
              f
              t
            
            ⁡
            
              (
              y
              )
            
          
        
      
    
  
  ;
  
    q
    =
    
      
        
          
            tanh
            ⁡
            
              (
              
                
                  1
                  2
                
                ⁢
                
                  ln
                  ⁡
                  
                    (
                    
                      α
                      z
                    
                    )
                  
                
              
              )
            
          
        
        
          
            2
            ⁢
            
              ln
              ⁡
              
                (
                
                  α
                  z
                
                )
              
            
          
        
      
      ⁢
      
        (
        
          
            
              f
              t
            
            ⁡
            
              (
              y
              )
            
          
          -
          μ
        
        )
      
    
  
  ;






 







  
    r
    =
    
      
        V
        ⁡
        
          (
          
            S
            ⁡
            
              (
              
                
                  V
                  T
                
                ⁢
                q
              
              )
            
          
          )
        
      
      +
      Dq
    
  
  ;
  
    r
    =
    
      
        1
        
          
            1
            +
            
              
                r
                T
              
              ⁢
              q
            
          
        
      
      ⁢
      r
    
  
  ;
  
    r
    =
    r
  
  ;







 For j=1, . . . ,k



  ρ = rTV(j,•); S(j, j) = S(j, j) − ρ2;



  r = r − ρV(j,•); s = [S(1,1), . . . ,S(k,k), − ∥ r ∥2]T



     {tilde over (k)} = argmaxi=1,...,k+1s(i);



     if ({tilde over (k)} ≦ k) { {



      D = D + S({tilde over (k)}, {tilde over (k)})|1TV(j,•)|diag(|V(k,•)|);



      S({tilde over (k)}, {tilde over (k)})=−∥r∥{circumflex over ( )}2; r=∥r∥{circumflex over ( )}(−1) r; V(k,•)=r }



     else { D = D − |1Tr|diag(|r|) } }



    



  
    
      
        μ
        +=
        
          
            α
            
              z
              +
              α
            
          
          ⁢
          
            (
            
              
                
                  f
                  t
                
                ⁡
                
                  (
                  y
                  )
                
              
              -
              μ
            
            )
          
        
      
      ;
      
        z
        +=
        α
      
      ;
    
    ⁢
    
      
    
    }
  
  ⁢
  
    
  
  }







   Output S ∈ diag(  k×k),V ∈  d×k, D ∈ diag(  d×d)









FIG. 5 is a diagram of an example parameter optimization system 500 that can be used to optimize parameters in accordance with at least one embodiment. The system 500 includes a processor 502, an operating system 504, memory 506 and an I/O interface 508. The memory 506 can include a parameter optimizer 510 and a section for parameter data 512 and data used to optimize parameters by computing a quadratic bound on a partition function.
In operation, the processor 502 may execute the parameter optimizer 510 stored in the memory 506. The parameter optimizer 510 can include software instructions that, when executed by the processor, cause the processor to perform operations for optimizing parameters in accordance with the present disclosure (e.g., performing one or more of steps 102-112, 202-212, steps 302-312 and/or steps 402-412 described above).
The parameter optimizer 510 can operate in conjunction with the operating system 504 and utilize the parameter data 512 as described above.
FIG. 6 is a diagram of an example unsupervised machine learning environment 600. The environment 600 includes a machine learning system 602 and a prediction system 604.
In operation, the machine learning system 602 receives feature vectors 608 derived from input data (e.g., image data, audio data, text files, web pages or the like). The machine learning system can determine an optimized parameter set based on the input feature vectors. The parameters can be learned or tuned using one or more of the partition function bounding techniques described above.
The tuned or optimized parameters can be supplied by the machine learning system 602 to the prediction system 604. The prediction system 604 can receive a feature vector 612 derived from new input data 610. Using the parameters received from the machine learning system 602, the prediction system 604 can make a prediction about the feature vector 612 and produce an output 614. The output can include a likelihood, an expected label, a predicted result or the like.
FIG. 7 is a diagram of an example supervised machine learning environment 700. The environment 700 includes a machine learning system 702 and a prediction system 704.
In operation, the machine learning system 702 receives feature vectors 708 derived from input data (e.g., image data, audio data, text files, web pages or the like). As part of supervised learning, the machine learning system 702 can also receive information (e.g., labels 716) corresponding to the feature vectors 708. The machine learning system can determine an optimized parameter set based on the input feature vectors 708 and the labels 716. The parameters can be learned or tuned using one or more of the partition function bounding techniques described above.
The tuned or optimized parameters can be supplied by the machine learning system 702 to the prediction system 704. The prediction system 704 can receive a feature vector 712 derived from new input data 710. Using the parameters received from the machine learning system 602, the prediction system 604 can make a prediction about the feature vector 612 and produce an output 614. The output can include an expected label 714, for example.
Any system described above can include, but is not limited to, a single processor system, a multi-processor system (co-located or distributed), a cloud computing system, or a combination of the above.
Any client device described above can include, but is not limited to, a desktop computer, a laptop computer, a portable computer, a tablet computing device, a smartphone, a feature phone, a personal digital assistant, a media player, an electronic book reader, an entertainment system of a vehicle or the like.
Networks described herein can be wired or wireless networks, and can include, but are not limited to, WiFi networks, local area networks, wide area networks, the Internet, or a combination of the above.
Data storage, memory and/or computer readable media can include a nontransitory storage device such as a magnetic storage device (hard disk drive or the like), optical storage device (CD, DVD or the like), electronic storage device (RAM, ROM, flash, or the like). The software instructions can also be contained in, and provided as, an electronic signal.
Moreover, embodiments of the disclosed method, system, and computer readable media can be implemented in software executed on a programmed general purpose computer, a special purpose computer, a microprocessor, or the like.
It is, therefore, apparent that there is provided in accordance with the presently disclosed subject matter, a method, system, a computer program product and a computer readable media with software for parameter optimization. While this disclosed subject matter has been described in conjunction with a number of embodiments, it is evident that many alternatives, modifications and variations would be or are apparent to those of ordinary skill in the applicable arts. Accordingly, applicants intend to embrace all such alternatives, modifications, equivalents and variations that are within the spirit and scope of the disclosed subject matter.
APPENDIX TO THE SPECIFICATION
Maximum Entropy Problem
Partition functions arise naturally in maximum entropy estimation or minimum relative entropy




  
    RE
    ⁡
    
      (
      
        p
        ∥
        h
      
      )
    
  
  =
  
    
      ∑
      y
    
    ⁢
    
      
        p
        ⁡
        
          (
          y
          )
        
      
      ⁢
      ln
      ⁢
      
        
      
      ⁢
      
        
          p
          ⁡
          
            (
            y
            )
          
        
        
          h
          ⁡
          
            (
            y
            )
          
        
      
    
  




estimation as follows

minRE(p∥h)s.t.Σyp(y)ƒ(y)=0, Σyp(y)g(y)≧0.

Therein, yεΩ, ƒ:Ωd and g:Ωd′ are arbitrary (non-constant) vector-valued functions over the sample space. The solution distribution p(y)=h(y)exp(θTƒ(y)+θTg(y))/Z(θ, θ) is recovered by the dual optimization





  θ
  ,
  
    θ
    =
    
      
        
          max
          arg
        
        
          
            θ
            ≥
            0
          
          ,
          θ
        
      
      ⁢
      
        
          -
          ln
        
        ⁢
        
          
            ∑
            y
          
          ⁢
          
            
              h
              ⁡
              
                (
                y
                )
              
            
            ⁢
            
              exp
              ⁡
              
                (
                
                  
                    
                      θ
                      T
                    
                    ⁢
                    
                      f
                      ⁡
                      
                        (
                        y
                        )
                      
                    
                  
                  +
                  
                    
                      θ
                      T
                    
                    ⁢
                    
                      g
                      ⁡
                      
                        (
                        y
                        )
                      
                    
                  
                
                )
              
            
          
        
      
    
  




where θεd and θεd′. These are obtained by minimizing Z(θ, θ) or equivalently by maximizing its negative logarithm. Algorithm 1 permits variational maximization of the dual via the quadratic program





  
    
      min
      
        
          θ
          ≥
          0
        
        ,
        θ
      
    
    ⁢
    
      
        1
        2
      
      ⁢
      
        
          (
          
            β
            -
            
              β
              ~
            
          
          )
        
        T
      
      ⁢
      
        ∑
        
          (
          
            β
            -
            
              β
              ~
            
          
          )
        
      
    
  
  +
  
    
      β
      T
    
    ⁢
    μ
  




where βT=[θTθT]. Note that any general convex hull of constraints βεΛ⊂d+d′ could be imposed without loss of generality.

Proof 1
Rewrite the partition function as a sum over the integer index j=1, . . . , n under the random ordering π:Ω{1, . . . , n}. This defines j=π(y) and associates h and ƒ with hj=h(π−1(j)) and ƒj=ƒ(π−1(j)). Next, write Z(θ)=Σj=1nαjexp(λTƒj) by introducing λ=θ−{tilde over (θ)} and αj=hjexp(θTƒj). Define the partition function over only the first i components as Zi(θ)=Σj=1iαjexp(λTƒj). When i=0, a trivial quadratic upper bound holds

Z0(θ)≦z0exp(1⁄2λTΣ0λ+λTμ0)

with the parameters z0→0+, μ0=0, and Σ0=z0I. Next, add one term to the current partition function Z1(θ)=Z0(θ)+α1exp(λTƒ1). Apply the current bound Z0(θ) to obtain

Z1(θ)≦z0exp(1⁄2λTΣ0λ+λTμ0)+α1exp(λTƒ1).

Consider the following change of variables





  
    
      
        u
        =
        
          
            
              ∑
              0
              
                1
                /
                2
              
            
            ⁢
            λ
          
          -
          
            
              ∑
              0
              
                
                  -
                  1
                
                /
                2
              
            
            ⁢
            
              (
              
                
                  f
                  1
                
                -
                
                  μ
                  0
                
              
              )
            
          
        
      
      )
    
    ⁢
    γ
  
  =
  
    
      
        α
        1
      
      
        z
        0
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            1
            2
          
          ⁢
          
            
              (
              
                
                  f
                  1
                
                -
                
                  μ
                  0
                
              
              )
            
            T
          
          ⁢
          
            
              ∑
              0
              
                -
                1
              
            
            ⁢
            
              (
              
                
                  f
                  1
                
                -
                
                  μ
                  0
                
              
              )
            
          
        
        )
      
    
  




and rewrite the logarithm of the bound as

ln Z1(θ)≦ln z0−1⁄2(ƒ1−μ0)TΣ0−1(ƒ1−μ0)+λTƒ1+ln(exp(1⁄2∥u∥2)+γ).

Apply the technique described in (T. Jebara, “Multitask sparsity via maximum entropy discrimination,” JMLR, 12:75-110, 2011) to the last term to get





  
    ln
    ⁢
    
      
    
    ⁢
    
      
        Z
        1
      
      ⁡
      
        (
        θ
        )
      
    
  
  ≤
  
    
      ln
      ⁢
      
        
      
      ⁢
      
        z
        0
      
    
    -
    
      
        1
        2
      
      ⁢
      
        
          (
          
            
              f
              1
            
            -
            
              μ
              0
            
          
          )
        
        T
      
      ⁢
      
        
          ∑
          0
          
            -
            1
          
        
        ⁢
        
          (
          
            
              f
              1
            
            -
            
              μ
              0
            
          
          )
        
      
    
    +
    
      
        λ
        T
      
      ⁢
      
        f
        1
      
    
    +
    
      ln
      ⁡
      
        (
        
          
            exp
            ⁡
            
              (
              
                
                  1
                  2
                
                ⁢
                
                  
                    
                    v
                    
                  
                  2
                
              
              )
            
          
          +
          γ
        
        )
      
    
    +
    
      
        
          v
          T
        
        ⁡
        
          (
          
            u
            -
            v
          
          )
        
      
      
        1
        +
        
          γexp
          ⁡
          
            (
            
              
                -
                
                  1
                  2
                
              
              ⁢
              
                
                  
                  v
                  
                
                2
              
            
            )
          
        
      
    
    +
    
      
        1
        2
      
      ⁢
      
        
          (
          
            u
            -
            v
          
          )
        
        T
      
      ⁢
      
        (
        
          I
          +
          
            Γ
            ⁢
            
              
            
            ⁢
            
              vv
              T
            
          
        
        )
      
      ⁢
      
        
          (
          
            u
            -
            v
          
          )
        
        .
      
    
  




Note that





  Γ
  =
  
    
      
        tanh
        ⁡
        
          (
          
            
              1
              2
            
            ⁢
            
              ln
              ⁡
              
                (
                
                  γ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    exp
                    ⁡
                    
                      (
                      
                        
                          -
                          
                            1
                            2
                          
                        
                        ⁢
                        
                          
                            
                            v
                            
                          
                          2
                        
                      
                      )
                    
                  
                
                )
              
            
          
          )
        
      
      
        2
        ⁢
        
          ln
          ⁡
          
            (
            
              γexp
              ⁡
              
                (
                
                  
                    -
                    
                      1
                      2
                    
                  
                  ⁢
                  
                    
                      
                      v
                      
                    
                    2
                  
                
                )
              
            
            )
          
        
      
    
    .
  




The bound is tight when u=v. To achieve tightness when θ={tilde over (θ)} or, equivalently, λ=0, choose v=E0−1/2(μ0−ƒ1) yielding

Z1(θ)≦z1exp(1⁄2λTΣ1λ+λTμ1)

where we have





  
    z
    1
  
  =
  
    
      
        z
        0
      
      +
      
        
          α
          1
        
        ⁢
        
          μ
          1
        
      
    
    =
    
      
        
          
            
              z
              0
            
            
              
                z
                0
              
              +
              
                α
                1
              
            
          
          ⁢
          
            μ
            0
          
        
        +
        
          
            
              α
              1
            
            
              
                z
                0
              
              +
              
                α
                1
              
            
          
          ⁢
          
            f
            1
          
          ⁢
          
            ∑
            1
          
        
      
      =
      
        
          ∑
          0
        
        ⁢
        
          
            +
            
              
                tanh
                ⁡
                
                  (
                  
                    
                      1
                      2
                    
                    ⁢
                    
                      ln
                      ⁡
                      
                        (
                        
                          
                            α
                            1
                          
                          /
                          
                            z
                            0
                          
                        
                        )
                      
                    
                  
                  )
                
              
              
                2
                ⁢
                
                  ln
                  ⁡
                  
                    (
                    
                      
                        α
                        1
                      
                      /
                      
                        z
                        0
                      
                    
                    )
                  
                
              
            
          
          ⁢
          
            (
            
              
                μ
                0
              
              -
              
                f
                1
              
            
            )
          
          ⁢
          
            
              
                (
                
                  
                    μ
                    0
                  
                  -
                  
                    f
                    1
                  
                
                )
              
              T
            
            .
          
        
      
    
  




This rule updates the bound parameters z0, μ0, Σ0 to incorporate an extra term in the sum over i in Z(θ). The process is iterated n times (replacing 1 with i and 0 with i−1) to produce an overall bound on all terms.

Proof 2
Begin by upper-bounding (in the Loewner ordering sense) the matrices Σj in Algorithm 3. Since ∥ƒxj(y)∥2≦r for all yεΩj and since μj in Algorithm 1 is a convex combination of ƒxj(y), the outer-product terms in the update for Σj satisfy

(ƒxj(y)−μ)(ƒxj(y)−μ)T°4rI. 

Thus, ΣjoF(α1, . . . , αn)4rI holds where





  
    F
    ⁡
    
      (
      
        
          α
          1
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          α
          n
        
      
      )
    
  
  =
  
    
      ∑
      
        i
        =
        2
      
      n
    
    ⁢
    
      
        tanh
        ⁡
        
          (
          
            
              1
              2
            
            ⁢
            
              ln
              ⁡
              
                (
                
                  
                    α
                    i
                  
                  
                    
                      ∑
                      
                        k
                        =
                        1
                      
                      
                        i
                        -
                        1
                      
                    
                    ⁢
                    
                      α
                      k
                    
                  
                
                )
              
            
          
          )
        
      
      
        2
        ⁢
        
          ln
          ⁡
          
            (
            
              
                α
                i
              
              
                
                  ∑
                  
                    k
                    =
                    1
                  
                  
                    i
                    -
                    1
                  
                
                ⁢
                
                  α
                  k
                
              
            
            )
          
        
      
    
  




using the definition of α1, . . . , αn in the proof of Theorem 1. The formula for F starts at i=2 since z0→0+. Assume permutation π is sampled uniformly at random. The expected value of F is then





  
    
      E
      π
    
    ⁡
    
      [
      
        F
        ⁡
        
          (
          
            
              α
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              α
              n
            
          
          )
        
      
      ]
    
  
  =
  
    
      1
      
        n
        !
      
    
    ⁢
    
      
        ∑
        π
      
      ⁢
      
        
          ∑
          
            i
            =
            2
          
          n
        
        ⁢
        
          
            
              tanh
              ⁡
              
                (
                
                  
                    1
                    2
                  
                  ⁢
                  
                    ln
                    ⁡
                    
                      (
                      
                        
                          α
                          
                            π
                            ⁡
                            
                              (
                              i
                              )
                            
                          
                        
                        
                          
                            ∑
                            
                              k
                              =
                              1
                            
                            
                              i
                              -
                              1
                            
                          
                          ⁢
                          
                            α
                            
                              π
                              ⁡
                              
                                (
                                k
                                )
                              
                            
                          
                        
                      
                      )
                    
                  
                
                )
              
            
            
              2
              ⁢
              
                ln
                ⁡
                
                  (
                  
                    
                      α
                      
                        π
                        ⁡
                        
                          (
                          i
                          )
                        
                      
                    
                    
                      
                        ∑
                        
                          k
                          =
                          1
                        
                        
                          i
                          -
                          1
                        
                      
                      ⁢
                      
                        α
                        
                          π
                          ⁡
                          
                            (
                            k
                            )
                          
                        
                      
                    
                  
                  )
                
              
            
          
          .
        
      
    
  




We claim that the expectation is maximized when all αi=1 or any positive constant. Also, F is invariant under uniform scaling of its arguments. Write the expected value of F as E for short. Next, consider





  
    ∂
    E
  
  
    ∂
    
      α
      l
    
  




at the setting αi=1, ∀i. Due to the expectation over π, we have





  
    
      ∂
      E
    
    
      ∂
      
        α
        l
      
    
  
  =
  
    
      ∂
      E
    
    
      ∂
      
        α
        o
      
    
  




for any l, o. Therefore, the gradient vector is constant when all αi=1. Since F(α1, . . . , αn) is invariant to scaling, the gradient vector must therefore be the all zeros vector. Thus, the point when all αi=1 is an extremum or a saddle. Next, consider





  
    ∂
    
      ∂
      
        α
        o
      
    
  
  ⁢
  
    
      ∂
      E
    
    
      ∂
      
        α
        l
      
    
  




for any l, o. At the setting





  
    
      α
      i
    
    =
    1
  
  ,
  
    
      
        
          ∂
          2
        
        ⁢
        E
      
      
        ∂
        
          α
          l
          2
        
      
    
    =
    
      
        -
        
          c
          ⁡
          
            (
            n
            )
          
        
      
      ⁢
      
        
      
      ⁢
      and
    
  
  ,
  
    
      
        ∂
        
          ∂
          
            α
            o
          
        
      
      ⁢
      
        
          ∂
          E
        
        
          ∂
          
            α
            l
          
        
      
    
    =
    
      
        c
        ⁡
        
          (
          n
          )
        
      
      /
      
        (
        
          n
          -
          1
        
        )
      
    
  




for some non-negative constant function c(n). Thus, the αi=1 extremum is locally concave and is a maximum. This establishes that Eπ[F(α1, . . . , αn)]≦Eπ[F(1, . . . , 1)] and yields the Loewner bound





  
    
      ∑
      j
      o
    
    ⁢
    
      
        (
        
          2
          ⁢
          r
          ⁢
          
            
              ∑
              
                i
                =
                1
              
              
                n
                -
                1
              
            
            ⁢
            
              
                tanh
                ⁡
                
                  (
                  
                    
                      ln
                      ⁡
                      
                        (
                        i
                        )
                      
                    
                    /
                    2
                  
                  )
                
              
              
                ln
                ⁡
                
                  (
                  i
                  )
                
              
            
          
        
        )
      
      ⁢
      I
    
  
  =
  
    ω
    ⁢
    
      
    
    ⁢
    
      I
      .
    
  




Apply this bound to each Σj in the lower bound on J(θ) and also note a corresponding upper bound





  
    J
    ⁡
    
      (
      θ
      )
    
  
  ≥
  
    
      J
      ⁡
      
        (
        
          θ
          ~
        
        )
      
    
    -
    
      
        
          
            t
            ⁢
            
              
            
            ⁢
            ω
          
          +
          
            t
            ⁢
            
              
            
            ⁢
            λ
          
        
        2
      
      ⁢
      
        
          
          
            θ
            -
            
              θ
              ~
            
          
          
        
        2
      
    
    -
    
      
        ∑
        j
      
      ⁢
      
        
          
            (
            
              θ
              -
              
                θ
                ~
              
            
            )
          
          T
        
        ⁢
        
          (
          
            
              μ
              j
            
            -
            
              
                f
                
                  x
                  j
                
              
              ⁡
              
                (
                
                  y
                  j
                
                )
              
            
          
          )
        
        ⁢
        
          J
          ⁡
          
            (
            θ
            )
          
        
      
    
  
  ≤
  
    
  
  ⁢
  
    
      J
      ⁡
      
        (
        
          θ
          ~
        
        )
      
    
    -
    
      
        
          t
          ⁢
          
            
          
          ⁢
          λ
        
        2
      
      ⁢
      
        
          
          
            θ
            -
            
              θ
              ~
            
          
          
        
        2
      
    
    -
    
      
        ∑
        j
      
      ⁢
      
        
          
            (
            
              θ
              -
              
                θ
                ~
              
            
            )
          
          T
        
        ⁢
        
          (
          
            
              μ
              j
            
            -
            
              
                f
                
                  x
                  j
                
              
              ⁢
              
                (
                
                  y
                  j
                
                )
              
            
          
          )
        
      
    
  




which follows from Jensen's inequality. Define the current {tilde over (θ)} at time τ as θτ, and denote by Lτ(θ) the above lower bound and by Uτ(θ) the above upper bound at time τ. Clearly, Lτ(θ)≦J(θ)≦Uτ(θ) with equality when θ=θτ. Algorithm 3 maximizes J(θ) after initializing at θ0 and performing an update by maximizing a lower bound based on Σj. Since Lτ(θ) replaces the definition of Σj with ωI±Σj, Lτ(θ) is a looser bound than the one used by Algorithm 3. Thus, performing θτ+1=arg maxθεΛLτ(θ) makes less progress than a step of Algorithm 1. Consider computing the slower update at each iteration τ and returning θτ+1=arg maxθεΛLτ(θ). Setting Φ=(tω+tλ)I, Ψ=tλI and





  κ
  =
  
    
      ω
      +
      λ
    
    λ
  




allows us to apply Theorem 3 as follows





  
    
      
        sup
        
          θ
          ∈
          Λ
        
      
      ⁢
      
        
          L
          τ
        
        ⁡
        
          (
          θ
          )
        
      
    
    -
    
      
        L
        τ
      
      ⁡
      
        (
        
          θ
          τ
        
        )
      
    
  
  =
  
    
      
        1
        κ
      
      ⁢
      
        sup
        
          θ
          ∈
          Λ
        
      
      ⁢
      
        
          U
          τ
        
        ⁡
        
          (
          θ
          )
        
      
    
    -
    
      
        
          U
          τ
        
        ⁡
        
          (
          
            θ
            τ
          
          )
        
      
      .
    
  




Since Lτ(θτ)=J(θτ)=Uτ(θτ), J(θτ+1)≧supθεΛLτ(θ) and supθεΛUτ(θ)≧J(θ*), we obtain





  
    
      J
      ⁡
      
        (
        
          θ
          
            τ
            +
            1
          
        
        )
      
    
    -
    
      J
      ⁡
      
        (
        
          θ
          *
        
        )
      
    
  
  ≥
  
    
      (
      
        1
        -
        
          1
          κ
        
      
      )
    
    ⁢
    
      
        (
        
          
            J
            ⁡
            
              (
              
                θ
                τ
              
              )
            
          
          -
          
            J
            ⁡
            
              (
              
                θ
                *
              
              )
            
          
        
        )
      
      .
    
  




Iterate the above inequality starting at t=0 to obtain





  
    
      J
      ⁡
      
        (
        
          θ
          τ
        
        )
      
    
    -
    
      J
      ⁡
      
        (
        
          θ
          *
        
        )
      
    
  
  ≥
  
    
      
        (
        
          1
          -
          
            1
            κ
          
        
        )
      
      τ
    
    ⁢
    
      
        (
        
          
            J
            ⁡
            
              (
              
                θ
                0
              
              )
            
          
          -
          
            J
            ⁡
            
              (
              
                θ
                *
              
              )
            
          
        
        )
      
      .
    
  




A solution within a multiplicative factor of ε implies that





  ɛ
  =
  
    
      
        
          (
          
            1
            -
            
              1
              κ
            
          
          )
        
        τ
      
      ⁢
      or
      ⁢
      
        
      
      ⁢
      
        ln
        ⁡
        
          (
          
            1
            /
            ɛ
          
          )
        
      
    
    =
    
      τ
      ⁢
      
        
      
      ⁢
      ln
      ⁢
      
        
          κ
          
            κ
            -
            1
          
        
        .
      
    
  




Inserting the definition for κ shows that the number of iterations τ is at most





  
    ⌈
    
      
        ln
        ⁡
        
          (
          
            1
            /
            ɛ
          
          )
        
      
      
        ln
        ⁢
        
          κ
          
            κ
            -
            1
          
        
      
    
    ⌉
  
  ⁢
  
    
  
  ⁢
  or
  ⁢
  
    
  
  ⁢
  
    
      ⌈
      
        
          ln
          ⁡
          
            (
            
              1
              /
              ɛ
            
            )
          
        
        
          ln
          ⁡
          
            (
            
              1
              +
              
                λ
                /
                ω
              
            
            )
          
        
      
      ⌉
    
    .
  




Inserting the definition for ω gives the bound.

Theorem 3

If κΨ±Φ>0 for Φ, Ψεd×d, then

L(θ)=−1⁄2(θ−{tilde over (θ)})TΦ(θ−{tilde over (θ)})−(θ−{tilde over (θ)})TμU(θ)=−1⁄2(θ−{tilde over (θ)})TΨ(θ−{tilde over (θ)})−(θ−{tilde over (θ)})Tμ

satisfy





  
    
      sup
      
        θ
        ∈
        Λ
      
    
    ⁢
    
      L
      ⁡
      
        (
        θ
        )
      
    
  
  ≥
  
    
      1
      κ
    
    ⁢
    
      sup
      
        θ
        ∈
        Λ
      
    
    ⁢
    
      U
      ⁡
      
        (
        θ
        )
      
    
  




for any convex Λ⊂d, {tilde over (θ)}εΛ, μεd and κε+.

Proof 3
Define the primal problems of interest as PL=supθεΛL(θ) and PU=supθεΛU(θ). The constraints θεΛ can be summarized by a set of linear inequalities Aθ≦b where Aεkd and bεk for some (possibly infinite) kε. Apply the change of variables z=θ−{tilde over (θ)}. The constraint A(z+{tilde over (θ)})≦b simplifies into Az≦b where b=b−A{tilde over (θ)}. Since {tilde over (θ)}εΛ, it is easy to show that b≧0. We obtain the equivalent primal problems PL=supAz≦b−1⁄2zTΦz−zTμ and PU=supAz≦b−1⁄2zTΨz−zTμ. The corresponding dual problems are




  
    
      
        
          D
          L
        
        =
        
        ⁢
        
          
            
              inf
              
                y
                ≥
                0
              
            
            ⁢
            
              
                
                  y
                  T
                
                ⁢
                A
                ⁢
                
                  
                
                ⁢
                
                  Φ
                  
                    -
                    1
                  
                
                ⁢
                
                  A
                  T
                
                ⁢
                y
              
              2
            
          
          +
          
            
              y
              T
            
            ⁢
            A
            ⁢
            
              
            
            ⁢
            
              Φ
              
                -
                1
              
            
            ⁢
            μ
          
          +
          
            
              y
              T
            
            ⁢
            b
          
          +
          
            
              
                μ
                T
              
              ⁢
              
                Φ
                
                  -
                  1
                
              
              ⁢
              μ
            
            2
          
        
      
    
  
  
    
      
        
          D
          U
        
        =
        
        ⁢
        
          
            
              inf
              
                y
                ≥
                0
              
            
            ⁢
            
              
                
                  y
                  T
                
                ⁢
                A
                ⁢
                
                  
                
                ⁢
                
                  Ψ
                  
                    -
                    1
                  
                
                ⁢
                
                  A
                  T
                
                ⁢
                y
              
              2
            
          
          +
          
            
              y
              T
            
            ⁢
            A
            ⁢
            
              
            
            ⁢
            
              Ψ
              
                -
                1
              
            
            ⁢
            μ
          
          +
          
            
              y
              T
            
            ⁢
            b
          
          +
          
            
              
                
                  μ
                  T
                
                ⁢
                
                  Ψ
                  
                    -
                    1
                  
                
                ⁢
                μ
              
              2
            
            .
          
        
      
    
  




Due to strong duality, PL=DL and PU=DU. Apply the inequalities Φ°κΨ and yTb>0 as





  
    
      P
      L
    
    ≥
    
      
        sup
        
          Az
          ≤
          b
        
      
      -
      
        
          κ
          2
        
        ⁢
        
          z
          T
        
        ⁢
        Ψ
        ⁢
        
          
        
        ⁢
        z
      
      -
      
        
          z
          T
        
        ⁢
        μ
      
    
  
  =
  
    
      
        
          
            inf
            
              y
              ≥
              0
            
          
          ⁢
          
            
              
                y
                T
              
              ⁢
              A
              ⁢
              
                
              
              ⁢
              
                Ψ
                
                  -
                  1
                
              
              ⁢
              
                A
                T
              
              ⁢
              y
            
            
              2
              ⁢
              κ
            
          
        
        +
        
          
            
              y
              T
            
            ⁢
            A
            ⁢
            
              
            
            ⁢
            
              Ψ
              
                -
                1
              
            
            ⁢
            μ
          
          κ
        
        +
        
          y
          ⁢
          
            
          
          ⁢
          
            
               
              T
            
            ⁢
            b
          
        
        +
        
          
            
              μ
              T
            
            ⁢
            
              Ψ
              
                -
                1
              
            
            ⁢
            μ
          
          
            2
            ⁢
            κ
          
        
      
      ≥
      
        
          1
          κ
        
        ⁢
        
          D
          U
        
      
    
    =
    
      
        1
        κ
      
      ⁢
      
        
          P
          U
        
        .
      
    
  




This proves that





  
    P
    L
  
  ≥
  
    
      1
      κ
    
    ⁢
    
      
        P
        U
      
      .
    
  




Theorem 4

For all uεd, ln




  
    (
    
      
        exp
        (
        
          
            1
            2
          
          ⁢
          
            
              
              u
              
            
            2
          
        
        )
      
      +
      γ
    
    )
  
  ≤
  
    
      ln
      (
      
        
          exp
          (
          
            
              1
              2
            
            ⁢
            
              
                
                v
                
              
              2
            
          
          )
        
        +
        γ
      
      )
    
    +
    
      
        
          v
          T
        
        ⁡
        
          (
          
            u
            -
            v
          
          )
        
      
      
        1
        +
        
          γ
          ⁢
          
            
          
          ⁢
          
            exp
            (
            
              
                -
                
                  1
                  2
                
              
              ⁢
              
                
                  
                  v
                  
                
                2
              
            
            )
          
        
      
    
    +
    
      
        1
        2
      
      ⁢
      
        
          (
          
            u
            -
            v
          
          )
        
        T
      
      ⁢
      
        (
        
          I
          +
          
            Γ
            ⁢
            
              
            
            ⁢
            
              vv
              T
            
          
        
        )
      
      ⁢
      
        (
        
          u
          -
          v
        
        )
      
    
  




when the scalar term





  Γ
  =
  
    
      
        tanh
        (
        
          
            1
            2
          
          ⁢
          
            ln
            ⁡
            
              (
              
                γ
                ⁢
                
                  
                
                ⁢
                
                  exp
                  ⁡
                  
                    (
                    
                      
                        -
                        
                          
                            
                            v
                            
                          
                          2
                        
                      
                      /
                      2
                    
                    )
                  
                
              
              )
            
          
        
        )
      
      
        2
        ⁢
        
          ln
          ⁡
          
            (
            
              γ
              ⁢
              
                
              
              ⁢
              
                exp
                ⁡
                
                  (
                  
                    
                      -
                      
                        
                          
                          v
                          
                        
                        2
                      
                    
                    /
                    2
                  
                  )
                
              
            
            )
          
        
      
    
    .
  




The bound holds for any γ≧0 and vεd. Strict equality is achieved when u=v.











Algorithm 5















 Input {tilde over (θ)}, h12,0, f12,0 and zc1,1, Σc1,1, μc1,1 ∀c1,1 = 1, . . . , m1,1


 Init z → 0+, μ = 0, Σ = zI


For each configuration Y120 {


 α =h12,0 (Πc1,1=1m1,1zc1,1 exp(−{tilde over (θ)}T μc1,1))(−{tilde over (θ)}T (f12,0 + Σc1,1=1m1,1 μc1,1)) 


 


   



  =
  
    
      h
      1
      
        2
        ,
        0
      
    
    ⁢
    
      exp
      ⁡
      
        (
        
          
            
              θ
              ~
            
            T
          
          ⁢
          
            f
            1
            
              2
              ,
              0
            
          
        
        )
      
    
    ⁢
    
      
        ∏
        
          
            c
            
              1
              ,
              1
            
          
          =
          1
        
        
          m
          
            1
            ,
            1
          
        
      
      ⁢
      
        
      
      ⁢
      
        z
        
          c
          
            1
            ,
            1
          
        
      
    
  






 


 l =f12,0 + Σc1,1=1m1,1 μc1,1 − μ


 


  



  ∑
  
    +=
    
      
        ∑
        
          
            c
            
              1
              ,
              1
            
          
          =
          1
        
        
          m
          
            1
            ,
            1
          
        
      
      ⁢
      
        
          ∑
          
            c
            
              1
              ,
              1
            
          
        
        ⁢
        
          
            +
            
              
                tanh
                ⁡
                
                  (
                  
                    
                      1
                      2
                    
                    ⁢
                    
                      (
                      
                        α
                        /
                        z
                      
                      )
                    
                  
                  )
                
              
              
                2
                ⁢
                
                  ln
                  ⁡
                  
                    (
                    
                      α
                      /
                      z
                    
                    )
                  
                
              
            
          
          ⁢
          
            ll
            T
          
        
      
    
  






 


 



  μ
  +=
  
    
      α
      
        z
        +
        α
      
    
    ⁢
    l
  






 


 z += α  }


Output z, μ, Σ









Proof of Correctness of Algorithm 3
Consider a simple junction tree of depth 2 (see, e.g., FIG. 8). The notation Yca,b refers to the cth tree node located on depth a, which has a parent b (for the root b=0). Note we assume the depth level of the tree increases moving from the leaves to the root.




  ∑
  
    Y
    
      c
      1
    
    
      
        a
        1
      
      ,
      
        b
        1
      
    
  




refers to the sum over all configurations of variables in





  
    Y
    
      c
      1
    
    
      
        a
        1
      
      ,
      
        b
        1
      
    
  
  ⁢
  
    
  
  ⁢
  and
  ⁢
  
    
  
  ⁢
  
    ∑
    
      
        Y
        
          c
          1
        
        
          
            a
            1
          
          ,
          
            b
            1
          
        
      
      ∖
      
        Y
        
          c
          2
        
        
          
            a
            2
          
          ,
          
            b
            2
          
        
      
    
  




refers to the sum over all configurations of variables that are in Yc1a1,b1 but not in Yc2a2,b2. The notation seems to be too complex for such small tree, but is should be clear that it can be directly applied to larger trees therefore we will further use it. To simplify the notation a little let: hc1a1,b1=hc1a1,b1(Yc1a1,b1), ƒc1a1,b1=ƒc1a1,b1(Yc1a1,b1) and ψc1a1,b1=ψc1a1,b1(Yc1a1,b1)=hc1a1,b1(Yc1a1,b1)exp(θTƒc1a1,b1(Yc1a1,b1)). The partition function can be expressed as:





  
    Z
    ⁡
    
      (
      θ
      )
    
  
  =
  
    
      
        ∑
        
          Y
          1
          
            2
            ,
            0
          
        
      
      ⁢
      
        
      
      ⁢
      
        [
        
          
            ψ
            1
            
              2
              ,
              0
            
          
          ⁢
          
            
              Π
              
                
                  c
                  
                    1
                    ,
                    1
                  
                
                =
                1
              
              
                m
                
                  1
                  ,
                  1
                
              
            
            (
            
              
                ∑
                
                  
                    Y
                    
                      c
                      
                        1
                        ,
                        1
                      
                    
                    
                      1
                      ,
                      1
                    
                  
                  ∖
                  
                    Y
                    1
                    
                      2
                      ,
                      0
                    
                  
                
              
              ⁢
              
                
              
              ⁢
              
                ψ
                
                  c
                  
                    1
                    ,
                    1
                  
                
                
                  1
                  ,
                  1
                
              
            
            )
          
        
        ]
      
    
    ≤
    
       
      
        
          
            ∑
            
              Y
              1
              
                2
                ,
                0
              
            
          
          ⁢
          
            
          
          ⁢
          
            [
            
              
                ψ
                1
                
                  2
                  ,
                  0
                
              
              ⁢
              
                Π
                
                  
                    c
                    
                      1
                      ,
                      1
                    
                  
                  =
                  1
                
                
                  m
                  
                    1
                    ,
                    1
                  
                
              
              ⁢
              
                z
                
                  c
                  
                    1
                    ,
                    1
                  
                
              
              ⁢
              
                exp
                (
                
                  
                    
                      1
                      2
                    
                    ⁢
                    
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                      T
                    
                    ⁢
                    
                      
                        ∑
                        
                          c
                          
                            1
                            ,
                            1
                          
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                    
                  
                  +
                  
                    
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                      T
                    
                    ⁢
                    
                      μ
                      
                        c
                        
                          1
                          ,
                          1
                        
                      
                    
                  
                
                )
              
            
            ]
          
        
        =
        
          
            ∑
            
              Y
              1
              
                2
                ,
                0
              
            
          
          ⁢
          
            [
            
              
                h
                1
                
                  2
                  ,
                  0
                
              
              ⁢
              
                exp
                ⁡
                
                  (
                  
                    
                      θ
                      T
                    
                    ⁢
                    
                      f
                      1
                      
                        2
                        ,
                        0
                      
                    
                  
                  )
                
              
              ⁢
              
                Π
                
                  
                    c
                    
                      1
                      ,
                      1
                    
                  
                  =
                  1
                
                
                  m
                  
                    1
                    ,
                    1
                  
                
              
              ⁢
              
                z
                
                  c
                  
                    1
                    ,
                    1
                  
                
              
              ⁢
              
                exp
                (
                
                  
                    
                      1
                      2
                    
                    ⁢
                    
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                      T
                    
                    ⁢
                    
                      
                        ∑
                        
                          c
                          
                            1
                            ,
                            1
                          
                        
                      
                      ⁢
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                    
                  
                  +
                  
                    
                      
                        (
                        
                          θ
                          -
                          
                            θ
                            ~
                          
                        
                        )
                      
                      T
                    
                    ⁢
                    
                      μ
                      
                        c
                        
                          1
                          ,
                          1
                        
                      
                    
                  
                
                )
              
            
            ]
          
        
      
    
  




where the upperbound comes from applying Theorem 1 to each of the terms:





  
    ∑
    
      
        Y
        
          c
          
            1
            ,
            1
          
        
        
          1
          ,
          1
        
      
      ∖
      
        Y
        1
        
          2
          ,
          0
        
      
    
  
  ⁢
  
    
  
  ⁢
  
    
      ψ
      
        c
        
          1
          ,
          1
        
      
      
        1
        ,
        1
      
    
    .
  




To explain the notation that will be further used, ma,b denotes the number of children of bth node situated on depth a+1.

Finally, by simply rearranging terms we get:




  
    Z
    ⁡
    
      (
      θ
      )
    
  
  ≤
  
    
      ∑
      
        Y
        1
        
          2
          ,
          0
        
      
    
    ⁢
    
      [
      
        
          
            
              
                
                  
                    
                      h
                      1
                      
                        2
                        ,
                        0
                      
                    
                    ⁡
                    
                      (
                      
                        
                          ∏
                          
                            
                              c
                              
                                1
                                ,
                                1
                              
                            
                            =
                            1
                          
                          
                            m
                            
                              1
                              ,
                              1
                            
                          
                        
                        ⁢
                        
                          
                            z
                            
                              c
                              
                                1
                                ,
                                1
                              
                            
                          
                          ⁢
                          
                            exp
                            ⁡
                            
                              (
                              
                                
                                  -
                                  
                                    
                                      θ
                                      ~
                                    
                                    T
                                  
                                
                                ⁢
                                
                                  μ
                                  
                                    c
                                    
                                      1
                                      ,
                                      1
                                    
                                  
                                
                              
                              )
                            
                          
                        
                      
                      )
                    
                  
                
              
              
                
                  
                    exp
                    ⁡
                    
                      (
                      
                        
                          θ
                          T
                        
                        ⁡
                        
                          (
                          
                            
                              f
                              1
                              
                                2
                                ,
                                0
                              
                            
                            +
                            
                              
                                ∑
                                
                                  
                                    c
                                    
                                      1
                                      ,
                                      1
                                    
                                  
                                  =
                                  1
                                
                                
                                  m
                                  
                                    1
                                    ,
                                    1
                                  
                                
                              
                              ⁢
                              
                                μ
                                
                                  c
                                  
                                    1
                                    ,
                                    1
                                  
                                
                              
                            
                          
                          )
                        
                      
                      )
                    
                  
                
              
            
          
        
        
          
            
              exp
              (
              
                
                  1
                  2
                
                ⁢
                
                  
                    (
                    
                      θ
                      -
                      
                        θ
                        ~
                      
                    
                    )
                  
                  T
                
                ⁢
                
                  (
                  
                    
                      ∑
                      
                        
                          c
                          
                            1
                            ,
                            1
                          
                        
                        =
                        1
                      
                      
                        m
                        
                          1
                          ,
                          1
                        
                      
                    
                    ⁢
                    
                      ∑
                      
                        c
                        
                          1
                          ,
                          1
                        
                      
                    
                  
                  )
                
                ⁢
                
                  (
                  
                    θ
                    -
                    
                      θ
                      ~
                    
                  
                  )
                
              
            
          
        
      
      ]
    
  




One can prove that this expression can be upperbounded by the expression of the form: z exp(1⁄2(θ−{circumflex over (θ)})TΣ(θ−{circumflex over (θ)})+(θ−{circumflex over (θ)})Tμ) where z, Σ and μ can be computed using Algorithm 5 (notice it is nothing more than just Algorithm 3 for this simple junction tree that we consider). We will call this result Lemma 1. The proof is a mirror analogy of Proof 1 and so we do not provide it.

Consider enlarging the previously discussed example tree to a tree of depth 3 (See, e.g., FIG. 9). The partition function can now be expressed as:




  
    Z
    ⁡
    
      (
      θ
      )
    
  
  =
  
    
      ∑
      
        Y
        1
        
          3
          ,
          0
        
      
    
    ⁢
    
      
    
    ⁢
    
      [
      
        
          ψ
          1
          
            3
            ,
            0
          
        
        ⁢
        
          
            Π
            
              
                c
                
                  2
                  ,
                  1
                
              
              =
              1
            
            
              m
              
                2
                ,
                1
              
            
          
          (
          
            
              ∑
              
                
                  Y
                  
                    c
                    
                      2
                      ,
                      1
                    
                  
                  
                    2
                    ,
                    1
                  
                
                ∖
                
                  Y
                  1
                  
                    3
                    ,
                    0
                  
                
              
            
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  ψ
                  
                    c
                    
                      2
                      ,
                      1
                    
                  
                  
                    2
                    ,
                    1
                  
                
                ⁢
                
                  
                    Π
                    
                      
                        c
                        
                          1
                          ,
                          
                            c
                            
                              2
                              ,
                              1
                            
                          
                        
                      
                      =
                      1
                    
                    
                      m
                      
                        1
                        ,
                        
                          c
                          
                            2
                            ,
                            1
                          
                        
                      
                    
                  
                  (
                  
                    
                      ∑
                      
                        
                          Y
                          
                            c
                            
                              1
                              ,
                              
                                c
                                
                                  2
                                  ,
                                  1
                                
                              
                            
                          
                          
                            1
                            ,
                            
                              c
                              
                                2
                                ,
                                1
                              
                            
                          
                        
                        ∖
                        
                          Y
                          
                            c
                            
                              2
                              ,
                              1
                            
                          
                          
                            2
                            ,
                            1
                          
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      ψ
                      
                        c
                        
                          1
                          ,
                          
                            c
                            
                              2
                              ,
                              1
                            
                          
                        
                      
                      
                        1
                        ,
                        
                          c
                          
                            2
                            ,
                            1
                          
                        
                      
                    
                  
                  )
                
              
              )
            
          
          )
        
      
      ]
    
  




By Lemma 1 we can upper bound each of the terms of the form:





  
    ∑
    
      
        
          
            
              Y
              
                2
                ,
                1
              
            
          
        
        
          
            
              c
              
                2
                ,
                1
              
            
          
        
      
      ⁢
      \
      ⁢
      
        Y
        1
        
          3
          ,
          0
        
      
    
  
  ⁢
  
    (
    
      
        ψ
        
          c
          
            2
            ,
            1
          
        
        
          2
          ,
          1
        
      
      ⁢
      
        
          ∏
          
            
              c
              
                1
                ,
                
                  c
                  
                    2
                    ,
                    1
                  
                
              
            
            =
            1
          
          
            m
            
              1
              ,
              
                c
                
                  2
                  ,
                  1
                
              
            
          
        
        ⁢
        
          (
          
            
              ∑
              
                
                  
                    
                      
                        Y
                        
                          1
                          ,
                          
                            c
                            
                              2
                              ,
                              1
                            
                          
                        
                      
                    
                  
                  
                    
                      
                        c
                        
                          1
                          ,
                          
                            c
                            
                              2
                              ,
                              1
                            
                          
                        
                      
                    
                  
                
                ⁢
                \
                ⁢
                
                  Y
                  
                    c
                    
                      2
                      ,
                      1
                    
                  
                  
                    2
                    ,
                    1
                  
                
              
            
            ⁢
            
              ψ
              
                c
                
                  1
                  ,
                  
                    c
                    
                      2
                      ,
                      1
                    
                  
                
              
              
                1
                ,
                
                  c
                  
                    2
                    ,
                    1
                  
                
              
            
          
          )
        
      
    
    )
  




by the expressions of the form: zc2,1exp (1⁄2(θ−{circumflex over (θ)})TΣc2,1(θ−{circumflex over (θ)})+(θ−{circumflex over (θ)})Tμc2,1) yielding:

Z(θ)≦ΣY13,0[ψ13,0Πc2,1=1m2,1zc2,1exp(1⁄2(θ−{tilde over (θ)})TΣc2,1(θ−{tilde over (θ)})+(θ−{tilde over (θ)})Tμc2,1)]

This process can be viewed as collapsing the subtrees S12,1, S22,1, . . . , Sm2,12,1 to supernodes that are represented by bound parameters: zc2,1, Σc2,1 and μc2,1. Notice that the obtained expression can be further upper bounded using again Lemma 1 (induction) yielding the bound of the form: zexp(1⁄2(θ−{circumflex over (θ)})TΣ(θ−{circumflex over (θ)})+(θ−{circumflex over (θ)})Tμ). Also, notice this procedure yields nothing more than just Algorithm 5 for this junction tree that we consider.

The partition function of a general junction tree of depth p can be expressed as:




  
    Z
    ⁡
    
      (
      θ
      )
    
  
  =
  
    
      ∑
      
        Y
        1
        
          p
          ,
          0
        
      
    
    ⁢
    
      [
      
        
          ψ
          1
          
            p
            ,
            0
          
        
        ⁢
        
          
            ∏
            
              
                c
                
                  
                    p
                    -
                    1
                  
                  ,
                  1
                
              
              =
              1
            
            
              m
              
                
                  p
                  -
                  1
                
                ,
                1
              
            
          
          ⁢
          
            (
            
              
                
                  
                    
                      ∑
                      
                        
                          
                            
                              
                                Y
                                
                                  
                                    
                                  
                                  
                                    
                                      p
                                      -
                                      1
                                    
                                    ,
                                    1
                                  
                                
                              
                            
                          
                          
                            
                              
                                c
                                
                                  
                                    
                                  
                                  
                                    
                                      p
                                      -
                                      1
                                    
                                    ,
                                    1
                                  
                                
                              
                            
                          
                        
                        ⁢
                        \
                        ⁢
                        
                          Y
                          1
                          
                            p
                            ⁢
                            
                              
                            
                            ,
                            0
                          
                        
                      
                    
                    ⁢
                    
                      
                        ψ
                        
                          c
                          
                            
                              p
                              -
                              1
                            
                            ,
                            1
                          
                        
                        
                          
                            p
                            -
                            1
                          
                          ,
                          1
                        
                      
                      ⁢
                      
                        ∏
                        
                          c
                          
                            
                              p
                              -
                              2
                            
                            ,
                            
                              c
                              
                                
                                  p
                                  -
                                  1
                                
                                ,
                                1
                              
                            
                          
                        
                        
                          m
                          
                            
                              p
                              -
                              2
                            
                            ,
                            
                              c
                              
                                
                                  p
                                  -
                                  1
                                
                                ,
                                1
                              
                            
                          
                        
                      
                    
                  
                
              
              
                
                  
                    (
                    
                      
                        ∑
                        
                          
                            
                              
                                
                                  Y
                                  
                                    
                                      p
                                      -
                                      2
                                    
                                    ,
                                    
                                      c
                                      
                                        
                                          p
                                          -
                                          1
                                        
                                        ,
                                        1
                                      
                                    
                                  
                                
                              
                            
                            
                              
                                
                                  c
                                  
                                    
                                      p
                                      -
                                      2
                                    
                                    ,
                                    
                                      c
                                      
                                        
                                          p
                                          -
                                          1
                                        
                                        ,
                                        1
                                      
                                    
                                  
                                
                              
                            
                          
                          ⁢
                          \
                          ⁢
                          
                            Y
                            
                              c
                              
                                
                                  p
                                  -
                                  1
                                
                                ,
                                1
                              
                            
                            
                              
                                p
                                -
                                1
                              
                              ,
                              1
                            
                          
                        
                      
                      ⁢
                      
                        (
                        
                          
                            ψ
                            
                              c
                              
                                
                                  p
                                  -
                                  2
                                
                                ,
                                
                                  c
                                  
                                    
                                      p
                                      -
                                      1
                                    
                                    ,
                                    1
                                  
                                
                              
                            
                            
                              
                                p
                                -
                                2
                              
                              ,
                              
                                c
                                
                                  
                                    p
                                    -
                                    1
                                  
                                  ,
                                  1
                                
                              
                            
                          
                          ⁢
                          ...
                        
                        )
                      
                    
                    )
                  
                
              
            
            )
          
        
      
      ]
    
  




It should now be clear that for this ‘general’ tree, one can follow exactly the same steps as described before, start from leaves and collapse nodes to supernodes, each represented by bound parameters. It yields Algorithm 5. We do not provide a formal induction proof to avoid using complex notation.

Proof of Correctness of Algorithm 4
We begin by proving a theorem that will be useful later.
Theorem 5
For all xεd and for all lεd:




  
    
      ∑
      
        i
        =
        1
      
      d
    
    ⁢
    
      
        
          x
          ⁡
          
            (
            i
            )
          
        
        2
      
      ⁢
      
        
          l
          ⁡
          
            (
            i
            )
          
        
        2
      
    
  
  ≥
  
    
      (
      
        
          ∑
          
            i
            =
            1
          
          d
        
        ⁢
        
          
            x
            ⁡
            
              (
              i
              )
            
          
          ⁢
          
            
              
                l
                ⁡
                
                  (
                  i
                  )
                
              
              2
            
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  d
                
                ⁢
                
                  
                    l
                    ⁡
                    
                      (
                      j
                      )
                    
                  
                  2
                
              
            
          
        
      
      )
    
    2
  




Proof 5
By Jensen's inequality:




  
    
      
        ∑
        
          i
          =
          1
        
        d
      
      ⁢
      
        
          
            x
            ⁡
            
              (
              i
              )
            
          
          2
        
        ⁢
        
          
            
              
            
            ⁢
            
              l
              ⁢
              
                
                  (
                  i
                  )
                
                2
              
            
          
          
            
              ∑
              
                j
                =
                1
              
              d
            
            ⁢
            
              
                l
                ⁡
                
                  (
                  j
                  )
                
              
              2
            
          
        
      
    
    ≥
    
      
        (
        
          
            ∑
            
              i
              =
              1
            
            d
          
          ⁢
          
            
              x
              ⁡
              
                (
                i
                )
              
            
            ⁢
            
              
                
                  l
                  ⁡
                  
                    (
                    j
                    )
                  
                
                2
              
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  d
                
                ⁢
                
                  
                    l
                    ⁡
                    
                      (
                      j
                      )
                    
                  
                  2
                
              
            
          
        
        )
      
      2
    
  
  ⇐
  
    
      
        
          ∑
          
            i
            =
            1
          
        
        d
      
      ⁢
      
        
          
            x
            ⁡
            
              (
              i
              )
            
          
          2
        
        ⁢
        
          
            l
            ⁡
            
              (
              i
              )
            
          
          2
        
      
    
    ≥
    
      
        (
        
          
            ∑
            
              i
              =
              1
            
            d
          
          ⁢
          
            
              x
              ⁡
              
                (
                i
                )
              
            
            ⁢
            
              
                
                  
                
                ⁢
                
                  l
                  ⁢
                  
                    
                      (
                      i
                      )
                    
                    2
                  
                
              
              
                
                  
                    ∑
                    
                      j
                      =
                      1
                    
                    d
                  
                  ⁢
                  
                    
                      l
                      ⁡
                      
                        (
                        j
                        )
                      
                    
                    2
                  
                
              
            
          
        
        )
      
      2
    
  




At ith iteration we store Mi using a low-rank representation ViTSiVi+Di where Viεk×d is orthonormal, Siεk×k is non-positive diagonal and Diεd×d is non-negative diagonal (each diagonal term of D1 (initialization) is set to 1/tλ where λ is the regularization term). We consider decrementing the matrix by a rank one update of the form Mi=Mi−1−ririT. By projecting ri onto each eigenvector in V, we can decompose ri as: ri=Σj=1kVi−1(j,•)riVi−1(j,•)T+res=Vi−1TVi−1ri+res. Thus the update rule can be rewritten as:




  
    
      
        
          
            
              
                M
                i
              
              =
              
              ⁢
              
                
                  M
                  
                    i
                    -
                    1
                  
                
                -
                
                  
                    r
                    i
                  
                  ⁢
                  
                    r
                    i
                    T
                  
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    V
                    
                      i
                      -
                      1
                    
                    T
                  
                  ⁢
                  
                    S
                    
                      i
                      -
                      1
                    
                  
                  ⁢
                  
                    V
                    
                      i
                      -
                      1
                    
                  
                
                +
                
                  D
                  
                    i
                    -
                    1
                  
                
                -
                
                  (
                  
                    
                      
                        V
                        
                          i
                          -
                          1
                        
                        T
                      
                      ⁢
                      
                        V
                        
                          i
                          -
                          1
                        
                      
                      ⁢
                      
                        r
                        i
                      
                    
                    +
                    res
                  
                  )
                
              
            
          
        
        
          
            
              
              ⁢
              
                
                  (
                  
                    
                      
                        V
                        
                          i
                          -
                          1
                        
                        T
                      
                      ⁢
                      
                        V
                        
                          i
                          -
                          1
                        
                      
                      ⁢
                      
                        r
                        i
                      
                    
                    +
                    res
                  
                  )
                
                T
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    
                      V
                      
                        i
                        -
                        1
                      
                      T
                    
                    ⁡
                    
                      (
                      
                        
                          S
                          
                            i
                            -
                            1
                          
                        
                        -
                        
                          
                            V
                            
                              i
                              -
                              1
                            
                          
                          ⁢
                          
                            r
                            i
                          
                          ⁢
                          
                            r
                            i
                            T
                          
                          ⁢
                          
                            V
                            
                              i
                              -
                              1
                            
                            T
                          
                        
                      
                      )
                    
                  
                  ⁢
                  
                    V
                    
                      i
                      -
                      1
                    
                  
                
                +
                
                  D
                  
                    i
                    -
                    1
                  
                
                -
                
                  resres
                  T
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    V
                    
                      i
                      -
                      1
                    
                    T
                  
                  ⁢
                  
                    S
                    
                      i
                      -
                      1
                    
                    ′
                  
                  ⁢
                  
                    V
                    
                      i
                      -
                      1
                    
                  
                
                +
                
                  D
                  
                    i
                    -
                    1
                  
                
                -
                
                  resres
                  T
                
              
            
          
        
      
    
    
      
        
      
    
  
  
    
      
        
          where
          ⁢
          
            
          
          ⁢
          
            S
            
              i
              -
              1
            
            ′
          
        
        =
        
          
            S
            
              i
              -
              1
            
          
          -
          
            
              V
              
                i
                -
                1
              
            
            ⁢
            
              r
              i
            
            ⁢
            
              r
              i
              T
            
            ⁢
            
              V
              
                i
                -
                1
              
              T
            
          
        
      
    
    
      
        
      
    
  




    
    
        Notice that Si−1′ can only have nonpositive entrances since S is initialized by a matrix of all zeros and then it is updated by subtracting nonnegative values from its diagonal.
    
    


By discarding the smallest singular value and its corresponding eigenvector, one ends up with matrix Mi′ of one of the following form:
1) If res was discarded:

Mi′=Vi−1TSi−1′Vi−1+Di−1=Mi+resresT=Mi+cvvT 

where c=1 and v=res

2) Otherwise, if mth eigenvector was discarded:




  
    
      
        
          M
          i
          ′
        
        =
        
        ⁢
        
          
            
              V
              
                i
                -
                1
              
              T
            
            ⁢
            
              S
              
                i
                -
                1
              
              ′
            
            ⁢
            
              V
              
                i
                -
                1
              
            
          
          +
          
            D
            
              i
              -
              1
            
          
          -
          
            resres
            T
          
          -
          
            
              
                S
                ′
              
              ⁡
              
                (
                
                  m
                  ,
                  m
                
                )
              
            
            ⁢
            
              
                V
                ⁡
                
                  (
                  
                    m
                    ,
                    ·
                  
                  )
                
              
              T
            
            ⁢
            
              V
              ⁡
              
                (
                
                  m
                  ,
                  ·
                
                )
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            M
            i
          
          -
          
            
              
                S
                ′
              
              ⁡
              
                (
                
                  m
                  ,
                  m
                
                )
              
            
            ⁢
            
              
                V
                ⁡
                
                  (
                  
                    m
                    ,
                    ·
                  
                  )
                
              
              T
            
            ⁢
            
              V
              ⁡
              
                (
                
                  m
                  ,
                  ·
                
                )
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            M
            i
          
          +
          
            cvv
            T
          
        
      
    
  




where c=−S′(m, m) and v=V(m,•)

Notice that both cases can be combined using the notation: Mi′=Mi+cvvT where c≧0 (since c=−S′(m, m) can only be nonnegative).
By discarding the smallest singular value and its corresponding eigenvector we violate the bound. Alternatively, instead of discarding, we can absorb those terms into a diagonal component, satisfying the bound. Formally, we look for diagonal matrix F such that Mi′′=Mi′−F and for all xεd: xTΣi′′x≧xTΣix where Σi=Mi−1 and Σi′′=Mi′′−1. Thus, we want to satisfy:

xTΣi′′x≧xTΣixxTMi′′−1x≧xTMi−1xxT(Mi′−F)−1x≧xTMi−1x 

xT(Mi+cvvT−F)−1x≧xTMi−1x 

From positive definiteness (throughout all iterations positive definiteness can be satisfied by the proper choice of λ while initializing D1, notice that to break positive definiteness in any iteration one would have to set λ to a very large value in the initialization, i.e. 1e23, which obviously is unreasonable in practice) it is equivalent to satisfy:

xT(Mi+cvvT−F)x≧xTMixxTcvvTx≧xTFxc(Σi=1dx(i)v(i))2≦Σi=1dx(i)2F(i)

where for the ease of notation F(i)=F(i, i).

Let




  
    
      ∀
      
        
          i
          =
          1
        
        ,
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ,
        d
      
    
    ⁢
    
      
        v
        ⁡
        
          (
          i
          )
        
      
      ′
    
  
  =
  
    
      
        
          v
          ⁡
          
            (
            i
            )
          
        
        w
      
      ⁢
      
        
      
      ⁢
      where
      ⁢
      
        
      
      ⁢
      W
    
    =
    
      
        ∑
        
          j
          =
          1
        
        d
      
      ⁢
      
        
          v
          ⁡
          
            (
            j
            )
          
        
        .
      
    
  




Let also for now assume that ∀i=1, . . . , dv(i)≧0. We will very soon get rid of this assumption. Thus we look for F such that: Σi=1dx(i)2F(i)≧c(Σi=1dx(i)Wv(i)′)2Σi=1dx(i)2F(i)≧cW2(Σi=1dx(i)v(i)′)2





  
    
      ∑
      
        i
        =
        1
      
      d
    
    ⁢
    
      
        
          x
          ⁡
          
            (
            i
            )
          
        
        2
      
      ⁢
      
        
      
      ⁢
      
        
          F
          ⁡
          
            (
            i
            )
          
        
        
          cW
          2
        
      
    
  
  ≥
  
    
      
        (
        
          
            ∑
            
              i
              =
              1
            
            d
          
          ⁢
          
            
              x
              ⁡
              
                (
                i
                )
              
            
            ⁢
            
              
                v
                ⁡
                
                  (
                  i
                  )
                
              
              ′
            
          
        
        )
      
      2
    
    .
  




Let





  
    
      ∀
      
        
          i
          =
          1
        
        ,
        ...
        ⁢
        
          
        
        ,
        d
      
    
    ⁢
    
      
        F
        ⁡
        
          (
          i
          )
        
      
      ′
    
  
  =
  
    
      
        F
        ⁡
        
          (
          i
          )
        
      
      
        cW
        2
      
    
    .
  




Thus we look for F′ such that: Σi=1dx(i)2F(i)′≧(Σi=1dx(i)v(i)′)2. By Theorem 5 one can easily show that the solution is F′=v(i)′ (simply substitute l(i)=sqrt(v(i)′) and keep in mind Σj=1dv(j)′=1). Thus:





  
    
      F
      ⁡
      
        (
        i
        )
      
    
    ′
  
  =
  
    
      
        v
        ⁡
        
          (
          i
          )
        
      
      ′
    
    =
    
      
        
          v
          ⁡
          
            (
            i
            )
          
        
        W
      
      .
    
  




Finally,





  
    F
    ⁡
    
      (
      i
      )
    
  
  =
  
    
      
        cW
        2
      
      ⁢
      
        
          F
          ⁡
          
            (
            i
            )
          
        
        ′
      
    
    =
    
      
        
          cW
          2
        
        ⁢
        
          
        
        ⁢
        
          
            v
            ⁡
            
              (
              i
              )
            
          
          W
        
      
      =
      
        
          cWv
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            cv
            ⁡
            
              (
              i
              )
            
          
          ⁢
          
            
              ∑
              
                j
                =
                1
              
              d
            
            ⁢
            
              
                v
                ⁡
                
                  (
                  j
                  )
                
              
              .
            
          
        
      
    
  




Thus for all xεd and for all xεd such that ∀i=1, . . . , d:v(i)≧0 and for F(i)=cv(i)Σj=1dv(j) the following inequality holds:

Σi=1dx(i)2F(i)≧c(Σi=1dx(i)v(i))2  (3)

To generalize the inequality to hold for all vectors vεd (also with negative entrances), it is sufficient to set F(i)=c|v(i)|Σj=1d|v(j)|. To see it consider flipping the sign of any v(i), the left side of the Inequality 3 does not change. For the right side of this inequality, flipping the sign of v(i) is equivalent to flipping the sign of x(i) and not changing the sign of v(i), but in this case the inequality holds as proven before (it holds for any xεd). Thus for all xεd and for all vεd and for F(i)=c|v(i)|Σj=1d|v(j)|, Inequality 3 holds.

## Claims

1. A system for optimizing parameters of a structured prediction model, the system comprising:
a computer-readable medium;
a parameter optimization processor coupled to the computer-readable medium; and
a communication interface coupled to the parameter optimization processor and adapted to receive and transmit electronic representations of structured prediction models to and from the parameter optimization processor, respectively,
the computer-readable medium having stored thereon software instructions that, when executed by the parameter optimization processor, cause the parameter optimization processor to perform operations including:
initializing a group of parameters to respective values corresponding to a state within a set of allowable structured prediction models;
bounding a partition function across a number of variable pairs to generate a plurality of bounds each being a quadratic upper bound on a partition function;
determining new values for the group of parameters that minimize a sum of the plurality of bounds;
setting the group of parameters to the new values;
optimizing the parameters by iteratively performing the bounding, determining and setting; and
stopping the optimizing when a termination condition is reached.

2. The system of claim 1, wherein the bounding includes updating a partition function value, a gradient and a curvature of the quadratic upper bound.

3. The system of claim 1, wherein the termination condition includes determining that a difference between a conditional likelihood based on the current parameters and a previous conditional likelihood based on previous parameters is less than a predetermined value.

4. The system of claim 1, wherein the termination condition includes determining that a difference between a current set of parameters and a previous set of parameters is less than a predetermined threshold value.

5. The system of claim 1, wherein the termination condition includes performing a predetermined number of iterations.

6. The system of claim 1, wherein the termination condition includes performing the bounding, determining and setting for a predetermined period of time.

7. The system of claim 1, wherein the set of allowable models forms a convex hull.

8. The system of claim 1, wherein each variable pair includes an observed input value and an observed output value.

9. The system of claim 1, wherein each variable pair includes a first sample and a second sample from an unknown distribution.

10. The system of claim 1, wherein the structured prediction model includes one of a deep belief network, a machine learning model, a pattern recognition model, a shallow parsing model, a named entity recognition model, a gene finding model, an object recognition model and an image segmentation model.

11. A computerized method for optimizing parameters for a structured prediction system, the method comprising:
initializing a group of parameters to respective values corresponding to a state within a set of allowable models;
bounding a partition function across a number of variable pairs to generate a plurality of bounds, wherein the bounding includes computing a quadratic upper bound on the partition function;
determining new values for the group of parameters that minimize a sum of the plurality of bounds;
setting the group of parameters to the new values;
optimizing the parameters by iteratively performing the bounding, determining and setting; and
stopping the optimizing when a termination condition is reached.

12. The method of claim 11, wherein the bounding includes updating a partition function value, a gradient and a curvature of the quadratic upper bound.

13. The method of claim 11, wherein the termination condition includes determining that a difference between a conditional likelihood based on the current parameters and a previous conditional likelihood based on previous parameters is less than a predetermined value.

14. The method of claim 11, wherein the termination condition includes determining that a difference between a current set of parameters and a previous set of parameters is less than a predetermined threshold value.

15. The method of claim 11, wherein the termination condition includes performing a predetermined number of iterations.

16. The method of claim 11, wherein the termination condition includes performing the bounding, determining and setting for a predetermined period of time.

17. The method of claim 11, wherein the set of allowable models forms a convex hull.

18. The method of claim 11, wherein each variable pair includes an observed input value and an observed output value.

19. The method of claim 11, wherein each variable pair includes a first sample and a second sample from an unknown distribution.

20. The method of claim 11, wherein the structured prediction system includes one of a machine learning system, a pattern recognition system, a shallow parsing system, a named entity recognition system, a gene finding system, an object recognition system and an image segmentation system.

21. The method of claim 11, wherein the bounding includes:
providing a graphical model arranged as a junction tree;
computing bounds for a set of variables that a clique of the junction tree has in common with a parent clique of the clique;
collecting pre-computed bounds from child cliques of the clique;
updating quadratic bound variables for the clique based on the computed bounds and the collected pre-computed bounds;
terminating the updating when a root clique is reached; and
outputting a curvature of a partition function bound, a partition function value and a gradient,
wherein the computing, collecting and updating are performed recursively beginning with leaf cliques of the junction tree and progressing toward root cliques.

22. The method of claim 11, wherein the bounding includes:
computing a partition function value;
computing a gradient vector for a number of indices; and
computing a curvature of a bound, wherein the curvature is stored as a group of low rank matrices including a first matrix having singular values, a second matrix having eigenvectors and a third matrix being a diagonal matrix.

23. A computerized method for optimizing parameters for a structured prediction system, the method comprising:
initializing a group of parameters to respective values corresponding to a state within a set of allowable models;
bounding a partition function, wherein the bounding includes one or more of:
a) computing a quadratic upper bound on the partition function;
b) iteratively computing upper bounds on the partition function and selecting parameters to minimize a sum of the bounds;
c) computing a partition function bound for a latent likelihood model;
d) computing a partition function bound for a graphical model; and
e) computing a partition function bound for a high dimensional model using a plurality of matrices to represent a curvature of the partition function bound;
determining new values for the group of parameters based on the bounding;
setting the group of parameters to the new values;
optimizing the parameters by iteratively performing the bounding, determining and setting; and
stopping the optimizing when a termination condition is reached.

24. The method of claim 23, wherein the optimizing converges monotonically.

25. The method of claim 23, wherein the optimizing converges monotonically when the bounding includes computing a partition function bound for a latent likelihood model.