Signed-Weight Boosting of Class-Conditional Mixtures

A mixture classifier models each class as a weighted sum of simple bumps, such as Gaussians, and classifies with Bayes' rule. That gives it two jobs at once: it should place bumps where each class's data actually lies, so it can score new inputs, flag outliers and handle missing features, and it should place bumps where they separate classes. Training both jobs jointly with one weighted loss is known to go badly. Raising the classification weight damages the density model, lowering it blurs the decision boundary, and joint gradient descent over all components collapses several components onto the same mode. Greedy component addition, which builds a mixture one bump at a time with earlier bumps frozen, avoids the collapse. So far it has served either density fitting alone or, in one 2007 method, binary discrimination alone.

We propose to derive the greedy step directly from a hybrid objective, meaning conditional log-likelihood of labels plus $\lambda$ times joint log-likelihood. The derivative of this objective with respect to adding one bump to class $c$ has a simple closed form. It is a weighted sum over training points, and the weights are signed. Points of class $c$ pull the new bump toward them in proportion to how misclassified they are, plus a constant $\lambda$ that ensures density coverage. Points of other classes push it away in proportion to how strongly the model already, wrongly, assigns them to $c$. The result is a natively multi-class procedure in which every added component is chosen by one criterion that trades off covering data against separating classes. A held-out version of the same derivative gives a stopping rule, and the procedure needs neither MCMC nor large matrix inversions.

Core Claim

Let $p(x, c) = \pi_c\, q_c(x)$ be the model, where $q_c$ is class $c$'s mixture density and $\pi_c$ its prior. Training maximizes

$$\mathcal{L} = \sum_i \log p(y_i \mid x_i) + \lambda \sum_i \log p(x_i, y_i),$$

where $(x_i, y_i)$ are training pairs and $\lambda \ge 0$ sets how much the density term counts. Adding a candidate component $g$ to class $c$ as $q_c \leftarrow (1-\alpha) q_c + \alpha g$ changes the objective at rate

$$\frac{\partial \mathcal{L}}{\partial \alpha}\Big|_{\alpha=0} = \sum_i w_i^{(c)} \left(\frac{g(x_i)}{q_c(x_i)} - 1\right), \qquad w_i^{(c)} = \mathbb{1}[y_i = c]\,\big(1 - p(c \mid x_i) + \lambda\big) - \mathbb{1}[y_i \ne c]\, p(c \mid x_i).$$

This one formula settles a tension in the literature. Generative boosting rewards a new component for covering mass the mixture fails to explain; that is the $\lambda/q_c$ part. Discriminative boosting rewards it for sitting where classification is wrong; that is the residual part. The negative weights add an explicit repulsion from confidently confused other-class points, and no existing greedy mixture method has this term.

At $\lambda = 0$ in the binary case, the positive weights take roughly the residual-over-density form of BxCML. As $\lambda \to \infty$, the procedure becomes ordinary greedy density fitting run per class. The claim we will test is that intermediate $\lambda$, chosen once, gives a mixture head with three properties together. Its accuracy should match discriminative mixture heads. Its held-out per-class log-likelihood should stay close to a purely generative greedy mixture. And it should reach both with fewer components than joint optimization of the same model family needs.

Relation to Prior Work

The supporting method comes from greedy mixture learning. Mixture Density Estimation shows that adding one component at a time reaches $O(1/k)$ approximation error independent of dimension. Efficient Greedy Learning of Gaussian Mixture Models shows empirically that this avoids the initialization traps of joint EM. We reuse that construction but change the objective. Universal Boosting Variational Inference adds components by matching a Hellinger-distance residual and then refits all weights convexly. It also shows that naive greedy objectives degenerate, with variances collapsing to zero on heavy-tailed targets. That negative result constrains our design: we use a covariance floor and a bounded square-root version of the selection score as a fallback (see Research Program). Statistical guarantees for boosting assume the per-step search is solved exactly, and Statistical Guarantees and Algorithmic Convergence Issues of Variational Boosting shows this fails under stochastic estimation. We therefore make no rate claims for the hybrid case and measure behavior empirically.

