# Patent

## Title
Constrained line search optimization for discriminative training of HMMS

## Abstract

An exemplary method for optimizing a continuous density hidden Markov model (CDHMM) includes imposing a constraint for discriminative training, approximating an objective function as a smooth function of CDHMM parameters and performing a constrained line search on the smoothed function to optimize values of the CDHMM parameters. Various other methods, devices and systems are disclosed.

## Background
BACKGROUND
In the past few decades, discriminative training (DT) has been a very active research topic in the field of automatic speech recognition (ASR). Many DT methods have been proposed to estimate Gaussian mixture continuous density hidden continuous density Markov models (CDHMMs) in a variety of speech recognition tasks, ranging from small vocabulary isolated word recognition to large vocabulary continuous speech recognition tasks. Generally speaking, DT of CDHMMs is a typical optimization problem that starts with formulation of an objective function according to certain estimation criterion. Some popular DT criteria widely used in speech recognition include maximum mutual information (MMI), minimum error estimation (MCE), minimum word or phone error (MWE or MPE), minimum divergence (MD), and so on. Once the objective function is formulated, an effective optimization method must be used to minimize or maximize the objective function with respect to its CDHMM parameters.
With respect to optimization, in speech recognition, several different methods have been used to optimize the derived objective function, including the GPD (generalized probabilistic descent) algorithm based on the first-order gradient descent method, and the approximate second-order Quickprop method, and the extended Baum-Welch (EBW) algorithm based on growth transformation and so on.
The GPD and Quickprop methods are mainly used for optimizing the MCE-derived objective function even though they are general optimization methods which can be used for any types of differentiable objective functions. On the other hand, the EBW method has been initially proposed to maximize a rational objective function and later extended to Gaussian mixture CDHMMs for the MMI and MPE (or MWE) objective functions. Recently, the EBW method has also been generalized to optimize the MCE objective function as well as the MD objective function.
The EBW method has been widely accepted for DT because it is relatively easy to be implemented on word graphs for large scale ASR tasks and it has been demonstrated that the EBW algorithm performs well in many tasks. Essentially, all of these optimization methods attempt to search for a nearby locally optimal point of the objective function from an initial point according to both a search direction and a step size. Normally, the search direction is locally computed based on the first-order derivative (such as gradient) and the step size must be empirically determined in practice. As the result, the performance of these optimization methods highly depends on the location of the initial point and the property of objective functions. If the derived objective function is highly nonlinear, jagged and non-convex in nature, it is extremely difficult to optimize it effectively with any simple optimization algorithm, which is one of the major difficulties of DT of HMMs for speech recognition.
As described herein, various exemplary techniques can be used to optimize CDHMM parameters for applications such as speech recognition or, more generally, pattern recognition.
SUMMARY
An exemplary method for optimizing a continuous density hidden Markov model (CDHMM) includes imposing a constraint for discriminative training, approximating an objective function as a smooth function of CDHMM parameters and performing a constrained line search on the smoothed function to optimize values of the CDHMM parameters. Various other methods, devices and systems are disclosed.



BRIEF DESCRIPTION OF THE DRAWINGS
Non-limiting and non-exhaustive embodiments are described with reference to the following figures, wherein like reference numerals refer to like parts throughout the various views unless otherwise specified.
FIG. 1 is a block diagram of an exemplary method for optimizing a continuous density hidden Markov model (CDHMM).
FIG. 2 is a block diagram of an exemplary method for optimizing a continuous density hidden Markov model (CDHMM) using objective function smoothing and a constrained line search.
FIG. 3 is a block diagram of an exemplary method for optimizing a continuous density hidden Markov model (CDHMM) that includes deciding if a critical point exists.
FIG. 4 is a block diagram of an exemplary method for imposing a constraint for discriminative training based on Kullback-Leibler divergence and obtaining a closed-form solution.
FIG. 5 is a table of criteria and associated functions.
FIG. 6 is a graphic of an exemplary technique to optimize an objective function that corresponds to a case referred to as Case 1.
FIG. 7 is a graphic of an exemplary technique to optimize an objective function that corresponds to a case referred to as Case 2.
FIG. 8 is a graphic of an exemplary technique to optimize an objective function that corresponds to a case referred to as Case 3.
FIG. 9 is a graphic of an exemplary technique to optimize an objective function that corresponds to a case referred to as Case 4.
FIG. 10 is a table that presents search directions for Cases 1, 2, 3 and 4.
FIG. 11 is a table that presents conditions for applying a CLS solution to “means” for Cases 1, 2, 3 and 4.
FIG. 12 is a table that presents conditions for applying a CLS solution to “variances” for Cases 1, 2, 3 and 4.
FIG. 13 is a table that presents trial setups for various recognition tasks for comparative trials.
FIG. 14 is a table that presents trial results for recognition performance.
FIG. 15 is a table that presents comparative trial results for recognition performed using an exemplary CLS optimization and other optimization techniques.
FIG. 16 is a diagram of various components of an exemplary computing device that may be used to implement part or all of various exemplary methods discussed herein.



DETAILED DESCRIPTION
An exemplary optimization method is referred to as a constrained line search (CLS) for discriminative training (DT) of Gaussian mixture continuous density hidden Markov models (CDHMM).
FIG. 1 shows an exemplary method 100 that includes a provision block 104 for providing a Gaussian mixture CDHMM. An optimization block 108 optimizes parameters of the Gaussian mixture CDHMM using a constrained line search (CLS) for discriminative training (DT). An application block 112 applies the model with the optimized parameters, which may include mean vectors, covariance matrices and mixture weights.
FIG. 2 shows an exemplary method 200 that contrasts a conventional approach 220 with an exemplary approach 240. The method 200 commences in a formulation block 210 that formulates an objective function based in part on an estimation criterion or estimation criteria. Some examples of criteria 212 include maximum mutual information (MMI), minimum classification error (MCE), minimum phone/word error (MPE/MWE), and minimum divergence (MD).
In the conventional approach 220, an optimization block 230 minimizes or maximizes the formulated objective function with respect to a set of CDHMM parameters (see, e.g., Background section). In this approach, a specification block 232 specifies an initial point, an iteration block 234 determines a search direction and a step size to move away from the initial point and a location block 236 finds a locally optimal point.
In the exemplary approach 240, an imposition block 242 imposes a constraint for discriminative training (DT) based on Kullback-Leibler divergence (KLD) between models (e.g., parameter values for an initial model and parameter values for an updated model). The imposition block 242 essentially casts discriminative training (DT) of the CDHMM as a constrained maximization problem where the constraint guarantees that an equalized updating process occurs across all parameters in a model set. Next, an approximation block 244 approximates the objective function as a smooth function of CDHMM parameters. As described in more detail below, based upon reasonable approximations, closed-form solutions can be obtained for CDHMM parameters. To find a locally optimal point representative of CDHMM parameter values, a search block 246 performs a constrained line search (CLS) on the smoothed function of the CDHMM parameters. As explained below, given a line search and some approximation assumptions, manageable closed-form solutions can be derived for CDHMMs. The exemplary method 200 can be used to optimize all model parameters in Gaussian mixture CDHMMs, including mean vectors, covariance matrices, mixture weights.
Trial results are presented for several benchmark speech recognition tasks, including TIDIGITS, Resource Management (RM) and Switchboard. Results indicate that the exemplary training method significantly outperforms the popular, conventional EBW (extended Baum-Welch) method in all tasks in terms of recognition performance and convergence behavior.
As mentioned, an exemplary optimization method is referred to as a CLS for DT of Gaussian mixture CDHMMs. As a general optimization method, under a unified framework, such an exemplary CLS method is capable of optimizing most DT objective functions, which are derived from one or more popular DT criteria in speech recognition, such as MMI, MCE, MPE (or MWE) and so on. In a particular aspect, a manageable closed-form optimization formula can be derived to efficiently update all parameters of Gaussian mixture CDHMMs, including mean vectors, covariance matrices and mixture weights.
FIG. 3 shows an exemplary method 300 that includes the steps 242, 244 and 246 of the exemplary approach 240 of FIG. 2. In addition, it includes a decision block 248 that decides if a critical point exists on the smoothed function. If a critical point exists, then the method 300 proceeds along a branch to a block 250 that performs a CLS along a line joining an initial point and the critical point. However, if the decision block 248 decides that a critical point does not exist, then the method 300 proceeds along a branch to a block 252 that performs a CLS along a gradient direction at the initial point.
In the method 300, the imposed constraint is based upon the nature that all the statistics are only reliable in a neighborhood of the original model. Under this constraint, the objective function can be approximated as a smooth function of CDHMM parameters and the sole critical point, if it exists, can be easily obtained by vanishing its derivative to zero. This is the role of the decision block 248 of the method 300, which is followed by a CLS to solve the constrained optimization problem.
As shown with respect to the blocks 250, 252, subject to the KLD constraint, the line search is performed either along the line joining the initial model and the critical point of the smoothed objective function if the critical point exists (the block 250) or along the gradient direction at the initial point if the critical point does not exist (the block 252).
FIG. 4 shows an exemplary method 400 that includes deriving a closed-form solution to a constrained optimization problem. As explained, an imposition block 404 can impose a constraint for DT based on KLD between CDHMM initial parameter values and updated parameter values. In the method 400, KLD acts a distortion constraint to smooth a model near an initial point in CDHMM parameter space. With smoothing, a derivation block 408 can derive a closed-form solution to the constrained optimization problem.
According to the method 400, a closed-form solution can be derived to solve a KLD constrained optimization as long as formulation or approximation of the KLD constraint occurs in an appropriate way. Constrained optimization relies on the fact that statistics in DT only remain reliably when models stay close to their original points. Unlike in Maximum Likelihood (ML) training, it is hard to find an auxiliary function along with which the original objective is guaranteed to increase. Hence, the exemplary method 400 constrains distortion of models by KLD, which is a statistically sound distribution similarity measure.
Through use of a CLS, some degree of control is introduced for updating every model to be equalized and an entire training process can be more stable and effective.
As described with respect to the trials, an exemplary method has been used to optimize the MMI as well as other DT objectives in several speech recognition tasks, including the connected digit string recognition using TIDIGITS database, the resource management (RM) task, and a large vocabulary recognition in the Switchboard task. Results show that an exemplary line search method can significantly outperform the conventional EBW method in all evaluated ASR tasks in terms of final recognition performance and convergence behavior.
Various exemplary techniques are described in more detail below, generally, as follows: a technique to formulate the discriminative training as a KLD-based constrained optimization problem under a unified framework, a constrained line search technique to solve a constrained optimization problem for DT, application of techniques to CDHMMs, and various associated algorithms. Formulation of KLD Constraint
DT criteria for a speech recognition model may assume that an acoustic model set Λ is composed of many individual Gaussian mixture CDHMMs, each of which is represented as λ=(π, A,B), where π={π1,π2, . . . πN} is the initial state distribution and N is the number of states in the HMM, A ={aij}NxN is the transition matrix, and B is the state output distribution set, composed of Gaussian mixture distributions for all state i: bi(x)=Σk=1Kωik·(x; μik, Σik), where Bi={ωi, μik, Σik|1≦k≦K} with K standing for the number of Gaussian mixture components in each state, and (x; μ,Σ) represents a multivariate Gaussian distribution with mean vector μ and covariance matrix Σ.
For any training utterance X and its transcription W, consider how to compute an acoustic model score p(X|W) based on the composite HMM λW of W. Suppose X={X1, X2, . . . XT}, let s={s1, s2, . . . sT} be any possible unobserved state sequence, and l={l1, l2, . . . lT} be the associated sequence of the unobserved mixture component labels. Thus, p(X|W) is computed as Equation 1 (Eq. 1):




  
    p
    ⁡
    
      (
      
        X
        |
        W
      
      )
    
  
  =
  
    
      ∑
      s
    
    ⁢
    
      
        ∑
        l
      
      ⁢
      
        {
        
          
            
              π
              _
            
            
              s
              1
            
          
          ⁢
          
            
              ∏
              
                t
                =
                2
              
              T
            
            ⁢
            
              
                a
                
                  
                    s
                    
                      t
                      -
                      1
                    
                  
                  ⁢
                  
                    s
                    t
                  
                
              
              ·
              
                
                  ∏
                  
                    t
                    =
                    1
                  
                  T
                
                ⁢
                
                  
                    ω
                    
                      
                        S
                        i
                      
                      ⁢
                      
                        l
                        t
                      
                    
                  
                  ·
                  
                    N
                    ⁡
                    
                      (
                      
                        
                          
                            x
                            t
                          
                          ;
                          
                            μ
                            
                              
                                s
                                i
                              
                              ⁢
                              
                                l
                                t
                              
                            
                          
                        
                        ,
                        
                          ∑
                          
                            
                              s
                              i
                            
                            ⁢
                            
                              l
                              t
                            
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
        }
      
    
  




where summations are taken over all possible state sequences s and mixture labels l.

Assume the whole training set consists of R different training utterances X1, X2, . . . , XR along with their corresponding transcriptions, denoted as W1, W2, . . . , WR. For a unified view to represent various discriminative training criteria, the objective functions of CDHMMs derived from various discriminative training criteria can be formulated as the following form, as Equation 2 (Eq. 2):




  
    
      
        
          F
          ⁡
          
            (
            Λ
            )
          
        
        =
        
        ⁢
        
          p
          ⁡
          
            (
            
              
                Λ
                |
                
                  
                    {
                    
                      
                        X
                        r
                      
                      ,
                      
                        W
                        r
                      
                      ,
                      
                        M
                        r
                      
                    
                    }
                  
                  
                    r
                    =
                    1
                  
                  R
                
              
              ,
              f
              ,
              κ
              ,
              G
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            1
            R
          
          ⁢
          
            
              ∑
              
                r
                =
                1
              
              R
            
            ⁢
            
              f
              (
              
                
                  log
                  [
                  
                    
                      
                        ∑
                        
                          E
                          ∈
                          
                            M
                            r
                          
                        
                      
                      ⁢
                      
                        
                          
                            p
                            κ
                          
                          ⁡
                          
                            (
                            
                              
                                X
                                r
                              
                              |
                              
                                W
                                r
                              
                            
                            )
                          
                        
                        ·
                        
                          p
                          ⁡
                          
                            (
                            
                              W
                              r
                            
                            )
                          
                        
                        ·
                        
                          G
                          ⁡
                          
                            (
                            
                              W
                              ,
                              
                                W
                                r
                              
                            
                            )
                          
                        
                      
                    
                    
                      
                        ∑
                        
                          W
                          
                            ′
                            ⁢
                            
                              
                            
                            ∈
                            
                              M
                              r
                            
                          
                        
                      
                      ⁢
                      
                        
                          
                            p
                            κ
                          
                          ⁡
                          
                            (
                            
                              
                                X
                                r
                              
                              |
                              
                                W
                                ′
                              
                            
                            )
                          
                        
                        ·
                        
                          p
                          ⁡
                          
                            (
                            
                              W
                              ′
                            
                            )
                          
                        
                      
                    
                  
                  ]
                
                
                  1
                  /
                  π
                
              
              )
            
          
        
      
    
  




where 0<κ≦1 is the acoustic scaling factor, and Mr stands for all competing hypotheses of utterance Xr which is compactly approximated by a word lattice generated from Viterbi decoding, and ƒ(·) is a mapping function to transform the objective function, and G(W, Wr) is the so-called gain function to measure the dissimilarity between the reference Wr and a hypothesis W. Both the mapping function ƒ(·) and the gain function G(W, Wr) take different functional forms in various discriminative training criteria, as listed in Table 500 of FIG. 5. For purposes of an exemplary analysis described herein, it is assumed that language model score p(W) is fixed.

For constrained optimization for discriminative training, substitution of Eq. (1) into Eq. (2) yields a general DT objective function, F(Λ). In this example, the function is a highly complicated nonlinear function, which is extremely difficult to optimize directly. An exemplary approach to smooth this function can make the following assumptions: i) assume that all competing hypothesis spaces  remain unchanged during optimization; ii) use a sufficiently small scaling factor κ(κ<<1) to smooth the original objective function, and then assume that all the state occupancies and Gaussian kernel occupancies remain unchanged. Under these assumptions, it becomes necessary to explicitly impose the constraint that the HMM model parameters Λ that do not significantly differ from their initial values to ensure that the above assumptions still remain valid during optimization since the initial models have been used to generate all word lattices  and to calculate likelihood function p(X|λW) in Eq. (1) and to accumulate statistics from training data in optimization. This kind of constraint can be quantitatively defined based on Kullback-Leibler divergence (KLD) between models. An exemplary approach formulates a discriminative training problem of CDHMMs as a constrained maximization problem. In such an approach, the updating procedure can proceed iteratively, and in each iteration, given the initial model Λ0, the optimization problem can be formulated as Equation 3 (Eq. 3):




  
    
      Λ
      ^
    
    =
    
      
        arg
        ⁢
        
          
        
        ⁢
        
          
            max
            Λ
          
          ⁢
          
            
              F
              ⁡
              
                (
                Λ
                )
              
            
            ⁢
            
              
            
            ⁢
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              
            
            ⁢
            
              D
              ⁡
              
                (
                
                  Λ
                  ||
                  
                    Λ
                    0
                  
                
                )
              
            
          
        
      
      ≤
      
        ρ
        2
      
    
  
  ,




where D(Λ∥Λ0) is KLD between Λ and its initial value Λ0, and ρ>0 is a pre-set constant to control the search range. The constraint in Eq. 3 intuitively specifies a trust region for optimization of the objective function.

Constrained Line Search

To solve the constrained optimization problem cast above, an exemplary approach uses a constrained line search (CLS) algorithm. The algorithm decomposes an optimization procedure into two steps. A first step involves determining an appropriate search direction to provide a direction to search for an optimal point. In a second step, searching occurs along the direction for an optimal linear inter/extrapolation factor which aims to maximize the objective function subject to the KLD constraint.
For purposes of explanation, any model parameter may be denoted λ and its corresponding initial value in a current iteration denoted λ0. In the first step, the best search direction is selected. Assuming the objective function F(λ) is differentiable, the critical point λ*, if it exists, can be obtained by vanishing ∇F(λ) to zero. Furthermore, if λ* is not a saddle point, it is reasonable to choose the line joining the critical point and the original point (i.e., λ* to λ0) as the search direction. Otherwise, when the critical point is a saddle point or if the critical point does not exist, the following approach adopts the gradient ∇F(λ0)≡∇F(λ)|λ=λ0 as the search direction. The search direction  can be selected according to Equation 4 (Eq. 4):




  d
  =
  
    {
    
      
        
          
            
              
                λ
                *
              
              -
              
                λ
                0
              
            
            ,
          
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              
                λ
                *
              
              ⁢
              
                
              
              ⁢
              exists
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              is
              ⁢
              
                
              
              ⁢
              not
              ⁢
              
                
              
              ⁢
              a
              ⁢
              
                
              
              ⁢
              saddle
              ⁢
              
                
              
              ⁢
              point
            
            ⁢
            
              
            
          
        
      
      
        
          
            
              ∇
              
                F
                ⁡
                
                  (
                  
                    λ
                    0
                  
                  )
                
              
            
            ,
          
        
        
          otherwise
        
      
    
  




In the second step, the constrained optimization problem in Eq. 3 can be reformulated as Equation 5 (Eq. 5), a constrained search problem in a scalar space:




  
    
      ε
      ^
    
    =
    
      
        arg
        ⁢
        
          
        
        ⁢
        
          
            max
            ε
          
          ⁢
          
            
              F
              ⁡
              
                [
                
                  λ
                  ⁡
                  
                    (
                    ε
                    )
                  
                
                ]
              
            
            ⁢
            
              
            
            ⁢
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              
            
            ⁢
            
              D
              ⁡
              
                [
                
                  
                    λ
                    ⁡
                    
                      (
                      ε
                      )
                    
                  
                  ||
                  
                    λ
                    0
                  
                
                ]
              
            
          
        
      
      ≤
      
        ρ
        2
      
    
  
  ,




where λ(ε)=λ0+ε·d is the new model parameters in the line search space accordingly to the factor ε.

In general, such a constrained line search problem should be solved iteratively. However, according to an exemplary technique, if the constraint possesses the following quadratic form of Equation 6 (Eq. 6):

D(λ∥λ0)=Q(λ−λ0,φ)≡(λ−λ0)Tφ−1(λ−λ0)

where φ is a positive-definite matrix, then the constrained line search problem can be solved directly. For conciseness of this explanation, Q() is introduced to express a quadratic form.
In the instance a solution can be obtained by finding the crossing point of the line space λ(ε) and the boundary of the trust region, or equivalently, solving D(λ0+ε·d∥λ0)=ρ2 with respect to ε. By substituting Eq. 6 into this Equation 7 (Eq. 7) results:

ε2·Q(d,φ)=ρ2 

where roots can be represented as:





  ε
  =
  
    
      ±
      ρ
    
    ·
    
      
        Q
        
          -
          
            1
            2
          
        
      
      ⁡
      
        (
        
          d
          ,
          φ
        
        )
      
    
  




An analysis of all the cases and boundary conditions provides a closed form solution for CLS with quadratic constraint. FIGS. 6, 7, 8 and 9 present graphics representing four cases (Case 1, 2, 3 and 4).
FIG. 6 shows an exemplary technique to maximize an objective function 600 that corresponds to Case 1. For Case 1, the critical point λ* exists, is a maximum and lies within a trust region. In Case 1, the model can be moved directly to the critical point λ*.
FIG. 7 shows an exemplary technique to maximize an objective function 700 that corresponds to Case 2. For Case 2, the critical point λ* exists and is a maximum but lies outside a trust region. In Case 2, the model can be moved to the positive root of Eq. 7.
FIG. 8 shows an exemplary technique to maximize an objective function 800 that corresponds to Case 3. For Case 3, the critical point λ* exists but is a minimum that lies outside a trust region. In Case 3, the model can be moved to the negative root of Eq. 7.
FIG. 9 shows an exemplary technique to maximize an objective function 900 that corresponds to Case 4. For Case 4, pertains to scenarios where the critical point λ* does not exist or where the critical point is a saddle point. In Case 4, the model can be moved to the positive root of Eq. 7.
FIG. 10 shows Table 1000, which lists solutions for Cases 1, 2, 3 and 4.
CLS for Gaussian Mixture CDHMM
A general solution for CLS with quadratic constraints has been explained. This exemplary approach can be applied to provide a solution to parameters of Gaussian Mixture CDHMMs. Such an approach solves two problems: First, how to decompose constraints to update mean, covariance and Gaussian weights separately, and then reasonably approximate the constraints by quadratic forms; and second, how to obtain the critical points and corresponding conditions, for example, as listed in Table 1000.
Constraint Decomposition for Gaussian Mixtures
It is reasonable to apply the KLD constraint to the Gaussian mixture model of each state. For the ith state, it can be written as: D(bi∥bi0)<ρ2. Furthermore, decomposition of the constraint for Gaussian weights, means and covariances can occur followed by updating them separately. By applying a log-sum inequality, an upper bound of the KLD between two Gaussian mixtures is obtained as Equation 8 (Eq. 8):

D(bi∥bi0)≦D(wi∥wi0)+wiTei 

where the transpose of vector wi denotes discrete distribution composed of all the Gaussian kernel weights in the ith state and where the vector ei includes

eik=D(ik∥ik0).

For KLD between two discrete distributions or two Gaussians, the Equation 9 (Eq. 9) represents closed-form solutions:



  
    
      D
      ⁡
      
        (
        
          N
          ||
          
            N
            0
          
        
        )
      
    
    =
    
      
        1
        2
      
      ⁢
      
        {
        
          
            Q
            ⁡
            
              (
              
                
                  μ
                  -
                  
                    μ
                    0
                  
                
                ,
                
                  Σ
                  0
                
              
              )
            
          
          +
          
            tr
            ⁡
            
              [
              
                
                  Σ
                  ⁡
                  
                    (
                    
                      Σ
                      0
                    
                    )
                  
                
                
                  -
                  1
                
              
              ]
            
          
          +
          
            log
            ⁢
            
              
            
            ⁢
            
              
                
                
                  Σ
                  0
                
                
              
              
                
                Σ
                
              
            
          
          -
          D
        
        }
      
    
  




  
    
      D
      ⁡
      
        (
        
          ω
          ||
          
            ω
            0
          
        
        )
      
    
    =
    
      
        ω
        T
      
      ⁡
      
        (
        
          
            log
            ⁢
            
              
            
            ⁢
            ω
          
          -
          
            log
            ⁢
            
              
            
            ⁢
            
              ω
              0
            
          
        
        )
      
    
  



where D is the dimensionality of the Gaussian. Accordingly, the KLD constraint can be decomposed to separate constraints for Gaussian means, covariances and weights as shown in Equation 10 (Eq. 10):





  {
  
    
      
        
          
            
              Q
              ⁡
              
                (
                
                  
                    
                      μ
                      ik
                    
                    -
                    
                      μ
                      ik
                      0
                    
                  
                  ,
                  
                    Σ
                    ik
                    0
                  
                
                )
              
            
            ≤
            
              ρ
              1
              2
            
          
        
        
          
            (
            
              1
              ≤
              k
              ≤
              K
            
            )
          
        
      
      
        
          
            
              
                tr
                ⁡
                
                  [
                  
                    
                      
                        Σ
                        ik
                      
                      ⁡
                      
                        (
                        
                          Σ
                          ik
                          0
                        
                        )
                      
                    
                    
                      -
                      1
                    
                  
                  ]
                
              
              +
              
                log
                ⁢
                
                  
                    
                    
                      Σ
                      ik
                      0
                    
                    
                  
                  
                    
                    
                      Σ
                      ik
                    
                    
                  
                
              
              -
              D
            
            ≤
            
              ρ
              2
              2
            
          
        
        
          
            (
            
              1
              ≤
              k
              ≤
              K
            
            )
          
        
      
      
        
          
            
              
                ω
                i
                T
              
              ⁡
              
                (
                
                  
                    log
                    ⁢
                    
                      
                    
                    ⁢
                    
                      ω
                      i
                    
                  
                  -
                  
                    log
                    ⁢
                    
                      
                    
                    ⁢
                    
                      ω
                      i
                      0
                    
                  
                
                )
              
            
            ≤
            
              ρ
              3
              2
            
          
        
        
          
            
          
        
      
    
     
  




where ρ12, ρ22, ρ32 are three pre-set constants to control ranges for weights, mean and covariance, respectively.

Quadratic Approximation of the Constraints

Based upon a basic assumption of CLS, the model parameters cannot run far away from their initial point. Given this assumption, the Taylor series approximation is applied to derive quadratic constraints for variances and weights. Consider an example that assumes a covariance matrix Σik that is diagonal. To guarantee the covariance is positive-definite, alternatively update the following vector logarithm domain: σik=(log σik12, . . . , log σikD2)T. Based upon the second-order Taylor series approximation ey−y−1 ̃y2/2 and denoting yikd=log(σikd/σikd0)2, provides Equation 11 (Eq. 11):




  
    
      
        
          D
          ⁡
          
            (
            
              
                Σ
                ik
              
              ||
              
                Σ
                ik
                0
              
            
            )
          
        
        =
        
        ⁢
        
          
            tr
            ⁡
            
              [
              
                
                  
                    Σ
                    ik
                  
                  ⁡
                  
                    (
                    
                      Σ
                      ik
                      0
                    
                    )
                  
                
                
                  -
                  1
                
              
              ]
            
          
          +
          
            log
            ⁢
            
              
                
                
                  Σ
                  ik
                  0
                
                
              
              
                
                
                  Σ
                  ik
                
                
              
            
          
          -
          D
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            
              d
              =
              1
            
            D
          
          ⁢
          
            (
            
              
                e
                
                  y
                  ikd
                
              
              -
              
                y
                ikd
              
              -
              1
            
            )
          
        
      
    
  
  
    
      
        ≈
        
        ⁢
        
          
            ∑
            
              d
              =
              1
            
            D
          
          ⁢
          
            
              y
              ikd
              2
            
            /
            2
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            1
            2
          
          ⁢
          
            
              (
              
                
                  σ
                  ik
                
                -
                
                  σ
                  ik
                  0
                
              
              )
            
            T
          
          ⁢
          
            (
            
              
                σ
                ik
              
              -
              
                σ
                ik
                0
              
            
            )
          
        
      
    
  




Also, for Gaussian weights, one can adopt the Taylor series approximation log z ̃z−1 (when z is near to 1) and denote Zik=wik/wik0. It is notable that for Gaussian weights, beside the KLD constraint, another constraint of





  
    
      ∑
      
        k
        =
        1
      
      K
    
    ⁢
    
      w
      ik
    
  
  =
  1.




Accordingly, Equation 12 (Eq. 12) can be obtained:




  
    
      
        
          
            D
            ⁡
            
              (
              
                
                  ω
                  i
                
                ||
                
                  
                    ω
                    ~
                  
                  i
                
              
              )
            
          
          =
          
          ⁢
          
            
              ω
              i
              T
            
            ⁡
            
              (
              
                
                  log
                  ⁢
                  
                    
                  
                  ⁢
                  
                    ω
                    i
                  
                
                -
                
                  log
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      ω
                      ~
                    
                    i
                  
                
              
              )
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              K
            
            ⁢
            
              
                ω
                ik
              
              ⁢
              log
              ⁢
              
                
              
              ⁢
              
                z
                ik
              
            
          
        
      
    
    
      
        
          ≈
          
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              K
            
            ⁢
            
              
                ω
                ik
              
              ⁡
              
                (
                
                  
                    z
                    ik
                  
                  -
                  1
                
                )
              
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              K
            
            ⁢
            
              
                
                  
                    ω
                    ik
                  
                  ⁢
                  
                    ω
                    ik
                  
                
                -
                
                  2
                  ⁢
                  
                    ω
                    ik
                    0
                  
                  ⁢
                  
                    ω
                    ik
                  
                
                +
                
                  
                    ω
                    ik
                    0
                  
                  ⁢
                  
                    ω
                    ik
                  
                
              
              
                ω
                ik
                0
              
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              
                (
                
                  
                    ω
                    i
                  
                  -
                  
                    ω
                    i
                    0
                  
                
                )
              
              T
            
            ⁢
            
              
                (
                
                  Π
                  i
                  0
                
                )
              
              
                -
                1
              
            
            ⁢
            
              (
              
                
                  ω
                  i
                
                -
                
                  ω
                  i
                  0
                
              
              )
            
          
        
      
    
  




  
    where
    ⁢
    
      
    
    ⁢
    
      
        {
        
          Π
          i
          0
        
        }
      
      
        K
        ×
        K
      
    
  



is a diagonal matrix with





  
    
      Π
      
        i
        ,
        kk
      
      0
    
    =
    
      w
      ik
      0
    
  
  ,




which is positive-definite. Equation 13 (Eq. 13) shows approximated quadratic constraints:





  {
  
    
      
        
          
            
              Q
              ⁡
              
                (
                
                  
                    
                      μ
                      ik
                    
                    -
                    
                      μ
                      ik
                      0
                    
                  
                  ,
                  
                    Σ
                    ik
                    0
                  
                
                )
              
            
            ≤
            
              ρ
              1
              2
            
          
        
        
          
            (
            
              1
              ≤
              k
              ≤
              K
            
            )
          
        
      
      
        
          
            
              Q
              ⁡
              
                (
                
                  
                    
                      σ
                      ik
                    
                    -
                    
                      σ
                      ik
                      0
                    
                  
                  ,
                  I
                
                )
              
            
            ≤
            
              2
              ⁢
              
                ρ
                2
                2
              
            
          
        
        
          
            (
            
              1
              ≤
              k
              ≤
              K
            
            )
          
        
      
      
        
          
            
              Q
              ⁡
              
                (
                
                  
                    
                      ω
                      i
                    
                    -
                    
                      ω
                      i
                      0
                    
                  
                  ,
                  
                    Π
                    i
                    0
                  
                
                )
              
            
            ≤
            
              ρ
              3
              2
            
          
        
        
          
            
          
        
      
    
     
  




Accordingly, all the constraints possess the form in Eq. 6, and general solutions can be applied directly for means, variances, and Gaussian weights.
Critical Points and Solutions
An exemplary technique determines a search direction for parameters of Gaussian mixture CDHMMs. According to this technique, critical points are derived based upon the general DT framework of Eq. 2, then concrete forms of the search directions for mean, variance and Gaussian weights are given.
According to the general assumptions in DT, the derivative of the objective function of Eq. 2 can be derived with respect to any model parameter and it can be represented as:




  
    ∇
    
      F
      ⁡
      
        (
        λ
        )
      
    
  
  =
  
    
      
        ∂
        
          ∂
          λ
        
      
      ⁢
      
        F
        ⁡
        
          (
          λ
          )
        
      
    
    =
    
      
        ∑
        i
      
      ⁢
      
        
          ∑
          
            k
            =
            1
          
          K
        
        ⁢
        
          
            O
            ik
          
          ⁡
          
            (
            
              
                ∂
                
                  ∂
                  λ
                
              
              ⁢
              
                log
                ⁡
                
                  (
                  
                    
                      ω
                      ik
                    
                    ·
                    
                      N
                      ⁡
                      
                        (
                        
                          
                            
                              x
                              rt
                            
                            ;
                            
                              μ
                              ik
                            
                          
                          ,
                          
                            Σ
                            ik
                          
                        
                        )
                      
                    
                  
                  )
                
              
            
            )
          
        
      
    
  




Concrete gradients and critical points of all the parameters in a Gaussian mixture CDHMM are given and then the aforementioned case conditions to facilitate applying the general CLS solution shown in Table 1000 are summarized. A general occupancy of each kernel is given as γik=Oik(1).

For mean vectors:




  
    ∇
    
      F
      ⁡
      
        (
        
          μ
          ik
        
        )
      
    
  
  =
  
    
      Σ
      ik
      
        -
        1
      
    
    ⁢
    
      {
      
        
          
            O
            ik
          
          ⁡
          
            (
            x
            )
          
        
        -
        
          
            γ
            ik
          
          ⁢
          
            μ
            ik
          
        
      
      }
    
  




The critical point is obtained by vanishing the equation to zero. Given a quadratic constraint, the general solution can be directly applied to mean vectors. Noting that the Laplacian operator of the objective function is semi-definite and the critical point cannot be a saddle point. Actually, the critical point is a maximum when the general occupancy is greater than zero and a minimum when the Oik(1)<0. To use the solutions presented in Table 1000 of FIG. 10, various case conditions are summarized in Table 1100 of FIG. 11.

For variances in a logarithm domain:




  
    ∇
    
      F
      ⁡
      
        (
        
          σ
          ik
        
        )
      
    
  
  =
  
    
      
        Σ
        ik
        
          -
          1
        
      
      
        2
        ⁢
        
          γ
          ik
        
      
    
    ⁢
    
      {
      
        
          
            γ
            ik
          
          ⁢
          
            
              O
              ik
            
            ⁡
            
              (
              
                x
                2
              
              )
            
          
        
        -
        
          
            O
            ik
            2
          
          ⁡
          
            (
            x
            )
          
        
        -
        
          
            γ
            ik
            2
          
          ⁢
          
            exp
            ⁡
            
              (
              
                σ
                ik
              
              )
            
          
        
      
      }
    
  




By vanishing to zero, the following critical point can be found:





  
    σ
    ik
    *
  
  =
  
    log
    ⁢
    
      
    
    ⁢
    
      
        
          
            γ
            ik
          
          ⁢
          
            
              O
              ik
            
            ⁡
            
              (
              
                x
                2
              
              )
            
          
        
        -
        
          
            O
            ik
            2
          
          ⁡
          
            (
            x
            )
          
        
      
      
        γ
        ik
        2
      
    
  




Given the approximated quadratic constraint:

Q(σik−σik0,I)≦ρ22 

the general solution can also be applied to variances. Noting that the Laplacian of the objective function, whether σ*ik is a minimum or maximum, is also determined by γik. Table 1200 of FIG. 12 summarizes the case conditions for variances.

For Gaussian weights:




  
    ∇
    
      F
      ⁡
      
        (
        
          ω
          i
        
        )
      
    
  
  =
  
    
      
        Π
        i
        
          -
          1
        
      
      ⁡
      
        (
        
          
            γ
            
              i
              ⁢
              
                
              
              ⁢
              1
            
          
          ,
          
            γ
            
              i
              ⁢
              
                
              
              ⁢
              2
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            γ
            iK
          
        
        )
      
    
    T
  




To guarantee the updated mixture weights form a valid discrete probability distribution, an exemplary approach performs a constrained line search along a projected gradient direction. Hence, the gradient is projected into the hyperplane of Σkwik=1, to satisfy the constraints of mixture weights. The projection can be represented as:





  
    d
    ⁡
    
      (
      
        ω
        i
      
      )
    
  
  =
  
    
      ∇
      
        F
        ⁡
        
          (
          
            ω
            i
            0
          
          )
        
      
    
    -
    
      
        
          1
          K
        
        ⁡
        
          [
          
            
              ∇
              
                F
                ⁡
                
                  (
                  
                    ω
                    i
                    0
                  
                  )
                
              
            
            ·
            u
          
          ]
        
      
      ⁢
      u
    
  




To obtain the solution, Case 4 of Table 1000 is followed along with use of the search direction given above.

Trial Results

To verify the effectiveness of an exemplary CLS optimization method, trials were performed on several benchmark speech recognition tasks, including connected digit string recognition using the TIDIGITS database, continuous speech recognition using the Resource Management (RM) database, and large vocabulary continuous speech recognition using the Switchboard (both the mini-train set and full h5train00 training set) database. Trial setups are summarized in Table 1300 of FIG. 13. In the trials, the trial exemplary CLS method was compared to a conventional EBW method for the criterion of MMI and other criteria with higher error resolution, such as MPE and MD. For all trials using EBW, kernel dependent smoothing factor was set to twice of the corresponding denominator occupancy. When applying EBW to MPE training, I-smoothing was used with a factor set to 100 in each iteration. Some of the trial recognition results are summarized in Table 1400 of FIG. 14. Additional results are summarized in Table 1500 of FIG. 15.
Exemplary Computing Device
FIG. 16 shows various components of an exemplary computing device 1600 that may be used to implement part or all of various exemplary methods discussed herein.
The computing device shown in FIG. 16 is only one example of a computer environment and is not intended to suggest any limitation as to the scope of use or functionality of the computer and network architectures. Neither should the computer environment be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the example computer environment.
With reference to FIG. 16, an exemplary system for implementing an exemplary optimization technique for speech recognition or other tasks that may rely on CDHMMs. In a very basic configuration, computing device 1600 typically includes at least one processing unit 1602 and system memory 1604. Depending on the exact configuration and type of computing device, system memory 1604 may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. System memory 1604 typically includes an operating system 1605, one or more program modules 1606, and may include program data 1607. This basic configuration is illustrated in FIG. 16 by those components within dashed line 1608.
The operating system 1605 may include a component-based framework 1620 that supports components (including properties and events), objects, inheritance, polymorphism, reflection, and provides an object-oriented component-based application programming interface (API), such as that of the .NETTM Framework manufactured by Microsoft Corporation, Redmond, Wash.
Computing device 1600 may have additional features or functionality. For example, computing device 1600 may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated in FIG. 16 by removable storage 1609 and non-removable storage 1610. Computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory 1604, removable storage 1609 and non-removable storage 1610 are all examples of computer storage media. Thus, computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device 1600. Any such computer storage media may be part of device 1600. Computing device 1600 may also have input device(s) 1612 such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 1614 such as a display, speakers, printer, etc. may also be included. These devices are well know in the art and need not be discussed at length here.
Computing device 1600 may also contain communication connections 1616 that allow the device to communicate with other computing devices 1618, such as over a network. Communication connection(s) 1616 is one example of communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, or other data storage structure. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. The term computer readable media as used herein includes both storage media and communication media.
Various modules and techniques may be described herein in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. for performing particular tasks or implement particular abstract data types. These program modules and the like may be executed as native code or may be downloaded and executed, such as in a virtual machine or other just-in-time compilation execution environment. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.
An implementation of these modules and techniques may be stored on or transmitted across some form of computer readable media. Computer readable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer readable media may comprise “computer storage media” and “communications media.”
An exemplary computing device may include a processor, a user input mechanism (e.g., a mouse, a stylus, a scroll pad, etc.), a speaker, a display and control logic implemented at least in part by the processor to implement one or more of the various exemplary methods described herein for speech recognition. For speech recognition, such a device may be a cellular telephone or generally a handheld computer.
One skilled in the relevant art may recognize, however, that the techniques described herein may be practiced without one or more of the specific details, or with other methods, resources, materials, etc. In other instances, well known structures, resources, or operations have not been shown or described in detail merely to avoid obscuring aspects of various exemplary techniques. While various examples and applications have been illustrated and described, it is to be understood that the techniques are not limited to the precise configuration and resources described above. Various modifications, changes, and variations apparent to those skilled in the art may be made in the arrangement, operation, and details of the methods, systems, etc., disclosed herein without departing from their practical scope.

## Claims

1. One or more computer-readable storage media comprising computer-executable instructions that, when executed by one or more processors, configure the one or more processors to perform acts comprising:
imposing a constraint for discriminative training, the constraint limiting a difference between an initial continuous density hidden Markov model (CDHMM) parameter value and an updated CDHMM parameter value;
approximating an objective function as a smooth function of CDHMM parameters; and
performing a constrained line search on the smoothed function to optimize values of the CDHMM parameters.

2. The one or more computer-readable storage media of claim 1, wherein the CDHMM comprises a speech recognition CDHMM.

3. The one or more computer-readable storage media of claim 1, wherein the imposing comprising imposing a constraint based on Kullback-Leibler divergence (KLD).

4. The one or more computer-readable storage media of claim 3, wherein the KLD comprises a divergence between the initial CDHMM parameter value and the updated CDHMM parameter value.

5. The one or more computer-readable storage media of claim 1, wherein the smooth function comprises a function having a first derivative with respect to a CDHMM parameter.

6. The one or more computer-readable storage media of claim 1, wherein the performing a constrained line search comprises deciding if a critical point exists.

7. The one or more computer-readable storage media of claim 6, wherein, if a critical point exists, the performing comprises performing a constrained line search along a line joining an initial point and the critical point.

8. The one or more computer-readable storage media of claim 6, wherein, if a critical point does not exist, the performing comprises performing a constrained line search along a gradient direction at an initial point.

9. The one or more computer-readable storage media of claim 1, wherein the imposing a constraint comprises imposing a distortion constraint.

10. The one or more computer-readable storage media of claim 9,wherein the distortion constraint allows for approximating a smooth model in a region near an initial point.

11. The one or more computer-readable storage media of claim 9, wherein the approximating an objective function comprises approximating the objective function as a quadratic function.

12. The one or more computer-readable storage media of claim 11, wherein the quadratic function comprises roots.

13. The one or more computer-readable storage media of claim 1, wherein the performing comprises selecting a trust region.

14. The one or more computer-readable storage media of claim 13, wherein the trust region acts to ensure accuracy of a quadratic solution to the smooth function.

15. The one or more computer-readable storage media of claim 13, wherein the selection of a positive or a negative root depends on whether a critical point exists in a selected trust region.

16. The one or more computer-readable storage media of claim 1, wherein the performing decides if a critical point does not exist or if a saddle point exists for the smooth function.

17. The one or more computer-readable storage media of claim 1, wherein the CDHMM comprises a CDHMM for pattern recognition.

18. One or more computer-readable storage media comprising computer-executable instructions that, when executed by one or more processors, configure the one or more processors to perform acts comprising:
imposing a constraint for discriminative training based on Kullback-Leibler divergence between an initial continuous density hidden Markov model (CDHMM) parameter value and an updated CDHMM parameter value;
approximating an objective function as a smooth function of CDHMM parameters; and
performing a constrained line search on the smoothed function to optimize values for the CDHMM parameters.

19. The one or more computer-readable storage media of claim 18, further comprising providing data and recognizing speech using optimized values.

20. A computing device comprising:
a processor;
memory coupled to the processor; and
control logic, maintained on the memory and operable on the processor, to impose a constraint for discriminative training, the constraint limiting a difference between an initial continuous density hidden Markov model (CDHMM) parameter value and an updated CDHMM parameter value, to approximate an objective function as a smooth function of CDHMM parameters and to perform a constrained line search on the smoothed function to optimize values for the CDHMM parameters.