Pith. sign in

REVIEW 2 major objections 7 minor 41 references

Branch-and-bound method for calculating Viterbi path in triplet Markov models

T0 review · 2 major / 7 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Branch-and-bound can solve the maximal marginal problem in triplet Markov models, with simulated searches visiting orders of magnitude fewer paths than exhaustive enumeration.

desk verdict Solid branch-and-bound framework for exact MAP decoding in TMMs, but the printed Samuelson bound is invalid as written and the code link is empty; revision needed before the results are fully trustworthy. read the letter →

arxiv 2507.19338 v1 pith:NTK7U6KY submitted 2025-07-25 stat.CO cs.ITmath.IT

Oskar Soop , Jüri Lember This is my paper · ORCID
classification stat.COcs.ITmath.IT
keywords PairwiseMarkovmodelsHiddenMaximumaposterioriestimationmaximalmarginalproblembranchandboundViterbipathtripletm-Viterbiapproximation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tackles the maximal marginal problem: find the single most probable realization of a hidden process X in a model where only the joint process (X,U) is Markov, so X by itself is not and the classical Viterbi algorithm cannot be applied. Its proposed solution is a branch-and-bound search over path prefixes, with upper and lower bounds on the probability of the best continuation. The bounds are computed from the joint Markov structure, which keeps their per-node cost low. In random binary triplet Markov models of length 25, the method visits on average about $2^{6}$ nodes instead of the $2^{26}$ an exhaustive search would need, and for longer chains it can stop early while still returning rigorous bounds on the optimum. The paper's claim is that exact or tightly bounded maximum a posteriori decoding in triplet Markov models is computationally practical.

What carries the argument

The central object is the branch probability $p^*(x_{1:k}) = \max_{x_{k+1:n}} p(x_{1:n})$, evaluated for every prefix of the path, and the search tree over all prefixes. The identity that carries the argument is that the joint process $(X,U)$ is Markov: summations over the nuisance process $U$ can be moved through transition kernels, and maximizations over continuations can be separated into blocks, so each bound family becomes a dynamic programming recursion. Branch-and-bound prunes any prefix whose upper bound falls below a global lower bound, so the method's efficiency is determined by how tight the bounds are relative to their per-node computation cost.

What would settle it

Evaluate the printed Samuelson upper bound (15) at any prefix with $0 < S_2(x_{1:k}) < p(x_{1:k})^2$, which occurs whenever the continuation is nondeterministic; the square root is then imaginary, so the formula is not a real upper bound. Alternatively, rerun the Section 4 experiments with the Samuelson bound literally implemented as printed and compare the number of visited nodes, which should collapse or produce errors if the formula is used.

Watch

Extended reading notes

Core claim

The central claim is that the maximal marginal probability $\max_x p(x)=\max_x \sum_u p(x,u)$ can, in practice, be computed or tightly bracketed by a branch-and-bound algorithm whose bounds exploit the joint Markov property of $(X,U)$. The paper introduces five bound families: simple, power-sum ($r$-PS), Samuelson-type, swapped max-sum ($m$-SMS), and $m$-Viterbi approximations, with recursions that price each prefix $x_{1:k}$ in polynomial time. In 1000 randomly generated binary TMMs of length 25, the combination of 10-PS bounds with a 2-Viterbi lower bound reduces the average number of visited nodes from $2^{26}$ to about $2^{6.3}$, and the experiments indicate that $m$-Viterbi approximations with $m\ge 2$ provide the strongest lower bounds, often essentially matching the optimum. The paper also shows, by constructed examples, that larger $m$ need not improve the $m$-Viterbi approximation and that such approximations can even have zero probability, so the lower bound should be combined with a simple bound as a safeguard.

Load-bearing premise

The load-bearing premise is that the printed formulas for the bounds are valid; in particular, the Samuelson upper bound in Equation (15), as printed, takes a square root of a negative quantity whenever the continuation probabilities are nonnegative and not degenerate, so the algorithm only works if its implementation uses the standard Samuelson inequality form.

Editorial extensions

