On the Stability of a non-hyperbolic nonlinear map with non-bounded set of non-isolated fixed points with applications to Machine Learning

Lautaro Estienne, R. O. Hansen, Matías Vera, Luciana Ferrer, Pablo Piantanida

Abstract

This paper investigates the convergence properties of the Semi-Unsupervised Calibration through Prior Adaptation (SUCPA) algorithm, a method designed to correct the probability scores of supervised machine learning classifiers under conditions of prior shift. We model the algorithm as a discrete dynamical system defined by first-order non-linear difference equations. The resulting map is non-hyperbolic and possesses a non-bounded set of non-isolated fixed points, presenting unique challenges for standard stability analysis. Using an ad-hoc geometrical approach, we rigorously prove that the map is globally asymptotically stable for binary classification problems. Numerical experiments across Large Language Model (LLM) sentiment analysis, image classification, and natural language inference support our theoretical findings and suggest that the stability holds for multi-class scenarios.

1. Introduction

Modern machine learning models, ranging from Large Language Models to deep convolutional neural networks, frequently exhibit miscalibration. A model is considered miscalibrated when its predicted probability scores do not accurately reflect the empirical likelihood of the predicted outcome. This issue is often exacerbated by prior shift, where the class distribution in the deployment environment (test data) differs significantly from the distribution encountered during training.

To address this, the SUCPA algorithm was developed to adapt model outputs without requiring additional labeled data. While SUCPA has demonstrated empirical success, its mathematical foundations remained largely unexamined. This paper provides the first rigorous proof of its stability, treating the algorithm as a $K$-dimensional nonlinear map where $K$ represents the number of classes.

2. The SUCPA Algorithm as a Dynamical System

The SUCPA algorithm functions by iteratively updating class probabilities. Mathematically, this can be expressed as a composition of exponential and rational functions. When analyzed as a dynamical system, several unique properties emerge:

  • Jacobian Analysis: The Jacobian matrix of the SUCPA map is a regular transition probability matrix. This structure implies that the system always possesses at least one eigenvalue equal to 1.
  • Non-Hyperbolicity: Because of the unit eigenvalue, the system is non-hyperbolic. Standard stability theorems, such as the Hartman-Grobman theorem, are inapplicable because the fixed points are not isolated; instead, they form an infinite, unbounded line (or hyperplane in higher dimensions).
  • The Line of Stability: The algorithm does not converge to a single point but rather to a specific line of fixed points. If the initial input is shifted by a constant across all classes, the resulting fixed point shifts by that same constant, maintaining the relative relationships between class scores.

3. Convergence Proof: A Geometrical Approach

Given the failure of standard Lyapunov functions to easily describe non-isolated fixed points, we developed an ad-hoc geometrical approach to prove stability for the binary ($K=2$) case. By defining specific monotone auxiliary functions, we demonstrate that any initial state is eventually "pulled" toward the stable line of fixed points. In this two-dimensional space, the trajectory of the algorithm becomes tangent to a line defined by the ratio of the class proportions ($N_1/N_2$), ensuring global asymptotic stability.

4. Experimental Validation

We validated our theoretical results through numerical experiments on three distinct tasks:

  1. Sentiment Polarity (SST-2): Using a GPT-2 model, we observed that SUCPA converged extremely rapidly, often requiring fewer than 5 iterations to reach the stable line.
  2. Image Classification (Asirra Dogs vs. Cats): Using a ResNet-18 model, the algorithm remained stable and reached the same theoretical limit, though it required significantly more iterations (up to 200) compared to the LLM task.
  3. Natural Language Inference (MNLI): To test the multi-class ($K=3$) scenario, we applied SUCPA to the MNLI dataset. While the formal proof is currently limited to $K=2$, the numerical evidence for $K=3$ showed identical stable behavior, supporting the conjecture that the algorithm is globally stable for any number of classes.

5. Limitations and Future Work

While this work establishes a rigorous foundation for SUCPA, two primary areas for future research remain. First, the formal mathematical proof for $K > 2$ remains a conjecture, despite strong numerical support. Second, SUCPA is sensitive to the accuracy of the estimated class proportions ($N_k$) in the test set. If these priors are incorrectly estimated, the calibration performance degrades significantly. Future work will focus on a sensitivity analysis to determine the error tolerances of the system and the development of a generalized Lyapunov function for this class of non-hyperbolic maps.

6. Conclusion

By framing the SUCPA algorithm as a discrete dynamical system, we have provided a rigorous explanation for its empirical success. The proof of global asymptotic stability in the binary case, combined with multi-class numerical evidence, confirms that SUCPA is a robust method for classifier calibration under prior shift. The code for all experiments is available at: https://github.com/LautaroEst/sucpa-convergence.

Summary updated

Abstract

This paper deals with the convergence analysis of the SUCPA (Semi Unsupervised Calibration through Prior Adaptation) algorithm, defined from a first-order non-linear difference equations, first developed to correct the scores output by a supervised machine learning classifier. The convergence analysis is addressed as a dynamical system problem, by studying the local and global stability of the nonlinear map derived from the algorithm. This map, which is defined by a composition of exponential and rational functions, turns out to be non-hyperbolic with a non-bounded set of non-isolated fixed points. Hence, a non-standard method for solving the convergence analysis is used consisting of an ad-hoc geometrical approach. For a binary classification problem (two-dimensional map), we rigorously prove that the map is globally asymptotically stable. Numerical experiments on real-world application are performed to support the theoretical results by means of two different classification problems: Sentiment Polarity performed with a Large Language Model and Cat-Dog Image classification. For a greater number of classes, the numerical evidence shows the same behavior of the algorithm, and this is illustrated with a Natural Language Inference example. The experiment codes are publicly accessible online at the following repository: https://github.com/LautaroEst/sucpa-convergence
BibTeX
@misc{estienne2024stability,
  author = {Lautaro Estienne and R. O. Hansen and Matías Vera and Luciana Ferrer and Pablo Piantanida},
  title = {{On the Stability of a non-hyperbolic nonlinear map with non-bounded set of non-isolated fixed points with applications to Machine Learning}},
  year = {2024},
  eprint = {2401.03051},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.03051},
}
Figure