Regular expressions for decoding of neural network
outputs
Tobias Strauß1 , Gundram Leifert1 , Tobias Grüning1 , and Roger Labahn1

arXiv:1509.04438v2 [] 22 Feb 2016

1

Department of Mathematics, University of Rostock, Rostock, Germany
February 23, 2016

Abstract
This article proposes a convenient tool for decoding the output of neural networks trained by Connectionist Temporal Classification (CTC) for
handwritten text recognition. We use regular expressions to describe the
complex structures expected in the writing. The corresponding finite automata are employed to build a decoder. We analyze theoretically which
calculations are relevant and which can be avoided. A great speed-up results from an approximation. We conclude that the approximation most
likely fails if the regular expression does not match the ground truth which
is not harmful for many applications since the low probability will be even
underestimated. The proposed decoder is very efficient compared to other
decoding methods. The variety of applications reaches from information
retrieval to full text recognition. We refer to applications where we integrated the proposed decoder successfully.

1

Introduction

Sequence labeling is the task of assigning a (class) label to each position of
an incoming sequence such as speech or handwriting recognition. These tasks
are typically very complex and even subproblems are challenging. This article
focuses on the decoding problem i.e. finding the most likely label sequence for
a given output of a classifier such as neural networks (NNs), Hidden Markov
Models (HMMs) or Conditional Random Fields (CRFs).
Deep learning methods has pushed the research of complex tasks such as
handwritten text recognition (see [8]). The special needs of such complex tasks
require advanced decoding methods. For example, a typical subproblem in full
text recognition is structuring the recognizers output into a sequence of regions
of words, punctuations and numbers. In many cases, the most likely label
sequence yields an acceptable segmentation. However, it happens that this label
sequence is not feasible i.e. it does not match the expected structure and has to
be corrected. Finding the optimal feasible structure is one of many applications
of this article. For this aim, we describe feasible structures by regular expressions
– a powerful pattern sequence which is used in nearly all computational text
processing systems such as text editors and programming languages like Java or
Python. We then derive an algorithm based on finite automata that yields the
most likely label sequence fitting the previously described regular expression.

1

