Efficient Optimization for Discriminative Latent Class Models

Armand Joulin, Francis R. Bach, Jean PonceNeurIPS 2010 · OpenReview

Introduction

In machine learning, latent representations—hidden layers of information—are frequently used to simplify complex data. In supervised learning, these representations must be discriminative, meaning they should specifically aid in predicting a label, such as a category for a text document.

The standard tool for training these models is the Expectation-Maximization (EM) algorithm. However, EM suffers from a significant drawback: it relies on a non-convex cost function. In high-dimensional spaces, EM frequently gets trapped in local maxima, leading to sub-optimal models. Furthermore, many existing generative models do not necessarily lead to the best predictive accuracy. To address this, researchers have introduced the Discriminative Latent Class (DLC) model, a probabilistic approach to dimensionality reduction that prioritizes predictive performance while remaining easy to optimize globally.

The Discriminative Latent Class (DLC) Model

The DLC model follows a simple Markov chain structure: Input ($x$) $\to$ Latent Class ($z$) $\to$ Output Label ($y$).

Unlike Restricted Boltzmann Machines (RBMs) that use complex softmax functions for both steps, the DLC model assumes the probability of a label given a latent class is linear. This subtle change is crucial because it allows for a much simpler mathematical approximation. By treating the output as a linear combination of latent classes, the authors bridge the gap between probabilistic modeling and classical ridge regression.

Overcoming EM's Local Optima

To fix the EM "local maxima" problem, the authors use a second-order Taylor expansion to create a quadratic approximation of the log-likelihood. This approximation is significantly easier to optimize than the original non-convex function. The paper demonstrates that EM is fundamentally sound but requires a robust starting point. By using their quadratic approximation to initialize the model, they significantly boost the final performance of the EM procedure.

Minimizing this quadratic approximation is still technically challenging because it occurs over simplices (probabilities that must sum to 1). To handle this, the authors designed a specialized algorithm utilizing convex relaxations and low-rank matrix representations. This allows the model to scale to large datasets that would otherwise crash standard optimization toolboxes.

Experimental Results

The model was evaluated across two primary domains: text classification and synthetic clustering.

Text Classification

The authors tested the DLC model on the 20 Newsgroups dataset, a classic benchmark containing thousands of forum posts across 20 categories, focusing on specific binary classification tasks.

Text Classification Results on 20 Newsgroups

As shown above, the DLC model consistently outperformed standard baselines, including Linear SVMs, Supervised Latent Dirichlet Allocation (sLDA), and PCA+SVM across various sample sizes ($N$) and latent class counts ($K$).

Robustness to Noise in Clustering

To test how well the model finds clusters in messy data, the authors generated simulated data with varying levels of "noise dimensions."

Robustness to Noise Dimensions

The clustering simulations revealed that the DLC model maintains high accuracy even as the number of irrelevant noise dimensions increases. It significantly outperformed standard unsupervised methods like k-means and GMM, as well as Diffrac, a popular discriminative clustering method.

Key Insights

  • The "Spread vs. Clump" Balance: The quadratic approximation reveals a fascinating tension. One part of the formula tries to push every data point into its own distinct cluster, while the ridge regression term tries to spread them out equally. The DLC model effectively finds the optimal balance between these two extremes.
  • Computational Efficiency: The proposed low-rank optimization method proved to be much faster and more scalable than general-purpose Semidefinite Programming (SDP) solvers, making it highly practical for real-world applications.

Limitations and Future Directions

While powerful, the DLC model assumes that the input $x$ and output $y$ are independent once the latent class $z$ is known. While this simplifies the mathematics, it might be too restrictive for highly complex data where $x$ and $y$ share more intricate relationships.

Currently, the "experts" (latent classes) in the model provide constant predictions. Extending this to non-constant predictions—where each latent class has its own mini-regression model—would be a powerful next step. Finally, adapting this quadratic approximation technique to more complex models, such as Discriminative Restricted Boltzmann Machines, remains a promising avenue for future research.

Summary updated

Abstract

Dimensionality reduction is commonly used in the setting of multi-label supervised classification to control the learning capacity and to provide a meaningful representation of the data. We introduce a simple forward probabilistic model which is a multinomial extension of reduced rank regression; we show that this model provides a probabilistic interpretation of discriminative clustering methods with added benefits in terms of number of hyperparameters and optimization. While expectation-maximization (EM) algorithm is commonly used to learn these models, its optimization usually leads to local minimum because it relies on a non-convex cost function with many such local minima. To avoid this problem, we introduce a local approximation of this cost function, which leads to a quadratic non-convex optimization problem over a product of simplices. In order to minimize such functions, we propose an efficient algorithm based on convex relaxation and low-rank representation of our data, which allows to deal with large instances. Experiments on text document classification show that the new model outperforms other supervised dimensionality reduction methods, while simulations on unsupervised clustering show that our probabilistic formulation has better properties than existing discriminative clustering methods.
BibTeX
@inproceedings{joulin2010efficient,
  author = {Armand Joulin and Francis R. Bach and Jean Ponce},
  title = {{Efficient Optimization for Discriminative Latent Class Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=SkEB6PbdWH},
}
Figure