If this is right

  • For triplet Markov models with moderate state spaces and sequence lengths, exact MAP decoding becomes feasible in practice rather than requiring exhaustive enumeration over $|\mathcal{X}|^n$ paths.
  • The $m$-Viterbi lower bound with $m\ge 2$ can serve as a fast near-exact decoder on its own; the branch-and-bound search then supplies a certificate of how far the approximation is from optimal.
  • The same bound machinery transfers to non-homogeneous Markov chains obtained by conditioning on observations, so it applies to segmentation tasks in TMMs and to hybrid-path decoding.
  • Because no upper bound dominates in the simulations, an implementation can combine several upper bounds and take their minimum, at a cost that the paper's complexity tables make explicit.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • We infer, beyond the paper's own caution, that the printed Samuelson formula is a typographical slip rather than a conceptual one: with the standard Samuelson inequality used in the actual code, the Table 3 result of about $2^{14.1}$ visited nodes is plausible. This is testable by checking the released code.
  • An implication the authors leave implicit is that the same bounding machinery should apply to continuous-observation PMMs and TMMs, because conditioning on the observations produces a finite non-homogeneous Markov chain; the experiments only cover binary states, so the relative performance of bounds in larger alphabets remains open.
  • One possible extension is to use the $m$-SMS and $m$-Viterbi bounds together with an adaptive choice of $m$ per layer, exploiting the layer-by-layer plots in Figure 5; the paper compares fixed strategies only.
  • Given the NP-hardness results cited in the paper, the exponential worst case cannot be removed in general; we infer that the practical gains will depend on bound tightness for the particular model, so the method is best viewed as an exact solver with a rigorous early-stopping certificate rather than a polynomial-time algorithm.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The paper studies the maximal marginal problem: for a finite-state non-homogeneous Markov chain (X,U), find argmax_x P(X=x), i.e. the Viterbi path of the marginal process X, motivated by MAP segmentation in triplet Markov models. It proposes a branch-and-bound algorithm with five families of bounds (simple, power-sum, Samuelson, swapped max-sum, and m-Viterbi), derives recursions for computing them, gives complexity tables, and reports experiments on randomly generated binary TMMs showing large reductions in the number of visited nodes relative to exhaustive search. Appendices contain derivations and counterexamples showing that m-Viterbi approximations can fail in non-monotone ways.

Significance. If the issues below are corrected, the paper makes a useful algorithmic contribution: an exact-or-bounded method for MAP decoding in TMMs, with explicitly derived recursions for the power-sum and swapped max-sum bounds and a careful empirical study of the m-Viterbi lower bound. The counterexamples in Appendix D are valuable and honestly presented. The main strengths are the explicit derivations of the bounds, the transparent complexity tables, and the clear statement of NP-hardness with the resulting modest expectations for worst-case performance.

major comments (2)
  1. [Section 3.3, Eq. (15)] The printed Samuelson upper bound is not a valid upper bound as written. With N=|X|^{n-k}, s1=p(x1:k), and s2=S2(x1:k), the standard inequality (14) gives (s1 + sqrt((N-1)(N s2 - s1^2)))/N, whereas Eq. (15) has sqrt((N-1)(S2(x1:k) - p(x1:k)^2)) in the numerator, omitting the factor N multiplying S2. Since every continuation probability is nonnegative, S2(x1:k) <= p(x1:k)^2, so the radicand is non-positive whenever the continuation mass is split among more than one path. This bound is used in the Samuelson strategy whose results appear in Table 3 and Figure 5, so the soundness of that strategy is not established as printed. The likely fix is a one-character correction inside the square root, but the code URL in Section 4 is empty, so the implementation cannot be checked against the printed formula.
  2. [Section 4.2, Table 4] The 'distance from lower bound' column does not measure closeness to the optimal value because the early-stopped B&B lower bound includes the 5-Viterbi approximation. For m=4 and m=5 the zero entries show only that the m-Viterbi path attains the same value as the 5-Viterbi heuristic, not that it is the true Viterbi path; the same issue partly affects the m=2 and m=3 rows. The upper-bound distances remain sizable (about 5.3 nats for n=500 and 10.9 nats for n=1000 for m>=2), so the conclusion in Section 5 that B&B 'does not significantly improve' on m-Viterbi for m>=2 is not supported by the table as presented. Please compare against an independent lower bound, or restrict the claim to the upper-bound comparison.
