Digital Signal Processing Reference
In-Depth Information
When stack filters are viewed as Boolean networks, the root signals are sim-
ply the attractors with cycle length equal to 1. Similarly, periodic behavior
of some stack filters is due to the attractors with cycle length greater than 1.
Root signals represent the “pass-band” characteristics of a filter, much like the
frequencies passed by a linear filter, and have been studied extensively for dif-
ferent types of filters, such as median filters, stack filters, and morphological
filters.
34
,
35
,
38
-
41
Root signals also represent a type of memory of a filter. These ideas were
developed in a series of papers by Yu and Coyle
42
,
43
on the
associative memory
of stack filters, where the set of root signals represents the filter's associative
memory. This, of course, is closely related to the associative memory of neural
networks. Indeed, because any positive Boolean function can be implemented
as a cascade of so-called threshold logic gates,
44
a stack filter can be viewed as
a neural network.
45
In fact, the monotone property of the Boolean functions
ensures that each neuron makes the best possible decision regarding whether
or not the input signal is greater than a given level, subject to consistency with
the decision of other neurons in the network.
45
Boolean networks are essentially deterministic finite-state machines or au-
tomata without inputs. The connection between stack filters and automata
has been explored for determining the statistical behavior of recursive me-
dian filters
46
,
47
and stack filters.
48
,
49
Root signals of stack filters were also
studied by using deterministic finite automata.
50
It was shown that the set of
root signals for a particular stack filter constitutes a regular language, and a
simple procedure for testing whether root signals of one stack filter are also
root signals of another filter was developed, making it possible to test whether
the root signal sets of two different stack filters are equivalent.
Finally, Boolean networks also represent an abstract model of computation,
by transforming a finite configuration (input) into another configuration (out-
put). For example, the partitioning of the state space into attractors with their
respective basins of attraction is a form of classification. In Reference 42, stack
filters, as simple cases of Boolean networks, were also considered to be a type
of classifiers. Similar work showed that cellular automata, which are also
special cases of Boolean networks, can process information
51
and are able to
perform computations, such as density classification.
52
,
53
13.3.2
Inference of Networks
To make progress in understanding the genetic regulation in specific organ-
isms and develop tools for rational therapeutic intervention in diseases such
as cancer, it is necessary to be able to identify the networks from real experi-
mental data. Much recent work on Boolean networks has focused on identi-
fying the network structure from gene expression data.
54
-
63
At the same time,
a large body of related work in computational learning theory has addressed
very similar problems, namely, learning or inferring Boolean functions from
examples of their input-output behavior. A major focus in this field has been
Search WWH ::
Custom Search