Beyond finding the optimal feasible label sequence fitting an expected structure (regular expression), we gain several other features since we also consider
the functionality of capturing groups. A capturing group defines a part of the
regular expression. The associated part of the matching label sequence can be
used to structure the decoding result for further analysis. In case of our previous
example, we obtain a complete segmentation into words, numbers and symbols
without additional parsing facilitating the calculation of the matching subsequence and the likelihood. We just define word, number and symbol capturing
groups. The complete decoding can be done in a few lines of code.
Keyword spotting is another obvious application which can be solved very
conveniently. The keyword is either the beginning of the line or there is a space
or another separating symbol (quotation marks, opening parenthesis, etc.) before the keyword. With the common notation of regular expressions, this pattern
may be captured by inserting (.*(?<pre>[ "(-]))? before the keyword which
means: If there is anything before the keyword, it ends with at least one of the
aforementioned symbols. This last symbol (if there is one) is contained in the
capturing group pre. Information about a group like its probability, containing
text or its positions in the sequence are very important for the keyword spotting and will be provided directly by the derived algorithm. A low probability
of the pre-group, for example, might indicate that a letter is more likely than
our separating symbol such that the spotted character sequence is only part of
a larger word. Analogously, there is an equivalent group after the keyword.
Regular expressions can be very complex and the calculation of the probability of all feasible sequences can be very time consuming. We give an approximation of the most likely label sequence which we motivate theoretically and
experimentally. The approximation is also fundamental to the proposed decoder
since a conventional A∗ -search suffers from a combinatorial explosion of all feasible sequences and leads to inefficient decoding times. It is developed for neural
networks trained by Connectionist Temporal Classification (CTC). Thus, CTCtrained systems are assumed all over the paper. Some of the currently most
successful handwriting recognition systems were trained with CTC as shown in
several competitions. To give just one example, the probably most challenging
real world task is the Maurdor project which was won by A2IA in 2014 using
CTC (see [14]). CTC is not limited to text recognition. Recently the performance of several speech recognition systems trained with CTC equaled those of
other state of the art methods (e.g. [7, 15]).
The proposed algorithm is an essential part of the award winning systems
[18] and [11] which were also trained with CTC. Recently, the system reaffirmed
the capability by winning the HTRtS15 competition [17].
The performant connection between regular expressions and machine learning algorithms has been investigated in previous articles. In the context of
speech recognition, [13] showed in detail how to incorporate static prior knowledge like n-grams or phoneme models into finite state transducers. Although
the authors exploit similar models to do the decoding, the purpose differs from
ours since they model more static connections between ton, speech and language
while we aim at a flexible, adaptive decoding algorithm. Earlier, [4] provided a
comprehensive analysis of links between probabilistic automata (i.e. automata
with a probabilistic transition) and HMMs from a theoretical point of view finally concluding – among other – that there is a correspondence between both
models. This basically means, HMMs can be seen as the probabilistic version
2

of finite automata.
Some links between regular expressions, their corresponding automata and
HMMs are given in [10]. The authors showed how to create HMMs from regular
expressions to detect biological sequences. A similar but generalized approach is
given in [9]. There the authors construct a simplified HMM model for a general
text line in the context of word spotting. These text line models basically consist
of the keyword surrounded by space and filler models. They also proposed an
enhanced model where only the prefix or suffix of the keyword is given. This
model allows a set of feasible words containing the defined prefix or suffix.
Recently, Bideault et al. published a similar approach to ours in [1]. They
proposed an HMM - BDLSTM hybrid model for word spotting exploiting regular expressions. Their model uses the posterior probability of the network as
emission probability of the HMM (which means using P(y|x) as estimator for
p(x|y), where x is the hidden variable and y is the observation). Analogously
to [9], they build small HMM models in advance (e.g. for a keyword, for digits
or letters) and combine them to a model capturing the regular expression. The
authors then applied their model to keyword and “regex” spotting.
In contrast to the above articles, we do not make use of an HMM model.
Yet in [9], the HMMs work only as convenient graphical model for decoding
rather than as classifier. Instead of using a generative model to find the most
likely sequence, our algorithm is based on the original graphical structure of the
regular expressions: The finite state automata. If the automaton accepts a label
sequence, it is feasible. Hence, we are able to search in the output of a neural
network for any regular expression without any previously created or trained
generative model. That means as input simply serve a regular expression and
the network’s output matrix and the output is the most likely sequence, their
probability or the capturing groups defined by the regular expression.
The remainder of this article is organized as follows: We first give a formal
definition of decoding (Section 2). In Section 3, we give a brief introduction
to regular expressions and automata. Furthermore, we modify the automaton slightly to adapt it to the NN-decoding requirements. We introduce the
RegEx-Decoder in Section 4. We finish with some experiments (Section 5) and
a conclusion. The appendix provides the proofs of our theorems for theoretically
interested readers.

2

Training and decoding

This section introduces the CTC training scheme for neural networks and some
basic aspects of their decoding. We mainly follow the notation of [6].
Let Σ be the alphabet and Σ0 = Σ ∪ {?} where ? is an artificial garbage label
(also called blank) indicating that none of the labels from Σ are present. We
call the garbage label not a character (NaC) in the following. An element
of Σ isS called character and appears in the ground truth. Sequences from
Σ∗ := t∈N Σt are called words. Elements of Σ0 are labels and represent different
classes of the NN. Sequences of (Σ0 )∗ are called paths. The most likely path
is called bestSpath. Assume a neural network which maps an input X 1 to a
0
∞
matrix Y ∈ T =1 [0, 1]T ×|Σ | of probabilities per position and label. I.e. yt,l
1 In

contrast to Y , both dimensions of X may vary.

3

denotes
P the probability for the lth label at position t. Note that we assume that
∀t : l yt,l = 1 and ∀t, l : yt,l > 0 throughout the paper.
To map a path π to a word z , one merges consecutive identical πt and deletes
the NaC s. Let F : (Σ0 )∗ → Σ∗ define the related function which maps a path to
π ) = D(S(π
π )) is the composition of two functions D
a word. More precisely: F(π
and S where S deletes all consecutive identical labels and D deletes all remaining
NaC s.
We assume that the likelihoods yt,c are conditionally independent for distinct
t given X . Thus, the likelihood of any path π is given as
π |X
X) =
P(π

T
Y

yt,πt .

(1)

t=1

The probability of any word z is then the sum of the probabilities of all paths
mapping to z :
X
X) =
π |X
X ).
P(zz |X
P(π
z)
π ∈F −1 (z

Let z ∈ (Σ0 )∗ be the extension of the word z ∈ Σ∗ , that means we add a NaC
before z , after z and between each pair of characters. Thus, |zz | = 2|zz | + 1. Then
X ) in an iterative manner: The forward variable αi (t)
one could calculate P(zz |X
denotes the probability of the prefix z1 , . . . , zd i−1 e of z at time t given X and,
2
hence, α1 (t) denotes the probability of the empty word prefix. Thus,
α1 (t) =

t
Y

yt0 ,z1 =

t
Y

yt0 ,? .

t0 =1

t0 =1

For t = 1, the other initial αi (1) are
α2 (1) = y1,z2 = y1,z1
αi (1) = 0

∀i > 2.

Then, probability of any prefix at time t is
αi (t) = yt,zi

X

αk (t − 1)

(2)

k∈φz (i)

where
(
φz (k) =

{k − 1, k}
{k − 2, k − 1, k}

if z k = z k−2 or k = 2
.
else

X ) is then equal to the sum α|zz | (T ) + α|zz |−1 (T ) of the two
The probability P(zz |X
last forward variables at time T . Analogously, one can start at T and calculate

4

the suffix probabilities:
β|Z
Z | (T ) = 1
T
Y

β|Z
Z | (t) =

yt0 ,?

t0 =t+1

β|Z
Z |−1 (T ) = 1
βi (T ) = 0 ∀i < T − 1
X
βi (t) = yzi ,t+1
βk (t + 1)
k∈ψz (i)

where
(
ψz (k) =

2.1

{k + 1, k}
{k + 2, k + 1, k}

if z k = z k+2 or k = |zz | − 1
.
else

Connectionist Temporal Classification

To optimize the log likelihood objective function
X ) → max,
O(zz , X ) = − ln P(zz |X
Connectionist Temporal Classification uses gradient decent. Hence, we need to
provide the gradient
∂O(zz , X )
1
=
X)
∂yt,l
P(zz |X

X

T
Y

yt0 ,πt0

z ) t00=1
π∈F −1 (z
t 6=t
πt =l

for any t ∈ {1, . . . , T } and l ∈ Σ0 . With the above defined α and β,
X

T
Y

yt0 ,πt0 =

0

z ) t 0=1
π∈F −1 (z
t 6=t
πt =l

z|
|z
X
αi (t)βt (t)
.
yt,l
i=1

z i =l

zX

z ,X
X)
Starting with ∂O(z
∂yt,l , the standard backpropagation algorithm propagates error
into the network and optimizes its parameters. A more detailed description can
be found in [6].

2.2

Decoding

During the prediction phase, we are interested in the z ∈ Σ∗ with maximizes
X ). Usually, there are conditions which allow only certain z ∈ Σ∗ . A
P(zz |X
common example is the condition that z must be an element of a certain vocabulary V. If the allowed words are restricted to a finite vocabulary of reasonable
X ) for
size, one can find the most likely vocabulary item by calculating P(zz |X
each z ∈ V individually using the forward probabilities α as introduced above.
We call this decoding procedure string-by-string decoding since we calculate the
word probabilities one after the other. We approximate the word likelihood by
5

the probability of its most likely path throughout this article by replacing the
sum by maximum in eq. (2). The most probable path yields an alignment of positions and class labels, it speeds up the calculation and – since there is typically
X ). Thus,
one dominant path – it is a reasonable approximation to P(zz |X
z ∗ = argmax
z ∈V

3

max

z)
π ∈F −1 (z

π |X
X ).
P(π

Regular expressions and finite automata

Finding the most likely label sequence following a special structure requires a
tool for describing this structure. We model them as regular languages which
have been developed to describe such complex structures (see [5]). There is a
correspondence between regular languages / regular expressions and finite-state
automata – a model of computation of that language. We use both – the regular
expression to describe the set of expected sequences and the automaton to exploit the transition graph during the decoding process. This section gives a brief
introduction in the field of regular expressions and finite state automata. Readers who are already familiar with regular expressions and finite state automata
may proceed with Subsection 3.1.
Definition 1 (regular expression / regular language). The empty word ε, the
empty set ∅ and a ∈ Σ are regular expressions denoting the regular languages
{ε}, ∅ and {a}, respectively. If L(r1 ) and L(r2 ) are two regular languages
defined by the regular expressions r1 and r2 , then also L(r1 ) ∪ L(r2 ) = L(r1 |r2 )
(alternation, i.e. r1 or r2 ), L(r1 )L(r2 ) = L(r1 r2 ) (concatenation of r1 and r2 )
and (L(r1 ))∗ = L(r1∗ ) (Kleene closure, i.e. the set of all finite sequences of words
from L(r1 )) are regular languages. There are no other regular languages than
the above.
Thus, regular expressions define languages containing specific sequences of
literals from Σ. Those expressions can be represented in a model of computation.
This model is known as
Definition 2 (Automaton). The nondeterministic finite automaton (NFA) N
is a 5-tuple (Q, Σ ∪ {ε}, δ, q0 , F ), where Q is the finite set of states, Σ is the
alphabet, ε is the empty word, δ : Q × Σ ∪ {ε} → P(Q) is the state transition
function, q0 ∈ Q is the initial state and F ⊆ Q is the set of final states.
We call N a deterministic finite automaton (DFA) iff ∀q ∈ Q : δ(q, ε) = ∅
and ∀q ∈ Q, a ∈ Σ : |δ(q, a)| ≤ 1.
For any regular expression there is an NFA accepting the corresponding
language and the other way around. There may be more than one automaton
accepting a regular language. Analogously, there may be more than one regular
expression describing the same language. For any specific regular expression, we
will create a corresponding NFA using Thompson’s Construction Algorithm (for
details see [19] according to which any regular expression can be converted by
some combination of the elementary NFAs depicted in Figure 1). An equivalent2
DFA is obtained by the Subset Construction Algorithm.
Generally, the subset construction algorithm generates a DFA with 2n states
if n is the number of NFA states. [12] showed that there are languages which
2 Two

finite automata are equivalent if they accept the same language.

6

NA

ε

ε

ε
ε

ε

ε
ε

NB

NA

ε

(b) A∗

(a) A|B

ε

NA

NB

(c) AB

Figure 1: Schematic representation of atomic NFAs resulting from Thompson’s
Algorithm. A and B are regular expressions and NA and NB are the related
NFAs. Other quantifiers or operators can be expressed by those three.
c
q1

c

q2

q1

(a) transition

?

q3

c

(b) substitution

q2

q1

?

q2

(c) leaf substitution

Figure 2: Illustrations for extended NFAs. Double circles represent final state.
also require exactly 2n DFA states, i.e. the NFA is exponentially more succinct
than the DFA. Instead of using DFAs, we substitute the states of the NFA by
their epsilon closure and use the resulting NFA. That means, we delete each εtransition and replace it by the next non-ε-transition. The resulting automaton
will accept the same language as the original one.

3.1

Adaptation to F

The function F (see Section 2) maps a label sequence to a word by deleting
consecutive identical labels (S) and deleting NaC s (D). To allow optional NaC s
between different characters during the decoding, we extended the word z to z̄z̄.
Analogously, we extend the transitions between the NFA-states the following
way: Figure 2(a) shows the transition which is substituted by Figure 2(b). If
q1 is final also q3 is final. q1 and q2 could even be the same state. Final
leaf states (i.e. states without outgoing edges) are connected to another finale
state by reading a NaC as shown on the Figure 2(c). Algorithm 1 provides the
w∈
pseudo code for extending the automaton. It accepts the language L(r) := {w
w ∈ L(rr )} of words interrupted by optional3 NaC s.
L(??w1 ? ?w2 ? ? . . . ? ?w|ww| ? ?)|w
This is the adaptation to the D-part of F.
Instead of adapting N also to S, we leaf this step to the algorithm in Section
4 to simplify the notation. Since S deletes identical consecutive labels, the
continuation of a read label is left (see the “cont” function in later sections). We
call the automaton adapted to D extended automaton and symbolize it by N .
Example 3. We construct an automaton accepting the language L = {cat, bat}.
The naïve alternation cat|bat of both words leads to an automaton with 14
states using Thomson’s Construction and the above described extension. We
3 We

use the regular expression notation (?) to mark symbols as optional.

7

Algorithm 1: extendAutomaton
input : NFA (Q, Σ, δ, q0 , F )
output: Extended NFA (Q, Σ0 , δ, q0 , F )
Q ← Q;
F ← F;
for q ∈ Q do
create new state q 0 ;
Q ← Q ∪ {q 0 };
δ(q, ?) ← {q 0 };
for a ∈ Σ do
δ(q 0 , a) ← δ(q, a);
if q ∈ F then
F ← F ∪ {q 0 };

could save 4 states and transitions by alternating only the first letters. The
regular expression (c|b)at will generate the following automaton:
?

c
c

?

start

b
b

t

a

a

?

a

?

t

a

?

If we aggregate the labels c and b like [bc]at, we could save two additional
states and even 5 transitions. Thus, instead of using multiple arcs for connecting the same states but reading different labels, we aggregate them into one
transition:
c |b
start

?

t

a
c |b

a

?

?

t

?

Thus, there is at most one transition between any two states which reads possibly
multiple labels. Obviously, any accepted label sequence produces an emission
sequence collapsing to “cat” or “bat”. Note, that we need just 10 transitions
where the decoding process from Section 2 needs to calculate 7 table columns
for each word. If we add the words fat, rat, hat to our list of accepted words,
the conventional decoding of Section 2 calculates 3.5 more table columns than
there are transitions in the automaton.

4

Efficient decoding of regular expressions

Given a regular expression r and the corresponding extended NFA N = (Q, Σ0 , δ, q0 , F ),
we search for the most likely word z ∗ in L(rr ):
z ∗ = argmax

max

−1 z )
r ) π ∈F (z
z ∈L(r

8

π |X
X ).
P(π

In contrast to calculating the likelihood of every single feasible word from L(rr ),
we exploit the graphical structure of N to find z ∗ . This can be done very
efficiently if N is succinct (as e.g. in Example 3).

4.1

A∗ and beam search

In this subsection, we review two standard algorithms – the A∗ -search and the
beam search – which are standard approaches of decoding.
Algorithm 2 describes a naïve A∗ -search algorithm on regular expressions
that returns the most likely path. This algorithm yields the best result but
it can be time consuming because of the huge number of possible paths. To
π , t|X
X ) for the final probability
cut unlikely paths, we define an upper bound P(π
πτ |X
X ) of the final path π τ starting with the prefix π (position 1 to t). In
P(π
our experiments, we filled up π with a β suffix (i.e. τ := β t+1:T ) such that
Q
Q
π , t|X
X ) := tr=1 yr,πr Ts=t+1 ys,βs . Another heuristic which appears to work
P(π
π

X

X)
well in practice is to sort the prefix list L by P(ππ,t|X
. This sorting yields a quick
t
first best guess such that unlikely paths can be deleted soon.

Algorithm 2: A∗ -search
input : Network output Y , extended NFA N = (Q, Σ0 , δ, q0 , F )
output: most likely feasible path π ∗
for γ ∈ Σ0 do
for q 0 ∈ δ(q0 , γ) do
Add (q 0 , γ, 1) to L;

/* initialize L */

while L not empty do
(q, π , t) ← Item from L with maximum
Remove (q, π , t) from L;
if t < T then
for γ ∈ Σ0 \ {πt } do
for q 0 ∈ δ(q, γ) do
Add (q 0 , π γ, t + 1) to L;

π ,t|X
X)
P(π
;
t

Add (q, π πt , t + 1) to L;
/* cover the S part of F */
else if q ∈ F then
π∗ ← π;
π 0 , t0 |X
X ) < P(π
π |X
X );
Remove all (q 0 , π 0 , t0 ) ∈ L with P(π

Since the number of feasible paths grows exponentially in the worst case,
there is a standard heuristic to reduce the search space called beam search. For
example in [7], the authors introduced a beam search algorithm for efficient
decoding in case of speech recognition which allows only n prefixes4 at any position. Algorithm 3 contains its pseudo code adapted to our problem. Generally,
beam search does not guaranty to find the optimal sequence. The given algorithm has the additional drawback that it does not even guaranty to find any
4n

is called the beam width.

9

feasible path at all since the final list L could contain only (q, π , T ) with q 6∈ F .
Algorithm 3: beam search
input : Network output Y , extended NFA N = (Q, Σ0 , δ, q0 , F )
output: most likely feasible path π ∗
for γ ∈ Σ0 do
for q 0 ∈ δ(q0 , γ) do
Add (q 0 , γ, 1) to L;

/* initialize L */

for i ← 2 to T do
L ← the n most likely item of L;
L ← {};
for (q, π , t) ∈ L do
for γ ∈ Σ0 \ {πt } do
for q 0 ∈ Q : q 0 ∈ δ(q, γ) do
Add (q 0 , π γ, t + 1) to L;
/* cover the S part of F */

Add (q, π πt , t + 1) to L;

π |X
X ) and q ∈ F ;
π ∗ ← π from (q, π , t) ∈ L with maximum P(π

4.2

RegEx-Decoder

In this subsection, we introduce another decoding algorithm which exploits the
structure of the given automaton and thus is more efficient than the A∗ -search
and guaranties – under mild conditions – to return the most likely path at the
same time. In contrast to the token passing algorithm from [20], one transition
may read several input labels. We finally show that considering the three most
likely labels per arc and position is sufficient. This feature allows us to preprocess the network output Y such that each arc only processes the most likely of
their reading outputs which avoids unnecessary calculations. Additionally, we
keep less paths compared to the token passing algorithm.
Let Π(t, q 0 , q) be the set of prefixes of F −1 (L(rr )) of length t on condition
that the automaton moves from state q 0 to q at position t. Instead of keeping
all possible prefixes, we only keep one prefix per arc, label of that arc and
time point: The probability of most likely prefix from Π(t, q 0 , q) is denoted by
1
i
αt,q
Multiply labeled arcs have different super scripts i of αt,q
0 ,q .
0 ,q each of
0
i
them corresponding to a different label of (q , q). The αt,q0 ,q can be calculated
iteratively by
i
αt,q
0 ,q =

max

πn
∈Π(t,q 0 ,q) o
j
πt 6∈ ζt,q
0 ,q |j<i

π |X
X)
P(π

i
0
where ζt,q
0 ,q denotes the ending label πt of the specific t-prefix π ∈ Π(t, q , q)
j
i
i
5
which has a likelihood of αt,q0 ,q (i.e. ζt,q0 ,q 6= ζt,q0 ,q for i 6= j). If we maximize
5 Let

αit,q0 ,q

i
αit,q0 ,q be the probability of the most likely prefix π i , then πti = ζt,q
0 ,q . Further,

> αi+1
.
t,q 0 ,q

10

over an empty set, we assume the result is zero. Let α be a variable containing
0
0
i
0
0
αt,q
0 ,q for each i, t and (q , q). Let P(q) = {q ∈ Q | ∃a ∈ Σ : q ∈ δ(q , a)} be
the set of predecessor states of q.
Remark 4. Let N be the extended automaton with respect to a regular expression r and α as defined above. The probability of the most likely path π ∗ (rr )
π ∗ (rr )) ∈ L(rr ) is given by
with F(π
π ∗ (rr )|X
X ) : = max
P(π

max

z)
z ∈L(r) π ∈F −1 (z

=
=

π |X
X)
P(π

max

max

max

1
αT,q
0 ,q .

q∈F,q 0 ∈P(q) π ∈Π(T,q 0 ,q)
q∈F,q 0 ∈P(q)

π |X
X)
P(π

1
Thus, we only need αT,q
0 ,q to calculate the likelihood of r with respect to Y .
Unfortunately, we need also the preceding α i for i > 1 to calculate α 1 .
Let
i
γt,q
argmax
y
0 ,q :=
n
o t,a
a∈Σ0 \

j
γt,q
0 ,q

S

j<i
0

q∈δ(q ,a)

be the ith likely label per arc (q 0 , q) and position t. This especially means
i
yt,γ 1 0 ≥ yt,γ 2 0 ≥ . . . . Obviously, the initial values of α are α1,q
0 ,q = y1,γ i
0
t,q ,q

t,q ,q

1,q ,q

i
if q 0 = q0 and α1,q
0 ,q = 0 else.

Remark 5. Note that every non-NaC -arc represents a character or a group
of equivalent characters of the regular expression. Thus, two consecutive arcs
must not read the same label a ∈ Σ at consecutive positions since this means
moving two characters forward in the accepted word. But a sequence of identical
consecutive labels is mapped to one character by F which means F allows
only one step forward. Thus, if the most likely previous arc (q 00 , q 0 ) ends on
1
1
ζt−1,q
00 ,q 0 = γt,q 0 ,q , we calculate the t-prefix probability by either combining the
1
1
most likely (t−1)-prefix not reading γt,q
0 ,q with γt,q 0 ,q or we keep the most likely
2
(t − 1)-prefix extending it by the second most likely label γt,q
0 ,q . In the first case,
2
we have to calculate also α t for all arcs.
i
There are two possible types of contributions to calculate αt,q
0 ,q : We either
come from a previous arc (i.e. append a new label) or we continue reading
the label of the previous prefix through (q 0 , q) (i.e., stay on the arc and cover
1
the S part of F). For the most likely t-prefix the likelihood αt,q
0 ,q is obviously
calculated by
1
0
0
αt,q
0 ,q = max{app(t, q , q, 1), cont(t, q , q, 1)}

where
 k
0
0
k
app(t, q 0 , q, 1) = 00max 0 max αt−1,q
00 ,q 0 yt,a | a ∈ Σ \ {ζt−1,q 00 ,q 0 } : q ∈ δ(q , a)
q ∈P(q ) k,a
n
o
k
cont(t, q 0 , q, 1) = max αt−1,q
.
0 ,q yt,ζ k
0
k

t−1,q ,q

11

A straight forward generalization with the additional restriction not to read
j
i
ζt,q
0 ,q (j < i) leads to the general calculation schema of αt,q 0 ,q :
i
0
0
αt,q
0 q = max {app(t, q q, i), cont(t, q , q, i)}

(3)

where
n
k
app(t, q 0 , q, i) = 00max 0 max αt−1,q
00 ,q 0 yt,a |
q ∈P(q ) k,a


o
j
k
: q ∈ δ(q 0 , a)
a ∈ Σ0 \ {ζt−1,q
00 ,q 0 } ∪ {ζt,q 0 ,q |j < i}
n
o
j
k
k
cont(t, q 0 , q, i) = max αt−1,q
|∀j
<
i
:
ζ
0 ,q yt,ζ k
0 ,q 6= ζt,q 0 ,q .
t−1,q
0
k

(4)

(5)

t−1,q ,q

i
0
Starting from q0 , we now calculate αt,q
0 ,q for each i, arc (q , q) and time point
1
t. The maximum αT,q0 ,q for q ∈ F will be the maximum probability of all
feasible paths. We yet even reduced the search space by keeping only one prefix probability per arc, allowed label of the specific arc and time point. This
means, we have a polynomial time complexity (instead of an exponential time
complexity
the A∗ -search). More precisely, the calculation of α requires
P as P
0
O(T |Σ | q∈Q q0 ∈P(q) |P(q 0 )|) multiplications in the worst case. Although the
running time seems to be cubic in the number of states |Q|, in practical applications, the number of predecessors of each state is typically limited by a constant.
Thus, the expected running time is rather linear in Q.
The most likely path can be found via simple backtracking.

Speed-up
In the following, we analyze the most likely paths of α and speed-up the process
by avoiding unnecessary calculations. The speed-up is based on two theorems
which finally lead to a time complexity which is independent of the number of
1
labels in Σ0 . The first theorem states that it is sufficient to know αt,q
00 ,q 0 and
2
00
0
0
αt,q00 ,q0 for every q ∈ P(q ) to calculate both app(t + 1, q , q, 1) and app(t +
1, q 0 , q, 2). Additionally, we only need the three most likely probabilities yt+1,a
per arc and time step no matter how many labels allow to move from q 0 to q.
j
k
Theorem 6. Let Γ(t, k, q 00 , q 0 , q) := {γt,q
0 ,q | j ∈ {1, 2, 3}} \ {ζt−1,q 00 ,q 0 } the
i
three most likely labels without the previous ending label ζt−1,q
00 ,q 0 . Then for
i = 1, 2 eq. (4) simplifies to
k
00
app(t, q 0 , q, 1) = max{αt−1,q
∈ P(q 0 ), k ∈ {1, 2}, a ∈ Γ(t, k, q 00 , q 0 , q)}
00 ,q 0 yt,a |q
k
00
app(t, q 0 , q, 2) = max{αt−1,q
∈ P(q 0 ), k ∈ {1, 2},
00 ,q 0 yt,a |q
1
a ∈ Γ(t, k, q 00 , q 0 , q) \ {ζt,q
0 ,q }}

.

The proof of Theorem 6 can be found in the Appendix. An equivalent
statement using the same values as in Theorem 6 for the calculation of the

12

likelihood of consecutive identical labels calculates cont(t, q 0 , q, i) as
n
k
g q 0 , q, 1) = max αt−1,q
cont(t,
| k ∈ {1, 2} :
0 ,q yt,ζ k
t−1,q 0 ,q
o
j
k
ζt−1,q
0 ,q ∈ {γt,q 0 ,q |j = 1, 2, 3}
n
k
k
1
g q 0 , q, 2) = max αt−1,q
cont(t,
| k ∈ {1, 2} : ζt−1,q
0 ,q yt,ζ k
0 ,q 6= ζt,q 0 ,q ∧
t−1,q 0 ,q
o
j
k
ζt−1,q
0 ,q ∈ {γt,q 0 ,q |j = 1, 2, 3} .

(6)

g q 0 , q, i) =
Although cont(t,
6 cont(t, q 0 , q, i) in general, the conditions given in
Theorem 7 are sufficient to ensure that this approximation does not influence
the final probability.
Theorem 7. Let π ∗ be the most likely feasible path with respect to the regular
expression r . Assume the following conditions:
∗
1. ∀t : (πt∗ , . . . , πt+n
) = an ∈ Σn ⇒ n ≤ 2 (i.e. π ∗ contains at most 2
consecutive identical labels from Σ)

2. ∀t : |{a ∈ Σ : yt,a > yt,? }| < 3 (the NaC is one of the three most likely
labels at each position)
1
π ∗ |X
X ) if α is calculated using (6)
Then, there is a q ∈ F such that αT,q
0 ,q = P(π
as substitution for (5).

Again, the proof can be found in the Appendix.
Remark 8. Errors only appear for arcs reading more than 2 characters. We
call these arcs critical.
The conditions of Theorem 7 are not unlikely to occur in Recurrent Neural
Networks trained with CTC. The NaC is always very probable (condition 2) and
the likelihoods of other labels are often very spiky (condition 1) i.e. one rarely
observes more than two consecutive identical labels in the best path except for
the NaC. (In [2] they call this the dominance of blank predictions.)
Remark 9. Theorem 6 and 7 allow us to preselect the most likely channels per
arc and position. The calculations of any arc can be reduced by calculating the
probability of prefixes ending on the three most likely labels of the considered
arc.
i
i
00
i
The calculation of αt+1,q
∈ P(q 0 ) and αt,q
0 ,q requires αt,q 00 ,q 0 for all q
0 ,q .
i
Thus, there are two possible chronological orders to calculate the αt,q0 ,q :
i
1. Fix t and calculate αt,q
0 ,q starting at q0 before moving on to t + 1.
i
2. Fix (q 0 , q) and calculate αt,q
0 ,q for all t before moving on to the successor
states.

We suggest the second variant mainly because of computational reasons. Finishing the calculation of one state allows to keep the necessary values in the
cache and promises a fast calculation. However, we did not test the first variant. The downside of the second variant is that we must not allow circles of
length greater than one for the automaton N (which results is circles of length
13

2 in the extended automaton). Otherwise, we would require information of subsequent (not yet calculated) arcs. This restriction forbids to use the Kleene star
operator in any regular expression. To allow at least the Kleene star for single
characters or character groups, we calculate all transitions depicted in Figure
2(b) at once whenever q1 = q2 .
The Algorithms 4 and 5 show the pseudo code of the proposed algorithm.
Algorithm 4: RegExDecoder
input : Network output Y , regular expression r
π ∗ (rr )|X
X)
output: Likelihood p = P(π
N ← createNFA(r);
// Thompson’s Construction Algorithm
N ← extendAutomaton(N );
// Algorithm 1
for q ∈ Successor(q0 ) do
1/2
calculate (αt,q0 ,q )Tt=1 ;
// Algorithm 5
p = 0;
for q ∈ F do
1
foreach q 0 ∈ P(q) do p ← max{p, αT,q
0 ,q }

Capturing Groups
As already mentioned, information about a part of the regular expression can be
crucial. In case of keyword spotting for example, the likelihood of the keyword
determines whether or not the current spot is accepted. But also the likelihood
of labels next to the keyword are important to decide whether or not the spotted
word is only a part of a larger word. To connect parts of the regular expression
with parts of the automaton, we take advantage of the notation of capturing
groups:
A capturing group g of a regular expression r is a consecutive part within a
pair of parentheses. Thus, the group is related to certain arcs of the automaton.
Hence, only if the most likely path related to r makes use of any arc related
to g, g captures some part of the current output Y . Then, the captured label
sequence is the part of most likely path π ∗ (rr ) read by the subautomaton related
to g. In a straight forward way, one calculates the probability or the bounds
(start and end position) of g according to π ∗ (rr ).6
Vocabularies
Typically, a decoding process includes one or more vocabularies. The regular
expression of such a vocabulary can be expressed as an alternation of words.
The optimal automaton accepting a collection of words is well know: The deterministic, acyclic finite state automata (DAFSA). There are very efficient
algorithms for a constructing a corresponding minimal DAFSA (see [3]). The
number of arcs decreases dramatically compared to alternating the vocabulary
words naïvely.
6 Since the NaC is not part of the regular expression, one may decide whether or not the
likelihood calculation and the optimal path include the starting and tailing NaC -labels.

14

1/2

Algorithm 5: calculate (αt,q0 ,q )Tt=1
input : likelihoods α , ending labels ζ , extended NFA N
i
00
if all αt,q
∈ P(q 0 ) are calculated then
00 ,q 0 with q
for i ← 1 to 2 do
if q 0 == q0 then
i
;
α1,q
0 ,q ← y1,γ i
0
1,q ,q

i
i
ζ1,q
0 ,q ← γ1,q 0 ,q ;
else
i
α1,q
0 ,q ← 0;

for t ← 2 to T do
app1t ← 0;
cont1t ← 0;
for k = 1 to 2 do
for j = 1 to 3 do
for q 00 ∈ P(q 0 ) do
j
k
if ζt−1,q
00 ,q 0 6= γt,q 0 ,q then
n

k
app1t ← max app1t , αt−1,q
00 ,q 0 y
t,γ j

t,q 0 ,q

k
if ζt−1,q
0 ,q ==

cont1t

j
γt,q
n0 ,q

o
;

then

k
← max cont1t , αt−1,q
0 ,q y
t,γ j

t,q 0 ,q

o
;

1
1
1
αt,q
0 ,q ← max{appt , contt };
1
1
i
update(ζt,q
// set ζt,q
0 ,q );
0 ,q to the maximizing γt,q 0 ,q
2
// calculate αt,q0 ,q analogously with the additional
1
constraint not to read ζt,q
0 ,q
1/2

foreach q̂ ∈ Successor(q) do calculate (αt,q,q̂ )Tt=1

15

Table 1: Statistics over the text recognition experiment: “size” denotes the
number of words of the vocabulary, “# arcs” denotes the number of arcs in
automaton and “# critical arcs” denotes the number of arcs which read more
than 2 labels. “greatest deviation - absolute” denotes the difference between the
exact negative logarithmic probability and the result of the RegEx-Decoder.
The “greatest deviation - relative” is the deviation divided by the exact absolute
logarithmic probability.

vocabulary
HTRtS
general English

size
9273
21698

# total
12398
25997

arcs
# critical
12
32

greatest deviation
absolute relative
9.95E-14 2.1E-12
9.95E-14 2.1E-12

Nevertheless, the number of arcs increases strongly for large vocabularies
such that a fast and effective decoding process is impossible.

5

Experiments

The aim of this section is to show that the decoding works properly and fast.
We show that the Algorithms 4 and 5 work correctly in practical applications
and analyze situations when it fails. We compare our approximation of eq. (6)
with the exact most likely path. Further applications of the RegEx-Decoder can
be found in [18] and [11].
We did all time statistics on a laptop with Intel i7-4940MX 3.10GHz CPU,
32GB RAM and SSD.

5.1

Text recognition

First, we show that our approximation is reasonable for practical applications
such as the HTRtS competition from the ICFHR2014 (see [16]). The data consists of 400 handwritten pages. We train on 350 pages and validate on 50 pages.
The validation set is also used to evaluate the decoding. Each page consists
of several lines of text including words, punctuations, numbers and symbols.
The neural network used in [18] generates the output matrices. We compare
the most likely word of a vocabulary obtained by the RegEx-Decoder7 with
the result of the string-by-string decoding from Section 2. For this purpose,
the RegEx-Decoder is used to splits these matrices into regions of words and
region containing spaces, numbers etc. The evaluation is done on the resulting
4657 submatrices representing the word regions. These matrices correspond to
outputs of subimages of single words. We use two vocabularies: one containing 9273 words (generated from HTRtS data) and one containing 21698 words
(a modern, general vocabulary made from two million English sentences from
http://corpora.uni-leipzig.de/).
Table 1 shows the deviation of the negative logarithmic likelihood of the
RegEx-Decoder and the exact decoding. Clearly, the deviation is negligible.
7 The

automaton is generated using the strategy of Section 4.2.

16

Figure 3: Artificial writings of two numbers for the number recognition task.
There is an intersection of both vocabularies which includes especially the most
frequent words. Thus, it is not surprising that both vocabularies show the
same deviation since both extrema (the greatest absolute and relative deviation)
appear for the same words (“General” and “of”). Since the number of critical arcs
is very small, we expected a small divergence due to our approximation. In fact
there is no additional confusion of words because of our approximation. Thus,
the experiment shows that the approximation of Theorem 7 can be applied in
practical applications with few critical arcs.
We evaluated the impact of the decoder empirically on the HTRtS15 test
set. We decreased the word error rate by 3 percentage points compared to the
best path decoding of the entire line (from 50.89% to 48.06%) just by defining
an appropriate regular expression for the expected line structure without any
vocabulary. Including a vocabulary, we further decreased the WER to 33.90%.

5.2

Number recognition

The next experiment involves artificially generated writings and investigates the
correctness of Alg. 4 in case of a relatively large number of critical arcs. By
Remark 8, we know that errors only appear for arcs reading more than two
labels. We enforce this condition by searching only for digits. Thus, every
arc not reading NaC s is critical since these arcs read more than two labels.
To enforce further continuation errors8 , we vary the number of digits actually
depicted in the image while the search pattern remains 3 to 5 digits (i.e. the
regular expression is [0-9]{3,5}). If the number of digits is greater than 5, the
decoder has to suppress emissions which also promotes errors.
We vary the number of digits from 4 to 9. For each number of digits, we
generate 10,000 synthetic writings. The digits are narrowly written to enforce
further confusions (see Figure 3). The resulting images work as input to four
neural networks with different number recognition expertise. We will compare
the decoding results over the output matrices generated by these networks. The
RegEx-Decoder searches in these output matrices for the most likely number
with 3 to 5 digits. The resulting number and probability is compared with the
most likely number resulting from a traditional string-by-string decoding as in
Section 2 using a vocabulary of all numbers with 3 to 5 digits. Any difference
in the resulting optimal path (but not its probability) is regarded as an error.
Table 2 shows the errors per network and digits in the image. The more the
algorithm is forced to suppress digits the more errors occur. For 4 and 5 digits
there is no force to suppress any written digit since the corresponding automaton
is allowed to accept the ground truth. The errors are negligible in this case.
However, although there are almost no errors in the resulting path, there are
8 Remember

that errors only happen while calculating cont(t, q 0 , q, i).

17

Table 2: Number recognition task: Number of differences in the most likely
paths of the RegEx-Decoder and the exact decoding for different neural nets
and different number of digits in the image but constant regular expression of
[0-9]{3,5}.

net1
net2
net3
net4

4
0
0
0
0

5
0
0
0
1

6
1
24
6
4

7
12
27
3
4

8
9
40
4
7

9
27
40
4
7

small differences between the probability of the string-by-string decoding and
the RegEx-Decoder. From 6 to 9, digits there are already significantly many
errors.
Even if there is a relatively high number of critical arcs, there will be only
little error if the regular expression fits to the image content. If it does not
fit to the number of digits in the image there will be a high risk of generating
additional confusion errors because of our approximation. However, even under
exact decoding the best feasible path then has a very low probability which can
only by further underestimated by the approximation. Hence the approximation
will likely not be harmful here since the decoding process result can either be
rejected immediately or it is unlikely to be of any significance in downstream
processing steps.
Figure 4 shows the required decoding time for the above network outputs and
regular expression. The RegEx-Decoder needs between 0.19 ms and 0.28 ms per
network output on average. The conventional string-by-string decoding needs
at least 4.68 ms per network output since it has to calculate the probabilities of
more or less all numbers with the specific number of digits under consideration.
To speed up the decoding time, this decoding method reuses already calculated
probabilities whenever the beginnings are the same9 . Additionally, it stops the
calculation of paths if the probability falls below the best yet found match. Even
with this speed-up mechanism the RegEx-decoder is more than 22 times faster.
The running time for the A∗ -search is growing exponentially as expected but
the results match perfectly those of the string-by-string decoding.
The beam search with beam value 100 needs almost seven times more time
for the calculation than the RegEx-Decoder. A point of criticism might be that
we use no independent implementation to compare the time complexity and we
may not implemented the beam search algorithm optimally. Figure 5 shows the
corresponding extended automaton. Let us count the multiplications: Beam
search with beam width 100 calculates for each of the 100 prefixes at each time
step 11 new prefixes (one for each digit plus one adding the NaC ) and thus 1100
multiplications per time step in total in the worst case. The RegEx-Decoder
calculates for each of the 10 arcs which read digits 6 new prefixes and for each of
the 6 transitions requiring a NaC there is only one multiplication. Thus, we have
66 multiplications in total. Therefore, our theoretical analysis rather indicates
that the RegEx-Decoder is implemented suboptimally since beam search needs
9 I.e.

12345 and 12346 share all probabilities for the prefix 1234.

18

10000
beam search (beam width 100)
A∗ -search
string-by-string decoder
RegEx-Decoder

time (s)

1000

100

10

1

4

5

6

7

8

9

# digits
Figure 4: Decoding times for the number recognition task (10,000 output matrices) averaged over all four networks.
[0-9]

start
?

[0

-9

]

[0-9]
?

[0

]

-9

[0-9]
?

]

-9

[0

[0-9]
?

-9

[0

]

[0-9]
?

[0

]

-9

?

Figure 5: Extended automaton accepting 3 to 5 digits and optional intermediate
NaC s.
16 times more multiplications. Although beam search with beam width 100 is
much slower it yields significantly more errors (round about 40 errors on average
if the ground truth are 4 or 5 digits). To get a comparable performance for the
experiments with 4 and 5 digits, we need a beam width of at least 100010 .

6

Conclusion

In this article, we consider regular expressions for the decoding of neural network
outputs. Regular expressions are a very efficient way to define a pattern of
interest to search in text strings. We suggest to use this pattern for a convenient
and clear decoding process. Similar results may also be archived by a smart
evaluation of the best path. The advantage of regular expressions over individual
10 The running time increases from round about 15 sec to 115 sec for all 10,000 output
matrices.

19

evaluation of the output is the simple and unified notation. Furthermore, the
proposed algorithm allows a highly adaptable decoding process since only the
regular expression has to be changed.
We show how to exploit finite automata to find the most likely feasible label
sequence of a regular language. A further analysis of the decoding procedure
yields a speed-up of the algorithm such that it also works fast for complex regular expressions or many network outputs. We propose also an approximation
which is shown to be exact under conditions which are commonly satisfied for
CTC-trained networks. This theoretical result was confirmed by experiments.
As a main result, we showed that the decoder is applicable in practical scenarios. Even if the approximation fails to produce exact results, it is likely that
the ground truth does not fit to the regular expression. This results in a low
probability decoding result further underestimated by our approximation which
should not be harmful in most applications. Additionally, these experiments
show that the proposed method is very efficient compared to state of the art
decoding algorithms.
π |X
X ) (instead
The proposed speed-ups work only for the path probability P(π
of the word probability). If the decoder should return the exact probability,
all paths contribute to the result and, thus, cannot be skipped. Hence, speedups seem to be hard. Additionally, we have to take care about distinct paths
through the automaton accepting the same label sequence. An Unambiguous
FSA or even a DFA is required to ensure that the automaton accepts every
path (of labels) only once. We already discussed the disadvantages of DFAs in
Section 3.
There are plenty of applications for the proposed algorithm. The method
can be applied e.g. to keyword spotting but also patterns of image retrieval
tasks can be described conveniently. The proposed decoder is an essential part
of our handwriting recognition systems e.g. for HTRtS (full text recognition)
and ANWRESH (form reading) competitions.

7

Acknowledgment

This research was supported by the research grant no. KF2622304SS3 (Zentrales
Innovationsprogramm Mittelstand) of the Federal Ministry for Economic Affairs
and Energy (Germany).
The authors would like to thank the anonymous reviewers for their valuable
comments improving the manuscript. We also thank U. Siewert for his detailed
and profound comments.

Appendix
Proof of Theorem 6. For t = 1, the claim is correct since the most likely path
of length 1 consists of the most likely character if q 0 = q0 . Otherwise we obtain
zero.
Let t > 1. To keep things simple, we fix q 00 to consider only prefixes through
1
(q 00 , q 0 ) and (q 0 , q). Therefore, let αt,q
00 ,q 0 ,q be the likelihood of the most likely

20

q 00

1
ζt,q
00 ,q 0

1
ζt+1,q
0 ,q

q0

q

1
yt+1,γt+1

αt1

2
yt+1,γt+1

αt2

Figure 6: Most likely suffix trough q 00 , q 0 and q and possible combinations to
1
calculate αt+1,q
00 ,q 0 ,q .
1
prefix through q 00 , q 0 and q and let ζt,q
00 ,q 0 ,q the read label at t. Then
1
app(t + 1, q 0 , q, 1) = 00max 0 αt+1,q
00 ,q 0 ,q .
q ∈P(q )

2
00 0
Analogously, let αt,q
00 ,q 0 ,q be the most likely feasible sequence through q , q and
1
q not ending on ζt,q0 ,q . Then
2
app(t + 1, q 0 , q, 2) = 00max 0 αt+1,q
00 ,q 0 ,q .
q ∈P(q )

The theorem is proven if
n
o
1
i
00 0
αt+1,q
αt,q
00 ,q 0 ,q = max
00 ,q 0 yt+1,a | i ∈ {1, 2}, a ∈ Γ(t + 1, i, q , q , q)
n
o
2
i
00 0
1
αt+1,q
αt,q
00 ,q 0 ,q = max
00 ,q 0 yt+1,a | i ∈ {1, 2}, a ∈ Γ(t + 1, i, q , q , q) \ {ζt+1,q 0 ,q } .
We make a case distinction, calculate the exact probability and show that
j
i
i
αt+1,q
00 ,q 0 ,q only depends on αt+1,q 00 ,q 0 for i ∈ {1, 2} and γt+1,q 0 ,q for j ∈ {1, 2, 3}.
j
For sake of simplicity, we omit the index q 0 , q for γt+1,q
0 ,q for the rest of the proof
00 0
i
i
i
i
i
Analogously, we omit q , q for αt,q00 ,q0 . Thus, αt = αt,q
00 ,q 0 and γt+1 = γt+1,q 0 ,q .
We check the following cases:
1
1
1: ζt,q
00 ,q 0 6= γt+1 , i.e. there are no restrictions by F. Hence, the most likely
path combines the most likely path through q 00 , q 0 with the most likely
1
label γt+1
at arc (q 0 , q):
1
1
αt,q
00 ,q 0 ,q = αt yt+1,γ 1
t+1

1
2
a: ζt,q
00 ,q 0 6= γt+1 (see Figure 7(a)). There are no restrictions such that
the second most likely path is
2
1
αt+1,q
.
00 ,q 0 ,q = αt yt+1,γ 2
t+1
1
2
1
b: ζt,q
00 ,q 0 = γt+1 (dotted combination in Figure 7(b)). The suffices γt+1
1
2
0
and (ζt,q00 ,q0 , γt+1 ) are not allowed in Π(t + 1, q , q). Thus,
n
o
2
3
2
αt+1,q
αt1 yt+1,γt+1
, αt2 yt+1,γt+1
.
00 ,q 0 ,q = max

21

1
yt+1,γt+1

αt1
αt1
αt2

1
yt+1,γt+1

2
yt+1,γt+1

αt2

2
yt+1,γt+1

3
γt,q
0 ,q

(a) Case 1a

(b) Case 1b

1
Figure 7: Subcases of 1. Combination of αt+1,q
00 ,q 0 ,q dashed, other forbidden paths are dotted. Solid arcs denote possible combinations to calculate
2
αt+1,q
00 ,q 0 ,q .
1
yt+1,γt+1

αt1
αt1
αt2

1
yt+1,γt+1

2
yt+1,γt+1

αt2

2
yt+1,γt+1

3
γt,q
0 ,q

(a) Case 2a

(b) Case 2b

1
Figure 8: Subcases of 2. Combination of αt+1,q
00 ,q 0 ,q dashed, other forbidden paths are dotted. Solid arcs denote possible combinations to calculate
2
αt+1,q
00 ,q 0 ,q .

1
1
2: ζt,q
00 ,q 0 = γt+1 . Thus, due to F, it is not allowed that consecutive arcs
read the same label at consecutive positions. The most likely path from
Π(t + 1, q 0 , q) through q 00 , q 0 and q combines either the most likely path
from Π(t, q 00 , q 0 ) with the second most likely label at position t + 1 or
the second most likely path from Π(t, q 00 , q 0 ) with the most likely label at
position t + 1:
n
o
1
2
1
αt,q
αt1 yt+1,γt+1
, αt2 yt+1,γt+1
00 ,q 0 ,q = max

1
1
a: ζt+1,q
00 ,q 0 ,q = γt+1 (dashed combination in Figure 8(a)). The only
1
restriction is not to read γt+1
such that the second most likely path
is simply
2
1
αt+1,q
.
00 ,q 0 ,q = αt yt+1,γ 2
t+1
1
2
b: ζt+1,q
00 ,q 0 ,q = γt+1 (dashed combination in Figure 8(b)). Hence, the
1
1
2
suffices (ζt,q00 ,q0 , γt+1
) and γt+1
are forbidden.
n
o
2
1
3
αt+1,q
αt2 yt+1,γt+1
, αt1 yt+1,γt+1
00 ,q 0 ,q = max

This completes the proof.

22

Proof of Theorem 7. Note, that the approximation is exact for arcs reading two
g q 0 , q, i) and cont(t, q 0 , q, i) maximize over
or less labels since in this case cont(t,
the same paths. Especially, NaC -transitions are always exact since they read
only one label.
Let π ∗ be the most likely feasible path with respect to the regular expression
r and let
0

cont(t, q , q, i) =

t
Y

yt0 ,πt∗0

t0 =1
∗
for i ∈ {1, 2}, i.e. πt∗ = πt−1
. Assume πt∗ ∈ Σ. Due to Assumption 1
∗
∗
∗
πt−2 , πt+1 6= πt .
j
∗
The likelihood of (π1∗ , . . . , πt−1
) is equal to αt−1,q
0 ,q for some j. j cannot be
2
∗
1
greater than 2 since otherwise πt−1 6∈ {γt−1,q0 ,q , γt−1,q
0 ,q } (see Figure 7(a)) and
∗
the substitution of πt−1
by ? would yield a feasible path with greater likelihood
due to condition 2. This contradicts to the assumption that π ∗ is maximizing
i
the likelihood of all feasible paths. Thus, we only need to compute αt,q
0 ,q for
i ≤ 2.
1
2
3
If πt∗ 6∈ {γt,q
0 ,q , γt,q 0 ,q , γt,q 0 ,q }, we get a feasible, more likely path by substi∗
tuting πt by ?. This new path collapses to the same word. Again, this is a
contradiction to the maximum likelihood of π ∗ . Thus, we only need to consider
the three most likely labels per arc.

References
[1] Gautier Bideault, Luc Mioulet, Clément Chatelain, and Thierry Paquet.
Spotting Handwritten Words and REGEX using a two stage BLSTM-HMM
architecture. In Document Recognition and Retrieval, 2015.
[2] Théodore Bluche, Hermann Ney, Jérôme Louradour, and Christopher Kermorvant. Framewise and CTC Training of Neural Networks for Handwriting Recognition. In International Conference on Document Analysis and
Recognition – ICDAR 2015, pages 81–85, 2015.
[3] Jan Daciuk, Stoyan Mihov, Bruce W Watson, and Richard E Watson.
Incremental construction of minimal acyclic finite-state automata. Computational linguistics, 26(1):3–16, 2000.
[4] Pierre Dupont, François Denis, and Yann Esposito. Links between probabilistic automata and hidden markov models: probability distributions,
learning models and induction algorithms. Pattern recognition, 38(9):1349–
1371, 2005.
[5] Jeffrey E.F. Friedl. Mastering Regular Expressions. O’Reilly, 2006.
[6] Alex Graves, Santiago Fernández, Faustino J. Gomez, and Jürgen Schmidhuber. Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks. In ICML, pages 369–376,
2006.

23

[7] Alex Graves and Navdeep Jaitly. Towards end-to-end speech recognition
with recurrent neural networks. In Proceedings of the 31st International
Conference on Machine Learning (ICML-14), pages 1764–1772, 2014.
[8] Alex Graves and Jürgen Schmidhuber. Offline handwriting recognition
with multidimensional recurrent neural networks. In Advances in neural
information processing systems, pages 545–552, 2009.
[9] Yousri Kessentini, Clément Chatelain, and Thierry Paquet. Word spotting
and regular expression detection in handwritten documents. In Document
Analysis and Recognition (ICDAR), 2013 12th International Conference
on, pages 516–520. IEEE, 2013.
[10] Anders Krogh et al. An introduction to hidden markov models for biological
sequences. New Comprehensive Biochemistry, 32:45–63, 1998.
[11] Gundram Leifert, Tobias Grüning, Tobias Strauß, and Roger Labahn. Citlab argus for historical data tables. 2014.
[12] Albert R Meyer and Michael J Fischer. Economy of description by automata, grammars, and formal systems. In Switching and Automata Theory, 1971., 12th Annual Symposium on, pages 188–191. IEEE, 1971.
[13] Mehryar Mohri, Fernando Pereira, and Michael Riley. Speech recognition
with weighted finite-state transducers. In Springer Handbook of Speech
Processing, pages 559–584. Springer, 2008.
[14] Bastien Moysset, Théodore Bluche, Maxime Knibbe, Mohamed Faouzi
Benzeghiba, Ronaldo Messina, Jérôme Louradour, and Christopher Kermorvant. The A2iA multi-lingual text recognition system at the second
Maurdor evaluation. In Frontiers in Handwriting Recognition (ICFHR),
2014 14th International Conference on, pages 297–302. IEEE, 2014.
[15] Hasim Sak, Andrew Senior, Kanishka Rao, Ozan Irsoy, Alex Graves,
Françoise Beaufays, and Johan Schalkwyk. Learning acoustic frame labeling for speech recognition with recurrent neural networks. In Acoustics,
Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on, pages 4280–4284. IEEE, 2015.
[16] Joan Andreu Sánchez, Verónica Romero, Alejandro H. Toselli, and Enrique Vidal. ICFHR2014 Competition on Handwritten Text Recognition
on tranScriptorium Datasets (HTRtS). In Proceedings of the International
Conference on Frontiers in Handwriting Recognition – ICFHR 2014, August 2014.
[17] Joan Andreu Sánchez, Alejandro H. Toselli, Verónica Romero, and Enrique
Vidal. ICDAR2015 Competition HTRtS: Handwritten Text Recognition on
the tranScriptorium Dataset. In Proceedings of the International Conference on Document Analysis and Recognition – ICDAR 2015, 2015.
[18] Tobias Strauß, Tobias Grüning, Gundram Leifert, and Roger Labahn. Citlab argus for historical handwritten documents. 2014.

24

[19] Ken Thompson. Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6):419–422, 1968.
[20] Stephen John Young, NH Russell, and JHS Thornton. Token passing: a
simple conceptual model for connected speech recognition systems. Cambridge University Engineering Department, 1989.

25

