Networks of Classical Conditioning Gates and Their Learning

We model classical conditioning as shown in Fig. 1. It is a two-state machine that switches between the states “YES” and “OR” based on the two input signals taking a binary value. When the state is “YES”, the gate operates as a logical YES gate, whose output is equal to the first input, as shown in Table 1. On the other hand, when the state is “OR”, the gate operates as a logical OR gate, whose output is equal to 1 if and only if at least one of the two inputs is equal to 1. The state changes when two types of training inputs are applied. When the state is “YES”, the state is changed to “OR” by entering the value $(1,1)$ several times in row. On the other hand, when the state is “OR”, the state is changed to “YES” by entering the value $(0,1)$ several times in row.

This model can be interpreted in terms of Pavlov’s dog experiment as follows. The state “YES” corresponds to responding only when the dog is being fed, while the state “OR” corresponds to responding when the dog is being fed or hears the bell. Then the input value $(1,1)$ is interpreted as the stimulus for acquisition, i.e., feeding with bell ringing, and $(0,1)$ is interpreted as the stimulus for extinction, i.e., bell ringing without feeding.

The model of the above classical conditioning gate is expressed as

where $x(t)\in\{{\rm YES},{\rm OR}\}$ is the state, $v(t)\in\{0,1\}$ and $w(t)\in\{0,1\}$ are the inputs, $y(t)\in\{0,1\}$ is the output, and $s\in\{1,2,\ldots\}$ is a period, called the unit training time. The state equation represents classical conditioning, while the output equation represents the resulting input-output relation at time $t$.

The following result presents a basic property of (10), which will be utilized for training a network of classical conditioning gates.

This shows that there exists an input value that sets an arbitrary value at the output while preserving the state value.

Now, we introduce a network of classical conditioning gates, as shown in Fig. 2. The network has a binary tree structure, where each gate, except for the leftmost gates, is connected to two other gates on the input side. The network has $m$ layers, indexed by $1,2,\ldots,m$ from the input side. The $i$-th layer has $2^{m-i}$ gates, and thus the network has $\sum_{i=1}^{m}2^{m-i}$ gates. We use $n_{i}$ and $n$ to denote these numbers, i.e., $n_{i}=2^{m-i}$ and $n=\sum_{i=1}^{m}2^{m-i}=\sum_{i=1}^{m}n_{i}$.

We introduce the following notation for the network. The network with $m$ layers is denoted by $\Sigma(m)$. The $j$-th gate from the top in the $i$-layer is called node $(i,j)$, and let $x_{ij}(t)\in\{{\rm YES},{\rm OR}\}$, $v_{ij}(t)\in\{0,1\}$, $w_{ij}(t)\in\{0,1\}$, and $y_{ij}(t)\in\{0,1\}$ be the state, first input, second input, and output of node $(i,j)$, respectively. The pair of $v_{ij}(t)$ and $w_{ij}(t)$ is often denoted by $u_{ij}(t)\in\{0,1\}^{2}$. We use $\bar{x}_{ij}(t)$ to represent the flipped value of $x_{ij}(t)$: $\bar{x}_{ij}(t)={\rm YES}$ for ${x_{ij}(t)}={\rm OR}$, while $\bar{x}_{ij}(t)={\rm OR}$ for ${x_{ij}(t)}={\rm YES}$.

Next, let us consider the collection of signals. We use ${\mathbf{N}}:=\{(1,1),(1,2),\ldots,$ $(m,1)\}$, which has $n$ elements, to represent the set of node indeces, and use ${\mathbf{N}}_{i}\subset{\mathbf{N}}$ to represent the set of node indeces in layer $i$. Let $X_{i}(t)\in\{{\rm YES},{\rm OR}\}^{n_{i}}$, $U_{i}(t)\in\prod_{j=1}^{n_{i}}(\{0,1\}\times\{0,1\})$, and $Y_{i}(t)\in\{0,1\}^{n_{i}}$ be the collective state, input, and output of the $i$-th layer. Let also $X(t):=(X_{1}(t),X_{2}(t),\ldots,X_{m}(t))\in\{{\rm YES},{\rm OR}\}^{n_{1}}\times\{{\rm YES},{\rm OR}\}^{n_{2}}\times\cdots\times\{{\rm YES},{\rm OR}\}^{n_{m}}=\{{\rm YES},{\rm OR}\}^{n}$. According to this notation, the state, input, and output of the network $\Sigma(m)$ are denoted by $X(t)$, $U_{1}(t)$, and $Y_{m}(t)$, respectively. Note that $Y_{m}(t)=y_{m1}(t)$.

