CC-Lerner als verknüpfter Automat (Lineare Zeit)

(Die englischen Abschnitte im folgenden Text werden später durch deutsche Texte ersetzt werden).

Wir machen hier die Annahme, dass sich jedes Neuron als Automat auffassen lässt und dass ein Netzwerk von Neuronen dann einem Netzwerk von Automaten entspricht.

Def.: A Network of Connected Automata (NCA) is given as a structure of the following kind:

\begin{displaymath}\langle A_{1}, \cdots, A_{k}, {\cal C}\rangle \end{displaymath}

with $A_{i}$ as a participating automaton and $\cal C$ as connection relation.

Def.: An Execution of a Network of Connected Automata ($\sigma^{+}$) is given as a sequence a sequence of configurations $\langle \sigma^{+}_{0},\sigma^{+}_{1}, \cdots, \sigma^{+}_{n}\rangle$ where every element $\sigma^{+}_{i}$ consists of two parts: a control part and a connection part (see above).

Als Automatentyp wird hier standardmässig der Typ Finite Transducer(Endlicher Übersetzer) vorausgesetzt (vgl. Bild 4.20). Dabei handelt es sich um einen generaliserten Mealy-Automaten (siehe auch Skript http://www.uffmm.org/science-technology/single/themes/computer-science/personal-sites/doeben-henisch/FM/
SESSIONS/THEORY/fsv/index.html):

Figure 4.20: Finite transducer (generalized mealy)
\includegraphics[width=2.5in]{automaton_finite_transducer.eps}

A finite transducer has an input tape and an output tape. Every neuron of the McCulloch-Pitts type can be considered as such a finite transducer. All the input neurons together are representing the actual input and the output represents the outgoing axon. A neuron can then be considered as an automaton representing some function $f$ with $f(input) = output$, where the $input$ as well as the $output$ will be considered as words from the sets $\Sigma^{*}$ (words about the input alphabet $\Sigma$) and $\Xi^{*}$ (words about the output alphabet $\Xi$). We will make the assumption that the output is given at point in time t+1 when the input is given to the automaton at point in time t: output$_{t+1}$ = f(input)$_{t}$. Thus the output at point in time t+1 can be redirected as a new input at time t+1 (cf. figure 4.21).

Figure 4.21: Finite transducer with redirection of output
\includegraphics[width=2.5in]{automaton_finite_transducer_redirected.eps}

In the next step we consider the cooperation of two such automata. The output of automata A can be redirected -by the environment E- to the input of the automaton A itself but also to the input of the automaton B, and vice versa. One has only to assume that the input and the output tapes are arranged in sections; one section per transition and every section is subdivided into subsections thus that every participating automaton has one subsection of point in time t for input as well as for output (see figure 4.20). Because the input is assumed to be a string we can assume that the output of different automata can be inserted in one of these input strings constituting different parts $input_{A} = output_{A}\mid output_{B}\mid \cdots \mid output_{X}$.

To formalize this we take two automata $\cal A$ and $\cal B$ with the structure

\begin{displaymath}\langle Q, I, F, \Sigma, \Xi, \Delta, \rangle\end{displaymath}

with $\Delta \subseteq Q \times \Sigma^{*} \times Q \times \Xi^{*}$. Thus the output of a finite transducer is a string $\xi \in \Xi^{*}$. Let $out_{A}$ design the output string of automaton $\cal A$ at a certain point of time. Similar let $in_{A}$ design the input of automaton $\cal A$ at a certain point of time. $OUT$ shall be the union of the outputs $out_{i}$ of all automata at a certain point in time t as well as $IN$ shall be the union of the inputs $in_{j}$ of all automata at a certain point in time t. Then we assume a connection (CON) between the participating automata as

\begin{displaymath}CON \subseteq out_{i} \times 2^{IN}\end{displaymath}

for all outputs of all automata (cf. general structure by figure 4.20).

Figure 4.22: Two finite transducers with redirection of output
\includegraphics[width=2.5in]{automaton_finite_transducer_redirected_two.eps}

Let us consider a simple example consisting of four neurons {A, B, C, D} from the McCulloch-Pitts type (cf. figure 4.19).

In the example with the four neurons {A, ..., D} we have neuron A receiving an input from the environment named $S1$. Neuron B is receiving an input $S1$ from the environment, an input $S2$ , and an input from another neuron D. Neuron C is receiving inputs from the neurons A and B, and neuron D is receiving inputs from itself as well as from neuron B and some source $F1$.

