pith. sign in

arxiv: 2606.17181 · v1 · pith:YMTVYFLGnew · submitted 2026-06-15 · 📊 stat.ME · stat.AP

Tropical Viterbi Tubes for Decoding Uncertainty in Hidden Markov Models

Aur\'elien Nicosia This is my paper

Pith reviewed 2026-06-27 02:26 UTC · model grok-4.3

classification 📊 stat.ME stat.AP
keywords hidden Markov modelsViterbi decodingpathwise uncertaintycredible regionsmax-plus algebralatent trajectoryposterior superlevel sets
0
0 comments X

The pith

The tropical Viterbi tube collects every hidden trajectory whose complete-data log-score stays within tolerance of the Viterbi optimum and yields calibrated pathwise uncertainty bands.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the tropical Viterbi tube as the set of all complete latent paths in a fitted hidden Markov model whose joint log-likelihood lies inside a user-chosen tolerance of the single Viterbi path. Projections of this set onto individual time points, transitions, or change events produce bands that remain consistent with globally near-optimal trajectories. The tolerance is interpreted as a log posterior-odds penalty and can be chosen so the tube contains a target fraction of the posterior mass on path space, thereby serving as a highest-posterior-density credible region for the entire latent sequence. Exact computation of the tube and its projections uses max-plus forward-backward recursions that scale linearly with sequence length.

Core claim

Conditional on a fitted HMM, the tropical Viterbi tube is the superlevel set of complete-data log-scores within a tolerance of the Viterbi optimum; its state, transition and change-status projections give pathwise uncertainty bands, and the tolerance can be calibrated to a target posterior mass so that the tube functions as an HPD credible region for the full latent path.

What carries the argument

The tropical Viterbi tube, the set of hidden trajectories whose complete-data log-score lies within a tolerance of the Viterbi optimum, computed exactly by max-plus forward-backward recursions.

If this is right

  • Projected tubes can be obtained in O(T K^2) time for dense transition matrices.
  • Posterior tube mass and HPD calibration are obtained by separate forward-filtering backward-sampling calculations.
  • Monotonicity and step-function properties of the tube guarantee deterministic stability when the tolerance is varied.
  • In the bat-tracking example the method separates foraging and commuting segments by differential enrichment for feeding buzzes at a fixed tolerance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same superlevel-set construction could be applied to other dynamic-programming decoders that return a single optimum path.
  • The calibrated bands supply a direct, non-MCMC alternative to sampling-based credible sets for entire latent trajectories.
  • Robust segments identified by the tube could be used as input features for downstream event detectors without retraining the HMM.

Load-bearing premise

The tolerance can be interpreted and calibrated as a log posterior-odds loss relative to the Viterbi path so that the tube becomes an HPD credible region for the complete latent path.

What would settle it

Exact enumeration of all paths on a short sequence with small state space would show whether the tube mass equals the claimed posterior probability or whether the projected bands achieve nominal coverage under repeated simulation with known ground-truth paths.

read the original abstract

Hidden Markov models are widely used to infer latent state sequences from sequential data, but Viterbi decoding reports only one most likely complete path. When decoded states carry scientific meaning, this single maximizer can conceal pathwise uncertainty created by multiple near-optimal trajectories. Conditional on a fitted HMM, we introduce the tropical Viterbi tube: the set of hidden trajectories whose complete-data log-score lies within a tolerance of the Viterbi optimum. State, transition, and change-status projections show which local features remain compatible with globally near-optimal complete paths, giving a pathwise uncertainty layer for HMMs in sequence analysis, ecology, finance, biomedical monitoring, and related domains. The tube is a posterior superlevel set on complete hidden-path space, with tolerance interpreted as a log posterior-odds loss relative to a Viterbi path. Calibrating the tolerance to a target posterior mass gives an HPD-threshold credible region for the complete latent path and conservative simultaneous projected bands. We prove monotonicity, step-function behavior, and deterministic stability guarantees, and compute projected tubes exactly by max-plus forward-backward recursions in O(TK^2) time for dense transitions. Posterior tube mass and HPD calibration are separate pathwise calculations approximated by FFBS. In a public bat-tracking application, robust foraging tube segments are enriched for feeding buzzes, whereas robust commuting segments are depleted: at eta = 0.005, enrichment is 2.25 with 95% bootstrap interval (1.73, 2.85) for robust foraging and 0.27 with interval (0.16, 0.44) for robust commuting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. Conditional on a fitted HMM, the manuscript defines the tropical Viterbi tube as the set of hidden trajectories whose complete-data log-score lies within a tolerance of the Viterbi optimum. Projections of the tube yield pathwise uncertainty bands. The tolerance is interpreted as a log posterior-odds loss, so that calibrating it to a target posterior mass produces an HPD credible region for the complete latent path (with conservative simultaneous projected bands). The paper proves monotonicity, step-function behavior, and deterministic stability guarantees, computes exact projections via max-plus forward-backward recursions in O(TK²) time, and approximates posterior mass and HPD calibration via FFBS. An application to bat-tracking data shows that robust foraging segments are enriched for feeding buzzes while robust commuting segments are depleted.

