Neural Networkでカウンタを実装する

 [Neural Networkで論理演算を実装する](https://qiita.com/cnloni/items/94f7d03bc8fe7dbe6f17)という記事で、基本的な論理演算を線形変換とReLU関数で表現した。この記事では、それを用いて、カウンタを実装する。実装と言っても、機械学習をするのではなく、頭で考えるだけである。これが、実際に役に立つかどうかは「？」である。しかし、ニューラルネットワークを機械学習を行う部分（変数テンソル）とあらかじめ確定した部分（定数テンソル）に分解するという考え方は、少なくとも私のプロジェクトでは役に立っている。


### 1ビットのカウンタ
前の記事に[カウンタの要件](https://qiita.com/cnloni/items/94f7d03bc8fe7dbe6f17#%E3%82%AB%E3%82%A6%E3%83%B3%E3%82%BF)だけを提示しておいたので、最初にお読みいただきたい。次のように、入力（$\boldsymbol{x}\_{0}$）として信号用1ビット（第1列）とカウンタ用1ビット（第2列）を持ち、出力（$\boldsymbol{x}\_{N-1}$）として桁上り用1ビット（第1列）とカウンタ用1ビット（第2列）を持つ。

$$ \boldsymbol{x}\_{0} = \left( \begin{array}{cc} 0 & 0 \\\ 0 & 1 \\\ 1 & 0 \\\ 1 & 1 \end{array} \right), \quad \boldsymbol{x}\_{N-1} = \left( \begin{array}{cc} 0 & 0 \\\ 0 & 1 \\\ 0 & 1 \\\ 1 & 0 \end{array} \right) \tag{1}$$

つまり、入力信号が0のときはカウンタは変化せず、入力信号が1のときはカウンタが増加する（カウンタが既に1のときは、0になる桁上りビットがセットされる）。

このカウンタは、かなり簡単な形をしている。入力の行の順番を反転すると、前の記事の式(1)に一致する。それに合わせて出力側の行順を反転して[前記事の表](https://qiita.com/cnloni/items/94f7d03bc8fe7dbe6f17#%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97%E3%81%AE%E8%A1%A8)と比較すると、出力側の第1列が入力側2ビットのANDになっていることがわかる。さらに、出力の第2列は入力のXORになっている。これを回路図（のようなもの。実際に使われる論理回路とは、動作の仕方が異なる）にしたのが以下である。回路記号は[前の記事の表](https://qiita.com/cnloni/items/94f7d03bc8fe7dbe6f17#%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97%E3%81%AE%E8%A1%A8)を参照していただきたい。

![counter1-label.png](https://qiita-image-store.s3.amazonaws.com/0/52659/daf87240-14a4-6b27-08b8-203a2438f195.png)

ANDとXORが並列になっていることが分かる。ところで、[前の記事の表](https://qiita.com/cnloni/items/94f7d03bc8fe7dbe6f17#%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97%E3%81%AE%E8%A1%A8)を見ると、ANDは2層で実現でき、XORは3層が必要なことが分かる。しかし、ANDの2層目には活性化が必要であるから、ANDには恒等変換の3層目があると考えれば、XORと同じネットワーク構造であるとすることもできる。つまり、

$$W\_{1}\^{AND} = \left( \begin{array}{cc} 1 & 0 \\\ 1 & 0 \\\ -1 & 1 \end{array} \right), \quad W\_{2}\^{AND} = \left( \begin{array}{cc} 1 & 0 \\\ 0 & 1 \end{array} \right)$$

$$W\_{1}\^{XOR} = \left( \begin{array}{ccc} 1 & -1 & 0 \\\ -1 & 1 & 0 \\\ 0 & 0 & 1 \end{array} \right), \quad W\_{2}\^{AND} = \left( \begin{array}{c} 1 & 0 \\\ 1 & 0 \\\ 0 & 1 \end{array} \right)$$

である。これを並列化するのは、少し煩雑である。まず$W\_1$だが、ANDとXORの双方から最下列（最も左の列）を取り除いたもの（アフィン変換のための定数列であるから）を横に並べ、その後に再び定数列を付加する。つまり、

$$W\_{1} = \left( \begin{array}{c} 1 \\\ 1 \\\ -1 \end{array} \right) \oplus \left( \begin{array}{cc} 1 & -1 \\\ -1 & 1 \\\ 0 & 0 \end{array} \right) \oplus \left( \begin{array}{c} 0 \\\ 0 \\\ 1 \end{array} \right) = \left( \begin{array}{cccc} 1 & 1 & -1 & 0\\\ 1 & -1 & 1 & 0\\\ -1 & 0 & 0 & 1\end{array} \right) \tag{2}$$

とする。この$W\_1$のうち、第1列はAND、第2列と第3列はXORからきたものである。$W\_2$は、各々から最下行（バイアス成分）を取り除いたものを__斜め下方向に__重ねて、最後にバイアス成分を戻して

$$W\_{2} = \left( \begin{array}{ccc} 1 & 0 & 0 \\\ 0 & 1 & 0\\\ 0 & 1 & 0\\\ 0 & 0 & 1 \end{array} \right) \tag{3}$$

となる。つまり、1ビットのカウンタは3層で実現できるのである。これが正しいことを入力$\boldsymbol{x}\_0$に作用させて確かめる。

$$\begin{align}
\tilde{\boldsymbol{x}}\_{2} &= ReLU(\tilde{\boldsymbol{x}}\_{0} W\_{1}) W\_{2} \\\ \\\
&= ReLU(\left( \begin{array}{ccc} 0 & 0 & 1\\\ 0 & 1 & 1\\\ 1 & 0 & 1\\\ 1 & 1 & 1\end{array}\right) \left( \begin{array}{cccc} 1 & 1 & -1 & 0 \\\ 1 & -1 & 1 & 0 \\\ -1 & 0 & 0 & 1 \end{array} \right)) W\_{2} \\\ \\\
&= ReLU(\left( \begin{array}{cccc} -1 & 0 & 0 & 1 \\\ 0 & -1 & 1 & 1 \\\ 0 & 1 & -1 & 1 \\\ 1 & 0 & 0 & 1 \end{array} \right)) W\_{2} \\\ \\\
&= \left( \begin{array}{cccc} 0 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 1 \\\ 0 & 1 & 0 & 1 \\\ 1 & 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\\ 0 & 1 & 0\\\ 0 & 1 & 0\\\ 0 & 0 & 1 \end{array} \right) \\\ \\\
&= \left( \begin{array}{ccc} 0 & 0 & 1 \\\ 0 & 1 & 1\\\ 0 & 1 & 1\\\ 1 & 0 & 1 \end{array} \right)
\end{align}$$

ここで、$\tilde{\boldsymbol{x}}\_{i}$はアフィン変換のために$\boldsymbol{x}\_{i}$を拡大したベクトルであり、要素が全て1である列を最後尾に加えたものである。よって、最終結果から最後尾に加えた列を取り除くと

$$\boldsymbol{x}\_{2} = \left( \begin{array}{cc} 0 & 0\\\ 0 & 1\\\ 0 & 1\\\ 1 & 0\end{array} \right)$$

が得られて(1)式に一致する（3層なので$N=3$である）。


### 2ビットのカウンタ
1ビットのカウンタを拡張して、2ビットのカウンタを作る。話は簡単である。1ビットカウンタを2個並べて、1個目の桁上り出力を2個目の信号入力にするだけである。回路図にすると下図になる。

![counter2-label.png](https://qiita-image-store.s3.amazonaws.com/0/52659/5c9f7a95-0f51-1c53-d1e8-2040664ef2cc.png)

これは、隠れ層を3層持つ5層のネットワークである。

$$\tilde{\boldsymbol{x}}\_{4} = ReLU(ReLU(\tilde{\boldsymbol{x}}\_{0} W\_{1}\^{(1)}) W\_{2}\^{(1)} W\_{1}\^{(2)}) W\_{2}\^{(2)} \tag{4}$$

ここで、$W\_{i}\^{(k)}$はk番目の1ビットカウンタのアフィン変換行列を表す。1ビットカウンタの場合、意味のある入力が信号とカウンタを併せて2ビットだったが、今度はカウンタが2ビットになるので計3ビットになる。このため、1ビット目カウンタである式(2)の$W\_{1}$は、3行目と4列目を挿入して$4 \times 5$行列になる。

$$W\_{1}\^{(1)} = \left( \begin{array}{ccccc} 1 & 1 & -1 & 0 & 0\\\ 1 & -1 & 1 & 0 & 0\\\ 0 & 0 & 0 & 1 & 0\\\ -1 & 0 & 0 & 0 & 1\end{array} \right) \tag{5}$$

同様に、式(3)の$W\_{2}$は、4行目と3列目を挿入して$ 5 \times 4$行列になる。

$$W\_{2}\^{(1)} = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0\\\ 0 & 1 & 0 & 0\\\ 0 & 0 & 1 & 0\\\ 0 & 0 & 0 & 1 \end{array} \right) \tag{6}$$

2ビット目のカウンタは、行を挿入する位置が異なり、各々次式で与えられる。

$$W\_{1}\^{(2)} = \left( \begin{array}{ccccc} 1 & 0 & 1 & -1 & 0\\\ 0 & 1 & 0 & 0 & 0\\\ 1 & 0 & -1 & 1 & 0\\\ -1 & 0 & 0 & 0 & 1\end{array} \right) \tag{7}$$

$$W\_{2}\^{(2)} = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0\\\ 0 & 0 & 1 & 0\\\ 0 & 0 & 1 & 0\\\ 0 & 0 & 0 & 1 \end{array} \right) \tag{8}$$

ところで、式(4)に注目して頂きたい。$W\_{2}\^{(1)} W\_{1}\^{(2)}$という部分がある。これは2つのアフィン変換の間で、活性化関数（非線形変換）が作用していないことを示す。1ビットカウンタの出力層に活性化関数が無いからである。この場合には、2つの行列の積を予め計算することができる。

$$W\_{1R}\^{(2)} \equiv W\_{2}\^{(1)} W\_{1}\^{(2)}
= \left( \begin{array}{ccccc} 1 & 0 & 1 & -1 & 0\\\ 0 & 1 & 0 & 0 & 0\\\ 0 & 1 & 0 & 0 & 0\\\ 1 & 0 & -1 & 1 & 0\\\ -1 & 0 & 0 & 0 & 1\end{array} \right) \tag{9}$$

結局

$$\tilde{\boldsymbol{x}}\_{4} \longrightarrow \tilde{\boldsymbol{x}}\_{3} = ReLU(ReLU(\tilde{\boldsymbol{x}}\_{0} W\_{1}\^{(1)}) W\_{1R}\^{(2)}) W\_{2}\^{(2)} \tag{10}$$

が得られる。3層の隠れ層を持つ5層のネットワークが、2層の隠れ層を持つ4層のネットワークに縮約されたのである。


### 4ビットのカウンタ
これまでの結果を使って、4ビットのカウンタを作成する。徒に行列のサイズが大きくなるだけなので詳細は省くが、4層の隠れ層を持つ計6層のネットワークである。それをTensorFlowで実装した（リスト1）。特にTensorFlowを使う必要はなく、NumPyだけを使う方が簡単なのだが、あえてTensoFlowを使った。

```py3:リスト1
import tensorflow as tf
import numpy as np
from builtins import staticmethod

#
# 1ビットカウンタ
#
class BitCounterProperty:
    def __init__(self, W1, b1, W2):
        # 線形変換行列とバイアスベクトルから定数Tensorを作成する
        self.W1 = tf.constant(W1, dtype=np.float32)
        self.b1 = tf.constant(b1, dtype=np.float32)
        self.W2 = tf.constant(W2, dtype=np.float32)

    # 前の層のTensor（layer）に、1ビットカウンタの演算を施す
    def operate(self, layer):
        layer = tf.nn.relu(tf.matmul(layer, self.W1) + self.b1)
        if self.W2 is not None:
            # 縮約されていない場合
            return tf.matmul(layer, self.W2)
        else:
            # 縮約されていた場合、W2がNoneである
            return layer
       
    # aのW2とbのW1の積を、新たにbのW1として縮約する
    @staticmethod
    def shrink(a, b):
        b.W1 = tf.matmul(a.W2, b.W1)
        a.W2 = None
    

#
# カウンタ（直列に並んだ1ビットカウンタ）
# nbits: カウンタのサイズ（ビット数）
#
class Counter:
    def __init__(self, nbits):
        # カウンタのビット数
        self.nbits = nbits

        # counter[0] 信号/桁上り用のビット
        # counter[1:nbits] カウンタの現在の値
        self.counter = np.zeros([self.nbits + 1, ], dtype=np.float32)
        
        # 格段の変換Tensorを格納する
        self.bitCounter = []
        
        # グラフ（=ネットワーク全体を表現する）
        self.g = tf.Graph()

        # tf.Sessionをあらかじめ作成しておく
        self.sess = tf.Session(graph=self.g)

        # グラフには、変換Tensorをあらかじめ登録しておく
        with self.g.as_default():
            # 入力
            self.x = tf.placeholder(tf.float32, shape=(None, self.nbits + 1))

            # 入力に対する教師データを格納する。今回は使わない
            self.y_ = tf.placeholder(tf.float32, shape=(None, self.nbits + 1))

            # 縮約する前のTensorを格納する
            for stage in range(self.nbits):
                self.bitCounter.append(self.createBitCounter(stage))

            # 変換Tensorを縮約する
            # W_2[stage-1]とW_1[stage]の積を、新たなW_1[stage]とする
            for stage in range(1, self.nbits):
                BitCounterProperty.shrink(
                    self.bitCounter[stage-1], self.bitCounter[stage])

            # 1ビットカウンタをnbits個、直列につないでグラフに登録する
            layer = self.x
            for stage in range(self.nbits):
                layer = self.bitCounter[stage].operate(layer)

            # 最後段を出力に
            self.y = layer

        self.g.finalize()

    # 線形変換とバイアスを計算する。W2に対するバイアスは無い
    def createBitCounter(self, k):
        if k < 0 or k >= self.nbits:
            return None
        m = self.nbits
    
        W1 = np.zeros([m+1, m+2], dtype=np.float32)
        for i in range(k+1):
            W1[i, i] = 1
        for i in range(k+2, m+1):
            W1[i, i+1] = 1
        W1[0, k+1] = W1[k+1, 0] = W1[k+1, k+2] = 1
        W1[0, k+2] = W1[k+1, k+1] = -1
        
        b1 = np.zeros([m+2, ], dtype=np.float32)
        b1[0] = -1

        W2 = np.zeros([m+2, m+1])
        for i in range(k+2):
            W2[i, i] = 1
        for i in range(k+1, m+1):
            W2[i+1, i] = 1

        return BitCounterProperty(W1, b1, W2)

    # カウントする
    def increment(self):
        self.counter[0] = 1
        feed_dict = {self.x: [self.counter]}
        ret = self.sess.run(self.y, feed_dict=feed_dict)
        self.counter = ret[0]

    def getCounter(self):
        return np.delete(self.counter, 0)

# 4ビットのカウンタ
nbits = 4
c = Counter(nbits)
print(c.getCounter())
for i in range(2**nbits):
    c.increment()
    print(c.getCounter())
```

なお、リスト1で使っているW1やW2は、アフィン変換ではなく、通常の線形変換である。プログラム実装の場合は、TensorFlowの習慣に従ってバイアスをb1として取り出している。上記の実行結果は以下になる。左側が下位ビット、右側が上位ビットである。

```
[ 0.  0.  0.  0.]
[ 1.  0.  0.  0.]
[ 0.  1.  0.  0.]
[ 1.  1.  0.  0.]
[ 0.  0.  1.  0.]
[ 1.  0.  1.  0.]
[ 0.  1.  1.  0.]
[ 1.  1.  1.  0.]
[ 0.  0.  0.  1.]
[ 1.  0.  0.  1.]
[ 0.  1.  0.  1.]
[ 1.  1.  0.  1.]
[ 0.  0.  1.  1.]
[ 1.  0.  1.  1.]
[ 0.  1.  1.  1.]
[ 1.  1.  1.  1.]
[ 0.  0.  0.  0.]
```

### 最後に
カウンタをニューラルネットワークとして実装しても、実用的な意味はない。

だからといって、何の意味もないわけではない。何らかの目的のためにニューラルネットワークをデザインするときには、必ず設計者の判断が必要である。各層のサイズをどうするか、活性化関数は何にするか、どこに畳み込みを入れるか...。それを設計する際にはデータの流れを司る論理を想定しなければならない。

そんなとき、Aが成立してBが成立したらCの流れを選択し、そうでないならDの流れを選択するというような、定まった論理構造が必要な状況が出てくる。これは、機械学習が必要な変数部分と、論理が定まった定数部分が混ざりあったハイブリッドなネットワークである。

このようなハイブリットなニューラルネットワークを考えるとき、ここで示したような、一見つまらない演習が役立つのではないだろうか。良い例があれば、実例を示して行きたい。