The Partially Observable Hidden Markov Model
and its Application to Keystroke Dynamics
John V. Monacoa,∗, Charles C. Tappertb

arXiv:1607.03854v7 [cs.IT] 20 Nov 2017

a U.S.

Army Research Laboratory, Aberdeen Proving Ground, MD 21005, USA
b Pace University, Pleasantville, NY 10570, USA

Abstract
The partially observable hidden Markov model is an extension of the hidden
Markov Model in which the hidden state is conditioned on an independent
Markov chain. This structure is motivated by the presence of discrete metadata,
such as an event type, that may partially reveal the hidden state but itself
emanates from a separate process. Such a scenario is encountered in keystroke
dynamics whereby a user’s typing behavior is dependent on the text that is
typed. Under the assumption that the user can be in either an active or passive
state of typing, the keyboard key names are event types that partially reveal the
hidden state due to the presence of relatively longer time intervals between words
and sentences than between letters of a word. Using five public datasets, the
proposed model is shown to consistently outperform other anomaly detectors,
including the standard HMM, in biometric identification and verification tasks
and is generally preferred over the HMM in a Monte Carlo goodness of fit test.
Keywords: hidden Markov model, keystroke biometrics, behavioral
biometrics, time intervals, anomaly detection

1. Introduction
The hidden Markov model (HMM), which dates back over 50 years [1], has
seen numerous applications in the recognition of human behavior, such as speech
[2], gesture [3], and handwriting [4]. Recent successes have leveraged the expressive power of connectionist models by combining the HMM with feed-forward
deep neural networks, which are used to estimate emission probabilities [5, 6, 7].
Despite the increasing interest in sequential deep learning techniques, e.g., recurrent neural networks, HMMs remain tried-and-true for time series analyses.
The popularity and endurance of the HMM can be at least partially attributed
∗ Corresponding

author
Email address: john.v.monaco2.civ@mail.mil (John V. Monaco)
URL: http://www.vmonaco.com (John V. Monaco)

Pattern Recognition (accepted manuscript)

November 21, 2017

2
to the tractability of core problems (parameter estimation and likelihood calculation), ability to be combined with other methods, and the level of insight it
provides to the data.
At least part its success can also be attributed to its flexibility, with many
HMM variants having been developed for specific applications. This usually
involves introducing a dependence, whether it be on time [8], previous observations [9], or a semantic context [10]. The motivation for doing so is often
to better reflect the structure of the underlying problem. Although many of
these variations have increased complexity and number of parameters over the
standard HMM, their estimation remains tractable.
In this work, we introduce the partially observable hidden Markov model
(POHMM), an extension of the HMM intended for keystroke dynamics. We are
interested in modeling the temporal behavior of a user typing on a keyboard,
and note that certain keyboard keys are thought to influence typing speed. Nonletter keys, such as punctuation and the Space key, indicate a greater probability
of being in a passive state of typing, as opposed to an active state, since the
typist often pauses between words and sentences as opposed to between letters
in a word [11]. The POHMM reflects this scenario by introducing a dependency
on the key names which are observed alongside the time intervals, and in this
way, the keys provide a context for the time intervals.
The idea of introducing a context upon which some behavior depends is
not new. Often, an observation depends not only on a latent variable but
on the observations that preceded it. For example, the neighboring elements
in a protein secondary structure can provide context for the element under
consideration, which is thought to depend on both the previous element and a
hidden state [9]; nearby phonemes can aid in the recognition of phonemes [12];
and the recognition of human activities can be achieved with greater accuracy
by considering both a spatial context (e.g., where the activity occurred) and
temporal context (e.g., the duration of the activity) [13].
Handwriting recognition has generally seen increased performance with models that consider the surrounding context of a handwritten character. The rationale for such an approach is that a character may be written with different
style or strokes depending on its neighboring characters in the sequence. Under this assumption, the neighboring pixels or feature vectors of neighboring
characters can provide additional context for the character under consideration.
Alternatively, a separate model can be trained for each context in which the
character appears, e.g., “t” followed by “e” versus “t” followed by “h” [10]. This
same principle motivates the development of the POHMM, with the difference
being that the context is provided not by the observations themselves, but by
a separate sequence.
We apply the POHMM to address the problems of user identification, verification, and continuous verification, leveraging keystroke dynamics as a behavioral biometric. Each of these problems requires estimating the POHMM parameters for each individual user. Identification is performed with the maximum
a posteriori (MAP) approach, choosing the model with maximum a posterior
probability; verification, a binary classification problem, is achieved by using

3
the model log-likelihood as a biometric score; and continuous verification is
achieved by accumulating the scores within a sliding window over the sequence.
Evaluated on five public datasets, the proposed model is shown to consistently
outperform other leading anomaly detectors, including the standard HMM, in
biometric identification and verification tasks and is generally preferred over the
HMM in a Monte Carlo goodness of fit test.
All of the core HMM problems remain tractable for the POHMM, including parameter estimation, hidden state prediction, and likelihood calculation.
However, the dependency on event types introduces many more parameters to
the POHMM than its HMM counterpart. Therefore, we address the problem of
parameter smoothing, which acts as a kind of regularization and avoids overfitting [14]. In doing so, we derive explicit marginal distributions, with event type
marginalized out, and demonstrate the equivalence between the marginalized
POHMM and the standard HMM. The marginal distributions conveniently act
as a kind of backoff, or fallback, mechanism in case of missing data, a technique
rooted in linguistics [15].
The rest of this article is organized as follows. Section 2 briefly describes
keystroke dynamics as a behavioral biometric. Section 3 introduces the POHMM,
followed by a simulation study in Section 4 and a case study of the POHMM
applied to keystroke dynamics in Section 5. Section 6 reviews previous modeling
efforts for latent processes with partial observability and contains a discussion.
Finally, Section 7 concludes the article. The POHMM is implemented in the
pohmm Python package and source code is publicly available1 .
2. Keystroke dynamics
Keystroke dynamics refers to the way a person types. Prominently, this
includes the timings of key press and release events, where each keystroke is
comprised of a press time tn and a duration dn . The time interval between
key presses, τn = tn − tn−1 , is of interest. Compared to random time intervals
(RTIs) in which a user presses only a single key [16], key press time intervals
occur between different keys and are thought to be dependent on key distance
[11]. A user’s keystroke dynamics is also thought to be relatively unique to
the user, which enable biometric applications, such as user identification and
verification [17].
As a behavioral biometric, keystroke dynamics enables low-cost and nonintrusive user identification and verification. Keystroke dynamics-based verification can be deployed remotely, often as a second factor to username-password
verification. Some of the same attributes that make keystroke dynamics attractive as a behavioral biometric also present privacy concerns [18], as there
exist numerous methods of detecting keystrokes without running software on
the victim’s computer. Recently, it has been demonstrated that keystrokes can
1 Available

at https://github.com/vmonaco/pohmm and through PyPI.

4
be detected through a wide range of modalities including motion [19], acoustics
[20], network traffic [21], and even WiFi signal distortion [22].
Due to the keyboard being one of the primary human-computer interfaces,
it is also natural to consider keystroke dynamics as a modality for continuous verification in which a verification decision is made upon each key pressed
throughout a session [23]. Continuous verification holds the promise of greater
security, as users are verified continuously throughout a session beyond the initial login, which is considered a form of static verification. Being a sequential
model, the POHMM is straightforward to use for continuous verification in addition to identification and static verification.
Keystroke time intervals emanate from a combination of physiology (e.g.,
age, gender, and handedness [24]), motor behavior (e.g., typing skill [11]), and
higher-level cognitive processes [25], highlighting the difficulty in capturing a
user’s typing behavior in a succinct model. Typing behavior generally evolves
over time, with highly-practiced sequences able to be typed much quicker [26].
In biometrics, this is referred to as template aging. A user’s keystroke dynamics
is also generally dependent on the typing task. For example, the time intervals
observed during password entry are much different than those observed during
email composition.
3. Partially observable hidden Markov model
The POHMM is intended for applications in which a sequence of event types
provides context for an observed sequence of time intervals. This reasoning
extends activities other than keystroke dynamics, such as email, in which a
user might be more likely to take an extended break after sending an email
instead of receiving an email, and programming, in which a user may fix bugs
quicker than making feature additions. The events types form an independent
Markov chain and are observed alongside the sequence of time intervals. This
is in contrast to HMM variants where the neighboring observations themselves
provide a context, such as the adjacent characters in a handwritten segment
[10]. Instead, the event types are independent of the dynamics of the model.
With this structure, a distinction can be made between user behavior and
task : the time intervals comprise the behavior, and the sequence of event types,
(e.g., the keys pressed) comprise the task. While the time intervals reflect how
the user behaves, the sequence of events characterize what the user is doing.
This distinction is appropriate for keystroke dynamics, in which the aim is to
capture typing behavior but not the text itself which may more appropriately
modeled by linguistic analysis. Alternatively, in case the user transcribes a
sequence, such as in typing a password, the task is clearly defined, i.e. the user
is instructed to type a particular sequence of characters. The POHMM aims to
capture the temporal behavior, which depends on the task.
3.1. Description
The HMM is a finite-state model in which observed values at time t depend
on an underlying latent process [2]. At the nth time step tn , a feature vector

3.1

5

Description

Event type
(observed)

ω1

ω2

ω N −1

ωN

State
(hidden)

z1

z2

z N −1

zN

Emission
(observed)

x1

x2

x N−1

xN

1

2

N −1

N

t
0

Figure 1: Partially observable hidden Markov model structure. Observed values (emission
and event type) are shown in gray, hidden values (system state) are shown in white.