Significance. If the results hold, the work supplies a direct, computationally tractable method for pathwise uncertainty quantification around Viterbi decoding that exploits the fact that complete-data log-score differences equal log posterior odds (normalizer cancels). The exact O(TK²) max-plus forward-backward algorithm for projections and the explicit demonstration that the tube is an HPD region by construction are clear strengths, as is the empirical illustration in the bat-tracking example. The approach is a natural extension of standard dynamic programming for HMMs.

minor comments (3)
  1. [Abstract] The abstract is lengthy and contains several distinct technical claims; condensing the description of the calibration step and the stability guarantees would improve readability.
  2. [Abstract] The connection between the 'tropical' nomenclature and max-plus algebra is used in the title and recursions but is not spelled out in the opening paragraph, which may slow readers unfamiliar with tropical geometry.
  3. [Application paragraph] In the bat-tracking application the bootstrap intervals are reported but the number of replicates and the precise resampling procedure are not stated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept. We are pleased that the contributions regarding the tropical Viterbi tube, its interpretation as an HPD region, the exact max-plus projection algorithm, and the bat-tracking application were viewed as strengths.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The tube is defined directly as the superlevel set of complete-data log-scores within tolerance of the Viterbi optimum. The observation that this equals a posterior superlevel set follows from cancellation of the marginal likelihood normalizer, a standard property of the complete-data likelihood that requires no additional assumptions or self-citations. Projected bands are obtained by standard max-plus dynamic programming extensions of Viterbi; monotonicity and stability are immediate consequences of the ordering. HPD calibration is handled by a separate FFBS Monte Carlo step whose inputs are the already-defined tube, not forced by the definition itself. No load-bearing self-citations, fitted inputs renamed as predictions, or ansatzes appear in the provided text.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard HMM generative model plus the new tube definition; the tolerance acts as a free parameter whose calibration is presented as an additional step.

free parameters (1)
  • tolerance eta
    User-chosen threshold on log-score difference that defines membership in the tube; calibrated to target posterior mass in the bat example at eta=0.005.
axioms (2)
  • domain assumption The complete-data log-score is a valid measure for comparing full hidden trajectories conditional on the fitted HMM parameters.
    Invoked when the tube is defined as a superlevel set on complete-data log-score space.
  • standard math Max-plus algebra operations correctly compute the required projections of the tube.
    Used to obtain the O(TK^2) exact algorithm for state, transition, and change-status projections.
invented entities (1)
  • tropical Viterbi tube no independent evidence
    purpose: Set of near-optimal complete hidden paths that supplies pathwise uncertainty quantification.
    New object introduced in the abstract; no independent evidence outside the paper is supplied.