minor comments (7)
  1. [Section 4] The sentence 'The code is available at .' has an empty URL; without the code the experimental results and the resolution of the Eq. (15) question cannot be verified.
  2. [Section 3.3, m-Viterbi paragraph] The text says 'only the case m >= k is considered', but Appendix C assumes k >= m; the intended condition is almost certainly k >= m, and the text should be corrected.
  3. [Section 3.3, Samuelson lower bound derivation] The proof that s2/s1 bounds the maximum contains an incorrect intermediate inequality: a1^2 + (1-a1)^2 <= a1 is not true for a1 < 0.5. The conclusion s2/s1 <= max_i a_i is still true, but the given argument should be replaced by the simpler argument s2 <= a1 * s1.
  4. [Section 4.1] The sentence defining the composite upper bound says 'the upper bound as minimum of all applied lower bounds'; it should say 'minimum of all applied upper bounds'.
  5. [Section 4.2] The text says 'Each model was then used to generate a sequence y1:25' even though the experiment uses n=100, 500, 1000; this should be y1:n.
  6. [Section 4.2, Table 4 description] The formulas 'ln(lower bound) - p(x1:n)' and 'ln(upper bound) - p(x1:n)' appear to have missing logarithms on the second term; the table is presumably reporting log-probability differences.
  7. [Appendix B] The recursion for delta contains index typos (for example 'delta_{n-(j-1)n}'), and the complexity expression in the text uses k where m is meant; these should be cleaned up.

Circularity Check

1 steps flagged · score 2.0 of 10

Central B&B derivation is self-contained; one local comparison in Section 4.2 is tautological because the m=5 'distance from lower bound' compares a path to a lower bound that includes that same path.

  1. self definitional [Section 4.2 (m-Viterbi approximation), Table 4 and surrounding text]
    "To measure the performance of m-Viterbi and UX-Viterbi approximation (and, by extension, the quality of the associated lower bounds), we compared m-Viterbi approximation for m = 0, 1, 2, 3, 4, 5 and UX-Viterbi against bounds obtained from B&B algorithm with early stopping. The bounds used in B&B were composite, consisting of 5-Viterbi, 5-SMS and 5-PS. ... Specifically, we computed ln(lower bound) −p(ˇx1:n) and ln(upper bound)−p(ˇx1:n)."

    For m=5 the object whose quality is being measured, the 5-Viterbi path ˇx1:n, is exactly the path generated by the 5-Viterbi lower bound included in the composite bound. Hence the lower bound in the denominator is, at least, the probability of that same path: ln(lower bound) − ln p(ˇx1:n) is forced to be ≥0 and in the reported random models it is exactly 0.0. Table 4's m=5 'distance from lower bound' column is therefore not an empirical measurement of approximation quality; it is an identity by construction. The conclusion about m≥2 is still supported by the independent upper-bound distances, and the B&B algorithm itself does not rely on this comparison, so the circularity is local rather than load-bearing.

full rationale

The branch-and-bound derivation is otherwise self-contained. The simple bounds (12), power-sum bounds (13), Samuelson-type bounds (14)-(15), swapped max-sum bounds, and m-Viterbi lower bounds are all derived from standard inequalities or from the defining property that any candidate path gives a valid lower bound; none of them fits a parameter to the quantity being predicted. The m-Viterbi bound is used inside B&B as a lower bound and is legitimate even though the path comes from an approximating Markov chain. Self-citations (e.g., [38] for m-Viterbi approximation) describe background and are not load-bearing because Appendix C gives the full recursion. The only circular step found is the Section 4.2 comparison of m=5 to a lower bound that includes the 5-Viterbi bound itself; that makes the 0.0 entries tautological. Separately, Equation (15) as printed is a genuine correctness risk: for nonnegative continuation probabilities S2(x1:k) ≤ p(x1:k)^2, so the printed square-root argument S2−p^2 is non-positive; the standard Samuelson inequality just above it requires N S2 − s1^2 inside the square root. This is not a circularity, but it should be corrected or verified against the implementation. Because the central claim does not reduce to its inputs and the tautological comparison is only a supporting sanity check, the circularity score is 2.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new entities are introduced. All bounds are derived from standard inequalities and Markov-chain probability calculations; the only hand-chosen numbers are algorithm hyperparameters m and r, and the experiments average over random models.

free parameters (2)
  • r (power sum order)
    User-selected integer in r-PS bounds; larger r gives sharper bounds but higher cost. Not fitted to a target; experiments use r = 2, 3, 5, 10.
  • m (block length for SMS / order for m-Viterbi)
    User-selected integer; experiments use m = 1, 2, 5, 10 for SMS and m = 0..5 for Viterbi. Not inferred from data.