xn is emitted and the system can be in any one of M hidden states, zn . Let
N
xN
1 be the sequence of observed emission vectors and z1 the sequence of hidden
states, where N is the total number of observations. The basic HMM is defined
by the recurrence relation,

P xn+1
, z1n+1 = P (xn1 , z1n ) P (xn+1 |zn+1 ) P (zn+1 |zn ) .
1

(1)

The POHMM is an extension of the HMM in which the hidden state and emission depend on an observed independent Markov chain. Starting with the HMM
axiom in Equation 1, the POHMM is derived through following assumptions:
1. An independent Markov chain of event types is given, denoted by ΩN
1 .
2. The emission xn+1 depends on event type Ωn+1 in addition to zn+1 .
3. The hidden state zn+1 depends on Ωn and Ωn+1 in addition to zn .
Applying the above assumptions to the HMM axiom, the conditional emission
probability P (xn+1 |zn+1 ) becomes P (xn+1 |zn+1 , Ωn+1 ); the conditional hidden
state probability P (zn+1 |zn ) becomes P (zn+1 |zn , Ωn , Ωn+1 ); and the recurrence
relation still holds. The complete POHMM axiom is given by the formula,

P xn+1
, z1n+1 = P (xn1 , z1n ) P (xn+1 |zn+1 , Ωn+1 ) P (zn+1 |zn , Ωn , Ωn+1 ) (2)
1
where Ωn and Ωn+1 are the observed event types at times tn and tn+1 . The
POHMM structure is shown in Figure 1.
The event types come from a finite alphabet of size m. Thus, while the HMM
has M hidden states, a POHMM with m event types has M hidden states per
event type, for a total of m × M unique hidden states.
The event type can be viewed as a partial indexing to a much larger state
space. Each observed event type restricts the model to a particular subset of M
hidden states with differing probabilities of being in each hidden state, hence the
partial observability. The POHMM starting and emission probabilities can be
viewed as an HMM for each event type, and the POHMM transition probabilities
as an HMM for each pair of event types.

3.1

6

Description

Time

Observed
emission

Observed
event type

1

xb1

b

Hidden state

1a

2a

1b

2b

1c

2c

Possible
transitions

2

xa2

a

1a

2a

1b

2b

1c

2c

3

xa3

ac

1a

2a

1b

2b

1c

2c

Figure 2: POHMM event types index a much larger state space. In this example, there are
two hidden states and three event types. Given observed event type b at time 1, the system
must be in one of the hidden states {1b, 2b}. The a observed at the next time step limits the
possible transitions from {1b, 2b} to {1a, 2a}.

To illustrate this concept, consider a POHMM with two hidden states and
three event types, where Ω31 = [b, a, c]. At each time step, the observed event
type limits the system to hidden states that have been conditioned on that event
type, as demonstrated in Figure 2. Beginning at time 1, given observed event
type Ω1 = b, the system must be in one of the hidden states {1b, 2b}. Event type
Ω2 = a observed at time 2 then restricts the possible transitions from {1b, 2b}
to {1a, 2a}. Generally, given any event type, the POHMM must be in one of M
hidden states conditioned on that event type. Section 3.6 deals with situations
where the event type is missing or has not been previously observed in which
case the marginal distributions (with the event type marginalized out) are used.
The POHMM parameters are derived from the HMM. Model parameters
include π [j|ω], the probability of starting in state j given event type ω, and
a [i, j|ψ, ω], the probability of transitioning from state i to state j, given event
types ψ and ω before and after the transition, respectively2 . Let f (·; b [j|ω]) be
the emission distribution that depends on hidden state j and event type ω, where
b [j|ω] parametrizes density function f (·). The complete set of parameters
is denoted by θ = {π, a, b}, where a is the m2 M 2 transition matrix. While
the total number of parameters in the HMM is M + M 2 + M K, where K
is the number of free parameters in the emission distribution, the POHMM
contains mM + m2 M 2 + mM K parameters. After accounting for normalization
constraints, the degrees of freedom (dof ) is m (M − 1)+m2 M (M − 1)+mM K.
Marginal distributions, in which the event type is marginalized out, are
also defined. Let π [j] and f (·; b [j]) be the marginalized starting and emission
probabilities, respectively. Similarly, the parameters a [i, j|ω], a [i, j|ψ], and
a [i, j] are defined as the transition probabilities after marginalizing out the first,
second, and both event types, respectively. The POHMM marginal distributions
are exactly equal to the corresponding HMM that ignores the event types. This
2 When a transition is involved, i and ψ always refer to the hidden state and event type,
respectively, before the transition; j and ω refer to those after the transition.

3.2

Model likelihood

7

ensures that the POHMM is no worse than the HMM in case the event types
provide little or no information as to the process being modeled. Computation of
POHMM marginal distributions is covered in Section 3.6 and simulation results
demonstrating this equivalence are in Section 4.
It may seem that POHMM parameter estimation becomes intractable, as
the number of possible transitions between hidden states increases by a factor
of m2 over the HMM and all other parameters by a factor of m. In fact, all
of the algorithms used for the POHMM are natural extensions of those used
for the HMM : the POHMM parameters and variables are adapted from the
HMM by introducing the dependence on event types, and parameter estimation
and likelihood calculation follow the same basic derivations as those for the
HMM. POHMM parameter estimation remains linearly bounded in the number
of observations, similar to the HMM, performed through a modification of the
Baum-Welch (BW) algorithm. The convergence property of the modified BW
algorithm is demonstrated analytically in Section 3.4 and empirically in Section
4. The rest of this section addresses the three main problems of the POHMM,
taken analogously as the three main problems of the HMM:
N
1. Determine P (xN
1 |Ω1 , θ), the likelihood of an emission sequence given the
model parameters and the observed event types.
2. Determine z1N , the maximum likelihood sequence of hidden states, given
N
the emissions xN
1 and event types Ω1 .
N
N
3. Determine arg maxθ∈Θ P (x1 |Ω1 , θ), the maximum likelihood parameters
θ for observed emission sequence xN
1 , given the event type sequence.