Fig. 3 shows an example for $m=3$. In this case, we have ${\mathbf{N}}=\{(1,1),(1,2),(1,3),$
$(1,4),(2,1),(2,2),(3,1)\}$, $X_{1}(t)=(x_{11}(t),x_{12}(t),x_{13}(t),x_{14}(t))$, $X_{2}(t)=(x_{21}(t),$ $x_{22}(t))$, $X_{3}(t)=x_{31}(t)$, $U_{1}(t)=(u_{11}(t),u_{12}(t),u_{13}(t),u_{14}(t))$, $U_{2}(t)=(u_{21}(t),u_{22}(t))$, $U_{3}(t)=u_{31}(t)$, $Y_{1}(t)=(y_{11}(t),y_{12}(t),y_{13}(t),y_{14}(t))$, $Y_{2}(t)=(y_{21}(t),y_{22}(t))$, and $Y_{3}(t)=y_{31}(t)$.

Since a classical conditioning gate operates as either logical YES or OR, the possible input-output relation of $\Sigma(m)$ is limited to logical OR of some of the inputs of $\Sigma(m)$. Moreover, the output $y_{m}(t)$ always depends on the input $v_{11}(t)$ because $v_{11}(t)$ propagates through nodes $(i,1)$ ($i=1,2,\ldots,m$) operating as logical YES or OR. For example, $y_{3}(0)=v_{11}(0)\vee v_{12}(0)$ for the network $\Sigma(3)$ in Fig. 3. This fact is formalized as follows.

The following result shows a structural property that indicates which inputs affect node $(i,j)$.

Lemma 3 is illustrated as follows. Consider the network $\Sigma(3)$ in Fig. 3 and node $(2,1)$. Then $U(t)$ is divided into $4$ blocks (where $2n_{2}=2^{2}$): $[U(t)]_{1}=(v_{11}(t),w_{11}(t))$, $[U(t)]_{2}=(v_{12}(t),w_{12}(t))$, $[U(t)]_{3}=(v_{13}(t),w_{13}(t))$, and $[U(t)]_{4}=(v_{14}(t),w_{14}(t))$. From Lemma 3, we have $v_{21}(t)=f_{1}(U_{[1]}(t))$ and $w_{21}(t)=f_{2}(U_{[2]}(t))$ for some $f_{1}:\{0,1\}^{2^{i-1}}\to\{0,1\}$ and $f_{2}:\{0,1\}^{2^{i-1}}\to\{0,1\}$. This is consistent with the interdependence between signals in Fig. 3.

Let us provide a key principle, called the flipping principle, for solving Problem 1.

The following is a preliminary result to derive the flipping principle.

Lemma 4 implies that there exists an input value for $\Sigma(m)$ that sets an arbitrary value at the output of $\Sigma(m)$ while preserving the state value. Note from this lemma that the state of $\Sigma(m)$ does not change by an input sequence that takes $(0,0,\ldots,0)$ and $(1,0,\ldots,0)$ at each time.

From Lemma 4, we obtain the flipping principle for learning of $\Sigma(m)$.

Theorem 1 implies that we can flip the state of any node while preserving the state of the other nodes in the layer to which the node to be flipped belongs and its upstream layers.

Theorem 1 implies that we can steer the state of the network $\Sigma(m)$ from any value to any value by flipping the state of each node one by one from the upstream node. Based on this idea, we obtain the following algorithm to solve Problem 1.

In the algorithm, $k$ is a variable to count the number of nodes whose state is flipped, and $\hat{\mathbf{N}}$ is the list of the nodes for which the algorithm has never checked whether their state needs to be flipped or not. In Step 1, $X^{*}$ is defined from (11) and $k$ and $\hat{\mathbf{N}}$ are initialized. Step 2 picks a node $(i,j)$ from the list $\hat{\mathbf{N}}$. Step 3 checks whether the state of node $(i,j)$ has to be flipped or not; if it has to be flipped, the state is flipped by applying the training input sequence specified in Theorem 1. Note here that $s$ steps of actual time elapsed while applying the input sequence to $\Sigma(m)$. In Step 4, node $(i,j)$ is removed from the list $\hat{\mathbf{N}}$. In addition, the terminate condition is checked; if $\hat{\mathbf{N}}$ is empty, the algorithm terminates; otherwise, the above procedure is performed for a remaining node in the list $\hat{\mathbf{N}}$.

For the algorithm, we obtain the following result.