assumptions (4)
  • domain assumption The joint process (X, U) is a possibly non-homogeneous Markov chain with known transition probabilities, and the conditional process (X, U) given Y remains Markovian.
    This is the defining assumption of PMMs and TMMs, used throughout Sections 2.3 and 3.3 to compute bounds via forward-backward recursions and dynamic programming.
  • standard math Standard dynamic programming identities for Markov chains, including Viterbi recursion and forward-backward marginalization, are valid.
    Used in Section 2.3 and the appendices to compute probabilities and bounds.
  • standard math Power mean and Samuelson inequalities hold for the finite set of nonnegative continuation probabilities.
    Used in Section 3.3 to derive the r-PS and Samuelson bounds.
  • standard math Exchanging maximization and summation in max-sum expressions yields valid upper bounds.
    Used for the swapped max-sum bounds in Section 3.3 and Appendix B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Branch-and-bound method for calculating Viterbi path in triplet Markov models." pith.science (2026). https://pith.science/paper/NTK7U6KY

@misc{pith2026250719338,
  author       = {Pith},
  title        = {Pith review of: Branch-and-bound method for calculating Viterbi path in triplet Markov models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NTK7U6KY}},
  note         = {Machine review of arXiv:2507.19338}
}
abstract

We consider a bivariate, possibly non-homogeneous, finite-state Markov chain $(X,U)=\{(X_t,U_t)\}_{t=1}^n$. We are interested in the marginal process $X$, which typically is not a Markov chain. The goal is to find a realization (path) $x=(x_1,\ldots,x_n)$ with maximal probability $P(X=x)$. If $X$ is Markov chain, then such path can be efficiently found using the celebrated Viterbi algorithm. However, when $X$ is not Markovian, identifying the most probable path -- hereafter referred to as the Viterbi path -- becomes computationally expensive. In this paper, we explore the branch-and-bound method for finding Viterbi paths. The method is based on the lower and upper bounds on maximum probability $\max_x P(X=x)$, and the objective of the paper is to exploit the joint Markov property of $(X,Y)$ to calculate possibly good bounds in possibly cheap way. This research is motivated by decoding or segmentation problem in triplet Markov models. A triplet Markov model is trivariate homogeneous Markov process $(X,U,Y)$. In decoding, a realization of one marginal process $Y$ is observed (representing the data), while $X$ and $U$ are latent processes. The process $U$ serves as a nuisance variable, whereas $X$ is the process of primary interest. Decoding refers to estimating the hidden sequence $X$ based solely on the observation $Y$. Conditional on $Y$, the latent processes $(X, U)$ form a non-homogeneous Markov chain. In this context, the Viterbi path corresponds to the maximum a posteriori (MAP) estimate of $X$, making it a natural choice for signal reconstruction.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 31 canonical work pages

  1. [1]

    Methodology and Computing in Applied Probability 25(2), 67 (2023) https://doi.org/10.1007/s11009-023-10044-z

    Kuljus, K., Lember, J.: Pairwise Markov models and hybrid segmentation approach. Methodology and Computing in Applied Probability 25(2), 67 (2023) https://doi.org/10.1007/s11009-023-10044-z

    work page doi:10.1007/s11009-023-10044-z 2023

  2. [2]

    Stochastic Processes and their Applications 130(3), 1388–1425 (2020) https:// doi.org/10.1016/j.spa.2019.05.004

    Lember, J., Sova, J.: Existence of infinite Viterbi path for pairwise Markov models. Stochastic Processes and their Applications 130(3), 1388–1425 (2020) https:// doi.org/10.1016/j.spa.2019.05.004

    work page doi:10.1016/j.spa.2019.05.004 2020

  3. [3]

    Journal of Theoretical Probability 34(1), 1–33 (2021) https://doi.org/10

    Lember, J., Sova, J.: Regenerativity of Viterbi process for pairwise Markov mod- els. Journal of Theoretical Probability 34(1), 1–33 (2021) https://doi.org/10. 1007/s10959-020-01022-z 32

    work page 2021

  4. [4]

    Electronic Journal of Probability 26, 1–30 (2021) https: //doi.org/10.1214/21-EJP628

    Lember, J., Sova, J.: Exponential forgetting of smoothing distributions for pair- wise Markov models. Electronic Journal of Probability 26, 1–30 (2021) https: //doi.org/10.1214/21-EJP628

    work page doi:10.1214/21-ejp628 2021

  5. [5]

    Pedestrian Models for Autonomous Driving Part II: High-Level Models of Human Behavior

    Pieczynski, W.: Pairwise Markov chains. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(5), 634–639 (2003) https://doi.org/10.1109/TPAMI. 2003.1195998

    work page Pith review arXiv 2003

  6. [6]

    IEEE Transactions on Signal Processing 52(9), 2477–2489 (2004) https://doi.org/10.1109/TSP.2004.832015

    Derrode, S., Pieczynski, W.: Signal and image segmentation using pairwise Markov chains. IEEE Transactions on Signal Processing 52(9), 2477–2489 (2004) https://doi.org/10.1109/TSP.2004.832015

    work page arXiv 2004

  7. [7]

    In: Advanced Concepts for Intelligent Vision Systems (2004)

    Lanchantin, P., Pieczynski, W.: Unsupervised non stationary image segmentation using triplet Markov chains. In: Advanced Concepts for Intelligent Vision Systems (2004)

    work page 2004

  8. [8]

    Signal Processing 91, 163–175 (2011) https://doi.org/10.1016/j.sigpro.2010.05

    Lanchatin, P., Lapuyade-Lahorgue, J., Pieczynski, W.: Unsupervised segmen- tation of randomly switching data hidden with non-Gaussian correlated noise. Signal Processing 91, 163–175 (2011) https://doi.org/10.1016/j.sigpro.2010.05. 033

    work page doi:10.1016/j.sigpro.2010.05 2011

