Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした