A fast optimization method for large margin estimation of HMMs based on second order cone programming

Yan Yin, Hui JiangInterspeech 2007

TL;DR

This paper introduces a faster, more memory-efficient method for training large margin Hidden Markov Models (HMMs) for speech recognition. By reformulating the optimization problem as a Second Order Cone Program (SOCP), they achieve comparable accuracy to previous methods but with significant speedups and reduced computational resource demands, making large margin training more practical for large-scale systems.

What Problem Does This Paper Address?

Speech recognition systems often use Hidden Markov Models (HMMs) to model the temporal nature of speech. Traditionally, these HMMs are trained using Maximum Likelihood Estimation (MLE), which can lead to models that generalize poorly to new data. Large Margin Estimation (LME) aims to improve generalization by ensuring a clear separation margin between the correct speech utterance and all other possible utterances.

However, solving the LME problem for continuous density HMMs (CDHMMs) results in a complex minimax optimization problem. Previous attempts to solve this included iterative localized optimization (ILO), constrained joint optimization (CJO), and semidefinite programming (SDP). While the SDP approach offered global optimality and good performance, it suffered from extremely high computational costs (both time and memory), especially as the number of Gaussian components in the HMMs increased. This made it impractical for state-of-the-art speech recognition systems that often involve tens or hundreds of thousands of Gaussians. The authors sought a method that could achieve the benefits of LME without the prohibitive computational burden of SDP.

Methods

The core contribution of this paper is the formulation of the LME problem for CDHMMs as a Second Order Cone Programming (SOCP) problem. SOCP is a class of convex optimization problems that can be solved efficiently. The authors propose a new convex relaxation condition that allows the LME problem to be transformed into an SOCP.

Key steps in their method include:

  • Reformulating the margin: The original minimax margin maximization problem is converted into a minimization problem with an added variable p representing the margin.
  • Spherical Constraint: A spherical constraint is introduced to ensure the boundedness of the margin, similar to previous SDP approaches.
  • SOCP Formulation: The constraints derived from the LME objective and the spherical constraint are then carefully reformulated into the standard form of SOCP constraints. This involves manipulating quadratic forms and introducing auxiliary variables (z_k) to represent certain terms.
  • Relaxation: A crucial step involves a relaxation of a non-convex constraint into a convex one, enabling the entire problem to be cast as an SOCP. This relaxation is key to achieving the computational benefits.
  • Optimization Tool: The resulting SOCP problem is solved using an off-the-shelf SOCP solver (MOSEK 4.0).

Datasets

  • TIDIGITS: The experiments were conducted on the TIDIGITS database, specifically using the adult portion for connected digit string recognition.
  • Training set: 8623 digit strings from 112 speakers.
  • Test set: 8700 digit strings from 113 speakers.
  • The models used were 11 whole-word CDHMMs representing digits, with varying numbers of Gaussian mixture components per state (from 1 to 32).

Key Insights and Ideas

  • SOCP as a Practical Alternative to SDP: The paper demonstrates that SOCP can effectively solve the LME problem, offering a more computationally feasible alternative to the previously dominant SDP approach.
  • Efficiency Gains: The primary insight is the dramatic improvement in computational efficiency. By reformulating the problem into SOCP, the optimization variable size becomes proportional to the number of Gaussians, not the square of it (as in SDP), leading to significant speedups and memory reductions.
  • Global Optimality Guarantee: Like SDP, SOCP is a convex optimization problem, meaning that algorithms can guarantee finding the globally optimal solution, avoiding the local optima issues of gradient-based methods.
  • Trade-off in Relaxation: The authors acknowledge that their SOCP formulation involves a relaxation, meaning the solution is an approximation to the true LME problem. However, the experimental results suggest this approximation is highly effective.

Key Results

  • Performance: The LME/SOCP method achieved comparable accuracy to the LME/SDP approach on the TIDIGITS dataset. It also outperformed the gradient descent (GRAD) method, except in the case of the largest model (32-mix).
  • Efficiency:
    • Speed: The LME/SOCP method was 20-200 times faster per iteration than the LME/SDP method. This speed advantage increased significantly with larger model sizes.
  • Memory: The SOCP method consumed substantially less memory compared to SDP.
  • Practicality: The SOCP method is described as "relatively easy to run," contrasting with gradient descent methods that require extensive parameter tuning.

Limitations and Future Work

  • Approximation: The authors acknowledge that the SOCP formulation involves a relaxation, meaning the solution is an approximation to the original LME problem.
  • Future Work: The paper suggests extending the LME/SOCP method to larger-scale speech recognition systems that involve tens or hundreds of thousands of Gaussians. The authors are currently pursuing this and plan to report results in the future.

Summary updated

BibTeX
@inproceedings{yin2007fast,
  author = {Yan Yin and Hui Jiang},
  title = {{A fast optimization method for large margin estimation of HMMs based on second order cone programming}},
  booktitle = {Interspeech},
  year = {2007},
}
Figure