Forward-Backward Latent State Inference for Hidden Continuous-Time semi-Markov Chains
Authors: Nicolai Engelmann
Heinz Koeppl
Venue: NeurIPS 2022 Accept (2022)
Keywords: forward-backward
continuous time
hsmm
ctsmc
semi-Markov
latent state inference

Abstract: Hidden semi-Markov Models (HSMM's) - while broadly in use - are restricted to a discrete and uniform time grid. They are thus not well suited to explain often irregularly spaced discrete event data from continuous-time phenomena. We show that non-sampling-based latent state inference used in HSMM's can be generalized to latent Continuous-Time semi-Markov Chains (CTSMC's). We formulate integro-differential forward and backward equations adjusted to the observation likelihood and introduce an exact integral equation for the Bayesian posterior marginals and a scalable Viterbi-type algorithm for posterior path estimates. The presented equations can be efficiently solved using well-known numerical methods. As a practical tool, variable-step HSMM's are introduced. We evaluate our approaches in latent state inference scenarios in comparison to classical HSMM's.

Forward-Backward Latent State Inference for Hidden Continuous-Time semi-Markov Chains
Nicolai Engelmann
Heinz Köppl
Department of Electrical Engineering
Department of Electrical Engineering
Technische Universitat Darmstadt
Department of Biology
64289, Darmstadt
Technische Universitat Darmstadt
nicolai.engelnnneee. waa.aaaeennemmmmmmuuuaaaaaaaaa
64289, Darmstadt
Abstract
Hidden semi-Markov Models (HSMM's) while broadly in use are restricted to discrete and uniform time grid. They are thus not well suited to explain often irregularly spaced discrete event data from continuous-time phenomena. We show that non- couu-samliing--ee based latent state inference used in HSMM's can be generalized to latent Continuous-Timgg semi-Markov Chains (CTSMC's). We formulate integro- differential forward and backward equations adjusted to the observation likelihood and introduce exact integral equation for the Bayesian posterior marginals and a scalable Viterbi-type algorithm for posterior path estimates. The presented equations can be efficiently solved using well-known numerical methods. As practical tool, variable-step HSMM's are introduced. We evaluate our approaches in latent state inference scenarios in comparison to classical HSMM's.
Introduction
Continuous- Time semi-Markov Chains (CTSMC's) comprise the continuous time analogue of (discrete-time) semi-Markov chains. In comparison Markov chains, semi-Markov chains al- low to model non-exponential, arbitrary waiting times between state changes. This more accurately matches such times occurring in many scientific fields (I]. Hidden semi-Markov Models (HSMM's) ss) on finite state spaces have seen wide application and thorough research [22]. However, confronted with measurements from continuous-time systems, their adaptivity is limited and computation might become unnecessarily expensive. Because of that, continuous time analogues of HSMM's have seen increased research interest lately [17] [ 77 However, latent state inference is hard in continuous time, since the usual methods demand a reformulation of the process to obtain the Markov prop- erty. Markovianization by state space expansion as used for HSMM's demands propagation of semi-infinite uncountable state for latent CTSMC's even if the original state space is finite. Thus, besides ad-hoe discretization, two classes of solution methods have emerged. First, a variety of sampling-based solutions has been published, often targeted at even generalized problems 7 2 i 9 Second, non-sampling based solutions are sought, state-space expansions based on approximations of waiting time measures are available [16] This second class, by detour, essentially tries to approx- imate Kolmogorov's (forwardd/ackkantg equations. However, a general framework not tailored to specific families of waiting time measures is still lacking. Kolmogorov's equations in integro- differential form have been studied recently [20]. Although initial or terminal states are given, the equations rely specific boundary conditions to restrict the non-Marke non-Markovian process to the considered time-window. Fixed conditions hinder the equations' usage in latent state inference which typically spans many such time-windows. To alleviate this restriction, terms in Kolmogorov's 's equations to include observations. As a consequence, we provide general forward and a backward algorithms, each encoded in single inhomogeneous integro-differential
show how to adjust the memory
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

equation. We also provide a method for exact Bayesian smoothing which uses the quantities obtained from the forward and backward algorithms. As a corollary. we propose a Siterbi-type approach for maximum-a-pose --postrrror path estimation and sketch method to implement adaptive step-size HSMM's that keep their homogenous properties. The resulting general framework may incorporate arbitrary numerical solvers or make use of approximations by the mentioned second class of solution methods.
Related Work. Continuous-time HMM's and their inference has recently been compiled by [14). Although tailored to specific problem, an interesting MAP path estimation method for CT-HSMM's based on stochastic state classes has been published [5]. Neural ODE's for the progression of memory variables have been investigated in [7]. An application of CT-HSMM's ' including parameter inference using a discretized waiting time variable [6. Generalized HSMM's 's that are lossless continuous discretizations but the transitions are observable has been proposed in [2 An elaborate -ewward-ilterinn--- filtering-backwaann -aaedlig--a for a HASMM [. To our knowledge, we are the first to introduce a "traditional" form of forward- harrddar algorithm for latent CTSMC. Also, while [ able to do MAP estimates of trajectories as well, their method is very different to our approach.
Notation. To maintain readability, we use the symbol P to denote density and mass functions alike. Which kind is needed should be clear from the context. Nonetheless, we refer to appendix section A for derivations and proofs using a stricter notation style.
1.1 Continuous-Timn semi-Markov Chains
Given a probability space (12, 8, Pr) and a measurable space (X, 3). In this work, we assume X' to be countable. Then, a continuous-time semi-Markov chain (CTSMC) on the state space X' is stochastic jump process X Ω x Rz0 - X. The general process is described by transition rates A X' R20 Rz0 X - 12 Conditioned on the current state x E X' at time / E R20 and the time since the last transition at t t- T < f. the rates A (z, t; x') describe the probability per unit time of transitioning shortly after time to state x'. These transition rates suffice to resolve the waiting times and jump directions for each tuple (x, T) at all times t. In this work, we restrict ourselves to CTSMC's which are homogeneous and direction-tima independent. The former means that A (z. T, t; x²) = X (z. T; x²) at all times t. The latter additionally implies the factorization (z, T: 2') = m (a') xx) X (zx r) with the exit rate X (z, r) = Ex' (xx t; x²) and the transition probabilities of the embedded Markov chain m (a'[x), z). Satisfying En' m (x'1x) = 1, i...,
excluding self-transitions, they form a categorical distribution over next states x' * x. Under direction-time independence, the waiting time in each state is thus statistically independent of the jump direction.
In this setting, for each state x, we have the waiting time measures (z 1 A (r with survival/tail functions A (r I²) = exp (- dr' X (xx r')) and their densities [ A (z, A) (T [z). For convenience of notation, we also introduce the forward transition operator of the embedded Markov chain M acting on a test-function g by Mg (z, t) = Ex'ee m (z x²) g (a',
and its backward adjoint MI, for which M g (z, t) = Ex' m (a' [z) (z', t) holds.
Further, a homogeneous continuous-time Markov chain (CTMC) is a homogeneous and direction-time independent CTSMC which has constant rates in each state. As such, the rates À (I, 7) = À (xx are left dependent only on the current state. Thus, the waiting time measures are strictly exponential and so F (T z) exp (-X (z) T) and (r x)) A (z) exp (-X r). Though significantly less expressive, inference in CTMC's is by large parts available analytically [18].
1.2 Observation Model
In this work, we consider a continuous-time version of a hidden semi-Markov model, where the latent process is a CTSMC X (t) and we are given set of observations at discrete time instances. This means, for specific t', the state X (t') is observable indirectly by means of a dependent random variable Y (t') taking values in measurable space ()', D). We assume to collect set of observations
No: V1.,... Ук E y only at discrete time instances to < t < ... < t and demand proper likelihood functions [x yk) be given and known at observation instances tj. Like mentioned above, we will use the notation P(jk X (t&) = x) = Lx(z) ykk) irrespective of ) being continuous or discrete. Finally, we will often write events in the form Vie.o) denoting the joint event obtained by intersecting single observation events, i.c., Vlv, r) = N..elr..) (Y (tx) }
2

---

1.3 General Idea
Latent state inference in Markov processes generally relies on the exploitation of their Markov property. It allows to describe the posterior latent state probability as product of forward and backward term. While the forward terms account for the probability of past observations any time instance I, the backward terms describe the likelihood of future observations starting from L. In the semi-Markov case, such a factorization is generally not possible, i.e. for state (() = Ft.
P ((x ((,,T)) x
P (1r ((.,))
x P (y11,19
posterior
forward
X
backward
However, as the name suggests, semi-Markov processes do not always violate the Markov property. In particular, the process is Markov at jump instances [13]. Thus, with respect to state changes, we can again find factorization similar (I). To be made precise later, let A, denote the event of X (t) transitioning to state x E X' from a different state X (t") ) o x at time instance t. Then, in contrast ( it holds that
P (A. MA,, ((Ar1y10.0) (y 1At).
posterior
forward
backward
where P now takes on the form of a density instead of the mass functions in (T. The term P(A, 1)) in (2) can be calculated under history dependence while the term P(y 2) A,) is by definition independent of any past trajectory up to since it is conditioned on the state change at t. In the following, we refer to such quantities like those occuring on the right-hand side of as "currents".
2 Forward and Backward Currents
Probability currents- in the context of Markoy chains - are known from the balance equation [19]. They also occur in the description of other stochastic processes [12), CTSMC's in particular as well [15] 3) In this section, we establish a general framework of input and output probability and likelihood currents under observations which is needed for the inference methods afterwards.
2.1 Input and Output Currents in Continuous-Time semi-Markov Chains
Consider again CTSMC {X (t))rz on a countable state space X. Let state x E X of the chain and a time instance & E R 20 be given. The following events form the core of the following section. Let V (x, t) = [X (t) = X (t + h) + r} denote the joint event of being in two different states x and some x' * at the beginning and end of a window of length h past t, i.e. the event of leaving state between and t h. Let in contrast further A (z, t) (X (t) # x, X (t + h) x} denote the joint event of being in state x' # x at the beginning of the window and in state x at the end, i.e. entering state x between / and + h. Then, we can quantify the flow of probability into per unit time with & (x, 1) = lim 1/2 P (An (x, 1)). We call the quantity ø (Ir, t) the input current of state at t. Analogously, we define the output current by vé (z, t) lim,-so J.P (Vv (x, t)).
In the following, may omit function arguments if they are the same for all functions. Let the marginal probability of being in state x at t be denoted by p (x, t) = P(X (t) = x). Then, p is related to the input and output currents by
dt P - (M l) 2b
at (
Σ Im (a (x|=') Se'al v (x', t),
(3)
where l vb is the identity operator and 8 is the Kronecker delta. This equation is equivalent to the forward equation in an inhomogeneous CTMC and the currents ó (I, t). vi (xx, t) can directly be derived from it (see appendix section A). The input and output currents are related by the forward transition operator of the embedded Markov chain é Myb The following Markov property makes the currents important w.r.t.. (2) Let x(),)) denote the trajectory of X (t) in the interval [t', f). Then, lim P (xx,, r) A (I, x :)) lim,-~ P (x T) An (z, t)) for any x and Thus, the current @ (z, t) specifies the probability per unit time of the CTSMC having the Markov property t
3

---

t
Hidden CTSMC
HSMM approximation
10
Or (1 t)
B t)
p(z,
08-
b)
d)
06
04-
x
02
00
2
3 5
1
2
3
1
2
3
4
a) Illustration of input and output currents to and from state at in 3-state chain. Like an electric current quantifying the flow of charge across set of wires, probability current quantifies the flow of probability across a set of edges in the graph for an infinitesimal duration. Particularly, currents describing probability (and likelihood) flow into and out of single states are important in this work; b), c), d) Exemplary calculations of forward a (b), backward 3 (c) and posterior ş (d) marginals from equations (IO) and (12) for only start- and endpoint constraints (Kolmogorov equations) for three-state chain with Gamma waiting time distributions. The markers show a HSMM approximation with step-size h = 10
Figure I:
next to entering state x. On the other hand up (z, t) specifies the likelihood of being Markov at and entering arbitrary state x' * An illustration of input and output currents is given in Fig. [
In this work, we talk about forward or filtered currents specifically if we condition on past ob- servations. For these, we write do (z, t) = lima-~o 1 LP (An (Iz 6) y1,, and to (I, t) = v( for the forward marginals. For the forward currents and marginals 3 holds unaltered. We comple- ment the forward currents with backward currents ds (I, t) lim P (y)t.)) r) An. (z, t)) and th (2x, 1) = limb-~0 P (yI,.) T) VA (1; 0)). We also assume a terminal condition to be fixed at T. Forward and backward currents share important properties. Let / (x, t) = P (y,,.) X (t) = x) be a marginal likelihood complementing a (ær, t). Then, we have for a, 3 and the both currents
lim;-o A P (Vn (ar, t) e)) We the notation (ar, t) P (x (t)
d dt 0 = G. - V/ = (M- 1) t/a
d
dt 4/2 0g (1 M') dg
while the backward currents are related by the = Mldg. Like (3), resemblance to classical forward and ward equations in a CTMC is not coincidental in (4) We have seen that knowledge of the currents Φa. ta and tha, dhg fully enables calculation of forward and backward terms. In the following, we will outline the necessary equations to determine them.
2.2 Obtaining the Forward and Backward Currents through Integral Equations
The input and output currents have an interpretation as a marginalization over paths. This, and their relation to the forward and backward terms (4), enables us to determine how the observations contribute a and | in the history dependent CTSMC. the following, we will use the shorthand X)rr,)) = x to denote the event of the trajectory X(r.,) being constant in (T) I, VT E [t', t). We begin by resolving a relationship between p and Φ fundamental to CTSMC's. Note, that the probability per unit time of X (t) entering state x at t - T, T > 0, and staying in at least until t, can be given by A (7 (z) & (z. 1 7- = lima-- 1/2 P (x 1) = x, An (r, L - -))) To obtain p (I, (), we need to marginalize over all trajectories X|t- having state at time t. Because of the Markov property at t J, we only need to marginalize over all constant trajectories
(-)) = I. Thus, we are left to integrate over all r > 0 to obtain (a, t). We stop at r = t and insert an initial condition from there. Doing this, we obtain the fundamental relationship
p(x, 1) J/' dr A ((--)(z))(2) T) 9p (z. t)
= LØ 9p
+
(5)
where L is a convolutional integral operator defined by LΦ (zr, () = 5o dr ( (I, T). The inhomogeneity yp X' x R20 + R2 is known general function and implements the initial condition. Choices for 9p will be discussed in section Instead of asking for x to be kept from t at least until t, we may also demand transition shortly after f to another state to obtain an

---

expression for v. This probability per unit time can then be given by X (z, a) (2,
(T) Φ (a, t 1) = lim 1 (V (r, t 7), X(t-1,)) = x, A (x. 1 - 7)). As the result of a we then obtain
marginalization over trajectories similar to ( i.c. integration over
v/ Frb + 9
(6)
with the integral operator F (z, t) = fo dr f (t 7 o (z. T). Again, Is implements the initial
condition. Note, that we can understand this as an expectation vi (z, 1) = E [eb (r. L ---.. )] over the waiting time in state z. Differentiating (5) w.r.t. time and comparing the result with (3) and (6), we
get the relation of the inhomogeneities Sp + 9 0. Remembering that Φ Mab, can obtain the two identities / = FMg + Mge and @ = MFΦ + 9 where gS Mg
In the following, we account for observations and then close with the backward currents. Let v (x; L'; () = (yle).) ()v, = x) /P (y(es,)) | Yj,,')) be the normalized joint observation likeli- hood of the constant latent trajectory x = x. The normalizer P (yle, (Y(o.e)) is the same as im- plicitly used when normalizing in a CTMC filtering update. The v (zc, t', t) is then a t-family of piece- wise constant functions with discontinuities in the f'-direction (or vice-versa). For convenience,
(ar, r), where fo (r, t| = (zz, T, (f (f--1 - x²) We also define La (zz t) for As (T, t a/)=) = u (æ, T, t) A (f xr) ana- loguously. Let further Up (x, t) = U (z, O, 2) be a shorthand for v in the interval [0, t). Then, we can generalize and to obtain
define the modified integral operator F. (2r, 1) = =[" dr fo (T, (|
L. + VoSpp and vha = F + Voga-
From 7 immediately follow the identities Va Mela + UgMg and 6a = MF. Vago. The backward currents obey relations analogous to 77. In the following, we will perform the similar construction.
Consider the product f( 2z the (z. t T)
lim T)) Vn (I, t +)) (++))) = x An (z, t)). It gives the likelihood of keeping state in the interval [t, + r), then leaving, and along the path encountering any future observations, given an entry in state x at t. Thus, 6g (æt, t) can be obtained again by marginalization over future trajectories. The marginal likelihood B (z, t) can also be shown to maintain an analogous rela- tionship with A (T x)) the (I, T). This is obtained by two-side marginalization along state entry As (z, t- 7) and exit Vn (z), t r') while implying no information on the time of entry t T. We refer to appendix section A for the derivation, since it takes more steps. In the reverse direction as we did for the forward case (7). we similarly normalize 33 and the backwards currents v.s 0g by P (Y1c. (") ()). This requires full forward pass to be performed before the backward calculations. Define the integral operators Fag (I, () = fe" dr Jo (1. T [)) &b (x, T) and Lav (1r, () for Av (1, T [ analogously. Let further again or (x, 1) = v (xr, 1, T) be a shorthand for v in the interval [t, 7). As conclusion, obtain the relations
B = Loghs + UT%P and Φ Fauhs + trre,
where the inhomogeneities 7p and 7/ implement the terminal condition. Note, that we write 7 to distinguish from the g for the initial conditions. Again by differentiation and consultation of ( we can find di 7/p + T 0 Like before, the recurrence relations dg = M' MMFadg + UT and
dbg = F ths + M77 follow. Also, Th = M1 Note, that if there are no observations and we only keep the terminal condition, particular case of both equations in g similar to (5) and (6) is obtained.
3 Integro-Differential Forward and Backward Equations
We first briefly sketch the derivation of Kolmogorov's forward equation. Our goal is a direct relation between
d and s). We then have (6) expressing i in terms of Φ and we also have 55) expressing p terms of ø. Convolutional equations can be conveniently treated using the Laplace transform. We use it on (5) to express & by a convolution of p. then plug
d a& and p. We start out with (3) relating d
the result into (6) to express d in terms of p. The latter result then inserted into (3) to express áp in terms of p. The result in the time domain is then
d Te -= = (M- Kp+ t ( = Σ L dr [m (x|x²) d x ( ()' T) (I,
d
(9)
5

---

with the integral operator Kp t) Snd dr K (z, 7) and the Kronecker delta 8. The memory kernel is then given by L {K) (z, s) = [ff (s /A) (s æ) with the symbol L denoting the Laplace transform with the Laplace variable s. The inhomogeneity g will be discussed at the end of the section.
In the following, we implement observations and introduce the backward case. Equation 2 is not
simply understood as path marginalization like 5 or (6). However, the path-wise contribution of the observation likelihood carries over from and (8) to equation ( the scaled likelihood function
e (2e, L', 1) is piece- constant. The analogue can be shown for the backward case. The rationale
is to subdivide the time-domain into intervals where V (z, t', t) is constant under variation of either t in the forward case or t' in the backward case. The two-argument functions ö (z, r) = v (z, T, t) (forward) and 2 (z, T) = v (x, t', 7) (backward) are then simple stepped functions under application of L. The following derivations are executed in detail in Appendix section A.
To obtain the forward equation, we repeat the steps to obtain b but instead use our extended equations 7 for each time interval. For the backward equation, we do the following steps. With
(4) and the two equations in (8) we have a similar toolset to the forward case. Thus, we apply the
Laplace transform to the left equation of (8). We then insert the expressed through 3 into the right
equation of (8) which gets us 6s in terms of Inserting this expression into 4 yields the backward
equation valid for the considered time- interinterval. Joining the obtained sequences of equations back together in both cases yields the integro-differentia forward and backward equations
d = (M- - 1) Kaa + vug
d 3 - (1 M1) K3B + eryy
and
(10)
dt
dt
with the modified integral operators K, (x, t) = f dr No (T, t, x) p (z, 7) and K& (z, t) Se" dr Ky (Ir, t. r) 8 (I, 7) where Ne (I, f, f) (zz t', t) (z, t- t'). Both inhomogencities g and 7 can be built from the inhomogeneities 9p- 9s and 7pp Tv from section 2.2 They satisfy the equations
(M- - 1) (op Kagp) and y = (1-Mi) (K07p -e)). We will consider these in the next section. Finally, note that a and 33 can not simply be multiplied to obtain the full Bayesian
posterior P w.r.t. the observations. How و can be obtained will be discussed in the next section.
4 Latent State Inference
There are two possibilities to realize the forward and backward algorithms. We exemplify this on the forward algorithm in the following. In popular HSMM literature [22), the discrete-time equivalent of the products &a and/or tha are fully calculated and a derived from them using 33. This general procedure poses the computationally most efficient overall solution under two circumstances. First, if we only aim to calculate the full Bayesian posterior P (z, t) = P ((x (t) = x Yoo r)) for all t we don't 't need a itself but only da and/or va. The currents &a. aa are obtained from 7 and (10) with comparable effort (c.f. section 4.2). Second, the classical memory kernel K and thus K.x is hard to evaluate (e.g. by numerical inverse Laplace transform), an evaluation of F and thus F. might be computationally preferable, even in the case where we aim to obtain & from or 7 afterwards. In this work, we chose to evaluate a and B directly from (0)) using finite-element approach. Thus, introduce a time-mesh lo < 4 < .... < Lk. where we set each L4 exactly at the times of observation.
Initial and Terminal Conditions. Until now, we assumed the boundary conditions g and y to be known but didn't specify them. Compared to CTMC's, the boundary conditions are not single states but semi-infinite trajectories. In HSMM literature [22), there are two popular boundary conditions. The first assumes, a transition occures both before to and after tg. The second assumes a steady state before to and uninformed progression after tx. The latter corresponds to the case that is classically expressed by a vector of ones in HMM's 's when the backward term is initialized. More on boundary conditions and their exact expressions are found in appendix section A.
4.1 Unidirectional Forward and Backward Algorithms
We formulate the general forward and backward algorithms in appendix section C. The interpolants Og and 8& valid in the k-th time interval t E [ts, 1x+1) obey the following integral equations
d au = (M- 1) Kip, 0g + 9k
d B, = (I-M') Ki tu Se + mh
(11)
dt
dt

---

where we introduce the truncated integral operators Kja, b)or; = Sa dr x (l--7, 2)) a (a, r) and K(a, SS. = 1 dr K (T t, I) B& (z: r). The inhomogeneities Ih and are built during runtime. We build 9% from the overall boundary condition 9o. the previous interpolants Ogg, k' < k, and the scaled likelihood function v. The backward " is built analogously with *K and BR. k' > k. Note, that the data likelihood P (N1,,)) usable to infer model parameters is obtained in the forward pass.
4.2 Borward-Backward Algorithm Posterior Marginals
Obtaining the posterior marginals is possible on the level of currents. Since they mark times when the
CTSMC has the Markov property, we can build the product of the two normalized currents t (x, , t) =
lim;--0 (VV (zz, t) ()) and ch, t) lim p(y r) (n, t))/ P(y T) [ t) to
obtain the posterior current (zr, () = lim At- P(V,( 1) yooo r)). We can then use & in 3 to obtain the derivative á We discuss this direct approach in appendix section A. Although the former is preferable from a runtime perspective, an more classical approach popular in discrete-time HSMM literature [2 uses two-sided path marginalization which allows usage of interpolation-based numerical methods. Thus, we calculate the posterior marginals from &a and v/g via
P 5 (Øa; 1h3) + G T
(12)
with the integral operator y (6o: vhs) = So dr Se" dr' do (x, 1 So (T, I' (2) (a,, + 1+))
and the boundary integral operators Gúb -o- dr (x, L +++000 (Iz, (+) vi (2,, + 7') and
Te = Jg d7 J." dr' da (x, t - T) vr (x, t - y) (z, 1). A written out version of (2) is available in Appendix section A. We need to add that the currents da and ahs are obtained as by- products without additional computation from the unidirectional forward and backward algorithms introduced in section 4.1 An algorithmic description and an explanation how da and Big are obtained as by-products can be found in Appendix section C.
4.3 Viterbi-type Algorithm Latent Trajectory Point Estimation
Besides latent state marginals, point estimates of whole posterior paths are as well important in further inference tasks. Originally stemming from HMM's, the Viterbi algorithm which calculates MAP path estimates has been successfully adopted to HSMM's 222 However, like hidden CTMC's, the unknown chain length, i.e. the number of state changes until the terminal state is reached, makes the algorithm hard to translate to continuous time. One is therefor often content with knowing the MAP state only at observation times [14]. The latter can in principle be obtained using forward algorithm in section I. Nonetheless, for finite number of jumps, the framework of currents allows the formulation of a scalable full-path algorithm. A max-proue moxx-podduct-ype reformulation of 7 allows an introduction of a max-input current
Ómax (x, t; n) sup lim - P P(An (z, t). X(o, e) (1 n2)
x(o. h- h
which - bluntly speaking substitutes the marginalization over all Xjo, r) in da with supremum. To keep track of the jump count, we equip this current with an additional parameter n. We also introduce maximizing transition operator Mmax for the embedded Markov chain M (I. () = max,' m (I x²) g (a', t). The transition operator Mmax resembles M where the sum over the set X \ {2) is exchanged by a maximization. The constituting recursion for Φmax (I, t; n) is then given by
Ómax (zz, t; n 1)
sup a' a'gla, FRR
(2', t T, t) @max (e', n) m (x|x)) (t - xx)) +1x')
(13)
which calculates the max-currents Φmax (z, t; n n 1) associated with the incremented chain length + 1. A detailed description is found in Appendix section A. The MAP terminal state x is related to the currents Qmax (Ir, t; n) by
sup P (x M), sup ((t-rlz)) (x. t- T, t) Qmax (z. T: n) P (m m) x)
I. T,
Let's first assume we found a maximizing tuple (x*, 7", n²). Then, if n* > O, we can insert Xmax (x", T"; n²" in (3) and proceed to trace back states and transition instances until the jump
7

---

counter reaches zero. However, to find the full tuple (x", -", n²), we need knowledge of the posterior chain length P(n M)o,T) for n up to infinity, which is intractable. Nonetheless, P(n ylo ry) can be obtained recursively and knowledge of the accumulated probability mass until a specific n' lets us bound the remaining mass for all n >> n' letting us know if we passed all high-probability regions. For the recursion, two more sets of input currents On (I, t) = lim i. P (Ar, (r, t) Y(o,e) e) and marginals pr (z, T) = P (x (T) = I, n (10, are introduced. These are then updated by
Pn (z, T) T)= L./ dr A(T-
pn+1 OF
and
T, T) on (z, 7)
(14)
The currents are initialized by do (x, t) = u (x, O, t) ga(z, t). Note that the left equation in (14 does not converge to the fixed-point &a but instead will vanish for 30. The posterior chain length P (n ((. = =Ex Pn (x. T) can then be obtained by marginalization. Again, we refer to appendix section A. While we still need to evaluate all equations for arbitrarily large for an exact result, in most practical scenarios, the most likely number of transitions n might be feasibly obtained by bounding. We stress that the bottleneck of our algorithm is the number of transitions, not their temporal closeness.
5 Adaptive Step-Size HSMM
One of the major advantages of continuous-time formulations is the availability of adaptive discretiza- tion 18] 4]. Although many continuous problems eventually need to be solved numerically on a discrete grid, adaptive step-size methods can bound the discretization error and allow a reduction of the amount of function evaluations. While much more elaborate techniques with tight error bounds are available for integral equations [10], we briefly sketch a simple adaptive discretization strategy to close with a practical perspective on the contributions in this work.
This strategy consists of maintaining a time-dependent
of samples of approximate currents and their timestamps P, (4) = ((0r,k (x) 4x - to < Amax, to < ... < LK. k =, O.... K}. An analogue set is built for 1/g- Then, by inserting polynomial interpolants (e.g. affine combinations of adjacent ( (4) and (0o, k++1 fx+1)). we can reformulate (7) so that it only contains the da,k- t and definite integrals of the f[|12) For these integrals, look-up tables are easily generated for speedup. The resulting linear system can then be solved to calculate the next step
((22) (Ir, Lx ++h, ht). As
a commonly adapted update rule for step size h. we use half step checks (0.5) (x., Lx + h), where we ? integration error E is then used in the update h - min foax mmax(min(( ( hmax)) hmiul , t' - tk- - h}
(0.3) (z, tg + h)). The do two steps using h as step size and then calculate E = 10 (2) (I. tx + h) Da
with the scaling s = max min tol and the next observation time
E smax), smin) for some pre-specified hmins Amaxs Smins 8max
The resulting HSMM is then only dependent on time-differences, i.e. still homogeneous, but adapts affine combinations are used as interpolants between the points (øa,k, 4)) and an implicit Euler step rule is chosen.
its step-size. In appendix section C, we provide the resulting update equation if
Evaluation
6.1 Calculation of Integral Equations
Our algorithms demand the solution of integral equations of the second kind. For each time interval [t, t') between observations, we used a backward Euler method to solve the possibly stiff equations
in 7 (8) or (10) with fixed number of steps calculated by N == =1"ーT J + 1. Then, all steps are of equal length h except the one at the end of the interval which scales dependent on t'. The integration involved in each step is performed by interpolation between the steps, where the trapezoidal rule has been used. This method outlined in detail in Appendix section B. An exception the evaluation of the adaptive step-size HSMM. As described in section there the step size is initialized by smallest value 10-4 and then the adaptive procedure generates any further grid positions. The integration at each step is also more precise. The details are outlined in Appendix B. For forward and backward passes, each interval alculated consecutively while the inhomogeneities g and 7 are updated upon entering each new interval outline in the algorithm section in Appendix C. The resulting continuous
8

---

a)
b)
truth
semi-Markov
Markov
Cr
X oobervvation
0.2
Mapped state
states
4/23
2-
Vnlx,
A01
x
0.0
10
15
20
25
30
2.5
7.5
10
12.5
15
17.5
20
time
time
truth
X observation
d)
MAP Second best
12
Best
Mapped state
-1
Mapped state 3
10-
Sccond
3-
2-
hidden CTSMC
adaptiva-step IISM
truth
X observalae
8
10
0
2
10 chain length n
12 14
timee
Cime
Figure 2: a) Normalized forward and backward currents (da. 19) of a latent CTSMC in presence of observations (vertical gray dotted lines). The areas outside the actual trajectory show the initial and terminal conditions (extending infinity); b) Mean and variance progression of the posterior latent state marginals ş inferred from the shown trajectory as the original CTSMC (blue) the optimal steady-state CTMC approximation (orange); c) Time grid generated by an adaptive step-size HSMM in forward pass as proposed in section (orange markers). The continuous blue line was generated by discrete HSMM with step size h 10-3; d) MAP latent trajectory estimate for sample trajectory from a four-state hidden CTSMC. Left: estimated trajectory (blue), second-best candidate (orange). Right: the chain length posterior P (n y(o, e)) for different chain lengths n.
functions a, 3, f and the currents then generated for each interval using cubic spline interpolation on the calculated steps.
6.2 Simulations
We calculated several randomly generated hidden CTSMC's. The number of states has been given, but waiting time distributions and transition probabilities were drawn randomly. For each state, we drew randomly parametrized waiting time distribution from specified family of distributions (we allowed Gamma and Weibull). The random parameters, were drawn from Gamma distributions with per-parameter calibrated hyperparameters. The transition probabilities of the embedded Markov chains were sampled as sets of random categorical distributions while prohibiting self-transitions. The categorical distributions were sampled by first drawing a vector uniformly from the |ey-hyyeee and then projecting it to the (I2') --simplxx via normalization. The observation times were drawn from a point process with Gamma inter-arrive times with fixed shape and rate hyperparameters. The observation values were noisy observations of function b X' + E mapping the latent states to fixed values in real observation space y R with the Borel o olalgebra 2) = 23 Only single points were allowed to be drawn, thus requiring density evaluations in the likelihood function v. Therefore, ((t) (bbX((t) (t)), d) with the standard deviation d as a hyperparameter.
The calculated o., 3, á were compared to those calculated by a HSMM. With step-size of hUSMM = 10-1 and hCTSMC 10-3 (backward Fuler step-size), difference was visible anymore any calculated trajectory. backward output currents V.g. In Fig. 2b the smoothed marginals of a four-state CTSMC are compared to those obtained from its steady-state CTMC approximation [13]. For both, smoothed mean and variance of (()(t)) are shown. The full trajectory of 6(X(t)) by the original CTSMC which generated the observations is shown as a ground truth. We built the adaptive step-size HSMM using our proposed method and ran it over the sampled trajectories as well. While quickly enlarging its step-size, it remained within the margins of a total error of 10 compared to fine- fine-grained HSMM, although this is not guaranteed by the method. An example run is shown in Fig. 2 Finally, we tested our Viterbi MAP estimator on the trajectories. An example run is shown in 21. The posterior chain length marginal (n Y(o,o) had a comparably sharp peak in all trajectories. We assume, this came from the observations greatly narrowing down the amount of candidate transition counts.
Fig. 2 we show an exemplary progression of the forward input da and

---

7 Conclusion
We have presented forward-backward framework applicable to hidden CTSMC's. Avoiding state space augmentation to enforce the Markov property, it gives rise to integral and integro-differential forward and backward equations and scalable Viterbi algorithm. Adaptive step-size HSMM's is can be derived, overcoming classical discrete-time core problems: out-of-grid observations and steady-state over-computation. We didn't 't consider CTSMC's that do not satisfy direction-tine independence in this work. These are especially interesting for coarse Searse-graining of large Markovian systems. Nonetheless, the algorithms can be generalized to this case by introduction of prrection-dependeen current.. Also, specific classes of waiting times could allow efficient computation of currents, e.g. power-law waiting times because of their relation fractional calculus. Possible solutions would then fit naturally in our framework which handles observation likelihood of past events. Inference of model parameters, e-g. using an expectation maximization algorithm, can also be tackled using the forward algorithm from section 4.1
Acknowledgements and Funding Disclosure
Nicolai Engelmann and Heinz Koeppl acknowledge support from the European Research Council (ERC) within the CONSYN project, grant agreement number 773196.
References
[1] Ahmed M. Alaa and Mihaela Van Der Schaar. hidden absorbing semi-markov model for informatively censored temporal data: Learning and inference. J. Mach. Learn. Res., 19(1): 108-169, jan 2018. ISSN 1532-4435.
[2] Ahmed M. Alaa, Scott Hu, and Mihaela van der Schaar. Learning from clinical judgments: Semi-Markov-motuulaed marked Hawkes processes for risk prognosis. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 09- PMLR, 06-11 11 Aug 2017.
[3] David Andrieux and Pierre Gaspard. The fluctuation theorem for currents in semi-markov processes. Journal of Staristical Mechanics: Theory and Experiment, 2008(1 11)):111)000) nov 2008. doi: 10. 1..-188//742-54466200000 1ttp////0////11111/1/// 1/p11007.
[4] Christopher T.H. Baker. A perspective on the numerical treatment of volterra equations. Journal of Computational and Applied Mathematics, 125(1):217-249, 2000. ISSN 0377-0427. doi: https://doi.org/ org/ 1016/50377-04270000 Differential Equations and Integral Equations.
Numerical Analysis 2000. Vol. VI: Ordinary
[5] Marco Biagi, Laura Carnevali, Marco Paolieri, Fulvio Patara, and Enrico Vicario. A continuous- time model-based approach for activity recognition in pervasive environments. IEEE Transac- tions on Sluman-Machinn Systems, 49(4):293-30) 2019. doi: 10.1 109/TH9/HSSM... 20TTHHM...0199..0
[6] Francesco Cannarile, Michele Compare, Piero Baraldi, Francesco Di Maio, and Enrico Zio. Homogeneous continuous-tims finite-state hidden semi-markon modeling for enhancing empir- ical classification system diagnostics of industrial components. Machines, 6(3), 2018. ISSN 2075-1702. doi: 33390/mmcchines6300034,,
[7] Jianzhun Du, Joseph Futoma, and Finale Doshi-Velez. Model-based reinforcement learning for semi-markov decision processes with neural odes. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33,
pages 19805-19816 Curran Associates, Inc., 2020.
[8] Raymond Holsapple, Ram Iyer, and David Doman. A variable step-size selection method for implicit integration schemes. In 2006 American Control Conference, pages 6-pp. IEEE, 2006.
[9] Matthew Johnson and Alan Willsky. Stochastic variational inference for bayesian time series models. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1854-1862, Bejing, China, 22-24 Jun 2014. PMLR.
10

---

[10] HM Jones and S McKee. Variable step size predictor-conee corrrctt schemes for second kind volterra integral equations. Mathematics of computation, 44(170):391-40) 1985.
[11] Michael Klann and Heinz Koeppl. Spatial simulations in systems biology: from molecules to cells. International Journal of Molecular Sciences, 13(6):7798-7827, 2012. ISSN 1422-0067. doi: (13390/jjs133667770
[12] Mikko Laine and Aleksi Vuorinen. Basics of thermal field theory. Lect. Notes Phys, 925(1): 1701-01554, 2016.
[13] Nikolaos Limnios and Gheorghe Oprisan. Semi-Markov processes and reliability. Springer Science Business Media, 2001.
[14] Ying Liu, Shuang Li, Fuxin Li, Le Song, and James M. Rehg. Efficient learning of continuous-time hidden markov models for disease progression. In Proceedings of the 28th International Conference Neural Information P Processing Systems Volume 2, NIPS'15 page 3600-3608, Cambridge, MA, USA, 2015. MIT Press.
[15] Christian Maes, Karel Netočný, and Bram Wynants. Dynamical fluctuatiins for semi- markov processes. Journal of Physies A: Mathematical and Theoretical, 42(36):365002, 2009.
[16] Manish Malhotra and Andrew Reibman. Selecting and implementing phase approximations for semi-markov models. Stochastic Models, 94))44335566 1993.
[17] Ramin Moghaddass and Ming J. Zuo. A parameter estimation method for a condition-monitore device under multi-state deterioration. Reliability Engineering System Safery, 106:94-103. 2012. ISSN 0951-8320. doi: http://dbb.rr//1000066/..ssss./
[18] J. R. Norris. Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1997. doi: 10.1017/CB0998051 000007085511110031 1810633.
[19] Masayuki Ohzeki and Akihisa Ichiki. Mathematical understanding of detailed balance condition violation and its application to langevin dynamics. Journal of Physies: Conference Series, 638: 012003, sep 2015. doi: 10. 100.100//11110
[20] Enzo Orsingher, Costantino Ricciuti, and Bruno Toaldo. On semi-markov processes and their kolmogorov' 's -iffrro-differentiall equations. Journal of Functional Analysis, 275(4):830-88) 2018. ISSN 0022-1236. doi:
[21] Felix Salfner. Modeling event-driven time series with generalized hidden semi-markov models. 2006.
[22] Shun-Zheng Yu. Hidden semi-markov models. Artificial Intelligence, 174(2):15-244,, 2010. ISSN 0004-3702. doi:
Special Review Issue.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODDO] (Ys]] [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In Appendix A
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] In the Supplement
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In Appendix E
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/]]
12