Show all 41 references
  1. [9]

    IEEE Signal Processing Letters 19(10), 619–622 (2012) https://doi.org/10.1109/LSP.2012

    Boudaren, M., Monfrini, E., Pieczynski, W.: Unsupervised segmentation of random discrete data hidden with switching noise distribution. IEEE Signal Processing Letters 19(10), 619–622 (2012) https://doi.org/10.1109/LSP.2012. 2209639

    2012 doi

  2. [10]

    Computational Statistics and Data Analysis 63, 81–98 (2013) https://doi.org/10.1016/j.csda.2013.01.027

    Derrode, S., Pieczynski, W.: Unsupervised data segmentation using pairwise Markov chains with automatic copula selection. Computational Statistics and Data Analysis 63, 81–98 (2013) https://doi.org/10.1016/j.csda.2013.01.027

    2013 doi

  3. [11]

    Signal Processing 128, 8–17 (2019) https://doi.org/10.1016/j.sigpro.2016.03.008

    Derrode, S., Pieczynski, W.: Unsupervised classification using hidden Markov chain with unknown noise copulas and margins. Signal Processing 128, 8–17 (2019) https://doi.org/10.1016/j.sigpro.2016.03.008

    2019 doi

  4. [12]

    Signal Processing 145, 183–192 (2018) https://doi.org/10.1016/j.sigpro.2017.12.006

    Gorynin, I., Gangloff, H., Monfrini, E., Pieczynski, W.: Assessing the segmenta- tion performance of pairwise and triplet Markov models. Signal Processing 145, 183–192 (2018) https://doi.org/10.1016/j.sigpro.2017.12.006

    2018 doi

  5. [13]

    IEEE Transactions on Pattern Analysis and Machine Intelligence 29(8), 1367–1378 (2007) https://doi.org/10.1109/TPAMI

    Benboudjema, D., Pieczynski, W.: Unsupervised statistical of nonstastionary images using triplet Markov fields. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(8), 1367–1378 (2007) https://doi.org/10.1109/TPAMI. 2007.1059

    2007

  6. [14]

    In: 3rd IEEE International Symposium on Biomedical Imaging, pp

    Bricq, S., Collet, C., Armspach, J.-P.: Triplet Markov chain for 3d mri brain segmentation using a probabilistic atlas. In: 3rd IEEE International Symposium on Biomedical Imaging, pp. 386–389 (2006). https://doi.org/10.1109/ISBI.2006. 1624934 33

    2006 doi

  7. [15]

    Compu- tational Statistics & Data Analysis 180 (2023) https://doi.org/10.1016/j.csda

    Gangloff, H., Morales, K., Petetin, Y.: Deep parameterizations of pairwise and triplet Markov models for unsupervised classification of sequential data. Compu- tational Statistics & Data Analysis 180 (2023) https://doi.org/10.1016/j.csda. 2022.107663

    2023

  8. [16]

    IEEE Transactions on Wireless Communications 12(9), 4582– 4591 (2013) https://doi.org/10.1109/TWC.2013.072513.121864

    Nguyen, T., Mark, B., Ephraim, Y.: Spectrum sensing using a hidden bivariate Markov model. IEEE Transactions on Wireless Communications 12(9), 4582– 4591 (2013) https://doi.org/10.1109/TWC.2013.072513.121864

    2013

  9. [17]

    IEEE Transactions on Wireless Communications 15(8), 5430–5439 (2016) https://doi.org/10.1109/TWC.2016

    Sun, Y., Mark, B., Ephraim, Y.: Collaborative spectrum sensing via online estimation of hidden bivariate Markov models. IEEE Transactions on Wireless Communications 15(8), 5430–5439 (2016) https://doi.org/10.1109/TWC.2016. 2558506

    2016 doi

  10. [18]

    Neurocomputing 362, 94–105 (2019) https://doi.org/10.1016/j.neucom.2019.06.081

    Li, H., Derrode, S., Pieczynski, W.: An adaptive and on-line imu-based locomo- tion activity classification method using a triplet Markov model. Neurocomputing 362, 94–105 (2019) https://doi.org/10.1016/j.neucom.2019.06.081

    2019 doi

  11. [19]

    Signal Processing 92, 29–42 (2012) https: //doi.org/10.1016/j.sigpro.2011.06.001

    Lapuyade-Lahorgue, J., Pieczynski, W.: Unsupervised segmentation of hidden semi-Markov non-stationary chains. Signal Processing 92, 29–42 (2012) https: //doi.org/10.1016/j.sigpro.2011.06.001

    2012 doi

  12. [20]

    Signal Processing 90, 2899– 2910 (2010) https://doi.org/10.1016/j.sigpro.2010.04.008

    Lapuyade-Lahorgue, J., Pieczynski, W.: Unsupervised segmentation of new semi- Markov chains hidden with long dependence noise. Signal Processing 90, 2899– 2910 (2010) https://doi.org/10.1016/j.sigpro.2010.04.008

    2010 doi

  13. [21]

    International Journal of Approximate Reasoning 162 (2023) https://doi.org/10.1016/j.ijar.2023.109025

    Fernandes, C., Pieczynski, W.: Non-stationary data segmentation with hidden evidential semi-Markov chains. International Journal of Approximate Reasoning 162 (2023) https://doi.org/10.1016/j.ijar.2023.109025

    2023

  14. [22]

    MIT Press, USA (2009)

    Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Tech- niques. MIT Press, USA (2009)

    2009

  15. [23]

    Journal of Machine Learning Research 15, 1–15 (2014)

    Lember, J., Koloydenko, A.: Bridging Viterbi and posterior decoding: a gener- alized risk approach to hidden path inference based on hidden Markov models. Journal of Machine Learning Research 15, 1–15 (2014)

    2014

  16. [24]

    In: Dymarski, P

    Lember, J., Kuljus, K., Koloydenko, A.: Theory of segmentation. In: Dymarski, P. (ed.) Hidden Markov Models: Theory and Applications. Intech, Rijeka (2011)

    2011

  17. [25]

    Annals of Applied Statistics 7(3), 1814–1835 (2013) https://doi.org/10.1214/ 13-AOAS657

    Holmes, C., Yau, C.: A decision-theoretic approach for segmental classification. Annals of Applied Statistics 7(3), 1814–1835 (2013) https://doi.org/10.1214/ 13-AOAS657

    2013

  18. [26]

    arXiv preprint arXiv:2504.15156 (2025) 34

    Bæk, Z., Macia, M., Skov, L., Hobolth, A.: Advanced posterior analyses of hid- den Markov models: finite Markov chain imbedding and hybrid decoding. arXiv preprint arXiv:2504.15156 (2025) 34

    2025 arXiv

  19. [27]

    https://arxiv.org/abs/cmp-lg/9805007

    Goodman, J.: Parsing Inside-Out (1998). https://arxiv.org/abs/cmp-lg/9805007

    1998 arXiv

  20. [28]

    Journal of Computer and System Sciences 65(3), 545–569 (2002) https://doi.org/10.1016/S0022-0000(02)00009-0

    Lyngsø, R.B., Pedersen, C.N.S.: The consensus string problem and the complexity of comparing hidden Markov models. Journal of Computer and System Sciences 65(3), 545–569 (2002) https://doi.org/10.1016/S0022-0000(02)00009-0 . Special Issue on Computational Biology 2002

    2002 doi

  21. [29]

    In: Bayesian Statistics 9

    Meek, C., Wexler, Y.: Approximating max-sum-product problems using multi- plicative error bounds. In: Bayesian Statistics 9. Oxford University Press, UK (2011). https://doi.org/10.1093/acprof:oso/9780199694587.003.0015

    2011

  22. [30]

    https://arxiv.org/abs/1212.2497

    Park, J.D., Darwiche, A.: Solving MAP Exactly using Systematic Search (2012). https://arxiv.org/abs/1212.2497

    2012 arXiv

  23. [31]

    Artificial Intelligence 42(2), 393–405 (1990) https: //doi.org/10.1016/0004-3702(90)90060-D

    Cooper, G.F.: The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence 42(2), 393–405 (1990) https: //doi.org/10.1016/0004-3702(90)90060-D

    1990 doi

  24. [32]

    Artificial Intelligence 60(1), 141–153 (1993) https://doi

    Dagum, P., Luby, M.: Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artificial Intelligence 60(1), 141–153 (1993) https://doi. org/10.1016/0004-3702(93)90036-B

    1993 doi

  25. [33]

    In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing

    Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. STOC ’06, pp. 681–690. Association for Computing Machinery, New York, NY, USA (2006). https:/...

    2006

  26. [34]

    METRON 77 (2018) https://doi.org/ 10.1007/s40300-019-00152-7

    Lember, J., Gasbarra, D., Koloydenko, A., Kuljus, K.: Estimation of Viterbi path in Bayesian hidden Markov models. METRON 77 (2018) https://doi.org/ 10.1007/s40300-019-00152-7

    2018 doi

  27. [35]

    Journal of Applied Statistics 49(5), 1203–1234 (2022) https://doi.org/10.1080/02664763.2020.1858273

    Koloydenko, A., Kuljus, K., Lember, J.: MAP segmentation in Bayesian hidden Markov models: a case study. Journal of Applied Statistics 49(5), 1203–1234 (2022) https://doi.org/10.1080/02664763.2020.1858273

    2022

  28. [36]

    IMA Journal of Numerical Analysis 41(4), 2311–2330 (2020) https://doi.org/10.1093/imanum/draa038

    Blanchard, P., Higham, D.J., Higham, N.J.: Accurately computing the log-sum- exp and softmax functions. IMA Journal of Numerical Analysis 41(4), 2311–2330 (2020) https://doi.org/10.1093/imanum/draa038

    2020 doi

  29. [37]

    The American Statistician 33, 143–144 (1979) https://doi.org/10.1080/00031305.1979.10482683

    Wolkowicz, H., Styan, G.: Extensions of Samuelson’s inequality. The American Statistician 33, 143–144 (1979) https://doi.org/10.1080/00031305.1979.10482683

    1979 arXiv

  30. [38]

    Mas- ter’s thesis, University of Tartu (2023)

    Soop, O.: Kolmekaupa Markovi ahelate viterbi raja l¨ ahendamine. Mas- ter’s thesis, University of Tartu (2023). https://dspace.ut.ee/items/ 72b723bb-cee2-4967-9bc7-4ba2405aabca 35

    2023

  31. [39]

    share.neic.no (2018)

    University of Tartu: UT Rocket. share.neic.no (2018). https://doi.org/10.23673/ PH6N-0144

    2018

  32. [40]

    Addison-Wesley, USA (1984)

    Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, USA (1984)

    1984

  33. [41]

    Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009) https://doi.org/10.1016/j.jcta.2008.05.005 36

    Bernardi, O., Bonichon, N.: Intervals in Catalan lattices and realizers of tri- angulations. Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009) https://doi.org/10.1016/j.jcta.2008.05.005 36

    2009 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.