The closest existing work is A recursive method for discriminative mixture learning (BxCML). It reweights samples by classification residual divided by joint density, refits a generative component by weighted maximum likelihood, and handles multi-class tasks only through one-vs-one binarization. Our step differs in three ways. It is derived per class for any number of classes. It contains the negative repulsion weights that a positive-weight maximum-likelihood refit cannot express. And it carries an explicit density-coverage term $\lambda$ that BxCML lacks. Its 2007 evaluation on Australian Sign Language is our main head-to-head point.

Two lines of work show why the problem matters. A Discriminative Gaussian Mixture Model with Sparsity (SDGM) shows that a softmax head equals a one-Gaussian-per-class mixture and that multi-component heads help. However, SDGM begins with too many components, prunes them with sparse Bayesian learning at cubic cost, and does not model $p(x)$. We build bottom-up instead, and the model keeps a usable density. The joint-loss hybrids, Learning Algorithms for the Classification Restricted Boltzmann Machine and Max-Margin Deep Generative Models, report that the discriminative weight trades directly against generative quality. Our proposal tests whether making that trade per component, rather than through one global weight, moves the frontier.

The decoupled score-space hybrids, Hybrid generative-discriminative classification using posterior divergence and Fisher Kernels for Logical Sequences, never let classifier errors change the generative model. Our signed weights are exactly that feedback channel.

Research Program

The algorithm starts each class with one component fit by maximum likelihood. It then repeats three steps. First, it computes the signed point scores $w_i^{(c)}/q_c(x_i)$ for every class. Second, for each class it searches for the component $g$ that maximizes the derivative above, using several restarts with Adam. Restarts are seeded at the highest-scoring misclassified points, which addresses the selection cost noted in the UBVI paper. Third, it adds the best (class, component) pair, chooses $\alpha$ by line search on the actual objective, and briefly refits all mixing weights by gradient ascent.

Because negative weights can push a Gaussian to shrink onto a single high-scoring point, we impose a covariance floor. We also compare against a bounded alternative that scores $\sqrt{g}$ against the signed residual, following UBVI. The stopping rule comes from the derivative itself. We hold out 10% of the training data, and growth stops when no candidate has a positive derivative on that split. This targets both the missing-stopping-rule problem and the overfitting that the FKL boosting study observed, where held-out likelihood fell as components were added (Variational refinement for importance sampling using the forward Kullback-Leibler divergence).

The component families are full-covariance Gaussians for vector features, HMMs for the sign-language sequences, and multinomials for text. For HMMs and multinomials, a weighted-EM fit on the positive weights provides a warm start, followed by gradient ascent on the full signed score. For perceptual data we apply the method as a head on frozen backbone features, matching SDGM's setting. The backbone itself is not boosted.

We will also analyze where components land. For each added component we record the fraction of its responsibility mass on misclassified points versus high-density interior points, and how that fraction shifts with $\lambda$. This directly measures the mode-versus-boundary tension.

Baselines

The naive reference is a softmax head (logistic regression) on the same features. SDGM reports 3.19% error for softmax on its 2D MNIST features, against 1.81% for SDGM (A Discriminative Gaussian Mixture Model with Sparsity). A density-free model like this cannot score inputs, so for density tasks it is paired with a separately fit greedy GMM.

The strongest discriminative-mixture competitor on vectors is SDGM. It is the most capable existing multi-component head, it chooses its own component count, and it reports 9.1% error on Ripley's synthetic data and 1.81% on MNIST 2D features. We rerun it on identical features and splits with its published settings. Beating it means matching or improving error with fewer active components, while also providing held-out density that SDGM cannot.

On sequences, the strongest competitor is BxCML itself, which reports 5.18% error on Australian Sign Language against 10.90% for a Fisher-kernel SVM (A recursive method for discriminative mixture learning). We reimplement it with the same HMM components and component budget. Beating it means lower error at an equal number of components. We also expect it to need fewer total components than the one-vs-one decomposition, which multiplies models by the number of class pairs.

On text, the hybrid ClassRBM reports 23.8% error on 20 Newsgroups against 32.8% for an SVM (Learning Algorithms for the Classification Restricted Boltzmann Machine). It is a joint-loss hybrid with a different model class, so it serves as context rather than a matched comparison. The convolutional max-margin model's 0.45% on MNIST (Max-Margin Deep Generative Models) uses an end-to-end trained backbone and is likewise context only.

The ablations that isolate the key ingredient all use the same Gaussian family and component budget. Joint-SGD training of the hybrid loss with fixed $K$ tests whether greedy addition matters. Greedy addition at $\lambda \to \infty$ is purely generative boosting per class. Greedy addition with negative weights clipped to zero is a native multi-class BxCML-style variant, and it tests whether repulsion matters. All variants get the same number of restarts and Adam steps per component, and $\lambda$ and the joint-loss weight receive the same validation grid.

Why not just…?

Why not just fit a separate greedy GMM per class and apply Bayes' rule? This is the $\lambda \to \infty$ endpoint, and it is a genuine threat on well-separated data, where good density estimates already yield good boundaries. Its known weakness is that it spends components on high-density interiors that do not affect the decision. The decoupled-generative Fisher SVM's 10.90% versus BxCML's 5.18% on sign language points that way. Our matched-$K$ accuracy curves settle the question. If the generative endpoint matches the hybrid's accuracy on all four benchmarks, the discriminative term is unnecessary and we will report that.

Why not just use softmax for classification and a separate density model for outliers? This decoupled pair is simpler and may match us on clean, unimodal-per-class features. It loses only where classes have subgroups, as in SDGM's 3.19% versus 1.81%, or where the density model must be compact. We compare at an equal total parameter count, and we report both accuracy and held-out-class detection.

Why not just train the mixture head jointly with SGD, or over-provision and prune like SDGM? The joint-loss hybrids document the accuracy-versus-likelihood conflict, and SDGM's pruning costs cubic time. Whether greedy construction actually moves the frontier, rather than just being slower, is the central empirical question. We answer it by plotting both methods' (error, held-out log-likelihood) pairs across their weight grids at matched $K$.

Proposed Experiments

The classification benchmarks are Ripley's synthetic data and MNIST 2D features, following the SDGM protocol; Australian Sign Language, following the BxCML protocol; and 20 Newsgroups with multinomial components. Density quality is measured as held-out per-class log-likelihood on these same datasets, against the generative greedy endpoint.

For image features we use SVHN-Remix rather than the official split, because The SVHN Dataset Is Deceptive for Probabilistic Generative Models Due to a Distribution Mismatch shows the official train and test sets differ (FID 16.7 versus 3.3 between training splits). That difference would corrupt any likelihood comparison. On SVHN-Remix features we hold out two digit classes and measure detection of those classes using $\log \sum_c p(x, c)$. No reported result was found on Lacuna for this held-out-class detection task, so all numbers will come from our own matched runs.

As a secondary test, we drop features at test time on Abalone and compare exact marginalization under the mixture against imputation followed by a discriminative classifier, mirroring the NRGBoost argument (NRGBoost: Energy-Based Generative Boosted Trees). No explicit number was found on Lacuna for NRGBoost's Abalone result.

Three checks decide whether the idea holds. First, at intermediate $\lambda$, the method must strictly dominate the joint-SGD frontier in (error, held-out log-likelihood) on at least three of four benchmarks. Second, removing the negative weights must measurably raise error at matched $K$ on the multi-class benchmarks, which shows that repulsion, not just multi-class handling, matters. Third, the held-out stopping rule must reach within one standard error of the best-validated $K$ without a sweep. If the first check fails, the claim reduces to "greedy ≈ joint," and the proposal's value would rest only on the stopping rule and on native multi-class support.