Digital Signal Processing Reference
In-Depth Information
[Parizeau and Plamondon, 1995] [Singer and Tishby, 1994] [Schomaker,
1993] [Manke et al., 1994] and others that decompose the recognition
problems to some extent [Cunn et al., 1997] [Man and Poon, 1993]
[Fukushima and Imagawa, 1993] [Kadirkamanathan and Rayner, 1993].
In cursive handwriting and in speech recognition, HMMs are a popular
and high quality solution [Rabiner, 1989]. However, the current HMM
theory accepts only simple sequences. Our approach is fundamentally
different in how we treat the problem. In traditional divide and con-
quer schemes for ordered information, a single larger problem is treated
as a composition of more manageable subproblems. If this composition
is mapped onto a graph, most methods treat the composition of the
problem as a simple sequence. In contrast, we believe that the composi-
tion as a DAG is vital for a robust recognition. Finite State Transduc-
ers (FSTs) can accept these complex graph compositions [Mohri, 1997],
but are less applicable to general signal processing because the current
domain of FSTs is restricted to the discrete, finite-element languages.
In recognition problems, FSTs generally applied to grammar modeling,
word-lat tices and other high-level constructs.
2. ORDER, MAPPING AND DAGS
Order aids in finding mapping between sets. When we use an order
to compare sets, a data structure (such as a list, sequence or a DAG)
that enforces an order over a set of data leads to efficient methods for
determining a mapping.
Linear orders defined on two sets of data can be used to efficiently
establish mapping between elements of the two sets by 1) restricting the
set of possible mappings and 2)
allowing divide and conquer techniques
to
be
applied.
An
ordered
mapping
between sets
(see Figure 5.1)
is
defined below:
{
{
b
↔
y
a
x
(
a
<
b
) → (
x
<
y
)
↔
S
2
,
if
then
a
,
b
S
1
,
x, y
(5.1)
(
a
>
b
) → (
x
>
y
)
where
S
1
and
S
2
are the two ordered sets. This restriction drastically
reduces the total number of possible mappings between sets. As shown
in Figure 5.1c, if we are determining an ordered mapping, we can decom-
pose the ordered mapping problem into two smaller independent ordered
mapping problems by fixing a mapping between an element from each
set. This type of decomposition allows a divide and conquer techniques
to be applied.
These properties of linear order are also true for a
topological
order
that exists in a DAG, i.e., an order of nodes such that every directed
edge of the graph goes from a lower to higher ordered node [Cormen
Search WWH ::
Custom Search