Python
DeepLearning
Brainf*ck
TensorFlow

はじめに

tf.png

TensorFlowはニューラルネットやディープラーニングのためのライブラリということばかりが取り上げられがちですが、グラフを構築することで一連の計算処理を実現するというデータフロープログラミング(DFP)の側面も持ち合わせています。

TensorFlowのグラフはif文やwhile文と同じようなAPIを持ち合わせているので、一般的なプログラミング言語と同等の表現力を持っています。つまり、C言語やPythonで書けるソートや探索といったアルゴリズムは、TensorFlowのグラフでも書けるわけです。

今回、TensorFlowによるデータフロープログラミングで、FizzBuzz・バブルソート・クイックソート・2分探索・Brainf*ckなどのアルゴリズムやEso Langを実装してみたので、ちょっとしたTIPSともにTensorFlowの普段と違った面白さを紹介してみたいと思います。

実装したコードは以下のレポジトリに公開しています。他アルゴリズムのコードもあるので興味がある方はぜひご覧ください。なお、TensorFlowのバージョンは、1.2.0以降に対応しています。1.0と1.1では動かないです。

FizzBuzz

まずは、TensorFlowのグラフだけでFizz Buzzを書いてみましょう。

from __future__ import print_function
import tensorflow as tf
class FizzBuzz():
    def __init__(self, length=30):
        self.length = length
        self.array = tf.Variable([str(i) for i in range(1, length+1)], dtype=tf.string, trainable=False)
        self.graph = tf.while_loop(self.cond, self.body, [1, self.array],
                            shape_invariants=[tf.TensorShape([]), tf.TensorShape(self.length)],
                            back_prop=False)
    def run(self):
        with tf.Session() as sess:
            tf.global_variables_initializer().run()
            return sess.run(self.graph)
    def cond(self, i, _):
        return (tf.less(i, self.length+1))
    def body(self, i, _):
        r = tf.cond(
            tf.logical_and( # tf.equal(tf.mod(i, 15), 0)
                tf.equal(tf.mod(i, 3), 0),
                tf.equal(tf.mod(i, 5), 0)),
                lambda: tf.assign(self.array[i - 1], 'FizzBuzz'),
                lambda: tf.cond(tf.equal(tf.mod(i, 3), 0),
                        lambda: tf.assign(self.array[i - 1], 'Fizz'),
                        lambda: tf.cond(tf.equal(tf.mod(i, 5), 0),
                                lambda: tf.assign(self.array[i - 1], 'Buzz'),
                                lambda: self.array
                )
            )
        )
        return (tf.add(i, 1), r)

if __name__ == '__main__':
    fizzbuzz = FizzBuzz(length=50)
    ix, array = fizzbuzz.run()
    print(array)

実行結果は以下のとおりです。ちゃんとFizzBuzzできていますね。

['1' '2' 'Fizz' '4' 'Buzz' 'Fizz' '7' '8' 'Fizz' 'Buzz' '11' 'Fizz' '13'
 '14' 'FizzBuzz' '16' '17' 'Fizz' '19' 'Buzz' 'Fizz' '22' '23' 'Fizz'
 'Buzz' '26' 'Fizz' '28' '29' 'FizzBuzz' '31' '32' 'Fizz' '34' 'Buzz'
 'Fizz' '37' '38' 'Fizz' 'Buzz' '41' 'Fizz' '43' '44' 'FizzBuzz' '46' '47'
 'Fizz' '49' 'Buzz']

バブルソート

定番のバブルソートもTensorFlowのグラフで実装できます。

from __future__ import print_function
import numpy as np
import tensorflow as tf
np.random.seed(123)
class BubbleSort():
    def __init__(self, array):
        self.i = tf.constant(0)
        self.j = tf.constant(len(array)-1)
        self.array = tf.Variable(array, trainable=False)
        self.length = len(array)

        cond = lambda i, j, _: tf.less(i-1, self.length-1)
        self.graph = tf.while_loop(cond, self.outer_loop, loop_vars=[self.i, self.j, self.array],
                shape_invariants=[self.i.get_shape(), self.j.get_shape(), tf.TensorShape(self.length)],
                parallel_iterations=1,
                back_prop=False)
    def run(self):
        with tf.Session() as sess:
            tf.global_variables_initializer().run()
            return sess.run(self.graph)
    def outer_loop(self, i, j, _):
        cond = lambda i, j, _: tf.greater(j, i)
        loop = tf.while_loop(cond, self.inner_loop, loop_vars=[i, self.length-1, self.array],
                    shape_invariants=[i.get_shape(), j.get_shape(), tf.TensorShape(self.length)],
                    parallel_iterations=1,
                    back_prop=False)
        return tf.add(i, 1), loop[1], loop[2]

    def inner_loop(self, i, j, _):
        body = tf.cond(tf.greater(self.array[j-1], self.array[j]),
                    lambda: tf.scatter_nd_update(self.array, [[j-1],[j]], [self.array[j],self.array[j-1]]),
                    lambda: self.array)
        return i, tf.subtract(j, 1), body

if __name__ == '__main__':
    x = np.array([1.,7.,3.,8.])
    _, _, sorted_array = BubbleSort(x).run()
    print(x)
    print(sorted_array)
    y = np.random.rand(20)
    print(y)
    _, _, sorted_array = BubbleSort(y).run()
    print(sorted_array)

実行結果は以下のとおりです。

[ 1.  7.  3.  8.]
[ 1.  3.  7.  8.]
[ 0.69646919  0.28613933  0.22685145  0.55131477  0.71946897  0.42310646
  0.9807642   0.68482974  0.4809319   0.39211752  0.34317802  0.72904971
  0.43857224  0.0596779   0.39804426  0.73799541  0.18249173  0.17545176
  0.53155137  0.53182759]
[ 0.0596779   0.17545176  0.18249173  0.22685145  0.28613933  0.34317802
  0.39211752  0.39804426  0.42310646  0.43857224  0.4809319   0.53155137
  0.53182759  0.55131477  0.68482974  0.69646919  0.71946897  0.72904971
  0.73799541  0.9807642 ]

BrainF*ck

もちろんプログラミング言語もデータフローグラフで作ることができます。BrainF*ckを実装してみましょう。長くなってしまうので、実行結果だけ示します。BrainF*ckのコードはGithubに公開してあります。

# Code abridged
if __name__ == '__main__':
    src_A = '++++++[> ++++++++++ < -]> +++++.'
    pc, tape, cur, jumps, output = BrainFuck(src_A).run()
    print(output) #=> A

    src_helloworld ='''
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.
'''
    pc, tape, cur, jumps, output = BrainFuck(src_helloworld).run()
    print(output) #=> Hello, world!

クイックソートや2分探索は?

他にも以下のようなアルゴリズムを実装してみたので、興味がある方はGithubのレポジトリを覗いてみてください。


TIPS

データフロープログラミング

データフロープログラミングとは聞き慣れない言葉ですが、手続き型プログラミングやオブジェクト指向プログラミング、関数型プログラミングと肩並べるプログラミングパラダイムの1つでで、データに着目してデータに対する操作の流れを記述していきます。TensorFlowにデータフロープログラミングを採用している背景には並行処理と親和性の高さがあり、マルチコアやマルチプロセッサだけではなく、Googleのような企業が有する何千何万台ものマシンをうまく協調的かつ分散的に計算処理を行いたいという動機があると思われます。

次のサンプルコードで考えてみます。

import tensorflow as tf
import tfgraphviz as tfg

x = tf.Variable(0, name="x")
y = tf.Variable(1, name="y")
a = tf.constant(3, name="a")
b = tf.constant(4, name="b")

mul_op = tf.multiply(a, b, name="mul_op")
assign_x_op = tf.assign(x, mul_op, name="assign_x")
assign_y_1_op = tf.assign_add(y, 1, name="assign_add_y_1")
assign_y_2_op = tf.assign_add(assign_y_1_op, 1, name="assign_add_y_2")
assign_y_3_op = tf.assign_add(assign_y_2_op, 1, name="assign_add_y_3")
assign_y_4_op = tf.assign_add(assign_y_3_op, 1, name="assign_add_y_4")
sum_op = tf.add(assign_x_op, assign_y_2_op, name="sum_op")

sess = tf.Session()
tfg.board(sess.graph)

上のサンプルコードでは、以下の図のようなデータフローグラフが構築されています。あるノードに対する関連する処理が明確になるので、例の変数xに対する処理、変数yに対する処理といったように役割分担が可能になり、並列的に処理を行うことができるようになります。

data-flow-graph.jpg

C言語で同等の処理を書いてみると、以下のようになるかと思います。言語自体の制約としてあるデータとそれに対する処理が入り混じって書けてしまうため、並列に処理するのは難しくなっているようです。

int main() {
    int x = 0, y = 1;
    int mul, sum;
    const int a = 3, b = 4;
    mul = a * b;
    x = mul;
    y++;
    y++;
    sum = x + y;
    y++;
    y++;
    return 0;
}

制御構文

TensorFlowのグラフでは、以下のAPIを使うことで制御構文を記述することができます。

  • tf.cond(...)
  • tf.while_loop(...)
  • (Optional) tf.case(...)

tf.cond(...)

tf.cond(...)はif文に相当するノードです。Bool値を返すノードpredの値に応じて、関数を呼び出します。true_fnflase_fnには、lambdaまたは関数を指定する必要があります。

tf.cond(
    pred,# 条件判定
    true_fn=None, # Trueの場合に呼び出される関数
    false_fn=None, # Falseの場合に呼び出される関数
)

tf-cond.jpg

サンプルコード

import tensorflow as tf
tf.InteractiveSession()
a = tf.constant(3)
b = tf.constant(7)
r = tf.cond(tf.greater(a, b), lambda: a, lambda: b)
r.eval() #=> 7

tf.while_loop(...)

tf.while_loop(
    cond, # 条件判定
    body, # condがTrueの場合に実行される処理
    loop_vars, # condとbodyに渡されるノード
    shape_invariants=None, # tf.while_loop(...)の返り値のshape
)

tf-while-loop.jpg

サンプルコード

以下は公式ドキュメントにあるサンプルコードです。condbodyに渡されるノードiの値が10より小さい時に繰り返してbodyを処理します。

import tensorflow as tf
tf.InteractiveSession()
i = tf.constant(0)
c = lambda i: tf.less(i, 10)
b = lambda i: tf.add(i, 1)
r = tf.while_loop(c, b, [i])
r.eval() #=> 10
tf.cond(
    pred,# Condition
    true_fn=None, # Process to be executed when cond is True
    false_fn=None, # Process to be executed when cond is False
)

値の交換

ソートアルゴリズムを実装する際には、値の交換(スワップ)が必要になります。整列対象となる配列をtf.Variable

import tensorflow as tf
import numpy as np
x = tf.Variable(np.arange(5)) #=> [0, 1, 2, 3, 4]
i = tf.constant(1)
j = tf.constant(4)
# インデックス1と4の要素を交換する
swap = tf.scatter_update(x, [i, j], [x[j], x[i]])
tf.InteractiveSession()
tf.global_variables_initializer().run()
swap.eval() #=> [0, 4, 2, 3, 1]

おわりに

普段見慣れないプログラミングパラダイムですが、パズル感覚でロジックを書けるので面白かったです。データフロープログラミングあたりの部分は、あまり自身がないのでツッコミを入れていただければうれしいです。