Figure 4.23: Connected automata inputs illustrated by four neurons
\includegraphics[width=3.5in]{example_mcps_a-d_inputs.eps}

Let us consider an automaton $\cal A$ for a moment as a function $f_{\cal A}(in)= out $. The execution of connected automata can then be formalized as a sequence $\sigma^{+}$ of configurations $\langle \sigma^{+}_{0},\sigma^{+}_{1}, \cdots, \sigma^{+}_{n}\rangle$ where every element $\sigma^{+}_{i}$ consists of two parts: a control part and a connection part.

The control part is the sequence of simple configuration elements like $\langle (f_{\cal A}, in_{\cal A}), (f_{\cal B}, in_{\cal B}), \cdots \rangle$ or extended configuration elements like $\langle \langle f_{\cal A}, in_{\cal A}, out_{\cal A}\rangle, \langle f_{\cal B}, in_{\cal B}, out_{\cal B}\rangle, \cdots \rangle$. This means that at this point in time every participating automaton has some actual tape input $\in$ as argument for the function $f_{\cal A}(in)$ and -in the extended version- has some actual tape output $out$. By the definition of the function one can compute the output of the function. New is the connection part as $\langle (\xi_{\cal A},\langle in_{\cal A}, in_{\cal B}, \cdots \rangle), (\xi_{\cal B},\langle in_{\cal A}, in_{\cal B}, \cdots \rangle) \rangle$. Every output is here mapped onto the input of some destination. With $n$-many participating automata would this amount to $n^{2}$ many input fields. But in most practical cases is the mean number of output connections $m$ much much smaller than the number $n$ of participating automata. Let us look to the example of the four interconnected neurons $A, \cdots, D$ (zur Definition der Funktion der einzelnen Automaten siehe die Tabellen weiter oben):

With these functions one can construct a possible execution as follows:

  1. Control: $\langle A(0), B(0,0,0), C(0,0), D(0,0,1) \rangle$
  2. Connection: $\langle (out_{A}, \{in_{C}\}), (out_{B}, \{ in_{C}, in_{D}\}), (out_{D}, \{ in_{D}, in_{B}\}),\rangle$
  3. Control: $\langle A(1), B(1,0,0), C(1,0), D(0,0,1) \rangle$
  4. Connection: $A:1 \rightarrow C$, $B:0 \rightarrow C, D$, $D:0 \rightarrow C,D$
  5. Control: $\langle A(0), B(0,1,0), C(1,0), D(0,0,1) \rangle$
  6. Connection: $A:0 \rightarrow C$, $B:0 \rightarrow C, D$, $D:0 \rightarrow C,D$
  7. Control: $\langle A(1), B(1,1,0), C(0,0), D(0,0,1) \rangle$
  8. Connection: $A:1 \rightarrow C$, $B:1 \rightarrow C, D$, $D:0 \rightarrow C,D$
  9. Control: $\langle A(0), B(0,0,1), C(1,1), D(1,1,1) \rangle$
  10. Connection: $A:0 \rightarrow C$, $B:0 \rightarrow C, D$, $D:1 \rightarrow C,D$
  11. Control: $\langle A(0), B(0,0,1), C(0,0), D(1,0,1) \rangle$
  12. Connection: $A:0 \rightarrow C$, $B:0 \rightarrow C, D$, $D:1 \rightarrow C,D$
  13. Control: $\langle A(0), B(0,1,1), C(0,0), D(1,1,1) \rangle$
  14. Connection: $A:0 \rightarrow C$, $B:1 \rightarrow C, D$, $D:1 \rightarrow C,D$
  15. Control: $\langle A(0), B(0,0,1), C(0,1), D(1,1,1) \rangle$
  16. Connection: $\cdots$
  17. $\cdots$

This execution shows some interesting dynamics in the behavior of these four neurons. There is a change in the observable behavior of this small network which happens after the occurence of S1 and S2 synchronously being '1':

S1 S2 $f_{A} \oplus f_{B} \oplus f_{C} \oplus f_{D}$
1 1 1
1 0 1
0 1 0
0 0 0
1 1 1
1 0 1
0 1 1
0 0 0

Dieses Beispiel soll nun weiter analysiert und verallgemeinert werden.

Gerd Doeben-Henisch 2010-12-16