Reviews:
[{"review_id": "s5xJH2-I18P", "reviewer": "Reviewer_if4n", "summary": "This paper propose inference algortihms for hidden continuous time semi-Markov\nchains (latent CTSMCs). Specifically it focuses on homogeneous and direction-time \nindependent CTSMCs. Both inference of posterior probabilities of latent states \ngiven observations, as well as maximum-a posteriori state path are addressed.\nThe foundation of the algorithm is the observation that given a transition\nevent at a specific time, past and future dynamics become independant. Therefore,\nthe core element is to update the intensity of such event (termed current) as a \nfunction of time and state. These updates involve integral equations that are solved \nusing numerical methods.\n", "questions": "**Suggestions**\n1. The role of current is introduced in Section 2.1. At this point it will be\ngood to state what are the challenges in computing them and to outline the approach\nfor doing so.\n2. Give detailed explanations about the initial conditions introduced after\nEquation 5 and in the algorithm summary.\n3. Give a short intuitive explanation about how integral equations are solved,\nwhat is the complexity of the solvers and the overall method. This is important\nin addition to the references that appear.\n4. Provide a summary of all the steps involved in the algorithm.\n\n**Questions and minor comments** \n1. Lines 112, 114: Should 'leaving' be replaced by 'entering' in line 112 and vice \n\tversa in line 114?\n2. Line 126: the current seem to be a density of a joint probability not a probability;\nis likelihood is a better term?\n3. Figure 1: Do the Gamma distributions refer to sojourn time?\n4. Line 134: What is the meaning of 'assume a terminal condition to be fixed at $T$?\nDoes it mean the we observed the end state? Do we observe also how the entry time\nto this state?\n5. Line 141: the opening sentence is not clear. \n6. **Equation 5:** what is $g_p$? Why is there an addition here? What are the properties\nof this function? Also in line 153: What properties should $g_\\phi$ satisfy? \n7. Line 154: the motivation to demanding a transition shortly after $t$ is not \nclear.\n8. Line 189: fix the reference. \n9. 201: Can you give a time-domain expression for $\\kappa$ and explain what is gained\n10. Equation 13: can you give an explicit reminder-reference there to how $\\phi_\\alpha$ \nand $\\psi_\\beta$ are computed as by-products? \n11. Line 317: fix 'differemces'\n", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis work tackles a very fundamental and important problem. The authors seem\nexploit the structured representation of direction-time Independence in a elegant way,\nnamely by focusing on the representation of currents. \n \nWeaknesses:\nAlthough the setup is well written, starting from Section 2.2 the derivations become\nhard to follow and it is hard to judge all the elements. The initial conditions are not \nclear. Additionally, the numerical algorithm as well as the overall complexity is not \nwell described. See suggestions below regarding missing descriptions and flow.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CILnPtzso-T", "reviewer": "Reviewer_LD4m", "summary": "This paper considers inference in Hidden Continuous-Time semi-Markov Chains. The authors derive a tractable algorithm for inference in these models. Notably, the authors consider the challenging case of irregularly spaced data. The introduced algorithm is of a forward-backward type; the output of this algorithm can be used for smoothing. This brings inference in the model class in line with other similar models. \n", "questions": "Could you give one example of an application of such a model? Where would you find this kind of data? The method is presented in entirety without any reference to applications. It would be good to have an idea of the practical scale of applicability of this method. \n\nFrom a numerics point of view, I don't really understand the discussion in the first paragraph of section 4.2, which seems somewhat crucial to the practical implementation of the method. You say that using (13) is numerically more costly but at the same time more stable. This is in comparison to the method presented in appendix C.\n\nMinor comments:\n\ntypo on line 333 \"where\" should be \"were\" \ntypo on line 347 \"testet\" should be \"tested\"\n", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this paper makes a good contribution. I have enjoyed reading the paper and it is well-written and (together with the supplementary material) provides sufficient detail to understand the proposed methodology. The derivation of the forward-backward equations for the considered model is non-trivial and at the same time a very natural question to ask. A more principled inference method as an alternative to existing ad hoc ones is certainly welcome. \n\nWhy not provide a description of the (main) forward-backward algorithm step by step in the main paper instead of leaving in to supplementary section C, where it is nicely described? \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8YDf5SLrp7", "reviewer": "Reviewer_6Ntb", "summary": "The paper generalizes latent state inference from HSMMs to continuous-time chains in latent space. In this case, the posterior is not simply proportional to the usual forward and backward probabilities. Instead, the transition random variables (\"currents\") are Markov. The authors take the limit of step size approaching 0 for these currents. The paper shows that the marginal $p(x, t)$, in this case, is found by a convolution over the input currents. Similarly, the output currents are a convolution over the input currents. Including observations, the authors derive Kolmogorov forward and backward equations, leading to algorithms akin to the classical sum-product (belief propagation) and max-sum (Viterbi) message-passing algorithms, but in continuous time. An additional advantage of the continuous formulation is the availability of adaptive step-sizing in the continuous case. The algorithms, as well as adaptive step-sizing, are evaluated in 1D experiments. ", "questions": "- What is the black line in figures 2b,c? Is it the underlying ground truth state? If so, why does the blue HSMM with adaptive step size line in 2c seem to perform so poorly?", "limitations": "The authors properly discuss the limitations in the conclusion.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Strong theoretical foundation.\n- Important generalization of well-known important algorithms to the continuous-time case.\n- Adaptive step-sizing.\n\nWeaknesses:\n- The paper was a bit hard to follow from time to time. This could either be due to my lack of background knowledge but also perhaps due to the quite liberal suppression of function arguments and sometimes rather cluttered mathematics mid-sentence.\n\n\nMinor:\n- Some typos: l271: \"therefor\", l317: \"differemces\", l189: equation reference failed, l274: what does \"(x)\" refer to?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-a5x09NajJH", "reviewer": "Reviewer_cruP", "summary": "The paper describes a class of models which the authors characterize as being \"continuous time hidden semi-Markov chains\" and provides an inferential framework for this class of models generalising the classical algorithms for HMM inference to this context.", "questions": "1. My first thought on seeing this paper was that in continuous time something like a hidden semi-Markov model is actually very much more natural than it is in discrete time where one has to jump through artificial hoops to induce the non-geometric holding time distribution. To what extent are hidden semi-Markov models different to the setting in which one has a latent piecewise deterministic Markov process in the sense of [Davis, M. H. A. (1984). \"Piecewise-Deterministic Markov Processes: A General Class of Non-Diffusion Stochastic Models\". Journal of the Royal Statistical Society. Series B (Methodological). 46 (3): 353–388. doi:10.1111/j.2517-6161.1984.tb01308.x. JSTOR 2345677.]? \n\n2. Following up on 1, how does what is presented here relate to what is known for filtering in the setting in which one has a latent PDMP? As the PDMP class is much broader than that considered here it's very probable that substantial benefits can be obtained by considering this particular context but it would be nice to see this discussed a little.\n\n3. Are there settings in which you envisage the method having real world application? The numerical example in this paper is underwhelming in that regard.\n\nMinor details:\nline 80: This seems to describe an overly general observation space Y given it's assumed to be real and to have a known conditional distribution function.\nline 85: this is the intersection isn't what's intended, is it? It's the intersection of possibly several points and hence typically empty. I think what's wanted is actually the intesection of the events so the intersection hould come outside the { } and it might be clearer if the implicit \\omega were made explicit.\n(2) could be made clearer: what precisely does \"Markov at jump instances\" mean. Can you give a reference?\nl189 (??)\nl317 time-differemces,\nl331 \"detailled\"\nl342 10^-4 and 10^-3\nl344 \"adative\"\nl347 testet\"\n", "limitations": "The authors have indicated that societal implications are N/A for this work and given the nature of the paper I think that is appropriate. I didn't note any particular limitations that are not discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a timely piece of work in the sense that there have been several innovations relating to inference for HSMMs in recent years and the development herein seems somewhat more principled than many of them. Working directly in continuous time seems to allow for a relatively clean derivation of forward and backward equations that facilitate the inferential tasks of interest. My impression is that there is currently interest in performing inference for this type of model and hence the work is likely to find an audience.\n\nThe main weaknesses, to my mind are:\n1. The bulk of the paper is dedicated to fairly routine computations and the extent of the novelty is perhaps a little limited.\n2. A lack of connection with the wider literature on hidden continuous time processes.\n3. The empirical study lacks any compelling application or use case to showcase the model or demonstrate its broad importance.\n4. The manuscript seems to have been a little hastily prepared and would benefit from careful proofreading (see the minor details in the next section for a few example typos)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept