DeepLearning
論理演算
NeuralNetwork
TensorFlow

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

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

1ビットのカウンタ

前の記事にカウンタの要件だけを提示しておいたので、最初にお読みいただきたい。次のように、入力($\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)に一致する。それに合わせて出力側の行順を反転して前記事の表と比較すると、出力側の第1列が入力側2ビットのANDになっていることがわかる。さらに、出力の第2列は入力のXORになっている。これを回路図(のようなもの。実際に使われる論理回路とは、動作の仕方が異なる)にしたのが以下である。回路記号は前の記事の表を参照していただきたい。

counter1-label.png

ANDとXORが並列になっていることが分かる。ところで、前の記事の表を見ると、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

これは、隠れ層を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を使った。

リスト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の流れを選択するというような、定まった論理構造が必要な状況が出てくる。これは、機械学習が必要な変数部分と、論理が定まった定数部分が混ざりあったハイブリッドなネットワークである。

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