The first and third problems are necessary for identifying and verifying users in
biometric applications, while the second problem is useful for understanding user
behavior. The rest of this section reviews the solutions to each of these problems
and other aspects of parameter estimation, including parameter initialization
and smoothing.
3.2. Model likelihood
Since we assume ΩN
1 is given, it does not have a prior distribution. Therefore, we consider only the likelihood of an emission sequence given the model
N
N 3
parameters θ and the observed event type sequence ΩN
1 , denoted by P (x1 |Ω1 ) ,
N
)
as
an
item
for
future
work.
leaving the joint model likelihood P (xN
,
Ω
1
1
In the HMM, P (xN
1 ) can be computed efficiently by the forward procedure
which defines a recurrence beginning at the start of the sequence. This procedure
differs slightly for the POHMM due to the dependence on event types. Notably,
the starting, transition, and emission parameters are all conditioned on the given
event type.
Let αn [zn , Ωn ] ≡ P (xn1 , zn |Ωn ), i.e., the joint probability of emission subsequence xn1 and hidden state zn , given event type Ωn . Then, by the POHMM
axiom (Equation 2), αn [zn , Ωn ] can be computed recursively by the formula,
3 For

N
N
N
brevity, the dependence on θ is implied, writing P (xN
1 |Ω1 , θ) as P (x1 |Ω1 ).

3.3

8

Hidden state prediction

αn+1 [zn+1 , Ωn+1 ]

=

P (xn+1 |zn+1 , Ωn+1 )
X
×
P (zn+1 |zn , Ωn , Ωn+1 ) αn [zn , Ωn ]

α1 [z1 , Ω1 ]

=

P (x1 |z1 , Ω1 ) P (z1 |Ω1 )

(3)

zn

(4)

where Equation 4 provides the initial condition. The modified forward algorithm
is obtained by substituting the model parameters into Equations 3 and 4, where
π [j|ω] ≡ P (z1 = j|Ω1 = ω)
f (xn ; b [j, ω])

≡ P (xn |zn = j, Ωn = ω)

a [i, j|ψ, ω] ≡ P (zn+1 = j|zn = i, Ωn = ψ, Ωn+1 = ω)

(5)
(6)
(7)

and αn [j, ω] is the sequence obtained after substituting the model parameters.
N
N
The
PM model likelihood is easily computed upon termination, since P (x1 |Ω1 ) =
j=1

αN [j, ω] where ω = ΩN .

A modified backward procedure is similarly
defined through a backwards

recurrence. Let βn [zn , Ωn ] ≡ P xN
n+1 |zn , Ωn . Then under the POHMM axiom,
βn [zn , Ωn ]

=

X

P (xn+1 |zn+1 , Ωn+1 )

(8)

zn+1

×P (zn+1 |zn , Ωn , Ωn+1 ) βn+1 [zn+1 , Ωn+1 ]
βN [zN , ΩN ]

=

(9)

1.

where βn [j, ω] is the sequence obtained after making the same substitutions.
Note that at each n, αn [j, ω] and βn [j, ω] need only be computed for the
observed ω = Ωn , i.e., we don’t care about event types ω 6= Ωn . Therefore,
only the hidden states (and not the event types) are enumerated in Equations
3 and 8 at each time step. Like the HMM, the modified forward and backward
algorithms have time complexity O(M 2 N ) and can be stored in a N ×M matrix.
3.3. Hidden state prediction
The maximum likelihood sequence of hidden states is efficiently computed
using the event type-dependent forward and backward variables defined above.

First, let the POHMM forward-backward variable γn [zn , Ωn ] ≡ P zn |Ωn , xN
1 ,
i.e., the posterior probability of hidden state zn , given event type Ωn and the
emission sequence xN
1 . Let γn [j, ω] be the estimate obtained using the model
parameters, making the same substitutions as above. Then γn [j, ω] is straightforward to compute using the forward and backward variables, given by
γn [j, ω]

=

αn [j|ω] βn [j|ω]
N
P (xN
1 |Ω1 )

(10)

3.4

9

Parameter estimation

Algorithm 1 Modified Baum-Welch for POHMM parameter estimation.
1. Initialization
Choose initial parameters θo and let θ ← θo .

2. Expectation

N
Use θ, xN
1 , Ω1 to compute αn [j|ω], βn [j|ω] , γn [j, ω], ξn [i, j|ψ, ω].
3. Maximization

Update θ using the re-estimation formulae (Eqs. 12, 14, 15) to get θ̇ = π̇, ȧ, ḃ .
4. Regularization
Calculate marginal distributions and apply parameter smoothing formulae.
5. Termination 

N
N
N
If ln P xN
1 |Ω1 , θ̇ − ln P x1 |Ω1 , θ < , stop; else let θ ← θ̇ and go to step 2.

=

αn [j|ω] βn [j|ω]
PM
i=1 αn [i|ω] βn [i|ω]

where ω = Ωn . The sequence of maximum likelihood hidden states is taken as,
zn = arg max1≤j≤M γn [j, ω] .

(11)

Similar to αn [j|ω]
 and βn [j|ω], γn [j, ω] can be stored in a N × M matrix and
takes O M 2 N time to compute. This is due to the fact that the event types
are not enumerated at each step; the dependency on the event type propagates
all the way to the re-estimated parameters, defined below.
3.4. Parameter estimation
Parameter estimation is performed iteratively, updating the starting, transition, and emission parameters using the current model parameters and observed
sequences. In each iteration of the modified Baum-Welch algorithm, summarized
in Algorithm 1, the model parameters are re-estimated using the POHMM forward, backward, and forward-backward variables. Parameters are set to initial
values before the first iteration, and convergence is reached upon a loglikelihood
increase of less than .
3.4.1. Starting parameters
Using the modified forward-backward variable given by Equation 10, the
re-estimated POHMM starting probabilities are obtained directly by
π̇ [j|ω] = γ1 [j|ω]

(12)

where ω = Ω1 and re-estimated parameters are denoted by a dot. Generally,
it may not be possible to estimate π̇ [j|ω] for many ω due to there only being
one Ω1 (or several Ω1 for multiple observation sequences). Parameter smoothing, introduced in Section 3.7, addresses this issue of missing and infrequent
observations.

3.4

10

Parameter estimation

3.4.2. Transition parameters
In contrast to the HMM, which has M 2 transition probabilities, there are
m M 2 unique transition probabilities
in the POHMM. Let ξn [zn , zn+1 |Ωn , Ωn+1 ] ≡

,
i.e.,
the
probability
of transitioning from state zn to
P zn+1 |zn , Ωn , Ωn+1 , xN
1
zn+1 , given event types Ωn and Ωn+1 as well as the emission sequence. Substituting the forward and backward variable estimates based on model parameters,
this becomes ξn [i, j|ψ, ω], given by
2

ξn [i, j|ψ, ω] =

αn [i, ω] a [i, j|ψ, ω] f (xn+1 ; b [j|ω]) βn [j|ω]
.
N
P (xN
1 |Ω1 )

(13)

for 1 ≤ n ≤ N − 1, ψ = Ωn and ω = Ωn+1 . The updated transition parameters
are then calculated by
PN −1

n=1 ξn [i, j|ψ, ω] δ (ψ, Ωn ) δ (ω, Ωn+1 )
PN −1
n=1 γn [i|ψ] δ (ψ, Ωn ) δ (ω, Ωn+1 )

ȧ [i, j|ψ, ω] =

(14)

where δ (ω, Ωn ) = 1 if ω = Ωn and 0 otherwise. Note that ȧ [i, j|ψ, ω] depends
only on the transitions between event types ψ and ω in ΩN
1 , i.e., where Ωn = ψ
and Ωn+1 = ω, as the summand in the numerator equals 0 otherwise. As a
result, the updated transition probabilities can be computed in O(M 2 N ) time,
the same as the HMM, despite there being m2 M 2 unique transitions.

3.4.3. Emission parameters
For each hidden state and event type, the emission distribution parameters
are re-estimated through the optimization problem,
ḃ [j|ω] = arg max
b∈B

N
X

γn [j|ω] ln f (xn ; b) δ (ω, Ωn ) .

(15)

n=1

Closed-form expressions exist for a variety of emission distributions. In this
work, we use the log-normal density for time intervals. The log-normal has
previously been demonstrated as a strong candidate for modeling keystroke
time intervals, which resemble a heavy-tailed distribution [27]. The log-normal
density is given by
"
#
2
1
− (ln x − η)
f (x; η, ρ) = √ exp
2ρ2
xρ 2π

(16)

where η and ρ are the log-mean and log-standard deviation, respectively. The
emission parameter re-estimates are given by
PN
η̇ [j|ω] =

n=1

PN

γn [j|ω] ln τn δ (ω, Ωn )

n=1

γn [j|ω] δ (ψ, Ωn )

(17)

3.5

11

Parameter initialization

and

PN

2

n=1

ρ̇ [j|ω] =

γn [j|ω] (ln τn − η̇j|ω )2 δ (ω, Ωn )
PN
n=1 γn [j|ω] δ (ψ, Ωn )

(18)

for hidden state j, given event type ω. Note that the estimates for η̇ [j|ω] and
ρ̇ [j|ω] depend only on the elements of γn [j|ω] where Ωn = ω.
3.4.4. Convergence properties
The modified Baum-Welch algorithm for POHMM parameter estimation
(Algorithm 1) relies on the principles of expectation maximization (EM) and is
guaranteed to converge to a local maximum. The re-estimation formula (Equations 12, 14, and 15) are derived from inserting the model parameters from


two successive iterations, θ and θ̇, into Baum’s auxiliary function, Q θ, θ̇ ,
 
and maximizing Q θ, θ̇ with respect to the updated parameters. Convergence
properties are evaluated empirically in Section 4, and Appendix B contains a
proof of convergence, which follows that of the HMM.
3.5. Parameter initialization
Parameter estimation begins with parameter initialization, which plays an
important role in the BW algorithm and may ultimately determine the quality
of the estimated model since EM guarantees only locally maximum likelihood
estimates. This work uses an observation-based parameter initialization procedure that ensures reproducible parameter estimates, as opposed to random
initialization. The starting and transition probabilities are simply initialized as
π [j|ω]

=

a [i, j|ψ, ω]

=

1
M
1
M

(19)
(20)

for all i, j, ψ, and ω. This reflects maximum entropy, i.e., uniform distribution,
in the absence of any starting or transition priors.
Next, the emission distribution parameters are initialized. The strategy proposed here is to initialize parameters in such a way that there is a correspondence
between hidden states from two different models. That is, for any two models
with M = 2, hidden state j = 1 corresponds to the active state and j = 2
corresponds to the passive state. Using a log-normal emission distribution, this
is accomplished by spreading the log-mean initial parameters. Let
PN
η [ω] =
and
2

ρ [ω] =

PN

n=1 ln xn δ (ω, Ωn )
PN
n=1 δ (ω, Ωn )

2
n=1 (ln xn − η [ω]) δ (ω, Ωn )
PN
n=1 δ (ω, Ωn )

(21)

(22)

3.6

12

Marginal distributions

be the observed log-mean and log-variance for event type ω. The model parameters are then initialized as


2h (j − 1)
η [j|ω] = η [ω] +
− h ρ [ω]
(23)
M −1
and

ρ2 [j|ω] = ρ2 [ω]

(24)

for 1 ≤ j ≤ M , where h is a bandwidth parameter. Using h = 2, initial states
are spread over the interval [η [ω] − 2ρ [ω] , η [ω] + 2ρ [ω]], i.e., 2 log-standard
deviations around the log-mean. This ensures that j = 1 corresponds to the
state with the smaller log-mean, i.e., the active state.

3.6. Marginal distributions
When computing the likelihood of a novel sequence, it is possible that some
event types were not encountered during parameter estimation. This situation
arises when event types correspond to key names of freely-typed text and novel
key sequences are observed during testing. A fallback mechanism (sometimes
referred to as a “backoff” model) is typically employed to handle missing or
sparse data, such as that used linguistics [15]. In order for the POHMM to
handle missing or novel event types during likelihood calculation, the marginal
distributions are used. This creates a two-level fallback hierarchy in which
missing or novel event types fall back to the distribution in which the event
type is marginalized out.
Note also that while we assume ΩN
1 is given (i.e., has no prior), the individual
Ωn do have a prior defined by their occurrence in ΩN
1 . It is this feature that
enables the event type to be marginalized out to obtain the equivalent HMM.
Let the probability of event type ω at time t1 be π [ω], and the probability
of transitioning from event type ψ to ω be denoted by a [ψ, ω]. Both can be
computed directly from the event type sequence ΩN
1 , which is assumed to be
a first-order Markov chain. The marginal π [j] is the probability of starting in
hidden state j in which the event type has been marginalized out,
X
π [j] =
π [j|ω] π [ω]
(25)
ω∈Ω

where Ω is the set of unique event types in ΩN
1 .
Marginal transition probabilities are also be defined. Let a [i, j|ψ] be the
probability of transitioning from hidden state i to hidden state j, given event
type ψ while in hidden state i. The second event type for hidden state j has
been marginalized out. This probability is given by
X
a [i, j|ψ] =
a [i, j|ψ, ω] a [ψ, ω] .
(26)
ω∈Ω

3.7

13

Parameter smoothing

The marginal probability a [i, j|ω] is defined similarly by
P
ψ∈Ω a [i, j|ψ, ω] a [ψ, ω]
P
a [i, j|ω] =
.
ψ∈Ω a [ψ, ω]

(27)

Finally, the marginal a [i, j] is the probability of transitioning from i to j,
a [i, j] =

1 XX
a [i, j|ψ, ω] a [ψ, ω] .
m

(28)

ψ∈Ω ω∈Ω

No denominator is needed in Equation 26 since the normalization constraints
of both transition matrices
P carry
P over to the left-hand side. Equation 28 is
1
normalized by m
since ψ∈Ω ω∈Ω a [ψ, ω] = m.
The marginal emission distribution is a convex combination of the emission
distributions conditioned on each of the event types. For normal and log-normal
emissions, the marginal emission is simply a mixture of normals or log-normals,
respectively. Let η [j] and ρ2 [j] be the log-mean and log-variance of the marginal
distribution for hidden state j. The marginal log-mean is a weighted sum of the
conditional distributions, given by
X
η [j] =
Π [ω] µ [j|ω]
(29)
ω∈Ω

where Π [ω] is the stationary probability of event type ω. This can be calculated
directly from the event type sequence ΩN
1 ,
Π [ω] =

N
1 X
δ (ω, Ωn ) .
N n=1

Similarly, the marginal log-variance is a mixture of log-normals given by
h
i
X
2
ρ2 [j] =
Π [ω] (η [j|ω] − η [j]) + ρ2 [j|ω] .

(30)

(31)

ω∈Ω

Marginalized distribution parameters for normal emission is exactly the same.
3.7. Parameter smoothing
HMMs with many hidden states (and parametric models in general) are
plagued by overfitting and poor generalization, especially when the sample size
is small. This has to due with there being a high dof in the model compared to
the number of observations. Previous attempts at HMM parameter smoothing
have pushed the emission and transition parameters towards a higher entropy
distribution [14] or borrowed the shape of the emission PDF from states that appear in a similar context [12]. Instead, our parameter smoothing approach uses
the marginal distributions, which can be estimated with higher confidence due
to there being more observations, to eliminate the sparseness in the event type-

3.7

14

Parameter smoothing

dependent parameters. Note that parameter smoothing goes hand-in-hand with
context-dependent models, at least in part due to the curse of dimensionality
which is introduced by the context dependence [12].
The purpose of parameter smoothing is twofold. First, it acts as a kind of
regularization to avoid overfitting, a problem often encountered when there is a
large number of parameters and small number of observations. Second, parameter smoothing provides superior estimates in case of missing or infrequent data.
For motivation, consider a keystroke sequence of length N . Including English
letters and the Space key, there are at most 27 unique keys and 729 unique
digrams (subsequences of length 2). Most of these will rarely, or never, be observed in a sequence of English text. Parameter smoothing addresses this issue
by re-estimating the parameters that depend on low-frequency observations using a mixture of the marginal distribution. The effect is to bias parameters that
depend on event types with low frequency toward the marginals, for which there
exist more observations and higher confidence, while parameters that depend
on event types with high frequency will remain unchanged.
Smoothing weights for the starting and emission parameters are defined as
wω = 1 −

1
1 + f (ω)

(32)

PN
where f (ω) = t=1 δ (ω, Ωn ) is the frequency of event type ω in the sequence
ΩN
1 . The POHMM starting probabilities are then smoothed by
π̃ [j|ω] = wω π [j|ω] + (1 − wω ) π [j]

(33)

where smoothed parameter estimates denoted by a tilde, and emission parameters are smoothed by
b̃ [j|ω] = wω b [j|ω] + (1 − wω ) b [j] .

(34)

As N increases, event type frequencies increase and the effect of parameter
smoothing is diminished, while parameters conditioned on infrequent or missing
event types are biased toward the marginal. This ensures that the conditional
parameters remain asymptotically unbiased as N → ∞.
The smoothing
weights for transition probabilities follow similar formulae.
PN −1
Let f (ψ, ω) = t=1 δ (ψ, Ωn ) δ (ω, Ωn+1 ), i.e., the frequency of event type ψ
followed by ω in the sequence ΩN
1 . Weights for the conditional and marginal
transition probabilities are defined as
wψ
wω
wψ,ω
w

1
f (ψ, ω) + f (ω)
1
=
f (ψ, ω) + f (ψ)
= 1 − (wψ + wω )

=

=

0

(35)

15
where wψ,ω + wψ + wω + w = 1. The smoothed transition matrix is given by
ã [i, j|ψ, ω] = wψ,ω a [i, j|ψ, ω] + wψ a [i, j|ψ] + wω a [i, j|ω] + wa [i, j] .

(36)

In this strategy, the weight for the marginal a [i, j] is 0, although in other weighting schemes, w could be non-zero.
4. Simulation study
It is important for statistical models and their implementations to be consistent. This requires that parameter estimation be both convergent and asymptotically unbiased. The POHMM algorithms include the parameter estimation
procedure and equations, and the implementation consists of the POHMM algorithms expressed in a programming language. While consistency of the POHMM
algorithms is theoretically guaranteed (proof in Appendix B), consistency of
the POHMM implementation under several different scenarios is validated in
this section using computational methods.
First, a model is initialized with parameters θo . From this model, S samples are generated, each containing N time intervals. For each sample, the
best-estimate parameters θ̂ are computed using the modified BW algorithm
(Algorithm 1). Let θ̂N be the parameters determined by the modified BW algorithm for an observed sequence of length N generated from a POHMM with
true parameters θo . Consistency requires that
lim

N →∞

|θ̂N − θo |
maxθ̂ |θ̂N − θo |

=0

(37)

insensitive to the choice of θo . As N increases, parameter estimation should
be able to recover the true model parameters from the observed data. Four
different scenarios are considered:
1. Train a POHMM (without smoothing) on POHMM-generated data.
2. Train a POHMM (with smoothing) on POHMM-generated data.
3. Train a POHMM (without smoothing) using emissions generated from an
HMM and random event types.
4. Train an HMM using emissions from a POHMM (ignore event types).
Convergence is theoretically guaranteed for scenarios 1 and 2. The first scenario
tests the POHMM implementation without parameter smoothing and should
yield unbiased estimates. Scenario 2 evaluates the POHMM implementation
with parameter smoothing, whose effect diminishes as N increases. Consequently, the smoothed POHMM estimates approach that of the unsmoothed
POHMM, and results should also indicate consistency.
Scenario 3 is a POHMM trained on an HMM, and scenario 4 is an HMM
trained on a POHMM. In scenario 3, the underlying process is an HMM with
the same number of hidden states as the POHMM, and the observed event
types are completely decorrelated from the HMM. As a result, the event types

3
2
1
0
1
2
3

1.0
0.8

N

10
50
100
500
1000

1. POHMM

2. POHMM
(smoothed)

3. POHMM
(random N1 )

4. HMM

(a) Studentized emission residuals.

Accuracy

Mean studentized residual

16

0.6
0.4
0.2
0.00

1. POHMM
2. POHMM smoothed
3. POHMM (random N1 )
4. HMM
250 500 750 1000

N

(b) Hidden state classification
accuracy.

Figure 3: Simulation study results. In 1 and 2, a POHMM is trained on data generated from
a POHMM; in 3, a POHMM is trained on data generated from an HMM (using random event
types); in 4, an HMM is trained on data generated from a POHMM (ignoring event types).

do not partially reveal the hidden state. In this case, the POHMM marginal
distributions, in which the event type is marginalized out, should converge to
the HMM. Finally, scenario 4 simply demonstrates the inability of the HMM
to capture the dependence on event types, and results should indicate biased
estimates.
For scenarios 1, 2 and 4, a POHMM with 3 event types and 2 hidden states
is initialized to generate the training data. The emission distribution is a univariate Gaussian with parameters chosen to be comparable to human key-press
time intervals, and transition probabilities are uniformly distributed. The emission and event type sequences are sampled from the POHMM and used to fit
the model. In scenario 3, an HMM generates the emission sequence xN
1 , and the
event type sequence ΩN
is
chosen
randomly
from
the
set
of
3
event
types, re1
flecting no dependence on event types. In this case, only the POHMM marginal
distribution parameter residuals are evaluated, as these should approximate the
underlying HMM. For each value of N in each scenario, 400 length-N samples
are generated and used to train the corresponding model.
Figure 3a contains the mean studentized residuals for emission parameters
of each model, and Figure 3b shows the hidden state classification accuracies
(where chance accuracy is 21N ). Both the unsmoothed and smoothed POHMM
residuals tend toward 0 as N increases, indicating consistency. The marginal
residuals for the POHMM with random event types also appear unbiased, an
indication that the POHMM marginals, in which the event type is marginalized
out, are asymptotically equivalent to the HMM. Finally, the HMM residuals,
when trained on data generated from a POHMM, appear biased as expected
when the event types are ignored. Similar results in all scenarios are seen for
the transition probability residuals (not shown), and we confirmed that these
results are insensitive to the choice of θo .

17
Table 1: Keystroke dataset summary. Columns 4-7 indicate: number of users, samples per
user, keystrokes per sample, and τ̄ =mean press-press latency (ms).
Users

Samples/user

Keys/sample

τ̄ (ms)

Short fixed

51

400

11

249

Short fixed

30

20

11

376

[31]

Short fixed

51

20

11

366

Fable

[33]

Long constrained

60

4

100

264

Essay

[34]

Long free

55

6

500

284

Dataset

Source

Category

Password

[29]

Keypad

[30]

Mobile

5. Case study: keystroke dynamics
Five publicly-available keystroke datasets are analyzed in this work, summarized in Table 1. We categorize the input type as follows:
• Fixed-text: The keystrokes exactly follow a relatively short predefined
sequence, e.g., passwords and phone numbers.
• Constrained-text: The keystrokes roughly follow a predefined sequence,
e.g., case-insensitive passphrases and transcriptions. Some massively open
online course (MOOC) providers require the student to copy several sentences for the purpose of keystroke dynamics-based verification [28].
• Free-text: The keystrokes do not follow a predefined sequence, e.g., responding to an open-ended question in an online exam.
The password, keypad, and mobile datasets contain short fixed-text input in
which all the users in each dataset typed the same 10-character string followed
by the Enter key: “.tie5Roanl” for the password dataset [29] and “9141937761”
for the keypad [30] and mobile datasets [31]. Samples that contained errors or
more than 11 keystrokes were discarded. The password dataset was collected on
a laptop keyboard equipped with a high-resolution clock (estimated resolution
to within ±200 μs [32]), while the timestamps in all other datasets were recorded
with millisecond resolution (see discussion in Section 2 on timestamp resolution).
The keypad dataset used only the 10-digit numeric keypad located on the right
side a standard desktop keyboard, and the mobile dataset used an Android
touchscreen keypad with similar layout. In addition to timestamps, the mobile
dataset contains accelerometer, gyroscope, screen location, and pressure sensor
features measured on each key press and release.
The fable dataset contains long constrained-text input from 60 users who
each copied 4 different fables or nursery rhymes [33, 34]. Since mistakes were
permitted, the keystrokes for each copy task varied, unlike the short fixed-text
datasets above. The essay dataset contains long free-text input from 55 users
who each answered 6 essay-style questions as part of a class exercise [34]. Both
the fable and essay datasets were collected on standard desktop and laptop keyboards. For this work, the fable samples were truncated to each contain exactly
100 keystrokes and the essay samples to each contain exactly 500 keystrokes.

0.008
0.007
0.006
0.005
0.004
0.003
0.002
0.001
0.000
0

Active state
Passive state

Density

Density

18

250

500

τ (ms)

750

1000

0.007
0.006
0.005
0.004
0.003
0.002
0.001
0.000
0

(a) Fixed-text

Active state
Passive state

250

500

τ (ms)

750

1000

(b) Free-text

Figure 4: POHMM marginal distributions showing a separation between active and passive
typing states. The marginal distributions are mixtures of log-normals conditioned on the key
names. Histograms show the empirical time interval distributions in each hidden state.

Each keystroke event contains two timing features,
τn
dn

P
= tP
n − tn−1

=

tR
n

−

tP
n

(38)
(39)

th
R
keystroke,
where tP
n and tn are the press and release timestamps of the n
respectively; τn is the press-press time interval and dn is the key-hold duration. Note that other timing features, such as release-release and release-press
intervals, can be calculated by a linear combination of the above two features.

Each user’s keystroke dynamics are modeled by a POHMM with log-normal
emission and two hidden states, all conditioned on the keyboard keys as the observed event types. A two-state model is the simplest model of non-homogeneous
behavior, as one state implies a sequence of independent and identically distributed (i.i.d.) observations. The two hidden states correspond to the active
and passive states of the user, in which relatively longer time intervals are observed in the passive state. Given the hidden state and the observed event
type, the keystroke time intervals τn and dn are each modeled by a log-normal
distribution (Equation 16), where η [j|ω] and ρ [j|ω] are the log-mean and logstandard deviation, respectively, in hidden state j given observed key ω.
The POHMM parameters are determined using Algorithm 1, and convergence is achieved after a loglikelihood increase less than 10−6 or 1000 iterations,
whichever is reached first. As an example, the marginal key-press time interval
distributions for each hidden state are shown in Figure 4 for two randomly selected samples. The passive state in the free-text model has a heavier tail than
the fixed-text, while the active state distributions in both models are comparable. The rest of this section presents experimental results for a goodness of
fit test, identification, verification, and continuous verification. Source code to
reproduce the experiments in this article is available4 .
4 Code

to reproduce experiments: https://github.com/vmonaco/pohmm-keystroke

5.1

19

Goodness of fit

5.1. Goodness of fit
To determine whether the POHMM is consistent with observed data, a
Monte Carlo goodness of fit test is performed. The test proceeds as follows.
For each keystroke sample (using the key-press time intervals only), the model
parameters θ̂m are determined. The area test statistic between the model and
empirical distribution is then taken. The area test statistic is a compromise
between the Kolmogorov-Smirnov (KS) test and CramÃ©r-von Mises test [35],
ˆ


A = |PD (τ ) − PM τ |θ̂m |dτ
(40)
where PD is the empirical cumulative distribution and PM is the model cumulative distribution. The POHMM marginal emission density is given by
g (x; θ) =

M
XX

Π [ω] Π [j] f (x; b [j|ω])

(41)

ω∈Ω j=1

where Π [j] is the stationary probability of hidden state j and Π [ω] is the stationary probability of event type ω. Using the fitted model with parameters
θ̂m , a surrogate data sample the same size as the empirical sample is generated.
Estimated parameters θ̂s are determined using the surrogate sample in a similar
fashion as the empirical sample. The area test statistic between the surrogatedata-trained model and surrogate data is computed, given by As . This process
repeats until enough surrogate statistics have accumulated to reliably determine
P (|As − hAs i| > |A − hAs i|). The biased p-value is given by
I (|As − hAs i| > |A − hAs i|) + 1
S+1

(42)

where I (·) is the indicator function. Testing the null hypothesis, that the model
is consistent with the data, requires fitting S + 1 models (1 empirical and S
surrogate samples).
The test is performed for both the HMM and the POHMM for each user
in the fable and essay datasets, using the key-press time intervals only. The
resulting p-value distributions are shown in Figure 5. The shaded area represents
a 0.05 significance level in which the null hypothesis is rejected. In the fable
dataset, the HMM is rejected for 45% of users, while the POHMM is rejected for
22% of users. The HMM is rejected for 100% of users in the essay dataset, and
the POHMM is rejected for 40% of users. If the POHMM truly reflected typing
behavior (i.e., the null hypothesis was actually true), the p-values would follow
a uniform distribution shown by the dashed black line. In both experiments,
the POHMM is largely preferred over the HMM.
5.2. Identification and verification
We use the POHMM to perform both user identification and verification,
and compare the results to other leading methods. Identification, a multiclass

20

Identification and verification

1.0

1.0

0.8

0.8

0.6
0.4
0.2
0.0
0.0

0.2

HMM (0.45)
POHMM (0.22)
0.4 0.6 0.8 1.0

p­value

(a) Constrained-text

Cumulative distribution

Cumulative distribution

5.2

0.6
0.4
0.2
0.0
0.0

0.2

HMM (1.00)
POHMM (0.40)
0.4 0.6 0.8 1.0

p­value

(b) Free-text

Figure 5: Keystroke goodness of fit p-value distributions testing the null hypothesis that the
model is consistent with the data. Proportions of rejected samples at the 0.05 significance
level are shown in parentheses. If the null hypothesis was true, i.e., the model was actually
consistent with the keystroke data, then p-values would follow a uniform distribution shown
by the dashed black line.

classification problem, is performed by the MAP approach in which the model
with maximum a posterior probability is chosen as the class label. This approach is typical in using a generative model to perform classification. Better
performance could, perhaps, be achieved through parameter estimation with
a discriminative criterion [36], or a hybrid discriminative/generative model in
which the POHMM parameters provide features for a discriminative classifier
[37]. Verification, a binary classification problem, is achieved by comparing the
claimed user’s model loglikelihood to a threshold.
Identification and verification results are obtained for each keystroke dataset
and four benchmark anomaly detectors in addition to the POHMM. The password dataset uses a validation procedure similar to Killourhy and Maxion [29],
except only samples from the 4th session (repetitions 150-200) are used for training and sessions 5-8 (repetitions 201-400) for testing. For the other datasets,
results are obtained through a stratified cross-fold validation procedure with the
number of folds equal to the number of samples per user: 20 for keypad and
mobile, 4 for fable, and 6 for essay. In each fold, one sample from each user is
retained as a query and the remaining samples are used for training.
Identification accuracy (ACC) is measured by the proportion of correctly
classified query samples. Verification performance is measured by the userdependent equal error rate (EER), the point on the receiver operating characteristic (ROC) curve at which the false rejection rate (FRR) and false acceptance
rate (FAR) are equal. Each query sample is compared against every model in
the population, only one of which will be genuine. The resulting loglikelihood is
normalized using the minimum and maximum loglikelihoods from every model
in the population to obtain a normalized score between 0 and 1. Confidence
intervals for both the ACC and EER are obtained over users in each dataset,
similar to [29].

5.2

21

Identification and verification

Table 2: Identification accuracy rates. Bold indicates systems that are not significantly worse
than the best system. Mobile+ includes mobile sensor features in addition to time intervals.

Password

Manhattan

Manhattan (Scaled)

SVM (One-class)

HMM

POHMM

0.510 (0.307)

0.662 (0.282)

0.465 (0.293)

0.467 (0.295)

0.789 (0.209)

0.623 (0.256)

0.713 (0.200)

0.500 (0.293)

0.478 (0.287)

0.748 (0.151)

Mobile

0.290 (0.230)

0.528 (0.237)

0.267 (0.229)

0.303 (0.265)

0.607 (0.189)

Mobile+

0.647 (0.250)

0.947 (0.104)

0.857 (0.232)

0.937 (0.085)

0.971 (0.039)

Fable

0.492 (0.332)

0.613 (0.314)

0.571 (0.235)

0.392 (0.355)

0.887 (0.175)

Essay

0.730 (0.320)

0.839 (0.242)

0.342 (0.302)

0.303 (0.351)

0.909 (0.128)

Keypad

Benchmark anomaly detectors include Manhattan distance, scaled Manhattan distance, one-class support vector machine (SVM), and a two-state HMM.
The Manhattan, scaled Manhattan, and one-class SVM operate on fixed-length
feature vectors, unlike the HMM and POHMM. Timing feature vectors for the
password, keypad, and mobile datasets are formed by the 11 press-press latencies
and 10 durations of each 11-keystroke sample for a total of 21 timing features.
The mobile sensors provide an additional 10 features for each keystroke event for
a total of 131 features. For each event, the sensor features include: acceleration
(meters/second2 ) and rotation (radians/second) along three orthogonal axes (6
features), screen coordinates (2 features), pressure (1 feature), and the length
of the major axis of an ellipse fit to the pointing device (1 feature). Feature
vectors for the fable and essay datasets are each comprised of a set of 218 descriptive statistics for various keystroke timings. Such timing features include
the sample mean and standard deviation of various sets of key durations, e.g.,
consonants, and latency between sets of keys, e.g., from consonants to vowels.
For a complete list of features see [33, 38]. The feature extraction also includes
a rigorous outlier removal step that excludes observations outside a specified
confidence interval and a hierarchical fallback scheme that accounts for missing
or infrequent observations.
The Manhattan anomaly detector uses the negative Manhattan distance to
the mean template vector as a confidence score. For the scaled Manhattan
detector, features are first scaled by the mean absolute deviation over the entire
dataset. This differs slightly from the scaled Manhattan in [29], which uses
the mean absolute deviation of each user template. The global (over the entire
dataset) mean absolute deviation is used in this work due to the low number
of samples per user in some datasets. The one-class SVM uses a radial basis
function (RBF) kernel and 0.5 tolerance of training errors, i.e., half the samples
will become support vectors. The HMM is exactly the same as the POHMM
(two hidden states and log-normal emissions), except event types are ignored.
Identification and verification results are shown in Tables 2 and 3, respectively, and ROC curves are shown in Figure 6. The best-performing anomaly
detectors in Tables 2 and 3 are shown in bold. The set of best-performing
detectors contains those that are not significantly worse than the POHMM,
which achieves the highest performance in every experiment. The Wilcoxon

0.8
0.6
0.4
0.2
0.0
0.0

0.2

0.4

0.6

0.8

False acceptance rate

1.0

(a) Password

1.0

Manhattan
Manhattan (scaled)
SVM (one­class)
HMM
POHMM

0.8
0.6
0.4
0.2
0.0
0.0

0.2

0.4

0.6

0.8

False acceptance rate

(b) Keypad

1.0

1.0

Manhattan
Manhattan (scaled)
SVM (one­class)
HMM
POHMM

0.8
0.6

False rejection rate

1.0

Manhattan
Manhattan (scaled)
SVM (one­class)
HMM
POHMM

False rejection rate

1.0

False rejection rate

22

Continuous verification

False rejection rate

5.3

0.4
0.2
0.0
0.0

0.2

0.4

0.6

0.8

False acceptance rate

1.0

Manhattan
Manhattan (scaled)
SVM (one­class)
HMM
POHMM

0.8
0.6
0.4
0.2
0.0
0.0

(c) Fixed-text

0.2

0.4

0.6

0.8

False acceptance rate

(d) Free-text

Figure 6: Keystroke ROC curves. Bands show the 95% confidence intervals.
Table 3: User-dependent EER. Bold indicates systems that are not significantly worse than
the best system. Mobile+ includes mobile sensor features in addition to time intervals.
Manhattan

Manhattan (scaled)

SVM (one-class)

HMM

POHMM

Password

0.088 (0.069)

0.062 (0.064)

0.112 (0.088)

0.126 (0.099)

0.042 (0.051)

Keypad

0.092 (0.069)

0.053 (0.030)

0.110 (0.054)

0.099 (0.050)

0.053 (0.025)

Mobile

0.194 (0.101)

0.097 (0.057)

0.170 (0.092)

0.168 (0.085)

0.090 (0.054)

Mobile+

0.084 (0.061)

0.009 (0.027)

0.014 (0.033)

0.013 (0.021)

0.006 (0.014)

Fable

0.085 (0.091)

0.049 (0.060)

0.099 (0.106)

0.105 (0.092)

0.031 (0.077)

Essay

0.061 (0.092)

0.028 (0.052)

0.098 (0.091)

0.145 (0.107)

0.020 (0.046)

signed-rank test is used to determine whether a detector is significantly worse
than the best detector, testing the null hypothesis that a detector has the same
performance as the POHMM. A Bonferroni correction is applied to control the
family-wise error rate, i.e., the probability of falsely rejecting a detector that is
actually in the set of best-performing detectors [39]. At a 0.05 significance level,
the null hypothesis is rejected with a p-value not greater than 0.05
4 since four
tests are applied in each row. The POHMM achieves the highest identification
accuracy and lowest equal error rate for each dataset. For 3 out of 6 datasets in
both sets of experiments, all other detectors are found to be significantly worse
than the POHMM.
5.3. Continuous verification
Continuous verification has been recognized as a problem in biometrics
whereby a resource is continuously monitored to detect the presence of a genuine user or impostor [40]. It is natural to consider the continuous verification of
keystroke dynamics, and most behavioral biometrics, since events are continuously generated as the user interacts with the system. In this case, it is desirable
to detect an impostor within as few keystrokes as possible. This differs from
the static verification scenario in the previous section in which verification performance is evaluated over an entire session. Instead, continuous verification
requires a verification decision to be made upon each new keystroke [23].
Continuous verification is enforced through a penalty function in which each
new keystroke incurs a non-negative penalty within a sliding window. The

1.0

5.3

23

Continuous verification
800
700
600

Penalty

500
400
300
200
100
0
0

100

200

Event

300

Impostor
Genuine
Threshold
400
500

Figure 7: Continuous verification example. Bands show the 95% confidence interval. In this
example, impostors are detected after an average of 81 keystrokes.

penalty at any given time can be thought of as the inverse of trust. As behavior
becomes more consistent with the model, the cumulative penalty within the
window can decrease, and as it becomes more dissimilar, the penalty increases.
The user is rejected if the cumulative penalty within the sliding window exceeds
a threshold. The threshold is chosen for each sample such that the genuine user
is never rejected, analogous to a 0% FRR in static verification. An alternative
to the penalty function is the penalty-and-reward function in which keystrokes
incur either a penalty or a reward (i.e., a negative penalty) [41]. In this work,
the sliding window replaces the reward since penalties outside the window do
not contribute towards the cumulative penalty.
The penalty of each new event is determined as follows. The marginal probability of each new event, given the preceding events, is obtained from the forward
lattice, α, given by

P (xn+1 |xn1 ) = P xn+1
− P (xn1 )
(43)
1
When a new event is observed, the likelihood is obtained under every model in
a population of U models. The likelihoods are ranked, with the highest model
given a rank of 0, and the lowest a rank of U − 1. The rank of the claimed user’s
model is the incurred penalty. Thus, if a single event is correctly matched to the
genuine user’s model, a penalty of 0 is incurred; if it scores the second highest
likelihood, a penalty of 1 is incurred, etc. The rank penalty is added to the
cumulative penalty in the sliding window, while penalties outside the window
are discarded. A window of length 25 is used in this work.
Continuous verification performance is reported as the number of events (up
to the sample length) that can occur before an impostor is detected. This is
determined by increasing the penalty threshold until the genuine user is never
rejected by the system. Since the genuine user’s penalty is always below the
threshold, this is the maximum number of events that an impostor can execute
before being rejected by the system while the genuine user is never rejected.
An example of the penalty function for genuine and impostor users is shown
in Figure 7. The decision threshold is set to the maximum penalty incurred by

24
Table 4: Continuous verification average maximum rejection time: the number of events that
occur before an impostor is detected given the genuine user is not falsely rejected.
HMM

POHMM

Password

5.64 (2.04)

3.42 (2.04)

Keypad

4.54 (2.09)

3.45 (1.73)

Mobile

5.63 (2.18)

4.29 (2.02)

Mobile+

0.15 (0.65)

0.12 (0.57)

Fable

33.63 (15.47)

20.81 (9.07)

Essay

129.36 (95.45)

55.18 (68.31)

the genuine user so that a false rejection does not occur. The average penalty
for impostor users with 95% confidence interval is shown. In this example, the
impostor penalties exceed the decision threshold after 81 keystrokes on average.
Note that this is different than the average imposter penalty, which exceeds the
threshold after 23 keystrokes.
For each dataset, the average maximum rejection time (AMRT) is determined, shown in Table 4. The maximum rejection time (MRT) is the maximum
number of keystrokes needed to detect an impostor without rejecting the genuine user, or the time to correct reject (TCR) with perfect usability [40]. The
MRT is determined for each combination of impostor query sample and user
model in the dataset to get the AMRT. The POHMM has a lower AMRT than
the HMM for every dataset, and less than half that of the HMM for free-text
input.
6. Discussion
There have been several generalizations of the standard HMM to deal with
hidden states that are partially observable in some way. These models are
referred to as partly-HMM [42], partially-HMM [43], and context-HMM [44].
The partly-HMM is a second order model in which the first state is hidden
and the second state is observable [42]. In the partly-HMM, both the hidden
state and emission at time tn depend on the observation at time tn−1 . The
partly-HMM can be applied to problems that have a transient underlying process, such as gesture and speech recognition, as opposed to a piecewise stationary
process that the HMM assumes [45]. Parameter estimation is performed by the
EM algorithm, similar to the HMM.
Partially observable states can also come in the form of partial and uncertain
ground truth regarding the hidden state at each time step. The partially-HMM
addresses this scenario, in which an uncertain hidden state label may be observed
at each time step [43]. The probability of observing the uncertain label and the
probability of the label being correct, were the true hidden state known, are
controlled by parameters pobs and ptrue , respectively. Thus, the probability of
observing a correct label is pobs × ptrue . This model is motivated by language
modeling applications in which manually labeling data is expensive and time

25
consuming. Similar to the HMM, the EM algorithm can be used for estimating
the parameters of the partially-HMM [43].
Past observations can also provide context for the emission and hidden state
transition probabilities in an HMM. Forchhammer and Rissanen [44] proposed
the context-HMM, in which the emission and hidden state probabilities at time
tn+1 are conditioned on contexts rn and sn , respectively. Each context is given
by a function of the previous observations up to time tn . The context-HMM has
information theoretic motivations, with applications such as image compression
[46]. Used in this way, the neighboring pixels in an image can provide context
for the emission and transition probabilities.
There are two scenarios in which previous models of partial observability
fall short. The first is when there is missing data during parameter estimation,
such missing context, and the second is when there is missing or novel data
during likelihood calculation. A possible solution to these problems uses the
explicit marginal emission and transition distributions, where, e.g., the context
is marginalized out. While none of the above models possess this property,
the POHMM, described in Section 3, has explicit marginal distributions that
are used when missing or novel data are encountered. Additionally, parameter
smoothing uses the marginal distributions to regularize the model and improve
parameter estimates.
The POHMM is different from the partly-HMM [42], being a first order
model, and different from the partially-HMM [43], since it doesn’t assume a
partial labeling. The POHMM is most similar to the context-HMM [44] in
the sense that emission and transition probabilities are conditioned on some
observed values. Despite this, there are several important differences between
the POHMM and context-HMM:
1. The context is not a function of the previous emissions; instead it is a
separate observed value (called an event type in this work).
2. The context for hidden state and emission is the same, i.e., sn = rn .
3. The emission at time n + 1 is conditioned on a context observed at time
n + 1 instead of time n.
4. An additional context sn+1 is available at time n + 1, upon which the
hidden state is also conditioned.
The first difference enables the POHMM to characterize system behavior that
depends on an independent Markov chain which emanates from a completely
separate process. Such a scenario is encountered in keystroke dynamics, whereby
typing behavior depends on the text that is being typed, but the text itself is not
considered part of the keystroke dynamics. This distinction is not made in the
context-HMM, as the context is based on the previously-observed emissions.
Additionally, the context-HMM, as original described, contains only discrete
distributions and lacks explicit marginal distributions; therefore it is unable to
account for missing or novel data during likelihood calculation, as would be
needed in free-text keystroke dynamics.

26
7. Conclusions
This work introduced the POHMM, an extension of the HMM in which the
hidden states are partially observable through an independent Markov chain.
Computational complexities of POHMM parameter estimation and likelihood
calculation are comparable to that of the HMM, which are linear in the number of observations. POHMM parameter estimation also inherits the desirable
properties of expectation maximization, as a modified Baum-Welch algorithm is
employed. A case study of the POHMM applied to keystroke dynamics demonstrates superiority over leading alternative models on a variety of tasks, including identification, verification, and continuous verification.
Since we assumedthe event type is given, we considered only the conditional

N
N
N
likelihood P xN
1 |Ω1 . Consideration of the joint likelihood P x1 , Ω1 remains
an item for future work. Applied to keystroke dynamics, the joint likelihood
N
P xN
would reflect both the keystroke timings and keys typed enabling
1 , Ω1
the model to capture both typing
 behavior and text generation. Alternatively,
N
the consideration of P ΩN
would enable the POHMM to recover the key
1 |x1
names from keystroke timings, also an item for future work.

References
[1] L. E. Baum, T. Petrie, Statistical inference for probabilistic functions of
finite state Markov chains, The annals of mathematical statistics 37 (6)
(1966) 1554–1563.
[2] L. Rabiner, A tutorial on hidden Markov models and selected applications
in speech recognition, Proceedings of the IEEE 77 (2) (1989) 257–286.
[3] J. Yamato, J. Ohya, K. Ishii, Recognizing human action in time-sequential
images using hidden markov model, in: Proc. IEEE Computer Society
Conference on Computer Vision and Pattern Recognition (CVPR), IEEE,
379–385, 1992.
[4] J. Hu, M. K. Brown, W. Turin, HMM based online handwriting recognition,
IEEE Transactions on pattern analysis and machine intelligence 18 (10)
(1996) 1039–1045.
[5] S. Espana-Boquera, M. J. Castro-Bleda, J. Gorbe-Moya, F. ZamoraMartinez, Improving offline handwritten text recognition with hybrid
HMM/ANN models, IEEE transactions on pattern analysis and machine
intelligence 33 (4) (2011) 767–779.
[6] G. Hinton, L. Deng, D. Yu, G. E. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior,
V. Vanhoucke, P. Nguyen, T. N. Sainath, et al., Deep neural networks for
acoustic modeling in speech recognition: The shared views of four research
groups, IEEE Signal Processing Magazine 29 (6) (2012) 82–97.

REFERENCES

27

[7] D. Wu, L. Pigou, P.-J. Kindermans, N. D.-H. Le, L. Shao, J. Dambre, J.-M.
Odobez, Deep dynamic neural networks for multimodal gesture segmentation and recognition, IEEE transactions on pattern analysis and machine
intelligence 38 (8) (2016) 1583–1597.
[8] S.-Z. Yu, Hidden semi-Markov models, Artificial Intelligence 174 (2) (2010)
215–243.
[9] Y. Li, Hidden Markov models with states depending on observations, Pattern Recognition Letters 26 (7) (2005) 977 – 984, ISSN 0167-8655.
[10] A.-L. Bianne-Bernard, F. Menasri, R. A.-H. Mohamad, C. Mokbel, C. Kermorvant, L. Likforman-Sulem, Dynamic and contextual information in
HMM modeling for handwritten word recognition, IEEE transactions on
pattern analysis and machine intelligence 33 (10) (2011) 2066–2080.
[11] T. A. Salthouse, Perceptual, cognitive, and motoric aspects of transcription
typing., Psychological bulletin 99 (3) (1986) 303.
[12] K.-F. Lee, H.-W. Hon, Speaker-independent phone recognition using hidden Markov models, IEEE Transactions on Acoustics, Speech, and Signal
Processing 37 (11) (1989) 1641–1648.
[13] P.-C. Chung, C.-D. Liu, A daily behavior enabled hidden Markov model
for human behavior understanding, Pattern Recognition 41 (5) (2008) 1572
– 1580, ISSN 0031-3203.
[14] O. Samanta, U. Bhattacharya, S. Parui, Smoothing of HMM parameters
for efficient recognition of online handwriting, Pattern Recognition 47 (11)
(2014) 3614 – 3629, ISSN 0031-3203.
[15] D. Jurafsky, J. H. Martin, A. Kehler, K. Vander Linden, N. Ward, Speech
and language processing: An introduction to natural language processing,
computational linguistics, and speech recognition, vol. 2, MIT Press, 2000.
[16] N. A. Laskaris, S. P. Zafeiriou, L. Garefa, Use of random time-intervals
(RTIs) generation for biometric verification, Pattern Recognition 42 (11)
(2009) 2787–2796.
[17] S. P. Banerjee, D. L. Woodard, Biometric authentication and identification using keystroke dynamics: A survey, Journal of Pattern Recognition
Research 7 (1) (2012) 116–139.
[18] J. V. Monaco, C. C. Tappert, Obfuscating Keystroke Time Intervals to
Avoid Identification and Impersonation, arXiv preprint arXiv:1609.07612 .
[19] H. Wang, T. Tsung-Te Lai, R. R. Choudhury, MoLe: Motion Leaks through
Smartwatch Sensors, in: Proc. 21st Annual International Conference on
Mobile Computing and Networking (MobiCom), ACM, 2015.

REFERENCES

28

[20] D. Asonov, R. Agrawal, Keyboard acoustic emanations, in: Proc. IEEE
Symposium on Security and Privacy (SP), IEEE, 3–11, 2004.
[21] D. X. Song, D. Wagner, X. Tian, Timing Analysis of Keystrokes and Timing
Attacks on SSH., in: Proc. USENIX Security Symposium, vol. 2001, 2001.
[22] K. Ali, A. X. Liu, W. Wang, M. Shahzad, Keystroke recognition using wifi
signals, in: Proc. 21st Annual International Conference on Mobile Computing and Networking (MobiCom), ACM, 90–102, 2015.
[23] P. Bours, S. Mondal, Performance evaluation of continuous authentication
systems, IET Biometrics 4 (4) (2015) 220–226.
[24] S. Z. S. Idrus, E. Cherrier, C. Rosenberger, P. Bours, Soft biometrics for
keystroke dynamics: Profiling individuals while typing passwords, Computers & Security 45 (2014) 147–155.
[25] D. G. Brizan, A. Goodkind, P. Koch, K. Balagani, V. V. Phoha, A. Rosenberg, Utilizing linguistically-enhanced keystroke dynamics to predict typist cognition and demographics, International Journal of Human-Computer
Studies .
[26] J. Montalvão, E. O. Freire, M. A. B. Jr., R. Garcia, Contributions to
empirical analysis of keystroke dynamics in passwords, Pattern Recognition
Letters 52 (Supplement C) (2015) 80 – 86, ISSN 0167-8655.
[27] J. R. M. Filho, E. O. Freire, On the equalization of keystroke timing histograms, Pattern Recognition Letters 27 (13) (2006) 1440 – 1446, ISSN
0167-8655.
[28] A. Maas, C. Heather, C. T. Do, R. Brandman, D. Koller, A. Ng, Offering
Verified Credentials in Massive Open Online Courses: MOOCs and technology to advance learning and learning research (Ubiquity symposium),
Ubiquity 2014 (May) (2014) 2.
[29] K. S. Killourhy, R. A. Maxion, Comparing anomaly-detection algorithms
for keystroke dynamics, in: Proc. IEEE/IFIP International Conference on
Dependable Systems & Networks (DSN), IEEE, 125–134, 2009.
[30] N. Bakelman, J. V. Monaco, S.-H. Cha, C. C. Tappert, Keystroke Biometric Studies on Password and Numeric Keypad Input, in: Proc. European
Intelligence and Security Informatics Conference (EISIC), IEEE, 204–207,
2013.
[31] M. J. Coakley, J. V. Monaco, C. C. Tappert, Keystroke Biometric Studies with Short Numeric Input on Smartphones, in: Proc. IEEE 8th International Conference on Biometrics Theory, Applications and Systems
(BTAS), IEEE, 2016.

REFERENCES

29

[32] K. Killourhy, R. Maxion, The effect of clock resolution on keystroke dynamics, in: Proc. International Workshop on Recent Advances in Intrusion
Detection (RAID), Springer, 331–350, 2008.
[33] J. V. Monaco, N. Bakelman, S.-H. Cha, C. C. Tappert, Recent Advances
in the Development of a Long-Text-Input Keystroke Biometric Authentication System for Arbitrary Text Input, in: Proc. European Intelligence
and Security Informatics Conference (EISIC), IEEE, 60–66, 2013.
[34] M. Villani, C. Tappert, G. Ngo, J. Simone, H. S. Fort, S.-H. Cha,
Keystroke biometric recognition studies on long-text input under ideal and
application-oriented conditions, in: Proc. Conference on Computer Vision
and Pattern Recognition Workshop (CVPRW), IEEE, 39–39, 2006.
[35] R. D. Malmgren, D. B. Stouffer, A. E. Motter, L. A. Amaral, A Poissonian
explanation for heavy tails in e-mail communication, Proceedings of the
National Academy of Sciences 105 (47) (2008) 18153–18158.
[36] N. Mutsam, F. Pernkopf, Maximum margin hidden Markov models for
sequence classification, Pattern Recognition Letters 77 (Supplement C)
(2016) 14 – 20, ISSN 0167-8655.
[37] M. Bicego, E. Pe,kalska, D. M. Tax, R. P. Duin, Component-based discriminative classification for hidden Markov models, Pattern Recognition
42 (11) (2009) 2637 – 2648, ISSN 0031-3203.
[38] C. C. Tappert, M. Villani, S.-H. Cha, Keystroke biometric identification
and authentication on long-text input, Behavioral biometrics for human
identification: Intelligent applications (2009) 342–367.
[39] G. Rupert Jr, et al., Simultaneous statistical inference, Springer Science &
Business Media, 2012.
[40] T. Sim, S. Zhang, R. Janakiraman, S. Kumar, Continuous verification using
multimodal biometrics, IEEE transactions on pattern analysis and machine
intelligence 29 (4) (2007) 687–700.
[41] P. Bours, Continuous keystroke dynamics: A different perspective towards
biometric evaluation, Information Security Technical Report 17 (1) (2012)
36–43.
[42] T. Kobayashi, S. Haruyama, Partly-hidden Markov model and its application to gesture recognition, in: Proc. IEEE International Conference on
Acoustics, Speech, and Signal Processing (ICASSP), vol. 4, IEEE, 3081–
3084, 1997.
[43] H. Ozkan, A. Akman, S. S. Kozat, A novel and robust parameter training approach for HMMs under noisy and partial access to states, Signal
Processing 94 (2014) 490–497.

REFERENCES

30

[44] S. O. Forchhammer, J. Rissanen, Partially hidden Markov models, IEEE
Transactions on Information Theory 42 (4) (1996) 1253–1256.
[45] T. Iobayashi, J. Furuyama, K. Mas, Partly hidden Markov model and its
application to speech recognition, in: Proc. IEEE International Conference
on Acoustics, Speech, and Signal Processing (ICASSP), vol. 1, IEEE, 121–
124, 1999.
[46] S. Forchhammer, T. S. Rasmussen, Adaptive partially hidden Markov models with application to bilevel image coding, Image Processing, IEEE Transactions on 8 (11) (1999) 1516–1526.
[47] S. E. Levinson, L. R. Rabiner, M. M. Sondhi, An introduction to the application of the theory of probabilistic functions of a Markov process to
automatic speech recognition, The Bell System Technical Journal 62 (4)
(1983) 1035–1074.
[48] L. E. Baum, T. Petrie, G. Soules, N. Weiss, A maximization technique
occurring in the statistical analysis of probabilistic functions of Markov
chains, The annals of mathematical statistics 41 (1) (1970) 164–171.

31
Appendix A. Summary of POHMM parameters and variables

Table A.5: Summary of POHMM parameters and variables.
Parameter

Description

ψ,ω

Event types

i, j

Hidden states

xN
1

Observation sequence; xn is the feature vector observed at time tn

ΩN
1

Event type sequence; Ωn is the event type observed at time tn

z1N

Sequence of hidden (unobserved) states; zn is the hidden state at time tn

M

Number of hidden states

m

Number of unique event types in ΩN
1

a [i, j|ψ, ω]

Probability of transitioning from state i to j, given event types ψ while in
state i and ω in state j

π [j|ω]

Probability of state j at time t1 , given event type ω

Π [j|ω]

Stationary probability of state j, given event type ω

b [j|ω]

Emission distribution parameters of state j, given event type ω

γn [j|ω]

Probability of state j at time tn , given event type ω

ξn [i, j|ψ, ω]

Probability of transitioning from state i at time tn to state j at time
tn+1 , given event types ψ and ω at times tn and tn+1 , respectively

Appendix B. Proof of convergence
The proof of convergence follows that of Levinson et al. [47] which is based
onBaum
 et al. [48]. Only the parts relevant to the POHMM are described. Let
Q θ, θ̇ be Baum’s auxiliary function,
 
X
Q θ, θ̇ =
ln uz1N ln vz1N

(B.1)

z1N ∈Z




N
N
N
N
N
where uz1N = P xN
1 , z1 |Ω1 , θ , vZ = P x1 , z1 |Ω1 , θ̇ , and Z is the set of all
state
of length N . By Theorem 2.1 in Baum’s proof [48], maximizing
 sequences

Q θ, θ̇ leads to increased likelihood, unless at a critical point, in which case
there is no change.
Using the POHMM parameters θ̇, ln vz1N can be written as
ln vz1N

=



N
ln P z1N , xN
1 |Ω1 , θ̇

=

ln π̇ [z1 |Ω1 ] +

N
−1
X
n=1

ln ȧ [zn , zn+1 |Ωn , Ωn+1 ] +

(B.2)

32
N
X



ln f xn ; ḃ [zn |Ωn ]

(B.3)

n=1

and similarly for ln uz1N . Then,
 
Q θ, θ̇

X 

=

ln π̇ [z1 |Ω1 ] +

ln ȧ [zn , zn+1 |Ωn , Ωn+1 ]

n=1

z1N ∈Z

+

N
−1
X

N
X



N
ln f xn ; ḃ [zn |Ωn ]
P z1N |xN
1 , Ω1 , θ


(B.4)

n=1

and regrouping terms,
 
Q θ, θ̇

=

X

N
ln π̇ [z1 |Ω1 ] P z1 |xN
1 , Ω1 , θ



z1 ∈Z

+

X

N
−1
X

N
ln ȧ [zn , zn+1 |Ωn , Ωn+1 ] P znn+1 |xN
1 , Ω1 , θ



n+1
zn
∈Z n=1

+

N
X X




N
ln f xn ; ḃ [zn |Ωn ] P zn |xN
1 , Ω1 , θ .

(B.5)

zn ∈Z n=1

Finally, substituting in the model parameters and variables gives,

 
Q θ, θ̇

=

M
X

γ1 [j|Ω1 ] ln π̇ [j|Ω1 ]

j=1

+

M X
M N
−1
X
X

ξn [i, j|Ωn , Ωn+1 ] ln ȧ [i, j|Ωn |Ωn+1 ]

j=1 i=1 n=1

+

M X
N
X



γn [j|Ωn ] ln f xn ; ḃ [zn |Ωn ]

(B.6)

j=1 n=1

The POHMM re-estimation formulae (Equations 12, 14, 15) follow directly
from the optimization of each term in Equation B.6. Even when parameter
smoothing is used, convergence is still guaranteed. This is due to the diminishing
effect of the marginal for each parameter, limN →∞ θ̃ = θ, where θ̃ are the
smoothed parameters.