pith-pipeline@v0.9.1-grok · 5822 in / 1525 out tokens · 36274 ms · 2026-06-27T02:26:15.407863+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 17 canonical work pages

  1. [1]

    AJI, S. M. and MCELIECE, R. J. (2000). The Generalized Distributive Law.IEEE Transactions on Information Theory46325–343. https://doi.org/10.1109/18.825794

    work page doi:10.1109/18.825794 2000

  2. [2]

    BACCELLI, F., COHEN, G., OLSDER, G. J. and QUADRAT, J.-P. (1992).Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley & Sons, New York

    1992

  3. [3]

    BROWN, D. G. and GOLOD, D. (2010). Decoding HMMs Using the k Best Paths: Algorithms and Applications. BMC Bioinformatics11S28. https://doi.org/10.1186/1471-2105-11-S1-S28 CAPPÉ, O., MOULINES, E. and RYDÉN, T. (2005).Inference in Hidden Markov Models. Springer, New York. https://doi.org/10.1007/0-387-28982-8

    work page doi:10.1186/1471-2105-11-s1-s28 2010

  4. [4]

    R., KROGH, A

    DURBIN, R., EDDY, S. R., KROGH, A. and MITCHISON, G. (1998).Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge

    1998

  5. [5]

    FORNEY, G. D. JR. (1973). The Viterbi Algorithm.Proceedings of the IEEE61268–278. https://doi.org/10.1109/PROC.1973.9030 GUÉDON, Y. (2007). Exploring the State Sequence Space for Hidden Markov and Semi-Markov Chains.Compu- tational Statistics & Data Analysis512379–2409. https://doi.org/10.1016/j.csda.2006.03.015

    work page doi:10.1109/proc.1973.9030 1973

  6. [6]

    and CYBENKO, G

    HERNANDO, D., CRESPI, V. and CYBENKO, G. (2005). Efficient Computation of the Hidden Markov Model Entropy for a Given Observation Sequence.IEEE Transactions on Information Theory512681–2685. https://doi.org/10.1109/TIT.2005.850223

    work page doi:10.1109/tit.2005.850223 2005

  7. [7]

    G., FLORES-MARTÍNEZ, J

    HURME, E., GURARIE, E., GREIF, S., HERRERAM., L. G., FLORES-MARTÍNEZ, J. J., WILKINSON, G. S. and YOVEL, Y. (2019a). Data from: Acoustic Evaluation of Behavioral States Predicted from GPS Tracking: A Case Study of a Marine Fishing Bat. doi:10.5441/001/1.kk3bg2f4. https://doi.org/10.5441/001/1.kk3bg2f4

    work page doi:10.5441/001/1.kk3bg2f4

  8. [8]

    YOVEL, Y. (2019b). Acoustic Evaluation of Behavioral States Predicted from GPS Tracking: A Case Study of a Marine Fishing Bat.Movement Ecology721. https://doi.org/10.1186/s40462-019-0163-7

    work page doi:10.1186/s40462-019-0163-7

  9. [9]

    IEEE Transactions on information theory , volume =

    KSCHISCHANG, F. R., FREY, B. J. and LOELIGER, H.-A. (2001). Factor Graphs and the Sum-Product Algo- rithm.IEEE Transactions on Information Theory47498–519. https://doi.org/10.1109/18.910572

    work page doi:10.1109/18.910572 2001

  10. [10]

    and MORALES, J

    LANGROCK, R., KING, R., MATTHIOPOULOS, J., THOMAS, L., FORTIN, D. and MORALES, J. M. (2012). Flexible and Practical Modeling of Animal Telemetry Data: Hidden Markov Models and Extensions.Ecology 932336–2342. https://doi.org/10.1890/11-2241.1

    work page doi:10.1890/11-2241.1 2012

  11. [11]

    and KOLOYDENKO, A

    LEMBER, J. and KOLOYDENKO, A. A. (2014). Bridging Viterbi and Posterior Decoding: A Generalized Risk Approach to Hidden Path Inference Based on Hidden Markov Models.Journal of Machine Learning Research 151–58

    2014

  12. [12]

    and STURMFELS, B

    MACLAGAN, D. and STURMFELS, B. (2015).Introduction to Tropical Geometry.Graduate Studies in Mathe- matics161. American Mathematical Society, Providence, RI

    2015

  13. [13]

    and THEODOSIS, E

    MARAGOS, P., CHARISOPOULOS, V. and THEODOSIS, E. (2021). Tropical Geometry and Machine Learning. Proceedings of the IEEE109728–755. https://doi.org/10.1109/JPROC.2021.3065238

    work page doi:10.1109/jproc.2021.3065238 2021

  14. [14]

    MCCLINTOCK, B. T. and MICHELOT, T. (2018). momentuHMM: R Package for Generalized Hidden Markov Models of Animal Movement.Methods in Ecology and Evolution91518–1530. https://doi.org/10.1111/2041- 210X.12995

    work page doi:10.1111/2041- 2018

  15. [15]

    TERSON, T. A. (2020). Uncovering Ecological State Dynamics with Hidden Markov Models.Ecology Letters 231878–1903. https://doi.org/10.1111/ele.13610

    work page doi:10.1111/ele.13610 2020

  16. [16]

    and STURMFELS, B

    PACHTER, L. and STURMFELS, B. (2004). Tropical Geometry of Statistical Models.Proceed- ings of the National Academy of Sciences of the United States of America10116132–16137. https://doi.org/10.1073/pnas.0406010101

    work page doi:10.1073/pnas.0406010101 2004

  17. [17]

    RABINER, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE77257–286. https://doi.org/10.1109/5.18626 TROPICAL VITERBI TUBES33

    work page doi:10.1109/5.18626 1989

  18. [18]

    and SUNDBERG, C.-E

    SESHADRI, N. and SUNDBERG, C.-E. W. (1994). List Viterbi Decoding Algorithms with Applications.IEEE Transactions on Communications42313–323. https://doi.org/10.1109/TCOMM.1994.577040

    work page doi:10.1109/tcomm.1994.577040 1994

  19. [19]

    and MARAGOS, P

    THEODOSIS, E. and MARAGOS, P. (2018). Analysis of the Viterbi Algorithm Using Tropical Algebra and Geom- etry. In2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)1–5. https://doi.org/10.1109/SPAWC.2018.8445777

    work page doi:10.1109/spawc.2018.8445777 2018

  20. [20]

    VITERBI, A. J. (1967). Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algo- rithm.IEEE Transactions on Information Theory13260–269. https://doi.org/10.1109/TIT.1967.1054010

    work page doi:10.1109/tit.1967.1054010 1967

  21. [21]

    ZUCCHINI, W., MACDONALD, I. L. and LANGROCK, R. (2016).Hidden Markov Models for Time Series: An Introduction Using R, 2 ed. Chapman and Hall/CRC. https://doi.org/10.1201/b20790

    work page doi:10.1201/b20790 2016